Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Методы роевого интеллекта Методы роевого интеллекта - общее название класса алгоритмов, описывающих поведение децентрализованной самоорганизующейся системы. Термин был введён Херардо Бени и Ван Цзином в 1989 г., в контексте системы клеточных роботов [6]. Методы роевого интеллекта являются алгоритмами, использующими стратегии эволюционного моделирования и принципы природных механизмов принятия решений. Он включает в себя муравьиные алгоритмы, пчелиные алгоритмы, метод роя частиц и др. Системы роевого интеллекта, как правило, состоят из множества агентов (бондов) локально взаимодействующих между собой и с окружающей средой. Каждый боид следует очень простым правилам и, несмотря на то, что нет какой- то централизованной системы управления поведения, которая бы указывала каждому из них на то, что ему следует делать, локальные и, в некоторой степени, случайные взаимодействия приводят к возникновению интеллек­ туального глобального поведения, неконтролируемого отдельными бондами. Существует также огромное количество других алгоритмов, основанных на методах роевого интеллекта, однако наибольшую известность получили вышеперечисленные. Муравьиный алгоритм Муравьиные алгоритмы (Ant colony optimization, АСО) представляют собой вероятностную жадную эвристику, где вероятности устанавливаются, исходя из информации о качестве решения, полученного из предыдущих решений [7]. Муравьи относятся к социальным насекомым, живущим внутри некоторого коллектива - колонии. Основу «социального» поведения муравьев составляет самоорганизация - множество динамических механизмов, обеспечи­ вающих достижение системой глобальной цели в результате низкоуровневого взаимодействия её элементов. Принципиальной особенностью такого взаимодействия является использование элементами системы только локальной информации. При этом исключается любое централизованное управление. В сравнении с генетическими алгоритмами муравьиные алгоритмы имеют некоторые преимущества: опираются на память всей колонии вместо памяти только о предыдущем поколении и меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии). Ряд экспериментов показывает, что эффективность муравьиных алгоритмов растёт с ростом размерности решаемых задач оптимизации и для нестационарных систем с изменяемыми во времени параметрами. Важным свойством муравьиных алгоритмов является неконвергентность: даже после большого числа итераций одновременно исследуется множество вариантов решения, что частично решает проблемы предварительной сходи­ мости. Перспективным путями улучшения муравьиных алгоритмов являются их гибридизация с другими методами природных вычислений, например, гене­ тическими алгоритмами [8]. Гибридизация может осуществляться по островной схеме, когда различные алгоритмы решают задачу параллельно и автономно, или по принципу «мастер-подмастерье» когда основной алгоритм - «мастер» - передаёт решение типовых подзадач «подмастерью». 65