Презентация на тему Муравьиные алгоритмы

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

отрицательная обратная связь.

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

Создание муравьёв
2. Поиск решения
3. Обновление феромонов
4.

Дополнительные действия {опционально}

задачу в виде набора компонент (вершин) и переходов (ребер)

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

начинает маршрут из своего города;

изначально количества феромона на рёбрах

принимается равным небольшому положительному числу.
 

основных изменения:
уровень феромонов на ребрах обновляется не только в

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

Ant System

Суть: ограничение на максимальную и минимальную концентрацию феромонов

на ребрах  эффективная защита от преждевременной сходимости к субоптимальным решениям.

в конце каждой итерации муравьи ранжируются в соответствие с

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