Міністерство освіти Російської Федерації
Кафедра алгебри і математичної логіки
РЕФЕРАТ
на тему В«Алгоритм мурашкиВ»
2009
Зміст
Введення.
1 Ідея алгоритму.
2 Покроковий опис загальної схеми
3 Мураха
4 Початкова популяція
5 Рух мурашки
6 Подорож мурахи
7 Випаровування ферменту
8 Повторний запуск
9 Блок-схема алгоритму
10 Демонстраційний приклад
11 Характерні особливості
12 Області застосування
Висновок
Список літератури
Введення
Кожен, хто хоч раз в житті спостерігав за мурахами, обов'язково повинен був помітити: вся діяльність цих комах має яскраво виражену групову забарвлення. Працюючи разом, група мурах здатна затягнути в мурашник шматок їжі або будівельного матеріалу, в 10 разів більше них самих. Організацію мурашок можна застосовувати і людям у вирішенні деяких завдань. Сам по собі мураха - достатньо примітивна істота. Всі його дії, по суті, зводяться до елементарних інстинктивним реакціям на навколишнє оточення і своїх побратимів. Однак кілька мурашок разом утворюють складну систему. Наприклад, група мурах прекрасно вміє знаходити найкоротшу дорогу до їжі. Якщо яке-небудь перешкода - палиця, камінь, нога людини - встає на шляху, вони швидко знаходять новий оптимальний маршрут. Мурахи вирішують проблеми пошуку шляхів за допомогою хімічної регуляції. Кожна мураха виділяє феромони, і їх слід утворює, таким чином, шлях мурашки. Інший мураха, зачувши слід на землі, спрямовується по ньому. Чим більше по одному шляху пройшло мурах - тим явнее слід, а ніж явнее слід - тим більший В«бажанняВ» піти в ту ж сторону виникає у мурашок. Оскільки мурахи, що знайшли найкоротший шлях до мети, витрачають менше часу на шлях туди і назад, їх слід швидко стає найбільш помітним. Він приваблює більше число мурашок, і коло замикається. Решта шляху - менш використовувані - Потихеньку пропадають. Алгоритми мурахи (Ant algorithms), або оптимізація по принципом мурашиної колонії (це назва була придумана винахідником алгоритму, Марко Доріго (Marco Dorigo)), засновані на застосуванні декількох агентів і володіють специфічними властивостями, притаманними мурашкам, і використовують їх для орієнтації у фізичному просторі. Алгоритми мурашки особливо цікаві тому, що їх можна використовувати для вирішення не тільки статичних, але і динамічних проблем, наприклад, у змінюються мережах.
Ми розглянемо загальний випадок алгоритму мурашиної колонії.
1. Ідея алгоритму
Два мурахи з мурашника повинні дістатися до їжі, яка знаходиться за перешкодою. Під час переміщення кожен мураха виділяє трохи феромона, використовуючи його в якості маркера.
Рис. 1.
За інших рівних кожен мураха вибере свій шлях. Перший мураха вибирає верхній шлях, а другий - нижній. Так як нижній шлях в два рази коротше верхнього, другий мураха досягне мети за час t 1 . Перший мураха в цей момент пройде тільки половину шляху (рис. 2).
Коли одна мураха досягає їжі, він бере один з об'єктів і повертається до мурашника по тому ж шляху. За час t 2 другий мураха повернувся в мурашник з їжею, а перший мураха досяг їжі (рис. 3).
При переміщенні кожного мураху на шляху залишається небагато феромона. Для першого мурашки за час t 0 t 2 шлях був покритий феромонами тільки один раз. У той же самий час другої мураха покрив шлях феромонами двічі. За час t 4 перший мураха повернувся в мурашник, а другий мураха вже встиг ще раз сходити до їжі і повернутися. При цьому концентрація феромона на нижньому шляху буде в два рази вище, ніж на верхньому. Тому перший мураха наступного разу вибере нижній шлях, оскільки там концентрація феромона вище.
Рис. 2. Рис. 3.
У цьому і полягає базова ідея алгоритму мурахи - оптимізація шляхом непрямої зв'язку між автономними агентами.
2. Покроковий опис загальної схеми
Припустимо, що навколишнє середовище для мурашок являє собою повний неорієнтовані граф. Кожне ребро має вагу, що позначається як відстань між двома вершинами, сполученими ім. Граф двонаправлений, тому мураха може подорожувати по грані в будь-якому напрямку (рис. 4).
Рис. 4.
Вірогідність включення ребра в маршрут окремого мурашки пропорційна кількості феромонів на цьому ребрі, а кількість відкладали феромона пропорційно довжині маршруту. Чим коротше маршрут тим більше феромона буде відкладено на його ребрах, отже, більшу кількість мурах буде включати його в синтез власних маршрутів. Моделювання такого підходу, що використовує лише позитивний зворотний зв'язок, призводить до передчасної збіжності - більшість мурашок рухається по локально-оптимальним маршрутом. Уникнути цього можна моделюючи негативно зворотний зв'язок у вигляді випаровування феромону. Причому, якщо феромон випаровується швидко, то це призводить до втрати пам'яті колонії і забування хороших рішень, з іншого боку, великий час випарів може призвести до отримання стійкого локального оптимального рішення.
3. Мураха
Мураха - це програмний агент, який є членом великої колонії і використовується для вирішення якої-небудь проблеми. Мураха забезпечується набором простих правил, які дозволяють йому вибирати шлях в графі. Він підтримує список вузлів, які він вже відвідав. Таким чином, мураха повинен проходити через кожний вузол тільки один раз. Шлях між двома вузлами графа, по якому мураха відвідав кожен вузол тільки один раз, називається шляхом Гамільтона, по імені математика сера Вільяма Гамільтона.
Вузли в списку "Поточного подорожі" розташовуються в тому порядку, в якому мураха відвідував їх. Пізніше список використовується для визначення протяжності шляху між вузлами. Справжній мураха під час переміщення по шляху буде залишати за собою феромони. В алгоритмі мурашки агент залишає феромони на ребрах графа після завершення подорожі.
Стартова точка, куди поміщається мураха, залежить від обмежень, що накладаються умовами задачі, так як для кожного завдання спосіб розміщення мурашок є визначальним. Або всі вони поміщаються в одну точку, або в різні з повтореннями, або без повторень.
На цьому ж етапі задається початковий рівень феромону. Він ініціалізується невеликим позитивним числом для того, щоб на початковому кроці ймовірності переходу в наступну вершину не були нульовими.
4. Початкова популяція
Після створення популяція мурашок порівну розподіляється по вузлах мережі. Необхідно рівне поділ мурах між вузлами, щоб всі вузли мали однакові шанси стати відправною точкою. Якщо всі мурашки почнуть рух з однієї точки, це буде означати, що дана точка є оптимальною для старту, а насправді ми цього не знаємо.
5. Рух мурашки
Рух мурашки грунтується на одному і дуже простому вероятностном рівнянні. Якщо мураха ще не закінчив шлях, тобто не відвідав всі вузли мережі, для визначення наступної грані шляху використовується рівняння:
(2.1)
Тут - Інтенсивність ферменту на межі між вузлами r і u, -Функція, яка представляє вимір зворотного відстані для грані, a -Вага ферменту, а b-коефіцієнт евристики. Параметри a і b визначають відносну значимість двох параметрів, а також їх вплив на рівняння. Згадайте, що мураха подорожує тільки по вузлах, які ще не були відвідані (як зазначено списком ...
