source: java/ecj/cecj/archive/ParetoCoevolutionArchive.java @ 567

Last change on this file since 567 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: 9.0 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.List;
10
11import cecj.interaction.InteractionResult;
12
13import ec.EvolutionState;
14import ec.Individual;
15
16/**
17 * Represents the archive for Pareto-Coevolution paradigm where each test is viewed as an objective
18 * in the sense of Multi-Objective Optimization.
19 *
20 * This class provides methods for comparing individuals on the basis of their interactions outcomes
21 * considered in the context of Pareto dominance relation (methods: <code>dominates</code>,
22 * <code>isDominated</code>). According to the results of these comparisons a test can be found
23 * useful if it proves that a particular candidate solution is not dominated by any other individual
24 * in the archive. Such usefulness can be verified using the methods of this class (
25 * <code>isUseful</code>, <code>findUsefulTest</code>). It provides methods for comparing
26 * individuals on the basis of their interaction results.
27 *
28 * @author Marcin Szubert
29 *
30 */
31public abstract class ParetoCoevolutionArchive extends CandidateTestArchive {
32
33        /**
34         * Tries to find a test for which <code>candidate1</code> has better outcome than
35         * <code>candidate2<code>. It is needed for <code>candidate1</code> to be non-dominated and thus
36         * useful to be stored in the archive. If the test is found it makes distinction between
37         * candidates.
38         *
39         * @param state
40         *            the current evolution state
41         * @param candidate1
42         *            the candidate which should appear to be better at some test
43         * @param candidate2
44         *            the reference candidate solution which is checked for dominating the candidate1
45         * @param tests
46         *            the list of test to be searched
47         * @return <code>null</code> if there is no such test
48         */
49        protected Individual findUsefulTest(EvolutionState state, Individual candidate1,
50                        Individual candidate2, List<Individual> tests) {
51                for (Individual test : tests) {
52                        InteractionResult result1 = problem.test(state, candidate1, test).first;
53                        InteractionResult result2 = problem.test(state, candidate2, test).first;
54                        if (result1.betterThan(result2)) {
55                                return test;
56                        }
57                }
58                return null;
59        }
60
61        /**
62         * Checks if <code>candidate1</code> Pareto-dominates <code>candidate2</code> or both candidates
63         * are equal with respect to <code>tests</code>. One candidate is Pareto-dominated if it has
64         * better or equal outcomes for all <code>tests</code> and for at least one - strictly better.
65         *
66         * @param state
67         *            the current evolution state
68         * @param candidate1
69         *            the candidate solution which is checked for dominating the other candidate
70         * @param candidate2
71         *            the candidate solutions which is checked for being dominated
72         * @param tests
73         *            the set of tests with respect to which dominance is checked
74         * @return <code>true</code> if <code>candidate1</code> dominates <code>candidate2</code> or
75         *         they are equal with respect to <code>tests</code>, <code>false</code> otherwise
76         */
77        protected boolean dominatesOrEqual(EvolutionState state, Individual candidate1,
78                        Individual candidate2, List<Individual> tests) {
79                return (findUsefulTest(state, candidate2, candidate1, tests) == null);
80        }
81
82        /**
83         * Checks if <code>candidate1</code> Pareto-dominates <code>candidate2</code> with respect to
84         * <code>tests</code>. One candidate is Pareto-dominated if it has better or equal outcomes for
85         * all <code>tests</code> and for at least one - strictly better.
86         *
87         * @param state
88         *            the current evolution state
89         * @param candidate1
90         *            the candidate solution which is checked for dominating the other candidate
91         * @param candidate2
92         *            the candidate solutions which is checked for being dominated
93         * @param tests
94         *            the set of tests with respect to which dominance is checked
95         * @return <code>true</code> if <code>candidate1</code> dominates <code>candidate2</code> with
96         *         respect to <code>tests</code>, <code>false</code> otherwise
97         */
98        protected boolean dominates(EvolutionState state, Individual candidate1, Individual candidate2,
99                        List<Individual> tests) {
100                if ((findUsefulTest(state, candidate2, candidate1, tests) == null)
101                                && (findUsefulTest(state, candidate1, candidate2, tests) != null)) {
102                        return true;
103                } else {
104                        return false;
105                }
106        }
107
108        /**
109         * Verifies if <code>candidate</code> is dominated by any candidate solution present in
110         * <code>cArchive</code> with respect to tests in <code>tArchive</code> or if another solution
111         * has equivalent outcomes for all tests in <code>tArchive</code>.
112         *
113         * If the archive contains a <code>candidate</code>, the outcome is <code>true</code>.
114         *
115         * @param state
116         *            the current evolution state
117         * @param candidate
118         *            the candidate which is checked for being dominated; it should not be in the
119         *            archive
120         * @param cArchive
121         *            the archive of candidate solutions
122         * @param tArchive
123         *            the archive of tests
124         * @return <code>true</code> if <code>candidate</code> is dominated by or equal to another
125         *         solution in the archive
126         */
127        protected boolean isDominatedOrEqual(EvolutionState state, Individual candidate,
128                        List<Individual> cArchive, List<Individual> tArchive) {
129                for (Individual otherCandidate : cArchive) {
130                        if (dominatesOrEqual(state, otherCandidate, candidate, tArchive)) {
131                                return true;
132                        }
133                }
134                return false;
135        }
136
137        /**
138         * Verifies if <code>candidate</code> is dominated by any candidate solution present in
139         * <code>cArchive</code> with respect to tests in <code>tArchive</code>.
140         *
141         * @param state
142         *            the current evolution state
143         * @param candidate
144         *            the candidate which is checked for being dominated
145         * @param cArchive
146         *            the archive of candidate solutions
147         * @param tArchive
148         *            the archive of tests
149         * @return <code>true</code> if <code>candidate</code> is dominated by any solution in the
150         *         archive
151         */
152        protected boolean isDominated(EvolutionState state, Individual candidate,
153                        List<Individual> cArchive, List<Individual> tArchive) {
154                for (Individual otherCandidate : cArchive) {
155                        if (dominates(state, otherCandidate, candidate, tArchive)) {
156                                return true;
157                        }
158                }
159                return false;
160        }
161
162        /**
163         * Checks if <code>newCandidate</code> is useful with respect to current archives of candidates
164         * and tests and new population of generated tests. A candidate solutions is considered
165         * <i>useful</i> if it is non-dominated and no solution is already present with identical
166         * outcomes for all tests.
167         *
168         * @param state
169         *            the current evolution state
170         * @param newCandidate
171         *            the candidate whose usefulness is verified
172         * @param cArchive
173         *            the archive of candidate solutions
174         * @param tArchive
175         *            the archive of tests
176         * @param newTests
177         *            the population of new tests
178         * @return <code>true</code> if <code>newCandidate</code> is <i>useful</i> and should be
179         *         included in the archive.
180         */
181        protected boolean isUseful(EvolutionState state, Individual newCandidate,
182                        List<Individual> cArchive, List<Individual> tArchive, List<Individual> newTests) {
183                if (isDominatedOrEqual(state, newCandidate, cArchive, tArchive)
184                                && isDominatedOrEqual(state, newCandidate, cArchive, newTests)) {
185                        return false;
186                } else {
187                        return true;
188                }
189        }
190
191        /**
192         * Finds tests which are needed to prove usefulness of given <code>newCandidate</code>. These
193         * tests should make distinctions between existing solutions in the <code>cArchive</code> and
194         * the new one. If the <code>newCandidate</code> solution is non-dominated without adding any of
195         * <code>newTests</code> to the test archive, the returned list is empty.
196         *
197         * @param state
198         *            the current evolution state
199         * @param newCandidate
200         *            the candidate solution whose non-dominated status is to be guaranteed
201         * @param cArchive
202         *            the archive of candidate solutions
203         * @param tArchive
204         *            the archive of tests
205         * @param newTests
206         *            the population of new tests
207         * @return the list of test individuals from <code>newTests</code> which should be added to the
208         *         <code>tArchive</code> to make <code>newCandidate</code> non-dominated. If even adding
209         *         all test is not sufficient, <code>null</code> is returned.
210         */
211        protected List<Individual> findUsefulTests(EvolutionState state, Individual newCandidate,
212                        List<Individual> cArchive, List<Individual> tArchive, List<Individual> newTests) {
213                List<Individual> selected = new ArrayList<Individual>();
214                List<Individual> rest = new ArrayList<Individual>(newTests);
215
216                for (Individual candidate : cArchive) {
217                        if (dominatesOrEqual(state, candidate, newCandidate, tArchive)
218                                        && dominatesOrEqual(state, candidate, newCandidate, selected)) {
219                                Individual test = findUsefulTest(state, newCandidate, candidate, rest);
220                                if (test == null) {
221                                        return null;
222                                } else {
223                                        selected.add(test);
224                                        rest.remove(test);
225                                }
226                        }
227                }
228
229                return selected;
230        }
231}
Note: See TracBrowser for help on using the repository browser.