Тема Мурашині алгоритми



Скачати 189.89 Kb.
Сторінка5/5
Дата конвертації06.11.2017
Розмір189.89 Kb.
1   2   3   4   5

Демонстраційний приклад


Щоб побачити, як працюють рівняння, розберемо функціонування розглянутого вище алгоритму на простому прикладі. Візьмемо простий сценарій з двома мурашками з прикладу яке розглянуто вище.

На рисунку показано приклад з двома ребрами між двома вузлами (V0 і V1). Кожне ребро ініціалізується і має однакові шанси на те, щоб бути обраним.



Два мурахи, що знаходяться у вузлі V0 позначаються як A0 і A1. Оскільки ймовірність вибору будь-якого шляху однакова, в цьому циклі проігноруємо рівняння вибору шляху.

Дані для завдання:


  • Число пройдених кроків: для A0 - 20, для A1 - 10

  • Рівень феромону (Q / пройдена відстань): для A0 - 0.5, A1 - 1.0

  • ρ = 0.6

  • α = 0.3

  • β = 1.0

На наступному рисунку показано, що кожна мураха вибирає свій шлях (мураха A0 йде по верхньому шляху, а мураха A1 - по нижньому). Мураха A0 зробила 20 кроків, а мураха A1, - тільки 10. За рівнянням (2) розраховуємо кількість феромонів, яке має бути "нанесено".

Примітка: Роботу алгоритму можна змінити, якщо перевизначити його параметри (наприклад, α, β або p), наприклад надати більшу вагу феромонам або відстані між вузлами.

Далі за рівнянням (3) обчислюється кількість феромону, яка буде застосовано.

Для мурахи A0 результат становить: 0,1+(0,5*0,6)=0,4

Для мурахи A1 результат становить: 0,1+(0,5*0,6)=0,4

Далі за допомогою рівняння (4) визначається, яка частина феромонів випарується і, відповідно, скільки залишиться. Результати (для кожного шляху відповідно) становлять:

0,4*(1,0-0,6)=0,16

0,7*(1,0-0,6)=0,28

Ці значення представляють нову кількість феромонів для кожного шляху (верхнього і нижнього, відповідно). Тепер перемістимо мурах назад у вузол V0 і скористаємося імовірнісним рівнянням вибору шляху (1), щоб визначити, який шлях повинні вибрати мурахи. Ймовірність того, що мураха вибере верхній шлях (представлений кількістю феромону 0,16), становить:



Ймовірність того, що мураха вибере нижній шлях (представлений кількістю феромону 0,28) становить:



При зіставленні двох ймовірностей обидві мурахи виберуть нижній шлях, який є найбільш оптимальним.


Характерні особливості


Для алгоритму мурашиної колонії необхідно вказати:

  • Закон виділення феромону.

  • Закон випаровування феромону.

  • Кількість агентів.

  • Місця розміщення.

Ці характеристики вибираються з врахуванням особливостей завдання на основі експериментальних досліджень (евристики).

Алгоритм:


  • Реалізує пошук наближених рішень.

  • Має поліноміальну складність.

  • Є одним з видів імовірнісних алгоритмів (закони виділення випаровування - імовірнісні закони).

Області застосування


Алгоритм оптимізації мурашиної колонії може бути успішно застосований для вирішення складних комплексних завдань оптимізації. Мета вирішення складних комплексних завдань оптимізації - пошук і визначення найбільш відповідного рішення для оптимізації (знаходження мінімуму або максимуму) цільової функції (ціни, точності, часу, відстані тощо) з дискретної множини можливих рішень.

Типовими прикладами вирішення такого завдання є задача календарного планування, завдання маршрутизації транспорту, різних мереж (GPRS, телефонні, комп'ютерні тощо), розподіл ресурсів та робіт. Ці задачі виникають у бізнесі, інженерії, виробництві та багатьох інших областях. Дослідження показали, що метод мурашиних колоній може давати результати, навіть кращі ніж при використанні генетичних алгоритмів і нейронних мереж.


Модифікації класичного алгоритму


Результати перших експериментів із застосуванням мурашиного алгоритму для вирішення завдання комівояжера були багатообіцяючими, проте далеко не кращими порівняно з вже існуючими методами. Однак, простота класичного мурашиного алгоритму («мурашиної системи») залишала можливості для доробок - і саме алгоритмічні вдосконалення стали предметом подальших досліджень фахівців у галузі комбінаторної оптимізації. В основному, ці вдосконалення пов'язано з великим використанням історії пошуку та більш ретельним дослідженням областей навколо вже знайдених вдалих рішень.

Elitist Ant System


Введення в алгоритм так званих «елітних мурах». Досвід показує, що проходячи ребра, що входять в короткі шляхи, мурахи з більшою ймовірністю будуть знаходити коротші шляхи. Ефективною стратегією є штучне збільшення рівня феромонів на найвдаліших маршрутах. Для цього на кожній ітерації алгоритму кожна з елітних мурах проходить шлях, який є найкоротшим із знайдених на даний момент.

Експерименти показують, що, до певного рівня, збільшення числа елітних мурах є досить ефективним, дозволяючи значно скоротити число ітерацій алгоритму. Однак, якщо число елітних мурах занадто велике, то алгоритм досить швидко знаходить субоптимальне рішення і застряє в ньому. Як і інші змінні параметри, оптимальне число елітних мурах слід визначати дослідним шляхом.


Ant-Q


Мурашиний алгоритм, який отримав свою назву за аналогією з методом машинного навчання Q-learning. В основі алгоритму лежить ідея про те, що мурашину систему можна інтерпретувати як систему навчання з підкріпленням. Ant-Q підсилює цю аналогію, запозичуючи багато ідей з Q-навчання.

Алгоритм зберігає Q-таблицю, що співставляє кожному з ребер величину, яка визначає «корисність» переходу по цьому ребру. Q-таблиця змінюється в процесі роботи алгоритму - відбувається навчання системи. Значення корисності переходу по ребру обчислюється виходячи із значень корисності переходу за наступними ребрам в результаті попереднього визначення можливих наступних станів. Після кожної ітерації корисності оновлюються виходячи з довжин шляхів, до складу яких було включено відповідні ребра.


Ant Colony System


Для підвищення ефективності в порівнянні з класичним алгоритмом введено три основних зміни.

По-перше, рівень феромонів на ребрах оновлюється не лише в кінці чергової ітерації, але і при кожному переході мурах з вузла у вузол. По-друге, наприкінці ітерації рівень феромонів підвищується тільки на найкоротшому із знайдених шляхів. По-третє, алгоритм використовує змінене правило переходу: або, з певною часткою ймовірності, мураха безумовно вибирає краще ребро у відповідності до довжини і рівня феромонів, або робить вибір так само, як і в класичному алгоритмі.


Max-min Ant System


Мурашиний алгоритм, в якому підвищення концентрації феромонів відбувається тільки на кращих шляхах з пройдених мурахами. Така велика увага до локальних оптимумів компенсується введенням обмежень на максимальну і мінімальну концентрацію феромонів на ребрах, які вкрай ефективно захищають алгоритм від передчасної збіжності до субоптимальних рішень.

На етапі ініціалізації, концентрація феромонів на всіх ребрах встановлюється рівною максимальній. Після кожної ітерації алгоритму тільки одна мураха залишає за собою слід - або найбільш успішна на даній ітерації, або, аналогічно до алгоритму з елітизмом, елітна. Цим досягається, з одного боку, більш ретельне дослідження області пошуку, з іншого - його прискорення.


ASrank


Модифікація класичного мурашиного алгоритму, в якому в кінці кожної ітерації мурахи ранжуються у відповідно до довжин пройдених ними шляхів. Кількість феромонів, що залишається мурахою на ребрах, таким чином, призначається пропорційно до її позиції. Для ретельного дослідження околу вже знайдених вдалих рішень, алгоритм використовує елітних мурах.

Висновок


Ефективність мурашиних алгоритмів порівнянна з ефективністю загальних мета евристичних методів, а в ряді випадків - і з проблемно-орієнтованими методами. Найкращі результати мурашині алгоритми показують для задач з великою розмірністю областей пошуку і можуть бути успішно застосовані для вирішення складних комбінаторних задач оптимізації. Мурашині алгоритми добре підходять для застосування разом з процедурами локального пошуку, дозволяючи швидко знаходити початкові точки для них.

Найбільш перспективними напрямками подальших досліджень у даному напрямку слід вважати аналіз способу вибору параметрів, що налаштовуються в алгоритмах. В останні роки пропонуються різні способи адаптації параметрів алгоритмів «на льоту». Оскільки від вибору параметрів сильно залежить поведінка мурашиних алгоритмів, саме до цієї проблеми звернено найбільшу увагу дослідників на даний момент.
Каталог: html
html -> 7 Периферійні пристрої. Мультимедійні пристрої
html -> 3 Небезпеки для веб-ресурсів
html -> 1 Хмарні технології
html -> Інформації для проекту Мета уроку: засвоєння знань про технологію аналізу та компо­нування інформації для проекту, формування вмінь компонувати інформацію в процесі проектування виробу та складання реферату
html -> 2 Основні об’єкти Інтернету
html -> Методичні вказівки до лабораторної роботи №3 з дисципліни «Веб проектування»
html -> 2 Класифікація комп’ютерів
html -> Тема Комп’ютерні мережі

Скачати 189.89 Kb.

Поділіться з Вашими друзьями:
1   2   3   4   5




База даних захищена авторським правом ©uchika.in.ua 2020
звернутися до адміністрації

    Головна сторінка