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

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

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

Игра «Ресторан»

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

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

Приложения

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

Анализ

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

Ссылки

• Бишоп, Дж. М. (1989). «Стохастические поисковые сети» (PDF) . Учеб. 1-я конференция IEE. по искусственным нейронным сетям . Лондон: 329–331.
• Бишоп Дж. М. и Торр П. (1992). Стохастическая поисковая сеть . В Р. Линггарде, DJ Майерсе, К. Найтингейле (ред.), Нейронные сети для изображений, речи и естественного языка, стр. 370–387, Нью-Йорк, Chapman & Hall.
• Битти, П.Д. и Бишоп, Дж.М. (1998). Самолокализация в автономной инвалидной коляске «Сенарио» . Журнал интеллектуальных и робототехнических систем 22, стр. 255–267, Kluwer Academic Publishers.
• Греч-Чини, Х.Дж. и Макки, Г.Т. (1993) Обнаружение области рта на изображениях человеческих лиц . В П.Сшенкере (ред.), Труды SPIE – Международного общества оптической инженерии, Sensor Fusion VI, 2059, Массачусетс.
• Мятт, Д.Р., Бишоп Дж.М. и Насуто, С.Дж. (2004). Минимальные устойчивые критерии сходимости для стохастического диффузионного поиска. Будет опубликовано в Electronics Letters.
• Насуто, SJ (1999). Анализ распределения ресурсов стохастического диффузионного поиска. Кандидатская диссертация. Университет Рединга, Великобритания.
• Насуто, С.Дж. и Бишоп, Дж.М. (1999). Анализ сходимости стохастического диффузионного поиска. Журнал параллельных алгоритмов и приложений 14:2, стр. 89–107.
• Насуто, С. Дж., Бишоп, Дж. М. и Лаурия, Л. (1998). Временная сложность стохастического диффузионного поиска. Нейронные вычисления '98, Вена, Австрия.
• Уитакер Р.М., Херли С. (2002). Агентский подход к выбору места для беспроводных сетей. Симпозиум Proc ACM по прикладным вычислениям (Мадрид). 574–577.
• Джонс, Д. (2002). Ограниченный стохастический диффузионный поиск . SCARP 2002, Университет Рединга, Великобритания.