Algorytmy genetyczne - podstawy
Ta sekcja przedstawia podstawową terminologię wymaganą do zrozumienia GA. W obu przedstawiono również ogólną strukturę GApseudo-code and graphical forms. Czytelnik powinien dobrze zrozumieć wszystkie pojęcia przedstawione w tej sekcji i pamiętać o nich również podczas czytania innych sekcji tego samouczka.
Podstawowa terminologia
Przed rozpoczęciem dyskusji na temat algorytmów genetycznych należy koniecznie zapoznać się z podstawową terminologią, która będzie używana w tym samouczku.
Population- Jest to podzbiór wszystkich możliwych (zakodowanych) rozwiązań danego problemu. Populacja dla AH jest analogiczna do populacji ludzi, z tym wyjątkiem, że zamiast ludzi mamy Rozwiązania Kandydatów reprezentujące ludzi.
Chromosomes - Chromosom jest jednym z takich rozwiązań danego problemu.
Gene - Gen to pozycja jednego elementu w chromosomie.
Allele - Jest to wartość, jaką gen przyjmuje określony chromosom.
Genotype- Genotyp to populacja w przestrzeni obliczeniowej. W przestrzeni obliczeniowej rozwiązania są przedstawiane w sposób, który można łatwo zrozumieć i manipulować za pomocą systemu komputerowego.
Phenotype - Fenotyp to populacja w rzeczywistej przestrzeni rozwiązań w świecie rzeczywistym, w której rozwiązania są reprezentowane w sposób, w jaki są reprezentowane w rzeczywistych sytuacjach.
Decoding and Encoding - W przypadku prostych problemów phenotype and genotypespacje są takie same. Jednak w większości przypadków fenotyp i przestrzeń genotypowa są różne. Dekodowanie to proces przekształcania rozwiązania z genotypu do przestrzeni fenotypowej, podczas gdy kodowanie jest procesem transformacji z fenotypu do przestrzeni genotypu. Dekodowanie powinno być szybkie, ponieważ jest wykonywane wielokrotnie w GA podczas obliczania wartości sprawności.
Rozważmy na przykład problem plecaka 0/1. Przestrzeń fenotypów składa się z rozwiązań, które zawierają tylko numery pozycji do pobrania.
Jednak w przestrzeni genotypu można go przedstawić jako ciąg binarny o długości n (gdzie n to liczba elementów). ZA0 at position x reprezentuje to xthPrzedmiot jest wybierany, a 1 oznacza odwrotność. Jest to przypadek, w którym przestrzenie genotypowe i fenotypowe są różne.
Fitness Function- Prosto zdefiniowana funkcja przystosowania to funkcja, która przyjmuje rozwiązanie jako dane wejściowe i tworzy odpowiedniość rozwiązania jako dane wyjściowe. W niektórych przypadkach funkcja przystosowania i funkcja celu mogą być takie same, podczas gdy w innych mogą być różne w zależności od problemu.
Genetic Operators- Zmieniają one skład genetyczny potomstwa. Należą do nich crossover, mutacja, selekcja itp.
Podstawowa struktura
Podstawowa struktura AH jest następująca -
Zaczynamy od populacji początkowej (która może być generowana losowo lub wysiewana przez inne heurystyki), wybieramy rodziców z tej populacji do krycia. Zastosuj operatory krzyżowania i mutacji na rodzicach, aby wygenerować nowe potomstwo. I wreszcie te źródła zastępują istniejące osobniki w populacji i proces się powtarza. W ten sposób algorytmy genetyczne faktycznie próbują do pewnego stopnia naśladować ewolucję człowieka.
Każdy z poniższych kroków został omówiony jako osobny rozdział w dalszej części tego samouczka.
Uogólniony pseudokod dla GA jest wyjaśniony w następującym programie -
GA()
initialize population
find fitness of population
while (termination criteria is reached) do
parent selection
crossover with probability pc
mutation with probability pm
decode and fitness calculation
survivor selection
find best
return best