source: java/ecj/cecj/archive/LAPCArchive.java @ 1254

Last change on this file since 1254 was 193, checked in by Maciej Komosinski, 11 years ago

Set svn:eol-style native for all textual files

  • Property svn:eol-style set to native
File size: 4.4 KB
Line 
1/*
2  Copyright 2009 by Marcin Szubert
3  Licensed under the Academic Free License version 3.0
4 */
5
6package cecj.archive;
7
8import java.util.ArrayList;
9import java.util.HashSet;
10import java.util.List;
11import java.util.Set;
12
13import ec.EvolutionState;
14import ec.Individual;
15import ec.util.Parameter;
16
17/**
18 * Layered Pareto-Coevolution Archive.
19 *
20 * This archive is a modified version of the IPCA archive. While the original one can grow
21 * indefinitely (tests are never removed from the archive), this type of archive limits the maximum
22 * number of stored individuals. However, this goal is achieved for the price of reducing the
23 * reliability of the algorithm. After appending non-dominated candidate solutions and useful tests
24 * to appropriate archives, <code>maintainLayers</code> and <code>updateTestArchive</code> methods
25 * are invoked in order to decrease the amount of used memory. The first one checks which candidate
26 * solutions belong to the first <code>num-layers</code> Pareto layers and keeps them in the
27 * archive. The second retains only these tests which make distinctions between neighboring layers.
28 *
29 * @author Marcin Szubert
30 *
31 */
32public class LAPCArchive extends ParetoCoevolutionArchive {
33
34        private static final String P_NUM_LAYERS = "num-layers";
35
36        private int numLayers;
37
38        private List<List<Individual>> layers;
39
40        @Override
41        public void setup(EvolutionState state, Parameter base) {
42                super.setup(state, base);
43
44                Parameter numLayersParameter = base.push(P_NUM_LAYERS);
45                numLayers = state.parameters.getInt(numLayersParameter, null, 1);
46                if (numLayers <= 0) {
47                        state.output.fatal("Number of LAPCA layers must be > 0.\n");
48                }
49
50                layers = new ArrayList<List<Individual>>(numLayers);
51        }
52
53        /*
54         * It is implemented in a IPCA-like way. Another method is to extend both existing archives by
55         * new individuals, then find first n layers of candidates with respect to all tests in the
56         * archive and in the population and finally select necessary tests making distinctions between
57         * layers.
58         */
59        @Override
60        protected void submit(EvolutionState state, List<Individual> candidates,
61                        List<Individual> cArchive, List<Individual> tests, List<Individual> tArchive) {
62                List<Individual> testsCopy = new ArrayList<Individual>(tests);
63                List<Individual> usefulTests;
64
65                for (Individual candidate : candidates) {
66                        if (isUseful(state, candidate, cArchive, tArchive, testsCopy)) {
67                                usefulTests = findUsefulTests(state, candidate, cArchive, tArchive, testsCopy);
68
69                                cArchive.add(candidate);
70                                tArchive.addAll(usefulTests);
71                                testsCopy.removeAll(usefulTests);
72                        }
73                }
74
75                maintainLayers(state, cArchive, tArchive);
76                updateTestArchive(state, tArchive);
77        }
78
79        private void updateTestArchive(EvolutionState state, List<Individual> tArchive) {
80                Set<Individual> tset = new HashSet<Individual>();
81                tset.addAll(findDistinguishingTests(state, layers.get(0), layers.get(0), tArchive));
82                for (int l = 1; l < numLayers; l++) {
83                        tset.addAll(findDistinguishingTests(state, layers.get(l - 1), layers.get(l), tArchive));
84                }
85
86                tArchive.clear();
87                tArchive.addAll(tset);
88        }
89
90        private List<Individual> findDistinguishingTests(EvolutionState state, List<Individual> layer1,
91                        List<Individual> layer2, List<Individual> tests) {
92                List<Individual> distinguishingTests = new ArrayList<Individual>();
93                for (Individual candidate1 : layer1) {
94                        for (Individual candidate2 : layer2) {
95                                if (candidate1.equals(candidate2))
96                                        continue;
97                                Individual test = findUsefulTest(state, candidate1, candidate2, tests);
98                                if ((test != null) && (!distinguishingTests.contains(test))) {
99                                        distinguishingTests.add(test);
100                                }
101                        }
102                }
103                return distinguishingTests;
104        }
105
106        private void maintainLayers(EvolutionState state, List<Individual> cArchive,
107                        List<Individual> tArchive) {
108                List<Individual> cArchiveCopy = new ArrayList<Individual>(cArchive);
109                for (int layer = 0; layer < numLayers; layer++) {
110                        List<Individual> frontPareto = findNonDominatedCandidates(state, cArchiveCopy, tArchive);
111                        layers.set(layer, frontPareto);
112                        cArchiveCopy.removeAll(frontPareto);
113                }
114                cArchive.removeAll(cArchiveCopy);
115        }
116
117        private List<Individual> findNonDominatedCandidates(EvolutionState state,
118                        List<Individual> cArchive, List<Individual> tArchive) {
119                List<Individual> result = new ArrayList<Individual>();
120                for (Individual candidate : cArchive) {
121                        if (!isDominated(state, candidate, cArchive, tArchive)) {
122                                result.add(candidate);
123                        }
124                }
125                return result;
126        }
127
128}
Note: See TracBrowser for help on using the repository browser.