Swarm Intelligence

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 18. dubna 2018; kontroly vyžadují 18 úprav .

Swarm intelligence ( RI) popisuje kolektivní chování decentralizovaného samoorganizujícího se systému .  V teorii umělé inteligence je považována za optimalizační metodu . Termín zavedli Gerardo Beni a Wang Jing v roce 1989 v kontextu systému celulárního robota [1] . Touto myšlenkou se však již dříve podrobně zabýval Stanisław Lem v románu Neporazitelný (1964) [2] a eseji Zbraňové systémy 21. století aneb Evoluce vzhůru nohama (1983).

Swarmové zpravodajské systémy se zpravidla skládají z mnoha agentů ( Boids ), kteří lokálně interagují mezi sebou as prostředím. Ideje chování zpravidla pocházejí z přírody a zejména z biologických systémů. Každý boyid se řídí velmi jednoduchými pravidly, a přestože neexistuje žádný centralizovaný systém kontroly chování, který by každému z nich řekl, co má dělat, místní a do jisté míry náhodné interakce vedou ke vzniku inteligentního skupinového chování, které je mimo kontrolu jednotlivých lidí. Přesná definice inteligence roje stále není formulována. Obecně by RI měl být multiagentní systém, který by měl samoorganizující se chování, které by celkově mělo vykazovat nějaké rozumné chování.

Aplikace principů roje v robotice se nazývá skupinová robotika , zatímco inteligence roje se týká obecnější sady algoritmů. "Swarm forecasting" se používá při řešení některých problémů předpovídání.

Příklady algoritmů

Metoda roje částic

Optimalizace roje částic (PSO ) je  numerická optimalizační metoda, která nevyžaduje znát přesný gradient optimalizované funkce. MFR byla prokázána Kennedym, Eberhartem a Sheou, původně měla napodobovat sociální chování. Algoritmus byl zjednodušen a bylo zjištěno, že je vhodný pro provádění optimalizace . Kniha Kennedyho a Eberharta popisuje mnohé z filozofických aspektů MFR a tzv. swarm intelligence. Mnoho výzkumů aplikací MFR provedl Paul [3] [4] .

MFR optimalizuje funkci udržováním populace možných řešení, nazývaných částice, a pohybem těchto částic v prostoru roztoku podle jednoduchého vzorce. Pohyb se řídí principem nejlepší polohy nalezené v tomto prostoru, která se neustále mění, když částice najdou příznivé polohy.

Ant algoritmus

Algoritmus optimalizace kolonií mravenců ( ant kolonie optimalizace, ACO ) je jedním z  účinných polynomiálních algoritmů pro hledání přibližných řešení problému obchodního cestujícího , stejně jako podobných problémů hledání tras v grafech. Přístup navržený belgickým výzkumníkem Marcem Dorigem .

Podstatou přístupu je analyzovat a použít behaviorální model mravenců hledajících cesty z kolonie k potravě. Algoritmus je založen na chování mravenčí kolonie - značení úspěšných cest velkým množstvím feromonů . Práce začíná umístěním mravenců na vrcholy grafu (města), poté začíná pohyb mravenců - směr je určen pravděpodobnostní metodou na základě vzorce:

,

kde:

 — Pravděpodobnost přecházení silnice ,  — délka tého přechodu,  — Počet feromonů na spojnici,  - Hodnota, která určuje "chamtivost" algoritmu,  — Hodnota, která určuje „herding“ algoritmu i .

Včelí algoritmus

Umělá optimalizace včelstev (ABC ) je rojový algoritmus založený na meta-heuristickém algoritmu představeném Karabogem v roce 2005 [ 5] .  Napodobuje chování krmných včel. Algoritmus ABC se skládá ze tří fází: včela dělnice, včela dozorkyně a včela skautka. Včely používají lokální vyhledávací algoritmus v blízkosti řešení vybraných na základě deterministického výběru včelami dělnicemi a pravděpodobnostního výběru včelami strážnými. Skautská včela provádí odmítnutí vyčerpaných zdrojů potravy v procesu krmení. V této analogii jsou řešení, která již nejsou užitečná pro nalezení řešení, vyřazena a jsou přidána nová řešení (podobně jako prozkoumávání nových regionů při hledání zdrojů).

Umělý imunitní systém

Umělý imunitní systém (AIS) je adaptivní výpočetní systém, který využívá modely, principy, mechanismy a funkce popsané v teoretické imunologii , které se používají k řešení aplikovaných problémů [6] .

Navzdory skutečnosti, že přirozené imunitní systémy nejsou zdaleka plně pochopeny, dnes existují nejméně tři teorie, které vysvětlují fungování imunitního systému a popisují interakci jeho prvků, a to: teorie negativní selekce, teorie klonální selekce. a teorie imunitní sítě. Tvořily základ pro vytvoření tří algoritmů pro fungování IIS.

Algoritmus šedého vlka

Netopýří algoritmus

Gravitační vyhledávací algoritmus

Gravitational Search Algorithm (GSA ) je vyhledávací  algoritmus založený na zákonu univerzální gravitace a konceptech hromadné interakce. Algoritmus je založen na teorii přitažlivosti z newtonovské fyziky . Algoritmus používá gravitační hmoty jako vyhledávací agenty.

V posledních letech byly vyvinuty různé heuristické optimalizační algoritmy . Mnoho z těchto algoritmů je založeno na přírodních jevech. Pokud porovnáme algoritmus gravitačního vyhledávání s jinými algoritmy, pak je tento algoritmus jedním z nejúčinnějších při řešení různých problémů optimalizace nelineárních funkcí.

Altruistický algoritmus

Švýcarští vědci vyvinuli algoritmus založený na Hamiltonově pravidle výběru rodiny. Algoritmus ukazuje, jak se altruismus jedince v roji může časem vyvíjet a vést k efektivnějšímu chování roje [7] [8] .

Algoritmus Firefly

Algoritmus kapky vody

Intelligent Water Droplet Algorithm ( IWD )  je optimalizační algoritmus založený na rojovém algoritmu, který využívá metody přirozených řek a toho, jak nacházejí téměř optimální cesty k cíli.

Najde optimální nebo téměř optimální cesty odvozené z reakcí probíhajících mezi vodními kapkami, když voda protéká korytem řeky. V algoritmu IWD je několik umělých kapek vody závislých na sobě a jsou schopny změnit své prostředí tak, aby si našly nejlepší cestu na cestě nejmenšího odporu. Algoritmus IWD je tedy konstruktivní populačně orientovaný optimalizační algoritmus [9] .

Metoda tvorby řeky

Metoda samohybných částic

Stochastické difúzní vyhledávání

Multiswarmová optimalizace

Kukaččí algoritmus

Vyhledávací algoritmus Cuckoo je optimalizovaný algoritmus vyvinutý Xin-She Yang a Suash Deb v roce 2009.

Inspirací pro jeho vznik byl hnízdní parazitismus některých druhů kukaček , které kladou vajíčka do hnízd jiných ptáků (jiných ptačích druhů). Někteří z majitelů hnízd se mohou dostat do přímého konfliktu s kukačkami, které se k nim vloupou. Pokud například majitel hnízda zjistí, že vejce nejsou jeho, pak tato mimozemská vejce buď vyhodí, nebo hnízdo jednoduše opustí a vytvoří si nové někde jinde.

Některé druhy kukaček, jako jsou hnízdní parazité Nového světa , jako je kukačka pruhovaná nebo čtyřkřídlá ( Tapera naevia ), se vyvinuly tak, že se samice velmi často specializují na napodobování barev a struktury vajíček vybraných hostitelských ptačích druhů [10 ] .

Optimalizace pohybu bakterií

Viz také

Literatura

Poznámky

  1. ↑ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. Pokročilý seminář NATO o robotech a biologických systémech, Toskánsko, Itálie, 26. až 30. června (1989)
  2. ↑ V kapitole „Laudova hypotéza“ je uvedena věta „roj se promění v takový „oblačný mozek“ (rój układa się w ten jakiś „chmuromózg“).
  3. ↑ Parsopoulos, K.E.; Vrahatis, MN Nedávné přístupy k problémům globální optimalizace prostřednictvím Particle Swarm Optimization   // Natural Computing : deník. - 2002. - Sv. 1 , ne. 2-3 . - S. 235-306 . - doi : 10.1023/A:1016568309421 .
  4. ↑ Particle Swarm Optimization Archived 22. února 2014 na Wayback Machine od Maurice Clerca, ISTE, ISBN 1-905209-04-5 , 2006.
  5. ↑ Karaboga, Dervis (2010) Algoritmus umělého včelstva Archivováno 3. dubna 2014 na Wayback Machine Scholarpedia , 5 (3):6915.
  6. ↑ de Castro, Leandro N.; Timmisi, Jonathane. Umělé imunitní systémy: Nový přístup výpočetní inteligence . - Springer , 2002. - S. 57-58. — ISBN 1852335947 , 9781852335946.  
  7. ↑ Altruismus pomáhá rojícím se robotům létat lépe Archivováno 15. září 2012 na Wayback Machine genevalunch.com , 4. května 2011.
  8. ↑ Waibel M, Floreano1 D a Keller L (2011) „Kvantitativní test Hamiltonova pravidla pro evoluci altruismu“ PLoS Biology , 9 (5): e1000615. doi : 10.1371/journal.pbio.1000615
  9. ↑ Šáh-Hosseini, Hamed. Inteligentní algoritmus vodních kapek: přírodou inspirovaný optimalizační algoritmus založený na roji  (anglicky)  // International Journal of Bio-Inspired Computation: journal. - 2009. - Sv. 1 , ne. 1/2 . - str. 71-79 .
  10. ↑ R. B. Payne, M. D. Sorenson a K. Klitz, The Cuckoos, Oxford University Press, (2005).