[6152] | 1 | This package implements various Differential Evolution algorithms from |
---|
| 2 | "Differential Evolution: A Practical Approach to Global Optimization" |
---|
| 3 | by Kenneth Price, Rainer Storn, and Jouni Lampinen. |
---|
| 4 | |
---|
| 5 | ECJ's implementation of Differential Evolution requires that the |
---|
| 6 | user specify one of several Breeders, and also that you (optionally but |
---|
| 7 | highly suggested) use a specific Evaluator. |
---|
| 8 | |
---|
| 9 | The Breeder options implement various Differential Evolution Algorithms. |
---|
| 10 | Options include: |
---|
| 11 | |
---|
| 12 | breed = ec.de.DEBreeder |
---|
| 13 | breed = ec.de.Best1BinDEBreeder |
---|
| 14 | breed = ec.de.Rand1EitherOrDEBreeder |
---|
| 15 | |
---|
| 16 | The Evaluator is ec.de.DEEvaluator: |
---|
| 17 | |
---|
| 18 | eval = ec.de.DEEvaluator |
---|
| 19 | |
---|
| 20 | The ec/app/ecsuite/de.params file contains an example. |
---|
| 21 | |
---|
| 22 | |
---|
| 23 | ECJ's DE implementation (for now) |
---|
| 24 | --------------------------------- |
---|
| 25 | |
---|
| 26 | ECJ implements Differential Evolution by largely by replacing the Breeder. |
---|
| 27 | The various DE breeders work like this: for each individual i in the |
---|
| 28 | population, construct a new individual using a function called |
---|
| 29 | createIndividual(..., i, ...). Then replace the entire population with the |
---|
| 30 | newly constructed individuals only if they are superior to the parents |
---|
| 31 | from which they were derived. The "only if" part is implemented by DEEvaluator, |
---|
| 32 | and if you don't use it, the children will directly replace their parents. |
---|
| 33 | |
---|
| 34 | In DE, all individuals are DoubleVectorIndividuals. |
---|
| 35 | |
---|
| 36 | DEBreeder has an additional method called crossover(...) which crosses the |
---|
| 37 | original parent into the child. Some operators use this method, others |
---|
| 38 | do not. You can override the method to perform your own custom kind of crossover; |
---|
| 39 | the default does a uniform crossover, while guaranteeing that at least one |
---|
| 40 | gene (chosen at random) from the child will be preserved. |
---|
| 41 | |
---|
| 42 | The different breeders differ largely based on how |
---|
| 43 | createIndividual(..., i, ...) is implemented. In all versions, |
---|
| 44 | createIndividual(..., i, ...) begins by choosing three random individuals |
---|
| 45 | r0, r1, and r2 which are different from one another and from i. Let j |
---|
| 46 | be the new individual. |
---|
| 47 | |
---|
| 48 | There are four parameters which may affect the operation below: |
---|
| 49 | |
---|
| 50 | F: scaling factor for mutating individuals |
---|
| 51 | CR: the probability, per-gene, of crossing over |
---|
| 52 | F_NOISE: Bounds on random noise added to F |
---|
| 53 | PF: Probability of picking one of two subalgorithms for mutation |
---|
| 54 | |
---|
| 55 | |
---|
| 56 | The default version, implemented by |
---|
| 57 | |
---|
| 58 | ec.de.DEBreeder |
---|
| 59 | |
---|
| 60 | ... creates a new individual as follows. |
---|
| 61 | |
---|
| 62 | j[g] <-- r0[g] + F * (r1[g] - r2[g]) |
---|
| 63 | |
---|
| 64 | This is the "classic" DE algorithm |
---|
| 65 | |
---|
| 66 | |
---|
| 67 | The next version, implemented by |
---|
| 68 | |
---|
| 69 | ec.de.Best1BinDEBreeder |
---|
| 70 | |
---|
| 71 | ... works like this. We first determine the best individual in the |
---|
| 72 | population. Then we say: |
---|
| 73 | |
---|
| 74 | j[g] <-- best[g] + (F + random(-F_NOISE / 2, F_NOISE / 2)) * (r1[g] - r2[g]) |
---|
| 75 | |
---|
| 76 | |
---|
| 77 | The final version, implemented by |
---|
| 78 | |
---|
| 79 | ec.de.Rand1EitherOrDEBreeder ` |
---|
| 80 | |
---|
| 81 | ... works like this. First we flip a coin of probability PF. If it comes |
---|
| 82 | up 'true', then we generate the individual as the classic form: |
---|
| 83 | |
---|
| 84 | j[g] <-- r0[g] + F * (r1[g] - r2[g]) |
---|
| 85 | |
---|
| 86 | ... else we generate the individual as: |
---|
| 87 | |
---|
| 88 | j[g] <-- r0[g] + 0.5 * (F + 1) * (r1[g] + r2[g] - 2 * r0[g]) |
---|
| 89 | |
---|
| 90 | |
---|
| 91 | Don't like any of these? It should be fairly straightforward to copy an |
---|
| 92 | existing one and modify it. |
---|
| 93 | |
---|
| 94 | Note that DEBreeder is a subclass of Breeder and does NOT implement |
---|
| 95 | multithreaded breeding: but DEEvaluator, as a subclass of SimpleEvaluator, |
---|
| 96 | DOES implement multithreaded evaluation. |
---|