151
“Young Scientist”
. # 4 (138)
. January 2017
Computer Science
4. Вспомогательные действия (не обязательно).
Далее рассмотрим каждый шаг подробнее:
1. Создание агентов:
— Начальное расположение,
где размещается агент, зависит от начальных условий и ограничений задачи. Агенты
могут или быть в одной точке, или в разных с повторениями, или в разных без повторений;
— Также указывается первоначальное
значение феромона, чтобы значения не были нулевыми.
2. Поиск подходящего решения:
— Вероятность того, что произойдет переход из вершины
i в
j, можно определить по формуле:
,
где τ
ij
(t) — уровень феромона, d
ij
— эвристическое расстояние,
— константные параметры.
— Если = 0, с большей вероятностью выберется ближайший город;
— Если = 0, выбор будет
основываться лишь на феромоне;
Необходим найденный экспериментальным способом компромисс между этими двумя величинами
3. Изменение феромона
— Уровень феромона изменяется по формуле:
,
где
𝝆 — интенсивность испарения,
L
k
(t) — цена текущего решения
k-го муравья,
Q —
параметр, который имеет
значение порядка цены оптимального решения,
— феромон, который откладывается
k-м муравьем,
который ис-
пользует ребро.
4. Вспомогательные действия: в основном используют алгоритмы локального поиска.
Алгоритм искусственной пчелиной колонии
Алгоритм искусственной пчелиной колонии (далее, пчелиный алгоритм) λ алгоритм роевого интеллекта, основан на
имитации поведения колонии пчел, может использоваться в задачах оптимизации. Необходимым
условием для его при-
менения является наличие некоторого топологического расстояния ли его аналога на области решений.
Для сбора нектара в пчелиной колонии применяется два вида пчел: пчелы-разведчики и пчелы-рабочие. Первые про-
водят исследование территории, окружающей улей, на предмет наличия нектара. По возвращении в улей, пчелы-раз-
ведчики сообщают информацию о
количестве нектара, направлении его расположения и расстоянии до него. Далее, в
наиболее подходящие области вылетают рабочие, причем, чем больше нектара в данной области, тем больше пчел вы-
летает в нее. Кроме сбора меда, в их задачу входит обновление информации о данной и близлежащих областях.
Искусственная колония использует алгоритм схожий с добычей нектара медоносными пчелами.
Вместо поля с цве-
тами рассмотрим область решений. Вместо нектара используем критерии задачи оптимизации, целевую функцию. На
каждой итерации алгоритма выбирается nb областей с лучшим значением целевой функции, они называются «лучшие»,
из оставшихся выбирается еще ng лучших, называемых «перспективными». Можно задать определенное минимальное
расстояние между двумя соседними областями. В этом случае, при возникновении наложения, область с худшим значе-
нием целевой функции отсекается. Вместо нее выбирается другая область. Данные области запоминаются и при следу-
ющей итерации в них посылается определенное количество пчел.
Схема описанного алгоритма представлена на рис. 5.
Работу алгоритма можно разбить на два этапа:
1. Инициализация
— При инициализации для n разведчиков генерируются начальные положения.
— В простейшем случае используется метод случайного перебора.
2.
Локальный поиск