Оптимізація системи часток!!!

Оптимізація системи часток (ОСЧ) - це евристичний алгоритм, що грунтується на популяції, який є наслідком соціальної поведінки певної системи, що сприяє глобальному оптимуму завдяки використанню часток, які впливають на соціальну та когнітивну поведінку цієї системи.

Сутність методу

Основні частки ОСЧ визначаються на основі їх положення та швидкості в пошуковому просторі. Частки притягуються до позицій у пошуковому просторі, що відображає їх найкращі особисті знахідки та кращий пошук системи (наприклад, місцеві та глобальні найкращі позиції). Формування швидкодії для ОСЧ використовує два коефіцієнти прискорення, щоб контролювати вплив найкращих особистих та кращих знахідок системи на нове рішення. Крім того, коефіцієнт, що називається Inertia Weight, використовується для контролю впливу останньої швидкості на оновлену версію. Частки в системі оновлюють свої позиції в пошуковому просторі, додавши їх оновлену швидкість до свого останнього місця в пошуковому просторі. ОСЧ має слабкі сторони з точки зору 1) контролю параметрів, 2) передчасної збіжності; 3) відсутності регулювання динамічної швидкості, що призводить до неможливості вирішення гірського розряду.

Для вирішення проблеми контрольних параметрів пропонуються різні модифікації, такі як:

1) лінійне зменшення ваги інерції,

2) зміна часу інерції ваги,

3) випадкова вага інерції,

4) фіксована вага інерції,

5) коефіцієнт розгону за часом,

6) коефіцієнти випадкового прискорення,

7) фіксація коефіцієнтів прискорення.

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

Сфера використання

Завдяки потенціалу ОСЧ у вирішенні складних проблем він широко використовувався у різних сценаріях та областях. Цинь та ін. згадували про більш легку реалізацію та меншу кількість параметрів як про основні переваги ОСЧ в порівнянні з генетичним алгоритмом. У багатьох дослідженнях показано, що ОСЧ працює однаково ефективно або навіть краще, ніж генетичний алгоритм. Модифіковані версії ОСЧ використовуються для планування шляху, сценаріїв пошуку та роботи з навігацією. Використовується модифікована версія ОСЧ, яка використовує фактор мутації для планування шляху. У деяких роботах введено мутаційну ОСЧ для обробки переносних завдань. У дослідженні агенти з можливостями реабілітації використовуються таким чином, щоб вони координували їх переміщення в сценарії, що складається з імітаційного багатопрограмного розподіленого шляху. Пью, Чжан і Мартінолі використовували локальну версію ОСЧ в сусідній перспективі в задачі оптимізації пошуку в багатокористувацьких пошукових системах, в яких метод ОСЧ перевершив генетичний алгоритм. Також модифікована версія ОСЧ, що називається DEADALUS, використовується для вирішення проблеми «глухого кута» роботів у сценаріях уникнення перешкод. У ОСЧ використовується в сценарії уникнення перешкод, у якому роботів призначено для переміщення між статичними та динамічними перешкодами. У дослідженні запропоновано функцію потоку, що називається Потенційний Потік, як техніку уникнення перешкод. Також зони розширення ОСЧ (AEPSO) і кооперативний AEPSO (CAEPSO) використовуються як навігатори рою роботів у динамічних та статичних середовищах. AEPSO та CAEPSO користуються макроскопічним моделюванням ОСЧ, крім додаткової евристики, яка використовує такі концепції, як навчання підкріплення та спільне навчання. Однорідні рої простих рятувальних роботів контрольованих AEPSO, демонструють потенціал у статичних та динамічних середовищах, обмежених статичними перешкодами, рятувальними місіями, що залежать від часу, та невизначеністю (випадковий шум). Група гетерогенних роботів, керованих CAEPSO, показала багатообіцяючу продуктивність навіть у презентації динамічних і ітераційно змінюваних комбінаторних шумів. Досягнуті результати CAEPSO переважно регулюються шляхом передачі знань, отриманих від раніше проведених симуляцій. Хоча ОСЧ широко застосовується для різних сценаріїв планування шляху та навігації, концептуально ці спроби не вносять суттєвих відмінностей від базової ОСЧ. Це пов'язано з тим, що ці дослідження зосереджені на оновленні параметрів швидкості, спрямованих на досягнення кращої та швидшої конвергенції. Хоча багато спроб було зроблено для вирішення основних проблем ОСЧ, більшість запропонованих рішень не є надійними в реальних та динамічних середовищах. Крім того, більшість із цих методів не мають спільної доменності.

Виконала Федорова Ольга

Developed by Інститут Програмних Систем