Created
March 6, 2012 22:02
-
-
Save cmd-ntrf/1989231 to your computer and use it in GitHub Desktop.
CMA Strategy inheriting from base.Toolbox
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Strategy(base.Toolbox): | |
""" | |
A strategy that will keep track of the basic parameters of the CMA-ES | |
algorithm. | |
:param centroid: An iterable object that indicates where to start the | |
evolution. | |
:param sigma: The list of initial standard deviations of the distribution, | |
it shall be the same length than the centroid. | |
:param parameter: One or more parameter to pass to the strategy as | |
described in the following table, optional. | |
+----------------+---------------------------+----------------------------+ | |
| Parameter | Default | Details | | |
+================+===========================+============================+ | |
| ``lambda_`` | ``int(4 + 3 * log(N))`` | Number of children to | | |
| | | produce at each generation,| | |
| | | ``N`` is the individual's | | |
| | | size (integer). | | |
+----------------+---------------------------+----------------------------+ | |
| ``mu`` | ``int(lambda_ / 2)`` | The number of parents to | | |
| | | keep from the | | |
| | | lambda children (integer). | | |
+----------------+---------------------------+----------------------------+ | |
| ``weights`` | ``"superlinear"`` | Decrease speed, can be | | |
| | | ``"superlinear"``, | | |
| | | ``"linear"`` or | | |
| | | ``"equal"``. | | |
+----------------+---------------------------+----------------------------+ | |
| ``cs`` | ``(mueff + 2) / | Cumulation constant for | | |
| | (N + mueff + 3)`` | step-size. | | |
+----------------+---------------------------+----------------------------+ | |
| ``damps`` | ``1 + 2 * max(0, sqrt(( | Damping for step-size. | | |
| | mueff - 1) / (N + 1)) - 1)| | | |
| | + cs`` | | | |
+----------------+---------------------------+----------------------------+ | |
| ``ccum`` | ``4 / (N + 4)`` | Cumulation constant for | | |
| | | covariance matrix. | | |
+----------------+---------------------------+----------------------------+ | |
| ``ccov1`` | ``2 / ((N + 1.3)^2 + | Learning rate for rank-one | | |
| | mueff)`` | update. | | |
+----------------+---------------------------+----------------------------+ | |
| ``ccovmu`` | ``2 * (mueff - 2 + 1 / | Learning rate for rank-mu | | |
| | mueff) / ((N + 2)^2 + | update. | | |
| | mueff)`` | | | |
+----------------+---------------------------+----------------------------+ | |
""" | |
def __init__(self, centroid, sigma, **kargs): | |
base.Toolbox.__init__(self) | |
self.params = kargs | |
# Create a centroid as a numpy array | |
self.centroid = numpy.array(centroid) | |
self.dim = len(self.centroid) | |
self.sigma = sigma | |
self.pc = numpy.zeros(self.dim) | |
self.ps = numpy.zeros(self.dim) | |
self.chiN = sqrt(self.dim) * (1 - 1. / (4. * self.dim) + \ | |
1. / (21. * self.dim**2)) | |
self.B = numpy.identity(self.dim) | |
self.C = numpy.identity(self.dim) | |
self.diagD = numpy.ones(self.dim) | |
self.BD = self.B * self.diagD | |
self.cond = 1 | |
self.lambda_ = self.params.get("lambda_", int(4 + 3 * log(self.dim))) | |
self.update_count = 0 | |
self.computeParams(self.params) | |
def generate(self, population=None): | |
"""Generate a population from the current strategy using the | |
centroid individual as parent. | |
:param ind_init: A function object that is able to initialize an | |
individual from a list. | |
:returns: A list of individuals. | |
""" | |
arz = numpy.random.standard_normal((self.lambda_, self.dim)) | |
arz = self.centroid + self.sigma * numpy.dot(arz, self.BD.T) | |
if population: | |
# Generate the individuals from the computed covariance matrix | |
# and replace the first lambda individuals of the population. | |
for ind, arzi in zip(population, arz): | |
ind[:] = arzi # This line does not allow ind to be of type array | |
return population | |
else: | |
return map(self.individual, arz) | |
def update(self, population): | |
"""Update the current covariance matrix strategy and *population*. | |
:param population: A list of individuals from which to update the | |
parameters and where the new population will be | |
placed. | |
""" | |
population.sort(key=lambda ind: ind.fitness, reverse=True) | |
old_centroid = self.centroid | |
self.centroid = numpy.dot(self.weights, population[0:self.mu]) | |
c_diff = self.centroid - old_centroid | |
# Cumulation : update evolution path | |
self.ps = (1 - self.cs) * self.ps \ | |
+ sqrt(self.cs * (2 - self.cs) * self.mueff) / self.sigma \ | |
* numpy.dot(self.B, (1. / self.diagD) \ | |
* numpy.dot(self.B.T, c_diff)) | |
hsig = float((numpy.linalg.norm(self.ps) / | |
sqrt(1. - (1. - self.cs)**(2. * (self.update_count + 1.))) / self.chiN | |
< (1.4 + 2. / (self.dim + 1.)))) | |
self.update_count += 1 | |
self.pc = (1 - self.cc) * self.pc + hsig \ | |
* sqrt(self.cc * (2 - self.cc) * self.mueff) / self.sigma \ | |
* c_diff | |
# Update covariance matrix | |
artmp = population[0:self.mu] - old_centroid | |
self.C = (1 - self.ccov1 - self.ccovmu + (1 - hsig) \ | |
* self.ccov1 * self.cc * (2 - self.cc)) * self.C \ | |
+ self.ccov1 * numpy.outer(self.pc, self.pc) \ | |
+ self.ccovmu * numpy.dot((self.weights * artmp.T), artmp) \ | |
/ self.sigma**2 | |
self.sigma *= numpy.exp((numpy.linalg.norm(self.ps) / self.chiN - 1.) \ | |
* self.cs / self.damps) | |
self.diagD, self.B = numpy.linalg.eigh(self.C) | |
indx = numpy.argsort(self.diagD) | |
self.cond = self.diagD[indx[-1]]/self.diagD[indx[0]] | |
self.diagD = self.diagD[indx]**0.5 | |
self.B = self.B[:, indx] | |
self.BD = self.B * self.diagD | |
def computeParams(self, params): | |
"""Computes the parameters depending on *lambda_*. It needs to be | |
called again if *lambda_* changes during evolution. | |
:param params: A dictionary of the manually set parameters. | |
""" | |
self.mu = params.get("mu", int(self.lambda_ / 2)) | |
rweights = params.get("weights", "superlinear") | |
if rweights == "superlinear": | |
self.weights = log(self.mu + 0.5) - \ | |
numpy.log(numpy.arange(1, self.mu + 1)) | |
elif rweights == "linear": | |
self.weights = self.mu + 0.5 - numpy.arange(1, self.mu + 1) | |
elif rweights == "equal": | |
self.weights = numpy.ones(self.mu) | |
else: | |
raise RuntimeError("Unknown weights : %s" % rweights) | |
self.weights /= sum(self.weights) | |
self.mueff = 1. / sum(self.weights**2) | |
self.cc = params.get("ccum", 4. / (self.dim + 4.)) | |
self.cs = params.get("cs", (self.mueff + 2.) / | |
(self.dim + self.mueff + 3.)) | |
self.ccov1 = params.get("ccov1", 2. / ((self.dim + 1.3)**2 + \ | |
self.mueff)) | |
self.ccovmu = params.get("ccovmu", 2. * (self.mueff - 2. + \ | |
1. / self.mueff) / \ | |
((self.dim + 2.)**2 + self.mueff)) | |
self.ccovmu = min(1 - self.ccov1, self.ccovmu) | |
self.damps = 1. + 2. * max(0, sqrt((self.mueff - 1.) / \ | |
(self.dim + 1.)) - 1.) + self.cs | |
self.damps = params.get("damps", self.damps) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment