Самарский государственный технический университет филиал в г. Сызрани
Электротехнический Факультет
Дисциплина
Методы параллельных
вычислений
Лекция 15.
Параллельные методы многоэкстремальной оптимизации
Тараканов А.В., доцент, к.п.н. Кафедра Информатики и систем управления
Содержание
Введение
Постановка задачи
Обзор методов
Решение одномерных задач (последовательный индексный алгоритм)
Редукция размерности задачи
Использование множественных отображений
Решение многомерных задач (параллельный индексный алгоритм)
Заключение
2 из 41
Введение
Задачи минимизации некоторой функции при ограничениях типа неравенств встречаются во многих областях науки и техники
Нахождение минимума является трудоемкой операцией, ее сложность экспоненциально растет с ростом размерности задачи
Методы оптимизации представляют собой современную динамично развивающуюся область применения параллельных вычислений
3 из 41
Постановка задачи…
Найти минимум функции (y):
y* min ( y) : y D, g j (y) 0,1 j m ,
D y RN : ai yi bi ,1 i n .
где
- (y) – минимизируемая функция (критерий), - gj(y), 1 j m – функциональные ограничения, - D – область поиска,
- y – вектор варьируемых параметров Допустимая область
Q y : y D, g j ( y) 0,1 j m .
4 из 41
Постановка задачи…
Априорная информация о задаче – предположение о выполнимости условия Липшица
( y1) ( y2 ) L
y1 y2 
, y1, y2 D
g j ( y1) g j ( y2 ) Lj 
y1 y2 
,1 j m, y1, y2 D.
5 из 41
Постановка задачи…
Пример задачи глобальной условной оптимизации
Критерий: |
|
|
|
|
( y1 |
1)( y2 |
1) 4 |
|
|
( y1 1) |
4 |
|
|
|
|||
2 |
|
2 |
|
2 |
|
|
4 |
||||||||||
( y) 1.5y1 |
exp 1 |
y1 |
20.25( y1 |
y2 ) |
|
|
|
|
|
exp |
2 |
|
|
|
( y2 1) |
|
|
|
2 |
|
2 |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Ограничения: g1(y)=0.01[(y1 2.2)2+(y2 1.2)2 2.25] 0 g2(y)=100[1 (y1 2)2/1.44 (0.5y2)2 ] 0
g3(y)=10[y2 1.5 1.5sin(2 (y1 1.75))] 0
Область поиска:
D={y R2, 0≤y1≤4, 1≤y2≤3}
6 из 41
Постановка задачи
(y)=const
y*
D gj(y)=0
7 из 41
Обзор методов…
Локальная оптимизация
Используется идея локального спуска
В многоэкстремальных задачах схема локального спуска, вообще говоря, не приводит к решению.
Мультистарт – запуск локального метода из нескольких точек.
Низкая эффективность мульти- стартовых схем в существенно многоэкстремальных задачах, т.к. одно и то же локальное решение
может быть найдено несколько раз.
8 из 41
Обзор методов…
Глобальная оптимизация
Построение случайных или детерминированных покрытий области поиска.
Количество узлов равномерной сетки увеличивается экспоненциально с увеличением размерности задачи.
N |
|
T T ( ) (bi ai ) / |
(y) |
i 1 |
y* |
|
D
gj(y)=0
9 из 41
Обзор методов…
Глобальная оптимизация
Построение неравномерных адаптивных покрытий области поиска (алгоритм глобального поиска)
Методы ориентированы на построение |
g3(y)=0 |
|
|
существенно более плотной сетки |
|
только в окрестности глобально- |
|
оптимального решения задачи, чем вне |
y* |
этой окрестности. |
(y)=const |
g2(y)=0 |
g1(y)=0 |
|
10 из 41