Численные методы оптимизации. Рейзлин В.И. - 44 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

44
6. Случайный поиск
Регулярные, или детерминированные методы спуска, рассмотренные нами
выше, не полноценны на неупорядоченном рельефе. Если экстремумов много, то
спуск из одного начального приближения может сойтись только к одному из ло-
кальных минимумов, не обязательно абсолютному. Кроме того, с ростом раз-
мерности задач резко снижается эффективность регулярных методов поиска, ко-
торые требуют очень больших вычислительных ресурсов. Поэтому иногда для
исследования таких сложных задач применяют случайный поиск.
6.1. Простой случайный поиск
Предполагают, что искомый минимум лежит в некотором n-мерном па-
раллелепипеде. В этом параллелепипеде по равномерному закону выбирают
случайным образом N пробных точек и вычисляют в них целевую функцию.
Точку, в которой функция имеет минимальное значение, берут в качестве реше-
ния задачи. Однако даже при очень большом числе пробных точек вероятность
того, что хотя бы одна точка попадает в небольшую окрестность локального ми-
нимума, ничтожно мала. Действительно, пусть N=10
6
и диаметр котловины око-
ло минимума составляет 10% от пределов изменения каждой координаты. Тогда
объем этой котловины составляет 0.1
n
часть объема n-мерного параллелепипеда.
Уже при числе переменных n>6 практически ни одна точка в котловину не попа-
дет.
Поэтому берут небольшое число точек
(5 )Nn
и каждую точку
рассматривают как нулевое приближение. Из каждой точки совершают спуск,
быстро попадая в ближайший овраг или котловину; когда шаги спуска быстро
укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже до-
статочно, чтобы судить о величине функции в ближайшем локальном минимуме
с удовлетворительной точностью. Сравнивая окончательные значения функции
на всех спусках между собой, можно изучить расположение локальных миниму-
мов и сопоставить их величины. После этого можно отобрать нужные по смыслу
задачи минимумы и провести в них дополнительные спуски для получения ко-
ординат точек минимума с более высокой точностью.
При решении экстремальных задач на областях со сложной геометрией
обычно эту область вписывают в
n
-мерный гиперпараллелепипед, в котором
генерируют случайные точки по равномерному закону, оставляя только те, ко-
торые попадают в допустимую область (рис. 24).

Страницы