Генетичний алгоритм!!!
Генетичний алгоритм - евристичний алгоритм планування шляху.
Сутність методу
Генетичний алгоритм, представлений Джоном Голландієм у 1975 році, є еволюційним методом, який користується перевагами таких операторів, як природний відбір, кросовер та мутація. Притаманний генетичному алгоритму паралельний пошук робить його привабливим для розробки оптимальних рішень. Підбір - це рейтинг хромосом на основі їхніх можливостей (тут можливість розуміється як відстань хромосом від цілі) і підбір хромосом з найкращим рейтингом (тих, що представляють короткі або гладкі шляхи) для генерації нового населення. Кросовер - це операція, що використовується для генерації нового населення із підібраних хромосом за допомогою оператора Selection (вибір). Як правило, оператор кросовера розділяє обрані хромосоми на дві частини і обмінює їх частки один з одним, щоб створити нове населення. Мутація - це операція, в якій одна або група хромосом вибирається випадковим чином як повністю, так і частково. Типовим є використання оператора мутації, коли населення зближується до локального оптимума, захопленого між перешкодами, або продуктивність не поліпшується для певної кількості поколінь через відсутність генетичної різноманітності.
Сфера використання
Генетичний алгоритм успішно застосовується до проблем, таких як класична проблема комівояжера, оптимізація потокового магазину та планування розкладу, в яких метою є або оптимізувати, або знайти найкраще рішення з безлічі можливостей.
Різні дослідження були зроблені на основі використання генетичного алгоритму в області навігації. Генетичний алгоритм використовується у сценарії динамічної багатосторінкової маршрутизації, що використовує генетичний алгоритм у сценаріях планування багатоканального трафіку, Денеб використовував гібридну версію генетичного алгоритму для планування шляху; також генетичний алгоритм використовується в сценаріях планування декількох шляхів у 3D та 2D середовищах відповідно. Садаті і Тахері використовували поєднання нейронної мережі Хопфілда та генетичного алгоритму в задачі планування шляху. Eргезер і Леблебіціоглу використовували модифікований генетичний аналіз для планування шляху для БЛА, метою якого є створення шляхів, які максимізують зібрану інформацію з регіонів інтересів, уникаючи заборонених областей. У аналогічному дослідженні Сяоньін та ін. досліджували потенціал розширеної версії генетичного алгоритму в плануванні польотів для безпілотних літальних апаратів, висвітлюючи здатність досягати глобальних оптимумів через покращення глобального та локального пошуку. Запропонована модифікація спрямована на диверсифікацію населення генетичного алгоритму, використовуючого концепцію подвійного населення. Ченг та ін. виявили такі переваги, як здатність надавати оптимальні рішення без необхідності повного ознайомлення з проблемною областю, на додаток до менш інтенсивного обчислення для генетичного алгоритму як планувальника шляху для безпілотних підводних транспортних засобів за лінійними та динамічними програмуваннями. Елсхемлі та ін. використовували розширену версію генетичного алгоритму, яка називається Планувальником Генетичного Алгоритму (ПГА) у задачі планування мобільних роботів. В ПГА ідея полягає у використанні хромосом із змінною довжиною для кодування шляху. Незважаючи на те, що попередні експерименти з ПГА показали свою доцільність у динамічному та статичному середовищах, вона як і раніше не має загальної екології та не підходить для всіх середовищ. Точно так само, Трояновський та ін. розглянули шлях планування в динамічних середовищах за допомогою генетичного алгоритму, який використовує локальну пам'ять для хромосом. Незважаючи на те, що підхід є можливим у динамічному середовищі, він страждає від великої кількості обчислень, і його продуктивність залежить від конфігурації середовища. Основним недоліком підходу генетичного алгоритму в області планування шляху є те, що він неможливий в динамічних середовищах. Це пов'язано з тим, що він працює на карті-сітці або використовує фіксоване рішення у пошуковому просторі та не контролює різноманітність населення, що спричиняє передчасну конвергенцію.
Виконала Федорова Ольга
Developed by Інститут Програмних Систем
