[deap] push by felix.antoine.fortin - Fix the implementation of EDA update method in eda/fctmin.py.... on 2014-04-04 14:25 GMT

[de...@googlecode.com]

Revision: f3f86a8548f0
Branch: dev
Author: felix.antoine.fortin
Date: Fri Apr 4 14:25:20 2014 UTC
Log: Fix the implementation of EDA update method in eda/fctmin.py.

The algorithm was converging, but the implementation was not
conformed to the algorithm presented by the paper Teytaud 2009.
The sigma was originally interpreted as a vector while it is
presented as a vector in the paper.

Also added is the reference to article and the class have been
renamed to represent the algorithm instead of generic EDA.
http://code.google.com/p/deap/source/detail?r=f3f86a8548f0

Modified:
/examples/eda/fctmin.py

=======================================
--- /examples/eda/fctmin.py Mon Jun 10 14:28:32 2013 UTC
+++ /examples/eda/fctmin.py Fri Apr 4 14:25:20 2014 UTC
@@ -28,17 +28,25 @@
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", numpy.ndarray, fitness=creator.FitnessMin)

-class EDA(object):
+class EMNA(object):
+ """Estimation of Multivariate Normal Algorithm (EMNA) as described
+ by Algorithm 1 in:
+
+ Fabien Teytaud and Olivier Teytaud. 2009.
+ Why one must use reweighting in estimation of distribution algorithms.
+ In Proceedings of the 11th Annual conference on Genetic and
+ evolutionary computation (GECCO '09). ACM, New York, NY, USA, 453-460.
+ """
def __init__(self, centroid, sigma, mu, lambda_):
self.dim = len(centroid)
- self.loc = numpy.array(centroid)
+ self.centroid = numpy.array(centroid)
self.sigma = numpy.array(sigma)
self.lambda_ = lambda_
self.mu = mu

def generate(self, ind_init):
# Generate lambda_ individuals and put them into the provided class
- arz = self.sigma * numpy.random.randn(self.lambda_, self.dim) +
self.loc
+ arz = self.centroid + self.sigma *
numpy.random.randn(self.lambda_, self.dim)
return list(map(ind_init, arz))

def update(self, population):
@@ -46,17 +54,17 @@
sorted_pop = sorted(population, key=attrgetter("fitness"),
reverse=True)

# Compute the average of the mu best individuals
- z = sorted_pop[:self.mu] - self.loc
+ z = sorted_pop[:self.mu] - self.centroid
avg = numpy.mean(z, axis=0)

- # Adjust variances of the distribution
- self.sigma = numpy.sqrt(numpy.sum((z - avg)**2, axis=0) / (self.mu
- 1.0))
- self.loc = self.loc + avg
+ # Adjust variance of the distribution
+ self.sigma = numpy.sqrt(numpy.sum(numpy.sum((z - avg)**2, axis=1))
/ (self.mu*self.dim))
+ self.centroid = self.centroid + avg

def main():
N, LAMBDA = 30, 1000
MU = int(LAMBDA/4)
- strategy = EDA(centroid=[5.0]*N, sigma=[5.0]*N, mu=MU, lambda_=LAMBDA)
+ strategy = EMNA(centroid=[5.0]*N, sigma=5.0, mu=MU, lambda_=LAMBDA)

toolbox = base.Toolbox()
toolbox.register("evaluate", benchmarks.rastrigin)