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

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

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

• 1 Ресторанная игра
• 2 Приложения
• 3 Анализ
• 4 ссылки

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

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

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

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

• Бишоп, JM (1989). «Стохастические поисковые сети» (PDF). Proc. 1-я конференция IEE Conf. по искусственным нейронным сетям. Лондон: 329–331.
• Бишоп, Дж. М. и Торр, П. (1992). Стохастическая поисковая сеть. В R. Linggard, DJ Myers, C. Nightingale (ред.), Neural Networks for Images, Speech and Natural Language, стр. 370–387, Нью-Йорк, Chapman amp; Hall.
• Битти, PD amp; Bishop, JM, (1998). Самолокация в автономной инвалидной коляске Senario. Журнал интеллектуальных и роботизированных систем 22, стр 255–267, Kluwer Academic Publishers.
• Греч-Чини, HJ и McKee, GT (1993) Определение местоположения области рта на изображениях человеческих лиц. В PSSchenker (Ed.), Proceedings of SPIE - The International Society for Optical Engineering, Sensor Fusion VI 2059, Massachusetts.
• Мятт, Д. Р., Епископ Дж. М. и Насуто, С. Дж. (2004). Минимальные критерии стабильной сходимости для поиска по стохастической диффузии Будут опубликованы в Electronics Letters.
• Насуто, SJ, (1999). Анализ распределения ресурсов стохастического диффузионного поиска. Кандидатская диссертация. Университет Рединга, Великобритания.
• Насуто, SJ и Бишоп, JM, (1999). Анализ сходимости стохастического диффузионного поиска. Журнал параллельных алгоритмов и приложений 14: 2, стр. 89–107.
• Насуто, С.Дж., Бишоп, Д.М. и Лаурия, Л. (1998). Временная сложность поиска стохастической диффузии. Neural Computation '98, Вена, Австрия.
• Уитакер, Р.М., Херли, С. (2002). Агентный подход к выбору места для беспроводных сетей. Proc ACM Симпозиум по прикладным вычислениям (Мадрид). 574–577.
• Джонс, Д. (2002). Ограниченный стохастический диффузионный поиск. SCARP 2002, Университет Рединга, Великобритания.