Algoritmi Evolutivi pentru Optimizare Multi-Criteriala - SPEA

Abstract:

Pentru început referatul cuprinde o introducere despre problemele de optimizare multi-criterială şi eficienţa acestei metode in favoarea metodelor clasice, cât şi o familiarizare cu anumiţi termeni necesari cum ar fi: optimizare multi-criterială, problemă de optimizare mulţi-criierială. soluţii în sens Pareto, algoritm evolutiv. In cea de a doua parte a referatului am prezentat algoritmul evolutiv de rezolvare a problemelor de optimizare multi-criterială SPEA.

Cuvinte cheie:

Soluţii în sens Pareio, valoare fitness , optimizare. SPEA, arhivă.

1. Introducere.

Multe din probleme reale de optimizare (inginerie sau economie) sunt multicriteriale, adică au unul sau mai multe criterii care trebuie optimizate. Rezolvarea acestor probleme este mai dificilă, deoarece conceptul de optim este greu de definit. Aşadar, optimizarea multi-criterială presupune optimizarea mai multor funcţii obiectiv, unele dintre ele fiind conflictuale. O astfel de problemă nu are soluţie unică ce optimizează toate criteriile, ci există o întreagă mulţime de soluţii de compromis numite soluţii în sens Pareto care se caracterizează prin faptul că nu există vectori în spaţiul de căutare care să fie mai buni decât ele în raport cu toate criteriile.

Pentru o înţelegere mai bună, considerăm următorul exemplu foarte simplu, o companie doreşte să producă produse de o calitate cât mai bună şi la un preţ cât mai mic. Deci compania are două criterii (problemă multi-criteriaiă): primul calitate cât mai bună, iar cel de al doilea preţ cât mai mic.

Figura 1 arată toate nivelele posibile de cost şi calitate care pot fi atinse de către produse. Cercurile de la A la L corespund fiecărui nivel. Soluţia D este evident mai bună decât soluţia H pentru ca este de o calitate mai bună şi de un cost mai mic. Deci soluţia D domină soluţia H. Soluţiile A şi D sunt non-dominante (sau non-inferiare) una faţă de cealaltă. Soluţia A este de un cost mai mic, dar calitatea soluţiei D este mai bună decât a soluţiei A. Deci nu putem spune care din soluţiile A sau D sunt mai bune. Soluţia unei probleme de optimizare multicriterială constă într-o mulţime de elemente care sunt nondominante unele faţă de celelalte.

O mulţime de soluţii non-dominante se defineşte ca o mulţime de soluţii care sunt non-dominate între ele şi oricare altă soluţie din afara mulţimii este dominată de cel puţin o soluţie din mulţime. Mulţimea globală de optim Pareto este mulţimea de soluţii non-dominate din tot spaţiu de soluţii posibile (tot spaţiul de căutare). Aşadar scopul optimizării multicriteriale este de a găsi mulţimea de optim Pareto pentru spaţiul de soluţii.

În figura 1 soluţiile A, B, C, D şi E formează mulţimea globală de optim Pareto peste tot spaţiul de soluţii.

Concluziile acestui exemplu: Exemplul prezentat mai sus poate fi generalizat la un număr mult mai mare de funcţii criteriu. Mulţimea de optim Pareto poate fi infinită, deci marea provocare este de a găsi soluţiile reprezentative ale adevăratei mulţimi de optim Pareto şi totodată de a menţine o bună împrâştiere a soluţiilor peste adevărata mulţime de optim Pareto.

Figura 1: Diferite nivele de calitate şi cost ale unui produs. Cercurile pline reprezintă frontul de optim Pareto. Soluţiile A, B, C, D şi E formează un spaţiu de soluţii nedominate

Determinarea unui vector al variabilelor de decizie care satisface constrângeri inegale, , constrângeri egale, şi optimizează funcţia vector: , ale cărui elemente reprezintă funcţii obiectiv se numeşte problemă de optimizare inulti-criterială.

Cele m constrângeri inegale şi cele p constrângeri egale determină zona soluţiilor posibile S. Constrângerile descriu dependenţa între variabilele de decizie şi constantele din problemă. Numărul ecuaţiilor trebuie să fie mai mic decât numărul variabilelor de decizie.

O soluţie se zice că domină altă soluţie , dacă şi numai dacă: ( soluţia , este mai bună decât soluţia dacă valorile funcţiilor obiectiv în punctul , sunt mai bune decât toate valorile funcţiilor obiectiv în punctul ). În acest caz se poate spune fie că soluţia , domină soluţia , sau ca soluţia este dominată de soluţia .

Diferitele abordări, folosite de obicei, pentru a rezolva problemele de optimizare multicriterială pot fi clasificate, în mare, în 2 categorii:

Optimizare multicriterială bazată pe preferinţă: Algoritmii din această clasă folosesc preferinţele utilizatorului pentru a combina toate funcţiile criteriu într-o singură funcţie. Funcţia criteriu astfel obţinută se optimizează folosind o tehnică de optimizare unicriterială. Totuşi este greu de cuantificat preferinţele utilizatorului în noua funcţie criteriu, deci algoritmii din această categorie pot fi aplicaţi unei clase restrânse de probleme.

Optimizare multicriterială ideală: Spre deosebire de algoritmii bazaţi pe preferinţele utilizatorului, această clasă de algoritmi încearcă să găsească toate soluţiile care aparţin mulţimii de optim Pareto. Aşadar utilizatorul nu trebuie sâ-şi cuantifice preferinţele pentru anumite critetrii. După ce soluţiile reprezentative ale mulţimii de optim Pareto sunt găsite utilizatorul poate alege dintre ele o soluţie.

2. Metode clasice de rezolvare a problemelor de programare multi-criterială

Metodele clasice de rezolvare a problemelor de programare multi-criterială se bazează pe transformarea problemei multi-obiectiv într-una cu un singur obiectiv. Câteva abordări de acest tip sunt: metoda mi-max, metoda deplasărilor faţă de valori ţintă, metoda agregării liniare a funcţiilor obiectiv, metoda sumei ponderilor şi metoda perturbării .

2.1. Metoda agregării liniare a funcţiilor obiectiv

Funcţiile obiectiv sunt combinate într-o singură funcţie obiectiv F:

(1)

unde reprezintă ponderea utilizată pentru funcţia obiectiv (adică indică importanţa obiectivului i). În general se alege . Toate soluţiile optime Pareto trebuie să se găsească în mulţimea soluţiilor posibile S.

Paşii metodei sunt:

• Se alege la întâmplare vectorul ponderilor w şi se optimizează funcţia obiectiv F pentru a se obţine o soluţie optimă. Soluţia optimă obţinută aparţine mulţimii soluţiilor optime Pareto.

• Pentru a obţine soluţii optime Pareto distincte, se aleg alte valori pentru vectorul ponderilor w şi se optimizează funcţia F obţinută în fiecare caz.

De asemnenea pentru o mai bună inţelegre considerăm următorul exemplu: Fie următoarea problemă ipotetică: o problemă de optimizare cu două funcţii obiectiv ce trebuie minimizate. ( figura 2).