Методи прямого пошуку для оптимізації унімодальних функцій якості без обмежень

 

4. Опис програми

 

Програма написана на мові Паскаль процедурним методом програмування.

Алгоритм  методу золотого січення показано нижче.

 

Рис. 2. Метод  золотого січення

Це один з найпростіших з методів пошуку мінімуму і він володіє гарантованою лінійною швидкістю збіжності, що не залежить від функції, мінімум якої шукається. Відрізок поділяється на частині, і на кожнім кроці приймається рішення: "ліворуч" чи "праворуч", без обліку особливостей поводження функції. Поза залежністю від того, яке значення функції ми одержали, вибравши лівий відрізок, що випливає значення функції ми будемо вважати в точці A, а вибравши правий, наступною точкою буде точка B.

Разом з тим, можна враховувати те, що в околицях мінімуму функція звичайно добре описується параболою. Перший прихожий у голову варіант: побудувати по трьох відомих значеннях функції параболу, і знайти її мінімум. Потім вибрати поруч зі знайденим наближенням до мінімуму ще три точки, і знову побудувати параболу, одержавши наступне наближення.

Швидкість збіжності такого методу квадратична, однак, такий метод на практиці незастосовний. По-перше, поблизу мінімуму гладка функція поводиться, як парабола, але на негладкій функції метод може дати збій. По-друге, до мінімуму треба ще підібратися досить близько, а удалині від мінімуму функція поводиться, як хоче, і можна запросто зійтися до максимуму замість мінімуму, чи ж виявитися "викинутим" за межі області пошуку при визначенні мінімуму чергової параболи.

Інший метод прямого пошуку - метод Брента сполучив у собі риси методу золотого перетину і методу параболічної інтерполяції. Він характеризується квадратичною швидкістю збіжності в околицях мінімуму гладких функцій і гарантованою лінійною швидкістю збіжності у випадку, якщо потрапиться негладка чи функція функція з дуже складним рельєфом. [1,4]

Небагато  про принципи роботи. Алгоритм зберігає в пам'яті п'ять точок: точки  a і b обмежують відрізок [a, b], у якому локалізований мінімум, у точках x, w, v зберігаються три точки з найкращими значеннями f(x), отримані алгоритмом за час роботи. По цим трьох точках будується парабола, у мінімумі якої обчислюється наступне значення функції. У випадку, якщо передбачуваний мінімум розташований за межами відрізка [a, b] чи якщо виконуються деякі умови, що говорять про негладкість чи функції про те, що ми ще не виявилися в околиці экстремума з квадратичної скосростью збіжності, те наступний крок робиться не на основі параболічної інтерполяції, а на основі методу золотого перетину.

Алгоритм  шукає локальний мінімум функції F(X) на відрізку [a,b].

Вхідні  параметри:

• a - ліва границя відрізка, на якому шукається мінімум
• b - права границя відрізка, на якому шукається мінімум
• Epsilon - абсолютна точність, з яким знаходиться розташування мінімуму

Вихідні параметри:

• XMin - точка знайденого мінімуму

Результат: значення функції в знайденому мінімумі  
 
 

Алгоритм  методу Брента показано нижче.

Рис. 3. Метод  Брента

5. Аналіз  контрольного прикладу

 

       На  початку роботи програми користувачеві  пропонується вибрати метод пошуку:

      Продемонструємо результат методу золотого січення:

Дослідимо залежність інтервалу, у який потрапляє  точка, від кількості розбиттів.

 

      Тепер оберемо метод Брента.

       Результат роботи методу Брента показано нижче.

 

      Залежність  результуючої точки від точності показано на наступному рисунку:

      

      При визначенні швидкодії двох методів експериментальним шляхом було встановлено, що незважаючи на довший програмний код, метод Брента при тих самих вхідних даних працює на 0.003 с швидше, ніж метод золотого січення.

 

6. Висновки

 

      У ході роботи над курсовою роботою  було вивчено методи прямого пошуку для оптимізації унімодальних функцій якости без обмежень. Серед методів пошуку бул розглянуто методи золотого січення, Фібоначчі та Брента. Перший та останній з них реалізовані у програмі на мові Паскаль. 

      Виконання курсової роботи дозволило поглибити мої теоретичні та практичні зання.

 

7. Список літературних джерел

 

1. Катренко  А.В. Дослідження операцій.
2. Обзор методов безусловной оптимизации. www/ict.nsc.ru/rus/textbooks/akhmarov/mo/
3. Многопараметрическая оптимизация. www/energy/power/bmst.ru
4. http://algolist/manual/ru/translator

 

8. Додатки

uses crt;

label beg,et,nt;

var a,b,e,x:real;

n,c,typ:integer;

procedure GoldenSectionOptimize(var A : real; var B : real; N,typ : Integer);

var

    i : Integer;

    S1 : real;

    S2 : real;

    U1 : real;

    U2 : real;

    FU1 : real;

    FU2 : real;

begin

    S1 := (3-Sqrt(5))/2;

    S2 := (Sqrt(5)-1)/2;

    U1 := A+S1*(B-A);

    U2 := A+S2*(B-A);

    case typ of

    1:begin  FU1 := sin(U1); FU2 := sin(U2); end;

    2:begin  FU1 := cos(U1); FU2 := cos(U2); end;

    3:begin  FU1 := ln(U1); FU2 := ln(U2); end;

    end;

    i:=1;

    while i<=N do

    begin

        if FU1<=FU2 then

        begin

            B := U2;

            U2 := U1;

            FU2 := FU1;

            U1 := A+S1*(B-A);

            case typ of

    1:begin  FU1 := sin(U1); end;

    2:begin  FU1 := cos(U1); end;

    3:begin  FU1 := ln(U1);  end;

            end;

        end

        else

        begin

            A := U1;

            U1 := U2;

            FU1 := FU2;

            U2 := A+S2*(B-A);

            case typ of

    1:begin  FU2 := sin(U2); end;

    2:begin  FU2 := cos(U2); end;

    3:begin  FU2 := ln(U2); end;

            end;

        end;

        Inc(i);

    end;

end; 

Function MySign(a, b : real) : real;

   var Result : real;

begin

    If b>0 then

        Result := Abs(a)

    Else

        Result := -Abs(a);

      MySign := Result;

End ; 
 

function BrentOptimize(a,b,Epsilom: real;typ:integer; var Xmin:real): real;

var   

    Result,ia,ib,bx,d,e,etemp,e2,fu,fv,fw,fx,p, temp1,temp2,q,r,u,v,w,x,xm,cgold: real;

    iter:integer;

    b1,b2,b3:boolean;

    begin

    cgold := 0.3819660;

    bx := 0.5*(a+b);

    e2:=Epsilom*2;

    If a<b then

        ia := a

    Else

        ia := b;

   

    If a>b then

        ib := a

    Else

        ib := b;

 

    v :=bx;

    w :=v;

    x :=v;

    e :=0.0;

        case typ of

    1: fx := sin(x);

    2: fx := cos(x);

    3: fx := ln(x);

    end;

    fv := fx;

    fw := fx;

    For iter:=1 To 100 do begin

        xm := 0.5*(ia+ib);

        If Abs(x-xm)<=e2-0.5*(ib-ia) then

            break;

        If Abs(e)>Epsilom then begin

            r := (x-w)*(fx-fv);

            q := (x-v)*(fx-fw);

            p := (x-v)*q-(x-w)*r;

            q := 2*(q-r);

            If q>0 then

                p := -p; 

            q := Abs(q);

            etemp := e;

            e := d;

            if  not (Abs(p)>=Abs(0.5*q*etemp))  then b1:=true else b1:=false;

            if not (p<=q*(ia-x)) then b2:=true else b2:=false;

            if not (p>=q*(ib-x)) then b3:=true else b3:=false;

            If b1 Or b2  Or b3 then begin

                d := p/q;

                u := x+d;

                if u-ia<e2 then b1:=true else b1:=false;

                if ib-u<e2 then b2:=true else b2:=false;

                If b1 Or b2 then

                    d := MySign(Epsilom, xm-x);

                End

            Else begin

                If x>=xm then

                    e := ia-x

                Else

                    e := ib-x;

                d := cgold*e;

                end  end

        Else begin

            If x>=xm then

                e := ia-x

            Else