Стохастический диффузионный поиск - Stochastic diffusion search

Стохастический диффузионный поиск (SDS) был впервые описан в 1989 году как алгоритм сопоставления с образцом, основанный на популяциях [Bishop, 1989]. Он принадлежит семье рой интеллект и естественно вдохновленный поиск и оптимизация алгоритмы, которые включают оптимизация колонии муравьев, оптимизация роя частиц и генетические алгоритмы; как таковая SDS была первой метаэвристикой Swarm Intelligence. В отличие от стигмергетической коммуникации, используемой в оптимизация колонии муравьев, который основан на модификации физических свойств моделируемой среды, SDS использует форму прямого (один-к-одному) общения между агентами, аналогично механизму тандемного вызова, используемому одним видом муравьев, Leptothorax acervorum.

В SDS агенты выполняют дешевые частичные оценки гипотезы (возможные решения проблемы поиска). Затем они обмениваются информацией о гипотезах (распространение информации) посредством прямого общения один на один. В результате механизма диффузии высококачественные решения могут быть определены из кластеров агентов с одной и той же гипотезой. Работу SDS легче всего понять с помощью простой аналогии - The Restaurant Game.

Ресторанная игра

Группа делегатов на длительной конференции в незнакомом городе. Каждую ночь каждый делегат должен найти, где пообедать. Есть большой выбор ресторанов, каждый из которых предлагает большой выбор блюд. Проблема, с которой сталкивается группа, состоит в том, чтобы найти лучший ресторан, то есть ресторан, в котором пообедало бы максимальное количество делегатов. Даже параллельный исчерпывающий поиск по комбинациям ресторанов и блюд потребует слишком много времени. Для решения проблемы делегаты решают использовать стохастический диффузионный поиск.

Каждый делегат действует как агент, поддерживающий гипотезу о лучшем ресторане в городе. Каждую ночь каждый делегат проверяет свою гипотезу, обедая там и случайным образом выбирая одно из предложенных блюд. На следующее утро за завтраком каждый делегат, который не получил удовольствия от еды накануне вечером, просит одного случайно выбранного коллегу поделиться своими впечатлениями от ужина. Если впечатления были хорошими, он также выбирает этот ресторан. В противном случае он просто выбирает наугад другой ресторан из тех, что перечислены в «Желтых страницах». Используя эту стратегию, выяснилось, что очень быстро значительное количество делегатов собираются вокруг «лучшего» ресторана в городе.

Приложения

SDS применялся для решения различных задач, таких как текстовый поиск [Bishop, 1989], распознавание объектов [Bishop, 1992], отслеживание функций [Grech-Cini, 1993], самоопределение мобильного робота [Beattie, 1998] и выбор места для беспроводной связи. сети [Whitaker, 2002].

Анализ

В отличие от многих техник поиска, вдохновленных природой, существует исчерпывающая математическая структура, описывающая поведение SDS. Анализ SDS исследовал ее глобальную оптимальность и сходимость [Nasuto, 1998], линейную временную сложность [Nasuto et al., 1999], надежность [Myatt, 2004] и распределение ресурсов [Nasuto, 1999] при различных условиях поиска.

Рекомендации

  • Бишоп, Дж. М., (1989). Стохастические поисковые сети. Proc. 1-я конференция IEE Conf. по искусственным нейронным сетям, стр. 329–331, Лондон.
  • Бишоп, Дж. М. и Торр, П. (1992). Стохастическая поисковая сеть. В R. Linggard, D.J. Майерс, К. Найтингейл (ред.), Нейронные сети для изображений, речи и естественного языка, стр. 370–387, Нью-Йорк, Chapman & Hall.
  • Битти, П. И Бишоп, Дж. М., (1998). Самолокация в автономной инвалидной коляске Senario. Журнал интеллектуальных и роботизированных систем 22, стр. 255–267, Kluwer Academic Publishers.
  • Греч-Чини, Х.Дж. и Макки, Г.Т. (1993) Расположение области рта на изображениях человеческих лиц. В P.S.Schenker (Ed.), Proceedings of SPIE - International Society for Optical Engineering, Sensor Fusion VI 2059, Massachusetts.
  • Мятт, Д.Р., Бишоп Дж. М. и Насуто, С. Дж. (2004). Минимальные критерии стабильной сходимости для поиска стохастической диффузии Будут опубликованы в Electronics Letters.
  • Насуто, С.Дж., (1999). Анализ распределения ресурсов стохастического диффузионного поиска. Кандидатская диссертация. Университет Рединга, Великобритания.
  • Насуто, С.Дж. И Бишоп, Дж. М., (1999). Анализ сходимости стохастического диффузионного поиска. Журнал параллельных алгоритмов и приложений 14: 2, стр. 89–107.
  • Насуто, С.Дж., Бишоп, Дж. М. и Лаурия, Л. (1998). Временная сложность поиска стохастической диффузии. Neural Computation '98, Вена, Австрия.
  • Уитакер, Р.М., Херли, С. (2002). Агентный подход к выбору места для беспроводных сетей. Proc ACM Симпозиум по прикладным вычислениям (Мадрид). 574–577.
  • Джонс, Д. (2002). Ограниченный стохастический поиск диффузии. SCARP 2002, Университет Рединга, Великобритания.