001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package org.jgap.impl;
011:
012: import java.util.*;
013: import org.jgap.*;
014: import org.jgap.util.*;
015:
016: /**
017: * Implementation of a NaturalSelector that is suited for being processed after
018: * genetic operators have been executed. It takes all chromosomes with no
019: * fitness value computed to the next generation. Then it takes the top n
020: * chromosomes from the remaining input into the next generation.
021: * Which chromosomes are the best is decided by evaluating their fitness value.
022: *
023: * @author Klaus Meffert
024: * @since 3.2
025: */
026: public class StandardPostSelector extends NaturalSelector implements
027: ICloneable {
028: /** String containing the CVS revision. Read out via reflection!*/
029: private final static String CVS_REVISION = "$Revision: 1.2 $";
030:
031: /**
032: * Stores the chromosomes to be taken into account for selection
033: */
034: private Population m_chromosomes;
035:
036: /**
037: * Indicated whether the list of added chromosomes needs sorting
038: */
039: private boolean m_needsSorting;
040:
041: /**
042: * Comparator that is only concerned about fitness values
043: */
044: private FitnessValueComparator m_fitnessValueComparator;
045:
046: /**
047: * Default constructor.<p>
048: * Attention: The configuration used is the one set with the static method
049: * Genotype.setConfiguration.
050: *
051: * @throws InvalidConfigurationException
052: *
053: * @author Klaus Meffert
054: * @since 3.2
055: */
056: public StandardPostSelector() throws InvalidConfigurationException {
057: this (Genotype.getStaticConfiguration());
058: }
059:
060: /**
061: * Constructor.
062: *
063: * @param a_config the configuration to use
064: * @throws InvalidConfigurationException
065: *
066: * @author Klaus Meffert
067: * @since 3.2
068: */
069: public StandardPostSelector(final Configuration a_config)
070: throws InvalidConfigurationException {
071: super (a_config);
072: m_chromosomes = new Population(a_config);
073: m_needsSorting = false;
074: m_fitnessValueComparator = new FitnessValueComparator();
075: }
076:
077: /**
078: * Add a Chromosome instance to this selector's working pool of Chromosomes.
079: *
080: * @param a_chromosomeToAdd the specimen to add to the pool
081: *
082: * @author Klaus Meffert
083: * @since 3.2
084: */
085: protected void add(final IChromosome a_chromosomeToAdd) {
086: // New chromosome, insert it into the sorted collection of chromosomes
087: a_chromosomeToAdd.setIsSelectedForNextGeneration(false);
088: m_chromosomes.addChromosome(a_chromosomeToAdd);
089: // Indicate that the list of chromosomes to add needs sorting.
090: // -----------------------------------------------------------
091: m_needsSorting = true;
092: }
093:
094: /**
095: * Selects a given number of Chromosomes from the pool that will move on
096: * to the next generation population. This selection will be guided by the
097: * fitness values. The chromosomes with the best fitness value win.
098: *
099: * @param a_from_pop the population the Chromosomes will be selected from
100: * @param a_to_pop the population the Chromosomes will be added to
101: * @param a_howManyToSelect the number of Chromosomes to select
102: *
103: * @author Klaus Meffert
104: * @since 1.1
105: */
106: public void select(final int a_howManyToSelect,
107: final Population a_from_pop, final Population a_to_pop) {
108: if (a_from_pop != null) {
109: int popSize = a_from_pop.size();
110: if (popSize < 1) {
111: throw new IllegalStateException(
112: "Population size must be greater 0");
113: }
114: for (int i = 0; i < popSize; i++) {
115: add(a_from_pop.getChromosome(i));
116: }
117: }
118: int canBeSelected;
119: int chromsSize = m_chromosomes.size();
120: if (chromsSize < 1) {
121: throw new IllegalStateException(
122: "Number of chromosomes must be greater 0");
123: }
124: if (a_howManyToSelect > chromsSize) {
125: canBeSelected = chromsSize;
126: } else {
127: canBeSelected = a_howManyToSelect;
128: }
129: int neededSize = a_howManyToSelect;
130: // First select all chromosomes with no fitness value computed.
131: // ------------------------------------------------------------
132: Iterator it = m_chromosomes.iterator();
133: while (it.hasNext()) {
134: IChromosome c = (IChromosome) it.next();
135: if (Math.abs(c.getFitnessValueDirectly()
136: - FitnessFunction.NO_FITNESS_VALUE) < FitnessFunction.DELTA) {
137: a_to_pop.addChromosome(c);
138: it.remove();
139: canBeSelected--;
140: if (canBeSelected < 1) {
141: break;
142: }
143: }
144: }
145:
146: // Sort the collection of chromosomes previously added for evaluation.
147: // Only do this if necessary.
148: // -------------------------------------------------------------------
149: if (m_needsSorting && canBeSelected > 0) {
150: Collections.sort(m_chromosomes.getChromosomes(),
151: m_fitnessValueComparator);
152: m_needsSorting = false;
153: }
154: // To select a chromosome, we just go thru the sorted list.
155: // --------------------------------------------------------
156: IChromosome selectedChromosome;
157: for (int i = 0; i < canBeSelected; i++) {
158: selectedChromosome = m_chromosomes.getChromosome(i);
159: selectedChromosome.setIsSelectedForNextGeneration(true);
160: a_to_pop.addChromosome(selectedChromosome);
161: }
162: int toAdd;
163: toAdd = neededSize - a_to_pop.size();
164: // Add existing Chromosome's to fill up the return
165: // result to contain the desired number of Chromosome's.
166: // -----------------------------------------------------
167: for (int i = 0; i < toAdd; i++) {
168: selectedChromosome = m_chromosomes.getChromosome(i
169: % chromsSize);
170: selectedChromosome.setIsSelectedForNextGeneration(true);
171: a_to_pop.addChromosome(selectedChromosome);
172: }
173: }
174:
175: /**
176: * Empties out the working pool of Chromosomes.
177: *
178: * @author Klaus Meffert
179: * @since 3.2
180: */
181: public void empty() {
182: // Clear the list of chromosomes
183: // -----------------------------
184: m_chromosomes.getChromosomes().clear();
185: m_needsSorting = false;
186: }
187:
188: /**
189: * @return always true as no Chromosome can be returnd multiple times
190: *
191: * @author Klaus Meffert
192: * @since 3.2
193: */
194: public boolean returnsUniqueChromosomes() {
195: return true;
196: }
197:
198: public boolean equals(Object a_o) {
199: if (a_o == null) {
200: return false;
201: }
202: StandardPostSelector other = (StandardPostSelector) a_o;
203: if (!m_fitnessValueComparator.getClass().getName().equals(
204: other.m_fitnessValueComparator.getClass().getName())) {
205: return false;
206: }
207: if (!m_chromosomes.equals(other.m_chromosomes)) {
208: return false;
209: }
210: return true;
211: }
212:
213: public Object clone() {
214: try {
215: StandardPostSelector sel = new StandardPostSelector(
216: getConfiguration());
217: sel.m_needsSorting = m_needsSorting;
218: return sel;
219: } catch (Throwable t) {
220: throw new CloneException(t);
221: }
222: }
223: }
|