Трубаров В.А., Гоголенко С.Ю., Теплинський К.С. | Підсистема оптимізації на базі еволюційних обчислень для паралельного моделюючого середовища

Биография
Реферат по магистерской работе
Библиотека по теме магистерской работы
Ссылки по теме магистерской работы
Отчёт о результатах поиска по теме магистерской работы
Индивидуальное задание

Доклад на региональную студенческую научно-техническую конференцию "Компьютерный мониторинг и информационные технологии", проводимую кафедрой компьютерного эколого-экономического мониторинга (КЭМ) факультета вычислительной техники и информатики (ФВТИ) Донецкого национального технического университета (ДонНТУ) 30 мая 2005 года. Доклад располагается в секции 7 "Искусственный интеллект и нейросетевые технологии".

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

Трубаров В.А., Гоголенко С.Ю., Теплинський К.С.
Донецький національний технічний університет

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

1. Локальні детерміністичні методи

Локальні детерміністичні методи можуть знайти вирішення задачі оптимізації із заданою точністю за обмежену кількість кроків, але вони шукають лише локальні оптимуми та не придатні для вирішення задач глобальної оптимізації. Вони використовуються у розробленій підсистемі для покращання точності рішення, знайденого генетичним алгоритмом. Використовуються два методи: градієнтний алгоритм Арміджо для оптимізації без обмежень та його модифікацію для оптимізації з обмеженнями [Polak97]. Вони ефективно покращують точність рішення після закінчення ГА.

2. Генетичний алгоритм

Основною ідеєю ГА [Holland75] є пошук у багатомірному просторі, який імітує еволюцію біологічних індивідуумів (мається на увазі науковий підхід, який базується на еволюційній теорії Дарвіна). Береться певна кількість індивідуумів (популяція), кожен з яких є рішенням задачі оптимізації. Цільова функція обчислюється для кожного індивідууму та є його пристосованістю.
ГА починається з ініціалізації початкової популяції (в більшості випадків випадковими значеннями). Потім різноманітні генетичні оператори, такі як кросовер, мутація та добір, застосовуються до поточної популяції. Еволюція продовжується, доки усі індивідууми будуть мати одне й те саме значення цільової функції (це рішення задачі оптимізації) або буде досягнуто максимальну кількість поколінь (у цьому випадку індивідуум з кращім значенням цільової функції буде рішенням).
Для всіх цих генетичних операторів існує велика кількість модифікацій (див. [ECS89, Goldberg89, Baeck96]). Представлення індивідуумів (яке є бінарним у ГА) також може бути різним (стандартний код або код Грея [Baeck96]).
Мутація – це оператор, який змінює випадкові біти індивідууму інвертуючи їх. Мутація може застосовуватися до випадкового біту або до кожного біту із заданою імовірністю pc.
Кросовер є найважливішим оператором ГА [Baeck96]. Він реалізує механізм генетичного спадкування важливих якостей батьків нащадками. Використовується два основних типи кросоверу: багатоточковий та однорідний. Перший обирає z >= 1 точок кросоверу та обмінює кожен другий сегмент між обраними батьками, утворюючи двох нащадків. Однорідний кросовер обмінює кожен біт між батьками з імовірністю pm.
Оператор добору втілює механізм природного добору. Існують такі модифікації добору, як "рулетка", "лінійне упорядкування" та "турнамент" [Baeck96]. Вони або обчислюють імовірність виживання залежно від відносної пристосованості індивідууму, або імітують внутрішню боротьбу за виживання в популяції. Додатковий елемент алгоритму під назвою "елітизм" може бути доданий до будь-якого добору; він забезпечує виживання кращого індивідууму. Будь-який оператор добору може бути застосовано тільки на нащадках ([mu, lambda] добір), або ще й на батьках ([mu + lambda] добір).

3. Оптимізація з обмеженнями та без

Оптимізація може мати обмеження. В цьому випадку кожен індивідуум має задовольняти наданим функціям g(x) >= 0 та h(x) = 0. У випадку локальних детерміністичних методів використовується спеціальний додатковий метод (модифікація методу Арміджо), а для ГА обмеження можуть або закладатися в кодуванні параметрів (у випадку коли параметри обмежені декількома безперервними зонами), або перевірятися надані функції в операторі добору (індивідууми, які не задовольняють обмеженням, знищуються).

4. Паралельна оптимізація

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

5. Реалізація, дослідження та результати

ГА був реалізований в підсистемі оптимізації, яка може бути сконфігурована на реалізацію різних модифікацій. Ці модифікації були протестовані на багатьох штучних цільових функціях від простих (сфера) до складних мультимодальних функцій (функція Еклі, фрактал, тощо). Було проведено тестування продуктивності та результативності модифікацій ГА з метою обирання найкращого набору параметрів для певної функції. Розроблений ГА показав високу ефективність, особливо з використанням локальних детерміністичних методів для покращання точності. Планується його портування до суперкомп’ютеру з MIMD архітектурою за допомогою бібліотеки MPI.

Література

[Polak97] E. Polak. Optimization. Algorithms and Consistent Approximation. SpringerVerlag, New York, Inc., 1997.
[Holland75] J.H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI, 1975.
[Baeck96] Th. Baeck. Evolutionary Algorithms in Theory and Practice. Oxford University Press, Inc., New York, 1996.
[ECS89] L.J. Eshelman, R.A. Caruna and J.D. Schaffer. Biases in the Crossover landscapes. In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 10-19. Morgan Kaufmann, 1989.
[Goldberg89] D.E. Goldberg. Genetic Algorithms in Search, Optimizations and Machine Learning. Addison Wesley, Reading, MA, 1989.


          
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            

            ДонНТУ