sprawko powell, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki i inne, DROPBOX, Laboratorium, lab4


Metoda Powella

Dana jest funkcja 4 zmiennych, dla której mamy przeprowadzić minimalizację z wykorzystaniem metody Powella.

Plik fn.m - implementacja funkcji w Matlabie:

function y = fn(x)

y=1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);

%dana funkcja zmiennych x1,x2,x3,x4


Plik powell.m - algorytm metody Powella:

function wynik = powell(x,eps)

p = 1;

i=0;

baza=[1,0,0,0;

0,1,0,0;

0,0,1,0;

0,0,0,1];

%pętla działająca do momentu spełnienia kryterium stopu

while( p > eps)

%wywołanie metody złotego podziału dla każdej współrzędnej

x0=x;

x=x+baza(:,1)*zlotyp(x,baza(:,1),eps);

x=x+baza(:,2)*zlotyp(x,baza(:,2),eps);

x=x+baza(:,3)*zlotyp(x,baza(:,3),eps);

x=x+baza(:,4)*zlotyp(x,baza(:,4),eps);

%wyznaczenie nowego kierunku poszukiwań

baza(:,5) = x0 - x;

%wywołanie metody złotego podziału dla wyznaczonego kierunku

x = x + baza(:,5)*zlotyp(x,baza(:,5),eps);

%kryterium stopu

p = sqrt( (x0(1)-x(1))^2 + (x0(2)-x(2))^2 + (x0(3)-x(3))^2 +(x0(4)-x(4))^2 );

%aktualizacja bazy kierunków

baza(:,1) = baza(:,2);

baza(:,2) = baza(:,3);

baza(:,3) = baza(:,4);

baza(:,4) = baza(:,5);

%licznik iteracji

i=i+1;

end

%wyświetlenie wyniku

pkt=x'

wynik = fn( x );

i

Plik zlotyp.m - algorytm metody złotego podziału:

function min = zlotyp(x,baza,eps)

%ustalenie punktów granicznych

zakres = 200 ;

a = -zakres;

b = zakres;

k = (sqrt(5)-1)/2;

j=1;

while j==1

while( (b-a) > eps )

%wybór 2 punktów wewnątrz przedziału poszukiwań

xp = b-((b-a)*k);

xk = a+((b-a)*k);

if fn(x+xp*baza) > fn(x+xk*baza)

a=xp;

xp = b-((b-a)*k);

xk = a+((b-a)*k);

else

b=xk;

xk = a+((b-a)*k);

xp = b-((b-a)*k);

end

end

%zwracana współrzędna punktu optymalnego

min = (xp+xk)/2;

%sprawdzenie czy zwrócony punkt nie jest punktem granicznym przedziału

%i ewentualne przesunięcie przedziału

if((a+eps)>min && (a-eps)<min)

a = a-zakres+eps;

b = a+eps;

j = 0;

end

if((b-eps)<min && (b+eps)>min)

a = b-eps;

b = b+zakres-eps;

j = 0;

end

end

Sprawdziliśmy poprawność działania napisanych algorytmów poprzez znalezienie minimum funkcją fminsearch:

f=@(x)1542+20*x(1)*x(4)+8*x(3)^2+96*x(2)*x(3)+96*x(1)*x(3)+298*x(2)^2+616*x(1)*x(2)+333*x(1)^2+40*x(4)+16*x(3)+286*x(2)+5*x(4)^2+10*x(2)*x(4)+556*x(1);

[min, fval] = fminsearch (f, [-1, 1,1,1]);

min

fval


Otrzymany wynik jest zbliżony do wyników zwracanych przez metodę Powella:

min =

-8.0000 1.0000 41.0000 11.0000

fval =

9.0000

W dalszej części sprawozdania wykorzystamy te same dane startowe, których używaliśmy dla metody Gaussa - Seidla w celu porównania działania obydwu metod.

Przykładowy przebieg procesu znajdowania minimum funkcji metodą Powella dla punktu początkowego (-7.5 , 0.5 , 39.5 , 10.5) oraz epsilon równego 0.01:

nr iteracji

punkt osiągnięty

wartość funkcji

kryterium stopu (T/N)

1

-7.3332, 0.5294, 39.6210, 10.1357

15.2734

0.4196 - Nie

2

-7.9436, 0.8511, 41.5488, 11.0978

9.0418

2.2624 - Nie

3

-7.9445, 0.8517, 41.5577, 1.0372

9.0224

0.0612 - Nie

4

-7.9444, 0.8518, 41.5579, 1.0373

9.0224

2.0844e-004 - Tak


W poniższej tabeli zamieściliśmy rezultaty kilku wywołań metody Powella dla różnych punktów przy stałej wartości epsilon.

liczba iteracji

punkt startowy

punkt osiągnięty

wartość minimum

epsilon

8

0; 0; 0; 0

-8.0001, 1.0000, 41.0002, 10.9997

9.0000

0.001

7

1; 1; 1; 1

-8.0000, 0.9999, 41.0005, 11.0000

9.0000

0.001

7

1; 2; 3; 4

-8.0000, 1.0001, 40.9997, 11.0000

9.0000

0.001

5

4; 8; 15; 16

-10.8253, 6.6524, 24.3410, 10.9982

49.6496

0.001

10

0; 8; 0; 19

-8.0000, 1.0001, 40.9997, 10.9998

9.0000

0.001

10

10; 20; 30; 40

-8.0000, 1.0000, 41.0000, 11.0000

9.0000

0.001

7

88; 27; -13; 105

-9.4885, 5.1450, 24.1135, 13.0921

87.2224

0.001

10

-100; -2000; 3; 4

-7.8319, 0.9439, 41.4517, 11.4375

22.2019

0.001

Dobór punktu startowego ma nieznaczny wpływ na ilość iteracji, gdyż metoda ogólnie jest szybka. W większości przypadków funkcja zwróciła oczekiwany wynik. Dla kilku punktów znalezione minimum znacząco odbiega od pozostałych. Sprawdziliśmy, że zmniejszenie wartości epsilon pozwoliło uzyskać prawidłowy wynik przy nieznacznym wzroście liczby iteracji.

W poniższej tabelce zamieściliśmy rezultaty kilku wywołań metody Powella dla stałego punktu startowego przy różnych wartościach epsilon.

liczba iteracji

punkt startowy

punkt osiągnięty

wartość minimum

epsilon

4

0,0,0,0

-9.5725, 5.2395, 25.0033, 9.9010

27.3536

0.1

6

0,0,0,0

-9.4523, 4.8905, 26.4346, 9.9684

24.4486

0.01

8

0,0,0,0

-8.0001, 1.0000, 41.0002, 10.9997

9.0000

0.001

7

0,0,0,0

-8.0000, 1.0000, 40.9999, 11.0000

9.0000

0.002

15

0,0,0,0

-8.0007, 1.0048, 40.9763, 10.9999

9.0001

0.007

11

0,0,0,0

-8.0000, 1.0000, 41.0001, 11.0000

9.0000

0.0001

7

0,0,0,0

-8.0000, 1.0000, 40.9999, 11.0000

9.0000

0.0004

14

0,0,0,0

-8.0000, 1.0001, 40.9997, 11.0000

9.0000

0.0009

Z analizy wyników tego doświadczenia możemy wyciągnąć wniosek, że im mniejsza wartość epsilon, tym dokładniejszy wynik uzyskujemy, ale możliwy jest wzrost ilości iteracji. Przyjęcie zbyt dużej wartości epsilon powoduje, że znalezione minimum nie jest globalnym minimum funkcji, którego poszukiwaliśmy.

Wnioski ogólne

Metoda Powella jest skuteczna. Sprawność i szybkość jej działania zależą od wyboru punktu startowego oraz dokładności epsilon. Odpowiednie dobranie epsilon ma szczególne znaczenie, gdyż dla zbyt dużych wartości funkcja zatrzymywała się w punkcie, który nie był minimum globalnym.
Dla zadanej funkcji minimum znajduje się w punkcie (-8,1,41,11), a jego wartość wynosi 9.

Wcześniej implementowaliśmy metodę Gaussa - Seidla. Po porównaniu wyników uzyskanych dla tych samych punktów i dokładności, stwierdzamy, że metoda Powella jest o wiele szybsza. Często nawet stukrotnie. Uzyskane wyniki również w większości przypadków są bardziej dokładne.



Wyszukiwarka

Podobne podstrony:
sprawko moo1, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
sprawko nowe, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
2Sprawozdanie z MOO, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce,
moo1 barteksprawko, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce,
2analityczne, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki
sprawozdanie-MaciejPawnukTomaszImiołek, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Opty
sprawko-6, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Laborki, lab6, got
sciaga kolos, Automatyka i Robotyka, Semestr III, Metody numeryczne
SPRAWKO 4 EiE nasze, Automatyka i Robotyka, Semestr III, Elektrotechnika i Elektromechanika, Gotowce
Mechanika - opracowanie, Automatyka i Robotyka, Semestr III, Mechanika, Gotowce, Mechanika, Mechanik
BD Lesiu, Automatyka i Robotyka, Semestr III, Bazy Danych, Gotowce
metody numeryczne wartosc funkcji, Automatyka i Robotyka, Semestr IV, Metody Numeryczne, Lab, lab2
Sprawko liniow, Automatyka i Robotyka, Semestr 5, EiN, sprawka
GR D, Automatyka i Robotyka, Semestr III, Bazy danych
sciaga a, Automatyka i Robotyka, Semestr III, Bazy danych
DAPTA spraweczko, Automatyka i Robotyka, Semestr III, Elektrotechnika i Elektromechanika, Gotowce, E

więcej podobnych podstron