Stochastické difúzní vyhledávání - Stochastic diffusion search

Stochastické difúzní vyhledávání (SDS) byl poprvé popsán v roce 1989 jako populační algoritmus pro porovnávání vzorů [Bishop, 1989]. Patří do rodiny rojová inteligence a přirozeně inspirované vyhledávání a optimalizace algoritmy, které zahrnují optimalizace kolonií mravenců, optimalizace roje částic a genetické algoritmy; jako takový byl SDS první metaheuristický Swarm Intelligence. Na rozdíl od stigmergetické komunikace používané v optimalizace kolonií mravenců, který je založen na modifikaci fyzikálních vlastností simulovaného prostředí, SDS používá formu přímé (one-to-one) komunikace mezi agenty podobnou mechanismu tandemového volání používaného jedním druhem mravenců, Leptothorax acervorum.

V SDS agenti provádějí levné, částečné hodnocení hypotézy (kandidátní řešení problému hledání). Poté sdílejí informace o hypotézách (šíření informací) prostřednictvím přímé komunikace one-to-one. Díky difúznímu mechanismu lze identifikovat vysoce kvalitní řešení od klastrů agentů se stejnou hypotézou. Fungování SDS lze nejsnadněji pochopit pomocí jednoduché analogie - The Restaurant Game.

Restaurační hra

Skupina delegátů se účastní dlouhé konference v neznámém městě. Každý večer si každý delegát musí někde najít večeři. Existuje velký výběr restaurací, z nichž každá nabízí širokou škálu jídel. Problém, kterému skupina čelí, je najít nejlepší restauraci, tedy restauraci, kde by si jídlo užívalo maximální množství delegátů. Dokonce i souběžné vyčerpávající hledání kombinací restaurací a jídel by trvalo příliš dlouho. K vyřešení problému se delegáti rozhodnou použít stochastické difúzní vyhledávání.

Každý delegát jedná jako agent, který udržuje hypotézu o nejlepší restauraci ve městě. Každý večer každý delegát testuje svou hypotézu tím, že tam stolová a náhodně vybere jedno z nabízených jídel. Následujícího rána u snídaně každý delegát, který si předchozí noc neužil jídlo, požádá jednoho náhodně vybraného kolegu, aby se podělil o své dojmy z večeře. Pokud byla zkušenost dobrá, přijme tuto restauraci také jako svoji volbu. Jinak si náhodně vybere jinou restauraci z těch, které jsou uvedeny ve Zlatých stránkách. Pomocí této strategie se zjistilo, že velmi rychle se shromažďuje značný počet delegátů kolem „nejlepší“ restaurace ve městě.

Aplikace

SDS byl aplikován na různé problémy, jako je textové vyhledávání [Bishop, 1989], rozpoznávání objektů [Bishop, 1992], sledování funkcí [Grech-Cini, 1993], autolokace mobilních robotů [Beattie, 1998] a výběr místa pro bezdrátové připojení sítě [Whitaker, 2002].

Analýza

Na rozdíl od mnoha technik vyhledávání inspirovaných přírodou existuje komplexní matematický rámec popisující chování SDS. Analýza SDS zkoumala jeho globální optimálnost a konvergenci [Nasuto, 1998], lineární časovou složitost [Nasuto et al., 1999], robustnost [Myatt, 2004] a alokaci zdrojů [Nasuto, 1999] za různých podmínek vyhledávání.

Reference

  • Bishop, J. M., (1989). Stochastické vyhledávací sítě. Proc. 1. IEE konf. o umělých neuronových sítích, str. 329–331, Londýn.
  • Bishop, J. M. a Torr, P., (1992). Stochastická vyhledávací síť. V R. Linggard, D.J. Myers, C. Nightingale (eds.), Neural Networks for Images, Speech and Natural Language, pp370–387, New York, Chapman & Hall.
  • Beattie, P.D. & Bishop, J.M., (1998). Vlastní lokalizace na autonomním invalidním vozíku „Senario“. Journal of Intelligent and Robotic Systems 22, pp 255–267, Kluwer Academic Publishers.
  • Grech-Cini, H. J. a McKee, G.T. (1993) Lokalizace oblasti úst v obrazech lidských tváří. In P.S.Schenker (Ed.), Proceedings of SPIE - The International Society for Optical Engineering, Sensor Fusion VI 2059, Massachusetts.
  • Myatt, D.R., Bishop J.M. a Nasuto, S.J., (2004). Minimální kritéria stabilní konvergence pro hledání stochastické difúze Bude zveřejněno v elektronických dopisech.
  • Nasuto, S.J., (1999). Analýza alokace zdrojů vyhledávání stochastické difúze. Disertační práce. University of Reading, Velká Británie.
  • Nasuto, S.J. & Bishop, J.M., (1999). Konvergenční analýza Stochastické difúzní vyhledávání. Journal of Parallel Algorithms and Applications 14: 2, pp 89–107.
  • Nasuto, S.J., Bishop, J.M. a Lauria, L., (1998). Časová složitost vyhledávání stochastické difúze. Neural Computation '98, Vídeň, Rakousko.
  • Whitaker, R.M., Hurley, S., (2002). Agentový přístup k výběru místa pro bezdrátové sítě. Proc ACM Symposium on Applied Computing (Madrid). 574–577.
  • Jones, D. (2002). Omezené vyhledávání stochastické difúze. SCARP 2002, University of Reading, UK.