NiaPy.algorithms.basic.es.EvolutionStrategyMpL.updateRho() - Code Metrics - Inspection of "Merge pull request #233 from kb2623/development" - NiaOrg/NiaPy - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( cc7745...279fb5 )

by Grega

created 2019-11-12 07:54 UTC

EvolutionStrategyMpL.updateRho() A

↳ Parent: NiaPy.algorithms.basic.es

Complexity

Conditions

Size

Total Lines	12
Code Lines	6

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	5
eloc	6
nop	3
dl	0
loc	12
rs	9.3333
c	0
b	0
f	0

# encoding=utf8
import logging
from math import ceil

from numpy import argmin, argsort, log, sum, fmax, sqrt, full, exp, eye, diag, apply_along_axis, round, any, asarray, dot, random as rand, tile, inf, where, append
from numpy.linalg import norm, cholesky as chol, eig, solve, lstsq

from NiaPy.algorithms.algorithm import Algorithm, Individual, defaultIndividualInit
from NiaPy.util.utility import objects2array

logging.basicConfig()
logger = logging.getLogger('NiaPy.algorithms.basic')
logger.setLevel('INFO')

__all__ = ['EvolutionStrategy1p1', 'EvolutionStrategyMp1', 'EvolutionStrategyMpL', 'EvolutionStrategyML', 'CovarianceMatrixAdaptionEvolutionStrategy']

class IndividualES(Individual):
	r"""Individual for Evolution Strategies.

	See Also:
		* :class:`NiaPy.algorithms.Individual`
	"""
	def __init__(self, **kwargs):
		r"""Initialize individual.

		Args:
			kwargs (Dict[str, Any]): Additional arguments.

		See Also:
			* :func:`NiaPy.algorithms.Individual.__init__`
		"""
		Individual.__init__(self, **kwargs)
		self.rho = kwargs.get('rho', 1)

class EvolutionStrategy1p1(Algorithm):
	r"""Implementation of (1 + 1) evolution strategy algorithm. Uses just one individual.

	Algorithm:
		(1 + 1) Evolution Strategy Algorithm

	Date:
		2018

	Authors:
		Klemen Berkovič

	License:
		MIT

	Reference URL:

	Reference paper:

	Attributes:
		Name (List[str]): List of strings representing algorithm names.
		mu (int): Number of parents.
		k (int): Number of iterations before checking and fixing rho.
		c_a (float): Search range amplification factor.
		c_r (float): Search range reduction factor.

	See Also:
		* :class:`NiaPy.algorithms.Algorithm`
	"""
	Name = ['EvolutionStrategy1p1', 'EvolutionStrategy(1+1)', 'ES(1+1)']

	@staticmethod

	def typeParameters():
		r"""Get dictionary with functions for checking values of parameters.

		Returns:
			Dict[str, Callable]:
				* mu (Callable[[int], bool])
				* k (Callable[[int], bool])
				* c_a (Callable[[Union[float, int]], bool])
				* c_r (Callable[[Union[float, int]], bool])
				* epsilon (Callable[[float], bool])
		"""
		return {
			'mu': lambda x: isinstance(x, int) and x > 0,
			'k': lambda x: isinstance(x, int) and x > 0,
			'c_a': lambda x: isinstance(x, (float, int)) and x > 1,
			'c_r': lambda x: isinstance(x, (float, int)) and 0 < x < 1,
			'epsilon': lambda x: isinstance(x, float) and 0 < x < 1
		}

	def setParameters(self, mu=1, k=10, c_a=1.1, c_r=0.5, epsilon=1e-20, **ukwargs):
		r"""Set the arguments of an algorithm.

		Arguments:
			mu (Optional[int]): Number of parents
			k (Optional[int]): Number of iterations before checking and fixing rho
			c_a (Optional[float]): Search range amplification factor
			c_r (Optional[float]): Search range reduction factor

		See Also:
			* :func:`NiaPy.algorithms.Algorithm.setParameters`
		"""
		Algorithm.setParameters(self, NP=mu, itype=ukwargs.pop('itype', IndividualES), **ukwargs)
		self.mu, self.k, self.c_a, self.c_r, self.epsilon = mu, k, c_a, c_r, epsilon

	def mutate(self, x, rho):
		r"""Mutate individual.

		Args:
			x (Individual): Current individual.
			rho (float): Current standard deviation.

		Returns:
			Individual: Mutated individual.
		"""
		return x + self.normal(0, rho, len(x))

	def updateRho(self, rho, k):
		r"""Update standard deviation.

		Args:
			rho (float): Current standard deviation.
			k (int): Number of succesfull mutations.

		Returns:
			float: New standard deviation.
		"""
		phi = k / self.k
		if phi < 0.2: return self.c_r * rho if rho > self.epsilon else 1
		elif phi > 0.2: return self.c_a * rho if rho > self.epsilon else 1
		else: return rho

	def initPopulation(self, task):
		r"""Initialize starting individual.

		Args:
			task (Task): Optimization task.

		Returns:
			Tuple[Individual, float, Dict[str, Any]]:
				1, Initialized individual.
				2, Initialized individual fitness/function value.
				3. Additional arguments:
					* ki (int): Number of successful rho update.
		"""
		c, ki = IndividualES(task=task, rnd=self.Rand), 0
		return c, c.f, {'ki': ki}

	def runIteration(self, task, c, fpop, xb, fxb, ki, **dparams):
		r"""Core function of EvolutionStrategy(1+1) algorithm.

		Args:
			task (Task): Optimization task.
			pop (Individual): Current position.
			fpop (float): Current position function/fitness value.
			xb (Individual): Global best position.
			fxb (float): Global best function/fitness value.
			ki (int): Number of successful updates before rho update.
			**dparams (Dict[str, Any]): Additional arguments.

		Returns:
			Tuple[Individual, float, Individual, float, Dict[str, Any]]:
				1, Initialized individual.
				2, Initialized individual fitness/function value.
				3. New global best solution.
				4. New global best soluitons fitness/objective value.
				5. Additional arguments:
					* ki (int): Number of successful rho update.
		"""
		if task.Iters % self.k == 0: c.rho, ki = self.updateRho(c.rho, ki), 0
		cn = objects2array([task.repair(self.mutate(c.x, c.rho), self.Rand) for _i in range(self.mu)])
		cn_f = asarray([task.eval(cn[i]) for i in range(len(cn))])
		ib = argmin(cn_f)
		if cn_f[ib] < c.f:
			c.x, c.f, ki = cn[ib], cn_f[ib], ki + 1
			if cn_f[ib] < fxb: xb, fxb = self.getBest(cn[ib], cn_f[ib], xb, fxb)
		return c, c.f, xb, fxb, {'ki': ki}

class EvolutionStrategyMp1(EvolutionStrategy1p1):
	r"""Implementation of (mu + 1) evolution strategy algorithm. Algorithm creates mu mutants but into new generation goes only one individual.

	Algorithm:
		(:math:`\mu + 1`) Evolution Strategy Algorithm

	Date:
		2018

	Authors:
		Klemen Berkovič

	License:
		MIT

	Reference URL:

	Reference paper:

	Attributes:
		Name (List[str]): List of strings representing algorithm names.

	See Also:
		* :class:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
	"""
	Name = ['EvolutionStrategyMp1', 'EvolutionStrategy(mu+1)', 'ES(m+1)']

	def setParameters(self, **kwargs):
		r"""Set core parameters of EvolutionStrategy(mu+1) algorithm.

		Args:
			**kwargs (Dict[str, Any]):

		See Also:
			* :func:`NiaPy.algorithms.basic.EvolutionStrategy1p1.setParameters`
		"""
		mu = kwargs.pop('mu', 40)
		EvolutionStrategy1p1.setParameters(self, mu=mu, **kwargs)

class EvolutionStrategyMpL(EvolutionStrategy1p1):
	r"""Implementation of (mu + lambda) evolution strategy algorithm. Mulation creates lambda individual. Lambda individual compete with mu individuals for survival, so only mu individual go to new generation.

	Algorithm:
		(:math:`\mu + \lambda`) Evolution Strategy Algorithm

	Date:
		2018

	Authors:
		Klemen Berkovič

	License:
		MIT

	Reference URL:

	Reference paper:

	Attributes:
		Name (List[str]): List of strings representing algorithm names
		lam (int): TODO

	See Also:
		* :class:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
	"""
	Name = ['EvolutionStrategyMpL', 'EvolutionStrategy(mu+lambda)', 'ES(m+l)']

	@staticmethod
	def typeParameters():
		r"""TODO.

		Returns:
			Dict[str, Any]:
				* lam (Callable[[int], bool]): TODO.

		See Also:
			* :func:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
		"""
		d = EvolutionStrategy1p1.typeParameters()
		d['lam'] = lambda x: isinstance(x, int) and x > 0
		return d

	def setParameters(self, lam=45, **ukwargs):
		r"""Set the arguments of an algorithm.

		Arguments:
			lam (int): Number of new individual generated by mutation.

		See Also:
			* :func:`NiaPy.algorithms.basic.es.EvolutionStrategy1p1.setParameters`
		"""
		EvolutionStrategy1p1.setParameters(self, InitPopFunc=defaultIndividualInit, **ukwargs)
		self.lam = lam

	def updateRho(self, pop, k):
		r"""Update standard deviation for population.

		Args:
			pop (numpy.ndarray[Individual]): Current population.
			k (int): Number of successful mutations.
		"""
		phi = k / self.k
		if phi < 0.2:
			for i in pop: i.rho = self.c_r * i.rho
		elif phi > 0.2:
			for i in pop: i.rho = self.c_a * i.rho

	def changeCount(self, c, cn):
		r"""Update number of successful mutations for population.

		Args:
			c (numpy.ndarray[Individual]): Current population.
			cn (numpy.ndarray[Individual]): New population.

		Returns:
			int: Number of successful mutations.
		"""
		k = 0
		for e in cn:
			if e not in c: k += 1
		return k

	def mutateRand(self, pop, task):
		r"""Mutate random individual form population.

		Args:
			pop (numpy.ndarray[Individual]): Current population.
			task (Task): Optimization task.

		Returns:
			numpy.ndarray: Random individual from population that was mutated.
		"""
		i = self.randint(self.mu)
		return task.repair(self.mutate(pop[i].x, pop[i].rho), rnd=self.Rand)

	def initPopulation(self, task):
		r"""Initialize starting population.

		Args:
			task (Task): Optimization task.

		Returns:
			Tuple[numpy.ndarray[Individual], numpy.ndarray[float], Dict[str, Any]]:
				1. Initialized populaiton.
				2. Initialized populations function/fitness values.
				3. Additional arguments:
					* ki (int): Number of successful mutations.

		See Also:
			* :func:`NiaPy.algorithms.algorithm.Algorithm.initPopulation`
		"""
		c, fc, d = Algorithm.initPopulation(self, task)
		d.update({'ki': 0})
		return c, fc, d

	def runIteration(self, task, c, fpop, xb, fxb, ki, **dparams):
		r"""Core function of EvolutionStrategyMpL algorithm.

		Args:
			task (Task): Optimization task.
			c (numpy.ndarray): Current population.
			fpop (numpy.ndarray): Current populations fitness/function values.
			xb (numpy.ndarray): Global best individual.
			fxb (float): Global best individuals fitness/function value.
			ki (int): Number of successful mutations.
			**dparams (Dict[str, Any]): Additional arguments.

		Returns:
			Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, float, Dict[str, Any]]:
				1. New population.
				2. New populations function/fitness values.
				3. New global best solution.
				4. New global best solutions fitness/objective value.
				5. Additional arguments:
					* ki (int): Number of successful mutations.
		"""
		if task.Iters % self.k == 0: _, ki = self.updateRho(c, ki), 0
		cn = objects2array([IndividualES(x=self.mutateRand(c, task), task=task, rnd=self.Rand) for _ in range(self.lam)])
		cn = append(cn, c)
		cn = objects2array([cn[i] for i in argsort([i.f for i in cn])[:self.mu]])
		ki += self.changeCount(c, cn)
		fcn = asarray([x.f for x in cn])
		xb, fxb = self.getBest(cn, fcn, xb, fxb)
		return cn, fcn, xb, fxb, {'ki': ki}

class EvolutionStrategyML(EvolutionStrategyMpL):
	r"""Implementation of (mu, lambda) evolution strategy algorithm. Algorithm is good for dynamic environments. Mu individual create lambda chields. Only best mu chields go to new generation. Mu parents are discarded.

	Algorithm:
		(:math:`\mu + \lambda`) Evolution Strategy Algorithm

	Date:
		2018

	Authors:
		Klemen Berkovič

	License:
		MIT

	Reference URL:

	Reference paper:

	Attributes:
		Name (List[str]): List of strings representing algorithm names

	See Also:
		* :class:`NiaPy.algorithm.basic.es.EvolutionStrategyMpL`
	"""
	Name = ['EvolutionStrategyML', 'EvolutionStrategy(mu,lambda)', 'ES(m,l)']

	def newPop(self, pop):
		r"""Return new population.

		Args:
			pop (numpy.ndarray): Current population.

		Returns:
			numpy.ndarray: New population.
		"""
		pop_s = argsort([i.f for i in pop])
		if self.mu < self.lam: return objects2array([pop[i] for i in pop_s[:self.mu]])
		npop = list()
		for i in range(int(ceil(float(self.mu) / self.lam))): npop.extend(pop[:self.lam if (self.mu - i * self.lam) >= self.lam else self.mu - i * self.lam])
		return objects2array(npop)

	def initPopulation(self, task):
		r"""Initialize starting population.

		Args:
			task (Task): Optimization task.

		Returns:
			Tuple[numpy.ndarray[Individual], numpy.ndarray[float], Dict[str, Any]]:
				1. Initialized population.
				2. Initialized populations fitness/function values.
				2. Additional arguments.

		See Also:
			* :func:`NiaPy.algorithm.basic.es.EvolutionStrategyMpL.initPopulation`
		"""
		c, fc, _ = EvolutionStrategyMpL.initPopulation(self, task)
		return c, fc, {}

	def runIteration(self, task, c, fpop, xb, fxb, **dparams):
		r"""Core function of EvolutionStrategyML algorithm.

		Args:
			task (Task): Optimization task.
			c (numpy.ndarray): Current population.
			fpop (numpy.ndarray): Current population fitness/function values.
			xb (numpy.ndarray): Global best individual.
			fxb (float): Global best individuals fitness/function value.
			**dparams Dict[str, Any]: Additional arguments.

		Returns:
			Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, float, Dict[str, Any]]:
				1. New population.
				2. New populations fitness/function values.
				3. New global best solution.
				4. New global best solutions fitness/objective value.
				5. Additional arguments.
		"""
		cn = objects2array([IndividualES(x=self.mutateRand(c, task), task=task, rand=self.Rand) for _ in range(self.lam)])
		c = self.newPop(cn)
		fc = asarray([x.f for x in c])
		xb, fxb = self.getBest(c, fc, xb, fxb)
		return c, fc, xb, fxb, {}

def CovarianceMaatrixAdaptionEvolutionStrategyF(task, epsilon=1e-20, rnd=rand):
	lam, alpha_mu, hs, sigma0 = (4 + round(3 * log(task.D))) * 10, 2, 0, 0.3 * task.bcRange()
	mu = int(round(lam / 2))
	w = log(mu + 0.5) - log(range(1, mu + 1))
	w = w / sum(w)
	mueff = 1 / sum(w ** 2)
	cs = (mueff + 2) / (task.D + mueff + 5)
	ds = 1 + cs + 2 * max(sqrt((mueff - 1) / (task.D + 1)) - 1, 0)
	ENN = sqrt(task.D) * (1 - 1 / (4 * task.D) + 1 / (21 * task.D ** 2))
	cc, c1 = (4 + mueff / task.D) / (4 + task.D + 2 * mueff / task.D), 2 / ((task.D + 1.3) ** 2 + mueff)
	cmu, hth = min(1 - c1, alpha_mu * (mueff - 2 + 1 / mueff) / ((task.D + 2) ** 2 + alpha_mu * mueff / 2)), (1.4 + 2 / (task.D + 1)) * ENN
	ps, pc, C, sigma, M = full(task.D, 0.0), full(task.D, 0.0), eye(task.D), sigma0, full(task.D, 0.0)
	x = rnd.uniform(task.bcLower(), task.bcUpper())
	x_f = task.eval(x)
	while not task.stopCondI():
		pop_step = asarray([rnd.multivariate_normal(full(task.D, 0.0), C) for _ in range(int(lam))])
		pop = asarray([task.repair(x + sigma * ps, rnd) for ps in pop_step])
		pop_f = apply_along_axis(task.eval, 1, pop)
		isort = argsort(pop_f)
		pop, pop_f, pop_step = pop[isort[:mu]], pop_f[isort[:mu]], pop_step[isort[:mu]]
		if pop_f[0] < x_f: x, x_f = pop[0], pop_f[0]
		M = sum(w * pop_step.T, axis=1)
		ps = solve(chol(C).conj() + epsilon, ((1 - cs) * ps + sqrt(cs * (2 - cs) * mueff) * M + epsilon).T)[0].T
		sigma *= exp(cs / ds * (norm(ps) / ENN - 1)) ** 0.3
		ifix = where(sigma == inf)
		if any(ifix): sigma[ifix] = sigma0
		if norm(ps) / sqrt(1 - (1 - cs) ** (2 * (task.Iters + 1))) < hth: hs = 1
		else: hs = 0
		delta = (1 - hs) * cc * (2 - cc)
		pc = (1 - cc) * pc + hs * sqrt(cc * (2 - cc) * mueff) * M
		C = (1 - c1 - cmu) * C + c1 * (tile(pc, [len(pc), 1]) * tile(pc.reshape([len(pc), 1]), [1, len(pc)]) + delta * C)
		for i in range(mu): C += cmu * w[i] * tile(pop_step[i], [len(pop_step[i]), 1]) * tile(pop_step[i].reshape([len(pop_step[i]), 1]), [1, len(pop_step[i])])
		E, V = eig(C)
		if any(E < epsilon):
			E = fmax(E, 0)
			C = lstsq(V.T, dot(V, diag(E)).T, rcond=None)[0].T
	return x, x_f

class CovarianceMatrixAdaptionEvolutionStrategy(Algorithm):
	r"""Implementation of (mu, lambda) evolution strategy algorithm. Algorithm is good for dynamic environments. Mu individual create lambda chields. Only best mu chields go to new generation. Mu parents are discarded.

	Algorithm:
		(:math:`\mu + \lambda`) Evolution Strategy Algorithm

	Date:
		2018

	Authors:
		Klemen Berkovič

	License:
		MIT

	Reference URL:
		https://arxiv.org/abs/1604.00772

	Reference paper:
		Hansen, Nikolaus. "The CMA evolution strategy: A tutorial." arXiv preprint arXiv:1604.00772 (2016).

	Attributes:
		Name (List[str]): List of names representing algorithm names
		epsilon (float): TODO
	"""
	Name = ['CovarianceMatrixAdaptionEvolutionStrategy', 'CMA-ES', 'CMAES']
	epsilon = 1e-20

	@staticmethod
	def typeParameters(): return {
			'epsilon': lambda x: isinstance(x, (float, int)) and 0 < x < 1
	}

	def setParameters(self, epsilon=1e-20, **ukwargs):
		r"""Set core parameters of CovarianceMatrixAdaptionEvolutionStrategy algorithm.

		Args:
			epsilon (float): Small number.
			**ukwargs (Dict[str, Any]): Additional arguments.
		"""
		Algorithm.setParameters(self, **ukwargs)
		self.epsilon = epsilon

	def runTask(self, task):
		r"""TODO.

		Args:
			task (Task): Optimization task.

		Returns:
			TODO.
		"""
		return CovarianceMaatrixAdaptionEvolutionStrategyF(task, self.epsilon, rnd=self.Rand)

# vim: tabstop=3 noexpandtab shiftwidth=3 softtabstop=3


1		# encoding=utf8
2		import logging
3		from math import ceil
4
5		from numpy import argmin, argsort, log, sum, fmax, sqrt, full, exp, eye, diag, apply_along_axis, round, any, asarray, dot, random as rand, tile, inf, where, append
6		from numpy.linalg import norm, cholesky as chol, eig, solve, lstsq
7
8		from NiaPy.algorithms.algorithm import Algorithm, Individual, defaultIndividualInit
9		from NiaPy.util.utility import objects2array
10
11		logging.basicConfig()
12		logger = logging.getLogger('NiaPy.algorithms.basic')
13		logger.setLevel('INFO')
14
15		__all__ = ['EvolutionStrategy1p1', 'EvolutionStrategyMp1', 'EvolutionStrategyMpL', 'EvolutionStrategyML', 'CovarianceMatrixAdaptionEvolutionStrategy']
16
17		class IndividualES(Individual):
18		r"""Individual for Evolution Strategies.
19
20		See Also:
21		* :class:`NiaPy.algorithms.Individual`
22		"""
23		def __init__(self, **kwargs):
24		r"""Initialize individual.
25
26		Args:
27		kwargs (Dict[str, Any]): Additional arguments.
28
29		See Also:
30		* :func:`NiaPy.algorithms.Individual.__init__`
31		"""
32		Individual.__init__(self, **kwargs)
33		self.rho = kwargs.get('rho', 1)
34
35		class EvolutionStrategy1p1(Algorithm):
36		r"""Implementation of (1 + 1) evolution strategy algorithm. Uses just one individual.
37
38		Algorithm:
39		(1 + 1) Evolution Strategy Algorithm
40
41		Date:
42		2018
43
44		Authors:
45		Klemen Berkovič
46
47		License:
48		MIT
49
50		Reference URL:
51
52		Reference paper:
53
54		Attributes:
55		Name (List[str]): List of strings representing algorithm names.
56		mu (int): Number of parents.
57		k (int): Number of iterations before checking and fixing rho.
58		c_a (float): Search range amplification factor.
59		c_r (float): Search range reduction factor.
60
61		See Also:
62		* :class:`NiaPy.algorithms.Algorithm`
63		"""
64		Name = ['EvolutionStrategy1p1', 'EvolutionStrategy(1+1)', 'ES(1+1)']
65
66	View Code Duplication	@staticmethod
		0 ignored issues – show Duplication introduced 2019-11-10 16:54 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
67		def typeParameters():
68		r"""Get dictionary with functions for checking values of parameters.
69
70		Returns:
71		Dict[str, Callable]:
72		* mu (Callable[[int], bool])
73		* k (Callable[[int], bool])
74		* c_a (Callable[[Union[float, int]], bool])
75		* c_r (Callable[[Union[float, int]], bool])
76		* epsilon (Callable[[float], bool])
77		"""
78		return {
79		'mu': lambda x: isinstance(x, int) and x > 0,
80		'k': lambda x: isinstance(x, int) and x > 0,
81		'c_a': lambda x: isinstance(x, (float, int)) and x > 1,
82		'c_r': lambda x: isinstance(x, (float, int)) and 0 < x < 1,
83		'epsilon': lambda x: isinstance(x, float) and 0 < x < 1
84		}
85
86		def setParameters(self, mu=1, k=10, c_a=1.1, c_r=0.5, epsilon=1e-20, **ukwargs):
87		r"""Set the arguments of an algorithm.
88
89		Arguments:
90		mu (Optional[int]): Number of parents
91		k (Optional[int]): Number of iterations before checking and fixing rho
92		c_a (Optional[float]): Search range amplification factor
93		c_r (Optional[float]): Search range reduction factor
94
95		See Also:
96		* :func:`NiaPy.algorithms.Algorithm.setParameters`
97		"""
98		Algorithm.setParameters(self, NP=mu, itype=ukwargs.pop('itype', IndividualES), **ukwargs)
99		self.mu, self.k, self.c_a, self.c_r, self.epsilon = mu, k, c_a, c_r, epsilon
100
101		def mutate(self, x, rho):
102		r"""Mutate individual.
103
104		Args:
105		x (Individual): Current individual.
106		rho (float): Current standard deviation.
107
108		Returns:
109		Individual: Mutated individual.
110		"""
111		return x + self.normal(0, rho, len(x))
112
113		def updateRho(self, rho, k):
114		r"""Update standard deviation.
115
116		Args:
117		rho (float): Current standard deviation.
118		k (int): Number of succesfull mutations.
119
120		Returns:
121		float: New standard deviation.
122		"""
123		phi = k / self.k
124		if phi < 0.2: return self.c_r * rho if rho > self.epsilon else 1
125		elif phi > 0.2: return self.c_a * rho if rho > self.epsilon else 1
126		else: return rho
127
128		def initPopulation(self, task):
129		r"""Initialize starting individual.
130
131		Args:
132		task (Task): Optimization task.
133
134		Returns:
135		Tuple[Individual, float, Dict[str, Any]]:
136		1, Initialized individual.
137		2, Initialized individual fitness/function value.
138		3. Additional arguments:
139		* ki (int): Number of successful rho update.
140		"""
141		c, ki = IndividualES(task=task, rnd=self.Rand), 0
142		return c, c.f, {'ki': ki}
143
144		def runIteration(self, task, c, fpop, xb, fxb, ki, **dparams):
145		r"""Core function of EvolutionStrategy(1+1) algorithm.
146
147		Args:
148		task (Task): Optimization task.
149		pop (Individual): Current position.
150		fpop (float): Current position function/fitness value.
151		xb (Individual): Global best position.
152		fxb (float): Global best function/fitness value.
153		ki (int): Number of successful updates before rho update.
154		**dparams (Dict[str, Any]): Additional arguments.
155
156		Returns:
157		Tuple[Individual, float, Individual, float, Dict[str, Any]]:
158		1, Initialized individual.
159		2, Initialized individual fitness/function value.
160		3. New global best solution.
161		4. New global best soluitons fitness/objective value.
162		5. Additional arguments:
163		* ki (int): Number of successful rho update.
164		"""
165		if task.Iters % self.k == 0: c.rho, ki = self.updateRho(c.rho, ki), 0
166		cn = objects2array([task.repair(self.mutate(c.x, c.rho), self.Rand) for _i in range(self.mu)])
167		cn_f = asarray([task.eval(cn[i]) for i in range(len(cn))])
168		ib = argmin(cn_f)
169		if cn_f[ib] < c.f:
170		c.x, c.f, ki = cn[ib], cn_f[ib], ki + 1
171		if cn_f[ib] < fxb: xb, fxb = self.getBest(cn[ib], cn_f[ib], xb, fxb)
172		return c, c.f, xb, fxb, {'ki': ki}
173
174		class EvolutionStrategyMp1(EvolutionStrategy1p1):
175		r"""Implementation of (mu + 1) evolution strategy algorithm. Algorithm creates mu mutants but into new generation goes only one individual.
176
177		Algorithm:
178		(:math:`\mu + 1`) Evolution Strategy Algorithm
179
180		Date:
181		2018
182
183		Authors:
184		Klemen Berkovič
185
186		License:
187		MIT
188
189		Reference URL:
190
191		Reference paper:
192
193		Attributes:
194		Name (List[str]): List of strings representing algorithm names.
195
196		See Also:
197		* :class:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
198		"""
199		Name = ['EvolutionStrategyMp1', 'EvolutionStrategy(mu+1)', 'ES(m+1)']
200
201		def setParameters(self, **kwargs):
202		r"""Set core parameters of EvolutionStrategy(mu+1) algorithm.
203
204		Args:
205		**kwargs (Dict[str, Any]):
206
207		See Also:
208		* :func:`NiaPy.algorithms.basic.EvolutionStrategy1p1.setParameters`
209		"""
210		mu = kwargs.pop('mu', 40)
211		EvolutionStrategy1p1.setParameters(self, mu=mu, **kwargs)
212
213		class EvolutionStrategyMpL(EvolutionStrategy1p1):
214		r"""Implementation of (mu + lambda) evolution strategy algorithm. Mulation creates lambda individual. Lambda individual compete with mu individuals for survival, so only mu individual go to new generation.
215
216		Algorithm:
217		(:math:`\mu + \lambda`) Evolution Strategy Algorithm
218
219		Date:
220		2018
221
222		Authors:
223		Klemen Berkovič
224
225		License:
226		MIT
227
228		Reference URL:
229
230		Reference paper:
231
232		Attributes:
233		Name (List[str]): List of strings representing algorithm names
234		lam (int): TODO
235
236		See Also:
237		* :class:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
238		"""
239		Name = ['EvolutionStrategyMpL', 'EvolutionStrategy(mu+lambda)', 'ES(m+l)']
240
241		@staticmethod
242		def typeParameters():
243		r"""TODO.
244
245		Returns:
246		Dict[str, Any]:
247		* lam (Callable[[int], bool]): TODO.
248
249		See Also:
250		* :func:`NiaPy.algorithms.basic.EvolutionStrategy1p1`
251		"""
252		d = EvolutionStrategy1p1.typeParameters()
253		d['lam'] = lambda x: isinstance(x, int) and x > 0
254		return d
255
256		def setParameters(self, lam=45, **ukwargs):
257		r"""Set the arguments of an algorithm.
258
259		Arguments:
260		lam (int): Number of new individual generated by mutation.
261
262		See Also:
263		* :func:`NiaPy.algorithms.basic.es.EvolutionStrategy1p1.setParameters`
264		"""
265		EvolutionStrategy1p1.setParameters(self, InitPopFunc=defaultIndividualInit, **ukwargs)
266		self.lam = lam
267
268		def updateRho(self, pop, k):
269		r"""Update standard deviation for population.
270
271		Args:
272		pop (numpy.ndarray[Individual]): Current population.
273		k (int): Number of successful mutations.
274		"""
275		phi = k / self.k
276		if phi < 0.2:
277		for i in pop: i.rho = self.c_r * i.rho
278		elif phi > 0.2:
279		for i in pop: i.rho = self.c_a * i.rho
280
281		def changeCount(self, c, cn):
282		r"""Update number of successful mutations for population.
283
284		Args:
285		c (numpy.ndarray[Individual]): Current population.
286		cn (numpy.ndarray[Individual]): New population.
287
288		Returns:
289		int: Number of successful mutations.
290		"""
291		k = 0
292		for e in cn:
293		if e not in c: k += 1
294		return k
295
296		def mutateRand(self, pop, task):
297		r"""Mutate random individual form population.
298
299		Args:
300		pop (numpy.ndarray[Individual]): Current population.
301		task (Task): Optimization task.
302
303		Returns:
304		numpy.ndarray: Random individual from population that was mutated.
305		"""
306		i = self.randint(self.mu)
307		return task.repair(self.mutate(pop[i].x, pop[i].rho), rnd=self.Rand)
308
309		def initPopulation(self, task):
310		r"""Initialize starting population.
311
312		Args:
313		task (Task): Optimization task.
314
315		Returns:
316		Tuple[numpy.ndarray[Individual], numpy.ndarray[float], Dict[str, Any]]:
317		1. Initialized populaiton.
318		2. Initialized populations function/fitness values.
319		3. Additional arguments:
320		* ki (int): Number of successful mutations.
321
322		See Also:
323		* :func:`NiaPy.algorithms.algorithm.Algorithm.initPopulation`
324		"""
325		c, fc, d = Algorithm.initPopulation(self, task)
326		d.update({'ki': 0})
327		return c, fc, d
328
329		def runIteration(self, task, c, fpop, xb, fxb, ki, **dparams):
330		r"""Core function of EvolutionStrategyMpL algorithm.
331
332		Args:
333		task (Task): Optimization task.
334		c (numpy.ndarray): Current population.
335		fpop (numpy.ndarray): Current populations fitness/function values.
336		xb (numpy.ndarray): Global best individual.
337		fxb (float): Global best individuals fitness/function value.
338		ki (int): Number of successful mutations.
339		**dparams (Dict[str, Any]): Additional arguments.
340
341		Returns:
342		Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, float, Dict[str, Any]]:
343		1. New population.
344		2. New populations function/fitness values.
345		3. New global best solution.
346		4. New global best solutions fitness/objective value.
347		5. Additional arguments:
348		* ki (int): Number of successful mutations.
349		"""
350		if task.Iters % self.k == 0: _, ki = self.updateRho(c, ki), 0
351		cn = objects2array([IndividualES(x=self.mutateRand(c, task), task=task, rnd=self.Rand) for _ in range(self.lam)])
352		cn = append(cn, c)
353		cn = objects2array([cn[i] for i in argsort([i.f for i in cn])[:self.mu]])
354		ki += self.changeCount(c, cn)
355		fcn = asarray([x.f for x in cn])
356		xb, fxb = self.getBest(cn, fcn, xb, fxb)
357		return cn, fcn, xb, fxb, {'ki': ki}
358
359		class EvolutionStrategyML(EvolutionStrategyMpL):
360		r"""Implementation of (mu, lambda) evolution strategy algorithm. Algorithm is good for dynamic environments. Mu individual create lambda chields. Only best mu chields go to new generation. Mu parents are discarded.
361
362		Algorithm:
363		(:math:`\mu + \lambda`) Evolution Strategy Algorithm
364
365		Date:
366		2018
367
368		Authors:
369		Klemen Berkovič
370
371		License:
372		MIT
373
374		Reference URL:
375
376		Reference paper:
377
378		Attributes:
379		Name (List[str]): List of strings representing algorithm names
380
381		See Also:
382		* :class:`NiaPy.algorithm.basic.es.EvolutionStrategyMpL`
383		"""
384		Name = ['EvolutionStrategyML', 'EvolutionStrategy(mu,lambda)', 'ES(m,l)']
385
386		def newPop(self, pop):
387		r"""Return new population.
388
389		Args:
390		pop (numpy.ndarray): Current population.
391
392		Returns:
393		numpy.ndarray: New population.
394		"""
395		pop_s = argsort([i.f for i in pop])
396		if self.mu < self.lam: return objects2array([pop[i] for i in pop_s[:self.mu]])
397		npop = list()
398		for i in range(int(ceil(float(self.mu) / self.lam))): npop.extend(pop[:self.lam if (self.mu - i * self.lam) >= self.lam else self.mu - i * self.lam])
399		return objects2array(npop)
400
401		def initPopulation(self, task):
402		r"""Initialize starting population.
403
404		Args:
405		task (Task): Optimization task.
406
407		Returns:
408		Tuple[numpy.ndarray[Individual], numpy.ndarray[float], Dict[str, Any]]:
409		1. Initialized population.
410		2. Initialized populations fitness/function values.
411		2. Additional arguments.
412
413		See Also:
414		* :func:`NiaPy.algorithm.basic.es.EvolutionStrategyMpL.initPopulation`
415		"""
416		c, fc, _ = EvolutionStrategyMpL.initPopulation(self, task)
417		return c, fc, {}
418
419		def runIteration(self, task, c, fpop, xb, fxb, **dparams):
420		r"""Core function of EvolutionStrategyML algorithm.
421
422		Args:
423		task (Task): Optimization task.
424		c (numpy.ndarray): Current population.
425		fpop (numpy.ndarray): Current population fitness/function values.
426		xb (numpy.ndarray): Global best individual.
427		fxb (float): Global best individuals fitness/function value.
428		**dparams Dict[str, Any]: Additional arguments.
429
430		Returns:
431		Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, float, Dict[str, Any]]:
432		1. New population.
433		2. New populations fitness/function values.
434		3. New global best solution.
435		4. New global best solutions fitness/objective value.
436		5. Additional arguments.
437		"""
438		cn = objects2array([IndividualES(x=self.mutateRand(c, task), task=task, rand=self.Rand) for _ in range(self.lam)])
439		c = self.newPop(cn)
440		fc = asarray([x.f for x in c])
441		xb, fxb = self.getBest(c, fc, xb, fxb)
442		return c, fc, xb, fxb, {}
443
444		def CovarianceMaatrixAdaptionEvolutionStrategyF(task, epsilon=1e-20, rnd=rand):
445		lam, alpha_mu, hs, sigma0 = (4 + round(3 * log(task.D))) * 10, 2, 0, 0.3 * task.bcRange()
446		mu = int(round(lam / 2))
447		w = log(mu + 0.5) - log(range(1, mu + 1))
448		w = w / sum(w)
449		mueff = 1 / sum(w ** 2)
450		cs = (mueff + 2) / (task.D + mueff + 5)
451		ds = 1 + cs + 2 * max(sqrt((mueff - 1) / (task.D + 1)) - 1, 0)
452		ENN = sqrt(task.D) * (1 - 1 / (4 * task.D) + 1 / (21 * task.D ** 2))
453		cc, c1 = (4 + mueff / task.D) / (4 + task.D + 2 * mueff / task.D), 2 / ((task.D + 1.3) ** 2 + mueff)
454		cmu, hth = min(1 - c1, alpha_mu * (mueff - 2 + 1 / mueff) / ((task.D + 2) ** 2 + alpha_mu * mueff / 2)), (1.4 + 2 / (task.D + 1)) * ENN
455		ps, pc, C, sigma, M = full(task.D, 0.0), full(task.D, 0.0), eye(task.D), sigma0, full(task.D, 0.0)
456		x = rnd.uniform(task.bcLower(), task.bcUpper())
457		x_f = task.eval(x)
458		while not task.stopCondI():
459		pop_step = asarray([rnd.multivariate_normal(full(task.D, 0.0), C) for _ in range(int(lam))])
460		pop = asarray([task.repair(x + sigma * ps, rnd) for ps in pop_step])
461		pop_f = apply_along_axis(task.eval, 1, pop)
462		isort = argsort(pop_f)
463		pop, pop_f, pop_step = pop[isort[:mu]], pop_f[isort[:mu]], pop_step[isort[:mu]]
464		if pop_f[0] < x_f: x, x_f = pop[0], pop_f[0]
465		M = sum(w * pop_step.T, axis=1)
466		ps = solve(chol(C).conj() + epsilon, ((1 - cs) * ps + sqrt(cs * (2 - cs) * mueff) * M + epsilon).T)[0].T
467		sigma = exp(cs / ds (norm(ps) / ENN - 1)) ** 0.3
468		ifix = where(sigma == inf)
469		if any(ifix): sigma[ifix] = sigma0
470		if norm(ps) / sqrt(1 - (1 - cs) ** (2 * (task.Iters + 1))) < hth: hs = 1
471		else: hs = 0
472		delta = (1 - hs) * cc * (2 - cc)
473		pc = (1 - cc) * pc + hs * sqrt(cc * (2 - cc) * mueff) * M
474		C = (1 - c1 - cmu) * C + c1 * (tile(pc, [len(pc), 1]) * tile(pc.reshape([len(pc), 1]), [1, len(pc)]) + delta * C)
475		for i in range(mu): C += cmu * w[i] * tile(pop_step[i], [len(pop_step[i]), 1]) * tile(pop_step[i].reshape([len(pop_step[i]), 1]), [1, len(pop_step[i])])
476		E, V = eig(C)
477		if any(E < epsilon):
478		E = fmax(E, 0)
479		C = lstsq(V.T, dot(V, diag(E)).T, rcond=None)[0].T
480		return x, x_f
481
482		class CovarianceMatrixAdaptionEvolutionStrategy(Algorithm):
483		r"""Implementation of (mu, lambda) evolution strategy algorithm. Algorithm is good for dynamic environments. Mu individual create lambda chields. Only best mu chields go to new generation. Mu parents are discarded.
484
485		Algorithm:
486		(:math:`\mu + \lambda`) Evolution Strategy Algorithm
487
488		Date:
489		2018
490
491		Authors:
492		Klemen Berkovič
493
494		License:
495		MIT
496
497		Reference URL:
498		https://arxiv.org/abs/1604.00772
499
500		Reference paper:
501		Hansen, Nikolaus. "The CMA evolution strategy: A tutorial." arXiv preprint arXiv:1604.00772 (2016).
502
503		Attributes:
504		Name (List[str]): List of names representing algorithm names
505		epsilon (float): TODO
506		"""
507		Name = ['CovarianceMatrixAdaptionEvolutionStrategy', 'CMA-ES', 'CMAES']
508		epsilon = 1e-20
509
510		@staticmethod
511		def typeParameters(): return {
512		'epsilon': lambda x: isinstance(x, (float, int)) and 0 < x < 1
513		}
514
515		def setParameters(self, epsilon=1e-20, **ukwargs):
516		r"""Set core parameters of CovarianceMatrixAdaptionEvolutionStrategy algorithm.
517
518		Args:
519		epsilon (float): Small number.
520		**ukwargs (Dict[str, Any]): Additional arguments.
521		"""
522		Algorithm.setParameters(self, **ukwargs)
523		self.epsilon = epsilon
524
525		def runTask(self, task):
526		r"""TODO.
527
528		Args:
529		task (Task): Optimization task.
530
531		Returns:
532		TODO.
533		"""
534		return CovarianceMaatrixAdaptionEvolutionStrategyF(task, self.epsilon, rnd=self.Rand)
535
536		# vim: tabstop=3 noexpandtab shiftwidth=3 softtabstop=3
537

NiaOrg / NiaPy

Push — master ( cc7745...279fb5 )

EvolutionStrategyMpL.updateRho() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like