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