Rozszerzenie algorytmu o zaawansowane operatory krzyżowania

W przeciwieństwie do reprezentacji binarnej wykorzystanie ciągów zmiennopozycyjnych jako reprezentacji chromosomów umożliwia zastosowanie bardziej elastycznych, zaawansowanych operatorów krzyżowania.

Krzyżowanie arytmetyczne

Ten dwuargumentowy operator definiuje się jako kombinację liniową dwóch osobników. Jeżeli krzyżowaniu mają podlegać wektory xi i X2 , to potomkowie są wyznaczani następująco: xj = ax1 + (1 – a)x2 oraz x2 = ax2 + (1 – a)xŁ. W operatorze używa się losowej wartości a e [0, 1], co zawsze gwarantuje, że uzyskane punkty należą do zbioru argumentów

funkcji celu.

Krzyżowanie heurystyczne wspierane krzyżowaniem dwupunktowym

Operator krzyżowania heurystycznego jest wyjątkowy z następujących powodów:

  • do określenia kierunku poszukiwań używa on wartości funkcji celu,
  • tworzy tylko jednego potomka,
  • może w ogóle nie utworzyć potomka.

Operator ten tworzy jednego potomka x3 z dwojga rodziców xi i x2 zgodnie z następującą regułą:

x3 = r(x2 – x1) + x2                                                                                      ( 2.2. )

gdzie r jest liczbą przypadkową leżącą między 0 a 1, zaś rodzic x2 jest nie gorszy od x1, to znaczy f(x2) > f(x1) dla zadania maksymalizacji i f(x2) < f(x1) dla zadania minimalizacji.

Ten operator może utworzyć potomka, który nie jest dopuszczalny, czyli nie jest elementem zbioru argumentów funkcji celu. W takim przypadku generuje się inną wartość losową r i tworzy innego potomka. Jeżeli po w próbach operator nie znajduje nowego punktu należącego do dziedziny, to poddaje się i nie tworzy nowego potomka. Parametr w nazywany jest wskaźnikiem cierpliwości krzyżowania heurystycznego.

W przypadku, gdy operatorowi krzyżowania heurystycznego nie uda się po w próbach utworzyć dopuszczalnego osobnika, algorytm genetyczny może zareagować dwojako: albo zrezygnować z tworzenia potomków na bazie wybranych genotypów, albo zmienić sposób krzyżowania, czyli przekazać wylosowanych rodziców do innego operatora krzyżowania. Zarzucenie próby skojarzenia osobników po każdej porażce krzyżowania heurystycznego może zaowocować nieskończenie długim czasem wykonania tej części algorytmu. Ponadto krzyżowanie heurystyczne wpływa na dokładność znalezionego rozwiązania; jego głównymi zadaniami są dokładne dostrajanie lokalne i poszukiwanie w obiecującym kierunku.

Ze względu na wyżej podane powody najrozsądniejsze wydaje się zastosowanie kooperacji krzyżowania heurystycznego z takim alternatywnym operatorem krzyżowania, który spełnia przeciwną rolę, czyli działa zdecydowanie na korzyść różnorodności genetycznej. Operatorem takim jest krzyżowanie dwupunktowe, którego sposób działania jest podobny do sposobu działania klasycznego krzyżowania prostego z tą różnicą, że zamiast jednego wybiera się dwa punkty cięcia i wymieniany jest materiał chromosomowy pomiędzy nimi.