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 takes the top n chromosomes into
018: * the next generation. n can be specified. Which chromosomes are the best is
019: * decided by evaluating their fitness value.
020: *
021: * @author Klaus Meffert
022: * @since 1.1
023: */
024: public class BestChromosomesSelector extends NaturalSelector implements
025: ICloneable {
026: /** String containing the CVS revision. Read out via reflection!*/
027: private final static String CVS_REVISION = "$Revision: 1.49 $";
028:
029: /**
030: * Stores the chromosomes to be taken into account for selection
031: */
032: private Population m_chromosomes;
033:
034: /**
035: * Allows or disallows doublette chromosomes to be added to the selector
036: */
037: private boolean m_doublettesAllowed;
038:
039: /**
040: * Indicated whether the list of added chromosomes needs sorting
041: */
042: private boolean m_needsSorting;
043:
044: /**
045: * Comparator that is only concerned about fitness values
046: */
047: private FitnessValueComparator m_fitnessValueComparator;
048:
049: private BestChromosomesSelectorConfig m_config = new BestChromosomesSelectorConfig();
050:
051: /**
052: * Default constructor.<p>
053: * Attention: The configuration used is the one set with the static method
054: * Genotype.setConfiguration.
055: *
056: * @throws InvalidConfigurationException
057: *
058: * @author Klaus Meffert
059: * @since 1.1
060: */
061: public BestChromosomesSelector()
062: throws InvalidConfigurationException {
063: this (Genotype.getStaticConfiguration());
064: }
065:
066: /**
067: * Using original rate of 1.0
068: *
069: * @param a_config the configuration to use
070: * @throws InvalidConfigurationException
071: *
072: * @author Klaus Meffert
073: * @since 3.0
074: */
075: public BestChromosomesSelector(final Configuration a_config)
076: throws InvalidConfigurationException {
077: this (a_config, 1.0d);
078: }
079:
080: public BestChromosomesSelector(final Configuration a_config,
081: final double a_originalRate)
082: throws InvalidConfigurationException {
083: super (a_config);
084: m_chromosomes = new Population(a_config);
085: m_needsSorting = false;
086: m_doublettesAllowed = true;
087: setOriginalRate(a_originalRate);
088: m_fitnessValueComparator = new FitnessValueComparator();
089: }
090:
091: /**
092: * Add a Chromosome instance to this selector's working pool of Chromosomes.
093: * @param a_chromosomeToAdd the specimen to add to the pool
094: *
095: * @author Klaus Meffert
096: * @since 1.1
097: */
098: protected void add(final IChromosome a_chromosomeToAdd) {
099: // If opted-in: Check if chromosome already added
100: // This speeds up the process by orders of magnitude but could lower the
101: // quality of evolved results because of fewer Chromosome's used!!!
102: if (!getDoubletteChromosomesAllowed()
103: && m_chromosomes.getChromosomes().contains(
104: a_chromosomeToAdd)) {
105: return;
106: }
107: // New chromosome, insert it into the sorted collection of chromosomes
108: a_chromosomeToAdd.setIsSelectedForNextGeneration(false);
109: if (getDoubletteChromosomesAllowed()) {
110: ICloneHandler cloner = getConfiguration().getJGAPFactory()
111: .getCloneHandlerFor(a_chromosomeToAdd, null);
112: if (cloner != null) {
113: try {
114: m_chromosomes.addChromosome((IChromosome) cloner
115: .perform(a_chromosomeToAdd, null, null));
116: } catch (Exception ex) {
117: ex.printStackTrace();
118: m_chromosomes.addChromosome(a_chromosomeToAdd);
119: }
120: } else {
121: m_chromosomes.addChromosome(a_chromosomeToAdd);
122: }
123: } else {
124: m_chromosomes.addChromosome(a_chromosomeToAdd);
125: }
126: // Indicate that the list of chromosomes to add needs sorting.
127: // -----------------------------------------------------------
128: m_needsSorting = true;
129: }
130:
131: /**
132: * Selects a given number of Chromosomes from the pool that will move on
133: * to the next generation population. This selection will be guided by the
134: * fitness values. The chromosomes with the best fitness value win.
135: *
136: * @param a_from_pop the population the Chromosomes will be selected from
137: * @param a_to_pop the population the Chromosomes will be added to
138: * @param a_howManyToSelect the number of Chromosomes to select
139: *
140: * @author Klaus Meffert
141: * @since 1.1
142: */
143: public void select(final int a_howManyToSelect,
144: final Population a_from_pop, final Population a_to_pop) {
145: if (a_from_pop != null) {
146: int popSize = a_from_pop.size();
147: if (popSize < 1) {
148: throw new IllegalStateException(
149: "Population size must be greater 0");
150: }
151: for (int i = 0; i < popSize; i++) {
152: add(a_from_pop.getChromosome(i));
153: }
154: }
155: int canBeSelected;
156: int chromsSize = m_chromosomes.size();
157: if (chromsSize < 1) {
158: throw new IllegalStateException(
159: "Number of chromosomes must be greater 0");
160: }
161: if (a_howManyToSelect > chromsSize) {
162: canBeSelected = chromsSize;
163: } else {
164: canBeSelected = a_howManyToSelect;
165: }
166: int neededSize = a_howManyToSelect;
167: double origRate;
168: origRate = m_config.m_originalRate;
169: if (origRate < 1.0d) {
170: canBeSelected = (int) Math.round((double) canBeSelected
171: * origRate);
172: if (canBeSelected < 1) {
173: canBeSelected = 1;
174: }
175: }
176: // Sort the collection of chromosomes previously added for evaluation.
177: // Only do this if necessary.
178: // -------------------------------------------------------------------
179: if (m_needsSorting) {
180: Collections.sort(m_chromosomes.getChromosomes(),
181: m_fitnessValueComparator);
182: m_needsSorting = false;
183: }
184: // To select a chromosome, we just go thru the sorted list.
185: // --------------------------------------------------------
186: IChromosome selectedChromosome;
187: for (int i = 0; i < canBeSelected; i++) {
188: selectedChromosome = m_chromosomes.getChromosome(i);
189: selectedChromosome.setIsSelectedForNextGeneration(true);
190: a_to_pop.addChromosome(selectedChromosome);
191: }
192: if (getDoubletteChromosomesAllowed()) {
193: int toAdd;
194: toAdd = neededSize - a_to_pop.size();
195: // Add existing Chromosome's to fill up the return
196: // result to contain the desired number of Chromosome's.
197: // -----------------------------------------------------
198: for (int i = 0; i < toAdd; i++) {
199: selectedChromosome = m_chromosomes.getChromosome(i
200: % chromsSize);
201: ICloneHandler cloner = getConfiguration()
202: .getJGAPFactory().getCloneHandlerFor(
203: selectedChromosome, null);
204: if (cloner != null) {
205: try {
206: selectedChromosome = (IChromosome) cloner
207: .perform(selectedChromosome, null, null);
208: } catch (Exception ex) {
209: ex.printStackTrace();
210: }
211: }
212: selectedChromosome.setIsSelectedForNextGeneration(true);
213: a_to_pop.addChromosome(selectedChromosome);
214: }
215: }
216: }
217:
218: /**
219: * Empties out the working pool of Chromosomes.
220: *
221: * @author Klaus Meffert
222: * @since 1.1
223: */
224: public void empty() {
225: // clear the list of chromosomes
226: // -----------------------------
227: m_chromosomes.getChromosomes().clear();
228: m_needsSorting = false;
229: }
230:
231: /**
232: * Determines whether doublette chromosomes may be added to the selector or
233: * will be ignored.
234: *
235: * @param a_doublettesAllowed true: doublette chromosomes allowed to be
236: * added to the selector. FALSE: doublettes will be ignored and not added
237: *
238: * @author Klaus Meffert
239: * @since 2.0
240: */
241: public void setDoubletteChromosomesAllowed(
242: final boolean a_doublettesAllowed) {
243: m_doublettesAllowed = a_doublettesAllowed;
244: }
245:
246: /**
247: * @return true: doublette chromosomes allowed to be added to the selector,
248: * false: this is sort of risky and might lead to unexpected population sizes
249: * during evolution!
250: *
251: * @author Klaus Meffert
252: * @since 2.0
253: */
254: public boolean getDoubletteChromosomesAllowed() {
255: return m_doublettesAllowed;
256: }
257:
258: /**
259: * @return always true as no Chromosome can be returnd multiple times
260: *
261: * @author Klaus Meffert
262: * @since 2.0
263: */
264: public boolean returnsUniqueChromosomes() {
265: return true;
266: }
267:
268: /**
269: * Setting this parameter controls how many chromosomes of the original
270: * population will be considered for selection to the next population. If
271: * the value is 1 then the whole original population is considered, if it is
272: * 0.5 only half of the chromosomes are considered. If doublettes are allowed,
273: * then a number of chromosomes missing (number of to be selected minus number
274: * selected) will be added.
275: * @param a_originalRate the rate of how many of the original chromosomes
276: * will be selected according to BestChromosomeSelector's strategy. The rest
277: * (non-original) of the chromosomes is added as duplicates
278: *
279: * @author Klaus Meffert
280: * @since 2.0
281: */
282: public void setOriginalRate(final double a_originalRate) {
283: if (a_originalRate < 0.0d || a_originalRate > 1.0d) {
284: throw new IllegalArgumentException(
285: "Original rate must be greater than"
286: + " zero and not greater than one!");
287: }
288: m_config.m_originalRate = a_originalRate;
289: }
290:
291: /**
292: *
293: * @return see setOriginalRate
294: *
295: * @author Klaus Meffert
296: * @since 2.0
297: */
298: public double getOriginalRate() {
299: return m_config.m_originalRate;
300: }
301:
302: class BestChromosomesSelectorConfig implements java.io.Serializable {
303: /**
304: * The rate of original Chromosomes selected. This is because we otherwise
305: * would always return the original input as output
306: */
307: public double m_originalRate;
308: }
309:
310: public boolean equals(Object a_o) {
311: if (a_o == null) {
312: return false;
313: }
314: BestChromosomesSelector other = (BestChromosomesSelector) a_o;
315: if (m_doublettesAllowed != other.m_doublettesAllowed) {
316: return false;
317: }
318: if (!m_fitnessValueComparator.getClass().getName().equals(
319: other.m_fitnessValueComparator.getClass().getName())) {
320: return false;
321: }
322: if (Math.abs(m_config.m_originalRate
323: - other.m_config.m_originalRate) > 0.001d) {
324: return false;
325: }
326: if (!m_chromosomes.equals(other.m_chromosomes)) {
327: return false;
328: }
329: return true;
330: }
331:
332: public Object clone() {
333: try {
334: BestChromosomesSelector sel = new BestChromosomesSelector(
335: getConfiguration(), m_config.m_originalRate);
336: sel.m_needsSorting = m_needsSorting;
337: // sel.m_chromosomes = (Population) m_chromosomes.clone();
338: sel.m_doublettesAllowed = m_doublettesAllowed;
339: return sel;
340: } catch (Throwable t) {
341: throw new CloneException(t);
342: }
343: }
344: }
|