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

Содержание

• 
  Слайд 1

  Муравьиные алгоритмыAntColonyoptimization

• 
  Слайд 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
  

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

• 
  Слайд 15
  

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

• 
  Слайд 16
  

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

• 
  Слайд 17

  Пример

• 
  Слайд 18

  Итерация 1

• 
  Слайд 19
  
• 
  Слайд 20
  
• 
  Слайд 21