Obliczenia ewolucyjne - Evolutionary computation
Część serii na |
Biologia ewolucyjna |
---|
W informatyce , obliczeń ewolucyjnych to rodzina algorytmów do optymalizacji globalnej zainspirowany ewolucji biologicznej i podpolu o sztucznej inteligencji i Soft Computing Badając te algorytmy. Pod względem technicznym są to rodzina populacyjnych metod rozwiązywania problemów metodą prób i błędów o metaheurystycznym lub stochastycznym charakterze optymalizacji .
W obliczeniach ewolucyjnych generowany jest początkowy zestaw rozwiązań kandydujących i iteracyjnie aktualizowany. Każda nowa generacja jest wytwarzana poprzez stochastyczne usuwanie mniej pożądanych rozwiązań i wprowadzanie niewielkich, losowych zmian. W terminologii biologicznej populacja rozwiązań poddawana jest selekcji naturalnej (lub selekcji sztucznej ) i mutacji . W rezultacie populacja będzie stopniowo ewoluować w kierunku wzrostu sprawności , w tym przypadku wybranej funkcji dopasowania algorytmu.
Ewolucyjne techniki obliczeniowe mogą tworzyć wysoce zoptymalizowane rozwiązania w szerokim zakresie ustawień problemów, co czyni je popularnymi w informatyce . Istnieje wiele wariantów i rozszerzeń, dostosowanych do bardziej specyficznych rodzin problemów i struktur danych. Obliczenia ewolucyjne są również czasami wykorzystywane w biologii ewolucyjnej jako procedura eksperymentalna in silico do badania wspólnych aspektów ogólnych procesów ewolucyjnych.
Historia
Zastosowanie ewolucyjnych zasad do automatycznego rozwiązywania problemów powstało w latach pięćdziesiątych XX wieku. Dopiero w latach sześćdziesiątych XX wieku w trzech różnych miejscach zaczęły powstawać trzy odmienne interpretacje tej idei.
Programowanie ewolucyjne zostało wprowadzone przez Lawrence'a J. Fogela w USA, a John Henry Holland nazwał swoją metodę algorytmem genetycznym . W Niemczech Ingo Rechenberg i Hans-Paul Schwefel przedstawili strategie ewolucyjne . Obszary te rozwijały się osobno przez około 15 lat. Od wczesnych lat dziewięćdziesiątych są zjednoczeni jako różni przedstawiciele („dialekty”) jednej technologii, zwanej ewolucyjnym przetwarzaniem komputerowym . Również na początku lat dziewięćdziesiątych pojawił się czwarty nurt podążający za ogólnymi ideami - programowanie genetyczne . Od lat 90. algorytmy inspirowane naturą stają się coraz ważniejszą częścią obliczeń ewolucyjnych.
Te terminologie oznaczają dziedzinę obliczeń ewolucyjnych i traktują programowanie ewolucyjne, strategie ewolucyjne, algorytmy genetyczne i programowanie genetyczne jako podobszary.
Najwcześniejsze komputerowe symulacje ewolucji z wykorzystaniem algorytmów ewolucyjnych i technik sztucznego życia zostały przeprowadzone przez Nilsa Aall Barricelli w 1953 roku, a pierwsze wyniki zostały opublikowane w 1954 roku. Kolejnym pionierem w latach pięćdziesiątych był Alex Fraser , który opublikował serię artykułów na temat symulacji sztucznej selekcji . Sztuczna ewolucja stała się powszechnie uznaną metodą optymalizacji w wyniku prac Ingo Rechenberga w latach sześćdziesiątych i wczesnych siedemdziesiątych XX wieku, który wykorzystywał strategie ewolucyjne do rozwiązywania złożonych problemów inżynieryjnych. Szczególnie algorytmy genetyczne zyskały popularność dzięki twórczości Johna Hollanda . Wraz ze wzrostem zainteresowania akademickiego, dramatyczny wzrost mocy komputerów umożliwił praktyczne zastosowania, w tym automatyczną ewolucję programów komputerowych. Algorytmy ewolucyjne są obecnie wykorzystywane do rozwiązywania problemów wielowymiarowych skuteczniej niż oprogramowanie tworzone przez ludzi, a także do optymalizacji projektowania systemów.
Techniki
Ewolucyjne techniki obliczeniowe obejmują głównie metaheurystyczne algorytmy optymalizacji . Mówiąc najogólniej, dziedzina ta obejmuje:
- Modelowanie agentowe
- Optymalizacja kolonii mrówek
- Sztuczne układy odpornościowe
- Sztuczne życie (zobacz także organizm cyfrowy )
- Algorytmy kulturowe
- Ewolucja różnicowa
- Ewolucja dwufazowa
- Szacowanie algorytmów dystrybucji
- Algorytmy ewolucyjne
- Programowanie ewolucyjne
- Strategia ewolucji
- Programowanie ekspresji genów
- Algorytm genetyczny
- Programowanie genetyczne
- Ewolucja gramatyczna
- Model ewolucji, którego można się nauczyć
- Uczenie się systemów klasyfikatorów
- Algorytmy memetyczne
- Neuroewolucja
- Optymalizacja roju cząstek
- Samoorganizacja, taka jak samoorganizujące się mapy , konkurencyjne uczenie się
- Inteligencja roju
Algorytmy ewolucyjne
Algorytmy ewolucyjne stanowią podzbiór obliczeń ewolucyjnych, ponieważ generalnie obejmują tylko techniki wdrażające mechanizmy inspirowane ewolucją biologiczną, takie jak rozmnażanie , mutacja , rekombinacja , dobór naturalny i przetrwanie najlepiej przystosowanych . Kandydujące rozwiązania problemu optymalizacji odgrywają rolę jednostek w populacji, a funkcja kosztu determinuje środowisko, w którym „żyją” rozwiązania (patrz także funkcja przystosowania ). Ewolucja populacji ma wtedy miejsce po ponownym zastosowaniu powyższych operatorów.
W tym procesie istnieją dwie główne siły, które stanowią podstawę systemów ewolucyjnych: mutacja rekombinacyjna i krzyżowanie tworzą niezbędną różnorodność, a tym samym ułatwiają wprowadzanie nowości, podczas gdy selekcja działa jako siła zwiększająca jakość.
Wiele aspektów takiego procesu ewolucyjnego ma charakter stochastyczny . Zmienione informacje w wyniku rekombinacji i mutacji są wybierane losowo. Z drugiej strony operatory selekcji mogą być deterministyczne lub stochastyczne. W tym drugim przypadku osoby o wyższej sprawności mają większe szanse na wybranie niż osoby o niższej sprawności , ale zazwyczaj nawet osoby słabe mają szansę zostać rodzicem lub przeżyć.
Algorytmy ewolucyjne i biologia
Algorytmy genetyczne dostarczają metod modelowania systemów biologicznych i biologii systemów, które są powiązane z teorią systemów dynamicznych , ponieważ są wykorzystywane do przewidywania przyszłych stanów systemu. Jest to po prostu żywy (ale może wprowadzający w błąd) sposób zwrócenia uwagi na uporządkowany, dobrze kontrolowany i wysoce ustrukturyzowany charakter rozwoju w biologii.
Jednak wykorzystanie algorytmów i informatyki, w szczególności teorii obliczeń , poza analogią do systemów dynamicznych, jest również istotne dla zrozumienia samej ewolucji.
Pogląd ten ma tę zaletę, że uznaje, że nie ma centralnej kontroli nad rozwojem; organizmy rozwijają się w wyniku lokalnych interakcji wewnątrz i między komórkami. Najbardziej obiecujące pomysły dotyczące podobieństw w rozwoju programów wydają się nam wskazywać na pozornie bliską analogię między procesami w komórkach a niskopoziomowym działaniem nowoczesnych komputerów. Zatem systemy biologiczne są jak maszyny obliczeniowe, które przetwarzają informacje wejściowe w celu obliczenia kolejnych stanów, tak że systemy biologiczne są bliższe obliczeniom niż klasyczny system dynamiczny.
Ponadto, zgodnie z koncepcjami z teorii obliczeniowej , mikroprocesy w organizmach biologicznych są zasadniczo niekompletne i nierozstrzygalne ( kompletność (logika) ), co oznacza, że „za analogią między komórkami i komputerami kryje się coś więcej niż prymitywna metafora.
Analogia do obliczeń rozciąga się również na związek między systemami dziedziczenia a strukturą biologiczną, co często uważa się za ujawnienie jednego z najpilniejszych problemów w wyjaśnianiu pochodzenia życia.
Automaty ewolucyjne , uogólnienie ewolucyjnych maszyn Turinga , zostały wprowadzone w celu dokładniejszego zbadania właściwości obliczeń biologicznych i ewolucyjnych. W szczególności pozwalają one na uzyskanie nowych wyników w zakresie wyrazistości obliczeń ewolucyjnych. Potwierdza to wstępny wynik dotyczący nierozstrzygalności naturalnej ewolucji oraz ewolucyjnych algorytmów i procesów. Ewolucyjne automaty skończone , najprostsza podklasa automatów ewolucyjnych pracujących w trybie terminalowym, mogą akceptować dowolne języki w danym alfabecie, w tym nierekurencyjnie wyliczalne (np. Język diagonalizacji) i rekurencyjnie wyliczalne, ale nie rekurencyjne języki (np. Język uniwersalnej maszyny Turinga ).
Znani praktycy
Lista aktywnych badaczy jest naturalnie dynamiczna i niewyczerpująca. Analiza sieciowa społeczności została opublikowana w 2007 roku.
- Kalyanmoy Deb
- Kenneth A De Jong
- Peter J. Fleming
- David B. Fogel
- Stephanie Forrest
- David E. Goldberg
- John Henry Holland
- Theo Jansen
- John Koza
- Zbigniew Michalewicz
- Melanie Mitchell
- Peter Nordin
- Riccardo Poli
- Ingo Rechenberg
- Hans-Paul Schwefel
Konferencje
Główne konferencje w dziedzinie obliczeń ewolucyjnych obejmują
- Konferencja ACM Genetic and Evolutionary Computation (GECCO),
- Kongres IEEE na temat obliczeń ewolucyjnych (CEC),
- EvoStar , na który składają się cztery konferencje: EuroGP, EvoApplications, EvoCOP i EvoMUSART,
- Równoległe rozwiązywanie problemów z natury (PPSN).
Zobacz też
- Adaptacyjne wyszukiwanie wymiarowe
- Sztuczny rozwój
- Autokonstrukcja
- Biologia rozwojowa
- Cyfrowy organizm
- Szacowanie algorytmu dystrybucji
- Ewolucyjna robotyka
- Rozwinięta antena
- Przybliżenie sprawności
- Sprawność fizyczna
- Krajobraz fitness
- Operatory genetyczne
- Ewolucja gramatyczna
- Obliczenia ewolucyjne oparte na człowieku
- Programowanie inferencyjne
- Interaktywne obliczenia ewolucyjne
- Lista cyfrowych symulatorów organizmów
- Testowanie mutacji
- Brak darmowego lunchu w wyszukiwaniu i optymalizacji
- Synteza programu
- Funkcje testowe do optymalizacji
- Uniwersalny darwinizm
Linki zewnętrzne
Bibliografia
- Cz. Bäck, DB Fogel i Z. Michalewicz (redaktorzy), Handbook of Evolutionary Computation , 1997, ISBN 0750303921
- Cz. Bäck i H.-P. Schwefel. Przegląd ewolucyjnych algorytmów optymalizacji parametrów . Evolutionary Computation, 1 (1): 1–23, 1993.
- W. Banzhaf, P. Nordin, RE Keller i FD Francone. Programowanie genetyczne - wprowadzenie. Morgan Kaufmann, 1998.
- S. Cagnoni i in., Real-World Applications of Evolutionary Computing , Springer-Verlag Lecture Notes in Computer Science , Berlin, 2000.
- R. Chiong, Th. Weise, Z. Michalewicz (red.), Variants of Evolutionary Algorithms for Real-World Applications , Springer , 2012, ISBN 3642234232
- KA De Jong, Obliczenia ewolucyjne: ujednolicone podejście. MIT Press , Cambridge MA, 2006
- AE Eiben i JE Smith, From evolutionary computation to the evolution of things , Nature, 521: 476-482, doi: 10.1038 / nature14544, 2015
- AE Eiben i JE Smith, Wprowadzenie do obliczeń ewolucyjnych, Springer, wydanie pierwsze , 2003; Druga edycja 2015
- DB Fogel. Obliczenia ewolucyjne. Ku nowej filozofii inteligencji maszynowej . IEEE Press, Piscataway, NJ, 1995.
- LJ Fogel, AJ Owens i MJ Walsh. Sztuczna inteligencja poprzez symulowaną ewolucję . Nowy Jork: John Wiley, 1966.
- DE Goldberg. Algorytmy genetyczne w wyszukiwaniu, optymalizacji i uczeniu maszynowym. Addison Wesley, 1989.
- JH Holland. Adaptacja w systemach naturalnych i sztucznych. University of Michigan Press , Ann Arbor, 1975.
- P. Hingston, L. Barone i Z. Michalewicz (redaktorzy), Design by Evolution, Natural Computing Series , 2008, Springer , ISBN 3540741097
- JR Koza. Programowanie genetyczne: o programowaniu komputerów za pomocą naturalnej ewolucji. MIT Press, Massachusetts, 1992.
- FJ Lobo, CF Lima, Z. Michalewicz (redaktorzy), Parameter Setting in Evolutionary Algorithms , Springer , 2010, ISBN 3642088929
- Z. Michalewicz , Genetic Algorithms + Data Structures - Evolution Programs , 1996, Springer , ISBN 3540606769
- Z. Michalewicz i DB Fogel, How to Solve It: Modern Heuristics , Springer , 2004, ISBN 978-3-540-22494-5
- I. Rechenberg. Strategia ewolucji: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973. (w języku niemieckim)
- H.-P. Schwefel. Numeryczna optymalizacja modeli komputerowych. John Wiley & Sons, Nowy Jork, 1981. 1995 - 2. wydanie.
- D. Simon. Ewolucyjne algorytmy optymalizacji . Wiley, 2013.
- M. Sipper, W. Fu, K. Ahuja i JH Moore (2018). „Badanie przestrzeni parametrów algorytmów ewolucyjnych” . BioData Mining . 11 : 2. doi : 10.1186 / s13040-018-0164-x . PMC 5816380 . PMID 29467825 . CS1 maint: używa parametru autorów ( link )
- Y. Zhang i S. Li. (2017). „PSA: nowatorski algorytm optymalizacji oparty na zasadach przetrwania porcellio scaber”. arXiv : 1709.09840 [ cs.NE ]. CS1 maint: używa parametru autorów ( link )
Bibliografia