Северин В.П. Методы ОП

чения целевой функции gk 1 с лучшим значением предыдущих итераций fk :

Умножением на это значение величины предыдущего шага находится значение следующего шага

Рассмотрим особенности процесса одномерного поиска для метода адаптации шага по формулам (3.28)–(3.31). Пусть в первой итерации из точки x0 со значением функции f0 выполняется начальный

шаг с переходом к пробной точке y1 x0 h0 и вычислением значения функции g1 f ( y1) . Если g1 f0 , то полагают x1 y1 , f1 g1 , множителю адаптации шага задают значение r1 0,5 , вычисляют следую-

щий шаг h1 r1h0 0,5h0 и переходят к следующей пробной точке y2 x1 h1 с вычислением значения функции g2 f (x2 ) .

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

71

72

Рис. 3.10. Изменение направления поиска методом адаптации шага

Если и в последующих итерациях с номерами k 2, 3, значе-

ния целевой функции не уменьшаются по сравнению со значением f0 ,

Таким образом, в этом случае на каждой итерации направление поиска меняется на противоположное (рис. 3.10).

73

Если значения функции продолжают уменьшаться, то выполняются итерации в отрицательном направлении по рекуррентной форму-

Рис. 3.11. Поиск методом адаптации шага в отрицательном направлении

В этом случае действия метода адаптации шага также похожи на действия метода Свенна за исключением более осторожных трех пер-

74

fm 2 gm 2 , rm 2 0,5 и вычисляют hm 2 rm 2hm 1 (рис. 3.11).

Влюбом случае лучшие точки поиска xk будут приближаться к

оптимальной точке x до тех пор, пока не выполнится условие hk 1 . Таким образом, метод адаптации шага основан как на идее

удвоения шага в методе Свенна при удачном направлении поиска, так и на идее деления шага на два или на четыре, что позволяет быстро приближаться к оптимальной точке. Если же задать начальное значение r0 0,5 , то сходство с методом Свенна увеличится.

А л г о р и т м м е т о д а а д а п т а ц и и ш а г а .

3.Если f y f x , то перейти к шагу 7.

4.Положить x y , f x f y .

5.Если r 0,5 , то положить r 2 , иначе положить r 0,5 .

6.Перейти к шагу 8.

7.Если r 2 , то положить r 0,25 , иначе положить r 0,5 .

8.Положить h h r .

9.Если h , то перейти к шагу 2.

75

10. Остановиться.

Сравнивая алгоритм метода адаптации шага с алгоритмами методов Свенна и деления интервала пополам, которые совместно решают ту же задачу минимизации целевой функции одной переменной, что и данный метод, можно сделать вывод, что алгоритм метода адаптации шага проще объединения двух указанных алгоритмов. К тому же в методе адаптации шага применяются только простые операции сложения, удвоения шага, деления шага на два и на четыре. Поэтому данный метод является надежным и эффективным на практике.

3.9.Сравнение методов уменьшения интервала неопределенности

Мы рассмотрели различные методы одномерного поиска, предназначенные для уменьшения интервала неопределенности точки мини-

мума x унимодальной целевой функции одной переменной f (x) без использования производных. Эти методы нулевого порядка, позволяющие находить минимум унимодальной функции произвольного вида, по объему исходной информации для их алгоритмов можно разделить на две группы.

1.Методы, использующие значения границ интервала неопределенности. Это методы равномерного поиска, дихотомии, деления интервала пополам, Фибоначчи и золотого сечения.

2.Метод, не использующий интервал неопределенности. Это один только метод адаптации шага.

Для работы методов из первой группы необходимо найти интервал неопределенности методом Свенна. Эффективность методов из этой группы можно оценить по значениям коэффициента уменьшения длины интервала неопределенности при n вычислениях значений целевой функции

rn LLn .

76

Формулы этого коэффициента для метода равномерного поиска (МРП) (3.1), метода дихотомии (МД) (3.2), метода деления интервала пополам (МДИП) (3.3), метода Фибоначчи (МФ) (3.17) и метода золотого сечения (МЗС) (3.27) для удобства сравнения сведены в табл. 3.3.

Таблица 3.3 – Коэффициенты уменьшения интервала

На основании этой таблицы, а также табл. 3.1 и табл. 3.2 для чисел Фибоначчи и степеней золотого сечения составлена табл. 3.4, в которой для тех же методов представлено количество вычислений целевой функции, необходимое для достижения требуемого уменьшения интервала неопределенности, которое задано значением коэффициента уменьшения интервала rn .

Таблица 3.4 – Количество вычислений функции

77

По этой таблице видно, что теоретически самым эффективным методом уменьшения интервала неопределенности является метод Фибоначчи. Незначительно уступает ему в эффективности метод золотого сечения. Верхняя оценка количества вычислений функции методом деления интервала пополам лишь на единицу превышает те же показатели для метода дихотомии, однако нижняя оценка почти вдвое ниже метода дихотомии и даже меньше, чем у метода Фибоначчи. Метод равномерного поиска для достижения той же точности, что и другие методы, тратит на несколько порядков больше вычислений значений функции. Самым надежным из этих методов уменьшения интервала неопределенности является метод деления интервала пополам, не зависящий от дополнительных параметров. Его надежность сравнима с надежностью метода адаптации шага.

Лабораторная работа

Т е м а л а б о р а т о р н о й р а б о т ы .

Разработка подпрограммы для метода уменьшения интервала неопределенности.

Ц е л ь л а б о р а т о р н о й р а б о т ы .

Разработать подпрограмму метода уменьшения интервала неопределенности унимодальной целевой функции.

П о р я д о к в ы п о л н е н и я л а б о р а т о р н о й р а б о т ы .

1.Получить у преподавателя задание на программирование одного из методов уменьшения интервала неопределенности:

1) метод равномерного поиска;

2) метод дихотомии;

3) метод деления интервала пополам;

4) метод Фибоначчи;

5) метод золотого сечения;

6) метод адаптации шага.

2.На основании алгоритма для заданного метода уменьшения интервала неопределенности написать компьютерную подпрограмму в

78

3)на каждой итерации выводить на экран компьютера строку, содержащую номер точки поиска k , длину интервала неопределенности Lk , значение функции fk и значение переменной xk ;

4)итерации продолжаются до тех пор, пока выполняются неравенства:

5)после окончания процесса оптимизации на экране должна отображаться таблица, имеющая соответствующий заголовок и представляющая процесс минимизации функции;

6)под таблицей необходимо отобразить количество вычислений целевой функции, длину конечного интервала неопределенности, минимальное значение функции и соответствующее ему значение независимой переменной.

3. Написать общую программу для выполнения вычислительного процесса минимизации целевой функции одной переменной и отображения на экране этого процесса в соответствии с требованиями:

1)за основу общей программы для минимизации функции взять общую программу поиска интервала неопределенности из предыдущей лабораторной работы и модифицировать эту программу;

2)задать в программе значения x0 , x , h , , N ;

3)путем вызова подпрограммы метода Свенна с использованием подпрограммы вычисления функции f (x) и значений x0 , h , N реа-

лизовать итерационный процесс поиска интервала неопределенности с

79

построением таблицы процесса на экране и получением массивов значений переменной X и функции F , границ интервала неопределенности a и b ;

4) путем вызова разработанной подпрограммы уменьшения интервала неопределенности реализовать итерационный процесс уменьшения интервала с построением таблицы процесса на экране и получением массивов значений переменной X и функции F , лучшей точки поиска x и значения в ней функции f x ;

5) с помощью подпрограммы графического отображения итерационного процесса по массивам X и F отобразить график процесса минимизации целевой функции одной переменной на экране компьютера.

4. Запустить на счет общую программу минимизации функции одной переменной для функций предыдущих лабораторных работ из нескольких начальных точек

5. Выполнить анализ полученных результатов:

1)на основании табличной и графической информации о работе методов одномерного поиска определить конечные точки метода Свенна и найденный этим методом интервал неопределенности;

2)на нескольких начальных итерациях по табличным данным и графикам сопоставить начало работы метода уменьшения интервала с его рабочими формулами;

3)оценить эффективность метода уменьшения интервала и сопоставить ее с теоретической эффективностью.

6. Ответить на вопросы преподавателя по теме лабораторной работы.

7. Оформить и сдать отчет о проведенной лабораторной работе.

80