1 /**
2 * @(#)AbstractRouletteWheel.java
3 * Copyright (C) 2008-2011 delhezi.com
4 *
5 * This class is released under the:
6 * GNU Lesser General Public License (LGPL) version 3 or later.
7 * http://www.gnu.org/copyleft/lesser.html
8 */
9 package com.delhezi.ga.selection;
10
11 import com.delhezi.ga.Chromosome;
12 import com.delhezi.ga.exception.GeneticAlgorithmException;
13 import java.util.LinkedList;
14 //import java.util.logging.Logger;
15
16 /**
17 * <code>AbstractRouletteWheel</code>: Metoda ruletki (odmiana reprodukcji
18 * proporcjonalnej. W reprodukcji proporcjonalnej prawdopodobieństwo wyboru
19 * osobnika do puli rodzicielskiej zależne jest od wartości funkcji
20 * przystosowania danego osobnika.)
21 * <p/>
22 * <b>Metoda źle sobie radzi z mała rozpiętością wartości wskaźnika
23 * przystosowania</b> (selekcja praktycznie nie zachodzi, w przypadku kiedy
24 * wartości wskaźnika przystosowania dozwolone są dla przedziału np. 0-100000,
25 * a wszystkie chromosomy mają fitness z przedziału 950000-100000).
26 * <p/>
27 * Prawdopodobieństwo wybrania każdego z osobników do nowej populacji
28 * określa się wzorem:
29 * <br/>
30 * a) w przypadku maksymalizacji funkcji celu:
31 * <code>wartość przystosowania danego osobnika / suma wartości
32 * przystosowania wszystkich osobników</code>,
33 * <br/>
34 * b) w przypadku minimalizacji funkcji celu:
35 * <code>odwrotność wartości przystosowania danego osobnika * odwrotność
36 * sumy odwrotności wartości przystosowania wszystkich osobników</code>.
37 * @version 1.0 2010-01-10
38 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
39 * Wojciech Wolszczak</a>
40 */
41 abstract class AbstractRouletteWheel {
42
43 /** Logger object. */
44 //private static final Logger LOGGER =
45 // Logger.getLogger(AbstractRouletteWheel.class.getName());
46
47 /** Delhezi Error Code. */
48 //private static final String DERC = "1-8-1-";
49
50 /**
51 * Funkcja selekcji.
52 * @param chromosomes Lista chromosomów.
53 * @return Wynikowa list chromosomów.
54 * @throws GeneticAlgorithmException (chromosomes == null)
55 * or (fitnessFunction == null)
56 * @since 1.0
57 */
58 public final LinkedList<Chromosome> select(
59 final LinkedList<Chromosome> chromosomes)
60 throws GeneticAlgorithmException {
61 if (chromosomes == null) {
62 throw new IllegalArgumentException("chromosomes is null.");
63 }
64 //Jest tylko jeden chromosom.
65 if (chromosomes.size() < 2) {
66 return chromosomes;
67 }
68
69 this.setVariable(chromosomes);
70
71 //Tablica z określonym prawdopodobieństwem wyboru dla każdego z
72 //chromosomów.
73 double[] normals = new double[chromosomes.size()];
74 int i = 0;
75 for (Chromosome ch : chromosomes) {
76 if (ch.isFitnessMaximisation() == true) {
77 normals[i] = ch.getFitness() / sumFitness;
78 } else {
79 normals[i] = 1 / (ch.getFitness() * sumaOdwrotnosci);
80 }
81 i++;
82 }
83
84 //double sump=0;
85 //for(int z = 0; z < chromosomes.size(); z++){
86 // sump+=normals[z];
87 // System.out.println("normals["+z+"] = " + normals[z]
88 // + ", chromosom = " + chromosomes.get(z).getFitness());
89 //}
90 //System.out.println("sum. prawd. = " +sump);//Suma prawdopodobieństw
91 //powinna być równa 1.
92
93 return this.rouletteWheelImpl(chromosomes, normals);
94 }
95
96 /**
97 * Implementacja metody ruletki.
98 * @param chromosomes Lista chromosomów.
99 * @param normals Tablica z określonym prawdopodobieństwem wyboru dla
100 * każdego z chromosomów.
101 * @return Wynikowa list chromosomów.
102 * @since 1.0
103 */
104 abstract LinkedList<Chromosome> rouletteWheelImpl(
105 final LinkedList<Chromosome> chromosomes,
106 final double[] normals);
107
108 /**
109 * Funkcja pomocnicza, wylicza wartości: minIndex,
110 * minFitness, maxIndex, maxFitness, sumFitness, odwrotnoscSumyOdwrotnosci.
111 * @param chromosomes Lista chromosomów.
112 * @throws GeneticAlgorithmException xxx
113 * @since 1.0
114 */
115 private final void setVariable(final LinkedList<Chromosome> chromosomes)
116 throws GeneticAlgorithmException {
117 assert chromosomes != null : "Illegal argument chromosomes: null";
118
119 double fitness;
120 this.minFitness = chromosomes.getFirst().getFitness();
121 this.maxFitness = chromosomes.getFirst().getFitness();
122 double tmpSumaOdwrotnosci = 0;
123
124 for (Chromosome ch : chromosomes) {
125 fitness = ch.getFitness();
126 this.sumFitness += fitness;
127 tmpSumaOdwrotnosci += (1 / ch.getFitness());
128 if (fitness < this.minFitness) {
129 this.minFitness = fitness;
130 }
131 if (fitness > this.maxFitness) {
132 this.maxFitness = fitness;
133 }
134 }
135 this.sumaOdwrotnosci = tmpSumaOdwrotnosci;
136 }
137
138 /** Najmniejsza znaleziona wartość wskaźnika przystosowania. */
139 private double minFitness;
140
141 /** Największa znaleziona wartość wskaźnika przystosowania. */
142 private double maxFitness;
143
144 /** Suma wartości wskaźników przystosowania osobników w całej populacji.*/
145 private double sumFitness;
146
147 /**
148 * Suma odwrotności wskaźników przystosowania osobników w całej populacji.
149 */
150 private double sumaOdwrotnosci;
151 }