Algorytm ewolucyjny - Evolutionary algorithm


Z Wikipedii, wolnej encyklopedii

W sztucznej inteligencji , ewolucyjny algorytm ( EA ) jest podzbiorem z obliczeń ewolucyjnych , ogólnej populacji oparte metaheurystyka optymalizacji algorytmu . EA wykorzystuje mechanizmy inspirowane ewolucji biologicznej , takich jak reprodukcji , mutacji , rekombinacji i selekcji . Rozwiązania kandydujące do problemu optymalizacji odgrywać rolę osobników w populacji, a funkcja fitness określa jakość rozwiązań (patrz równieżFunkcja strat ). Rozwój populacji następnie odbywa się po wielokrotnym zastosowaniu powyższych operatorów.

Algorytmy ewolucyjne rozwiązania często wykonywać dobrze zbliżonych do wszystkich rodzajów problemów, ponieważ idealnie nie dokonywać żadnych założeń o leżącej siłowni krajobrazu . Techniki od zastosowanych algorytmów ewolucyjnych do modelowania ewolucji biologicznej są zasadniczo ograniczone do poszukiwań microevolutionary procesów i modeli planowania oparte na procesach komórkowych. W większości rzeczywistych zastosowań EA, złożoność obliczeniowa jest czynnikiem zabranianie. W rzeczywistości, to złożoność obliczeniowa jest wynikiem oceny funkcji fitness. Fitness przybliżeniem jest jednym z rozwiązań w celu przezwyciężenia tych trudności. Jednak pozornie proste EA może rozwiązać często złożonych problemów; Dlatego nie może być żaden bezpośredni związek pomiędzy złożonością algorytmów i złożoności problemu.

Realizacja

Krok pierwszy: Generowanie początkową populację z osobników losowo. (Pierwsza generacja)

Krok drugi: Ocenić przydatność każdego osobnika w tej populacji (terminie przydatności wystarczający osiągnięty, itd.)

Krok trzeci: Powtórz następujące regenerational kroki do zakończenia:

  1. Wybierz najlepiej dopasowanej osób do reprodukcji . (Rodzice)
  2. Wyhodować nowe osoby przez zwrotnice i mutacji operacji do rodzenia potomstwa .
  3. Oceny sprawności fizycznej nowych jednostek.
  4. Wymienić populację najmniej pasuje do nowych jednostek.

rodzaje

Podobne techniki różnią się reprezentacji genetycznej oraz inne szczegóły wykonania i natury konkretnego zastosowanego problemu.

  • Algorytm genetyczny - Jest to najbardziej popularny typ EA. Jeden szuka rozwiązania problemu w postaci ciągów liczb (tradycyjnie binarnych, chociaż najlepsze reprezentacje są zwykle te, które odzwierciedlają coś o problem jest rozwiązany) przez zastosowanie operatorów takich jak rekombinacji i mutacji (czasami jeden, czasami oba) , Ten typ EA jest często używany w optymalizacji problemów. Inna nazwa dla niego jest fetura , od łacińskiego do hodowli.
  • Programowanie genetyczne - tutaj rozwiązania są w postaci programów komputerowych, a ich kondycja zależy od ich zdolności do rozwiązywania problemów obliczeniowych.
  • Programowanie ewolucyjne - Podobny do programowania genetycznego, ale struktura programu jest stała i jej parametry numeryczne mogą ewoluować.
  • Programowanie ekspresji genów - Like programowania genetycznego, GEP ewoluuje także programów komputerowych, ale bada system genotyp-fenotyp, gdzie programy komputerowe o różnych rozmiarach są zakodowane w liniowych chromosomów stałej długości.
  • Strategia Evolution - Współpracuje z wektorów liczb rzeczywistych jako reprezentacje rozwiązań i zazwyczaj używa samodostosowującego częstości mutacji.
  • Różnica ewolucja - na podstawie różnic wektorowej, a zatem przede wszystkim nadaje się do numerycznych optymalizacji problemów.
  • Neuroevolution - Podobny do programowania genetycznego ale genomy reprezentować sztucznych sieci neuronowych opisując strukturę i podłączenie wagi. Kodujący genom może być bezpośrednie lub pośrednie.
  • Learning System klasyfikatora - Oto rozwiązanie to zbiór klasyfikatorów (przepisy lub warunki). Michigan ACC zmienia się na poziomie poszczególnych separatorów natomiast Pittsburgh ACC wykorzystuje populacje klasyfikatora zestawów. Początkowo były tylko binarne klasyfikatorów, ale teraz to prawdziwe, sieć neuronowa, lub S-wyrażenie typów. Fitness jest zazwyczaj określane zarówno z siły i dokładności w oparciu uczenia zbrojenie lub nadzorowanego uczenia podejścia.

Porównanie procesów biologicznych

Możliwe ograniczenia wielu algorytmów ewolucyjnych jest brak wyraźnego genotyp-fenotyp rozróżnienia . W naturze zapłodniona komórka jajowa przechodzi skomplikowany proces zwany w embriogenezie stać dojrzały fenotyp . Ten pośredni kodowania uważa się, aby poszukiwanie genetyczny bardziej wydajny (to znaczy zmniejszenie prawdopodobieństwa śmiertelnych mutacji), a także może zwiększyć ewoluowalność organizmu. Takie pośrednie (aka generatywne lub rozwojowe) kodowania również umożliwić ewolucję wykorzystać regularności w środowisku. Ostatnie prace w dziedzinie sztucznej embryogeny lub sztuczne systemy rozwojowe, stara się rozwiązać te problemy. Oraz programowanie ekspresji genów powodzeniem bada system genotyp-fenotyp, gdzie genotyp składa się z liniowych chromosomów wielogenową stałej długości i fenotyp składa się z wielu drzew ekspresyjnych lub programów komputerowych o różnych rozmiarach i kształtach.

Powiązane techniki

Algorytmy rój zawierać

Inne populacyjnych metaheurystyka metody

  • Polowanie Search - metoda zainspirowaną polowania grupowego niektórych zwierząt, takich jak wilki, które organizują swoje stanowisko otoczyć ofiary, każdy z nich w stosunku do pozycji innych, a zwłaszcza, że ich przywódcy. Jest to sposób ciągły optymalizacji dostosowywane kombinatorycznej metody optymalizacji.
  • Adaptacyjne wyszukiwania wymiarowa - W przeciwieństwie metaheurystyka technik inspirowanych naturą, adaptacyjny algorytm wyszukiwania wymiarowa nie implementuje żadnej metafory jako zasadę podstawową. Zamiast tego wykorzystuje się proste metody wysokowydajne, w oparciu o aktualizacji stosunek wyszukiwania wymiarowości (SDR) parametru, przy każdej iteracji.
  • Algorytm Firefly jest inspirowana przez zachowanie świetliki, przyciągając do siebie przez migające światło. Jest to szczególnie przydatne dla multimodalnego optymalizacji.
  • Szukaj Harmony - Opierając się na idei zachowania muzyków w poszukiwaniu lepszych harmonie. Algorytm ten jest przeznaczony do optymalizacji kombinatorycznej, jak również optymalizację parametrów.
  • Gaussian adaptacja - na podstawie teorii informacji. Wykorzystywane do maksymalizacji wydajności produkcji, myśli kondycję lub średnią informacji . Patrz na przykład entropii w termodynamice i teorii informacji .
  • Memetyczna algorytm - hybrydowy metoda, zainspirowany Richard Dawkins pojęciem „s z meme, że powszechnie przyjmuje postać algorytmu populacyjnego w połączeniu z poszczególnymi procedurami kształcenia zdolnych do wykonywania lokalnych udoskonalenia. Podkreśla wykorzystanie wiedzy specyficznych problemów i próbuje zgrać przeszukiwanie lokalnej i globalnej w synergiczny sposób.

Przykłady

Symulacje komputerowe Tierra i Avida próbować modelować macroevolutionary dynamikę.

Galeria

Referencje

  1. ^ Vikhar, PA „Algorytmy ewolucyjne: Krytyczny przegląd i perspektywy na przyszłość” . Proceedings of 2016 Międzynarodowej Konferencji na temat globalnych trendów w Signal Processing, Informacji i Komunikacji Computing (ICGTSPICC) . Jalgaon, 2016, ss. 261-265. ISBN  978-1-5090-0467-6 .
  2. ^ B Cohoon, J; i in. Algorytmy ewolucyjne dla fizycznego projektowania układów VLSI (PDF) . Advances in Evolutionary Computing: Theory and Applications . Springer, str. 683-712, 2003. ISBN  978-3-540-43330-9 .
  3. ^ Jon Roland, Kapryśna Świat . Powieść, która wykorzystuje fetura wybór kandydatów na stanowiska publiczne.
  4. ^ GS Hornby JB rdzawca. „Tworzenie komponentów wysokiego szczebla z generatywnej reprezentacji do ewolucji ciało-mózg”. Sztuczne Życie , 8 (3): 223-246, 2002.
  5. ^ Jeff Clune Benjamin Beckmann, Charles Ofria i Robert Pennock. „Evolving Skoordynowane czworonóg chodach z HyperNEAT generatywnej Kodowanie” . Proceedings of IEEE Congress on Evolutionary Computing Odcinek specjalny ewolucyjne Robotyki , 2009 Trondheim, Norwegia.
  6. ^ J Clune C. Ofria i RT Pennock, "jak generatywnej kodowania taryfy miarę zmniejszania problemów regularność" w PPSN (G. Rudolph, T. Jansen SM Lucas C Poloniego i N. Beume, wyd .), tom. 5199 z Lecture Notes in Computer Science , s. 358-367, Springer, 2008.
  7. ^ Ferreira, C., 2001. "Gene Expression Programowanie: A New Adaptacyjny algorytm rozwiązywania problemów" . Complex Systems , Vol. 13, wydanie 2: 87-129.
  8. ^ F Merrikh-Bayat „Algorytm płoza root: a metaheurystyka jednomodalnych rozkładach i do rozwiązywania problemów optymalizacyjnych multimodalne inspirowane płozy i korzenie roślin w przyrodzie” Applied Soft Computing , tom. 33, str. 292-303, 2015
  9. ^ R. Oftadeh i in. (2010), "Powieść algorytm optymalizacji meta-heurystyczne zainspirowane polowania grupy zwierząt: szukaj Hunting" , 60, 2087-2098.
  10. ^ Aminy Agharghor; Mohammed Essaid Riffi (2017). „Najpierw Adaptacja algorytmu wyszukiwania Polowanie na kwadratowej Przypisanie problem”. Europa i MENA Współpraca osiągnięć w dziedzinie technologii informacyjnych i komunikacyjnych : 263-267. doi : 10.1007 / 978-3-319-46568-5_27 . ISBN  978-3-319-46567-8 .
  11. ^ Hasançebi, O., Kazemzadeh Azad, S. (2015), "Adaptacyjny Dimensional Szukaj: A New metaheurystyka Algorytm Discrete Truss Dobór Optimization" Komputery i budowle , 154, 1-16.
  12. ^ Simionescu, Pensylwania; Beale, DG; Dozier, GV (2004). „Ograniczone rozwiązywania problemu optymalizacji za pomocą algorytmów estymacji dystrybucji” (PDF) . Proc. Kongresu z 2004 roku w sprawie obliczeń ewolucyjnych - CEC2004. Portland, OR: 1647/53. doi : 10,1109 / CEC.2006.1688506 . Źródło 7 styczeń wykupu w 2017 r .
  13. ^ Simionescu, Pensylwania; Dozier, GV; Wainwright, RL (2006). „Dwa-Populacja ewolucyjny algorytm ograniczone Optimization Problems” (PDF) . Proc 2006 IEEE International Conference on obliczeń ewolucyjnych. Vancouver, Kanada: 1647/53. doi : 10,1109 / CEC.2006.1688506 . Źródło 7 styczeń wykupu w 2017 r .
  14. ^ Simionescu, PA (2014). Computer Aided graficzny i narzędzia symulacyjne dla użytkowników AutoCAD (1st ed.). Boca Raton, FL: CRC Press . ISBN  978-1-4822-5290-3 .

Bibliografia