Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Стохастикалық диффузиялық іздеу (СДС) алғаш рет 1989 жылы популяцияға негізделген, үлгіге сәйкес келетін алгоритм ретінде сипатталды. Ол құмырсқалар колониясын оңтайландыруды, бөлшектер құмырсқаларын оңтайландыруды және генетикалық алгоритмдерді қамтитын құмырсқалар ақыл-ойының және табиғи түрде илһамланған іздеу және оңтайландыру алгоритмдерінің отбасына жатады; осындай SDS алғашқы құмырсқалар ақыл-ойы метагеуристикалық болды. Шымшықтар колониясын оңтайландыруда қолданылатын, симуляцияланған ортаның физикалық қасиеттерін өзгертуге негізделген стигмергетикалық қарым-қатынастан айырмашылығы, SDS агенттер арасында тікелей (бір-бірден) қарым-қатынас түрін қолданады. SDS агенттерінде арзан, гипотезаның ішінара бағалауы (іздестіру мәселесінің кандидаттық шешімі) жүргізіледі. Олар гипотезалар туралы ақпаратты тікелей бір-бір байланыс арқылы бөліседі (ақпаратты тарату). Диффузиялық механизмнің нәтижесінде бірдей гипотезаға ие агенттердің кластерлерінен жоғары сапалы ерітінділерді анықтау мүмкін. SDS-тің жұмысын қарапайым ұқсастық арқылы оңай түсінуге болады Ресторандық ойын.
Stochastic diffusion search (SDS) was first described in 1989 as a population based, pattern matching algorithm. It belongs to a family of swarm intelligence and naturally inspired search and optimisation algorithms which includes ant colony optimization, particle swarm optimization and genetic algorithms; as such SDS was the first Swarm Intelligence metaheuristic. Unlike stigmergetic communication employed in ant colony optimization, which is based on modification of the physical properties of a simulated environment, SDS uses a form of direct (one to one) communication between the agents similar to the tandem calling mechanism employed by one species of ants, Leptothorax acervorum. In SDS agents perform cheap, partial evaluations of a hypothesis (a candidate solution to the search problem). They then share information about hypotheses (diffusion of information) through direct one to one communication. As a result of the diffusion mechanism, high quality solutions can be identified from clusters of agents with the same hypothesis. The operation of SDS is most easily understood by means of a simple analogy – The Restaurant Game.
Ресторандық ойын
Бір топ делегаттар бейтаныс қалада ұзаққа созылған конференцияға қатысады. Әр кеш сайын делегаттар тамақ ішуге бір жерді табулары керек. Мұнда мейрамханалар көп, әрқайсысында түрлі тағамдар ұсынылады. Топтың алдындағы мәселе - ең жақсы мейрамхананы табу, яғни ең көп делегаттың тамақтануға қуанатын мейрамхана. Тіпті, тамақхана мен ас үйлесімдерін іздеу үшін де көп уақыт қажет. Мәселені шешу үшін делегаттар стохастикалық диффузиялық іздеуді қолдануға шешім қабылдайды. Әр делегат қаладағы ең жақсы мейрамхананы анықтайтын гипотезаны қолданатын агент ретінде әрекет етеді. Әр кеш сайын әр делегат өзінің гипотезасын сол жерде тамақтанып, ұсынылған тағамдардың бірін кездейсоқ таңдайды. Келесі күні таңертеңгі тамақта өткен түні тамақтанбай қалған әрбір делегат кездейсоқ таңдалған әріптестерінен кешкі ас туралы әсерлерін бөлісуін сұрайды. Егер тәжірибе жақсы болса, ол осы мейрамхананы өзінің таңдауы ретінде қабылдайды. Әйтпесе ол "Сары парақшалар" тізіміне енген басқа да мейрамхананы кездейсоқ таңдайды. Бұл стратегияны қолдану арқылы делегаттардың едәуір көп саны қаладағы "ең жақсы" мейрамхананың айналасында тез жиналады.
A group of delegates attends a long conference in an unfamiliar town. Every night each delegate must find somewhere to dine. There is a large choice of restaurants, each of which offers a large variety of meals. The problem the group faces is to find the best restaurant, that is the restaurant where the maximum number of delegates would enjoy dining. Even a parallel exhaustive search through the restaurant and meal combinations would take too long to accomplish. To solve the problem delegates decide to employ a stochastic diffusion search. Each delegate acts as an agent maintaining a hypothesis identifying the best restaurant in town. Each night each delegate tests his hypothesis by dining there and randomly selecting one of the meals on offer. The next morning at breakfast every delegate who did not enjoy his meal the previous night, asks one randomly selected colleague to share his dinner impressions. If the experience was good, he also adopts this restaurant as his choice. Otherwise he simply selects another restaurant at random from those listed in `Yellow Pages'. Using this strategy it is found that very rapidly significant number of
delegates congregate around the 'best' restaurant in town.
Қолданбалар
SDS мәтіндік іздеу [Бишоп, 1989], объектілерді тану [Бишоп, 1992], функцияларды қадағалау [Греч Цини, 1993], мобильді роботтардың өзіндік орналасуы [Бити, 1998] және сымсыз желілер үшін сайтты таңдау [Уайткер, 2002] сияқты әртүрлі мәселелерге қолданылды.
SDS has been applied to diverse problems such as text search [Bishop, 1989], object recognition [Bishop, 1992], feature tracking [Grech Cini, 1993], mobile robot self localisation [Beattie, 1998] and site selection for wireless networks [Whitaker, 2002].
Талдау
Көптеген табиғаттан рухтандырылған іздеу әдістерінен айырмашылығы, SDS-тің мінез-құлқын сипаттайтын жан-жақты математикалық негіздеме бар. SDS-ті талдау оның жаһандық оптималдықты және конвергенттілігін [Nasuto, 1998], сызықтық уақыт күрделілігін [Nasuto et al., 1999], беріктігін [Myatt, 2004] және ресурстарды бөлуді [Nasuto, 1999] әртүрлі іздеу жағдайларында зерттеді.
Unlike many Nature Inspired Search techniques there is a comprehensive mathematical framework describing the behaviour of SDS. Analysis of SDS has investigated its global optimality and convergence [Nasuto, 1998], linear time complexity [Nasuto et al., 1999], robustness [Myatt, 2004], and resource allocation [Nasuto, 1999] under a variety of search conditions.