1 /**
2 * @(#)PartiallyMappedCrossover.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.crossover.permutation;
10
11 import com.delhezi.ga.Chromosome;
12 import java.util.ArrayList;
13 import java.util.logging.Logger;
14
15 /**
16 * <code>PartiallyMatchedCrossover</code>: Krzyżowanie z częściowym
17 * odwzorowaniem; PartiallyMatchedCrossover (PMX).
18 * @version 1.0 2009-06-10
19 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
20 * Wojciech Wolszczak</a>
21 */
22 public class PartiallyMatchedCrossover
23 implements com.delhezi.ga.crossover.ICrossover {
24
25 /** Logger object. */
26 private static final Logger LOGGER =
27 Logger.getLogger(PartiallyMatchedCrossover.class.getName());
28
29 /** Delhezi Error Code. */
30 //private static final String DERC = "1-1.2-2-";
31
32 /** Class name. */
33 private static final String CLASS_NAME =
34 PartiallyMatchedCrossover.class.getName();
35
36 /**
37 * Funkcja crossover implementuje krzyżowanie z częściowym odwzorowaniem;
38 * Geny w chromosomach powinny być unikalne, ich wartości nie mogą
39 * sie powtarzać; Punkty krzyżowania wybierane są losowo w ciele funkcji.
40 * @param chromosome1 Chromosom.
41 * @param chromosome2 Chromosom.
42 * @since 1.0
43 */
44 @Override
45 public final void crossover(final Chromosome chromosome1,
46 final Chromosome chromosome2) {
47 LOGGER.entering(CLASS_NAME, "crossover",
48 new Object[] {chromosome1, chromosome2 });
49 assert (chromosome1.getGenes().length ==
50 chromosome2.getGenes().length);
51 if (chromosome1.getGenes().length == 0) {
52 return;
53 }
54
55 final int geneLength = chromosome1.getGenes().length;
56
57 //Losowe określenie dwóch punktów krzyżowania.
58 //cutLength = długość sekcji dopasowania min 1, max geneLength-1.
59 final int cutLength = (int) (Math.random() * (geneLength - 1) + 1);
60 final int cutpoint1 = (int) (Math.random() * (geneLength - cutLength));
61 final int cutpoint2 = cutpoint1 + cutLength;
62 this.crossover(chromosome1, chromosome2, cutpoint1, cutpoint2);
63 LOGGER.exiting(CLASS_NAME, "crossover");
64 }
65
66 /**
67 * Funkcja crossover implementuje krzyżowanie z częściowym odwzorowaniem;
68 * Geny w chromosomach powinny być unikalne, ich wartości nie mogą
69 * sie powtarzać.
70 * @param chromosome1 Chromosom.
71 * @param chromosome2 Chromosom.
72 * @param cutpoint1 Punkt krzyżowania np. xx|xxx|xx cutpoint1=2.
73 * @param cutpoint2 Punkt krzyżowania np. yy|yyy|yy cutpoint2=5.
74 * @since 1.0
75 */
76 public final void crossover(final Chromosome chromosome1,
77 final Chromosome chromosome2,
78 final int cutpoint1, final int cutpoint2) {
79 LOGGER.entering(CLASS_NAME, "crossover",
80 new Object[] {chromosome1, chromosome2, cutpoint1,
81 cutpoint2 });
82 assert (chromosome1.getGenes().length ==
83 chromosome2.getGenes().length);
84 assert (cutpoint1 < cutpoint2);
85 if (chromosome1.getGenes().length == 0) {
86 return;
87 }
88
89 final int geneLength = chromosome1.getGenes().length;
90
91 //Tworzymy geny potomków.
92 Object[] child1 = new Object[geneLength];
93 Object[] child2 = new Object[geneLength];
94 //Odwzorowania genów dla sekcji dopasowania.
95 ArrayList<Object> substring1 =
96 new ArrayList<Object>(cutpoint2 - cutpoint1);
97 ArrayList<Object> substring2 =
98 new ArrayList<Object>(cutpoint2 - cutpoint1);
99
100 //Dla sekcji dopasowania.
101 for (int i = cutpoint1; i < cutpoint2; i++) {
102 //Wypełnij sekcję dopasowania chromosomów potomnych genami
103 //drugiego rodzica.
104 child1[i] = chromosome2.getGene(i);
105 child2[i] = chromosome1.getGene(i);
106 //Stwórz pary genów stanowiące odwzorowania dla sekcji
107 //dopasowania.
108 substring1.add(chromosome2.getGene(i));
109 substring2.add(chromosome1.getGene(i));
110 }
111 //Optymalizacja tabeli odwzorowań dla sekcji dopasowania.
112 optSubstring(substring1, substring2);
113
114 // Dla każdego z genów spoza sekcji dopasowania.
115 for (int i = 0; i < geneLength; i++) {
116 if ((i < cutpoint1) || (i >= cutpoint2)) {
117
118 //Dla child1.
119 //Sprawdź czy w kolekcji substring1 występuje gen
120 //parent1.getGene(i). contains(obj) zwraca wartość true jeśli
121 //kolekcja zawiera obiekt identyczny z porównywanym
122 //obiektem "obj". W przypadku kiedy występuje zastosuj
123 //algorytm naprawy dla osobnika potomnyego zamieniając
124 //niedozwolony gen zgodnie z tabelą odwzorowań dla sekcji
125 //dopasowania. W przypadku kiedy nie występuje kopiuj gen.
126 if (substring1.contains(chromosome1.getGene(i))) {
127 //Określ na którym miejscu występuje.
128 int subI = substring1.indexOf(chromosome1.getGene(i));
129 child1[i] = substring2.get(subI);
130 } else {
131 child1[i] = chromosome1.getGene(i);
132 }
133
134 //Dla child2.
135 if (substring2.contains(chromosome2.getGene(i))) {
136 int subI = substring2.indexOf(chromosome2.getGene(i));
137 child2[i] = substring1.get(subI);
138 } else {
139 child2[i] = chromosome2.getGene(i);
140 }
141 } //if
142 } //for
143
144 chromosome1.setGenes(child1);
145 chromosome2.setGenes(child2);
146 LOGGER.exiting(CLASS_NAME, "crossover");
147 }
148
149 /**
150 * Optymalizacja tabeli odwzorowań dla sekcji dopasowania.
151 * Przykład dla substring1(6,9,2,1), substring2(3,2,7,9):
152 * 6 <-> 3
153 * 9 <-> 2
154 * 2 <-> 7
155 * 1 <-> 9
156 * "zlepiając" powyższe odwzorowanie otrzymujemy:
157 * 6 <-> 3
158 * 1 <-> 9 <-> 2 <-> 7
159 * co po skróceniu daje:
160 * 6 <-> 3
161 * 1 <-> 7
162 *
163 * @param <T> xxx
164 * @param substring1 Sekcja dopasowania.
165 * @param substring2 Sekcja dopasowania.
166 * @since 1.0
167 */
168 public final <T> void optSubstring(final ArrayList<T> substring1,
169 final ArrayList<T> substring2) {
170 LOGGER.entering(CLASS_NAME, "optSubstring",
171 new Object[] {substring1, substring2 });
172 for (int i = 0; i < substring1.size(); i++) {
173 if (substring1.get(i) == substring2.get(i)) {
174 substring1.remove(i);
175 substring2.remove(i);
176 i--;
177 } else {
178 //Sprawdź czy w kolekcji substring2 występuje gen
179 //substring1.get(i). contains(obj) zwraca wartość true jeśli
180 //kolekcja zawiera obiekt identyczny z porównywanym
181 //obiektem "obj".
182 if (substring2.contains(substring1.get(i))) {
183 //Określ na którym miejscu występuje.
184 int sub2i = substring2.indexOf(substring1.get(i));
185 substring2.set(sub2i, substring2.get(i));
186 substring1.remove(i);
187 substring2.remove(i);
188 i--;
189 }
190 }
191 }
192 LOGGER.exiting(CLASS_NAME, "optSubstring");
193 }
194 }