1 /**
2 * @(#)_2Opt.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.mutation.heuristics;
10
11
12 import com.delhezi.ga.Chromosome;
13 import com.delhezi.ga.genes.Point;
14 import com.delhezi.ga.mutation.IMutation;
15 import java.util.Random;
16 //import java.util.logging.Logger;
17
18 /**
19 * Klasa <code>_2Opt</code>: Algorytm 2-opt;
20 *
21 * Algorytm lokalnego przeszukiwania; Wersja zrandomizowana, ilość prób
22 * podjętych do znalezienia lepszego rozwiązania okrela wartość counter;
23 * Przydatny w rozwiązaniu symetrycznego problemu komiwojażera
24 * (symmetric travelling salesman problem: STSP) – w którym dla każdego
25 * miasta istnieje połączenie do wszystkich pozostałych miast, oraz
26 * odległości pomiędzy miastami w obydwu kierunkach są sobie równe;
27 * Dla pary miast (węzłów) istnieje tylko jeden łuk o określonej długości;
28 *
29 * Losowo wybieramy 2 krawędzie; Jeśli długość cyklu po wymianie jest
30 * mniejsza niż przed, krawędzie są zamieniane; W innym przypadku
31 * przeszukiwana jest dostępna pula rozwiązań (iterakcyjnie wybieramy
32 * kolejne krawędzie) w celu znalezienia pierwszego wystąpienia
33 * cyklu lepszego.
34 * @version 1.0 2010-01-10
35 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
36 * Wojciech Wolszczak</a>
37 */
38 public class _2Opt implements IMutation {
39
40 /** Logger object. */
41 //private static final Logger LOGGER =
42 // Logger.getLogger(_2Opt.class.getName());
43
44 /** Delhezi Error Code. */
45 //private static final String DERC = "1-6.2-1-";
46
47 /** Random. */
48 private static Random random = new Random();
49
50 /**
51 * Implementacja funkcji mutacji 2-opt.
52 * @param chromosome Chromosom podlegający mutacji.
53 * @since 1.0
54 */
55 @Override
56 public final void mutation(final Chromosome chromosome) {
57
58 if (chromosome == null) {
59 throw new NullPointerException("Chromosome is null.");
60 }
61 int chromosomeSize = chromosome.size();
62 //Dla chromosomeSize <= 3 dowolne połączenie jest optymalne
63 if (chromosomeSize <= 3) {
64 return;
65 }
66
67 //Losuje liczny z zakresu od 0 do chromosomeSize i dodaje 1 gdyż
68 //krawęd 0 jest niepoprawna.
69 //Pierwsza krawędź edge1=2 dla xx-xxxxxxxx.
70 int edge1 = (int) (random.nextDouble() * chromosomeSize + 1);
71 //Druga krawędź edge2=5 dla xxxxx-xxxxx.
72 int edge2 = (int) (random.nextDouble() * chromosomeSize + 1);
73
74 //Korekta wyniku.
75 //Istnieje bardzo małe prawdopodobienstwo wylosowania liczby o
76 //wartosci chromosomeSize (poza zakresem), np. 4.999999999999999
77 //zaokraglane jest do 4, ale sprawdzę:
78 if (edge1 > chromosomeSize) {
79 edge1 = chromosomeSize;
80 }
81 if (edge2 > chromosomeSize) {
82 edge2 = chromosomeSize;
83 }
84
85 this.mutation(chromosome, edge1, edge2);
86 }
87
88 /**
89 * Implementacja funkcji mutacji 2-opt.Szukamy lepszego zarwiązania
90 * zaczynając od odwrócenia fragmentu genów wskazanych
91 * krawędziami edge1 i edge2. W przypadku niepowodzenia funkcja
92 * deterministycznie, metodycznie (inkrementuje edge1 i edge2),
93 * poszukuje lepszego rozwiązania.
94 * Uwaga;
95 * Ostania krawędź edge=chromosomeSize łączy ostatni gen z pierwszym
96 * Przykład: edge=8 xxxxxxxx-
97 * @param chromosome Chromosom podlegający mutacji.
98 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>.
99 * Przykład: edge1=4 dla xxxx-xxxx.
100 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>.
101 * Przykład: edge2=8 dla xxxxxx-xx.
102 * @since 1.0
103 */
104 protected final void mutation(Chromosome chromosome, int edge1,
105 int edge2) {
106 /** Licznik ilości podjętych prób.*/
107 int counter = 70;
108
109 //Chromosom nie może być wartością null.
110 assert chromosome != null : "Illegal argument chromosome: null";
111
112 int chromosomeSize = chromosome.size();
113
114 //Krawędź edge1 powininna zawierać się w obszare chromosomu.
115 assert (edge1 >= 1 && edge1 <= chromosomeSize)
116 : "Illegal argument edge1: " + edge1;
117 //Krawędź edge2 powininna zawierać się w obszare chromosomu.
118 assert (edge2 >= 1 && edge2 <= chromosomeSize)
119 : "Illegal argument edge2: " + edge2;
120
121 //Dla chromosomeSize <= 3 dowolne połączenie jest optymalne
122 if (chromosomeSize <= 3) {
123 return;
124 }
125
126 //Szukamy deterministycznie, wiec przestawiamy krawędzie
127 if (edge1 == edge2) {
128 edge2 = (edge2 == chromosomeSize) ? 1 : ++edge2;
129 }
130
131 int edge1iter = edge1;
132 int edge2iter = edge2;
133 boolean koniec = false;
134 int tmpEdge1IterNext;
135
136 //Sprawdź czy edge2iter nie jest bezpośrednio po edge1iter lub
137 //edge2iter nie pokrywa się z edge1iter.
138 //Jeśli tak to zmiana krawędzi nie zmieni porządku genów w chromosomie,
139 //więc od razu przestawiamy edge2iter do kolejnego przypadku.
140 tmpEdge1IterNext = (edge1iter == chromosomeSize) ? 1 : edge1iter + 1;
141 if (tmpEdge1IterNext == edge2iter) {
142 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
143 }
144
145 //Poszukuj iterakcyjnie lepszego cyklu dla ścieżki.
146 //Kręć PETLA 2 i zwiekszaj w każdym obrocie edge2iter+1 (lub
147 //przejdź na początek jeśli edge2iter dojdzie do końca tablicy).
148 //Jeśli edge2 zatoczyło koło to zwiększ edge1+1 i ponownie
149 //kręć PETLA 2 zwiększając w każdej iterakcji edge2+1
150 //do wyczerpania wszystkich możliwości.
151 //Pomiń pary ścieżek powtarzające się w edge1 i edge2.
152 for (int i1 = 0; i1 < chromosomeSize - 2; i1++) { //PETLA 1
153
154 // TU SĄ ZAWSZE PRZYGOTOWANE ZMIENNE edge1iter, edge1, edge2iter, edge2.
155
156 //----------- PETLA 2
157 koniec = false;
158 while (koniec == false) { //Zakończ jeśli zatoczysz pełne koło
159 //z edge2.
160 //Możlie wyjście przez break wówczas idziemy
161 //do pętli zewnętrznej do GOTO2
162
163 //Licznik ilości podjętych prób.
164 if (counter == 0) {
165 return;
166 }
167 counter--;
168
169 //Sprawdź, czy po zmianie uzyskamy lepszy cykl.
170 if (selectEdge(chromosome, edge1iter, edge2iter) == true) {
171 //System.out.println("ZNALAZLEM. Odcinki edge1=" + edge1 +
172 //", edge2=" + edge2 + " należy usunąć.");
173 changeEdge(chromosome, edge1iter, edge2iter);
174 return;
175 }
176
177 //Ustaw edge2iter o jeden dalej.
178 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
179
180 //ZAŁOŻENIE. edge1 nigdy nie jest rowne edge2
181 if (edge2iter == edge2) {
182 //WYJŚCIE Z PETLI2
183 //USTAW edge2iter do następnej petli.
184 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
185 koniec = true;
186
187 //Tu sprawdzamy czy po przesunieciu edge2iter wchodzi
188 //na edge1
189 //Nie musimy sprawdzać czy edge2 jest wewnątrz ścieżki
190 //"edge1-edge1iter", bo był przed ścieżką.
191 if (edge2iter == edge1) {
192 edge2iter = (edge1iter == chromosomeSize) ? 1
193 : edge1iter + 1;
194 }
195 } else { //(edge2iter != edge2)
196
197 //Sprawdź czy edge2iter wchodzi na edge1.
198 //Jeśli tak to przeskocz nim za ścieżką "edge1-edge1iter".
199 if (edge2iter == edge1) {
200 //USTAW edge2iter za ścieżką "edge1-edge1iter"
201 edge2iter = (edge1iter == chromosomeSize) ? 1
202 : edge1iter + 1;
203
204 //edge2 jest we wnetrzu "edge1-edge1iter"
205 //WYJŚCIE Z PETLI2
206 if ((edge2 <= edge1iter) && (edge2 >= edge1)) {
207 koniec = true;
208 break; //GOTO2
209 } else {
210 //Sprawdź czy po przeskoczeniu ścieżki nie trafisz
211 //edge2iter == edge2. Nie musisz sprawdzać, czy dalej
212 //nie ma "edge1-edge1iter", bo już była.
213 if (edge2iter == edge2) {
214 //USTAW edge2iter do następnej petli !!!
215 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
216 break; //GOTO2
217 }
218 }
219 } //if (edge2iter == edge1)
220 } //koniec //(edge2iter != edge2)
221 } //----------- koniec PETLA 2
222
223 //Tu wychodzimy z GOTO2
224
225 edge1iter = (edge1iter == chromosomeSize) ? 1 : edge1iter + 1;
226
227 //Ewentualna korekta edge2iter
228 if (edge2iter == edge1iter) {
229 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
230 }
231 }
232 }
233
234 /**
235 * Jeśli znaleziono lepszy cykl; Zamień "krzyżowo" ścieżki;
236 * Przykład:
237 * edge1=ab, edge2=cd
238 * Zawsze odwracamy odcinek bc.
239 * 1) dxxa-b12c-, edge1=ab=4, edge2=cd=8 -- wynik dxxa-c21b-
240 * 2) xxa-b12c-dxx, edge1=ab=3, edge2=cd=7 -- wynik xxa-c21b-dxx
241 * @param chromosome Chromosom.
242 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>
243 * np. edge1=4 dla xxxx-xxxx.
244 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>
245 * np. edge2=8 dla xxxxxx-xx.
246 * @since 1.0
247 */
248 protected final void changeEdge(Chromosome chromosome,
249 final int edge1,
250 final int edge2) {
251 int chromosomeSize = chromosome.size();
252 int pA;
253 int pB;
254 int pC;
255 int pD;
256
257 //Zawsze odwracamy punkty pomiędzy B a C.
258
259 if (edge1 == chromosomeSize) { //bxxxxxxxxa-
260 pA = edge1 - 1; //geny licza sie od 0
261 pB = 0;
262 } else { //xxxxxa-bxxx
263 pA = edge1 - 1; //geny licza sie od 0
264 pB = edge1;
265 }
266
267 if (edge2 == chromosomeSize) { //dxxxxxxxxc-
268 pC = edge2 - 1; //geny licza sie od 0
269 pD = 0;
270 } else { //xxxxxc-dxxx
271 pC = edge2 - 1; //geny licza sie od 0
272 pD = edge2;
273 }
274
275 //Liczba genów podlegających inwersji.
276 int inversionGenes = (pB < pC) ? pC - pB + 1
277 : (chromosomeSize - pB) + pC + 1;
278
279 //tmpGenes - sekcja inwersji po operacji inwersji.
280 Object[] invGenes = new Object[inversionGenes];
281 int ii;
282 if (pB < pC) {
283 ii = pC;
284 for (int i = 0; i < invGenes.length; i++) {
285 invGenes[i] = chromosome.getGene(ii);
286 ii--;
287 }
288 } else {
289 ii = 0;
290 for (int i = pC; i >= 0; i--) {
291 invGenes[ii++] = chromosome.getGene(i);
292 }
293
294 for (int i = chromosomeSize - 1; i >= pB; i--) {
295 invGenes[ii++] = chromosome.getGene(i);
296 }
297 }
298
299 int inv = 0;
300 if (edge1 < edge2) {
301 for (int i = edge1; i < edge2; i++) {
302 chromosome.setGene(i, invGenes[inv]);
303 inv++;
304 }
305 } else {
306 for (int i = edge1; i < chromosomeSize; i++) {
307 chromosome.setGene(i, invGenes[inv]);
308 inv++;
309 }
310 for (int i = 0; i < edge2; i++) {
311 chromosome.setGene(i, invGenes[inv]);
312 inv++;
313 }
314 }
315 chromosome.changed();
316 }
317
318 /**
319 * Funkcja sprawdza, czy udało sie wybrać właściwe krawędzie do
320 * usunięcia; Cykl po usunięciu wybraych krawędzi (edge1, edge2) oraz
321 * po utworzeniu nowych "na krzyż" powinien być badziej optymalny;
322 * Przykład:
323 * dxxa-bxxc-, edge1=ab=4, edge2=cd=8
324 * Jeśli długości odcinków ac+bd jest mniejsza niż ab+cd to
325 * znaleziono cykl lepszy (zwróć true).
326 * @param chromosome Chromosom.
327 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>
328 * np. edge1=4 dla xxxx-xxxx.
329 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>
330 * np. edge2=8 dla xxxxxx-xx.
331 * @return true, w przypadku kiedy usuniecie wybranych odcinków i
332 * utworzenie nowych skraca cykl.
333 * @since 1.0
334 */
335 protected final boolean selectEdge(Chromosome chromosome,
336 final int edge1,
337 final int edge2) {
338
339 int chromosomeSize = chromosome.size();
340 double sizeAB;
341 double sizeCD;
342 double sizeAC;
343 double sizeDB;
344 Point pA, pB, pC, pD;
345
346 if (edge1 == chromosomeSize) { //bxxxxxxxxa-
347 pA = (Point) chromosome.getGene(edge1 - 1); //geny licza sie od 0
348 pB = (Point) chromosome.getGene(0);
349 } else { //xxxxxa-bxxx
350 pA = (Point) chromosome.getGene(edge1 - 1); //geny licza sie od 0
351 pB = (Point) chromosome.getGene(edge1);
352 }
353 sizeAB = distance(pA.getx(), pA.gety(), pB.getx(), pB.gety());
354
355 if (edge2 == chromosomeSize) { //dxxxxxxxxc-
356 pC = (Point) chromosome.getGene(edge2 - 1); //geny licza sie od 0
357 pD = (Point) chromosome.getGene(0);
358 } else { //xxxxxc-dxxx
359 pC = (Point) chromosome.getGene(edge2 - 1); //geny licza sie od 0
360 pD = (Point) chromosome.getGene(edge2);
361 }
362 sizeCD = distance(pC.getx(), pC.gety(), pD.getx(), pD.gety());
363
364 sizeAC = distance(pA.getx(), pA.gety(), pC.getx(), pC.gety());
365 sizeDB = distance(pD.getx(), pD.gety(), pB.getx(), pB.gety());
366
367 //if ac+bd<ab+cd ZANLEZIONO lepszy cykl
368 if (sizeAC + sizeDB < sizeAB + sizeCD) {
369 return true;
370 } else {
371 return false;
372 }
373 }
374
375 /**
376 * Odległość pomiędzy dwoma punktami w układzie współrzędnych
377 * (wzór na odległość Euklidesową pomiędzy dwoma punktami).
378 * @param x1 Wspłórzędna x pierwszego punktu.
379 * @param y1 Wspłórzędna y pierwszego punktu.
380 * @param x2 Wspłórzędna x drugiego punktu.
381 * @param y2 Wspłórzędna y drugiego punktu.
382 * @return Odległość.
383 * @since 1.0
384 */
385 private double distance(final int x1, final int y1, final int x2,
386 final int y2) {
387 int xdiff = x1 - x2;
388 int ydiff = y1 - y2;
389 return Math.sqrt(xdiff * xdiff + ydiff * ydiff);
390 }
391 }