[b]Algorytm genetyczny:[/b]

Aby w ogóle rozmawiać o krzyżowaniu w algorytmach genetycznych, musimy najpierw wiedzieć czym właściwie jest sam algorytm genetyczny. Jak jest zbudowany, jak działa i – co ważniejsze – w jakim celu został stworzony. Algorytm genetyczny jest rodzajem algorytmu przeszukującego przestrzeń alternatywnych rozwiązań zadanego problemu w celu znalezienia rozwiązania optymalnego. Działanie takiego algorytmu przypomina ewolucję biologiczną. Problem definiuje środowisko, w którym istnieje pewna grupa osobników. Każdy z osobników ma przypisany pewien zbiór danych stanowiących jego genotyp będący podstawą do utworzenia tzw. fenotypu. Fenotyp to zbiór cech podlegających ocenie funkcji przystosowania modelującej środowisko. Inaczej mówiąc genotyp opisuje proponowane rozwiązanie problemu, a funkcja przystosowania ocenia, jak dobre jest to rozwiązanie. Genotyp składa się z chromosomów, gdzie zakodowany jest fenotyp i ewentualnie pewne informacje pomocnicze dla algorytmu genetycznego. Chromosom natomiast składa się z genów. Wspólnymi cechami algorytmów ewolucyjnych, odróżniającymi je od innych, tradycyjnych metod optymalizacji, są:

1.stosowanie operatorów genetycznych, które dostosowane są do postaci rozwiązań, 2.przetwarzanie populacji rozwiązań, prowadzące do równoległego przeszukiwania przestrzeni rozwiązań z różnych punktów, 3.do celu nakierowania procesu przeszukiwania wystarcza jakość aktualnych rozwiązań, 4.celowe wprowadzenie elementów losowych.

Kodowanie jest bardzo istotnym etapem projektowania algorytmu. Sposób zakodowania w chromosomie informacji o proponowanym rozwiązaniu wpływa na szybkość i jakość wyników. Przyczyną takiego zjawiska jest wpływ kodowania na sposób w jaki przeszukiwana jest przestrzeń rozwiązań. Złe kodowanie może spowodować, że nigdy nie zostanie przeszukany fragment przestrzeni, w którym znajdują się najlepsze rozwiązania. Najczęściej stosowane kodowania chromosomu:

•wektorem genów, z których każdy z nich może być jedno- lub wielo-bitową liczbą całkowitą, bądź też rzeczywistą. •za pomocą drzewiastych struktur danych

Funkcja oceny to miara jakości osobnika (rozwiązania) w populacji. Dla każdego osobnika jest ona obliczana na podstawie pewnego modelu rozwiązywanego problemu. Załóżmy dla przykładu, że chcemy zaprojektować obwód elektryczny o pewnej charakterystyce. Funkcja oceny będzie wyszukiwała rozwiązania najbardziej zbliżone do danej charakterystyki, zbudowane z najmniejszej liczby elementów. W procesie selekcji wybierane będą najlepsze osobniki. Staną się one “rodzicami” dla nowej populacji.

[b]Krzyżowanie:[/b]

Przed każdym etapem selekcji osobniki, które przetrwały w populacji (wybrane przez funkcję oceny) są poddawane “obróbce” za pomocą dwóch podstawowych operatorów genetycznych: krzyżowania i mutacji. My zajmiemy się tylko operatorem krzyżowania. Zadaniem operatora krzyżowania jest łączenie w różnych kombinacjach cech pochodzących z różnych osobników populacji. Krzyżowanie polega na połączeniu niektórych (wybierane losowo) genotypów w jeden. Operacja ta ma sprawić, że „potomek” dwóch osobników rodzicielskich ma zespół cech, który jest kombinacją cech „rodziców” (może się zdarzyć, że tych najlepszych). Sposób krzyżowania jest zależny od kodowania chromosomów i problemu. Jednak można wskazać kilka standardowych metod krzyżowania: •rozcięcie dwóch chromosomów i stworzenie nowego poprzez sklejenie lewej części jednego rodzica z prawą częścią drugiego rodzica

[01|1010] + [11|0111] = [010111]

•stosowanie operacji logicznych (kodowanie binarne), •obliczenie wartości średniej genów (kodowanie liczbami rzeczywistymi).

[b]Krzyżowanie mieszające:[/b]

Operatorów krzyżowania w algorytmach genetycznych jest bardzo dużo. Różnią się one skutecznością, czasochłonnością czy złożonością obliczeniową. Jednym z tych operatorów jest krzyżowanie mieszające (ang. Blend crossover). Krzyżowanie mieszające dzieli się na dwa algorytmy, BLX– α oraz BLX–α–β .

Algorytm BLX-α : (α – dodatni parametr)

Z danej populacji wybieramy parę rodziców np.

X = |2,1,1,1,1,1| Y = |0,0,0,0,0,2|.

Zadaniem jest utworzenie pary potomków. Kolejno odnajdujemy geny potomstwa X’ i Y’ w następujący sposób: (Parametr α w naszym przykładzie wynosi 1)

di =|Xi – Yi|

w ten sposób otrzymujemy d1 = |2| . Następnie z równomiernym prawdopodobieństwem losujemy liczbę rzeczywistą u gdzie:

u ≡ (min(Xi, Yi) - αdi, max(Xi,Yi) + αdi)

tak więc:

u ≡ (min(2,0) - 2 , max(2,0) + 2 )

Powstaje nam u ≡ |-2,4|, X’i = wylosowane u. Czyli mamy np. X,i = -2 .

Całą operację powtarzamy w celu znalezienia Y’i: Z równomiernym prawdopodobieństwem losujemy liczbę rzeczywistą u.

u ≡ (min(2,0) – 2 , max(2,0) + 2 )

u ≡ |2,4|

np. Y’i = 4 Po otrzymaniu X'1 oraz Y'1, Które w naszym przypadku wynoszą -2 i 4, powtarzamy całość od znalezienia di w celu znalezienia pozostałych genów potomstwa. Po zakończeniu algorytmu dla naszego przykładu otrzymałem następujące, przykładowe potomstwo:

X’ = |-2, 2,-1,-1, 2, 0| Y’ = | 4,-1, 2,-1,-1, 1|

Wektor d wynosi d = |2, 1, 1, 1, 1,-1|

Algorytm BLX-α-β (α β – dodatnie parametry)

Algorytm BLX-α-β różni się od BLX-α tylko jednym warunkiem i wzorem na znalezienie u.

Weźmy naszą parę rodziców: X = |2,1,1,1,1,1| Y = |0,0,0,0,0,2|.

Zakładając, że X jest lepszy od Y należy odnaleźć parę potomków X’ i Y’ w następujący sposób:

(Parametry α i β w naszym przykładzie wynoszą 1)

Odnajdujemy di: di = |X – Y|

di = |2|

Jeżeli Xi jest mniejszy, bądź równy Yi losujemy Z równomiernym prawdopodobieństwem liczbę rzeczywistą u gdzie:

u ≡ (Xi - αdi, Yi + βdi)

X’i=u

Z równomiernym prawdopodobieństwem liczbę rzeczywistą u

Y’i=u

Jeżeli warunek Xi ≤ Yi nie jest spełniony, wtedy liczbę u szukamy według wzoru:

u ≡ (Xi - βdi, Yi + αdi)

W naszym przykładzie parametry α i β są równe, więc powyższy warunek traci znaczenie. Inaczej byłoby, gdyby parametry różniły się od siebie. Wtedy należy sprawdzać czy Xi jest większe, bądź równe od Yi i zastosować odpowiedni wzór na odnalezienie zbioru u.

u ≡ (2 – 2 , 0 + 2)

u ≡ (0 , 2)

Po wylosowaniu liczb ze zbioru u otrzymaliśmy następujące geny potomstwa:

X'1 = 0 Y'1 = 0

Całość powtarzamy tyle razy, ile jest genów w rodzicu, ponieważ potomstwo musi mieć tyle samo genów co rodzice.

Po zakończeniu algorytmu dla naszego przykładu otrzymałem następujące, przykładowe potomstwo:

X’ = | 0, 1, 0, 0, 0, 1| Y’ = | 0, 0, 0, 1, 1, 2|

Wektor d wynosi d = |2, 1, 1, 1, 1,-1| Zastosowania algorytmów genetycznych: Algorytmy genetyczne znajdują zastosowanie tam, gdzie nie jest dobrze określony lub poznany sposób rozwiązania problemu, ale znany jest sposób oceny jakości rozwiązania. Przykładem jest np. Problem Komiwojażera gdzie należy znaleźć najkrótszą drogę łączącą wszystkie miasta, tak by przez każde miasto przejść tylko raz. Przy zastosowaniu podejścia ewolucyjnego dobre rozwiązanie można znaleźć bardzo szybko, ale oczywiście pewni możemy być jedynie uzyskania wielu rozwiązań optymalnych, co wynika z formalnie opisanej trudności problemu. Algorytmy genetyczne równie dobrze radzą sobie w znajdowaniu przybliżeń ekstremów funkcji, których nie da się obliczyć w sposób analityczny. Algorytmy genetyczne wykorzystywane są również do zarządzania populacją sieci neuronowych. Projektowanie maszyn bądź obwodów elektrycznych są doskonałe dla wykazania się tych algorytmów. Inżynierowi podczas tworzenia nowych pomysłów nie chodzi o znalezienie najlepszego możliwego rozwiązania a tylko o przybliżone spełnienie warunków oraz optymalizację projektu. W odróżnieniu od człowieka algorytmy genetyczne nie działają schematycznie. Program nie zna wcześniejszych projektów, więc nie może opierać swojego „toku myślenia” na wcześniejszych przykładach. Co więcej człowiek często opiera się na bardzo przybliżonych modelach, które dają fałszywy obraz problemu. Algorytm genetyczny może przeanalizować złożony problem i znaleźć rozwiązanie, na które człowiek by nie wpadł. Algorytmy genetyczne można także wykorzystać do projektowania obwodów elektrycznych. Ocena każdego osobnika opiera się na ilości elementów oraz własnościach elektrycznych, które łatwo jest obliczyć.

[b]Podsumowując:[/b] Algorytmy genetyczne oparte są na zjawisku ewolucji w naturze i stworzone zostały w celu odnajdywania optymalnego rozwiązania zadanego problemu. Podstawowymi operatorami tych algorytmów są mutacja i krzyżowanie. Krzyżowanie polega na wymieszaniu genów „rodziców” tworząc w ten sposób genotypy „potomstwa”, które są alternatywnymi rozwiązaniami problemu. Ocena optymalności otrzymanego rozwiązania należy do Funkcji oceny, która stwierdzając, że dane rozwiązanie jest najlepsze spośród otrzymanych zatrzymuje dalsze krzyżowanie. Operatorów krzyżowania w algorytmach genetycznych jest bardzo wiele od prostych, polegających na przecięciu i wymianie części genotypów „rodziców” po skomplikowane, wymagające szeregu operacji matematycznych przeprowadzanych na parach genów „rodziców” Krzyżowanie mieszające dzieli się na dwa algorytmy BLX-α i BLX-α- β Algorytmy genetyczne mają szereg zastosowań w wielu dziedzinach nauki i techniki.