Презентация по математике "Муравьиные алгоритмы" - скачать

Август 27, 2022

Главная
Математика
Презентация по математике "Муравьиные алгоритмы" - скачать

Содержание

2. САМООРГАНИЗАЦИЯ Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность;
3. При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути.
4. ОБОБЩЁННЫЙ АЛГОРИТМ • ПОКА (условия выхода не выполнены) 1. Создание муравьёв 2. Поиск решения 3. Обновление
5. ПОИСК РЕШЕНИЯ
6. ОБНОВЛЕНИЕ ФЕРОМОНА
7. ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ПРИ ПОМОЩИ МУРАВЬИНЫХ АЛГОРИТМОВ 1. Представить задачу в виде набора компонент (вершин) и
8. ПРИМЕНЕНИЕ ACO ДЛЯ ЗАДАЧИ КОММИВОЯЖЁРА
9. СОЗДАНИЕ МУРАВЬЕВ Общее количество муравьёв равно количеству городов; каждый муравей начинает маршрут из своего города; изначально
10. ПОИСК РЕШЕНИЯ
11. ОБНОВЛЕНИЕ ФЕРОМОНА
12. ОБНОВЛЕНИЕ ФЕРОМОНА
13. МОДИФИКАЦИИ АЛГОРИТМОВ ACO
14. МОДИФИКАЦИИ АЛГОРИТМОВ ACO Модифицированная муравьиная система Ant Colony System Три основных изменения: уровень феромонов на ребрах
15. МОДИФИКАЦИИ АЛГОРИТМОВ ACO Муравьиная система Max-min Max-min Ant System Суть: ограничение на максимальную и минимальную концентрацию
16. МОДИФИКАЦИИ АЛГОРИТМОВ ACO Муравьиная система с ранжированием AS-rank Суть: в конце каждой итерации муравьи ранжируются в
17. ПРИМЕР
18. ИТЕРАЦИЯ 1
19. ИТЕРАЦИЯ 1
20. ИТЕРАЦИЯ 1
22. Скачать презентацию

Слайд 2

САМООРГАНИЗАЦИЯ
Основу поведения муравьиной колонии составляет самоорганизация.
Самоорганизация является результатом взаимодействия следующих четырех

компонентов:
- случайность;
- многократность;
- положительная обратная связь;
- отрицательная обратная связь.

Слайд 3

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

другими муравьями для выбора пути.

Слайд 4

ОБОБЩЁННЫЙ АЛГОРИТМ
• ПОКА (условия выхода не выполнены)
1. Создание муравьёв
2.

Поиск решения
3. Обновление феромонов
4. Дополнительные действия {опционально}

Слайд 5

ПОИСК РЕШЕНИЯ

Слайд 6

ОБНОВЛЕНИЕ ФЕРОМОНА

Слайд 7

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ПРИ ПОМОЩИ МУРАВЬИНЫХ АЛГОРИТМОВ
1. Представить задачу в виде

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

Слайд 8

ПРИМЕНЕНИЕ ACO ДЛЯ ЗАДАЧИ КОММИВОЯЖЁРА

Слайд 9

СОЗДАНИЕ МУРАВЬЕВ
Общее количество муравьёв равно количеству городов;
каждый муравей начинает маршрут из

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

Слайд 10

ПОИСК РЕШЕНИЯ

Слайд 11

ОБНОВЛЕНИЕ ФЕРОМОНА

Слайд 12

ОБНОВЛЕНИЕ ФЕРОМОНА

Слайд 13

МОДИФИКАЦИИ АЛГОРИТМОВ ACO

Слайд 14

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Модифицированная муравьиная система Ant Colony System
Три основных изменения:
уровень феромонов

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

Слайд 15

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Муравьиная система Max-min Max-min Ant System
Суть: ограничение на максимальную

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

Слайд 16

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Муравьиная система с ранжированием AS-rank
Суть: в конце каждой итерации

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

Слайд 17

ПРИМЕР

Слайд 18

ИТЕРАЦИЯ 1

Слайд 19

ИТЕРАЦИЯ 1

Слайд 20

Презентация по математике "Муравьиные алгоритмы" - скачать

Содержание

САМООРГАНИЗАЦИЯОснову поведения муравьиной колонии составляет самоорганизация.Самоорганизация является результатом взаимодействия следующих четырех

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

ОБОБЩЁННЫЙ АЛГОРИТМ• ПОКА (условия выхода не выполнены) 1. Создание муравьёв 2.

ПОИСК РЕШЕНИЯ

ОБНОВЛЕНИЕ ФЕРОМОНА

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ПРИ ПОМОЩИ МУРАВЬИНЫХ АЛГОРИТМОВ1. Представить задачу в виде

ПРИМЕНЕНИЕ ACO ДЛЯ ЗАДАЧИ КОММИВОЯЖЁРА

СОЗДАНИЕ МУРАВЬЕВОбщее количество муравьёв равно количеству городов;каждый муравей начинает маршрут из

ПОИСК РЕШЕНИЯ

ОБНОВЛЕНИЕ ФЕРОМОНА

ОБНОВЛЕНИЕ ФЕРОМОНА

МОДИФИКАЦИИ АЛГОРИТМОВ ACO

МОДИФИКАЦИИ АЛГОРИТМОВ ACOМодифицированная муравьиная система Ant Colony SystemТри основных изменения:уровень феромонов

МОДИФИКАЦИИ АЛГОРИТМОВ ACOМуравьиная система Max-min Max-min Ant SystemСуть: ограничение на максимальную

МОДИФИКАЦИИ АЛГОРИТМОВ ACOМуравьиная система с ранжированием AS-rankСуть: в конце каждой итерации

ПРИМЕР

ИТЕРАЦИЯ 1

ИТЕРАЦИЯ 1

ИТЕРАЦИЯ 1

Похожие презентации

САМООРГАНИЗАЦИЯ
Основу поведения муравьиной колонии составляет самоорганизация.
Самоорганизация является результатом взаимодействия следующих четырех

ОБОБЩЁННЫЙ АЛГОРИТМ
• ПОКА (условия выхода не выполнены)
1. Создание муравьёв
2.

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ПРИ ПОМОЩИ МУРАВЬИНЫХ АЛГОРИТМОВ
1. Представить задачу в виде

СОЗДАНИЕ МУРАВЬЕВ
Общее количество муравьёв равно количеству городов;
каждый муравей начинает маршрут из

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Модифицированная муравьиная система Ant Colony System
Три основных изменения:
уровень феромонов

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Муравьиная система Max-min Max-min Ant System
Суть: ограничение на максимальную

МОДИФИКАЦИИ АЛГОРИТМОВ ACO
Муравьиная система с ранжированием AS-rank
Суть: в конце каждой итерации