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


Покроковий опис загальної схеми



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

Покроковий опис загальної схеми


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

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

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

Мураха


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

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

Стартова точка, куди поміщається мураха, залежить від обмежень, накладених умовами завдання, оскільки для кожного завдання спосіб розміщення мурашок є визначальним. Або всі вони поміщаються в одну точку, або в різні з повтореннями, або без повторень.

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


Рух мурашки


Рух мурашки ґрунтується на простому ймовірнісному рівнянні. Якщо мураха ще не закінчила шлях, тобто не відвідала усі вузли мережі, для визначення наступного ребра шляху використовується рівняння

(1)

Тут  (r,u) - інтенсивність ферменту на ребрі між вузлами r і u, η (r, u) - функція, яка представляє вимір зворотньої відстані для грані, α - вага ферменту, a β - коефіцієнт евристики. Параметри α і β визначають відносну значимість двох параметрів, а також їх вплив на рівняння. Оскільки мураха подорожує тільки по вузлах, які ще не були відвідані (як зазначено списком табу), ймовірність обчислюється лише для ребер, які ведуть до ще не відвіданих вузлів. Ці ребра представляє змінна k.



Каталог: 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
звернутися до адміністрації

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