Работа №4 Оценка эффективности методов оптимизации

Задание

1. Ознакомиться с критериями и методикой оценки эффективности методов оптимизации.

2. Составить программу расчета показателя эффективности для различных методов одномерной оптимизации (методов равномерного поиска, деления отрезка пополам и «золотого сечения») и отладить ее на контрольном примере.

3. Рассчитать показатель эффективности различных методов одномерной оптимизации, произвести сопоставление и выбрать наиболее эффективный для данного класса функций.

Методические указания

1. Эффективность метода определяется одномерной оптимизации определяется по формуле (см. раздел 3, тема 8):

,

где ξ – коэффициент эффективности, (в – а) – заданный интервал, а n – число вычислений целевой функции.

2. Для выполнения задания рекомендуется воспользоваться готовыми программами, использованными в лабораторных работах №1, №2, №3. Программы каждого из методов (равномерного поиска, деления отрезка пополам и «золотого сечения») необходимо модифицировать – вставить счетчик числа обращений к подпрограмме вычисления целевой функции:

n: = n + 1.

Предварительно счетчик необходимо очистить – присвоить «ноль»: n = 0. Вместе с точкой экстремума нужно вывести на печать и значение счетчика.

3. Задаваясь несколькими значениями точности e = 0,1; 0,01; 0,001, произвести расчеты экстремума методом равномерного поиска для целевой функции F(x) и интервала согласно варианту задания из табл. 3. Вывести на печать значения счетчика n1 для всех трех случаев.

То же самое проделать для методов деления отрезка пополам и «золотого сечения». Распечатать значения счетчиков числа вычислений целевой функции n2 и n3.

Результаты расчетов n1, n2, n3 свести в таблицу аналогично табл. 4.

Программа расчета эффективности для различных методов одномерной оптимизации в Mathcad приведена на рис. 29.

Рис. 29. Программа расчета эффективности различных методов одномерной оптимизации.

По сопоставлению значений n, n1, n2 оценивается эффективность каждого из методов, что позволяет сделать заключение о наиболее эффективном методе.

Пример расчета эффективности методов для одной из функций при различный значения точности показан в табл.4.

Таблица 4

Метод оптимизации	Число вычислений F(x)
Заданная точность е	0,1	0,01	0,001
Равномерный поиск (n1)	14	140	14000
Деление отрезка пополам (n2)	4	14	32
«Золотого сечения» (n3)	3	11	24

Анализ результатов расчета эффективности для данной целевой функции позволяет заключить:

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

- при увеличении точности расчетов на порядок количество вычислений целевой функции в методе равномерного поиска возрастает пропорционально, а в методах деления отрезка пополам и «золотого сечения» по логарифмическому закону.

Пользуясь полученными значениями n1, n2, n3, рассчитать показатель эффективности ξ для каждого из методов и сделать выводы о наиболее эффективном методе для своего варианта задания.