RAPORTUL STIINTIFIC SI TEHNIC

FAZA DE EXECUTIE NR. 2

CU TITLUL Schitarea unei noi paradigme

RAPORTUL STIINTIFIC SI TEHNIC

1.1. Cuprins

1.2. Obiective generale.............................................................................. 4

1.3. Obiectivele fazei de executie............................................................... 4

1.4. Rezumatul fazei.................................................................................. 5

1.5. Descriere stiintifica si tehnica............................................................. 7

1.5.1 Argumente pentru schimbarea de paradigma in modelarea complexitatii –

Schita noii paradigme.................................................................................... 7

1.5.1.1. Noi concepte si modele ale complexitatii propuse si dezvoltate de echipa proiectului in faza raportata............................................................................

7

1.5.1.2.Complexitatea invatarii traiectoriei sistemelor dinamice prin exemple.......

7

1.5.1.3. Modele neconventionale in probleme complexe de mari dimensiuni. Invatare si cautare locala...............................................................................

8

1.5.1.4. Modelul adversarial de activare in dinamica sistemelor complexe.............

8

1.5.1.5. Identificarea impactului topologiei spatiului solutiilor asupra complexitatii temporale a algoritmilor de cautare.................................................................

8

1.5.1.6. Analiza datelor complexe. Noi modele de masini cu suport vectorial......... 9

1.5.1.7. Noi modele evolutive de cautare si optimizare. Modele distribuite spatial.. 9

1.5.2. Elaborarea de modele ale dinamicii sistemelor complexe. Studiul aspectului

temporal......................................................................................................

9

1.5.2.1. Generalizarea unor modele din fizica statistica in automate celulare si in retele complexe............................................................................................

9

1.5.2.2. Dinamica populatiilor in modele distribuite spatial.................................. 10

1.5.2.3. Comportament haotic in retele neuronale……………………………………………………

10

1.5.2.4. Aspecte temporale ale dinamicii balantei sociale....................................

11

1.5.2.5. Modelul dinamicii bazat pe inteligenta roiurilor (swarm intelligence)......... 13

1.5.2.6. Analiza statistica a dinamicii populatiei corespunzatoare unei clase de algoritmi evolutivi………………………………………………………………………………………………………..

13

1.5.3. Identificarea de probleme practice semnificative de mare

complexitate. Studii de caz.........................................................................

15

1.5.3.1. Probleme neseparabile cu numar foarte mare de variabile.......................

15

1.5.3.2. Cautare/optimizare competitiva pentru probleme complexe. Studii de caz..

15

1.5.3.3. Optimizare multimodala evolutiva. Studii de caz....................................

15

1.5.3.4. Modele distribuite spatial. Experimente numerice si studii de caz............. 16

1.5.3.5. Identificarea topologiei spatiului de cautare in probleme complexe…………..

16

1.5.3.6. Metaeuristici hibride. Experimente numerice in cazul optimizarii functiilor cu numar mare de variabile............................................................................

17

1.5.3.7. Clasificare si clustering. Studii de caz................................................... 18

1.5.3.8. Identificarea starii de energie minima in sistemele de tip „Ising Spin Glass”...........................................................................................................

18

1.5.3.9. Modelarea seriilor de timp. Studii de caz............................................... 19

1.5.3.10. Modelarea unor fenomene biologice si analiza datelor medicale.............. 19

1.5.3.11. Utilizarea retelelor neuronale cu comportament haotic in criptografie. Studiu de caz................................................................................................

20

1.5.3.12. Clasificarea nesupervizata a documentelor electronice. Studiu de caz...... 21

1.6. Anexe................................................................................................... 25

1.7. Concluzii............................................................................................... 25

1.8. Referinte............................................................................................... 26

1.8.1. Lucrari publicate in cadrul fazei de catre echipa proiectului……………………....... 26 1.8.2. Alte referinte……………………………………………………………………………………………………… 29

1.2 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

1.3. Obiectivele fazei de executie

Aceasta faza de executie are ca obiectiv principal schitarea unei noi paradigme si poate fi asociata cu obiectivele generale Ob3, Ob4, Ob5 si Ob6:

• Studiul invatarii si auto-organizarii in sisteme complexe si in sisteme complexe dinamice

• Dezvoltarea unui cadru general, flexibil si usor de utilizat pentru selectia si aplicarea inteligenta a MIN problemelor reale

• Proiectarea de noi modele evolutive pentru rezolvarea problemelor complexe • Dezvoltarea studiilor de caz

Realizarea acestui obiectiv general al fazei a fost urmarita prin urmatoarele activitati:

• Argumente pentru schimbarea de paradigma in modelarea complexitatii – Schita noii paradigme

• Identificarea de probleme practice semnificative de mare complexitate

• Studiul aspectului temporal

• Elaborarea de modele ale dinamicii sistemelor complexe

• Studii de caz

1.4. Rezumatul fazei

A. In cadrul acestei etape echipa proiectului a realizat- conform obiectivelor fazei 2- studii teoretice si experimente numerice privind o noua abordare a complexitatii. Aceste studii au vizat in principal aspecte ale comportarii sistemelor dinamice vazute atat ca modele teoretice dar si ca modele computationale asociate unor probleme complexe precum si aspecte legate de probleme practice a caror rezolvare ridica dificultati metodelor traditionale.

In acest context au fost obtinute rezultate privind:

• Inferenta prin invatare din exemple a unor limbaje de tip Lindenmayer asociate comportarii unui sistem dinamic.

• Utilizarea mecanismelor de invatare nesupervizata utilizate in retelele neuronale

cu auto-organizare pentru identificarea corelatiilor dintre variabilele ce apar in probleme de optimizare cu numar mare de variabile.

• Convergenta algoritmilor de cautare locala si complexitatea algoritmilor evolutivi.

• Analiza topologiei spatiului solutiilor in cazul problemelor de optimizare. In cazul

problemelor de optimizare combinatoriala a fost analizat impactul topologiei asupra complexitatii temporale a algoritmilor de cautare iar in cazul problemelor de optimizare continue au fost identificate strategii de localizare a optimelor multiple.

• Caracterul asincron al activarii in sisteme complexe si al proceselor de cautare

evolutive. Au fost puse in evidenta atat comportamente interesante din punct de vedere matematic cat si avantaje din punct de vedere computational.

• Modele de cautare evolutiva bazate pe distribuirea spatiala a elementelor

populatiei si procese de colaborare intre subpopulatii. Au fost identificate diferite tipuri de comportament si intervale de valori pentru parametrii de control care conduc la un anumit comportament.

• Dinamica populatiei in algoritmii de tip „Differential Evolution” si alti algoritmi

aleatori inruditi. A fost analizat impactul diferitilor operatori de incrucisare asupra comportarii algoritmilor de acest tip si au fost obtinute rezultate teoretice care confirma observatiile experimentale.

• Comportamentul haotic al unor retele neuronale cu dinamica discreta constituite

din neuroni cu intarziere; a fost analizat atat cazul retelelor constituite din doi neuroni cat si a celor constituite din n neuroni interconectati in conformitate cu o topologie de tip inel.

• Modelarea retelei de reglare corespunzatoare procesului de coagulare a sangelui.

Spre deosebire de modelele studiate pana in prezent care tratau separat calea intrinseca si cea extrinseca de reglare a procesului de coagulare, modelul propus trateaza simultan cele doia cai iar rezultatele numerice obtinute sunt in concordanta cu rezultatele experimentale.

B. Au fost efectuate studii de caz privind:

• Rezolvarea problemelor de optimizare cu numar mare de variabile neseparabile. In acest context a fost analizata eficacitatea atat a strategiilor de descoperire a

corelatiilor intre variabile cat si a unor variante hibride care implica algoritmi de tip Harmony Search.

• Rezolvarea problemelor de optimizare cu numar mare de optime locale. In acest sens au fost propuse imbunatatiri ale algoritmilor de tip „cromodinamica genetica”.

• Dificultatile ridicate de analiza datelor complexe. Problemele vizate au fost: clasificare, grupare nesupervizata, predictie in serii de timp dinamice, extragere de reguli din date. In acest sens au fost investigate noi modele de masini cu suport vectorial, a fost propusa o strategie evolutiva de identificare a punctelor de schimbare a modelului in seriile temporale, a fost propusa o metoda de pre-procesare pentru clustering bazata pe o tehnica de tip „particle swarm optimization” si au fost analizate particularitatile algoritmilor evolutivi de optimizare multicriteriala pentru extragerea regulilor (clasificare, predictie, asociere) din date.

• Identificarea starii de energie minima in sistemele de spini magnetici. Studiul de caz a condus la dezvoltarea unei noi modalitati de reprezentare si a unor noi operatori genetici a caror aplicare a condus la rezultate competitive in raport cu alte metode.

• Utilizarea retelelor neuronale cu comportare haotica in criptografie, in particular in criptarea imaginilor digitale.

• Problemele ce intervin in proiectarea unui sistem de clasificare a colectiilor voluminoase de documente electronice. Au fost efectuate teste pe colectii de date utilizand un algoritm de clasificare nesupervizata de tip „Adaptive Resonance Theory”.

C. Au fost identificate problemele deschise si directiile de cercetare pentru faza urmatoare. D. Pe baza rezultatelor obtinute s-au publicat mai mult de 20 de articole ISI in jurnale internationale si in lucrarile unor importante conferinte internationale si un capitol de carte. Rezultatele raportate au fost bine primite de comunitatea stiintifica. Alte lucrari au fost acceptate pentru publicare in reviste internationale sau sunt in curs de evaluare.

Au fost sustinute trei teze de doctorat si au fost elaborate sapte lucrari de dizertatie corelate cu tematica proiectului. Studentii doctoranzi au facut 14 prezentari la doua scoli de vara cu tematici corelate cu tematica proiectului (una in tara si una in strainatate). Membrii echipei au sustinut conferinte invitate in cadrul unor scoli de vara sau conferinte internationale.

E. Consortiul s-a consolidat prin organizarea cu participarea efectiva a tuturor partenerilor a doua manifestari stiintifice: Scoala de vara doctorala „Doctoral Intensive Summer School on Meta-Heuristics in Optimisation and in Intelligent Data Analysis” organizata la Iasi in iunie 2008 [http://thor.info.uaic.ro/ ~summerschool/] si workshopul „Natural Computing and Applications” organizat la Timisoara in septembrie 2008 [http://synasc08.info.uvt.ro/nca]

1.5. Descrierea stiintifica si tehnica

In cadrul proiectului am realizat studiul aspectelor temporale ale dinamicii sistemelor complexe centrat pe urmatoarele directii de cercetare:

1.5.1. Argumente pentru schimbarea de paradigma in modelarea complexitatii –

Schita noii paradigme.

1.5.1.1 Noi concepte si modele ale complexitatii propuse si dezvoltate de

echipa proiectului in faza raportata

Rezultatele recente din literatura de specialitate au aratat ca exista metode eficiente pentru rezolvarea problemelor complexe cu un numar foarte mare de variabile, chiar si in medii influentate de zgomot, dar care sunt separabile (Sastry et al., 2007). Insa abordarea problemelor complexe non-separabile cu sute de mii sau milioane de variabile ar necesita terabytes de memorie (Yu et al., 2007; Pelikan et al., 2000). De exemplu, metodele ce estimeaza distributiile solutiilor si construiesc modele ajutatoare necesita foarte multe evaluari de solutii si populatii foarte mari pentru a putea garanta corectitudinea solutiilor. Abordarea problemelor complexe non-separabile, cu milioane de variabile se dovedeste astfel a fi o provocare pentru dezvoltarea unor noi tehnici de optimizare. Aceste tehnici trebuie sa fie foarte eficiente in ceea ce priveste memoria necesara si constructia/detectarea modulelor care trebuie combinate. In acest sens s-a propus incorporarea de technici de invatare automate supervizate si nesupervizate bazate pe retele neuronale artificiale (ANN) in procesul de cautare evolutiva, pentru a putea detecta variabile puternic interdependente (Iclanzan, Dumitrescu, 2008a). Costul includerii acestor technici e relativ mic, complexitatea in termeni de stocare (memorie) si constructia modelului fiind maxim liniara in numarul de variabile ale problemei. Optimizarea evolutiva a proceselor care apar in cadrul unor sisteme complexe a fost abordata pornind de la principiile si dinamicile modelului Ising. Au fost studiate atat retelele complexe, precum si retelele de tip Scale-Free, dezvoltate de Albert Barabasi. 1.5.1.2. Complexitatea Invatarii Traiectoriei Sistemelor Dinamice prin exemple.

Problema invatarii dinamicii unui sistem complex este una din problemele de maxima importanta in studiul/predictia acestor sisteme. Un model acceptat in teoria invatarii computationale este modelul invatarii prin exemple. Prin urmare in (Istrate 2008b) am considerat problema invatarii prin exemple a traiectoriilor unui sistem dinamic. In general aceasta problema nu poate fi rezolvata algoritmic, chiar daca ne limitam la cazul Dinamicii Simbolice, pentru care metodele discrete din informatica sunt aplicabile. Intr-adevar exista sisteme dinamice pentru care limbajul asociat multimii traiectoriilor nu poate fi recunoscut de o Masina Turing. Pentru cele mai putin complexe tipuri de sisteme dinamice, acelea pentru care limbajul asociat este regulat, problema invatarii este rezolvabila prin rezultatele clasice ale lui Angluin. Clasa acestor sisteme dinamice este relativ limitata si este descrisa in literatura de specialitate. In (Istrate 2008b) studiem problema inferentei unei clase de limbaje mai largi decat cea a limbajelor regulate: familia limbajelor Lindenmayer. Relevanta acestei familii pentru studiul sistemelor complexe provine din faptul ca o serie de operatii fizice asupra

sistemelor dinamice (de exemplu operatia de renormalizare, operatori de compozitie,etc)

conduc in mod natural la sisteme Lindenmayer. Rezultatul din (Istrate 2008b) arata faptul ca familia gramaticilor de tip Lindenmayer poate fi invatata din exemple

structurate. Acest tip de exemple (si rezultatul nostru) au o relevanta fizica evidenta: in general exista mai multe gramatici care genereaza acelasi limbaj. Invatarea din exemple structurate revine la invatarea mecanismelor care conduc la limbaje de tip Lindenmayer, si nu doar a limbajelor asociate unui sistem dinamic. 1.5.1.3. Modele neconventionale in probleme complexe de mari dimensiuni

Invatare si cautare locala

Cadrul de cautare locala bazata pe modele propus in (Iclanzan, Dumitrescu, 2007) a fost mai departe extins in (Iclanzan, Dumitrescu, 2008c). Acesta include un mecanism de invatare si constructie de modele online. Harti auto-organizatorice (SOM - retele Kohonen), bazate pe paradigma invatarii competitive sunt instruite online pentru a acumula experienta de cautare. Aceasta experienta este exploatata odata cu convergenta retelei: hartile SOM au capabilitatea sa invete automat topologia unui spatiu sau a unei multimi prezentata la intrarea retelei. Legatura dintre variabile si structura problemei poate fi astfel detectata. Metoda propusa, Online Model Based Local-Search (OMBLS), foloseste o structura de vecinatate adaptiva (dinamica), care faciliteaza operatiile direct pe module. Marele avantaj al invatarii online (in plus fata de cerintele mici de memorie), e faptul ca invatarea e un proces automat. Astfel, nu este nevoie de cautarea si evaluarea repetata a unui model, ca in metodele clasice bazate pe populatii. 1.5.1.4. Modelul adversarial de activare in dinamica sistemelor complexe

Activarea asincrona ocupa un rol important in determinarea proprietatilor dinamice ale modelelor matematice (sau computationale de tip multiagent) ale dinamicii sociale, influentand in mod decisiv convergenta/timpul de convergenta al acestor dinamici. In lucrarea (Istrate 2008a) propunem modelul adversarial de activare drept o varianta de analiza a proprietatilor unui sistem multiagent (matematic sau computational). Scopul acestei analize este sa decupleze specificarea ordinii de activare de specificarea celorlaltor proprietati ale sistemului, urmarind o intelegere a cauzelor/factorilor care induc un anumit rezultat. Intentia este de a mari robustetea acestor rezultate, contribuind la verificarea si validarea acestui tip de modele. In (Istrate 2008a) prezentam filosofia acestei metode, impreuna cu un model matematic simplu, construit intr-o maniera bottom-up, pentru exemplificare. In (Istrate et al. 2008) analizam un model mai complicat, bazat pe o dinamica aleatoare, intalnit in literatura din domeniul Inteligentei artificiale, precum si in cea din domeniul Lanturilor Markov cu amestecare rapida. Scopul acestui rezultat este sa arate ca modelul adversarial de activare poate conduce la dinamici matematic interesante si netriviale. In sfarsit, in (Istrate 2008c) studiem intr-un cadru adversarial celebrul model al segregarii definit de Thomas Schelling. Concluzia acestei analize este ca pentru validitatea rezultatului din cazul activarii aleatoare determinanta este capacitatea activatorului de a alege urmatorul nod activat bazat pe starea sistemului.

1.5.1.5. Identificarea impactului topologiei spatiului solutiilor asupra

complexitatii temporale a algoritmilor de cautare.

O directie de cercetare subsumata acestei directii (Percus, Istrate et al 2008), (Istrate 2008c) priveste modul in care structura spatiului solutiilor unor probleme combinatoriale

este corelata cu complexitatea temporala a algoritmilor de rezolvare. O paradigma din domeniul Mecanicii Statistice este asa-numita metoda a replicilor. Una din problemele clasice care a rezistat pana acum aplicarii acestei metode este problema bisectiei unui graf aleator, mai precis cazul grafurilor ”rare” (cu numar liniar de muchii). In (Percus, Istrate et al. 2008) am obtinut o noua margine superioara pentru largimea de bisectie a unui graf aleator prin definirea si analiza unui algoritm numit Core Peeling. In lucrare mai prezentam evidenta experimentala ca structura spatiului fazelor problemei este descrisa de asa numita presupunere de simetrie a replicilor in jurul tranzitiei de faza. Acest lucru este corelat cu faptul ca problema bisectiei grafurilor aleatoare este rezolvabila relativ

usor cu ajutorul algoritmilor de tipul optimizare extremala si constituie un prim exemplu de problema in care am avea simetrie a replicilor dincolo de punctul in care costul devine pozitiv. De asemenea, in (Istrate 2008c) studiem o alta problema NP-completa care din punctul de vedere al complexitatii in medie este usor de rezolvat: problema 1-in-k satisfiabilitatii. Tranzitia de faza a acestei probleme este cunoscuta riguros si este in aceeasi clasa cu a problemei 2-satisfiabilitatii (pentru care simetria replicilor este demonstrata riguros). Un indiciu al exactitatii simetriei replicilor pentru 1-in-k satisfiabilitate ar fi demonstratia faptului ca multimea solutiilor este alcatuita dintr-un singur cluster. In (Istrate 2008c) demonstram o varianta a acestui rezultat: faptul ca multimea solutiilor problemei 1-in-k satisfiabilitatii nu contine „gauri”. 1.5.1.6. Analiza datelor complexe. Noi modele de masini cu suport vectorial

In cadrul abordarii evolutive asupra masinilor cu suport vectorial, calea de invatare ramane neschimbata, dar coeficientii functiei de decizie, creata din clasica privire geometrica a metodei canonice, pot fi acum evoluati in raport cu obiectivele de optimizare privind acuratetea si generalizarea (Stoean et al, 2008a). Contrar tehnicii canonice, abordarea evolutiva poate in orice moment sa obtina in mod explicit coeficientii functiei de decizie, fara alte constrangeri ulterioare. Mai mult, pentru a converge, metoda evolutiva nu necesita proprietati de (semi-)definire pozitiva pentru kernele in cadrul invatarii neliniare (Stoean et al, 2008b). 1.5.1.7. Noi modele evolutive de cautare si optimizare. Modele distribuite spatial

O alta tehnica evolutiva dezvoltata a fost testata pe o serie de functii reale unimodale si multimodale dificile, cu foarte multe optime locale apropiate unele de altele (Chira et al, 2008). Exista multe probleme reale care pot fi modelate ca astfel de functii cu multe optime locale, astfel ca rezultatele obtinute sunt extrem de relevante pentru cercetarea noastra viitoare in care vor fi abordate in principal probleme complexe reale. Tehnica propusa se bazeaza pe o o distributie spatiala a indivizilor din populatie si pe o aplicare asincrona a operatorilor de cautare. O alta caracteristica este coexistenta a trei subpopulatii care au roluri diferite in procesul de cautare – realizarea unei cautari globale, realizarea unei cautari locale, si mentinerea unei interactiuni, inteleasa ca schimb de material genetic, intre acesti indivizi diferiti. Mai mult decat atat, indivizii se comporta ca niste agenti inteligenti care sunt capabili sa decida in ceea ce priveste perechea aleasa pentru recombinare. Aceasta se realizeaza printr-un schimb de informatii intre indivizi (Gog et al, 2008a).

1.5.2. Elaborarea de modele ale dinamicii sistemelor complexe. Studiul

aspectului temporal

1.5.2.1. Generalizarea unor modele din fizica statistica in automate celulare si in

retele complexe

Modelul Ising este unul din pilonii mecanicii statistice. El presupune existenta unui grid (latice). Fiecare celula a gridului poate avea doar 2 valori (rosu sau alb, 0 sau 1, + sau -). Celulele vecine tind sa aiba aceleasi valori (datorita unor preferinte energetice). Precum un sistem cu spini magnetici +/-, modelul Ising este un model pentru magnetism sau pentru miscarea moleculelor unui lichid supus unui stimul extern. Se pot observa

anumite tranzitii: regiunile „dense” ocupate de lichid sunt inconjurate de regiunile „diluate” ocupate de gaz. Modelul Ising clasic poate fi extins prin atribuirea a mai mult de 2 stari unui singur spin (modelul Potts), prin modificarea laticei (triunghiulara, hexagonala), prin introducerea unor sublatice (modelul decorat). In cazul unei retele complexe fiecare nod al retelei „cunoaste” toate celelalte noduri ale retelei. De aceea se spune ca avem de-a face cu o retea completa de „cunostinte” (Diosan, Dumitrescu, 2008). In cazul retelelor de tip Scale-Free, este prezent un anumit numar de noduri care au foarte multe legaturi, in timp ce restul nodurilor au foarte putine legaturi, dar minim una. In cadrul retelelor de tip Scale-Free întâlnim un fel de nuclee (sau hub-uri) în jurul cărora se concentrează restul nodurilor. În cadrul unor astfel de reŃele au fost studiate procesele de formare a coaliŃiilor şi relaŃiile lor cu parametrii reŃelei (Diosan, Dumitrescu, 2008). 1.5.2.2. Dinamica populatiilor in modele distribuite spatial

A fost propus si studiat (Gog et al, 2009) un nou model computational care se bazeaza pe o distributie spatiala a elementelor de cautare si pe aplicarea asincrona a operatorilor de evolutie. S-a studiat dinamica sistemului constand din mai multe subpopulatii cu roluri diferite in procesul de cautare. Elementele de cautare au fost concepute ca agenti inteligenti inzestrati cu un grad de autonomie. Efectele comunicarii intre subpopulatii asupra distribuirii elementelor in cazul existentei a trei subpopulatii caracterizate prin strategii diferite de selectare a perechii in procesul de recombinare au fost studiate experimental pentru diferite tipuri de recombinare si teoretic prin dezvoltarea unui model probabilist. Modelul probabilist se bazeaza pe o strategie de asignare a elementelor noi generate unei subpopulatii sau alteia pe baza unei probabilitati de dominare. Estimand valori ale probabilitatilor de acceptare a elementelor nou generate pornind de la rezultate experimentale obtinute pe un set de functii test s-a putut reproduce prin intermediul modelului teoretic comportamentul observat experimental. Modelul teoretic permite identificarea valorilor probabilitatii de dominare pentru care una dintre subpopulatii preia controlul asupra intregii populatii sau pentru care toate trei sau doua dintre subpopulatii ajung in stare de echilibru. In lucrarea (Gog et al, 2008b) studiul este orientat inspre cazul a trei subpopulatii urmarindu-se in principal efectul probabilitatii de dominare asupra dimensiunii subpopulatiilor fara sa se puna accentul pe eficacitatea operatorilor de recombinare si mutatie. In lucrarea (Gog et al, 2008c) s-a continuat acest studiu punandu-se de aceasta data accentul pe utilizarea unor operatori care sa permita rezolvarea unor probleme dificile de optimizare. In acest context s-a analizat dinamica pentru cazul a doua subpopulatii bazate pe variante de algoritmi de tip „differential evolution” cu abilitati diferite de explorare/exploatare. Pe langa studiul experimental, a fost identificat si un model probabilist care modeleaza dinamica dimensiunilor subpopulatiilor. Pe langa varianta bazata pe o probabilitate de dominare fixata aprioric si care a fost studiata in lucrarea anterioara a fost analizata si varianta in care probabilitatea de dominare depinde de dimensiunea curenta a subpopulatiei, fiind in felul variabila in timp. Intrucat s-a observat experimental ca se obtin rezultate mai bune in regiunea de echilibru in raport cu dimensiunile subpopulatiilor, au fost identificate conditii suficiente pentru atingerea acestui echilibru.

1.5.2.3. Comportament haotic in retele neuronale

Retelele neuronale recurente caracterizate printr-o conectivitate arbitrara a unitatilor de procesare (neuroni) prezinta un comportament dinamic care poate fi descris atat in timp

continuu (prin ecuatii diferentiale) cat si la momente discrete de timp (ecuatii cu diferente). Marea majoritate a rezultatelor calitative privind comportarea retelelor neuronale recurente au fost obtinute in cazul continuu insa in ultimii ani a crescut semnificativ interesul si pentru variantele discrete. Exista cel putin doua argumente care motiveaza aceasta crestere a interesului. Pe de o parte, simularile retelelor neuronale utilizate in rezolvarea unor probleme concrete (optimizare, prelucrare imagini etc) se bazeaza pe discretizari ale modelelor continue, iar pe de alta parte dinamica sistemelor discrete este mult mai bogata in tipuri de comportament decat cea a sistemelor descrise in timp continuu. De exemplu ecuatii cu diferente obtinute prin discretizarea unor ecuatii diferentiale de ordinul intai pot avea comportament haotic pe cand in cazul ecuatiilor diferentiale un astfel de comportament poate fi pus in evidenta doar in cazul ordinelor mari. Exista diferite modalitati de a induce un comportament haotic in retelele neuronale: utilizarea unui semnal haotic de intrare, utilizarea unui functii de activare neuronala care are comportament haotic sau introducerea unor intarzieri. In aceasta etapa a proiectului s-a investigat impactul introducerii unor intarzieri in cazul unei retele constituite din doi neuroni interconectati. Considerand ca intarzierile satisfac proprietatea ca suma auto-intazierilor este egala cu suma intarzierilor semnalelor provenite de la celalalt neuron s-a identificat domeniul de stabilitate al solutiei nule si tipurile de bifurcatie care apar pe frontiera in functie de valorile unor parametri caracteristici. Parametri caracteristici luati in considerare sunt corelati cu ponderile conexiunilor si cu pantele in origine ale functiilor de activare. Pe masura ce parametrii caracteristici se indeparteaza de domeniul de stabilitate dinamica retelei devine din ce in ce mai complexa ajungandu-se la un comportament haotic. Trecerea de la stabilitate catre haos se realizeaza prin stadii intermediare caracterizate prin solutii periodice si atractori stranii. Toate aceste tipuri de comportament au fost puse in evidenta prin simulari numerice. Rezultatele au fost publicate in lucrarile (Kaslik, Balint 2008a) si (Kaslik, Balint 2008b). Rezultatele cele mai recente obtinute in aceasta directie se refera la studiul unui 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 dar adaptata pentru cazul a p neuroni s-a putut identifica domeniul de stabilitate a solutiei nule 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. Aceste rezultate sunt prezentate in lucrarea (Kaslik, Balint, 2008c), submisa pentru publicare (in curs de evaluare).

1.5.2.4. Aspecte temporale ale dinamicii balantei sociale. In (Istrate 2009) studiem un model al dinamicii sociale, bazat pe teoria balantei sociale a lui Heider, introdus in literatura din domeniul Fizicii Statistice de catre Antal, Krapivsky si Redner. Rezultatul nostru leaga dinamica studiata de Antal, Krapivsky si Redner de o generalizare la hipergrafuri a unui model din teoria sistemelor interactive de particule, modelul mersurilor aleatoare cu coalescenta. Dupa cunostinta noastra definirea unui model de particule interactive pe hipergrafuri este o premiera in literatura de specialitate. Spre deosebire de cazul tratat de acesti autori (topologia corespunzand unui graf complet) in cazul general determinarea starilor recurente ale sistemului este mai

complicata. In lucrarea noastra dam un criteriu necesar si suficient si un algoritm polinomial pentru testarea recurentei unei stari a sistemului. De asemenea am studiat dimensiunea temporala a convergentei dinamicii, cu urmatoarele rezultate:

• Pentru cea mai simpla familie nontriviala de grafuri (ciclul triadic, reprezentat in cazul cu 18 varfuri in Figura 1) timpul de convergenta este liniar.

• In general timpul de convergenta depinde de proprietatile unui hipergraf dual grafului original. Pentru graful din Figura 1 ilustram constructia acestui hipergraf dual in Figura 2 (in care caz e chiar un graf)

• In cazul in care hipergraful dual este chiar un graf, putem masura timpul de convergenta utilizand un parametru structural al topologiei grafului dual, asa numita constanta Cheeger.

Figura 1: ciclul triadic Fig 2: dualul ciclului triadic

• In cazul general situatia este mai delicata, iar determinarea timpului de

convergenta este o problema nerezolvata. Pe de alta parte rezultatul tehnic cel mai dificil al lucrarii priveste caracterizarea starilor recurente pentru dinamica, in cazul particular in care hipergraful dual nu contine muchii (hipermuchii cu doua varfuri). In acest caz am aratat faptul ca determinarea recurentei unei stari se poate face rezolvand (in timp polinomial) un sistem liniar de ecuatii booleene).

Rezultatele obtinute in (Istrate 2009) au o aplicatie neasteptata la determinarea complexitatii algoritmilor de cautare: aceste rezultate ofera un exemplu de analiza

riguroasa a timpului de convergenta a unui algoritm natural de cautare locala (algoritmul bazat pe mers aleator pentru asa numita problema XOR-SAT) folosind unii parametri care caracterizeaza structura formulei de intrare. Acest lucru sugereaza faptul ca metodele matematice folosite in studiul sistemelor interactive de particule pe grafuri finite pot fi folosite pentru analiza matematic riguroasa a algoritmilor de cautare locala, un lucru potential folositor pentru alte clase de probleme si algoritmi de cautare locala. Algorithm RandomWalkSat(F):

INPUT: XOR-SAT instance F. Start with an arbitrary assignment U. while (there exists some unsatisfied clause) pick a random unsatisfied clause C change the value of a random variable of C in U RETURN assignment U

Fig 3. Algoritmul bazat pe mers aleator pentru problema XOR-SAT

1.5.2.5. Modelul dinamicii bazat pe inteligenta roiurilor (swarm intelligence)

O metoda aparuta relativ recent se inspira din comportamentul roiurilor de mari dimensiuni. Studiile efectuate asupra diferitelor forme de organizare sociala in lumea animala (roiuri de insecte, bancuri de pesti etc.) au evidentiat ca asemenea tipuri de grupuri obtin succese remarcabile in atingerea scopurilor urmarite, indiferent daca este vorba despre identificarea traseului optim spre anumite locatii, evitarea pradatorilor etc. Remarcabil este faptul ca, desi grupurile sunt de mari dimensiuni, comportamentul unitar rezulta exclusiv din interactiunile intre vecini.

Succesul acestui tip de comportament a inspirat elaborarea unei metode de optimizare nesupervizata, numita Particle Swarm Optimization (PSO). Desi are unele puncte comune cu metode consacrate, precum calculul evolutiv (in principal utilizarea functiei fitness, care asociaza o valoare fiecarei solutii candidat), PSO procedeaza in mod diferit. Fiecare solutie candidat, numita in acest context particula, se afla in permanenta miscare, in incercarea de a se apropia de doua valori importante: cea mai buna valoare a functiei fitness pe care particula respectiva a inregistrat-o de-a lungul evolutiei sale, respectiv cea mai buna valoare a functiei fitness inregistrata de oricare particula din vecinatatea sa de-a lungul evolutiei acestora.

Ceea ce diferentiaza in mod fundamental PSO de alte tehnici este separarea completa a spatiului in care se misca particulele de spatiul solutiilor asa cum este definit de problema. Particulele se misca intr-un spatiu bidimensional, iar pozitiile lor (si implicit distantele dintre acestea) sunt initializate aleator si evolueaza doar in functie de relatiile stabilite cu vecinii topologici. Datorita acestei separari, PSO se preteaza la abordarea oricarui tip de problema de optimizare. O directie in care s-au obtinut rezultate deosebite este clasa problemelor de clasificare si in special clustering, care profita de importanta acordata in PSO relatiilor dintre vecini.

De asemenea, PSO deschide noi perspective prin posibilitatile de hibridizare cu alte metode, deterministe sau euristice. Datorita modului diferit de actiune, PSO poate aduce imbuntatatiri substantiale prin integrarea cu alte tehnici. Din acest motiv, cercetarea in domeniul PSO este extrem de promitatoare, permitand elaborarea de noi paradigme de calcul.

1.5.2.6. Analiza statistica a dinamicii populatiei corespunzatoare unei clase de

algoritmi evolutivi.

Exista doua abordari principale in analiza statistica a dinamicii algoritmilor evolutivi: una bazata pe estimarea momentelor de ordinal intai si de ordin superior si cealalta bazata pe ipoteza ca elementele populatiei sunt realizari ale unor variabile aleatoare avand un anumit tip de distributie. Majoritatea rezultatelor existente au fost obtinute pentru algoritmi evolutivi caracterizati prin mutatie bazata pe repartitia normala. In cazul algoritmilor ce utilizeaza un alt tip de mutatie (cum sunt cei de tip Differential Evolution - DE) rezultatele sunt inca putine (Xue, 2005). In lucrarea (Zaharie, 2008a) se demonstreaza ca pentru aproape toate variantele de algoritmi de tip DE utilizate la ora actuala varianta medie a populatiei (la nivel de componenta) obtinute prin mutatie si incrucisare depinde liniar de varianta media a populatiei curente. Aceasta dependenta liniara implica parametrii de control ai strategiei (factorul de scala si rata de incrucisare) ceea ce permite controlul variantei (implicit a diversitatii) populatiei prin modificarea valorilor parametrilor. Au fost identificate diferente semnificative pentru variante de algoritm ce utilizeaza diferite tipuri de incrucisare (binomiala, exponentiala si aritmetica). Aceste rezultate permit alegerea intr-o maniera fundamentata teoretic a parametrilor de control in functie de tipul de incrucisare utilizat. Dintre observatiile cu impact practic mentionam faptul ca o valoare mare a raportului intre volumul populatiei si dimensiunea problemei nu garanteaza o crestere a diversitatii populatiei. In schimb parametrii de control (factorul de scalare si rata de incrucisare) au un impact mai mare asupra

conservarii diversitatii populatiei. Aceasta inseamna ca alegand adecvat parametrii de control se pot evita situatiile de convergenta premature chiar si atunci cand se opereaza cu populatii de dimensiune mica. Pornind de la rezultatele teoretice obtinute a fost propusa un tip mutatie care nu utilizeaza diferente dar care conduce la un comportament similar al varianŃei cu cel din cazul algoritmului DE. Studiul numeric al acestui tip de mutatie a pus in evidenta faptul ca dinamica variantei populatiei are o influenta importanta asupra comportamentului algoritmului. Pe de alta parte s-a pus in evidenta si faptul ca reproducerea dinamicii din punctul de vedere al variantei nu este suficienta pentru a obtine acelasi comportament global. Recent (Gong, Tuson, 2007) au fost propuse variante ale algoritmilor de tip Differential Evolution pentru cazul codificarii binare. Analizand teoretic impactul probabilitatii de mutatie asupra distributiei de probabilitate a componentelor s-au observat diferente semnificative in raport cu mutatia clasica bazata pe complementarea componentelor. In cazul mutatiei clasice distributia de probabilitate a componentelor este puternic influentata de catre probabilitatea de mutatie pe cand in cazul variantei de tip DE influenta probabilitatii de mutatie este semnificativ mai mica, distributia populatiei fiind robusta la variatiile probabilitatii de mutatie. Un studiu detaliat al influentei operatorului de incrucisare asupra comportarii algoritmilor de tip DE este prezentat in (Zaharie, 2008b). Elementul cheie al incrucisarii utilizate in cazul algoritmilor DE este faptul ca determina care si cate dintre componentele unui element vor fi inlocuite cu componentele corespunzatoare din elementul obtinut prin mutatie. Astfel rata de incrucisare determina de fapt valoarea unui parametru similar probabilitatii de mutatie. Unul dintre principalele rezultate obtinute este faptul ca pentru aceeasi valoare a ratei de incrucisare se pot obtine valori semnificativ diferite ale probabilitatii de mutatie, in functie de tipul de incrucisare folosita (binomiala sau exponentiala). In cazul incrucisarii de tip binomial dependenta dintre probabilitatea de mutatie si rata de incrucisare este liniara pe cand in cazul incrucisarii exponentiale este neliniara. In felul acesta au putut fi explicate diferentele observate experimental intre diferitele tipuri de incrucisare si aduse argumente teoretice pentru regulile de natura euristica privind alegerea valorii ratei de incrucisare care sunt folosite de catre practicieni: “in cazul incrucisarii exponentiale rata de incrucisare trebuie aleasa intre 0.9 si 1” sau “in cazul incrucisarii exponentiale sunt necesare valori mai mari ale ratei de incrucisare decat in cazul celei binomiale”. In plus, in cazul problemelor de dimensiuni mari domeniul de valori ale ratei de incrucisare pentru care valoarea probabilitatii de mutatie este semnificativa devine foarte mic. Aceasta inseamna ca variantele bazate pe incrucisare exponentiala nu sunt indicate pentru probleme de dimensiuni mari cu exceptia cazului in care acestea sunt separabile (caz in care se obtin rezultate bune pentru valori mici ale probabilitatii de mutatie intrucat cautarea se realizeaza de fapt separat pe componente). Intrucat parametrii de control sunt intercorelati s-a observat si faptul ca pentru evitarea convergentei premature, in cazul incrucisarii exponentiale pentru aceeasi valoare a ratei de incrucisare este necesara utilizarea unei valori mai mari pentru factorul de scalare. Cu scopul de a dezvolta variante eficiente din punctul de vedere al timpului de executie au fost propuse variante de implementare ale incrucisarii exponentiale care utilizeaza putine apeluri ale generatorului de numere aleatoare. Pe de alta parte s-a investigat modul in care se comporta cateva variante recente (Mezura et al., 2006), (Brest et al., 2005) de ajustare si auto-adaptare a parametrilor atunci cand se schimba tipul de incrucisare. Concluzia la care s-a ajuns este ca in cazul incrucisarii exponentiale utilizarea unei repartitii uniforme pentru alegerea/adaptarea valorii ratei de incrucisare nu este adecvata. Este propusa o distributie ne-uniforma de probabilitate care utilizata pentru selectia ratei de incrucisare conduce la o repartitie

uniforma a valorilor corespunzatoare ale probabilitatii de mutatie. O problema inca deschisa este de a identifica clase de probleme pentru care incrucisarea exponentiala conduce la rezultate mai bune decat incrucisarea binomiala. 1.5.3. Identificarea de probleme practice semnificative de mare complexitate.

Studii de caz

1.5.3.1. Probleme neseparabile cu numar foarte mare de variabile

Metodele propuse in (Iclanzan and Dumitrescu, 2008c) deschid drumul spre rezolvarea unor probleme grele, cu module non separabile si cu milioane de variabile. Aceste tehnici vor putea fi in continuare imbunatatite prin codificarea legaturii dintre module ca o variabila aleatoare, si prin paralelizarea metodelor propuse, atat prin aplicarea concomitenta a strategiilor de cautare, cat si prin paralelizarea constructiei modelului de cautare (Iclanzan and Dumitrescu, 2008c). 1.5.3.2. Cautare/optimizare competitiva pentru probleme complexe. Studii de

caz

Ca studiu de caz s-a aratat cum metodele de invatare (bazata pe retele neuronale) a structurii functiilor obiectiv pot extinde metoda simpla (1+1) Evolutionary Algorithm, facilitand rezolvarea unor probleme grele care sunt demonstrabil intractabile folosind reprezentari simple si operatori ficsi. Mai mult rezultatele obtinute au aratat ca in cazul unor probleme cu cuplaj bivariat puternic intre variabile, metoda extinsa depaseste ca performanta metodele clasice complexe bazate pe populatii (Iclanzan and Dumitrescu, 2008a). Ulterior a fost dezvoltata o metodologie capabila sa detecteze si sa combine module foarte largi, chiar si in cazul legaturilor genetice nefavorabile si in lipsa gradientilor intra-bloc care in mod normal pot ghida cautarea intr-o maniera locala, sau chiar si in cazul deceptivitatii (Iclanzan, Dumitrescu, 2008b). Aceste rezultate au fost posibile prin investirea numarului de evaluari a functiilor obiectiv intr-o cautare locala cu o putere exploratorie puternica, si prin limitarea detectarii modelelor la cateva cateva solutii optime local. Rezultatele obtinute au confirmat faptul ca aceasta tehnica este capabila sa rezolve cu mare siguranta si exactitate probleme foarte grele cu blocuri neutre mari sau probleme cu un numar exponential de optime locale (masiv deceptive), cu o complexitate cuadratica in marimea modulelor.

1.5.3.3. Optimizare multimodala evolutiva. Studii de caz

Rezultatele obtinute in (Stoean et al, 2008) sunt comparate cu cele obtinute de metode bazate pe clustering aplicate la diverse stadii de populatii evoluate. S-au luat in calcul functiile standard bidimensionale Waves si Six-Hump Camel Back, pentru care numarul de optime este stiut, si functia Rastrigin in mai multe dimensiuni, unde nu este cunoscuta nicio informatie legata de varfuri. In mod interesant, exista un punct din care metoda propusa este clar mai buna, desi, pentru bugete scazute de evaluari de performanta, tehnicile de clustering au avantaje.

Probleme complexe multimodale au fost de asemenea avute in vedere. Astfel, manipularea precisa a razelor in cadrul tehnicilor evolutive multimodale a fost mereu o problema cruciala si niciodata simpla. Este si cazul paradigmei cromodinamicii genetice, care realizeaza examinarea mai multor bazine de atractie in acelasi timp prin interactiuni intre indivizi care se afla in regiuni determinate de praguri definite de utilizator (Stoean et al, 2008). In acest sens, este propus un mecanism adaptiv alternativ pentru detectarea subpopulatiilor, bazat pe exploatarea topologiei formei functiei obiectiv. In

cadrul imbunatatirii propuse, aceasta examinare implica practic verificarea faptului daca o pereche de indivizi urmareste acelasi optim sau nu (Stoean et al, 2008c). Testul este condus pe un numar de functii multimodale – Himmelblau, Schaffer si Six-Hump Camel Back. Comparatia este facuta fata de metoda originala si, in afara de cea de-a doua functie, amandoua metodele isi ating scopul. Este insa interesant de remarcat ca cea nou propusa gaseste solutiile intr-o maniera mai rapida. Rezultatele demonstreaza flexibilitatea si comportamentul imbunatatit in ceea ce priveste algoritmul considerat. Probleme complexe reale cum ar fi diagnoza diabetului mellitus, determinarea bolilor plantelor de soia, recunoasterea plantelor de iris, detectarea spam-ului si predictia imobiliara in Boston au fost rezolvate cu o noua tehnica evolutiva construita ca o alternativa a arhitecturii standard a masinilor cu suport vectorial. Abordarea adopta strategia de invatare a acestora dar tinteste spre a simplifica si generaliza antrenarea, oferind un substituent transparent cutiei negre initiale. Rezultatele computationale si comparatia cu o implementare standard a masinilor cu suport vectorial clasice demonstreaza validitatea noii abordari in termeni de timp de rulare, acuratete de predictie si flexibilitate.

1.5.3.4. Modele distribuite spatial. Experimente numerice si studii de caz

Dinamica celor trei subpopulatii ce intervin in modelele distribuite spatial (Gog et al., 2008b) a fost studiata si au fost evidentiate procese complexe care au aratat ca sistemul aparent simplu al celor trei societati este de fapt un sistem complex cu un comportament ce nu poate fi prevazut. A fost evidentiat si un interval asociat cu o tranzitie de faza, interval in care au loc fenomene computationale complexe asociate cu solutii mai bune decat in afara intervalului. Comparate cu alte metode evolutive aparute in literatura de specialitate, rezultatele obtinute sunt un bun indicator al eficientei metodei propuse. Ideea utilizarii unor subpopulatii caracterizate prin strategii diferite de recombinare a fost aplicata si in scopul obtinerii unor algoritmi evolutivi care asigura un compromis intre explorarea si exploatarea intensiva. Studiul comparativ prezentat in (Gog et al., 2008c) cuprinde pe langa modelul propus si variante bazate pe tehnici adaptive propuse in ultimii ani (Qin et al., 2005), (Brest et al., 2007).

1.5.3.5. Identificarea topologiei spatiului de cautare in probleme complexe

O alta clasa de probleme complexe abordate este aceea a problemelor care au solutii intr-un spatiu de cautare despre care nu avem informatii a priori. Pentru acest tip de probleme, numarul de optime existente, fie ele globale sau locale, are o importanta decisiva pentru a alege algoritmul potrivit si pentru a gasi cele mai adecvate valori pentru parametrii sai. Se propune o metoda bazata pe o tehnica evolutiva pentru optimizare in cazul codificarii reale in scopul de a oferi o estimare a numarului de optime pe care il detine o functie, cu un buget foarte redus de evaluari ale functiei de performanta. Aceasta unealta este bazata pe un algoritm evolutiv si achizitioneaza date legate de profilul formei spatiului de cautare al unei probleme definita pe domenii reale. In loc sa obtinem o multime cu cele mai bune solutii, scopul a fost de a obtine o estimare a numarului de optime pe care il are functia obiectiv. Cum unealta este una de preprocesare, trebuie sa nu fie foarte costisitoare cu privire la numarul de apeluri ale functiei obiectiv. In acest scop, utilizam o populatie cu marime variabila: Pornim cu o populatie mare si continuam numai cu cei mai prolifici indivizi care apartin la bazine de atractie diferite. Astfel, numarul de evaluari ale functiei de

performanta este mentinut redus. Marimea populatiei poate creste din nou pe parcursul reproducerii, dar, cu exceptia situatiei in care sunt descoperite noi bazine de atractie, este redusa din nou la minim. O alta constrangere importanta este ca nu a fost adaugat vreun parametru aditional in raport cu un algoritm evolutiv canonic care sa depinda de problema considerata. 1.5.3.6. Metaeuristici hibride. Experimente numerice in cazul optimizarii

functiilor cu numar mare de variabile.

In scopul identificarii unor metode adecvate pentru optimizarea functiilor cu numar mare de variabile au fost investigate meta-euristici propuse relativ recent, au fost identificate avantajele si dezavantajele acestora si au fost propuse variante imbunatatite. Una dintre aceste meta-euristici este Harmony Search (HS) propusa in (Geem et al., 2001). Strategia de tip HS se bazeaza pe analogia dintre procesul de optimizare si cel de descoperire a armoniei in cadrul unui ansamblu de instrumente muzicale. Implementarea acestei idei se bazeaza pe utilizarea unei arhive de configuratii (initializate aleator si actualizate in momentul in care este descoperita o configuratie mai buna decat cea mai slaba din arhiva) si pe generarea de noi configuratii prin incrucisarea uniform aleatoare a unor configuratii din arhiva si aplicarea unei perturbatii aleatoare. HS este astfel un algoritm de cautare aleatoare care foloseste aceleasi instrumente ca si algoritmii evolutivi insa motivate de un alt tip de analogie decat cea cu evolutia biologica. In lucrarea (Nicoara, 2008) este prezentat un studiu detaliat al caracteristicilor acestei tehnici si al abilitatii ei de a rezolva probleme de optimizare continua. Una dintre motivatiile analizei acestei tehnici a reprezentat-o faptul ca HS a fost aplicata cu succes in rezolvarea unor probleme de optimizare in domenii discrete. Ca prim rezultat al analizei efectuate au fost identificate cateva dezavantaje ale metodei, si anume: inabilitatea de a localiza optimul global chiar daca regiunea sa de atractie a fost identificata, predispozitia pentru convergenta prematura, inabilitatea de a rezolva probleme de dimensiuni mari. Ca principala cauza a acestor limitari a fost identificata absenta unui operator de mutatie care sa favorizeze perturbatiile mici in detrimentul celor mari (operatorul de perturbare din varianta HS clasica se bazeaza pe o repartitie uniforma). In plus necesitatea de a ajusta atent valorile parametrilor utilizati pentru perturbarea configuratiilor reprezinta un dezavantaj din punctul de vedere al unui utilizator. In scopul eliminarii sau cel putin a reducerii impactului acestor dezavantaje au fost propuse noi variante caracterizate prin: (a) utilizarea unei recombinari convexe in care este implicat cel mai bun element al arhivei si un element selectat aleator; (b) utilizarea unei perturbatii cu repartitie normala sau Cauchy. Pe langa variantele in care s-a utilizat doar una dintre distributii au fost testate si variante hibride in care au fost utilizate ambele variante fie simultan (conducand la generare la fiecare etapa a doua noi elemente care pot fi asimilate in arhiva) fie alternativ (fiecare tip de perturbare este aplicata pentru un numar prestabilit de generatii). Toate variantele propuse au fost testate pentru functii de test avand 30, 100 respectiv 500 de variabile si comparate cu variante ale algoritmului DE (Differential Evolution) si FEP (Fast Evolutionary Programming). Variantele propuse au condus la rezultate mai bune decat cele clasice comportandu-se mai bine decat FEP si fiind comparabile cu DE. Castigul s-a dovedit semnificativ in cazul problemelor de dimensiuni mari (n=500). Totusi pentru probleme de dimensiuni mai mari (n>1000) nu ating performantele tehnicilor care utilizeaza strategii coevolutive si cooperative (de exemplu DECC (Yang et al. 2007)). Introducerea strategiilor cooperativ-coevolutive in HS reprezinta una din directiile viitoare de cercetare.

1.5.3.7. Clasificare si clustering. Studii de caz

Problemele de clasificare presupun gruparea unui set dat de obiecte in clase predefinite. In general, dimensiunea setului este foarte mare, ceea ce face ca metodele deterministe sa nu fie eficiente. O serie de tehnici euristice obtin rezultate foarte bune in rezolvarea acestui tip de probleme. O varianta mai dificila o constituie problemele de clustering. In acest caz nu se cunoaste dinainte numarul clusterelor in care trebuie realizata gruparea si nici nu exista informatii cunoscute apriori despre pozitionarea acestor clustere in spatiul de cautare. Desi unele metode, in special algoritmii genetici si retelele neurale, pot da rezultate bune in clustering, problema este inca deschisa, datorita complexitatii sale si dificultatilor in definirea exacta a problemelor concrete. In (Breaban, Luchian, 2008) este abordata problema din punct de vedere al Particle Swarm Optimization (PSO). Este propusa o forma mai simpla si mai directa de mapare a problemei pe modul de lucru al PSO decat in variantele existente. In acest scop au fost aduse o serie de modificari fata de modelul PSO standard, inclusiv adaugarea unor pasi de pre- si post-procesare. Tehnica a fost testata pe diverse seturi de date, avand atat clustere bine definite, cat si clustere puternic suprapuse. Rezultatele obtinute arata ca o asemenea metoda poate depasi ca performanta algoritmii de tip centroid. In acelasi timp, s-a observat o puternica dependenta de setarile algoritmului, care sunt realizate empiric. O aplicatie practica de tip clustering se refera la sistemele de recomandare pentru navigarea pe web (Breaban, Alboaie, Luchian, 2008). In acest caz, problema consta in gruparea utilizatorilor pe baza preferintelor acestora, tinand cont de faptul ca informatiile privind preferintele sunt in general incomplete. O dificultate suplimentara, in afara dimensiunii setului de date, rezida in faptul ca nu exista o referinta absoluta pentru corectitudinea informatiilor disponibile, increderea fiind puternic dependenta de relatiile dintre utilizatori, avand deci un puternic caracter local. Abordarea a constat in utilizarea metodei PSO cu unele modificari, impreuna cu un algoritm aglomerativ de clustering. Rezultatele s-au dovedit superioare celor obtinute de metodele existente si sugereaza aplicarea tehnicii propuse pentru orice tip de retele sociale. 1.5.3.8. Identificarea starii de energie minima in sistemele de tip „Ising Spin

Glass”

Dincolo de importanta sa ca punct de pornire in dezvoltarea de noi tehnici, modelul Ising ridica si o serie de probleme practice, cum ar fi identificarea starilor de baza ale spinului. Problema, deosebit de importanta in fizica aplicata, reprezinta o provocare din punct de vedere computational, datorita complexitatii sale. In (Bautu, Bautu, Luchian, 2008a) se propune o noua reprezentare, de tip spanning tree, care considera starile restrictiilor privitoare la legaturile dintre spini. Abordarea este bazata pe structura clasica a unui algoritm genetic, dar sunt introdusi operatori specifici problemei, cei clasici fiind putin eficenti in acest caz. Mai exact, mutatia si incrucisarea au fost proiectate astfel incat sa tina cont de relatiile dintre muchiile arborelui care formeaza reprezentarea. La partea experimentala, pentru comparatie s-au luat in considerare trei algoritmi: un algoritm genetic simplu, utilizand reprezentarea standard (care ia in considerare direct spinii, nu legaturile); un algoritm care utilizeaza reprezentarea nou propusa, dar operatori standard; un algoritm care utilizeaza atat reprezentarea nou propusa, cat si

operatorii nou introdusi. Experimentele efectuate arata ca, in timp ce pentru dimensiuni reduse ale problemei rezultatele sunt la acelasi nivel, la cresterea dimensiunii ultimul algoritm se detaseaza clar. Este in schimb de remarcat faptul ca noua reprezentare propusa nu duce la cresterea performantei decat atunci cand se aplica si operatorii nou introdusi, in caz contrar observandu-se chiar o scadere de performanta. 1.5.3.9. Modelarea seriilor de timp. Studii de caz.

O problema cu aplicatii directe in domenii critice (e.g., economie, managementul energiei) o reprezinta analiza si predictia seriilor de timp. Practic toate metodele dezvoltate pana astazi obtin rezultate bune pe seturi de date sintetice, dar esueaza in fata datelor provenite din lumea reala. Explicatia nu consta in dimensiunea datelor, ci in faptul ca mediul care genereaza datele are un comportament in continua schimbare. Lucrarea (Bautu, Bautu, Luchian, 2008b) propune o forma imbunatatita de algoritm genetic, adaptat pentru modelarea seriilor de timp generate de procese dinamice. Reprezentarea se concentreaza asupra notiunii de punct de schimbare in cadrul seriei de timp, iar algoritmul este orientat spre identificarea acestor puncte de schimbare. Reprezentarea utilizata consta dintr-un set de gene, fiecare gena modeland un punct de schimbare; astfel, un cromozom contine informatii despre toate punctele de schimbare din seria de timp. La randul sau, fiecare gena contine: locatia punctului de schimbare; tipul de model care se potriveste cu sectiunea din seria de timp pana la urmatorul punct de schimbare; parametrii modelului pentru sectiunea respectiva. Data fiind complexitatea reprezentarii, operatorii genetici sunt adaptati pentru a elimina redundantele (de exemplu, crearea nedorita de noi puncte de schimbare). Operatorii de incrucisare realizeaza intreschimbarea unor gene intre parinti, relativ la punctul de taiere. Operatorii de mutatie realizeaza diferite actiuni elementare: modificarea modelului intr-o gena (deci intr-o sectiune a seriei de timp); schimbarea locatiei unei gene; inserarea unei noi gene (deci a unui nou punct de schimbare); stergerea unei gene existente. Rezultatele experimentale arata ca algoritmul are inca probleme pe anumite seturi de date, dar directia aleasa promite obtinerea unor performante foarte bune. O abordare alternativa este prezentata in (Bautu, Kim, Bautu, Luchian, Zhang, 2008). Conceptul de baza este cel de hiperretea, care reprezinta o generalizare a structurii de tip hipergraf, continand informatii despre relatiile dintre date. Abordarea isi propune sa dezvolte prin metode evolutive o hiperretea care identifica un mare numar de pattern-uri, predictia rezultand din combinarea acestora din urma. Metoda este inspirata din tehnicile de invatare automata, dar hibridizarea cu tehnicile evolutive ii confera un avantaj important. Rezultatele testelor efectuate pe serii de date reale (evolutia unor indici bursieri) arata o eficienta superioara metodelor existente. 1.5.3.10. Modelarea unor fenomene biologice si analiza datelor medicale.

Complexitatea sistemelor biologice este bine cunoscuta iar modelarea acestora reprezinta o provocare atat pentru matematica cat si pentru informatica. Majoritatea fenomenelor din sistemele vii sunt controlate prin intermediul unor retele de reglare cu structura complexa. Modelarea acestor retele necesita un numar mare de ecuatii sau reguli de transformare astfel ca simularea lor poate ridica probleme de natura computationala. Una dintre retelele de reglare este cea care controleaza procesul de coagulare a sangelui

prin formarea trombinei. Reactiile implicate in procesul de coagulare formeaza o cascada cu multiple bucle inverse (atat pozitive cat si negative) astfel ca un model matematic apropiat de realitate este unul bazat pe zeci de ecuatii. In cascada de reactii exista doua cai principale una intrinseca si una extrinseca care se intersecteaza. Majoritatea modelelor trateaza separat aceste doua cai. In lucrarea (Braescu, 2008) cele doua cai sunt cuprinse in acelasi model obtinandu-se un sistem cu 36 de ecuatii difierentiale de ordinul 1. Rezultatele obtinute prin rezolvarea numerica a sistemului sunt in conformitate cu cele experimentale atat in ce priveste profilul trombinei cat si in ceea ce priveste durata fazei de initiere a procesului de producere a trombinei.

O alta problema dificila o reprezinta extragerea informatiilor din datele medicale. Dificultatea este generata de cel putin doua aspecte: (a) datele medicale sunt mixte (numerice, nominale, ordinale, imagini etc), pot proveni din diferite surse (date distribuite) si sunt adesea afectate de zgomot si valori absente; (b) scopul urmarit este extragerea unor modele predictive care sa aiba si caracter explicativ. O posibila solutie pentru satisfacerea celui de al doilea aspect este de a reprezenta prin reguli (de clasificare, de predictie sau de asociere) cunostintele extrase din date. Procesul de extragere a regulilor poate fi interpretat ca o problema de optimizare multi-criteriala in care se urmareste optimizarea mai multor criterii care cuantifica gradul de confidenta, comprehensibilitatea si nu in ultimul rand gradul de noutate (interes din punctul de vedere al expertului uman). Pentru fiecare dintre aceste caracteristici ale regulilor exista diferite masuri de evaluare astfel ca apare problema selectarii celor adecvate. Problema este critica in special in cazul masurilor care cuantifica gradul de noutate, avand in vedere ca acesta are un caracter subiectiv si la ora actuala exista cel putin 40 astfel de masuri. Majoritatea algoritmilor evolutivi destinati rezolvarii problemelor de optimizare multicriteriala functioneaza bine pentru cazul unui numar mic de criterii (doua sau trei) insa prezinta dificultati pentru cazul unui numar mare de criterii. Recent au fost propuse variante de asigurare a scalabilitatii in raport cu numarul criteriilor de optimi a algoritmilor evolutivi (Kukkonen et al., 2008), (Ishibuchi et al., 2008) insa problema este inca incomplet rezolvata. O alta dificultate identificata in procesul de extragere a regulilor este legata de forma regulilor si de numarul mare de reguli care sunt produse de algoritmul de optimizare multicriteriala (cu cat numarul de criterii este mai mare cu atat setul solutiilor nedominate este mai mare). In (Zaharie et al., 2008) a fost propusa o varianta de extragere interactiva a regulilor in care expertul uman poate sa evalueze regulile produse si sa ghideze procesul de cautare in spatial regulilor. Abordarea interactiva a fost analizata doar pentru cazul regulilor de predictie in care antecedentul si consecinta sunt conjunctii de termeni ce includ atribute individuale. Extinderea pentru cazul unor reguli arbitrare reprezinta o problema ce va fi studiata in continuare.

1.5.3.11. Utilizarea retelelor neuronale cu comportament haotic in criptografie.

Studiu de caz.

Criptarea informatiilor este una dintre problemele cele mai frecvent intalnite in proiectarea sistemelor securizate de comunicare. In scopul identificarii unor tehnici robuste de criptare in ultimii ani au fost propuse diferite mecanisme bazate pe sisteme cu comportament haotic. In (Yu, Cao, 2006) este propus un sistem de criptare bazat pe o retea neuronala recurenta cu intarzieri modelata in timp continuu, printr-un sistem de ecuatii diferentiale. Sistemul se caracterizeaza prin entropie informationala mare si printr-o distributie uniforma a valorilor corespunzatoare semnalului codificat. Intrucat simularea unei retele recurente se realizeaza in timp discret este mai avantajos sa se utilizeze din start un model de retea neuronala cu dinamica discreta si comportament haotic. In lucrarea (Darau, Kaslik, Balint, 2008) este propus un astfel de model caracterizat prin: (a) reteaua contine doi neuroni interconectati dar fara auto-conexiuni;

(b) valorile ponderilor conexiunilor sunt suficient de mari in valoare absoluta pentru a induce un comportament haotic; (c) fiecare neuron are o intarziere proprie. Procesul de codificare se bazeaza pe urmatoarele etape: (i) se simuleaza dinamica retelei pentru un numar de iteratii corespunzatoare perioadei de tranzitie care precede comportamentul haotic; (ii) folosind valorile produse de catre unul dintre neuroni (neuronul utilizat se alege in baza unor reguli prestabilite) si o functie prag se genereaza niste siruri binare; (iii) unul dintre sirurile binare interpretat ca valoare naturala se foloseste pentru a permuta circular blocuri atat din informatia care trebuie codificata cat si din celalalt sir binar; (iv) informatia codificata se obtine prin aplicarea disjunctiei exclusive asupra variantelor permutate ale informatiei de codificat si ale celui de al doilea sir binar. Cheia de criptare este sirul binar folosit pentru permutare impreuna cu caracteristicile retelei (ponderile conexiunilor, intarzierile, ratele de descrestere, numarul de iteratii din faza tranzitorie). Sistemul propus a fost testat pentru criptarea imaginilor digitale si au fost analizate proprietatile sale statistice observandu-se o corelatie foarte mica intre pixelii vecini ai imaginii criptate ceea ce creaza dificultati in gasirea unui indiciu pentru decriptare. S-a aratat ca sistemul este senzitiv la datele initiale astfel ca in absenta valorilor exacte ale conditiilor initiale decriptarea este imposibila. 1.5.3.12. Clasificarea nesupervizata a documentelor electronice. Studiu de caz

In conditiile existentei unui volum imens de informatii nestructurate una dintre problemele curente in documentarea stiintifica din diferite domenii o reprezinta necesitatea de a accesa rapid si fiabil informatia dorita. Acest demers este insa dificil in absenta unor instrumente care să faciliteze:

• navigarea ghidată în "marea" de documente; ghidarea referindu-se la faptul de a avea la dispoziŃie o "busolă" care să îi indice direcŃia spre care o ia navigarea, mai mult chiar, o busolă cu mai multe ace, fiecare indicând spre un anumit domeniu, indicând practic întretăierea domeniilor;

• evaluarea din punct de vedere calitativ al conŃinutului, mai exact gradul de adecvare şi acurateŃe a faptelor şi afirmaŃiilor prezentate în lucrarea în discuŃie;

• sumarizarea din punct de vedere semantic al conŃinutului, pentru extragerea esenŃei celor prezentate;

Dacă cea de a doua problemă nu poate fi rezolvată decât în mod exclusiv subiectiv şi manual, celelalte probleme pot avea o soluŃionare automată, sau cel puŃin construind un punct de plecare. SoluŃia pentru problema generică a navigării o reprezintă clasificarea documentelor (document clustering), şi anume atribuirea unui document la una sau mai multe clase (domenii). Această clasă de probleme se incadreaza in domeniul regasirii informatiilor (information retrieval) si reprezinta o ramura in domeniul explorarii datelor (data mining). Domeniul prelucrarii automate a documentelor electronice necesita utilizarea a diverse tehnici: statistice, specifice procesarii limbajului natural sau chiar meta-euristici inspirate de natura. Ca produse directe al acestui domeniu îl constituie sistemele de recomandare, anume:

• sisteme de recomandare bazate pe conŃinut (content based recommender systems), în care atribuirea unui document la o clasă (domeniu) se face în mod exclusiv pe baza conŃinutului său;

• sisteme de recomandare colaborative (collaborative recommender systems), unde conŃinutul este ignorat, atribuirea fiind realizată pe baza reactiei utilizatorilor

• sisteme de recomandare hibride ce încearcă combinarea avantajelor celor două direcŃii;

Este evident faptul că fiecare dintre direcŃiile de mai sus au avantajele şi dezavantajele lor, fiecare încercând să menŃină un echilibru între calitatea clasificării (privită prin prisma perceperii umane), complexitatea şi responsivitatea sistemului. Ca direcŃie aleasă de noi, ne încadrăm în prima categorie, anume a sistemelor de recomandare bazate pe conŃinut, a cărui timp de răspuns (timpul scurs de la intrarea în sistem a unui document şi până la clasificarea lui) este minim, iar acurateŃea clasificării este bună.

Problema clasificarii automate a documentelor poate fi descrisa succinct prin specificarea intrarilor si a iesirilor corespunzatoare, dupa cum urmeaza:

• intrări: o colecŃie de documente (evident în format electronic, eventual eterogen); precum şi o colecŃie de clase (domenii) deja descoperite şi elementele sale definitorii; (aceste intrări din urmă sunt opŃionale);

• ieşiri: atribuirea fiecărui document la un set de clase (domenii).

Obiectivul urmarit a fost implementarea unui sistem de clasificare automată a documentelor, vazut ca o componenta a unui system de navigare destinat unei biblioteci de documente ştiinŃifice. Ipotezele de lucru au fost urmatoarele:

• nu există o colecŃie predefinită de clase, sistemul trebuind să le detecteze în mod automat;

• clasele ar trebui să constituie un arbore reprezentând modul în care un domeniu îşi conŃine subdomeniile;

• fiecare document poate fi atribuit mai multor clase (domenii), ponderate cu o anumita probabilitate;

• întregul sistem trebuie să fie nesupervizat.

In ceea ce priveste terminologia, în cele ce urmează vom utiliza în mod interschimbabil următorii termeni: "clasă", "categorie", "domeniu" sau (uneori) "prototip". De asemenea termenul de document poate avea înŃeles dublu, atât ca şi lucrare în format electronic, cât şi ca reprezentare abstractă a conŃinutului acesteia în funcŃie de necesităŃile diferiŃilor algoritmi. Algoritmii de clasificare utilizati se caracterizeaza prin:

• algoritmii în sine nu utilizează textual documentele, ci reprezentări numerice, vectoriale;

• pentru aceasta documentele sunt trecute printr-o fază de preprocesare, proces prin care fiecărui document îi este ataşat un vector caracteristic, format din frecvenŃa cuvintelor (sau a unui subset de cuvinte) din textul original;

• din setul global de vectori obŃinut anterior, se selectează (de regulă în mod aleator) un set de antrenare suficient de mare;

• utilizând setul de antrenare se identifică un set de clase, reprezentate tot prin vectori numerici, ce pot fi interpretate ca documente prototip pentru respectiva categorie;

• în procesul de clasificare, se utilizează o funcŃie de distanŃă ce încearcă să aproximeze apartenenŃa unui document la o anumită categorie (în general se numeşte funcŃie de similaritate).

In lucrarea (Craciun, 2008) este prezentat un prototip de sistem de clasificare a documentelor bazat pe o retea neuronala de tip ART (Adaptive Resonance Theory). Identificarea categoriilor existente intr-un set de date (documente) se bazeaza pe urmatorul proces iterativ:

1. pentru fiecare document identificăm categoria de care se apropie cel mai mult; a. dacă apropierea (similaritatea) se află peste un anumit prag de vigilenŃă

(prestabilit), ajustăm vectorul caracteristic al categoriei, utilizând o rată de învăŃare (prestabilită);

b. în caz contrar, se crează o nouă clasă, utilizând ca vector caracteristic însuşi documentul curent;

2. se iterează întregul proces de una numit număr de ori (prestabilit).

Procesul de antrenare a clasificatorului este influenŃat de trei parametri, de a căror alegere depinde calitatea clasificării: pragul de vigilenŃă, rata de învăŃare, numărul de iteraŃii. Algoritmul standard de ajustare a fost adaptat pentru particularitatile problemei de clasificare a documentelor. Pentru validarea clasificatorului au fost utilizate atat metode de validare externa cat si metode de validare interna. Validarea externă se bazează pe subiectivitatea umană, măsurând (din punct de vedere calitativ) cât de mult se apropie clasificatorul automat, de modul în care un om ar clasifica (în mod subiectiv) documentele; astfel chiar dacă o astfel de verificare este esenŃială în probleme în care fiecare punct din setul de date reprezintă o instanŃă clară a unei clase, în cazul unei clasificări de documente ea se poate dovedi inadecvată, deoarece nu se poate realiza o clasificare obiectivă, fiecare dintre noi privind în mod subiectiv un anumit set de documente. Validarea internă se bazează exclusiv pe calităŃile claselor rezultate în urma clasificării; în acest sens această verificare fiind mult mai adecvată problemei de faŃă, deoarece va testa doar proprietăŃile claselor în sine, verificând dacă acestea sunt echilibrate, atât din punctul de vedere al documentelor ce aparŃin, cât şi din punct de vedere al depărtării faŃă de alte categorii. Indicatorii utilizati pentru validare sunt: Rand, Jaccard, indexul Folkes and Mallows, entropia si puritatea (validare externa), respectiv PBM (validare interna) .

Prototipul utilizat in studiul de caz se încadrează în sistemele bazate pe servici (SOA -- Service Oriented Architecture), în care fiecare componentă are exact un singur rol, singurele interacŃiuni bazându-se pe comunicarea între componente prin intermediul unor interfeŃe bine stabilite. Arhitectura generala este ilustrata in figura urmatoare.

Principalele componente ale sistemului sunt:

• clasificatorul nesupervizat (unsupervized classifier): reprezintă rezultatul direct al activităŃii desfăşurate în acest proiect, el având scopul clasificării (sau reclasificării) documentelor cu ajutorul unor tehnici nesupervizate.

• clasificatorul colaborativ (collaborative classifier): componentă ce ar trebui să aducă în cadrul procesului de clasificare şi expertiza umană, pe baza feedback-ului utilizatorilor; (această componentă poate fi implementată ca o extensie);

• sistemul de recomandare (recommender system): acesta joacă rolul de mediator între cele două sisteme de clasificare (nesupervizat şi supervizat), coroborând rezultatele acestora două; precum şi inferenŃe legate de profilul unui anumit utilizator pe baza istoricului navigării; (ca şi în cazul componentei precedente, el reprezintă o componentă opŃională);

• baza de date (database): punctul central al întregii aplicaŃii în ceea ce priveşte stocarea datelor şi comunicarea între componente; se poate observa că prototipul

nostru se depărtează (practic, nu principial) de metodologia SOA prin utilizarea unei baze de date (în locul omniprezentelor servicii web) în ceea ce priveşte comunicaŃia; această alegere a fost motivată de faptul că (potenŃialele) mesaje schimbate între diversele componente prezintă un caracter determinist şi permanent, acestea reprezentând rezultate finale sau intermediare ale clasificării sau procesării; de asemenea utilizarea unei baze de date ca intermediar înlesneşte şi comunicarea asincronă sau în loturi;

• pre-procesor de documente (document loader): transforma documentele în intrări specifice clasificatoarelor (în cazul nostru vectori caracteristici);

• portalul web (web portal): reprezintă una dintre interfeŃele posibile între utilizatorii direcŃi şi componentele sistemului;

Fluxul principal al activitatilor este ilustrat in figura urmatoare.

În vederea preprocesării documentelor s-au utilizat următoarele tehnici:

• transformarea documentelor PDF sau PS în text s-au utilizat unelte deja existente pdftotext şi pstotext;

• determinarea cuvintelor cu ajutorul expresiilor regulate ce considerau cuvinte orice înlănŃuire de cel puŃin 2 litere (mici sau mari);

• extragerea rădăcinilor lexicale; • construirea tabelei de frecvenŃe a rădăcinilor pentru fiecare document; • eliminarea cuvintelor de legătură (stop words), conform unei liste predefinite; • eliminarea rădăcinilor ce apar în mai puŃin de 0.5% (1/200) din documente

(deoarece ar putea genera mai mult de 200 de categorii;) • eliminarea rădăcinilor ce apar în mai mult de 20% (1/5) din documente

(deoarece nu ar putea determina (distinge) decât maxim categorii;)

Ultimele doua reguli de eliminare au fost determinate experimental, având în vedere balansarea, pe de-o parte, a reducerii numărului de caracteristici (ce influenteaza viteza de execuŃie a clasificatorului), iar, pe de altă parte, păstrarea unui număr suficient de caracteristici cu entropie mare (ce influenteaza acurateŃea clasificatorului). Astfel s-a redus cu până la 80% dimensiunea vectorilor caracteristici.

Clasificatorul implementat a fost testat atat pentru seturi de test clasice (CISI, CRAN, Medline, News, Reuters) cat si pentru o colectie proprie de articole in format PDF si PS din domeniul calculului evolutiv. Comportarea algoritmului ART adaptat pentru clasificarea documentelor a fost comparata cu comportarea algoritmului k-means.

Studiul de caz efectuat a condus la urmatoarele observatii:

• atât varianta clasică cât şi cea adaptată a algoritmului ART este comparabilă cu K-means (in conditiile in care in varaianta bazata pe ART nu se indica aprioric numarul de categorii);

• varianta adaptata se dovedeşte puŃin mai bună decât cea clasică (datorită luării în considerare a măsurii de similaritate);

• comportamentul bun al algoritmilor pe colecŃia (CISI+Cran+Med), este explicabil prin faptul ca documentele din colecŃiile în sine sunt foarte diferite în ceea ce priveşte conŃinutul;

• pe de altă parte, pentru colecŃia News20, se observă un comportament mai slab (în ceea ce priveşte indicii de validare externi), deoarece partiŃiile au fost create pe alte considerente decât cele de conŃinut; în cazul de faŃă partiŃiile se identifică cu lista de discuŃii pe care a fost trimis un anumit email, astfel putem observa că toate email-urile în care se vinde (sau cumpără) ceva, algoritmii le pun într-o singură categorie, pe când în listele de discuŃii se află împrăştiate în funcŃie de domeniul produsului (sport, calculatoare, etc.)

• rezultatele obtinute pe colectia locala de documente bibliografice din domeniul calculului evolutiv este incurajatoare.

1.6. Anexe (documentatie de executie, caiet de sarcini, teme de proiectare, buletine de incercari, atestari, certificari, etc. – dupa caz);

Lucrarile realizate in cadrul temei de cercetare sunt atasate (intr-un document aditional in format pdf).

1.7. Concluzii

Cercetarile efectuate au vizat aspecte esentiale ale studiului complexitatii. Mecanismele complexitatii au fost abordate din perspective diferite in incercarea de a stabili noi concepte, modele si teorii care sa aduca un plus de intelegere si de eficienta.

Au fost propuse mai multe abordari noi. Au fost introduse noi concepte si tehnici inspirate de legatura dintre complexitate si optimizare.

Experimentele numerice si studiile de caz evidentiaza potentialul modelelor propuse. Putem aprecia ca aceste rezultate reprezinta o contributie semnificativa- acceptata si validata ca atare de comunitatea stiintifica nationala si internationala.

Studiile de caz efectuate au identificat o serie de probleme complexe care reprezinta provocari pentru meta-euristicile inspirate de natura, si anume:

• Identificarea tuturor optimelor in cazul problemelor de optimizare cu functii obiectiv puternic neseparabile si cu numar mare de optime

• Efectuarea de predictii in serii de timp cu discontinuitati • extragerea cunostintelor din date descrise printr-un numar mare de atribute de

tipuri diferite, afectate de zgomot si/sau incomplete • modelarea retelelor de reglare in sistemele biologice • organizarea automata a colectiilor mari de documente electronice

In vederea rezolvarii problemelor de optimizare de dimensiuni mari au fost identificate ca strategii potentiale cele bazate pe cooperare si coevolutie.

1.8. Bibliografie

1.8.1 Lucrari publicate in cadrul fazei de catre echipa proiectului

UBB/CO

David Iclanzan and D. Dumitrescu, (Iclanzan, Dumitrescu, 2007), Overcoming hierarchical difficulty by hill-climbing the building block structure. In Dirk Thierens et al., editor, GECCO ’07: Proceedings of the 9th annual conference on Genetic and Evolutionary

Computation, volume 2, pages 1256–1263, London, 7-11 July 2007. ACM Press. ISBN 978-1-59593-697-4. URL http://www.cs.bham.ac.uk/wbl/biblio/gecco2007/docs/p1256.pdf. 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), 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. ISBN 978-1-60558-130-9. http://doi.acm.org/10.1145/1389095.1389173. 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.

Catalin Stoean, Mike Preuss, Ruxandra Stoean, D. Dumitrescu, (Stoean et al, 2008), EA-Powered Basin Number Estimation by Means of Preservation and Exploration, Parallel Problem Solving from Nature – PPSN X, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, vol. 5199, pp 569-578, 2008, ISBN 978-3-540-87699-1.

Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, (Stoean et al, 2008a), An Evolutionary Emulator to Support Vector Machines for Classification and Regression, Journal of the Operational Research Society (ISI journal), accepted 2008. Ruxandra Stoean, Mike Preuss, Catalin Stoean, Elia El-Darzi, D. Dumitrescu, (Stoean et al, 2008b), An Evolutionary Approximation for the Coefficients of Decision Functions within a Support Vector Machine Learning Strategy, Foundations on Computational Intelligence, Book Chapter in Studies in Computational Intelligence Series, Springer, accepted 2008. Ruxandra Stoean, Catalin Stoean, D. Dumitrescu, (Stoean et al, 2008c), Shifting from Radius-Centered Separation to Local Landscape Topology-Based Partition into Subpopulations within Crowding Genetic Chromodynamics, 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2008.

C. Chira, C.-M. Pintea, D. Dumitrescu, (Chira et al, 2008), Stigmergy and Sensitivity in Heterogeneous Agent-Based Models, Workshop on Natural Computing and Applications, Proceedings of the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2008), September 26-29,Timişoara, Romania, 2008, p.13-17. C. Chira, A. Gog, D. Dumitrescu, (Chira et al, 2009), Distribution, collaboration and

coevolution in asynchronous search, Proceedings of the International Symposium on Distributed Computing and Artificial Intelligence (DCAI 2008), Salamanca, Spain, Advances in Soft Computing , Vol. 50, 2009, p.596-604. A. Gog, C. Chira, D. Zaharie, D. Dumitrescu, (Gog et al, 2008a), Analysis of a Distributed

Collaborative Evolutionary Algorithm, Workshop on Natural Computing and Applications, Proceedings of the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2008), Timişoara, Romania, September 26-29, 2008, p. 25-32. A. Gog, C. Chira, D. Dumitrescu, (Gog et al, 2008b), Hybrid Multi-Population

Collaborative Asynchronous Search. Proceedings of the 3rd International Workshop on Hybrid Artificial Intelligence Systems (HAIS 2008), Burgos, Spain, September 24-26, Lecture Notes in Artificial Intelligence 5271, Springer, 2008, p. 148-155 A. Gog, C. Chira, D. Dumitrescu, D. Zaharie, (Gog et al, 2008c) Analysis of Some Mating

and Collaboration Strategies in Evolutionary Algorithms, Proc. of SYNASC 2008, IEEE Computer Science. Diosan L., Dumitrescu D., Evolutionary coalition formation in full connected and scale free networks, INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, 3, 259-264, 2008 (ISI journal) UVT/P1 E. Kaslik, S. Balint, (Kaslik, Balint, 2008a) Bifurcations in Discrete-Time Delayed Hopfield

Neural Networks of Two Neurons. In V. Kurkova, R. Neruda, and J. Koutnik (Eds.): Proceedings of ICANN 2008, Part II, LNCS 5164. Springer-Verlag Berlin Heidelberg, 2008, 655-664.

E. Kaslik, S. Balint, (Kaslik, Balint, 2008b) Dynamics of Two-Dimensional Discrete-Time Delayed Hopfield Neural Networks, chapter in : Xiaolin Hu and P. Balasubramaniam (eds), Recurrent Neural Networks, ISBN 978-953-7619-08-4, IN-TECH, 2008, 343-356.

E. Kaslik, S. Balint, (Kaslik, Balint, 2008c) Complex and chaotic dynamics in a discrete-time delayed Hopfield neural network with ring architecture, raport de cercetare, iulie 2008, submisa pentru publicare (in curs de evaluare). M. Nicoara, (Nicoara, 2008) Comparative analysis of some metaheuristics inspired by nature, Master thesis, Universitatea de Vest din Timisoara, iulie 2008. D. Zaharie, (Zaharie, 2008a) Statistical properties of differential evolution and related random search algorithms, invited paper, in Paula Brito (ed.) Proceedings of International Conference on Computational Statistics Porto, Portugal, August 24-29, Physica-Verlag HD, ISBN978-3-7908-2083-6, pg. 473-485, 2008. D. Zaharie, (Zaharie, 2008b) Influence of Crossover on the Behavior of Differential Evolution Algorithms, acceptata cu modificari minore pentru publicare in Applied Soft Computing, 2009.

M. Darau, E. Kaslik, S. Balint, (Darau, Kaslik, Balint 2008) Cryptography using chaotic discrete-time Hopfield neural networks with delays, Mathematical Problems in Engineering, Aerospace and Sciences, June 25-27, 2008, University of Genoa, Italy L. Braescu, T. F. George, C. Orbulescu and M. Leretter, (Braescu, 2008) Dynamics of Thrombin Formation Using a Mathematical Model Including Both Intrinsic and Extrinsic Pathways of Blood Coagulation, Conf. on Differential Equations and Dynamical Systems, 22.05.08-26.05.08, Baltimore, USA, acceptata pentru publicare in Dynamics of Continuous, Discrete and Impulsive Systems (Series A) C. Craciun, (Craciun, 2008) Unsupervised document clustering with ART, Summer School on Neural Networks, 7-11 iulie 2008, Porto IeAT/P2

A. Percus, G. Istrate, B. Goncalves, R. Sumi, S. Boettcher, (Percus, Istrate et al. 2008) The peculiar phase structure of Random Graph Bisection, Journal of Mathematical Physics vol. 49, issue 12, Decembrie 2008. SPECIAL ISSUE: STATISTICAL MECHANICS ON RANDOM STRUCTURES. (ISI Journal, Impact Factor 1.14). DOI 10.1063/1.3043666.

G. Istrate, (Istrate 2009) On the dynamics of Social Balance on general networks (with

an application to XOR-SAT), Fundamenta Informaticae (acceptat), prevazut pentru apartie in Aprilie 2009. (ISI Journal, Impact Factor 0.69). Varianta preliminara disponibila ca preprint 0811.0381, arXiv.org. G. Istrate, (Istrate 2008a) Dissecting the Artificial: the Adversarial Scheduling Approach

to Validating Game-Theoretic Models and Social Simulations, in Flaminio Squazzoni (editor), Proceedings of the Fifth Conference of the European Social Simulation Association (ESSA’08), Brescia, Italia, 1-5 Septembrie 2008. G. Istrate, (Istrate 2008b) Grammatical Inference and Symbolic Dynamics (extended abstract), Fifth European Conference on Complex Systems (ECCS’08), Ierusalim, Israel, 14-19 Septembrie 2008. G. Istrate, (Istrate 2008c) Stochastic Stability in Schelling’s Segregation Model with Contagion (extended abstract), Fifth European Conference on Complex Systems (ECCS’08), Ierusalim, Israel, 14-19 Septembrie 2008. G. Istrate (Istrate 2008d) Geometric properties of satisfying assignments of random ε-1-

in-k SAT, trimisa spre publicare la International Journal of Computer Matematics. De asemenea preprint 0811.3116, arXiv.org G. Istrate, M.V. Marathe, S.S. Ravi (Istrate et al 2008) Adversarial Scheduling in

Evolutionary Game Dynamics, trimisa spre publicare la Advances in Complex Systems. De asemenea preprint 0812.1194, arXiv.org

UAIC/P3

M. Breaban, S. Luchian, Shaping Up Clusters with PSO. Proceedings of the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2008), Timisoara, 2008, pg. 48-55. M. Breaban, L. Alboaie, H. Luchian, Guiding Users within Trust Networks Using Swarm

Algorithms. Submitted to CEC 2009 (Congress of Evolutionary Computation).

A. Bautu, E. Bautu, H. Luchian, Searching Ground States of Ising Spin Glasses with a

Tree Bond-Based Representation. Proceedings of the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2008), Timisoara, 2008, pg. 33-39. E. Bautu, A. Bautu, H. Luchian, An Evolutionary Approach for Modelling Time Series. Proceedings of the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2008), Timisoara, 2008, pg. 68-75. E. Bautu, S. Kim, A. Bautu, H. Luchian, B.T. Zhang, Evolving Hypernetwork Models of

Binary Time Series for Forecasting Price Movements on Stock Markets. Submitted to CEC 2009 (Congress of Evolutionary Computation). 1.8.2 Alte referinte

Martin Pelikan, David E. Goldberg, and Erick Cantú-Paz, (Pelikan et al, 2000), Bayesian optimization algorithm, population sizing, and time to convergence. In L. Darrell Whitley, David E. Goldberg, Erick Cantú-Paz, Lee Spector, Ian C. Parmee, and Hans-Georg Beyer, editors, GECCO, pages 275–282. Morgan Kaufmann, 2000. ISBN 1-55860-708-0. Kumara Sastry, David E. Goldberg, and Xavier Llora, (Sastry et al, 2007), Towards billion-bit optimization via a parallel estimation of distribution algorithm. In GECCO ’07:

Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 577–584, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-697-4. http://doi.acm.org/10.1145/1276958.1277077. Tian-Li Yu, Kumara Sastry, David E. Goldberg, and Martin Pelikan, (Yu et al, 2007), Population sizing for entropy-based model building in discrete estimation of distribution algorithms. In Hod Lipson, editor, GECCO, pages 601–608. ACM, 2007. ISBN 978-1-59593-697-4. URL http://doi.acm.org/10.1145/1276958.1277080. J. Kennedy, R.C. Eberhart, Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks, Piscataway, 1995. A. Abraham, S. Das, S. Roy, Swarm Intelligence Algorithms for Data Clustering, Soft Computing for Knowledge Discovery and Data Mining, Springer Verlag, 2007. J. Brest, B. Boskovic, S. Greiner, V. Zurner and M.S. Maucec, (Brest et al., 2005) Performancecomparison of self-adaptive and adaptive differential evolution algorithms, Soft Computing, 11, issue 7 (2007) 617 - 629. A. Qin and P. Suganthan (Qin et al., 2007): Self-adaptive Differential Evolution for Numerical Optimization, in: Proceedings of CEC 2005, (IEEE Computer Press, 2005) vol. 1, 630-636. Geem, Z. W., Kim, J., Loganathan, G., (Geem et al., 2001) A New Heuristic Optimization Algorithm: Harmony Search, Simulation, 76(2), pp. 60-68, 2001. T. Gong, A. Tuson, (Gong, Tuson, 2007) Differential Evolution for Binary Encoding.In: Soft Computing in Industrial Applications, (Springer-Verlag,2007) vol. 39, 251-262, 2007. Yang, Z., Tang, K., Yao, X., (Yang et al., 2007) Differential evolution for high-dimensional function optimization, 2007 IEEE Congress on Evolutionary Computation(CEC 2007), pp. 3523-3530, 2007.

E. Mezura-Montes, J. Vel\asquez-Reyes and C.A. Coello Coello, (Mezura et al., 2006) A Comparative Study of Differential Evolution Variants for Global Optimization, in: Maarten Keijzer et al., eds., 2006 Genetic and Evolutionary Computation Conference (GECCO'2006), Vol. 1, (ACM Press,2006) 485-492. Hisao Ishibuchi, Noritaka Tsukamoto, Yasuhiro Hitotsuyanagi, Yusuke Nojima (Ishibuchi et al., 2008) Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. GECCO 2008: 649-656. D. Zaharie, D. Lungeanu, F. Zamfirache, (Zaharie et al., 2008) Interactive Search of Rules in Medical Data Using Multiobjective Evolutionary Algorithms, in Proceedings of the 2008 GECCO Conference Genetic and Evolutionary Computation (workshop MedGEC--medical applications of genetic and evolutionary computation), Atlanta august 2008, ISBN:978-1-60558-131-6, pg. 2065-2072, 2008 Kukkonen, S., Deb, K., (Kukkonen et al., 2007) An Empirical Scalability Study of A Non-Dominated Solutions Pruning Algorithm, The 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Late Breaking Papers Proceedings, Matsushima, Japan, March, 2007, pp. 69-74, 2007. W. Yu, J. Cao. (Yu, Cao, 2006) Cryptography based on delayed chaotic neural networks. Physiscs Letter A, 356, 333-8, 2006. Xue, F., Sanderson, A.C. and Graves, R.J..(Xue, 2005) Multi-objective differential evolution - algorithm, convergence analysis and applications. In: Proceedings of CEC 2005, IEEE Computer Press, 743-750, 2005.