Презентация на тему: Муравьиные алгоритмы
Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность; - многократность; - положительная обратная связь; - отрицательная обратная связь.
При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути.
• ПОКА (условия выхода не выполнены) 1. Создание муравьёв 2. Поиск решения 3. Обновление феромонов 4. Дополнительные действия {опционально}
1. Представить задачу в виде набора компонент (вершин) и переходов (ребер) или набором взвешенных графов, на которых муравьи могут строить решения. 2. Определить эвристику поведения муравья при построении решения (определение вероятностей переходов – (1)). 3. Определить значение следа феромона (соотношение (2)). 4. Определить процедуру эффективного локального поиска (если возможно). 5. Подобрать параметры ACO–алгоритма
Общее количество муравьёв равно количеству городов; каждый муравей начинает маршрут из своего города; изначально количества феромона на рёбрах принимается равным небольшому положительному числу.
Модифицированная муравьиная система Ant Colony System Три основных изменения: уровень феромонов на ребрах обновляется не только в конце очередной итерации, но и при каждом переходе муравьев из узла в узел. в конце итерации уровень феромонов повышается только на кратчайшем из найденных путей. алгоритм использует измененное правило перехода: либо, с определенной долей вероятности, муравей безусловно выбирает лучшее – в соответствие с длиной и уровнем феромонов – ребро, либо производит выбор так же, как и в классическом алгоритме.
Муравьиная система Max-min Max-min Ant System Суть: ограничение на максимальную и минимальную концентрацию феромонов на ребрах эффективная защита от преждевременной сходимости к субоптимальным решениям.
Муравьиная система с ранжированием AS-rank Суть: в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции.
