Оптимізація колонії мурашок!!!
Оптимізація колонії мурашок (ОКМ) - евристичний алгоритм планування шляху.
Сутність методу
Метод ОКМ надихається соціальною поведінкою мурашок і імітує колективну поведінку мурашок, що рухаються від гнізда до джерела їжі, щоб знайти оптимум в пошуковому просторі. Мурахи використовують хімічну речовину, що називається феромон, для позначення маршрутів. Це допомагає їм відстежувати шлях. Якість шляху буде оцінюватися на основі кількості феромонів, залишених мурашками, що пройшли цим маршрутом, використовуючи такі чинники, як концентрація та пропорція. Пропорція та концентрація феромонів вказують на довжину маршруту та кількість мурашок, що пройшли через цей маршрут відповідно. Мурахи вибрали маршрути з найбільшою ймовірністю пропорції до концентрації феромона. ОКМ використовує популяцію випадково ініціалізованих мурашок у пошуковому просторі, що отримають їжу у місці мети, щоб знайти оптимальний шлях. Оптимізація шляху досягається шляхом оцінки кількості феромонів, нанесених мурахами на шляхи. Хань вважає, що швидкий алгоритм виконання ОКМ не займає надмірну кількість часу в процесі ітерації і це одне з основних його переваг над генетичним алгоритмом. З іншого боку, непотрібні кроки, вжиті в ОКМ як результат використання глобального терміну притягування, щоб визначити найкраще рішення, робить цей підхід нижчим за генетичний алгоритм. Однією із запропонованих модифікацій для розгляду недоліків ОКМ є використання великої кількості мурашок, що покращує процес пошуку рішення, але також призводить до додаткового обчислювального навантаження. Інша можливість полягає в тому, щоб вводити мурашок з різними значеннями феромонів (в термінах кількості феромонів, що покриваються різними мурашками) та якостями (з точки зору тривалості життя феромону).
Сфера використання
Лукас і Геттіер використовували ОКМ в гібриді з програмуванням обмеження в динамічно адаптованому сценарії планування шляху автомобіля за допомогою значно швидшого пошуку рішення, одночасно підтримуючи оптимальність рішень. Чжан та ін. використовували комбінацію ОКМ, алгоритму імітації відпалу та обрамленого чотириколірного дерева для збільшення ефективності планування шляху. У дослідженні OКМ використовується для надання кращих вихідних рішень для алгоритму імітації відпалу, тоді як обрамлене чотириколірне дерево використовується для покращення розкладеної ефективності середовища. Досягнута продуктивність від імітаційних сценаріїв вказує на потенціал запропонованого гібридного підходу з точки зору забезпечення вільних шляхів зіткнення з покращеною навігацією. Лі та ін. вирішив проблему планування глобального шляху, запропонувавши гетерогенний підхід ОКМ, який модифікує звичайну ОКМ, використовуючи функцію імовірності переходу з перехресним переходом та оновленням феромонів. Запропонований підхід виконував генетичний алгоритм у сценаріях моделювання, забезпечуючи більш плавні шляхи. Хао та ін. використовували ОКМ в гібриді з штучною функцією переходу. Ідея полягає в тому, щоб використовувати ОКМ як планування глобального шляху та штучну функцію імовірності як метод локального планування шляху. Співпраця між ОКМ та штучною функцією імовірності базується на використанні феромонів траєкторії ОКМ в штучній функції імовірності, щоб уникнути локального мінімуму в сценарії планування декількох роботів. МакЛуркін і Ямін запропонували чотири алгоритми і порівняли їх у переключенні ролі між членами рою в сценарії планування динамічного шляху. Ши та ін. запропонували гібрид алгоритмів ОКМ та функції імовірності переходу в задачі планування шляху робота. У дослідженні ОКМ застосовується для планування шляхів на транзитних територіях, а роль функції імовірності переходу - оптимізувати параметри ОКМ. Традиційні ОКМ містять деякі обмеження, такі як тривалий час, щоб досягти місцевого мінімуму, якщо розмір проблеми великий. У традиційному ОКМ, феромони концентрації всіх елементів однаково ініціалізуються. Отже, рішення початково сконструйовані на початку еволюційної фази, і знадобиться багато часу, щоб знайти кращий шлях серед великої кількості плавних шляхів.
Developed by Інститут Програмних Систем
