| 1 | This package contains an implementation of the Non-Dominated Sorting |
|---|
| 2 | Genetic Algorithm 2 (NSGA-II). |
|---|
| 3 | |
|---|
| 4 | Details of this approach can be found in the following paper: |
|---|
| 5 | |
|---|
| 6 | Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A Fast and |
|---|
| 7 | Elitist Multiobjective Genetic Algorithm: NSGA-II. In IEEE Transactions |
|---|
| 8 | On Evolutionary Computation. 6(2). 2002. |
|---|
| 9 | |
|---|
| 10 | The ec.app.moosuite package contains common multiobjective test cases |
|---|
| 11 | to test NSGA-II against. |
|---|
| 12 | |
|---|
| 13 | |
|---|
| 14 | |
|---|
| 15 | How ECJ implements NSGA-II |
|---|
| 16 | -------------------------- |
|---|
| 17 | |
|---|
| 18 | NSGA-II is an "archive" elitist method which uses Pareto front ranks |
|---|
| 19 | instead of composite fitness, and sparsity along the front rank when |
|---|
| 20 | there is not enough remaining room to fill the archive. |
|---|
| 21 | |
|---|
| 22 | We extend SimpleBreeder merely to build the next-generation population |
|---|
| 23 | by breeding children from the previous population (the archive) and then |
|---|
| 24 | appending the current archive to the newly-generated children. This |
|---|
| 25 | is essentially a version of (mu+mu). |
|---|
| 26 | |
|---|
| 27 | Most of the actual work is done in a special version of SimpleEvaluator, |
|---|
| 28 | where the Individuals are evaluated, then broken into Pareto Front Ranks, |
|---|
| 29 | then loaded into the archive. When there's not enough room left in the |
|---|
| 30 | archive for another full rank, sparsity is used to decide who gets to be |
|---|
| 31 | included. The archive then forms the next-generation population. |
|---|
| 32 | |
|---|
| 33 | NSGA-II has fixed archive size (the population size), and so ignores the 'elites' |
|---|
| 34 | declaration. However it will adhere to the 'reevaluate-elites' parameter |
|---|
| 35 | to determine whether to force fitness reevaluation. |
|---|
| 36 | |
|---|
| 37 | SPEA2 and NSGA-II have different approaches to building archives which impacts |
|---|
| 38 | on how you need to set your population sizes in order to achieve the same number |
|---|
| 39 | of evaluations. In ECJ, NSGA-II does not include the archive as part of the basic |
|---|
| 40 | population size. Rather, it builds the archive separately, then builds the |
|---|
| 41 | population by breeding from the archive, then gloms the two together. On the |
|---|
| 42 | other hand, SPEA2 uses a (tunable) portion of its population as the archive, and |
|---|
| 43 | breeds individuals into the remainder of the population. This means that to have |
|---|
| 44 | a "population size" for SPEA2 that's the same as NSGA-II, you need to increase |
|---|
| 45 | SPEA2's population size to NSGA-II's population size plus SPEA2's archive (elites) |
|---|
| 46 | size. For example, if you have an NSGA-II population size of 100, and SPEA2 is using |
|---|
| 47 | an archive size of 50, to be fair you should make SPEA2's population size be 150. |
|---|
| 48 | |
|---|
| 49 | If you set things so that SPEA2 and NSGA-II must reevaluate the fitness of |
|---|
| 50 | their archives (which is rare), things are different. Now you should set SPEA2 |
|---|
| 51 | so that its archive size and population size is equal to twice NSGA-II's population |
|---|
| 52 | size (because NSGA-II's archive size is the size of its population). |
|---|
| 53 | |
|---|
| 54 | The classes in question: |
|---|
| 55 | |
|---|
| 56 | |
|---|
| 57 | ec.multiobjective.nsga2.NSGA2Breeder |
|---|
| 58 | |
|---|
| 59 | The SimpleBreeder subclass. |
|---|
| 60 | |
|---|
| 61 | |
|---|
| 62 | ec.multiobjective.nsga2.NSGA2Evaluator |
|---|
| 63 | |
|---|
| 64 | The SimpleEvaluator subclass. |
|---|
| 65 | |
|---|
| 66 | |
|---|
| 67 | ec.multiobjective.nsga2.NSGA2MultiObjectiveFitness |
|---|
| 68 | |
|---|
| 69 | A special subclass of MultiObjectiveFitness which adds auxillary fitness |
|---|
| 70 | measures special to NSGA-II (notably rank and sparsity). |
|---|
