IDENTIFICAREA SISTEMELOR NELINIARE PRIN TEHNICI BAZATE … · împrospătare a materialului...

UNIUNEA EUROPEANĂ GUVERNUL ROMÂNIEI

MINISTERUL MUNCII, FAMILIEI ŞI PROTECŢIEI SOCIALE

AMPOSDRU

Fondul Social European

POSDRU 2007-2013

Instrumente Structurale

2007-2013 OIPOSDRU UNIVERSITATEA TEHNICĂ

“GHEORGHE ASACHI” DIN IAŞI

UNIVERSITATEA TEHNICĂ


Şcoala Doctorală a Facultăţii de

Automatică şi Calculatoare

IDENTIFICAREA SISTEMELOR NELINIARE PRIN TEHNICI BAZATE PE PROGRAMARE

GENETICĂ

GENETIC PROGRAMMING TECHNIQUES FOR NONLINEAR SYSTEMS IDENTIFICATION

- REZUMATUL TEZEI DE DOCTORAT -

Conducător de doctorat:

Prof. dr. ing. Octavian Păstrăvanu

Doctorand:

Ing. Alina Patelli

IAŞI - 2011

UNIUNEA EUROPEANĂ GUVERNUL ROMÂNIEI

MINISTERUL MUNCII, FAMILIEI ŞI PROTECŢIEI SOCIALE

AMPOSDRU

Fondul Social European

POSDRU 2007-2013

Instrumente Structurale

2007-2013 OIPOSDRU UNIVERSITATEA TEHNICĂ


Proiectul „Burse Doctorale - O Investiţie în Inteligenţă

(BRAIN)”, POSDRU/6/1.5/S/9, ID 6681, este un proiect

strategic care are ca obiectiv general „Îmbunătățirea

formării viitorilor cercetători în cadrul ciclului 3 al

învățământului superior - studiile universitare de doctorat -

cu impact asupra creșterii atractivității şi motivației pentru

cariera în cercetare”.

Proiect finanţat în perioada 2008 - 2011.

Finanţare proiect: 14.424.856,15 RON

Beneficiar: Universitatea Tehnică “Gheorghe Asachi” din

Iaşi

Partener: Universitatea “Vasile Alecsandri” din Bacău

Director proiect: Prof. univ. dr. ing. Carmen TEODOSIU

Responsabil proiect partener: Prof. univ. dr. ing. Gabriel LAZĂR

UNIVERSITATEA TEHNICĂ “GHEORGHE ASACHI” DIN IAŞI

R E C T O R A T U L Către

______________________________________________________________

______________________________________________________________ Vă facem cunoscut că, în ziua de 1 noiembrie 2011 la ora 15.00. în Sala

de consiliu a Facultăţii de Automatică şi Calculatoare, va avea loc susţinerea publică

a tezei de doctorat intitulată:

“IDENTIFICAREA SISTEMELOR NELINIARE PRIN TEHNICI BAZATE PE

PROGRAMARE GENETICĂ”

“GENETIC PROGRAMMING BASED TECHNIQUES FOR NONLINEAR SYSTEMS

IDENTIFICATION”

elaborată de doamna ALINA PATELLI în vederea conferirii titlului ştiinţific de doctor.

Comisia de doctorat este alcătuită din:

1. Prof. Dr. Ing. Vasile Manta preşedinte Universitatea Tehnică „Gheorghe Asachi” din Iaşi

2. Prof. Dr. Ing. Octavian Păstrăvanu conducător ştiinţific Universitatea Tehnică „Gheorghe Asachi” din Iaşi

3. Prof. Dr. Ing. Daniel Coca membru Universitatea din Sheffield, Marea Britanie

4. Prof. Dr. Ing. Radu-Emil Precup membru Universitatea „Politehnica” din Timişoara

5. Conf. Dr. Ing. Lavinia Ferariu membru Universitatea Tehnică „Gheorghe Asachi” din Iaşi

CUPRINS

Introducere

1. Contribuții principale 8

2. Diseminarea rezultatelor 10

I. Metode evolutive pentru rezolvarea problemelor de optimizare multiobiectiv

1. Problema de optimizare multiobiectiv 18

2. Algoritmi evolutivi 20

3. Componentele principale ale algoritmilor evolutivi 21

3.1. Codificarea cromozomială 21

3.2. Evaluarea indivizilor 22

3.3. Selecţia pentru reproducere 22

3.4. Operatorii genetici 23

3.5. Reinserţia şi criteriul de terminare 24

4. Metode evolutive moderne pentru soluţionarea problemelor MOO 24

5. Probleme deschise şi direcţii viitoare de cercetare 25

II. Tehnici de programare genetică

1. Programarea genetică în contextul EA 30

2. Etapele principale ale algoritmilor de GP 30

2.1. Construirea setului de primitive 31

2.2. Construirea arborilor din populaţia iniţială 31

2.3. Configurarea operatorilor genetici şi de selecţie 32

2.4. Adoptarea strategiei MOO 34

2.5. Stabilirea tehnicilor de căutare locală 34

2.6. Controlul fenomenelor nedorite 35

3. Aplicaţiile GP în probleme inginereşti 36

4. Tehnici avansate pentru eficientizarea algoritmilor GP 36

5. Convergenţa EA şi alte rezultate teoretice 38

5.1. Teoria schemelor în modelarea transferului de trăsături de la părinţi la copii 38

5.2. Modelarea cu lanţuri Markov 39

Cuprins 6

5.3. Teoreme de convergenţă a algoritmilor GP 40

5.4. Perspective teoretice viitoare 40

6. Concluzii cu privire la aplicaţiile GP 41

III. Aplicaţiile programării genetice în identificarea sistemelor neliniare

1. Programarea genetică – un instrument eficient în identificarea sistemelor 44

2. Optimizare mono-obiectiv bazată pe GP pentru NSI 45

3. Optimizare multiobiectiv non-elitistă bazată pe GP pentru NSI 48

4. Optimizare multiobiectiv elitistă bazată pe GP pentru NSI 51

5. Hibrizi GP-fuzzy pentru NSI multiobiectiv 54

6. Teoria schemelor regresive în NSI multiobiectiv 56

Tabloul contribuţiilor şi concluzii generale

1. Contribuţii algoritmice 66

2. Contribuţii teoretice 69

3. Contribuţii software şi experimentale 70

ANEXA A. Bibliografie 73

INTRODUCERE

Controlul automat este unul din instrumentele principale ale progresului tehnologic. Un

element cheie in proiectarea unor sisteme automate performante il constituie determinarea

modelului matematic pentru procesul condus. Această lucrare abordează problema identificării

sistemelor neliniare, sugerând o serie de algoritmi originali bazați pe programarea genetică.

Metodele propuse sunt capabile să genereze modele exacte si compacte, asigurând astfel

fezabilitatea acestora in aplicații practice. Paradigma programării genetice a fost aleasă ca suport

al acestei cercetări datorita capacității de a răspunde la provocările impuse de problemele de

regresie simbolică, ce implică determinarea atât a structurii cât si a parametrilor modelelor.

Majoritatea abordărilor non-evolutive consideră o structură prestabilită, problema de identificare

fiind astfel redusă la estimarea parametrilor. De cele mai multe ori, în contextul aplicațiilor

inginereşti structura modelului nu este disponibilă iar o aproximare cu grad satisfăcător de

precizie este dificilă, dată fiind natura neliniară a proceselor ce trebuie modelate. În aceste

circumstanțe, programarea genetică e un instrument de interes, deoarece lucrează simultan cu

mai multe structuri de modele potențiale (o populație) distribuite pe întregul spațiu de căutare,

conform unuia sau mai multor obiective de optimizare (acuratețe, compactitate, etc). Astfel,

structura și parametrii modelelor candidate sunt optimizate continuu, în mod nesupervizat, până

la atingerea nivelului dorit de calitate. Prin distribuirea modelelor candidate peste întregul

domeniu al problemei, nu mai sunt necesare configurări suplimentare ale algoritmului (cum ar fi

punctul de start al căutării necesar in contextul procedurilor de optimizare bazate pe gradient).

Ceilalți parametrii ai algoritmului (dimensiunea populației, numărul maxim de generații,

probabilitatea de aplicare a operatorilor genetici, etc) pot fi determinați prin experimente de tip

incercare-eroare sau automat, chiar de către algoritm. Procedurile de programare genetică

evolueaza soluții candidate, de-a lungul mai multor generații, prin intermediul tranzițiilor

stohastice (folosind operatori probabilistici cum ar fi cel de recombinare sau cel de selecție).

Datorită absenței instrumentelor deterministe de calcul (derivatele folosite de metode bazate pe

gradient), programarea genetică e robustă, cu o probabilitate redusă de blocaj in puncte de optim

local si capacitatea de a lucra cu funcții obiectiv discontinue.

1. CONTRIBUȚII PRINCIPALE

Principalele contribuții propuse in această lucrare pot fi clasificate in doua categorii:

algoritmice si teoretice. Prima clasă este reprezentată de algoritmi clasici de prgramare genetică

imbunatațiți cu mecanisme originale menite să crească performanțele la rulare. Aceștia sunt

descriși la nivel conceptual si testați pe diferite scenarii experimentale, unele simple (sisteme de

test demonstrative), altele complexe (instalații industriale). Implementarea software pentru

fiecare din metodele propuse, desi nu este inclusă explicit in lucrarea de față, e disponibilă si a

Introducere 9

fost folosită in toate experimentele. Principalele contribuții referitoare la propunerea de noi

algoritmi sunt enumerate si descrise pe scurt in cele ce urmează:

1. Un algoritm de optimizare mono-obiectiv imbunătățit cu o procedură de construcție

exhaustivă a arborilor, ce generează indivizi echilibrați structural și matematic corecți,

fără redundanțe în informația codificată;

2. Suport pentru procesarea modelelor regresive (conform cu formalismul neliniar, liniar in

parametri), ceea ce implică un mecanism pentru transformarea arborilor generaţi de

procedura de construcţie exhaustivă în structuri regresive, menţinând echivalenţa

matematică relativ la arborii originali; această transformare e menită să asigure

compatibilitatea cu procedura de descompunere QR care calculează în mod determinist

parametrii modelelor;

3. Un algoritm multiobiectiv ce implementează un nou mecanism de grupare a populației

precum şi o procedură de migrație adaptivă menită să calibreze dinamic importanța

relativă a obiectivelor de optimizare folosite;

4. Un algoritm multiobiectiv elitist ce oferă suport pentru configurarea adaptivă a razei de

proximitate, parametru folosit in calculul valorilor fitness pentru incurajarea diversității;

5. Un algoritm multiobiectiv elitist în care procesul de generare a soluțiilor urmaşi este unul

dublu ramificat (peste setul elitelor si peste populația obişnuită) şi o procedura de

împrospătare a materialului genetic, ce încurajează diversitatea cu un impact negativ

minim asupra calității medii a arborilor;

6. Un algoritm hibrid evolutiv – fuzzy cu un modul fuzzy menit să evalueze fitness-ul

blocurilor structurale si să le protejeze pe cele valoroase, prin încapsulare, de efectul

distructiv al operatorului de incrucişare;

7. Un algoritm de exploatare la nivel microscopic ce combină logica fuzzy – pentru

evaluarea calității blocurilor structurale – şi instrumente de calcul bazate pe teoria

schemelor – pentru creşterea eficienței încapsulării (în ceea ce priveşte cantitatea de

informații despre sistem conținută de modelele evoluate şi consumul de resurse

computaționale);

8. Suport software pentru toate imbunatațirile menționate anterior, folosit in numeroase

validări experimentale, precum şi interpretarea rezultatelor testelor desfăşurate.

De observat că primele 5 contribuții exploatează implicit blocurile structurale, încurajând

supraviețuirea indivizilor ca un tot, in raport cu performanțele lor relativ la obiectivele

considerate (acest tip de abordare se numeşte macroscopic). A şasea contribuție e un instrument

de exploatare macro-micro, ce combină evaluarea arborilor cu cea a blocurilor constructive

(fragmente de arbori). Finalmente, a şaptea procedură sugerată exploatează blocurile structurale

in mod explicit (o abordare microscopică). Toți algoritmii propuşi rezolvă problema combinării

Introducere 10

pferințelor intr-o manieră progresivă, altfel spus logica de decizie e integrată dinamic in procesul

de căutare.

Contribuțiile teoretice se referă la o versiune originală a teoriei schemelor, ce surprinde

caracterul regresiv al modelelor. Teoria propusă are două variante:

prima e folosită pentru a monitoriza efectele încapsulării fuzzy;

a doua e implementată ca o procedură de optimizare locală peste spațiul tuturor

urmaşilor posibili ai indivizilor din generația curentă, cu scopul estimării şanselor de

supraviețuire a blocurilor structurale; această ultimă informație e apoi folosită pentru

a valida procesul de încapsulare.

Prima variantă a teoriei schemelor pentru modele regresive are doua componente:

un suport matematic cuprinzând definițiile conceptelor necesare pentru formularea

teoriei, cum ar fi notația regresorilor, taxonomia lor si descrierea folosind seturi

extinse;

probabilitățile de transmisie a cel puțin unei instanțe de schemă în generația

următoare, probabilități folosite la măsurarea eficienței încapsulării fuzzy în ceea ce

priveşte propagarea regresorilor valoroşi.

A doua variantă, mai rafinată, a teoriei schemelor pentru modele regresive are trei

componente:

componenta formală este acceaşi ca in cazul anterior;

probabilitățile de transmisie sunt reformulate pentru a putea calcula şansele de a

crea/distruge o instanță de schemă in indivizii copii relativ la parinți;

componenta predictivă oferă suport pentru calculul net al numărului aşteptat de

instanțe transmise in intreaga populație a generației următoare (spre deosebire de

limita inferioară oferită de versiunea anterioară).

2. DISEMINAREA REZULTATELOR

Rezultatele activității de cercetare desfaşurate pe perioada doctoratului au fost publicate

in 17 lucrări, anume 5 lucrări publicate în reviste – una intr-un jurnal cotat ISI cu factor de

impact 0.688 si 4 in jurnale CNCSIS B+, 3 capitole de carți – doua publicate de Springer (ISI

proceedings) si una de IGI Global, si 9 lucrări în volumele conferințelor – doua sunt indexate de

ISI Web of Knowledge, doua de IEEE Xplore, una a fost publicata sub auspiciile European

Union Control Association (EUCA), două sunt incluse in volume sponsorizate IEEE, una a fost

prezentată la un consorțiu doctoral IEEE şi una a fost publicată de Silesian University of

Technology. În prezent, două alte lucrari sunt in stadiul de recenzie.

Introducere 11

Cercetările iniţiale au vizat componentele principale ale algoritmului de programare

genetică, cum ar fi generarea arborilor si configurarea operatorilor genetici. Rezultatul a constat

în implementarea unei metode noi, imbunatațite, de construcție a cromozomilor ierarhici, şi a

unei proceduri de transformare pentru facilitarea calculului parametrilor. De asemenea, operatorii

de incrucişare si mutație au fost reconfigurați pentru a lucra mai eficient cu structurile

arborescente specifice menționate anterior. Interesul principal, in această faza inițială, a fost

testarea noilor instrumente computaționale, construite special pentru abordarea eficientă a

provocărilor impuse de problema de indentificare neliniară (codificarea regresivă a modelelor,

folosirea eficientă a materialului genetic disponibil, calculul rapid si precis al parametrilor,

selecția automată a structurii, etc). Astfel, algoritmul se bazează pe o abordare mono-obiectiv, ce

ia în considerare doar acuratețea modelelor, pentru ca interacțiunea componentelor anterior

menționate sa poată fi mai uşor studiată. Aceste aspecte au fost prezentate în:

Patelli A.

Ferariu L.

Nonlinear System Identification by

Means of Genetic Programming

Proc. of the European Control Conference,

Publicate sub auspiciile EUCA

prezentată în: Budapesta, Ungaria

ISBN 978-963-311-369-1

502

507

2009

Odată ce componentele de bază au fost integrate cu succes, activitatea ulterioară s-a

concentrat pe imbunătățirea evaluării modelelor. În acest scop, a fost introdus un nou obiectiv, pe

lângă cel de acuratețe, anume compactitatea modelului. Pentru o mai bună explorare a spațiului

de căutare, dată fiind importanța crescută a acurateții asupra compactității, a fost proiectată o

nouă tehnică de grupare a populației, în spațiul obiectivelor, în combinație cu o procedură

originală de migrație. Algoritmul rezultat a fost descris, testat si analizat în:

Ferariu L.

Patelli A.

Multiobjective Genetic Programming

for Nonlinear System Identification

Adaptive And Natural Computing

Algorithms (ISI Proceedings)

(Lecture Notes in Computer Science, 5495)

Springer

prezentată în: Kuopio, Finlanda

ISSN 0302-9743

233

242

2009

Cu toate că noul algoritm multiobiectiv beneficiază de câteva calități adiționale față de

cel mono-obiectiv (o abordare realistă a problemei de optimizare prin includerea celui de-al

doilea obiectiv, o explorare mai eficientă a spațiului de căutare, etc), el implică, în acelaşi timp, o

serie de compromisuri, în special în ceea ce priveşte compelxitatea computațională. Beneficiile si

neajunsurile celor două abordări au fost analizate în:

Patelli A.

Ferariu L.

Monoobjective and Multiobjective

Genetic Programming in Nonlinear

Systems Identification

Proc. of the 17th International Conference

on Control Systems and Computer Science,

Sponsorizată de IEEE, Romanian Division

prezentată în: Bucureşti, România

ISSN 2066-4451

9

14

2009

Introducere 12

Algoritmul multiobiectiv sugerat a fost apoi folosit pentru identificarea unui sistem

industrial complicat, cu mai multe intrări, pentru a-i observa performanțele într-un spațiu neliniar

complex. Un sistem cu timp mort a fost de asemenea considerat in analiza experimentală, în

scopul investigării capacității algoritmului de a elimina automat materialul genetic nenecesar, şi

de a configura în mod nesupervizat trăsăturile modelului nedisponibile aprioric (timpul mort).

Studiul, ce a demonstrat experimental eficienţa algoritmului sugerat in ceea ce priveşte reducerea

complexităţii modelului si explorarea unui vast spaţiu de căutare neliniar, a fost publicat în:

Patelli A.

Ferariu L.

Enhanced Multiobjective Genetic

Programming for Multivariable

Nonlinear Systems Identification

Recent Developments in Artificial

Intelligence Methods, AI-METH series

prezentată în: Gliwice, Polonia

ISBN 83-60759-15-4

247

258

2009

Activitatea ulterioară s-a axat pe rafinarea instrumentului de indentificare multiobiectiv

propus, prin extinderea platformei experimentale (sisteme de test demonstrative ce implică

provocări specifice, cum ar fi parametrii “ascunşi” – timp mort sau exponenţi ridicati ai

termenilor modelului – sisteme industriale complexe cu un comportament neliniar sever, diferite

combinaţii de valori ale parametrilor algoritmului şi studii comparative). Observaţiile

experimentale au fost apoi folosite pentru perfecţionarea algoritmilor propuşi. Un exemplu in

acest sens este imbunataţirea adusă procedurii de migraţie, anume implementarea praguriloe

adaptive. Diferite combinaţii de scenarii de test si concluziile ce au rezultat au fost publicate în:

Ferariu L.

Patelli A.

Migration-based Multiobjective

Genetic Programming for Nonlinear

System Identification

Proc. of the 5th Int. Symposium on Applied

Computational Intelligence and Informatics

(ISI Proceedings)

ISBN 978-1-4244-4478-6

475

480

2009

Ferariu L.

Patelli A.


with Insular Evolution and Adaptive

Migration

Bulletin of the University of

Timisoara:

Transactions on Automatic

Control and Computer Science

CNCSIS B+

ISSN 1224-600X

54(68) 155

162

2009

Patelli A.

Ferariu L.

Cluster Based Multiobjective Genetic

Programming in Nonlinear Systems

Identification

Annals of the University of

Craiova, Series: Automatics,

Computers, Electronics and

Mechatronics

CNCSIS B+

ISSN 1841-0626

6(33) 60

66

2009

Prima încercare de a configura un algoritm elitist de identificare a constat in

inplementarea abordării lui Deb, bazată pe conceptul de fitness partajat (engl. “fitness sharing”).

Noua viziune a fost integrată in platforma oferită de algoritmul multiobiectiv configurat anterior.

Introducere 13

Instrumentul computaţional rezultat a fost comparat cu versiunile existente considerând o

varietate de cazuri de test, concluziile fiind publicate în:

Patelli A.

Ferariu L.

Multiple Genetic Programming

Based Techniques for Nonlinear


Bulletin of the Polytechnic

Institute of Iasi

CNCSIS B+

ISSN 1220-2169

LV(LIX) 23

36

2009

Incursiunea în domeniul abordărilor elitiste a deschis drumul catre noi direcţii de

cerecetare. Mai exact, metoda fitness-ului partajat a lui Deb a fost particularizată pentru a

răspunde mai bine la neliniarităţile imprevizibile ale spaţiului de căutare, prin calculul dinamic al

parametrului rază de proximitate, crucial în asigurarea unei bune distribuţii a soluţiilor situate pe

frontul Pareto. În plus, autoarea a implementat o nouă procedură pentru gruparea elitelor în

combinaţie cu o tehnică de augmentare a fitness-ului pentru creşterea presiunii de selecţie în

favoarea elitelor fezabile. Noul algoritm obţinut prin integrarea acestor noi îmbunătăţiri în

contextul platformei multiobiectiv existente a fost descris si testat în:

Patelli A.

Ferariu L.

Elite Based Multiobjective Genetic


Identification

Advances in Electrical and

Computer Engineering

Factor de impact ISI = 0.688

ISSN 1582-7445

10(1) 94

99

2010

O analiza comparativă generală a tuturor instrumentelor computaţionale descrise până

acum au oferit autoarei oportunitatea de a testa în mod suplimentar platforma software

implementată, şi de a disemina rezultatele prin propunerea unei lucrări extinse, analizate în

cadrul unui consorţiu doctoral. Articolul a fost distins cu premiul doi în competiţia pentru cea

mai bună lucrare doctorală.

Patelli A.

Ferariu L.

Genetic Programming Based Tools

for Nonlinear Systems Identification

Doctoral Consortium of the IEEE

International Conference on Networking,

Sensing and Control

Prezentată în: Chicago, SUA

2

9

2010

Observaţiile primite în contextul consorţiului doctoral au dus la configurarea unei noi

versiuni a algoritmului elitist. Astfel, pentru a exploata mai eficient materialul genetic codificat

de elite, am implementat un proces dublu ramificat de generare a indivizilor urmaşi. Menţinerea

diversităţii populaţiei este de asemenea crucială pentru calitatea procesului de evoluţie, aşa că a

fost sugerat un mecanism de reîmprospătare a materialului genetic. Acesta constă în injecţia în

populaţia curentă a imaginii unui set nedominat de la o generaţie anterioară, în cazul în care

gradul de asemănare intre cromozomi este ridicat. Algoritmul ce încorporează aceste două

tehnici a fost descris în:

Introducere 14

Patelli A.

Ferariu L.

Elitist Multiobjective Nonlinear

Systems Identification with Insular

Evolution and Diversity Preservation

Proc. of the IEEE Congress on

Evolutionary Computation (ISI

Proceedings)

Prezentată în: Barcelona, Spania

ISBN 978-1-4244-6910-9

1

6

2010

Algoritmii elitişti (publicaţi în ultimele două lucrări menţionate anterior) au fost

comparaţi cu abordări nonelitiste considerând scenarii experimentale diverse. În plus, următoarea

lucrare conţine o comparaţie între instrumentele evolutive de identificare sugerate şi alţi

algoritmi populari pentru generarea de modele neliniare (utilizând reţele MLP şi RBF precum si

structuri NLP maximale cu reduceri ulterioare de termeni). Toate aceste rezultate, împreună cu o

analiză reziduală reprezentativă au fost incluse în:

Ferariu L.

Patelli A.

Genetic Programming for System

Identification

Formal and Practical Aspects of Autonomic

Computing and Networking: Specification,

Development and Verification

IGI Global

în

curs

de

publi

care

2009

Următoarea etapă a cercetărilor mele s-a axat pe exploatarea cromozomilor la nivel

microscopic. Toate metodele anterioare foloseau unelte evolutive (operatori genetici, metode de

calcul al valorilor fitness, operatori de selecţie, etc) la nivel macroscopic, analizând indivizii ca

entităţi globale/unitare. Noua direcţie a presupus investigarea blocurilor structurale interne ale

cromozomilor, prin intermediul unui controler fuzzy special configurat în acest scop. Procedura a

fost hibridizată cu mai multe tehnici de exploatare macroscopică, rezultatele legate de logica

algoritmului si performaţele experimentale fiind incluse în:

Patelli A.

Ferariu L.

Increasing Crossover Operator

Efficiency in Multiobjective


Proc. of the IEEE Int. Conf. on Intelligence

Systems (indexed by Scopus)

Prezentată în: Londra, Marea Britanie

ISBN 978-1-4244-5164-7

426

431

2010

Cercetarea a continuat în contextul exploatării microscopice prin implementarea unei

metode noi, mai eficiente, pentru configurarea parametrilor modulului fuzzy folosit. Rezultatele

experimentale au arătat că hibridul miro-macro cu parametri fuzzy configuraţi dinamic avea

performanţe asemănătoare cu cele ale abordărilor pur macroscopice. Aceste concluzii, impreună

cu algoritmii suport, au fost publicate în:

Patelli A.

Ferariu L.

Dynamic Fuzzy Controlled

Regressor Encapsulation in Evolving

Nonlinear Models

Proc. of the 14th Int. Conf. on System

Theory and Control

Sponsorizată de IEEE Control Systems

Society

Prezentată în: Sinaia, România

ISSN 2068-0465

373

378

2010

Introducere 15

Patelli A.

Ferariu L.

Regressor Encapsulation Using

Fuzzy Control in Evolving Nonlinear

Models

Annals of the University of

Craiova, Series: Automatics,

Computers, Electronics and

Mechatronics

CNCSIS B+

ISSN 1841-0626

7(34) 26

32

2010

Rezultatele practice promiţătoare menţionate anterior au constituit un imbold pentru

continuarea cercetării în domeniul exploatării explicite a blocurilor structurale, ceea ce a condus

la dezvoltarea unei tehnici pur microscopice. În acest nou algoritm este introdusă o versiune

originală a teoriei schemelor, una special construită pentru modele regresive. Eficienţa acestui

nou instrument (probabilităţi matematice calculate în contextul teoretic al schemelor) în

monitorizarea eficienţei modulului fuzzy relativ la promovarea blocurilor structurale adaptate

este ilustrată în:

Patelli A.

Ferariu L.

Regressor Survival Rate Estimation

for Enhanced Crossover

Configuration

Adaptive And Natural Computing

Algorithms (ISI Proceedings)

(Lecture Notes in Computer Science, 6593)

Springer

prezentată în: Ljubljana, Slovenia

ISSN 0302-0743

290

300

2011

Ulterior, autoarea a sugerat două îmbunătăţiri ale teoriei schemelor menţionate anterior.

Prima utilizează analiza propagării schemelor ca o tehnica de căutare locală peste spaţiul tuturor

structurilor posibile de indivizi copii. Spre deosebire de monitorizare, această nouă abordare

presupune implementarea unei bucle de reacţie negativă pentru controlul acţiunii operatorilor

genetici. Cu alte cuvinte, folosind numărul aşteptat de instanţe de regresori calculat în cadrul

teoriei schemelor, procesul de încapsulare fuzzy poate fi aplicat doar atunci când este necesar,

salvând astfel resurse computaţionale. Prima versiune a algoritmului îmbunătăţit foloseşte doar

operatorul de încrucişare, şi a fost dezvoltată în două etape. Lucrările respective sunt momentan

în cadrul procesului de recenzie:

Patelli A.

Ferariu L.

Regressive Schema Theory Based

Methods in Evolutionary Nonlinear


Journal of Control Engineering

and Applied Informatics

ISI indexed

în curs de

recenzare

2011

Patelli A.

Ferariu L.

Variable Size and Shape Schema

Theory for Explicit Building Block

Exploitation in GP

Genetic Programming and

Evolvable Machines

în curs de

recenzare

2011

Am construit a doua variantă îmbunătăţită a teoriei schemelor considerând atât operatorul

de încrucişare cât şi pe cel de mutaţie. Această parte a cercetării a fost publicată în:

Introducere 16

Patelli A.

Ferariu L.

A regressive schema theory based

tool for GP

evolved nonlinear models

Proc. of the 17th International Conference

on Automation & Computing

Indexată de IEEE Xplore

ISBN 978-1-86218-098-7

215

220

2011

De asemenea, menţionez cele doua perioade de mobilitate desfăşurate la Universitatea

din Sheffield, dat fiind că au reprezentat o şansă pentru aprofundarea inţelegerii domeniului

programării genetice şi nu numai. Bazele de date ştiinţifice şi resursele de cercetare puse la

dispoziţie de către universitate au constituit un ajutor important în realizarea acestei lucrări:

Statut Departament Universitate Perioadă

student Automatic Control and Systems

Engineering

University of Sheffield

Martie – Iulie 2008

doctorand Automatic Control and Systems

Engineering

University of Sheffield

Mai – August 2010

I. METODE EVOLUTIVE PENTRU REZOLVAREA

PROBLEMELOR DE OPTIMIZARE MULTIOBIECTIV

1. PROBLEMA DE OPTIMIZARE MULTIOBIECTIV

Cele mai multe probleme de optimizare din domeniul ingineriei, implică existenţa mai

multor criterii (obiective), de obicei conflictuale. Rezolvarea unei astfel de probleme se numeşte

optimizare multiobiectiv (engl. multiobjective optimisation – MOO). Teoretic, există un numar

infinit de soluţii optimale, acest set (setul Pareto optimal) având o formă dificil de descris

analitic. Scopul oricărei metode de optimizare este aproximarea cât mai exactă a setului Pareto

optimal, prin construirea unei imagini discrete conţinând un număr mare de puncte uniform

distribuite. Principalele provocări legate de atingerea acestui scop se referă la spaţiul de căutare

vast, uneori dinamic, la cantitatea limitată de informaţii a priori relativ la domeniul problemei, la

prezenţa zgomotului şi/sau la forma neregulata (discontinuă, concavă, etc) a frontului Pareto.

Matematic, problema MOO este descrisă de Definiţia I.1. Orice problemă de maximizare

poate fi trensformată într-una de minimizare prin schimbarea semnului funcţiilor obiectiv. În

această lucrare, noţiunile de optimizare si minimizare sunt echivalente, fără pierderea

generalităţii.

Definiţia I.1. Fie k funcţii obiectiv, kif ni ,,:)x( 1 , şi m+p constrângeri, anume

pjhhmigg jn

jin

i ,,)x(,:,,,)x(,: 1010 . Problema de optimizare

multiobiectiv constă în minimizarea/maximizarea ))x(,),x(()x(F kff 1 1 unde x este

vectorul variabilelor de decizie.

Toţi vectorii x ce respectă constrângerile de mai sus formează spaţiul admisibil sau

fezabil, notat . Această lucrare consideră cazul restricţiilor simple, de tip inegalitate, ce

mărginesc superior/inferior valorile variabilelor de decizie, supinfjjj lxl .

Când sunt implicate obiective multiple, relaţia de ordine ce se poate defini în raport cu

vectorii valorilor obiectiv este una parţială. Oricare doi vectori din spaţiul de decizie se află în

una din următoarele relaţii: dominanţă (slabă) şi non-dominanţă. Fie x1 şi x2 doi vector din

spaţiul de decizie asociat problemei MOO.

Definiţia I.2. Vectorul x1 domină slab vectorul x2, cu notaţia 21 xx , dacă si numai dacă

2121 1 x,x,,),x()x( kiff ii .

1 În această lucrare, un vector n

α e simbolizat prin oricare din următoarele notaţii: ),,( n1

şi ][ n1 . Cum, în această lucrare, vectorii sunt importanţi din perspectiva componentelor lor, nu se face

distincţie între vectorii linie si cei coloană, cu excepţia cazurilor când acest lucru e specificat explicit.

I. Metode evolutive pentru rezolvarea problemelor de optimizare multiobiectiv 19

Definiţia I.3. Vectorul x1 domină vectorul x2, cu notaţia 21 xx , dacă si numai dacă

kiff ii ,),x()x( 121 , şi 2121 x,x),x()x(: ii ffi .

Definiţia I.4. Vectorii x1 şi x2 sunt în relaţie de non-dominanţă (nedominaţi unul faţă de

celălalt), cu notaţia 21 xx , dacă si numai dacă )x()x(: 21 ii ffi şi

2121 1 x,x,,,),x()x(: kjiffj jj .

Soluţia problemei MOO, în cazul general, când obiectivele sunt parţial conflictuale, e dat

de setul tuturor vectorilor nedominaţi din spaţiul fezabil . Fie x şi x’ doi vectori din spaţiul de

decizie.

Definiţia I.5. Vectorul x este Pareto optimal dacă si numai dacă 'x , x’ nu îl domină

pe x.

Intuitiv, Definiţia I.5 afirmă că x fie domină, fie e în relaţie de non-dominanţă cu orice

altă soluţie din spaţiul de decizie.

Dat fiind faptul ca spaţiul variabilelor de decizie si cel al obiectivelor de optimizare sunt

distincte, se impune următoarea clarificare. Setul Pareto optimal conţine toate soluţiile

nedominate din spaţiul de decizie, P = { x /x e dat de Definiţia I.5}. Fiecare soluţie Pareto

optimală corespunde unui punct din spaţiul obiectivelor, reuniunea acestora constituind frontul

Pareto optimal, }Px/)x(F{FP , unde F e introdus în Definiţia I.1. În cazuri simple, frontul

Pareto optimal e continuu si convex. În situatii practice, e foarte probabil ca fronturile Pareto să

fie discontinue şi/sau concave, cu unul sau mai multe puncte de inflexiune. În asemenea situaţii,

aproximarea frontului Pareto e o problemă NP completă, ce necesită metode de rezolvare

robuste, de genul celei propuse în (Rachmawati şi Srinivasan, 2009).

Una dintre cele mai populare abordări clasice relativ la rezolvarea problemei MOO

constă in reducerea ei la una mono-obiectiv. Acest lucru poate fi realizat prin agregarea

obiectivelor, ordonare lexicografică, ordonare min-max, etc. Dezavantajele acestor proceduri

constau în necunoaşterea ponderilor relative ale obiectivelor (folosite în construcţia funcţiilor

agregate), a priorităţilor acestora (necesare în ordonarea lexicografică) şi în generarea unei soluţii

Pareto optimale la fiecare rulare (neajuns comun tuturor ceor trei tehnici menţionate anterior

Problemele MOO pot fi rezolvate şi prin metoda programării “compromisului” (eng.

compromise programming) (Ehrgott, 2005), metodă ce determină limitele inferioară şi superioară

ale frontului Pareto optimal. Metoda e aplicabilă în cazul în care frontul Pareto are o formă

complicată (concavă, cu puncte de inflexiune), însa cunoscută aprioric, sau cel puţin aproximată

cu grad acceptabil de acurateţe. La acest dezavantaj, se adaugă dificultatea calculului funcţiilor

obiectiv inverse (metoda implică determinarea punctelor din spaţiul de decizie corespunzătoare


celor din spaţiul obiectiv), o provocare dificilă în cazul problemelor reale, unde criteriile de

optimizare pot avea forme analitice complicate. În plus, se menţine neajunsul generării setului

Pareto optimal punct cu punct, fiind necesară câte o rulare a algoritmului pentru fiecare noua

soluţie nedominată.

În cazul problemelor MOO cu funcţii obiectiv neliniare, aplicarea metodelor de rezolvare

bazate pe gradient e condiţionată de folosirea aproximărilor liniare (funcţiile obiectiv/restricţiile

nederivabile sunt transformate in funcţii cuadratic diferenţiabile) (Mietinnen, 2004), ceea ce

reduce acurateţea soluţiilor generate. Spre deosebire de metodele clasice de optimizare (care

abordează obiectivele multiple prin agregare si neliniarităţile prin liniarizare), algoritmii

evolutivi (eng. evolutionary algorithms - EA) nu impun ipoteze de lucru dificil de îndeplinit,

fiind capabili sa gestioneze neliniarităţi, chiar în prezenţa funcţiilor obiectiv nedifierenţiabile.

Datorită căutării bazate pe populaţii, EA oferă mai multe soluţii nedominate într-o singură rulare,

ceea ce-i permite inginerului să configureze algoritmul în sensul generării unui set Pareto bine

reprezentat si divers.

2. ALGORITMI EVOLUTIVI

Una dintre cele mai folosite clasificări ale metodelor de optimizare implică existenţa a

trei categorii (Coello Coello et al, 2007). Abordările enumerative testează iterativ toate soluţiile

fezabile, şi au un grad restrâns de aplicabilitate, ce exclude problemele cu spaţii de căutare

multidimensionale, vaste. Procedurile deterministe cuprind metodele bazate pe gradient,

algoritmii “greedy” şi abordările bazate pe grafuri (“branch & bound”, căutare în

lăţime/adâncime/începând cu cel mai bun candidat, etc). Ele necesită o definire detaliată a

funcţiilor obiectiv pentru calcularea derivatelor de diferite ordine (în cazul metodelor bazate pe

gradient) sau pentru organizarea spaţiului de căutare pe o structură de graf. În plus, tehnicile din

această categorie necesită informaţii apriorice referitoare la sistemul vizat, pentru a configura o

serie de parametrii interni cum ar fi soluţia iniţială sau pasul de invăţare (pentru metodele bazate

pe gradient). La acestea se adaugă dificultăţile întâmpinate de metodele deterministe în

rezolvarea problemelor cu optime locale (cu derivata nulă), discontinuităţi (unde nu se poate

calcula derivata) sau multimodale (este generat cel mult unul din optimele globale per rulare).

Spre deosebire de abordările deterministe, cele stohastice au un grad ridicat de autonomie,

parţial datorită configurării aleatoare a unor parametrii interni. Cu toate acestea, metodele

stohastice non-evolutive generează o singură soluţie la o rulare. Datorită naturii lor

probabilistice, algoritmii din această clasă sunt dificil de descris teoretic (printre altele,

demonstrarea convergenţei lor e problematică).

Printre trăsăturile atractive ale EA (pe lânga cele enumerate la sfârşitul capitolului 1) se

numără capacitatea crescută de explorare, datorată distribuţiei populaţiei iniţiale peste întregul


spaţiu de căutare. Pe lângă aplicabilitatea crescută a EA în cadrul problemelor multimodale, cu

spaţii de căutare multidimensionale, explorarea eficientă mai are un efect pozitiv, anume

descoperirea unor relaţii ascunse, uneori contra-intuitive, între variabilele de decizie. Cum

parametrii EA sunt, în mare parte, auto-adaptaţi (configuraţi în interiorul algoritmului, cu

implicare minimă din partea designer-ului uman), cantitatea de informaţii apriorice necesare este

redusă, clasa EA fiind inclusă în cea a tehnicilor nesupervizate de optimizare. Flexibilitatea

procesului de evaluare si calcul al valorilor fitness pentru fiecare model potenţial face ca

algoritmii evolutivi sa poată fi uşor configuraţi pentru rezolvarea problemelor multiobiectiv.

3. COMPONENTELE PRINCIPALE ALE ALGORITMILOR EVOLUTIVI

Din punct de vedere computaţional, un EA implică parcurgerea următoarei secvenţe de

paşi:

Formularea unei legi de codificare pentru construcţia indivilor din populaţia iniţială.

Evaluarea fiecărui individ prin calculul ieşirilor funcţiilor obiectiv considerate.

Asignarea de valori fitness care să reflecte parformanţele (gradul de adaptare) al

cromozomilor din populaţie2.

Selecţia părinţilor pentru bazinul de reproducere pe baza valorilor fitness calculate

anterior.

Aplicarea operatorilor genetici asupra cromozomilor din bazinul de reproducere

pentru generarea soluţiilor copii.

Reinserarea copiilor generaţi în populaţie.

Reiterarea algoritmului începând cu pasul al doilea în cazul în care criteriul de

terminare nu este îndeplinit.

3. 1. CODIFICAREA CROMOZOMIALĂ

Stabilirea informaţiilor de codificat în cromozom depinde direct de specificul problemei.

Cele mai uzitate modalităţi de codificare sunt cea liniară, folosind un alfabet binar, real, etc, şi

cea ierarhică, unde un individ e stocat sub formă de arbore. Această ultimă variantă de codificare

e folosită în programarea genetică, dat fiind că un arbore (Fig. II.1) suprinde mai uşor caracterul

ierarhic (în sensul că o instrucţiune e subordonată logic alteia) al unui program de calculator

decât codificarea liniară. Pentru a creşte capacitatea de explorare a instrumentului de identificare

2 În această lucrare, valorile fitness nu sunt echivalente cu valorile obiectiv. Fitness-ul e interpretat ca o

probabilitate de selecţie, folosită pentru a măsura şansele unui individ anume de a fi inclus în bazinul de

reproducere. Astfel, valorile fitness sunt în aşa fel calculate încât să reflecte valorile obiectiv, şi în acelaşi timp să

respecte definiţia unor probabilităţi – să fie situate în intervalul [0 1] iar suma lor să fie 1.


configurat în (Patelli şi Ferariu, 2009c), autoarea propune metoda exhaustiva de construcţie a

arborilor (eng. exhaustive tree building), bazată pe trei reguli ce încurajează producţia de arbori

compacţi (fără material genetic redundant) şi echilibraţi structural (vezi capitolul 2 din partea a

III-a pentru detalii).

3. 2. EVALUAREA INDIVIZILOR

În contextul EA, fitness-ul este un număr real ce măsoară capacitatea unui arbore de a

minimiza funcţiile obiectiv. Acest indicator numeric al adaptării este luat în considerare la

selecţia indivizilor pentru bazinul de reproducere, motiv pentru care valorile fitness sunt, de fapt,

probabilităţi de selecţie. În cazul problemelor MOO, principala provocare relativ la definirea

funcţiei de fitness CFit : , unde C reprezintă setul de cromozomi, constă în stabilirea unei

legături între performanţele arborilor, exprimate prin mai multe valori obiectiv, şi o valoare reală

unică. În acest context, cele mai cunoscute metode de calcul al valorilor fitness sunt cea bazată

pe scalare (eng. scaling), ce pastrează diferenţele relative între indivizi, şi cea bazată pe rang

(ranking), unde e indivizii sunt ordonaţi echidistant, cu efect de temperare a presiunii de selecţie.

În cazul problemelor MOO fără agregare, o metodă des folosită de calcul al valorii fitness este

cea bazată pe analiza dominaţei (Deb, 2001). Valorile obiectiv sunt folosite doar pentru calculul

distanţei între doua soluţii în spaţiul obiectivelor. Valoarea fitness Fit(c) (I.1) va reflecta ordinul

frontului Pareto PFi pe care se situează soluţia curentă c (Fit(c) e cu atât mai mare cu cât i e mai

mic, deci soluţia e mai aproape de frontul Pareto real) şi gradul de aglomerare (Fit(c) creşte cu

cât soluţia curentă are mai puţin vecini, pentru a încuraja arborii solitari să roducă indivizi copii

în zonele slab reprezentate ale frontului Pareto).

),(

),()(

zcdiPFz

R

zcd

FcFit

1

.

(I.1)

În (I.1), FR reprezintă o valoare de referinţă ce scade odată cu ordinul frontului Pareto

curent i, d e distanţa euclidiană, iar simbolizează raza de proximitate, jalonul în funcţie de

care se determină dacă vecinii lui c sunt apropiaţi sau nu. În versiunea originală a procedeului de

analiză a nondominaţei, parametrul este fixat aprioric. Autoarea sugerează o metoda de calcul

dinamic pentru , pentru calculul realist al valorilor fitness (vezi 4 din partea a III-a).

3. 3. SELECŢIA PENTRU REPRODUCERE

Selecţia parinţilor poate fi deterministă, fiecărui individ atribuindu-i-se un număr fix de

selecţii, sau stohastică. În ultimul caz, cromozomilor li se acordă o şansă de a fi selectaţi

proporţională cu fitness-ul asignat în faza de evaluare. De exemplu, în cazul selecţiei universale


stohastice (eng. stochastic universal sampling – SUS), fiecarui individ îi este atribuit un sector de

cerc de arie proporţională cu valoarea sa de fitness, selecţia efectivă desfăşurându-se după

principiul ruletei. Alegerea celui mai bun individ este astfel cea mai probabilă, însă nu este

garantată. În acest fel este descurajată pierderea diversităţii, un pericol în cazul selecţiei

deterministe, cauzată de includerea mai multor copii ale aceluiaşi individ în bazinul de

reproducere. Selecţia bazată pe competiţii de ordin k este un alt procedeu stohastic, unde

cromozomii sunt grupaţi în s grupuri (nu neapărat disjuncte) a câte k indivizi, din fiecare grup

fiind selectată soluţia cu fitness-ul cel mai ridicat. După fiecare selecţie, individul inclus în bazin

este şters din populaţia curentă, ceea ce evită inserţiile multiple şi încurajează diversitatea

(prevenind astfel convergenţa prematură).

3. 4. OPERATORII GENETICI

Scopul evoluţiei este moştenirea trăsăturilor bine adaptate ale părinţilor de către indivizii

copii. Astfel, operatorii genetici trebuie configuraţi în aşa fel încât să recombine eficient

materialul genetic al părinţilor pentru a îndeplini dezideratul anterior. Operatorul de încrucişare

cu punct de tăiere slectează un nod în structura fiecăruia din cei doi părinţi şi interschimbă

subarborii corespunzători. În încercarea de a controla dimensiunea cromozomilor urmaşi şi de a

asigura transmiterea trăsăturilor (codificate de subarbori/blocuri structurale) adaptate în

generaţiile următoare, au fost propuse diferite variante de operatori de încrucişare cu punct de

tăiere (vezi 2.3). Autoarea sugerează două versiuni originale ale acestui operator, prima fiind

capabilă să detecteze blocurile structurale identice (cu cele mai mari şanse de a reprezenta

trăsături bine adaptate) şi să le protejeze de tăiere. A doua versiune de încrucişare selectează

punctele de tăiere conform unor probabilităţi modificate de un procedeu original, numit

încapsulare fuzzy. Astfel, blocurile structurale vor fi “tăiate” cu o probabilitate p ce reflectă

gradul lor de adaptare (stabilit de un controler fuzzy) – p e mai mare pentru blocurile slab

adaptate şi mai mică pentru cele valoroase.

Lucrarea de faţă propune doua versiuni originale ale operatorului de mutaţie. Prima,

mutaţia duble impact, poate modifica atât numele terminalilor cât şi exponentul lor, acest din

urmă efect reprezentând un mijloc suplimentar de comtrol al dimensiunii arborilor. Al doilea

operator de mutaţie sugerat modifică un nod terminal (înlocuindu-l cu o alelă) cu o probabilitate

calculată în urma procesului de încapsulare fuzzy. Justificarea este aceeaşi ca în cazul

operatorului de incrucişare cu punct de tăiere amintit anterior, anume protejarea regresorilor în

mod proporţional cu gradul lor de adaptare.


3. 5. REINSERŢIA ŞI CRITERIUL DE TERMINARE

Reinserţia, adică selecţia indivizilor pentru generaţia următoare, are un dublu rol în cadrul

procesului de evoluţie. În primul rând, ea trebuie să asigure transmiterea materialului genetic de

calitate (cromozomi cu fitness ridicat) al generaţiei curente, în cea următoare. În al doilea rând,

un operator de reinserţie bine configurat va menţine un grad acceptabil de diversitate în

populaţie, evitând promovarea în generaţiei următoare a indivizilor identici sau foarte

asemănători. Schema generală de reinserţie este )/(,

, unde reprezintă numărul de

indivizi din generaţia curentă, simbolizează numărul de părinţi selectaţi pentru bazinul de

reproducere, iar notează numarul de indivizi urmaşi (Kramer, 2008). Dacă se optează pentru

reinserţia de tip “+” (model generaţional cu suprapunere) cromozomii din generaţia viitoare sunt

selectaţi dintre cei părinţi şi copii (DeJong, 2006). Această abordare e eficientă în cazul în

care fitness-ul mediu al copiilor e mai mic decat cel al parinţilor, considerarea populaţiei reunite

ca bază de selecţie prevenind riscul scaderii calităţii medii a populaţiei de la o generaţie la alta.

În cazul reinserţiei “,” (model generaţional fără suprapunere) indivizii noii generaţii sunt aleşi

dintre cei copii, ceea ce restricţionează viaţa unui anume cromozom la o singură generaţie.

Schema de reinserţie ),,,( k încurajează diversitatea (DeJong, 2006), eliminând un

cromozom după k generaţii, indiferent de fitness-ul său.

Criteriul de terminare al buclei evolutive poate fi de trei feluri (Koza, 1998):

generaţional, de evaluare şi de excepţie. Predicatele generaţionale opresc algoritmul dupa un

număr prescris de iteraţii. Predicatele de evaluare sistează evoluţia odată cu obţinerea unei soluţii

care minimizează toate funcţiile obiectiv considerate complet (eroare de aroximare nula –

predicat de evaluare absolut) sau în limite acceptabile (eroarea de aproximare se situează sub o

anumită valoare – predicat de evaluare aproximativ). Algoritmul evolutiv se poate termina în

situaţii excepţionale, cum ar fi existenţa unui singur individ în populaţie (când dimensiunea

acesteia nu este fixată). Sunt utile şi combinaţii ale predicatelor de terminare menţionate anterior.

4. METODE EVOLUTIVE MODERNE PENTRU SOLUŢIONAREA PROBLEMELOR MOO

Procedurile evolutive se pot clasifica după mai multe criterii. În ceea ce priveşte etape de

reinserţie, EA pot fi elitişti (când cel mai bun individ al generaţiei curente supravieţuieşte

garantat şi în generaţia următoare) sau nonelitişti (când exista riscul pierderii individului cel mai

bine adaptat din populaţia curentă). Relativ la modul în care sunt promovate trăsăturile utile din

structura cromozomilor, se disting două categorii, anume algoritmi cu exploatare implicită a


blocurilor structurale (eng. building blocks - BB) şi cei cu exploatare explicită. Din prima

categorie fac parte EA ce apreciază calitatea unui individ la nivel global (abordare

macroscopică), iar în a doua se încadrează algoritmii ce analizează structura cromozomilor la

nivel de subarbore (abordare microscopică). După modul în care este implementat mecanismul

de decizie (direcţionarea căutării spre zonele admisibile, cu aplicabilitate practică ale spaţiului de

căutare), EA se împart în algoritmi cu articulare a priori a preferinţelor (agregarea

obiectivelor, penalizarea soluţiilor neadmisibile, etc), cu articulare progresivă a preferinţelor

(mecanismul de decizie e distribuit pe parcursul procesul de evoluţie) şi cu articulare a posteriri

a preferinţelor (selecţia soluţiilor admisibile se face dupa generarea frontului Pareto final). Cu

privire la etapa de evaluare a indivizilor, metodele evolutive pot fi Pareto (calculul valorilor

fitness se face pe baza principiului dominanţei) sau non-Pareto (nu se ţine cont de relaţia de

dominanţă). Mai distingem clasa algoritmilor evolutivi puri, ce respectă schema de principiu din

introducerea capitolului 3, si cea a algoritmilor evolutivi memetici, unde procesul evolutiv e

hibridizat cu tehnici (deterministe sau de altă natură) de căutare locală.

Din multitudinea tehnicilor evolutive moderne propuse în literatură pentru rezolvarea

problemelor MOO, am selectat (în teza extinsă) câteva dintre cele mai importante, organizate în

conformitate cu clasificările de mai sus. Categoriile cele mai slab reprezentate în literatură sunt

cele caracterizate de articularea progresivă a preferinţelor (simbioza dintre mecanismul de

decizie si procesul evolutiv e dificil de implementat datorită complexităţii logice) şi de

exploatarea explicită a BB (analiza la nivel de fragment de cromozom implică un efort

computaţional considerabil). Toţi algoritmii propuşi în această lucrare completează prima nişă

semnalată integrând dinamic mecanismul de decizie în cadrul procesului de evoluţie (tehnici de

grupare, bonificaţii de fitness pentru dirijarea populaţiei, etc). Algoritmul hibridizat cu module

de logică fuzzy şi instrumente derivate din teoria schemelor (capitolul 6 din partea a III-a)

exploatează explicit blocurile structurale, pentru o promovare eficientă a trăsăturilor adaptate în

generaţiile ulterioare (fiind astfel adresată si a doua provocare menţionată).

5. PROBLEME DESCHISE ŞI DIRECŢII VIITOARE DE CERCETARE

Domeniul EA este unul tânăr. În consecinţă, lista provocărilor legate de eficientizarea

procedurilor evolutive în probleme de optimizare/identificare este consistentă. Literatura de dată

recentă (O’Neill et al, 2010) subliniază cele mai importante aspecte legate de EA, insuficient

investigate la momentul curent, a căror perfecţionare ar putea conduce la o nouă generaţie de

instrumente computaţionale.

Codificarea cromozomială (şi implicit construcţia indivizilor din populaţia iniţială)

depinde direct de specificul problemei de rezolvat, trebuind să asigure, simultan, un consum

redus de memorie, o cantitate suficientă de material genetic pentru a reprezenta soluţia la nivelul


de calitate dorit şi o configurare uşoară a operatorilor genetici. Dată fiind natura heterogenă a

acestor deziderate, elaborarea unui proceduri/reguli unice de codificare, valabilă pentru o gamă

largă de probleme, e o chestiune dificilă. În contextul rezolvării problemei identificării sistemelor

neliniare, această lucrare propune un algoritm exhaustiv de construcţie (eng. exhaustive building

– EB) a cromozomilor arborescenţi din populaţia iniţiala (2 din partea a III-a). Procedura EB

generează modele potenţiale compatibile cu fomalismul neliniar, liniar în parametri (NLP), un

aproximator universal (se poate construi un model NLP pentru a aproxima orice funcţie continuă,

cu orice grad de acurateţe). De aici aplicabilitatea largă a procedurii de construcţie exhaustivă.

Regulile pe care se bazează algoritmul EB asigură absenţa terminalilor redundanţi din arborii

iniţiali. În plus, forma matematică particulară a modelelor NLP implică doar doi operatori (+ si

*). Aceste doua aspecte asigură un consum redus de memorie pentru stocarea populaţiei iniţiale.

Logica procedurii EB garantează inserţia tuturor terminalilor disponibili (de aici termenul

“exhaustiv” din denumire), ceea ce oferă o bază de material genetic suficientă pentru un proces

evolutiv de calitate. Codificarea NLP este de natură regresivă (vezi 2 din partea a III-a pentru

detalii), ceea ce permite configurarea operatorilor genetici (încrucişare cu punct de tăiere si

mutaţie punctuală) în scopul promovării trăsăturilor (blocurilor structurale) adaptate, adică al

exploatării microscopice.

Scalabilitatea EA se referă la capacitatea de a rezolva o gamă largă de probleme de

complexităţi diferite, prin generarea de module funcţionale (fragmente de indivizi/blocuri

structurale) echivalente cu segmentele de cod reutilizabil din programarea clasică. Această

lucrare propune o soluţie algoritmică pentru generarea si exploatarea modulelor funcţionale în

context regresiv (6 din partea a III-a). În esenţă, un regresor bine adaptat este încurajat (prin

încapsulare fuzzy şi operatori genetici specifici) să supravieţuiască de la o generaţie la alta,

compunerea mai multor astfel de regresori ducând la generarea unor indivizi capabili să

optimizeze din ce in ce mai bine funcţiile obiectiv. Astfel, regresorii pot fi priviţi ca module de

cod reutilizabil, folosite de diferite programe (reprezentate de cromozomi ierarhici).

Pentru a determina dacă un algoritm evolutiv este un instrument potrivit pentru

rezolvarea unei anumite probleme, eficienţa sa trebuie estimată înainte de folosirea propriu-zisă,

sau măsurată pe o problemă de test, şi comparată cu cea a altor proceduri. Acest lucru este greu

de realizat datorită caracterului stohastic, deci imprevizibil, al algoritmilor evolutivi. În contextul

identificării neliniare, autoarea propune un instrument teoretic de evaluare a eficienţei metodei

bazate de GP propuse în capitolul 6 din partea a III-a. Este astfel calculată rata de supravieţuire a

regresorilor bine adaptaţi de la o generaţie la alta (cu cât este mai mare cu atât algoritmul e mai

eficient), fără a necesita estimări, ci folosind doar informaţii disponibile la momentul curent.

Convergenţa prematură cauzată de pierderea diversităţii populaţiei este un dezavantaj

major al EA elitişti. Datorită promovării intense a cromozomilor bine adaptaţi, există riscul ca


materialul genetic al acestora să se multiplice excesiv, cu impact negativ asupra capacităţii de

explorare a noi regiuni din spaţiul de căutare. Pentru a preveni apariţia acestui fenomen nedorit,

unul din algoritmii sugeraţi (capitolul 4 din partea a III-a) pastrează diversitatea populaţiei prin

implementarea unui proces dublu de generare a soluţiilor urmaş, arborii rezultaţi fiind reuniţi în

urma unei analize a similitudinii. În plus, populaţia e reîmprospătată cu material genetic dintr-o

generaţie anterioară atunci când gradul de diversitate scade sub un prag prestabilit.

O alta provocare importantă este asigurarea unui echilibru între exploatare si explorare,

între promovarea blocurilor structurale adaptate şi investigarea noilor regiuni din spaţiul de

căutare. În acest scop, autoarea propune un mecanism de încapsulare folosit la configurarea unor

operatori genetici ce protejează instanţele blocurilor adaptate si creează altele noi (capitolul 6 din

partea a III-a). Astfel, e încurajată generarea de cromozomi cu fitness ridicat si diversitate

structurală mare.

Caracterul stohastic al EA face dificilă construcţia unui model teoretic general ce ar

permite formularea si demonstrarea unor teoreme de convergenţă sau ar facilita descrierea

matematică şi imbunătăţirea unor fenomene interne procesului evolutiv. Această lucrare

sugerează o versiune originală a teoriei schemelor, adaptată la cazul regresorilor, variabili ca

formă şi dimensiune (capitolul 6 din partea a III-a). Suportul matematic construit este apoi folosit

pentru demonstrarea riguroasă a eficienţei tehnicii de încapsulare, în ceea ce priveşte promovarea

BB adaptate.

În cele de mai sus am arătat cum algoritmii originali propuşi de autoare (partea a III-a)

răspund unor provocări de data recentă din domeniul EA. Eficienţa lor este demonstrată

experimental şi/sau teoretic în ultima parte a lucrării.

II. TEHNICI DE PROGRAMARE GENETICĂ

1. PROGRAMAREA GENETICĂ ÎN CONTEXTUL EA

Programele de calculator oferă un suport unitar pentru exprimarea soluţiilor unor

probleme diverse. În plus, sunt direct implementabile, fără a necesita “traducerea” în limbajul de

programare dorit, ca în cazul modelelor matematice. Koza postuleaza că programele de

calculator sunt destul de complexe si flexibile pentru a exprima soluţia oricărei probleme, oricât

de dificilă ar fi aceasta (Koza, 1998). În încercarea de a dezvolta un algoritm universal, capabil

de a rezolva orice problemă, exprimând rezultatul sub forma unui program de calculator, Koza a

introdus fundamentele unei noi paradigme evolutive, în sfera de confluenţă a inteligenţei

artificiale cu ştiinţa calculatoarelor, anume programarea genetică. Conform exemplului lumii

biologice, unde fiecare provocare importantă este rezolvată prin procedeul unic al adaptării la

mediu, GP oferă un algoritm unic (fără modificări substanţiale de la o aplicaţie la alta), înseşi

soluţia la problema rezolvării problemelor, în general.

Cum marea majoritate a problemelor din domeniul ingineresc au soluţii ce pot fi

exprimate în formalismul intrare-ieşire, GP are un domeniu de aplicabilitate larg. Legatura

strânsă dintre programele de calculator si structurile arborescente a fost prezentată în 3.1. Într-un

arbore, fiecare nod poate reţine adresele rădăcinii si succesorilor săi, ceea ce face ca execuţia

(evaluarea) programelor codificate să fie mai rapidă ca în cazul reprezentării liniare. Din acest

punct de vedere, GP e un instrument computaţional potrivit pentru problemele ce implică mai

multe funcţii obiectiv (MOO). Bineînteles, strategiile generice, comune tuturor EA, pentru

eficientizarea explorarii spaţiului obiectivelor pot fi preluate şi îmbunătăţite în cadrul GP

(capitolul 3 din partea a III-a).

Dintre trăsăturile specifice ale GP, se remarcă posibilitatea codificării directe a

informaţiei în genom (nodurile arborelui sunt instrucţiuni si operatori ai programului

reprezentat), nefiind necesară prelucrări suplimentare (ca în cazul GA cu indivizi binari). Spre

deosebire de alte paradigme evolutive ce lucrează cu structuri de dimensiuni si forme fixe, GP nu

necesită astfel informaţii apriorice. Forma si dimensiunea indivizilor evoluaţi este configurată

automat, prin aplicări repetate ale operatorilor genetici şi de selecţie, în contextul obiectivelor

considerate.

2. ETAPELE PRINCIPALE ALE ALGORITMILOR DE GP

Sunt prezentate în cele ce urmează paşii de parcurs în configurarea unei proceduri de

optimizare bazate pe programare genetică. Diferenţele faţă de etapele algoritmului evolutiv

generic, prezentate în capitolul 3, sunt subliniate şi comentate pentru o mai bună întelegere a

importanţei GP ca instrument computaţional individual.

II. Tehnici de programare genetică 31

2. 1. CONSTRUIREA SETULUI DE PRIMITIVE

GP este teoretic capabilă sa genereze arbori pornind de la un set voluminos de operatori

(algebrici, logici, etc). Această abordare nu este fezabilă din punct de vedere computaţional

deoarece resursele algoritmului s-ar pierde pe eliminarea materialului genetic redundant în loc să

fie investite în îmbunătăţirea arborilor din populaţie. Astfel, e de preferat un set de funcţii (cvasi)

minimal, ce îndeplineşte condiţiile lui Koza de închidere şi suficienţă (Koza, 1998).

În cazul utilizării frecvente a unor segmente de arbore anume, se poate opta pentru funcţii

definite automat (eng. automaticaly defined functions – ADF), echivalentele codului reutilizabil

din programarea clasică. Acestea sunt de fapt noduri compactate ce conţin informaţii minimale

cu privire la subarborele pe care îl “ascund”. La evaluare, un nod ADF se expandează o singură

dată, rezultatul fiind folosit de câte ori este nevoie în structura aceluiaşi arbore, sau a arborilor

diferiţi.

În cazul problemelor complexe, cum ar fi identificarea/controlul sistemelor neliniare sau

diagnoză, stabilirea unui set de primitive e precedată de găsirea unui formalism matematic

convenabil, capabil să reprezinte modelul dorit/legea de control. Un astfel de formalism pentru

exprimarea modelelor intrare-ieşire ale sistemelor eliniare este cel neliniar, liniar în parametri

(NLP). Modelele NLP sunt regresive, reprezentând combinaţii liniare de termeni neliniari numiţi

regresori, adică sume de produse:

nickFcky irr

iriri ,,,)()(ˆ 1 ; )()( kxkFj

jir . (II.1)

Iesirea cu numarul i a sistemului, cu valoarea estimată ŷi la momentul k, e o combinaţie

liniară de regresori notaţi Fir, cu coeficienţi reali, cir. În acest context, setul de terminali conţine

toate intrările si ieşirile sistemului la diferite tacte (II.2), iar setul de operatori are doua elemente,

anume adunarea şi înmulţirea.

)}(y,),(y),(u,),(u),(u{)(x yu nkknkkkk 11 . (II.2)

Setul de terminali x conţine toate intrările sistemului, stocate în vectorul u, şi toate

ieşirile sale, incluse în vectorul y, începând de la tactul curent k şi regresând până la întârzierile

maxime pe intrare (nu) şi ieşire (ny).

2. 2. CONSTRUIREA ARBORILOR DIN POPULAŢIA INIŢIALĂ

Seturile de primitive sunt folosite la construcţia indivizilor din populaţia iniţială, prin

inserţii repetate ale elementelor lor în structura cromozomilor ierarhici. Pentru a încuraja

explorarea, metoda de construcţie a arborilor trebuie să distribuie uniform arborii pe întreaga

întindere a spaţiului de căutare.


Procedura exhaustivă de construcţie a arborilor (EB), descrisă în capitolul 2 din partea a

III-a, are ca scop generarea unor indivizi echilibraţi structural (prevenind apariţia cromozomilor

foarte mici, foarte mari sau degeneraţi în liste). EB nu impune restricţii explicite asupra formei

sau dimensiunii arborilor, însă regulile pe care se bazează încurajează generarea arborilor

compleţi, care conţin toţi terminalii disponibili organizaţi într-o formă cvasi-simetrică. De

remarcat că EB nu prezintă dezavantajul abordărilor de tip eliminare (engl pruning) care includ

toate combinaţiile posibile de primitive în arborele iniţial, apoi elimină gradual termenii

redundanţi. În schimb, EB asigură doar prezenţa tuturor terminalilor în fiecare genom iniţial,

algoritmul GP urmând a-i combina în regresori, exploataţi în contextul teoriei schemelor

regresive (secţiunea 6 din partea a III-a).

2. 3. CONFIGURAREA OPERATORILOR GENETICI ŞI DE SELECŢIE

Cel mai important aspect de avut în vedere la stabilirea combinaţiei optime de operatori

genetici este echilibrul dintre exploatare şi explorare. La nivel macroscopic (individul e exploatat

ca un întreg), se poate folosi operatorul de copiere/reproducere/replicare pentru exploatarea

arborilor adaptaţi şi operatorul de încrucişare cu punct de tăiere pentru explorarea noilor zone ale

spaţiului de căutare. Dacă problema e privită la nivel microscopic (arborele e văzut ca o

combinaţie de blocuri structurale), se poate opta pentru operatorul de încapsulare în scopul

exploatării (protejării) BB şi pentru un operator de încrucişare special configurat să fabrice noi

subarbori bine adaptaţi, în scopul explorării.

În literatura de specialitate, operatorul de încapsulare substituie o combinaţie de noduri

dintr-un arbore cu un meta-operator, imun la acţiunea operatorilor genetici (Koza, 1998),

(Rodriguez-Vasquez, 1999), (Ashlock, 2005). Nodul simbolic protejează astfel subarborii bine

adaptaţi, fiind expandat la forma iniţială după terminarea procesului de evoluţie. În varianta sa

clasică, operatorul de încapsulare e de natura deterministă, adică poate fi aplicat sau nu, în

funcţie de calitatea subarborelui înlocuit. Versiunea propusă în această lucrare (capitolul 6 din

partea a III-a) e aplicată cu o probabilitate cuprinsă între 0 şi 1, depinzând de gradul de adaptare

al BB analizat. Astfel, cele două situaţii posibile implicate de varianta clasică (încapsulare totală

sau absentă) sunt înlocuite cu o gamă mai largă de posibilitaţi (încapsulare de diferite intensităţi,

unde fiecare bloc e protejat într-o măsură egală cu gradul său de adaptare). Noul operator de

încapsulare diminuează probabilitatea ca încrucişarea să selecteze un nod de tăiere în interiorul

unui bloc protejat (diminuarea e cu atât mai accentuată cu cât blocul e mai bine adaptat - Fig.

II.1). Gradul de adaptare al unui BB anume e stabilit de un controler fuzzy (vezi capitolul

capitolul 6 din partea a III-a).


Fig. II.1. Regresori (BB) cu diferite probabilităţi de încapsulare: p = probabilitate implicită de selecţie (= 1/n), n =

numărul de noduri terminal din arbore, p1, p2 = probabilităţi de selecţie după încapsulare, p1 = f(ga(R1)), p2 =

f(ga(R2)), ga(R) = gradul de adaptare a lui R, ga(R3) = 0 R3 nu e încapsulat (nodurile interne ale lui R3 îşi

menţin probabilităţile implicite de selecţie); dacă )()( 12 RgaRga atunci p1 < p2 < p; dacă )()( 21 RgaRga atunci

p2 < p1 < p; regresorii cu un singur terminal nu sunt încapsulaţi indiferent de ga (ei sunt deja atomici, deci imuni

la acţiunea operatorilor genetici)

Operatorul de încrucişare cu punct de tăiere (engl. cut point crossover - cpCO) poate

configurat pentru a preveni difuzia trăsăturilor prin deviaţie (engl. diffusive bias) (Poli şi

McPhee, 2003a). Acest efect se bazează pe presupunerea că trasăturile adaptate au o influenţă

pozitivă asupra calităţii arborelui gazdă dacă sunt situate la o anumită poziţie (au o rădăcină

anume). Pentru a evita deviaţia rădăcinii în arborii copii, ceea ce ar duce la difuzia/diluarea

efectului pozitiv exercitat de BB, punctele de tăiere din cei doi părinţi sunt selectate la aceeaşi

poziţie, în cadrul unor regiuni cu topologii asemănătoare. De remarcat că, în cazul arborilor

compatibili NLP (II.1), pericolul difuziei prin deviaţie este nul datorită comutativităţii

operatorului de nmuliţire. Încrucişarea poate fi configurată pentru controlul dimensiunii soluţiilor

urmaşi prin interschimbarea unor subarbori cu acelaşi număr de noduri (engl. size fair

crossover). Varianta de cpCO propusă în această lucrare (capitolul 6 din partea a III-a) selectează

nodurile de tăiere conform cu probabilităţile stabilite prin încapsulare fuzzy, protejând adecvat

trăsăturile adaptate (exploatare) şi generând altele noi din materialul genetic neîncapsulat

(explorare).

Operatorul de selecţie implementat de autoare include în bazinul de reproducere N/2

părinţi din totalul de N indivizi din populaţie. Întregul efectiv de N arbori rezultaţi în urma

aplicării operatorilor genetici (cei N/2 părinţi reuniţi cu cei N/2 copii) sunt reinseraţi în populaţia

generaţiei următoare. Considerarea efectivului reunit al părinţilor şi copiilor evită cazul posibil,

deşi improbabil, ca, în pofida încapsulării, fitness-ul mediu al urmaşilor să rezulte redus în

comparaţie cu cel al predecesorilor. Menţinerea unei dimensiuni constante a populaţiei previne

p2 N

+

+ ×

+

+

+

R1 R1

R3 R2

R2

R2

p p

p

p

p

×

D E

p1

p1 p1

p1 p1

A ×

B C

×

* p2

p2 p2

×

F G

p2

p2 p2

p2 p2

×

F G

M p1

p1 p1

p1 p1

A ×

B C

× ×

F G


explozia demografică (creşterea exponenţială a numărului de arbori), pentru controlul

consumului de resurse computaţionale.

2. 4. ADOPTAREA STRATEGIEI MOO

În majoritatea problemelor realiste, calitatea soluţiilor e evaluată relativ la mai multe

criterii de performanţă, uzual conflictuale. De exemplu, în identificare, se urmeşte obţinerea unui

model exact – cu eroare de modelare minimă peste setul de date de antrenare – si compact – cu

număr redus de termeni. (Vladislavleva, 2008) extinde noţiunea de compactitate (parcimonie)

pornind de la ideea că simplitatea structurală nu este de ajuns pentru a garanta o capacitate de

generalizare satisfăcătoare. Conform cercetătoarei, un comportament adecvat peste setul de date

de validare e condiţionat de netezimea modelului în spaţiul obiectivelor (de absenţa anomaliilor

punctuale severe), ceea ce permite extrapolarea în puncte ce nu sunt incluse în setul de date de

antrenare. Proprietatea e denumită parcinomie comportamentală (engl. behavioural parsimony).

După stabilirea obiectivelor de optimizare, evaluarea indivizilor în context MOO se poate

realiza în manieră non-Pareto (abordarea prădător-pradă) sau Pareto, făcând apel la analiza

dominaţei. Datorită naturii conflictuale a criteriilor de optimizare, spaţiul obiectiv e organizat

conform unei relaţii de ordonare parţială, numită non-dominanţă, introdusă de Definiţia I.4 din

partea I. Împarţirea populaţiei pe fronturi Pareto de diferite ordine (prin determinarea setului

nedominat, izolarea lui şi repetarea celor doi paşi până la epuizarea indivizilor generaţiei

curente) e o operaţie de complexitate O(N2), unde N e numărul indivizilor din populaţie (Coello

Coello et al, 2007). Valorile fitness se acordă invers proporţional cu ordinul frontului Pareto

(soluţiile de pe fronturi cu ordin scăzut sunt mai aproape de frontul Pareto optimal, deci vor avea

fitness mare) şi cu gradul de aglomerare (soluţiile din zone slab populate ale frontului sunt

încurajate prin fitness ridicat să producă urmaşi în vecinătatea lor) (Deb, 2001).

Pentru a garanta supravieţuirea soluţiilor de pe frontul Pareto de ordin 0 (nedominate

relativ la întreaga populaţie) se poate apela la o strategie elitistă, unde acestea sunt stocate într-o

arhivă externă. Lucrarea de faţă propune mai multe proceduri pentru gestionarea eficientă a

arhivei, cum ar fi gruparea populaţiei pentru calibrarea dinamică a ponderii obiectivelor de

optimizare (3 din partea a III-a) si un ecanism de generare a soluţiilor urmaş ce vizează atât

populaţia activă cât şi indivizii din arhivă (4 din partea a III-a).

2. 5. STABILIREA TEHNICILOR DE CĂUTARE LOCALĂ

Pentru a reduce timpul de rulare al algoritmilor inspiraţi din natură (relativ la procedurile

deterministe de optimizare), platforma evolutivă de bază poate fi hibridizată cu tehnici de căutare

locală (engl. local search - LS), rezultând un algoritm memetic (Coello Coello et al, 2007),


(Smith, 2007), (Ong et al, 2006), (Molina et al, 2010). Scopul unei LS este îmbunătăţirea soluţiei

curente într-o vecinătate locală, ţinând cont de faptul că mecanismele evolutive nu sunt

instrumente de precizie. Astfel, abordările Lamarckiene stochează în cromozom genele

modificate de LS, în timp ce tehnicile Baldwiniene înlocuiesc indivizii originali cu cei obţinuţi

dupa rafinarea locală, fără a stoca modificările în genom (nu sunt prevăzute gene pentru

atributele modificate de LS) (Smith, 2007).

Descompunerea QR este o tehnica deterministă de căutare locală, ce generează o soluţie

unică la problema determinării parametrilor modelului (capitolul 2 din partea a III-a). Conform

codificării propuse (capitolul 2 din partea a III-a), nu sunt prevăzute gene pentru stocarea

coeficienţilor modelului, însă valorile acestora sunt considerate în faza de evaluare. În concluzie,

procedura LS bazată pe QR se situează între cele două categorii menţionate anterior.

Încapsularea fuzzy (capitolul 5 din partea a III-a) e o tehnică LS stohastică ce reprezintă o

abordare Baldwiniană.

2. 6. CONTROLUL FENOMENELOR NEDORITE

Pierderea diversităţii populaţiei favorizează convergenţa prematură, un fenomen

nedorit ce poate duce la blocaj în puncte de optim local. (Deb, 2001) sugerează stabilirea unei

hipersfere, centrată în punctul din spaţiul obiectiv reprezentând individul curent, cu rază

configurată aprioric sau dinamic, prin recalculare la fiecare generaţie (Patelli şi Ferariu, 2010b)

dacă vecinătatea astfel delimitată conţine un număr mare de indivizi, cromozomul central e

penalizat, deoarece zona ocupată de acesta e deja bine reprezentată. O altă posibilitate constă în

relaxarea relaţiei de non-dominanţă, astfel că soluţiile ce sunt uşor mai slabe ca cele dominante,

relativ la un număr restrâns de obiective, sunt de asemenea incluse în setul nedominat. Formarea

perechilor de părinţi poate constitui un factor de păstrare a diversităţii dacă sunt aleşi cromozomi

suficient de îndepărtaţi (în sens euclidian) în spaţiul obiectivelor.

Dezechilibrul între explorare şi exploatare poate fi cauzat de promovarea exagerată a

elitelor sau de generarea de indivizi în zone noi ale spaţiului de căutare cu preţul scaderii calitaţii

acestora. Motorul principal al explorării este operatorul de încrucişare, ce poate fi folosit, la nivel

microscopic, şi pentru exploatarea blocurilor adaptate prin evitarea divizării acestora. Astfel,

indivizii urmaşi vor moşteni trăsăturile utile ale părinţilor, fiind încurajată de asemenea formarea

altora noi (prin combinarea materialului genetic conţinut de blocurile neprotejate ale

predecesorilor).

Fenomenul de expandare (engl. bloat) constă în creşterea dimensiunii medii a arborilor

din populaţie, fără niciun câştig în materie de fitness (Poli et al, 2008). Complexitatea structurală

crescută este, de obicei, un semn al unei capacităţi slabe de generalizare. În majoritatea cazurilor,


considerarea unui obiectiv de complexitate e o metodă eficientă de prevenţie a expandării, însă

se poate avea în vedere şi configurarea operatorilor genetici în acest sens.

3. APLICAŢIILE GP ÎN PROBLEME INGINEREŞTI

O arie de interes crescut în domeniul ingineresc este cea a controlului automat, câteva

exemple reprezentative de aplicaţii ale GP în acest context fiind disponibile în (Koza, 1998).

Lucrarea de faţă aplică principiile GP în rezolvarea problemei identificării sistemelor neliniare,

un efort motivat de faptul că un model matematic de calitate simplifică substanţial sinteza unei

strategii eficiente de control.

Găsirea unui model prin tehnici de GP implică atât identificarea unei structuri adecvate

cât si configurarea setului optimal de parametri, o problemă compusă numita regresie simbolică.

În această lucrare, termenii “modelare” şi “regresie simbolică” sunt echivalenţi3. Rezolvarea

problemei de modelare poate fi văzută ca o buclă cu reacţie negativă (Vladislavleva, 2008) ce

include trei etape principale: (I) generarea, analiza şi adaptarea datelor experimentale, (II)

dezvoltarea propriu-zisă a modelului, (III) analiza şi reducerea problemei. Generarea datelor

experimentale e realizată prin simulare sau observare directă în timpul funcţionării sistemului.

Analiza şi adaptarea datelor experimentale nu fac obiectul acestei lucrări. Dezvoltarea modelului

se poate realiza utilizând un algoritm bazat pe GP, organizat conform descrierii din capitolul 2,

sau considerând una din metodele alternative amintite în alineatul următor. A treia etapă

presupune validarea modelului şi interpretarea informaţiilor conţinute de acesta. De exemplu,

cele mai frecvent întâlnite blocuri din structura indivizilor nedominaţi pot conţine informaţii

despre variabilele reprezentative ale sistemului şi despre modul în care trebuie combinate pentru

a obţine calitatea dorită. Reducerea constă în identificarea variabilelor nesemnificative, ce nu

apar în modelele finale, sau au coeficienţi neglijabili.

Literatura conţine analize comparative bine documentate între GP şi alte tehnici populare

de identificare neliniară (Vladislavleva, 2008). Concluziile exprimate de Vladislavleva identifică

dimensiunea crescută a spaţiului de căutare şi caracterul stohastic (imprevizibil) ca fiind

principalele neajunsuri ale abordărilor bazate pe GP relativ la celelalte alternative. Totuşi

cercetătoarea conchide că avantajele GP (enumerate în capitolul 1) plasează acest tip de metode

în categoria celor competitive.

4. TEHNICI AVANSATE PENTRU EFICIENTIZAREA ALGORITMILOR GP

Literatura de dată recentă abundă în strategii pentru creşterea performanţelor

computaţionale (viteză, consum de memorie, robusteţe, etc) ale algoritmilor bazaţi pe GP.

3 Unele abordări definesc modelarea prin calculul parametrilor pe o structură dată.


Enumerăm aici doar ceva dintre aceste propuneri, o analiză detaliată fiind disponibilă în lucrarea

extinsă. Configurarea parametrilor (probabilităţile de aplicare a operatorilor genetici,

dimensiunea populaţiei, etc) poate fi făcută în contextul specific al problemei de rezolvat, ceea

ce duce la algoritmi specializaţi, performanţi în situaţia dată, dar ineficienţi în circumstanţe

diferite. Folosirea procedurilor cu parametri generici nu necesită reconfigurarea acestora pentru

fiecare nouă problemă, ceea ce le conferă aplicabilitate largă, însă cu performanţe medii.

Controlul parametrilor e realizabil în manieră deterministă (valorile parametrilor se schimbă

dupa o regulă matematică la un interval de timp dat), adaptivă (modificările se realizează în

concordanţă cu raspunsul algoritmului, uzual, în funcţie de valoarea unei alte variabile) sau

autoadaptivă (prin codificarea lor în genom, ca în cazul strategiilor evolutive – vezi capitolul 2

din partea I).

Acţiunea operatorului de încrucişare poate fi monitorizată/modelată pe baza distanţei

operative (engl. operator based distance) propuse în (Gustafson şi Vanneschi, 2008). Generarea

noilor indivizi prin aplicarea cpCO se poate realiza plecând de la o colecţie de blocuri structurale

(fragmente de indivizi generate aleator) în loc de a recombina material genetic din structura

parinţilor (Day, 2005). Cromozomii pot avea o comportare substanţial diferită relativ la scenarii

distincte de fitness (în modelare, un scenariu de fitness e un subset al mulţimii de date de

antrenare, necesar evaluării individului la momentul k). Pentru o evaluare rafinată a arborilor,

(Day şi Nandy, 2008) utilizează câte un şir binar de lungime p, unde p reprezintă numărul

scenariilor de fitness, pentru fiecare individ evaluat. Fiecare locaţie din şir codifică mărimea

erorii de modelare pe scenariul curent – 0 pentru eroare mare, 1 pentru eroare mică (engl. binary

string fitness characterisation). Diversitatea semantică a indivizilor e asigurată prin folosirea

unei baze de date sematice (Beadle şi Johnson, 2009) ce stochează, în fază iniţială, toţi

terminalii disponibili. Aceştia sunt combinaţi prin considerarea câte unui operator, structurile

rezultate fiind reinserate în baza de date dacă sunt unice. Fenomenul de expandare (vezi 2.6)

poate fi controlat la nivel genotipic – metoda limitei dinamice (Silva şi Costa, 2009), a distanţei

de editare (Gustafson, 2004), a criteriului combinat de complexitate (Patelli şi Ferariu, 2010e) –

şi la nivel fenotipic – metoda Tarpeiana (Poli, 2003), sau cea a liniilor de descendenţă genetică

(Gustafson, 2004).

Algoritmii memetici prezintă pericolul supra-exploatării vecinătăţii locale investigate

(procedura LS nu mai poate aduce îmbunătăţiri soluţiei curente), situaţie evitată în (Molina et al,

2010) prin folosirea conceptului de lanţuri locale. (Lara et al, 2009) propun o metodă LS (engl.

hill climber with side step) ce anlizează geometria conului gradienţilor în spaţiul obiectivelor

pentru determinarea direcţiei de căutare. Amintim aici cele doua tehnici LS folosite de algoritmii

propuşi în 2 şi 6 (partea a III-a), anume descompunerea QR pentru calculul parametrilor şi


modulul hibrid fuzzy-TSR (teoria schemelor regresive), ce explorează spaţiul tuturor perechilor

de noduri de tăiere posibile.

5. CONVERGENŢA EA ŞI ALTE REZULTATE TEORETICE

Intuitiv, populaţia procesată de un algoritm GP este un nor de puncte (indivizi) care, pe

parcursul evoluţiei, îşi schimbă forma şi dimensiunea în spaţiul de căutare (Poli et al, 2010).

Construcţia unui suport teoretic pentru metodele computaţionale bazate pe GP implică

identificarea regulilor ce ghidează mişcarea norului. Acest deziderat e dificil de îndeplinit

datorită dimensiunii crescute şi complexităţii domeniului problemei. Pot fi modelate fenomene şi

mărimi interne procesului de evoluţie, cum ar fi expandarea arborilor, viteza procesului de

explorare sau numărul de blocuri structurale din componenţa indivizilor generaţiei următoare.

Dezavantajul acestor modele parţiale este capacitatea lor redusă de a surprinde interacţiunile

neliniare subtile între componentele algoritmului.

5. 1. TEORIA SCHEMELOR ÎN MODELAREA TRANSFERULUI DE TRĂSĂTURI DE LA

PĂRINŢI LA COPII

În (Poli şi McPhee, 2003b) o schemă este un arbore format din noduri specifice, de tip

operator şi terminal şi noduri generice (engl. wildcard), ce pot fi substituite cu orice primitivă

disponibilă. De remarcat ca schemele introduse de Poli şi McPhee sunt poziţionate, adică

nodurile specifice ocupă locaţii fixe în toţi arborii ce reprezintă aceeaşi schemă. (Patelli şi

Ferariu, 2011a) definesc o schemă ca o expresie, fără simboluri generice, ce se poate situa

oriunde în structura unui arbore. În context NLP, o schemă conţine doar operatori de tip

înmulţire şi terminali, fiind expresia analitică a unui regresor (fragment de arbore sau bloc

structural). Astfel, noile scheme sunt nepoziţionate, de formă şi dimensiune variabile, permiţând

monitorizarea dinamicii blocurilor (la nivel microscopic), schemele poziţionate descrise mai sus

fiind utile doar pentru analize macroscopice.

(Poli şi McPhee, 2003b) sunt primii care formulează o teorie exactă a schemelor

(poziţionate, de formă şi dimensiune fixe), oferind o valoare netă a numărului aşteptat de indivizi

ce instanţiază schema H, E[m(H,t)] din (II.3). Adjectivul “exactă” atribuit teoriei schemelor se

referă la caracterul net al rezultatului din (II.3), spre deosebire de abordările anterioare care

ofereau limite superioare/inferioare. Caracterul stohastic al ecuaţiei (II.3) e dat de termenul

),( tH , ce reprezintă probabilitatea ca un individ nou creat să instanţieze schema H, şi e inerent

tuturor EA datorită selecţiei probabilistice a părinţilor şi a punctelor de tăiere. Simbolul M

semnifică dimensiunea populaţiei la generaţia curentă t.

MtHtHmE ),()],([ . (II.3)


Teoria macroscopică a schemelor (Poli şi McPhee, 2003b) oferă o descriere matematică a

acestei cantităţi.

Teorema II.1. Probabilitatea totală de transmisie a unei scheme H de formă şi dimensiune fixe,

sub acţiunea operatorului de încrucişare cu punct de tăiere este:

1 2

212121

1

h h Hi jxo

xo

jiHLhiHUhhhjipthpthpp

tHpptH

)),,(()),((),|,(),(),(

),()(),(

. (II.4)

In (II.4), pxo reprezintă probabilitatea aplicării operatorului de încrucişare. Dacă acesta nu

este aplicat, unul din părinţi va trece nemodificat în generaţia t+1. În acest caz, ),( tH

reprezintă probabilitatea ca părintele în discuţie să instanţieze schema H, anume

)(

),(),(),(

tfM

tHftHmtHp , unde m(H, t) simbolizează numărul de instanţe ale schemei H la

generaţia curentă t, f(H,t) notează fitnessul mediu al instanţelor schemei H, M reprezintă numărul

de indivizi la generaţia t, iar )(tf e fitnessul mediu4 al tuturor arborilor din populaţie.

În cel de-al doilea termen din (II.4), p(h, t) marchează probabilitatea de a selecta părintele

h, ce se poate calcula uşor, dat fiind că selecţia părinţilor e proporţională (vezi 3.3 din partea I).

Probabilitatea de a selecta punctele de tăiere i şi j în cei doi părinţi h1 şi h2 e reprezentată de p(i,

j|h1, h2). Predicatul )(exp returnează 1 dacă expresia primită ca argument de intrare e adevarată.

U(H, i) şi L(H, i, j) din (II.4) sunt hiperscheme, adică arbori ce conţin noduri specifice (terminali

şi operatori) şi noduri generice ( “=” şi “#”). Nodurile “#” pot fi înlocuite cu orice subarbore

legal din punct de vedere sintactic. Cele două hiperscheme (U(H, i) se referă la partea superioară

a schemei relativ la nodul i iar L(H, i, j) la partea ei inferioară) sunt construite în contextul

reprezentării carteziene sugerate de Poli şi McPhee, explicaţii detaliate fiind oferite în lucrarea

extinsă.

Teoria schemelor de formă şi dimensiune variabile menţine avantajul unei estimări nete a

numărului de instanţe ale schemei H la generaţia următoare, şi elimină necesitatea reprezentării

carteziene. Astfel, nu este necesară renumerotarea nodurilor, convenţia “preordine” considerată

la iniţializare rămânând valabilă pe toată durata procesului evolutiv.

5. 2. MODELAREA CU LANŢURI MARKOV

Toţi EA îndeplinesc condiţia Markov (Poli et al, 2010) prin aceea că arborii generaţiei

curente sunt alcătuiţi din materialul genetic al generaţiei precedente. Cu alte cuvinte, starea

curentă a lanţului Markov folosit la modelarea procesului de evoluţie depinde numai de cea

4 Poli consideră că fitness-ul individului T este ieşirea funcţiei obiectiv obţinută pentru T


precedentă. Modelele bazate pe lanţuri Markov oferă suport pentru calculul probabilitaţii de a

găsi soluţia problemei în n paşi, pentru determinarea fitness-ului mediu al populaţiei, etc.

(Poli şi Langdon, 2007) sugerează un model bazat pe lanţuri Markov pentru

comportamentul unui program (spre deosebire de abordarea clasică ce studiază evoluţia unei

întregi populaţii). Scopul celor doi cercetători este calculul probabilităţii ca programul să conţină

instrucţiuni de salt, şi al probabilitaţii ca programul sa-şi execute ultima instrucţiune (engl.

halting probability). (Mitavskiy şi Cannings, 2009) folosesc lanţuri Markov pentru a calcula

frecvenţa de apariţie pe termen lung a unei enume secvenţe de stări (configuraţii posibile ale

populaţiei). Acest parametru, numit distribuţie staţionară, e utilizat pentru determinarea timpului

de rulare mediu al algoritmului de GP până la generarea soluţiei şi pentru aprecierea deplasării

(engl. bias) cauzate de selecţie şi recombinare. (Ong et al, 2006) folosesc lanţuri Markov pentru

a demosntra convergenţa globală a algoritmilor memetici (descrişi în 2.5). În acest context,

matricea de tranziţie P asociată procedurii hibride e definită ca produsul a patru componente: cea

datorată încrucişării Pc, cea asociată mutaţiei Pm, cea corespunzătoare selecţiei Ps, şi cea legată

de tehnica LS, Pl.

5. 3. TEOREME DE CONVERGENŢĂ A ALGORITMILOR GP

Teoremele de convergenţă propuse în literatură (Coello Coello et al, 2007), (Kramer,

2008) au o serie de dezavantaje. Cele mai importante se referă la garantarea convergenţei în

număr infinit de paşi, şi la condiţiile restrictive impuse (cunoaşterea distanţei dintre frontul

Pareto curent şi cel real, construcţia unei liste cu structura şi probabilităţile de generare ale

tuturor urmaşilor ce pot fi obţinuţi din arborii curenţi, etc). În lucrarea extinsă sunt prezentate

câteva exemple concrete de astfel de teoreme, avantajele şi neajunsurile fiecăreia fiind discutate

pe larg.

5. 4. PERSPECTIVE TEORETICE VIITOARE

Teoria schemelor oferă suport pentru calculul numărului aşteptat de instanţe ale unei

scheme în generaţiile viitoare5. Acest instrument poate fi aplicat numai atunci când se foloseşte o

anumită combinaţie de operatori genetici – numai cpCO (Poli şi McPhee, 2003b), (Poli et al,

2008), cpCO şi mutaţie punctuală (McPhee şi Poli, 2002), (Patelli şi Ferariu, 2011a), etc. În plus,

majoritatea rezultatelor legate de teoria schemelor sunt obţinute în prezenţa unui anume tip de

5 În (Poli si McPhee, 2003b), numărul aşteptat de instanţe ale unei scheme, la generaţia t+1, e calculat în

condiţiile în care numărul de instanţe de la generaţia curentă t e cunoscut. Dacă procedura e aplicată recurent,

estimarea pentru generaţiile t+s, 2s se bazează pe estimările anterioare, ceea ce duce la scăderea graduală a

preciziei de predicţie.


selecţie, anume cea proporţională. (Poli et al, 2010) sugerează investigarea altor combinaţii

posibile de operatori genetici si de selecţie, un posibil răspuns la această provocare fiind oferit de

versiunea regresivă a teoriei schemelor, descrisă în capitolul 6 al părţii a III-a, aplicabilă sub

acţiunea operatorului de selecţie bazată pe rang. Teoria schemelor rescrie dinamica algoritmilor

GP în sistemul de referinţă al blocurilor structurale (Poli et al, 2010), însă, la momentul actual,

nu a fost propusă nicio strategie clară pentru definirea acestor blocuri. Metoda descrisă în

capitolul 6 al părţii a III-a se înscrie în această direcţie de cercetare deoarece propune o definiţie

clară a conceptului de bloc structural, acesta fiind echivalent cu un regresor. În plus, componenta

I a TSR formalizează riguros toate noţiunile folosite în dezvoltarea propriu-zisă a teoremelor

implicate. (Poli et al, 2010) militează în favoarea unei noi clasificări, bazată pe comportamentul

agoritmilor GP după modelul tabelului periodic al lui Mendeleev. Autorii propun de asemenea

modelarea algoritmilor GP în medii dinamice, unde poate fi exploatată flexibilitatea teoriei

schemelor şi lanţurilor Markov.

6. CONCLUZII CU PRIVIRE LA APLICAŢIILE GP

Ca toţi algoritmii evolutivi, GP prezintă o serie de avantaje dificil de obţinut prin

implementarea metodelor deterministe de optimizare. GP lucrează cu populaţii de soluţii, deci

evoluează mai multe modele candidate în acelaşi timp, conform principiului supravieţuirii celui

mai bine adaptat (relativ la obiectivele considerate). Astfel, algoritmul asigură o capacitate

crescută de explorare, de folos pentru rezolvarea problemelor multidimensionale. Robusteţea GP

rezidă în tranziţiile stohastice de la o generaţie la alta, realizate de operatorii de selecţie, genetici

si de reinserţie (capitolul 2). În acest mod, riscul blocării în puncte de optim local este

semnificativ redus, iar lucrul cu funcţii obiectiv discontinue/neliniare devine posibil (capitolul 1).

Principala trăsătură a GP, care diferenţiază această tehnică de restul paradigmelor EA,

este codificarea cromozomilor ierarhici (capitolul 1). Folosirea cromozomilor arborescenţi

influenţează configurarea operatorilor genetici, o legatură de interes pentru cerecetători, în

încercarea de a asigura un echilibru între exploatare şi explorare. Hibridizarea algoritmilor GP cu

metode de căutare locală constituie un alt efort în direcţia menţionată anterior. Cele mai recente

abordări referitoare la aceste aspecte sunt prezentate în capitolul 4.

O direcţie importantă în cercetarea GP de data recentă se referă la construcţia unei baze

teoretice pentru modelarea acestor algoritmi (formularea unei descrieri matematice consistente a

comportamentului general al algoritmilor GP). Eforturile depuse ca răspuns la această provocare

se bazează pe lanţuri Markov, studiul convergenţei globale (în timp infinit), pe teoria schemelor,

etc (capitolul 5). Această lucrare propune mai multe contribuţii în domeniul teoretic, configurate

în mod special pentru cazul modelelor regresive, cum ar fi teoria schemelor pentru forme şi

dimensiuni variabile, prezentată în partea a III-a.

III. APLICAŢIILE PROGRAMĂRII GENETICE ÎN

IDENTIFICAREA SISTEMELOR NELINIARE

1. PROGRAMAREA GENETICĂ – UN INSTRUMENT EFICIENT ÎN IDENTIFICAREA

SISTEMELOR

În majoritatea problemelor reale de identificare, sistemul vizat e complex, dinamic,

neliniar şi afectat de zgomot, dificultăţi ce trebuie gestionate de instrumentul computaţional ales

pentru generarea modelului, la costuri acceptabile (consum redus de resurse fără afectarea

acurateţii soluţiei). Pentru ca modelele generate să fie fezabile (să respecte standardele de calitate

impuse şi să fie uşor de folosit de alte aplicaţii), problema de identificare e formulată în manieră

multiobiectiv.

Identificarea sistemelor neliniare poate fi realizată cu ajutorul instrumentelor polinomiale

(modele autoregresive cu intrări exogene – NARMAX, NARX, NOE – cunoscute drept

polinoame Kolmogorov-Gabor, modele bazate pe serii Volterra trunchiate/finite, reprezentări

polinomiale ale modelelor Hammerstein şi Wiener). Acestea oferă reprezentări intrare-ieşire ale

sistemului, constând în toate combinaţiile posibile de intrări şi ieşiri la diferite momente de timp.

Principalul avantaj al modelelor polinomiale este liniaritatea în parametri, ce permite calculul

coeficienţilor prin optimizare liniară (Fletcher, 2000). Totuşi, pentru o aproximare suficient de

bună a comportamentului sistemului, este necesară considerarea unui număr mare de regresori,

ce implică costuri computaţionale pe măsură (pentru stabilirea termenilor relevanţi, calculul

parametrilor, etc).

Folosirea tehnicilor evolutive (GP) în identificare prezintă avantajul lucrului în absenţa

informaţiilor apriorice cu privire la structura modelului, o trăsătură valoroasă în aplicaţii realiste,

unde astfel de informaţii sunt, de cele mai mute ori, inaccesibile. Daca modelele sunt generate în

concordanţă cu formalismul NLP – comun tuturor polinoamelor Kolmogorov-Gabor – numărul

şi configuraţia regresorilor implicaţi vor fi stabilite nesupervizat (Poli et al, 2008).

Algoritmii de identificare propuşi în cele ce urmează se în cadrează în cinci categorii:

proceduri de optimizare mono-obiectiv (încorporând construcţia exhaustivă a arborilor,

transformarea din forma brută în forma regresivă si hibridizarea cu descompunerea QR pentru

calculul parametrilor), algoritmi multiobiectiv (ce includ tehnici de grupare şi migraţie adaptivă

pentru calibrarea priorităţilor obiectivelor), algoritmi MOO elitişti (cu construcţie dinamică a

arhivei, generare dublu ramificată a indivizilor urmaşi şi reinserţie specială a copiilor), algoritmi

memetici fuzzy (conţinând un mecanism original de configurare a parametrilor funcţiilor de

apartenenţă şi un operator cpCO îmbunătăţit) şi algoritmis bazaţi pe teoria schemelor (ce

utilizează concepte noi precum seturi extinse, regresori atomici/recursivi/locali/globali, predicate

logice şi probabilităţi de tăiere/geneză/reparare, toate reunite în cadrul teoriei schemelor

regresive).

III. Aplicaţiile programării genetice în identificarea sistemelor neliniare 45

2. OPTIMIZARE MONO-OBIECTIV BAZATĂ PE GP PENTRU NSI

Eforturile timpurii ale autoarei legate de aplicarea şi îmbunătăţirea principiilor GP în

identificarea sistemelor neliniare au vizat implementarea unei platforme computaţionale robuste

care să ofere suport pentru reprezentarea şi procesarea structurilor regresive ierarhice. Pentru a

concentra cercetarea pe construcţia şi manipularea arborilor, schema de optimizare aplicată

implică un singur obiectiv, anume acurateţea modelelor.

Aspectele cheie ale algoritmului simplu obiectiv sugerat (engl. single objective

optimisation algorithm – SOO)6 constau în:

O procedură exhaustivă de construcţie a arborilor (engl. exhaustive tree building

procedure) ce utilizează toţi terminalii disponibili, inserând pe fiecare o singură dată

la poziţii pseudo-aleatoare ale structurii ierarhice;

Un mecanism de transformare ce reconfigurează arborii generaţi pseudo-aleator,

pentru a asigura compatibilitatea NLP, simultan cu păstrarea echivalenţei

matematice între arborele regresiv şi cel original;

Hibridizarea algoritmului evolutiv cu o procedură deterministă bazată pe

descompunere QRpentru calculul parametrilor modelului;

Implementarea unei versiuni specifice a operatorului de încrucişare, capabilă să

detecteze, la nivel rudimentar, subarborii similari din structura părinţilor.

Numele algoritmului propus reflectă cele două trăsături principale ale sale, acronimul

utilizat fiind SOO-EBRS-MEA (single objective optimisation – exhaustive tree building and

regressive support – memetic evolutionary algorithm). Natura memetică a instrumentului

computaţional sugerat se datorează hibridizării cu procedura deterministă QR. În cele ce

urmează, din considerente de simplitate, algoritmul va fi denumit EBRS. Algoritmul a fost

prezentat iniţial în (Patelli şi Ferariu, 2009c).

Înainte de derularea procesului efectiv de modelare, trebuie identificate intrările ui, i =

1..m, şi ieşirile yj, j = 1..n, ale sistemului vizat, împreună cu întârzierile maxime acceptate, nu şi

ny. Ulterior, este construit setul de terminali, x(k), unde k notează momentul curent de timp:

njminkykynkukukuk yjjuiii ..,..)},(,),(),(,),(),({)(x 1111 . (III.1)

Fiecare arbore din populaţia iniţială este construit prin inserţii repetate ale elementelor

setului x, conectate de noduri operator ai setului },{O . Cei doi operatori alcătuiesc setul

6 Termenul “mono” a fost înlocuit cu “single” în numele algoritmului pentru a evita confuzia datorată

faptului că “multiobjective” începe de asemenea cu litera “m”. În această lucrare, MOO semnifică optimizare

multiobiectiv, iar SOO înseamnă optimizare mono-obiectiv.


minimal suficient, necesar pentru construcţia modelelor NLP (II.1). De remarcat că seturile de

terminali şi operatori îndeplinesc condiţiile lui Koza de închidere şi suficienţă (Koza, 1998).

Construcţia exhaustivă a arborilor este un mecanism original sugerat de autoare, ce se

bazează pe următoarele trei reguli:

Toţi terminalii disponibili sunt incluşi, fiecare o singură dată, în individul construit.

Probabilitatea de inserţie a terminalilor este uşor mai ridicată decât cea de

inserţie a operatorilor.

Eventualele locuri rămase libere în arbore, după epuizarea terminalilor disponibili,

sunt ocupate cu noduri de tip constantă.

Prima regulă e menită să încurajeze o distribuţie uniformă a arborilor iniţiali peste spaţiul

de căutare, prin aceea că fiecare nou arbore reprezintă o altă combinaţie posibilă a terminalior

din set7. În acest mod, riscul de supra-inserţie a anumitor terminali, şi de neglijare a altora, este

eliminat. Incluzând fiecare terminal o singură dată, arborii nu conţin material genetic redundant,

deci resursele computaţionale ale algoritmului nu vor fi irosite pentru procesarea genelor

duplicat. Consecinţa directă a acestui aspect este aceea că unii arbori vor conţine locaţii vacante

după epuizarea terminalilor disponibili (unele noduri operator ar putea avea un descendent în loc

de doi, cum e matematic corect). Pentru a asigura validitatea matematică, fără a influenţa etapa

de evaluare (ieşirea funcţiei obiectiv să rămână aceeaşi), poziţiile vacante sunt completate cu

noduri constante (regula a treia) de valoare 0 (dacă predecesorul direct e un nod “+”), sau 1 (în

restul cazurilor). Conform celei de-a doua reguli, pentru a genera arbori compacţi, terminalii sunt

inseraţi cu o probabilitate uşor mai ridicată decât operatorii. Astfel, majoritatea arborilor din

populaţia iniţială vor necesita un număr redus de operatori pentru conectarea nodurilor terminal,

şi, în consecinţă, vor conţine mai puţine poziţii vacante, reducând numărul apelurilor funcţiei de

generare a constantelor.

Autoarea introduce conceptul de explozie a intronilor la iniţializare (engl. initialisation

intron explosion – IIE), folosit la apreciera cantităţii de material genetic redundant (introni)

existent în populaţia iniţială (numărul de noduri constantă). În acest context, autoarea defineşte

rangul IIE (engl. IIE-rank).

Definiţia III.1. În contextul evoluţiei arborilor compatibili NLP (considerând setul de

operatori },{O ), ce utilizează procedura de construcţie exhaustivă, IIE-rank(d) este

procentul de arbori din populaţia iniţială care conţin cu d noduri mai mult decât dimensiunea

structurii minimale (fără constante) necesară pentru codificarea aceluiaşi model.

7 Arborii pot conţine terminali duplicat la generaţii ulterioare, ca rezultat al transformării din forma brută în cea

regresivă şi al acţiunilor repetate ale operatorilor genetici.


Pentru a asigura o diversitate satisfăcatoare a arborilor populaţiei iniţiale, este necesar ca

unii indivizi să aibă structuri diferite de cea minimală, astfel e de dorit ca, pentru valori mici ale

lui d, IIE-rank(d) să returneze valori nenule. A doua regulă a procedurii de construcţie exhaustivă

e menită să asigure un echilibru între diversitatea populaţiei iniţiale şi evitarea IIE, prin

considerarea unui raport de 0.7/0.3 al probabilităţilor de inserţie a nodurilor terminal respectiv

operator. Procedura de construcţie exhaustivă bazată pe cele trei reguli enumerate mai sus

genrează, cel mai probabil, arbori cu valori scăzute ale IIE-rank(d), pentru valori mari ale lui d.

Suportul regresiv (compatibilitatea modelelor cu formalismul NLP) nu e garantat de

procedura de construcţie exhaustivă, adică forma poloneză a modelelor candidate nu e neapărat

regresivă (sumă de produse). Pentru a obţine compatibilitatea NLP, autoarea introduce un

mecanism de transformare regresivă (engl. raw to regressive – R2R), ce reconfigurează nodurile

din structura iniţială pentru a obţine o alta, echivalentă matematic cu prima, şi compatibilă NLP.

Procedura exploatează distributivitatea inmulţirii faţă de adunare si e ilustrată în Fig. III.1.

Datorită echivalenţei matematice între cele două versiuni ale arborelui, este păstrată distribuţia

soluţiilor în spaţiul de căutare – asigurată de procedura de construcţie exhaustivă.

Fig. III.1. Un arbore generat de procedura de construcţie exhaustivă (stânga) şi forma sa regresivă obţinută

prin aplicarea R2R (dreapta)

Justificarea aplicării transformării R2R constă în obţinerea de structuri liniare în

parametri, unde coeficienţii modelului pot fi uşor calculaţi în mod determinist. Autoarea

sugerează hibridizarea algoritmului evolutiv cu un modul bazat pe descompunere QR, destinat

rezolvării sistemelor liniare, pentru calculul rapid şi exact al parametrilor. Rezolvarea sistemului

liniar din (III.2), pentru fiecare arbore din populaţie, ar fi semnificativ mai costisitoare pentru

indivizi în forma brută, deoarece matricea sistemului ar fi mai dificil de extras.

)(

)(

)(

))(x())(x())(x(

))(x())(x())(x(

))(x())(x())(x(

py

y

y

c

c

c

pFpFpF

FFF

FFF

i

i

i

ir

i

i

irii

irii

irii

2

1222

111

2

1

21

21

21

nipi

ri

rpiiii ,,y;c;F,ycF 1 .

(III.2)

u(k) y(k-1)

u(k-1) u(k-2) y(k-2) u(k-2) y(k-2) u(k-1)

u(k) y(k-1) u(k-2) +

+

+ +


Matricea de regresie Fi conţine valori numerice pentru toţi regresorii r dintr-un arbore,

calculate pentru cele p date din setul de antrenare. Coeficienţii modelului (parametrii) sunt

stocaţi în vectorul ci, iar iy reprezintă vectorul asociat ieşirii cu numarul i a sistemului. Pentru

arbrele regresiv din Fig. III.1 (partea dreaptă), o linie din F1 conţine următorii termeni:

)()()( 111 kykukF , )()()( 2212 kykukF şi )()()( 2113 kukukF , unde k = 1..p este

momentul curent de timp (pentru simplitate, vectorul terminalilor, x, a fost omis din notaţie

pentru că este unic).

Versiunea îmbunătăţită a operatorului de încucişare propusă de autoare se bazează pe

un fenomen caracteristic tuturor abordărilor evolutive, deci deseori observat la rularea

algoritmului EBRS, anume propagarea intensă a subarborilor bine adaptaţi către sfârşitul

procesului de căutare. Această constatare îndreptăţeşte presupunerea că subarborii adaptaţi sunt

încurajaţi inerent să supravieţuiască în instanţe multiple, în special dupa scurgerea unui număr

reprezentativ de generaţii. Astfel, protejarea explicită a regresorilor frecvent întâlniţi în structura

cromozomilor ar putea îmbunătăţi exploatarea şi, implicit, creşte viteza de căutare. În acest

context, autoarea sugerează o metodă particularizată de selecţie a punctelor de tăiere, conform

căreia nodurile interne şi descendenţii rădăcinii regresorilor similari din structura părinţilor nu

sunt considerate eligibile. În această variantă, operatorul de încrucişare detectează doar regresorii

similari globali (cu rădăcina într-un descendent al unui nod “+”). O versiune mai performantă e

descrisă în capitolul 6, în contextule teoriei schemelor regresive.

Studiile experimentale (descrise în lucrarea extinsă) au vizat identificarea unor subsiteme

ale staţiei de evaporare din cadrul unei fabrici de zahăr. A fost pusă în evdientă capacitatea bună

de aproximare, pe setul de date de antrenare şi validare, a modelelor obţinute prin rularea

procedurii EBRS.

3. OPTIMIZARE MULTIOBIECTIV NON-ELITISTĂ BAZATĂ PE GP PENTRU NSI

Toate problemele realiste de identificare impun mai multe criterii de calitate asupra

modelelor generate, o situaţie ce implică o configurare multiobiectiv a algoritmului de căutare. În

controlul automat, cele mai importante trăsături ale unui model fezabil sunt acurateţea şi

parcimonia (compactitatea structurală). Altfel spus, un model cu aplicabilitate practică trebuie o

aproximare realistă şi compactă a sistemului real. Obiectivul legat de complexitate e necesar

datorită faptului că soluţiile cu structură simplă au şanse mai mari să manifeste o capacitate

crescută de generalizare (erori de aproximare mici pe setul de date de validare).

Algoritmul GP multiobiectiv sugerat în această lucrare foloseşte un criteriu de

complexitate compus (engl. complexity evaluation function – CF) în plus faţă de cel de


acurateţe (eroarea medie pătratică pe setul de antrenare). r

ii

yu

cnn

trMCF

11lg)(

măsoară complexitatea structurală la trei nivele, folosind informaţii despre numărul de terminali

t, numarul de regresori r si relevanţa parametrilor modelului ci. Principala provocare

întâmplinată la proiectarea unui EA MOO constă în cantitatea limitată de informaţii a priori

despre priorităţile obiectivelor de optimizare (în controlul automat, acurateţea e, de obicei, mai

importantă decât parcimonia). În aceste ipoteze, algoritmul de identificare trebuie să detecteze

automat un compromis viabil între criteriile de optimizare şi să dirijeze căutarea spre aria de

interes a frontului Pareto optimal, un proces cunoscut sub numele de articulare progresivă a

preferinţelor (combinarea procesului evolutiv cu mecanismul de decizie) (Coello Coello et al,

2007).

Pentru a îndeplini acest obiectiv, algoritmul MOO sugerat implementează mai multe

mecanisme inovatoare8:

O tehnică de grupare a populaţiei ce separă indivizii în două mulţimi, evoluate

diferit (SOO şi MOO). Graniţele (limitele) celor două mulţimi sunt calculate adaptiv

în funcţie de performanţele arborilor din populaţia curentă.

O schemă de migraţie adaptivă menită să crească dinamic presiunea de selecţie în

favoarea obiectivului de acurateţe, atribuind o oarecare importanţă şi complexităţii

modelelor. Rata migraţiei între grupuri dictează numărul exact de indivizi ce urmează

a fi interschimbaţi.

Denumirea procedurii propuse îi reflectă trăsăturile principale, având acronimul MOO-

PCAM-MEA (engl. multiobjective optimisation – population clustering and adaptive migration

– memetic evolutionary algorithm), şi va fi referită în cele ce urmează drept PCAM. Descrierea

algoritmului alături de studii experimentale variate a fost publicată în (Ferariu şi Patelli, 2009a),

(Ferariu şi Patelli, 2009b), (Ferariu şi Patelli, 2009c) şi (Patelli şi Ferariu, 2009b), (Patelli şi

Ferariu, 2009d), (Patelli şi Ferariu, 2009e).

Pentru a creşte presiunea de selecţie în favoarea criteriului de acurateţe, populaţia iniţială

e divizată în două grupuri de dimensiuni egale ce conţin indivizi selectaţi aleatoriu (în spaţiul

obiectivelor, cele două subpopulaţii nu ocupă arii complet disjuncte) (Fig. III.2). Primul grup de

indivizi, G1 este evoluat din perspectiva acurateţii iar al doilea, G2 e împărţit în două subdiviziuni

– CSOO, unde cromozomii sunt evaluaţi numai relativ la acurateţe, şi CMOO, unde calitatea

modelelor e apreciată atât din perspectiva acurateţii cât şi a compactităţii. CSOO şi CMOO sunt

separate de valorile medii ale SEF şi CF din G2. Separarea populaţiei în G1 şi G2 e efectuată o

8 Pe lângă îmbunătăţirile implementate pentru algoritmul SOO (capitolul anterior).


singură dată (la prima iteraţie a algoritmului), în timp ce CSOO şi CMOO sunt reconstruite la fiecare

generaţie prin reconfigurarea celor două valori medii ale obiectivelor de optimizare folosite.

Fig. III.2. Gruparea şi divizarea populaţiei la o generaţie dată

Subdiviziunea CSOO ocupă spaţiul din stânga jos al lui G1 (Fig. III.2), deci include, cel

mai probabil, un număr semnificativ de arbori nedominaţi fezabili. Evoluând acestă subdiviziune

numai conform acurateţii, presiunea de selecţie e crescută în favoarea indivizilor cu o capacitate

crescută de aproximare. La fiecare generaţie, după reconfigurarea limitelor dintre CSOO şi CMOO,

arborii cu structuri simple din cadrul CMOO al generaţiei anterioare vor fi incluşi în CSOO, dacă

sunt suficient de precişi. Astfel, presiunea de selecţie este crescută şi în favoarea obiectivului

complexitate, dar într-o măsură mai mică decât în cazul acurateţii.

Cele două subdiviziuni, CSOO şi CMOO, fac schimb de indivizi de la o generaţie la alta prin

retrasarea graniţelor. Grupurile G1 şi G2 schimbă cromozomi (cei mai precişi în cazul G1 şi cei

nedominaţi în cazul G2) prin migraţie, un alt mijloc de calibrare dinamică a presiunii de selecţie.

Numărul exact de arbori ce migrează dinspre o subpopulaţie spre cealaltă e determinat adaptiv,

fiind considerate trei praguri: r1 = 10%, r2 = 20% şi r3 = 25%. Dacă complexitatea medie în G1 e

mai mică decât cea a arborilor din G2, atunci mulţi dintre arborii simpli şi precişi evoluaţi SOO

vor fi incluşi în CSOO, cu probabilitate mare (Fig. III.2). Astfel, procentajul maxim (25%) din

arborii G1 vor migra înspre G2, în timp ce numai 10% vor parcurge drumul invers. Când

complexitătile medii în G1 şi G2 sunt comparabile, rata de migraţie în ambele direcţii este 20%.

Finalmente, daca arborii G1 sunt semnificativ mai complecşi decât cei din G2 (semn că obiectivul

complexitate nu a fost acentuat suficient), şansele lor de a fi incluşi în CSOO şi de a popula

regiunea de interes a frontului Pareto de ordin întâi sunt mici. Numai 10% din indivizii G1 vor

migra înspre G2, în timp ce 25% din arborii simpli, însă de acurateţe mai scăzută vor parcurge

drumul invers.

CMOO

SEF

CF CFavg

SEFavg CSOO

G2

G1


Frontul Pareto de ordin întâi generat de PCAM e comparat cu cel generat de o procedură

MOO fără nici una din îmbunătăţirile sugerate, în contextul subsecţiunii “steam” a fabricii de

zahăr. În lucrarea extinsă sunt comentate diferenţele legate de distribuţia soluţiilor pe frontul

Pareto (PCAM se concentrează pe zona fezabilă, algoritmul de referinţă nu reuşeste acest lucru)

şi de acurateţea lor (PCAM generează un front Pareto mai apropiat de cel real).

4. OPTIMIZARE MULTIOBIECTIV ELITISTĂ BAZATĂ PE GP PENTRU NSI

În cadrul procesului evolutiv, este posibil ca arborii unei anumite generaţii să fie mai slab

adaptaţi decât cei ai generaţiei anterioare. Pentru a diminua acest risc, autoarea propune

următoarele mecanisme computaţionale originale, implementate în context elitist:

O rază de proximitate calculată dinamic menită să incurajeze distribuţia uniformă a

soluţiilor nedominate (diversitatea elitelor), spre deosebire de raza de proximitate

configurată static propusă în (Deb, 2001). Prin actualizarea parametrului după

fiecare modificare a arhivei, este încurajată generarea de noi soluţii în zonele slab

populate ale frontului Pareto.

O procedură de grupare a elitelor orientată înspre calculul unui bonus de fitness care

să răsplătească indivizii cei mai apropiaţi de zona fezabilă a frontului Pareto.

Un proces de generare a soluţiilor urmaş desfăşurat pe două fire de execuţie9,

unde atât elitele cât şi indivizii obişnuiţi produc copii. Cele două seturi de arbori

urmaşi sunt reunite pentru a creşte presiunea de selecţie în acelaşi timp cu păstrarea

diversităţii.

O tehnică de reînnoire a populaţiei constând în injecţia imaginii unui set nedominat

de la o generaţie anterioară în cea curentă. Procedura previne pierderea diversităţii şi

e aplicată de câte ori gradul de similitudine între arbori creşte peste un anumit nivel.

Aceste mecanisme sunt incluse, în perechi (primele două şi ultimele două), în două proceduri

evolutive elitiste. Primul (engl. elitist multiobjective optimisation – dynamic crowding and elite

clustering – memetic evolutionary algorithm – EMO-DCEC-MEA), va fi referit în cele ce

urmează cu acronimul DCEC – vezi şi (Patelli şi Ferariu, 2009a). Al doilea algoritm (engl. elitist

multiobjective optimisation – similarity analysis and diversity preservation – memetic

evolutionary algorithm – EMO-SADP-MEA), sau pe scurt SADP a fost prima oară prezentat în

(Patelli şi Ferariu, 2010a), (Patelli şi Ferariu, 2010e).

9 Cele două procese de generare a soluţiilor urmaşi sunt conceptual paralele, din punct de vedere al

suportului software, execuţia lor fiind secvenţială (pe un singur fir de execuţie). Scopul acestei tehnici este creşterea

presiunii de selecţie, nu reducerea timpului de calcul.


Pentru a creşte autonomia procesului de căutare, autoarea propune o metodă automată

pentru configurarea , prin recalcularea acesteia după fiecare actualizare a arhivei (Fig.

III.3c):

2||

,

),(

E

jiji

ji

C

eed

. (III.3)

În (III.3), ei, ej sunt indivizi elite, |E| reprezintă cardinalul arhivei, d notează distanţa

euclidiană iar 2||EC simbolizează numărul combinaţiilor de câte două elite din arhivă. Raza de

proximitate dată de (III.3) reflectă distanţa relativă dintre elite, astfel riscul unei alegeri

neadecvate a pasului de discretizare (prea mic – Fig. III.3a sau prea mare – Fig. III.3b) este

evitat, iar distribuţia uniformă a elitelor în zona fezabilă a frontului Pareto e încurajată în mod

corespunzător.

a b c

Fig. III.3. Moduri diferite de a calcula raza de proximitate - cu pas de discretizare prestabilit: prea mic

(a), prea mare (b) – configurată dinamic (c)

Pentru a concentra căutarea pe zonele fezabile, autoarea sugerează creşterea suplimentară

a fitnessului soluţiilor din apropierea acesteia. În acest scop, sunt calculate performanţele medii

ale elementelor arhivei, relativ la acurateţe şi complexitate. Grafic (Fig. III.4), valorile obţinute

reprezintă coordonatele unui punct din spaţiul obiectivelor ce poate fi atribuit unui individ “fals”,

D. Media distanţelor euclidiene dintre toate elitele şi D reprezintă valoarea bonusului adăugat la

fitnessul10

indivizilor obişnuiţi situaţi în regiunea fezabilă.

10

Fitnessul de bază, la care se adaugă bonusul, e calculat folosind abordarea lui Deb (engl. sharing

fitness)cu diferenţa ca e configurat dinamic.

SEF

CF

SEF

CF

SEF

CF


a b

Fig. III.4. Asignarea bonificaţiilor de fitness prin gruparea elitelor –calculul bonusului în interiorul arhivei

(a) – asignarea bonusului; când originalul nu poate fi determinat, bonusul e acordat celui mai apropiat individ

(b)

În ceea ce priveşte explorarea, elitele sunt entităţi inactive, deoarece nu participă la

producerea de urmaşi. Autoarea introduce conceptul de elite “active”, referitor la o arhivă de

cromozomi eligibili pentru a deveni părinţi. Elitele fezabile din arhiva actualizată (cadranul

stânga jos din Fig. III.4, relativ la D) sunt supuse unui proces de selecţie, pentru stabilirea unui

set de părinţi. Operatorii genetici (cpCO dependentă de context şi mutaţia dublu impact) produc

indivizi copii ce sunt apoi reuniţi cu cei generaţi în cadrul populaţiei obişnuite.

Cum arhivele sunt duplicate ale indivizilor nedominaţi obişnuiţi, există şansa ca unii

copii elitişti să fie asemănători cu cei obişnuiţi, deci includerea lor în setul reunit ar fi

redundantă. Pentru a preveni această situaţie urmaşii elitelor şi cei ai indivizilor obişnuiţi sunt

analizaţi structural, pentru a detecta eventualele similitudini, conform urmatoarei formule:

)()(,),(,

),(},{

)()(,),(},{\}{

cSEFeSEFcedneschimbat

ceeC

cSEFeSEFcedceC

C

cc

cc

ccc

(III.4)

Toţi copiii c ai populaţiei obişnuite sunt incluşi în setul reunit, C. Fiecare urmaş elită ec e

analizat prin calculul distanţei euclidiene d(ec, c) valoarea obţinută fiind apoi comparată cu una

de prag , unde c e elementul din C cel mai apropiat de ec. Daca cei doi indivizi comparaţi sunt

apropiaţi în spaţiul obiectivelor, şi ec e mai exact decât c, atunci ec îl înlocuieşte pe c în C. Dacă

d(ec, c) e suficient de mare, elita e inserată în C, fără eliminarea nici unui element existent.

În ciuda acestor precauţii, diversitatea populaţiei poate descreşte de-a lungul generaţiilor.

Pentru prevenirea acestui risc, setul nedominat al fiecărei generaţii e stocat separat. Acest lucru e

necesar deoarece arhiva generală e actualizată mereu, deci imaginile fiecărui front Pareto de

ordin întâi din istoria algoritmului sunt greu de recuperat. Dacă dispersia distanţelor euclidiene

între oricare doi indivizi scade continuu mai mult de dc generaţii, atunci una din imaginile

seturilor nedominate din istoria algoritmului e injectată în populaţia curentă. Procedând astfel,

SEF

CF

D

SEF

CF

?


diversitatea poate fi restabilită fără modificarea semnificativă a calităţii medii a cromozomilor

(caz ce nu ar putea fi evitat daca materialul genetic injectat ar fi generat aleator).

Lucrarea extinsă conţine o comparaţie detaliată între performanţele algoritmilor propuşi

de autoare. De asemenea, procedurile PCAM şi DCEC sunt comparate cu alte metode frecvent

utilizate de identificare (bazate pe reţele neuronale şi structuri NLP maximale), superioritatea

primelor fiind astfel demonstrată în contextul experimentului propus.

5. HIBRIZI GP-FUZZY PENTRU NSI MULTIOBIECTIV

Tehnicile evolutive implementate în cadrul algoritmilor descrişi anterior stabilesc

echilibrul între exploatare şi explorare la nivel macroscopic, privind arborii ca entităţi de sine

stătătoare. Calitatea unui individ este însă influenţată de componentele sale, anume blocurile

structural (engl. building blocks – BB). Astfel, supravieţuirea trăsăturilor adaptate poate fi

încurajată la nivel microscopic, prin promovarea blocurilor structurale în locul arborilor ca

întregi. În acest context, mecanismele originale propuse sunt următoarele:

O procedură de căutare a regresorilor comuni (engl. common regressor search –

CRS) ce identifică blocurile structurale din componenţa mai multor arbori nedominaţi

ai generaţiei curente. Cum arborii investigaţi sunt cei mai buni din populaţie,

componentele lor prezintă şanse crescute de a fi bine adaptate.

Un modul fuzzy (engl. fuzzy module – FM) cu parametri calculaţi dinamic,

configurat special pentru estimarea gradului de adaptare a regresorilor.

Reconfigurarea mecanismului de selecţie a punctelor de tăiere, pentru a evita

distrugerea BB de către încrucişare (engl. regressor encapsulation11

), ce duce la

obţinerea unei versiuni îmbunătăţite a operatorului cpCO dependent de context,

descris în 2 (care protejează nediferenţiat toate substructurile similare).

Primul hibrid propus (engl. elitist multiobjective optimisation – similarity analysis and

fuzzy encapsulation – memetic evolutionary algorithm – EMO-SAFE-MEA), pe scurt SAFE, a

fost introdus în (Patelli şi Ferariu, 2010c). Al doilea algoritm (engl. elitist multiobjective

optimisation – similarity analysis şi dynamic encapsulation – memetic evolutionary algorithm –

EMO-SADE-MEA), pe scurt SADE, e descris în (Patelli şi Ferariu, 2010d) şi (Patelli şi Ferariu,

2010e).

Modulul fuzzy oferă o măsură cantitativă a calităţii regresorilor (a capacităţii lor de a

creşte performanţele indivizilor gazdă) identificaţi de CRS, măsură exprimată prin AEL (engl.

11 Cu toate că, la nivel conceptual, încapsularea regresorilor e similar cu acţiunea operatorului de

încapsulare introdus de (Koza, 1998), procedura sugerată în această lucrare e original, bazată pe o logică total

diferită.


adaptation estimation label). AEL este un număr real subunitar ce ia valori dintr-un set discret şi

reprezintă echivalentul microscopic al fitnessului calculat pentru indivizi. FM are două intrări

(variabile fuzzy) prima fiind dispersia, var(SEF), a valorilor SEF calculate pentru arborii

nedominaţi curenţi ce conţin macar o instanţa a regresorului în discuţie R. A doua intrare este

dispersia, var(CF), a valorilor CF calculate pentru acelaşi set de arbori. Clasele şi funcţiile de

apartenenţă asociate celor două variabile fuzzy sunt ilustrate în Fig. III.5.

Fig. III.5. Variabilele fuzzy, clasele şi funcţiile de apartenenţă ale MF

Variabila fuzzy var(SEF) e mică dacă indivizii nedominaţi ce-l conţin pe R au valori

asemănătoare ale erorii de aproximare. Acest lucru arată că R este, cel mai probabil, un bloc util

(toţi indivizii gazdă sunt exacţi)12

. Dimpotrivă, dacă var(SEF) e ridicată, arborii nedominaţi au

grade diferite de adaptare, deci influenţa lui R e mică. Variabila fuzzy var(CF) poate avea valori

convenabile sau ridicate, distincţie menită să permită acordarea unui AEL mai mare blocurilor

compacte.

Logica internă a FM e dată de un set de 6 reguli fuzzy (III.5). Intuitiv, FM asignează

eticheta 1 (grad maxim de adaptare) regresorilor compacţi din structura unor arbori cu acurateţe

asemănătoare, conform primei reguli. Regresorii de dimensiune ridicată, aparţinând unor

cromozomi cu nivele diferite de acurateţe sunt etichetaţi cu valoarea 0, adică au, cel mai

probabil, o influenţă nesemnificativă.

IF var(SEF) IS small AND var(CF) IS convenient THEN AEL = 1

IF var(SEF) IS medium AND var(CF) IS convenient THEN AEL = 0.8

IF var(SEF) IS high AND var(CF) IS convenient THEN AEL = 0

IF var(SEF) IS small AND var(CF) IS large THEN AEL = 0.9

IF var(SEF) IS medium AND var(CF) IS large THEN AEL = 0.5

IF var(SEF) IS high AND var(CF) IS large THEN AEL = 0.

(III.5)

Algoritmii SAFE şi SADE pot detecta doar regresorii comuni globali, o limitare rezolvată

de procedura propusă în capitolul 6. Pentru definirea completă a celor 5 funcţii de apartnenţă,

coordonatele vi, i = 1..6 din Fig. III.5 sunt configurate adaptiv (detalii în lucrarea extinsă).

12 Cazul în care var(SEF) e mică şi avg(SEF) e mare corespunde situaţiei în care arborii nedominaţi sunt

prost adaptaţi, ceea ce e puţin probabil. Asatfel, FM nu alocă resurse computaţionalepentru calculul avg(SEF), unde

avg (engl average) denumeşte valoarea aşteptată/media, ce e implicit considerată a fi scăzută.

v1 v2 v3 v4 v5 v6 var(SEF)

smallMF

var(CF)

mediumMF highMF convenientMF largeMF


Încapsularea regresorului TkiR , (vezi 6 pentru detalii despre notaţie) constă în scăderea

probabilităţii p(i|T) de selecţie a unui nod interior al său ca punct de tăiere, de către operatorul de

încrucişare. Iniţial, nTip /)|( 1 , unde n notează numărul nodurilor eligibile (terminali si noduri

“*”). Noile probabilităţi, mai mici, reflectă calitatea regresorului (AEL):

801

.)(,,)(

)|( ,,

max

, Tk

Tk

Tk

enc RAELRiNN

RAELTip .

(III.6)

În (III.6), )|( Tipenc reprezintă probabilitatea de selecţie asociată nodului i, după

procesul de încapsulare, iar NNmax notează numărul maxim de noduri eligibile (terminali şi

noduri „*”) conţinute de un părinte dintre cei consideraţi. Probabilităţile de selecţie asociate

nodurilor ce aparţin regresorilor neîncapsulaţi sunt reconfigurate astfel încât }{\

)|(Ti

enc Tip 1 .

Astfel,

80

1

80

8000

00

.)(,,

)|()(

)|( ,,

.

.),

(,,

,,

Tk

Tk

Tj

RAELTj

R

Tjenc

Tj

enc RAELRiNN

TRlpRRS

Tip

(III.7)

unde RS(TjR 0, ) returnează dimensiunea regresorului primit la intrare, iar NN<0.8 este numărul

nodurilor eligibile din regresorii neîncapsulaţi ai arborelui T.

Fronturile Pareto finale generate de SADE şi SADP sunt comparate cu cel obţinut prin

rularea algoritmului de referinţă, rezultatele fiind comentate în lucrarea extinsă. De asemenea,

cei doi algoritmi sunt analizaţi în contextul unor experimente variate (diferite configuraţii ale

parametrilor algoritmilor, studiul performanţelor modelelor pe setul de date de validare, etc).

6. TEORIA SCHEMELOR REGRESIVE ÎN NSI MULTIOBIECTIV

STRM (engl. schema theory for regressive models) este un instrument teoretic ce oferă

valori nete pentru numărul aşteptat de instanţe ale unui regresor la generaţia următoare, folosind

doar informaţii disponibile la cea curentă. Astfel, suportul STRM poate fi utilizat pentru

construcţia unui model al algoritmului evolutiv, datorită informaţiilor oferite cu privire la

dinamica componentelor structurale.

Principalele inovaţii implicate de utilizarea STRM ca instrument teoretic sunt:

Introducerea unui nou concept, anume schema de dimensiune si formă variabile, ce

face posibilă monitorizarea regresorilor ierarhici cu orice configuraţie; matematic,

schemele sunt reprezentate prin seturi extinse, un nou mod de a descrie regresori fără

a include informaţii cu privire la poziţia nodurilor lor interioare;


O nouă taxonomie a regresorilor pentru o mai bună identificare a acestora în

structura indivizilor gazdă;

Teoreme demonstrate riguros pentru calculul numului aşteptat de instanţe de

regresori bine adaptaţi în generaţia următoare.

Algoritmii evolutivi sugeraţi în acest capitol beneficiază de avantajele STRM în moduri

diferite. Aplicaţiile practice ale acestui instrument teoretic constau în:

O metodă originală pentru monitorizarea ratelor de supravieţuire asociate regresorilor

încapsulaţi;

Utilizarea STRM ca tehnică de căutare locală peste spaţiul tuturor arborilor urmaşi

posibili pentru a determina configuraţia optimă de puncte de tăiere;

Extensia STRM-LS pentru o combinaţie de operatori genetici, anume cpCO şi

mutaţia clasică.

Aplicaţiile practice ale STRM enumerate mai sus sunt reprezentate de trei versiuni ale

algoritmului FCE-STRM-MEA (engl. fuzzy controlled encapsulation – schema theory for

regressive models – memetic evolutionary algorithm).

Toate cele trei versiuni ale algoritmului FCE-STRM-MEA sunt hibrizi, construiţi drept

combinaţii între instrumentele STRM şi logica fuzzy. Trăsătura lor comună e utilizarea unui

modul fuzzy în aprecierea fitnessului microscopic (al blocurilor structurale). Diferenţa majoră

constă în modul în care FM interacţionează cu modulul STRM. Astfel, FCE-STRM-MEA I

rulează FM pentru toţi regresorii identificaţi de CRS, întocmai ca SAFE şi SADE, însă fără adiţii

macroscopice. Modulul STRM e folosit pentru monitorizarea (în sensul confirmării teoretice)

eficienţei încapsulării. Totuşi, estimările oferite de STRM nu sunt incluse în logica FM, multe

BB fiind încapsulate redundant. FCE-STRM-MEA II rulează STRM imediat după utilizarea FM.

Iesirea STRM (probabilităţile de transmisie a BB) e folosită pentru identificarea blocurilor cu

şanse inerente de supravieţuire mici. Numai aceştia vor fi încapsulaţi, economisind astfel resurse

computaţionale. A treia versiune, FCE-STRM-MEA III, se bazează pe aceeaşi logică dar

consideră şi operatorul de mutaţie în faza de producere a soluţiilor urmaşi (FCE-STRM-MEA II

lucrează doar cu operatorul de încrucişare).

Componenta formală e comună tuturor celor trei versiuni ale algoritmului FCE-STRM-

MEA. Dată fiind natura recursivă a structurilor ierarhice, autoarea propune notaţia TkiR , ca

permite o definiţie flexibilă a unui regresor, relativ la oricare din nodurile sale interne i. În Fig.

III.6, subarborele cu rădăcina în nodul 4 din T1 poate fi notat în 5 moduri 104

TR

, = 115

TR

, = 116

TR

,

= 127

TR

, = 128

TR

, , unde k reprezintă numărul de nivele ale arborelui între rădăcina lui R şi nodul i.


Fig. III.6. Arbori ce conţin diferite tipuri de regresori ierarhici

Considerând relaţiile structurale dintre regresori, autoarea propune clasificarea lor

înregresori atomici ( 107

TR

,), adică terminali, şi recursivi ( 2

06T

R,

= 218

TR

,= 2

17T

R,

, 202

TR

,= 2

28T

R,

), ce

reprezintă combinaţii de alţi regresori (atomici sau recursivi). Relativ la poziţia lor în arbore,

regressors pot fi locali ( 206

TR

,) – situaţi în interiorul altui regresor – sau globali ( 2

02T

R,

, 109

TR

,) – cu

rădăcina într-un descendent direct al unui nod „+” sau în rădăcina arborelui.

Un set extins descrie un regresor TkiR , prin intermediul terminalilor săi (nume şi număr

de apariţii), fără a conţine informaţii despre poziţia nodurilor:

},,x/),({)( , jiptsssvspRS jiiiiiT

ki . Vectorul x e dat de (III.1), iar perechile pi = (si,

vi) conţin numărul de apariţii, vi, ale fiecărui terminal unic, si, în structura T

kiR , . Setul extins

asociat lui 109

TR

, este )}),((),),((),),({()(,

111211109

kykukuRST

, ce îl descrie de asemenea şi

pe 209

TR

,.

Componenta estimativă pentru monitorizare se bazează pe ipoteza ca propagarea unei

scheme în generaţia viitoare se face prin transfer direct sau prin combinarea unor subarbori

convenabil selctaţi în structura părinţilor. Astfel, probabilitatea de transmisie, ),( tH , a schemei

H, calculată la generaţia t, sub acţiunea operatorului de încrucişare, este:

),(),(),( tHtHtH joinpres , (III.8)

unde ),( tHpres reprezintă efectul de transfer direct – presupunând că unul din părinţi conţine o

instanţă a schemei H care e pasată unuia dintre indivizii urmaşi, fără modificări structurale, iar

),( tHjoin se referă la efectul de combinare. Dacă unul din părinţi conţine mai multe instanţe

ale schemei vizate, probabilitatea de transmisie e calculată relativ la oricare dintre ele (dar numai

u(k)

u(k-1)

u(k-1) y(k-1)

u(k-1) y(k-1)

u(k-2)

+

u(k) u(k-1) y(k-1) u(k) y(k-1) u(k-1)

+

u(k-2)

1

2

3 4

5 6

7 8

9

10

11 12

13 1

2

3

4 5

6

7 8

9

10

11 12

13

T1

T2


una). În acest context, (III.8) reprezintă probabilitatea de a transmite cel puţin o instanţă a

schemei. Astfel, predictorii (numărul aşteptat de instanţe ale schemei în generaţia următoare) ce

ar putea fi construiţi pe baza (III.8) reprezintă limite inferioare.

Teorema III.1. Probabilitatea, ),( tHpres , de transmisie a cel puţin o instanţa a schemei

H, prin transfer direct, sub acţiunea cpCO este :

}{\}{\

),|(),(),(rHTiHT

pres tTiptTptH , (III.9)

unde T este părintele curent din populaţie, ),( tTp reprezintă probabilitatea ca T să fie selectat ca

părinte, ),|( tTip notează probabilitatea de selecţie a nodului i, r este rădăcina schemei H, iar t

simbolizează generaţia curentă.

Teorema III.2. Probabilitatea, ),( tHjoin , de transmisie a cel puţin o instanţa a schemei

H, prin recombinare (efect “join”), sub acţiunea cpCO este:

1

20

10

1

21

2121

21k

Tj

Ti

T

ki

TjTiTT

join HSRSRSRStTjptTiptTptTptH ))()()(\)((),|(),|(),(),(),( ,,,

}{\}{\,

, (III.10)

unde T1 şi T2 sunt părinţii curenţi, ),|(),,|( tTjptTip 21 reprezintă probabilităţile de selecţie ale

punctelor de tăiere i şi j, )( ,T

kiRS semnifică setul extins asociat regresorului Tki

R,

, () este un

predicat ce returnează valoarea de adevăr a expresiei primite ca argument iar t simbolizează

generaţia curentă.

Demonstraţiile tuturor teoremelor din această lucrare sunt disponibile în versiunea

extinsă.

Componenta estimativă pentru STRM aplicată ca LS porneşte de la formularea unor

predicate logice ce descriu situaţiile de geneză/distrugere a unei scheme prin aplicarea cpCO şi a

mutaţiei.

O schemă H este distrusă de încrucişare dacă punctul de tăiere/punctul vizat de mutaţie, i,

e interior lui H, situaţie în care predicatul )(icut e adevărat:

1kRSHSik

Tkicut ,))()(()( , (III.11)

Geneza unei noi instanţe a schemei H e descrisă de predicate diferite, câte unul pentru

fiecare din cei doi operatori. În cazul cpCO, formarea unei noi instanţe a H e dată de validarea

predicatului ),( jijoin :

121100 kRSRSRSHSji

k

Tj

Ti

Tkijoin ,))()(\)()((),(

,,,. (III.12)


În cazul aplicării mutaţiei orientată pe terminali, geneza unei noi instanţe a H e posibilă

dacă părintele direct conţine o schemă “defectă”, care diferă de cea corectă printr-un singur

terminal. Dacă acel terminal, wi, e înlocuit de mutaţie cu elementul corect, xj (care “repară”

schema), atunci predicatul ),( jirepair e validat:

111 kxwRSHSjik

jiT

kirepair ,)),(),(\)()((),(,

. (III.13)

Considerând un bazin de reproducere cu N părinţi organizaţi în N/2 perechi, fiecare

pereche de copii poate conţine o instanţă mai puţin, acelaşi număr de instanţe, sau o instanţă în

plus relativ la cei doi părinţi. Considerând cpCO si mutaţia orientată pe terminali probabilităţile

asociate celor trei scenarii menţionate mai sus sunt:

),(),(),( tHptHptH mtmtcoco111 ,

),(),(),( tHptHptH mtmtcoco000 ,

),(),(),( tHptHptH mtmtcoco111 .

(III.14)

În (III.14), pco şi pmt sunt probabilităţile de aplicare a celor doi operatori genetici.

Probabilităţile de creştere/conservare/descreştere cu o unitate a numărului de instanţe ale H,

relativ la ambii părinţi, şi considerând doar cpCO sunt:

21

2

1

21211

TTjoincut

TjTi

co jiitTjptTiptTptTptH,

}{\}{\

),()(),|(),|(),(),(),( ,

21

2

1

21210

TTjoincutjoincut

TjTi

co jiijiitTjptTiptTptTptH,

}{\}{\

)),()(),()((),|(),|(),(),(),(

),()(),|(),|(),(),(),(,

}{\}{\

jiitTjptTiptTptTptH joinTT

cut

TjTi

co

21

2

1

21211 ,

(III.15)

unde )(icut şi ),( jijoin sunt daţi de (III.11) şi (III.12).

În cazul mutaţiei, probabilităţile de mai sus se reformulează astfel:

jxTrepaircut

jxTi

jmt jiitxptTiptTptH,

x}{\

),()(),x|(),|(),(),(1 ,

jxTrepaircutrepaircut

jxTi

jmt jiijiitxptTiptTptH,

x}{\

)),()(),()((),x|(),|(),(),(0 ,

),()(),x|(),|(),(),(,

x}{\

jiitxptTiptTptH repairjxT

cut

jxTi

jmt1 ,

(III.16)

unde )(icut şi ),( jirepair sunt daţi de (III.11) şi (III.13).


Calculând cele trei probabilităţi din (III.14), algoritmul poate determina şansele de

supravieţuire ale unui regresor bine adaptat. Astfel, încapsularea e aplicată numai acelor BB cu

AEL > 0.8, 201 .),( tH şi 801 .),( tH . Regresorii cu AEL peste 0.8, care au şanse

inerente de supravieţuire mari, nu necesită protecţie prin încapsulare, care ar reprezenta o risipă

de resurse.

În cazul mutaţiei, probabilităţile de selecţie a punctelor de tăiere sunt reconfigurate diferit

decât în cazul cpCO, deoarece mutaţia vizează doar terminali, în timp ce cpCO poate acţiona şi

asupra terminalilor şi a nodurilor “*”. Formulele de reconfigurare în urma încapsulării pentru

mutaţia orientată pe terminali sunt:

801

.)(,,)(

)|( ,,

max

, Tk

Tki

Tk

enc RAELRiNZ

RAELTip

80

1

80

8000

00

.)(,

)|()(

)|( ,

.

.),

(,,

,,

Tk

Tj

RAELTj

R

Tjenc

Tj

enc RAELNZ

TRwpRTS

Tip

(III.17)

unde NZmax reprezintă numul maxim de terminali, conţinuţi de regresori încapsulaţi, din

interiorul unui părinte, NZ<0.8 notează numărul terminalilor din regresorii neîncapsulaţi ai

arborelui T, iar TS( Tj

R0,

) returnează numărul de terminali ai regresorului primit ca argument.

Rezultatele din (III.18) au fost formulate considerând o singură pereche de părinţi,

formată din T1, conţinând n noduri eligibile, şi T2, ce nu conţine regresori încapsulaţi (pentru ca

p(j|T2) să fie acelaşi pentru co şi encco , ) :

),())((

),(max

, tHNN

HAELntH coencco

11 1,

),(

))(

(

),(max

, tHhn

NN

HAELhn

tH co

qq

qq

encco11

11

.

(III.18)

Considerând aceleaşi presupuneri ca mai sus, probabilităţile de distrugere/geneză în cazul

mutaţiei rezultă substituind (III.17) în (III.16):

),())((

),(max

, tHNZ

HAELztH mtencmt

11 1,

),(

))(

(

),( max, tH

wz

NZ

HAELwz

tH mt

qq

qq

encmt11

11

,

(III.19)


unde z e numărul de terminali din T1 iar wq reprezintă numărul de terminali din al q-lea regresor

încapsulat al T1.

Componenta predictivă se bazează pe exprimarea numărului aşteptat de regresori ce

instanţiază schema H, din structura celor doi arbori copii, considerând toate cele trei scenarii

posibile:

)),()(,(),(),()),()(,()],([ 111 101 tHFtHtHFtHtHFtHtHFE . (III.20)

În (III.20), ),( tH1 , ),( tH0 , ),( tH1 sunt date de (III.14), F(H,t+1) este numărul

apariţiilor lui H (frecvenţa lui H) în cei doi copii, la generaţia t+1, iar F(H,t) reprezintă numărul

de instanţe ale H din structura celor doi părinţi la generaţia t. În prezenţa încapsulării, numărul

aşteptat de instanţe ale schemei devine:

)),()(,(),(),()),()(,()],([ 111 101 tHFtHtHFtHtHFtHtHFE encencencenc , (III.21)

unde ),( tHenc1 , ),( tHenc

0 , ),( tHenc1 se obţin din (III.14) prin adăugarea indicelui enc

fiecărui termen .

Diferenţa dintre cele două cantităţi de mai sus, (III.20) scăzută din (III.21), este:

)),(),((),(),()],([)],([ tHtHtHtHtHFEtHFE encencenc111111 =

)),(),(),(),(( ,, tHtHtHtHp coenccocoenccoco1111 +

)),(),(),(),(( ,, tHtHtHtHp mtencmtmtencmtmt1111

.

(III.22)

Semnul celor doi termeni din (III.22), ),(),(),(),( ,, tHtHtHtH coenccocoencco1111 şi

),(),(, tHtH mtencmt11 ),(),(, tHtH mtencmt

11 , se rezumă la evaluarea următoarelor cantităţi:

max

maxmaxmax )(),(

)()(

),(NN

HnAELnNNtH

hn

HAELhNN

n

NN

nh

tHD

qq

qqq

qq

co11

1

max

maxmaxmax )(),(

)()(

),(NZ

HnAELzNZtH

hn

HAELwNZ

z

NZ

zw

tHD mt

qq

qqq

qq

mtmt11

1

.

(III.23)

Numărul de noduri din T1 este evident mai mic decât numărul de noduri din cel mai mare

individ din populaţie, astfel că nNNmax . Ieşirea FM, AEL(H) e o valoare pozitivă, iar

dimensiunea cumulată a tuturor regresorilr încapsulaţi din T1 e mai mică decat numărul total de

noduri din T1, adică q

q nh . Termenul Dmt este de asemnea pozitiv, în urma unui raţionament


similar. Concluzia trasă în urma analizei rezultatului (III.23) este aceea că, în prezenţa

încapsulării, numărul aşteptat de instanţe ale unei scheme din structura celor doi copii

rezultaţi e mai mare decât cel al părinţilor, considerând ca părintele indirect nu cnţine

regresori încapsulaţi. Relativ la întreaga populaţie, în ipotezele de mai sus, se obţine:

21 TTmtmtcoco DpDp

,

, (III.24)

o valoare de asemena pozitivă, conform (III.23).

În figura de mai jos, frontul Pareto final generat de FCE-STRM-MEA III e comparat cu

cele obţinute prin rularea SADP şi respectiv a algoritmului de referinţă. O analiză experimentală

extinsă, care confirmă rezultatele teoretice trecute în revistă mai sus, e disponibilă în lucrarea

extinsă.

6 8 10 12 14 16 18 200

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8Algorithms' performances

complexity[CF]

accura

cy[M

SE

F]

RFRC 1st order PF

SADP 1st order PF

STRM 1st order PF

Fig. III.7. Fronturile nedominate finale generate de SADP şi STRM

TABLOUL CONTRIBUŢIILOR ŞI CONCLUZII

GENERALE

Lucrarea de faţă descrie contribuţiile originale ale autoarei, atât cele de interes general

pentru programarea genetică, cât si cele cu referire directă la problema identificării sistemelor

neliniare folosind GP. Noutăţile propuse pot fi organizate în trei categorii, anume contribuţii

algoritmice, teoretice şi experimentale, detaliate în cele ce urmează.

1. CONTRIBUŢII ALGORITMICE

Conceptele originale implementate pentru îmbunătăţirea instrumentelor de identificare

bazate pe GP se încadrează în trei categorii: cele folosite pentru eficientizarea componentelor

de bază ale algoritmului, tehnici legate de aspecte MOO şi proceduri pentru exploatarea

explicită a BB. Prima categorie constă în:

a. Procedura exhaustivă de construcţie a arborilor

Arborii sunt construiţi folosind toţi terminalii disponibili, conform unui algoritm bazat pe trei

reguli (Patelli şi Ferariu, 2009c). Astfel, populaţia iniţială va conţine indivizi echilibraţi

structural, ce codifică modele potenţiale corecte matematic (formal) şi cu o bună distribuţie

peste spaţiul de căutare.

b. Transformarea structurală a arborilor generaţi exhaustiv în arbori regresivi

Pentru compatibilitate NLP (şi aplicare facilă a procedurii QR), arborii construiţi cu

algoritmul exhaustiv sunt reconfiguraţi (Patelli şi Ferariu, 2009c), astfel încât structurile

obţinute să fie regressive, şi echivalente matematic cu originalele.

c. Hibridizarea cu procedura de descompunere QR pentru calculul parametrilor

Procedura deterministă e folosită ca tehnică de căutare locală peste spaţiul tuturor vectorilor

posibili de parametri. Setul de coeficienţi ai modelului, folosit ulterior în faza de evaluare, e

calculat cu un consum limitat de resurse.

d. Propuneri referitoare la operatorii genetici

o Operatorul de încrucişare cu punct de tăiere, dependent de context

cpCO cu detecţia similitudinii structurale

Această variantă de cpCO detectează componentele (subarborii) identice din

structura părinţilor şi le evită în cadrul procesului de generare a soluţiilor copii

(Patelli şi Ferariu, 2009c). Este astfel încurajată diversitatea structurală la nivelul

indivizilor urmaşi.

cpCO configurat fuzzy cu reducerea dinamică a listei punctelor de tăiere

eligibile

Pe baza probabilităţilor de încapsulare (ce reflectă fitness-ul BB) atribuite fiecărui

regresor de către un modul fuzzy, această versiune de cpCO protejează

Tabloul contribuţiilor şi concluzii generale 67

substructurile bine adaptate ale părinţilor (Patelli şi Ferariu, 2010c), (Patelli şi

Ferariu, 2010d).

cpCO configurat fuzzy – STRM cu reducerea dinamică a listei punctelor de

tăiere eligibile

Reducerea listei punctelor de tăiere eligibile e ghidată atât de controlerul fuzzy cât

şi de modulul de analiză a schemelor, ce lucrează simbiotic pentru a asigura

eficienţa încapsulării (Patelli şi Ferariu, 2011a), (Patelli şi Ferariu, 2011b).

Versiunea aceasta de cpCO protejează doar regresorii bine adaptaţi cu şanse

inerente mici de supravieţuire, şi are de asemenea un rol creaţionist (e încurajată

generarea de noi instanţe ale unei scheme adaptate anume).

o Operatorul de mutaţie

Mutaţia cu dublu impact

Aceasta versiune vizează atât numele cât şi exponenţii terminalilor din model

(Patelli şi Ferariu, 2009c), cu efecte pozitive în controlul dimensiunii arborilor

(subarborele u(k)* u(k), poate fi stocat ca u2(k)).

Mutaţie configurată fuzzy – STRM cu reducerea dinamică a listei punctelor de

impact eligibile

Simbioza dintre controlerul fuzzy şi modulul de analiză a schemelor e folosită la

protejarea instanţelor existente ale BB adaptate şi la încurajarea genezei altora noi

(Patelli şi Ferariu, 2011a), (Patelli şi Ferariu, 2011b).

A doua categorie de îmbunătăţiri algoritmice, anume cele dezvoltate în context MOO

sunt enumerate mai jos.

a. Configurarea dinamică a priorităţilor obiectivelor

Tehnicile propuse în acest context se referă la articularea (combinarea) progresivă (distribuită

pe durata procesului de căutare) a preferinţelor (informaţiilor vagi despre importanţa

acurateţii relativ la cea a compactităţii modelelor).

o Gruparea populaţiei

Arborii sunt împărţiţi în doua subpopulaţii, supuse unor scheme de evoluţie diferite

(Ferariu şi Patelli, 2009b), (Patelli şi Ferariu, 2009d), (Patelli şi Ferariu, 2009e). Una

dintre cele două subpopulaţii e divizată în două grupuri, relativ la performanţele medii ale

indivizilor, crescând astfel presiunea de selecţie, în mod dinamic, în favoarea modelelor

precise şi de complexitate moderată.


o Gruparea elitelor

Versiunea elitistă a metodei de grupare de mai sus e îmbogăţită cu un mecanism

suplimentar, anume acordarea unui bonus de fitness indivizilor din zona Pareto cu

aplicabilitate practică (Patelli şi Ferariu, 2010a).

o Migraţiune adaptivă

Această tehnică ne-elitistă oferă un mijloc de comunicare între cele două subpopulaţii

supuse unor scheme diferite de evoluţie (Ferariu şi Patelli, 2009b), (Patelli şi Ferariu,

2009d), (Patelli şi Ferariu, 2009e). În consecinţă, priorităţile obiectivelor sunt calibrate cu

grad mai mare de rafinare, ceea ce duce la o distribuţie mai buna (de dorit uniformă) în

zonele cu aplicabilitate practică ale frontului Pareto.

b. Păstrarea diversităţii populaţiei

o Aglomerarea dinamică

Un parametru de importanţă majoră în calculul valorilor de fitness ale elitelor, anume

raza de proximitate , e calculat adaptiv, spre deosebire de abordarea clasică din

literatură, unde valoarea sa e prestabilită (Patelli şi Ferariu, 2010a). Valorile fitness ale

elitelor reflectă astfel şi gradul de aglomerare a zonei Pareto unde sunt situate, pe lânga

performanţele în raport cu funcţiile obiectiv.

o Analiza similitudinii structurale

Arhiva elitelor şi populaţia uzuală sunt supuse unui proces dublu ramificat de generare a

soluţiilor copii (Patelli şi Ferariu, 2010e). Indivizii urmaşi sunt trimişi în populaţia

următoarei generaţii doar dacă au o structură diferită relativ la materialul genetic deja

inclus, procedeu de încurajează diversitatea.

o Reîmprospătarea materialului genetic

Acest instrument pentru păstrarea diversităţii e folosit de câte ori gradul de asemănare

între arborii populaţiei creşte peste un nivel de control (Patelli şi Ferariu, 2010e). O

imagine a setului nedominat de la o generaţie anterioară e injectată în cea curentă,

îmbunătăţind diversitatea, fără o scădere drastică în fitnessul mediu al indivizilor.

A treia clasă de contribuţii algoritmice e legată de exploatarea explicită a blocurilor

structurale şi constă în următoarele îmbunătăţiri:

a. Controlerul fuzzy

Modulul fuzzy implementat apreciază gradul de adaptare a BB pe baza performanţelor

indivizilor gazdă (Patelli şi Ferariu, 2010c), (Patelli şi Ferariu, 2010d). Valoarea AEL

rezultată e mai apoi folosită în configurarea operatorilor genetici, cu scopul protejării

instanţelor schemelor bine adaptate de posibila tăiere în timpul generării soluţiilor copii


b. Procesul de încapsulare

Procedura constă în diminuarea probabilităţilor de selecţie ca puncte de tăiere a nodurilor

interioare regresorilor bine adaptaţi (Patelli şi Ferariu, 2010c), (Patelli şi Ferariu, 2010d),

(Patelli şi Ferariu, 2011a), (Patelli şi Ferariu, 2011b), reducere proporţională cu valoarea

AEL. Numarul instanţelor bine adaptate propagate în generaţia următoare este astfel încurajat

să crească, ceea ce va duce la îmbunătăţirea calităţii generale a arborilor.

o Încapsulare de bază

Prima versiune propusă e nediferenţiată, fiind aplicată pentru toţi regresorii bine adaptaţi,

indiferent de ratele lor inerente de supravieţuire.

o Încapsulare rafinată

Pentru a economisi resurse computaţionale, încapsulările redundante sunt evitate prin

consultarea în prealabil a rezultatelor produse de teoria regresivă a schemelor. Sunt astfel

protejaţi doar regresorii cu şanse inerente mici de supravieţuire.

Încapsulare rafinată simplu strat

Probabilităţile de selecţie asociate nodurilor regresorilor sunt reconfigurate doar o

dată, singurul operator genetic folosit fiind cpCO.

Încapsulare rafinată dublu strat

Operatorii de mutaţie şi cpCO vizează seturi diferite de puncte de tăiere, astfel că

reconfigurarea probabilităţilor prin încapsulare trebuie efectuată de doua ori.

2. CONTRIBUŢII TEORETICE

Autoarea propune o serie de modele teoretice pentru propagarea BB de-a lungul

gneraţiilor. Modelele au fost dezvoltate în context NLP şi constituie o teorie regresivă a

schemelor pentru forme si dimensiuni variabile. În această lucrare, modelele au fost folosite

pentru a eficientiza procesul de încapsulare, cu scopul creşterii numărului de instanţe ale

regresorilor adaptaţi în structura indivizilor urmaşi. Urmează clasificarea contribuţiilor teoretice.

a. Modele probabilistice pentru transmisia BB în context regresiv

o Pentru monitorizarea transmisiei BB

Prima versiune a teoriei schemelor pentru modele regresive a fost construită pentru

monitorizarea încapsulării fuzzy persistente. Această variantă are două componente: cea

formală şi cea estimativă.

o Pentru îmbunătăţirea ratei de transmisie a BB

Rezultatele oferite de teorema schemelor au fost folosite pentru a reduce consumul de

resurse computaţionale implicat de încapsulare, prin limitarea aplicării acesteia la

regresorii bine adaptaţi cu şanse inerente mici de supravieţuire (Patelli şi Ferariu, 2011b).


Această versiune a teoriei schemelor are trei componente: cea formală (oferind mai multa

flexibilitate decât componenta formală în varianta anterioară), cea estimativă (mai precisă

decât varianta anterioară) şi cea predictivă.

Considerând doar cpCO

A doua versiune a teoriei schemelor e aplicată în contextul unui proces de

încapsulare simplu strat.

Considerând cpCO şi mutaţie

A treia versiune a teoriei schemelor e aplicată în contextul unui proces de

încapsulare dublu strat.

b. Un instrument teoretic general pentru validarea oricărei tehnici de exploatare

microscopică

Componenta predictivă e un instrument general de validare ce poate fi folosit în evaluarea

unei tehnici generice de exploatare microscopică. În acest scop, poate fi estimat numărul

instanţelor unei scheme date, în generaţia urmatoare, în prezenţa/absenţa tehnicii de

exploatare evaluate, pentru a-i testa utilitatea. În această lucrare, folosirea instrumentului de

validare (predictorul) e exemplificată pe cazul tehnicii de încapsulare.

3. CONTRIBUŢII SOFTWARE ŞI EXPERIMENTALE

Toţi algoritmii propuşi au fost implementaţi de autoare în C++ şi Matlab. Suportul

software realizat asigură atât funcţionalitătile principale ale agoritmului GP de bază (selecţia

stohastică universală, calculul ieşirilor funcţiilor obiectiv şi ale funcţiilor de fitness, împărţirea

populaţiei pe fronturi Pareto şi validarea modelului) cât şi comportamentul specific al

instrumentelor de identificare sugerate, datorat metodelor specifice descrise în partea a III-a a

lucrării (generarea şi transformarea structurală a arborilor din populaţia iniţială, interfaţa cu

procedura QR – atât în C++ cât şi în Matlab, operatori genetici îmbunătăţiţi, tehnici pentru

eficientizarea peocesului de optimizare în context multiobiectiv, implementarea modulului bazat

pe logică fuzzy şi suportul pentru teoria schemelor regresive). Exceptând procedura QR, care a

fost importată din nucleul Matlab, nu a fost utilizat niciun modul software extern, deci toţi

algoritmii propuşi au implementări originale. În ceea ce priveste proiectarea bazata pe GP, în

lumea academica si de cerectare nu s-a impus încă un software dedicat. Bibliotecile existente în

Matlab se referă doar la cromozomi liniari nu arborescenti. În plus, dezvoltarea integrală a

suportului software a permis o serie de optimizări rezultate din exploatarea eficientă a

proprietăţilor matematice ale operatorilor “+” si “*” în prelucrarea arborilor binari rezultaţi.

Algoritmii software au fost utilizaţi de autoare atât în contextul identificării unor sisteme

simulate, cât şi pentru modelarea unor procese industriale complexe (SISO şi MISO).


Concluziile experimentale demonstrează capacitatea instrumentelor computaţionale propuse de a

reduce automat termenii redundanţi ai modelului, de a oferi informaţii particulare despre sistem

(existenţa timpului mort) şi de a genera soluţii Pareto optimale cu aplicabilitate practică şi grad

mare de diversitate. Pe lângă comparaţiile experimentale între diferiţi algoritmi propuşi de

autoare, aceştia au fost testaţi împreună cu alte proceduri de identificare neliniară nonelitiste. În

acest context, rezultatele testelor statistice ilustrează capacitatea algoritmilor propuşi de a crea

modele cu termeni relevanţi. Investigaţiile experimentale de la finalul fiecărui capitol al parţii a

III-a (din lucrarea extinsă) vizează influenţa diferitelor configuraţii de parametri de intrare asupra

performanţelor algoritmilor, pentru toate sistemele identificate, simple şi complexe.

Rezultatele experimentelor comparative împreună cu demonstraţiile teoretice ale

eficienţei tehnicilor sugerate recomandă algoritmii evolutivi descrişi drept instrumente

competitive în domeniul identificării neliniare. În plus, modelele teoretice şi instrumentele de

validare propuse sunt capabile să evalueze alte metode posibile bazate pe GP, încurajând astfel

cercetarea în această direcţie.

Anexa A BIBLIOGRAFIE (EXTRAS)

Cărţi:

Ashlock D. Evolutionary Computation for Modelling

and Optimization

Springer 2005

Coello Coello C.A.

Lamont G.B.

Van Veldhuizen D.A.

Evolutionary Algorithms for Solving

Multi-Objective Problems

Springer

IInd ed

2007

Deb K. Multi-Objective Optimization using

Evolutionary Algorithms

John Wiley & Sons 2001

DeJong K.A. Evolutionary Computation – A Unified

Approach

The MIT Press 2006

Ehrgott M. Multicriteria Optimisation Springer

IInd ed

2005

Fletcher R. Practical Methods of Optimization John Wiley & Sons 2000

Koza J.R. Genetic Programming – On the

Programming of Computers By Means of

Natural Selection

The MIT Press

VIth ed

1998

Kramer O. Self-Adaptive Heuristics for

Evolutionary Computation

Springer 2008

Miettinen K. Nonlinear Multiobjective Optimisation Kluwer Academic Publishers

IVth ed

2004

Poli R.

Langdon W.B.

McPhee N.F.

A Field Guide to Genetic Programming http://www.gp-field-guide.org.uk 2008

Lucrări în jurnale:

Beadle L.

Johnson C.G.

Semantic Analysis of Program

Initialisation in Genetic Programming

Genetic Programming

and Evolvable

Machines [Springer]

10(3) 307

337

2009

Day P.

Nandy A.K.

Binary String Fitness Characterization

and Comparative Partner Selection in

Genetic Programming

IEEE Transactions on

Evolutionary

Computation

12(6) 724

735

2008

http://www.gp-field-guide.org.uk/

Anexa A. Bibliografie 74

Ferariu L.

Patelli A.


with Insular Evolution and Adaptive

Migration

The Scientific Bulletin

of the “Politehnica”

University of Timisoara

54(68) 155

162

2009a

Gustafson S.M.

Vanneschi L.

Crossover Based Tree Distance in

Genetic Programming


Evolutionary

Computation

12(4) 506

524

2008

Lara A.

Sanchez G.

Coello Coello C.A.

Schutze O.

HCS – A New Local Search Strategy for

Memetic Multiobjective Evolutionary

Algorithms


Evolutionary

Computation

14(1) 112

132

2009

Mitavskiy B.

Cannings C.

Estimating the Ratios of the Stationary

Distribution Values for Markov Chains

Modelling Evolutionary Algorithms

Evolutionary

Computation

[The MIT Press]

17(3) 343

377

2009

Molina D.

Lozano M.

Garcia-Martinez C.

Herrera F.

Memetic Algorithms for Continuous

Optimization Based on Local Search

Chains

Evolutionary

Computation

[The MIT Press]

18(1) 27

63

2010

O’Neill M.

Vanneschi L.

Gustafson S.

Banzhaf W.

Issues in Genetic Programming Genetic Programming

and Evolvable

Machines

[Springer]

11(3-4) 339

363

2010

Ong Y.S.

Lim M.H.

Zhu N.

Whong K.W.

Classification of Adaptive Memetic

Algorithms: A Comparative Study


Systems, Man and

Cybernetics—Part B:

Cybernetics

36(1) 141

152

2006

Patelli A.

Ferariu L.

Multiple Genetic Programming Based

Techniques for Nonlinear Systems

Identification

Bulletin of the

Polytechnic Institute of

Iasi

55(59) 23

36

2009a

Patelli A.

Ferariu L.

Cluster Based Multiobjective Genetic


Identification

Annals of the

University of Craiova

6(33) 60

66

2009

b

Patelli A.

Ferariu L.

Regressor Encapsulation Using Fuzzy

Control in Evolving Nonlinear Models

Annals of the

University of Craiova

7(34) 26

32

2010a


Patelli A.

Ferariu L.

Elite Based Multiobjective Genetic


Identification

Advances In Electrical

And Computer

Engineering

10(1) 94

99

2010

b

Poli R.

Langdon W.B.

Backward-chaining Evolutionary

Algorithms

Artificial Intelligence

[Elsevier]

170(11) 953

982

2006

Poli R.

McPhee N.F.

General Schema Theory for Genetic

Programming with Subtree Swapping

Crossover: Part I

Evolutionary

Computation

[The MIT Press]

11(1) 53

66

2003a

Poli R.

McPhee N.F.

General Schema Theory for Genetic

Programming with Subtree Swapping

Crossover: Part II

Evolutionary

Computation

[The MIT Press]

11(2) 169

206

2003b

Poli R.

Vanneschi L.

Langdon W.B.

McPhee N.F.

Theoretical Results in Genetic

Programming: The Next Ten Years?

Genetic Programming

and Evolvable

Machines

[Springer]

11(3-4) 285

320

2010

Rachmawati L.

Srinivasan D.

Multiobjective Evolutionary Algorithm

with Controllable Focus on the Knees of

the Pareto Front


Evolutionary

Computation

13(4) 810

824

2009

Silva S.

Costa E.

Dynamic Limits for Bloat Control in

Genetic Programming and a review of

Past and Current Bloat Theories

Genetic Programming

and Evolvable

Machines [Springer]

10(2) 141

179

2009

Smith J.E.

Coevolving Memetic Algorithms: A

Review and Progress Report


Systems, Man and

Cybernetics—Part B:

Cybernetics

37(1) 6

17

2007

Capitole de cărţi:

Ferariu L.

Patelli A.

Multiobjective Genetic Programming for

Nonlinear System Identification

Adaptive And Natural

Computing Algorithms

(Lecture Notes in Computer

Science, 5495) Springer

233

242

2009b

Patelli A.

Ferariu L.

Regressor Survival Rate Estimation for

Enhanced Crossover Configuration

Adaptive And Natural

Computing Algorithms



290

300

2011a


Poli R. A Simple but Theoretically-motivated

Method to Control Bloat in Genetic

Programming

Genetic Programming



204

217

2003

Lucrări în volumele conferinţelor:

Ferariu L.

Patelli A.

Migration-Based Multiobjective Genetic

Programming for Nonlinear System

Identification

Proc. of the 5th Int. Symp. on

Applied Computational

Intelligence and Informatics

475

480

2009c

McPhee N.F.

Poli R.

Using schema theory to explore

interactions of multiple operators

Proc of the Genetic and

Evolutionary Computation

Conference

853

860

2002

Patelli A.

Ferariu L.

Nonlinear Systems Identification by

Means of Genetic Programming

Proc. of the European Control

Conference

502

507

2009c

Patelli A.

Ferariu L.

Monoobjective and Multiobjective

Genetic Programming in Nonlinear


Proc. of the17th Int. Conf. on

Control Systems and Computer

Science

9

14

2009d

Patelli A.

Ferariu L.

Enhanced Multiobjective Genetic

Programming for Multivariable


Recent Developments in

Artificial Intelligence Methods

247

258

2009e

Patelli A.

Ferariu L.

Increasing Crossover Operator

Efficiency in Multiobjective Nonlinear


Proc. of the IEEE International

Conference on Intelligence

Systems

426

431

2010c

Patelli A.

Ferariu L.

Dynamic Fuzzy Controlled Regressor

Encapsulation in Evolving Nonlinear

Models

Proc. of the 14th International

Conference on System Theory

and Control

373

378

2010d

Patelli A.

Ferariu L.

Elitist Multiobjective Nonlinear Systems

Identification with Insular Evolution and

Diversity Preservation

Proc. of the IEEE World

Congress on Evolutionary

Computation

2076

2081

2010e

Patelli A.

Ferariu L.

A regressive schema theory based tool

for GP evolved nonlinear models

Proc. of the 17th Int. Conf. on

Automation and Computing

215

220

2011b


Teze de doctorat:

Day R.O. Explicit Building Block Multiobjective

Evolutionary Computation: Methods and

Applications

http://www.stormingmedia.us/51/5127

/A512734.html

2005

Gustafson S.M. An Analysis of Diversity in Genetic

Programming

http://etheses.nottingham.ac.uk/57/1/p

hdthesis-gustafson.pdf

2004

Rodriguez-Vasquez

K.

Multiobjective Evolutionary Algorithms

in Nonlinear System Identification

http://www.lania.mx/~ccoello/phdthes

es.html#R

1999

Vladislavleva E. Model Based Problem Solving through

Symbolic Regression via Pareto Genetic

Programming

http://arno.uvt.nl/show.cgi?fid=80764 2008

http://www.stormingmedia.us/51/5127/A512734.html

http://www.stormingmedia.us/51/5127/A512734.html

http://etheses.nottingham.ac.uk/57/1/phdthesis-gustafson.pdf

http://etheses.nottingham.ac.uk/57/1/phdthesis-gustafson.pdf

http://www.lania.mx/~ccoello/phdtheses.html#R

http://www.lania.mx/~ccoello/phdtheses.html#R

http://arno.uvt.nl/show.cgi?fid=80764

Date post:	15-Oct-2019
Category:	Documents
Upload:	others
View:	23 times
Download:	0 times

IDENTIFICAREA SISTEMELOR NELINIARE PRIN TEHNICI BAZATE … · împrospătare a materialului...

Documents