Algoritmul SPEA2 - Aplicat unei Probleme Biobiectiv

Enunţul problemei

O grindă trebuie sudată de altă grindă astfel încât să poată suporta la capătul liber o anumită forţă de încărcare. Se cere determinarea valorilor a 4 parametri de proiectare:

- h - grosimea sudurii,

- b - grosimea grindei,

- l - lungimea sudurii,

- t - înălţimea grindei

care să satisfacă două obiective :

- cost minim, dat de funcţia: f1(x)=1.10471h2l + 0.04811tb(14.0+l)

- îndoire minimă a grindei la capătul liber, dată de funcţia: f2(x)=2.1952/(t3b)

şi să respecte restricţiile

0.125≤(h,b)≤5.0 0.1≤(l,t)≤10.0

b≥h

Un design optim din punctul de vedere al costului va presupune ca toţi parametrii să aibă valori cât mai mici, însă un astfel de design ar produce o îndoire accentuată a grindei. Invers, o soliditate mare a grindei şi a sudurii presupune valori mari ale parametrilor, valori care conduc la un cost mare.

Aşadar, problema este multiobiectiv (biobiectiv) cu funcţii obiectiv conflictuale. Acest fapt conduce la soluţii optime-Pareto.

Codificarea unui individ (soluţie posibilă) este următoarea: (h,b,l,t), toţi parametrii având valori reale în intervalele de definiţie.

Datele de intrare ale algoritmului sunt:

- nmax - numărul maxim de indivizi în populaţie (dimensiunea populaţiei)

- nmaxa – numărul maxim de indivizi în arhivă (dimensiunea arhivei)

- nr – numărul iniţial de indivizi în populaţie (dimensiunea populaţiei la generaţia 0)

- maxgen – numărul maxim de generaţii

- pm – probabilitatea de mutaţie genetică

- k – numărul de perechi selectate pentru încrucişare

Algoritmul SPEA 2 este:

Pas1. Initializarea populaţiei. Se generează o populaţie iniţială de nr<nmax indivizi şi se creează arhiva vidă. t=0 (generaţia 0).

Pas2. Evaluarea. Se calculează valoarea indivizilor din Pt (populaţia la generatia t) şi At (arhiva la generaţia t).

Pas3. Selecţia ambientală. Se copiază toţi indivizii nedominaţi din Pt şi din At în At+1. Dacă mărimea arhivei At+1 depăşeşte nmaxa, se reduce At+1 prin operatorul de trunchiere, iar dacă mărimea arhivei At+1 este mai mică decât nmaxa se umple At+1 cu indivizi dominaţi din Pt şi din At.

Pas4. Terminare. Dacă t ≥ maxgen sau nr(numărul actualizat al indivizilor din Pt) ≥ nmax atunci se alege drept soluţie cel mai bun individ din arhiva curentă. Stop.

Pas5. Selecţia pentru încrucişare. Se selectează k perechi de indivizi, cei mai buni, pentru a fi părinţi, din At, apoi, dacă mai este nevoie, din Pt.

Pas6. Variere. Se combină informaţia părinţilor pentru a genera k descendenţi. Se aplică operatorul de mutaţie genetică asupra a pm*nr indivizi din Pt. Pt+1 este Pt la care s-au adăugat descendenţii şi în care indivizii mutaţi s-au modificat. t=t+1. Se trece la Pas2.

Datele de ieşire ale algoritmului sunt reprezentate de valorile celor 4 parametri care constituie soluţia optimă la ultima generaţie.

Rularea algoritmului pentru următoarele valori ale datele de intrare:

nmax=30

nmaxa=5

maxgen=3

pm=20%

k=3

nr=10

La generaţia 0 iniţializarea populaţiei se face generând aleator cei nr=10 indivizi care să respecte restricţiile problemei. Aceştia sunt :

ind 0 – {0.347000 , 1.233000 , 9.100000 , 5.700000} - grosimea sudurii de 0.347000 inch, grosimea grindei de 1.233000 inch, lungimea sudurii de 9.100000 inch, înălţimea grindei de 5.700000 inch.

ind 1 – {2.243000 , 2.971000 , 1.600000 , 4.900000}

ind 2 – {1.877000 , 4.130000 , 5.900000 , 7.200000}

ind 3 – {3.380000 , 3.868000 , 6.100000 , 1.300000}

ind 4 – {2.347000 , 2.964000 , 4.800000 , 2.000000}

ind 5 – {2.192000 , 2.316000 , 8.600000 , 1.500000}

ind 6 – {3.135000 , 3.371000 , 9.400000 , 3.500000}

ind 7 – {3.561000 , 3.980000 , 9.600000 , 6.200000}

ind 8 – {1.468000 , 3.865000 , 8.900000 , 6.700000}

ind 9 – {3.790000 , 4.114000 , 6.700000 , 6.500000}

Pentru evaluarea populaţiei se atribuie fiecărui individ din P0 şi A0 o valoare reprezentând puterea sa (numărul de soluţii pe care le domină – relaţie de dominanţă Pareto).

putere[0]=4

putere[1]=4

putere[2]=4

putere[3]=0

putere[4]=2

putere[5]=0

putere[6]=0

putere[7]=0

putere[8]=4

putere[9]=1

Această relaţie de dominanţă se observă şi din figura următoare. Având în vedere că ambele funcţii se cer minimizate, cele mai bune puncte se află pe prima bandă curbă din colţul stânga jos al graficului, în zona de minim.