1#    This file is part of DEAP.
2#
3#    DEAP is free software: you can redistribute it and/or modify
4#    it under the terms of the GNU Lesser General Public License as
5#    published by the Free Software Foundation, either version 3 of
6#    the License, or (at your option) any later version.
7#
8#    DEAP is distributed in the hope that it will be useful,
9#    but WITHOUT ANY WARRANTY; without even the implied warranty of
10#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11#    GNU Lesser General Public License for more details.
12#
13#    You should have received a copy of the GNU Lesser General Public
14#    License along with DEAP. If not, see <http://www.gnu.org/licenses/>.
15
16"""Implementation of the Dynamic Differential Evolution algorithm as presented
17in *Mendes and Mohais, 2005, DynDE: A Differential Evolution for Dynamic
18Optimization Problems.*
19"""
20
21import array
22import itertools
23import math
24import operator
25import random
26
27import numpy
28
29from deap import base
30from deap.benchmarks import movingpeaks
31from deap import creator
32from deap import tools
33
34scenario = movingpeaks.SCENARIO_2
35
36NDIM = 5
37BOUNDS = [scenario["min_coord"], scenario["max_coord"]]
38
39mpb = movingpeaks.MovingPeaks(dim=NDIM, **scenario)
40
41def brown_ind(iclass, best, sigma):
42    return iclass(random.gauss(x, sigma) for x in best)
43
44creator.create("FitnessMax", base.Fitness, weights=(1.0,))
45creator.create("Individual", array.array, typecode='d', fitness=creator.FitnessMax)
46
47toolbox = base.Toolbox()
48toolbox.register("attr_float", random.uniform, BOUNDS[0], BOUNDS[1])
49toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, NDIM)
50toolbox.register("brownian_individual", brown_ind, creator.Individual, sigma=0.3)
51toolbox.register("population", tools.initRepeat, list, toolbox.individual)
52toolbox.register("select", random.sample, k=4)
53toolbox.register("best", tools.selBest, k=1)
54toolbox.register("evaluate", mpb)
55
56def main(verbose=True):
57    NPOP = 10   # Should be equal to the number of peaks
58    CR = 0.6
59    F = 0.4
60    regular, brownian = 4, 2
61
62    stats = tools.Statistics(lambda ind: ind.fitness.values)
63    stats.register("avg", numpy.mean)
64    stats.register("std", numpy.std)
65    stats.register("min", numpy.min)
66    stats.register("max", numpy.max)
67
68    logbook = tools.Logbook()
69    logbook.header = "gen", "evals", "error", "offline_error", "avg", "max"
70
71    # Initialize populations
72    populations = [toolbox.population(n=regular + brownian) for _ in range(NPOP)]
73
74    # Evaluate the individuals
75    for idx, subpop in enumerate(populations):
76        fitnesses = toolbox.map(toolbox.evaluate, subpop)
77        for ind, fit in zip(subpop, fitnesses):
78            ind.fitness.values = fit
79
80    record = stats.compile(itertools.chain(*populations))
81    logbook.record(gen=0, evals=mpb.nevals, error=mpb.currentError(),
82                   offline_error=mpb.offlineError(), **record)
83    if verbose:
84        print(logbook.stream)
85
86    g = 1
87    while mpb.nevals < 5e5:
88        # Detect a change and invalidate fitnesses if necessary
89        bests = [toolbox.best(subpop)[0] for subpop in populations]
90        if any(b.fitness.values != toolbox.evaluate(b) for b in bests):
91            for individual in itertools.chain(*populations):
92                del individual.fitness.values
93
94        # Apply exclusion
95        rexcl = (BOUNDS[1] - BOUNDS[0]) / (2 * NPOP**(1.0/NDIM))
96        for i, j in itertools.combinations(range(NPOP), 2):
97            if bests[i].fitness.valid and bests[j].fitness.valid:
98                d = sum((bests[i][k] - bests[j][k])**2 for k in range(NDIM))
99                d = math.sqrt(d)
100
101                if d < rexcl:
102                    if bests[i].fitness < bests[j].fitness:
103                        k = i
104                    else:
105                        k = j
106
107                    populations[k] = toolbox.population(n=regular + brownian)
108
109        # Evaluate the individuals with an invalid fitness
110        invalid_ind = [ind for ind in itertools.chain(*populations) if not ind.fitness.valid]
111        fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
112        for ind, fit in zip(invalid_ind, fitnesses):
113            ind.fitness.values = fit
114
115        record = stats.compile(itertools.chain(*populations))
116        logbook.record(gen=g, evals=mpb.nevals, error=mpb.currentError(),
117                       offline_error=mpb.offlineError(), **record)
118        if verbose:
119            print(logbook.stream)
120
121        # Evolve the sub-populations
122        for idx, subpop in enumerate(populations):
123            newpop = []
124            xbest, = toolbox.best(subpop)
125            # Apply regular DE to the first part of the population
126            for individual in subpop[:regular]:
127                x1, x2, x3, x4 = toolbox.select(subpop)
128                offspring = toolbox.clone(individual)
129                index = random.randrange(NDIM)
130                for i, value in enumerate(individual):
131                    if i == index or random.random() < CR:
132                        offspring[i] = xbest[i] + F * (x1[i] + x2[i] - x3[i] - x4[i])
133                offspring.fitness.values = toolbox.evaluate(offspring)
134                if offspring.fitness >= individual.fitness:
135                    newpop.append(offspring)
136                else:
137                    newpop.append(individual)
138
139            # Apply Brownian to the last part of the population
140            newpop.extend(toolbox.brownian_individual(xbest) for _ in range(brownian))
141
142            # Evaluate the brownian individuals
143            for individual in newpop[-brownian:]:
144                individual.fitness.value = toolbox.evaluate(individual)
145
146            # Replace the population
147            populations[idx] = newpop
148
149        g += 1
150
151    return logbook
152
153if __name__ == "__main__":
154    main()
155