1 /**
2 * @(#)LinKernighan.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 import com.delhezi.ga.Chromosome;
12 import com.delhezi.ga.genes.Point;
13 import com.delhezi.ga.mutation.IMutation;
14 import java.util.Random;
15 //import java.util.logging.Logger;
16
17 /**
18 * Klasa <code>LinKernighan</code>: Algorytm Lina-Kernighana;
19 * LinKernighan (LK);
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 *
35 *
36 * http://www.akira.ruc.dk/~keld/research/LKH/
37 * ZOBACZ TO
38 *
39 * Algorytm lokalnego poszukiwania ze zmienną liczbą wymienianych krawędzi
40 * zależną od poprawy całkowitej ściezki; Dedykowany dla TSP;
41 *
42 * Tworzony jest łańcuch kolejnych wymian, który kończy się, gdy nie można
43 * znaleźć kolejnej wymiany poprawiającej długość cyklu; W każdej
44 * iteracji następuje próba utworzenia kolejnego łańcucha o co najmniej
45 * 2 elementach, jeśli to się nie powiedzie algorytm kończy działanie.
46 *
47 *
48 * @version 1.0 2010-01-10
49 * @author <a href="mailto:wojciech.wolszczak@delhezi.com">
50 * Wojciech Wolszczak</a>
51 */
52 public class LinKernighan implements IMutation {
53
54 /** Logger object. */
55 //private static final Logger LOGGER =
56 // Logger.getLogger(LinKernighan.class.getName());
57
58 /** Delhezi Error Code. */
59 //private static final String DERC = "1-6.2-3-";
60
61
62 /** Random. */
63 private static Random random = new Random();
64
65 /**
66 * Implementacja funkcji mutacji 2-opt.
67 * @param chromosome Chromosom podlegający mutacji.
68 * @since 1.0
69 */
70 @Override
71 public final void mutation(final Chromosome chromosome) {
72
73 if (chromosome == null) {
74 throw new NullPointerException("Chromosome is null.");
75 }
76 int chromosomeSize = chromosome.size();
77 //Dla chromosomeSize <= 3 dowolne połączenie jest optymalne
78 if (chromosomeSize <= 3) {
79 return;
80 }
81
82 //Losuje liczny z zakresu od 0 do chromosomeSize i dodaje 1 gdyż
83 //krawęd 0 jest niepoprawna.
84 //Pierwsza krawędź edge1=2 dla xx-xxxxxxxx.
85 int edge1 = (int) (random.nextDouble() * chromosomeSize + 1);
86 //Druga krawędź edge2=5 dla xxxxx-xxxxx.
87 int edge2 = (int) (random.nextDouble() * chromosomeSize + 1);
88
89 //Korekta wyniku.
90 //Istnieje bardzo małe prawdopodobienstwo wylosowania liczby o
91 //wartosci chromosomeSize (poza zakresem), np. 4.999999999999999
92 //zaokraglane jest do 4, ale sprawdzę:
93 if (edge1 == chromosomeSize + 1) {
94 edge1 = chromosomeSize;
95 }
96 if (edge2 == chromosomeSize + 1) {
97 edge2 = chromosomeSize;
98 }
99
100 this.mutation(chromosome, edge1, edge2);
101 }
102
103 /**
104 * Implementacja funkcji mutacji Lina-Kernighana.Szukamy lepszego
105 * zarwiązania zaczynając od odwrócenia fragmentu genów wskazanych
106 * krawędziami edge1 i edge2. W przypadku niepowodzenia funkcja
107 * deterministycznie, metodycznie (inkrementuje edge1 i edge2),
108 * poszukuje lepszego rozwiązania.
109 * Uwaga;
110 * Ostania krawędź edge=chromosomeSize łączy ostatni gen z pierwszym
111 * Przykład: edge=8 xxxxxxxx-
112 * @param chromosome Chromosom podlegający mutacji.
113 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>.
114 * Przykład: edge1=4 dla xxxx-xxxx.
115 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>.
116 * Przykład: edge2=8 dla xxxxxx-xx.
117 * @since 1.0
118 */
119 protected final void mutation(Chromosome chromosome,
120 int edge1,
121 int edge2) {
122
123 /** Licznik ilości podjętych prób.*/
124 int counter = 50;
125
126 //Walidacja parametrów wejściowych.
127
128 //Chromosom nie może być wartością null.
129 assert chromosome != null : "Illegal argument chromosome: null";
130
131 int chromosomeSize = chromosome.size();
132
133 //Krawędź edge1 powininna zawierać się w obszare chromosomu.
134 assert (edge1 >= 1 && edge1 <= chromosomeSize)
135 : "Illegal argument edge1: " + edge1;
136 //Krawędź edge2 powininna zawierać się w obszare chromosomu.
137 assert (edge2 >= 1 && edge2 <= chromosomeSize)
138 : "Illegal argument edge2: " + edge2;
139
140 //Dla chromosomeSize <=3 dowolne połączenie jest optymalne
141 if (chromosomeSize <= 3) {
142 return;
143 }
144
145 //Koniec walidacji parametrów wejściowych.
146
147 //Szukamy deterministycznie, wiec przestawiamy krawędzie
148 if (edge1 == edge2) {
149 edge2 = (edge2 == chromosomeSize) ? 1 : ++edge2;
150 }
151
152 int edge1iter = edge1;
153 int edge2iter = edge2;
154 boolean koniec = false;
155 int tmpEdge1IterNext;
156
157 //Sprawddż czy edge2iter nie jest bezpośrednio po edge1iter
158 //Jeśli tak to zmiana krawędzi nie zmieni porządku genów w chromosomie,
159 //więc od racu przestaw edge2iter do kolejnego przypadku.
160 tmpEdge1IterNext = (edge1iter == chromosomeSize) ? 1 : edge1iter + 1;
161 if (tmpEdge1IterNext == edge2iter) {
162 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
163 }
164
165 //Poszukuj iterakcyjnie lepszego cyklu dla ścieżki.
166 //Jeśli nie znaleziono lepszego cyklu w pierwszym obrocie PETLI 2 to
167 //kręć PETLA 2 i zwiekszaj w każdym obrocie edge2iter+1 (lub
168 //przejdź na początek tablicy jeśli edge2 dojdzie do końca tablicy).
169 //Jeśli edge2 zatoczyło koło to zwiększ edge1+1 i ponownie
170 //kręć PETLA 2 zwiększając w każdej iterakcji edge2+1
171 //do wyczerpania wszystkich możliwości.
172 //Pomiń pary ścieżek powtarzające się w edge1 i edge2.
173 for (int i1 = 0; i1 < chromosomeSize - 2; i1++) { //PETLA 1
174
175 // TU SĄ ZAWSZE PRZYGOTOWANE ZMIENNE edge1iter, edge1, edge2iter, edge2.
176
177 //----------- PETLA 2
178 koniec = false;
179 while (koniec == false) { //Zakończ jeśli zatoczysz
180 //pełne koło z edge2.
181 //Możlie wyjście przez break wówczas idziemy
182 //do pętli zewnętrznej do GOTO2
183
184 //Licznik ilości podjętych prób.
185 if (counter == 0) {
186 return;
187 }
188 counter--;
189
190
191 //Sprawdź, czy po zmianie uzyskamy lepszy cykl.
192 if (kwpj(chromosome, edge1iter, edge2iter) > 0) {
193 //System.out.println("ZNALAZLEM. Odcinki edge1=" + edge1 +
194 //", edge2=" + edge2 + " należy usunąć.");
195 changeEdge(chromosome, edge1iter, edge2iter);
196 return; //GOTO2 Wychodzimy z 2Opt, nie ma sensu usawiać
197 //innych zmiennych.
198 }
199
200 //Ustaw edge2iter o jeden dalej.
201 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
202
203 //ZAŁOŻENIE. edge1 nigdy nie jest rowne edge2
204 if (edge2iter == edge2) {
205 //WYJŚCIE Z PETLI2
206 //USTAW edge2iter do następnej petli.
207 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
208 koniec = true;
209
210 //Tu sprawdzamy czy po przesunieciu nextEdge2 wchodzi
211 //na edge1
212 //Nie mysimy sprawdzać czy edge2 jest wewnątrz ścieżki
213 //"edge1-edge1iter", bo był przed ścieżką.
214 if (edge2iter == edge1) {
215 edge2iter = (edge1iter == chromosomeSize) ? 1
216 : edge1iter + 1;
217 }
218 } else { //(edge2iter != edge2)
219
220 //Sprawdź czy edge2iter wchodzi na edge1.
221 //Jeśli tak to przeskocz nim za ścieżką "edge1-edge1iter".
222 if (edge2iter == edge1) {
223 //USTAW edge2iter za ścieżką "edge1-edge1iter"
224 edge2iter = (edge1iter == chromosomeSize) ? 1
225 : edge1iter + 1;
226
227 //edge2 jest we wnetrzu "edge1-edge1iter"
228 //WYJŚCIE Z PETLI2
229 if ((edge2 <= edge1iter) && (edge2 >= edge1)) {
230 koniec = true;
231 break; //GOTO2
232 } else {
233 //Sprawdź czy po przeskoczeniu ścieżki nie trafisz
234 //edge2iter == edge2. Nie musisz sprawdzać, czy dalej
235 //nie ma "edge1-edge1iter", bo już była.
236 if (edge2iter == edge2) {
237 //USTAW edge2iter do następnej petli !!!
238 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
239 break; //GOTO2
240 }
241 }
242 } //if (edge2iter == edge1)
243 } //koniec //(edge2iter != edge2)
244 } //----------- koniec PETLA 2
245
246 //Tu wychodzimy z GOTO2
247
248 edge1iter = (edge1iter == chromosomeSize) ? 1 : edge1iter + 1;
249
250 //Ewentualna korekta edge2iter
251 if (edge2iter == edge1iter) {
252 edge2iter = (edge2iter == chromosomeSize) ? 1 : edge2iter + 1;
253 }
254 }
255 }
256
257 /**
258 * Jeśli znaleziono lepszy cykl; Zamień "krzyżowo" ścieżki;
259 * Przykład:
260 * edge1=ab, edge2=cd
261 * Zawsze odwracamy odcinek bc.
262 * 1) dxxa-b12c-, edge1=ab=4, edge2=cd=8 -- wynik dxxa-c21b-
263 * 2) xxa-b12c-dxx, edge1=ab=3, edge2=cd=7 -- wynik xxa-c21b-dxx
264 * @param chromosome Chromosom.
265 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>
266 * np. edge1=4 dla xxxx-xxxx.
267 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>
268 * np. edge2=8 dla xxxxxx-xx.
269 *
270 */
271 protected final void changeEdge(Chromosome chromosome,
272 final int edge1,
273 final int edge2) {
274 int chromosomeSize = chromosome.size();
275 int pA;
276 int pB;
277 int pC;
278 int pD;
279
280 //Zawsze odwracamy punkty pomiędzy B a C.
281
282 if (edge1 == chromosomeSize) { //bxxxxxxxxa-
283 pA = edge1 - 1; //geny licza sie od 0
284 pB = 0;
285 } else { //xxxxxa-bxxx
286 pA = edge1 - 1; //geny licza sie od 0
287 pB = edge1;
288 }
289
290 if (edge2 == chromosomeSize) { //dxxxxxxxxc-
291 pC = edge2 - 1; //geny licza sie od 0
292 pD = 0;
293 } else { //xxxxxc-dxxx
294 pC = edge2 - 1; //geny licza sie od 0
295 pD = edge2;
296 }
297
298
299 //Liczba genów podlegających inwersji.
300 int inversionGenes = (pB < pC) ? pC - pB + 1
301 : (chromosomeSize - pB) + pC + 1;
302
303 //tmpGenes - sekcja inwersji po operacji inwersji.
304 Object[] invGenes = new Object[inversionGenes];
305 int ii;
306 if (pB < pC) {
307 ii = pC;
308 for (int i = 0; i < invGenes.length; i++) {
309 invGenes[i] = chromosome.getGene(ii);
310 ii--;
311 }
312 } else {
313 ii = 0;
314 for (int i = pC; i >= 0; i--) {
315 invGenes[ii++] = chromosome.getGene(i);
316 }
317
318 for (int i = chromosomeSize - 1; i >= pB; i--) {
319 invGenes[ii++] = chromosome.getGene(i);
320 }
321 }
322
323 int inv = 0;
324 if (edge1 < edge2) {
325 for (int i = edge1; i < edge2; i++) {
326 chromosome.setGene(i, invGenes[inv]);
327 inv++;
328 }
329 } else {
330 for (int i = edge1; i < chromosomeSize; i++) {
331 chromosome.setGene(i, invGenes[inv]);
332 inv++;
333 }
334 for (int i = 0; i < edge2; i++) {
335 chromosome.setGene(i, invGenes[inv]);
336 inv++;
337 }
338 }
339 chromosome.changed();
340 }
341
342 /**
343 * Funkcja wylicza kumulatywny współczynnik przyrostu jakości;
344 * Pożądanym jest aby cykl po usunięciu wybraych krawędzi (edge1, edge2)
345 * oraz utworzeniu nowych "na krzyż" był badziej optymalny;
346 * Przykład:
347 * dxxa-bxxc-, edge1=ab=4, edge2=cd=8
348 * Jeśli długości odcinków ac+bd jest mniejsza niż ab+cd to
349 * znaleziono cykl lepszy.
350 * @param chromosome Chromosom.
351 * @param edge1 Pierwsza krawędź, wartość z zakresu <1, chromosomeSize>
352 * np. edge1=4 dla xxxx-xxxx.
353 * @param edge2 Druga krawędź, wartość z zakresu <1, chromosomeSize>
354 * np. edge2=8 dla xxxxxx-xx.
355 * @return Różnca długości drogi przed i po zmianie. Wartość dodatnia
356 * oznacza wzrost wartości rozwiązania (dystans o jaki udało sie
357 * skrócić drogę), wartość ujemna oznacza pogorszenie wartości
358 * rozwiązania (dystatns o jaki wydłużyła się doroga po dokonaniu zmiany).
359 */
360 protected final double kwpj(Chromosome chromosome,
361 final int edge1,
362 final int edge2) {
363
364 int chromosomeSize = chromosome.size();
365 double sizeAB;
366 double sizeCD;
367 double sizeAC;
368 double sizeDB;
369 Point pA, pB, pC, pD;
370
371 if (edge1 == chromosomeSize) { //bxxxxxxxxa-
372 pA = (Point) chromosome.getGene(edge1 - 1); //geny licza sie od 0
373 pB = (Point) chromosome.getGene(0);
374 } else { //xxxxxa-bxxx
375 pA = (Point) chromosome.getGene(edge1 - 1); //geny licza sie od 0
376 pB = (Point) chromosome.getGene(edge1);
377 }
378 sizeAB = distance(pA, pB);
379
380 if (edge2 == chromosomeSize) { //dxxxxxxxxc-
381 pC = (Point) chromosome.getGene(edge2 - 1); //geny licza sie od 0
382 pD = (Point) chromosome.getGene(0);
383 } else { //xxxxxc-dxxx
384 pC = (Point) chromosome.getGene(edge2 - 1); //geny licza sie od 0
385 pD = (Point) chromosome.getGene(edge2);
386 }
387 sizeCD = distance(pC, pD);
388
389 sizeAC = distance(pA, pC);
390 sizeDB = distance(pD, pB);
391
392 //if ab+cd > ac+bd ZANLEZIONO lepszy cykl
393 return (sizeAB + sizeCD) - (sizeAC + sizeDB);
394 }
395
396 /**
397 * Odległość pomiędzy dwoma punktami w układzie współrzędnych
398 * (wzór na odległość Euklidesową pomiędzy dwoma punktami).
399 * @param p1 Punkt 1.
400 * @param p2 Punkt 2.
401 * @return Odległość.
402 */
403 private double distance(final Point p1, final Point p2) {
404 int xdiff = p1.getx() - p2.getx();
405 int ydiff = p1.gety() - p2.gety();
406 return Math.sqrt(xdiff * xdiff + ydiff * ydiff);
407 }
408 }
409