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



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

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


http://habrahabr.ru/post/105302/

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

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

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

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

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



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

Ідея алгоритму


Мураха прямує від мурашника (М) у випадковому напрямку. Якщо вона знаходить їжу (Ї), то повертається до мурашника і залишає по собі слід з феромону.

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



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



Базова ідея алгоритму мурахи полягає в оптимізації шляхом непрямого зв'язку між автономними агентами.

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

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

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

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





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

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