Одномерные методы безусловной оптимизации (методы Фибоначчи и квадратичной аппроксимации)

Міністерство освіти і науки, молоді та спорту України

Національний технічний університет

Харківський політехнічний інститут

Кафедра «Автоматизованих систем управління»

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

по предмету: Математичні методи дослідження операцій

на тему: Одномірні методи безумовної оптимізації (Методи Фібоначчі та квадратичної апроксимації)

Виконав:

Копп А.М.

Харків 2013



Цель работы

Изучить одномерные методы оптимизации, минимизировать функцию, заданную преподавателем, двумя методами; сравнить результаты оптимизации и выдать рекомендации по применению исследуемых методов.

Алгоритм метода Фибоначчи

Подготовительный этап:

1) Выбрать - точность вычисления минимума на интервале . Положить и .

2) .

3) Если

тогда , иначе и идти к 3.

4) Вычислить:

.

5) Если , тогда , и идти к 6. Если и идти к 6.

6) Положить .

Основной этап:

7) Если , тогда и идти к 8. Иначе , и идти к 9.

8) Вычислить

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

9) Вычислить

и . И идти к 10.

10) Если , то и идти к 11, иначе и идти к 11.

11) Если , тогда и идти к 7.

Иначе положить

и вычислить.



Блок-схема алгоритма



Алгоритм метода квадратичной аппроксимации

1) Вычислить

2) Вычислить и .

3) Если , тогда . Если , то .

4) Вычислить и найти , .

5) С использованием посчитать .

6) Условия окончания поиска: и . Если оба выполняются, закончить алгоритм. В противном случае - идти к шагу 7.

7) Выбрать «лучшую» точку среди или , И две точки слева и справа от нее. Расположить их в естественном порядке и идти к шагу 4.

После шага (5) следует провести дополнительную проверку, и в случае, если точка слишком далеко от , заменить ее точкой .



Блок-схема алгоритма

Код программы

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Data;

using ZedGraph;

namespace Algorithms

{

public class Fibonachi

{

private int func;

private double xOpt, fOpt;

private int iter;

private string process;

PointPairList points;

public PointPairList Points

{

get { return points; }

set { points = value; }

}

public string Process

{

get { return process; }

set { process = value; }

}

public double FOpt

{

get { return fOpt; }

set { fOpt = value; }

}

public double XOpt

{

get { return xOpt; }

set { xOpt = value; }

}

public int Iter

{

get { return iter; }

set { iter = value; }

}

public Fibonachi(int func)

{

this.func = func;

}

private double Func(double x)

{

if (func == 1)

{

return 2 * Math.Pow((x - 3), 2) + Math.Exp(Math.Pow(x, 2) / 2);

}

if (func == 2)

{

return (Math.Pow(x, 3) + x) / (Math.Pow(x, 4) - Math.Pow(x, 2) + 1);

}

return 0;

}

private double F(int p)

{

if (p == 1 || p == 2)

{

return 1;

}

else

{

return (F(p - 1) + F(p - 2));

}

}

public void Fibo(double a0, double b0, double eps)

{

points = new PointPairList();

int j = 1;

int m;

for (; ;)

{

if (F(j + 1) < (1 / eps) * (b0 - a0) && F(j + 2) >= (1 / eps) * (b0 - a0))

{

m = j;

break;

}

j++;

}

double x1s = a0 + (F(m) / F(m + 2)) * (b0 - a0);

double x2s = a0 + (F(m + 1) / F(m + 2)) * (b0 - a0);

double a1, b1;

if (Func(x1s) <= Func(x2s))

{

a1 = a0;

b1 = x2s;

}

else

{

a1 = x1s;

b1 = b0;

}

double x1k = x1s;

double x2k = x2s;

double ak = a1;

double bk = b1;

Process = "";

for (int k = 1; k <= m - 1; k++)

{

double x1k1, x2k1;

double ak1, bk1;

if (Func(x1k) <= Func(x2k))

{

x2k1 = x1k;

x1k1 = ak + (F(m - k) / F(m + 2)) * (b0 - a0);

}

else

{

x1k1 = x2k;

x2k1 = ak + (F(m - k + 1) / F(m + 2)) * (b0 - a0);

}

if (Func(x1k1) <= Func(x2k1))

{

ak1 = ak;

bk1 = x2k1;

}

else

{

ak1 = x1k1;

bk1 = bk;

}

Process += "x: " + (ak1 + bk1) / 2 + "; f(x): " + Func((ak1 + bk1) / 2) + "; итерация: " + k + ";\n";

points.Add(k, Math.Abs(ak1 - bk1));

x1k = x1k1;

x2k = x2k1;

ak = ak1;

bk = bk1;

}

XOpt = (ak + bk) / 2;

FOpt = Func(XOpt);

Iter = m - 1;

}

public void Quadratic(double x1, double deltaX, double eps1, double eps2)

{

points = new PointPairList();

double x2 = x1 + deltaX;

double x3;

if (Func(x1) > Func(x2))

{

x3 = x1 + 2 * deltaX;

}

else

{

x3 = x1 - deltaX;

}

int k = 1;

Process += "";

for (; ;)

{

double[] F = { Func(x1), Func(x2), Func(x3) };

double Fmin = F.Min();

int minIndex = Array.IndexOf(F, Fmin);

double xMin = 0;

switch (minIndex)

{

case 0: xMin = x1; break;

case 1: xMin = x2; break;

case 2: xMin = x3; break;

default: break;

}

double a1 = (F[1] - F[0]) / (x2 - x1);

double a2 = (1 / (x3 - x2)) * ((F[2] - F[0]) / (x3 - x1) -

(F[1] - F[0]) / (x2 - x1));

double xS = ((x2 + x1) / 2) - (a1 / (2 * a2));

if (xS > (x3 + deltaX))

{ оптимизация функция фибоначчи итерация

xS = x3 + deltaX;

}

if (Math.Abs(Fmin - Func(xS)) <= eps1 && Math.Abs(xMin - xS) <= eps2)

{

Process += "x: " + xS + "; f(x): " + Func(xS) + "; итерация: " + k + "; \n";

points.Add(k, Math.Abs(x1 - x3));

XOpt = xS;

FOpt = Func(xS);

Iter = k;

break;

}

else

{

double[] xBest = { Func(xS), Func(xMin) };

int minInd = Array.IndexOf(xBest, xBest.Min());

switch (minInd)

{

case 0: x2 = xS; break;

case 1: x2 = xMin; break;

default: break;

}

x1 = x2 - deltaX;

x3 = x2 + deltaX;

Process += "x: " + xS + "; f(x): " + Func(xS) + "; итерация: " + k + "; \n";

k++;

}

if (k > 10000)

{

Process = "Необходимо увеличить значения Е1 и Е2, или уменьшить шаг!";

break;

}

}

}

}

}

Результаты работы программы

Задание: f(x) = 2(x - 3)² + exp{x² / 2}, [0, 100]

Рисунок 1 - Решение методом Фибоначчи, график изменения длинны интервала неопределенности от номера итерации



Результат работы программы для метода Фибоначчи:

x: 19,0983005609879; f(x): 1,59730815994183E+79; итерация: 1;

x: 11,8033988780243; f(x): 1,79061609368607E+30; итерация: 2;

x: 7,2949016829636; f(x): 359433594996,898; итерация: 3;

x: 4,50849719506067; f(x): 25937,6006853167; итерация: 4;

x: 2,78640448790293; f(x): 48,6136188214171; итерация: 5;

x: 1,72209270715774; f(x): 7,67136451462504; итерация: 6;

x: 1,06431178074518; f(x): 9,25565487933309; итерация: 7;

x: 1,47084263507781; f(x): 7,62630189506422; итерация: 8;

x: 1,72209270715774; f(x): 7,67136451462504; итерация: 9;

x: 1,56681192490506; f(x): 7,52057196317356; итерация: 10;

x: 1,66278121473232; f(x): 7,56084342303454; итерация: 11;

x: 1,60346972230689; f(x): 7,51727760135902; итерация: 12;

x: 1,56681192490506; f(x): 7,52057196317356; итерация: 13;

x: 1,58946561992866; f(x): 7,51593707248513; итерация: 14;

x: 1,60346972230689; f(x): 7,51727760135902; итерация: 15;

x: 1,59482012966151; f(x): 7,51606349215786; итерация: 16;

x: 1,58946561992866; f(x): 7,51593707248513; итерация: 17;

x: 1,59276070284119; f(x): 7,51595867486789; итерация: 18;

x: 1,59070127602086; f(x): 7,51592415514834; итерация: 19;

x: 1,59193693211305; f(x): 7,51593644659914; итерация: 20;

x: 1,59111316138492; f(x): 7,51592544841694; итерация: 21;

x: 1,59070127602086; f(x): 7,51592415514834; итерация: 22;

x: 1,59028939065679; f(x): 7,51592566285447; итерация: 23;

x*: 1,59028939065679; f(x)*: 7,51592566285447; Число итераций: 23



Рисунок 2 - Решение методом квадратичной аппроксимации

Результат для метода квадаратичной аппроксимации:

x: 1,03; f(x): 9,46149700020013; итерация: 1;

x: 1,05; f(x): 9,34042093880804; итерация: 2;

x: 1,07; f(x): 9,22240461705795; итерация: 3;

x: 1,09; f(x): 9,10750938343364; итерация: 4;

x: 1,11; f(x): 8,99579975896803; итерация: 5;

x: 1,13; f(x): 8,8873436109131; итерация: 6;

x: 1,15; f(x): 8,78221233700656; итерация: 7;

x: 1,17; f(x): 8,6804810610181; итерация: 8;

x: 1,19; f(x): 8,58222884030586; итерация: 9;

x: 1,21; f(x): 8,48753888616402; итерация: 10;

x: 1,23; f(x): 8,39649879779722; итерация: 11;

x: 1,25; f(x): 8,30920081081562; итерация: 12;

x: 1,27; f(x): 8,22574206120736; итерация: 13;

x: 1,29; f(x): 8,14622486581229; итерация: 14;

x: 1,31; f(x): 8,07075702039334; итерация: 15;

x: 1,33; f(x): 7,99945211647944; итерация: 16;

x: 1,35; f(x): 7,93242987823748; итерация: 17;

x: 1,37; f(x): 7,86981652072031; итерация: 18;

x: 1,39; f(x): 7,81174513093462; итерация: 19;

x: 1,41; f(x): 7,75835607327569; итерация: 20;

x: 1,43; f(x): 7,70979742098812; итерация: 21;

x: 1,45; f(x): 7,66622541543119; итерация: 22;

x: 1,47; f(x): 7,62780495505703; итерация: 23;

x: 1,49; f(x): 7,59471011614841; итерация: 24;

x: 1,51; f(x): 7,56712470751294; итерация: 25;

x: 1,53; f(x): 7,54524286149153; итерация: 26;

x: 1,55; f(x): 7,52926966381242; итерация: 27;

x: 1,57; f(x): 7,51942182500937; итерация: 28;

x: 1,59; f(x): 7,5159283963241; итерация: 29;

x: 1,59068610054296; f(x): 7,51592416101319; итерация: 30;

x*: 1,59068610054296; f(x)*: 7,51592416101319; Число итераций: 30



Вывод

При выполнении лабораторной работы мною были изучены одномерные методы оптимизации (метод Фибоначчи и квадратичная аппроксимация), написана программа на языке C#, которая позволяет оптимизировать заданные функции этими методами.

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

Размещено на Allbest.ru

...