'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

F1* F2* x1* x2* F(x,t) x S1* S2* t a b S


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

Методы, использующие дополнительную память: диплоидное представление ?(s) генотип фенотип приспособленность


Слайд 10

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


Слайд 11

Схемы доминирования : четырехаллельная Алфавит А={0,1,i,o} Матрица доминирования:


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

Алгоритм с памятью F(x,t) x Индекс состояния среды: I2 Память Индекса I2 в памяти нет Индекс I2 найден в памяти Формируется новая популяция Популяция берется из памяти


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

Сравнение эффективности алгоритмов


Слайд 20

Литература J. Branke. Memory enhanced evolutionary algorithms for changing optimization problems. In Congress on Evolutionary Computation CEC99, volume 3, pages 1875--1882. IEEE, 1999. 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 6760. (1990). Dasgupta D., McGregor D. R. Nonstationary function optimization using the Structured Genetic Algorithm. In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28-30 September, pages 145--154, 1992. 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 666--671, 1998. Grefenstette John J. Genetic Algorithms for changing environments. In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28-30 September, pages 137--144, 1992. 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 , 2001. Ronald W. Morrison. Performance Measurement in Dynamic Environments, citeseer.ist.psu.edu/676673.html 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, 1995. C. Ramsey and J. Grefenstette. Case-based initialization of genetic algorithms. In Proc. Fifth International Conference on Genetic Algorithms, pages 84--91, 1993. 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 ICEC’97, pp. 355-360. IEEE Publishing, 1997. Weicker, K.: Performance Measures for Dynamic Environments. In: Parallel Problem Solving from Nature - PPSN VII, Lecture Notes in Computer Science 2349. Springer-Verlag 2002 64-73


×

HTML:





Ссылка: