com.delhezi.ga.mutation.heuristics

Class LinKernighan

java.lang.Object

com.delhezi.ga.mutation.heuristics.LinKernighan

All Implemented Interfaces:

IMutation

public class LinKernighan
extends Object
implements IMutation

Klasa LinKernighan: Algorytm Lina-Kernighana; LinKernighan (LK); Algorytm lokalnego przeszukiwania; Wersja zrandomizowana, ilość prób podjętych do znalezienia lepszego rozwiązania okrela wartość counter; Przydatny w rozwiązaniu symetrycznego problemu komiwojażera (symmetric travelling salesman problem: STSP) – w którym dla każdego miasta istnieje połączenie do wszystkich pozostałych miast, oraz odległości pomiędzy miastami w obydwu kierunkach są sobie równe; Dla pary miast (węzłów) istnieje tylko jeden łuk o określonej długości; Losowo wybieramy 2 krawędzie; Jeśli długość cyklu po wymianie jest mniejsza niż przed, krawędzie są zamieniane; W innym przypadku przeszukiwana jest dostępna pula rozwiązań (iterakcyjnie wybieramy kolejne krawędzie) w celu znalezienia pierwszego wystąpienia cyklu lepszego. http://www.akira.ruc.dk/~keld/research/LKH/ ZOBACZ TO Algorytm lokalnego poszukiwania ze zmienną liczbą wymienianych krawędzi zależną od poprawy całkowitej ściezki; Dedykowany dla TSP; Tworzony jest łańcuch kolejnych wymian, który kończy się, gdy nie można znaleźć kolejnej wymiany poprawiającej długość cyklu; W każdej iteracji następuje próba utworzenia kolejnego łańcucha o co najmniej 2 elementach, jeśli to się nie powiedzie algorytm kończy działanie.

Version:

1.0 2010-01-10

Author:

Wojciech Wolszczak

Constructor Summary

Constructors

Constructor and Description
LinKernighan()

Method Summary

Methods

Modifier and Type	Method and Description
void	mutation(Chromosome chromosome) Implementacja funkcji mutacji 2-opt.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LinKernighan

public LinKernighan()

Method Detail

mutation

public final void mutation(Chromosome chromosome)

Implementacja funkcji mutacji 2-opt.

Specified by:

mutation in interface IMutation

Parameters:

chromosome - Chromosom podlegający mutacji.

Since:

1.0