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

/*
  Copyright 2009 by Marcin Szubert
  Licensed under the Academic Free License version 3.0
 */

package cecj.archive;

import java.util.ArrayList;
import java.util.List;

import cecj.interaction.InteractionResult;

import ec.EvolutionState;
import ec.Individual;

/**
 * Represents the archive for Pareto-Coevolution paradigm where each test is viewed as an objective
 * in the sense of Multi-Objective Optimization.
 * 
 * This class provides methods for comparing individuals on the basis of their interactions outcomes
 * considered in the context of Pareto dominance relation (methods: <code>dominates</code>,
 * <code>isDominated</code>). According to the results of these comparisons a test can be found
 * useful if it proves that a particular candidate solution is not dominated by any other individual
 * in the archive. Such usefulness can be verified using the methods of this class (
 * <code>isUseful</code>, <code>findUsefulTest</code>). It provides methods for comparing
 * individuals on the basis of their interaction results.
 * 
 * @author Marcin Szubert
 * 
 */
public abstract class ParetoCoevolutionArchive extends CandidateTestArchive {

        /**
         * Tries to find a test for which <code>candidate1</code> has better outcome than
         * <code>candidate2<code>. It is needed for <code>candidate1</code> to be non-dominated and thus
         * useful to be stored in the archive. If the test is found it makes distinction between
         * candidates.
         * 
         * @param state
         *            the current evolution state
         * @param candidate1
         *            the candidate which should appear to be better at some test
         * @param candidate2
         *            the reference candidate solution which is checked for dominating the candidate1
         * @param tests
         *            the list of test to be searched
         * @return <code>null</code> if there is no such test
         */
        protected Individual findUsefulTest(EvolutionState state, Individual candidate1,
                        Individual candidate2, List<Individual> tests) {
                for (Individual test : tests) {
                        InteractionResult result1 = problem.test(state, candidate1, test).first;
                        InteractionResult result2 = problem.test(state, candidate2, test).first;
                        if (result1.betterThan(result2)) {
                                return test;
                        }
                }
                return null;
        }

        /**
         * Checks if <code>candidate1</code> Pareto-dominates <code>candidate2</code> or both candidates
         * are equal with respect to <code>tests</code>. One candidate is Pareto-dominated if it has
         * better or equal outcomes for all <code>tests</code> and for at least one - strictly better.
         * 
         * @param state
         *            the current evolution state
         * @param candidate1
         *            the candidate solution which is checked for dominating the other candidate
         * @param candidate2
         *            the candidate solutions which is checked for being dominated
         * @param tests
         *            the set of tests with respect to which dominance is checked
         * @return <code>true</code> if <code>candidate1</code> dominates <code>candidate2</code> or
         *         they are equal with respect to <code>tests</code>, <code>false</code> otherwise
         */
        protected boolean dominatesOrEqual(EvolutionState state, Individual candidate1,
                        Individual candidate2, List<Individual> tests) {
                return (findUsefulTest(state, candidate2, candidate1, tests) == null);
        }

        /**
         * Checks if <code>candidate1</code> Pareto-dominates <code>candidate2</code> with respect to
         * <code>tests</code>. One candidate is Pareto-dominated if it has better or equal outcomes for
         * all <code>tests</code> and for at least one - strictly better.
         * 
         * @param state
         *            the current evolution state
         * @param candidate1
         *            the candidate solution which is checked for dominating the other candidate
         * @param candidate2
         *            the candidate solutions which is checked for being dominated
         * @param tests
         *            the set of tests with respect to which dominance is checked
         * @return <code>true</code> if <code>candidate1</code> dominates <code>candidate2</code> with
         *         respect to <code>tests</code>, <code>false</code> otherwise
         */
        protected boolean dominates(EvolutionState state, Individual candidate1, Individual candidate2,
                        List<Individual> tests) {
                if ((findUsefulTest(state, candidate2, candidate1, tests) == null)
                                && (findUsefulTest(state, candidate1, candidate2, tests) != null)) {
                        return true;
                } else {
                        return false;
                }
        }

        /**
         * Verifies if <code>candidate</code> is dominated by any candidate solution present in
         * <code>cArchive</code> with respect to tests in <code>tArchive</code> or if another solution
         * has equivalent outcomes for all tests in <code>tArchive</code>.
         * 
         * If the archive contains a <code>candidate</code>, the outcome is <code>true</code>.
         * 
         * @param state
         *            the current evolution state
         * @param candidate
         *            the candidate which is checked for being dominated; it should not be in the
         *            archive
         * @param cArchive
         *            the archive of candidate solutions
         * @param tArchive
         *            the archive of tests
         * @return <code>true</code> if <code>candidate</code> is dominated by or equal to another
         *         solution in the archive
         */
        protected boolean isDominatedOrEqual(EvolutionState state, Individual candidate,
                        List<Individual> cArchive, List<Individual> tArchive) {
                for (Individual otherCandidate : cArchive) {
                        if (dominatesOrEqual(state, otherCandidate, candidate, tArchive)) {
                                return true;
                        }
                }
                return false;
        }

        /**
         * Verifies if <code>candidate</code> is dominated by any candidate solution present in
         * <code>cArchive</code> with respect to tests in <code>tArchive</code>.
         * 
         * @param state
         *            the current evolution state
         * @param candidate
         *            the candidate which is checked for being dominated
         * @param cArchive
         *            the archive of candidate solutions
         * @param tArchive
         *            the archive of tests
         * @return <code>true</code> if <code>candidate</code> is dominated by any solution in the
         *         archive
         */
        protected boolean isDominated(EvolutionState state, Individual candidate,
                        List<Individual> cArchive, List<Individual> tArchive) {
                for (Individual otherCandidate : cArchive) {
                        if (dominates(state, otherCandidate, candidate, tArchive)) {
                                return true;
                        }
                }
                return false;
        }

        /**
         * Checks if <code>newCandidate</code> is useful with respect to current archives of candidates
         * and tests and new population of generated tests. A candidate solutions is considered
         * <i>useful</i> if it is non-dominated and no solution is already present with identical
         * outcomes for all tests.
         * 
         * @param state
         *            the current evolution state
         * @param newCandidate
         *            the candidate whose usefulness is verified
         * @param cArchive
         *            the archive of candidate solutions
         * @param tArchive
         *            the archive of tests
         * @param newTests
         *            the population of new tests
         * @return <code>true</code> if <code>newCandidate</code> is <i>useful</i> and should be
         *         included in the archive.
         */
        protected boolean isUseful(EvolutionState state, Individual newCandidate,
                        List<Individual> cArchive, List<Individual> tArchive, List<Individual> newTests) {
                if (isDominatedOrEqual(state, newCandidate, cArchive, tArchive)
                                && isDominatedOrEqual(state, newCandidate, cArchive, newTests)) {
                        return false;
                } else {
                        return true;
                }
        }

        /**
         * Finds tests which are needed to prove usefulness of given <code>newCandidate</code>. These
         * tests should make distinctions between existing solutions in the <code>cArchive</code> and
         * the new one. If the <code>newCandidate</code> solution is non-dominated without adding any of
         * <code>newTests</code> to the test archive, the returned list is empty.
         * 
         * @param state
         *            the current evolution state
         * @param newCandidate
         *            the candidate solution whose non-dominated status is to be guaranteed
         * @param cArchive
         *            the archive of candidate solutions
         * @param tArchive
         *            the archive of tests
         * @param newTests
         *            the population of new tests
         * @return the list of test individuals from <code>newTests</code> which should be added to the
         *         <code>tArchive</code> to make <code>newCandidate</code> non-dominated. If even adding
         *         all test is not sufficient, <code>null</code> is returned.
         */
        protected List<Individual> findUsefulTests(EvolutionState state, Individual newCandidate,
                        List<Individual> cArchive, List<Individual> tArchive, List<Individual> newTests) {
                List<Individual> selected = new ArrayList<Individual>();
                List<Individual> rest = new ArrayList<Individual>(newTests);

                for (Individual candidate : cArchive) {
                        if (dominatesOrEqual(state, candidate, newCandidate, tArchive)
                                        && dominatesOrEqual(state, candidate, newCandidate, selected)) {
                                Individual test = findUsefulTest(state, newCandidate, candidate, rest);
                                if (test == null) {
                                        return null;
                                } else {
                                        selected.add(test);
                                        rest.remove(test);
                                }
                        }
                }

                return selected;
        }
}