Н.В. Старостин
2006,ННГУ
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Д.И.Батищев, Е.А.Неймарк, Н.В. Старостин 2006,ННГУ презентация
Содержание
- 1. ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Д.И.Батищев, Е.А.Неймарк, Н.В. Старостин 2006,ННГУ
- 2. Задача нестационарной дискретной оптимизации
- 3. Вид целевой функции
- 4. F1* F2* x1*
- 5. Стационарная задача об одномерном ранце
- 6. Нестационарная задача об одномерном ранце
- 7. Стационарная задача коммивояжера
- 8. Нестационарная задача коммивояжера
- 9. Методы решения нестационарных задач методы увеличения
- 10. Методы, использующие дополнительную память: диплоидное представление μ(s) генотип фенотип приспособленность
- 11. Схемы доминирования : триаллельная Алфавит А={0,1,i} – возможные аллели Матрица доминирования:
- 12. Схемы доминирования : четырехаллельная Алфавит А={0,1,i,o} Матрица доминирования:
- 13. Методы, использующие дополнительную память: структурное представление
- 14. Структурное представление Допустимые решения Уровень регулирующих генов Уровень простых генов
- 15. Алгоритм с памятью Формируется начальная популяция
- 16. Алгоритм с памятью F(x,t) x Индекс состояния
- 17. Пример решения нестационарной задачи о ранце
- 18. Пример решения нестационарной задачи о ранце
- 19. Меры эффективности алгоритмов для нестационарных задач Точность
- 20. Сравнение эффективности алгоритмов
- 21. Литература J. Branke. Memory enhanced evolutionary
Задача нестационарной дискретной оптимизации
Слайд 1ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Д.И.Батищев, Е.А.Неймарк,
Слайд 9Методы решения нестационарных задач
методы увеличения генетического разнообразия при изменении среды
[2,10],
методы постоянного поддержания генетического разнообразия [4,5],
методы, использующие дополнительную память [3,8,9],
методы, использующие дополнительные популяции [1,6].
методы постоянного поддержания генетического разнообразия [4,5],
методы, использующие дополнительную память [3,8,9],
методы, использующие дополнительные популяции [1,6].
Слайд 10Методы, использующие дополнительную память: диплоидное представление
μ(s)
генотип
фенотип
приспособленность
Слайд 11Схемы доминирования :
триаллельная
Алфавит А={0,1,i} – возможные аллели
Матрица доминирования:
Слайд 13Методы, использующие дополнительную память: структурное представление
генотип
Уровень регулирующих генов
Уровень
простых
генов
Слайд 15Алгоритм с памятью
Формируется начальная
популяция
Состояние среды
изменилось
Генетический поиск
Состояние среды
индикатор среды Ik
Индикатор Ik
найден в базе
Популяция загружается
из базы
индикатор среды Ik
НЕТ
ДА
НЕТ
ДА
k:=0
k:=k+1
Слайд 16Алгоритм с памятью
F(x,t)
x
Индекс состояния среды: I2
Память
Индекса I2 в
памяти нет
Индекс I2 найден в памяти
Формируется новая популяция
Популяция берется из памяти
Слайд 19Меры эффективности алгоритмов для нестационарных задач
Точность [11]
Средняя коллективная приспособленность [7]
Средняя скорость
отклика – среднее количество вычислений, затрачиваемое для нахождения оптимального решения текущей задачи.
Слайд 21Литература
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
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
