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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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.)
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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 𝐴𝑖.
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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(𝑡)
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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.
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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.
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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.).
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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)
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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
4. Aplicații ale metodelor genetice de optimizare multiobiectiv în probleme de planificare
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.)
5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția atributelor
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
5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția atributelor
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.)
5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția atributelor
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.)
5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția atributelor
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
5. Aplicații ale metodelor genetice de optimizare multiobiectiv în selecția 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).
6. Concluzii generale
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
6. Concluzii generale
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).
6. Concluzii generale
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.
2. Procedura genetică de optimizare multiobiectiv pentru selecția trăsăturilor relevante din
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.
3. Procedura genetică de optimizare multiobiectiv pentru selecția trăsăturilor relevante din
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).
6. Concluzii generale
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
6. Concluzii generale
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.
Lista publicațiilor
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.
Lista publicațiilor
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/.
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.
Referințe bibliografice
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.
Referințe bibliografice
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.
Referințe bibliografice
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.