W dziedzinie sztucznej inteligencji algorytm ewolucyjny (EA) jest podzbiorem obliczeń całkowitej populacji opartych na optymalizacji metaheurystycznej. EA wykorzystuje mechanizmy inspirowane rozwojem biologicznym, takie jak reprodukcja, mutacja, rekombinacja i selekcja. Kandydujące rozwiązanie problemu ewolucyjnych algorytmów optymalizacji pełni rolę jednostek w populacji. A także funkcja fitness określa jakość odpowiedzi.
Algorytmy ewolucyjne często dobrze przybliżają rozwiązania wszystkich rodzajów problemów. Ponieważ najlepiej byłoby, gdyby nie robili żadnych założeń dotyczących podstawowego krajobrazu fitness. Metody wykorzystywane do modelowania ewolucyjnego i algorytmów genetycznych są zwykle ograniczone do badań procesów mikroewolucyjnych i modeli planowania opartych na etapach komórkowych. W większości rzeczywistych aplikacji EA złożoność obliczeniowa jest czynnikiem zaporowym.
Właściwieproblem ten związany jest z estymacją funkcji sprawności. Przybliżenie sprawności jest jednym ze sposobów przezwyciężenia tej trudności. Jednak pozornie prosty EA może rozwiązać często złożone problemy. Dlatego nie może być bezpośredniego związku między złożonością sekwencji a problemem. Więcej szczegółów można znaleźć w książkach „Algorytmy ewolucyjne”.
Wdrożenie
Pierwszy krok to losowe utworzenie początkowej populacji osobników.
Krok drugi to ocena przydatności każdej osoby w tej grupie (limit czasu, wystarczające przygotowanie itp.).
Krok trzeci - powtórz następujące kroki regeneracji do końca:
- Wybierz najbardziej odpowiednich ludzi do hodowli (rodziców).
- Przyprowadź nowe osobniki, które przeszły algorytm ewolucyjny, używając krzyżowania i mutacji, aby uzyskać potomstwo.
- Oceń indywidualną kondycję nowych ludzi.
- Zastąp nimi najmniej pasującą populację.
Typy
Algorytm genetyczny to sekwencja ewolucyjna, najpopularniejszy rodzaj Expert Advisor. Rozwiązanie problemu poszukuje się w postaci ciągów liczb (tradycyjnie binarnych, chociaż zwykle najlepsze reprezentacje to te, które bardziej odzwierciedlają rozwiązywany problem) przez zastosowanie operatorów takich jak rekombinacja i mutacja (czasem jeden, w niektórych przypadkach oba). Ten rodzaj Expert Advisor jest często używany w problemach optymalizacyjnych. Inną nazwą na to jest fetura (z łaciny „narodziny”):
- Programowanie genetyczne. Przedstawia rozwiązania jako kody komputerowe, a ich przydatność określa zdolność do wykonywania zadań obliczeniowych.
- Programowanie ewolucyjne. Podobny do ewolucyjnego algorytmu genetycznego, ale struktura jest stała, a jej parametry liczbowe mogą się zmieniać.
- Programowanie ekspresji genów. Tworzy aplikacje komputerowe, ale bada system genotyp-fenotyp, w którym projekty o różnych rozmiarach są kodowane na liniowych chromosomach o stałej długości.
- Strategia. Pracuje z wektorami liczb rzeczywistych jako reprezentacjami rozwiązań. Zwykle używa samodostosowujących się algorytmów ewolucyjnych szybkości mutacji.
- Rozwój różnicowy. Oparte na różnicach wektorów i dlatego nadaje się przede wszystkim do rozwiązywania problemów optymalizacji numerycznej.
- Neuroewolucja. Podobny do programowania ewolucyjnego i algorytmów genetycznych. Ale te ostatnie to sztuczne sieci neuronowe, opisujące strukturę i wagę połączeń. Kodowanie genomu może być bezpośrednie lub pośrednie.
Porównanie z procesami biologicznymi
Możliwym ograniczeniem wielu algorytmów ewolucyjnych jest brak wyraźnego rozróżnienia między genotypem a fenotypem. W naturze zapłodnione jajo przechodzi złożony proces zwany embriogenezą, aby stać się dojrzałym. Uważa się, że to pośrednie kodowanie zwiększa wiarygodność poszukiwań genetycznych (tj. zmniejsza prawdopodobieństwo spowodowania śmiertelnych mutacji) i może również poprawić zdolność organizmu do rozwoju. Takie pośrednie (innymi słowy,kodowania generatywne lub rozwojowe) pozwalają również ewolucji na wykorzystanie regularności w środowisku.
Niedawne prace nad sztuczną embriogenezą lub systemami rozwojowymi mają na celu rozwiązanie tych problemów. Podczas programowania ekspresji genów z powodzeniem bada się region genotyp-fenotyp, gdzie pierwszy składa się z liniowych wielogenowych chromosomów o stałej długości, a drugi z wielu drzew ekspresji lub programów komputerowych o różnych rozmiarach i kształtach.
Powiązane techniki
Algorytmy obejmują:
- Optymalizacja kolonii mrówek. Opiera się na założeniu, że owady poszukują pożywienia, łącząc się z feromonami, tworząc ścieżki. Nadaje się przede wszystkim do optymalizacji kombinatorycznej i problemów z wykresami.
- Algorytm suwaka głównego. Twórca zainspirował się funkcją korzeni roślin w przyrodzie.
- Algorytm dla sztucznych kolonii pszczół. Na podstawie zachowania pszczół miodnych. Jest on głównie proponowany do optymalizacji numerycznej i rozszerzony do rozwiązywania problemów kombinatorycznych, ograniczonych i wielokryterialnych. Algorytm pszczół opiera się na zachowaniu żerowania owadów. Został zastosowany w wielu aplikacjach, takich jak routing i planowanie.
- Optymalizacja roju cząstek - oparta na pomysłach na zachowanie stada zwierząt. A także nadaje się przede wszystkim do zadań związanych z procesami numerycznymi.
Inne popularne metody metaheurystyczne
- Wyszukiwanie polowań. Metoda polegająca na grupowym łapaniu określonych zwierząt, np. wilków, które:rozdzielają swoje obowiązki, aby otoczyć zdobycz. Każdy z członków algorytmu ewolucyjnego w jakiś sposób odnosi się do pozostałych. Dotyczy to zwłaszcza lidera. Jest to metoda ciągłej optymalizacji zaadaptowana jako metoda procesu kombinatorycznego.
- Wyszukaj według pomiarów. W przeciwieństwie do metod metaheurystycznych opartych na przyrodzie, algorytm procesu adaptacyjnego nie wykorzystuje metafory jako głównej zasady. Zamiast tego wykorzystuje prostą metodę zorientowaną na wydajność, opartą na aktualizowaniu parametru współczynnika wymiaru wyszukiwania w każdej iteracji. Algorytm Firefly jest inspirowany tym, jak świetliki przyciągają się nawzajem swoim migającym światłem. Jest to szczególnie przydatne przy optymalizacji multimodalnej.
- Szukaj harmonii. Oparte na wyobrażeniach zachowania muzyków. W tym przypadku algorytmy ewolucyjne są drogą do optymalizacji kombinatorycznej.
- Adaptacja Gaussa. Oparte na teorii informacji. Służy do maksymalizacji wydajności i średniej dostępności. Przykład algorytmów ewolucyjnych w tej sytuacji: entropia w termodynamice i teorii informacji.
Memetic
Hybrydowa metoda oparta na pomyśle Richarda Dawkinsa na mem. Zwykle przybiera formę algorytmu populacyjnego połączonego z indywidualnymi procedurami uczenia się zdolnymi do wykonywania lokalnych udoskonaleń. Kładzie nacisk na wykorzystanie wiedzy dotyczącej konkretnego problemu i próby organizowania szczegółowych i globalnych wyszukiwań w sposób synergiczny.
Ewolucyjnyalgorytmy to heurystyczne podejście do problemów, których nie można łatwo rozwiązać w czasie wielomianowym, takich jak klasycznie NP-trudne problemy i wszystko inne, czego wyczerpujące przetwarzanie zajęłoby zbyt dużo czasu. Kiedy są używane niezależnie, są zwykle używane do problemów kombinatorycznych. Jednak algorytmy genetyczne są często używane w połączeniu z innymi metodami, stanowiąc szybki sposób na znalezienie wielu optymalnych miejsc początkowych do pracy.
Założenie algorytmu ewolucyjnego (zwanego doradcą) jest dość proste, biorąc pod uwagę, że znasz proces doboru naturalnego. Zawiera cztery główne kroki:
- inicjalizacja;
- wybór;
- operatory genetyczne;
- koniec.
Każdy z tych kroków w przybliżeniu odpowiada pewnemu aspektowi doboru naturalnego i zapewnia łatwe sposoby modularyzacji tej kategorii algorytmów. Mówiąc najprościej, w EA najlepsi członkowie przetrwają i rozmnażają się, podczas gdy niesprawni członkowie umrą i nie wniosą wkładu do puli genów następnego pokolenia.
Inicjalizacja
Aby uruchomić algorytm, musisz najpierw stworzyć zestaw rozwiązań. Populacja będzie zawierać dowolną liczbę możliwych stwierdzeń problemowych, często określanych jako członkowie. Często są one generowane losowo (w ramach ograniczeń zadania) lub, jeśli znana jest wcześniejsza wiedza, wstępnie skoncentrowane wokół tego, co jest uważane za idealne. Ważne jest, aby populacja obejmowała szeroki wachlarz rozwiązań,ponieważ jest to zasadniczo pula genów. Dlatego, jeśli ktoś chce zbadać wiele różnych możliwości w ramach algorytmu, powinien dążyć do posiadania wielu różnych genów.
Wybór
Po utworzeniu populacji jej członkowie muszą być teraz oceniani zgodnie z funkcją sprawności. Funkcja sprawności uwzględnia cechy członka i podaje liczbową reprezentację jego sprawności. Ich tworzenie może być często bardzo trudne. Ważne jest, aby znaleźć dobry system, który dokładnie przedstawia dane. Jest to bardzo specyficzne dla problemu. Teraz konieczne jest obliczenie przydatności wszystkich uczestników i wybranie kilku najlepszych członków.
Funkcje wielu celów
EA można również rozszerzyć, aby korzystać z tych systemów. To nieco komplikuje proces, ponieważ zamiast identyfikować jeden optymalny punkt, przy ich użyciu uzyskuje się zbiór. Zbiór rozwiązań nosi nazwę granicy Pareto i zawiera elementy, które są równie odpowiednie w tym sensie, że żadne z nich nie dominuje nad innymi.
Operatory genetyczne
Ten krok obejmuje dwa podetapy: crossover i mutację. Po wybraniu najlepszych terminów (zazwyczaj 2 najlepsze, ale liczba ta może się różnić), są one teraz wykorzystywane do tworzenia kolejnej generacji algorytmu. Stosując cechy wybranych rodziców, powstają nowe dzieci, które są mieszanką cech. Często może to być trudne w zależności od rodzaju danych, ale zwykle w przypadku problemów kombinatorycznychcałkiem możliwe jest mieszanie i wyprowadzanie prawidłowych kombinacji.
Teraz konieczne jest wprowadzenie do pokolenia nowego materiału genetycznego. Jeśli ten ważny krok nie zostanie wykonany, naukowiec bardzo szybko utknie w lokalnych skrajnościach i nie uzyska optymalnych wyników. Ten krok jest mutacją i jest wykonywany po prostu, zmieniając niewielką część dzieci w taki sposób, że przeważnie nie odzwierciedlają one podzbiorów genów rodziców. Mutacja zwykle pojawia się probabilistycznie, ponieważ prawdopodobieństwo, że dziecko ją dostanie, a także jej nasilenie zależy od rozkładu.
Rozwiązanie
Ostatecznie algorytm musi się zakończyć. Zwykle dzieje się tak w dwóch przypadkach: albo osiągnął maksymalny czas wykonania, albo osiągnął próg wydajności. W tym momencie ostateczne rozwiązanie jest wybierane i zwracane.
Przykład algorytmów ewolucyjnych
Teraz, aby zilustrować wynik tego procesu, musisz zobaczyć doradcę w działaniu. W tym celu możemy przypomnieć, jak kilka pokoleń dinozaurów nauczyło się chodzić (stopniowo opanowywać teren), optymalizować budowę ciała i przykładać siłę mięśni. Mimo że gady wczesnej generacji nie mogły chodzić, doradca był w stanie wyewoluować je z biegiem czasu poprzez mutacje i krzyżowanie do formy zdolnej do chodzenia.
Te algorytmy stają się coraz bardziej istotne we współczesnym świecie, ponieważ oparte na nich rozwiązania są coraz częściej wykorzystywane w branżach takich jak marketing cyfrowy, finanse iopieka zdrowotna.
Gdzie są używane EA?
W szerszym ujęciu, algorytmy ewolucyjne są wykorzystywane w wielu różnych zastosowaniach, takich jak przetwarzanie obrazu, wyznaczanie tras pojazdów, optymalizacja komunikacji mobilnej, tworzenie oprogramowania, a nawet uczenie sztucznych sieci neuronowych. Narzędzia te są podstawą wielu aplikacji i witryn internetowych, z których ludzie korzystają na co dzień, w tym Map Google, a nawet gier, takich jak The Sims. Ponadto medycyna wykorzystuje EA do podejmowania decyzji klinicznych dotyczących leczenia raka. W rzeczywistości algorytmy ewolucyjne są tak niezawodne, że można ich użyć do rozwiązania prawie każdego problemu optymalizacyjnego.
Prawo Moore'a
Rosnąca popularność EO jest napędzana przez dwa główne czynniki: dostępną moc obliczeniową i akumulację dużych zbiorów danych. Pierwsza może być opisana przez prawo Moore'a, które zasadniczo stwierdza, że ilość mocy obliczeniowej w komputerze podwaja się mniej więcej co dwa lata. Ta przepowiednia utrzymuje się od dziesięcioleci. Drugi czynnik związany jest z coraz większym uzależnieniem od technologii, która pozwala instytucjom na gromadzenie niewiarygodnie dużej ilości danych, co pozwala analizować trendy i optymalizować produkty.
W jaki sposób algorytmy ewolucyjne mogą pomóc marketerom?
Warunki rynkowe szybko się zmieniają i są bardzo konkurencyjne. Zmusiło to menedżerów marketingu do konkurowania o lepsze podejmowanie decyzji. Zwiększenie dostępnychmoc obliczeniowa skłoniła pracowników do korzystania z EA do rozwiązywania problemów.
Optymalizacja konwersji
Jednym z głównych celów jest zwiększenie liczby odwiedzających witrynę. Problem ten sprowadza się do optymalizacji liczby użytkowników, którzy robią to, czego chce marketer. Na przykład, jeśli firma sprzedaje laptopy, idealnym rozwiązaniem jest zwiększenie liczby odwiedzających witrynę, którzy ostatecznie kupują produkt. To jest istota optymalizacji współczynnika konwersji.
Jednym z zaskakująco ważnych aspektów jest wybór interfejsu użytkownika. Jeśli projekt strony internetowej nie jest zbyt przyjazny dla użytkownika, są tacy, którzy w końcu nie kupują produktu z tego czy innego powodu. Celem jest zatem zmniejszenie liczby użytkowników, którzy nie dokonają konwersji, co zwiększa ogólny zysk.
