Algorytmy genetyczne - krótki przewodnik

Algorytm genetyczny (GA) to technika optymalizacji oparta na wyszukiwaniu, oparta na zasadach Genetics and Natural Selection. Jest często używany do znajdowania optymalnych lub prawie optymalnych rozwiązań trudnych problemów, których rozwiązanie w innym przypadku zajęłoby całe życie. Jest często używany do rozwiązywania problemów optymalizacyjnych, w badaniach i uczeniu maszynowym.

Wprowadzenie do optymalizacji

Optymalizacja to proces making something better. W każdym procesie mamy zestaw danych wejściowych i zestaw wyjść, jak pokazano na poniższym rysunku.

Optymalizacja polega na znalezieniu wartości wejść w taki sposób, aby uzyskać „najlepsze” wartości wyjściowe. Definicja „najlepszego” różni się w zależności od problemu, ale w kategoriach matematycznych odnosi się do maksymalizacji lub minimalizacji jednej lub więcej funkcji celu poprzez zmianę parametrów wejściowych.

Zbiór wszystkich możliwych rozwiązań lub wartości, które dane wejściowe mogą zająć przestrzeń poszukiwań. W tej przestrzeni poszukiwań znajduje się punkt lub zbiór punktów, który daje optymalne rozwiązanie. Celem optymalizacji jest znalezienie tego punktu lub zbioru punktów w przestrzeni poszukiwań.

Co to są algorytmy genetyczne?

Natura zawsze była wielkim źródłem inspiracji dla całej ludzkości. Algorytmy genetyczne (GA) to algorytmy oparte na wyszukiwaniu, oparte na pojęciach doboru naturalnego i genetyki. GA są podzbiorem znacznie większej gałęzi obliczeń znanej jakoEvolutionary Computation.

GA zostały opracowane przez Johna Hollanda oraz jego studentów i współpracowników z University of Michigan, w szczególności Davida E. Goldberga, i od tego czasu były testowane z dużym powodzeniem w różnych problemach optymalizacyjnych.

W GA mamy pool or a population of possible solutionsdo zadanego problemu. Następnie roztwory te ulegają rekombinacji i mutacji (podobnie jak w genetyce naturalnej), rodząc nowe dzieci, a proces ten powtarza się przez różne pokolenia. Każdej osobie (lub proponowanemu rozwiązaniu) przypisywana jest wartość przystosowania (oparta na wartości funkcji celu), a sprawniejsze osobniki mają większą szansę na kojarzenie się i wydanie bardziej „sprawniejszych” osobników. Jest to zgodne z darwinowską teorią „przetrwania najsilniejszych”.

W ten sposób nieustannie „rozwijamy” lepsze jednostki lub rozwiązania przez pokolenia, aż osiągniemy kryterium zatrzymania.

Algorytmy genetyczne mają wystarczająco losowy charakter, ale działają znacznie lepiej niż losowe wyszukiwanie lokalne (w którym po prostu próbujemy różnych losowych rozwiązań, śledząc najlepsze do tej pory), ponieważ wykorzystują również informacje historyczne.

Zalety GA

GA mają różne zalety, dzięki którym są niezwykle popularne. Należą do nich -

Nie wymaga żadnych informacji pochodnych (które mogą nie być dostępne w przypadku wielu rzeczywistych problemów).
Jest szybszy i wydajniejszy w porównaniu do metod tradycyjnych.
Posiada bardzo dobre możliwości równoległe.
Optymalizuje funkcje ciągłe i dyskretne, a także problemy z wieloma celami.
Zawiera listę „dobrych” rozwiązań, a nie tylko pojedyncze rozwiązanie.
Zawsze otrzymuje odpowiedź na problem, która z czasem staje się coraz lepsza.
Przydatne, gdy przestrzeń wyszukiwania jest bardzo duża i występuje duża liczba parametrów.

Ograniczenia GA

Jak każda technika, GA również cierpią z powodu kilku ograniczeń. Należą do nich -

GA nie są dostosowane do wszystkich problemów, zwłaszcza problemów, które są proste i dla których dostępne są informacje pochodne.
Wartość sprawności jest obliczana wielokrotnie, co może być kosztowne obliczeniowo w przypadku niektórych problemów.
Będąc stochastycznym, nie ma gwarancji co do optymalności ani jakości rozwiązania.
Jeśli nie zostanie prawidłowo wdrożony, GA może nie osiągnąć optymalnego rozwiązania.

GA - Motywacja

Algorytmy genetyczne są w stanie dostarczyć „wystarczająco dobre” rozwiązanie „wystarczająco szybko”. To sprawia, że algorytmy genetyczne są atrakcyjne do wykorzystania w rozwiązywaniu problemów optymalizacyjnych. Powody, dla których potrzebne są GA, są następujące -

Rozwiązywanie trudnych problemów

W informatyce istnieje wiele problemów, którymi są NP-Hard. W istocie oznacza to, że rozwiązanie tego problemu nawet w przypadku najpotężniejszych systemów komputerowych zajmuje bardzo dużo czasu (nawet lata!). W takim scenariuszu GA okazują się skutecznym narzędziem dostarczaniausable near-optimal solutions w krótkim czasie.

Niepowodzenie metod opartych na gradientach

Tradycyjne metody oparte na rachunku różniczkowym działają na zasadzie startu w losowym punkcie i poruszania się zgodnie z kierunkiem nachylenia, aż osiągniemy szczyt wzgórza. Ta technika jest wydajna i działa bardzo dobrze w przypadku funkcji celu z pojedynczym szczytem, takich jak funkcja kosztu w regresji liniowej. Ale w większości rzeczywistych sytuacji mamy bardzo złożony problem zwany krajobrazami, które składają się z wielu szczytów i wielu dolin, co powoduje, że takie metody zawodzą, ponieważ cierpią z powodu nieodłącznej tendencji do utknięcia w lokalnych optymach. jak pokazano na poniższym rysunku.

Szybkie uzyskanie dobrego rozwiązania

Niektóre trudne problemy, takie jak problem z podróżującym sprzedawcą (TSP), mają zastosowania w świecie rzeczywistym, takie jak wyszukiwanie ścieżek i projektowanie VLSI. Teraz wyobraź sobie, że korzystasz z systemu nawigacji GPS i obliczenie „optymalnej” ścieżki od źródła do celu zajmuje kilka minut (lub nawet kilka godzin). Opóźnienia w takich rzeczywistych zastosowaniach są nie do przyjęcia i dlatego wymagane jest „wystarczająco dobre” rozwiązanie, które jest dostarczane „szybko”.

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 x^thPrzedmiot 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

Jedną z najważniejszych decyzji, jakie należy podjąć podczas wdrażania algorytmu genetycznego, jest określenie reprezentacji, której będziemy używać do reprezentowania naszych rozwiązań. Zaobserwowano, że niewłaściwa reprezentacja może prowadzić do słabego działania AH.

Dlatego wybór właściwej reprezentacji, posiadanie właściwej definicji mapowań między fenotypem a przestrzeniami genotypów jest niezbędne dla sukcesu GA.

W tej sekcji przedstawiamy niektóre z najczęściej używanych reprezentacji algorytmów genetycznych. Jednak reprezentacja jest wysoce specyficzna dla problemu i czytelnik może uznać, że inna reprezentacja lub mieszanka przedstawień wymienionych tutaj może lepiej odpowiadać jego problemowi.

Reprezentacja binarna

Jest to jedna z najprostszych i najczęściej używanych reprezentacji w GA. W tego rodzaju reprezentacji genotyp składa się z ciągów bitów.

W przypadku niektórych problemów, gdy przestrzeń rozwiązań składa się z boolowskich zmiennych decyzyjnych - tak lub nie, reprezentacja binarna jest naturalna. Weźmy na przykład problem plecaka 0/1. Jeśli istnieje n elementów, możemy przedstawić rozwiązanie za pomocą łańcucha binarnego n elementów, gdzie x- ^ty element mówi, czy element x został wybrany (1), czy nie (0).

W przypadku innych problemów, szczególnie tych dotyczących liczb, możemy przedstawić liczby w ich binarnej reprezentacji. Problem z tym rodzajem kodowania polega na tym, że różne bity mają różne znaczenie, a zatem operatory mutacji i krzyżowania mogą mieć niepożądane konsekwencje. Do pewnego stopnia można to rozwiązać za pomocąGray Coding, ponieważ zmiana jednego bitu nie ma dużego wpływu na rozwiązanie.

Prawdziwie wyceniona reprezentacja

W przypadku problemów, w których chcemy zdefiniować geny za pomocą zmiennych ciągłych, a nie dyskretnych, reprezentacja o wartościach rzeczywistych jest najbardziej naturalna. Dokładność tych liczb rzeczywistych lub zmiennoprzecinkowych jest jednak ograniczona do komputera.

Reprezentacja liczby całkowitej

W przypadku genów o wartości dyskretnej nie zawsze możemy ograniczyć przestrzeń rozwiązań do binarnego „tak” lub „nie”. Na przykład, jeśli chcemy zakodować cztery odległości - północ, południe, wschód i zachód, możemy zakodować je jako{0,1,2,3}. W takich przypadkach reprezentacja liczb całkowitych jest pożądana.

Reprezentacja permutacji

W wielu problemach rozwiązanie jest reprezentowane przez kolejność elementów. W takich przypadkach najbardziej odpowiednia jest reprezentacja permutacyjna.

Klasycznym przykładem tego przedstawienia jest problem komiwojażera (TSP). W tym przypadku sprzedawca musi zwiedzić wszystkie miasta, odwiedzić każde z nich dokładnie raz i wrócić do miasta początkowego. Całkowity dystans wycieczki musi być zminimalizowany. Rozwiązaniem tego TSP jest oczywiście uporządkowanie lub permutacja wszystkich miast, dlatego użycie reprezentacji permutacji ma sens w przypadku tego problemu.

Ludność to podzbiór rozwiązań obecnej generacji. Można go również zdefiniować jako zestaw chromosomów. Jest kilka rzeczy, o których należy pamiętać, mając do czynienia z populacją AH -

Należy zachować różnorodność populacji, w przeciwnym razie może to doprowadzić do przedwczesnej konwergencji.
Wielkość populacji nie powinna być bardzo duża, ponieważ może to spowodować spowolnienie AH, podczas gdy mniejsza populacja może nie wystarczyć dla dobrej puli godowej. Dlatego optymalna wielkość populacji musi zostać ustalona metodą prób i błędów.

Populacja jest zwykle definiowana jako dwuwymiarowa tablica - size population, size x, chromosome size.

Inicjalizacja populacji

Istnieją dwie podstawowe metody inicjowania populacji w GA. Oni są -

Random Initialization - Zapełnij początkową populację całkowicie losowymi rozwiązaniami.
Heuristic initialization - Zapełnij początkową populację przy użyciu znanej heurystyki problemu.

Zaobserwowano, że cała populacja nie powinna być inicjalizowana przy użyciu heurystyki, ponieważ może to spowodować, że populacja będzie miała podobne rozwiązania i bardzo małą różnorodność. Zaobserwowano eksperymentalnie, że losowe rozwiązania są tymi, które prowadzą populację do optymalności. Dlatego przy inicjalizacji heurystycznej po prostu zasiewamy populację kilkoma dobrymi rozwiązaniami, wypełniając resztę rozwiązaniami losowymi, zamiast wypełniać całą populację rozwiązaniami opartymi na heurystyce.

Zaobserwowano również, że inicjalizacja heurystyczna w niektórych przypadkach wpływa tylko na początkową sprawność populacji, ale ostatecznie to różnorodność rozwiązań prowadzi do optymalności.

Modele populacji

Istnieją dwa szeroko stosowane modele populacji -

Stan stabilny

W stanie ustalonym GA generujemy jedno lub dwa potomstwo w każdej iteracji i zastępują one jedną lub dwie osobniki z populacji. Stan ustalony GA jest również znany jakoIncremental GA.

Pokoleniowe

W modelu pokoleniowym generujemy 'n' potomków, gdzie n jest wielkością populacji, a cała populacja jest zastępowana nową na końcu iteracji.

Po prostu zdefiniowana funkcja przystosowania to funkcja, która przyjmuje wartość candidate solution to the problem as input and produces as output jak „pasuje” do nas, jak „dobre” jest rozwiązanie w odniesieniu do rozważanego problemu.

Obliczanie wartości sprawności jest wykonywane wielokrotnie w GA i dlatego powinno być wystarczająco szybkie. Powolne obliczanie wartości przystosowania może niekorzystnie wpłynąć na AH i sprawić, że będzie wyjątkowo wolne.

W większości przypadków funkcja przystosowania i funkcja celu są takie same, jak celem jest maksymalizacja lub minimalizacja danej funkcji celu. Jednak w przypadku bardziej złożonych problemów z wieloma celami i ograniczeniami plikAlgorithm Designer może wybrać inną funkcję sprawności.

Funkcja sprawności powinna mieć następujące cechy:

Funkcja przydatności powinna być wystarczająco szybka do obliczenia.
Musi ilościowo mierzyć, jak odpowiednie jest dane rozwiązanie lub jak sprawne osoby mogą być wyprodukowane z danego rozwiązania.

W niektórych przypadkach bezpośrednie obliczenie funkcji przystosowania może nie być możliwe ze względu na nieodłączną złożoność problemu. W takich przypadkach przybliżamy sprawność fizyczną zgodnie z naszymi potrzebami.

Poniższy rysunek przedstawia obliczenia sprawności dla rozwiązania plecaka 0/1. Jest to prosta funkcja kondycji, która po prostu sumuje wartości zysków pobieranych przedmiotów (które mają 1), skanując elementy od lewej do prawej, aż plecak się zapełni.

Wybór rodziców to proces selekcji rodziców, którzy łączą się w pary i ponownie łączą, aby stworzyć potomstwo dla następnego pokolenia. Wybór rodziców jest bardzo istotny dla stopnia konwergencji AH, ponieważ dobrzy rodzice kierują poszczególne osoby do lepszych i bardziej dopasowanych rozwiązań.

Należy jednak uważać, aby nie dopuścić do tego, aby jedno wyjątkowo odpowiednie rozwiązanie przejęło całą populację w ciągu kilku pokoleń, ponieważ prowadzi to do bliskości rozwiązań w przestrzeni rozwiązań, co prowadzi do utraty różnorodności. Maintaining good diversityw populacji jest niezwykle istotne dla sukcesu AH. To pochłanianie całej populacji jednym niezwykle odpowiednim rozwiązaniem jest znane jakopremature convergence i jest stanem niepożądanym w AH.

Wybór proporcjonalny do sprawności

Selekcja proporcjonalna do sprawności to jeden z najpopularniejszych sposobów selekcji rodziców. W tym przypadku każdy może zostać rodzicem z prawdopodobieństwem proporcjonalnym do jego sprawności. Dlatego bardziej sprawne osobniki mają większe szanse na krycie i rozmnażanie swoich cech na następne pokolenie. Dlatego taka strategia selekcji nakłada presję selekcyjną na bardziej sprawne osobniki w populacji, z czasem ewoluując lepiej.

Rozważmy okrągłe koło. Koło jest podzielone nan pies, gdzie n to liczba osobników w populacji. Każda osoba otrzymuje część koła, która jest proporcjonalna do jej wartości sprawności.

Możliwe są dwie implementacje selekcji proporcjonalnej do dopasowania -

Wybór koła ruletki

W wyborze koła ruletki koło jest podzielone tak, jak opisano wcześniej. Na obwodzie koła wybiera się stały punkt, jak pokazano, i koło jest obracane. Region koła, który znajduje się przed punktem stałym, jest wybierany jako rodzic. W przypadku drugiego rodzica ten sam proces się powtarza.

Oczywiste jest, że osoba montująca ma większy placek na kole, a tym samym większą szansę na wylądowanie przed punktem stałym, gdy koło jest obracane. Dlatego prawdopodobieństwo wyboru osoby zależy bezpośrednio od jej sprawności.

Mądrze wdrażamy, wykonujemy następujące kroki -

Oblicz S = suma finezji.
Wygeneruj liczbę losową z zakresu od 0 do S.
Zaczynając od góry populacji, dodawaj finezji do częściowej sumy P, aż P <S.
Osoba, dla której P przewyższa S, jest wybraną osobą.

Stochastic Universal Sampling (SUS)

Stochastic Universal Sampling jest dość podobny do wyboru koła ruletki, jednak zamiast mieć tylko jeden stały punkt, mamy wiele stałych punktów, jak pokazano na poniższym obrazku. Dlatego wszyscy rodzice są wybierani za jednym zamachem. Taka konfiguracja zachęca również wysoce sprawne osoby do wybrania przynajmniej raz.

Należy zauważyć, że metody selekcji proporcjonalnej do sprawności nie sprawdzają się w przypadkach, w których dopasowanie może mieć wartość ujemną.

Wybór turnieju

W selekcji turniejów K-Way wybieramy losowo K osób z populacji i wybieramy najlepsze z nich, aby zostać rodzicami. Ten sam proces jest powtarzany w celu wyboru następnego rodzica. Selekcja turniejowa jest również niezwykle popularna w literaturze, ponieważ może działać nawet z ujemnymi wartościami sprawności.

Wybór rangi

Wybór rang działa również z ujemnymi wartościami sprawności i jest stosowany głównie, gdy osobniki w populacji mają bardzo zbliżone wartości sprawności (dzieje się to zwykle pod koniec biegu). Prowadzi to do tego, że każda osoba ma prawie równy udział w tortu (jak w przypadku doboru proporcjonalnego przystosowania), jak pokazano na poniższym obrazku, a zatem każda osoba, bez względu na to, jak pasuje do siebie, ma w przybliżeniu takie samo prawdopodobieństwo, że zostanie wybrana jako rodzic. To z kolei prowadzi do utraty presji selekcyjnej na osoby bardziej sprawne, co sprawia, że AH w takich sytuacjach źle wybiera rodziców.

W tym przypadku usuwamy pojęcie wartości sprawności podczas wyboru rodzica. Jednak każda osoba w populacji jest uszeregowana według jej sprawności. Wybór rodziców zależy od rangi każdej osoby, a nie od sprawności. Osoby o wyższej randze są preferowane bardziej niż osoby o niższej randze.

Chromosom	Wartość sprawności	Ranga
ZA	8.1	1
b	8.0	4
do	8.05	2
re	7.95	6
mi	8.02	3
fa	7,99	5

Losowy wybór

W tej strategii losowo wybieramy rodziców z istniejącej populacji. Nie ma presji selekcyjnej na osoby sprawne fizycznie, dlatego zazwyczaj unika się tej strategii.

W tym rozdziale omówimy, czym jest Crossover Operator wraz z innymi jego modułami, ich zastosowaniami i zaletami.

Wprowadzenie do Crossover

Operator krzyżowania jest analogiczny do reprodukcji i biologicznego krzyżowania. W tym przypadku wybiera się więcej niż jednego rodzica i jedno lub więcej potomków jest produkowanych przy użyciu materiału genetycznego rodziców. Crossover jest zwykle stosowany w GA z dużym prawdopodobieństwem -p_c .

Operatory zwrotnicy

W tej sekcji omówimy niektóre z najpopularniejszych operatorów crossoverów. Należy zauważyć, że te operatory krzyżowania są bardzo ogólne i Projektant GA może również zdecydować się na zaimplementowanie operatora skrzyżowania specyficznego dla problemu.

One Point Crossover

W tym jednopunktowym skrzyżowaniu wybierany jest losowy punkt krzyżowania, a ogony jego dwóch rodziców są zamieniane, aby uzyskać nowe potomstwo.

Crossover wielopunktowy

Wielopunktowa zwrotnica jest uogólnieniem jednopunktowej zwrotnicy, w której naprzemienne segmenty są zamieniane w celu uzyskania nowych sprężyn.

Jednolity crossover

W jednolitej krzyżówce nie dzielimy chromosomu na segmenty, a raczej traktujemy każdy gen oddzielnie. W tym przypadku zasadniczo rzucamy monetą dla każdego chromosomu, aby zdecydować, czy zostanie on włączony wiosną, czy nie. Możemy również skierować monetę do jednego z rodziców, aby mieć więcej materiału genetycznego w dziecku od tego rodzica.

Pełna rekombinacja arytmetyczna

Jest to często używane do reprezentacji liczb całkowitych i działa na podstawie średniej ważonej dwóch rodziców przy użyciu następujących wzorów:

Dziecko1 = α.x + (1-α). Y
Dziecko2 = α.x + (1-α). Y

Oczywiście, jeśli α = 0,5, to oba dzieci będą identyczne, jak pokazano na poniższym obrazku.

Zamówienie Crossover Davisa (OX1)

OX1 jest używany do crossoverów opartych na permutacji z zamiarem przekazywania informacji o względnym zamówieniu do odrostów. Działa w następujący sposób -

Utwórz dwa losowe punkty krzyżowania w rodzicu i skopiuj segment między nimi od pierwszego rodzica do pierwszego potomstwa.
Teraz, zaczynając od drugiego punktu przecięcia w drugim rodzicu, skopiuj pozostałe nieużywane liczby z drugiego rodzica do pierwszego dziecka, zawijając listę.
Powtórz dla drugiego dziecka z odwróconą rolą rodzica.

Istnieje wiele innych zwrotnic, takich jak częściowo mapowany crossover (PMX), zwrotnica oparta na zamówieniu (OX2), Shuffle Crossover, Ring Crossover itp.

Wprowadzenie do mutacji

Mówiąc prościej, mutację można zdefiniować jako małe, losowe modyfikacje chromosomu w celu uzyskania nowego rozwiązania. Służy do utrzymania i wprowadzania różnorodności w populacji genetycznej i jest zwykle stosowany z niskim prawdopodobieństwem -p_m. Jeśli prawdopodobieństwo jest bardzo wysokie, GA zostaje zredukowana do wyszukiwania losowego.

Mutacja jest częścią AH, która jest związana z „eksploracją” przestrzeni poszukiwań. Zaobserwowano, że mutacja jest niezbędna do konwergencji GA, podczas gdy crossover nie.

Operatory mutacji

W tej sekcji opisujemy niektóre z najczęściej używanych operatorów mutacji. Podobnie jak operatory krzyżowania, nie jest to wyczerpująca lista i projektant GA może uznać kombinację tych podejść lub operator mutacji specyficzny dla problemu za bardziej przydatny.

Bit Flip Mutation

W tej mutacji odwracania bitów wybieramy jeden lub więcej losowych bitów i odwracamy je. Jest to używane w przypadku GA zakodowanych binarnie.

Losowe resetowanie

Losowe resetowanie jest rozszerzeniem przerzucania bitów w reprezentacji liczb całkowitych. W tym przypadku losowa wartość ze zbioru wartości dopuszczalnych jest przypisywana losowo wybranemu genowi.

Zamień mutację

W przypadku mutacji typu zamiana losowo wybieramy dwie pozycje na chromosomie i zamieniamy wartościami. Jest to powszechne w kodowaniach opartych na permutacji.

Mutacja Scramble

Mutacja mieszana jest również popularna w przypadku reprezentacji permutacji. W tym przypadku z całego chromosomu wybierany jest podzbiór genów, a ich wartości są losowo zaszyfrowane lub przetasowane.

Mutacja inwersji

W mutacji inwersyjnej wybieramy podzbiór genów, jak w przypadku mutacji mieszanej, ale zamiast tasować podzbiór, po prostu odwracamy cały ciąg w podzbiorze.

Polityka selekcji ocalałych określa, które osoby mają zostać wyrzucone, a które zatrzymać w następnym pokoleniu. Jest to kluczowe, ponieważ powinno zapewnić, że bardziej sprawne osobniki nie zostaną wyrzucone z populacji, przy jednoczesnym zachowaniu różnorodności populacji.

Niektóre AH stosują Elitism. Mówiąc prosto, oznacza to, że obecnie najlepiej przystosowany członek populacji jest zawsze rozmnażany do następnego pokolenia. Dlatego pod żadnym pozorem nie można zastąpić najsilniejszego członka obecnej populacji.

Najłatwiejszą polityką jest wyrzucanie przypadkowych członków z populacji, ale takie podejście często wiąże się z problemami z konwergencją, dlatego szeroko stosuje się następujące strategie.

Wybór na podstawie wieku

W selekcji na podstawie wieku nie mamy pojęcia o sprawności. Opiera się na założeniu, że każdy osobnik może przebywać w populacji przez skończone pokolenie, w którym może się rozmnażać, a następnie jest wyrzucany z populacji, bez względu na to, jak dobrze jest przystosowany.

Na przykład w poniższym przykładzie wiek to liczba pokoleń, przez które dana osoba była w populacji. Najstarsi członkowie populacji, tj. P4 i P7, są wyrzucani z populacji, a wiek pozostałych członków zwiększa się o jeden.

Wybór oparty na sprawności

W tej selekcji opartej na sprawności, dzieci mają tendencję do zastępowania najmniej sprawnych osobników w populacji. Selekcja najmniej dopasowanych osób może odbywać się za pomocą różnych zasad selekcji opisanych wcześniej - selekcja turniejowa, selekcja proporcjonalna do sprawności itp.

Na przykład na poniższej ilustracji dzieci zastępują najmniej sprawne osobniki P1 i P10 populacji. Należy zauważyć, że ponieważ P1 i P9 mają tę samą wartość sprawności, decyzja o usunięciu tego osobnika z populacji jest arbitralna.

Warunek zakończenia algorytmu genetycznego jest ważny przy określaniu, kiedy zakończy się przebieg GA. Zaobserwowano, że początkowo GA postępuje bardzo szybko, a lepsze rozwiązania pojawiają się co kilka iteracji, ale ma to tendencję do nasycania się na późniejszych etapach, gdzie ulepszenia są bardzo małe. Zwykle zależy nam na takim warunku zakończenia, aby nasze rozwiązanie było zbliżone do optymalnego na końcu przebiegu.

Zwykle zachowujemy jeden z następujących warunków wypowiedzenia -

Kiedy nie nastąpiła poprawa populacji dla X iteracji.
Kiedy osiągniemy absolutną liczbę pokoleń.
Gdy wartość funkcji celu osiągnęła określoną z góry określoną wartość.

Na przykład w algorytmie genetycznym prowadzimy licznik, który śledzi pokolenia, dla których nie nastąpiła poprawa populacji. Początkowo ustawiamy ten licznik na zero. Za każdym razem, gdy nie generujemy potomstwa, które jest lepsze niż osobniki w populacji, zwiększamy licznik.

Jeśli jednak sprawność któregoś ze sprężyn jest lepsza, wówczas resetujemy licznik do zera. Algorytm kończy się, gdy licznik osiągnie z góry określoną wartość.

Podobnie jak inne parametry GA, warunek zakończenia jest również wysoce specyficzny dla problemu i projektant GA powinien wypróbować różne opcje, aby zobaczyć, co najlepiej pasuje do jego konkretnego problemu.

Do tej pory w tym samouczku wszystko, co omawialiśmy, odpowiada darwinowskiemu modelowi ewolucji - dobór naturalny i zmienność genetyczna poprzez rekombinację i mutację. W naturze tylko informacje zawarte w genotypie jednostki mogą być przekazywane następnemu pokoleniu. To jest podejście, które stosowaliśmy do tej pory w samouczku.

Jednak inne modele adaptacji dożywotniej - Lamarckian Model i Baldwinian Modelteż istnieją. Należy zauważyć, że którykolwiek model jest najlepszy, jest otwarty na dyskusję, a wyniki uzyskane przez naukowców pokazują, że wybór adaptacji w okresie życia jest wysoce specyficzny dla problemu.

Często hybrydyzujemy GA z wyszukiwaniem lokalnym - jak w algorytmach memetycznych. W takich przypadkach można zdecydować się na model Lamarcki lub Baldwinian, aby zdecydować, co zrobić z osobami wygenerowanymi po lokalnym wyszukiwaniu.

Model lamarcki

Model lamarcki zasadniczo mówi, że cechy, które jednostka nabywa za życia, mogą zostać przekazane jej potomstwu. Został nazwany na cześć francuskiego biologa Jean-Baptiste Lamarcka.

Mimo że biologia naturalna całkowicie zlekceważyła lamarckizm, ponieważ wszyscy wiemy, że można przekazywać tylko informacje zawarte w genotypie. Jednak z punktu widzenia obliczeń wykazano, że przyjęcie modelu lamarckowskiego daje dobre rezultaty w przypadku niektórych problemów.

W modelu lamarckowskim lokalny operator wyszukiwania bada otoczenie (uzyskując nowe cechy), a jeśli znajdzie lepszy chromosom, staje się potomkiem.

Model Baldwina

Model Baldwina to pośrednia idea nazwana na cześć Jamesa Marka Baldwina (1896). W modelu Baldwina chromosomy mogą kodować tendencję do uczenia się korzystnych zachowań. Oznacza to, że w przeciwieństwie do modelu lamarckiego nie przekazujemy nabytych cech następnemu pokoleniu, ani też nie ignorujemy całkowicie nabytych cech, jak w modelu darwinowskim.

Model Baldwina znajduje się pośrodku tych dwóch skrajności, w których zakodowana jest skłonność jednostki do nabywania pewnych cech, a nie same cechy.

W tym modelu Baldwina, lokalny operator wyszukiwania bada otoczenie (uzyskując nowe cechy), a jeśli zostanie znaleziony lepszy chromosom, przypisuje on tylko lepszą dopasowanie do chromosomu i nie modyfikuje samego chromosomu. Zmiana przystosowania oznacza zdolność chromosomów do „nabycia cechy”, nawet jeśli nie jest ona przekazywana bezpośrednio przyszłym pokoleniom.

Analizy GA mają bardzo ogólny charakter i samo zastosowanie ich do dowolnego problemu z optymalizacją nie dałoby dobrych wyników. W tej sekcji opisujemy kilka punktów, które pomogłyby i wspomogłyby projektanta GA lub implementującego GA w ich pracy.

Wprowadzenie wiedzy dziedzinowej specyficznej dla problemu

Zaobserwowano, że bardziej specyficzną dla problemu wiedzę dziedzinową włączamy do GA; otrzymujemy lepsze obiektywne wartości. Dodawanie informacji specyficznych dla problemu można wykonać za pomocą operatorów krzyżowania lub mutacji specyficznych dla problemu, niestandardowych reprezentacji itp.

Poniższe zdjęcie przedstawia pogląd Michalewicza (1990) na EA -

Zmniejsz tłumienie

Stłoczenie ma miejsce, gdy wysoce dopasowany chromosom często się rozmnaża, a za kilka pokoleń cała populacja jest wypełniona podobnymi rozwiązaniami o podobnej sprawności. Zmniejsza to różnorodność, która jest bardzo istotnym elementem zapewniającym sukces AH. Istnieje wiele sposobów na ograniczenie tłoku. Niektóre z nich to -

Mutation wprowadzić różnorodność.
Przełączać na rank selection i tournament selection które mają większą presję selekcyjną niż selekcja proporcjonalna do sprawności dla osób o podobnej sprawności.
Fitness Sharing - W tym przypadku sprawność osobista jest ograniczona, jeśli populacja zawiera już podobne osobniki.

Randomizacja pomaga!

Zaobserwowano eksperymentalnie, że najlepsze rozwiązania są napędzane przez losowe chromosomy, ponieważ zapewniają różnorodność populacji. Osoba wdrażająca GA powinna uważać, aby zachować wystarczającą liczbę randomizacji i różnorodności w populacji, aby uzyskać najlepsze wyniki.

Hybrydyzacja GA z wyszukiwaniem lokalnym

Wyszukiwanie lokalne polega na sprawdzaniu rozwiązań w sąsiedztwie danego rozwiązania w celu wyszukania lepszych wartości obiektywnych.

Czasami może być przydatne hybrydyzacja GA z wyszukiwaniem lokalnym. Poniższy obraz przedstawia różne miejsca, w których można wprowadzić wyszukiwanie lokalne w GA.

Zmienność parametrów i technik

W algorytmach genetycznych nie ma „jednego rozmiaru dla wszystkich” ani magicznej formuły, która działa na wszystkie problemy. Nawet gdy początkowe GA jest gotowe, zajmuje dużo czasu i wysiłku, aby bawić się parametrami, takimi jak wielkość populacji, prawdopodobieństwo mutacji i krzyżowania, itp., Aby znaleźć te, które pasują do konkretnego problemu.

W tej sekcji przedstawiamy kilka zaawansowanych tematów dotyczących algorytmów genetycznych. Czytelnik szukający jedynie wprowadzenia do AH może pominąć tę sekcję.

Ograniczone problemy optymalizacji

Ograniczone problemy optymalizacji to te problemy optymalizacyjne, w których musimy maksymalizować lub minimalizować daną wartość funkcji celu, która podlega pewnym ograniczeniom. Dlatego nie wszystkie wyniki w przestrzeni rozwiązań są wykonalne, a przestrzeń rozwiązań zawiera możliwe obszary, jak pokazano na poniższym rysunku.

W takim scenariuszu operatorzy krzyżowania i mutacji mogą dać nam rozwiązania, które są niewykonalne. W związku z tym w przypadku ograniczonych problemów optymalizacji należy zastosować dodatkowe mechanizmy w GA.

Niektóre z najczęstszych metod to -

Za pomocą penalty functions co zmniejsza przydatność niewykonalnych rozwiązań, najlepiej tak, aby przydatność była zmniejszana proporcjonalnie do liczby naruszonych ograniczeń lub odległości od wykonalnego obszaru.
Za pomocą repair functions które biorą niewykonalne rozwiązanie i modyfikują je tak, aby naruszone ograniczenia zostały spełnione.
Not allowing infeasible solutions w ogóle wejść do populacji.
Użyć special representation or decoder functions co zapewnia wykonalność rozwiązań.

Podstawy teoretyczne

W tej sekcji omówimy schemat i twierdzenie NFL wraz z hipotezą bloku konstrukcyjnego.

Twierdzenie o schemacie

Naukowcy próbowali zrozumieć matematykę stojącą za działaniem algorytmów genetycznych, a twierdzenie o schemacie Hollanda jest krokiem w tym kierunku. W ciągu roku wprowadzono różne ulepszenia i sugestie do twierdzenia o schemacie, aby uczynić je bardziej ogólnym.

W tej sekcji nie zagłębiamy się w matematykę twierdzenia o schemacie, a raczej staramy się wypracować podstawowe zrozumienie tego, czym jest twierdzenie o schemacie. Podstawowa terminologia, którą należy znać, jest następująca -

ZA Schemajest „szablonem”. Formalnie jest to ciąg nad alfabetem = {0,1, *},

gdzie * nie obchodzi i może mieć dowolną wartość.

Dlatego * 10 * 1 może oznaczać 01001, 01011, 11001 lub 11011

Z punktu widzenia geometrii schemat jest hiperpłaszczyzną w przestrzeni poszukiwań rozwiązań.
Order schematu to liczba określonych ustalonych pozycji w genie.

Defining length to odległość między dwoma najdalszymi stałymi symbolami w genie.

Twierdzenie o schemacie stwierdza, że ten schemat o ponadprzeciętnej sprawności, krótkiej długości definiowanej i niższym rzędzie ma większe szanse na przetrwanie krzyżowania i mutacji.

Hipoteza blokowa

Bloki konstrukcyjne to schematy niskiego rzędu, o małej długości definiującej, o podanej powyżej średniej sprawności. Hipoteza bloku budulcowego mówi, że takie bloki budulcowe służą jako podstawa sukcesu GA i adaptacji w GA w miarę ich postępu poprzez sukcesywną identyfikację i rekombinację takich „bloków budulcowych”.

Twierdzenie o braku darmowego lunchu (NFL)

Wolpert i Macready w 1997 roku opublikowali artykuł zatytułowany „No Free Lunch Theorems for Optimization”. Zasadniczo stwierdza się, że jeśli uśrednimy wszystkie możliwe problemy, to wszystkie nieodwiedzające algorytmy czarnej skrzynki będą wykazywać taką samą wydajność.

Oznacza to, że im lepiej rozumiemy problem, nasz AH staje się bardziej specyficzny dla problemu i daje lepszą wydajność, ale nadrabia to, słabo radząc sobie z innymi problemami.

Uczenie maszynowe oparte na GA

Algorytmy genetyczne znajdują również zastosowanie w uczeniu maszynowym. Classifier systems są formą genetics-based machine learning(GBML), które są często używane w dziedzinie uczenia maszynowego. Metody GBML to niszowe podejście do uczenia maszynowego.

Istnieją dwie kategorie systemów GBML -

The Pittsburg Approach - W tym podejściu jeden chromosom zakodował jedno rozwiązanie, więc rozwiązaniom przypisuje się dopasowanie.
The Michigan Approach - jedno rozwiązanie jest zwykle reprezentowane przez wiele chromosomów, więc dopasowanie jest przypisywane rozwiązaniom częściowym.

Należy pamiętać, że standardowe zagadnienia, takie jak crossover, mutation, lamarckian czy darwinian, są również obecne w systemach GBML.

Algorytmy genetyczne są wykorzystywane przede wszystkim w różnego rodzaju problemach optymalizacyjnych, ale często są również wykorzystywane w innych obszarach zastosowań.

W tej sekcji wymieniamy niektóre obszary, w których często używane są algorytmy genetyczne. To są -

Optimization- Algorytmy genetyczne są najczęściej wykorzystywane w problemach optymalizacyjnych, w których musimy maksymalizować lub minimalizować zadaną wartość funkcji celu przy zadanym zbiorze ograniczeń. Podejście do rozwiązywania problemów optymalizacji zostało podkreślone w całym samouczku.
Economics - GA są również używane do charakteryzowania różnych modeli ekonomicznych, takich jak model pajęczyny, rozwiązanie równowagi teorii gier, wycena aktywów itp.
Neural Networks - GA są również używane do uczenia sieci neuronowych, w szczególności powtarzających się sieci neuronowych.
Parallelization - GA mają również bardzo dobre możliwości równoległe i okazują się być bardzo skutecznymi środkami w rozwiązywaniu pewnych problemów, a także stanowią dobry obszar do badań.
Image Processing - GA są używane do różnych zadań cyfrowego przetwarzania obrazu (DIP), a także do dopasowywania gęstych pikseli.
Vehicle routing problems - Z wieloma miękkimi oknami czasowymi, wieloma magazynami i niejednorodną flotą.
Scheduling applications - GA są używane do rozwiązywania różnych problemów związanych z planowaniem, w szczególności problemów związanych z planowaniem czasu.
Machine Learning - jak już wspomniano, uczenie maszynowe oparte na genetyce (GBML) to niszowy obszar uczenia maszynowego.
Robot Trajectory Generation - Zastosowano GA do planowania ścieżki, którą pokonuje ramię robota, przemieszczając się z jednego punktu do drugiego.
Parametric Design of Aircraft - GA były używane do projektowania samolotów poprzez zmianę parametrów i rozwój lepszych rozwiązań.
DNA Analysis - Zastosowano GA do określenia struktury DNA na podstawie danych spektrometrycznych dotyczących próbki.
Multimodal Optimization - GA są oczywiście bardzo dobrymi podejściami do optymalizacji multimodalnej, w których musimy znaleźć wiele optymalnych rozwiązań.
Traveling salesman problem and its applications - Zastosowano GA do rozwiązania TSP, który jest dobrze znanym problemem kombinatorycznym przy użyciu nowatorskich strategii krzyżowania i pakowania.

Poniższe książki można odnieść w celu dalszego poszerzenia wiedzy czytelnika na temat algorytmów genetycznych i ogólnie obliczeń ewolucyjnych:

Algorytmy genetyczne w wyszukiwaniu, optymalizacji i uczeniu maszynowym wg David E. Goldberg.
Algorytmy genetyczne + Struktury danych = Programy ewolucyjne wg Zbigniew Michalewicz.
Praktyczne algorytmy genetyczne wg Randy L. Haupt i Sue Ellen Haupt.
Optymalizacja wielu celów za pomocą algorytmów ewolucyjnych wg Kalyanmoy Deb.