Podręcznik

Zgodnie z definicją podaną przez Goldberga (1995), algorytmy genetyczne stanowią klasę algorytmów poszukujących, które opierają swoje działanie na inspiracji mechanizmami znanymi z biologii: dziedzicznością oraz doborem naturalnym. Ich funkcjonowanie odzwierciedla sposób, w jaki ewolucja kształtuje populacje organizmów w naturze.

W ramach tego podejścia, algorytm operuje na całej populacji potencjalnych rozwiązań danego problemu – a nie tylko na pojedynczym rozwiązaniu, jak ma to miejsce w klasycznych metodach optymalizacji. Każdy osobnik w tej populacji stanowi konkretną propozycję rozwiązania. Osobniki funkcjonują w środowisku - które umożliwia ocenianie i porównywanie osobników, i jest zależne od funkcji celu. Każdy osobnik ma przyporządkowaną wartość liczbową, nazywaną stopniem przystosowania lub po prostu przystosowaniem.  Przystosowanie określa bezpośrednio jakość danego osobnika, i zazwyczaj jest ona wyliczana na na podstawie funkcji celu, odpowiadającej konkretnemu zadaniu optymalizacyjnemu.

W naturze przetrwanie i możliwość rozmnażania się zależy od tego, jak dobrze organizm radzi sobie w danym środowisku. Im lepiej jest przystosowany, tym większe ma szanse na przekazanie swoich genów potomstwu. AG próbują wykorzystać tę ideę do rozwiązywania problemów optymalizacyjnych. Szukają rozwiązań, które w danym kontekście mają największe "szanse przetrwania" – czyli są najlepsze w sensie przyjętej funkcji celu.

Zamiast operować tylko na jednym kandydacie rozwiązania (jak robi to wiele klasycznych metod), AG pracują na całej populacji. Każdy osobnik tej populacji to konkretne rozwiązanie problemu – lepsze lub gorsze. W każdej iteracji (czyli pokoleniu) populacja ewoluuje: osobniki są selekcjonowane, krzyżowane, poddawane mutacjom. Dzięki temu, z pokolenia na pokolenie, jakość populacji (czyli jakość rozwiązań) zwykle się poprawia.

Genotyp i fenotyp – czym się różnią?

W AG każdy osobnik opisuje potencjalne rozwiązanie zadania, ale żeby algorytm mógł nad tym pracować, musi jakoś je zapisać. Dlatego stosuje się dwa poziomy reprezentacji:

• Genotyp to zakodowana forma rozwiązania. Można o nim myśleć jak o "DNA" osobnika. Zwykle jest to wektor (lista) liczb, np.:

  g = [g1, g2, ..., gng]

  W zależności od problemu, te liczby mogą być bitami (0 lub 1), wartościami rzeczywistymi, permutacjami elementów itd. Algorytm operuje właśnie na genotypie – krzyżuje go, mutuje itd. Sama forma genotypu jest zrozumiała dla AG, natomiast może być nieczytelna dla rozwiązującego. Jest to punkt w przestrzeni kodów - a nie konkretny zestaw parametrów stanowiących rozwiązanie problemu.

• Fenotyp to rozkodowane (czyli przekształcone) rozwiązanie, które można bezpośrednio ocenić. To forma, którą rozumie funkcja celu – np. zestaw parametrów wejściowych do jakiegoś modelu lub układu. Fenotyp wynika z genotypu poprzez proces dekodowania (który może być prosty lub złożony, zależnie od zastosowania).

Przykład: jeśli mamy zadanie doboru parametrów regulatora PID, to:

• genotyp może zawierać binarne lub rzeczywiste zakodowanie wartości Kr, Ti, Td;
• fenotyp to konkretne wartości tych parametrów użyte do symulacji układu i obliczenia błędu regulacji.

Zatem genotyp to sposób przechowywania i operowania rozwiązaniami w AG, a fenotyp to to, co naprawdę reprezentują – ich realna "forma" z punktu widzenia zadania optymalizacyjnego.

Inne istotne pojęcia, które "odziedziczyliśmy" z nauk biologicznych: 

• Populacja – zbiór osobników w danym pokoleniu. Jest to główny obiekt przetwarzania w AG – algorytm nie działa na jednym rozwiązaniu, lecz na całej grupie.
• Osobnik – pojedynczy element populacji. Reprezentuje jedno konkretne rozwiązanie problemu.
• Chromosom – struktura danych opisująca genotyp osobnika. Można go traktować jako kompletną reprezentację rozwiązania w postaci zakodowanej.
• Gen – najmniejszy element składowy chromosomu. Odpowiada jednej zmiennej problemu lub jednej cechy rozwiązania.
• Genotyp – cały zbiór genów osobnika, zakodowany w chromosomie. To właśnie na nim operują krzyżowanie i mutacja.
• Allel – wartość konkretnego genu. Czyli: gen to miejsce w chromosomie, allel to to, co tam siedzi. Np. jeśli gen odpowiada za kolor, to allel to „czerwony”, „zielony” itp.
• Locus – pozycja genu w chromosomie. Umożliwia jednoznaczną identyfikację, gdzie dany gen się znajduje.

Wszystkie te pojęcia wspólnie tworzą podstawowy język, w którym opisujemy działanie algorytmów genetycznych. W praktyce – dobre zrozumienie tych terminów pomaga w projektowaniu skutecznych algorytmów.