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

Русский English




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

кандидат технічних наук, Потьомкін М.М. ШЛЯХИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЕВОЛЮЦІЙНИХ МЕТОДІВ ОПТИМІЗАЦІЇ

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

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

ШЛЯХИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЕВОЛЮЦІЙНИХ МЕТОДІВ ОПТИМІЗАЦІЇ

Одним з перспективних напрямків розвитку методів оптимізації, який сьогодні інтенсивно розвивається, є еволюційне моделювання. Найбільш ефективним визнане його використання для розв'язання тих задач оптимізації, для яких застосування інших методів за якихось причин є недоцільним. На сьогодні група еволюційних методів оптимізації складається з: генетичних алгоритмів (ГА) [1 - 3], моделювання відпалу (МВ) [1; 3], LARES [4; 5], оптимізації роєм часток [6; 7], мурашиною колонією [7; 8], колонією бактерій [7; 9] та роєм бджіл [7].

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

Як відомо [11; 12], фундаментальними фізичними величинами, які характеризують стан дисипативної системи, є кількість та потоки речовини, енергії, ентропії та інформації, при цьому перехід від хаотичного стану системи до впорядкованого пов'язується з обов'язковим експортом ентропії та з наявністю малих первинних флуктуацій стану окремих її елементів. За сталості зовнішніх умов, за яких забезпечується експорт ентропії, перехід до впорядкованого стану є незворотнім, а саме поняття „еволюція" пов'язується з процесом, що забезпечує такий перехід [11; 12].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклади реалізації першого та другого підходів наведені в [2-4; 13 та ін.].

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

Прикладом такого запозичення є перенесення окремих елементів ГА в інші еволюційні методи оптимізації, наприклад, [5; 7; 13 та ін.].

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

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

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

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

Література:

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

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

3. Гладков Л.А. и др. Генетические алгоритмы. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

4. Irizarry R. LARES: An Artificial Chemical Process Approach for Optimization / Evolutionary Computation. - Vol. 12. - № 4 (2004). - P. 435-459.

5. Потьомкін М.М. Удосконалена концепція штучної хімічної реакції та її застосування для розв'язання сепарабельних задач нелінійного програмування // Матеріали П'ятої всеукраїнської науково-практичної інтернет-конференції "Українська наука ХХІ століття" (17-19 червня 2009 р.), Ч.4.- К.: ТОВ "ТК Меганом", 2009. - С. 43-45.

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

7. 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.

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

9. Liu Y., Passino K.M. Biomimicry of social foraging bacteria for distributed optimization: models, principles and emergent behaviors // Journal of optimization theory and application. - December 2002.- Vol. 115. - № 3. - P. 603-628.

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

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

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

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


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

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