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

Русский English




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

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

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

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

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

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

image002372.png

за обмежень

image002373.png, i = 1, ..., m.

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

Різновидом методів розв'язання дискретних задач оптимізації є метод оптимізації роєм часток (PSO - particle swarm optimization) [3], який базується на понятті популяції і моделює поведінку птахів у зграї (косяків риб). Первісною основою методу PSO була імітація руху птахів у зграї (риб у косяку) з метою виявлення базових принципів, завдяки яким птахи літають (риби плавають) синхронно та вміють змінювати напрямок руху з перегрупуванням в оптимальні формації.

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

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

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

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

Крім того, проведені нами обчислювальні експерименти з формулою швидкості частинок v з [3]

vij(t+1) = w vij(t) + c1 [yij(t) - xij(t)] random + c2 [qj(t) - xij(t)] random,   (1)

де t - номер кроку; vij(t) - швидкість i-ї частинки по j-ій змінній на кроці t; xij(t) - значення j-ї змінної i-ї частинки на кроці t; w - коефіцієнт інерційності; c1, c2 - позитивні константи прискорення, які використовуються для варіювання ваг когнітивної та соціальної компонент швидкості частинки відповідно; yij(t) - найкраща за значенням цільової функції точка, знайдена частинкою за всі кроки; qj(t) - найкраща за значенням цільової функції точка, знайдена роєм за всі кроки; random - випадкова величина, що має рівномірний розподіл у діапазоні [0,1];

показали, що кращі результати дає її модифікація виду

vij(t+1) = w vij(t) random + c1 [yij(t) - xij(t)] random + c2 [qj(t) - xij(t)] random.   (2)

Тому, третім напрямком удосконалення методу PSO можна вважати використання для розрахунку швидкості частинки формулу (2) замість формули (1). За вдосконаленим PSO була розв'язана тестова задача (див. табл.).

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

Метод розв'язання Максимального елемента ГА PSO Удосконалений PSO
Відносна точність 0,93 0,99 0,94 1

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

Література:

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

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

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

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

5. Потьомкін М.М. Генетичні алгоритми як перспективний метод розв'язання задач оптимального розподілу неоднорідних ресурсів // Наука і оборона. - №2. - 2005. - С. 51 - 53.

6. Premalatha K. Discrete PSO with GA Operators for Document Clustering // International Journal of Recent Trends in Engineering. - May 2009. - Vol 1. - № 1. - P. 20-24.

e-mail: favorite_p@mail.ru


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

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