_

Вопрос 42: Алгоритмы, вдохновленные живой природой

Все алгоритмы, вдохновленные живой природой относятся к классу эвристических алгоритмов (heuristic algorithms), то есть алгоритмов, для которых сходимость к глобальному решению не доказана, но экспериментально установлено, что в большинстве случаев они дают достаточно хорошее решение. В качестве общего названия членов популяции используем термин агент (agent). В различных популяционных алгоритмах агенты называются индивидами, особями и т.д. Общая схема популяционных алгоритмов включает в себя следующие этапы:

1. Инициализация популяции. В области поиска тем или иным образом создаем некоторое число начальных приближений к искомому решению задачи – инициализируем популяцию агентов.
2. Миграция агентов популяции. С помощью некоторого набора миграционных операторов, специфических для каждого из популяционных алгоритмов, перемещаем агентов в области поиска таким образом, чтобы в конечном счете приблизиться к искомому экстремуму оптимизируемой функции.
3. Завершение поиска. Проверяем выполнение условий окончания итераций, и если они выполнены, завершаем вычисления, принимая лучшее изнайденных по ложений агентов популяции за приближенное решение задачи. Если указанные условия не выполнены, возвращаемся к выполнению этапа 2.

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

Миграцию агентов, например, в генетическом алгоритме, который мы так же относим к популяционным алгоритмам, реализуют генетические операторы скрещивания, мутации и другие.

В качестве условия окончания поиска используют, как правило, условие достижения заданного числа итераций (поколений). Часто используют также условие стагнации(stagnation) алгоритма, когда лучшее достигнутое значение оптимизируемой функции не изменяется втечение заданного числа поколений. Могут быть использованы и другие условия, например, условие исчерпания времени, отпущенного на решение задачи.

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

Агенты популяции обладают следующими основными свойствами.

• Автономность – агенты движутся впространстве поиска, хотябы частично, независимо друг от друга.
• Стохастичность – процесс миграции агентов содержит случайную компоненту.
• Ограниченность представления – каждый из агентов популяции обладает информацией лишь обисследуемой им части области поиска и, быть может, об окружении некоторых других агентов.
• Децентрализация – отсутствие агентов, управляющих процессом поиска вцелом.
• Коммуникабельность – агенты тем или иным способом могут обмениваться между собой информацией о топологии (ландшафте) оптимизируемой функции, выявленной в процессе исследования своей части области поиска.

Даже если стратегия поведения каждого из агентов популяции достаточно проста, указанные свойства агентов обеспечивают формирование так называемого роевого интеллекта (swarm intelligence) популяции, проявляющегося в самоорганизации и сложном поведении популяции в целом.

К числу алгоритмов, вдохновленнх природой, относят: алгоритм светлячков, сорняковый алгоритм, кукушкин поиск, обезьяний алгоритм, поиск косяком рыб, алгоритм, инспирированный летучими мышами.