Марусенко Роман

Науковий керівник: канд. т.- н., старший викладач Нарадовий В.В.

Кіровоградський державний педагогічний університет імені Володимира Винниченка

Актуальність теми. Використання ройового інтелекту, як методу оптимізації.

Мета роботи. Розробити програму з візуалізацією роботи одного з алгоритмів ройового інтелекту. Для досягнення мети поставлено такі завдання:

1. Визначити основні поняття ройового інтелекту;
2. Виявити основні принципи ройового інтелекту;
3. Зробити огляд основних алгоритмів ройового інтелекту;
4. Розробити програму з візуалізацією одного з алгоритмів.

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

 Ройовий інтелект (англ. Swarm Intelligence) описує колективну поведінку децентралізованої системи, яка здатна до самоорганізації. Інколи ройовий інтелект називають колективним інтелектом і він розглядається в теорії штучного інтелекту, як метод оптимізації. Термін був уведений Херардо Бені й Ван Цизмом у 1989 році, у контексті системи клітинних роботів.

 Системи ройового інтелекту, як правило, складаються з множини агентів (мультиагентна система), які локально взаємодіють між собою, а також з навколишнім середовищем [1, с.287]. Самі агенти зазвичай досить прості, але всі разом, взаємодіючи, вони створюють, так званий, ройовий інтелект. Прикладом у природі може служити колонія мурах, рій бджіл, зграя птахів, косяк риб.

Для визначення основних принципів колективного інтелекту досить розглянути принципи поведінки різних колективних комах. До колективних комах відносяться комахи, які живуть колоніями, наприклад, мурахи, бджоли, терміти, деякі види ос і т.п. В основі поведінки колоній таких комах лежить самоорганізація [1, с.288]. Самоорганізація – множина динамічних механізмів, відповідно до яких система регулюється на глобальному рівні за рахунок взаємодії її компонентів на нижньому рівні без прямої взаємодії між цими компонентами.

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

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

Спеціалізація полягає в тому, що різні дії виконуються окремими спеціалізованими групами індивідів.

Алгоритм колонії мурах (мурашиний алгоритм, алгоритм оптимізації мурашиної колонії, англ. ant colony optimization, ACO) – один з ефективних поліноміальних алгоритмів для знаходження наближених розв‘язків задачі комівояжера, а також завдань пошуку маршрутів на графах [2, с.2]. Алгоритм можна описати у 3 етапи (рис. 1):

1. Перша мураха знаходить джерело їжі (F) через якийсь шлях (а). Потім повертається до гнізда (N), залишивши за собою слід з феромонів (b).
2. Мурахи вибирають будь-який шлях, але шлях, на якому міститься феромон робить його більш привабливішим як найкоротший шлях.
3. Мурахи вибирають коротший шлях, а з часом інші шляхи втрачають щільність феромонового сліду.

        

         Рис. 1 – Поведінка мурах в колонії

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

Бджолиний алгоритм (алгоритм оптимізації наслідуванням бджолиної колонії, англ. artificial bee colony optimization, ABC) – один з поліноміальних евристичних алгоритмів для розв‘язку оптимізаційних задач в області інформатики та дослідження операцій [4, с.2]. Відноситься до категорії стохастичних біонічних алгоритмів, заснований на імітації поведінки колонії медоносних бджіл при зборі нектару в природі. Ідея бджолиного алгоритму полягає в тому, що усі бджоли на кожному кроці будуть вибирати як елітні ділянки для дослідження, так і ділянки в околиці елітних, що дозволить, по-перше, урізноманітнити популяцію пошуків на наступних ітераціях, по-друге, збільшити ймовірність виявлення розв‘язку близького до оптимального.

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

Метод рою частинок, МРЧ (англ. Particle Swarm Optimization, PSO) – метод чисельної оптимізації, для використання якого не потрібно знати точного градієнта оптимізованої функції. МРЧ оптимізує функцію, підтримуючи популяцію можливих розв'язків, називаних частками, і переміщаючи ці частки в просторі розв'язків згідно із простою формулою. Переміщення підпорядковуються принципу найкращого знайденого в цьому просторі положення, що постійно змінюється при знаходженні частками вигідніших положень [5, с.2].

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

Для реалізації програми з візуалізацією роботи одного з алгоритмів ройового інтелекту було обрано алгоритм колонії мурах. При написанні програми було обрано мову JavaScript та технологію Canvas для візуалізації роботи алгоритму. Програма складається з таких основних модулів (класів):

1. Ant.js. Клас, який описує мурах, які є основною алгоритму.
2. Cell.js. Вся область руху мурах поділена на невеликі комірки (які утворюють матрицю).
3. World.js. Основний клас, який відповідає за рух мурах по області, а також генерацію місця і їжею.

Список літератури:

1. Субботін С. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / С. О. Субботін, А. О. Олійник, О. О. Олійник. – Запоріжжя: ЗНТУ, 2009. – 375 с.
2. Кочегурова Е. А. Алгоритм муравьиных колоний для задачи проектирования рациональных маршрутных сетей городского пассажирского транспорта / Е. А.Кочегурова, Я. А. Мартынов, Ю. А. Мартынова, С. Г. Цапко. // СибГУТИ. – 2014. – №3. – С. 89–100.
3. Курейчик В. В. Роевой алгоритм в задачах оптимизации / В. В. Курейчик, Д. Ю. Запорожец. // Известия Южного федерального университета. Технические науки. – 2010. – №7. – С. 28–32.
4. Курейчик В. В. Эволюционная оптимизация на основе алгоритма колонии пчёл / В. В. Курейчик, Е. Е. Полупанова. // Известия Южного федерального университета. Технические науки. – 2009. – №12. – С. 41–46.
5. Карпенкко А. П. Обзор методов роя частиц для задачи глобальной оптимизации (particle swarm optimization) / А. П. Карпенко, Е. Ю. Селиверстов. // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. – 2009. – №3. – С. 1–26.

 Відомості про авторів:

         Марусенко Роман Вікторович – студент VI курсу фізико-математичного факультету Кіровоградського державного педагогічного університету імені Володимира Винниченка.