::Algorytm genetyczny::

     Algorytm genetyczny to rodzaj algorytmu przeszukujšcego przestrzeń alternatywnych rozwišzań problemu w celu wyszukania rozwišzań najlepszych. Sposób działania algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji biologicznej, ponieważ ich twórca John Henry Holland właœnie z biologii czerpał inspiracje do swoich prac.

     Algorytm genetyczny operuje na populacji jednostek:

gdzie: n jest numerem generacji, natomiast R oznacza rozmiar populacji.

Klasyczne algorytmy genetyczne w żaden sposób nie wykorzystujš wiedzy o rozwišzywanym problemie. To, że znajdujš rozwišzanie wynika z faktu, że do każdej następnej generacji przedostajš się lepsze jednostki z generacji poprzedniej, a operatory genetyczne wymieniajš informacje zawarte w tych jednostkach tworzšc nowe, potencjalnie doskonalsze rozwišzania. Proces tworzenia nowej populacji przedstawiony jest na poniższym rysunku.

    ::Troszkę historii::

1957-62: Barricelli, Fraser, Martin, Cockerham – modelowanie procesów genetycznych

1960: Holland (Uniw. Michigan) – systemy adaptacyjne à Algorytmy Genetyczne

1967: Bagley – program gry w 6 pionków

1971: Hollstien;

1975: De Jong – optymalizacja funkcji

1985: Goldberg – optymalizacja pracy gazocišgu

    ::Polacy, a algorytmy genetyczne::     

Michalewicz (Uniw. Północnej Karoliny, Charlotte, USA)

„Algorytmy genetyczne + struktury danych = programy ewolucyjne”

Buller (ATR Kioto, Japonia) „Sztuczny mózg. To już nie fantazje”

M. J. Kasperski, „Sztuczna Inteligencja. Droga do myœlšcych maszyn”

    ::Przykłady i zastosowania::

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.

    ::Podstawowe pojęcia::

ˇ  Chromosom jest to cišg bitów. Każdy pojedynczy bit jest odpowiednikiem pojedynczego „genu”, np. Kobieta Mężczyzna.

ˇ  Operacja krzyżowania polega na losowym przecięciu dwóch chromosomów (cišgów bitów) w jednym punkcie i zamianie podzielonych częœci między chromosomami. Powstajš dwa nowe chromosomy. Ważne jest to ze „dzieci” całkowicie zastępujš „rodziców”.

11010010

    ↓↑    - krzyżowanie

00100101

      ↓↓   -Powstajš dwa nowe osobniki zastępujšce rodziców:

11010101

00100010

ˇ  Operacja mutacji polega na zamianie na przeciwny losowo wybranego bitu.

    ↓   - bit mutacji

10010111

10110111 – osobnik po zmutowaniu.

ˇ  Selekcja osobników do krzyżowania następuje na drodze losowania.

- Metoda koła ruletki, która przydziela prawdopodobieństwa wylosowania każdego osobnika bezpoœrednio na podstawie jednej funkcji oceny,

- Ranking liniowy - Selekcja tš metodš jest bardzo podobna do selekcji metodš koła ruletki. Modyfikacja polega jedynie na zmianie funkcji okreœlajšcej prawdopodobieństwo wyboru danego osobnika. Przed przystšpieniem do tej selekcji należy nadać każdemu z osobników pewnš wartoœć (przystosowanie) zależnš od jego położenia na liœcie posortowanej względem wartoœci funkcji oceny,

- Turniej - Metoda jest zupełnie różna od powyższych i polega na losowym wyborze z całej populacji kilku osobników (jest to tzw. grupa turniejowa), a póŸniej z tej grupy wybierany jest osobnik najlepiej przystosowany i on przepisywany jest do nowo tworzonej populacji. Losowanie grup turniejowych oraz wybieranie z nich najlepszego osobnika należy powtórzyć aż do utworzenia całej nowej populacji.

ˇ  Populacja ma stały rozmiar, a w kolejnych cyklach ewolucji wszystkie chromosomy podlegajš wymianie na nowe (dzieci całkowicie zastępujš rodziców).

ˇ  Rozwišzaniem problemu jest najlepiej przystosowany osobnik z ostatniej wygenerowanej populacji. Należy dodać, że musimy z góry okreœlić warunek zatrzymania ewolucji (np. uzyskanie osobnika o wystarczajšco dobrych parametrach albo po z góry okreœlonej maksymalnej liczbie iteracji).

    ::Przykład komiwojażera::

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.

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.