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

Русский English




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

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

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

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

УЗАГАЛЬНЕНИЙ ЕВОЛЮЦІЙНИЙ АЛГОРИТМ ТА СТВОРЕННЯ НА ЙОГО ОСНОВІ ЕВОЛЮЦІЙНИХ МЕТОДІВ ОПТИМІЗАЦІЇ

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

До еволюційних методів оптимізації можна віднести генетичні алгоритми (ГА) [2], моделювання відпалу [2], оптимізацію роєм частинок [4], мурашиною колонією [1], колонією бактерій [4] та роєм бджіл [4].

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

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

Однак дослідження, наведені в [5; 6], створили достатнє теоретичне підґрунтя для розроблення підходу до створення нових еволюційних методів оптимізації як формалізованої процедури без обов'язкового використання природних еволюційних процесів як їх прототипів.

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

У його основу покладений узагальнений еволюційний алгоритм, побудований на основі аналізу наведених вище еволюційних методів оптимізації (табл. 1).

Таблиця 1

Узагальнений еволюційний алгоритм

№ блоку Дії, що виконуються в блоці Джерело даних, попередній блок Отримувач даних, наступний блок
1 Ініціалізація змінних - блок 2
2 Випадкове створення вихідної інформації блок 1 блок 3
3 Запам'ятовування вихідної інформації блок 2 короткотермінова пам'ять, блок 4
4 Відбирання найбільш важливої вихідної інформації блок 3 блок 5
5 Запам'ятовування найбільш важливої вихідної інформації блок 4 довготермінова пам'ять, блок 12
6 Створення нової інформації блок 13 блок 7
7 Відбирання інформації блок 6 блок 8
8 Запам'ятовування нової інформації блок 7 короткотермінова пам'ять, блок 9
9 Відбирання найбільш важливої нової інформації блок 8 блок 10
10 Перевірка умови "Важливість нової інформації більша за важливість інформації, яка зберігається довготривало?" блок 9 "Так" - блок 11;  

"Ні" - блок 14

11 Запам'ятовування найбільш важливої нової інформації блок 10 довготермінова пам'ять, блок 12
12 Відбирання інформації короткотермінова пам'ять блок 13
13 Відбирання інформації довготермінова пам'ять блок 6
14 Додаткові функції блок 10 блок 12

 

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

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

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

Фактично узагальнений еволюційний алгоритм складається з двох основних частин: ініціалізуючої (блоки 1-5) та еволюційної (блоки 6-13).

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

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

Еволюційна частина алгоритму являє собою циклічне повторення етапів створення (блок 6), відбирання (блоки 7, 12 та 13) та запам'ятовування (блоки 8 та 11) нової інформації.

Стосовно створення нової інформації необхідно зазначити, що відповідно до [7; 8] для еволюції дисипативної системи необхідно, щоб її поведінка описувалась нелінійними залежностями. Окрім того, у [2; 4] наголошується, що еволюційні методи (по аналогії з природними системами) досліджують простір незалежних змінних шляхом поєднання детермінованості та стохастичності.

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

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

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

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

Еволюція завершується тоді, коли після деякого циклу DHi = 0 = const, опосередкованою ознакою чого є відсутність появи більш важливої інформації, і, як наслідок, незмінність інформації у пристрої довготермінового запам'ятовування. За розв'язок задачі оптимізації приймається найбільш важлива інформація з пристрою довготермінового запам'ятовування.

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

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

Покажемо можливість практичного використання запропонованого методичного підходу на конкретному прикладі.

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

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

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

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

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

Відбір з пристрою довготривалого зберігання будемо здійснювати в два етапи. На першому етапі сформуємо множину лише тих молекул, найкращі точки яких одночасно задовольняють двом умовам: їх важливість більша за важливість поточної молекули; їх важливість більша за 0,9 важливості найкращої молекули.

На другому етапі турнірним відбором (аналогічно ГА) відберемо дві молекули, найкращі точки яких позначимо як yij(t) та bij(t).

Нову інформацію будемо створювати з використанням формули

 

xij(t+1) = xij(t) + [yij(t) - xij(t)] random + [bij(t) - xij(t)] random

 

де random - випадкова величина, що має рівномірний розподіл у діапазоні [0, 1]; j - номер змінної; i - номер молекули в наборі; t - номер ітерації; xij(t) - координати j-ї змінної для i-ї молекули в наборі на t-ї ітерації.

Окрім того, як додаткову функцію, по аналогії з [9], використаємо декілька послідовних наборів молекул з переносом найкращої молекули до нового набору.

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

Таблиця 2

Відносні результати тестових розрахунків за різними методами

Метод розв'язання Удосконалений PSO [9] ГА [2] Запропонований
Відносне значення цільової функції 0,999 0,992 1

 

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

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

Література:

1.  Штовба, С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. - 2003. - № 4. - С. 70-75.

2. Ємельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. В. Курейчик, В. М. Курейчик. - М.: ФИЗМАТЛИТ, 2003. - 432 с.

3. Каширина, И. Л. Введение в эволюционное моделирование. - Воронеж: ВГУ, 2007. - 40 с.

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

5. Потьомкін, М. М. Шляхи підвищення ефективності еволюційних методів оптимізації // Матер. шостої Всеукр. наук.-практ. інтернет-конф. "Українська наука ХХІ століття" (16-18 червня 2010 р.), Ч. 4. - К.: ТОВ "ТК Меганом", 2010. - С. 42-47.

6. Потьомкін, М. М. Класифікація методів еволюційного моделювання // Матер. шостої Всеукр. наук.-практ. інтернет-конф. „Науковий потенціал України 2010"(22-24 березня 2010 р.), Ч. 3. - К.: ТОВ "ТК Меганом", 2010. - С. 33-38.

7. Волькенштейн, М. В. Энтропия и информация. - М.: Наука, 1986. - 192 с.

8. Рубин, А. Б. Биофизика: В 2-х кн.: Учеб. для биол. спец. вузов. Кн. 1. Теоретическая биофизика [Текст] - М.: Высш. шк., 1987. - 319 с.

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

e-mail: favorite_p@mail.ru


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

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