1 /**
2 * @(#)LinearRanking.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.Collections;
14 import java.util.LinkedList;
15 import java.util.ListIterator;
16 import java.util.Random;
17 //import java.util.logging.Logger;
18
19 /**
20 * Klasa <code>LinearRanking</code>: Selekcja liniowa wg rang.
21 * @version 1.0 2010-01-10
22 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
23 * Wojciech Wolszczak</a>
24 */
25 public class LinearRanking implements ISelect {
26
27 /** Logger object. */
28 //private static final Logger LOGGER =
29 // Logger.getLogger(LinearRanking.class.getName());
30
31 /** Delhezi Error Code. */
32 //private static final String DERC = "1-8-2-";
33
34 private static Random random = new Random();
35
36 /**
37 * Funkcja select.
38 * @param chromosomes Lista chromosomów.
39 * @return Wynikowa list chromosomów.
40 * @throws GeneticAlgorithmException (chromosomes == null)
41 * or (fitnessFunction == null)
42 * @since 1.0
43 */
44 public final LinkedList<Chromosome> select(final LinkedList<Chromosome> chromosomes)
45 throws GeneticAlgorithmException {
46 if (chromosomes == null) {
47 throw new IllegalArgumentException("chromosomes is null.");
48 }
49 //Jest tylko jeden chromosom.
50 if (chromosomes.size() < 2) {
51 return chromosomes;
52 }
53
54 //Sortuje chromosomy dla maksymalizacji: od najmniejszej do najwiekszej,
55 //dla minimalizacji: od najwiekszej do najmniejszej wartosci fitness.
56 Collections.sort(chromosomes);
57
58 LinkedList<Chromosome> newChromosomes = new LinkedList<Chromosome>();
59
60 //Zaraz po utworzeniu iterator wskazuje na specjalną wartość przed
61 //pierwszym elementem, tak by pierwszy element był pobrany
62 //przy pierwszym wywołaniu next()
63 ListIterator<Chromosome> itr = chromosomes.listIterator(0);
64
65 int j = 1; //Pozycja rozpatrywanego chromosomu w populacji.
66 double roll;
67 boolean wylosowany;
68 Chromosome chTmp;
69 double normal;
70 //Tworzymy uwzględniając przystosowanie NOWĄ listę chromosomów
71 //newChromosomes o wielkości równej chromosomes.size().
72 for (int i = 0; i < chromosomes.size(); i++) {
73 wylosowany = false;
74 while (!wylosowany) { //Losujemy i-ty chromosom do newChromosomes.
75
76 //Wróć na początek listy jeśli doszedłeś do końca.
77 if (j > chromosomes.size()) {
78 itr = chromosomes.listIterator(0);
79 j = 1;
80 }
81
82 roll = random.nextDouble() / chromosomes.size();
83 normal = getNormal(chromosomes.size(), j);
84 chTmp = itr.next();
85
86 if (normal >= roll) {
87 newChromosomes.add(chTmp.clone());
88 wylosowany = true;
89 }
90 j++;
91 }
92 }
93 return newChromosomes;
94 }
95
96 /**
97 * Wylicza prawdopodobieństwo wybrania chromosomu.
98 * @param populationSize Wielkość populacji.
99 * @param chromosomePosition Pozycja chromosomu w populacji dla którego
100 * wyliczamy prawdopodobieństwo wybrania. Wymagane jest wcześniejsze
101 * posortowanie populacji, dla przypadku
102 * maksymalizacji: od najmniejszej do najwiekszej,
103 * dla minimalizacji: od najwiekszej do najmniejszej wartości fitness.
104 * @return Prawdopodobieństwo wybrania chromosomu <0,1>.
105 * @since 1.0
106 */
107 private final double getNormal(int populationSize,
108 int chromosomePosition) {
109 return (double)(2 * chromosomePosition) /
110 (populationSize * (populationSize + 1));
111 }
112 }