ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Д.И.Батищев, Е.А.Неймарк, Н.В. Старостин 2006,ННГУ

Задача нестационарной дискретной оптимизации

Вид целевой функции

F1*F1* F2*F2* x1*x1* x2*x2* T = 2 F(x,t) x S1*S1* S2*S2* t ab S

Стационарная задача об одномерном ранце

Нестационарная задача об одномерном ранце

Стационарная задача коммивояжера

Нестационарная задача коммивояжера

Методы решения нестационарных задач методы увеличения генетического разнообразия при изменении среды [2,10], методы постоянного поддержания генетического разнообразия [4,5], методы, использующие дополнительную память [3,8,9], методы, использующие дополнительные популяции [1,6].

Методы, использующие дополнительную память: диплоидное представление А1А1 А2А2 А3А3...АNАN B1B1 B2B2 B3B3...BNBN С1С1 С2С2 С3С3...СNСN Принцип доминирования Оценивание (s) Особь генотип фенотип приспособленность

Схемы доминирования : триаллельная Алфавит А={0,1,i} – возможные аллели Матрица доминирования: Вторая хромосома Первая хромосома 0i i i10 i

Схемы доминирования : четырехаллельная Алфавит А={0,1,i,o} Матрица доминирования : 01i1o10 i1100o Вторая хромосома Первая хромосома 0o1i 0 000/10 о i 0 11

Методы, использующие дополнительную память: структурное представление Фенотип: генотип Уровень регулирующих генов Уровень простых генов

Генотип Структурное представление Допустимые решения Фенотип: Уровень регулирующих генов Уровень простых генов

Алгоритм с памятью Формируется начальная популяция Состояние среды изменилось Генетический поиск Состояние среды индикатор среды I k Индикатор I k найден в базе Популяция загружается из базы из базы индикатор среды I k НЕТ ДА НЕТ ДА k:=0 k:=k+1

Алгоритм с памятью F(x,t) x F1*F1* F2*F2* Индекс состояния среды: I 2 I2I2 Популяция, допустимая для состояния среды I1I1 Популяция (I 1 ) I2I2 Популяция (I 2 ) Память Индекса I 2 в памяти нет Индекс I 2 найден в памяти Формируется новая популяция Популяция берется из памяти

Пример решения нестационарной задачи о ранце T=4

Пример решения нестационарной задачи о ранце

Меры эффективности алгоритмов для нестационарных задач Точность [11] Средняя коллективная приспособленность [7] Средняя скорость отклика – среднее количество вычислений, затрачиваемое для нахождения оптимального решения текущей задачи.

Сравнение эффективности алгоритмов Алгоритм Коллективная приспособленность точностьСредняя скорость отклика (поколений) Алгоритм с памятью Структурный алгоритм , Гаплоидный с преобразованием генотипа , Диплоидный , Гаплоидный со штрафной функцией ,

Литература 1.J. Branke. Memory enhanced evolutionary algorithms for changing optimization problems. In Congress on Evolutionary Computation CEC99, volume 3, pages IEEE, Cobb H. An Investigation into the Use of Hypermutation as an adaptive Operator in Genetic Algorithm Having Continuous, Time-Dependent Nonstationary Environments. Naval Research Laboratory Memorandum Report (1990). 3.Dasgupta D., McGregor D. R. Nonstationary function optimization using the Structured Genetic Algorithm. In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, September, pages , Ghosh, S. Tstutsui, and H. Tanaka. Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals. In IEEE Intl. Conf. on Evolutionary Computation, pages , Grefenstette John J. Genetic Algorithms for changing environments. In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, September, pages , J. Eggermont, T. Lenaerts, S. Poyhonen and A. Termier Raising the Dead; Extending Evolutionary Algorithms with a Case-Based Memory Proceedings of the Fourth European Conference on Genetic Programming (EuroGP'01) LNCS 2038, Ronald W. Morrison. Performance Measurement in Dynamic Environments, citeseer.ist.psu.edu/ html 8.K. P. Ng and K. C. Wong. A new diploid scheme and dominance change mechanism for non- stationary function optimization. In L. J. Eshelman, editor, Proc. 6th Int'l Conference on Genetic Algorithms, C. Ramsey and J. Grefenstette. Case-based initialization of genetic algorithms. In Proc. Fifth International Conference on Genetic Algorithms, pages , Vavak,F., Jukes,K.A., Fogarty,T.C. Leaning the Local search range for genetic optimization in nonstationary environments/ In IEEE Intl/ Conf/ on Evolutionary Computation ICEC97, pp IEEE Publishing, Weicker, K.: Performance Measures for Dynamic Environments. In: Parallel Problem Solving from Nature - PPSN VII, Lecture Notes in Computer Science Springer-Verlag