1 Pakiety numeryczne Optymalizacja Łukasz Sztangret Katedra Informatyki Stosowanej i Modelowania

2 Optymalizacja „Dążenie człowieka do perfekcji znajduje swój wyraz w optymalizacji. Zajmuje się ona tym, jak opisać i osiągnąć Najlepsze, gdy wiemy już jak mierzyć i zmieniać Dobre i Złe […].” Beightler C. S., Phillips D. T., Wilde D. J., Foundations of optimization, Englewood Cliffs, N.J., Prentice-Hall, 1979.

3 Zadanie optymalizacji

4 Zbiór rozwiązań dopuszczalnych

5 Funkcja celu

6 Minimum globalne

7 Metody optymalizacji Programowanie liniowe, Metody bezgradientowe (bezpośredniego szukania), Metody gradientowe, Metody niedeterministyczne.

8 Problem binarny Wektor x może przyjmować jedynie wartości 0 lub 1. Szukamy maksimum funkcji celu: przy ograniczeniach: [x_opt y_opt] = bintprog(f,A,b,Aeq,beq) Funkcja bintprog szuka minimum funkcji celu przy ograniczeniach nierównościowych (zmienne A i b) oraz równościowych (zmienne Aeq i beq). Wartości zwracane to wektor zmiennych decyzyjnych x_opt oraz wartość funkcji celu y_opt.

9 Dyskretny problem plecakowy Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka. Lp.WartościWaga 1757 22708 32506 4354 5103 61009

10 Dyskretny problem plecakowy f=-[75 270 250 35 10 100]; A=[7 8 6 4 3 9]; b=10; [x_opt y_opt]=bintprog(f,A,b) Optimization terminated. x_opt = 0 0 1 1 0 0 y_opt = -285 LpWartościWaga 1757 22708 32506 4354 5103 61009 Znak minus jest konieczny ponieważ szukamy maksymalnej wartości plecaka a funkcja bintprog szuka wartości minimalnej

11 Dyskretny problem plecakowy Dodatkowe ograniczenie: zabierając przedmiot nr 3 musimy zabrać przedmiot nr 5 i odwrotnie. f=-[75 270 250 35 10 100]; A=[7 8 6 4 3 9]; b=10; Aeq=[0 0 1 0 -1 0]; beq=0; [x_opt y_opt]=bintprog(f,A,b,Aeq,beq) Optimization terminated. x_opt = 0 1 0 0 0 0 y_opt = -270 LpWartościWaga 1757 22708 32506 4354 5103 61009

12 Problem linowy Szukamy maksimum funkcji celu: przy ograniczeniach: [x_opt y_opt] = linprog(f,A,b,Aeq,beq,lb,ub) Funkcja linprog szuka minimum funkcji celu przy ograniczeniach nierównościowych (zmienne A i b), równościowych (zmienne Aeq i beq) oraz kostkowych (zmienne lb i ub). Wartości zwracane to wektor zmiennych decyzyjnych x_opt oraz wartość funkcji celu y_opt.

13 Ciągły problem plecakowy f=-[75 270 250 35 10 100]; A=[7 8 6 4 3 9]; b=10; [x_opt y_opt]=linprog(f,A,b) Exiting: One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far: the dual appears to be infeasible (and the primal unbounded). (The primal residual < TolFun=1.00e-008.) x_opt = 1.0e+014 * -0.0000 0.0000 1.1715 -0.0000 -0.7810 y_opt = -2.1478e+016

14 Ciągły problem plecakowy f=-[75 270 250 35 10 100]; A=[7 8 6 4 3 9]; b=10; lb=[0 0 0 0 0 0]; [x_opt y_opt]=linprog(f,A,b,[],[],lb) Optimization terminated. x_opt = 0.0000 1.6667 0.0000 y_opt = -416.6667

15 Poszukiwanie minimum funkcji jednej zmiennej z ograniczeniami f=@(x)(x-2).^2; lb=-2; ub=5; [x_opt y_opt]=fminbnd(f,lb,ub) x_opt = 2 y_opt = 0 Uchwyt do funkcji celu Dolne ograniczenie Górne ograniczenie Funkcja fminbnd wykorzystuje metodę złotego podziału oraz aproksymacji kwadratowej

16 Poszukiwanie minimum funkcji wielu zmiennych bez ograniczeń function y=fun_celu(x) y=(x(1)-5).^2+(x(2)-5).^2; [x_opt y_opt]=fminsearch(@fun_celu,[2;2]) x_opt = 5.0000 y_opt = 1.4622e-009 Uchwyt do funkcji celu Punkt startowy Funkcja celu jest zdefiniowana w osobnym pliku o nazwie fun_celu Funkcja fminsearch wykorzystuje metodę sympleks Neldera-Meada

17 Poszukiwanie minimum funkcji wielu zmiennych bez ograniczeń f=@(x)x(1).^2+x(2).^2; [x_opt y_opt]=fminunc(f,[2;2]) Warning: Gradient must be provided for trust-region algorithm; using line-search algorithm instead. > In fminunc at 365 Local minimum found. Optimization completed because the size of the gradient is less than the default value of the function tolerance. x_opt = 0 0 y_opt = 0 Funkcja fminunc wykorzystuje metodę gradientową

18 Poszukiwanie minimum funkcji wielu zmiennych bez ograniczeń f=@(x)x(1).^2+x(2).^2; g=@(x)[2*x(1); 2*x(2)]; opcje=optimset('GradObj','on'); [x_opt y_opt]=fminunc({f;g},[2;2],opcje) Local minimum found. Optimization completed because the size of the gradient is less than the default value of the function tolerance. x_opt = 0 0 y_opt = 0

19 Poszukiwanie minimum funkcji wielu zmiennych bez ograniczeń function [y dy]=fun_celu(x) syms X Y f=X.^2+Y.^2; g=gradient(f); X=x(1); Y=x(2); y=eval(f); dy=eval(g); opcje=optimset('GradObj','on'); [x_opt y_opt]=fminunc(@fun_celu,[2;2],opcje) Local minimum found. Optimization completed because the size of the gradient is less than the default value of the function tolerance. x_opt = 0 0 y_opt = 0 Utworzenie dwóch zmiennych symbolicznych Zdefiniowanie funkcji celu (również zmienna symboliczna) Zdefiniowanie gradientu funkcji f Zmiennym X oraz Y przypisujemy konkretne wartości liczbowe Obliczamy wartość funkcji i jej gradientu w punkcie o współrzędnych X oraz Y

20 Poszukiwanie minimum funkcji wielu zmiennych z ograniczeniami [x_opt y_opt]=fmincon(@fun_celu,x0,A,b,Aeq,beq,lb,ub,@ograniczenia) Uchwyt do funkcji celu Punkt startowy Ograniczenia nierównościowe Ograniczenia równościowe Ograniczenia kostkowe Ograniczenia nieliniowe function [c ceq]=ograniczenia(x) c=x(1).^2+x(2).^2-4; ceq=[];

21 Poszukiwanie minimum funkcji wielu zmiennych z ograniczeniami function y=fun_celu(x) y=(x(1)-5).^2+(x(2)-5).^2; function [c ceq]=ograniczenia(x) c=x(1).^2+x(2).^2-4; ceq=[]; [x_opt y_opt]=fmincon(@fun_celu,[10;10],[],[],[],[],[-5;-5],[15;15],@ograniczenia) x_opt = 1.4142 y_opt = 25.7157 Funkcja celu Funkcja z ograniczeniami nieliniowymi

22 Poszukiwanie minimum funkcji wielu zmiennych z ograniczeniami Algorytm genetyczny [x_opt y_opt]=ga(@fun_celu,N,A,b,Aeq,beq,lb,ub,@ograniczenia) Rozmiar przestrzeni poszukiwań function [c ceq]=ograniczenia(x) c=x(1).^2+x(2).^2-4; ceq=[];

23 Poszukiwanie minimum wielu funkcji wielu zmiennych z ograniczeniami [x_opt y_opt]=fminimax(@fun_celu,x0,A,b,Aeq,beq,lb,ub,@ograniczenia) Argumenty jak przy funkcji fmincon. Minimalizowana funkcja celu zwraca wektor (wiele funkcji celu). Funkcja fminimax poszukuje rozwiązania minimalizującego wszystkie funkcje celu. function y=fun_celu(x) y(1)=(x-1).^2; y(2)=(x+1).^2; [x_opt y_opt]=fminimax(@fun_celu,5) x_opt = 4.8750e-016 y_opt = 1.0000 1.0000

24 Dwukryterialna optymalizacja belki Belka o długości l i przekroju kołowym o średnicy d jest obciążona siłą P. Ugięcie belki pod wpływem działania siły wynosi: występujące naprężenie wynosi:

25 Dwukryterialna optymalizacja belki Zadanie polega na wyznaczeniu wymiarów belki: aby zapewnić minimalną masę belki oraz minimalne ugięcie. Dodatkowymi ograniczeniami są maksymalne ugięcie belki oraz maksymalne naprężenie wynoszące odpowiednio:

26 Dwukryterialna optymalizacja belki ro=7800; P=1e3; E=207e9; u_max=5e-3; sigma_max=300e6; l_lim=[200,1000]*1e-3; d_lim=[10,50]*1e-3; m=@(x)0.25*ro*x(1)*pi*x(2)^2; u=@(x)(64*P*x(1)^3)/(3*E*pi*x(2)^4); sigma=@(x)(32*P*x(1))/(pi*x(2)^3);

27 Dwukryterialna optymalizacja belki l=linspace(l_lim(1),l_lim(2),100); d=linspace(d_lim(1),d_lim(2),100); D=[]; P=[]; for i=1:length(l) for j=1:length(d) if u([l(i);d(j)])

28 Dwukryterialna optymalizacja belki figure('Color',[1 1 1]); plot(D(1,:),D(2,:),'.'); set(gca,'FontSize',28); xlabel('l[m]'); ylabel('d[m]'); figure('Color',[1 1 1]); plot(P(1,:),P(2,:),'.') set(gca,'FontSize',28); xlabel('m[kg]'); ylabel('u[m]');

29

30 Normalizacja max_m=m([l_lim(2);d_lim(2)]); min_m=m([l_lim(1);d_lim(1)]); max_u=u([l_lim(2);d_lim(1)]); min_u=u([l_lim(1);d_lim(2)]); m_norm=@(x)(m(x)-min_m)/(max_m-min_m); u_norm=@(x)(u(x)-min_u)/(max_u-min_u);

31 Optymalizacja dwukryterialna f=@(x)[m_norm(x);u_norm(x)]; x_opt=fminimax(f,… [range(l_lim)*rand+l_lim(1);range(d_lim)*rand+d_lim(1)],... [],[],[],[],[l_lim(1);d_lim(1)],[l_lim(2);d_lim(2)],... @(x)limits(x,u,sigma,u_max,sigma_max)); function [c ceq]=limits(x,u,sigma,u_max,sigma_max) ceq=[]; c=[u(x)-u_max;sigma(x)-sigma_max]; x_opt=[200mm; 18.9mm] m(x_opt)= 0.4394kg u(x_opt)= 2.0409mm

32 Metoda sumy ważonej w=0:0.01:1;n=length(w); M=zeros(1,n); U=zeros(1,n); for i=1:n f=@(x)w(i)*m_norm(x)+(1-w(i))*u_norm(x); x_opt=fmincon(f,… [range(l_lim)*rand+l_lim(1);range(d_lim)*rand+d_lim(1)],... [],[],[],[],[l_lim(1);d_lim(1)],[l_lim(2);d_lim(2)],... @(x)limits(x,u,sigma,u_max,sigma_max)); M(i)=m(x_opt); U(i)=u(x_opt); end

33 Metoda sumy ważonej figure('Color',[1 1 1]); plot(M,U,'*','MarkerSize',20,'LineWidth',3) set(gca,'FontSize',28); xlabel('m[kg]'); ylabel('u[m]');

34 Prezentacja udostępniona na licencji Creative Commons: Uznanie autorstwa, Na tych samych warunkach 3.0. Pewne prawa zastrzeżone na rzecz autorów. Zezwala się na dowolne wykorzystywanie treści pod warunkiem wskazania autorów jako właścicieli praw do prezentacji oraz zachowania niniejszej informacji licencyjnej tak długo, jak tylko na utwory zależne będzie udzielana taka sama licencja. Tekst licencji dostępny jest na stronie: http://creativecommons.org/licenses/by-sa/3.0/deed.pl