SECTIUNEA 1

RAPORTUL STIINTIFIC SI TEHNIC (RST)

ETAPA DE EXECUTIE NR. III CU TITLUL Elaborarea de noi modele de invatare si auto-organizare in sisteme complexe. Aspecte practice

  RST - Raport stiintific si tehnic in extenso*

  Proces verbal de avizare interna

  Procese verbale de receptie a lucrarilor de la

parteneri

  Raport final de activitate (numai pentru etapa

finala)

* pentru Programul 4 “Parteneriate in domeniile prioritare” se va utiliza modelul din Anexa 1

Cod: PO-04-Ed3-R1-F5

Anexa 1 - RST

RST - Raport stiintific si tehnic in extenso

Cuprins

_Toc240736721 1. Obiective generale .......................................................................................................... 3 2. Obiectivele etapei de executie .......................................................................................... 3 3. Rezumatul etapei (maxim 2 pagini) ................................................................................... 3 4. Descrierea stiintifica si tehnica ......................................................................................... 6

4.1 Detectarea interactiunilor in probleme complexe. Modele competente de invatare si optimizare evolutiva ........................................................................................................ 6 4.2 Studiul interactiilor in sisteme complexe ....................................................................... 6

4.2.1 Strategii de colaborare in algoritmi evolutivi ............................................................ 7 4.2.2 Studiul dinamicii complexe intr-un sistem evolutiv .................................................... 7 4.2.3 Detectarea evolutiva de reguli in automate celulare .................................................. 7 4.2.4 Studii de caz ........................................................................................................ 8

4.3 Invatare si auto-organizare in sisteme complexe stigmergice .......................................... 8 4.3.1 Noi modele de agenti stigmergici ............................................................................ 8 4.3.2 Explorare si exploatare prin agenti sensibili cu invatare ............................................. 9 4.3.3 Agenti stigmergici cu revenire ................................................................................ 9

4.4 Noi tipuri de echilibre in jocuri necooperative. Detectarea evolutiva a echilibrelor. Aplicatii practice semnificative .......................................................................................... 9

4.4.1 Detectarea evolutiva a echilibrelor .......................................................................... 9 4.4.2 Metarationalitate si echilibre generalizate .............................................................. 10 4.4.3 Detectarea echilibrelor unei piete a energiei electrice .............................................. 10

4.5 Identificarea impactului topologiei spatiului solutiilor asupra complexitatii temporale a algoritmilor de cautare ................................................................................. 10 4.6 Analiza datelor complexe si invatare supervizata. Noi modele de masini cu suport vectorial ....................................................................................................................... 10 4.7 Selectia atributelor in invatarea nesupervizata: optimizare multi-modala ........................ 11 4.8 Coevolutie de tip cooperativ. Aplicatii in rezolvarea problemelor de optimizare de dimensiuni mari. ........................................................................................................... 12

4.8.1 Analiza aplicabilitatii coevolutiei de tip cooperativ in cresterea scalabilitatii metaeuristicilor ........................................................................................................... 12 4.8.2 Aspecte practice in implementarea algoritmilor coevolutivi ....................................... 12 4.8.3 Rezultate obtinute in optimizarea functiilor cu numar mare de variabile ..................... 14

4.9 Comportament haotic in retele neuronale. Analiza arhitecturilor de tip inel. .................... 14 4.9.1 Arhitectura de tip inel .......................................................................................... 14 4.9.2 Arhitectura bidirectionala ..................................................................................... 15

4.10 Analiza robustetii metaeuristicilor. Studiu de caz in planificarea taskurilor in sistemele distribuite. ..................................................................................................... 15 4.11 Mediu pentru proiectarea si testarea metaeuristicilor inspirate de natura ..................... 15

4.11.1 Structura functionala si arhitectura platformei propuse .......................................... 16 4.11.2 Configuratia si modulele aplicatiei ....................................................................... 16

4.12 Invatare colectiva cu autoorganizare. Minority Game .................................................. 17 4.13 Un model strategic de generare a retelelor sociale ..................................................... 18 4.14 Determinarea comunitatilor in retele sociale folosind algoritmi de tip swarm ................. 19

5. Anexe ......................................................................................................................... 19 6. Concluzii ...................................................................................................................... 22 7. Bibliografie .................................................................................................................. 23

1. Obiective generale

Obiectivele proiectului pot fi sumarizate astfel:

Ob1. Investigarea paradigmelor actuale in studiul complexitatii Ob2. Analiza aspectelor dinamice in studiul complexitatii Ob3. Studiul invatarii si auto-organizarii in sisteme complexe si in sisteme complexe dinamice Ob4. Dezvoltarea unui cadru general, flexibil si usor de utilizat pentru selectia si aplicarea inteligenta a metaeuristicilor inspirate de natura problemelor reale Ob5. Proiectarea de noi modele evolutive pentru rezolvarea problemelor complexe Ob6. Dezvoltarea studiilor de caz Ob7. Dezvoltarea de aplicatii pentru scenarii complexe din lumea reala Ob8. Diseminarea rezultatelor

2. Obiectivele etapei de executie

Obiectivul etapei se refera la Elaborarea de noi modele de invatare si auto-organizare in sisteme complexe. Aspecte practice. Subobiectivele urmarite sunt:

· Studiul interactiunilor in sistemele complexe · Elaborarea de modele ale proceselor de invatare si ale auto–organizarii in

sistemele complexe · Elaborarea de noi modele de invatare evolutiva in sisteme complexe dinamice

Aceste obiective sunt strans corelate cu obiectivele generale Ob3, Ob4, Ob5, Ob6 si

Ob8. Obiectivele au fost urmarite in cadrul proiectului prin urmatoarele activitati:

· studiul interactiilor in sisteme complexe · investigarea proceselor de invatare in sisteme complexe · studiul auto-organizarii in sisteme complexe · dezvoltarea unor modele evolutive de invatare pentru sistemele complexe · studiul auto-organizarii in medii dinamice · investigarea sistemelor disipative si a celor departe de echilibru · proiectarea de noi modele de automate celulare pentru sisteme dinamice

complexe · testare si evaluare · studii de caz

3. Rezumatul etapei (maxim 2 pagini) In cadrul acestei etape echipa proiectului a propus si studiat noi modele de invatare si

auto-organizare in sisteme complexe - conform obiectivelor etapei curente. Pe baza cercetarilor efectuate in cadrul proiectului au fost publicate 16 articole indexate ISI, 2 articole in jurnale indexate BDI. Alte 6 articole sunt in curs de aparitie in reviste indexate

ISI. Rezultatele au fost diseminate in cadrul unor evenimente stiintifice internationale (congrese, workshop-uri, scoli de vara).

Rezultatele obtinute in cadrul acestei etape pot fi sumarizate astfel:

· Au fost studiate noi modele competente de invatare si optimizare evolutiva (sectiunea 4.1). S-a propus o metodologie generala de constructie a modelelor necesare estimarii distributiilor, bazata pe analiza si extinderea corelatiilor dintre variabile. Rezultatele au fost publicate in volumul conferintei GECCO 2009 (ACM proceedings).

· Au fost studiate interactiunile in sisteme complexe si au fost propuse noi strategii de colaborare in algoritmi evolutivi (sectiunea 4.2). Rezultate promitatoare obtinute in optimizarea unor functii reale complexe au fost publicate in volumul post-proceedings IEEE al SYNASC 2008 si extinse in volumul IEEE al conferintei CEC 2009. Studiul dinamicii complexe intr-un sistem evolutiv ce a permis imbunatatirea strategiilor propuse este prezentat intr-un articol al revistei Creative Mathematics and Informatics. Rezultatele unui nou model evolutiv geometric obtinute pentru detectarea evolutiva de reguli in automate celulare au fost prezentate la conferinta HAIS 2009 si apar intr-un volum LNCS, Springer. Modelele propuse au fost investigate si prin studii de caz pe probleme implicand sisteme de mare complexitate, inspirate din domeniile fizicii si predictiei seriilor de timp (sectiunea 4.2.4).

· Au fost propuse modele de invatare si auto-organizare in sisteme complexe stigmergice (sectiunea 4.3). A fost studiat un model de agenti stigmergici ce pot comunica prin schimb direct de informatii si cunostinte despre mediul inconjurator fiind inzestrati cu comportament stigmergic. Potentialul modelului este confirmat de rezultatele bune obtinute in rezolvarea unor probleme complexe de optimizare combinatoriala. Aceste rezultate au fost publicate in revista Int. J. of Computers, Communications & Control. Noi metode de diversificare a cautarii prin agenti stigemergici au fost prezentate intr-un articol din seria Studies in Computational Intelligence, Springer 2009. Rezultatele modelului de agenti stigmergici cu revenire obtinute in rezolvarea unei probleme NP-dificile din economie au fost acceptate pentru prezentare la workshop-ul NCA din cadrul SYNASC’09 – http://synasc09.info.uvt.ro.

· Au fost propuse si analizate noi tipuri de echilibre in jocuri necooperative (sectiunea 4.4). Rezultatele privind detectarea evolutiva a echilibrelor au fost publicate intr-un capitol din cartea Applications of Evolutionary Computing din seria Lecture Notes in Computer Science, Springer. Aceste modele au fost generalizate intr-o lucrare in cadrul conferintei internationale SYNASC’09 – http://synasc09.info.uvt.ro.

· A fost propusa notiunea de metarationalitate care permite o generalizare semnificativa a notiunii de joc. Rezultatele au fost publicate in volumul conferintei GECCO 2009 (ACM proceedings).

· Au fost investigate aplicatii practice semnificative ale modelelor de jocuri propuse: detectarea echilibrelor unei piete a energiei electrice. Rezultatele au fost publicate in revista Studia Universitatis Babes-Bolyai, Informatica Series.

· A fost studiat impactul topologiei spatiului solutiilor asupra complexitatii temporale a algoritmilor de cautare (sectiunea 4.5). Rezultatele au fost publicate in revista IEEE Transactions on Evolutionary Computation.

· Au fost analizate mecanisme de invatare supervizata din date complexe (sectiunea 4.6). S-au propus noi modele de masini cu suport vectorial prezentate in lucrari aparute in seria Studies in Computational Intelligence, Springer, 2009 si in revista Journal of the Operational Research Society.

· A fost abordata reducerea dimensiunii problemelor prin selectia/extragerea atributelor semnificative. S-a dezvoltat un algoritm evolutiv ce trateaza invatarea

nesupervizata ca si problema de optimizare multi-modala (sectiunea 4.7). Rezultatele au fost prezentate la conferinta GECCO 2009 (ACM proceedings).

· A fost studiat comportamentul mai multor variante de coevolutie de tip cooperativ in principal din perspectiva influentei asupra scalabilitatii diferitilor algoritmi evolutivi (sectiunea 4.8). Au fost identificate si comparate diferite variante de implementare si au fost efectuate teste numerice pentru probleme de optimizare de dimensiuni mari. Rezultatele au fost prezentate la doua manifestari stiintifice si una dintre lucrari a fost acceptata pentru publicare in volumul conferintei LSSC’09 - http://parallel.bas.bg/Conferences/SciCom09.html (post-proceedings LNCS, Springer).

· S-a extins analiza, inceputa in etapa anterioara, privind comportamentul haotic al retelelor neuronale cu dinamica discreta constituite din neuroni cu intarziere plasati in nodurile unei arhitecturi de tip inel de la cazul unidirectional la cel bidirectional (sectiunea 4.9). Rezultatele au fost cuprinse intr-o lucrare acceptata pentru publicare in revista Neural Networks si au fost prezentate si publicate in proceedings-ul conferintei ICNN’09 - http://www.ijcnn2009.com/.

· S-au efectuat implementarile necesare si s-au obtinut primele rezultate experimentale privind aplicabilitatea algoritmilor de tip ACO in rezolvarea problemelor de planificare a task-urilor in sisteme distribuite de tipul grid-ului sau a serviciilor software (sectiunea 4.10). Rezultatele obtinute au fost acceptate pentru prezentare la workshop-ul NCA, SYNASC’09 – http://synasc09.info.uvt.ro.

· S-au finalizat cercetarile privind impactul operatorilor de incrucisare si a parametrilor acestora asupra comportarii algoritmilor de tip DE - „differential evolution”. Rezultatele au fost publicate intr-o lucrare aparuta in 2009 in Applied Soft Computing. In aceasta directie s-a initiat o serie de studii privind comportarea variantelor discrete ale algoritmilor de tip DE in rezolvarea unor probleme ce intervin in modelarea sistemelor complexe.

· S-a stabilit arhitectura unui mediu de proiectare si testare a metaeuristicilor inspirate de natura (prevazut in obiectivul Ob4) caracterizat prin facilitati de configurare de catre utilizator a metodei si de definire a unei strategii de analiza statistica a rezultatelor (sectiunea 4.11). Implementarea propriu-zisa a mediului face obiectul etapei urmatoare.

· S-a studiat un model de invatare colectiva cu autoorganizare (sectiunea 4.12). Modelul generalizeaza celebrul Minority Game din econofizica, un model stilizat de functionare a pietelor financiare. Rezultatele sunt in curs de aparitie in revista Computational and Mathematical Organization Theory.

· S-a propus un model strategic de generare a retelelor sociale (sectiunea 4.13). Modelul este o varianta a modelului clasic Jackson-Watts: difera de acesta prin ordinea de activare a muchiilor. Rezultatele sunt in curs de aparitie in revista Journal of Economic Behavior and Organization.

· S-a dezvoltat un model de tip swarm pentru determinarea comunitatilor in retelele sociale (sectiunea 4.14). Rezultatele au fost prezentate la conferinta IEEE CEC 2009.

Consortiul s-a consolidat prin organizarea cu participarea efectiva a tuturor partenerilor la manifestari stiintifice: Doctoral Intensive Summer School on Meta-Heuristics in Optimisation and in Intelligent Data Analysis, Iasi, 2009 [http://thor.info.uaic.ro/ ~summerschool/] si workshopul Natural Computing and Applications, Timisoara 2009 [http://synasc09.info.uvt.ro/nca], organizat de membrii proiectului. A fost organizata sectiunea Intelligent Knowledge Discovery in cadrul International Conference on Knowledge Engineering, Principles and Techniques (KEPT) Cluj-Napoca, 2009.

4. Descrierea stiintifica si tehnica In continuare sunt descrise in detaliu principalele rezultate obtinute in cadrul etapei, rezultate ce urmaresc obiectivele si activitatile mentionate mai sus. Rezultatele obtinute sunt corelate cu cele mai importante directii de cercetare si tehnici din domeniul sistemelor complexe.

4.1 Detectarea interactiunilor in probleme complexe. Modele competente de invatare si optimizare evolutiva Multe din noile metode competente propuse in literatura pun un accent pe invatarea corelatiilor dintre variabilele problemei. Deseori problemele reale sunt caracterizate de existenta unor structuri regulate intrinseci sau chiar a unor blocuri de constructie (building blocks) de diferite marimi. Daca exista blocuri de constructie, evolutia se poate face printr-un progres incremental, gradual (Holland, 2000).

Rezultate din literatura (Goldberg et al., 1989; Thierens, Goldberg, 1993) au aratat ca si pentru probleme separabile timpul de convergenta poate fi exponential daca nu se cunosc grupurile de variabile dependente. Pentru a aplana aceasta dificultate, o varietate de technici de invatare a legaturilor au fost propuse in literatura. Metodele propuse sunt capabile de aproximarea distributiei variabilelor problemei (Muhlenbein, PaaB, 1996).

Metode acceptate larg in circuitul international includ Linkage Learning Genetic Algorithm propus de Harik and Goldberg (1997), preluat si dezvoltat in (Lobo et al., 1998; Chen, Goldberg, 2005; Sastry, Goldberg, 2003). Alta linie de cercetare inlocuieste populatia cu o estimare a probabilitatilor fiecarei gene (Harik et al., 1999; Sastry and Goldberg, 2000; Rastegar and Hariri, 2006). In abordarea lui Pelikan et al. (1999); Pelikan (2002); Pelikan (2005) relatiile dintre variabile sunt invatate cu ajutorul unor retele neuronale Bayesiene. Algoritmul DevRep (de Jong, 2003) este o alta metoda capabila de a-si evolua reprezentatia in functie de corelatiile dintre variabile. Intr-o abordare recenta Yu si Goldberg (2006) propun detectarea relatiilor prin modelarea cu ajutorul matricelor de dependenta (Browning, 1998).

Aceste metode ce estimeaza distributiile solutiilor si construiesc modele ajutatoare reprezinta o clasa de metode cunoscuta ca Estimation of Distribution Algorithms (EDAs). Metodele EDAs pot rezolva problem grele, cu module interdependente prin identificarea si exploatarea dependentelor. Din nefericire ele necesita populatii/evaluari de solutii foarte costisitoare pentru a putea garanta functionarea adecvata si corectitudinea solutiilor. Astfel operatia cautarii si construirii unui model din solutiile stocate in memorie in metodele folosite implica costuri ce pot usor depasi limitele puterii de calcul aflate la dispozitie.

In cadrul proiectului, s-a propus o metodologie generala de constructie a modelelor necesare estimarii distributiilor, bazata pe analiza si extinderea corelatiilor dintre variabile [Iclanzan et al, 2009]. Motivatia de baza a fost reducerea costurilor in metodele EDA clasice. Acestea aplica strategii de cautare a modelelor neghidate, ce extind sau rafineaza modele prin perturbatii stochastice, sau print-o enumerare deterministica, exhaustiva.

Pentru modelele dezvoltate in cadrul proiectului s-a demonstrat ca metricile introduse pot ghida procesul de cautare/constructie, livrand modele corecte in timp liniar. Metodele originale de constructie a modelelor au o complexitate mult mai ridicata, de exemplu O(n^3) in cazul Extended Compact Genetic Agorithm (Sastry, Goldberg, 2000).

Aplicand noua tehnica, timpul de rulare poate fi redus cu ordine de magnitudine (minute vs. zile de rulare), permitand construirea unor metode intr-adevar scalabile, ce pot rezolva probleme de dimensiuni foarte mari.

4.2 Studiul interactiilor in sisteme complexe

In cadrul actualei etape a proiectului au fost studiate diferite strategii de colaborare in algoritmi evolutivi, dinamica complexa ce rezulta in urma acestora si aplicatiile lor in analiza comportamentului complex generat de automate celulare.

4.2.1 Strategii de colaborare in algoritmi evolutivi

Intr-un algoritm evolutiv, selectia partenerilor pentru recombinare poate sa influenetze in mod semnificativ procesul de cautare. In [Gog et al, 2008] sunt analizate diferite strategii de selectie bazata pe calitatea indivizilor si a unei strategii de colaborare intre indivizii din populatie, folosind diferite reguli de recombinare.

S-a propus un model evolutiv colaborativ distribuit [Chira et al, 2008]. Modelul este caracterizat de distributia indivizilor populatiei folosind o topologie bazata pe calitatea acestora. Fiecare individ apartine unei societati de agenti caracterizata de o anumita strategie de recombinare. Apartenenta la una dintre societati a indivizilor rezultati in urma recombinarii este decisa intr-o maniera probabilistica tinandu-se cont de o probabilitate de dominanta intre societati. Influenta acestei probabilitati de dominanta asupra dinamicii societatilor este studiata atat din perspectiva empirica cat si teoretica. Experimentele numerice evidentiaza un comportament caracterizat de o dinamica interesanta in care apare un interval de tranzitie pentru probabilitatea de dominare. S-a verificat experimental ipoteza ca in acest interval se obtin cele mai bune rezultate pentru clase importante de functii de test.

4.2.2 Studiul dinamicii complexe intr-un sistem evolutiv Un model geometric colaborativ evolutiv (ce extinde modelul din [Gog et al, 2009a]) este prezentat si studiat in [Gog et al, 2009b]. Modelul este caracterizat de o cautare asincrona realizata prin propagarea graduala a materialului genetic al celor mai buni indivizi din populatie in restul populatiei. Fiecare individ actioneaza ca un agent autonom care poate sa comunice cu ceilalti indivizi si sa isi selecteze un partener pentru recombinare.

Modelul foloseste trei strategii de recombinare, fiecare corespunzand unei subpopulatii sau societati de agenti. Este investigata dinamica sistemului, punandu-se in evidenta existenta unui comportament emergent semnificativ si a unui interval de tranzitie. Rezultatele numerice indica o buna performanta a modelului propus.

4.2.3 Detectarea evolutiva de reguli in automate celulare

In lucrarea [Gog et al, 2009a] este propus un nou model circular evolutiv de optimizare. Acest model este aplicat pentru obtinerea regulilor in automate celulare. Automatele Celulare reprezinta instrumente puternice pentru studiul calitativ al dinamicii sistemelor (economice, sociale, etc) complexe. A fost abordata problema detectarii regulilor de evolutie in automate celulare finite. Interesul stiintific in astfel de probleme este justificat de potentialul de a genera o mare varietate de comportamente complexe. Regulile cautate trebuie sa fie capabile sa genereze un comportament global pe baza unor interactiuni locale.

Problema densitatii considerata este o aplicatie importanta care a fost intensiv studiata datorita simplitatii sale si potentialului de a genera comportamente complexe. In modelul propus se urmareste exploatarea materialului genetic relevant in acelasi timp cu cresterea diversitatii populatiei, prin integrarea unei topologii a populatiei bazata pe calitatea potentialelor solutii si o schema de cautare asincrona. Experimentele numerice arata potentialul modelului propus, prin comparatii cu alte modele evolutive. In acelasi context s-au efectuat studii preliminare privind comportarea pentru aceeasi problema a mai multor variante recente ale algoritmului DE („differential evolution”) adaptat pentru reprezentari binare. Rezultatele obtinute au condus la concluzia ca, daca in cazul problemelor de optimizare in domenii continue operatorii de recombinare bazati pe

diferente sunt foarte efectivi in cazul domeniilor discrete lucrurile stau diferit, ceea ce impune identificarea unor noi variante de DE adecvate reprezentarii binare.

4.2.4 Studii de caz Au fost realizate o serie de studii de caz privitoare la probleme implicand sisteme de mare complexitate, inspirate din domeniile fizicii si predictiei seriilor de timp. Principalele rezultate in acest sens sunt urmatoarele:

a) S-a continuat explorarea posibilitatilor de abordare a problemei identificarii starilor de baza ale spinului in modelul Ising. A fost propus [Bautu, Luchian, 2009] un algoritm bazat pe metoda Particle Swarm Optimization (PSO). Rezultatele experimentale s-au dovedit superioare celor obtinute alterior prin utilizarea algoritmilor genetici.

O alta problema din fizica abordata o reprezinta problema lui Thomson - gasirea unei distributii a N particule incarcate electric pe suprafata unei sfere, care minimizeaza energia electrostatica a sistemului. In lucrarea [Bautu, Bautu, 2009] este propusa utilizarea tehnicii PSO pentru rezolvarea problemei. Lucrarea [Bautu, 2009] investigheaza influenta topologiei utilizate asupra performantei obtinute, in cazul abordarii PSO. Pe baza unei testari extensive se ajunge la concluzia ca o topologie complet conectata duce la rezultatele cele mai bune. De asemenea, alegerea adecvata a marimii roiului de particule joaca un rol important in performanta obtinuta.

b) In lucrarea [Barbulescu, Bautu, 2009] este propusa modelarea evolutiei climatului in regiunea Dobrogea prin intermediul metodei Gene Expression Programming (GEP). Problema este din clasa predictiei seriilor de timp. Pentru orice metoda nou propusa se impune comparatia cu metodele clasice, bazate pe statistica. Rezultatele experimentale arata ca GEP prezinta o serie de avantaje fata de metodele clasice.

c) Predictia seriilor de timp financiare este abordata in lucrarile [Bautu, Barbulescu 2009] si [Bautu, Bautu, Luchian, 2009]. In prima lucrare este dezvoltata o tehnica hibrida, care combina o metoda clasica, Autoregressive Integrated Moving Average (ARIMA), si una evolutiva, GEP. Modelul hibrid are performante superioare fiecareia din cele doua metode luate individual. A doua lucrare duce mai departe aceeasi idee, comparand metoda GEP cu diverse tehnici hibride care includ aceasta metoda. Concluzia generala este ca metodele hibride au un potential mai ridicat decat metodele "pure".

4.3 Invatare si auto-organizare in sisteme complexe stigmergice Sistemele compuse din mai multi agenti autonomi sunt investigate pentru potentialul lor de a aborda in mod eficient probleme complexe din lumea reala.

4.3.1 Noi modele de agenti stigmergici

In [Pintea et al, 2009a] este prezentat un model in care agentii comunica prin schimb direct de informatii si cunostinte despre mediul inconjurator. Ei au capacitatea de a invata si a reactiona in timp ce actioneaza in mediul lor. Se propune inzestrarea agentilor cu un comportament stigmergic in scopul de a face fata problemelor complexe de optimizare combinatoriala.

In modelul propus agentii sunt capabili sa comunice in mod indirect prin feromoni. In plus, se propune inzestrarea agentilor stigmergici cu diferite niveluri de sensibilitate. Astfel in cadrul unui sistem este facilitata stabilirea unui echilibru intre comunicarea directa si stigmergie. Pentru diversificarea cautarii si intensificarea ei, agentii pot invata sa-si modifice nivelul lor de sensibilitate in functie de caracteristicile de mediu si de experienta anterioara. Modelul combina comportamentul stigmergic sensibil la mediu cu comunicarea directa si cu abilitatile de invatare. Rezulta o metaeuristica robusta orientata agent, adaptata pentru optimizarea combinatoriala. Modelul propus a fost testat pentru rezolvarea unor probleme NP-dificile. Experimentele numerice indica robustetea si potentialul acestei metaeuristici.

4.3.2 Explorare si exploatare prin agenti sensibili cu invatare

Un mecanism de invatare pentru agenti stigmergici sensibili este prezentat in [Chira et al, 2008]. Agentii comunica prin schimb direct de informatii si cunostinte despre mediul inconjurator. In acelasi timp agentii sunt inzestrati cu comportament stigmergic si sunt capabili sa comunice in mod indirect prin producerea si influenta traseelor de feromoni.

Fiecare agent stigmergic are un anumit nivel de sensibilitate la feromoni care permite diferite tipuri de reactii la un mediu in schimbare. Un agent cu un nivel inalt de sensibilitate sustine intensificarea cautarii. Agentii cu nivel scazut de sensibilitate sunt influentati de urmele de feromon aducand diversitate in procesul de cautare. Acest nivel de sensibilitate este adaptat dinamic de fiecare agent printr-un mecanism de invatare ce incurajeaza orientarea sensibilitatii in sensul imbunatatirii solutiilor obtinute. Spre exemplu, un agent cu un nivel ridicat de sensibilitate care a obtinut o solutie calitativ mai buna decat cea precedenta va fi incurajat sa isi intensifice cautarea prin cresterea nivelului de sensibilitate. Mecanismul de invatare propus este testat cu succes pentru rezolvarea problemelor asimetrice Traveling Salesman Problem.

4.3.3 Agenti stigmergici cu revenire

Pornind de la modelul prezentat in [Chira et al, 2008], este propus Step-Back Sensitive Ant Model [Pintea et al, 2009b] inspirat de comportamentul real al furnicilor Niger Lasius. Aceste furnici folosesc intoarcerile cu 180 de grade (U-turns) in procesul de cautare. Un agent executa o intoarcere/revenire (step-back) in cazul in care ajunge intr-o stare virtuala modulata de diferitele niveluri de sensibilitate (la feromon) ale agentilor. O explorare eficienta a spatiului de cautare este efectuata in special de catre agentii cu sensibilitate scazuta la feromon in timp ce exploatarea unor solutii intermediare este facilitata de agenti extrem de sensibili. Acest nou model original a fost testat cu success in rezolvarea unei probleme complexe din economie numita Linear Ordering Problem.

4.4 Noi tipuri de echilibre in jocuri necooperative. Detectarea evolutiva a echilibrelor. Aplicatii practice semnificative Teoria jocurilor reprezinta un corpus de concepte de mare importanta in analiza interactiunilor in sisteme complexe de natura economica si sociala. Detectarea echilibrelor in jocurile necooperative este una dintre cele mai dificile probleme computationale. S-a propus o metoda generala de caracterizare si detectare a echilibrelor. Pornind de la aceasta caracterizare s-au definit si caracterizat noi concepte de echilibru.

4.4.1 Detectarea evolutiva a echilibrelor In [Dumitrescu et al, 2009b] este prezentata o metoda pentru detectarea echilibrelor (solutiilor) in jocuri ne-coopertative cu ajutorul metodelor evolutive. Intre strategii sunt definite relatii generative, specifice fiecarui tip de echilibru. Multimea strategiilor nedominate, relativ la o relatie generativa, va forma echilibrul (solutia) pentru acel joc. Sunt prezentate relatiile generative pentru diverse concepte de solutie precum echilibrul Nash, echilibrul Pareto, strategia dominanta, echilibrele epsilon-Nash si epsilon- Pareto. O metoda evolutiva pentru detectarea unor aproximatii cat mai precise ale echilibrelor este propusa si investigata. Metoda porneste cu o populatie initiala de profile de strategie aleasa aleator. Aplicandu-se succesiv operatori specifici de mutatie, recombinare precum si utilizand o metoda de sortare bazata pe non-dominare in vederea stabilirii fitness-ului indivizilor, populatia „evolueaza” conducand catre indivizi cat mai apropiati de echilibrele cautate.

Diverse experimente numerice sunt descrise. Aceste experimente valideaza metoda. Jocurile pe care sunt aplicate sunt modelul lui Bertrand si jocul lui Cournot cu doi sau trei jucatori.

4.4.2 Metarationalitate si echilibre generalizate

S-a introdus notiunea de metarationalitate care permite o generalizare semnificativa a notiunii de joc [Dumitrescu et al, 2009a]. S-a propus o metoda evolutiva pentru a detecta echilibrele pentru aceste jocuri generalizate. Metoda este bazata pe tehnicile evolutive de optimizare multicriteriala. Relatia generativa este la randul ei generalizata pentru a tine cont de rationalitatea jucatorilor. Rationalitatea este codificata intr-o metastrategie – un profil de strategie care are completat tipul de strategie specific fiecarui jucator. Echilibrul va fi multimea nedominata de metastrategii. Se porneste cu o populatie de metastrategii aleasa aleator (mai putin tipul de rationalitate care ramane fixat). Asupra indivizilor se aplica operatori de mutatie si recombinare. Populatia este ordonata in raport cu nedominarea din perspectiva relatiei generative. Fitnessul este dat de distanta intre indivizi si rangul in raport cu nedominarea descrisa anterior. Se obtin astfel aproximatii ale noilor echilibre din ce in ce mai bune [Dumitrescu et al, 2009d].

Metoda este validata prin diverse experimente numerice. Se studiaza cazul cand toti jucatorii sunt de tip Nash sau toti de tip Pareto. Se obtin aceleasi rezultate ca si in cazul jocurilor obisnuite. O analiza calitativa si cantitativa este facuta pentru cazul Nash-Pareto si Pareto–Nash. Se compara castigurile medii intre cele trei tipuri de jocuri (cu rationalitate Nash, cu rationalitate Pareto si cu rationalitate Nash-Pareto).

4.4.3 Detectarea echilibrelor unei piete a energiei electrice In lucrarea [Dumitrescu et al, 2009c] o metoda generala de determinare a echilibrelor in jocuri necooperative este folosita pentru a calcula echilibrul Nash pentru un joc ce modeleaza o piata a energiei electrice.

Metoda este bazata pe folosirea unei relatii generative pentru a caracteriza echilibrul Nash. Aceasta relatie induce un concept de dominare specific. Folosind acest concept de dominare si un algoritm evolutiv de optimizare multicriteriala se determina o foarte buna aproximatie a echilibrului jocului propus, acest echilibru fiind multimea de profile de strategie ne-dominate cu respect la relatia generativa.

O populatie de strategii este evoluata. Populatia de strategii poate fi considerata ca fiind aproximatia echilibrului. Selectia indivizilor supravietuitori se bazeaza pe un operator bazat pe dominarea indusa de relatia generativa. In acest fel noile populatii sunt tot mai apropiate de solutia cautata.

Experimentele numerice sunt facute pe un joc ce simuleaza o piata spot de electricitate, cu trei jucatori. Echilibrul Nash este detectat rapid folosind resurse relativ reduse. Un studiu calitativ al rezultatelor arata acuratetea si eficienta metodei.

4.5 Identificarea impactului topologiei spatiului solutiilor asupra complexitatii temporale a algoritmilor de cautare Orice tehnica eficienta de optimizare multimodala trebuie sa raspunda la doua intrebari esentiale: (i) cum sa distinga intre bazine de atractie diferite, si (ii) cum sa salveze solutiile utile detectate.

S-a propus o noua tehnica ce integreaza conservarea celor mai bune solutii locale succesive cu o separare topologica a subpopulatiilor-separare ce inlocuieste interactiuni bazate pe un concept topologic de vecinatate [Stoean et al, 2009a]. Tehnica propusa a fost testata pe o serie de functii de test de mare complexitate. A fost investigata problema independentei parametrilor metodei.

4.6 Analiza datelor complexe si invatare supervizata. Noi modele de masini cu suport vectorial S-a dezvoltat o noua tehnica evolutiva ce reprezinta o alternativa la modelul standard al masinilor cu suport vectorial (SVM standard support vector machines). Modelul propus

[Stoean et al, 2009b] ofera un substitut transparent al modului standard SVM – in esenta de tip black-box – si pastreaza in mod explicit coeficientii functiei de decizie. In plus metoda evolutiva propusa nu mai impune pentru cazul invatarii neseparabile liniar ca nucleele functiei de decizie sa satisfaca restrictia de a fi pozitiv definite. Au fost efectuate teste extinse. Rezultatele au evidentiat validitatea noii abordari in termeni de timp de rulare, acuratete a predictiei si flexibilitate. Metoda a fost aplicata pentru rezolvarea unor probleme practice de medicina (diagnostic automat) si tehnologia informatiei (detectarea spam-ului).

Masinile cu suport vectorial (SVM) reprezinta paradigma state-of-the-art in clasificare si invatare din date. In [Stoean et al, 2009c] s-a propus o abordare evolutiva a SVM. In acest fel se simplifica problema centrala a optimizarii in SVM. Modelul propus reduce in mod esential complexitatea in rezolvarea acestei probleme. Se deschide in acest fel calea spre generalizari semnificative si spre aplicatii extrem de complexe in timp real.

4.7 Selectia atributelor in invatarea nesupervizata: optimizare multi-modala Reducerea dimensiunii [Breaban, Luchian, 2009] este o problema intens studiata atat in invatarea supervizata cat si in cea nesupervizata. Principalul scop este reducerea dimensiunii reprezentarii datelor pentru a minimiza costul computational necesar analizei ulterioare, cu alterari minime a semnificatiei sau a acuratetei descriptive. Reducerea dimensiunii este abordata in general in doua moduri: Selectia Atributelor (FS) si Extragerea Atributelor (FE). Abordarea FS identifica atribute irelevante si le exclude; ca o generalizare, ponderarea atributelor poate fi realizata. Metodele FE creaza noi atribute pe baza celor existente. Punctele in spatiu original D-dimensional sunt mapate in noi puncte intr-un spatiu d-dimenional, d<D. Metodele FE furnizeaza o reprezentare imbunatatita a intregului set de date in comparatie cu metodele FS; cu toate acestea, un dezavantaj major al metodelor FE este dificultatea interpretarii relatiilor dintre spatiul original si cel redus. Ponderarea atributelor si ordonarea atributelor sunt generalizari ale selectiei atributelor. Ponderarea atributelor vizeaza cuantificarea numerica a contributiei fiecarui atribut in realizarea celei mai bune partitionari. Ordonarea atributelor este o relaxare a primei abordari si vizeaza stabilirea unei hierarhi de atribute care poate servi in continuare unei selectii a atributelor.

Literatura FS include un numar mai mare de studii decat cea FE, ambele probleme au fost abordate doar relativ recent in mediul nesupervizat. Selectia nesupervizata a atributelor este realizata prin urmatoarele modalitati: 1) abordari filtru bazate pe calculul unei entropii pentru a cuantifica tendinta de grupare a atributelor in diferite subspatii a atributelor. Metoda de invatare nesupervizata ulterioara este complet ignorata; 2) abordari wrapper care realizeaza efectiv cautarea partitiilor in diferite subspatii a atributelor prin utilizarea unui algoritm de clasificare. Metodele wrapper dau rezultate mai bune deoarece evaluarea este bazata chiar pe rezultatele metodei de analiza exploratorie vizata. Metodele wrapper au totusi doua dezavantaje importante: timp computational mare si bias. Intr-un mediu nesupervizat, functia obiectiv care ghideaza cautarea pentru partitii optime induce anumite polarizari/bias-uri asupra dimensiunii spatiului atributelor si a numarului de clase.

In literatura exista mai multe abordari care vizeaza eliminarea bias-ului cu privire la numarul de clase. Totusi, nici o functie fitness nu a fost inca propusa pentru a elimina concomitent ambele bias-uri. Abordari existente utilizeaza proiectarea incrucisata sau algoritmi mult-obiectiv in care bias-ul introdus in prima functie obiectiv este contracarat de o a doua functie obiectiv. Studiile noastre abordeaza selectia atributelor ca problema de optimizare multi-modala: subspatii de atribute diferite pot duce la partitionari semnificative diferite a datelor originale. Odata ce subspatii promitatoare au fost identificate, acestea pot fi utilizate in diferite moduri pentru a oferi o partitionare imbunatatita: a) calea cea mai simpla este de a returna cea mai buna partitie dintre tate optimele locale detectate; in cel mai nefavorabil abordarea aceasta ar trebui sa se

comporte la fel de bine ca optimizatorii globali (datorita capacitatii imbunatatitede explorare); b) partitii bune, obtinute in diferite subspatii ale atributelor, pot servi ca si componente clasificarea ansamblu; aceasta ar fi o abordare interesana deoarece ambele constrangeri necesare pentru ansamble bune de clasificatori sunt indeplinite: calitate si diversitate ridicata; aceasta ipoteza urmeaza a fi verificata expermental in studii viitoare; c) toate submultimile de atribute pot fi utilizate pentru a construi un singur spatiu al atibutelor care sa duca la o partitionare imbunatatita.

Studiile efectuate in cadrul proiectului [Breaban, Luchian, 2009] valideaza cea de a treia ipoteza. Algoritmul genetic Multi-Niche Crowding GA a fost utilizat pentru a determina submultimi de atribute diverse dar de buna calitate in acelasi timp, in conjunctie cu metoda k-mediilor pentru a determina partitiile optime. Solutia este construita utilizand intreaga populatie de la sfarsitul rularii: fiecarui atribut ii este asociata o pondere pe baza prezentei sale in submultimile de atribute codificate de cromozomi. Aceasta abordare de tip wrapper functioneaza intr-un mediu complet nesupervizat: bias-ul referitor la numarul de clase este rezolvat prin utilizarea unei functii potrivite de clasificare nesupervizata iar bias-ul corespunzator dimensionalitatii este rezolvat explicit prin utilizarea proiectarii incrucisate sau implicit datorita cautarii multi-modale in conjunctie cu anumite limite asupra numarului de atribute permis. Experimentele arata ca diversitatea si calitatea solutiilor evoluate in diferite zone ale spatiului de cautare pot fi utilizate pentru a calcula ponderi care ofera o buna aproximare a relevantei atributelor si furnizeaza partitii de calitate ridicata cand sunt utilizate in clasificare. Mai mult, o selectie a atributelor poate fi realizata intr-un pas de post-procesare in spatiul de cautare redus pe baza ordonarii atributelor.

4.8 Coevolutie de tip cooperativ. Aplicatii in rezolvarea problemelor de optimizare de dimensiuni mari. Coevolutia, atat cea de tip cooperativ cat si cea de tip competitiv, este unul dintre mecanismele care permit generarea unor comportamente complexe atat in sistemele naturale cat si in algoritmii inspirati de natura. Variantele de tip cooperativ permit rezolvarea unor probleme complexe. In acest context cercetarea desfasurata in aceasta etapa a vizat in principal maniera in care coevolutia de tip cooperativ poate fi exploatata pentru a imbunatati scalabilitatea unor metaeuristici existente in rezolvarea problemelor de optimizare cu numar mare de variabile. Rezultatele principale au fost cuprinse in lucrarea [Craciun, Nicoara, Zaharie, 2009b] prezentata la LSSC’09 si acceptata pentru publicare.

4.8.1 Analiza aplicabilitatii coevolutiei de tip cooperativ in cresterea scalabilitatii metaeuristicilor Pornind de la cateva modele existente, s-au dezvoltat diferite variante de implementare si s-a studiat impactul lor asupra a doua clase de algoritmi evolutivi: “differential evolution” (DE) si “harmony search” (HS). Trebuie mentionat faptul ca pana in prezent nu au fost studiate variante evolutive pentru “harmony search” iar rezultatele obtinute au confirmat faptul ca se poate obtine o imbunatatire semnificativa a eficientei algoritmului.

Pornind de la structura mecanismului de coevolutie de tip cooperativ care este determinat in principal de modul in care se definesc componentele si de maniera in carea acestea coevolueaza au fost propuse mai multe variante si a fost efectuat un studiu comparativ al acestora. Motivatia acestui studiu comparativ a fost faptul ca in literatura de specialitate nu exista o analiza comparativa a variantelor sincrona respectiv asincrona.

4.8.2 Aspecte practice in implementarea algoritmilor coevolutivi Un element important in faza initiala de investigare a oricarei metode, o reprezinta experimentarea. In contextul analizei experimentale a algoritmilor evolutivi apare

necesitatea dezvoltarii unor noi algoritmi (in practica aceasta implica luarea unui algoritm de baza si alterarea lui prin inlocuirea unor operatori, sau hibridizarea mai multor algoritmi de baza) si determinarea "retetei" parametrilor de control (identificarea unui set de valori, sau a unor formule pentru calcularea parametrilor de control al algoritmilor investigati). In ambele cazuri ceea ce se urmareste este fie eficientizarea resurselor necesare (numar de evaluari a functiilor tinta, sau dimensiunea populatiilor) fie imbunatatirea acuratetii metodelor.

Indiferent de scopul urmarit experimentarea in cazul acestor algoritmi, necesita un numar semnificativ de rulari pentru fiecare combinatie, datorita naturii non-deterministe ale acestora (spre exemplu pentru a clasifica un experiment ca "statistic reprezentativ" necesita cel putin 30 de rulari). Aceasta problema este exacerbata si datorita numarului foarte mare de configuratii posibile.

Un caz concret il reprezinta investigarea impactului co-evolutiei in cazul problemelor de aproximare pentru functii reale cu multe necunoscute (mult mai mare de 100 de necunoscute), in care s-a impus empiric o limita de 5000 de evaluari pentru fiecare necunoscuta. Astfel pentru 1000 de necunoscute vor fi executate in jur de 5 milioane de evaluari ale functiei obiectiv. Ca urmare orice crestere a timpului de evaluare are un impact major asupra timpului total de executie a unui singur experiment. Pentru a reduce timpul total de executie al experimentelor se poate utiliza una dintre urmatoarele metode clasice: · paralelizarea algoritmului in sine - aceasta implica cunoasterea in amanuntime a

modului de functionare al algoritmului, impunerea unor restrictii, reducand astfel flexibilitatea si usurinta de modificare a codului; in general aceasta metoda nu poate fi aplicata decat daca algoritmii vizati o permit;

· distribuirea rularii - practic se executa ca procese independente (pe acelasi calculator, sau pe calculatoare diferite) fiecare experiment.

In urma unei analize atente si verificate experimental, prima metoda de eficientizare -

cea bazata pe paralelizare - a fost considerata insuficienta, din urmatoarele motive: · paralelismul putea fi introdus la nivelul populatiei (evoluand in paralel un set de

indivizi), insa natura algoritmilor bazati pe coevolutie este una seriala, deci aceasta metoda este imposibil de aplicat;

· un alt punct de actiune al paralelismului, putea fi asupra evaluarii populatiei, insa datorita numarului mic de indivizi (50-100) costurile de sincronizare reduc semnificativ castigul (deoarece in cazul cel mai favorabil in locul utilizarii unui procesor timp de 10 secunde, vom utiliza 10 procesoare timp de 1 secunda, ceea ce poate fi obtinut mult mai usor in cazul distribuirii);

· de asemenea se poate incerca paralelizarea functiei de evaluare, insa aceasta metoda nu functioneaza decat asupra anumitor functii (gen suma, produs) fiind imposibil de generalizat;

· nu in ultimul rand munca depusa pentru implementarea si depanarea codului ar fi fost comparabil cu timpul pierdut in asteptarea rezultatelor (in cazul neparalelizarii).

Ca urmare decizia eficientizarii a fost luata prin aplicarea distributiei

experimentelor pe mai multe noduri. Un alt element important in eficientizarea rularilor il reprezinta eficienta limbajului

de programare. Spre exemplu in experimente ce implica in principal calcule numerice, diferenta intre un limbaj interpretat (byte-code sau scripting) fata de unul compilat la cod masina poate fi intre 5 si 10 ori. In cazul nostru implementarea a fost realizata in doi pasi: · implementare rapida in Java, ce a servit scopul tatonarii problemei si identificarii unor

solutii promitatoare (algoritmi potentiali si configuratii), in urma unor rulari pe dimensiuni reduse ale problemelor;

· implementare laborioasa in C++, care a servit rolul aprofundarii metodelor identificate anterior, precum si a parametrilor de control optimi.

O valoare empirica a diferentei de eficienta este in jur de 3, anume implementarea in Java poate dura in jur de 20 de minute, pe cand cea din C++ doar 7 minute. (Rularile fiind realizate pe calculatoare comparabile, si pentru probleme de optimizare cu numar de variabile de ordinul sutelor si miilor). Chiar si acele 7 minute pot reprezenta mult daca numarul de experimente ce trebuie efectuat este de ordinul sutelor. Iar astfel inca se simte nevoia optimizarii. Urmatorul pas a constat in: · inlocuirea parametrilor variabili cu constante la compilare, (lucru realizat prin

utilizarea template-urilor in C++) astfel incat compilatorul poate eficientiza buclele; · inlocuirea alocarii dinamice cu "smart-pointers", care recicleaza obiectele (spre

exemplu indivizii unei populatii). Acest pas este necesar doar daca se doreste pastrarea implementarii intr-un stil orientat-obiect;

· fortarea "inline-ing"-ului tuturor functiilor, cea ce duce la eliminarea costurilor de apel a functiilor;

· utilizarea unor biblioteci matematice specializate.

Ca urmare a acestor tehnici timpul de rulare a fost imbunatatit pana la aproximativ 2 minute.

Totusi exista potential pentru mai mult: inlocuirea compilatorului. Spre exemplu cele 2 minute prezentate anterior au fost obtinute in urma rularii codului compilat cu GCC (GNU Compiler Collection), dar prin utilizarea lui ICC (Inter C Compiler) timpul de executie a fost redus la 20 de secunde (in urma selectiei, prin experimentare, a unui set potrivit de optiuni de compilare, specializate pentru arhitectura hardware pe care va avea loc rularea).

In concluzie, in urma aplicarii mai multor pasi de eficientizare a rularii, s-a ajuns la o diferenta considerabila (20 de minute -- Java, 20 de secunde C++ compilat cu ICC, deci un factor de 600), ceea ce ne-a permis executia a mai mult de 1000 de teste preliminare, si aproximativ 400 de teste consolidate si publicate, fiecare a 30 de rulari (totalizand 17 zile de timp de procesor.)

4.8.3 Rezultate obtinute in optimizarea functiilor cu numar mare de variabile S-a efectuat o serie extinsa de teste numerice, experimente care au permis extragerea catorva concluzii privind performantele coevolutiei de tip cooperativ in rezolvarea problemelor de optimizare de dimensiuni mari.

Varianta asincrona se comporta usor mai bine decat cea sincrona si lungimea evolutiei independente per componenta depinde de metaeuristica pe care se aplica coevolutia (in cazul algoritmilor de tip HS trebuie sa fie relativ mica – pana in 5 – iar in cazul algoritmilor de tip DE s-au obtinut rezultate bune si pentru 50 de etape de evolutie independenta/componenta).

In ceea ce priveste scalabilitatea, rezultatele obtinute pentru HS confirma faptul ca prin coevolutie de tip competitiv comportarea algoritmului poate fi imbunatatita semnificativ.

4.9 Comportament haotic in retele neuronale. Analiza arhitecturilor de tip inel. In aceasta etapa a proiectului s-a continuat analiza comportamentului haotic al retelelor neuronale cu interconectivitate slaba si neuroni caracterizati prin intarzieri explorandu-se cazul arhitecturilor de tip inel, atat uni cat si bidirectionale.

4.9.1 Arhitectura de tip inel In lucrarea [Kaslik, Balint, 2009] s-au publicat rezultate referitoare la un ansamblu de p neuroni conectati intr-o topologie de tip inel unidirectional: neuronul i transmite un semnal neuronului i+1 pentru fiecare i intre 1 si p-1 iar neuronul p transmite un semnal catre primul neuron.

Fiecare neuron este caracterizat de o intarziere proprie cu care transmite semnalul catre neuronul urmator. Utilizand o tehnica similara studiului a doi neuroni (propusa in lucrarile elaborate in etapa anterioara) dar adaptata pentru cazul a p neuroni s-a putut identifica domeniul de stabilitate si au fost identificate valori ale parametrilor caracteristici pentru care se pot identifica bifurcatii de tip Fold/Cusp, Neimark-Sacker si Flip.

Analiza teoretica a retelei cu topologie de tip inel arata ca daca produsul ponderilor asociate interconexiunilor si al pantelor functiilor de activare in origine este suficient de mic in valoare absoluta atunci solutia nula este asimptotic stabila. Pe masura ce valoarea acestui produs creste dinamica in jurul originii devine din ce in ce mai complexa. Daca in plus functia de activare a cel putin unui neuron se anuleaza pentru un argument nenul atunci sistemul are un comportament haotic in sens Marotto.

4.9.2 Arhitectura bidirectionala In lucrarea [Kaslik, 2009] s-a realizat o analiza similara pentru cazul arhitecturii bidirectionale: neuronul i este conectat in maniera circulara atat cu neuronul (i-1) cat si cu neuronul (i+1).

Pentru aceasta arhitectura au fost identificati parametrii caracteristici pentru care apar bifurcatii in origine si a fost demonstrata existenta bifurcatiilor Fold/Cusp, Neimark-Sacker si a unor bifurcatii de codimensiune mare.

Pentru cazul particular a 4 neuroni au fost vizualizate diverse tipuri de comportament convergent sau haotic. S-a observat ca dinamica intr-o vecinatate a originii devine din ce in ce mai complexa pe masura ce parametrii caracteristici devin mai mari.

4.10 Analiza robustetii metaeuristicilor. Studiu de caz in planificarea taskurilor in sistemele distribuite. Planificarea task-urilor in sistemele distribuite este o problema dificila datorita caracterului dinamic al mediului de executie. Problema de planificare poate fi formulata ca o problema de optimizare cu sau fara restrictii, uni sau multi-criteriala. In majoritatea variantelor functia/functiile obiectiv depind de estimari ale caracteristicilor masinilor (procesoarelor) pe care urmeaza sa fie executate taskurile.

Datorita specificului sistemelor distribuite aceste estimari sunt influentate de zgomot, astfel ca un aspect important in rezolvarea problemei este asigurarea robustetei metodei. In lucrarile [Zamfirache, Frincu, Zavoianu, 2009] si [Zamfirache, 2009] au fost identificate particularitatile problemei si a fost initiata analiza robustetii algoritmilor bazati pe modelul coloniilor de furnici. Varianta de problema abordata in [Zamfirache, 2009] se refera la minimizarea duratei maxime de finalizare a task-urilor.

Au fost implementate si analizate mai multe variante de algoritmi care difera intre ei prin modul de calcul a probabilitatii asignarii unui task la un procesor. Au fost efectuate teste comparative folosind ansamblul de date de test din (Braun, 2001) care modeleaza scenarii ce difera intre ele prin gradul de heterogeneitate al task-urilor respectiv procesoarelor. Analiza robustetii a fost efectuata prin adaugarea unor perturbatii aleatoare in estimarile timpilor de executie corespunzatori diferitelor scenarii. Rezultatele preliminare obtinute ilustreaza faptul ca in cazul in care atat task-urile cat si procesoarele sunt heterogene algoritmii de tip ACO se comporta mai bine decat euristicile traditionale, cum este MinMin.

4.11 Mediu pentru proiectarea si testarea metaeuristicilor inspirate de natura Necesitatea unei platforme generice pentru proiectarea si testarea metaeuristicilor inspirate de natura este motivata de diversificarea tehnicilor din aceasta categorie. Odata cu dezvoltarea de noi metaeuristici sau de noi variante pentru cele bine-cunoscute

se pune problema testarii acestora prin compararea cu variantele clasice, impunandu-se necesitatea folosirii unei platforme care sa ofere multiple date de test si posibilitati de evaluare, sa asigurae faptul ca rezultatele sunt obtinute ın conditii similare de rulare si deci sunt comparabile. De asemenea, prin dezvoltarea unui cadru care sa modeleze structurile generice ale diferitelor clase de metaeuristici se pot usor testa noi combinatii sau se pot adauga noi implementari a unor componente existente evitandu-se astfel reimplementarea de la zero a ıntregului sistem pentru testarea unei idei noi.

La ora actuala exista o serie de platforme destinate calculului evolutiv si metaeuristicilor inrudite dintrre care se pot aminti: ECJ, jMetal, JCLEC, Evolvica, ParadisEO, OpenBeagle, PISA. Principalele aspecte pozitive ale acestor platforme (in particular, ECJ, JCLEC si ParadisEO) sunt legate de faptul ca indeplinesc o serie de criterii de genericitate (ofera reprezentari, functii de evaluare dar si operatori generici). Unul dintre principalele dezavantaje ale acestor platforme este suportul limitat pentru analize statistice ale comportarii algoritmilor, element esential in stabilirea eficacitatii si eficientei metaeuristicilor.

4.11.1 Structura functionala si arhitectura platformei propuse In acest context s-a stabilit structura functionala a unei alternative la platformele mentionate mai sus care sa care sa reuneasca ın cadrul unei aplicatii componente care sa asiste utilizatorul ın diferitele etape de lucru cu metaeuristici inspirate de natura: dezvoltare (extinderea modulului cu noi componente), proiectare (compunerea elementelor existente), validarea configuratiilor, rulare si prelucrarea rezultatelor. Dezvoltarea unei astfel de platforme este in concordanta cu obiectivul general: Ob4. „Dezvoltarea unui cadru general, flexibil si usor de utilizat pentru selectia si aplicarea inteligenta a metaeuristicilor inspirate de natura problemelor reale”

In aceasta etapa a fost stabilita arhitectura aplicatiei si rolul fiecarui modul. Aplicatia este structurata din module care grupeaza functionalitati similare. Aceste module vor fi ıncarcate, ın functie de necesitatile sistemului, la startup sau pe parcursul rularii. Gestiunea modulelor este centalizata ıntr-un controller de module (ModuleController) care pe langa rolul de a porni si de a opri modulele mai are si rolul de a pastra un registru al acestora pentru regasirea ulterioara astfel ıncat modulele sa poata comunica ıntre ele.

4.11.2 Configuratia si modulele aplicatiei

Configuratia initiala (la pornire) a aplicatiei este stabilita dinamic cu ajutorul unui script de pornire. Acest script are rolul de a defini o serie de perechi de tipul (cheie, valoare) ce reprezinta parametrii necesari configurarii diferitelor module si de a ıncarca anumite modulele. Similar, la oprirea aplicatiei este rulat un script de oprire ın care se poate defini comportamentul aplicatiei la oprire. Ca si limbaj de scripting a fost ales jscheme datorita sintaxei compacte datorate limbajului scheme si a facilitatii de accesare a claselor java pusa la dispozitie de aceasta implementare. De asemenea, prin intermediul unui interpretor global, utilizatorul poate interactiona cu sistemul in lipsa unei interfete grafice. Modelul propus este inspirat de cel pus la dispozitie de platforma ECJ cu mici modificari ın ceea ce priveste definirea algoritmilor si modalitatea de regasire a componentelor referite.

Exista trei module de baza in cadrul aplicatiei: modulul de design, modulul de rulare si modulul de prelucrari statistice.

Modulul de design are rolul de a stabili configuratiile de rulare a metaeuristicilor si de a valida aceste configuratii. Practic, folosind modulul de design utilizatorul poate defini diferite scenarii de rulare care sunt validate si salvate sub forma unor fisiere de configurare care sunt ulterior folosite de modulul de rulare ın procesul de instantiere a componentelor. Aceste scenarii definite de utilizator sunt grupate sub forma de proiecte aflate ıntr-o zona de lucru (workspace). Strategia de configurare a componentelor este inspirata de fisierele de configurare din platforma ECJ. Acestea sunt fisiere ierarhice de proprietati (un fisier poate mosteni continutul parintelui printr-o procedura de tip include)

ın care fiecare cheie reprezinta o cale care modeleaza ierarhia de componente. O astfel de cale este formata dintr-o baza (calea componentei parinte) concatenata cu un cuvant cheie ce reprezinta numele parametrului componentei respective. Dificultatea elaborarii unui fisier de parametri ın ECJ vine din faptul ca lista parametrilor pentru fiecare componenta cat si restrictiile pentru valorile acestora sunt documentate la nivel de javadoc. Pentru a ajuta utilizatorul ın procesul de configurare, modulul de design pe care il propunem foloseste doua concepte, definitie si legatura (binding), care ın final vor forma un scenariu de configurare similar fisierelor de parametrii din ECJ. Pentru fiecare entitate care poate fi componenta a unei metaeuristici, sistemul va detine o instanta definitie a entitatii respective ın care sunt specificate elementele de configurare necesare si constrangerile acestora. Utilizatorul defineste scenarii de rulare (grupate ın proiecte) folosind definitiile disponibile (ın modelul standard sau adaugate de utilizator) completand componente binding. O componenta binding contine: o referinta catre definitia corespunzatoare, o lista de binding-uri pentru parametri, o lista de binding-uri pentru socket-uri.

Modulul de rulare este responsabil de instantierea componentelor metaeuristiciilor pornind de la un scenariu de configurare si de rulare a algoritmilor.

Modulul de prelucrari statistice are ca scop asigurarea prelucrarii rezultatelor in concordanta cu optiunile utilizatorului pentru a permite acestuia efectuare de comparatii si studii de eficienta. Acest modul va permite efectuarea prelucrarilor statistice uzuale si returnarea rezultatelor intr-un format care sa permita vizualizarea lor atat in format text cat si in format grafic.

4.12 Invatare colectiva cu autoorganizare. Minority Game Mai multe lucrari pe aceasta tema raportate “in curs” in etapa anterioara au aparut efectiv in reviste cotate ISI [Istrate, 2009a], [Percus, 2008], [Istrate, 2009b].

S-a studiat un model de “invatare colectiva” cu autoorganizare care generalizeaza celebrul Minority Game din econofizica, un model stilizat de functionare a pietelor financiare [Istrate, 2009d]. In varianta noastra inlocuim functia minoritate cu o functie booleana simetrica arbitrara si ne propunem sa raspundem la urmatoarea intrebare: cum influenteaza structura functiei booleene proprietatile dinamicii ? In particular:

1. Exista functii booleene simetrice care nu sunt “colectiv invatabile”, in sensul in care functia minoritate este invatabila in Minority Game ?

2. Putem caracteriza functiile “colectiv invatabile”, poate prin metode de tipul analizei Fourier pe corpuri finite (care s-a dovedit foarte utila recent in teoria functiilor booleene) ?

In [Istrate, 2009d] obtinem un raspuns afirmativ la prima intrebare:

asa numita functie “paritate negata” nu este invatabila colectiv (Figura 1), si dezvoltam o explicatie pentru acest lucru.

Figura 1: Functia “paritate negata” nu este colectiv invatabila. Valoarea medie a parametrului de ordine e mai mare decat cea pentru modelul aleator (linia) pentru toate valorile parametrului memorie.

Problema a doua s-a dovedit mult mai dificila: rezultatele experimentale din [Istrate,

2009d] arata ca tipurile de comportament ale modelului sunt mult mai bogate decat am anticipat initial:

· Modelul general are in multe cazuri “puncte fixe”, de mai multe tipuri. Aceste puncte fixe nu apar la functia minoritate. Eliminarea lor complica considerabil definitiile.

· Proprietatile modelului depind intr-o maniera foarte delicata de felul in care masuram impactul propriei alegeri asupra functiei agregate. Pentru a ilustra acest lucru sa notam ca in functia paritate setand un bit 0/1 putem modifica valoarea functiei independent de ceilalti biti. Acest lucru nu este adevarat in cazul functiei minoritate.

· parametrul global de ordine, cel al carui masurare indica “invatarea colectiva” este mult mai dificil de definit in general decat in cazul functiei minoritate. In particular, desi am obtinut un parametru generic, nu este inca foarte clar ca alegerea noastra este adecvata in general.

Cu toate acestea rezultatele obtinute pana acum sunt foarte promitatoare, si arata

faptul ca modelul studiat are intr-adevar proprietati specifice unui proces de “invatare colectiva cu autoorganizare”.

4.13 Un model strategic de generare a retelelor sociale In lucrarea [Istrate, 2009e] se propune un model strategic de formare a retelelor sociale. Modelul e o varianta a modelului clasic al lui Jackson si Watts (Jackson, 2000), si difera prin acesta prin ordinea de activare a muchiilor: in modelul initial aceasta era aleasa aleator.

In varianta noastra consideram un proces de “contagiune” specificat astfel:

· consideram o a doua retea “de influenta”, ale carei varfuri sunt muchiile retelei initiale.

· Procesul de activare se efectueaza prin “contagiune”: o muchie activata “infecteaza” (determina activarea) unui numar mediu de vecini din aceasta retea de influenta.

Putem justifica aceasta ordine de activare prin contagiune prin exemplele reale la

care se aplica modelul Jackson-Watts: modelarea legaturilor comerciale, a relatiilor de colaborare, etc. In acest context activarea unei legaturi poate determina activarea/dezactivarea altor legaturi “influentate” de aceasta.

Folosind conceptul de stari stocastic stabile al lui Peyton-Young (Peyton, 1998) am obtinut o caracterizare a retelelor care se obtin cand rulam procesul dinamic din modelul Jackson-Watts cu activarea de mai sus: sunt retelele care minimizeaza o anumita functie “potential”, similar cazului activarii aleatoare. Spre deosebire de acest caz demonstratia rezultatului este mult mai delicata, modelul fiind specificat de un lant Markov cu structura mai complicata.

Mentionam impactul stiintific al cercetarilor efectuate in cadrul proiectului: Gabriel Istrate va participa (in calitate de prezentator invitat) la un “Workshop on Techniques and Challenges from Statistical Physics”, organizat la Centre de Recerca Matemàtica (CRM), Bellaterra, Barcelona, Spain, in perioada 14-16 Octombrie 2009.

4.14 Determinarea comunitatilor in retele sociale folosind algoritmi de tip swarm

In lucrarea [Breaban, Alboaie, Luchian, 2009] este abordata o problema de mare interes si studiata intens in ultimii ani, si anume determinarea comunitatilor in retelele sociale.

Problema este definita formal ca o problema de grafuri: se cere identificarea de grupuri de noduri intre care exista conexiuni dense. Este un tip de problema de clasificare intr-un spatiu vag definit. Din acest motiv, datele sunt mapate intr-un spatiu 2-dimensional euclidian prin simularea particulelor intr-un roi.

In pasul de initializare, fiecarui utilizator din comunitate (corespunzand unui nod in graf) i se asociaza un punct generat aleator in spatiul 2-dimensional. Aceste puncte sunt in continuare considerate vectori-pozitie ale particulelor in metoda PSO. In continuare, un proces iterativ duce la organizarea particulelor astfel incat utilizatorii cu interactiuni puternice/dense vor corespunde unor puncte apropiate in spatiu Euclidian. In final, in spatiul Euclidian se aplica o procedura de clasificare mai putin costisitoare.

5. Anexe

Lista lucrarilor publicate in cadrul etapei curente:

David Iclanzan, D. Dumitrescu, Béat Hirsbrunner. Correlation guided model building. In GECCO ’09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 421–428, New York, NY, USA, 8-12 July 2009. ACM. ISBN 978-1-60558-325-9. http://doi.acm.org/10.1145/1569901.1569960. A. Gog, C. Chira, Cellular Automata Rule Detection using Circular Asynchronous Evolutionary Search, Proceedings of the 4th International Workshop on Hybrid Artificial Intelligence Systems (HAIS 2009), Salamanca, Spain, Lecture Notes in Computer Science, vol. 5572, 2009a, p. 261-268. A. Gog, C. Chira. D. Dumitrescu, Asynchronous Evolutionary Search: Multi-Population Collaboration and Complex Dynamics, Proceedings of IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, 2009b, p. 240-246.

A. Gog, C. Chira, D. Dumitrescu, D. Zaharie, Analysis of Some Mating and Collaboration Strategies in Evolutionary Algorithms, SYNASC 2008, IEEE Computer Society, 2008, p. 538-542, volum aparut in 2009. C. Chira, A. Gog, D. Zaharie, D. Dumitrescu, Complex Dynamics in a Collaborative Evolutionary Search Model, Creative Mathematics and Informatics, vol. 17, nr. 3, 2008 (accepted for publication). C-M. Pintea, C. Chira, D.Dumitrescu, Sensitive Ants: Inducing Diversity in the Colony, Nature Inspired Cooperative Strategies for Optimization, Series "Studies in Computational Intelligence", Vol. 236 ( Krasnogor, N.; Melián-Batista, B.; Moreno-Pérez, J.A.; Moreno-Vega, J.M.; Pelta, D.; Eds.) Springer-Verlag, 2009a (ISBN: 978-3-642-03210-3) C. Chira, C-M. Pintea, D. Dumitrescu, An Agent-Based Approach to Combinatorial Optimization, Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844, Vol. III (2008), Suppl. Issue, pp. 212-217. C.M. Pintea, C. Chira, D. Dumitrescu, Results of Ant-Based Models for Solving the Linear Ordering Problem, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing Timisoara, Romania, 2009b. D. Dumitrescu, R. I. Lung, T. D. Mihoc, Evolutionary Equilibria Detection in Non-cooperative Games, Book Series: Lecture Notes in Computer Science, Publisher Springer Berlin / Heidelberg, Volume 5484 / 2009, Book: Applications of Evolutionary Computing, DOI 10.1007/978-3-642-01129-0, ISBN 978-3-642-01128-3, DOI 10.1007/978-3-642-01129-0_29, 2009a, pages 253-262 D. Dumitrescu, R. I. Lung, T. D. Mihoc, Generative Relations for Evolutionary Equilibria Detection, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, 2009b, Montreal, 1507-1512 D. Dumitrescu, R. I. Lung, T. D. Mihoc, Equilibria Detection In Electricity Market Games, Studia Universitatis Babes-Bolyai, Informatica Series, Special Issue, 2009c, pp. 111–114 Dumitrescu, R. I. Lung, T. D. Mihoc, Approximating and Combining Equilibria in Non cooperative Games, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing Timisoara, Romania, 2009d Catalin Stoean, Mike Preuss, Ruxandra Stoean, D. Dumitrescu, Multimodal Optimization by Means of a Topological Species Conservation Algorithm, IEEE Transactions on Evolutionary Computation, second revision submitted, 2009a. Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, An Evolutionary Resemblant to Support Vector Machines for Classification and Regression, Journal of the Operational Research Society, Palgrave Macmillan, Vol. 60, Issue 8 (August 2009), Special Issue: Data Mining and Operational Research: Techniques and Applications, Guest Editors: Kweku-Muata Osei-Bryson and Vic J Rayward-Smith, pp. 1116-1122, ISSN 0160-5682, 2009b. http://www.palgrave-journals.com/jors/journal/v60/n8/abs/jors2008124a.html Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, An Evolutionary Approximation for the Coefficients of Decision Functions within a Support Vector Machine Learning Strategy, Foundations on Computational Intelligence, Studies in Computational Intelligence, Springer, Aboul Ella Hassanien and Ajith Abraham (Eds.), Vol. 1, pp. 83-114, ISSN 1860-949X, 2009c.

http://www.springerlink.com/content/171842762370r863/?p=9c1e9fb4a20243ecade47cd622bafa6dπ=0 C. Craciun, M. Nicoara, D. Zaharie, Enhancing the scalability of metaheuristics by cooperative coevolution, 7th International Conference on "Large-Scale Scientific Computations", Sozopol, Bulgaria, June 4-8, 2009b, acceptata pentru publicare in post-proceedings (LNCS) E. Kaslik, Dynamics of a Discrete-Time Bidirectional Ring of Neurons with Delay, Proceedings of International Joint Conference on Neural Networks, Atlanta, Georgia, USA, June 14-19, 2009, pp.1539-1546. E. Kaslik, St. Balint, Complex and chaotic dynamics in a discrete-time-delayed Hopfield neural network with ring architecture, acceptata pentru publicare in Neural Networks, (2009), doi:10.1016/j.neunet.2009.03.009

D. Zaharie, Influence of crossover on the behavior of Differential Evolution Algorithms, Applied Soft Computing 9 (2009) 1126–1138

F. Zamfirache, Robustness Analysis of Ant-based Scheduling in Heterogeneous Computing Environments, acceptata pentru prezentare la NCA workshop, SYNASC’09, Timisoara, Sept. 26-29, 2009. Gabriel Istrate, On the dynamics of Social Balance on general networks (with an application to XOR-SAT). Fundamenta Informaticae, 91 (2), pp. 341-356, 2009a. Allon Percus, Gabriel Istrate, Bruno Tavares Gonçalves, Robert Z. Sumi, Stefan Boettcher, The Peculiar Phase Structure of Random Graph Bisection. Journal of Mathematical Physics, 49 (12), p. 125219, 2008. Gabriel Istrate. Geometric Properties of Satisfying Assignments of random ε-1-in-k SAT. International Journal of Computer Mathematics, 2009b. Gabriel Istrate, Madhav V. Marathe, S.S. Ravi, Adversarial Scheduling in Evolutionary Game Dynamics, Computational and Mathematical Organization Theory, 2009c. G. Istrate, Robert Z. Sumi, Computation and coordination in Boolean markets, Technical report, 2009d. G. Istrate, Incorporating contagion into models of network formation, submitted to Journal of Economic Behavior and Organization, 2009e. A. Bautu, H. Luchian, Further Investigations on Using the Tree Bond-based Representation for Ising Spin Glasses, to appear in Proceedings of the Natural Computing and Applications Workshop, 11th International Symposium on Symbolic and Numeric Algorithms Scientific Computing (SYNASC’09), Timisoara, Sept. 26-29, 2009. A. Bautu, E. Bautu. Energy Minimization of Point Charges on a Sphere with Particle Swarms, Romanian Journal of Physics - Volume 54, Numbers 1-2, pp. 29-36, 2009. A. Bautu. A Study of Topology Influence on Particle Swarm Optimization for Thomson Problem. Proceedings of the 9th Balkan Conference on Operational Research (BALCOR 2009), Constanta, 2-6 Sept. 2009, ISBN 973-86979-9-9.

E. Bautu, A. Bautu, H. Luchian. Stock Market Trend Forecasting with GEP Ensembles, to appear in Proceedings of the Natural Computing and Applications Workshop, 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC’09), Timisoara, Sept. 26-29, 2009. E. Bautu, A. Barbulescu. Forecasting Financial Time Series with a Hybrid ARIMA-GEP Approach. Proceedings of the 9th Balkan Conference on Operational Research (BALCOR 2009), Constanta, 2-6 Sept. 2009, ISBN 973-86979-9-9. A. Barbulescu, E. Bautu. Mathematical Models of Climate Evolution in Dobrudja, in Theoretical and Applied Climatology, Springer Wien, 2009, http://www.springerlink.com/content/b664275mn3j4l627/. M. Breaban, H. Luchian. Unsupervised Feature Weighting with Multi Niche Crowding Genetic Algorithms. Proceedings of the 11th Annual conference on Genetic and evolutionary computation (GECCO 2009), NY, USA, ACM, 1163-1170, 2009. M. Breaban, L. Alboaie, H. Luchian. Guiding Users within Trust Networks Using Swarm Algorithms. Proceedings of IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, IEEE, 1770-1777, 2009.

6. Concluzii

Analizele teoretice, implementarile si studiile experimentale efectuate in cadrul acestei etape au condus la urmatoarele concluzii:

· metodologia propusa pentru construirea modelelor necesare estimarii distributiilor utilizate in procesul de evolutie a populatiilor de solutii potentiale s-a dovedit eficienta, conducand la construirea unor metode scalabile aplicabile in rezolvarea problemelor de dimensiuni mari;

· structurarea populatiilor algoritmilor evolutivi prin utilizarea unei topologii dinamice, ghidata de calitatea solutiilor, precum si a unor mecanisme de colaborare intre subpopulatii cu caracteristici explorative diferite a condus la rezultate bune atat in contextul rezolvarii problemelor de optimizare in domenii continue cat si in cel al proiectarii automatelor celulare;

· introducerea de noi modele de comunicare si adaptare a agentilor dintr-un sistem stigmergic a permis aplicarea cu succes a acestora in rezolvarea unor probleme de optimizare combinatoriala cu aplicatii practice in domeniul economic;

· metodologia de caracterizare si aproximare evolutiva a echilibrelor in jocuri necooperative propusa in aceasta etapa a permis analiza unui numar mare de variante de echilibru si a deschis o directie de studiu cu un potential aplicativ semnificativ;

· variantele de masini cu suport vectorial bazate pe tehnici evolutive s-au dovedit a fi instrumente eficiente de analiza a datelor cu aplicabilitate in rezolvarea problemelor complexe de clasificare ce intervin in diferite domenii;

· selectia atributelor in clasificarea nesupervizata a fost abordata cu succes ca si o problema de optimizare multi-modala folosind un algoritm genetic (pentru determinarea unor submultimi de atribute diverse de buna calitate) in conjunctie cu metoda k-mediilor (pentru determinarea partitiilor optime);

· rezultatele obtinute in studiul modelelor de invatare colectiva cu auto-organizare, a modelelor de formare a retelelor sociale si detectare a

comunitatilor in retelele sociale sunt promitatoare si cu potential aplicativ in domeniul financiar si in cel al proiectarii sistemelor colaborative;

· procesele de coevolutie permit modelarea unor dinamici complexe, iar din punct de vedere practic permit imbunatatirea scalabilitatii diverselor metaeuristici inspirate de natura; s-au identificat aspectele de implementare care permit eficientizarea aplicarii coevolutiei de tip competitiv pentru rezolvarea problemelor de dimensiuni mari;

· primele rezultate privind robustetea metaeuristicilor inspirate de modelul coloniilor de furnici a permis identificarea unor variante adecvate problemelor cu caracter dinamic;

· platformele existente pentru proiectarea metaeuristicilor inspirate de natura au limitari in ceea ce priveste analiza statistica a rezultatelor, motiv pentru care a fost propusa arhitectura unui mediu de proiectare si testare care sa aiba un modul dedicat analizei statistice a rezultatelor.

Directiile de lucru identificate pentru a fi continuate in etapa urmatoare sunt:

· extinderea rezultatelor obtinute in ceea ce priveste caracterizarea si detectarea echilibrelor in jocuri necooperative pentru cazul strategiilor mixte si adaptarea tehnicii evolutive pentru a permite detectarea echilibrelor in cazul unui numar mare de jucatori;

· continuarea studiilor privind identificarea unor tehnici evolutive adecvate rezolvarii problemelor complexe (de exemplu, evolutia regulilor pentru automate celulare);

· dezvoltarea de algoritmi de planificare a sarcinilor in medii distribuite cu caracter dinamic;

· aplicarea mecanismului de coevolutiei pentru alte metaeuristici si testarea comportarii pentru alte probleme de dimensiuni mari (de exemplu, optimizarea structurilor moleculare);

· utilizarea rezultatelor obtinute in studiile referitoare la comportamentul haotic al retelelor neuronale in analiza sistemelor de tip “reservoir computing”;

· finalizarea implementarii mediului de proiectare si testare a metaeuristicilor inspirate de natura.

7. Bibliografie David Iclanzan and D. Dumitrescu, (Iclanzan, Dumitrescu, 2008), Going for the big fishes: Discovering and combining large neutral and massively multimodal building-blocks with model based macro-mutation. In GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 423–430, Atlanta, GA, USA, 2008. ACM. David Iclanzan and D. Dumitrescu, (Iclanzan, Dumitrescu, 2008a), How can artificial neural networks help making the intractable search spaces tractable. In 2008 IEEE World Congress on Computational Intelligence (WCCI 2008), pages 4016–4023, Hong-Kong, 01-06 June 2008. ISBN 978-1-4244-1823-7. David Iclanzan and D. Dumitrescu, (Iclanzan, Dumitrescu, 2008b), Towards memoryless model building. In GECCO ’08: Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, pages 2147–2152, Atlanta, GA, USA, 2008. ACM. David Iclanzan and D. Dumitrescu, (Iclanzan, Dumitrescu, 2008c), Large-scale optimization of non-separable building-block problems. In PPSN 2008: 10th International

Conference on Parallel Problem Solving From Nature, pages 899–908, Dortmund, Germany, 13-17 September 2008. 10.1007/978-3-540-87700-4\s\do5(8)9. A. Gog, C. Chira, Cellular Automata Rule Detection using Circular Asynchronous Evolutionary Search, Proceedings of the 4th International Workshop on Hybrid Artificial Intelligence Systems (HAIS 2009), Salamanca, Spain, Lecture Notes in Computer Science, vol. 5572, 2009a, p. 261-268. A. Gog, C. Chira. D. Dumitrescu, Asynchronous Evolutionary Search: Multi-Population Collaboration and Complex Dynamics, Proceedings of IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, 2009b, p. 240-246. A. Gog, C. Chira, D. Dumitrescu, D. Zaharie, Analysis of Some Mating and Collaboration Strategies in Evolutionary Algorithms, SYNASC 2008, IEEE Computer Society, 2008, p. 538-542. C. Chira, A. Gog, D. Zaharie, D. Dumitrescu, Complex Dynamics in a Collaborative Evolutionary Search Model, Creative Mathematics and Informatics, vol. 17, nr. 3, 2008 (accepted for publication).

C-M. Pintea, C. Chira, D.Dumitrescu, Sensitive Ants: Inducing Diversity in the Colony, Nature Inspired Cooperative Strategies for Optimization, Series "Studies in Computational Intelligence", Vol. 236 ( Krasnogor, N.; Melián-Batista, B.; Moreno-Pérez, J.A.; Moreno-Vega, J.M.; Pelta, D.; Eds.) Springer-Verlag, 2009a (ISBN: 978-3-642-03210-3) C. Chira, C-M. Pintea, D. Dumitrescu, An Agent-Based Approach to Combinatorial Optimization, Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844, Vol. III (2008), Suppl. Issue, pp. 212-217. C.M. Pintea, C. Chira, D. Dumitrescu, Results of Ant-Based Models for Solving the Linear Ordering Problem, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing Timisoara, Romania, 2009b. D. Dumitrescu, R. I. Lung, T. D. Mihoc, Evolutionary Equilibria Detection in Non-cooperative Games, Book Series: Lecture Notes in Computer Science, Publisher Springer Berlin / Heidelberg, Volume 5484 / 2009, Book: Applications of Evolutionary Computing, DOI 10.1007/978-3-642-01129-0, ISBN 978-3-642-01128-3, DOI 10.1007/978-3-642-01129-0_29, 2009, pages 253-262. D. Dumitrescu, R. I. Lung, T. D. Mihoc, Evolutionary Equilibria Detection in Non-cooperative Games, EvoWorkshops 2009, Applications of Evolutionary Computing, EvoWorkshops 2009: EvoCOMNET, EvoENVIRONMENT, EvoFIN, EvoGAMES, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, EvoNUM, EvoSTOC, EvoTRANSLOG, Tubingen, Germany, April 15-17, 2009. D. Dumitrescu, R. I. Lung, T. D. Mihoc, Generative Relations for Evolutionary Equilibria Detection, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, 2009, Montreal, 1507-1512 D. Dumitrescu, R. I. Lung, T. D. Mihoc, Equilibria Detection In Electricity Market Games, Studia Universitatis Babes-Bolyai, Informatica Series, Special Issue, 2009c, pp. 111–114 Dumitrescu, R. I. Lung, T. D. Mihoc, Approximating and Combining Equilibria in Non cooperative Games, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing Timisoara, Romania, 2009

Catalin Stoean, Mike Preuss, Ruxandra Stoean, D. Dumitrescu, Multimodal Optimization by Means of a Topological Species Conservation Algorithm, IEEE Transactions on Evolutionary Computation, second revision submitted, 2009a. Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, An Evolutionary Resemblant to Support Vector Machines for Classification and Regression, Journal of the Operational Research Society, Palgrave Macmillan, Vol. 60, Issue 8 (August 2009), Special Issue: Data Mining and Operational Research: Techniques and Applications, Guest Editors: Kweku-Muata Osei-Bryson and Vic J Rayward-Smith, pp. 1116-1122, ISSN 0160-5682, 2009b. http://www.palgrave-journals.com/jors/journal/v60/n8/abs/jors2008124a.html Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, An Evolutionary Approximation for the Coefficients of Decision Functions within a Support Vector Machine Learning Strategy, Foundations on Computational Intelligence, Studies in Computational Intelligence, Springer, Aboul Ella Hassanien and Ajith Abraham (Eds.), Vol. 1, pp. 83-114, ISSN 1860-949X, 2009c. http://www.springerlink.com/content/171842762370r863/?p=9c1e9fb4a20243ecade47cd622bafa6dπ=0

C. Craciun, M. Nicoara, D. Zaharie - Using Cooperative Coevolution in Solving High-Dimensional Optimization Problems, Zilele Academice Timisene, mai 2009a

C. Craciun, M. Nicoara, D. Zaharie – Enhancing the scalability of metaheuristics by cooperative coevolution, 7th International Conference on "Large-Scale Scientific Computations", Sozopol, Bulgaria, June 4-8, 2009b, acceptata pentru publicare in post-proceedings (LNCS) E. Kaslik - Dynamics of a Discrete-Time Bidirectional Ring of Neurons with Delay, Proceedings of International Joint Conference on Neural Networks, Atlanta, Georgia, USA, June 14-19, 2009, pp.1539-1546. E. Kaslik, St. Balint - Complex and chaotic dynamics in a discrete-time-delayed Hopfield neural network with ring architecture, acceptata pentru publicare in Neural Networks, (2009), doi:10.1016/j.neunet.2009.03.009

D. Zaharie - Influence of crossover on the behavior of Differential Evolution Algorithms, Applied Soft Computing 9 (2009) 1126–1138

D. Zaharie - Large Scale optimization with cooperative coevolution, Doctoral Intensive Summer School on Evolutionary Computing in Optimization and Data Mining, iunie 2009b, Iasi, Romania (http://thor.info.uaic.ro/~summerschool/program.php)

F. Zamfirache, M. Frincu, C. Zavoianu - Nature Inspired Metaheuristics for Grid Scheduling, Zilele Academice Timisene, mai 2009.

F. Zamfirache – Robustness Analysis of Ant-based Scheduling in Heterogeneous Computing Environments, acceptata pentru prezentare la NCA workshop, SYNASC’09, Timisoara, Sept. 26-29, 2009. Gabriel Istrate. On the dynamics of Social Balance on general networks (with an application to XOR-SAT). Fundamenta Informaticae, 91 (2), pp. 341-356, 2009a.

Allon Percus, Gabriel Istrate, Bruno Tavares Gonçalves, Robert Z. Sumi, Stefan Boettcher. The Peculiar Phase Structure of Random Graph Bisection. Journal of Mathematical Physics, 49 (12), p. 125219, 2008. Gabriel Istrate. Geometric Properties of Satisfying Assignments of random ε-1-in-k SAT. International Journal of Computer Mathematics, 2009b. Gabriel Istrate, Madhav V. Marathe, S.S. Ravi. Adversarial Scheduling in Evolutionary Game Dynamics, Computational and Mathematical Organization Theory, 2009c. G. Istrate, Robert Z. Sumi. Computation and coordination in Boolean markets, Technical report, 2009d. G. Istrate. Incorporating contagion into models of network formation, submitted to Journal of Economic Behavior and Organization, 2009e. A. Bautu, H. Luchian, Further Investigations on Using the Tree Bond-based Representation for Ising Spin Glasses, to appear in Proceedings of the Natural Computing and Applications Workshop, 11th International Symposium on Symbolic and Numeric Algorithms Scientific Computing (SYNASC’09), Timisoara, Sept. 26-29, 2009a. A. Bautu, E. Bautu. Energy Minimization of Point Charges on a Sphere with Particle Swarms, Romanian Journal of Physics - Volume 54, Numbers 1-2, pp. 29-36, 2009b. A. Bautu. A Study of Topology Influence on Particle Swarm Optimization for Thomson Problem. Proceedings of the 9th Balkan Conference on Operational Research (BALCOR 2009), Constanta, 2-6 Sept. 2009c, ISBN 973-86979-9-9. E. Bautu, A. Bautu, H. Luchian. Stock Market Trend Forecasting with GEP Ensembles, to appear in Proceedings of the Natural Computing and Applications Workshop, 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC’09), Timisoara, Sept. 26-29, 2009d. E. Bautu, A. Barbulescu. Forecasting Financial Time Series with a Hybrid ARIMA-GEP Approach. Proceedings of the 9th Balkan Conference on Operational Research (BALCOR 2009), Constanta, 2-6 Sept. 2009e, ISBN 973-86979-9-9. A. Barbulescu, E. Bautu. Mathematical Models of Climate Evolution in Dobrudja, in Theoretical and Applied Climatology, Springer Wien, 2009, http://www.springerlink.com/content/b664275mn3j4l627/. M. Breaban, H. Luchian. Unsupervised Feature Weighting with Multi Niche Crowding Genetic Algorithms. Proceedings of the 11th Annual conference on Genetic and evolutionary computation (GECCO 2009), NY, USA, ACM, 1163-1170, 2009a. M. Breaban, L. Alboaie, H. Luchian. Guiding Users within Trust Networks Using Swarm Algorithms. Proceedings of IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, IEEE, 1770-1777, 2009b.

Braun, T. D., Siegel, H. J., Beck, N., Boloni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D., and Freund, R. F., A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6):810837, 2001.

R. Tyson Browning. Use of dependency structure matrices for product development cycle time reduction. In Proceedings of the Fifth ISPE International Conference on Concurrent Engineering: Research and Applications, pages 89–96, Tokyo, Japan, July 15–17 1998.

Ying-Ping Chen and David E. Goldberg. Convergence time for the linkage learning genetic algorithm. Evolutionary Computation, 13(3):279–302, 2005. URL http://dx.doi.org/10.1162/1063656054794806.

Edwin D. de Jong. Representation Development from Pareto-Coevolution. In Erick Cantú-Paz et al., editor, GECCO ’03:, pages 262–273. Springer, LNCS, vol. 2723, July 2003.

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.

G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. IEEE-EC, 3(4):287, November 1999.

Georges Harik and D. Goldberg. Learning Linkage. Morgan Kaufmann, San Mateo, CA, 1997.

John H. Holland. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation, 8(4):373–391, 2000.

David Iclanzan, D. Dumitrescu, and Béat Hirsbrunner. Correlation guided model building. In GECCO ’09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 421–428, New York, NY, USA, 8-12 July 2009. ACM. ISBN 978-1-60558-325-9. http://doi.acm.org/10.1145/1569901.1569960.

M. Jackson and A. Watts "The evolution of social and economic networks", Journal of Economic Theory, Volume 106, Number 2, October 2002 , pp. 265-295(31).

Fernando G. Lobo, Kalyanmoy Deb, David E. Goldberg, Georges R. Harik, and Liwei Wang. Compressed introns in a linkage learning genetic algorithm. In John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 551–558, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.

Heinz Muhlenbein and Gerhard PaaB. From recombination of genes to the estimation of distributions: I. binary parameters. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, Parallel Problem Solving From Nature-PPSN IV (4th PPSN’96), volume 1141 of Lecture Notes in Computer Science (LNCS) September 1996, pages 178–187. Springer-Verlag, Berlin, 96.

M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer Verlag, 2005.

Martin Pelikan. Bayesian optimization algorithm: from single level to hierarchy. PhD thesis, 2002. Adviser-David E. Goldberg.

Martin Pelikan, David E. Goldberg, and Erick Cantú-Paz. BOA: The Bayesian optimization algorithm. In Wolfgang Banzhaf et al., editor, GECCO ’99, volume I, pages 525–532, Orlando, FL, 13-17 July 1999. Morgan Kaufmann Publishers, San Fransisco, CA. ISBN 1-55860-611-4.

H. Peyton Young "Individual strategy and social structure: An evolutionary theory of institutions", Princeton University Press 1998.

Reza Rastegar and Arash Hariri. A step forward in studying the compact genetic algorithm. Evolutionary Computation, 14(3):277–289, 2006. URL http://dx.doi.org/10.1162/evco.2006.14.3.277.

Kumara Sastry and David E. Goldberg. On extended compact genetic algorithm. In Darrell Whitley, editor, Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, pages 352–359, Las Vegas, Nevada, USA, 8 July 2000.

Kumara Sastry and David E. Goldberg. Probabilistic model building and competent genetic programming. In Rick L. Riolo and Bill Worzel, editors, Genetic Programming Theory and Practice, chapter 13, pages 205–220. Kluwer, 2003.

Dirk Thierens and David E. Goldberg. Mixing in genetic algorithms. In Stephanie Forrest, editor, Proc. of the 5th International Conference on Genetic Algorithms, pages 38–47, San Francisco, CA, USA, 1993. Morgan Kaufmann. ISBN 1-55860-299-2.

Tian-Li Yu and David E. Goldberg. Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression. In GECCO ’06: pages 1385–1392, NY, USA, 2006. ACM Press. ISBN 1-59593-186-4. http://doi.acm.org/10.1145/1143997.1144210.