Ройовий інтелект

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

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

Одним з найвідоміших прикладів є алгоритм мурашиної оптимізації (Ant Colony Optimization, ACO). Він моделює процес пошуку їжі мурахами, які залишають сліди феромону на шляху до джерела їжі. Чим коротший або ефективніший маршрут, тим сильніший феромон, і тим більша ймовірність, що інші мурахи оберуть саме цей шлях. В задачах оптимізації це сприяє знаходженню наближених оптимальних рішень, наприклад, в задачі комівояжера або при маршрутизації транспортних потоків.

Інший популярний підхід — алгоритм рою частинок (Particle Swarm Optimization, PSO), натхненний рухом зграї птахів або косяка риб. В цьому методі кожна «частинка» представляє потенційне рішення і рухається в просторі можливих рішень, орієнтуючись на власний найкращий досвід та найкращий досвід всієї групи. Такий механізм спроможний швидко знаходити хороші розв’язки для складних задач з великою кількістю параметрів.

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

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

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

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

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

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

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

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

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

Рис. 2. JS-демонстрація мурашиного алгоритму (відкрити)

Алгоритм рою частинок

Ідея алгоритму була частково запозичена з досліджень поведінки скупчень тварин (косяків риб, зграй птахів тощо), модель була трохи спрощена, а особини названо нейтрально - частинки.

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

Найважливіше в алгоритмі – це корекція швидкості, саме від цього кроку залежить збіжність алгоритму.

Рис. 2. JS-демонстрація алгоритму рою частинок (відкрити)

Пояснення до прикладу:

Реалізації алгоритмів ройового інтелекту в Python

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

1. Універсальні фреймворки (багато алгоритмів в одному)

Ці бібліотеки є найбільш потужними, оскільки дозволяють порівнювати різні підходи (PSO, ACO, ABC тощо) в межах одного коду.

• PyPop7. Сучасна та дуже потужна бібліотека, яка підтримує величезну кількість популяційних алгоритмів, включаючи PSO, ABC, Firefly, Bat, Cuckoo Search та багато інших.
• Mealpy. Мабуть, найбільш повна бібліотека. Вона містить понад 150 алгоритмів, включаючи всі згадані вами: Wolf Pack, Monkey Search, Fish School, Ant Colony та інші.
• NiaPy. Мікро-фреймворк для природних алгоритмів. Добре структурований, підтримує PSO, BA, FFA, CSS.
• PySwarms. Спеціалізована та дуже популярна бібліотека саме для PSO (Particle Swarm Optimization). Вона має докладну документацію та інтеграцію з NumPy.

2. Спеціалізовані рішення за типами алгоритмів

• PSO (Рой частинок). PySwarms, MealPy
• ACO (Мурахи). AntColony (для задачі комівояжера) або MealPy
• ABC (Бджоли). BeePy або Mealpy
• CSA (Зозулі). CuckooSearch (у складі NiaPy або MealPy)
• WPS, BA, FFA, MS, FSS. Найкраще реалізовано в NiaPy або MealPy

3. Гібридні та еволюційні фреймворки

Якщо вам потрібна висока продуктивність або можливість створювати власні варіації алгоритмів:

• DEAP (Distributed Evolutionary Algorithms in Python). Це "золотий стандарт" для еволюційних обчислень. Хоча вона більше орієнтована на генетичні алгоритми, її гнучкість дозволяє легко реалізувати PSO або ACO.
• PyGMO (Python Parallel Global Multiobjective Optimization). Дуже швидка (написана на C++ з інтерфейсом Python), підтримує паралельні обчислення та складні топології роїв.

Вибір алгоритму

• Якщо потрібно швидко протестувати різні алгоритми (наприклад, порівняти Вовків з Кажанами) — обирайте Mealpy.
• Якщо це наукове дослідження і потрібна стабільність та візуалізація PSO — обирайте PySwarms.
• Якщо потрібна максимальна швидкість для складних обчислень — використовуйте PyGMO.