source: java/ecj/cecj/archive/MaxSolveArchive.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: 5.2 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.Collections;
9import java.util.Comparator;
10import java.util.HashMap;
11import java.util.List;
12import java.util.Map;
13
14import cecj.interaction.InteractionResult;
15import cecj.utils.EquivalenceComparator;
16
17import ec.EvolutionState;
18import ec.Individual;
19import ec.util.Parameter;
20
21/**
22 * The simplest type of candidate-test archive.
23 *
24 * During the first step of the <code>submit</code> method, new candidates and tests are added to
25 * corresponding archives; then duplicate candidate solutions are eliminated (two individuals are
26 * considered equal if for each test in the archive they have identical outcomes). After sorting
27 * candidates by number of solved tests, the best <code>archive-size</code> individuals are kept in
28 * the archive. The last step is elimination of unsolved and duplicated (with respect to the
29 * outcomes against archival candidates) tests.
30 *
31 * Since duplicates removal is a common task, a purpose-built <code>EquivalenceComparator</code>
32 * interface is used for defining custom equivalence criteria.
33 *
34 * @author Marcin Szubert
35 *
36 */
37public class MaxSolveArchive extends CandidateTestArchive {
38
39        private static final String P_ARCHIVE_SIZE = "archive-size";
40
41        private int archiveSize;
42
43        @Override
44        public void setup(EvolutionState state, Parameter base) {
45                super.setup(state, base);
46
47                Parameter archiveSizeParameter = base.push(P_ARCHIVE_SIZE);
48                archiveSize = state.parameters.getInt(archiveSizeParameter, null, 1);
49                if (archiveSize <= 0) {
50                        state.output.fatal("Archive size must be > 0\n");
51                }
52        }
53
54        @Override
55        protected void submit(EvolutionState state, List<Individual> candidates,
56                        List<Individual> cArchive, List<Individual> tests, List<Individual> tArchive) {
57                cArchive.addAll(candidates);
58                tArchive.addAll(tests);
59
60                eliminateDuplicates(cArchive, new CandidateEquivalenceComparator(state, tArchive));
61                Map<Individual, Integer> numSolved = countSolved(state, cArchive, tArchive);
62                Collections.sort(cArchive, new NumberSolvedComparator(numSolved));
63
64                if (cArchive.size() > archiveSize) {
65                        cArchive.subList(archiveSize, cArchive.size()).clear();
66                }
67
68                eliminateUnsolvedTests(state, cArchive, tArchive);
69                eliminateDuplicates(tArchive, new TestEquivalenceComparator(state, cArchive));
70        }
71
72        private void eliminateDuplicates(List<Individual> archive,
73                        EquivalenceComparator<Individual> comparator) {
74                for (int ind1 = 0; ind1 < archive.size(); ind1++) {
75                        for (int ind2 = archive.size(); ind2 > ind1; ind2--) {
76                                if (comparator.equal(archive.get(ind1), archive.get(ind2))) {
77                                        archive.remove(ind2);
78                                }
79                        }
80                }
81        }
82
83        private void eliminateUnsolvedTests(EvolutionState state, List<Individual> cArchive,
84                        List<Individual> tArchive) {
85                for (int test = 0; test < tArchive.size(); test++) {
86                        if (!isSolved(state, tArchive.get(test), cArchive)) {
87                                tArchive.remove(test);
88                        }
89                }
90        }
91
92        private boolean isSolved(EvolutionState state, Individual test, List<Individual> candidates) {
93                for (Individual candidate : candidates) {
94                        if (problem.solves(state, candidate, test)) {
95                                return true;
96                        }
97                }
98                return false;
99        }
100
101        private Map<Individual, Integer> countSolved(EvolutionState state, List<Individual> candidates,
102                        List<Individual> tests) {
103                Map<Individual, Integer> result = new HashMap<Individual, Integer>();
104                for (Individual candidate : candidates) {
105                        int countTest = 0;
106                        for (Individual test : tests) {
107                                if (problem.solves(state, candidate, test)) {
108                                        countTest++;
109                                }
110                        }
111                        result.put(candidate, countTest);
112                }
113                return result;
114        }
115
116        private class NumberSolvedComparator implements Comparator<Individual> {
117                private Map<Individual, Integer> solved;
118
119                public NumberSolvedComparator(Map<Individual, Integer> solved) {
120                        this.solved = solved;
121                }
122
123                public int compare(Individual o1, Individual o2) {
124                        if (solved.get(o1) > solved.get(o2)) {
125                                return -1;
126                        } else if (solved.get(o1) > solved.get(o2)) {
127                                return 1;
128                        } else {
129                                return 0;
130                        }
131                }
132        }
133
134        private class CandidateEquivalenceComparator implements EquivalenceComparator<Individual> {
135                private EvolutionState state;
136                private List<Individual> tests;
137
138                public CandidateEquivalenceComparator(EvolutionState state, List<Individual> tests) {
139                        this.state = state;
140                        this.tests = tests;
141                }
142
143                public boolean equal(Individual o1, Individual o2) {
144                        for (Individual test : tests) {
145                                InteractionResult result1 = problem.test(state, o1, test).first;
146                                InteractionResult result2 = problem.test(state, o2, test).first;
147                                if (!result1.equals(result2)) {
148                                        return false;
149                                }
150                        }
151                        return false;
152                }
153        }
154
155        private class TestEquivalenceComparator implements EquivalenceComparator<Individual> {
156                private EvolutionState state;
157                private List<Individual> candidates;
158
159                public TestEquivalenceComparator(EvolutionState state, List<Individual> candidates) {
160                        this.state = state;
161                        this.candidates = candidates;
162                }
163
164                public boolean equal(Individual o1, Individual o2) {
165                        for (Individual candidate : candidates) {
166                                InteractionResult result1 = problem.test(state, candidate, o2).second;
167                                InteractionResult result2 = problem.test(state, candidate, o2).second;
168                                if (!result1.equals(result2)) {
169                                        return false;
170                                }
171                        }
172                        return false;
173                }
174        }
175}
Note: See TracBrowser for help on using the repository browser.