METODE GENETICE DE OPTIMIZARE MULTIOBIECTIV Rezumatul ...

larul PO.CSUD.01-F1

UNIVERSITATEA TEHNICĂ “GHEORGHE ASACHI” DIN IAŞI

METODE GENETICE DE OPTIMIZARE

MULTIOBIECTIV

Rezumatul tezei de doctorat

Ing. Corina Agrigoroaie (căs. Cîmpanu)

Conducător de doctorat : Prof.dr.ing. Vasile-Ion Manta

Promotor: Conf.dr.ing. Lavinia-Eugenia Ferariu

IAŞI, 2018

Cuprins

1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Obiective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. Contribuții, lucrări publicate și diseminarea rezultatelor . . . . . . . . . . . . . . . 5

1.3. Structura tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2. Metode evolutive de optimizare multiobiectiv . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3. Metode de grupare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de

planificare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

4.1. Configurarea algoritmilor genetici pentru planificarea rutei optimale . . . . . 20

4.2. Algoritm genetic multiobiectiv cu clasificare pe ranguri folosind clustere și

cu controlul direct al diversității [MOO-DB] . . . . . . . . . . . . . . . . . . . . . . . .

23

4.3. Schemă genetică de asignare a valorilor fitness aplicată în problema

planificării traiectoriei unui robot [MOO-AR] . . . . . . . . . . . . . . . . . . . . . . .

24

4.4. Metodă evolutivă multiobiectiv de planificare a traiectoriei unui robot mobil

cu clasificare adaptivă pe ranguri Pareto folosind cromozomi de lungime

variabilă [MOO-ARCCP] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.5. Schemă genetică adaptivă de asociere a rangurilor Pareto bazată pe

clusterizare [MOO-ARC] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.6. Metodă hibridizată de asociere a rangurilor Pareto prin intermediul

algoritmului lui Dijkstra multiobiectiv [MOO-ARCP] . . . . . . . . . . . . . . . . .

29

4.7. Rezultate experimentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția

atributelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

5.6. Selecția atributelor EEG în seturi de date de dimensiune foarte mare.

Procedură genetică de optimizare multiobiectiv bazată pe comutarea între

clasificatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

5.7. Procedură evolutivă configurată dinamic pentru selecția de trăsături bazată

pe utilizarea extensiilor temporale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

5.8. Sistem fuzzy pentru selecția genetică a trăsăturilor EEG în seturi de date de

dimensiune foarte mare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

5.9. Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6. Concluzii generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.1. Contribuții algoritmice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.2. Investigații experimentale și analiza datelor . . . . . . . . . . . . . . . . . . . . . . . . . 47

Lista publicațiilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Referințe bibliografice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3

Capitolul 1

Introducere

Majoritatea aplicațiilor inginerești sau industriale presupun soluționarea unor probleme de

optimizare multiobiectiv ce urmăresc optimizarea simultană a mai multor funcţii obiectiv.

Comparativ cu problemele de optimizare mono-obiectiv care pot admite şi o singura soluţie de

optim sau un număr finit de soluţii de optim, optimizările multiobiectiv ale unor obiective

conflictuale conduc implicit la obținerea unui număr infinit de soluții optime, numite Pareto

optimale, fiecare din ele indicând un posibil consens între obiectivele considerate. Reprezentarea

acestor soluții în spațiul obiectiv reprezintă frontul optimal.

În rezolvarea problemelor de optimizare multiobiectiv, principala dificultate rezultă din

faptul că este posibilă doar o ordonare parţială a soluţiilor. Ordonarea soluţiilor în funcţie de gradul

lor de adaptare conduce implicit la subseturi de soluţii asociate cu acelaşi rang, i.e. cu acelaşi grad

de adaptare. Schemele de asociere a rangurilor pot include şi preferinţe suplimentare, extrase din

mecanismul decizional. Aceste modificări trebuie însă gestionate astfel încât să evite orientarea

prematură a explorării către o anumită preferință.

Scopurile principale ale unei metode de optimizare multiobiectiv sunt obținerea unor

aproximări cât mai bune pentru frontul optimal și distribuirea bună a soluțiilor de-a lungul acestuia.

Între abordările propuse în literatură, algoritmii metaeuristici se evidențiază prin avantaje precum

capacitate de explorare, capacitate de adaptare și simplitatea operațiilor. Metaeuristicile sunt

strategii care permit rezolvarea problemelor de căutare şi optimizare. Algoritmii evolutivi sunt

metaeuristici ce simulează evoluția naturală.

Algoritmii evolutivi de optimizare multiobiectiv sunt recomandați în rezolvarea

problemelor de optimizare multiobiectiv cu obiective conflictuale. Lucrând pe multiple de soluţii

la fiecare iteraţie, aceștia s-au remarcat prin robusteţe, conducând la rezultate foarte bune în diverse

aplicaţii. Particularitatea lor de a lucra cu o populație de indivizi permite găsirea unui set de soluții

distribuite în apropierea setului Pareto, dintr-o singură rulare. Considerând cele anterior amintite,

algoritmii genetici multiobiectiv trebuie proiectaţi astfel încât să îndeplinească simultan cerinţele

principale: să aproximeze frontul Pareto utilizând un mecanism evolutiv de căutare și să asigure

diversitatea soluţiilor mai bine adaptate. A doua cerinţă este cel mai adesea rezolvată utilizând

tehnici specifice precum partajarea sau gruparea.

1.1. Obiective

Obiectivul general al acestei teze îl reprezintă dezvoltarea unor algoritmi genetici de

optimizare multiobiectiv și investigarea utilității acestora în rezolvarea unor probleme care implică

variaţia intensităţii conflictului dintre obiective. Pentru investigarea adecvată a metodelor propuse

au fost considerate două aplicații: determinarea traiectoriei optime pentru un robot mobil pe o

scenă de lucru cu obstacole și selecția de trăsături relevante pentru clasificarea semnalelor EEG

pentru determinarea nivelului de încărcare cognitivă.

Pentru atingerea obiectivului propus, lucrarea tratează următoarele aspecte:

1. Introducere

4

Ilustrarea principalelor noțiuni teoretice relaționate cu problema optimizării multiobiectiv

abordată folosind metode evolutive;

Ilustrarea principalelor noțiuni teoretice și a noutăților în domeniul algoritmilor de

clasificare supervizată sau nesupervizată;

Dezvoltarea unor metode genetice de optimizare multiobiectiv a traiectoriei unui robot

mobil pentru o scenă de lucru fixă, cu obstacole multiple, cu formă convexă sau concavă,

prin:

o Dezvoltarea unor algoritmi adaptivi pentru asocierea rangurilor Pareto, care să asigure

control direct asupra diversității indivizilor din populație şi integrarea progresivă a

preferinţei pentru mijlocul celor mai bune fronturi Pareto:

. Dezvoltarea unei metode evolutive de optimizare multiobiectiv bazată pe

ordonarea potențialelor soluții printr-o grupare adaptivă care să conducă

procesul de căutare spre soluţiile preferate situate la mijlocul fronturilor Pareto;

. Dezvoltarea unei scheme de asociere a rangurilor bazate pe gruparea soluțiilor

în funcție de punctul nadir difuz și de valorile medii ale funcţiilor obiectiv

considerate;

. Analiza distribuției soluțiilor pe baza unei grupări nesupervizate a populaţiei în

spaţiul obiectiv, urmate de asocierea rangurilor Pareto în funcție de centrii

grupurilor rezultate;

. Dezvoltarea unor metode de conservare sau ameliorare a diversităţii soluţiilor

bazate pe definirea unui obiectiv suplimentar sau ajustarea rangurilor pe

subseturi consecutive de fronturi.

o Crearea unor proceduri de generare a populației inițiale care să susțină optimizarea

multiobiectiv plecând de la indivizi de lungime fixată generați aleator, ameliorând

calitatea materialului genetic prin proceduri de optimizare locală mono-obiectiv

o Gestionarea unei populații de indivizi cu lungime variabilă prin intermediul unor

operatori specifici;

. Configurarea unor operatori genetici care să permită utilizarea unor cromozomi

de lungime variabilă;

o Dezvoltarea unor algoritmi de corecţie a indivizilor care încalcă restricţiile, folosind

triangularizări Delaunay şi algoritmul Dijkstra:

. Definirea algoritmilor în sens mono-obiectiv.

. Extensia algoritmului Dijkstra în sens multiobiectiv şi integrarea lui în

algoritmul de corecţie a soluţiilor, pentru rezolvarea restricţiilor asociate

traiectoriilor robotului;

Dezvoltarea unor algoritmi genetici de optimizare multiobiectiv adecvați selecției

atributelor pentru clasificarea nivelelor de încărcare cognitivă, utilizând semnale de tip

ElectroEncefaloGramă (EEG) și teste de încărcare a memoriei:

o Analiza nivelelor de încărcare cognitivă folosind semnale EEG și teste de memorie de

tip n-back sau aritmetice, pentru diferite tipuri de clasificatori sau indicatori statistici;

o Verificarea compatibilității între dispozitive de achiziție EEG diferite pentru un set

restrâns de atribute EEG;

o Analiza nivelelor de încărcare a memoriei de lucru pentru selecția atributelor EEG;

o Dezvoltarea unor metode de optimizare mono-obiectiv şi multiobiectiv pentru selecția

atributelor EEG relevante din seturi EEG de dimensiune foarte mare și cuprinzând

numeroase atribute:

1. Introducere

5

o selecţia trăsăturilor implicând un singur tip de clasificator;

o selecţia trăsăturilor prin comutare între două tipuri de clasificatori;

o selecția trăsăturilor folosind metode genetice de optimizare multiobiectiv

configurate dinamic pentru seturi de trăsături EEG cu extensie temporală;

o selecţia trăsăturilor prin eliminarea graduală a atributelor nerelevante cu

ajutorul unui sistem fuzzy.

1.2. Contribuții, lucrări publicate şi diseminarea rezultatelor

Rezultatele activității de cercetare au fost diseminate în 23 de lucrări (20 publicate și 3 în

curs de elaborare) înscrise în următoarele categorii:

2 lucrări au fost publicate într-o revistă cotată CNCSIS B+;

2 lucrări publicate într-o revistă OpenAccess și indexate de CEEOL;

11 lucrări au fost publicate în volumele unor conferințe internaționale, dintre care:

o 9 indexate în IEEE Xplore din care 6 fiind indexate ISI Proceedings;

o 2 publicate de Advanced Distributed Learning Association (ADLA);

4 lucrări au fost prezentate în cadrul unor conferințe naționale;

1 lucrare sub formă de poster a fost prezentată în cadrul conferinţei unei școli internaționale

de vară;

2 lucrări acceptate pentru a fi prezentate și publicate în volumul unei conferințe indexate

în IEEE Xplore ISI Proceedings;

1 lucrare în curs de elaborare pentru publicare în cadrul unei reviste ISI;

2 lucrări în curs de elaborare pentru publicare în cadrul unei reviste cotate CNCSIS B+.

Principalele direcții de cercetare prezentate în această teză vizează noi metode de asociere

a rangurilor Pareto în cadrul procedurilor evolutive de optimizare multiobiectiv, respectiv noi

metode genetice de optimizare multiobiectiv pentru selecția de trăsături relevante în cadrul

clasificării supervizate. Metodele de asociere a rangurilor Pareto propuse presupun ca gruparea

nesupervizată a soluțiilor în spațiul obiectiv să încorporeze specificațiile factorului decizional. De

asemenea acestea trebuie să țină cont de dimensiunea spațiului explorat pentru identificarea unei

soluții, precum și de calitatea rezultatelor și capacitatea de generalizare oferită de un clasificator

în general.

Gruparea nesupervizată a tiparelor reprezintă o problemă de cercetare actuală, principalele

dificultăți fiind legate în special de faptul că gruparea trebuie realizată în absența unor informații

a priori despre modul de grupare, uneori chiar fără a ști numărul de categorii relevante. (Cîmpanu

& Ferariu, 2012) analizează cele mai importante abordări în domeniu. Algoritmii propuşi în lucrări

de dată recentă sunt comparați cu cei clasici (bazați pe tehnici de grupare asemănătoare), ilustrând

cu această ocazie principalele aspecte care ar putea fi îmbunătățite ulterior. De asemenea, a fost

discutată oportunitatea folosirii tehnicilor evolutive în rezolvarea problemelor de grupare

nesupervizată și sunt oferite câteva exemplificări ilustrative în acest sens în:

C. Cîmpanu, L. Ferariu, Survey of Clustering Algorithms, Buletinul Institutului

Politehnic din Iasi, Tome LVIII(LXII), Fasc. 3, pp. 23-42, AUTOMATIC CONTROL

and COMPUTER SCIENCE Section, Iași, România, 2012, CNCSIS B+.

Clasificarea supervizată a semnalelor de tip EEG în cadrul sistemelor BCI (“Brain-

Computer Interface” – engl.; [sistem de interfațare creier-calculator]) reprezintă de asemenea o

1. Introducere

6

direcție de cercetare deschisă. Pentru clasificarea nivelelor de încărcare cognitivă sau a activității

memoriei de lucru, au fost folosite tehnici de clasificare: SVM (”Support Vector Machine” – engl.;

[metode bazate pe vectori suport]) și RF (“Random Forest” – engl.; [păduri de arbori de decizie

generați aleator]). Performanța unui proces de învățare (fie acesta un sistem standard, e-learning

sau mediu virtual) este asociată cu încărcarea cognitivă și cu activitatea memoriei de lucru.

Memoria pe termen scurt reprezintă capacitatea de a reține multiple fragmente informaționale pe

parcursul rezolvării unei probleme. Pe durata utilizării memoriei de lucru, regiunile frontale și

prefrontale ale creierului devin foarte active. S-a demonstrat de asemenea că lobilor frontali le sunt

asociate funcții cognitive de nivel superior, cum ar fi gândirea, analizarea și luarea de decizii.

Uneori, inclusiv apelul anumitor funcții decizionale de nivel înalt este asociat cu cortexul pre-

frontal. Scopul urmărit de (Ungureanu et. Al, 2017) este de a studia și evalua diverse abordări

pentru identificarea și clasificarea nivelelor de încărcare cognitivă și ale memoriei de lucru pe

parcursul unei activități de învățare. Datele înregistrate au fost preprocesate pentru eliminarea

artefactelor și filtrate pentru a extrage formele de undă (Delta, Theta, Alpha, Beta și Gamma) ce

compun un semnal EEG în vederea analizării lor ulterioare, dar și pentru clasificare. Pentru fiecare

formă de undă studiată, atât funcția spectrală cât și anvelopele semnalului au fost calculate pentru

starea de relaxare dar și pentru diverse niveluri de încărcare a memoriei utilizând teste n-back sau

efectuând simple operații aritmetice (Ungureanu et al., 2017). Rezultatele obținute au fost

prezentate în:

F. Ungureanu, C. Cîmpanu, T. Dumitriu, V.I. Manta, Cognitive Load and Short Term

Memory Evaluation Based on EEG Techniques, The 13th eLearning and Software for

Education Conference, ELSE 2017, vol. 2, pp. 217-224, ISSN: 2066-026X, ISSN-L:

2066-026X, ISSN CD: 2343-7669, April 27-28, Bucharest, Romania, 2017, Published

by ADLA, CEEOL Indexed Journal Article, OpenAccess.

Identificarea unui anumit nivel de încărcare cognitivă utilizând semnale EEG reprezintă un

domeniu de cercetare activ și ofertant. Dezvoltarea echipamentelor de achiziție EEG wireless a

atras atenția cercetătorilor din domeniul sistemelor colaborative de tip om-mașină. În cadrul acestei

lucrări, două tipuri de metode de clasificare sunt utilizate pentru a diferenţia nivelele de încărcare

ale memoriei de scurtă durată utilizând înregistrări EEG. Undele cerebrale au fost achiziționate cu

ajutorul unor experimente de încărcare a memoriei de tip teste n-back. Selectarea atributelor

potrivite pentru a putea identifica cu acuratețe nivelul de încărcare al memoriei rămâne o problemă

dificil de rezolvat pentru o gamă variată de aplicații practice. Semnalele EEG preprocesate sunt

clasificate cu ajutorul unor algoritmi recomandați pentru clasificarea semnalelor non staționare.

Experimentele propuse ghidează o selecție empirică a trăsăturilor EEG și corelează clasificarea

tiparelor EEG pentru anumite niveluri de încărcare a memoriei între diverse dispozitive de achiziție

a datelor EEG. Comparația vizează o cască profesională de achiziție date EEG de la Brain Products

și un echipament de achiziție date EEG cu cost scăzut și conexiune wireless de la Emotiv, Emotiv

Epoc+. Rezultatele demonstrează impactul clasificatorilor multi-clasă RF și SVM în selecția

atributelor pentru clasificarea semnalelor EEG în funcție de tipul activității n-back. Această lucrare

evidențiază însă și câteva dezavantaje ale echipamentelor EEG wireless. Rezultatele obținute

sugerează că atât RF cât și SVM obțin performanțe foarte bune aplicați în clasificarea de tipare

EEG. Nivelele de încărcare a memoriei de scurtă durată pot fi identificate precis folosind RF și

activând un set limitat de electrozi din regiunea frontală pentru semnalele achiziționate cu ajutorul

ambelor dispozitive:

1. Introducere

7

C. Cîmpanu, F. Ungureanu, T. Dumitriu, V.I. Manta, A Comparative Study on

Classification of Working Memory Tasks Using EEG Signals, The 21th International

Conference on Control Systems and Computer Science, CSCS21, pp. 245-251, ISSN:

2379-0482, May 29-31, Bucharest, Romania, 2017, IEEE Conference Proceedings.

Clasificarea supervizată a semnalelor EEG poate fi foarte utilă și în cazul proiectării unei

proceduri educative. Procedeul instrucțional este proiectat adeseori pe baza teoriei legate de

încărcarea cognitivă. Percepția umană asupra cunoașterii poate fi descrisă ca un sistem nativ de

procesare a informației care a evoluat împreună cu specia umană. Există și un aspect critic de care

trebuie ținut cont și anume, sistemul cognitiv uman nu evoluează în mod explicit pentru a învăța

tematici care să necesite cunoștințe specifice domeniului. Această particularitate este relaționată

direct cu capacitatea memoriei de lucru și este imperios necesară pentru dezvoltarea unei

arhitecturi relevante pentru proiectarea cadrului instrucțional. Ținând cont că memoria de lucru se

activează pe plan secundar ca proces de stocare a cunoștințelor specifice unui anumit domeniu,

încărcarea cognitivă poate fi utilizată pentru a calibra încărcarea memoriei de lucru pe parcursul

procesului educațional.

Scopul cercetării prezentate în (Cîmpanu et al., 2018a) este de a evalua și analiza diferite

modalități de clasificare și identificare a nivelelor de încărcare cognitivă corespunzătoare activității

memoriei de lucru pe parcursul activității de învățare, în condiții de stres. Pentru realizarea acestor

experimente, s-a propus achiziționarea de semnale EEG, beneficiind de intuitivitatea informațiilor

conținute de acestea referitor la diagnosticarea și prognozarea proceselor relaționate de gândirea

și memoria umană. Rezultatele clasificării semnalelor EEG utilizând metode de clasificare precum

AB (”AdaBoost” – engl.), kNN (”k Nearest Neighbors” – engl. [Clasificare bazată pe cei mai

apropiați k vecini]), clasificatorul Bayesian naiv (”Naive Bayes” – engl.), RF sau SVM sunt

ilustrate în:

C. Cîmpanu, T. Dumitriu, F. Ungureanu, Instructional Design Based on the

Assessment of Cognitive Load and Working Memory Load, The 14th eLearning and

Software for Education Conference, ELSE 2018, vol. 2, pp. 54-61, April 19-20,

Bucharest, Romania, 2018, Published by ADLA, CEEOL Indexed Journal Article,

OpenAccess.

Metodele genetice de optimizare multiobiectiv propuse în această teză sunt aplicate pe două

categorii de probleme: identificarea traiectoriei optimale între două poziţii prestabilite pentru un

robot mobil într-o zonă de lucru cu obstacole și selecția trăsăturilor relevante pentru clasificarea

semnalelor EEG. Problema optimizării traiectoriei liniare pe porţiuni a unui robot mobil presupune

identificarea celei mai rapide rute admisibile între două puncte prestabilite într-o scenă cu

obstacole. Cea mai rapidă dintre rutele admisibile este selectată genetic prin minimizarea simultană

a lungimii traiectoriei și a sumei unghiurilor de viraj. Adeseori, metodele Pareto sunt bazate doar

pe analiza dominanței pentru a oferi o sortare parțială a soluțiilor fără să țină cont de specificitatea

conflictului dintre obiective. Această abordare bazată doar pe analiza dominanței poate genera

efecte negative cum ar fi dispersarea excesivă a soluțiilor prin păstrarea în populaţie a unor soluţii

nedominate, mai puţin utile în practică.

Un algoritm de asociere a rangurilor Pareto prin combinarea progresivă a mecanismelor de

căutare și decizie este prezentat în (Ferariu & Cîmpanu, 2013) și poate fi folosit pentru rezolvarea

problemelor de optimizare multiobiectiv cu un număr redus de obiective. Mai exact, deciziile sunt

implementate progresiv prin intermediul unei grupări adaptive care ghidează căutarea către

1. Introducere

8

mijlocul fronturilor Pareto. Această combinație activează eliminarea graduală a soluțiilor inutile.

Prin monitorizarea continuă a dimensiunii grupurilor de soluţii identificate în spațiul obiectiv,

această procedură este capabilă să detecteze convergența prematură și să intervină pentru a încuraja

sau pentru a menține nivelul diversității în cadrul populației. Pentru a îmbunătăți și pentru a

menține diversitatea soluțiilor, algoritmul activează un obiectiv suplimentar, ori de câte ori este

necesar, cu rolul de a controla în mod direct diversitatea materialului genetic valoros pentru

procedura de explorare. Aplicabilitatea metodei propuse este ilustrată experimental pentru

problema determinării traiectoriei optime pentru un robot mobil pe scene de lucru continue

conținând obstacole disjuncte, cu formă convexă sau concavă în:

L. Ferariu, C. Cîmpanu, Multi-Objective Genetic Algorithm with Clustering-based

Ranking and Direct Control of Diversity, The 17th International Conference on System

Theory, Control and Computing, ICSTCC 2013, pp. 341-346, ISBN 978-1-4799-2228-

4, ISBN 978-1-4799-2227-7, October 11-13, Sinaia, Romania, 2013, ISI Proceedings.

Pentru a preveni eliminarea nedorită a soluțiilor localizate la extremitățile primelor fronturi

Pareto, o nouă modalitate de asociere a rangurilor Pareto aplicată în cadrul unei proceduri genetice

de optimizare multiobiectiv este propusă în (Cîmpanu & Ferariu, 2013). Rangurile sunt asociate

după gruparea soluțiilor din populație, pe baza punctului nadir difuz și a valorilor medii ale

obiectivelor considerate. Această grupare vine în sprijinul sortării parțiale a soluțiilor asigurată de

analiza dominanței și oferă posibilitatea încurajării anumitor soluții valoroase recomandate de

distribuția populației în spațiul obiectiv. În plus, această grupare preliminară permite eficientizarea

controlului diversității pe parcursul buclei evolutive. Eficiența schemei de alocare a valorilor

fitness este demonstrată pentru problema planificării traiectoriei optime a unui robot mobil.

Studiile de caz iau în considerare scene de lucru continue cu obstacole convexe/ non-convexe în:

C. Cîmpanu, L. Ferariu, Genetic Multiobjective Fitness Assignment Scheme Applied

to Robot Path Planning, Proceedings of the 10th International Conference On

Electronics Computer And Computation, ICECO 2013, pp. 196-199, ISBN: 978-605-

4894-00-0, November 7-9, Ankara, Turkey, 2013, ISI Proceedings.

Metodele de optimizare anterior enumerate s-au confruntat cu dezavantajul unui spațiu de

căutare vast și de limitarea capacității de explorare prin utilizarea cromozomilor de lungime fixă,

precum și de inexistența unor proceduri care să corecteze soluțiile penalizate deoarece nu asigurau

ocolirea obstacolelor. În (Ferariu & Cîmpanu, 2014a) o nouă procedură de asociere a rangurilor

asigură o modalitate adaptivă progresivă de a combina mecanismele de căutare cu cele decizionale

în funcție de distribuția soluțiilor în spațiul obiectiv. Materialul genetic este conservat prin

aplicarea unui mecanism de control adaptiv al diversității în cadrul populației, ori de câte ori este

nevoie. Algoritmul genetic lucrează pe cromozomi de lungime variabilă, fiind definit un operator

de încrucișare compatibil care să evite producerea copiilor cu lungime superioară părinților.

Traiectoriile care încalcă restricţia sunt reparate și scurtate prin intermediul unui algoritm de

corecție. Această corecție este aplicată o singură dată pentru fiecare cromozom și are rolul

principal de a ghida mecanismul genetic de căutare către regiunile admisibile din spațiul de

căutare. Experimentele demonstrează eficiența metodelor propuse pentru diferite scene de lucru

conținând o varietate de amplasamente pentru obstacole după cum se poate urmări în detaliu în:

L. Ferariu, C. Cîmpanu, Multiobjective Hybrid Evolutionary Path Planning with

Adaptive Pareto Ranking of Variable-Length Chromosomes, The IEEE 12th

International Symposium on Applied Machine Intelligence and Informatics, SAMI

1. Introducere

9

2014, pp. 23-28, ISBN: 978-1-4799-3441-6, January 23-25, Herl’any, Slovakia, 2014,

ISI Proceedings.

În (Ferariu & Cîmpanu, 2014b) traiectoriile sunt definite în cadrul unor scene continue

conținând unul sau mai multe obstacole disjuncte cu formă convexă sau non-convexă, pentru un

robot care se deplasează pe traiectorii liniare compuse dintr-un număr variabil de segmente. Pentru

a asigura o sortare parțială eficientă a soluțiilor potențiale, algoritmul genetic utilizează o schemă

auto-adaptivă de asociere a rangurilor Pareto bazată pe gruparea indivizilor și pe analiza

dominanței. Înainte de asocierea rangurilor, toate soluțiile neadmisibile sunt corectate prin

înlocuirea fragmentelor de traiectorie care înregistrează coliziuni cu setul de obstacole. Segmentele

admisibile sunt alese pe baza unor grafuri generate cu triangularizarea Delaunay prin aplicarea

unei noi proceduri de identificare a celei mai rapide rute. Această procedură este derivată din

algoritmul clasic Dijkstra într-o nouă variantă multiobiectiv de asignare a rangurilor. Procedura

este compatibilă cu orice funcție obiectiv neliniară și permite utilizarea aceleiași scheme de alocare

a rangurilor pe parcursul căutării evolutive și a corecției traiectoriilor, garantând astfel respectarea

restricţiei fără a afecta semnificativ demersul evolutiv de căutare. Algoritmul propus poate fi de

asemenea folosit în rezolvarea oricărei probleme de planificare bazată pe grafuri și care necesită

optimizarea oricărui număr de obiective. Experimentele au demonstrat utilitatea tehnicilor sugerate

pe scene de lucru cu diferite configurații de obstacole în:

L. Ferariu, C. Cîmpanu, Pareto-Evolutionary Path Planning Hybridized with

Multiobjective Dijkstra’s Algorithm, The 18th International Conference on System

Theory, Control and Computing, ICSTCC 2014, October 17-19, Sinaia, Romania,

2014, IEEE Conference Proceedings.

Schema propusă în (Ferariu & Cîmpanu, 2015) pentru asocierea rangurilor Pareto este

folosită pentru selectarea părinților și a supraviețuitorilor în cadrul procedurii genetice de

optimizare multiobiectiv. Pentru a elimina dezavantajele relaționate cu puterea conflictului dintre

obiective sau cu pierderea diversității, respectiv dispersarea excesivă a soluțiilor, abordarea

propusă adaptează politica de asociere a rangurilor în funcție de distribuția populației în spațiul

obiectiv. O primă inovație propusă în această lucrare este legată de examinarea distribuției

soluțiilor. Această analiză este bazată pe grupare nesupervizată, urmată de asocierea rangurilor

Pareto cu centrii rezultați. Centrii aparținând celor mai bune fronturi sunt mai apoi folosiți pentru

a desemna zona de căutare preferată și pentru a decide dacă diversitatea soluțiilor necesită

îmbunătățiri. În această privință, o a doua contribuție susține diversificarea soluțiilor preferate prin

intermediul ajustării rangurilor. Algoritmul de ordonare sugerat este validat experimental pe

probleme de optimizare multiobiectiv sintetice și pe problema optimizării multiobiectiv a

traiectoriei unui robot. Scenariile de test exemplifică distribuții distincte ale fronturilor Pareto

pentru diverse situații conflictuale între două obiective:

L. Ferariu, C. Cîmpanu, Adaptive Genetic Pareto Ranking Based on Clustering,

EAIS 2015, 2015 IEEE Conference on Evolving and Adaptive Intelligent Systems, pp.

1-7, ISBN: 978-146736697-7, December 1-3, Douai, France, 2015, ISI Proceedings.

În prezent, dispozitivele EEG permit înregistrarea semnalelor folosite pentru a extrage

informații necesare în identificarea proceselor cognitive. Așa cum am demonstrat în publicațiile

enumerate în clasa problemelor de clasificare, semnalele EEG reprezintă unul din reperele

biologice recomandate pentru identificarea nivelului de încărcare a memoriei de lucru. Pentru

clasificarea semnalelor EEG, selecția trăsăturilor este una din etapele fundamentale, deoarece acest

1. Introducere

10

tip de probleme presupun procesarea unui număr foarte mare de tipare descrise prin foarte multe

atribute. Extragerea de trăsături în cazul semnalelor EEG a fost studiată intens în ultimii ani.

Abordările existente sunt bazate în general pe învățare. În studiile recente din domeniu există o

multitudine de proceduri supervizate de selecție a trăsăturilor pentru clasificarea semnalelor EEG.

Impactul unei abordări evolutive pentru optimizarea multiobiectiv a procedurii de extragere a

trăsăturilor pentru clasificarea nivelelor de încărcare a memoriei, folosind semnalele EEG este

studiat în (Cîmpanu et al., 2017b). Principalele contribuții se referă la analiza vectorilor de trăsături

candidat sub aspectele acurateței clasificării și a complexităţii; dar și la dezvoltarea unui algoritm

genetic de optimizare multiobiectiv, cu o modalitate de selecție a soluției finale preferate. Vectorii

de trăsături sunt clasificați cu ajutorul algoritmilor SVM și RF. Algoritmii sugerați au fost validați

pe două seturi de date, optimizarea selecţiei de trăsături fiind efectuată pentru diferențierea

nivelelor de încărcare a memoriei utilizând date EEG. Performanțele superioare ale metodei o

recomandă pentru faza de preprocesare a semnalelor EEG în cadrul aplicațiilor complexe așa cum

se poate observa din:

C. Cîmpanu, L. Ferariu, T. Dumitriu, F. Ungureanu, Multi-Objective Optimization of

Feature Selection Procedure for EEG Signals Classification, 6th edition of the

International Conference on e-Health and Bioengineering, EHB 2017, pp. 434-437,

ISBN: 978-1-5386-0358-1, June 22-24, Sinaia, Romania, 2017, IEEE Conference

Proceedings.

Indiferent de configurarea acestora, sub forma unor optimizări mono sau multiobiectiv,

aceste metode integrate de selecţie de trăsături evaluează calitatea vectorilor de trăsături prin

verificarea directă a utilității lor pentru fiecare clasificator în parte. În acest context, definirea

funcțiilor obiectiv independent de modelul clasificatorului utilizat este aproape imposibilă, aceasta

însemnând că selecția de trăsături este în mod natural afectată de modelul clasificatorului implicat.

Clasificarea activităților de încărcare a memoriei de tip n-back este rezolvată în (Cîmpanu et al.,

2017c) utilizând o nouă metodă de selecție a trăsăturilor pentru semnale EEG bazată pe algoritmi

genetici. Metoda de optimizare asigură o evaluare robustă a subseturilor de atribute intrate în

competiție, prin utilizarea unui mecanism de comutare care permite evaluarea calității soluțiilor

pentru diverși clasificatori fără a creşte semnificativ timpul de execuție necesar evaluării soluțiilor.

Această abordare implică clasificatori de tip RF și SVM, care complică selecţia trăsăturilor

deoarece oferă indicații limitate privind relevanța/irelevanța trăsăturilor; in acest context, validarea

metodei de selecţie a fost mai sugestivă. Este de asemenea discutată proiectarea etapei de

preprocesare a semnalelor EEG, destinată amplificării relevanței tiparelor EEG clasificate în

categoriile unor activități cognitive de tip n-back. În cele din urmă, caracteristicile metodei

sugerate sunt ilustrate experimental, în două scheme de asociere a rangurilor Pareto în sensul

optimizării multiobiectiv, așa cum reiese din:

C. Cîmpanu, L. Ferariu, F. Ungureanu, T. Dumitriu, Genetic Feature Selection for

Large EEG Data with Commutation between Multiple Classifiers, The 21st

International Conference on System Theory, Control and Computing, ICSTCC 2017,

pp. 434-437, ISBN: 978-1-5386-0358-1, October 19-21, Sinaia, Romania, 2017, ISI

Proceedings.

Selecția de atribute considerând un efect inerţial este realizată prin intermediul unei metode

genetice de optimizare multiobiectiv incorporate (“embedded” – engl.) ce presupune evoluţia unei

populații de soluții potențiale (subseturi de trăsături), în sensul minimizării erorii de clasificare și

a numărului de atribute selectate în (Ferariu et al., 2018). Setul de atribute disponibil după sesiunile

1. Introducere

11

experimentale este extins cu aceleași seturi de atribute de la momente de timp anterioare, selecția

realizându-se pe setul extins. În plus, sunt propuse două tipuri de îmbunătățiri pentru procedura

MOO, pentru a încuraja clasificarea pe ranguri a soluțiilor în cadrul spațiului de căutare extins. De

aceea, numărul arborilor considerați pentru algoritmul de clasificare este incrementat gradual,

pentru a reduce efortul computațional solicitat la evaluarea erorii de clasificare, fără a afecta

semnificativ explorarea. De asemenea, minimizarea erorii de clasificare este încurajată prin

definirea unei funcții obiectiv dinamice care să descrie numărul de atribute selectate. Metodele

propuse sunt ilustrate experimental pentru date EEG achiziționate în cursul efectuării unor

secvențe de operații matematice cu complexitate graduală.

L. Ferariu, C. Cîmpanu, T. Dumitriu, F. Ungureanu, EEG Multi-Objective Feature

Selection Using Temporal Extension, The IEEE 14th International Conference on

Intelligent Computer Communication and Processing, ICCP 2018, Cluj, Romania,

2018, Accepted, September, 6-8, Cluj, Romania, 2018, IEEE Conference

Proceedings.

1.3. Structura tezei

Această lucrare este structurată în șase capitole și centralizează rezultatele cercetării

prezentate în subcapitolul anterior. Secțiunea introductivă debutează cu prezentarea motivației

alegerii temei, continuă cu descrierea inovațiilor aduse evidențiind principalele publicații în care

au fost diseminate rezultatele și se încheie cu prezentarea structurii tezei. Pe lângă acest capitol

introductiv, teza este organizată după cum urmează.

Capitolul doi încadrează noțiunile teoretice studiate și explică conceptele principale

necesare pentru o mai bună înțelegere a aplicaţiilor considerate. În cadrul acestui capitol sunt

discutate terminologia și principalele definiții matematice relaționate cu o problemă de optimizare

multiobiectiv și cu conceptul de dominanță Pareto. Se prezintă în mod succint o clasificare a

problemelor de optimizare de tip multiobiectiv şi sunt detaliate diverse aspecte legate de

configurarea unui algoritm evolutiv, asociere de ranguri, selecție, operatori de încrucișare și

mutație, supraviețuire, menținerea diversității, etc. Cea de a doua parte a acestui capitol trece în

revistă principalii algoritmi evolutivi de optimizare multiobiectiv recomandaţi în literatură. Ca

bază teoretică necesară pentru aplicațiile prezentate în capitolele patru și cinci se va face referire

la NSGA I și NSGA II ca termen de comparație pentru metodele propuse.

Capitolul trei este dedicat prezentării noțiunilor teoretice asociate grupării supervizate și

nesupervizate a tiparelor. Capitolul debutează cu definirea clasificării și a terminologiei asociate,

prezintă principalele metrici de similaritate și disimilaritate între tipare. Metodele de grupare

nesupervizată sunt separate în patru categorii: algoritmi de grupare bazați pe distanțe, algoritmi de

grupare bazați pe densitate, algoritmi de grupare bazați pe structuri de tip grid și algoritmi de

grupare bazați pe modele. Fiecare categorie este descrisă succint evidențiind și cei mai cunoscuți

algoritmi asociați. Sunt prezentate, de asemenea, metode de grupare supervizată, cu accent pe

clasificatori precum AdaBoost, NB, kNN, RF, SVM, utilizaţi în capitolul aplicativ 5.

Capitolul patru evidențiază și compară algoritmii genetici de optimizare multiobiectiv

propuși pentru rezolvarea problemelor de proiectare a traiectoriei unui robot mobil ce se

deplasează între două puncte prestabilite, într-o scenă de lucru cu obstacole fixe, de formă convexă

sau concavă. Problema planificării optimale vizează obținerea unui timp de parcurgere minim, prin

minimizarea simultană a lungimii traiectoriei şi a sumei unghiurilor de viraj, considerând

traiectorii liniare pe porţiuni. Pentru acest demers au fost propuși o serie de algoritmi genetici de

optimizare multiobiectiv bazați pe ordonarea potențialelor soluții prin grupări nesupervizate

1. Introducere

12

adaptive care să favorizeze explorarea către mijlocul fronturilor Pareto. În plus, un obiectiv

adițional este activat la detectarea convergenței premature în urma monitorizării grupurilor de

soluţii și are rolul de a conserva sau ameliora diversitatea soluțiilor din populație. Populația inițială

este mai întâi generată aleatoriu, conținând indivizi cu lungime fixă, calitatea materialului genetic

fiind mai apoi ameliorată prin proceduri genetice de optimizare locală, mono-obiectiv. Codificarea

cromozomială este apoi extinsă, considerând un număr variabil de gene și se definesc operatori

genetici specifici. Sunt propuse inclusiv proceduri de corecție bazate pe triangularizări Delaunay

şi/sau pe algoritmul lui Dijkstra în sens multiobiectiv. Performanțele acestor algoritmi sunt

evaluate experimental pentru diverse configurații de lucru.

Capitolul cinci prezintă problema clasificării nivelelor de încărcare cognitivă pe baza

semnalelor EEG și a paradigmei testelor de tip n-back. De la o simplă clasificare a unui set de date

EEG descris printr-un număr redus de atribute, problema clasificării crește gradual în complexitate

până la clasificarea tiparelor EEG descrise printr-un număr foarte mare de atribute. Sunt trecute în

revistă două variante de experimente pentru generarea nivelelor de încărcare cognitivă: testele n-

back și efectuarea de operații aritmetice. De asemenea, pentru fiecare situație experimentală, este

prezentat modul de achiziționare și preprocesare a datelor EEG în vederea clasificării lor

ulterioare. Pentru seturile de date EEG de dimensiune redusă, procedura de optimizare propusă

este argumentată și comparată cu alte două proceduri genetice de optimizare mono-obiectiv. Pe de

altă parte, pentru seturile de date EEG de dimensiune mare se consideră ambele tipuri de

experimente și o serie de metode inovatoare constând într-un mecanism de comutare între

clasificatorii utilizați pentru evaluarea soluțiilor sau constând în eliminarea graduală a atributelor

irelevante. Acestea din urmă pot fi integrate în ambele variante de optimizare, atât în cea mono cât

și în cea multiobiectiv. În plus, pe baza informațiilor adiționale induse de regimul inerțial al datelor

EEG, este propusă o procedură evolutivă dinamică de optimizare multiobiectiv.

Principalele concluzii referitoare la rezultatele obținute pentru algoritmii propuși sunt

prezentate în cadrul capitolului șase.

În cadrul acestui rezumat, notarea algoritmilor, a figurilor, a ecuațiilor și a tabelelor este

identică cu notarea din cadrul tezei.

13

Capitolul 2

Metode evolutive de optimizare multiobiectiv

Optimizarea reprezintă procesul decizional ce utilizează resursele disponibile pentru a

obține cel mai bun rezultat. Problema care consideră simultan optimizarea mai multor funcții

obiectiv este denumită problemă de optimizare multiobiectiv. Majoritatea aplicațiilor din inginerie

se confruntă adeseori cu optimizări multiobiectiv care implică o serie de obiective conflictuale

neliniare (Ferariu & Cîmpanu, 2013). Aceste obiective conduc la puncte diferite de optim atunci

când sunt tratate separat, în consecință agregarea lor într-un singur criteriu nu asigură o explorare

relevantă (Handl & Knowles, 2008; Coello-Coello et al., 2007; Rachmawati & Sirinivasan, 2009).

Deşi majoritatea problemelor presupun optimizarea concomitentă a mai multor obiective

conflictuale, dificultatea întâmpinată în rezolvarea lor conduce adesea la formulări simplificate, de

tip mono-obiectiv. În literatura de specialitate există documentate mai multe clasificări ale

metodelor de optimizare. În funcţie de natura algoritmului folosit, metodele de căutare și

optimizare pot fi deterministe sau stohastice (Coello-Coello et al, 2007). Metodele deterministe

sunt cel mai adesea folosite pentru spații de căutare de dimensiune redusă. Cele mai multe metode

deterministe exploatează informații caracteristice domeniului problemei. Însă problemele reale

presupun spații de căutare de dimensiune foarte mare, pentru care aplicarea tehnicilor deterministe

nu este potrivită. Metodele stohastice s-au dezvoltat ca o alternativă de rezolvare pentru

problemele care nu pot fi rezolvate cu ajutorul metodelor deterministe. Prin natura lor, algoritmii

evolutivi sunt metode stohastice (Coello-Coello et al, 2007).

În cazul optimizării multiobiectiv există o infinitate de puncte de optim, cunoscute sub

denumirea de soluții Pareto optimale. Această denumire face referire la extinderea noțiunii de

optim cu sensul că, în spațiul de căutare nu există alte soluții cu performanțe superioare faţă de o

soluţie Pareto-optimală pentru toate obiectivele considerate. Din perspectiva optimizării

multiobiectiv problema admite un set infinit de soluții optimale, fiecare dintre acestea ilustrând un

compromis între obiective (Coello-Coello et al., 2007). Prin urmare, tehnicile de optimizare

multiobiectiv trebuie să fie capabile să identifice soluții cât mai apropiate de setul Pareto optimal

şi cât mai diverse posibil. În acest context, algoritmii evolutivi devin o alternativă viabilă de

rezolvare deoarece după o singură rulare, prin evoluţia unei populații de indivizi, aceștia permit

controlul diversității rezultatelor (Ferariu & Cîmpanu, 2014). Dacă numărul obiectivelor nu este

foarte mare, sortarea parțială a soluțiilor în spațiul obiectiv poate fi rezolvată prin analiza

dominanței (Handl & Knowles, 2008). Atunci când este comparată calitatea a două soluții

concurente alese în mod aleator, notate cu 𝑎 și 𝑏, analiza dominanței recomandă alegerea lui 𝑎

dacă acesta este mai bine adaptat decât 𝑏, ori de câte ori 𝑎 obține perfomanțe superioare pentru cel

puțin un obiectiv și performanțe cel puţin la fel de bune pentru restul obiectivelor (Ferariu &

Cîmpanu, 2014a). Dacă 𝑎 nu îl domină pe 𝑏 și 𝑏 nu îl domină pe 𝑎, soluțiile vor fi considerate la

fel de bine adaptate și vor avea asociat același rang (fiind localizate pe același front Pareto). De

exemplu, NSGA I (”Nondominated Sorting Genetic Algorithm” – engl. [algoritm genetic cu

sortare pe baza non-dominanței]) (Deb, 2001; Handl & Knowles, 2008; Coello-Coello et al., 2007)

asociază primul rang soluțiilor nondominate din populație, al doilea rang soluțiilor non-dominate

extrase după eliminarea primelor clasate, etc.

2. Metode evolutive de optimizare multiobieectiv

14

Tehnicile Pareto folosesc selecția bazată pe ranguri pentru a alege părinții pentru bazinul

de reproducere și supraviețuitorii generației următoare. O diversitate sporită în cadrul populației

crește relevanța sortării și permite obţinerea unui front de soluţii nedominate mai relevante pentru

descrierea frontului Pareto-optimal (dacă aceste soluţii nedominate sunt în vecinătatea frontului

Pareto-optimal) (Handl & Knowles, 2008; Rachmawati & Sirinivasan, 2009). Diversitatea poate

fi crescută prin intermediul unor operatori genetici cu productivitate mare (Chen et al., 2009), prin

inserarea bazată pe similitudine, dar și prin mecanisme specifice asocierii rangurilor în cadrul

optimizărilor multiobiectiv (Rachmawati & Sirinivasan, 2009; Ferariu & Burlacu, 2011; Ferariu

& Cîmpanu, 2013) cum sunt favorizarea soluțiilor izolate de pe fiecare rang sau folosirea unor

obiective suplimentare dedicate controlului direct al diversității (ca de exemplu, maximizarea

distanței până la cel mai apropiat vecin) (Handl & Knowles, 2008). Diversitatea poate fi

îmbunătățită în timpul grupării pe ranguri, prin încurajarea soluțiilor solitare, prin partajare sau

îngrămădire (Deb, 2001). Opțional, diversitatea poate fi îmbunătățită doar în regiunile preferate

(Ferariu & Burlacu, 2011).

În general, tehnicile Pareto nu țin cont dacă relația conflictuală dintre obiective este

neuniformă pe întreg domeniul de căutare. Însă natura acestei relații conflictuale dintre obiective

oferă informații esențiale pentru ghidarea explorării. În cazul obiectivelor puternic conflictuale,

primele fronturi vor avea tendința de a fi foarte ample, dar soluțiile plasate la extremitățile lor, deși

promovate de analiza dominanței, vor ilustra compromisuri nefolositoare între obiective. Din acest

motiv devine utilă eliminarea progresivă a soluţiile plasate la extremităţile primelor fronturi și

direcționarea căutării către mijlocul primelor fronturi Pareto. Totuşi, eliminarea unor soluții poate

fi periculoasă în cazul în care obiectivele sunt slab-conflictuale, deoarece în această situație fiecare

front Pareto cu soluţii bine adaptate include de obicei un număr redus de soluții distincte, iar

explorarea în regiunile adiacente acestora ar fi bine-venită (Cîmpanu & Ferariu, 2013).

Luând în considerare robustețea, flexibilitatea și universalitatea abordării, algoritmii

evolutivi au devenit alternative extrem de cunoscute de rezolvare a problemelor de optimizare

multiobiectiv. Abordările de tip Pareto folosind algoritmi evolutivi sunt probabil cele mai

eficiente, dacă se consideră un număr limitat de funcții obiectiv (Coello-Coello et al., 2007). Aşa

cum a fost deja menţionat, tehnicile Pareto utilizează analiza dominanței pentru a asigura sortarea

parțială a soluțiilor. Mai multe soluții pot fi clasificate pe același nivel; însă cerinţa principală a

abordării constă în menținerea unui grad ridicat al diversității în cadrul populației.

În cadrul acestui capitol sunt prezentate concepte de bază din domeniul optimizării

multiobiectiv, cu accent pe analiza dominanței Pareto pentru ordonarea parțială a soluțiilor. Sunt

de asemenea analizate efectele produse prin integrarea mecanismului decizional cu procedura de

căutare, pentru variante de lucru de tip generativ, non-interactiv și interactiv. În contextul

optimizărilor multiobiectiv, sunt discutate caracteristicile algoritmilor evolutivi și avantajele pe

care aceștia le conferă în generarea unor soluții diverse, nedominate, ilustrând avantajele rezultate

pentru descrierea mai relevantă a frontului Pareto-optimal. Pentru extinderea variantelor de

algoritmi genetici canonici la versiunea multiobiectiv sunt analizate metodele de tip Pareto, care

pot fi integrate simplu în algoritmul genetic standard prin calcularea adecvată a rangurilor. Astfel,

sunt discutați algoritmii cei mai recomandați în literatura de specialitate, și anume MOGA, NSGA,

NSGA II, NPGA, PAES, SPEA, MOMGA, etc.

Capitolul oferă bazele teoretice necesare pentru metodele genetice de optimizare

multiobiectiv propuse în capitolele viitoare. Aceste metode integrează căutarea și decizia, și

încurajează îmbunătățirea materialului genetic folosind ca artificiu recalcularea adecvată a

rangurilor pentru soluțiile preferate sau solitare.

15

Capitolul 3

Gruparea tiparelor

Algoritmii de grupare sunt intens analizaţi în cadrul domeniului învăţării automate

(Suthaharan, 2016). Domeniul învățării automate oferă cadrul științific pentru studiul modelelor și

algoritmilor de învățare care ajută mașinile să învețe un sistem de organizare plecând de la date și

de aceea unul din obiectivele învățării automate îl reprezintă construirea unui sistem inteligent.

Modelele și algoritmii de învățare automată reprezintă în fond metode de recunoaștere a tiparelor;

o problemă din domeniul învățării automate presupune identificarea unui model care să realizeze

potrivirea dintre un set de date și răspunsurile asociate, dar și antrenarea și validarea modelului

respectiv pentru a învăța caracteristicile sistemului plecând de la existența unui set de date și a

răspunsurilor oferite de un sistem pentru setul respectiv (Suthaharan, 2016). În acest context,

gruparea tiparelor în categorii relevante constituie o problemă cheie în multe aplicații. De fapt,

gruparea asigură o organizare preliminară a datelor şi interpretarea la nivel înalt a semnificaţiei

acestora. Determinarea claselor din care fac parte tiparele este dificilă mai ales dacă dependențele

dintre variabilele înregistrate în baza de date nu sunt înțelese complet de la început, sunt de tip

neliniar şi/sau setul de date de antrenare este dimensiune mare și, eventual, neechilibrat (conținând

un număr diferit de tipare din fiecare categorie și/sau tipare neuniform distribuite în cadrul fiecărui

grup).

Gruparea poate fi realizată în mod supervizat (”classification” – engl.) sau nesupervizat

(”clustering” – engl.). Dacă datele pot fi grupate pe categorii și există etichete pentru apartenența

la o anumită clasă, atunci modelul de grupare poate fi obținut în mod supervizat și poate fi de

asemenea optimizat pe baza acestor informații. În această situație învățarea este supervizată

(Suthaharan, 2016). Atunci când domeniul datelor permite separarea acestora pe categorii și nu

există etichete care să indice apartenența la o anumită clasă, învățarea este de tip nesupervizat

(Suthaharan, 2016). Dacă spre deosebire de aceste situații, separarea datelor pe categorii nu este

posibilă, atunci nu se mai pune problema unei grupări, dar poate fi considerată învățarea

supervizată bazată pe regresie (Dumitriu et al., 2017).

Principalele dificultăţi sunt legate de seturile de date de antrenare de mari dimensiuni,

împrăștiate sau care conțin zgomot (Breaban, 2010). În acest context, o serie de pre-procesări

preliminare ale spațiului trăsăturilor pot fi de folos. Transformarea trăsăturilor proiectează setul

inițial de trăsături într-unul nou ce oferă o distribuire mai avantajoasă a tiparelor și/sau este de

dimensiune mai redusă, dar care este uzual lipsit de semnificație fizică și dificil de interpretat (Liu

et al., 2003). O altă variantă este selectarea (Dhilloon et al., 2003) unui subset relevant de trăsături

din cadrul setului original de trăsături prin reținerea semnificației fizice (Boutsidis et al., 2009).

Pentru gruparea nesupervizată, selecția unor atribute relevante reprezintă o problemă şi mai

dificilă, datorită faptului că etichetele claselor (şi uneori chiar numărul lor) nu sunt necunoscute a

priori (Law et al., 2003).

Aplicațiile discutate în cadrul acestei lucrări în capitolele 4 şi 5 vor face referire şi la

rezolvarea unor probleme de grupare în mod supervizat și nesupervizat. Astfel, capitolul 4 va

prezenta metode evolutive multiobiectiv bazate pe gruparea indivizilor din populaţie, gruparea

soluţiilor fiind utilizată pentru extragerea de informaţii utile în adaptarea schemelor de calcul al

3. Gruparea tiparelor

16

valorilor fitness. Pe de altă parte, capitolul 5 va prezenta alternative pentru rezolvarea problemelor

de grupare supervizată pentru semnalele EEG (Cîmpanu et al., 2017a; Cîmpanu et al., 2017b;

Cîmpanu et al., 2017c; Cîmpanu et al., 2018a; Dumitriu et al., 2018). În acest context, elementele

teoretice prezentate în capitolul de faţă se vor referi la cele două categorii de algoritmi de grupare

– clasificare şi clusterizare.

Se consideră că un tipar 𝑥𝑖 din spațiul trăsăturilor 𝑆, d

i S x este definit ca un exemplu

înregistrat în setul de date disponibil, în timp ce un atribut este definit ca o trăsătură individuală

care descrie tiparul. Astfel, setul de date poate fi considerat a fi o mulţime de tipare,

},....,,{ 21 NX xxx , în cadrul căreia fiecare tipar este reprezentat printr-un vector de valori ale

trăsăturilor, Sx djiji ,..,1][x (Jain et al., 1999). Folosind o metrică de disimilaritate, se pot urmări

deosebirile dintre tipare. Disimilaritatea 𝐷: 𝑆 × 𝑆 → ℜ+, 𝐷(𝒙𝑖, 𝒙𝑗) calculată între două tipare are

o valoare mare pentru tipare foarte diferite și o valoare mică pentru tipare asemănătoare. Astfel,

clusterul poate fi descris ca un grup de obiecte asemănătoare, disimilaritatea dintre un obiect din

cluster şi alt obiect din cluster fiind (de preferat) mai mică decât dintre un obiect din cluster şi un

obiect care nu aparţine clusterului: 𝐷(𝒙𝑖, 𝒙𝑗) > 𝐷(𝒙𝑖, 𝒙𝑚), pentru orice 𝑥𝑖 , 𝑥𝑗 și 𝑥𝑚 ∈ 𝑋 cu mx și

ix aparținând aceluiași cluster și jx aparținând altui cluster. Dată fiind marea varietate de algoritmi

de clusterizare descriși în literatura de specialitate, este dificilă o separare a acestora pe categorii

clare și disjuncte luând în considerare metoda utilizată în delimitarea clusterelor. În cadrul acestui

subcapitol sunt discutate patru categorii principale de algoritmi de grupare nesupervizată care

cuprind aproape toate abordările existente (algoritmi bazați pe distanțe, bazați pe densitate, bazați

pe modele și bazați pe structuri de tip grid).

Gruparea supervizată rezolvă asocierea dintre tipare necunoscute (care nu au mai fost

văzute sau procesate) și etichete de clase, pe baza unor tipare gata etichetate. Tiparele etichetate

specifică setul de antrenare. Astfel, setul de antrenare este format din perechi (𝒙, 𝑦), unde 𝒙 =

(𝑥1, 𝑥2, … , 𝑥𝑑) reprezintă un tipar, iar 𝑦 valoarea ieșirii dorite, de obicei eticheta clasei căreia îi

corespunde 𝒙, 𝑦 ∈ {𝐶1, 𝐶2, … , 𝐶𝑘}. Fiind dat un astfel de set de date de antrenare, scopul unui

algoritm de grupare supervizată este de a analiza aceste date și de a genera modelul pe baza căruia

să poată fi clasificate și alte tipare, neincluse în setul de antrenare. În cadrul literaturii de

specialitate există o gamă variată de algoritmi de grupare supervizată rezultaţi din varietatea de

modele folosite pentru clasificator. În cadrul acestui subcapitol sunt discutate trei dintre categoriile

principale de algoritmi de grupare supervizată care cuprind aproape toate abordările existente

(algoritmi bazați pe instanțe, bazați pe metode probabilistice, respectiv bazați pe ansambluri).

Stabilirea unui număr redus de trăsături relevante pentru descrierea tiparelor reprezintă un

element cheie pentru problemele de grupare. Dacă trăsăturile sunt insuficiente, diferenţierea

claselor nu poate fi rezolvată corect. Pe de altă parte, folosirea unor trăsături redundante sau

irelevante afectează acuratețea rezultatelor şi conduce la creşterea nejustificată a timpului de

execuţie. Din acest motiv, trăsăturile inutile (nerelaționate cu specificul grupărilor, al informației

descrise), trebuie eliminate din setul original, procesul de eliminare fiind cunoscut în literatura de

specialitate ca procedura selecției de trăsături. Selecția de trăsături poate reduce riscul supra-

determinării obţinute atunci când modelul clasificatorului proiectat considerând un număr prea

mare de trăsături, unele din ele inutile, este prea complex. Desigur, selecția de trăsături relevante

nu poate corecta lipsa de robustețe, legată de existența unui set suficient de relevant de exemple.

De exemplu, aplicațiile bio-medicale (Cîmpanu et al., 2017a; Cîmpanu et al., 2017b; Ferariu et al.,

2018) implică de cele mai multe ori exemple de dimensiune foarte mare, pentru care selecţia

3. Gruparea tiparelor

17

trăsăturilor este recomandată ca etapă preliminară clasificării propriu-zise (Cîmpanu et al., 2017a;

Cîmpanu et al., 2017b; Ferariu et al., 2018).

Selecția de trăsături presupune extragerea unui subset din setul original, conservând

trăsăturile semnificative din setul original, eliminând trăsăturile irelevante, redundante sau lipsite

de importanță. Principalele categorii de metodele de selecție de trăsături sunt prezentate în (Tang

et al., 2015). Luând în considerare modul de analiză a relevanţei trăsăturilor, metodele supervizate

de selecție de trăsături pot fi clasificate în metode de tip filtru (”filter methods” – engl.), metode

de tip împachetare (”wrapper methods” – engl.) și metode de tip încorporat (”embedded methods”

– engl.). Metodele de tip încorporat verifică calitatea unui subset de trăsături rezolvând direct

problema de clasificare cu ajutorul unui anumit tip de clasificator. Acest tip de metode sunt

costisitoare ca timp de execuție, în special pentru seturi descrise de un număr mare de trăsături

(Okun, 2011). Spre deosebire de metodele de tip filtru sau împachetare care sunt independente de

un anumit clasificator, metodele de tip încorporat consideră că subsetul optim de trăsături trebuie

să depindă de predispozițiile și euristicile algoritmului de clasificare (Tang et al., 2015).

Considerând un algoritm de grupare supervizată predefinit, o metodă de tip încorporat cuprinde

următoarele etape: căutarea unui subset de trăsături și evaluarea subsetului selectat pe baza

performanțelor algoritmului de grupare supervizată. Etapele se repetă până la atingerea nivelului

de calitate dorit. În cadrul acestor metode, algoritmul de grupare supervizată predefinit

funcționează după principiul cutiei negre.

Analiza datelor reprezintă unul dintre cele mai importante subiecte de cercetare din

domeniul științei calculatoarelor. În cadrul acestui capitol sunt discutate elementele de bază

implicate în procesul de grupare supervizată sau nesupervizată, pornind de la prezentarea

metricilor de disimilaritate/ similaritate uzuale pe baza cărora se poate analiza cât se asemănătoare

sunt soluţiile şi discutarea indicatorilor de evaluare a rezultatului grupării. Cele mai cunoscute

categorii de algoritmi de grupare sunt analizate din perspectiva metodei de grupare utilizate,

folosind exemplificări relevante prezentate în literatura de specialitate.

În cazul algoritmilor de grupare nesupervizată sunt discutați algoritmi bazați pe distanțe

(k-medii, k-medii fuzzy, k-medoizi, PAM, CLARA, k-mediani), algoritmi bazați pe densitate

(DBSCAN, SNN, OPTICS), algoritmi bazați pe modele (arbori de decizie, SOM) și algoritmi

bazați pe structuri de tip grid (O-CLUSTER, STING, ”Mountain Clustering”), evidențiind

particularitățile acestora, avantajele și limitările fiecărei abordări în parte. Pentru gruparea

supervizată au fost considerați algoritmi bazați pe instanțe (KNN, SVM), algoritmi bazați pe

metode probabilistice (clasificatorul Bayesian naiv), algoritmi bazați pe ansambluri (RF,

AdaBoost) și algoritmi bazați pe reguli.

Capitolul de față vizează conturarea cadrului teoretic necesar pentru prezentarea aplicațiilor

dezvoltate pe parcursul stagiului doctoral. Mai exact, tehnici de grupare nesupervizată (k-medii)

vor fi folosite pentru analiza populației de soluții obținută de algoritmul genetic pe parcursul

generațiilor pentru detecția situațiilor în care diversitatea materialului genetic este inadecvată

și/sau pentru integrarea avantajoasă între decizie și căutare (Capitolul 4). Pe de altă parte,

algoritmii de grupare supervizată vor fi utilizați pentru identificarea nivelelor de încărcare

cognitivă pe baza semnalelor EEG achiziționate pe durata efectuării unor teste de memorie. În

acest context, clasificarea va fi analizată folosind AdaBoost, KNN, NB, RF sau SVM. De

asemenea, RF și SVM vor fi încorporați în metode genetice multiobiectiv de selecție a trăsăturilor

(Capitolul 5).

18

Capitolul 4

Aplicații ale metodelor genetice de optimizare

multiobiectiv în probleme de planificare

Scopul general al unei probleme de planificare a rutei optime îl constituie identificarea unei

căi care să minimizeze/maximizeze o serie de funcţii obiectiv, respectând restricții de tip static sau

dinamic impuse de mediul de lucru. Indicatorii de performanță pot fi timpul de parcurgere,

lungimea, energia consumată, etc. Restricțiile pot fi statice (compoziția refractară a terenului) sau

dinamice (limitarea vitezei pentru a preveni alunecarea sau răsturnarea) (Krishnan et al., 2017).

Planificarea rutei optime în sens multiobiectiv presupune optimizarea simultană a mai multor

funcţii obiectiv. Luând în calcul relaţia conflictuală dintre obiective, problema multiobiectiv de

identificare a traiectoriei optime este mult mai complicată decât cea mono-obiectiv. Pe de altă

parte, din punctul de vedere al decidentului, soluțiile rezultate prin optimizare multiobiectiv sunt

mai concludente.

În capitolul de faţă sunt prezentate metode pentru rezolvarea problemei de planificare a

traiectoriei unui robot mobil, formulată în sens multiobiectiv. Metodele prezentate se bazează pe

algoritmii evolutivi. Motivul principal ale acestei alegeri rezultă din faptul acești algoritmi sunt

bazați pe populații de soluții și astfel pot oferi un control sporit asupra diversității rezultatelor,

permiţând chiar generarea unui set de soluții finale distribuite de-a lungul şi în apropierea frontului

Pareto optimal, dintr-o singură rulare. De asemenea, algoritmii evolutivi permit integrarea flexibilă

a unor cunoștințe suplimentare în cadrul buclei evolutive pentru implementarea acțiunilor

mecanismului decizional, aşa cum a fost detaliat în capitolul 2. În plus, algoritmii evolutivi oferă

robustețe sporită în căutare și asigură compatibilitatea cu funcții obiectiv neliniare, discontinue sau

variabile în timp. Pornind de la aceste aspecte, algoritmii genetici sunt adeseori aplicați în

rezolvarea problemei de planificare a rutei optimale în medii complexe cu obstacole staționare,

având însă suficientă putere computațională pentru a lucra și în medii cu obstacole mobile și cu

localizare necunoscută (Krukhmalev & Pshikhopov, 2017). Există în literatură o gamă variată de

abordări bazate pe teoria grafurilor. Algoritmii prezentați în cadrul acestui capitol consideră

gestionarea suprafeței de lucru prin stabilirea pozițiilor inițiale și finale pentru un robot mobil,

localizarea și marcarea obstacolelor, precum și reprezentarea spațiului permis pentru deplasare.

Metodele de optimizare multiobiectiv trebuie configurate luând în calcul numărul

obiectivelor considerate (Handl & Knowless, 2008; Hughes, 2008). În cazul metodelor de

optimizare multiobiectiv cu puține obiective sunt recomandate tehnicile Pareto (Deb, 2001;

Coello-Coello et al., 2007). Acestea permit calcularea rangurilor soluțiilor pe baza analizei de

dominanță și prin extragerea fronturilor Pareto. Cea mai importantă cerință pe care o impun

metodele Pareto o reprezintă menținerea diversității în cadrul populației. Aşa cum a fost deja

discutat în capitolul 2, varietatea materialului genetic poate fi îmbunătățită prin intermediul unor

operatori genetici productivi (Chen et al., 2009), dar şi prin tehnici care vizează calculul valorilor

4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare

19

fitness, cum ar fi prin mărirea valorii fitness pentru soluțiile izolate, prin îngrămădire sau nișare

(Deb, 2001; Rodriguez-Vazquez et al., 2004). Menținerea diversității în centrul fronturilor

nondominate primește atenție specială în (Rachmawati & Sirinivasan, 2009), deoarece se așteaptă

ca aceste regiuni să fie preferate la final de către mecanismul decizional. În mod evident,

diversitatea soluțiilor poate fi măsurată în spațiul obiectiv sau de căutare (Deb, 2001; Rodriguez-

Vazquez et al., 2004). O serie de imbunătătţiri pentru menţinerea diversităţii vor fi introduse în

subcapitolele următoare.

Tehnicile de menţinere a diversităţii au fost integrate în metode bazate pe combinarea

progresivă a deciziei cu căutarea. Zona soluţiilor preferate este considerată mijlocul primelor

fronturi Pareto. Eliminarea graduală a soluțiilor nedominate cu utilitate redusă poate fi avantajoasă.

Însă, configurarea simbiozei dintre decizie şi căutare este foarte dificilă, dat fiind faptul că toate

criteriile folosite de factorul decizional sunt cunoscute doar la nivel calitativ. De obicei, în cadrul

buclei evolutive evaluarea soluțiilor este realizată pentru obiective cu priorități egale. Orice abatere

de la acest standard poate fi interpretată ca articulare progresivă a preferințelor factorului

decizional. Suplimentarea obiectivelor este indicată atunci când se dorește o diferenţiere

suplimentară a calităţii soluțiilor existente sau când algoritmul se blochează pe un palier al

suprafeței obiectiv. Pe de altă parte, eliminarea obiectivelor poate fi folositoare atunci când

fronturile conțin prea puține soluții. Un mecanism decizional bazat pe diferite nivele de priorități

și obiective țintă predefinite este ilustrat în (Rodriguez-Vazquez et al., 2004). În acest capitol sunt

propuse tehnici adaptive de menținere a diversității bazate pe gruparea nesupervizată a soluțiilor

care permit determinarea naturii conflictului dintre obiective pe baza distribuţiei soluţiilor în

spaţiul obiectiv. Pe baza acestei analize, sunt configurate presiunea de selecţie pentru zona

preferată şi tehnicile de diversificare a soluţiilor. Acest tip nou de abordare evaluează indivizii din

populație în funcție de diferite seturi de obiective, în funcție de grupul lor de apartenență. În plus,

spre deosebire de ideile prezentate în (Ferariu & Burlacu, 2011a; Ferariu & Burlacu, 2011b)

variantele prezentate (Ferariu & Cîmpanu, 2013) tratează obiective cu priorități similare și prezintă

diferite strategii de ajustare a limitelor grupurilor.

Alte îmbunătăţiri prezentate vizează codificările soluţiilor în lanţuri cromozomiale de

dimensiune variabilă şi dezvoltarea unor operatori genetici compatibili cu aceste codificări. Nu în

ultimul rând, sunt propuse metode pentru rezolvarea restricțiilor prin îmbunătăţiri locale derulate

în sens mono şi multi-obiectiv. Combinând îmbunătăţirile menţionate mai sus, în cadrul acestui

capitol sunt analizați cinci algoritmi genetici aplicați pentru optimizarea multiobiectiv a rutei unui

robot mobil între două poziții predefinite pe o suprafață plană cu obstacole poligonale fixe:

MOO-DB (”Multi-Objective Optimization with integrated Decision Block mechanism” –

engl.): Algoritm genetic de optimizare multiobiectiv cu factor decizional integrat (Ferariu &

Cîmpanu, 2013);

MOO-AR (”Multi-Objective Optimization with Adaptive Ranking” – engl.): Algoritm

genetic de optimizare multiobiectiv cu repartizare adaptivă a rangurilor (Cîmpanu & Ferariu,

2013);

MOO-ARCCP (”Multi-Objective Optimization with Adaptive Ranking Scheme, a new

Crossover and Corrective Procedure” – engl.): Algoritm genetic de optimizare multiobiectiv


20

cu încrucișare pe cromozomi de lungime variabilă și procedură de corecție (Ferariu &

Cîmpanu, 2014a);

MOO-ARCP (”Multi-Objective Optimization with Adaptive Ranking based Corrective

Procedure” – engl.): Algoritm genetic de optimizare multiobiectiv cu procedură corectivă

bazată pe grupare adaptivă (Ferariu & Cîmpanu, 2014b);

MOO-ARC (”Multi-Objective Optimization with Adaptive Ranking based on Clustering” –

engl.): Algoritm genetic de optimizare multiobiectiv cu asociere adaptivă a rangurilor bazată

pe grupare nesupervizată (Ferariu & Cîmpanu, 2015).

4.1. Configurarea algoritmilor genetici pentru planificarea rutei optimale

Fie 𝑆 o scenă de lucru plană continuă bidimensională, pe suprafața căreia este prezentată

sub forma unei hărți amplasarea arbitrară a unui set de obstacole (de exemplu în Figura 4.1.). Fără

a afecta generalitatea abordării, obstacolele sunt aliniate după un grid de dimensiune 𝑚 × 𝑚

(Bayili & Polat, 2011; Ahmed & Deb, 2012; Davoodi et al, 2013; Ferariu & Cîmpanu, 2013;

Cîmpanu & Ferariu, 2013; Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu, 2014b; Ferariu &

Cîmpanu, 2015) sau sunt dispuse aleator (Ferariu & Cîmpanu, 2014; Ferariu & Cîmpanu, 2015).

Obstacolele pot avea orice formă, inclusiv concavă. În cele ce urmează va fi studiat exclusiv cazul

configurației fixe pentru obstacolele definite pe suprafață. Abordarea poate fi extinsă însă foarte

ușor pentru hărți de obstacole care variază în timp.

Figura 4.1. Scena de lucru WS1 și un obstacol cu formă concavă definit pe un grid de

dimensiune 8 × 8, respectiv două dintre traiectoriile admisibile cu 2 (negru) sau cu 3 (roșu)

puncte intermediare.

Fie (𝑥, 𝑦) ∈ 𝑆 un punct din 𝑆, descris prin coordonatele reale 𝑥, 𝑦 ∈ ℝ. Robotul mobil

trebuie să se deplaseze plecând de la un punct 𝐴𝑠𝑡𝑎𝑟𝑡 = (𝑥𝑠𝑡𝑎𝑟𝑡, 𝑦𝑠𝑡𝑎𝑟𝑡) până la o destinație

prestabilită 𝐴𝑠𝑡𝑜𝑝 = (𝑥𝑠𝑡𝑜𝑝, 𝑦𝑠𝑡𝑜𝑝) fără a intra în coliziune cu obstacolele. Traiectoria robotului

este reprezentată printr-un șir finit de segmente:

𝑇 = [(𝑥𝑠𝑡𝑎𝑟𝑡 , 𝑦𝑠𝑡𝑎𝑟𝑡), (𝑥1, 𝑦1)] ∪ [(𝑥1, 𝑦1), (𝑥2, 𝑦2)] ∪ …∪ [(𝑥𝑁 , 𝑦𝑁), (𝑥𝑠𝑡𝑜𝑝, 𝑦𝑠𝑡𝑜𝑝)] (4.1.)

trecând prin cele 𝑁 ≥ 0 puncte intermediare. În fiecare punct intermediar 𝐴𝑖 = (𝑥𝑖, 𝑦𝑖) ∈ 𝑊𝑆

robotul își schimbă direcția. Astfel, o traiectorie oarecare 𝑇 poate fi reprezentată printr-un set de

puncte intermediare, în fiecare având loc schimbarea direcției robotului:

𝑇 = {(𝑥1, 𝑦1),… , (𝑥𝑁 , 𝑦𝑁)|(𝑥𝑖 , 𝑦𝑖) ∈ 𝑆, 𝑖 = 1,…𝑁}. (4.2.)


21

Fiecare traiectorie candidat este codificată în populația algoritmului genetic prin

coordonatele reale ale punctelor intermediare și este compusă dintr-un număr fix de puncte

intermediare (Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu, 2013) sau dintr-un număr variabil

de puncte intermediare (Ferariu & Cîmpanu, 2014; Ferariu & Cîmpanu, 2015). Traiectoria astfel

definită este caracterizată prin două funcţii obiectiv: lungimea totală 𝐿 și suma unghiurilor de viraj

(denumită în continuare curbura şi notată cu 𝐶).

(xstop,ystop)

T1

T2

α1

α2

WS1

(x1,y1)(x2,y2)

(xstart,ystart)

stopstart

T3

Figura 4.2. Reprezentarea traiectoriilor pe scena de lucru

Problema planificării traiectoriei optimale a robotului vizează obținerea unui timp minim

de parcurgere (Davoodi et al, 2013; Haupt & Haupt, 2004). Evident, traiectoria optimală trebuie

să fie localizată în perimetrul scenei de lucru. Problema de optimizare multiobiectiv va urmări

identificarea celei mai rapide căi considerând că viteza robotului trebuie corelată cu curbura căii.

Aşa cum a fost menţionat, cele două obiective vor viza minimizarea concomitentă (Ferariu &

Cîmpanu, 2013; Cîmpanu & Ferariu, 2013; Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu,

2014b, Ferariu & Cîmpanu, 2015) a lungimii traiectoriei și a sumei unghiurilor de viraj pentru

traiectoria considerată conform ecuațiilor (4.3.) și (4.4.).

𝑂1: 𝑔ă𝑠𝑒ș𝑡𝑒 argmin𝑇⊂𝑆

(𝐿(𝑇)) (4.3.)

𝑂2: 𝑔ă𝑠𝑒ș𝑡𝑒 argmin𝑇⊂𝑆

(𝐶(𝑇)) (4.4.)

Cele două funcții obiectiv: 𝑓1(𝑇) = 𝐿(𝑇) și 𝑓2(𝑇) = 𝐶(𝑇), unde 𝐿(𝑇) reprezintă lungimea totală

a traiectoriei sunt definite considerând (𝑥0, 𝑦0) = (𝑥𝑠𝑡𝑎𝑟𝑡, 𝑦𝑠𝑡𝑎𝑟𝑡)ș𝑖 (𝑥𝑁+1, 𝑦𝑁+1) = (𝑥𝑠𝑡𝑜𝑝, 𝑦𝑠𝑡𝑜𝑝)

și 𝐶(𝑇) curbura acesteia, definită ca fiind suma unghiurilor de viraj:

𝐿(𝑇) =∑‖(𝑥𝑖, 𝑦𝑖) − (𝑥𝑖+1, 𝑦𝑖+1)‖

𝑁

𝑖=0

, (𝑥𝑖, 𝑦𝑖) ∈ 𝑇 (4.5.)

𝐶(𝑇) =∑𝛼𝑖

𝑁

𝑖=1

(4.6.)

Aici, ‖∎‖ indică distanța Euclidiană, iar 𝛼𝑖 unghiul de viraj în punctul intermediar 𝐴𝑖.


22

În Figura 4.2. sunt ilustrate două exemple de traiectorii 𝑇1 și 𝑇2 pentru scena de lucru 𝑊𝑆1.

Din această figură se poate observă că cele două obiective sunt conflictuale şi nu pot fi agregate

într-un singur obiectiv. Exemplificarea este oferită de 𝑇1 și 𝑇2, deoarece comparându-le se remarcă

faptul că reducerea lungimii lui 𝑇2 poate duce la creşterea curburii (vezi 𝑇2), iar reducerea curburii

lui 𝑇1 poate duce la creşterea lungimii (vezi 𝑇1). În plus calea directă 𝑇3 intră în coliziune cu

obstacolul încălcând restricţia. De aceea, pentru a rezolva posibilele situațiile de inadmisibilitate a

unei traiectorii se vor aplica independent penalizări pentru fiecare funcţie obiectiv în parte. O

alternativă de rezolvare a restricției unei traiectorii o constituie implementarea unui algoritm de

corecție. O parte din algoritmii propuşi se vor baza pe această idee.

Minimizarea celor două funcții obiectiv este conflictuală din cauza prezenţei obstacolelor.

Ideea este ilustrată simplu cu Figura 4.2. Segmentul care ar uni direct punctele de start şi stop nu

formează o traiectorie admisibilă, dar pe o scenă fără obstacole, aceasta ar fi traiectoria optima. În

orice caz în care segmentul care unește punctele de start și de stop nu este admisibil, obiectivele

devin conflictuale. “Tăria” conflictului dintre obiective este diferită în zone diferite ale spaţiului

obiectiv, de aceea analizarea acestui conflict va fi utilă pentru mecanismul de decizie.

Metodele multiobiectiv considerate folosesc fronturile Pareto delimitate prin analiza

dominanței. Aceasta asigură o sortare parțială a soluțiilor, care permite plasarea mai multor indivizi

pe același front/rang. Mai exact, un individ ce codifică traiectoria 𝑇1 este etichetat ca fiind dominat

de un alt individ ce codifică traiectoria 𝑇2, dacă și numai dacă: (𝐿(𝑇1) < 𝐿(𝑇2) ș𝑖 𝐶(𝑇1) ≤

𝐶(𝑇2)) sau (𝐿(𝑇1) ≤ 𝐿(𝑇2) ș𝑖 𝐶(𝑇1) < 𝐶(𝑇2)).

În cazul metodelor propuse în (Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu, 2013),

situațiile de inadmisibilitate a traiectoriei pe scena de lucru sunt rezolvate prin adăugarea unor

penalizări. Valorile ambelor funcții obiectiv sunt crescute artificial cu o cantitate predefinită

proporțională cu numărul segmentelor inadmisibile conținute în traiectorie. De aceea, după

asocierea penalizării aferente fiecare traiectorie inadmisibilă devine dominată de către traiectoriile

admisibile. În cazul soluțiilor prezentate în (Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu,

2014b; Ferariu & Cîmpanu, 2015), rezolvarea restricției pentru traiectoria determinată nu mai este

necesară deoarece procedura de corecție folosită va elimina orice traiectorie inadmisibilă din

cadrul populației.

Aşa cum a fost menţionat anterior, fiecare cromozom codifică coordonatele reale ale

punctelor intermediare prin care trece robotul. O primă variantă de codificare consideră

cromozomi de aceeași lungime, ce pot fi procesați cu ajutorul operatorilor genetici canonici

(Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu, 2013; Ferariu & Cîmpanu, 2014a). Deoarece

unele segmente incluse în traiectorie pot rezulta de dimensiune foarte mică, această o codificare

nu este excesiv de limitativă. Cromozomul care codifică traiectoria 𝑇 conține coordonatele

carteziene reale ale punctelor intermediare regăsite de-a lungul traiectoriei. Așadar, operatorii

genetici canonici disponibili pentru reprezentări cromozomiale în virgulă mobilă pot fi aplicați

direct. Operatorii genetici folosiţi în acest caz pentru prelucrarea materialului genetic al populației

de copii sunt: încrucișarea aritmetică intermediară și mutația uniformă.

Pentru a câștiga în flexibilitate în codificarea traiectoriilor, [MOO-ARCCP] lucrează cu

traiectorii ce conțin un număr variabil de puncte intermediare. Aceasta se traduce prin lucrul cu

cromozomi de lungime variabilă în cadrul algoritmului genetic. Merită menționat că rezolvarea


23

cerinței de asigurare a admisibilității impune în mod implicit un număr minim de puncte

intermediare pentru fiecare configurație specifică (𝐴𝑠𝑡𝑎𝑟𝑡, 𝐴𝑠𝑡𝑜𝑝 și 𝑊𝑆). Mai mult, costurile

computaționale reduse rezultă pentru căile scurte codificate prin cromozomi de lungime redusă;

însă reducerea numărului de puncte intermediare este foarte folositoare atât timp cât nu afectează

diveristatea populației. Algoritmul genetic trebuie să utilizeze un operator de încrucișare

compatibil cu acest tip de reprezentare a cromozomilor. Prin concatenarea sau prin scindarea

cromozomilor nu poate fi asigurată suficientă productivitate pentru o codificare în virgule mobilă.

În acest context a fost introdus şi un operator de încrucişare compatibil proiectat în sensul de a

produce copii cât mai diferiți, exploatând cât mai avantajos materialul genetic al părinților (fiecare

părinte este format dintr-un șir de coordonate reale corespunzând punctelor intermediare ce

compun traiectoria).

Înlocuirea segmentelor inadmisibile se realizează sub forma unor optimizări locale,

efectuate în funcție de 𝐿 pentru toți cromozomii inadmisibili. O descreștere suplimentară a lui 𝐿

este realizată prin intermediul reducerii punctelor intermediare. De aceea, aceste corecții sporesc

riscul unei convergențe premature nedorite în cadrul buclei de optimizare multiobiectiv.

Explorarea poate fi avantajată prin folosirea unor valori mari pentru delta și a unor valori mici

pentru probabilitatea de reducere. Trebuie menționat că formarea căilor prin triangularizări

Delaunay de sine stătătoare nu reprezintă o alternativă pentru optimizarea multiobiectiv a

traiectoriei, deoarece costurile cu care sunt etichetate muchiile grafului referă doar unul dintre

obiective (lungimea căii).

𝑑0𝑘(𝑇𝑖) = √(𝐿(𝑇𝑖)

∑ 𝐿(𝑇𝑖)𝑇𝑖∈𝑃(𝑘) )

2

+ (𝐶(𝑇𝑖)

∑ 𝐶(𝑇𝑖)𝑇𝑖∈𝑃(𝑘))

2

(4.7.)

Selecția pentru recombinare și supraviețuirea sunt rezolvate prin intermediul schemelor de

asociere a valorilor fitness prezentate în subcapitolele următoare. La finalul buclei evolutive,

rezultatul algoritmului este selectat ca fiind calea cu cea mai mică distanță până la originea

spațiului obiectiv (𝐿, 𝐶).

4.2. Algoritm genetic multiobiectiv cu clasificare pe ranguri folosind clustere și cu controlul

direct al diversității [MOO-DB]

În cadrul algoritmului [MOO-DB] rangurile sunt asignate progresiv prin combinarea

tehnicilor de căutare cu cele de decizie. Tehnicile de decizie sunt implementate printr-o grupare

adaptivă a soluţiilor ce ghidează procesul de căutare către mijlocul celor mai bune fronturi Pareto.

Astfel sunt eliminate gradual soluțiile inutile, amplasate la periferia acestor fronturi, care sunt

puternic încurajate de analiza de dominanţă. Algoritmul propus detectează convergența prematură

prin monitorizarea variației dimensiunii grupurilor de soluţii rezultate și intervine dacă este necesar

pentru a conserva sau îmbunătăți diversitatea populației de soluții. În acest demers, algoritmul va

utiliza un al treilea obiectiv ori de câte ori va fi necesar (Ferariu & Cîmpanu, 2013). Obiectivul

suplimentar are rolul de a controla varietatea materialului genetic corespunzător indivizilor

superiori din populație. Eficiența algoritmului [MOO-DB] a fost ilustrată experimental prin


24

rezolvarea problemei de planificare a traiectoriei unui robot mobil, considerând un spațiu de lucru

continuu conținând obstacole convexe și/sau concave, disjuncte (Ferariu & Cîmpanu, 2013).

Schema procedurii de alocare a valorilor fitness este prezentată în cele ce urmează

(Algoritmul 4.4.). Algoritmul 4.5. descrie procedura genetică care integrează metoda de clasificare

pe ranguri Pareto propusă anterior. În final soluția localizată cel mai aproape de originea spațiului

obiectivelor (𝐿, 𝐶) (4.5.) este aleasă ca fiind rezultatul algoritmului. Această selecție reprezintă

ultima interacțiune cu factorul decizional.

Algoritmul 4.4. Asocierea rangurilor pentru MOO-DB 1: Împarte 𝑃(𝑘) în două clustere 𝐺1(𝑘) și 𝐺2(𝑘) folosind pentru delimitarea acestora 𝑙 și 𝑐.

2: Dacă |𝐺1(𝑘)| < 0.1|𝑃(𝑘)| sau |𝐺1(𝑘)| > 0.9|𝑃(𝑘)| 3: Ajustează 𝑙 și 𝑐 (extindere respectiv reducere)

4: Dacă este cazul unei convergențe riscante

5: Marchează convergența riscantă

6: Clasifică pe ranguri indivizii din 𝐺2 aplicând NSGA I pentru optimizarea lui 𝐿 și 𝐶.

7: Clasifică pe ranguri indivizii din 𝐺1 aplicând NSGA I.

8: Dacă este marcată convergența riscantă

9: Optimizează 𝐿, 𝐶 (minimizare) și 𝐷𝐶𝑁 (maximizare).

10: Altfel Optimizează 𝐿 și 𝐶.

11: Mapează liniar rangurile în valori fitness.

Algoritmul 4.5. Optimizarea multiobiectiv cu încorporarea preferințelor factorului decizional 1: Generează aleator o populație inițială, uniform distribuită pe 𝑆.

2: Îmbunătățește populația cu ajutorul unui algoritm genetic mono-obiectiv aplicat 𝑃𝑔𝑒𝑛 generații.

3: Calculează lungimea și curbura traiectoriilor, cu penalizarea cazurilor inadmisibile.

4: Pentru 𝑀𝐴𝑋𝐺𝐸𝑁 − 𝑃𝑔𝑒𝑛 generații, execută:

5: Calculează valorile fitness folosind procedura prezentată în Tabelul 4.4.

6: Selectează părinții.

7: Generează copiii prin aplicarea operatorilor de încrucișare și de mutație.

8: Calculează L și C pentru traiectoriile codificate de copii cu penalizarea cazurilor inadmisibile.

9: Calculează valorile fitness utilizând procedura descrisă în Figura 4.11.

10: Inserează cei mai buni copii în populație.

11: Stabilește soluția finală.

4.3. Schemă genetică de asignare a valorilor fitness aplicată în problema planificării

traiectoriei unui robot [MOO-AR]

Acest subcapitol descrie o nouă metodă Pareto adaptivă de clasificare pe ranguri pentru

algoritmii genetici de optimizare multiobiectiv [MOO-AR] (Cîmpanu & Ferariu, 2013). Rangurile

sunt asignate după clasificarea indivizilor din populație pe baza punctului nadir difuz și pe baza

valorilor medii ale obiectivelor. Acest tip de grupare sprijină sortarea indivizilor din populație

folosind analiza dominanței și încurajează soluțiile valoroase recomandate în spațiul obiectivelor.

În plus, această grupare preliminară permite controlul foarte eficient al diversității indivizilor din

populație.

Spre deosebire de [MOO-DB], în cazul algoritmului [MOO-AR], populația inițială este

inițializată prin intermediul mai multor optimizări mono-obiectiv aplicate independent pe aceeași

populație generată aleator vizându-se optimizarea fiecărui obiectiv în parte (Cîmpanu & Ferariu,

2013). Din populațiile rezultate după aceste optimizări independente se vor păstra cei mai buni


25

50% dintre indivizi. Dacă algoritmul [MOO-DB] împarte populația în două grupuri bazându-se pe

variaţia dimensiunii primului grup de soluţii pe parcursul a două generații succesive și folosind pe

post de repere două limite 𝑘𝑙 și 𝑘𝑐 configurate în mod adaptiv, algoritmul [MOO-AR] va folosi ca

reper pentru gruparea populației de indivizi soluția virtuală asociată punctului nadir difuz.

Criteriile de validare a unei situații de convergență riscantă în cazul algoritmului [MOO-DB]

sunt verificate prin reducerea rapidă a dimensiunii primului cluster; prin descreșterea alertă a

distanței până la cel mai apropiat vecin în spațiul obiectiv pentru cromozomii din prima grupare;

sau prin descreșterea prea rapidă a distanței medii calculate până la originea spațiului obiectiv.

Spre deosebire de algoritmul [MOO-DB], algoritmul [MOO-AR] prevede două situații separate,

prima considerând că soluția virtuală domină cel puțin 30% din indivizii din populație (cazul 1),

împărţind populația în două grupuri, respectiv cazul în care soluția virtuală domină mai puțin de

30% din indivizii din populație (cazul 2), împărţind populația în trei grupuri.

L

C

G1

G2

max (mean(fj))L

C

G1

G2

G3

min (mean(fj))

max (mean(fj))

Figura 4.7. Gruparea indivizilor pe clustere: cazul 1 (stânga), cazul 2 (dreapta).

4.4. Metodă evolutivă multiobiectiv de planificare a traiectoriei unui robot mobil cu

clasificare adaptivă pe ranguri Pareto folosind cromozomi de lungime variabilă [MOO-

ARCCP]

Metodele [MOO-DB] și [MOO-AR] lucrează cu o populație de indivizi cu reprezentare

cromozomială de lungime fixă, lucru care impune un număr prestabilit și fix de puncte

intermediare în cadrul traiectoriei (Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu, 2013). Pentru

a elimina acest dezavantaj, abordarea [MOO-ARCCP] din acest subcapitol propune utilizarea unor

cromozomi cu lungime variabilă şi foloseşte operatorul de încrucişare prezentat anterior, pentru a

evita generarea de cromozomi copii cu lungime mult mai mare decât cea a cromozomilor părinți.

În plus, lungimea unui cromozom poate fi redusă prin intermediul algoritmului de corecție care

operează ca o metodă hibridă de optimizare locală a cromozomului descris în subcapitolul 4.1. În

principiu, această procedură repară porțiunile inadmisibile ale traiectoriei codificate, ghidând

astfel căutarea exclusiv spre regiunile admisibile.

În cazul metodelor [MOO-DB] și [MOO-AR], numărul de traiectorii admisibile generate

de algoritm în cazul unor scene de lucru de dimensiune mai mare sau având o suprafață mai mare

interzisă deplasării robotului putea fi foarte mic. Existența unor soluții admisibile în populația

inițială constituie o condiție obligatorie pentru ca algoritmul evolutiv de optimizare multiobiectiv


26

să poată genera un rezultat. Metoda [MOO-ARCCP] propune rezolvarea acestui impediment

printr-o procedura de corecție, urmată sau nu de o procedură de reducere a numărului de puncte

intermediare pentru a genera 100% indivizi admisibili în cadrul populației inițiale sau la anumiți

pași din evoluția algoritmului genetic. Descrierile acestor proceduri au fost deja prezentate în 4.1

Cele două obiective nu sunt neapărat puternic conflictuale pe întreg spațiul obiectiv. Pentru

a detecta cât de puternic este conflictul dintre obiective procedura adaptivă pentru calculul

rangurilor ia în considerare dispunerea soluţiilor în spațiul obiectiv și dinamica populației.

Algoritmul 4.7. Procedura MOO_ARCCP

1: Generează în mod aleator populația initială, uniform distribuită pe 𝑊𝑆.

2: Corectează căile inadmisibile și aplică reducerea punctelor intermediare conform lui 𝑃𝑟 (Tabelul 4.9. și

Figura 4.6.)

3: Pentru 𝑀 generații execută

4: Calculează valorile obiectiv optimizând 𝐿 și 𝐶.

5: Calculează valorile fitness considerând schema de clasificare pe ranguri (Algoritmul 4.8.)

6: Selectează părinții folosind selecția stohastică universală.

7: Generează copiii prin intermediul operatorului de încrucișare aritmetic intermediar și aplicând operatorul

de mutație uniformă pentru reprezentări cromozomiale în virgulă mobilă.

8: Corectează copiii inadmisibili (Figura 4.6.) și aplică procedura de reducere a punctelor intermediare în

funcție de 𝑃𝑟 (Algoritmul 4.1.).

9: Calculează valorile obiectiv ale copiilor optimizând 𝐿 și 𝐶.

10: Calculează valorile fitness ale copiilor considerând procedura de clasificare pe ranguri (Algoritmul 4.8.)

11: Inserează celor mai buni copii în populație.

12: Selectează rezultatul algoritmului conform ecuației (4.7.).

L

rS

rL

RS

RL

S

G2 G1

G2 G3

LLL wRLr ,

SSS wRSr ,

L

rS

rL

RS

RL

S

G2 G1

G2 G3

LLL wRLr ,

SRwr SSS ,

Figura 4.8. Exemplificare celor două tipuri de grupare adaptivă. Punctul nadir difuz este

marcat cu o stea. 𝐺1 este colorat cu gri închis, 𝐺2 cu gri deschis și 𝐺3 cu alb.

La final, procedura propusă detectează dacă este necesară îmbunătățirea diversității celor

mai bune soluții. Dacă cele mai bune ranguri din 𝐺1 conțin prea puține soluții distincte va fi folosit

un obiectiv suplimentar pentru redelimitarea fronturilor din 𝐺1. Acest obiectiv suplimentar solicită

maximizarea distanței până la cel mai apropiat vecin 𝐷𝐶𝑁 calculată în spațiul obiectiv (𝐿, 𝑆). Este


27

de așteptat ca alerta apărută la pierderea diversității să fie asociată cu un prim front Pareto ceva

mai compact. Aceasta asociere conduce la cazul în care 𝐺1 conține puține soluții diferite deoarece

limitele grupului sunt date de punctul nadir difuz, iar separarea lor pe ranguri nu implică costuri

computaționale mari.

Separarea adaptivă pe ranguri este descrisă prin Algoritmul 4.8. Utilitatea sa poate fi

evidențiată prin faptul că pierderea diversității este detectată adaptiv, iar variația materialului

genetic este forțată doar dacă este necesar, cu costuri computaționale reduse; utilitatea soluțiilor

este stabilită prin gruparea adaptivă și este reflectată de rangurile asociate; iar dominanța este

analizată pentru grupuri de dimensiune redusă la costuri computaționale reduse.

Algoritmul 4.8. Schema adaptivă de clasificare pe ranguri (𝑃(𝑘))

1: Determină valorile medii ale obiectivelor în 𝑃(𝑘) și punctul nadir difuz.

2: Separă indivizii în grupuri, conform ecuațiilor (4.17.).

3:

Separă pe ranguri, secvențial, indivizii din 𝐺1, 𝐺2 și 𝐺3 aplicând NSGA I, considerând că rangurile

indivizilor din 𝐺1 sunt mai bune decât ale indivizilor din 𝐺2, iar cele associate acestora sunt mai bune decât

ale indivizilor din 𝐺3.

4: Calculează media soluțiilor distincte localizate în prima jumătate de fronturi din 𝐺1 (𝑛𝑜).

5: Dacă 𝑛𝑜 < 𝑛𝑜_𝑙𝑖𝑚 separarea pe ranguri este repetată în 𝐺1 folosind NSGA I, considerând relațiile (4.1.) și

(4.2.) precum și distanța până la cel mai apropiat vecin.

4.5. Schemă genetică adaptivă de asociere a rangurilor Pareto bazată pe clusterizare [MOO-

ARC]

Acest subcapitol prezintă o schemă de asociere a rangurilor Pareto ce urmărește de

asemenea integrarea adaptivă a proceselor de căutare și decizie, personalizată în funcție de

distribuția populaţiei în spațiul obiectiv. Mai exact, distribuția soluțiilor curente și istoricul câtorva

puncte cheie vor fi examinate pentru a caracteriza diversitatea populației la fel ca și natura

conflictului dintre obiective. Această analiză activează atenționările în cazul fronturilor prea mici

sau prea dispersate și declanșează dacă este necesar mecanismul de îmbunătățire a diversității.

Diversitatea este îmbunătățită prin promovarea la un rang superior a soluțiilor izolate într-o gamă

permisă a unui subset de fronturi succesive. Explicații detaliate sunt prezentate în cele ce urmează.

Algoritmul de asociere a rangurilor este descris pentru un set oarecare de soluții P(t) vizând

minimizarea simultană a 𝑓𝑖: 𝑅𝑛 → 𝑅, 𝑖 = 1, 𝑁𝑜. Urmărind ideile prezentate în (Ferariu & Cîmpanu,

2014a; Petrescu & Ferariu, 2009) populația este divizată în câteva grupuri, fiecare specificând o

anumită clasă de utilitate pentru soluțiile conținute. Însă, maniera în care este realizată gruparea

diferă față de abordările precedente prin următoarele particularități: populația curentă este

împărțită în două grupuri 𝐺1(𝑡) conținând soluțiile preferate și 𝐺2(𝑡) conținând restul setului.

Conform regulilor preferențiale adoptate, primul grup reunește soluțiile caracterizate de valori mici

în toate direcțiile obiectiv. Din acest motiv, primul grup este configurat ca un hipercub 𝐺10(𝑡)


28

delimitat în spațiul obiectiv de limitele 𝑀𝑗(𝑡)|𝑗=1,𝑁0̅̅ ̅̅ ̅̅ extinse apoi, ori de câte ori este necesar cu

alte soluții plasate aproape de limitele precedente 𝐺1𝑒𝑥𝑡(𝑡) :

𝐺10(𝑡) = {𝑥 ∈ 𝑃(𝑡)|𝑓𝑖(𝑥) ≤ 𝑀𝑖(𝑡), 𝑖 = 1,𝑁0̅̅ ̅̅ ̅̅ )}

𝐺1(𝑡) = 𝐺10(𝑡) ∪ 𝐺1

𝑒𝑥𝑡(𝑡) 𝐺2(𝑡) = 𝑃(𝑡) ∖ 𝐺1(𝑡)

(4.18)

Urmează să fie clarificat faptul că extensia primului grup permite o manieră simplă și

flexibilă de definire a zonelor preferențiale cu formă neregulată, ușor configurabilă în funcție de

necesitățile populației curente. Înaintea elucidării modului de calculare a marginilor și a extensiei

primului grup, următorul subcapitol explică tipurile de atenționări primite la finalul procesului de

analiză pentru a asista mecanismele adaptive.

Figura 4.9. Construcția grupurilor 𝐺1,2(𝑡) pentru 𝑁𝑜 = 2 ilustrând cele mai bune fronturi

Patero dispersate (#stânga) și de dimensiune redusă (#dreapta). Indivizii sunt reprezentați cu

alb, iar centrii clusterelor cu culoarea roșie. Linia punctată delimitează în figura din dreapta

extensia 𝐺1𝑒𝑥𝑡 utilizată pentru a lărgi zona preferată în afara limitelor marcate de 𝑀1 și 𝑀2.

Algoritmul 4.9. Schema generică de asociere a valorilor fitness [MOO-ARC]

1: Setează valoarea lui NC şi clasifică soluţiile din P(t) folosind k-medii

2: Dacă clusterizarea este efectuată cu succes execută

3: Identifică 𝐹1𝐶(𝑡) şi 𝐹2𝐶(𝑡) conform NSGA

4: Suprascrie 𝐴𝐶(𝑡) cu setul de soluţii non-dominate din 𝐴𝐶(𝑡 − 1) ∪ 𝐹1𝐶(𝑡)

5: Activează mecanismele de semnalare a cazurilor în care soluţiile preferate sunt puţine

sau exagerat de dispersate, dacă este necesar.

6: Calculează limitele 𝐺10(𝑡) conform ecuaţiei prezentate

7: Activează alertarea pentru un 𝐺10(𝑡) mult prea aglomerat, dacă este necesar

8: Dacă nu a fost activată nici o avertizare, va fi activată avertizarea pentru fronturi mult prea

condensate şi se va construi 𝐺1𝑒𝑥𝑡(𝑡)

9: Se va construi 𝐺2(𝑡) în concordanţă cu ecuaţia asociată din (4.18.)

10: Se aplică NSGA în 𝐺1(𝑡) şi apoi în 𝐺2(𝑡) şi se asociază rangurile

11: Dacă este activă alerta pentru o grupare prea înghesuită sau prea dispersată, rangurile din

𝐺1(𝑡) vor fi reajustate

12: Asociază liniar valorile fitness în funcţie de valoarea rangului

După identificarea grupurilor 𝐺1,2(𝑡), NSGA este aplicat în mod independent în interiorul

fiecărui grup, asociind fiecărei soluţii un anumit rang. În concordanţă cu regula preferenţială

adoptată, algoritmul garantează ranguri mai bune indivizilor din 𝐺1 comparativ cu indivizii din 𝐺2.


29

Mai mult de atât, ori de câte ori se impune ca diversitatea să fie îmbunatăţită, rangurile din

interiorul primului grup vor suferi uşoare modificări pentru a favoriza soluţiile solitare. Această

variantă de îmbunătăţire este aplicată în cazul unei alerte de tipul celor pentru o regiune

preferenţială de dimensiune redusă sau excesiv de dispersată. Foarte interesant se remarcă faptul

că această corecţie are roluri diferite în cele două cazuri. Pentru un prim grup destul de restrâns,

trebuie împiedicată convergenţa prea rapidă şi trebuie reparate eventualele neajunsuri produse de

în generaţiile precedente. Contrariu acestei perspective, îmbunătăţirea diversităţii aplicată

fronturilor Pareto dispersate asigură o relevanţă crescută a sortării soluţiilor.

Sortarea parţială poate fi schimbată în cadrul seturilor de p fronturi succesive, fără a altera

ordonarea comparativ cu soluţiile care nu aparţin fronturilor selectate. Mai exact, subseturi de

ranguri adiacente sunt vizitate secvenţial, 𝑆𝑧 = {𝑧 ∙ 𝑝 + 1, … , 𝑧 ∙ 𝑝 + 𝑝}, cu 𝑧 = 0,1, … şi ajustând

rangurile în cadrul fiecărui subset în funcţie de

�̃�(𝒙) = 𝑟(𝒙) + 𝛽 (1 −𝑑𝐶𝑁(𝒙)

max𝒚𝜖𝑃(𝑡)

𝑑𝐶𝑁(𝒚) + 𝛾) + 𝛼𝑧 (4.24.)

unde 𝛼𝑧 , 𝛽, 𝛾 > 0 sunt constante, �̃�(𝒙), 𝑟(𝒙) indică rangul lui 𝒙 după și înainte calibrare, iar

𝑑𝐶𝑁(𝒙) specifică distanţa calculată în spaţiul obiectiv dintre soluţia indicată ca argument şi cel mai

apropiat vecin al său în cadrul lui 𝑃(𝑡) după scalarea valorilor obiectiv în intervalul [0, 1] pe fiecare

axă în parte. În acest caz, 𝛾 este utilizat cu rol de regularizator, în timp ce restul constantelor sunt

folosite pentru a asigura că rangurile din 𝑆𝑧 vor rezulta mai mici decât cele din 𝑆𝑧+1 şi evident mai

mari decât 𝑆𝑧−1. Spre deosebire de partajarea valorilor fitness, rangurile sunt în acest caz asociate

ajustând distanţa până la un singur vecin, indiferent de valoarea acesteia. Acest mecanism permite

un control simplificat a gamei de variaţie a rangurilor. Variaţiile de rang sunt de asemenea

mărginite datorită calibrărilor rezolvate pe subseturi de dimensiune fixă, |𝑆𝑧| = 𝑝.

4.6. Metodă hibridizată de asociere a rangurilor Pareto prin intermediul algoritmului lui

Dijkstra multiobiectiv [MOO-ARCP]

Algoritmii bazați pe grafuri prezentați în cadrul acestui subcapitol sunt capabili să integreze

orice schemă de asociere de ranguri, asigurând în mod implicit compatibilitatea cu orice număr de

obiective. Pentru abordarea hibridă propusă, rolul algoritmului bazat pe grafuri este acela de a

garanta admisibilitatea tuturor soluțiilor procesate de algoritmul genetic, astfel încât acesta să

rămână doar cu responsabilitatea rezolvării unei probleme de optimizare multiobiectiv fără

restricții. Corecția este necesară după fiecare etapă care modifică materialul genetic (inițializarea

populației și generarea urmașilor). Pentru îmbunătățirea interacțiunii dintre algoritmul genetic și

procedura de corecție, ambele sunt dezvoltate în sensul optimizării multiobiectiv şi folosesc

aceeaşi schemă de separare a rangurilor. Mai mult, corecția este combinată cu o reducere aleatoare

a numărului de puncte intermediare (Ferariu & Cîmpanu, 2014b). Traiectoriile reduse rămân

admisibile, dar sunt codificate prin cromozomi de lungime mai mică. Probabilitatea de reducere

𝑃𝑟 are un impact foarte mare asupra diversității soluțiilor și de aceea valoarea acestui parametru

este controlată în mod adaptiv în cadrul buclei genetice. Dezvoltarea procedurii de corecție a


30

traiectoriilor în sens multiobiectiv este principala îmbunătățire adusă metodelor propuse de

(Ferariu & Cîmpanu, 2013; Ferariu & Cîmpanu, 2014a).

Problema de optimizare multiobiectiv este rezolvată prin intermediul algoritmului genetic

prezentat în tabelul de mai jos. Principala buclă evolutivă lucrează pe o populație de cromozomi

cu lungime variabilă, fiecare dintre aceștia codificând o traiectorie potențială. Mai exact, șirul de

gene care formează cromozomul include coordonatele nodurilor intermediare, prezentate ca

variabile de decizie conform ecuației (4.1.). Algoritmul genetic este adaptat cu toate mecanismele

necesare pentru manipularea cromozomilor de lungime variabilă: i) construcția traiectoriilor

inițiale conținând un număr diferit de puncte de viraj (𝑁 < 𝑁𝑚𝑎𝑥 ) în concordanță cu distribuția

uniformă a acestor noduri pe 𝑊𝑆; ii) utilizarea unui operator de încrucișare care să asigure extensia

cromozomului părinte de lungime mai mică (Ferariu & Cîmpanu, 2014b) înainte de aplicarea

operatorului de încrucișare aritmetic standard pentru a evita alterarea fenotipurilor (prin duplicarea

anumitor gene selectate în mod aleator). Algoritmul genetic utilizează schema adaptivă

multiobiectiv de asociere a rangurilor prezentată în (Ferariu & Cîmpanu, 2014a).

Cea de a doua etapă în cadrul procedurii de corecție selectează o rută admisibilă între 𝑉𝑖 și

𝑉𝑗 (Figura 4.5. – dreapta) prin explorarea grafului rezultat prin intermediul unui algoritm

multiobiectiv inovator. Admisibilitatea este garantată de modul în care este construit graful. Pentru

o simbioză reușită cu algoritmul genetic, procedura de corecție trebuie să selecteze traiectorii

compatibile cu obiectivele vizate de algoritmul genetic, care să fie şi cât mai diverse posibil.

Aceasta se traduce în necesitatea de a reformula algoritmul clasic al celei mai scurte căi din

varianta mono-obiectiv în varianta multiobiectiv în conformitate cu restricțiile impuse de problema

de planificare considerată (2). Înlocuirea fragmentului inadmisibil al unei rute va putea genera un

număr oarecare de puncte intermediare.

Spre deosebire de versiunile mono-obiectiv, această procedură de corecție configurează

algoritmul lui Dijkstra astfel încât să determine calea cea mai scurtă în funcție de rangul asociat în

spațiul obiectiv. Pe parcursul explorării grafului, costurile muchiilor ce pleacă dintr-un anumit nod

rezultă din alocarea de ranguri traiectoriilor de adâncime ℎ care poate fi explorată plecând de la

nodul respectiv. Celor mai bune soluții li se asociază primul rang, astfel încât minimizarea costului

să conducă la selecția celei mai bune rute. Ori de câte ori mai multe soluții au asociat primul rang,

soluția cu lungimea minimă va fi preferată. De asemenea, asocierea unui rang favorizează

traiectoriile care se finalizează în 𝑉𝑗 deoarece punctul respectiv marchează finalul corecției. Dacă

se alege o cale intermediară având ℎ > 1, atunci algoritmul continuă din punctul terminal al căii

respective. Acest artificiu permite reducerea timpului de execuție indus de metoda de asociere a

rangurilor, nefiind necesară aplicarea backtraking-ului pentru toate nodurile intermediare (Ferariu

& Cîmpanu, 2014b).

Mai exact, algoritmul de optimizare multiobiectiv bazat pe grafuri conține următoarele

etape. Pentru fiecare nod al grafului în care trebuie continuată căutarea unei căi, se construiește un

arbore prin traversarea în lățime pentru un număr fixat de nivele. Acest arbore este expandat prin

adăugarea muchiilor din graful original care sunt adiacente setului de noduri. Pe baza acestui graf

parțial, setul de căi alternative este generat prin backtracking. O cale începe din rădăcina arborelui

și are lungimea egală cu numărul de niveluri pentru care s-a generat arborele ℎ. Aceste traiectorii

sunt clasificate pe ranguri și muchiile lor componente sunt etichetate cu valoarea celui mai mic

rang ales în funcție de traiectoriile din care muchiile respective fac parte.


31

Algoritmul 4.10. Procedura genetică de optimizare multiobiectiv

1: Generează în mod aleatoriu o populație inițială de traiectorii cu 𝑁 < 𝑁𝑚𝑎𝑥 noduri intermediare uniform

distribuite în spațiul WS;

2: Repară fiecare fragment inadmisibil al acestor traiectorii și reduce numărul de noduri intermediare în funcție

de probabilitatea de reducere 𝑃𝑟

3: Pe parcursul a 𝑀 generații execută,

4: Evaluează lungimea și suma unghiurilor de viraj pentru fiecare traiectorie;

5: Sortează parțial soluțiile prin intermediul procedurii multiobiectiv de asociere a rangurilor

6: Aplică eșantionarea stohastică universală pentru completarea bazinului reproductiv;

7: Aplică operatorii de încrucișare și mutație pentru a genera populația de copii;

8: Adaptează valoarea probabilității de reducere 𝑃𝑟 pe baza indicatorilor care descriu diversitatea soluțiilor;

9: Repară populația de copii inadmisibili (după izolarea fragmentelor inadmisibile ale unei traiectorii) aplică

procedura de reparare și reducere conform probabilității 𝑃𝑟;

10: Calculează valorile obiectiv ale indivizilor ce formează populația de copii;

11: Sortează parțial soluțiile în conformitate cu schema adoptată;

12: Înlocuiește cele mai slab adaptate soluții cu soluții având performanțe superioare din populația de copii;

13: Stabilește rezultatul final conform ecuației (4.7.).

Aşa cum a fost indicat în cadrul secțiunii 4.1, reducerea numărului de puncte intermediare

aplicată unui lanț aciclic de puncte este aplicată până la obținerea celui mai scurt lanț admisibil.

Secvențial, procedura de reducere înlocuiește segmentele adiacente 𝑉𝑖𝑉𝑖+1 și 𝑉𝑖+1𝑉𝑖+2 cu

conexiunea directă 𝑉𝑖𝑉𝑖+2 dacă restricţia nu este încălcată. Dacă nu poate avea loc înlocuirea,

reducerea continuă cu următoarea secvență 𝑉𝑖+1𝑉𝑖+2𝑉𝑖+3, altfel cu 𝑉𝑖+2𝑉𝑖+3𝑉𝑖+4. Reducerea este

aplicată iterativ până când nu se mai marchează nici o modificare la parcurgerea completă a șirului

de puncte (Ferariu & Cîmpanu, 2014). Fiind activată probabilistic, reducerea poate fi aplicată unui

număr variabil de indivizi. Valori mici ale probabilității de reducere 𝑃𝑟 pot fi folosite pentru

păstrarea diversității materialului genetic. Pentru un mai bun control al impactului lui 𝑃𝑟, valorile

acestuia sunt modificate adaptiv în interiorul buclei genetice. Diversitatea este monitorizată în

spațiul genotipic prin intermediul distanței până la cel mai apropiat vecin având același număr de

puncte intermediare (GMD). Variațiile mari ale lui GMD la generații succesive activează

creșterea/descreșterea lui 𝑃𝑟.

4.7. Rezultate experimentale

În cazul primilor doi algoritmi prezentați [MOO-DB] și [MOO-AR], pentru validarea

eficienței acestora au fost folosite trei scene de lucru (𝑊𝑆1,𝑊𝑆2 și 𝑊𝑆 3), reprezentând diverse

hărți de obstacole (ca amplasare sau densitate a obstacolelor în funcție de dimensiunea scenei de

lucru a robotului), de dimensiune 8𝑥8 sau 16𝑥16. Pe scena de lucru 𝑊𝑆1 de dimensiune 8𝑥8

(Figura 4.1.) există un singur obstacol cu formă concavă care poate fi ocolit foarte ușor de

traiectorii admisibile. Admisibilitatea unei traiectorii este mai greu de obținut în celelalte două

scene de lucru, 𝑊𝑆2 și 𝑊𝑆3. Scena de lucru 𝑊𝑆2 are un obstacol cu formă concavă și arie de

acoperire de 43.75% din suprafața scenei de dimensiune 8𝑥8, iar 𝑊𝑆3 conține atât blocuri

convexe cât și blocuri concave de diverse dimensiuni, distribuite pe un grid de dimensiune 16𝑥16

(Figura 4.13.). Pentru validarea performanțelor algoritmului [MOO-ARCCP] pe lângă scenele de

lucru 𝑊𝑆1 și 𝑊𝑆2, va fi folosită scena 𝑊𝑆4 de dimensiune 16𝑥16 cu o densitate de obstacole de

31.25% (Figura 4.13.).


32

Pentru [MOO-DB] configurațiile (#) experimentale sunt stabilite pentru diverse localizări

ale punctelor terminale 𝑠𝑡𝑎𝑟𝑡 și 𝑠𝑡𝑜𝑝 și pentru un număr diferit de puncte intermediare, inițial

𝑁min. 𝑁𝑚𝑖𝑛 indică numărul minim de puncte intermediare necesar pentru a forma o traiectorie

admisibilă (toate traiectoriile care trec prin 𝑁 < 𝑁𝑚𝑖𝑛 puncte intermediare fiind inadmisibile), o

serie de rezultate fiind prezentate în Figura 4.10.

Figura 4.10.a. [MOO-DB] Scena WS2 cu traiectoriile obținute: #7 (stânga sus), #8

(stânga jos). b. Scena WS3 cu traiectoriile obținute: #9(dreapta sus), #10(dreapta jos)

Aplicabilitatea metodei de optimizare multiobiectiv cu clasificare adaptivă pe ranguri

Pareto [MOO-AR] este verificată și validată pe cele trei scene de lucru 𝑊𝑆1,𝑊𝑆2 și 𝑊𝑆3 descrise

anterior având dimensiuni și hărți de obstacole diferite (Figura 4.11.).

Performanțele metodei [MOO-ARCCP] sunt investigate pe scenele de lucru indicate în

Figurile 4.10. și 4.13., în funcție de configurațiile descrise în Tabelul 4.7.

Pentru a asigura o perspectivă mai clară asupra performanţelor metodei [MOO-ARC], setul

de experimente se constituie sub forma unor binecunoscute probleme de optimizare bi-obiectiv,

exemplificând distribuţii diferite ale fronturilor Pareto optimale: convexe (#1), concave (#2 și #4)

sau discontinue (#3).

Deoarece MOO-ARCP implică o procedură multiobiectiv de asociere a rangurilor în cadrul

procedurii de corecţie, căutarea nu este direcționată exclusiv către minimizarea lui 𝐿 cum este

cazul procedurii [𝐴1]. Această îmbunătățire a capacității de explorare ajută procedura MOO-

ARCP să găsească cele mai bune rute pentru aproape toate experimentele. O parte din rezultatele

obținute sunt ilustrate în Figura 4.20. Aceste traiectorii sunt admisibile, au un număr redus de

puncte intermediare și distanță nesemnificativă față de conturul obstacolelor.

Figura 4.11. Traiectoriile rezultate: WS1 #1 (stânga), WS2 #5 (centru), WS3 #6 (dreapta)


33

Figura 4.14. Scenele de lucru utilizate pentru [T1]: #1 în stânga, #2 în mijloc şi #3 în dreapta.

Figura 4.20. Rutele selectate de procedura MOO-ARCP pentru scena de lucru WS1-b (stânga

sus), WS2 (dreapta sus), WS3 (stânga jos) şi WS4 (dreapta jos).

În cadrul acestui capitol sunt prezentați algoritmii genetici de optimizare multiobiectiv

propuşi pentru rezolvarea unei probleme de planificare a traiectoriei optimale pentru un robot

mobil. O serie a îmbunătăţiri vizează calculul valorilor fitness, astfel încât să se permită integrarea

graduală a preferinţei pentru mijlocul primelor fronturi Pareto cu căutarea, asigurând îmbunătăţirea

adecvată a diversităţii materialului genetic. Fiind bazate pe folosirea fronturilor Pareto, toate aceste

proceduri pot fi aplicate cu succes pentru rezolvarea problemelor de optimizare multiobiectiv cu

un număr redus de obiective, nefiind limitate la aplicaţia prezentată.

În acest context, algoritmul [MOO-DB] calculează rangurile Pareto lucrând separat pe

grupuri de soluţii (Ferariu & Cîmpanu, 2013). Gruparea este configurată să direcționeze gradual

procesul de căutare către mijlocul frontului Pareto, prin calcularea separată a rangurilor în două

grupuri, unul incluzând soluţiile preferate, şi anume soluţiile cu performanțe mai bune decât media

populaţiei. Algoritmul monitorizează numărul soluţiilor preferate, distanţa medie a acestora până

la cel mai apropiat vecin (DCN) şi până la origine în spaţiul valorilor obiectiv, pentru a detecta

dacă îmbunătăţirea materialului genetic este necesară. Diversificarea este susţinută doar în grupul

soluţiilor preferate, folosind un obiectiv suplimentar, şi anume maximizarea DCN.

Schema de determinare a rangurilor propusă în (Cîmpanu & Ferariu, 2013) [MOO-AR],

rafinează modul de stabilire a soluţiilor preferate, cu scopul de permite asocierea rangurilor în mai

bună concordanţă cu natura conflictului dintre obiective. Populaţia este împărţită în două sau trei

grupuri (Cîmpanu & Ferariu, 2013). Repartizarea soluțiilor pe grupuri se realizează pe baza

numărului de soluții dominate de soluția virtuală optimă: două grupuri în cazul în care soluția

virtuală domină suficiente soluții bine adaptate, respectiv trei grupuri în cazul în care există un

număr redus de soluții valoroase și se dorește încurajarea explorării. Procedura de asociere a


34

rangurilor presupune introducerea unui nou obiectiv – maximizarea distanței până la cel mai

apropiat vecin - pentru îmbunătăţirea diversității, dacă se detectează o aglomerare a soluțiilor în

primele fronturi sau existența unui număr redus de soluții valoroase. Modul propus de separare a

soluţiilor pe grupuri permite asocierea convenabilă a rangurilor şi în cazul unor obiective mai putin

conflictuale.

Pentru o analiză mai pertinentă a distribuţiei populaţiilor de soluţii, utilă pentru integrarea

graduală dintre decizie şi căutare, metoda propusă de asociere a rangurilor bazată pe clasificare

nesupervizată [MOO-ARC] aplică algoritmul k-medii pentru gruparea nesupervizată a soluţiilor

în spaţiul obiectiv şi apoi analizează dominanţa centrilor clusterelor rezultate. Astfel, algoritmul

extrage informaţii valoroase legate de natura conflictului dintre obiective, ceea ce permite

stabilirea soluţiilor preferate şi monitorizarea diversităţii soluţiilor. Pentru îmbunătăţirea

diversităţii, este introdusă o procedură care modifică rangul soluţiilor solitare, considerând în

secvenţă subseturi de ranguri succesive.

Alte contribuţii prezentate în acest capitol vizează dezvoltarea unui operator de încrucişare

pentru cromozomi cu lungime variabilă codificând traiectoriile robotului mobil şi un algoritm de

corecţie pentru traiectoriile care nu ocolesc obstacolele. În acest mod, toate soluţiile din populaţie

sunt păstrate admisibile şi explorarea prin intermediul algoritmului genetic, efectuată în jurul

oricărei soluţii din populaţie devine de interes (Ferariu & Cîmpanu, 2014) în [MOO-ARCCP].

Tehnicile propuse pentru corecția traiectoriilor care rezultă inadmisibile au ca scop transformarea

soluțiilor inadmisibile în admisibile prin înlocuirea unor segmente incluse în traiectorie. De

asemenea, pentru a evita generarea de traiectorii cu multe puncte intermediare, pe traiectoriile

corectate se aplică o reducere a numărului de puncte intermediare care menţine traiectoriile

admisibile. Repararea porțiunilor din traiectorii care nu respectă restricţia de ocolire a obstacolelor

este realizată pe baza triangulațiilor Delaunay și a algoritmului lui Dijkstra (Ferariu & Cîmpanu,

2014). Algoritmului lui Dijkstra este folosit considerând costurile în graf egale cu lungimea

traiectoriei corespunzătoare. Strategia de clasificare pe ranguri este adaptată în funcție de

distribuția soluțiilor în spațiul obiectiv și în funcție de performanțele populației curente, prin

intermediul unei grupări preliminare; asigurând simultan controlul direct al diversității oricând este

necesar.

[MOO-ARCP] îmbunătăţeşte procedura de corecţie prin extinderea algoritmului lui

Dijkstra în sens multiobiectiv. Pentru aceasta, graful este definit astfel încât costurile muchiilor ce

pleacă dintr-un nod să corespundă rangurilor traiectoriilor de adâncime h. Această limitare a

adâncimii permite evitarea obţinerii unor grafuri excesiv de mari, în care căutarea ar fi costisitoare.

Procedura propusă permite utilizarea aceleiaşi scheme de determinare a rangurilor în procedura de

corecţie şi în algoritmul genetic, ceea ce aduce avantaje atât pentru explorare, cât şi exploatare.

Performanţele metodelor propuse au fost verificate experimental pe diferite scene de lucru

care includ obstacole disjuncte, non-convexe. Pentru a ilustra dificultatea de găsire a unor

traiectorii admisibile pe diferite hărţi de obstacole şi localizări ale punctelor de start şi stop, au fost

introduşi indicatori definiţi pe baza unui set numeros, aleator de soluţii iniţiale. În cazul [MOO-

ARC], rezultatele experimentale au inclus şi probleme suplimentare de optimizare bi-obiectiv

definite sintetic pentru a evidenţia fronturi Pareto convexe sau non-convexe şi diferite tipuri de

relaţii conflictuale între obiective.

35

Capitolul 5

Aplicații ale metodelor genetice de optimizare

multiobiectiv în selecția atributelor

În domeniul neuroștiințelor cognitive, memoria de lucru (sau de scurtă durată) reprezintă

capacitatea unei persoane de a reține informații multiple pe durata soluționării unei probleme

(Murphy et al., 2016). Încărcarea cognitivă este definită ca fiind volumul de solicitare mentală

aplicat memoriei de lucru pe parcursul rezolvării unei sarcini (Zarjam et al., 2011). În cadrul

sistemelor critice de tip interfață creier-mașină, nivelul de încărcare cognitivă al operatorului uman

este relaționat în principal cu performanța obținută în rezolvarea unei anumite activități (Murphy

et al., 2016). Încărcarea cognitivă este asociată așadar activităților memoriei de lucru. Menținerea

unui nivel adecvat de concentrare va maximiza acuratețea și eficiența personalului, în domenii ca

de exemplu controlul traficului aerian, centrale nucleare, transport public sau operațiuni militare

unde orice diminuare a performanței poate genera accidente catastrofale (Murphy et al., 2016;

Zarjam et al., 2011; Zhong &Jianhua, 2016). În acest domeniu, proiectarea și evaluarea sarcinilor

de lucru se bazează pe analiza încărcării cognitive (Fallahi et al., 2016). Tehnologia de interfațare

creier-mașină existentă în prezent (Das et al., 2015) face posibilă analizarea încărcării cognitive în

domenii în care acest proces este unul critic dar extrem de folositor (Zhong & Jianhua, 2016;

Fallahi et al., 2016; Das et al., 2014). Pentru aceasta, dispozitive EEG de cost scăzut sunt

comparate după precizie și aplicabilitate (Das et al., 2015).

Activitățile de evaluare continuă a performanțelor cognitive de tip ”n-back”(-engl. [cu 𝑛

pași în urmă]) au fost inventate de Wayne Kirchner ca o măsură a capacității memoriei de lucru

(Gazzaniga, 2009). Acest tip de activitate este foarte folosit pentru indentificarea nivelului de

încărcare a memoriei de lucru grație proprietății sale de a reflecta procese cognitive generale de

tipul memorare și extragere de informații sau actualizare – înlocuirea conținutului memoriei cu

informații actualizate (Wang et al., 2016). În timpul unei activități de tip ”n-back”, subiectul de

test primește o secvență de stimuli vizuali sau auditivi (litere, numere, imagini, etc.) și trebuie să

semnaleze potrivirile între stimulul curent și unul din stimulii primiți cu n pași înainte în secvență.

În cadrul acestui capitol datele EEG sunt achiziționate în timpul unor activități de tip n-back sau

aritmetice cu stimuli vizuali. Factorul de încărcare este configurat între 0 și 3 în sensul

incrementării dificultății activității. Pentru exemplificarea rezultatelor obținute va fi utilizată

anvelopa semnalului EEG (rădăcina medie pătratică) calculată în anumite benzi de frecvenţă

relevante pentru problema de grupare supervizată.

Atunci când analiza semnalelor EEG este folosită în dezvoltarea unei interfețe standard

între creierul uman și calculator, trebuie considerate următoarele blocuri: achiziția de date EEG,

preprocesarea acestora, identificarea trăsăturilor relevante și clasificarea tiparelor EEG rezultate.

Extragerea şi selecţia de trăsături pentru date de tip EEG este poate una din cele mai ambițioase

5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția atributelor

36

etape în dezvoltarea unui sistem BCI. De obicei, semnalele EEG în formă brută sunt transformate

în domeniu frecvență și trăsăturile sunt selecționate din anumite benzi de frecvență (Sweet, 2011;

Amin et al., 2016; Ungureanu et al., 2017). Găsirea setului minimal de trăsături EEG care să

asigure o clasificare corectă a tiparelor EEG este foarte dificilă, deoarece dependenţele dintre

variabile nu sunt complet cunoscute, exemplele din setul de antrenare sunt foarte multe, datele sunt

zgomotoase şi numărul iniţial al trăsăturilor este mare. (Martin-Smith et al., 2017; Upadhyay et

al., 2015). Fiind colectate în urma interacțiunii cu ființe umane, datele pot fi inconsistente. Dintr-

o perspectivă strict computațională, prin lucrul cu seturi de atribute cu cardinalitate redusă se evită

supradeterminarea și se intensifică capacitatea de generalizare a clasificatorului. Din acest motiv

scad și timpii de execuție în cadrul BCI. Mai mult, selecția atributelor poate susține înțelegerea

unor aspecte suplimentare legate de procesele cognitive și poate ajuta la proiectarea unor

echipamente de dimensiune redusă, care să îi ofere confort sporit utilizatorului (Lorenz & Rejer,

2015; Martin-Smith et al., 2017). Această ultimă remarcă se datorează și partiționării anatomice a

creierului uman pe regiuni. Această asociere a regiunilor cu diferite tipuri de activități poate ajuta

la eliminarea anumitor canale începând din etapa de achiziție a datelor (Handiru & Prasad, 2016).

Aşa cum a fost menţionat anterior, abordările specifice selecției de trăsături pot fi rezolvate

şi fără a ține cont de un anumit tip de clasificator, prin abordări de tip filtru (”filter”-engl.) care

evaluează rolul fiecărei trăsături sau a celor de tip colectiv (”wrapper”-engl.) care evaluează

subseturi de trăsături. Aceste tipuri de metode sunt uzual bazate pe analize statistice limitate la

detecția unor dependențe liniare. În această privință, indicatori statistici cum sunt media, rădăcina

pătratică medie sau cros-corelația maximă calculate pentru segmente EEG de lungime fixă

achiziționate în timpul activităților de încărcare cognitivă sunt prezentate în (Ungureanu et al.,

2017). Investigarea tuturor subseturilor de trăsăsturi pentru metode prin împachetare sau

incorporate nu este rezonabilă din punct de vedere computaţional. Considerând dimensiunea

spațiului subseturilor potențiale ce ar trebui explorat, utilizarea algoritmilor genetici este

recomandată. Mai mult, aceștia pot gestiona o optimizare de tip multiobiectiv prin evaluarea

rafinată a vectorilor de trăsături din mai multe perspective. În acest caz, eroarea de clasificare este

calculată după antrenarea mai multor tipuri de clasificatori: hărți cu auto-organizare, SVM și SVM

multi-clasă. Câteva metode propuse, bazate pe algorimi genetici mono-obiectiv şi multi-obiectiv

sunt discutate în continuare.

După cum s-a menționat deja, în cadrul acestui capitol problema de optimizare este

rezolvată cu ajutorul algoritmilor genetici. Fiecare soluție candidat mapează prezența (𝑓 = 1) sau

absența (𝑓 = 0) unui anumit atribut prin intermediul unui cromozom binar de lungime 𝑀 = 56 de

forma:

𝑥 = [𝑓1, … , 𝑓56] = [𝑓𝛼1 , … , 𝑓𝛼14 , 𝑓𝛽1 , … , 𝑓𝛽14 , 𝑓𝛾1 , … , 𝑓𝛾14 , 𝑓𝜃1 , … , 𝑓𝜃14] (5.8.)

În relația (5.8.), 𝛼, 𝛽, 𝛾 și 𝜃 ilustrează undele Alfa, Beta, Gama și Theta ale semnalului EEG

achiziționat pe cele 14 canale indicate în figura 1 și anume: FP1, F7, F3, C3, P3, P7, O1, O2, FP2,

F8, F4, C4, P4 și P8 (Cîmpanu et al., 2017).

Selecția trăsăturilor relevante este efectuată în concordanță cu minimizarea următoarelor

funcții obiectiv:

𝐶𝐸𝑅𝑅(𝑥) =𝑁 − 𝐶𝐶𝑆(𝑥)

𝑁∙ 100 (5.9.)


37

𝑁𝑆𝐹(𝑥) =∑𝑓𝑖

𝑁

𝑖=1

(5.10.)

unde 𝑥 notează o soluție candidat definită conform relației (5.8.), 𝑁 este numărul de tipare, 𝐶𝐸𝑅𝑅

indică eroarea de clasificare, iar 𝐶𝐶𝑆(𝑥) reprezintă numărul de tipare correct clasificate care

rezultă după antrenarea clasificatorului conform selecției de atribute din 𝑥, iar 𝑁𝑆𝐹 contorizează

numărul total de atribute implicate în procesul de clasificare.

5.6. Selecția atributelor EEG în seturi de date de dimensiune foarte mare. Procedură

genetică de optimizare multiobiectiv bazată pe comutarea între clasificatori

Dubla verificare a acurateței de clasificare este realizată prin comutări periodice între

diferiți clasificatori. Implementarea mecanismului de comutare implică o simplă modificare a unui

algoritm genetic standard indiferent de configurația acestuia (Figura 5.20.). Este evident că acest

mecanism de comutare este compatibil cu orice tip de clasificator și cu orice număr de tipuri de

clasificatori alternativi implicați. Oricum, creșterea numărului de metode de clasificare implicate

în asocierea valorilor fitness determină creșterea dimensiunii populației și utilizarea unor tehnici

eficiente de îmbunătățire a diversității indivizilor pentru a putea permite supraviețuirea soluțiilor

etichetate a fi valoroase de câteva dintre metodele de clasificare. Pe parcursul evaluării, aceste

soluții pot direcționa explorarea în spațiul de căutare. Aceste soluții validate de toți clasificatorii

folosiți vor avea asociate probabilități de selecție ridicate; din acest motiv se urmărește în

perspectivă prezența unor indivizi adaptați în raport cu doi clasificatori în cadrul populației finale

(Cîmpanu et al., 2017).

Schema propusă este compatibilă atât cu optimizări mono-obiectiv cât și cu optimizări

multiobiectiv. În cele ce urmează vor fi prezentate două configurații pentru asocierea rangurilor

Pareto derivate conform mecanismului de comutare, pentru a ilustra și motiva utilitatea comutării

și pentru a demonstra impactul procedurii de actualizare a valorilor fitness în diverse contexte

evolutive (Cîmpanu et al., 2017).

Algoritmul 5.1. Procedura genetică de optimizare multiobiectiv bazat pe comutare 1: Generează în mod aleator o populație de soluții conținând 𝐼𝑁𝐷 indivizi codificați binar, definiți conform

ecuației (5.8.).

2: Selectează tipul de clasificator (în acest caz, RF sau SVM)

3: Pentru maxim 𝐺𝐸𝑁 generații execută:

4: O dată la 𝐺𝐸𝑁𝑐 generații comută între tipurile de clasificatori utilizate pentru evaluare.

5: Calculează valorile obiectiv ale soluțiilor în conformitate cu clasificatorul adoptat și asociază

valorile fitness prin intermediul rangurilor soluțiilor.

6: Selectează 𝐼𝑁𝐷/2 indivizi pentru recombinare cu selecție stohastică universală.

7: Generează 𝐼𝑁𝐷/2 copii folosind încrucișarea discretă, cu probabilitate 𝑃𝑐 = 0.7.

8: Aplică mici variații asupra materialului genetic al copiilor cu ajutorul mutațiilor cu probbailitatea

𝑃𝑚 = 0.1. 9: Calculează valorile fitness ale copiilor.

10: Selectează 𝐼𝑁𝐷/2 indivizi pentru recombinare cu selecție stohastică universală.

Mecanismul de comutare poate fi exemplificat pentru diverse configurații ale unui algoritm

genetic aplicat pentru extragerea de trăsături datorită compatibilității existente. În acest subcapitol,

utilizarea mecanismului de comutare este ilustrată pentru două metode de asociere a rangurilor


38

după cum urmează. În plus, pentru o analiză experimentală completă, alți algoritmi genetici fără

comutare sunt aduși în discuție. În acest demers, 𝑆𝑂𝑂 − 𝐸𝑅𝑅 este procedura mono-obiectiv ce

vizează minimizarea erorii de clasificare și antrenează un singur tip de clasificator în cadrul buclei

evolutive, RF sau SVM, în timp ce 𝑆𝑂𝑂 − 𝐴𝐺𝐺𝑅 minimizează o funcție obiectiv rezultată din

agregarea liniară între eroarea de clasificare și numărul de atribute selectate, fără a comuta între

cei doi clasificatori. După cum a fost demonstrat experimental, 𝑆𝑂𝑂 − 𝐸𝑅𝑅 și 𝑆𝑂𝑂 − 𝐴𝐺𝐺𝑅 au

capacitate limitată de explorare, ambii fiind ineficienți pentru eliminarea atributelor irelevante.

Procedura standard de asociere a rangurilor pentru abordările multiobiectiv prezentată în

acest studiu este NSGA-ul propus de Deb (MOO-NSGA din Tabelul 5.8.). MOO-NSGA (Deb,

2011) este aplicat fără alte mecanisme de comutare. Variantele ulterioare de optimizare MOO-

COM1 și MOO-COM2 includ mecanisme de comutare între cele două tipuri de clasificatori.

Atunci când este aplicat pe seturi de date de dimensiune mare, descrise printr-un număr mare de

atribute, se MOO-COM1 poate să reducă atât numărul atributelor selectate cât și dependența de

un anumit tip de clasificator mai eficient decat MOO-NSGA. Cea de-a doua variantă de asociere

a rangurilor, exploatează faptul că mecanismul de comutare necesită reevaluarea tuturor soluțiilor

pentru compatibilitatea la nivel de acuratețe de clasificare cu noul clasificator adoptat pentru

generațiile în cadrul cărora este activat acest mecanism (Cîmpanu et al., 2017c).

5.7. Procedură evolutivă configurată dinamic pentru selecția de trăsături bazată pe

utilizarea extensiilor temporale

În acest subcapitol, selecția de trăsături este definită în raport cu minimizarea erorii de

clasificare, dar și cu numărul de trăsături selectate. Cromozomii sunt construiți în concordanță cu

o reprezentare care să permită extinderea setului de valori al trăsăturilor curente prin adăugarea

valorilor anterioare ale acelorași trăsături, oferind așadar o imagine mai clară a dinamicii

activităților mentale. De obicei, dinamica este caracterizată de atribute care indică anvelopa

semnalului EEG pentru anumite forme de undă obținute după filtrarea semnalului. Din acest motiv,

un singur vector de trăsături va cuprinde informații despre semnalul EEG din tipare consecutive.

O descriere mai rafinată a semnalului EEG este oferită prin introducerea valorilor anterioare ale

atributelor în setul curent, aceste variații oferind clasificatorului informații pe parcursul unei

ferestre temporale extinse. Această expansiune aduce însă dezavantajul creșterii dimensiunii

setului de trăsături potențiale dar și a spațiului de explorat. În acest context, se va utiliza o

codificare compactată folosind valori întregi și se vor utiliza două tehnici care să conducă la o

explorare rapidă și eficientă. În primul rând, structura clasificatorului încorporat este crescută

gradual. În al doilea rând, eroarea de clasificare este diminuată prin introducerea unei funcții

obiectiv dinamice care să permită evaluarea complexității vectorului de trăsături selectate.

Optimizarea multiobiectiv este rezolvată utilizând un algoritm genetic cu codificare în

mulțimea numerelor naturale. Mai exact, fiecare cromozom este obținut prin concatenarea a patru

subșiruri de câte 14 gene corespunzând formelor de undă Alfa, Beta, Gamma și Theta filtrate de

pe cele 14 poziţii anterior menționate. Codificarea adoptată este o codificare în baza 4 și are rolul

de a indica prin intermediul alelelor dacă un atribut este selectat și dacă se folosesc valori întârziate

ale acestuia. Un astfel de cromozom de lungime fixă este definit după cum urmează:

𝑉 = [𝑔1, 𝑔2, … , 𝑔𝑀] (5.12.)


39

unde 𝑔𝑖 cu 𝑖 = 1,𝑚̅̅ ̅̅ ̅̅ și 𝑀 = 56 este gena asociată trăsăturii 𝑖 din 𝐷. Decodificarea genei 𝑔𝑖 se face

după cum urmează:

𝑔𝑖 =

{

0, 𝑒𝑙𝑖𝑚𝑖𝑛ă 𝑓(𝑘)

1, 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑎𝑧ă 𝑓𝑖(𝑘)

2, 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑎𝑧ă 𝑓𝑖(𝑘), 𝑓𝑖(𝑘 − 1)

3, 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑎𝑧ă 𝑓𝑖(𝑘), 𝑓𝑖(𝑘 − 1), 𝑓𝑖(𝑘 − 2)

(5.13.)

unde 𝑓𝑖(𝑘) indică valoarea atributului 𝑖 de la momentul de timp 𝑘 al sesiunii înregistrate. În cea

de-a doua ecuație, 𝑓𝑖(𝑘) indică valoarea curentă a atributului 𝑖, în timp ce 𝑓𝑖(𝑘 − 1) și 𝑓𝑖(𝑘 − 2)

indică valorile de la momentele de timp anterioare ale aceleiași trăsături. Decodificarea lui 𝑔𝑖 este

reprezentată pentru o întârziere de maxim 2 unități, dar poate fi extinsă și pentru alte valori.

Conform schemei de codificare prezentate, lungimea cromozomului nu depinde de

întârzierile folosite și singura schimbare care va trebui aplicată la modificarea întârzierii maxime

este baza în care sunt codificate genele, în acest caz baza este 𝐵 = 4 = 𝐿𝑎𝑔𝑀𝑎𝑥 + 2. Pentru o

bază de codificare oarecare, acest lucru presupune explorarea unui spațiu de dimensiune 𝐵𝑀 al

soluțiilor potențiale. Codificarea binară ia în calcul și soluții care folosesc doar anumite valori

anterioare, cum ar fi de exemplu 𝑓𝑖(𝑘) și 𝑓𝑖(𝑘 − 2) fără a considera și 𝑓𝑖(𝑘 − 1).

Algoritmul 5.2. Procedura genetică de optimizare multiobiectiv folosită pentru selecția

de trăsături 1: Generează în mod aleator o populație de 𝑁𝐼𝑁𝐷 indivizi conform relațiilor (5.12.) și (5.13.).

2: Evaluează indivizii din populația inițială conform relațiilor (5.14.) și (5.15.). Se va aplica un clasificator de

tip RF configurat cu 𝑁𝑇 arbori și antrenat pe 5% din datele din set.

3: Pentru 𝐺 generații execută:

4: Asociază valorile fitness folosind NSGA;

5: Selectează 𝑁𝐼𝑁𝐷/2 indivizi pentru recombinare, prin intermediul selecției stohastice universale;

6: Generează 𝑁𝐼𝑁𝐷/2 copii, aplicând operatorul de încrucișare discretă cu probabilitate de 0.7, urmat

de operatorul de mutație aleatoare uniformă cu o probabilitate de 0.1;

7: Calculează valorile fitness ale copiilor și inserează cei mai buni 𝑁𝐼𝑁𝐷/4 dintre ei în populație prin

înlocuirea soluțiilor slab adaptate existente;

8: Conform procedurii de selecție și generației curente, actualizează 𝑁𝑇, 𝑃 sau ambii parametri dacă

este necesar;

9: Dacă 𝑁𝑇 sau 𝑃 au fost actualizați, atunci reevaluează toți indivizii în conformitate cu relațiile (5.14.)

și (5.15.) pentru nole valori ale lui 𝑁𝑇 și 𝑃.

10: Alege rezultatul algoritmului din centrul frontului Pareto non-dominat.

Selectarea celor mai reprezentative trăsături EEG pentru identificarea nivelelor de

încărcare cognitivă este realizată urmărind minimizarea următoarelor funcții obiectiv:

𝑀𝑅(𝑉) =𝑁 − 𝐶𝐶(𝑉)

𝑁∙ 100 (5.14.)

𝑁𝐹(𝑉) = [∑𝑔𝑖𝑃

𝑀

𝑖=1

] (5.15.)


40

unde 𝑉 indică vectorul de trăsături selectate, 𝑁 este numărul de tipare disponibile în set, 𝐶𝐶(𝑉)

indică numărul de tipare clasificate corect, [∎] indică partea întreagă a unui număr real și 𝑃 ≥ 1

un parametru de tip întreg care indică nivelul de detaliu aplicat pentru al doilea obiectiv. În acest

caz, vectorul 𝑉 este construit în conformitate cu relațiile (5.12.) și (5.13.); incluzând atât valorile

curente, cât și valorile precedente ale atributelor.

Pentru a eficientiza explorarea unui spațiu de căutare vast, sunt propuse două tipuri de

îmbunătățiri. Una dintre ele o reprezintă folosirea funcțiilor obiectiv dinamice care să descrie

dimensiunea vectorilor de trăsături. Această tehnică permite minimizarea în special a obiectivului

principal prin reducerea graduală a numărului de trăsături selectat. Cea de-a doua îmbunătățire se

referă la configurarea numărului de arbori de decizie utilizați în gruparea supervizată de algoritmul

RF. Simplificarea structurii algoritmului RF permite reducerea efortului computațional, creșterea

acestuia fiind permisă la finalul buclei evolutive pentru indivizii care vor ajunge în populația finală.

5.8. Sistem fuzzy pentru selecția genetică a trăsăturilor EEG în seturi de date de

dimensiune foarte mare

În acest subcapitol este prezentat un mecanism fuzzy de eliminare a atributelor EEG

irelevante, integrat în algoritmul genetic. Soluțiile ce conțin atribute irelevante primesc penalizări

la nivel de rang, încurajându-se în acest fel dezactivarea genelor inutile. Cele două abordări

multiobiectiv inovatoare propuse pentru selecția atributelor din semnalele EEG sunt: MOO-FRIF

și MOO-FPDIF. Ambele proceduri de optimizare multiobiectiv descurajează gradual și elimină

atributele EEG cu influență negativă în cadrul mecanismului decizional al clasificatorilor RF și

SVM. În cadrul acestui studiu se va lucra pe o populație inițială generată în mod aleator, conținând

cromozomi codificați în binar. Procedurile genetic propuse urmăresc optimizarea acurateței de

clasificare și a complexității clasificatorului în funcție de următoarele funcții obiectiv (5.9.) și

(5.10.).

Două proceduri de optimizare mono-obiectiv parcurg spațiul obiectiv pentru a minimiza

fie eroarea de clasificare 𝑆𝑂𝑂 − 𝐸𝑅𝑅, fie pentru a obține un compromis relevant între eroarea de

clasificare și numărul atributelor EEG selectate 𝑆𝑂𝑂 − 𝐴𝐺𝐺. O a treia procedură de optimizare

mono-obiectiv vizează integrarea unui mecanism fuzzy de clasare a atributelor EEG irelevante.

Trei proceduri de optimizare multiobiectiv pentru selecția atributelor EEG sunt analizate și

comparate: o procedură de optimizare multiobiectiv standard bazată pe NSGA (MOO-NSGA), o

procedură de optimizare multiobiectiv bazată pe descalificarea atributelor irelevante (MOO-FRIF)

și o procedură de optimizare multiobiectiv bazată pe eliminarea progresivă a atributelor EEG

irelevante (MOO-FPDIF).

O dată la un număr predefinit de generații, sistemul fuzzy este apelat pentru a evalua

utilitatea atributelor implicate în procesul de clasificare. Două abordări diferite sunt indicate pentru

a fi integrate în mecanismul decizional al algoritmului genetic. Prima abordare constă în reducerea

lungimii cromozomilor. Ori de câte ori sistemul fuzzy detectează atribute irelevante, genele

inactive comune ale acestora vor fi eliminate din cromozomi. Pornind de la sistemul fuzzy

prezentat, această reducere permite diminuarea dimensiunii spațiului de căutare fără deteriorarea

semnificativă a calității populației de soluții. Deoarece nu va mai fi posibilă reactivarea atributelor


41

astfel eliminate, procedura de eliminare poate genera o convergență prematură, mai ales atunci

când valoarea limită pentru ranguri 𝑟𝑤 este foarte mică.

O abordare mai puțin “intruzivă” constă în modificarea valorilor fitness ale indivizilor care

în conformitate cu propriul material genetic propun ignorarea etichetelor atributelor marcate ca

fiind irelevante de către sistemul fuzzy (genele setate pe 0). Această configurare se realizează prin

creșterea valorii fitness a unui individ ori de câte ori o genă setată pe 0 în cromozom este

confirmată de decizia finală a sistemului fuzzy. Deoarece valorile fitness mari asigură în mod

implicit creșterea probabilității de selecție pentru recombinare și supraviețuire, indivizii care

promovează dezactivări ale atributelor similare cu cele indicate de sistemul fuzzy, vor fi avantajați.

Variația valorilor fitness poate fi constantă sau liniar dependentă de gradul de încredere returnat

de sistemul fuzzy. În mod evident, ultimul caz poate încuraja indivizii care dezactivează atributele

corespunzătoare ieșirilor ”mari” ale sistemului fuzzy.

5.9. Concluzii

Scopul principal al metodelor studiate în primele subcapitole constă în evaluarea nivelelor

de încărcare cognitivă pe baza semnalelor EEG înregistrate pe parcursul unor teste de memorie de

tip n-back. În acest demers a fost definit un set de trei indicatori statistici calculați separat pentru

cele două seturi de date. Acest studiu prezintă rezultate referitoare la performanța algoritmilor de

clasificare RF și SVM utilizați pentru a identifica activitățile efectuate de memoria de lucru și

pentru a asocia un anumit nivel de încărcare cognitivă în timpul procesului de învățare.

Următoarele subcapitole pun în evidență importanța procedurii de selecție de trăsături ca

etapă preliminară în cadrul aplicațiilor din domeniul învățării automate, pornind de la rezultatele

recente prezentate în literatura de specialitate. Subcapitolul şase propune o procedură genetică

inovativă aplicată pentru extragerea trăsăturilor semnalelor EEG pentru seturi foarte mari de date,

așa cum sunt și cele implicate în procesul de evaluare al nivelului de încărcare al memoriei pe

termen scurt bazat pe clasificarea tiparelor EEG. Exemplificarea procedurii propuse este realizată

folosind clasificatorii RF și SVM, investigațiile experimentale vizând diferite metode de

optimizare mono și multiobiectiv, demonstrând eficiența strategiilor multiobiectiv cu comutare.

Subcapitolul șapte definește selecția de trăsături în raport cu minimizarea erorii de

clasificare, dar și cu numărul de trăsături selectate. Cromozomii sunt construiți în concordanță cu

o reprezentare care să permită extinderea setului de valori al trăsăturilor curente prin adăugarea

valorilor anterioare ale acelorași trăsături, oferind așadar o imagine mai clară a dinamicii

activităților mentale. Rezultatele metodei propuse sunt investigate în comparație cu o abordare

standard bazată pe NSGA și demonstrează utilitatea folosirii valorilor anterioare pentru atribute

dar și eficiența politicilor dinamice de actualizare a parametrilor implicați.

Subcapitolul opt analizează viabilitatea unui mecanism de tip fuzzy pentru eliminarea

progresivă a atributelor irelevante. În acest caz, periodic, un sistem fuzzy analizează utilitatea unui

atribut luând în calcul performanţele şi numărul indivizilor din populaţie care au acel atribut

activat, resectiv neselectat. Ieşirea sistemului fuzzy poate fi folosită pentru inactivarea directă a

atributelor inutile sau pentru creşterea valorilor fitness pentru inidivizii care activează atribute

utile. Rezultatele exeprimentale au ilustrat ca prima variantă poate asigura o eliminare mai rapidă

a trăsăturilor irelevante, fără a afecta acurateţea clasificării.

42

Capitolul 6

Concluzii generale

Obiectivul principal al acestei teze a fost dezvoltarea unor algoritmi genetici de optimizare

multiobiectiv și investigarea utilității acestora în rezolvarea unor probleme care implică variația

conflictului dintre obiective. Pentru un demers cât mai ilustrativ, au fost considerate două aplicații:

determinarea traiectoriei optime pentru un robot mobil, respectiv problema selecției de trăsături

pentru clasificarea semnalelor EEG. În cazul primei probleme, intensitatea conflictului dintre

obiective pentru soluţiile admisibile este influenţată de harta obstacolelor și localizarea punctelor

de start și stop. Pentru a doua problemă, obiectivele considerate sunt slab conflictuale în anumite

zone ale spațiului de căutare, deoarece reducerea numărului de trăsături poate favoriza

îmbunătăţirea rezultatelor clasificării chiar şi pe setul de date de antrenare.

Rezultatele prezentate în cadrul acestei teze au fost diseminate în 20 de lucrări publicate

dintre care: 2 lucrări publicate într-o revistă cotată CNCSIS B+, 2 lucrări publicate într-o revistă

OpenAccess, indexate de CEEOL și incluse în volumele unor conferințe internaționale publicate

de ADLA, 9 lucrări publicate în volumele unor conferințe internaționale indexate în IEEE Xplore

dintre care 6 sunt ISI Proceedings, 4 lucrări publicate în manifestărilor unor conferințe naționale,

1 lucrare prezentată sub formă de poster în cadrul manifestărilor unei școli internaționale de vară,

2 lucrări sunt în curs de publicare în volumele unei conferințe indexate în IEEE Xplore ISI

Proceedings. Pe lângă acestea, sunt în curs de elaborare 3 lucrări dintre care: 1 lucrare în curs de

elaborare pentru publicare în cadrul unei reviste indexate ISI și 2 lucrări în curs de elaborare pentru

publicarea în cadrul unei reviste cotate CNCSIS B+. O prezentare detaliată a acestora în funcție

de categorie poate fi consultată în cadrul anexei ”Lista publicațiilor”.

Rezultatele ştiinţifice prezentate în capitolele 4 și 5 răspund obiectivelor stabilite. La

obţinerea lor autoarea acestei teze a contribuit pe durata stagiului doctoral. În cadrul subcapitolelor

următoare, sunt reluate principalele avantaje pe care metodele introduse le vizează şi contextul în

care acestea pot fi utilizate, împreună cu referințele bibliografice în care sunt exemplificate.

6.1. Contribuții algoritmice

Conceptele algoritmice originale implementate în cadrul metodelor genetice de

optimizare multiobiectiv a traiectoriilor optimale pentru un robot mobil pe o suprafață care

conține obstacole, inclusiv cu formă non-convexă se încadrează în cinci categorii:

1. Algoritmi pentru ordonarea parțială a soluțiilor în contextul unei probleme de

optimizare multiobiectiv care asigură creşterea graduală a probabilităţii de selecţie pentru

soluţiile preferate fără creşterea exagerată a riscului de apariție a unei convergențe

premature, prin monitorizarea distribuţiei populaţiei în spaţiul obiectiv. Aceşti algoritmi

iau în calcul natura diversă a conflictului dintre obiective şi integrează decizia cu căutarea

prin tehnici adaptive. Pot fi aplicaţi pentru orice algoritm bazat de populaţii.

6. Concluzii generale

43

Algoritm de calcul al rangurilor bazat pe separarea populaţiei în două grupuri

(un grup incluzând soluţiile preferate), care asigură ajustarea acestei grupări prin

monitorizarea dinamicii soluţiilor preferate în spaţiul obiectiv, luând în considerare

diversitatea şi numărul lor, precum şi distanţele dintre acestea şi originea spaţiului

obiectiv (Ferariu & Cîmpanu, 2013). Algoritmul permite etichetarea dinamică a

soluţiilor preferate, fără a solicita cunoştinţe apriorice despre problemă.

Algoritm de calcul al rangurilor bazat pe separarea populaţiei în două sau trei

grupuri, în funcţie de dispersia primelor fronturi Pareto din populaţie, pentru

etichetarea adecvată a soluţiilor preferate inclusiv pentru cazul obiectivelor slab

conflictuale (Cîmpanu & Ferariu, 2013). Algoritmul permite evitarea creşterii excesive

a presiunii de selecţie impuse de soluţiile preferate. Separarea se face folosind punctul

nadir difuz.

Algoritm de calcul al rangurilor bazat pe clusterizarea populaţiei şi analiza

dominanţei Pareto pentru centrii clusterelor, pentru a investiga distribuţia

fronturilor Pareto. Clusterele formate oferă informaţii relevante pentru etichetarea

soluţiilor preferenţiale, evitând eliminări nedorite (Ferariu & Cîmpanu, 2014a; Ferariu

& Cîmpanu, 2014b).

Scopul principal al acestor algoritmi a fost asigurarea unei integrări graduale între căutare

și decizie, asigurând preferința pentru soluțiile amplasate către mijlocul primelor fronturi

Pareto, cu diminuarea riscului de apariție a unei convergențe premature prin:

monitorizarea grupurilor de soluții în spațiul obiectiv și încurajarea soluțiilor

localizate spre mijlocul fronturilor Pareto (Ferariu & Cîmpanu, 2013; Cîmpanu &

Ferariu, 2013; Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu, 2014b; Ferariu &

Cîmpanu, 2015). Gruparea indivizilor din populație este realizată fie în funcție de

valorile medii ale obiectivelor considerate (Ferariu & Cîmpanu, 2013), fie în funcție de

valorile medii ale obiectivelor considerate și de punctul nadir difuz, ținând cont în acest

caz de cantitatea soluțiilor dominate de soluția virtuală asociată punctului nadir difuz

(Cîmpanu & Ferariu, 2013). În (Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu,

2014b) grupurile sunt construite pe baza valorilor medii ale obiectivelor considerate,

pe baza punctului nadir difuz și în funcție de gradul de împăștiere a soluțiilor localizate

pe frontul Pareto de ordinul I pentru a trata intensitatea naturii conflictuale a

obiectivelor.

rafinarea grupurilor prin utilizarea unui grup suplimentar G3 pentru o mai bună

explorare a regiunii în care sunt localizate cele mai bune soluții și pentru a nu reduce

drastic numărul de soluții preferate de mecanismul decizional (Cîmpanu & Ferariu,

2013; Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu, 2014b);

îmbinarea procedurii de grupare nesupervizată cu mecanismele de decizie

(Ferariu & Cîmpanu, 2015). Indivizii din populație sunt grupați nesupervizat folosind

k-medii considerând pentru relevanța grupării un număr variabil de grupuri de la o

generație la alta. Centrii grupurilor rezultate sunt utilizați pentru tratarea preferențială

a conflictului dintre obiective ca mecanism de alertă pentru extinderea regiunii

preferențiale în limitele unor limite prestabilite sau pentru prevenirea extinderii

exagerate a regiunii preferate de factorul decizional (Ferariu & Cîmpanu, 2015).


44

2. Algoritmi pentru îmbunătățirea diversității materialului genetic sunt reprezentați de:

Algoritm pentru controlul diversității cu ajutorul unui obiectiv suplimentar,

temporar introdus – maximizarea distanței până la cel mai apropiat vecin în spațiul

obiectiv. Algoritmul foloseşte mecanisme care să permită aplicarea acestei politici

preferențial pe regiuni şi doar în anumite generații, decizia de utilizare fiind luată pe

baza analizei distribuţiei soluţiilor din populaţie în spaţiul obiectiv;

Algoritm pentru controlul diversității indivizilor prin rafinarea rangurilor pe

subseturi de fronturi succesive a cărui influenţă poate fi modificată variind numărul

de fronturi dintr-un subset.

Algoritmii propuși pentru ameliorarea diversității informației genetice a indivizilor

presupun:

controlul diversității printr-un obiectiv suplimentar și activarea controlului pe

baza unei diagnoze de aplicare preferențială pentru anumite soluţii şi doar la

anumite generaţii (Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu, 2013; Ferariu &

Cîmpanu, 2014a). Această acţiune este necesară fie în cazul scăderii prea rapide a

numărului de indivizi preferați, fie atunci când diversitatea indivizilor din populație

scade prea mult, fie când distanța medie față de originea spațiului obiectiv scade prea

repede (Ferariu & Cîmpanu, 2013). Variaţia acestor valori este monitorizată pentru

generații consecutive (Ferariu & Cîmpanu, 2013). În (Cîmpanu & Ferariu, 2013)

maximizarea distanței până la cel mai apropiat vecin este aplicată întotdeauna pentru

diversificarea sau protejarea soluțiilor localizate în cadrul grupului preferat de

mecanismul decizional, în timp ce în (Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu,

2014b), îmbunătățirea diversității indivizilor este considerată doar dacă este necesar.

controlul diversității indivizilor pe secvențe de fronturi (Ferariu & Cîmpanu, 2015).

În acest caz, îmbunătățirea diversității este activată în cazul în care este semnalată o

diminuare sau o extindere semnificativă a regiunii preferențiale, întrucât această

regiune conține soluţii amplasate în pe primele fronturi Pareto, în apropierea mijlocului

acestora. Diminuarea cardinalului grupului de soluţii preferate este considerată critică

după o serie de reduceri succesive, în timp ce expansiunea excesivă a indivizilor din

această regiune este semnalată ca inconvenient în cazul în care obiectivele sunt slab

conflictuale (Ferariu & Cîmpanu, 2015).

3. Codificarea cromozomială și operatori genetici

În cazul codificării cromozomilor și a operatorilor genetici asociați acesteia, contribuțiile

originale sunt reprezentate de:

Codificarea în virgulă mobilă a unor cromozomi de lungime variabilă pentru

reprezentarea traiectoriilor robotului, liniare pe porțiuni, utilizată în aplicațiile propuse

în (Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu, 2014b; Ferariu & Cîmpanu, 2015).

Acest tip de reprezentare permite o explorare mai eficientă a spațiului de căutare și

eliminarea limitării numărului de puncte intermediare care descriu o traiectorie, impuse

de la început în cadrul problemelor rezolvate în (Ferariu & Cîmpanu, 2013; Cîmpanu


45

& Ferariu, 2014), conferind astfel independenţa în configurarea structurii

cromozomiale față de un parametru influent ce trebuia indicat în prealabil.

Operatorul de încrucișare dedicat pentru reprezentarea cromozomială de

lungime variabilă, prezentat în (Ferariu & Cîmpanu, 2014a), utilizat și în cadrul

aplicațiilor din (Ferariu & Cîmpanu, 2014b; Ferariu & Cîmpanu, 2015). Implementarea

acestuia este realizată în funcție de lungimea cromozomilor părinților. Dacă aceștia au

lungimi egale, atunci copiii vor fi generați cu ajutorul operatorului de încrucișare

aritmetic intermediar, însă dacă părinții codifică traiectorii cu număr distinct de puncte

intermediare, atunci lanțul cromozomial mai scurt va fi expandat prin duplicarea

punctelor intermediare, fără a afecta semnificația fizică a reprezentării inițiale (Ferariu

& Cîmpanu, 2014a).

4. Rezolvarea restricţiei în problema determinării traiectoriei optimale are ca obiectiv

principal înlocuirea traiectoriilor inadmisibile rezultate prin generarea aleatoare a

populației inițiale sau prin acţiunea operatorilor genetici, având în vedere dezavantajele

aduse de acestea algoritmului evolutiv (Ferariu & Cîmpanu, 2013; Cîmpanu & Ferariu,

2013). Repararea traiectoriilor inadmisibile este rezolvată prin intermediul unor proceduri

de corecție bazate pe utilizarea triangularizărilor Delaunay. Sunt construite în acest demers

două triangularizări Delaunay constrânse cu scopul de a obține un graf bicolor (muchii

admisibile, respectiv inadmisibile) pentru care se va aplica algoritmul Dijkstra. În acest

sens sunt descrise:

procedura de corecție mono-obiectiv utilizând triangularizări Delaunay presupune

ca algoritmul Dijkstra să fie aplicat exclusiv în funcție de lungimea muchiilor (Ferariu

& Cîmpanu, 2014a) și

extensia multiobiectiv a procedurii de corecție bazată pe folosirea algoritmului

Dijkstra care presupune gestionarea costurilor asociate muchiilor prin explorarea

grafului existent pornind dintr-un nod și calculând costul prin asocierea de ranguri

folosind NSGA pentru traiectoriile de lungime maximă specificată care pleacă din

nodul respectiv (Ferariu & Cîmpanu, 2014b). În cazul existenței unor variante cu rang

egal, va fi încurajată traiectoria de lungime minimă.

5. Procedură de reducere a numărului de puncte intermediare dintr-o traiectorie cu

condiția menținerii admisibilității acesteia presupune simplificarea traiectoriilor după

corecție. Este utilă atunci când scenele de lucru conțin obstacole cu forme complexe și al

cărui contur extins determină obținerea unor traiectorii corectate cu un număr foarte mare

de puncte intermediare (Ferariu & Cîmpanu, 2014a; Ferariu & Cîmpanu, 2014b; Ferariu &

Cîmpanu, 2015). Reducerea este realizată în două etape și anume: sunt eliminate mai întâi

buclele, urmând reducerea secvențială a punctelor intermediare care permite păstrarea

admisibilității traiectoriei pentru toate traiectoriile (Ferariu & Cîmpanu, 2014a), respectiv

pentru anumite traiectorii selectate în mod aleatoriu (Ferariu & Cîmpanu, 2014b).


46

Conceptele algoritmice originale dezvoltate în cadrul metodelor genetice de optimizare

multiobiectiv a selecției trăsăturilor relevante pentru semnale EEG în vederea identificării

nivelelor de încărcare cognitivă sunt prezentate în cele ce urmează. Selecția trăsăturilor relevante

reprezentate de anvelopa semnalelor EEG achiziționate este realizată prin minimizarea

concomitentă a erorii de clasificare și a numărului de trăsături luat în calcul (Cîmpanu et al., 2017b;

Cîmpanu et al., 2017c; Ferariu et al., 2018). Cei trei algoritmi propuși reprezintă proceduri de

selecție de trăsături de tip încorporat, și anume:

1. Procedura genetică de optimizare multiobiectiv pentru selecția trăsăturilor relevante din

semnale EEG cu comutare între clasificatori presupune comutarea ciclică între modele de

algoritmi de grupare supervizată diferiţi (exemplificarea este oferită pentru RF și SVM) pentru

a elimina amprenta individuală lăsată de un anumit model de clasificator asupra rezultatului

(Cîmpanu et al., 2017c), asigurând astfel o selecţie obiectivă a trăsăturilor, care poate fi mai

utilă în înţelegerea proceselor cognitive considerate. Dubla evaluare a soluțiilor candidat

permite încurajarea soluțiilor cu performanțe superioare pentru ambele modele de clasificator,

eliminând zgomotul indus de aceste modele, în condiţiile în care nu se solicită la toate

generaţiile evaluarea tuturor soluţiile în raport cu ambii clasificatori.


semnale EEG bazată pe utilizarea extensiilor temporale presupune construirea unor

cromozomi care să permită utilizarea valorilor precedente ale atributelor într-un singur vector

de trăsături pentru o mai bună înțelegere a dinamicii unei activități mentale. Acest demers

asigură informarea clasificatorului referitor la variația semnalelor EEG pentru un interval

temporal extins faţă de cel pentru care sunt calculate anvelopele semnalului pe diferite benzi

de frecvenţă pentru extragerea de trăsături (Ferariu et al., 2018). Deși este avantajoasă din acest

punct de vedere, expansiunea setului de atribute potențiale ridică problema creșterii

dimensiunii spațiului de căutare. Pentru a evita acest neajuns codificarea compactă în baza

patru a cromozomilor este însoțită de două tehnici care eficientizează explorarea spațiului de

căutare. Prima se referă la creşterea graduală a complexităţii modelului de clasificare, iar cea

de-a doua se referă la configurarea dinamică a funcţiei obiectiv care stabileşte complexitatea

vectorului de trăsături selectate.


semnale EEG bazată pe sisteme fuzzy presupune integrarea în cadrul algoritmului genetic

de optimizare multiobiectiv a unui mecanism fuzzy de eliminare a trăsăturilor irelevante prin

intermediul unor penalizări aplicate la nivel de rang astfel încât să conducă la dezactivarea

graduală a genelor inutile sau la eliminarea atributelor cu influență negativă. Pentru a permite

o detecție rapidă a atributelor irelevante, populația de indivizi este analizată periodic de un

sistem fuzzy de tip Mamdani. Două abordări diferite sunt indicate pentru a fi integrate în

mecanismul decizional și anume: reducerea lungimii cromozomilor, prin eliminarea genelor

inactive comune (eliminarea atributelor irelevante), respectiv creșterea valorilor fitness ale

indivizilor ale căror gene comune au fost nerecomandate de sistemul fuzzy (descurajarea

atributelor irelevante) (Cîmpanu et al., 2018d).


47

6.2. Investigații experimentale și analiza datelor

Toate structurile propuse pentru simularea componentelor problemei și toate procedurile

genetice de optimizare multiobiectiv anterior discutate au fost dezvoltate în MATLAB.

Investigațiile experimentale efectuate pentru evidențierea performanțelor procedurilor propuse în

soluționarea problemei de determinare a traiectoriei optimale pentru un robot mobil pe o

suprafață cu obstacole au vizat:

1. Proiectarea unor scenarii de verificare experimentală pentru simularea unor suprafețe

plane, conținând obstacole cu formă convexă sau non-convexă, cu grad diferit de acoperire și

stabilirea unor configurații ale punctelor terminale și fixarea unui anumit număr de puncte

intermediare în cadrul unei traiectorii astfel încât să se genereze scenarii de lucru cu

complexitate diferită pentru o reprezentare cât mai ilustrativă a rezultatelor obținute și pentru

o comparare relevantă a acestora. În acest context au fost definiţi indicatori pentru ilustrarea

gradului de dificultate pentru obținerea traiectoriilor admisibile pe o scenă de lucru

oarecare cu obstacole. Gradul de dificultate al unui scenariu de test rezidă în dimensiunea

scenei de lucru, depinde de numărul și forma obstacolelor dispuse pe scena respectivă, dar și

de suprafața ocupată de acestea, precum și de localizarea punctelor terminale ale unei

traiectorii.

2. Analizarea și testarea aplicațiilor prezentate în cadrul secțiunii algoritmice pe diverse

scene de lucru în contextul scenariilor considerate a urmărit evaluarea modului de gestionare

a situațiilor în care dificultatea rezolvării restricţiilor creşte. În acest context, ținând cont de

introducerea a unor mecanisme de eficientizare a explorării, algoritmii propuși au reușit să

selecteze soluții admisibile convenabile din perspectiva minimizării simultane a lungimii și a

curburii unei traiectorii.

3. Definirea unor indicatori pentru analiza performanțelor operatorului de încrucișare și a

unor indicatori pentru analizarea diversității soluțiilor a fost necesară pentru a cuantifica

impactul produs atât de operatorul de încrucișare pentru cromozomi de lungime variabilă cât

și de procedura de corecție aplicată pentru repararea traiectoriilor inadmisibile în următoarele

contexte: după aplicarea operatorului de încrucișare, după corecția copiilor rezultați și după

reducerea numărului de puncte intermediare. Contribuțiile originale în cadrul acestei secțiuni

se referă la aprecierea impactului produs în fiecare context anterior menționat asupra populației

de copii prin: procentul de perechi de cromozomi părinte care generează unul sau doi copii

admisibili, procentul de copii care ating performanțe inferioare sau superioare performanțelor

părinților, distanța medie calculată în spațiul obiectiv între părinți și copiii admisibili, respectiv

inadmisibili rezultați și distanța medie până la cel mai apropiat vecin în spațiul obiectiv.

Metodele propuse pentru analiza datelor și pentru investigarea experimentală a

performanțelor algoritmilor genetici de optimizare multiobiectiv propuși pentru selecția

trăsăturilor relevante pentru semnale EEG au urmărit:

1. Importanța utilizării procedurilor genetice de optimizare multiobiectiv în detrimentul

celor mono-obiectiv pentru selecția trăsăturilor relevante din semnale EEG a fost

analizată subliniind principalele limitări ale procedurilor de optimizare de tip mono-obiectiv


48

care au vizat minimizarea separată sau prin agregare liniară a erorii de clasificare și a numărului

de trăsături relevante selectate, mai exact: ghidarea căutării în sensul minimizării erorii de

clasificare nu garantează eliminarea tuturor trăsăturilor irelevante, în timp ce ghidarea căutării

în sensul minimizării numărului de trăsături selectate afectează precizia modelului de

clasificare. Minimizarea unei funcţii obiectiv care rezultă prin agregarea liniară a celor două

funcţii anterior amintite este puternic influențată de alegerea ponderilor. Au fost analizate și

comparate pentru acest demers performanțele obținute de metodele de optimizare mono- și

multiobiectiv, considerând diferite scheme de asociere a rangurilor și pentru diferite

configurații ale parametrilor clasificatorilor.

2. Analiza performanțelor algoritmilor de grupare supervizată în experimente de

determinare a nivelelor de încărcare cognitivă folosind semnale EEG a fost realizată pe

seturi de date EEG cu un număr redus de atribute, respectiv pe seturi de date EEG de cardinal

mare achiziționate în cadrul unor experimente de încărcare a memoriei cognitive realizate pe

baza unor teste ”n-back”, cu n = 1, 2 sau 3 sau pe baza unor calcule matematice cu complexitate

incrementată gradual. Aceste experimente au vizat ilustrarea importanței selectării intuitive a

trăsăturilor utilizate pentru clasificare, precum și analiza comparativă a performanțelor

obținute pentru seturi de date achiziționate cu dispozitive diferite. Nu în ultimul rând au fost

analizate și comparate performanțele a diferite modele de clasificare (KNN, NB, AB, SVM

sau RF) pentru identificarea nivelelor de încărcare a memoriei de lucru pe baza unui set de date

EEG de cardinal mare obţinut pentru experimente care implică activităţi aritmetice mentale.

3. Analiza statistică a semnalelor EEG ce descriu diferite nivele de încărcare cognitivă a

considerat indicatori statistici precum: valoarea medie, rădăcina medie pătratică și

intercorelația pentru a ilustra diferențele între nivelele de încărcare cognitivă considerate, dar

și pentru a indica relevanţa trăsăturilor considerate. Această analiză a evidenţiat dificultatea de

rezolvare a problemei de selecţie folosind metode de tip filtru sau împachetare şi a justificat

demersul de dezvoltare a unor metode de selecţie de tip incorporat.

4. Analiza metodelor dezvoltate pentru selecţia trăsăturilor semnalelor EEG ce descriu

diferite nivele de încărcare cognitivă a considerat investigarea comparativă a rezultatelor pe

diferite configuraţii de lucru mono şi multiobiectiv, urmărind totodată să ilustreze influenţa

parametrilor algoritmilor pe fiecare caz în parte. Cele mai bune rezultate au fost obţinute pentru

abordările multiobiectiv.

Conceptele și rezultatele prezentate în cele șase capitole sunt rezultatul unui proces

extensiv de cercetare și documentare, acest demers generând acumularea unui nivel ridicat de

expertiză în acest domeniu care a permis sintetizarea, dezvoltarea și implementarea unor noi

metode de optimizare multiobiectiv bazate pe algoritmi genetici.

49

Lista publicațiilor

1. Articole publicate în volumele unor conferințe indexate ISI Proceedings:

Lavinia Ferariu and Corina Cîmpanu, Multi-Objective Genetic Algorithm with

Clustering-based Ranking and Direct Control of Diversity, The 17th International

Conference on System Theory, Control and Computing, ICSTCC 2013, pp. 341-346,

ISBN 978-1-4799-2228-4, ISBN 978-1-4799-2227-7, October 11-13, Sinaia, Romania,

2013.

Corina Cîmpanu and Lavinia Ferariu, Genetic Multiobjective Fitness Assignment

Scheme Applied to Robot Path Planning, Proceedings of the 10th International

Conference On Electronics Computer And Computation, ICECO 2013, pp. 196-199,

ISBN: 978-605-4894-00-0, November 7-9, Ankara, Turkey, 2013.

Lavinia Ferariu and Corina Cîmpanu, Multiobjective Hybrid Evolutionary Path

Planning with Adaptive Pareto Ranking of Variable-Length Chromosomes, The

IEEE 12th International Symposium on Applied Machine Intelligence and Informatics,

SAMI 2014, pp. 23-28, ISBN: 978-1-4799-3441-6, January 23-25, Herl’any, Slovakia,

2014.

Lavinia Ferariu and Corina Cîmpanu, Adaptive Genetic Pareto Ranking Based on

Clustering, EAIS 2015, 2015 IEEE Conference on Evolving and Adaptive Intelligent

Systems, pp. 1-7, ISBN: 978-146736697-7, December 1-3, Douai, France, 2015.

Corina Cîmpanu, Lavinia Ferariu, Florina Ungureanu and Tiberius Dumitriu, Genetic

Feature Selection for Large EEG Data with Commutation between Multiple

Classifiers, The 21st International Conference on System Theory, Control and

Computing, ICSTCC 2017, pp. 434-437, ISBN: 978-1-5386-0358-1, October 19-21,

Sinaia, Romania, 2017.

Tiberius Dumitriu, Raluca Petronela Dumitriu and Corina Cîmpanu, Artificial neural

networks and support vector regression modeling for prediction of some silver

colloidal suspensions rheological behavior, The 21st International Conference on

System Theory, Control and Computing, ICSTCC 2017, pp. 624-628, ISBN: 978-1-

5386-0358-1, October 19-21, Sinaia, Romania, 2017.

2. Articole publicate în volumele unor jurnale indexate de CEEOL

Florina Ungureanu, Corina Cîmpanu, Tiberius Dumitriu, and Vasile Ion Manta,

Cognitive Load and Short Term Memory Evaluation Based on EEG Techniques, The

13th eLearning and Software for Education Conference, ELSE 2017, vol. 2, pp. 217-

224, ISSN: 2066-026X, ISSN-L: 2066-026X, ISSN CD: 2343-7669, April 27-28,

Bucharest, Romania, 2017.


50

Corina Cîmpanu, Tiberius Dumitriu, and Florina Ungureanu, Instructional Design

Based on the Assessment of Cognitive Load and Working Memory Load, The 14th

eLearning and Software for Education Conference, ELSE 2018, vol. 2, pp. 54-61, April

19-20, Bucharest, Romania, 2018.

3. Articole publicate în volumele unor reviste indexate BDI, CNCSIS B+

Corina Agrigoroaie (Cîmpanu), Lavinia Ferariu and Cătălin Brăescu, Reflective

Online Reconfiguration of Real-Time Applications Having Tasks with Static

Priorities, Buletinul Institutului Politehnic din Iaşi, Tome LVIII (LXII), Fasc. 1, pp. 9-

26, AUTOMATIC CONTROL and COMPUTER SCIENCE Section, Iași, România,

2012.

Corina Cîmpanu and Lavinia Ferariu, Survey of Clustering Algorithms, Buletinul

Institutului Politehnic din Iasi, Tome LVIII(LXII), Fasc. 3, pp. 23-42, AUTOMATIC

CONTROL and COMPUTER SCIENCE Section, Iași, România, 2012.

4. Articole publicate în volumele unor conferințe indexate IEEE Xplore

Lavinia Ferariu and Corina Cîmpanu, Pareto-Evolutionary Path Planning

Hybridized with Multiobjective Dijkstra’s Algorithm, The 18th International

Conference on System Theory, Control and Computing, ICSTCC 2014, October 17-

19, Sinaia, Romania, 2014.

Corina Cîmpanu, Florina Ungureanu, Tiberius Dumitriu and Vasile Ion Manta, A

Comparative Study on Classification of Working Memory Tasks Using EEG Signals,

The 21th International Conference on Control Systems and Computer Science,

CSCS21, pp. 245-251, ISSN: 2379-0482, May 29-31, Bucharest, Romania, 2017.

Corina Cîmpanu, Lavinia Ferariu, Tiberius Dumitriu and Florina Ungureanu, Multi-

Objective Optimization of Feature Selection Procedure for EEG Signals

Classification, 6th edition of the International Conference on e-Health and

Bioengineering, EHB 2017, pp. 434-437, ISBN: 978-1-5386-0358-1, June 22-24,

Sinaia, Romania, 2017.

5. Lucrări sub formă de poster

Corina Cîmpanu, Evolutionary Multi-Objective Optimization of the Feature

Selection Procedure for EEG Signals, International Summer School on Imaging with

Medical Applications: How is Artificial Intelligence Reinventing Healthcare, SSIMA

2018, Accepted with Scholarship, July, 2-6, Sibiu, Romania, 2018.

6. Lucrări publicate în volumele unor conferințe naționale

Corina Cîmpanu and Tiberius Dumitriu, Comparative Study on EEG Signals

Classification and Multi-Objective Optimization of Feature Selection, First

Conference of the TUIASI Doctoral School, CSD 2017, May 29-30, Iasi, Romania,

2017.


51

Tiberius Dumitriu and Corina Cîmpanu, The Assessment of Short Term Memory and

Cognitive Load using EEG Techniques, First Conference of the TUIASI Doctoral

School, CSD 2017, May 29-30, Iasi, Romania, 2017.

Corina Cîmpanu, Lavinia Ferariu, Tiberius Dumitriu and Florina Ungureanu, A

Comparison of Ranking Methods Used in Multiobjective Optimization for Feature

Selection in EEG Signals, Conference of the TUIASI Doctoral School 2nd Edition,

CSD 2018, May 23-24, 2018, Iasi, Romania, 2018.

Corina Cîmpanu, Lavinia Ferariu, Tiberius Dumitriu and Florina Ungureanu, On the

Impact of a Classification Model in EEG Feature Selection for Cognitive Load

Assessment, Conference of the TUIASI Doctoral School 2nd Edition, CSD 2018, May

23-24, 2018, Iasi, Romania, 2018.

7. Lucrări în curs de publicare sau elaborare

Lavinia Ferariu, Corina Cîmpanu, Tiberius Dumitriu and Florina Ungureanu, EEG

Multi-Objective Feature Selection Using Temporal Extension, The IEEE 14th

International Conference on Intelligent Computer Communication and Processing,

ICCP 2018, Cluj, Romania, 2018, Accepted, September, 6-8, Cluj, Romania, 2018.

Tiberius Dumitriu, Florina Ungureanu, Corina Cîmpanu and Vasile-Ion Manta,

Emotion Classification Techniques Based on Physiological Measures, The IEEE

14th International Conference on Intelligent Computer Communication and

Processing, ICCP 2018, Cluj, Romania, 2018, Accepted, September, 6-8, Cluj,

Romania, 2018.

Corina Cîmpanu, Lavinia Ferariu, Tiberius Dumitriu and Florina Ungureanu, Feature

Selection in EEG Signals via Multi-Objective Genetic Algorithm with Fuzzy Fitness

Assignment Scheme, Journal of Control Engineering and Applied Informatics, în

lucru, 2018.

Corina Cîmpanu, Evaluation of Ranking Methods Used in Multiobjective

Optimization for Feature Selection in EEG Signals, Buletinul Institutului Politehnic

din Iaşi, în lucru, 2018.

Corina Cîmpanu, On the Impact of a Classification Model in EEG Feature

Selection for Cognitive Load Assessment, Buletinul Institutului Politehnic din Iaşi, în

lucru, 2018.

8. Proiecte

Project PN-II-ID-PCE-2011-3-0563/ 2011, contract no. 343/ 5.10.2011, Models from

Medicine and Biology: mathematical and numerical insights, January 2012 –

December 2016, Director: Prof.dr. Narcisa Dumitriu, http://is7s.com/mmbpmn/.

http://is7s.com/mmbpmn/

52

Referințe bibliografice

Amin H.U., Malik A.S., Kamel N., Hussain M., (2016). “A novel approach based on data redundancy

for Feature Extraction of EEG Signals”, Brain Topography, 29 (2), Springer US, pp.207-217.

Boutsidis C., Mahoney M.W., Drineas P., (2009). ”Unsupervised Feature Selection for the K-

means Clustering Problem”, In Annual Advances in Neural Information Processing Systems,

Proceedings of the NIPS’09 Conference.

Breaban M., (2010). ”Optimized Ensembles for Clustering Noisy Data”, in Blum C., Battiti R.

(Eds.) Learning and Intelligent Optimization, Lecture Notes in Computer Science, 6073, pp.220−223,

Springer, Berlin.

Chen G., Low P.C., Yang Z.H., (2009). ”Preserving and Exploiting Genetic Diversity in Evolutionary

Programming Algorithms”, IEEE Transactions on Evolutionary Computation, 13(3), pp.661-673.

Cîmpanu C. and Ferariu L., (2012). ”Survey of Clustering Algorithms”, Buletinul Institutului

Politehnic din Iasi, Tome LVIII(LXII), Fasc. 3, pp. 23-42, AUTOMATIC CONTROL and COMPUTER

SCIENCE Section, Iași, România.

Cîmpanu C. and Ferariu L., (2013). ”Genetic Multiobjective Fitness Assignment Scheme Applied to

Robot Path Planning”, Proceedings of the 10th International Conference On Electronics Computer And

Computation, ICECO 2013, pp. 196-199, ISBN: 978-605-4894-00-0, November 7-9, Ankara, Turkey.

Cîmpanu C., Ungureanu F., Dumitriu T. and Manta V.I., (2017a). ”A Comparative Study on

Classification of Working Memory Tasks Using EEG Signals”, The 21th International Conference on

Control Systems and Computer Science, CSCS21, pp. 245-251, ISSN: 2379-0482, May 29-31, Bucharest,

Romania.

Cîmpanu C. and Dumitriu T., (2017). ”Comparative Study on EEG Signals Classification and Multi-

Objective Optimization of Feature Selection”, First Conference of the TUIASI Doctoral School, CSD 2017,

May 29-30, Iasi, Romania.

Cîmpanu C., Ferariu L., Dumitriu T. and Ungureanu F., (2017b). ”Multi-Objective Optimization of

Feature Selection Procedure for EEG Signals Classification”, 6th edition of the International Conference

on e-Health and Bioengineering, EHB 2017, pp. 434-437, ISBN: 978-1-5386-0358-1, June 22-24, Sinaia,

Romania.

Cîmpanu C., Ferariu L., Ungureanu F. and Dumitriu T., (2017c). ”Genetic Feature Selection for Large

EEG Data with Commutation between Multiple Classifiers”, The 21st International Conference on System

Theory, Control and Computing, ICSTCC 2017, pp. 434-437, ISBN: 978-1-5386-0358-1, October 19-21,

Sinaia, Romania.

Cîmpanu C., Dumitriu T., and Ungureanu F., (2018a). ”Instructional Design Based on the Assessment

of Cognitive Load and Working Memory Load”, The 14th eLearning and Software for Education

Conference, ELSE 2018, vol. 2, pp. 54-61, April 19-20, Bucharest, Romania.

Cîmpanu C., Ferariu L., Dumitriu T., and Ungureanu F., (2018b). ”A Comparison of Ranking

Methods Used in Multiobjective Optimization for Feature Selection in EEG Signals”, Conference of the

TUIASI Doctoral School 2nd Edition, CSD 2018, May 23-24, Iasi, Romania.

Cîmpanu C., Ferariu L., Dumitriu T., and Ungureanu F., (2018c). ”On the Impact of a Classification

Model in EEG Feature Selection for Cognitive Load Assessment”, Conference of the TUIASI Doctoral

School 2nd Edition, CSD 2018, May 23-24, Iasi, Romania.


53

Cîmpanu C., Ferariu L., Dumitriu T. and Ungureanu F., (2018d). ”Feature Selection in EEG Signals

via Multi-Objective Genetic Algorithm with Fuzzy Fitness Assignment Scheme”, Journal of Control

Engineering and Applied Informatics, in development.

Coello-Coello C. A., Lamont G. B., Van Veldhuizen D. A., (2007). ”Evolutionary Algorithms for

Solving Multi-Objective Problems 2nd Edition”, Genetic and Evolutionary Computation Series, D. E.

Goldberg, J. R. Koza, Springer-Verlag, Berlin.

Das R., Chatterjee D., Das D., Sinharay A., Sinha A., (2015). “Cognitive Load Measurement – A

Methodology to Compare Low Cost Commercial EEG Devices”, Proceedings of the 2014 International

Conference on Advances in Computing, Communications and Informatics, ICACCI 2014, pp. 1188-1194,

Elsevier B.V.

Das D., Chatterjee D., Sinha A., (2014). “Unsupervised Approach for Measurement of Cognitive

Load using EEG Signals”, 13th IEEE International Conference on BioInformatics and BioEngineering,

IEEE BIBE 2013, Elsevier B.V.

Davoodi M., Panahi F., Mohades A., Hashemi S. N., (2013). “Multi-objective Path Planning in

Discrete Space”, Applied Soft Computing, vol. 13(1), pp. 709-720, Elsevier.

Deb K., (2001). ”Multiobjective Optimization Using Evolutionary Algorithms”, Wiley&Sons.

Deb K., (2011). “Multi-Objective Optimization using Evolutionary Algorithms”, Wiley.

Dhillon I., Kogan J., Nicholas C., Feature Selection and Document Clustering. In Berry M.W. (Ed.),

Survey of Text Mining I: Clustering, Classification, and Retrieval, 1, 73−100, Springer, 2003.

Dumitriu T. and Cîmpanu C., (2017a). ”The Assessment of Short Term Memory and Cognitive Load

using EEG Techniques”, First Conference of the TUIASI Doctoral School, CSD 2017, May 29-30, Iasi,

Romania.

Dumitriu T., Dumitriu R.P., and Cîmpanu C., (2017b). Artificial neural networks and support vector

regression modeling for prediction of some silver colloidal suspensions rheological behavior, The 21st

International Conference on System Theory, Control and Computing, ICSTCC 2017, pp. 624-628, ISBN:

978-1-5386-0358-1, October 19-21, Sinaia, Romania.

Dumitriu T., Cîmpanu C., Ungureanu F., Manta V.I., (2018). ”Experimental Analysis of Emotion

Classification Techniques”, 2018 IEEE 14th International Conference on Intelligent Computer

Communication and Processing, Cluj-Napoca, September 6-8.

Fallahi M., Motamedzade M., Heidarimoghadam R., Soltanian A.R., Farhadian M., Miyake S.,

(2016). “Analysis of the mental workload of city traffic control operators while monitoring traffic density:

A field study”, International Journal of Industrial Ergonomics, vol. 54, pp. 170-177, Elsevier B.V.

Ferariu L., Burlacu B., (2011a). “Multiobjective Design of Evolutionary Hybrid Neural Networks”,

IEEE International Conference on Automation and Computing, ICAC, Huddersfield, UK, pp.195-200,

2011.

Ferariu L., Burlacu B., (2011b). “Multiobjective Genetic Programming with Adaptive Clustering”,

in IEEE 7th International Conference on Intelligent Computer Communication and Processing, ICCP 2011,

Cluj Napoca, Romania, pp. 27-32.

Ferariu L. and Cîmpanu C., (2013). ”Multi-Objective Genetic Algorithm with Clustering-based

Ranking and Direct Control of Diversity”, The 17th International Conference on System Theory, Control

and Computing, ICSTCC 2013, pp. 341-346, ISBN 978-1-4799-2228-4, ISBN 978-1-4799-2227-7,

October 11-13, Sinaia, Romania.

Ferariu L. and Cîmpanu C., (2014a). ”Multiobjective Hybrid Evolutionary Path Planning with

Adaptive Pareto Ranking of Variable-Length Chromosomes” The IEEE 12th International Symposium on

Applied Machine Intelligence and Informatics, SAMI 2014, pp. 23-28, ISBN: 978-1-4799-3441-6, January

23-25, Herl’any, Slovakia.


54

Ferariu L. and Cîmpanu C., (2014b) Pareto-Evolutionary Path Planning Hybridized with

Multiobjective Dijkstra’s Algorithm, The 18th International Conference on System Theory, Control and

Computing, ICSTCC 2014, October 17-19, Sinaia, Romania.

Ferariu L. and Cîmpanu C., (2015). ”Adaptive Genetic Pareto Ranking Based on Clustering”, The

IEEE Conference on Evolving and Adaptive Intelligent Systems, EAIS 2015, pp. 1-7, ISBN: 978-

146736697-7, December 1-3, Douai, France.

Ferariu L., Cîmpanu C., Dumitriu T., Ungureanu F., (2018). ” EEG Multi-Objective Feature Selection

Using Temporal Extension”, 2018 IEEE 14th International Conference on Intelligent Computer

Communication and Processing, Cluj-Napoca, September 6-8.

Gazzaniga S.M., (2009). “Cognitive Neuroscience: The Biology of the Mind” 4th ed., The MIT Press.

Handl J., Knowles J., (2008). “Modes of Problem Solving with Multiple Objectives: Implications for

Interpreting the Pareto Set and for Decision Making”, Multiobjective Problem Solving from Nature, J.

Knowles, D. Corne, K. Deb (Eds.), Springer, pp.131-154.

Haupt R.L., Haupt S.E., (2004). “Robot Trajectory Planning”, in Practical Genetic Algorithms 2nd

Edition, Wiley Interscience, Ch. 6, pp. 156-160.

Hughes E.J., (2008). “Fitness Assignment Methods for Many-Objective Problems”, in Multiobjective

Problem Solving from Nature, J. Knowles, D. Corne,• K. Deb (Eds.), Springer, pp. 307-330.

Jain A.K., Murty M.N., Flynn P.J., (1999). ”Data Clustering: A Review.”, ACM Computing

Surveys, 31, 3, pp.264−323.

Krishnan J., Rajeev U.P., Jayabalan J., Sheela D.S., (2017). ”Optimal motion planning based on path

length minimisation”, Robotics and Autonomous Systems, Elsevier, vol.94, pp.245-263.

Krukhmalev V., Pshikhopov V. (2017). ”Genetic Algorithms Path Planning”, in Path Planning for

Vehicles Operating in Uncertain 2D Environments, ch.4, pp.137-184, Elsevier.

Law M.H.C., Jain A.K., Figueiredo M.A.T., (2003). ”Feature Selection in Mixture Based

Clustering”, Advances in Neural Information Processing Systems, 15, pp.609−616.

Lorenz K. and Rejer I., (2015). “Feature selection with NSGA and GAAM in EEG signals domain”,

8th IEEE International Conference on Human System Interactions (HSI 2015), pp. 94-98.

Martín-Smith P., Ortega J., Asensio-Cuber J., Gan J.Q. and Ortiz A., (2017). “A supervised filter

method for multi-objective feature selection in EEG classification based on multi-resolution analysis for

BCI”, in Neurocomputing 250, 2017, pp. 45–56.

Murphy G., Groeger J.A., Greene C.M., (2016). “Twenty years of load theory – Where are we now,

and where should we go next?”, Psychonomic Bulletin & Review, vol. 23, issue 5, pp.1315-1340, Springer

Link.

Okun O., (2011). ”Feature Selection and Ensemble Methods for Bioinformatics – Algoritmic

Classification and Implementations”, IGI Global.

Petrescu C., Ferariu L., (2009). ”Optimization Of Ferrofluid Actuator Using Evolutionary Algorithms

And Finite Element Method”, Revue Roumaine Des Sciences Techniques-Serie Electrotechnique Et

Energetique, 54(1), pp.77-86.

Rachmawati L., Srinivasan D., (2009). “Multiobjective Evolutionary Algorithm with Controllable

Focus on the Knees of the Pareto Front” in IEEE Transactions on Evolutionary Computation, 13 (4), pp.

810-824.

Rodriguez-Vazquez K., Fonseca C. M., Fleming P. J., (2004). “Identifying the Structure of Nonlinear

Dynamic Systems Using Multiobjective Genetic Programming” in IEEE Transactions on Systems Man and

Cybernetics, Part A – Systems and Humans, vol. 34, pp. 531-545.

Suthaharan S., (2016). ” Machine Learning Models and Algorithms for Big Data Classification”,

Springerlink.


55

Sweet L.H., (2011). “The n-back paradigm”, Enciclopedia of clinical neuropsychology, Springer

New York, pp.1718-1719.

Tang J., Alelyani S., Liu H., (2015). ”Feature Selection for Classification: A Review”, in Aggarawal

C.C. ed., Data Classification Algorithms and Applications, CRC Press, Taylor & Francis, pp.37-64.

Ungureanu F., Cîmpanu C., Dumitriu T., and Manta V.I., (2017). ”Cognitive Load and Short Term

Memory Evaluation Based on EEG Techniques”, The 13th eLearning and Software for Education

Conference, ELSE 2017, vol. 2, pp. 217-224, ISSN: 2066-026X, ISSN-L: 2066-026X, ISSN CD: 2343-

7669, April 27-28, Bucharest, Romania.

Upadhyay R., Manglick A., Reddy D.K., Padhy P.K., Kankar P.K., (2015). “Channel optimization

and nonlinear feature extraction for Electronecephalogram signals classification”, Computers and Electrical

Engineering, 45, Elsevier, pp.222-234.

Zarjam P., Epps J., Chen F., (2011a). “Characterizing Working Memory Load Using EEG Delta

Activity”, EUSIPCO 2011, Barcelona, Spain, August 29 - September 2, 2011.

Zhong Y., Jianhua Z., (2016). “Recognition of Cognitive Task Load Levels Using Single Channel

EEG and Stacked Denoising Autoencoder”, Proceedings of the 35th Chinese Control Conference, CCC

2016, pp. 3907-3912, Elsevier B.V.

Wang S., Gwizdka J., Chaovalitwongse W.A., (2016). “Using Wireless EEG Signals to Assess

Memory Workload in the n-Back Task”, IEEE Transactions on Human-Machine Systems, vol. 46, issue 3.,

pp. 424-435, Elsevier B.V.

METODE GENETICE DE OPTIMIZARE MULTIOBIECTIV Rezumatul ...

Documents

Transcript of METODE GENETICE DE OPTIMIZARE MULTIOBIECTIV Rezumatul ...