Исследование методов оптимизации
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
72577143620,9721125960,96670099114,7557785614259005,39134331530,9602526060,94929807514,6474534571582005,17083115740,9441204790,93714339414,5458088271694004,99936495450,9312507040,92245524514,4500157556303004,85103852160,9170526690,90990556714,3595224191039004,71534384970,9042653410,89664829414,2738949399639004,58811715680,8912104990,88436899814,1927681121372004,46748661190,8788695370,87203035014,1158178434957004,352565782100,8666286260,86023055214,0427530347540004,242801681110,8548316090,84858970013,9733086626862004,137814211120,8432508970,83731403713,9072429878283004,037283606130,8320015420,82626120613,8443345058966003,940936337140,8209955530,81549774313,7843800451890003,848521743150,8102669790,80496695713,7271928088998003,759812059160,7997783960,79468635813,6726008530993003,674595835170,7895358000,78463034513,6204456363624003,592677880180,7795203660,77479971113,5705807907100003,513876598190,7697288170,76518041613,5228709928576003,438023378200,7601494720,75576791813,4771909740798003,364961115210,7507763520,74655274913,4334246232260003,294543452220,7416007980,73752898313,3914641877660003,226633778230,7326163680,72868919813,3512095525295003,161104506240,7238159110,72002740613,3125675921953003,097836320250,7151932480,71153729213,2754515864311003,03671754618260,0000004250,00000042512,0000000000004000,00000120218270,0000004220,00000042212,0000000000004000,00000119318280,0000004190,00000041912,0000000000004000,00000118418290,0000004150,00000041512,0000000000003000,00000117418300,0000004120,00000041212,0000000000003000,00000116518310,0000004090,00000040912,0000000000003000,00000115618320,0000004060,00000040612,0000000000003000,00000114718330,0000004020,00000040212,0000000000003000,00000113818340,0000003990,00000039912,0000000000003000,00000112918350,0000003960,00000039612,0000000000003000,00000112018360,0000003930,00000039312,0000000000003000,00000111218370,0000003900,00000039012,0000000000003000,00000110318380,0000003870,00000038712,0000000000003000,00000109418390,0000003840,00000038412,0000000000003000,00000108618400,0000003810,00000038112,0000000000003000,00000107718410,0000003780,00000037812,0000000000003000,00000106918420,0000003750,00000037512,0000000000003000,00000106118430,0000003720,00000037212,0000000000003000,00000105218440,0000003690,00000036912,0000000000003000,00000104418450,0000003660,00000036612,0000000000003000,00000103618460,0000003630,00000036312,0000000000003000,00000102818470,0000003610,00000036112,0000000000003000,00000102018480,0000003580,00000035812,0000000000003000,00000101218490,0000003550,00000035512,0000000000003000,00000100418500,0000003520,00000035212,0000000000002000,000000996
Данные по количеству итераций и заданным точностям для градиентного метода сведены в таблицу 5.14
Таблица 5.14 - Зависимость числа итераций от точности
ТочностьКоличество итераций0,13820,016760,0019690,000112630,0000115560,0000011850
Рисунок 5.2 Графическое представление зависимости количества итераций N от точности E для градиентного метода.
Таким образом, анализируя полученные зависимости можно сделать вывод о том, что метод Нелдера-Мида является более эффективным. Так же следует отметить, что градиентный метод быстро приближается к экстремуму, когда текущая точка находится далеко от него, и резко замедляется вблизи экстремума.
Следует заметить, что эффективность применения методов оптимизации прежде всего обусловлена видом функции.
6. ЗАКЛЮЧЕНИЕ
В курсовой работе произведена минимизации функции с помощью метода оптимизации нулевого порядка метода Нелдера-Мида и метода оптимизации первого порядка градиентного метода с дроблением шага.
В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции: . Данный оптимум достигается в точке . Этот метод позволяет найти минимум (при начальной точке Х (1 ; 1)) за 29 итераций при точности решения . При этом параметр останова равен 0,0000921.
В результате реализации градиентного метода минимальное значение функции составляет . Данный оптимум достигнут в точке . Этот метод позволяет найти минимум (при начальной точке Х(1;1)) за 1263 итерации при точности решения . При этом параметр останова равен 0,000099491.
Для каждого из методов была установлена зависимость числа итераций от заданной точности . Анализируя полученные результаты, можно сделать вывод о том, что по числу итераций более эффективным является метод Нелдера-Мида. Однако следует отметить, что эффективность этих методов может изменяться в зависимости от выбора начального приближения и вида функции. Следует также учесть, что градиентный метод может быть непригоден в тех случаях, если расчет производных вызывает затруднение.
7. ПРИЛОЖЕНИЕ
В таблицах представлены координаты точек, образующих линии уровня
В настоящем приложении представлена реализация программного кода для каждого из методов оптимизации. Используемый язык программирования Visual Studio C# 2005.
Градиентный метод с дроблением шага
namespace GradientL
{public partial class Form1 : Form
{public Form1()
{InitializeComponent();}
public static string[] str = new string[100000];
struct Tk
{public double x1, x2;
public Tk(double X, double Y)
{x1 = X;
x2 = Y;}
public static Tk operator /(Tk v1, double q)
{return new Tk(v1.x1 / q, v1.x2 / q);}
public static Tk operator *(Tk v, double d)
{return new Tk(v.x1 * d, v.x2 * d);}
public static Tk operator *(Tk v1, Tk v2)
{return new Tk(v1.x1 * v2.x1, v1.x2 * v2.x2);}
public static Tk operator -(Tk v1, Tk v2)
{return new Tk(v1.x1 - v2.x1, v1.x2 - v2.x2);}
public static Tk operator +(Tk v1, Tk v2)
{return new Tk(v1.x1 + v2.x1, v1.x2 + v2.x2);}
public static double Dist(Tk v1, Tk v2)
{return Math.Sqrt((v1.x1 - v2.x1) * (v1.x1 - v2.x1) + (v1.x2 - v2.x2) * (v1.x2 - v2.x2));}
public override string ToString()
{return "(" + this.x1.ToString("f5") + ";" + this.x2.ToString("f5") + ")";}}
class Pr
{public static double f(Tk c)
{return 12 + c.x1 * c.x1 + (1 + c.x2 * c.x2) * c.x2 * c.x2 + (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 - c.x2) * (c.x1 - c.x2);}
static Tk gradient(Tk c)
{Tk N = new Tk(2 * c.x1 + 2 * c.x1 * c.x2 * c.x2 *
( c.x1 - c.x2)*(c.x1 - c.x2) + 2 * (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 - c.x2),
2 * c.x2*c.x2*c.x2+2*c.x2*(1+c.x2*c.x2)+
2*c.x2*c.x1*c.x1*(c.x1-c.x2)*(c.x1-c.x2)-2*(c.x1-c.x2)*
(c.x1*c.x1*c.x2*c.x2+100));
return N;}
public static double Dl(Tk c)
{return Math.Sqrt(c.x1 * c.x1 + c.x2 * c.x2);}
public static void Tr(double eps, ref Tk ca, out double fn, out int i)
{Tk cb = new Tk(1, 1), st = new Tk(0.5, 0.5);
Tk step = new Tk(1, 1), eq; i = 0;
do
{while (true)
{cb = ca - step * gradient(ca);
eq = st * step * gradient(cb) * gradient(cb);
if (f(cb - step * gradient(cb)) >= (f(cb) - Dl(eq)))
{ step.x1 /= 2;
step.x2 /= 2;}
else break;}
fn = f(ca);
i++;
str[i] = String.Format("{0}" + ") " + "{1}" + "; " +
"{2}" + "; " + "{3}" + ".", i.ToString(), ca.ToString(), fn.ToString("f6"), Dl(gradient(cb)).ToString("f6"));