Algorytmy genetyczne znalazły
zastosowanie do rozwiązywania problemów optymalizacji, rozpoznawania obrazów,
przewidywaniu ruchów na giełdzie, tworzenia grafiki oraz projektowania budynków
i maszyn.
W problemie komiwojażera, celem jest znalezienie najkrótszej odległości miedzy N różnymi miastami.
Analizując każda możliwość dla N miast będzie N! kombinacji. 30-sto miastowa mapa będzie nam dawała 2.56 x 1032 kombinacji. Zakładając ze obliczenia 1 miliona kombinacji trwa sekundę obliczenie wszystkich kombinacji trwało by ponad 8,000,000,000,000,000 lat. Dodając jeszcze jedno miasto zwiększyło by liczbę kombinacji 31 razy. Jest to niemożliwe rozwiązanie.
Algorytm genetyczny może być użyty do znalezienia rozwiązania w dużo krótszym czasie. Jednak prawdopodobnie nie będzie to najlepsze rozwiązanie, dobrze zaimplementowany algorytm potrafi znaleźć rozwiązanie bliskie idealnemu w mniej niż minutę. Istnieją dwa podstawowe kroki do rozwiązania problemu komiwojażera za pomocą Algorytmu Genetycznego. Po pierwsze stworzyć grupę wielu przypadkowych dróg co będzie zwane populacja. Te drogi są zapisane jako sekwencja liczb. Po drugie wybrać dwie z krótszych „rodziców” dróg z populacji skrzyżować je aby powstały „dzieci”, w nadziei ze stworzą lepsze rozwiązanie.
Ideą Algorytmów Genetycznych jest symulacja ewolucji natury. Dobre rozwiązania są brane do reprodukcji w nadziei ze stworzą jeszcze lepsze rozwiązania a te gorsze są usuwane.
Największym problemem w problemie komiwojażera jest zakodowanie rozwiązania. Kodowanie nie może po prostu być listą miast w kolejności odwiedzania. Jak pokazano poniżej, operacja krzyżowania nie będzie działać. Krzyżowanie następuje po 3 pozycji.
|
Rodzic 1 |
1 2 3 4 5 |
|
Rodzic 2 |
3 5 2 1 4 |
|
Dziecko 1 |
1 2 3 1 4 |
|
Dziecko 1 |
3 5 2 4 5 |
Jak widać w tabeli miasto 1 występuje dwa razy a miasto 5 ani razu w dziecku 1. Dlatego musi być użyte bardziej skomplikowane kodowanie. Np. tablica NxN gdzie w miejsca odpowiadające połączeniom miedzy miastami odpowiada jeden bit 0 lub 1.