XIV Міжнародна наукова інтернет-конференція ADVANCED TECHNOLOGIES OF SCIENCE AND EDUCATION (19-21.04.2018)

Русский English




Научные конференции Наукові конференції

канд. технічн. наук Потьомкін М.М. УДОСКОНАЛЕННЯ МЕТОДУ ОПТИМІЗАЦІЇ КОЛОНІЄЮ БДЖІЛ ТА ЙОГО ЗАСТОСУВАННЯ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ З СЕПАРАБЕЛЬНИМИ ФУНКЦІЯМИ

Кандидат технічних наук Потьомкін Михайло Михайлович

Центральний науково-дослідний інститут Збройних Сил України

УДОСКОНАЛЕННЯ МЕТОДУ ОПТИМІЗАЦІЇ КОЛОНІЄЮ БДЖІЛ ТА ЙОГО ЗАСТОСУВАННЯ ДЛЯ РОЗВ'ЯЗАННЯ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ З СЕПАРАБЕЛЬНИМИ ФУНКЦІЯМИ

На сьогодні для ефективного розподілу ресурсів [1] великий практичний інтерес становить розв'язання сепарабельних задач нелінійного програмування (НЛП) [2], загальна математична постановка яких має вигляд

image002200.gif

за обмежень

image002201.gif, i = 1, ..., m.

Специфіка цих задач визначає спеціальний клас методів їх розв'язання, які застосовуються i є ефективними тільки для таких задач [2]. Причому, відповідно до [2], для їх розв'язання доводиться застосовувати, як правило, методи, що дозволяють знаходити лише наближені розв'язки або вимагають нескінченного числа кроків для досягнення точного розв'язку. Необхідно зазначити також, що додаткові проблеми виникають у разі, коли на змінні додатково накладається умова дискретності [1]. Тому пошук нових та удосконалення існуючих методів розв'язання сепарабельних задач НЛП є актуальним науковим завданням.

Різновидом методів розв'язання дискретних задач оптимізації є метод оптимізації колонією бджіл [3; 4], який базується на понятті популяції і моделює поведінку бджіл під час пошуку джерел харчування.

Аналіз результатів розв'язання задач сепарабельного НЛП за цим методом засвідчив, що у деяких випадках він суттєво поступається методу максимального елемента [5] та методу оптимізації роєм частинок [6].

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

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

По-друге, порівняння формул для розрахунку нового положення робочих бджіл з [3; 4] з аналогічними формулами для методу оптимізації роєм частинок [3; 6] свідчить, що вони є частковим випадком варіанта lbest методу оптимізації роєм частинок, у якому соціальні знання частинки пов'язуються з сусідами. Тому другим напрямком удосконалення методу оптимізації роєм бджіл може бути запозичення більш загальної формули з методу оптимізації роєм частинок [6].

Необхідно зазначити також, що детальний аналіз формул з для розрахунку нового положення з [6] свідчить про можливість урахування в ній під час оптимізації не двох масштабів пошуку оптимуму, як це має місце в методі оптимізації колонією бджіл (глобального за рахунок розвідників та локального за рахунок робочих бджіл), а трьох: глобального (розвідниками, які орієнтуються на найкращу точку поточної колонії), середнього (робочими бджолами, які орієнтуються на найкращі точки інших робочих бджіл) та локального (вільними завербованими бджолами, які орієнтуються на кращу точку своєї робочої бджоли).

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

Окремого розгляду потребує формула, яка встановлює пропорційність між кількістю завербованих бджіл та перспективністю j-го джерела їжі через його відносну корисність image002202.gif , де Nроб - загальна кількість бджіл для вербування., де - загальна кількість бджіл для вербування.За такого використання величин fitnessj на вигляд функції, яка підлягає максимізації, накладається додаткове обмеження виду fitnessj > 0, порушення якого може призводити до від'ємних значень кількості завербованих бджіл та/або діленню на 0. Забезпечення уникнення таких ситуацій суттєво ускладнює процес переходу від вихідної задачі оптимізації до fitness-функції.

Тому четвертий напрямок удосконалення методу оптимізації роєм бджіл передбачає введення до розгляду додаткової величини - важливості джерела їжі Wj, граничні значення для якої встановлюється, наприклад, у такий спосіб:

для джерела їжі з найбільшим значенням fitness-функції (fitnessmax) Wmax = 0,9;

для джерела їжі з найменшим значенням fitness-функції (fitnessmin) Wmin = 0,1.

Тоді Wj обчислюється за формулою

image002203.gif,,а кількість завербованих бджіл для j-го джерела їжі визначається як

Nj віл = Nвіл image002204.gif.

За вдосконаленим методом оптимізації колонією бджіл була розв'язана тестова задача (див. табл.). Аналіз отриманих результатів засвідчив, що запропоновані вдосконалення дозволили підвищити точність до рівня, сумірного з PSO [6]. При цьому час розрахунків порівняно з PSO [6] скоротився приблизно в 3,4 рази.

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

 

Таблиця. Відносна точність розглянутих методів оптимізації

Метод розв'язання Максимального елемента [5] Удосконалений PSO [6] Колонією бджіл [3; 4] Удосконалений колонією бджіл
Відносна точність 0,929 0,998 0,791 1

 Література:

1. Гурин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. - М.: Сов. радио, 1968. - 464 с.

2. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. - К.: Ел. вид. Ел. бібл. фак-ту кібернетики КНУ ім. Т. Шевченка, 2003. - 215 с.

3. Субботін С.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей // С.О. Субботін, А.О. Олійник, О.О. Олійник. - Запоріжжя: ЗНТУ, 2009. - 375 с.

4. Karaboga D., Akay B. A comparative study of Artificial Bee Colony algorithm // Applied Mathematics and Computation. - 2009. - № 214. -P. 108-132.

5. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. - М.: Сов.радио, 1974. - 304 с.

6. Потьомкін М.М. Удосконалення методу оптимізації роєм часток та його застосування для розв'язання сепарабельних задач нелінійного програмування // Матер. шостої всеукраїнської наук.-практ. інтернет-конференції "Україна наукова" (21-23 грудня 2009 р.), Ч.6. - К.: ТОВ "ТК Меганом", 2009. - С. 48-50.

7. Радченко В.Г., Песенко Ю.А. Биология пчел. - СПб.: Зоол. ит-тут РАН. - 1994. - 350 с.

e-mail: favorite_p@mail.ru


Залиште коментар!

Дозволено використання тегів:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>