Презентация "Муравьиные алгоритмы" по математике – проект, доклад

Муравьиные алгоритмы Ant C olony optimization

самоорганизация

Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность; - многократность; - положительная обратная связь; - отрицательная обратная связь.

При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути.

Обобщённый алгоритм

• ПОКА (условия выхода не выполнены) 1. Создание муравьёв 2. Поиск решения 3. Обновление феромонов 4. Дополнительные действия {опционально}

Поиск решения

Обновление феромона

Этапы решения задачи при помощи муравьиных алгоритмов

1. Представить задачу в виде набора компонент (вершин) и переходов (ребер) или набором взвешенных графов, на которых муравьи могут строить решения. 2. Определить эвристику поведения муравья при построении решения (определение вероятностей переходов – (1)). 3. Определить значение следа феромона (соотношение (2)). 4. Определить процедуру эффективного локального поиска (если возможно). 5. Подобрать параметры ACO–алгоритма

Применение ACO для задачи коммивояжёра

Создание муравьев

Общее количество муравьёв равно количеству городов; каждый муравей начинает маршрут из своего города; изначально количества феромона на рёбрах принимается равным небольшому положительному числу.

МОДИФИКАЦИИ Алгоритмов ACO

Модифицированная муравьиная система Ant Colony System Три основных изменения: уровень феромонов на ребрах обновляется не только в конце очередной итерации, но и при каждом переходе муравьев из узла в узел. в конце итерации уровень феромонов повышается только на кратчайшем из найденных путей. алгоритм использует измененное правило перехода: либо, с определенной долей вероятности, муравей безусловно выбирает лучшее – в соответствие с длиной и уровнем феромонов – ребро, либо производит выбор так же, как и в классическом алгоритме.

Муравьиная система Max-min Max-min Ant System Суть: ограничение на максимальную и минимальную концентрацию феромонов на ребрах  эффективная защита от преждевременной сходимости к субоптимальным решениям.

Муравьиная система с ранжированием AS-rank Суть: в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции.

Пример

Итерация 1