cursul nr1
DESCRIPTION
cursul 1 din algoritmi de optimizareTRANSCRIPT
CURSUL NR. 1.
INTRODUCERE ÎN PROBLEMATICA OPTIMIZĂRII. CLASIFICAREA PROBLEMELOR DE OPTIMIZARE. FORMA STANDARD A UNEI PROBLEME DE OPTIMIZARE.
1. INTRODUCERE
1.1. ASPECTE GENERALE PRIVIND PROBLEMELE DE OPTIMIZARE
În cadrul etapelor de proiectare (design), optimizarea a devenit o componentă necesară, obligatorie, atunci când
se impun cerinţe de performanţă a produsului realizat. Zona problematică nu se reduce doar la inginerie, fiind
cunoscute o serie de aplicaţii economice, de la evaluarea şi optimizarea performanţelor unei investiţii la aplicaţii
bancare ori din sfera asigurărilor. În anii din urmă, când optimizarea profitului a devenit un termen al limbajului
comun, aplicaţiile de optimizare, explicite ori implicite (de exemplu, programele care comanda maşinile
automate de croire/tăiere în industria lemnului ori industria confecţiilor) sunt tot mai prezente. De asemenea,
instrumentele soft-ware de tip MAT-LAB au cunoscut în ultimele versiuni îmbogăţirea semnificativă a
aplicaţiilor utilizabile pentru rezolvarea problemelor de optimizare.
Optimizarea reprezintă în cazul general acţiunea de obţinere a celui mai bun rezultat în anumite
condiţii impuse.
Conform definiţiei, procedeul poate fi aplicat unei extrem de largi varietăţi de probleme. Din domeniul
ingineriei, cele mai importante direcţii care au determinat în timp evoluţia tehnicilor de optimizare, sunt :
- proiectarea aerospaţială (probleme de masa minimă)
- inginerie civilă (dimensionarea structurilor de rezistenţă, dimensionarea grinzilor în structurile metalice,
dimensionarea spaţiilor utile din construcţii)
- proiectarea pieselor mecanice
- proiectarea dispoziţivelor electrotehnice (dimensionarea miezului magnetic, al înfăşurărilor, al
elementelor de răcire, controlul nivelului de vibraţii ori al armonicilor)
- proiectarea echipamentelor energetice şi a reţelelor energetice
- proiectarea unităţilor ori a liniilor de producţie
Din punct de vedere istoric, bazele clasice ale tehnicilor de optimizare, bazate pe operatori derivativi, au
fost puse prin lucrările lui Newton, Filipacci, Euler, dar mai ales prin cercetările lui Cauchy şi Lagrange.
Aceştia din urma au reuşit în sec. 19 să acopere teoretic domeniul clasic al problemelor de optimizare, pentru
funcţii liniare şi neliniare dar şi pentru cazurile aplicaţiilor care suferă restricţii.
Pînă la mijlocul sec.20 progresele în domeniul teoretic şi practice al tehnicilor de optimizare au fost
neînsemnate. Apariţia calculatorului numeric a schimbat fundamental direcţiile cercetării matematice şi a grăbit
în anii ’50 şi ’60 cercetările şcolii engleze de matematică care s-au orientat asupra domeniului algoritmilor
numerici. Al doilea impuls a venit din direcţia care se poate încadra sub numele generic de “inteligenţă
artificială”.
1
Elementele generale ale formulării unei probleme de optimizare presupun cunoaşterea prealabilă a
regulilor de proiectare dintr-un domeniu specific apoi abilitatea de a descrie proiectarea în termeni matematici.
Aceasta presupune:
- designul variabilelor
- designul parametrilor
- designul funcţiilor obiectiv
În cele ce urmează, prin termenul “design” vom desemna operaţiile de proiectare, alegere. Cum
termenul ales are o sferă mai largă în raport cu fiecare operaţie amintită, este potrivit în descrierea etapelor
algoritmilor, tehnicilor de optimizare.
1.2. CLASIFICAREA PROBLEMELOR DE OPTIMIZARE.
Problemele de optimizare pot fi descrise, clasificate în mai multe feluri, în funcţie de diverse moduri de
abordare:
A) pe baza existenţei constrîngerilor: optimizări cu ori făra constrîngeri
-problemele fără constrîngeri prezintă funcţtie obiectiv dar lipsesc constrîngerile aplicate variabilelor.
Ajustarea datelor masurate ori calculate, data fitting, este un domeniu tipic al acestui gen de optimizare.
Funcţia obiectiv trebuie sa fie obligatoriu una neliniară, deoarece minimum unei funcţii liniare fara
constrîngeri este -∞.
B) pe baza naturii variabilelor de design (variabile de proiectare) se definesc
două tipuri importante:
-optimizarea parametrilor (optimizare statică): problema este aflarea valorilor pentru setul de parametrii
de proiectare care formează un set de funcţii prescrise, supuse unor constrîngeri
-optimizarea traiectoriei (optimizare dinamică) : problema este aflarea setului de parametrii de
proiectare, care sunt funcţii continue de alţi parametrii, care minimizează functia obiectiv supusă unui set de
restricţii
C) pe baza structurii fizice a problemei se definesc două grupe:
-control optimal: sunt probleme de programare matematică ce presupune mai multe etape, unde fiecare
etapă este determinată de cea precedentă într-un mod prescriptibil. Sunt descrise de două tipuri de variabile:
cele de stare şi cele de control. Variabilele de control (variabilele de design) trebuiesc determinate aşa încît
să minimizeze toate funcţiile obiectiv (indicele de performanţă) supuse la setul de restrcţii, la nivelul tuturor
etapelor care definesc procesul.
-controlul suboptimal: nu minimizează îtregul set de variabile pe la nivelul tuturor etapelor din proces. De
multe ori ţn problemele practice de inginerie, adoptarea tehnicilor suboptimale poate simplifica remarcabil
soluţia problemei, pătrînd un nivel de performanţă impus iniţial
D) pe baza naturii ecuaţiilor modelului matematic: expresiile matematice ale funcţei obiectiv ori ale
constrîngerilor au permis dezvoltarea mai multor metode de rezolvare specifice claselor de probleme
2
următoare: liniare, neliniare, geometrice ori pătratice (quadratic). Vom reveni în detaliu asupra
specificului fiecărui tip de problemă enunţată în capitolele următoare.
-optimizarea liniară (programarea liniară): cînd funţia obiectiv şi toate constrîngerile sunt de tip liniar.
- optimizarea pătratică (programare pătratică): dacă funţia obiectiv este de tip pătratic iar toate
constrîngerile sunt de tip liniar. Metodele de rezolvare permit extinderea celor elaborate pentru optimizarea
liniară.
- optimizarea neliniară (programarea neliniară): unde una sau mai multe restricţii, constrîngeri sunt de
tip neliniar
E) pe baza valorilor permise variabilelor de design: probleme se împart în doua categorii:
-cu variabile întregi
-cu variabile reale
F) pe baza naturii de tip deterministic a variabilelor:
-deterministe
-stohastice
G) pe baza separabilităţii funcţiilor:
-probleme separabile dacă funcţiile ce descriu problema sunt separabile, adică pot fi descrise ca sumă
de n funcţii de unică variabilă
-probleme inseparabile daca funcţiile modelului matematic nu sunt separabile
H) pe baza numarului funcţiilor obiectiv:
-probleme cu unică funcţie obiectiv
-probleme multiobiectiv
Clasificarea propusă pînă acum este una derivată din aspectele matematice ori fizice ale modelelor pe baza
cărora se obţin soluţiile optimale. Este utilă de amintit şi clasificarea propusă în cadrul toolbox-ului de
optimizare MATLAB, respectiv algoritmi standard de optimizare şi algoritmi de optimizare de dimensiune
mare (large scale).
De asemenea metodele clasice de optimizare pot fi grupate în două categorii principale:
- metode neiterative (într-un singur pas) – utilizează operatori derivative şi folosesc proprietăţile de
derivabilitate, convexitate ale funcţiei obiectiv
- metode iterative – utilizează algoritmi numerici iterativi de aflare a optimului.
Startul metodei îl reprezintă o valoare iniţială aleasă arbitrar din spaţiul de căutare iar ulterior se calculează la
fiecare iteraţie o noua soluţie a problemei. Metodele iterative se împart la rîndul lor în două categorii:
- metode de căutare directă
- metode de gradient (de coborâre) - care reprezintă în prezent cele mai cunoscute şi utilizate metode de
optimizare
3
1.3. FORMA STANDARD A PROBLEMEI DE OPTIMIMIZARE
Exprimarea matematică generală a de optimizare se face astfel:
să se minimizeze: f(X1,X2,…,Xn) (1)
în prezenţa restricţiilor: h1(X1,X2,…,Xn)=0
h2(X1,X2,…,Xn)=0
hl(X1,X2,…,Xn)=0
g1(X1,X2,…,Xn)≤ 0
g2(X1,X2,…,Xn)≤ 0
gm(X1,X2,…,Xn)≤ 0
în condiţiile: xi,min≤ xi≤ xi,max
unde:
f(X1,X2,…,Xn) = funcţia obiectiv (cost) dată că funcţie de n parametrii
xi,min = valoarea minimă admisă pentru parametrul xi
xi,max = valoarea maximă admisă pentru parametrul xi
În cazul problemelor clasice de optimizare, funcţia obiectiv este unică. Se optimizează astfel un singur
aspect, considerat esenţial, al problemei (de exemplu, în cazul proiectării maşinilor electrice se alege drept
funcţie obiectiv doar randamentul). Practica impune însă unui produs ori unei acţiuni umane îndeplinirea
simultană a mai multor indici de calitate, funcţii obiectiv. În exemplul proiectării maşinii electrice, se poate
adaugă şi elementul cost că şi direcţie semnificativă al designului optimal global. Acest tip de proiectare, de
design, se numeşte design multiobiectiv (design multidisciplinar). În mod evident funcţiile obiectiv alese sunt
impuse de cerinţele temei de proiectare şi putem regăsi alături de randament ori preţ şi masă, temperatura
maximă, nivelul de vibraţii, conţinutul de armonici, viteze maxime ş.a.m.d. Conform percepţiei generale, ne
aşteptăm că aceste funcţii obiectiv să fie concurente, contradictorii. Exista totuşi şi situaţii în care ele sunt
obiective cooperante. Din punct de vedere al interesului actual, problemele de optimizare multiobiectiv sunt
cele mai importante, interesul pentru tehnicile şi algoritmii multiobiectiv fiind pe primul loc. În cazul
problemelor multiobiectiv, funcţia f va deveni vectorul f.
Din punct de vedere al formalismului matematic, minimizarea funcţiei obiectiv (a funcţiei cost)
este preferabilă şi are că semnificaţie practică tocmai reducerea efortului, resurselor necesare atingerii unui
anumit obiectiv, scop. În cazul în care funcţia obiectiv impune determinarea maximului (în cazul optimizării
randamentului unui echipament, instalaţii, proces) atunci se poate foarte simplu afla minimul funcţiei obiectiv
negate:
Min f(x)=Max [- f(x)] (2)
4