Algorytm genetyczny - Genetic algorithm

Antena sondy kosmicznej NASA ST5 z 2006 roku . Ten skomplikowany kształt został odnaleziony przez ewolucyjny program komputerowy do tworzenia najlepszego wzorca promieniowania. Jest znany jako rozwinięta antena .

W informatyce i Badań Operacyjnych , o algorytm genetyczny ( GA ) jest metaheurystyka zainspirowany procesie doboru naturalnego , który należy do większej klasy algorytmów ewolucyjnych (EA). Algorytmy genetyczne są powszechnie używane do generowania wysokiej jakości rozwiązań problemów optymalizacji i wyszukiwania, opierając się na operatorach inspirowanych biologicznie, takich jak mutacja , krzyżowanie i selekcja .

Metodologia

Problemy z optymalizacją

W algorytmu genetycznego, o ludności z rozwiązań kandydujących (zwane jednostki, stworzenia lub fenotypy ) do problemu optymalizacji jest ewoluowały w kierunku lepszych rozwiązań. Każde rozwiązanie kandydujące ma zestaw właściwości (ich chromosomy lub genotyp ), które mogą być zmutowane i zmienione; tradycyjnie rozwiązania są reprezentowane w postaci binarnej jako ciągi zer i jedynek, ale możliwe są również inne kodowania.

Ewolucja zwykle rozpoczyna się od populacji losowo wygenerowanych osobników i jest procesem iteracyjnym , przy czym populacja w każdej iteracji nazywana jest pokoleniem . W każdym pokoleniu oceniana jest sprawność każdego osobnika w populacji; dopasowanie jest zwykle wartością funkcji celu w rozwiązywanym zadaniu optymalizacyjnym. Bardziej dopasowane osobniki są wybierane stochastycznie z obecnej populacji, a genom każdego osobnika jest modyfikowany ( rekombinowany i prawdopodobnie losowo mutowany), aby utworzyć nowe pokolenie. Nowa generacja rozwiązań kandydujących jest następnie wykorzystywana w kolejnej iteracji algorytmu . Zwykle algorytm kończy się, gdy wyprodukowano maksymalną liczbę pokoleń lub osiągnięto zadowalający poziom sprawności dla populacji.

Typowy algorytm genetyczny wymaga:

  1. genetyczny reprezentację w domenie roztworu,
  2. funkcja przydatności do oceny domenę rozwiązanie.

Standardową reprezentacją każdego kandydującego rozwiązania jest tablica bitów (nazywana również bit set lub bit string ). 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 wyrównać ze względu na ich stały rozmiar, co ułatwia proste operacje krzyżowania . Można również stosować reprezentacje o zmiennej długości, ale w tym przypadku implementacja krzyżowania jest bardziej złożona. Reprezentacje drzewiaste są badane w programowaniu genetycznym, a reprezentacje w formie grafów są badane w programowaniu ewolucyjnym ; W programowaniu ekspresji genów badana jest mieszanka zarówno chromosomów liniowych, jak i drzew .

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

Inicjalizacja

Wielkość populacji zależy od charakteru 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ć „zaszczepiane” w obszarach, w których istnieje prawdopodobieństwo znalezienia optymalnych rozwiązań.

Wybór

W każdym kolejnym pokoleniu część istniejącej populacji jest wybierana do rozmnażania nowego pokolenia. Indywidualne rozwiązania są wybierane w procesie opartym na kondycji , w którym zazwyczaj częściej wybierane są rozwiązania dla monterów (mierzone przez funkcję fitness ). 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 przystosowania jest definiowana przez reprezentację genetyczną 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) wskazuje, czy obiekt znajduje się w plecaku. Nie każda taka reprezentacja jest słuszna, ponieważ rozmiary przedmiotów mogą przekraczać pojemność plecaka. Przydatności roztworu jest sumą wartości wszystkich przedmiotów w plecaku czy reprezentacja jest poprawny, lub 0 w przeciwnym przypadku.

W niektórych problemach trudno lub nawet niemożliwe jest zdefiniowanie wyrażenia przystosowania; w takich przypadkach można zastosować symulację do określenia wartości funkcji sprawności fenotypu (np. obliczeniowa dynamika płynów służy do określenia oporu powietrza pojazdu, którego kształt jest zakodowany jako fenotyp), a nawet można wykorzystać interaktywne algorytmy genetyczne .

Operatorzy genetyczni

Następnym krokiem jest wygenerowanie drugiej generacji populacji rozwiązań z tych wybranych przez kombinację operatorów genetycznych : crossover (zwanej również rekombinacją) i mutację .

Dla każdego nowego rozwiązania, które ma zostać wyprodukowane, z wcześniej wybranej puli wybierana jest para rozwiązań „rodzicielskich” do hodowli. Tworząc rozwiązanie „dziecięce” przy użyciu powyższych metod krzyżowania i mutacji, tworzone jest nowe rozwiązanie, które zazwyczaj posiada wiele cech charakterystycznych dla 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 dwóch 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ą powstaniem populacji chromosomów następnej generacji, która różni się od pierwszej generacji. Ogólnie rzecz biorąc, dzięki tej procedurze przeciętna przydatność dla populacji wzrośnie, ponieważ do hodowli wybierane są tylko najlepsze organizmy z pierwszego pokolenia, wraz z niewielkim odsetkiem mniej dopasowanych roztworów. Te mniej dopasowane rozwiązania zapewniają różnorodność genetyczną w obrębie puli genetycznej rodziców, a tym samym zapewniają różnorodność genetyczną kolejnego pokolenia dzieci.

Opinia jest podzielona co do znaczenia krzyżowania w porównaniu z mutacją. Istnieje wiele odniesień w Fogel (2006), które potwierdzają znaczenie wyszukiwania opartego na mutacjach.

Chociaż crossover 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.

Warto dostroić parametry, takie jak prawdopodobieństwo mutacji, prawdopodobieństwo krzyżowania i wielkość populacji, aby znaleźć rozsądne ustawienia dla badanej klasy problemu. Bardzo małe tempo mutacji może prowadzić do dryfu genetycznego (który nie ma charakteru ergodycznego ). Zbyt wysoki współczynnik rekombinacji może prowadzić do przedwczesnej konwergencji algorytmu genetycznego. Zbyt wysoki współczynnik mutacji może prowadzić do utraty dobrych rozwiązań, o ile nie zostanie zastosowana selekcja elitarna . 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 metody heurystyczne, aby obliczenia były szybsze lub bardziej niezawodne. W specjacji karze heurystyczne łączącym między rozwiązań kandydującej, 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, które spełnia minimalne kryteria
  • Osiągnięto stałą 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 poziom plateau, tak że kolejne iteracje nie dają już lepszych wyników
  • Kontrola ręczna
  • Kombinacje powyższych

Hipoteza budulcowa

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

  1. Opis heurystyki, która dokonuje adaptacji poprzez identyfikację i rekombinację „cegiełek budulcowych”, tj. schematów niskiego rzędu, o małej długości definiowania z ponadprzeciętną sprawnością.
  2. Hipoteza, że ​​algorytm genetyczny dokonuje adaptacji poprzez pośrednią i wydajną implementację tej heurystyki.

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

„Krótkie, nisko uporządkowane i wysoce dopasowane schematy są próbkowane, rekombinowane [skrzyżowane] 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 rozwiązań cząstkowych z poprzednich sampli.
„Ponieważ wysoce dopasowane schematy o małej długości i niskim porządku odgrywają tak ważną rolę w działaniu algorytmów genetycznych, nadaliśmy im już specjalną nazwę: cegiełki. Tak jak dziecko tworzy wspaniałe twierdze poprzez układanie prostych bloków drewno, tak samo algorytm genetyczny dąży do osiągnięcia niemal optymalnej wydajności poprzez zestawienie krótkich, niskorzę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 na przestrzeni lat. Zaproponowano na przykład wiele algorytmów estymacji rozkładu , próbując zapewnić środowisko, w którym hipoteza będzie słuszna. Chociaż w niektórych klasach problemów zgłoszono dobre wyniki, sceptycyzm dotyczący ogólności i/lub praktyczności hipotezy bloku budulcowego jako wyjaśnienia wydajności GA nadal pozostaje. Rzeczywiście, istnieje rozsądna ilość pracy, która próbuje zrozumieć jego ograniczenia z perspektywy estymacji algorytmów dystrybucji.

Ograniczenia

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

  • Wielokrotna ocena funkcji sprawności dla złożonych problemów jest często najbardziej hamującym 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 sprawności . 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żonego dopasowania, które jest wydajne obliczeniowo. Oczywiste jest, że połączenie modeli przybliżonych może być jednym z najbardziej obiecujących podejść do przekonującego wykorzystania GA do rozwiązywania złożonych problemów rzeczywistych.
  • 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 ​​niezwykle trudno jest zastosować technikę w takich problemach, jak projektowanie silnika, domu czy samolotu. Aby takie problemy można było poddać poszukiwaniom ewolucyjnym, należy je rozłożyć na możliwie najprostszą reprezentację. Dlatego zwykle widzimy algorytmy ewolucyjne kodujące projekty łopatek wentylatora zamiast silników, kształty budynków zamiast szczegółowych planów konstrukcyjnych i profile lotnicze zamiast projektów całych samolotów. Drugim problemem złożoności jest kwestia ochrony części, które wyewoluowały, aby reprezentować dobre rozwiązania, przed dalszymi destrukcyjnymi mutacjami, szczególnie gdy ich ocena sprawności wymaga, aby dobrze łączyły się z innymi częściami.
  • „Lepsze” rozwiązanie jest tylko w porównaniu 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 arbitralnych 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 zależy od kształtu krajobrazu sprawności : niektóre problemy mogą ułatwiać podejście do globalnego optimum, inne mogą ułatwiać funkcji odnalezienie lokalnego optima. Problem ten można złagodzić, stosując inną funkcję przystosowania, 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ą utrzymania różnorodności jest nałożenie „kary niszowej”, w 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, pozwalając na inne (mniej podobne ) osobniki, które mają zostać utrzymane 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 programowaniu genetycznym ), ponieważ przekroczenie jednorodnej populacji nie daje nowych rozwiązań. W strategiach ewolucyjnych i programowaniu ewolucyjnym różnorodność nie jest niezbędna ze względu na większe uzależnienie od mutacji.
  • Operowanie na dynamicznych zestawach danych jest trudne, ponieważ genomy zaczynają wcześnie zbliżać się do rozwiązań, które mogą nie mieć już zastosowania dla późniejszych danych. Zaproponowano kilka metod, aby temu zaradzić poprzez zwiększenie różnorodności genetycznej i zapobieganie wczesnej konwergencji, albo poprzez zwiększenie prawdopodobieństwa mutacji, gdy jakość rozwiązania spada (tzw. wyzwalana hipermutacja ), albo przez okazjonalne wprowadzanie zupełnie nowych, losowo generowanych elementów do puli genów (nazywani przypadkowymi imigrantami ). Ponownie, strategie ewolucyjne i programowanie ewolucyjne można wdrażać za pomocą tak zwanej „strategii przecinkowej”, w której rodzice nie są utrzymywani, a nowi rodzice są wybierani 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/niewłaściwa (jak problemy decyzyjne ), ponieważ nie ma sposobu na osiągnięcie zbieżności w rozwiązaniu (brak wzniesienia do pokonania). W takich przypadkach wyszukiwanie losowe 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 instancji problemów inne algorytmy optymalizacji mogą być bardziej wydajne niż algorytmy genetyczne pod względem szybkości zbieżności. Alternatywnym i algorytmy uzupełniających obejmują strategii ewolucji , programowanie ewolucyjny , symulowaną denaturację , Gaussa adaptacji , gradientowe i rój inteligencji (np mrówka optymalizacji kolonii , optymalizacji cząstek rój ) oraz metody oparte na całkowitej programowania liniowego . 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

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ściach rzeczywistych, ale w rzeczywistości jest ono mylące, ponieważ tak naprawdę nie reprezentuje teorii bloków konstrukcyjnych zaproponowanej przez Johna Henry'ego Hollanda w latach 70. XX wieku. Ta teoria nie jest jednak pozbawiona poparcia, opartego na wynikach teoretycznych i eksperymentalnych (patrz poniżej). Podstawowy algorytm wykonuje crossover i mutację na poziomie bitowym. Inne warianty traktują chromosom jako listę liczb, które są indeksami w tablicy instrukcji, węzłami w połączonej liście , haszami , obiektami lub jakąkolwiek inną wyobrażalną strukturą danych . Krzyżowanie i mutacje są wykonywane tak, aby respektować granice elementów danych. Dla większości typów danych można zaprojektować określone operatory wariacji. Różne typy danych chromosomowych wydają się działać lepiej lub gorzej dla różnych specyficznych domen problemowych.

Gdy używane są reprezentacje liczb całkowitych w postaci ciągu bitowego, często stosuje się kodowanie Graya . W ten sposób na małe zmiany liczby całkowitej można łatwo wpływać przez mutacje lub krzyżówki. 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 zaskoczyło badaczy, że dobre wyniki uzyskano przy użyciu chromosomów o wartościach rzeczywistych. Wyjaśniono to jako zbiór rzeczywistych wartości w skończonej populacji chromosomów tworzących wirtualny alfabet (gdy dominuje selekcja i rekombinacja) o znacznie niższej kardynalności niż można by oczekiwać od reprezentacji zmiennoprzecinkowej.

Rozszerzenie dostępnej domeny problemowej algorytmu genetycznego można uzyskać poprzez bardziej złożone kodowanie puli rozwiązań przez 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 strojenia regulatora struktura regulatora pętli wewnętrznej może należeć do konwencjonalnego regulatora trzech parametrów, podczas gdy pętla zewnętrzna może implementować regulator językowy (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 po przekroju i jest użytecznym narzędziem do modelowania i symulacji złożonych systemów adaptacyjnych, zwłaszcza procesów ewolucyjnych.

Elitaryzm

Praktycznym wariantem ogólnego procesu konstruowania nowej populacji jest umożliwienie najlepszemu organizmowi (organizmom) z obecnego pokolenia, aby przeniósł się do następnego, w niezmienionej formie. Ta strategia jest znana jako selekcja elitarna i gwarantuje, że jakość rozwiązania uzyskanego przez GA nie spadnie z pokolenia na pokolenie.

Wdrożenia równoległe

Równoległe implementacje algorytmów genetycznych występują w dwóch odmianach. Gruboziarniste równoległe algorytmy genetyczne zakładają populację na każdym z węzłów komputerowych i migrację osobników między węzłami. Drobnoziarniste równoległe algorytmy genetyczne zakładają jednostkę na każdym węźle procesora, która współpracuje z sąsiednimi osobnikami w celu selekcji i reprodukcji. Inne warianty, takie jak algorytmy genetyczne dla problemów optymalizacji online , wprowadzają zależność czasową lub szum w funkcji sprawności.

Adaptacyjne GA

Algorytmy genetyczne z parametrami adaptacyjnymi (adaptacyjne algorytmy genetyczne, AGA) to kolejny znaczący i obiecujący wariant algorytmów genetycznych. Prawdopodobieństwo krzyżowania (pc) i mutacji (pm) w dużym stopniu determinuje stopień dokładności rozwiązania i szybkość zbieżności, jaką mogą uzyskać algorytmy genetyczne. 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, a także utrzymania zdolności do konwergencji. W AGA (adaptacyjny algorytm genetyczny) dopasowanie pc i pm zależy od wartości dopasowania rozwiązań. W CAGA (adaptacyjny algorytm genetyczny oparty na klastrach), poprzez wykorzystanie analizy skupień do oceny stanów optymalizacji populacji, dostosowanie pc i pm zależy od tych stanów optymalizacji. Połączenie GA z innymi metodami optymalizacji może być całkiem skuteczne. GA wydaje się być całkiem dobra w znajdowaniu ogólnie dobrych rozwiązań globalnych, ale dość nieefektywna 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 wspinanie się na wzniesieniach i GA może poprawić wydajność GA, jednocześnie przezwyciężając brak solidności wspinania się na wzniesienia.

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 po sobie – krzyżowanie może sumować liczbę kroków z DNA matki dodając liczbę kroków z DNA ojcowskiego i tak dalej. To jest jak dodawanie wektorów, które najprawdopodobniej mogą podążać wzdłuż grzbietu w krajobrazie fenotypowym. W ten sposób wydajność procesu można zwiększyć o wiele rzędów wielkości. Co więcej, operator inwersji ma możliwość umieszczenia stopni w kolejności następującej po sobie lub innej odpowiedniej kolejności na korzyść przetrwania lub wydajności.

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

Opracowano wiele odmian, aby spróbować poprawić wydajność GA w problemach z wysokim stopniem dopasowania epistazy, tj. gdzie dopasowanie rozwiązania składa się z oddziałujących podzbiorów jego zmiennych. Takie algorytmy mają na celu poznanie (przed wykorzystaniem) tych korzystnych interakcji fenotypowych. Jako takie, są one zgodne z Hipotezą Bloków Budowlanych w adaptacyjnej redukcji destrukcyjnej rekombinacji. Wybitne przykłady tego podejścia obejmują mGA, GEMGA i LLGA.

Domeny problemowe

Problemy, które wydają się być szczególnie odpowiednie dla roztworu za pomocą algorytmów genetycznych obejmują rozkładów jazdy i problemy planowania i wiele pakietów oprogramowania planowania są oparte na gazie. Gazy gazowe 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 problematycznych domenach, które mają złożony krajobraz sprawnościowy, ponieważ mieszanie, tj. mutacja w połączeniu z crossoverem , ma na celu odsunięcie populacji od lokalnego optymizmu , w którym tradycyjny algorytm wspinaczki może utknąć c. Zauważ, że powszechnie stosowane operatory krzyżowania nie mogą zmienić żadnej jednolitej 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 zaprojektowane do odbierania sygnałów radiowych w kosmosie, metody chodzenia dla figur komputerowych, optymalne projektowanie ciał aerodynamicznych w złożonych polach przepływu

W swoim podręczniku Algorytmów , Skiena odradza algorytmów genetycznych dla każdego zadania:

[I]nienaturalne jest modelowanie aplikacji pod kątem operatorów genetycznych, takich jak mutacje 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 zajmują bardzo dużo czasu w przypadku nietrywialnych problemów. [...] Analogia do ewolucji – gdzie znaczny postęp wymaga [sic] milionów lat – może być całkiem odpowiednia.

[...]

Nigdy nie spotkałem się z żadnym problemem, w którym algorytmy genetyczne wydawały mi się właściwym sposobem na zaatakowanie tego. 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 swoich potrzeb heurystycznego wyszukiwania voodoo.

—  Steven Skiena

Historia

W 1950 roku Alan Turing zaproponował „uczącą się maszynę”, która byłaby paralelna z zasadami ewolucji. Komputerowa symulacja ewolucji rozpoczęła się już w 1954 roku dzięki pracy Nilsa Aalla Barricelli , który korzystał z komputera w Institute for Advanced Study w Princeton, New Jersey . Jego publikacja z 1954 r. nie została powszechnie zauważona. Począwszy od 1957 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ł w latach 60. serię artykułów, w których również przyjęto populację rozwiązań problemów optymalizacji, przechodzącą rekombinację, mutację i selekcję. Badania Bremermanna obejmowały również elementy nowoczesnych algorytmów genetycznych. Innymi godnymi uwagi pionierami z wczesnego okresu są Richard Friedberg, George Friedman i Michael Conrad. Wiele wczesnych prac jest przedrukowywanych przez Fogela (1998).

Chociaż Barricelli w swojej pracy, którą przedstawił w 1963 roku, 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. i na początku XX wieku. Lata 70. – grupa Rechenberga była w stanie rozwiązywać złożone problemy inżynieryjne poprzez strategie ewolucyjne . Innym podejściem była ewolucyjna technika programowania Lawrence'a J. Fogela , która została zaproponowana do generowania sztucznej inteligencji. Programowanie ewolucyjne pierwotnie wykorzystywało automaty skończone do przewidywania środowisk, a także wykorzystywało zmienność i selekcję do optymalizacji logiki predykcyjnej. Algorytmy genetyczne stały się popularne w szczególności dzięki pracom Johna Hollanda we wczesnych latach 70., a zwłaszcza jego książce Adaptacja w systemach naturalnych i sztucznych (1975). Jego praca wywodzi się z badań nad automatami komórkowymi , prowadzonych przez Hollanda i jego studentów na Uniwersytecie Michigan . Holland wprowadził sformalizowany model do przewidywania jakości następnej generacji, znany jako Twierdzenie o Schemacie Hollanda . Badania nad GA pozostawały w dużej mierze teoretyczne do połowy lat 80., kiedy w Pittsburghu w Pensylwanii odbyła się Pierwsza Międzynarodowa Konferencja na temat Algorytmów Genetycznych .

Produkty komercyjne

Pod koniec lat 80. firma General Electric rozpoczęła sprzedaż pierwszego na świecie produktu w postaci algorytmu genetycznego, zestawu narzędzi opartego na komputerach mainframe, przeznaczonego do procesów przemysłowych. W 1989 roku firma Axcelis, Inc. wydała Evolver , pierwszy na świecie komercyjny produkt GA dla komputerów stacjonarnych. John Markoff, autor technologii New York Times , pisał o Evolverze w 1990 roku i do 1995 roku pozostał on jedynym interaktywnym komercyjnym algorytmem genetycznym. Evolver został sprzedany firmie Palisade w 1997 roku, przetłumaczony na kilka języków i jest obecnie w szóstej wersji. Od lat 90. MATLAB zbudował trzy algorytmy heurystyczne optymalizacji bez pochodnych (symulowane wyżarzanie, optymalizacja roju cząstek, algorytm genetyczny) oraz dwa algorytmy wyszukiwania bezpośredniego (przeszukiwanie proste, wyszukiwanie wzorców).

Powiązane techniki

Pola nadrzędne

Algorytmy genetyczne to poddziedzina:

Pola pokrewne

Algorytmy ewolucyjne

Algorytmy ewolucyjne to poddziedzina obliczeń ewolucyjnych .

  • Strategie ewolucji (ES, patrz Rechenberg, 1994) ewoluują osobniki za pomocą mutacji i pośredniej lub dyskretnej rekombinacji. Algorytmy ES są zaprojektowane specjalnie 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 mutacją i selekcją oraz arbitralnymi reprezentacjami. Wykorzystują samoadaptację do dostosowania parametrów i mogą obejmować inne operacje wariacyjne, takie jak łączenie informacji od wielu rodziców.
  • Estimation of Distribution Algorithm (EDA) zastępuje tradycyjne operatory reprodukcji operatorami opartymi na modelu. Takie modele są uczone od populacji poprzez zastosowanie technik uczenia maszynowego i reprezentowane jako probabilistyczne modele graficzne, z których można próbować nowe rozwiązania lub generować je z krzyżowania kierowanego.
  • 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 oparty na drzewie wewnętrznej struktury danych do reprezentowania programy komputerowe do adaptacji zamiast z lista struktur typowych algorytmów genetycznych. Istnieje wiele wariantów genetycznych, w tym programowania kartezjańskiej programowania genetycznego , programowanie ekspresji genów , gramatyczna Evolution , Linear programowania genetycznego , wypowiedzi multi programowania itp
  • Grupujący algorytm genetyczny (GGA) jest ewolucją GA, w której punkt ciężkości przesuwa się z pojedynczych pozycji, jak w klasycznych GA, na grupy lub podzbiory pozycji. Ideą tej ewolucji GA zaproponowaną przez Emanuela Falkenauera jest to, że rozwiązywanie niektórych złożonych problemów, czyli problemów z grupowaniem lub partycjonowaniem , gdzie zestaw elementów musi być podzielony na rozłączną grupę elementów w optymalny sposób, byłoby lepiej osiągnięte poprzez tworzenie charakterystyk grup przedmiotów równoważnych genom. Tego rodzaju problemy obejmują pakowanie pojemników , równoważenie linii, grupowanie w odniesieniu do miary odległości, równe stosy itp., na których klasyczne GA okazały się kiepskie. Uczynienie genów równoważnymi grupom implikuje chromosomy, które są ogólnie różnej długości i specjalne operatory genetyczne, które manipulują całymi grupami elementów. W szczególności w przypadku pakowania bin, GGA zhybrydyzowane z Kryterium Dominacji Martello i Totha jest prawdopodobnie najlepszą techniką do tej pory.
  • Interaktywne algorytmy ewolucyjne to algorytmy ewolucyjne, które wykorzystują ludzką ocenę. Są one zwykle stosowane w dziedzinach, w których trudno jest zaprojektować funkcję sprawności obliczeniowej, na przykład ewoluujące obrazy, muzyka, projekty artystyczne i formy dopasowane do preferencji estetycznych użytkowników.

Inteligencja roju

Inteligencja roju jest poddziedziną 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 obszarów produktywnych lokalnie.
  • Chociaż jest uważany za algorytm szacowania rozkładu , optymalizacja roju cząstek (PSO) jest metodą obliczeniową 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 najbardziej znana pozycja, jak i najbardziej znana globalna pozycja roju. Podobnie jak algorytmy genetyczne, metoda PSO polega na dzieleniu się informacjami wśród członków populacji. W niektórych problemach PSO jest często bardziej wydajny obliczeniowo niż GA, zwłaszcza w nieograniczonych problemach ze zmiennymi ciągłymi.

Algorytmy ewolucyjne połączone z inteligencją roju

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 podlegają również lokalnym fazom doskonalenia. Idea algorytmów memetycznych pochodzi od memów , które w przeciwieństwie do genów potrafią się dostosowywać. W niektórych obszarach problemowych okazuje się, że są one bardziej wydajne niż tradycyjne algorytmy ewolucyjne.
  • Algorytmy bakteriologiczne (BA) inspirowane ekologią ewolucyjną, a dokładniej adaptacją bakteriologiczną. Ekologia ewolucyjna to nauka o żywych organizmach w kontekście ich środowiska w celu odkrycia, w jaki sposób się przystosowują. Jego podstawową koncepcją jest to, że w heterogenicznym środowisku nie ma jednej osoby pasującej 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 z pozycjonowaniem (anteny do telefonów komórkowych, urbanistyka itd.) lub 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 (DS) inspirowana migracją superorganizmów.
  • Adaptacja Gaussa (normalna lub naturalna adaptacja, w skrócie NA, aby uniknąć pomyłki z GA) ma na celu maksymalizację wydajności produkcyjnej systemów przetwarzania sygnału. Może być również używany do zwykłej optymalizacji parametrycznej. Opiera się na pewnym twierdzeniu ważnym dla wszystkich obszarów akceptowalności i wszystkich rozkładów Gaussa. Wydajność NA opiera się na teorii informacji i pewnym twierdzeniu o wydajności. Jego efektywność jest definiowana jako informacja podzielona przez pracę potrzebną do uzyskania informacji. Ponieważ NA maksymalizuje średnią kondycję, a nie kondycję jednostki, krajobraz jest wygładzony tak, że doliny między szczytami mogą zniknąć. Dlatego ma pewną „ambicję” unikania lokalnych szczytów w krajobrazie fitness. NA jest również dobry we wspinaniu się po ostrych szczytach poprzez adaptację macierzy momentów, ponieważ NA może maksymalizować zaburzenie ( średnia informacja ) Gaussa, jednocześnie utrzymując średnią sprawność na stałym poziomie.

Inne metody metaheurystyczne

Metody metaheurystyczne w szerokim zakresie zaliczają się do stochastycznych metod optymalizacji.

  • Symulowane wyżarzanie (SA) to powiązana globalna technika optymalizacji, która przemierza przestrzeń poszukiwań, testując losowe mutacje w indywidualnym rozwiązaniu. Zawsze akceptowana jest mutacja zwiększająca sprawność. Mutacja obniżająca dopasowanie jest akceptowana probabilistycznie na podstawie różnicy w sprawności i malejącego parametru temperatury. W mowie SA mówi się o poszukiwaniu najniższej energii zamiast maksymalnej sprawności. SA można również użyć w ramach standardowego algorytmu GA, zaczynając od stosunkowo wysokiego wskaźnika mutacji i zmniejszając go w czasie zgodnie z określonym harmonogramem.
  • Wyszukiwanie tabu (TS) jest podobne do symulowanego wyżarzania, ponieważ oba przechodzą przez przestrzeń rozwiązania, testując mutacje pojedynczego 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 rozwiązań częściowych lub kompletnych. Zabronione jest przechodzenie do rozwiązania, które zawiera elementy listy tabu, która jest aktualizowana w miarę przechodzenia rozwiązania przez przestrzeń rozwiązań.
  • Optymalizacja ekstremalna (EO) W przeciwieństwie do GA, które działają z populacją potencjalnych rozwiązań, EO rozwija jedno rozwiązanie i wprowadza lokalne modyfikacje najgorszych składników. Wymaga to wybrania odpowiedniej reprezentacji, która pozwala na przypisanie poszczególnym składnikom rozwiązania miary jakości ("fitness"). Naczelną zasadą tego algorytmu jest wyłaniające się doskonalenie poprzez selektywne usuwanie komponentów niskiej jakości i zastępowanie ich komponentami wybranymi losowo. Jest to zdecydowanie sprzeczne z GA, który wybiera dobre rozwiązania, próbując stworzyć lepsze rozwiązania.

Inne metody optymalizacji stochastycznej

  • Metoda entropii krzyżowej (CE) generuje kandydujące rozwiązania za pomocą sparametryzowanego rozkładu prawdopodobieństwa. Parametry są aktualizowane poprzez minimalizację entropii krzyżowej, aby generować lepsze próbki w następnej iteracji.
  • Optymalizacja wyszukiwania reaktywnego (RSO) opowiada się za integracją podsymbolicznych technik uczenia maszynowego z heurystyką 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 samostrojenia krytycznych parametrów. Metodologie zainteresowania Reactive wyszukiwania obejmują uczenia maszynowego i statystyk, w szczególności nauki zbrojenia , aktywnego uczenia się lub zapytań , sieci neuronowych i metaheurystyk .

Zobacz też

Bibliografia

Bibliografia

Zewnętrzne linki

Zasoby

Poradniki