Universitatea Politehnica din BucurestiFacultatea de Inginerie Electrica

Elaborarea si testarea algoritmilor de optimizare. Analiza performantelor

numerice pe aplicatii test

STUDENT: PIRVU ANDREEA-ELENA

GRUPA: IPSE1

BUCURESTI2015

1. Testarea Algoritmului Simplex Downhill (ASD) pentru o funcţie obiectiv convexă simplă, cu 2 parametri (Ftest2par.m). Se lansează în execuţie fişierul MATLAB ASD_Ftest2par.m. Se modifică eroarea eps (precizia de căutare) în intervalul 10-9 şi 10-2 şi se trasează:

a) graficul nr_evaluari = f(eps) b) graficul param_optim_X = f(eps) c) graficul param_optim_Y = f(eps) d) graficul val_min_f_obiectiv = f(eps) e) graficul curbelor de nivel ale funcţiei obiectiv (reprezentare în plan) cu evoluţia

punctului optim curent către minimul găsit (graficul se trasează pentru o singură valoare a lui eps).

Pentru a testa Algoritmului Simplex Downhill (ASD) putea rula programul ASD_Ftest2par in Matlab,modificand astfel valoarea erorii „eps” incepand cu valoarea 10-9 pana la 10-2.

Din Matlab extragem valorile nr_evaluari,param_optim_x,param_optim_y si val_min_f_obiectiv pentru diferitele valori ale erorilor. Vom realiza un tabel cu datele si vom face graficele in functie de eroarea „eps”.

eps nr_evaluari param_optim_x param_optim_y val_min_f_obiectiv1E-09 195 2 5 61E-08 185 2 5 61E-07 170 2 4,99 61E-06 142 1,9998 5,0004 61E-05 122 1,999 5,00014 61E-04 102 2,0074 4,9998 6,00011E-03 82 1,9843 4,9887 6,00041E-02 63 1,9439 5,0505 6,0057

a)

0E+00 5E-03 1E-02 2E-020

50

100

150

200

250

Graficul nr_evaluari = f(eps)

b)

0E+00 5E-03 1E-02 2E-021.91

1.92

1.93

1.94

1.95

1.96

1.97

1.98

1.99

2

2.01

2.02

Graficul param_optim_X = f(eps)

c)

0E+00 5E-03 1E-02 2E-024.95

4.96

4.97

4.98

4.99

5

5.01

5.02

5.03

5.04

5.05

5.06

Graficul param_optim_Y = f(eps)

d)

0E+00 5E-03 1E-02 2E-025.997

5.998

5.999

6

6.001

6.002

6.003

6.004

6.005

6.006

6.007

Graficul val_min_f_obiectiv = f(eps)

e) ) graficul curbelor de nivel ale funcţiei obiectiv (reprezentare în plan) cu evoluţia punctului optim curent către minimul găsit (eps= 10-2)

Din cele doua ultime grafice observam ca am obtinut valoarea minima cu ajutorul algoritmului. Acest algoritm determinist asigura aflarea punctului de minim global in cazul functiilor obiectiv de tip unimodal.

Dupa realizarea graficelor am putut observa ca pe masura ce valoarea erorii creste,numarul de evaluari creste ,obtinandu-se astfel parametrii doriti ,insa in cazul unor erori mici, algoritmul nu mai ofera randament , deoarece se opreste atunci cand atinge eroarea impusa , iar algoritmul se opreste fara a mai continua sa caute o alta valoare mai eficienta.

2. Testarea Algoritmului Simplex Downhill (ASD) pentru o funcţie obiectiv cu 2 parametri, cu mai multe minime, (Camila.m). Se lansează în execuţie fişierul MATLAB ASD_Camila.m. Se modifică eroarea eps (precizia de căutare) în intervalul 10 -9 şi 10-2 şi se trasează:

- graficul val_min_f_obiectiv = f(eps)- graficul nr_evaluari = f(eps)- graficul param_optim_X = f(eps)- graficul param_optim_Y = f(eps)- graficul curbelor de nivel ale funcţiei obiectiv (reprezentare în plan) şi evoluţia

punctului optim curent către minimul găsit (graficul se trasează pentru o singură valoare a lui eps).

Ca si in cazul Algoritmului Simplex Downhill (ASD),(Ftest2par.m), vom apela functia si vom lua fiecare eroare incepand cu 10-9 pana la 10-2.

Din Matlab extragem valorile nr_evaluari,param_optim_x,param_optim_y si val_min_f_obiectiv pentru diferitele valori ale erorilor. Vom realiza un tabel cu datele si vom face graficele in functie de eroarea „eps”.

eps nr_evaluari param_optim_x param_optim_y val_min_f_obiectiv

1E-09 199 -0,0899 0,7127 -1,0316

1E-08 179 -0,0899 0,7127 -1,0316

1E-07 169 -0,0898 0,7127 -1,0316

1E-06 150 -0,09 0,7127 -1,0316

1E-05 131 -0,0893 0,7125 -1,0316

1E-04 116 -0,913 0,7132 -1,0316

1E-03 76 -0,1389 0,7131 -1,0223

1E-02 76 -0,1389 0,7131 -1,0223

a)

0E+00 5E-03 1E-02 2E-02

-1.034

-1.032

-1.03

-1.028

-1.026

-1.024

-1.022

-1.02

-1.018

-1.016

Graficul val_min_f_obiectiv = f(eps)

b)

0E+00 5E-03 1E-02 2E-020

50

100

150

200

250

Graficul nr_evaluari = f(eps)

c)

0E+00 5E-03 1E-02 2E-02

-1

-0.9

-0.8

-0.7

-0.6

-0.5

-0.4

-0.3

-0.2

-0.1

0

Graficul param_optim_X = f(eps)

d)

0E+00 5E-03 1E-02 2E-020.712

0.7122

0.7124

0.7126

0.7128

0.713

0.7132

0.7134

Graficul param_optim_Y = f(eps)

e) - graficul curbelor de nivel ale funcţiei obiectiv (reprezentare în plan) şi evoluţia punctului optim curent către minimul găsit

In cazul acestui algoritm se poate observa ca eroarea impusa face ca algoritmul sa converge mai greu pentru o eroare mai mica,dar obtine valori de parametrii optimi impusi,iar pentru cazul in care eorile sunt mici , acest algoritm converge mai repede,insa erorile sunt mai mari ,oprindu-se mai repede convergenta pentru o valoare minima a functiei obiectiv.

3) Se consideră o coloană de transformator a cărei secţiune transversală se încadrează într-un cerc cu raza R, ca în Fig. 1. Valoarea parametrului geometric R (raza coloanei) este individuală, fiind indicată pentru fiecare student în parte în tabelele de mai jos. Coloana de transformator este realizată din pachete de tole, în două trepte.

Fig. 1. Coloană de transformator în două trepte.

Să se determine lăţimile optime ale celor două trepte (L1 şi L2) aşa încât suprafaţa de oţel So asociată secţiunii transversale a coloanei să fie maximă.

Notă: Pentru rezolvarea aplicaţiei 3 se va exprima suprafaţa So în funcţie de cele două lăţimi (L1 şi L2) şi se va utiliza ASD cu doi parametri în vederea maximizării funcţiei : So = f(L1, L2).]

Stiim ca:

Functia:

function out = Latimi trepte(x,y)

global nr_evaluari;

global R;

nr_evaluari = nr_evaluari +1

out= pi*(R^2)/2-2*x*sqrt(R^2-x^2)-2*y*sqrt(R^2-(x+y)^2);

Valorile utilizate

R=66[mm]

eps=1e-9

Am obtinut:

L2 =112.2859

L1 = 69.3965

Param_optim_x=34.6983

Param_optim_y = 21.4447

Aria_cerc = 1.3685e+04

Aria_totala_trepte = 9.6317e+03

Arie_ramasa = 4.0530e+03

Programul rulat pentru a obtine valorile latimilor optime ale treptelor unei coloane de transformator reprezinta un algoritm de optimizare pentru mai multe erori de cautare.

Marimea razei ,R, are un efect considerabil pentru latimile treptelor,deoarece acestea vor creste atat in lungime cat si in latime,indicand spre un dreptunghi care nu ofera o suprafata optima ca aceea a unui patrat.

4) Se va elabora un raport care conţine:- informaţii generale privind probleme şi algoritmi de optimizare- descrierea pe scurt a algoritmului ASD - rezultate obţinute (grafice) prin testarea ASD - rezolvarea problemei de optimizare a coloanei de transformator cu două trepte

folosind un algoritm de optimizare (la alegere)- concluzii privind rezultatele numerice obţinute.

OPTIMIZAREA SI ALGORITIMI DE OPTIMIZARE

Conceptul de optimizare este bine încetăţenit ca principiul de bază în analiza problemelor complexe de decizie sau alocare. Folosirea optimizării se bazează pe concentrarea atenţiei asupra unui singur obiectiv conceput să cuantifice performanţa şi calitatea deciziei într-o problemă ce ar necesita determinarea valorilor unui număr mare de variabile interconectate. Acest obiectiv este maximizat sau minimizat supus unor restricţii care să limiteze alegerea variabilelor de decizie. Dacă un aspect al problemei poate fi identificat şi caracterizat printr-un obiectiv (de exemplu: profitul într-o afacere) atunci optimizarea poate să ofere un cadru adecvat pentru o astfel de analiză. Optimizarea ar trebui privită ca un instrument de concepere şi analiză, şi nu ca un principiu care să ducă la soluţia corectă din punct de vedere filozofic. Formularea problemei implică întotdeauna găsirea unui echilibru între construirea unui model suficient de complex pentru a descrie cât mai bine problema şi uşurinţa de rezolvare a acestuia.

Proiectarea optimală a maşinilor electrice în raport cu anumite criterii impuse de beneficiar face apel tot mai frecvent la tehnici de analiză numerică evoluate care au la bază modele de câmp pilotate de algoritmi inteligenţi de optimizare numerică.

Algoritmii de optimizare numerică au cunoscut în ultimii ani o dezvoltare continuă şi un grad tot mai ridicat de aplicare în concepţia şi optimizarea echipamentelor şi proceselor, respectiv în rezolvarea problemelor inverse.

Concepţia asistată de calculator cuplată cu algoritmi de optimizare eficienţi:

-simplifică sarcina inginerului proiectant,

-diminueaza timpul de lucru şi costurile de personal.

Algoritmii de optimizare numerica se impart in doua mari clase, si anume algoritmi deterministi si algoritmi stochastici.

Algoritmul Simplex-Downhill (detalii, operaţii, paşii algoritmului) ASD este un algoritm determinist de ordin 0, necesitând evaluări doar ale funcţiei obiectiv, nu şi ale derivatelor sale.

In literatura de specialitate, poate fi numita metoda Monte Carlo sau algoritmul stochastic. Algoritmi random search sunt utili in rezolvarea problemelor de

optimizări globale prost structurate, în cazul în care funcţia obiectiv poate fi nonconvexa şi, eventual, discontinua pe un domeniu continuu, discret, sau mixte (continuu-discrete). O problemă optimizării globale cu variabile continue poate conţine mai multe optime locale sau puncte staţionare. O problemă cu variabile discrete se încadrează în categoria de optimizăre combinatorica. O combinaţie de variabile continue si discrete apare în multe sisteme complexe, inclusiv probleme de proiectare, programare, şi alte aplicaţii în sistemele biologice şi economice.

Algoritmul Simplex Downhill este unul dintre algoritmii de optimizare numerica cei mai robusti si simpli de implementat. Acest algoritm de tip determinist asigura aflarea punctului de minim global in cazul functiilor obiectiv de tip unimodal. Dezavantajul sau principal, comun tuturor algoritmilor deterministi, iese in evidenta in cazul functiilor obiectiv cu mai multe puncte de minim cand plecand de la aceleasi puncte initiale algoritmul conduce intotdeauna la aceeasi solutie care nu este neaparat minimul global al functiei obiectiv. Acest dezavantaj poate fi depasit repornind algoritmul din diferite puncte de plecare initiale distribuite aleator sau uniform in domeniul de cautare. Ulterior cea mai mica valoare selectata din lista punctelor de minim corespunzatoare diferitelor puncte de plecare initiale va fi considerata punct de minim global al problemei de optimizare. In practica, o buna parte dintre problemele de optimizare bine formulate avand suport fizic nu au decat un singur punct de minim care este de fapt punctual de minim global al functiei obiectiv.

Avantajele ASD: simplitate si robusteţe.

Un simplex este o figură geometrică care în cazul problemelor cu n parametri este un poliedru cu n+1 vârfuri, ce conţine toate interconexiunile de tip segmente între vârfuri, feţe poligonale, etc.

Probleme de optimizare cu:

- 2 parametrii => simplex = triunghi,

- 3 parametrii => simplex = tetraedru etc.

Prezinta interes structurile simplex nedegenerate, care delimitează un volum interior n - dimensional nenul.

În cazul problemelor de optimizare n - dimensionale ASD are nevoie de n+1 puncte de plecare care definesc simplexul iniţial. ASD presupune o serie de paşi, in mare parte pentru a deplasa punctul în care FO ia valoarea cea mai mare (pt. pb. de minimizare). Deplasarea acestui punct se face spre faţa opusă a simplexului, într-un punct în care se presupune că FO ia o valoare mai mică. Acest tip de operaţie se numeşte reflexie şi este construită aşa încât simplexul să păstreze acelaşi volum ca cel iniţial. Pentru a accelera viteza de căutare, simplexul este capabil să efectueze şi operaţii de expansiune.

Algoritmul Random Search

ARS face parte din clasa algoritmilor stochastici si permite o explorare aleatoare a domeniului de cautare in vederea gasirii punctului de minim al functiei obiectiv.

Avantajele ARS:

- Este un algoritm de ordinul 0, deci nu necesita decat evaluarea functiei obiectiv si nu si a derivatelor sale,

- Este simplu de inteles, respectiv de implementat si este bine adaptat aplicatiilor practice.

Varianta imbunatatita a ARS tine cont de urmatoarele observatii :

- Daca alegerea unei directii de cautare conduce la o valoare mai mare a functiei obiectiv, directia opusa ar putea conduce la o valoare mai mica;

- Daca o anumita directie de cautare conduce la rezultate pozitive, aceasta ar trebui sa polarizeze cautarile uterioare. Dimpotriva, esecuri succesive dupa o anumita directie de cautare, ar trebui sa descurajeze cautarile ulterioare dupa respectiva directie.

Modele de grafic: