Descrierea problemei şi a metodelor de rezolvare utilizate

Algoritmii evolutivi permit obţinerea unei aproximări a mulţimii Pareto optimale prin folosirea unei populaţii, iniţializată cu elemente aleatoare din D, şi modificată succesiv, de-a lungul mai multor generaţii prin operaţii de recombinare şi mutaţie. La fiecare generaţie se construieşte o nouă populaţie pe baza unui criteriu de selecţie ce foloseşte relaţia de nedominare.

Date de intrare şi ieşire

Datele de intrare specifice aplicaţiei DEMO/G pot fi grupate în următoarele categorii:

• Date specifice problemei. Acestea sunt fi cu caracter general, ca: numărul variabilelor de decizie (n), numărul funcţiilor obiectiv (k), fie cu caracter particular problemei concrete de rezolvat:
• Datele ce urmează a fi prelucrate (în cazul în care DEMO/G este folosită pentru a rezolva probleme de analiza a datelor)
• Numele codurilor executabile ce permit evaluarea funcţiilor obiectiv (în cazul în care DEMO/G este folosită pentru a rezolva probleme de optimizare în care evaluarea funcţiilor obiectiv se bazeaza pe simularea unor fenomene pentru care pot fi folosite coduri deja existente)
• Date specifice algoritmului. Acestea se refera la tipul algoritmului, parametrii de control ai acestuia precum şi la caracteristicile specifice implementării distribuite bazate pe divizarea populaţiei în subpopulaţii:
• Numărul de subpopulaţii
• Tipul comunicării dintre subpopulaţii
• Frecvenţa de comunicare între subpopulaţii
• Probabilitate de selecţie a elementelor care migrează dintr-o subpopulaţie în alta
• Numărul de etape de comunicare

Datele de ieşire sunt aceleaşi indiferent de tipul de problemă pentru care este folosită aplicaţia şi anume:

• Aproximarea mulţimii Pareto optimale
• Aproximarea frontului Pareto

Implementarea în mediul Grid

Justificare

Dezavantajele implementărilor clasice ale algoritmilor evolutivi pentru optimizare multicriterială sunt legate atât de costul computaţional implicat cât şi de senzitivitatea comportării lor în raport cu valorile parametrilor de control. Limitarea acestor dezavantaje poate fi realizată prin exploatarea execuţiei în paralel a unor prelucrări. In contextul unei implementări în mediul Grid au fost identificate două scenarii:

• Execuţia pe mai multe locaţii din mediul Grid a unor instanţe ale aplicaţiei caracterizate prin strategii diferite (algoritmi evolutivi diferiţi sau doar valori diferite ale parametrilor de control) dar adresând aceeaşi problemă. Prin combinarea rezultatelor obţinute prin aplicarea mai multor metode se pot compensa deficienţele unei metode sau instanţe caracterizate printr-un anumit set de parametri.
• Execuţia pe mai multe locaţii din mediul Grid a aceleiaşi instanţe dar pentru subprobleme ale unei probleme de dimensiune mare (de exemplu in cazul unei probleme de analiză a datelor subproblema ar corespunde prelucrării unui subset de date).

Soluţia de implementare

S-a optat pentru o soluţie care să permită execuţia fiecăruia dintre cele două scenarii de mai sus. In plus soluţia aleasă permite:

• rezolvarea problemelor pentru care functiile obiectiv se evaluează utilizând un cod extern aplicaţiei DEMO/G. In acest scop a fost implementat un modul care asigură interfaţa dintre DEMO/G şi codul extern (cod Java sau cod executabil provenit din C sau Fortran).
• lansarea pe un cluster din mediul Grid a unor joburi paralele implementate folosind MPIJava.

Cerinţe privind infrastructura Grid

Cerinţele privind infrastructura Grid depind de varianta de execuţie aleasă:

• Execuţie pe grid a implementării secvenţiale: nu necesită cerinţe particulare
• Execuţie pe grid a implementării paralele: necesită existenţa pachetului mpich

Interfaţa de utilizare

Lansarea în execuţie a unuia sau mai multor joburi pe Grid poate fi realizată de către utilizator prin intermediul unui portal (GOC – Grid Operating Center) dezvoltat în cadrul proiectului. GOC a fost dezvoltat folosind limbajul JSP care este suportat de platforma Apache-Tomcat. Este format din mai multe componente/module de bază:

• modulul de autentificare (care realizează verificarea drepturilor unui utilizator de acces la resursele oferite de portal)
• modulul profil (oferă utilizatorului dreptul de a modifica anumite informaţii personale)
• modulul Grid (facilitează trimiterea spre execuţie a instanţelor create de utilizator folosind interfaţa utilizator a aplicaţiei implementate)
• modulul DemoGIF (interfaţa utilizator pentru aplicaţia de optimizare Demo/G)

Avantaje

Tinând cont de faptul ca strategiile corespunzatoare execuţiei pe Grid se caracterizează prin absenţa comunicării directe între joburile executate în locaţii diferite (varianta paralelă se executa pe un cluster aflat într-o locaţie a gridului) este de aşteptat să se obţină un câştig în timpul de execuţie. Trebuie ţinut însă cont şi de faptul că procesul în sine de lansare a joburilor pe grid induce un cost determinat de efectuarea submiterii şi planificarii joburilor precum şi de preluarea rezultatelor. In Tabelul 10.1 sunt ilustrate valori ale costurilor corespunzătoare lansarii a unuia respectiv 3, 5 şi 10 joburi. Se remarcă faptul că pentru un număr de joburi mai mare decât 3 costurile adiţionale induse de lansarea execuţiei pe grid sunt compensate de câştigul obţinut prin execuţia în paralel a instanţelor aplicaţiei. Pe de altă parte se remarcă faptul că dintre costurile aferente lansării cel predominant este cel al procesului de planificare a jobului/joburilor.