Програмне забезпечення інтелектуальних систем:Проект

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Програмне забезпечення інтелектуальних систем:Іспит

Програмне забезпечення інтелектуальних систем:Проект

Команда

Оксана Журавльова
Коля Найчук
Мирослава Ромашевська (генетичні алгоритми)
Крячко Максим (алгоритм мурашки)

Постановка задачі

Задача комівояжера (знайти гамільтонів цикл найменшої вартості).

Використовувані алгоритми

Алгоритм мурашки

Вступ

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

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

Ідея така:

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

В арсеналі мурашок:

їх кількість (популяція)
феромон, який вони розприскують поки ходять
альтернативи руху

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

Математична модель

Кожна мурашка, що перебуває в місті i переходить в місто j, що обирається серед усіх міст, що не були відвідані відповідно цій формулі:

, де:

p_k(i,j) - ймовірність що k-та, що мурашка рухатиметься з вершини i до вершини j
$j \in J_k(i)$ є множиною міст що не були досі відвідані мурашкою k, що перебуває в місті i.
α є відносною силою (важливістю) сліду з феромону
β є відносною силою (важливістю) між містами

Отож ймовірність що місто обрано мурашкою є функцією від:

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

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

$p.\tau(i,j)+\sum_{k=1}^{m} {}_{\Delta} \tau_k(i,j)$ - множить концентрацію феромону на ребрі між містами i та j p(ρ), що зветься "константою випаровування". Її значення обирається між 0 та 1. Швидше випаровування феромону відбувається на малих значеннях цієї величини.
$\sum_{k=1}^{m} {}_{\Delta} \tau_k(i,j)$ - є величиною феромону k-ої мурашки, що виприскує на ребрі, яке визначається як $L k$ що є довжиною шляху проробленого цією мурашкою. Зрозуміло що більш короткі маршрути матимуть більшу концентрацію феромону.

Алгоритм відпалу

Генетичний алгоритм

Основна ідея:

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

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

Схема алгоритму

Кодування розв'язків
Ініціалізація
Моделювання еволюційного процесу (репродукція)
1. Селекція (оцінювання та відбір)
2. рекомбінація (застосування генетичних операторів)
3. перехід на п. 3.1
завершення роботи

Повний перебір

Реалізація алгоритмів на задачі

Вимоги до проекту

Лабораторна робота полягає в колективному (формуються групи по 4 студенти) написанні програми, яка дозволяє розв’язувати поставлену задачу різними методами. Програма повинна мати зручний графічний інтерфейс, який дозволяє:

вводити вхідні дані задачі;

обирати алгоритм розв’язку задачі;

для кожного алгоритму повинні бути передбечені:

сторінка налаштування параметрів алгоритму з обов’язковою наявністью кнопки Reset, яка скидає значення параметрів у значення по замовченню (значеннями по замовченню повинні бути оптимальні значення вирішення даним алгоритмом заданого класу задач, підібрані розробником в результаті експериментів); також повинна бути передбачена можливість зберегти підібрані користувачем значення параметрів, що є оптимальними для певного набору вхідних даних, з метою подальшого їх використання;

відображення проміжних результатів роботи алгоритму (з кроком N);

можливість передчасної зупинки алгоритму користувачем (для запобігання “зависанню” програми);

відображення результату роботи алгоритму із відповідною статистикою:

+ вхідні дані

+ значення параметрів

+ кількість кроків

+ оптимальний результат кожного кроку, кожних N кроків, а також поточні значення всіх членів популяції

+ час роботи

+ знайдений результат

+ реальний результат (якщо відомий)

“зведена” сторінка порівняння результатів роботи різних алгоритмів над спільними вхідними даними:

+ назва алгоритму