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). |
---|