генетический алгоритм
Н. В. Панов, С. П. Шарый
Институт
вычислительных технологий СО РАНг. Новосибирск
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Презентация на тему Стохастические интервальные подходы в задачах глобальной оптимизацииИнтервальный генетический алгоритм
Содержание
- 1. Стохастические интервальные подходы в задачах глобальной оптимизацииИнтервальный генетический алгоритм
- 2. Глобальная оптимизация функций Поиск глобального
- 3. Глобальная оптимизация функций Удачная область для
- 4. Да Выход: Оценка
- 5. Но Застаивание и избыточность интервальной оценки могут существенно ухудшить производительность метода.
- 6. Целевая функция (шестигорбый верблюд) F = 4x2 +
- 7. Целевая функция (шестигорбый верблюд) F = 4x2 +
- 8. Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)
- 9. Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)
- 10. Застаивание и избыточность интервальной оценки могут существенно ухудшить производительность метода.
- 11. Процесс работы алгоритма [ «неудобная» функция «Шестигорбый верблюд» ]
- 12. Маленький промежуточный итог Интервальный анализ удобен для задач
- 13. Причины неуспешности алгоритма Алгоритмы этого типа запрограммированы на
- 14. Пути улучшения Процедуры отбраковки Отбраковка по значению
- 15. Пути улучшения Смена алгоритма [ Отказ от
- 16. Случайный интервальный поиск Извлечь из рабочего списка
- 17. Тестовая функция Трекани F = x4 + 4x3 + 4x2 + y2
- 18. Случайный интервальный поиск Распределение ширины брусов
- 19. Случайный интервальный поиск
- 20. Повышение эффективности метода Отбраковка бесперспективных Локальные оптимизирующие процедуры И т.д.
- 21. Случайный интервальный поиск с приоритетом Извлечь из
- 22. Параметры исследования Приоритет по ширине интервала Приоритет по ширине интервальной оценки
- 23. Функция «Розенброк4» (RB4) Общий вид (слева) и поведение вблизи точки глобального минимума (справа).
- 24. Результаты экспериментов
- 25. Интервальный симулированный отжиг Алгоритм Метрополиса
- 26. Выход: Глобальный оптимум целевой
- 27. Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного отжига на «шестигорбом верблюде»
- 28. Целевая функция Растригина (10ая) F = x2 + y2 – cos(18x) – cos(18y)
- 29. Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного
- 30. Алгоритм интервального адаптивного дробления
- 31. Интервальный алгоритм симулированного отжига [ неоптимальные настройки ]
- 32. Интервальный генетический алгоритм
- 33. Интервальный генетический алгоритм Популяция – список брусов
- 34. Интервальный генетический алгоритм Вариативность: Максимальное количество
- 35. Интервальный генетический алгоритм Объединенная функция приспособленности: f(b)
- 36. 0. Создать начальную популяцию (произвести несколько дроблений). 1. Вычислить
- 37. Результаты работы
- 38. Вывод 1) Отказ от чистого детерминизма
- 39. Дополнительная информация
- 40. Точность интервальных оценок
- 43. Скачать презентацию
Глобальная оптимизация функций Поиск глобального минимума ( или максимума ) вещественнозначной функции на прямоугольном
Слайды и текст этой презентации
Слайд 1Стохастические интервальные подходы в задачах глобальной оптимизации Интервальный
генетический алгоритм
вычислительных технологий СО РАНг. Новосибирск
Слайд 2Глобальная оптимизация функций
Поиск глобального минимума
( или
максимума )
вещественнозначной функции
на прямоугольном брусе Х
со сторонами, параллельными
координатным осям.
Ищем
Слайд 3Глобальная оптимизация функций
Удачная область для применения
интервальных методов
В отличии от классических (точечных)
методов не требуется знание априорной информации о функции Константа Липшица
Производные
Интервальное расширение функции, фактически, дает верхнюю и нижнюю оценку оптимума.
Границы могут быть избыточными.
Результат гарантируется
Слайд 4Да
Выход:
Оценка
глобального
оптимума.
Вход:
Целевая функция.
Область.
Допуск на размер бруса.
Извлечь из
рабочего списка ведущий (наиболее “перспективный”) брус.Достигнут
критерий остановки?
Нет
Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список
Блок-схема оптимизационного алгоритма адаптивного интервального дробления
Слайд 5Но
Застаивание и избыточность интервальной оценки могут существенно
ухудшить производительность метода.
Слайд 10Застаивание и избыточность интервальной оценки могут существенно
ухудшить производительность метода.
![Процесс работы алгоритма [ «неудобная» функция «Шестигорбый верблюд» ]](/img/tmb/1/76504/be1d723f47b9aa1bff258ee3fede5ec2-800x.jpg)
Слайд 12Маленький промежуточный итог
Интервальный анализ удобен для задач
глобальной оптимизации.
Существующий алгоритм бывает недостаточно эффективен.
Слайд 13Причины неуспешности алгоритма
Алгоритмы этого типа запрограммированы на
неудачу в задачах такого рода. В соответствии
со своей внутренней логикой они будет последовательно мельчить ложные ведущие брусы, лишь незначительно улучшая точность интервальной оценки.
Слайд 14Пути улучшения
Процедуры отбраковки
Отбраковка по значению
Тест на
монотонность
Тест на выпуклость-вогнутость
Метод Ньютона
Слайд 15Пути улучшения Смена алгоритма [ Отказ от
детерминизма ]
Отказываемся от жесткого детерминизма метода
и допускаем некоторые статистические переходы.![Пути улучшения
Смена алгоритма [ Отказ от детерминизма ] Отказываемся](/img/tmb/1/76504/e53ce0459d40f678f9aeb708552c81c1-800x.jpg)
Слайд 16Случайный интервальный поиск
Извлечь из рабочего списка случайный
брус.
Достигнут критерий остановки?
Да
Выход:
Оценка
глобального
оптимума.
Нет
Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список.
Вход:
Целевая функция.
Начальная область определения.
Критерий остановки.
Слайд 20Повышение эффективности метода
Отбраковка бесперспективных
Локальные оптимизирующие процедуры
И т.д.
Слайд 21Случайный интервальный поиск
с приоритетом
Извлечь из рабочего
списка брус случайным образом с учетом ширины.
Достигнут критерий остановки?Да
Выход:
Глобальный
оптимум.
Нет
Раздробить брус. Вычислить интервальные расширения целевой функции по брусам-потомкам и добавить их в рабочий список.
Вход:
Целевая функция.
Область.
Допуск на размер бруса (критерий остановки).
Слайд 23Функция «Розенброк4» (RB4)
Общий вид (слева) и поведение
вблизи точки глобального минимума (справа).
Слайд 25Интервальный
симулированный отжиг
Алгоритм Метрополиса
Метод M(RT)2
Алгоритм «Отпуска»
Симулированный отжиг.
Слайд 26Выход:
Глобальный
оптимум целевой
функции.
Количество шагов.
Использованная
память.
Вход:
Целевая функция.
Область ее определения. Допуск на размер бруса. Начальная температура.Случайным образом извлечь брус из рабочего списка.
Да
Нет
Температура < 0
Достигнуто условие выхода?
Поделить брус любым способом на подбрусы-потомки. Вычислить интервальные расширения целевой функции по подбрусам. Добавить брусы-потомки в рабочий список.
На этом брусе
получаем лучшую оценку целевой функции?
Да
Нет
Уменьшить температуру Т.
Нет
Брус при-
нимается с вероятностью
exp(-ΔE / kT). Брус
принят?
Да
Слайд 27Сравнение адаптивного интервального дробления (бисекции) и интервального
симулированного отжига
на «шестигорбом верблюде»
Слайд 29Сравнение адаптивного интервального дробления (бисекции) и интервального
симулированного отжига на функции F = x2
+ y2 – cos(18x) – cos(18y)Сравнение адаптивного интервального дробления (бисекции) и интервального симулированного отжига
на функции F = x2 + y2 – cos(18x) – cos(18y)
![Интервальный алгоритм симулированного отжига [ неоптимальные настройки ]](/img/tmb/1/76504/2e4b96012beea3c78efb4db750fc309e-800x.jpg)
Слайд 33Интервальный
генетический алгоритм
Популяция
– список брусов
Благоприятные условия:
среда обитания
–
оценка значения функции на брусе
способность к воспроизводству
–
ширина бруса
Слайд 34Интервальный
генетический алгоритм
Вариативность:
Максимальное количество потомков
Минимальное
количество потомков
Сколько объектов, начиная с самого
приспособленного, могут оставить потомство. Брусы бьются на равные части, либо же в некой пропорции, «разновесные» дети.
Приспособленность:
Нижняя оценка функции на брусе.
Ширина интервальной оценки на брусе.
Размер бруса.
Слайд 35Интервальный
генетический алгоритм
Объединенная функция приспособленности:
f(b) – интервальная
оценка целевой функции f на брусе b
f(b) – нижняя граница интервальной оценки (оценка минимума снизу)
wid(f(b)) – ширина (точность) интервальной оценки.
Слайд 360. Создать начальную популяцию (произвести несколько дроблений).
1. Вычислить
функцию приспособленности по новым подбрусам.
2. N из наиболее
приспособленных брусов с вероятностью Pn оставляют от Ln до Un потомков.3. M из неприспособленных брусов с вероятностью Pm оставят от Lm до Um потомков.
4.* Подбрусы проверяются на жизнеспособность (применяются критерии отбраковки)
5.* Если критерий отбраковки был улучшен, случается Эпидемия (улучшенные критерии применяются ко всему списку брусов)
Интервальный генетический алгоритм
глобальной оптимизации
Слайд 38Вывод
1) Отказ от чистого детерминизма
традиционных интервальных методов
глобальной оптимизации
может привести к созданию численных алгоритмов
с качественно новыми свойствами,
в частности, с улучшенной эффективностью.
2) Применение стохастических подходов
в интервальных методах
глобальной оптимизации оправдано.
