Algorytm genetyczny

Część serii o
algorytmie ewolucyjnym
Algorytm genetyczny
Programowanie genetyczne

NASA ST5 z 2006 roku . Ten skomplikowany kształt został znaleziony przez ewolucyjny komputerowy program do projektowania, aby stworzyć najlepszy wzór promieniowania. Nazywa się to wyewoluowaną anteną .

W informatyce i badaniach operacyjnych algorytm genetyczny ( GA ) to metaheurystyka inspirowana procesem doboru naturalnego , która należy do większej klasy algorytmów ewolucyjnych (EA). Algorytmy genetyczne są powszechnie używane do generowania wysokiej jakości rozwiązań optymalizacji i wyszukiwania , opierając się na operatorach inspirowanych biologią, takich jak mutacja , krzyżowanie i selekcja . Niektóre przykłady aplikacji GA obejmują optymalizację drzew decyzyjnych w celu uzyskania lepszej wydajności, rozwiązywanie łamigłówek sudoku , optymalizację hiperparametrów itp.

Metodologia

Problemy z optymalizacją

W algorytmie genetycznym populacja potencjalnych rozwiązań (zwanych jednostkami, stworzeniami, organizmami lub fenotypami ) problemu optymalizacji ewoluuje w kierunku lepszych rozwiązań. Każde rozwiązanie kandydujące ma zestaw właściwości (jego chromosomy lub genotyp ), które można mutować i zmieniać; tradycyjnie rozwiązania są reprezentowane binarnie jako ciągi zer i jedynek, ale możliwe są również inne kodowania.

Ewolucja zwykle zaczyna się od populacji losowo generowanych osobników i jest procesem iteracyjnym , w którym populacja w każdej iteracji nazywana jest pokoleniem . W każdym pokoleniu sprawność każdego osobnika w populacji; dopasowanie jest zwykle wartością funkcji celu w rozwiązywanym problemie optymalizacyjnym. Bardziej sprawne osobniki są stochastycznie z obecnej populacji, a genom każdego osobnika jest modyfikowany ( rekombinacja i prawdopodobnie losowo zmutowane), aby utworzyć nową generację. Nowa generacja rozwiązań kandydujących jest następnie wykorzystywana w następnej iteracji algorytmu . Zwykle algorytm kończy się, gdy zostanie wyprodukowana maksymalna liczba pokoleń lub osiągnięty zostanie zadowalający poziom sprawności populacji.

Typowy algorytm genetyczny wymaga:

  1. genetyczna reprezentacja domeny rozwiązania,
  2. funkcja dopasowania do oceny dziedziny rozwiązania.

Standardową reprezentacją każdego kandydującego rozwiązania jest tablica bitów (zwana także zestawem bitów lub ciągiem bitów ). Tablice innych typów i struktur mogą być używane zasadniczo w ten sam sposób. Główną właściwością, która sprawia, że ​​te reprezentacje genetyczne są wygodne, jest to, że ich części można łatwo dopasować ze względu na ich stały rozmiar, co ułatwia proste operacje krzyżowania . Można również zastosować reprezentacje o zmiennej długości, ale implementacja zwrotnicy jest w tym przypadku bardziej złożona. Reprezentacje przypominające drzewa są badane w programowaniu genetycznym a reprezentacje w postaci wykresów są badane w programowaniu ewolucyjnym ; mieszanka zarówno liniowych chromosomów, jak i drzew jest badana w programowaniu ekspresji genów .

Po zdefiniowaniu reprezentacji genetycznej i funkcji dopasowania GA przystępuje do inicjalizacji populacji rozwiązań, a następnie do jej ulepszenia poprzez powtarzalne stosowanie operatorów mutacji, krzyżowania, inwersji i selekcji.

Inicjalizacja

Wielkość populacji zależy od natury problemu, ale zazwyczaj zawiera kilkaset lub tysiące możliwych rozwiązań. Często populacja początkowa jest generowana losowo, pozwalając na cały wachlarz możliwych rozwiązań ( przestrzeń poszukiwań ). Czasami rozwiązania mogą być „zasiewane” w obszarach, w których prawdopodobnie można znaleźć rozwiązania optymalne.

Wybór

Główny artykuł: Selekcja (algorytm genetyczny)

W każdym kolejnym pokoleniu część istniejącej populacji jest wybierana do reprodukcji dla nowego pokolenia. Indywidualne rozwiązania są wybierane w opartym na dopasowaniu , w którym zazwyczaj częściej wybierane są rozwiązania lepiej dopasowane (mierzone za pomocą funkcji dopasowania ). Niektóre metody selekcji oceniają przydatność każdego rozwiązania i preferencyjnie wybierają najlepsze rozwiązania. Inne metody oceniają tylko losową próbę populacji, ponieważ pierwszy proces może być bardzo czasochłonny.

Funkcja dopasowania jest zdefiniowana na podstawie reprezentacji genetycznej i mierzy jakość reprezentowanego rozwiązania. Funkcja fitness jest zawsze zależna od problemu. Na przykład w problemie plecakowym chce się zmaksymalizować całkowitą wartość przedmiotów, które można umieścić w plecaku o określonej pojemności. Reprezentacją rozwiązania może być tablica bitów, gdzie każdy bit reprezentuje inny obiekt, a wartość bitu (0 lub 1) reprezentuje, czy obiekt znajduje się w plecaku. Nie każda taka reprezentacja jest słuszna, gdyż rozmiary przedmiotów mogą przekraczać pojemność plecaka. Sprawność fizyczna rozwiązania jest sumą wartości wszystkich przedmiotów w plecaku, jeśli reprezentacja jest poprawna, lub 0 w przeciwnym przypadku.

W niektórych problemach zdefiniowanie wyrażenia przystosowania jest trudne lub wręcz niemożliwe; w takich przypadkach symulacja może być wykorzystana do określenia wartości funkcji dopasowania fenotypu ( np. obliczeniowa dynamika płynów jest wykorzystywana do określenia oporu powietrza pojazdu, którego kształt jest zakodowany jako fenotyp), a nawet stosowane są interaktywne algorytmy genetyczne .

Operatory genetyczne

Główne artykuły: Crossover (algorytm genetyczny) i Mutacja (algorytm genetyczny)

Następnym krokiem jest wygenerowanie drugiej generacji populacji rozwiązań z tych wybranych, poprzez kombinację operatorów genetycznych : krzyżowanie (zwane też rekombinacją) i mutację .

Dla każdego nowego rozwiązania, które ma zostać wyprodukowane, wybierana jest do rozmnażania para rozwiązań „macierzystych” z wcześniej wybranej puli. Tworząc rozwiązanie „potomne” przy użyciu powyższych metod krzyżowania i mutacji, tworzone jest nowe rozwiązanie, które zazwyczaj ma wiele cech swoich „rodziców”. Dla każdego nowego dziecka wybierani są nowi rodzice, a proces trwa do momentu wygenerowania nowej populacji rozwiązań o odpowiedniej wielkości. Chociaż metody reprodukcji oparte na wykorzystaniu dwojga rodziców są bardziej „inspirowane biologią”, niektóre badania sugerują, że więcej niż dwoje „rodziców” generuje chromosomy wyższej jakości.

Procesy te ostatecznie skutkują następną generacją populacji chromosomów, która różni się od początkowej generacji. Ogólnie rzecz biorąc, dzięki tej procedurze średnia przystosowanie populacji wzrośnie, ponieważ do hodowli wybierane są tylko najlepsze organizmy z pierwszego pokolenia, a także niewielka część mniej dopasowanych rozwiązań. Te mniej dopasowane rozwiązania zapewniają różnorodność genetyczną w puli genetycznej rodziców, a tym samym zapewniają różnorodność genetyczną kolejnego pokolenia dzieci.

Opinie na temat znaczenia krzyżowania i mutacji są podzielone. Istnieje wiele odniesień w Fogel (2006), które potwierdzają znaczenie wyszukiwania opartego na mutacjach.

Chociaż krzyżowanie i mutacja są znane jako główne operatory genetyczne, możliwe jest użycie innych operatorów, takich jak przegrupowanie, kolonizacja-wymieranie lub migracja w algorytmach genetycznych. [ potrzebne źródło ]

Warto dostroić parametry, takie jak prawdopodobieństwo mutacji , prawdopodobieństwo krzyżowania się i wielkość populacji, aby znaleźć rozsądne ustawienia dla klasy problemu, nad którą pracujemy. Bardzo małe tempo mutacji może prowadzić do dryfu genetycznego (który ma charakter nieergodyczny) . Zbyt wysoka szybkość rekombinacji może prowadzić do przedwczesnej konwergencji algorytmu genetycznego. Zbyt wysoki wskaźnik mutacji może prowadzić do utraty dobrych rozwiązań, chyba że selekcja elitarna jest zatrudniony. Odpowiednia wielkość populacji zapewnia wystarczającą różnorodność genetyczną dla danego problemu, ale może prowadzić do marnowania zasobów obliczeniowych, jeśli zostanie ustawiona na wartość większą niż wymagana.

Heurystyka

Oprócz powyższych głównych operatorów, można zastosować inne heurystyki , aby obliczenia były szybsze lub bardziej niezawodne. Heurystyka specjacji penalizuje krzyżowanie się rozwiązań kandydujących, które są zbyt podobne; sprzyja to różnorodności populacji i pomaga zapobiegać przedwczesnej konwergencji do mniej optymalnego rozwiązania.

Zakończenie

Ten proces generacji jest powtarzany aż do osiągnięcia warunku zakończenia. Typowe warunki zakończenia to:

  • Znaleziono rozwiązanie spełniające minimalne kryteria
  • Osiągnięto ustaloną liczbę pokoleń
  • Osiągnięto przydzielony budżet (czas obliczeń/pieniądze).
  • Dopasowanie rozwiązania o najwyższym rankingu osiąga lub osiągnęło taki poziom, że kolejne iteracje nie dają już lepszych wyników
  • Kontrola ręczna
  • Kombinacje powyższych

Hipoteza bloków konstrukcyjnych

Algorytmy genetyczne są proste do wdrożenia, ale ich zachowanie jest trudne do zrozumienia. W szczególności trudno jest zrozumieć, dlaczego te algorytmy często odnoszą sukcesy w generowaniu rozwiązań o wysokiej sprawności, gdy są stosowane do problemów praktycznych. Hipoteza bloków konstrukcyjnych (BBH) składa się z:

  1. Opis heurystyki, która dokonuje adaptacji poprzez identyfikację i rekombinację „cegiełek”, tj. schematów niskiego rzędu, o małej długości definiującej i ponadprzeciętnym dopasowaniu.
  2. Hipoteza, że ​​algorytm genetyczny dokonuje adaptacji poprzez niejawne i efektywne wdrożenie tej heurystyki.

Goldberg opisuje heurystykę w następujący sposób:

„Krótkie, niskiego rzędu i wysoce dopasowane schematy są próbkowane, rekombinowane [przecinane] i ponownie próbkowane w celu utworzenia ciągów o potencjalnie wyższym dopasowaniu. W pewnym sensie, pracując z tymi konkretnymi schematami [elementami konstrukcyjnymi], zmniejszyliśmy złożoność naszego problemu; zamiast budować struny o wysokiej wydajności, próbując każdej możliwej kombinacji, konstruujemy coraz lepsze struny z najlepszych częściowych rozwiązań z poprzednich sampli.
„Ponieważ wysoce dopasowane schematy o małej długości definiującej i niskim rzędzie odgrywają tak ważną rolę w działaniu algorytmów genetycznych, nadaliśmy im już specjalną nazwę: klocki. Tak jak dziecko tworzy wspaniałe fortece poprzez układanie prostych klocków z drewna, podobnie jak algorytm genetyczny szuka niemal optymalnej wydajności poprzez zestawienie krótkich, nisko rzędowych, wysokowydajnych schematów lub bloków konstrukcyjnych”.

Pomimo braku konsensusu co do słuszności hipotezy budulcowej, była ona konsekwentnie oceniana i wykorzystywana jako odniesienie przez lata. Zaproponowano na przykład wiele algorytmów szacowania dystrybucji , próbując zapewnić środowisko, w którym hipoteza byłaby spełniona. Chociaż odnotowano dobre wyniki dla niektórych klas problemów, nadal pozostaje sceptycyzm co do ogólności i / lub praktyczności hipotezy bloków konstrukcyjnych jako wyjaśnienia wydajności GA. Rzeczywiście, istnieje rozsądna ilość pracy, która próbuje zrozumieć jego ograniczenia z perspektywy szacowania algorytmów dystrybucji.

Ograniczenia

Istnieją ograniczenia stosowania algorytmu genetycznego w porównaniu z alternatywnymi algorytmami optymalizacyjnymi:

  • Wielokrotna ocena funkcji przystosowania dla złożonych problemów jest często najbardziej wygórowanym i ograniczającym segmentem sztucznych algorytmów ewolucyjnych. Znalezienie optymalnego rozwiązania złożonych, wielowymiarowych, multimodalnych problemów często wymaga bardzo kosztownych ocen funkcji dopasowania . W rzeczywistych problemach, takich jak problemy optymalizacji strukturalnej, ocena pojedynczej funkcji może wymagać od kilku godzin do kilku dni pełnej symulacji. Typowe metody optymalizacji nie radzą sobie z tego typu problemami. W takim przypadku może być konieczne zrezygnowanie z dokładnej oceny i zastosowanie przybliżonej sprawności to jest wydajne obliczeniowo. Oczywiste jest, że połączenie przybliżonych modeli może być jednym z najbardziej obiecujących podejść do przekonującego wykorzystania GA do rozwiązywania złożonych problemów z życia wziętych.
  • Algorytmy genetyczne nie skalują się dobrze ze złożonością. Oznacza to, że tam, gdzie liczba elementów narażonych na mutację jest duża, często następuje wykładniczy wzrost rozmiaru przestrzeni poszukiwań. To sprawia, że ​​​​bardzo trudno jest zastosować tę technikę w przypadku problemów, takich jak projektowanie silnika, domu lub samolotu [ potrzebne źródło ] . Aby takie problemy były możliwe do rozwiązania w ramach poszukiwań ewolucyjnych, należy je rozbić na najprostszą możliwą reprezentację. Dlatego zwykle widzimy algorytmy ewolucyjne kodujące projekty łopatek wentylatorów zamiast silników, kształty budynków zamiast szczegółowych planów konstrukcyjnych i płaty zamiast projektów całych samolotów. Drugim problemem złożoności jest kwestia ochrony części, które ewoluowały, aby reprezentować dobre rozwiązania, przed dalszymi destrukcyjnymi mutacjami, zwłaszcza gdy ich ocena przydatności wymaga, aby dobrze łączyły się z innymi częściami.
  • „Lepsze” rozwiązanie to tylko porównanie z innymi rozwiązaniami. W rezultacie kryterium zatrzymania nie jest jasne w każdym problemie.
  • W wielu problemach GA mają tendencję do zbiegania się w kierunku lokalnych optimów lub nawet dowolnych punktów, a nie globalnego optimum problemu. Oznacza to, że nie „wie, jak” poświęcić krótkoterminową sprawność, aby uzyskać długoterminową sprawność. Prawdopodobieństwo wystąpienia tego zjawiska zależy od kształtu krajobrazu fitness : niektóre problemy mogą zapewniać łatwe wejście w kierunku optimum globalnego, inne mogą ułatwiać funkcji znalezienie lokalnych optimów. Problem ten można złagodzić, stosując inną funkcję dopasowania, zwiększając tempo mutacji lub stosując techniki selekcji, które utrzymują zróżnicowaną populację rozwiązań, chociaż twierdzenie No Free Lunch dowodzi, że nie ma ogólnego rozwiązania tego problemu. Powszechną techniką utrzymywania różnorodności jest nakładanie „kary niszowej”, w ramach której każda grupa osobników o wystarczającym podobieństwie (promień niszy) ma dodaną karę, która zmniejszy reprezentację tej grupy w kolejnych pokoleniach, dopuszczając inne (mniej podobne ) osobników do utrzymania w populacji. Ta sztuczka może jednak nie być skuteczna, w zależności od krajobrazu problemu. Inną możliwą techniką byłoby po prostu zastąpienie części populacji losowo wygenerowanymi osobnikami, gdy większość populacji jest do siebie zbyt podobna. Różnorodność jest ważna w algorytmach genetycznych (i programowanie genetyczne ), ponieważ krzyżowanie jednorodnej populacji nie daje nowych rozwiązań. W strategiach ewolucji i programowaniu ewolucyjnym różnorodność nie jest niezbędna ze względu na większą zależność od mutacji.
  • Operowanie na dynamicznych zbiorach danych jest trudne, ponieważ genomy zaczynają wcześnie zbliżać się do rozwiązań, które mogą już nie być ważne dla późniejszych danych. Zaproponowano kilka metod, aby temu zaradzić, zwiększając w jakiś sposób różnorodność genetyczną i zapobiegając wczesnej konwergencji, albo poprzez zwiększenie prawdopodobieństwa mutacji, gdy jakość rozwiązania spada (zwana hipermutacją wyzwalaną ), albo przez sporadyczne wprowadzanie zupełnie nowych, losowo generowanych elementów do puli genów (nazywani przypadkowymi imigrantami ). Znowu strategie ewolucyjne i programowanie ewolucyjne można realizować tzw. „strategią przecinkową”, w której nie utrzymuje się rodziców, a nowych rodziców wybiera się tylko z potomstwa. Może to być bardziej skuteczne w przypadku problemów dynamicznych.
  • GA nie mogą skutecznie rozwiązywać problemów, w których jedyną miarą sprawności jest pojedyncza miara dobra/zła (jak problemy decyzyjne ), ponieważ nie ma sposobu na zbieżność rozwiązania (nie ma wzgórza do pokonania). W takich przypadkach losowe wyszukiwanie może znaleźć rozwiązanie tak szybko, jak GA. Jeśli jednak sytuacja pozwala na powtórzenie próby sukcesu/porażki, dając (ewentualnie) różne wyniki, to stosunek sukcesów do porażek stanowi odpowiednią miarę sprawności.
  • W przypadku określonych problemów optymalizacyjnych i przypadków problemów inne algorytmy optymalizacyjne mogą być bardziej wydajne niż algorytmy genetyczne pod względem szybkości zbieżności. Algorytmy alternatywne i uzupełniające obejmują strategie ewolucyjne , programowanie ewolucyjne , symulowane wyżarzanie , adaptację Gaussa , wspinaczkę górską i inteligencję roju (np. optymalizacja kolonii mrówek , optymalizacja roju cząstek ) oraz metody oparte na programowaniu liniowym liczb całkowitych . Przydatność algorytmów genetycznych zależy od stopnia znajomości problemu; dobrze znane problemy często mają lepsze, bardziej specjalistyczne podejście.

Warianty

Reprezentacja chromosomów

Główny artykuł: reprezentacja genetyczna

Najprostszy algorytm przedstawia każdy chromosom jako ciąg bitów . Zazwyczaj parametry numeryczne mogą być reprezentowane przez liczby całkowite , chociaż możliwe jest użycie reprezentacji zmiennoprzecinkowych . Reprezentacja zmiennoprzecinkowa jest naturalna dla strategii ewolucyjnych i programowania ewolucyjnego . Zaproponowano pojęcie algorytmów genetycznych o wartości rzeczywistej, ale w rzeczywistości jest to myląca nazwa, ponieważ tak naprawdę nie reprezentuje teorii bloków konstrukcyjnych zaproponowanej przez Johna Henry'ego Hollanda W latach siedemdziesiątych. Teoria ta nie jest jednak pozbawiona wsparcia, opartego na wynikach teoretycznych i eksperymentalnych (patrz poniżej). Podstawowy algorytm wykonuje krzyżowanie i mutacje na poziomie bitowym. Inne warianty traktują chromosom jako listę liczb, które są indeksami w tabeli instrukcji, węzłami na połączonej liście , skrótami , obiektami lub jakąkolwiek inną możliwą do wyobrażenia strukturą danych . Krzyżowanie i mutacja są przeprowadzane w taki sposób, aby respektować granice elementów danych. Dla większości typów danych można zaprojektować określone operatory wariacyjne. Różne typy danych chromosomowych wydają się działać lepiej lub gorzej w przypadku różnych specyficznych domen problemowych.

Gdy używane są reprezentacje liczb całkowitych w postaci łańcuchów bitów, często stosuje się kodowanie Graya . W ten sposób na małe zmiany liczby całkowitej można łatwo wpływać poprzez mutacje lub krzyżowania. Stwierdzono, że pomaga to zapobiegać przedwczesnej konwergencji w tak zwanych ścianach Hamminga , w których musi wystąpić zbyt wiele jednoczesnych mutacji (lub zdarzeń krzyżowania), aby zmienić chromosom na lepsze rozwiązanie.

Inne podejścia obejmują użycie tablic liczb o wartościach rzeczywistych zamiast ciągów bitów do reprezentowania chromosomów. Wyniki teorii schematów sugerują, że generalnie im mniejszy alfabet, tym lepsze wyniki, ale początkowo badacze byli zaskoczeni, że dobre wyniki uzyskano, stosując chromosomy o wartościach rzeczywistych. Zostało to wyjaśnione jako zbiór rzeczywistych wartości w skończonej populacji chromosomów tworzących wirtualny alfabet (gdy dominuje selekcja i rekombinacja) o znacznie mniejszej liczności, niż można by oczekiwać od reprezentacji zmiennoprzecinkowej.

Rozszerzenie domeny problemowej dostępnej za pomocą algorytmu genetycznego można uzyskać poprzez bardziej złożone kodowanie pul rozwiązań poprzez połączenie kilku typów heterogenicznie kodowanych genów w jeden chromosom. To szczególne podejście pozwala na rozwiązywanie problemów optymalizacyjnych, które wymagają bardzo różnych dziedzin definicji parametrów problemu. Na przykład w problemach kaskadowego dostrajania kontrolera struktura kontrolera pętli wewnętrznej może należeć do konwencjonalnego regulatora trzech parametrów, podczas gdy pętla zewnętrzna może implementować kontroler lingwistyczny (taki jak system rozmyty), który ma z natury inny opis. Ta szczególna forma kodowania wymaga wyspecjalizowanego mechanizmu krzyżowania, który rekombinuje chromosom według sekcji, i jest użytecznym narzędziem do modelowania i symulacji złożonych systemów adaptacyjnych, zwłaszcza procesów ewolucyjnych.

Elitarność

Praktycznym wariantem ogólnego procesu konstruowania nowej populacji jest umożliwienie przeniesienia najlepszych organizmów z obecnego pokolenia do następnego, w niezmienionej postaci. Strategia ta znana jest jako selekcja elitarna i gwarantuje, że jakość rozwiązania uzyskanego przez GA nie spadnie z pokolenia na pokolenie.

Implementacje równoległe

Równoległe implementacje algorytmów genetycznych występują w dwóch odmianach. Równoległe algorytmy genetyczne gruboziarniste zakładają populację na każdym z węzłów komputera i migrację osobników między węzłami. Drobnoziarniste równoległe algorytmy genetyczne zakładają, że w każdym węźle procesora znajduje się osobnik, który współpracuje z sąsiednimi osobnikami w celu selekcji i reprodukcji. Inne warianty, takie jak algorytmy genetyczne dla optymalizacji online , wprowadzają zależność od czasu lub szum w funkcji dopasowania.

Adaptacyjne GA

Algorytmy genetyczne z parametrami adaptacyjnymi (adaptacyjne algorytmy genetyczne, AGA) to kolejny znaczący i obiecujący wariant algorytmów genetycznych. Prawdopodobieństwa krzyżowania się (pc) i mutacji (pm) w dużej mierze determinują stopień dokładności rozwiązania i szybkość zbieżności, jaką mogą uzyskać algorytmy genetyczne. Naukowcy przeanalizowali analitycznie konwergencję GA.

Zamiast używać stałych wartości pc i pm , AGA wykorzystują informacje o populacji w każdym pokoleniu i adaptacyjnie dostosowują pc i pm w celu utrzymania różnorodności populacji, jak również utrzymania zdolności do konwergencji. W AGA (adaptacyjny algorytm genetyczny) dopasowanie pc i pm zależy od wartości dopasowania rozwiązań. Istnieje więcej przykładów wariantów AGA: Metoda sukcesywnego powiększania jest wczesnym przykładem poprawy konwergencji. w CAGA (adaptacyjny algorytm genetyczny oparty na klastrowaniu), dzięki zastosowaniu analizy skupień do oceny stanów optymalizacji populacji, dostosowanie pc i pm zależy od tych stanów optymalizacji. Najnowsze podejścia wykorzystują bardziej abstrakcyjne zmienne do decydowania o pc i pm . Przykładami są zasady dominacji i współdominacji oraz wypoziomowane podejścia interpolacyjne, które łączą elastyczne GA ze zmodyfikowanym wyszukiwaniem A*, aby poradzić sobie z anizotropowością przestrzeni wyszukiwania.

Połączenie GA z innymi metodami optymalizacji może być dość skuteczne. GA jest zwykle dość dobry w znajdowaniu ogólnie dobrych globalnych rozwiązań, ale dość nieskuteczny w znajdowaniu kilku ostatnich mutacji, aby znaleźć absolutne optimum. Inne techniki (takie jak prosta wspinaczka górska ) są dość skuteczne w znajdowaniu absolutnego optimum w ograniczonym regionie. Naprzemienne GA i wspinaczka górska mogą poprawić efektywność GA [ potrzebne źródło ] , jednocześnie przezwyciężając brak solidności wspinaczki górskiej.

Oznacza to, że reguły zmienności genetycznej mogą mieć inne znaczenie w przypadku naturalnym. Na przykład – pod warunkiem, że kroki są przechowywane w kolejności – crossing-over może zsumować kilka kroków z DNA matki, dodając liczbę kroków z DNA ojca i tak dalej. To jest jak dodanie wektorów, które z większym prawdopodobieństwem mogą podążać za grzbietem w krajobrazie fenotypowym. W ten sposób wydajność procesu można zwiększyć o wiele rzędów wielkości. Ponadto operator inwersji ma możliwość ułożenia kroków w następującej po sobie kolejności lub dowolnej innej odpowiedniej kolejności na korzyść przetrwania lub wydajności.

Odmiana, w której ewoluuje populacja jako całość, a nie jej poszczególni członkowie, jest znana jako rekombinacja puli genów.

Opracowano szereg odmian, aby spróbować poprawić działanie GA w problemach o wysokim stopniu dopasowania epistazy, tj. gdy dopasowanie rozwiązania składa się z oddziałujących na siebie podzbiorów jego zmiennych. Takie algorytmy mają na celu poznanie (przed wykorzystaniem) tych korzystnych interakcji fenotypowych. W związku z tym są one zgodne z hipotezą bloków konstrukcyjnych w adaptacyjnym zmniejszaniu destrukcyjnej rekombinacji. Wybitnymi przykładami tego podejścia są mGA, GEMGA i LLGA.

Domeny problematyczne

Problemy, które wydają się być szczególnie odpowiednie do rozwiązania za pomocą algorytmów genetycznych, obejmują układanie harmonogramów i problemy z planowaniem , a wiele pakietów oprogramowania do planowania jest opartych na GA [ potrzebne źródło ] . GA zostały również zastosowane w inżynierii . Algorytmy genetyczne są często stosowane jako podejście do rozwiązywania globalnych problemów optymalizacyjnych.

Jako ogólna zasada, algorytmy genetyczne mogą być przydatne w domenach problemowych, które mają złożony krajobraz sprawności , ponieważ mieszanie, tj. mutacja w połączeniu z krzyżowaniem , ma na celu odsunięcie populacji od lokalnych optimów , w których tradycyjny algorytm wspinaczki górskiej mógłby utknąć in. Zauważ, że powszechnie używane operatory krzyżowania nie mogą zmienić żadnej jednorodnej populacji. Sama mutacja może zapewnić ergodyczność całego procesu algorytmu genetycznego (postrzeganego jako łańcuch Markowa ).

Przykłady problemów rozwiązywanych przez algorytmy genetyczne obejmują: lustra zaprojektowane do kierowania światła słonecznego do kolektora słonecznego, anteny przeznaczone do odbierania sygnałów radiowych w kosmosie, metody chodzenia figur komputerowych, optymalne projektowanie ciał aerodynamicznych w złożonych polach przepływu

W swoim Podręczniku projektowania algorytmów Skiena odradza stosowanie algorytmów genetycznych do jakichkolwiek zadań :

[I] t jest całkiem nienaturalne modelować aplikacje pod względem operatorów genetycznych, takich jak mutacja i krzyżowanie na ciągach bitów. Pseudobiologia dodaje kolejny poziom złożoności między tobą a twoim problemem. Po drugie, algorytmy genetyczne bardzo długo zajmują się nietrywialnymi problemami. […] [T] on analogia z ewolucją - gdzie znaczący postęp wymaga [sic] milionów lat - może być całkiem odpowiednia.

[...]

Nigdy nie spotkałem problemu, w którym algorytmy genetyczne wydawałyby mi się właściwym sposobem na zaatakowanie go. Co więcej, nigdy nie widziałem żadnych wyników obliczeń przy użyciu algorytmów genetycznych, które wywarłyby na mnie pozytywne wrażenie. Trzymaj się symulowanego wyżarzania dla potrzeb heurystycznego wyszukiwania voodoo.

— Stefan Skiena

Historia

W 1950 roku Alan Turing zaproponował „uczącą się maszynę”, która odpowiadałaby zasadom ewolucji. Komputerowa symulacja ewolucji rozpoczęła się już w 1954 roku od pracy Nilsa Aalla Barricelliego , który korzystał z komputera w Institute for Advanced Study w Princeton, New Jersey . Jego publikacja z 1954 roku nie została powszechnie zauważona. Począwszy od 1957 roku australijski genetyk ilościowy Alex Fraser opublikował serię artykułów na temat symulacji sztucznej selekcji organizmów z wieloma loci kontrolującymi mierzalną cechę. Od tych początków komputerowa symulacja ewolucji przez biologów stała się bardziej powszechna we wczesnych latach sześćdziesiątych, a metody zostały opisane w książkach Frasera i Burnella (1970) oraz Crosby'ego (1973). Symulacje Frasera obejmowały wszystkie istotne elementy nowoczesnych algorytmów genetycznych. Ponadto Hans-Joachim Bremermann opublikował serię artykułów w latach 60. XX wieku, w których przyjęto również populację rozwiązań problemów optymalizacyjnych, przechodzących rekombinację, mutację i selekcję. Badania Bremermanna obejmowały również elementy nowoczesnych algorytmów genetycznych. Inni godni uwagi pionierzy to Richard Friedberg, George Friedman i Michael Conrad. Wiele wczesnych artykułów zostało przedrukowanych przez Fogela (1998).

Chociaż Barricelli w pracy, którą przedstawił w 1963 r., symulował ewolucję umiejętności grania w prostą grę, sztuczna ewolucja stała się powszechnie uznaną metodą optymalizacji dopiero w wyniku prac Ingo Rechenberga i Hansa-Paula Schwefela w latach 60. Lata 70. – grupa Rechenberga była w stanie rozwiązywać złożone problemy inżynierskie za pomocą strategii ewolucyjnych . Innym podejściem była technika programowania ewolucyjnego Lawrence'a J. Fogela , która została zaproponowana do generowania sztucznej inteligencji. Programowanie ewolucyjne pierwotnie używał automatów skończonych do przewidywania środowisk oraz używał zmienności i selekcji do optymalizacji logiki predykcyjnej. W szczególności algorytmy genetyczne stały się popularne dzięki pracom Johna Hollanda we wczesnych latach siedemdziesiątych, a zwłaszcza jego książce Adaptation in Natural and Artificial Systems (1975). Jego praca wywodzi się z badań nad automatami komórkowymi , prowadzonych przez Hollanda i jego studentów na University of Michigan . Holland wprowadził sformalizowane ramy przewidywania jakości następnej generacji, tzw Twierdzenie o schemacie Hollanda . Badania nad GA pozostawały w dużej mierze teoretyczne aż do połowy lat 80. XX wieku, kiedy to w Pittsburghu w Pensylwanii odbyła się Pierwsza Międzynarodowa Konferencja na temat Algorytmów Genetycznych .

Produkty komercyjne

Pod koniec lat 80-tych General Electric zaczął sprzedawać pierwszy na świecie produkt algorytmu genetycznego, zestaw narzędzi oparty na komputerach typu mainframe przeznaczony do procesów przemysłowych. [ odniesienie cykliczne ] W 1989 roku firma Axcelis, Inc. wypuściła Evolver , pierwszy na świecie komercyjny produkt GA dla komputerów stacjonarnych. John Markoff, pisarz technologiczny New York Timesa pisał o Evolverze w 1990 roku i pozostał jedynym interaktywnym komercyjnym algorytmem genetycznym do 1995 roku. Evolver został sprzedany firmie Palisade w 1997 roku, przetłumaczony na kilka języków i obecnie jest w szóstej wersji. Od lat 90. MATLAB wbudował trzy heurystyczne algorytmy optymalizacji bez pochodnych (symulowane wyżarzanie, optymalizacja roju cząstek, algorytm genetyczny) oraz dwa algorytmy wyszukiwania bezpośredniego (przeszukiwanie simpleksowe, wyszukiwanie wzorców).

Powiązane techniki

Zobacz też: Lista zastosowań algorytmów genetycznych

Pola nadrzędne

Algorytmy genetyczne to poddziedzina:

Powiązane pola

Algorytmy ewolucyjne

Główny artykuł: Algorytm ewolucyjny

Algorytmy ewolucyjne to poddziedzina obliczeń ewolucyjnych .

  • Strategie ewolucyjne (ES, patrz Rechenberg, 1994) ewoluują osobniki za pomocą mutacji i pośredniej lub dyskretnej rekombinacji. Algorytmy ES są zaprojektowane w szczególności do rozwiązywania problemów w dziedzinie wartości rzeczywistych. Wykorzystują samoadaptację do dostosowania parametrów kontrolnych wyszukiwania. Derandomizacja samoadaptacji doprowadziła do powstania współczesnej strategii ewolucji adaptacji macierzy kowariancji ( CMA-ES ).
  • Programowanie ewolucyjne (EP) obejmuje populacje rozwiązań z głównie mutacjami i selekcją oraz arbitralnymi reprezentacjami. Wykorzystują samoadaptację do dostosowywania parametrów i mogą obejmować inne operacje wariacyjne, takie jak łączenie informacji od wielu rodziców.
  • Algorytm szacowania dystrybucji (EDA) zastępuje tradycyjne operatory reprodukcji operatorami sterowanymi modelami. Takich modeli uczy się od populacji za pomocą technik uczenia maszynowego i przedstawia w postaci probabilistycznych modeli graficznych, z których można pobierać próbki nowych rozwiązań lub generować je za pomocą krzyżowania z przewodnikiem.
  • Programowanie genetyczne (GP) to pokrewna technika spopularyzowana przez Johna Kozę , w której optymalizowane są programy komputerowe, a nie parametry funkcji. Programowanie genetyczne często wykorzystuje wewnętrzne struktury danych oparte na drzewach do reprezentowania programów komputerowych do adaptacji zamiast struktur list typowych dla algorytmów genetycznych. Istnieje wiele wariantów programowania genetycznego, w tym kartezjańskie programowanie genetyczne , programowanie ekspresji genów , ewolucja gramatyczna , liniowe programowanie genetyczne , Programowanie wielu wyrażeń itp.
  • Algorytm grupowania genetycznego (GGA) to ewolucja GA, w której punkt ciężkości jest przesunięty z pojedynczych elementów, jak w klasycznych GA, na grupy lub podzbiór elementów. Ideą stojącą za tą ewolucją GA zaproponowaną przez Emanuela Falkenauera jest to, że rozwiązywanie niektórych złożonych problemów, czyli grupowania lub partycjonowania , w których zestaw elementów musi zostać podzielony na rozłączną grupę elementów w optymalny sposób, byłoby lepiej osiągnięte poprzez charakterystykę grup elementów równoważnych genom. Tego rodzaju problemy obejmują pakowanie pojemników , równoważenie linii, tworzenie klastrów w odniesieniu do miary odległości, równych stosów itp., na których klasyczne GA okazały się słabe. Uczynienie genów równoważnymi grupom implikuje chromosomy, które na ogół mają zmienną długość, oraz specjalne operatory genetyczne, które manipulują całymi grupami elementów. W szczególności w przypadku pakowania do pojemników, hybrydyzacja GGA z kryterium dominacji Martello i Totha jest prawdopodobnie najlepszą dotychczas techniką.
  • Interaktywne algorytmy ewolucyjne to algorytmy ewolucyjne, które wykorzystują ludzką ocenę. Zwykle stosuje się je w dziedzinach, w których trudno jest zaprojektować funkcję sprawności obliczeniowej, na przykład zmieniając obrazy, muzykę, projekty artystyczne i formy, aby dopasować je do preferencji estetycznych użytkowników.

Inteligencja roju

Główny artykuł: Inteligencja roju

Inteligencja roju to poddziedzina obliczeń ewolucyjnych .

  • Optymalizacja kolonii mrówek ( ACO ) wykorzystuje wiele mrówek (lub agentów) wyposażonych w model feromonów do przemierzania przestrzeni rozwiązania i znajdowania lokalnie produktywnych obszarów.
  • Chociaż uważany za algorytm szacowania dystrybucji , optymalizacja roju cząstek (PSO) to metoda obliczeniowa optymalizacji wieloparametrowej, która również wykorzystuje podejście populacyjne. Populacja (rój) potencjalnych rozwiązań (cząstek) porusza się w przestrzeni poszukiwań, a na ruch cząstek wpływa zarówno ich własna najlepiej znana pozycja, jak i najlepiej znana globalna pozycja roju. Podobnie jak algorytmy genetyczne, metoda PSO polega na wymianie informacji między członkami populacji. W niektórych problemach PSO jest często bardziej wydajny obliczeniowo niż GA, zwłaszcza w nieograniczonych problemach ze zmiennymi ciągłymi.

Inne ewolucyjne algorytmy obliczeniowe

Obliczenia ewolucyjne to poddziedzina metod metaheurystycznych .

  • Algorytm memetyczny (MA), często nazywany między innymi hybrydowym algorytmem genetycznym , jest metodą populacyjną, w której rozwiązania również podlegają lokalnym fazom doskonalenia. Idea algorytmów memetycznych wywodzi się z memów , które w przeciwieństwie do genów potrafią się dostosowywać. W niektórych problematycznych obszarach okazały się one bardziej wydajne niż tradycyjne algorytmy ewolucyjne.
  • Algorytmy bakteriologiczne (BA) inspirowane ekologią ewolucyjną , aw szczególności adaptacją bakteriologiczną. Ekologia ewolucyjna to badanie żywych organizmów w kontekście ich środowiska, w celu odkrycia, w jaki sposób się dostosowują. Jego podstawową koncepcją jest to, że w heterogenicznym środowisku nie ma jednej osoby, która pasowałaby do całego środowiska. Trzeba więc rozumować na poziomie populacji. Uważa się również, że BA można z powodzeniem zastosować do złożonych problemów związanych z pozycjonowaniem (anteny do telefonów komórkowych, planowanie urbanistyczne itp.) Lub do eksploracji danych.
  • Algorytm kulturowy (CA) składa się z komponentu populacyjnego prawie identycznego z algorytmem genetycznym oraz dodatkowo komponentu wiedzy zwanego przestrzenią przekonań.
  • Ewolucja różnicowa (DE) inspirowana migracją superorganizmów.
  • Adaptacja Gaussa (adaptacja normalna lub naturalna, w skrócie NA, aby uniknąć pomylenia z GA) ma na celu maksymalizację wydajności produkcji systemów przetwarzania sygnałów. Może być również wykorzystany do zwykłej optymalizacji parametrycznej. Opiera się na pewnym twierdzeniu obowiązującym dla wszystkich obszarów dopuszczalności i wszystkich rozkładów Gaussa. Efektywność NA opiera się na teorii informacji i pewnym twierdzeniu o efektywności. Jego efektywność definiuje się jako informację podzieloną przez pracę potrzebną do jej uzyskania. Ponieważ NA maksymalizuje średnie przystosowanie, a nie przystosowanie jednostki, krajobraz jest wygładzony w taki sposób, że doliny między szczytami mogą zniknąć. Dlatego ma pewną „ambicję”, aby uniknąć lokalnych szczytów w krajobrazie fitness. NA jest również dobra we wspinaniu się na ostre grzbiety poprzez adaptację macierzy momentu, ponieważ NA może maksymalizować nieład ( informacje o średniej ) Gaussa przy jednoczesnym utrzymaniu stałej średniej sprawności .

Inne metody metaheurystyczne

Metody metaheurystyczne zasadniczo mieszczą się w stochastycznych metodach optymalizacji.

  • Symulowane wyżarzanie (SA) to powiązana globalna technika optymalizacji, która przemierza przestrzeń poszukiwań poprzez testowanie losowych mutacji w indywidualnym rozwiązaniu. Mutacja zwiększająca sprawność jest zawsze akceptowana. Mutacja obniżająca sprawność jest akceptowana probabilistycznie na podstawie różnicy w sprawności i malejącego parametru temperatury. W żargonie SA mówi się o poszukiwaniu najniższej energii zamiast maksymalnej sprawności. SA może być również używany w ramach standardowego algorytmu GA, rozpoczynając od stosunkowo wysokiego tempa mutacji i zmniejszając go w czasie zgodnie z określonym harmonogramem.
  • Wyszukiwanie z Tabu (TS) jest podobne do symulowanego wyżarzania, ponieważ oba przechodzą przez przestrzeń rozwiązań, testując mutacje indywidualnego rozwiązania. Podczas gdy symulowane wyżarzanie generuje tylko jedno zmutowane rozwiązanie, wyszukiwanie tabu generuje wiele zmutowanych rozwiązań i przechodzi do rozwiązania o najniższej energii spośród wygenerowanych. Aby zapobiec cyklom i zachęcić do większego ruchu w przestrzeni rozwiązań, utrzymywana jest lista tabu częściowych lub kompletnych rozwiązań. Zabrania się przechodzenia do rozwiązania, które zawiera elementy z listy tabu, która jest aktualizowana w miarę przechodzenia rozwiązania przez przestrzeń rozwiązań.
  • Ekstremalna optymalizacja (EO) W przeciwieństwie do GA, które działają z populacją potencjalnych rozwiązań, EO rozwija pojedyncze rozwiązanie i dokonuje lokalnych modyfikacji najgorszych komponentów. Wymaga to wybrania odpowiedniej reprezentacji, która pozwala na przypisanie poszczególnym składnikom rozwiązania miary jakości („fitness”). Główną zasadą tego algorytmu jest wyłaniająca się poprawa poprzez selektywne usuwanie komponentów niskiej jakości i zastępowanie ich losowo wybranym komponentem. Jest to zdecydowanie sprzeczne z GA, która wybiera dobre rozwiązania, próbując stworzyć lepsze rozwiązania.

Inne stochastyczne metody optymalizacji

  • Metoda entropii krzyżowej (CE) generuje rozwiązania kandydujące poprzez sparametryzowany rozkład prawdopodobieństwa. Parametry są aktualizowane poprzez minimalizację entropii krzyżowej, aby wygenerować lepsze próbki w następnej iteracji.
  • Reaktywna optymalizacja wyszukiwania (RSO) opowiada się za integracją subsymbolicznych technik uczenia maszynowego z heurystykami wyszukiwania w celu rozwiązywania złożonych problemów optymalizacyjnych. Słowo reaktywny wskazuje na gotową reakcję na zdarzenia podczas przeszukiwania wewnętrznej pętli sprzężenia zwrotnego online w celu samodostrojenia krytycznych parametrów. Metodologie interesujące dla wyszukiwania reaktywnego obejmują uczenie maszynowe i statystyki, w szczególności uczenie przez wzmacnianie , uczenie aktywne lub uczenie oparte na zapytaniach , sieci neuronowe i metaheurystykę .

Zobacz też

Bibliografia

Linki zewnętrzne

Zasoby

Samouczki

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Genetic_algorithm&oldid=1141656867 ”