4552034829

W ten sposob uzyskujemy dwa poprawnie skrzyżowane ze sobą osobniki. Porównując wynik pierwszej zaproponowanej wersji krzyżowania (niepoprawnej) z powyższym wynikiem można zauważyć czasem spore rozbieżności (część wspólna zaznaczona na zielono):

Krzyżowanie niepoprawne:	Krzyżowanie poprawne:
Ścieżka #1: A B A BE]c	Ścieżka#1: CD F 6E A
Ścieżka #2: D F jDEj	Ścieżka #2: B A C D E F

Jednak nasz algorytm krzyżowania gwarantuje poprawność uzyskanych chromosomów, jednocześnie jest dość prosty do zaimplementowania i szybki w działaniu.

Zaimplementowaliśmy też nieco bardziej złożoną wersję krzyżowania - z dwoma osiami krzyżowania. Wówczas zamianie podlegały jedynie miasta, które znalazły się pomiędzy wyznaczonymi dwoma osiami. Zazwyczaj wychodzi na to, że im proces jest prostszy, tym jest bardziej skuteczny. W tym przypadku jednak zastosowanie dwóch osi krzyżowania nieznacznie polepsza wyniki algorytmu (są to wartości rzędu kilku procent). Tak więc pozostaliśmy przy efektywniejszej implementacji - z dwoma osiami krzyżowania.

3.4 Mutacja

Ponieważ po wylosowaniu pierwszej generacji osobników algorytm genetyczny poprzez selekcję i krzyżowanie będzie starał się ulepszać rozwiązanie na bazie dostarczonych mu na początku osobników, może zdarzyć się sytuacja, w której algorytm „utknie" w lokalnym ekstremum funkcji, co zdecydowanie nie zapewnia nam otrzymania rozwiązania zbliżonego do optymalnego. Dlatego stosowana jest operacja mutacji, która ma na celu zmodyfikowanie chromosomu w sposób losowy. Wprowadzone „zakłócenie" pozwala na otrzymanie osobników różniących się od pozostałych, przez co algorytm będzie poszukiwał najlepszego rozwiązania w różnych obszarach funkcji.

Mutacja przeprowadzana na naszych osobnikach polega na losowej zamianie miejscami alleli w obrębie jednego chromosomu. W celu optymalizacji tego procesu zdecydowaliśmy się na zezwalanie jedynie na mutacje, które poprawiają jakość rozwiązania. Jeśli dokonana mutacja pogarsza jakość osobnika, wycofujemy zmiany, których dokonała.

W naszej aplikacji możemy ustalić procentowy poziom mutacji, które będą zachodzić podczas poszukiwań najlepszego rozwiązania. Jednak z racji tego, że uznajemy jedynie mutacje poprawiające rozwiązanie, efektywny procent mutacji zawsze będzie dużo niższy niż wejściowy parametr.

4. Specyfikacja zewnętrzna

Program VRP Solver składa się z jednego głównego okienka podzielonego na dwie sekcje.

Z lewej strony widnieje biały kwadrat, na którym graficznie przedstawiane jest położenie magazynu (czerwona kropka) i miast (czarne kropki). Panel ten pozwala dodawać nowe miasta (lewy przycisk myszy), usuwać istniejące miasta (prawy przycisk myszy; magazynu nie da się usunąć). Współrzędne poszczególnych kropek - miast można odczytać przy pomocy „balonika z podpowiedzią", ukazującym się ponad wskazanym miastem, jak również w dolnej belce statusu - tam wyświetlane są współrzędne punktu na mapie, w jakim znajduje się kursor.

Po uruchomieniu obliczeń na tym samym panelu rysowane będzie najlepsze dotychczasowe rozwiązanie problemu (Rys. 3).

Panel po prawej stronie umożliwia podglądanie, jak i ustawianie parametrów pracy programu.