Метод равномерного поиска

Пусть априорная информация об унимодальности функции крайне недостаточна, чтобы строить разумный процесс поиска экстремума. Наиболее приемлемым способом поведения в такой обстановке является последовательное вычисление целевой функции I(x) при всех допустимых значениях варьируемого параметра x

a £ x £ b ,

где a, b – границы интервала поиска.

Пусть d заданная величина погрешности определения оптимального параметра x*. Тогда для реализации алгоритма поиска следует определить значение I(x) в точках, равномерно отстоящих друг от друга на расстоянии h = d, т. е. в точках

Из полученных значений показателя качества I(x_j) выбирается наибольшее значение (глобальный максимум). Такой способ поиска называется сканированием. При малой заданной погрешности d этот метод требует слишком большое число вычислений функции I(x) и больших затрат машинного времени.

Метод поразрядного приближения

Этот метод применим для поиска оптимума унимодальной функции и обладает более высоким быстродействием. Это достигается тем, что используется алгоритм с переменным шагом поиска. Вначале величина шага выбирается достаточно большой, значительно превышающей требуемую погрешность определения положения оптимума, и выполняется грубый поиск. В районе оптимума поиск производится с меньшим шагом.

Рассмотрим алгоритм такой стратегии поиска максимума функции I(x). Пусть интервал [a,b] содержит внутри себя максимальное значение параметра x*: a £ x* £ b.

Задается начальное значение параметра x₀ = a и вычисляется I₀=I(x₀). Задаются начальный шаг поиска h и кратность k уменьшения шага в районе оптимума. Производится поиск максимума I(x) из начальной точки x=x₀ по алгоритму:

x(j+1)=x(j)+h(j+1);

(1.3)

где j – номер шага.

Поэтому алгоритму поиск из начальной точки x = x₀ осуществляется с постоянным шагом h. После каждого шага вычисляется значение критерия I(x), оно сравнивается с предыдущим значением и, в случае улучшения критерия, шаги продолжаются до тех пор, пока очередной шаг не окажется неудачным. После этого поиск максимума продолжается из последней точки в обратном направлении с шагом в k раз меньше прежнего. Эта процедура поиска продолжается до тех пор, пока не будет выполнено условие:

| h | £ d,

где d – заданная погрешность определения оптимума.

Метод дихотомии

Этот метод отыскания экстремума применим для класса унимодальных функций. Идея метода проста – делить интервал [a,b], где расположен оптимум I(x), пополам

x₀ = (a + b)/2

и отбрасывать часть, где оптимума заведомо быть не может. С этой целью достаточно вычислить показатель качества I(x) в точках x₀ ± d, отстоящих друг от друга на расстояние 2d < d, где d – заданная погрешность определения оптимума. По двум вычисленным значениям I(x₀–d) и I(x₀+d), в силу унимодальности функции I(x), легко установить новый интервал неопределенности по следующим условиям (при поиске максимума):

(1.4)

Таким образом, в результате двух вычислений I(x) промежуток, где содержится оптимум, сокращается почти вдвое. Следующая пара измерений проводится в районе середины нового интервала неопределенности [a, x₀+d] или [x₀–d, b] в зависимости от того, какое из условий (4.4) выполняется.

Аналогично производятся последующие шаги поиска до тех пор, пока на k-ом шаге после 2k измерений I(x) длина интервала неопределенности l_k = (b-a)/2^k, где находится оптимум, не станет меньше или равен d, т. е. l_k£d.

Как видно, метод дихотомии позволяет довольно быстро попадать в район оптимума. Так, после 10 шагов дихотомии (20 измерений показателя качества) длина интервала неопределенности, где локализован оптимум, в 2¹⁰=1024 раза меньше исходной длины l = b – a. Для достижения такой точности в методе равномерного приближения потребуется вычисление I(x) в 1025 точках.