Панов Н.В. КТИ ВТ CО РАН Новосибирск. Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Интервальные методы распространени. - презентация

1 Панов Н.В. КТИ ВТ CО РАН Новосибирск

2 Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Интервальные методы распространени я ограничений

3 Детерминистски е Стохастические случайный поиск поиск с приоритетом интервальный метод имитации отжига интервальные генетические алгоритмы Мультиметоды Интервальные алгоритмы адаптивного дробления

4 Интервальные расширения асимптотически точны: х = х х f(x) f(x), f(x) f(x) f(x) – оценка минимума снизу f ( x ) f(x)f(x) x Интервальные алгоритмы адаптивного дробления

5 f(x) Интервальные алгоритмы адаптивного дробления Детерминистский алгоритм

6 f(x) Интервальные алгоритмы адаптивного дробления

7 f(x) Интервальные алгоритмы адаптивного дробления

8 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x [] Брусы Интервальная оценка значений функции Область поиска

9 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x [] Брусы Интервальная оценка значений функции Область поиска

10 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x [] Брусы Интервальная оценка значений функции Область поиска

11 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x [] Брусы Интервальная оценка значений функции Область поиска «Особи»

12 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x Функция приспособленности x2x2 x1x1 F1F1 F2F2 F3F3

13 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления f(x)f(x) x2x2 x1x1 Функция приспособленности

14 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления Функция приспособленности f(b) – интервальная оценка целевой функции f на брусе b f(b) – нижняя граница интервальной оценки (оценка минимума снизу) wid(f(b)) – ширина (точность) интервальной оценки.

15 Стохастические Интервальные генетические алгоритмы Интервальные алгоритмы адаптивного дробления 0. Создаётся начальная популяция { Основной цикл 1. Вычисляется значение функции приспособленности новорожденных особей; 2. N из наиболее приспособленных особей с вероятностью P n оставляют от L n до U n потомков; 3. M из неприспособленных особей с вероятностью P m оставят от L m до U m потомков; 4. Потомки проверяются на жизнеспособность; 5. Если критерий отбраковки был улучшен, организуется эпидемия; } Конец основного цикла

16 Критерии отбраковки Техники, позволяющие распознать интервалы, гарантированно не содержащие оптимум Отбраковка по значению Отбраковка по первой производной Отбраковка по второй производной

17 Отбраковка по производным [ ] Тест на монотонность Тест на выпуклость

18 Детерминистски е Стохастические случайный поиск поиск с приоритетом интервальный метод имитации отжига интервальные генетические алгоритмы Мультиметод Интервальные алгоритмы адаптивного дробления

19 Детерминистски е Стохастические случайный поиск поиск с приоритетом интервальный метод имитации отжига интервальные генетические алгоритмы Мультиметод Интервальные алгоритмы адаптивного дробления

20 Мультиметод

21 время ширина оценки оптимума Мультиметод

22 Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Мультистарт Интервальные методы распространени я ограничений Интервальные методы отбраковки Интервальные алгоритмы адаптивного дробления

23 Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Мультистарт Интервальные методы распространени я ограничений Интервальные методы отбраковки Интервальные алгоритмы адаптивного дробления

24 Интервальные методы распространения ограничений

25 x (+) y (=) z Пример: o f(x) = 0 o 2x - 4y = 0 o x = x 0 x 1 Если x 0 = [1, 2]; y 0 = [1, 2], x = [1, 2] [2, 4] = [1, 2], y = [1, 2] [½, 1] = [1, 1]. o x 1 = 2y o y 1 = ½x U U U x = [1, 2] [2, 2] = 2, y = [1, 1] [1, 1] = 1. U U

26 Интервальные методы распространения ограничений Природа ограничений: Область поиска, Ноль первой производной, Знак второй производной, Значение целевой функции не более (не менее) уже найденных. Проблема: Взаимодействие с методами дробления

27 Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Дифференцирование Мультистарт Интервальные методы распространени я ограничений Интервальные методы отбраковки Интервальные алгоритмы адаптивного дробления

28 Дифференцирование Символьная алгебра Обратная польская запись: a + b => +(a b) Дерево Кантаровича Правила дифференцирования Упрощение выражений x' = 1 * x 0 IAMath: x y = exp(y*log(x)) Направленное округление 0 * x = [-e, +e] 0 exp([-e, +e]) 1 Повышение точности оценки Уменьшение вычислений

29 Решатель Методы параллелизации Интервальная арифметика Интервальные алгоритмы поиска ДетерминистскиеМультиметоды Стохастические Случайный поиск с приоритетом Интервальный моделированный отжиг Интервальный эволюционный алгоритм Классические точечные алгоритмы Мультистарт Методы распространения ограничений Алгоритмы дифференцирования Символьное дифференцирование Упрощение выражений Вычисление интервального расширения функции Методы отбраковкиПо значениюПо 1 ой производнойПо 2 ой производной Интервальный метод Ньютона Общая структура

30 Заключение 58 классов и интерфейсов 5000 строк кода 114 юнит-тестов 2300 строк кода Обобщённая функция Розенброка до размерности 35 Де Йонг до 10,000 минус: Функции должны быть заданы в явном виде

31 Спасибо!

32