СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ. - презентация

1 СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ

2 Схема работы метода муравьиных колоний

3 Метод муравьиных систем (AS) плотностный; количественный; циклический. Правило выбора следующей грани: Правило обновления феромонов:

4 Элитная стратегия основывается на дополнительном увеличении количества феромонов для лучшего глобального пути в данный момент времени t. Таким образом, процедура добавления феромона для дуг, которые входят лучший на данный момент времени путь, выполняется повторно, при этом количество добавляемого феромона рассчитывается в соответствии с длиной лучшего пути.

5 Метод муравьиных систем, основанный на ранжировании (AS rank ) Правило обновления феромонов: агенты сортируются по длине составленных ими путей, после чего на глобально лучшем пути феромоны увеличиваются с весом w; и производится увеличение феромонов для дуг, вошедших в пути (w–1) лучших агентов; при этом k-ый лучший агент будет добавлять феромон с весом (w–k)

6 Метод муравьиных колоний (ACS) Правило обновления феромонов: использование строгой элитной стратегии при обновлении феромонов на гранях ; использование псевдослучайного пропорционального правила.

7 Макси-минный метод муравьиных систем (MMAS) использование строгой элитной стратегии при обновлении феромонов на гранях ; вводит нижнюю и верхнюю границу для возможных значений феромонов на грани: min ru max ru.

8 КритерийASAS rank ACSMMAS Добавление феромонов Осуществляется после получения решения Происходит в процессе составления решения Применение элитной стратегии Все агенты участвуют в обновлении путей Обновление выполняют (w-1) локально лучших агентов и глобально лучший агент Обновление выполняет только лучший (глобально или локально) агент Другие особенности –– Используется псевдо- случайное пропорциональное правило Используется интервал значений феромонов Различия между разновидностями метода муравьиных колоний