1 /**
2 * @(#)RouletteWheelEffectiveImplementation.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 java.util.LinkedList;
13 import java.util.Random;
14 //import java.util.logging.Logger;
15
16 /**
17 * Klasa <code>RouletteWheelEffectiveImplementation</code>: Metoda ruletki
18 * implementacja efektywna;
19 * Koszt stały + liniowy koszt inicjacji tablic zależny od wielkości
20 * populacji.
21 * M. D. Vose, A Linear Algorithm For Generating Random Numbers With a
22 * Given Distribution, IEEE Transactions on Software Engineering,
23 * vol. 17, no. 9, september 1991
24 *
25 * Metoda ruletki - (odmiana reprodukcji proporcjonalnej. W reprodukcji
26 * proporcjonalnej prawdopodobieństwo wyboru osobnika do puli rodzicielskiej
27 * zależne jest od wartości funkcji przystosowania danego osobnika;)
28 * @version 1.0 2010-01-10
29 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
30 * Wojciech Wolszczak</a>
31 */
32 public class RouletteWheelEffectiveImplementation extends AbstractRouletteWheel
33 implements ISelect {
34
35 /** Logger object. */
36 //private static final Logger LOGGER =
37 // Logger.getLogger(RouletteWheelEffectiveImplementation.class.getName());
38
39 /** Delhezi Error Code. */
40 //private static final String DERC = "1-8-3-";
41
42 /** */
43 private static Random random = new Random();
44
45 /**
46 * Efektywna implementacja funkcji ruletki.
47 * @param chromosomes Lista chromosomów.
48 * @param normals Tablica z określonym prawdopodobieństwem wyboru dla
49 * każdego z chromosomów.
50 * @return Wynikowa list chromosomów.
51 * @since 1.0
52 */
53 @Override
54 protected final LinkedList<Chromosome> rouletteWheelImpl(
55 final LinkedList<Chromosome> chromosomes,
56 final double [] normals) {
57
58 LinkedList<Chromosome> newChromosomes = new LinkedList<Chromosome>();
59 int[] alias = new int[chromosomes.size()]; //Tab. indeksów zapasowych
60
61 tableInitialize(chromosomes,normals,alias);
62
63 double roll;
64 int ui;
65
66 for (int i = 0; i < chromosomes.size(); i++) {
67 roll = random.nextDouble() * chromosomes.size() + 1;
68 ui = (int) roll; //Obcina część ułamkową.
69
70 if (i - ui <= normals[i]) {
71 newChromosomes.add(chromosomes.get(i).clone());
72 } else {
73 newChromosomes.add(chromosomes.get(alias[i]).clone());
74 }
75 }
76 return newChromosomes;
77 }
78
79 /** */
80 protected void tableInitialize(final LinkedList<Chromosome> chromosomes,
81 final double [] normals,
82 final int[] alias) {
83 int n = chromosomes.size();
84 double _1n = (double) 1 / n;
85
86 int[] small = new int[n]; //Stosy pomocnicze indeksów do ps
87 int[] large = new int[n]; //Stosy pomocnicze indeksów do ps
88
89 int l = 0;
90 int s = 0;
91 for (int j = 0; j < n; j++) {
92 if (normals[j] > _1n) {
93 large[l] = j;
94 l++;
95 } else {
96 small[s] = j;
97 s++;
98 }
99 }
100
101 // "redystrybucja" i przeskalowanie prawdopodobienstw
102 double[] prob = new double[n]; //Tab. względnych częstości
103 int j;
104 int k;
105 while ((s > 0) && (l > 0)) {
106 s = s - 1;
107 j = small[s];
108 l = l - 1;
109 k = large[l];
110 prob[j] = n * normals[j];
111 alias[j] = k;
112 normals[k] = normals[k] + (normals[j] - _1n);
113 if (normals[k] > _1n) {
114 l = l + 1;
115 } else {
116 small[s] = k;
117 s = s + 1;
118 }
119 }
120
121 // zostały tylko "kawałki" długosci 1/N
122 while (s > 0) {
123 s = s - 1;
124 prob[small[s]] = 1;
125 }
126 // naprawa błedów zaokraglen
127 while (l > 0) {
128 l = l - 1;
129 prob[large[l]] = 1;
130 }
131 }
132 }