Seria
RCAI "Computer Science"
212 UNIVERSITATEA DIN CRAIOVA Facultatea de Matematică şi Informatică CENTRUL DE CERCETARE ÎN INTELIGENŢĂ ARTIFICIALĂ
CALCUL EVOLUTIV
ION IANCU
EDITURA UNIVERSITARIA
CRAIOVA, 2009
Referenţi ştiinţifici:
Prof. dr. I. Văduva, Universitatea din Bucureşti
Prof. dr. D. Dumitrescu, Universitatea „Babeş-Bolyai”, Cluj-Napoca
CUPRINS
Prefaţă…………………………………………………………9
1 Introducere în calculul evolutiv………………..………...13 1.1 Specificul calculului evolutiv..........................................13 1.2 Noţiuni de bază...............................................................19 1.3 Domenii de aplicabilitate.................................................24
2 Spaţiul de căutare şi funcţia de adecvare.….……………27 2.1 Codificarea spaţiului de căutare …….......…….………28
2.1.1 Structuri de date………………..……...………28 2.1.2 Reguli de codificare…….…….………...……..28
2.1.2.1 Codificarea binară ……..……..……..……29 2.1.2.2 Codificarea întreagă ……...………..……..33 2.1.2.3 Codificarea reală …...…………...………..34 2.1.2.4 Codificarea specifică......………………….35
2.1.2.4.1 Codificarea prin adiacenţă .....….35 2.1.2.4.2 Codificarea ordinală….……....…36 2.1.2.4.3 Codificarea prin drumuri ….…...37 2.1.2.4.4 Codificarea prin numerotare…...37 2.1.2.4.5 Codificarea matriceală …..……..38
2.2 Construirea funcţiei de adecvare ………………………41
3 Metode de selecţie………………...……..…………….…..47 3.1 Introducere……………..…………………….….……47
4
3.2 Selecţia după rang …….……………….…….………49 3.3 Metoda ruletei …………..………………..…….…….50 3.4 Metoda fitnessului proporţionat …….…..…………...52 3.5 Selecţia stochastică universală …………..……..……54
3.6 Selecţia trunchiată ……………………………………54 3.7 Selecţia de tip turneu ….………..…………………....55 3.8 Selecţia locală …...……...……………………………56 3.9 Compararea metodelor de selecţie ……………….......59
4 Operatori genetici…………….…………………………...61
4.1 Încrucişarea ……………….………………………….61 4.1.1 Încrucişarea binară …………...………………….61 4.1.1.1 Încrucişarea simplă ……..……….………...61 4.1.1.2 Încrucişarea multiplă .………….………… 62 4.1.1.3 Încrucişarea uniformă …….……………….63 4.1.1.4 Încrucişarea amestecată ...…..…….……… 65 4.1.1.5 Algoritmul de încrucişare ............................65 4.1.2 Încrucişarea reală …………………….….……….66 4.1.2.1 Încrucişarea discretă ………………...……. 66 4.1.2.2 Încrucişarea intermediară …………….….. 68
4.1.2.3 Încrucişarea liniară ………………...………70 4.1.3 Încrucişarea adiacentă …………………….……..71 4.1.3.1 Încrucişarea prin muchii alternante …….... 71 4.1.3.2 Încrucişarea prin subtrasee ……………...…72 4.1.3.3 Încrucişarea euristică …………………...… 72 4.1.4 Încrucişarea ordinală…………………….……… 74 4.1.5 Încrucişarea prin drumuri ……………………… 75
5
4.1.5.1 Încrucişarea PMX ……………...………… 75 4.1.5.2 Încrucişarea OX …………………..……… 77 4.1.5.3 Variante ale încrucişării OX …………..…. 78 4.1.5.4 Încrucişarea CX ………………………….. 80 4.1.6 Încrucişarea prin muchii …….…………….……. 81 4.1.7 Încrucişarea matriceală …………………….…… 83 4.2. Mutaţia …………………………………...………….. 86 4.2.1 Mutaţia binară …………………………...………. 86 4.2.1.1 Mutaţia tare ..................................................87 4.2.1.2 Mutaţia slabă ............................................... 87 4.2.1.3 Mutaţia neuniformă ..................................... 87 4.2.1.4 Mutaţia auto-adaptivă .................................. 88 4.2.1.5 Mutaţia cromozomială …………………… 89 4.2.2 Mutaţia reală …………………………………….. 90 4.2.2.1 Mutaţia uniformă ........................................90 4.2.2.2 Mutaţia neuniformă .................................... 91 4.2.2.3 Mutaţia auto-adaptivă ................................. 92 4.2.3 Mutaţia întreagă …………………………………. 93 4.2.4 Mutaţia specifică ………………………………... 93 4.3 Reinserţia ……………………………………………. 95 4.3.1 Reinserţia globală ………………………………. 95
4.3.2 Reinserţia locală ………………………………….96
5 Funcţionarea algoritmilor genetici…..…………………..99 5.1 Maximizarea unei funcţii ………...…..……………...100 5.2 Problema comis-voiajorului …………...……………115
5.3 Aplicaţii în probleme de algebră ................................ 119
6
5.4 Orarul unei şcoli.......................................................... 122 5.5 O problemă de proiectare.............................................. 127
6 Scheme şi blocuri…………………………………..…….133
6.1 Scheme: definiţie, proprietăţi ……………….………133 6.2 Teorema schemei ....................................................... 138 6.3 Blocuri.........................................................................148
7 Variante de algoritmi genetici…………..………….…...151 7.1 Probleme de convergenţă ........................................... 151 7.2 Algoritmul genetic modificat ..................................... 154 7.3 Algoritmul hillclimbing ............................................. 156 7.4 Algoritmul călire simulată .......................................... 159 7.5 Algoritmi de tip contracţie ..........................................161 7.6 Algoritmi cu dimensiunea variabilă a populaţiei ...….167 7.7 Algoritmi cu constrângeri ……..….……………...…. 171 7.8 Algoritmi genetici dezordonaţi …..……………….… 177 7.9 Algoritmi virali ………………..………………….… 180 7.10 Algoritmul delta………………………...………….. 185 7.11 Studiul calitativ al algoritmilor genetici ….…..….… 186
8 Strategii evolutive…………..………………...…….…...193 8.1 Generalităţi.................... ............................................ 193 8.2 Operatori de evoluţie................................................... 197 8.2.1 Încrucişarea ........................................................... 197 8.2.1.1 Încrucişarea discretă ...................................... 197 8.2.1.2 Încrucişarea intermediară............................... 198
7
8.2.2 Mutaţia ………...…………………………………..199 8.3 Funcţionarea strategiilor evolutive.……………..……. 200 8.3.1 Strategia )11( + …………...……………………... 200
8.3.2 Strategia )1( +μ ……………………………….…. 203
8.3.3 Strategii multidescendent …………………….…..203 8.3.4 Utilizarea mutaţiilor corelate…..…………………..207 8.4 Analiza convergenţei …………………………………210 8.5 Domenii de aplicabilitate...............................................213
9 Programare evolutivă şi programare genetică..….…...215 9.1 Programare evolutivă.................................................. 215 9.1.1 Generalităţi ........................................................... 215 9.1.2 Funcţionarea automatului Turing .......................... 217 9.1.3 Optimizare folosind programarea evolutivă........... 219 9.2 Programare genetică…………….…………...……… 223 9.2.1 Reprezentarea indivizilor…….....………………..224 9.2.2 Populaţia iniţială……..………….…………….… 228 9.2.3 Operatori de evoluţie…… ……………………… 234 9.2.4 Rularea programelor în programarea genetică……236
10 Software de algoritmi evolutivi……………...…….…...241 Bibliografie................................................................................249
PREFAŢĂ
La mijlocul anilor ’70 s-a constatat că tot mai multe probleme care modelau fenomene complexe din domenii precum biologia, mecanica, climatologia, chimia, analiza datelor rămâneau nerezolvabile sau soluţiile oferite de metodele matematice, cunoscute în acel moment, erau nesatisfăcătoare datorită aproximărilor grosiere.
Astfel, a aparut ideea de a rezolva astfel de probleme folosind principiile evoluţiei şi eredităţii. O astfel de tehnică menţine o mulţime (populaţie) de soluţii potenţiale şi foloseşte metode de selecţie bazate pe “fitnessul” (adecvarea) indivizilor şi anumiţi operatori “genetici” pentru a construi generaţia următoare. Astfel a apărut calculul evolutiv iar conjenctura lui Rechenberg constituie şi azi justificarea aplicării tehnicilor evolutive în rezolvarea problemelor de optimizare: ''Evoluţia naturală este, sau cuprinde, un proces de optimizare foarte eficient, care, prin simulare, poate duce la rezolvarea de probleme dificil de optimizat''.
Ideea de bază a calculului evolutiv este imitarea unor procese evolutive din natură; de aceea el este o ramură a calculului natural şi, mai general, a calculului inteligent (soft computing).
La rândul său, calculul evolutiv cuprinde mai multe direcţii, precum cele enumerate în continuare:
- strategiile evolutive, care sunt algoritmi ce imită evoluţia naturală pentru a rezolva probleme de optimizare parametrică, având ca
10
element distinctiv un parametru al evoluţiei, utilizat pentru a modifica soluţia curentă;
- programarea genetică, a cărei caracteristică principală constă în faptul că populaţia este formată din programe care candidează la rezolvarea problemei;
- algoritmii genetici, care - în accepţiunea lui John Holland – erau algoritmi evolutivi ce utilizau ca structură de date şirul de biţi pentru a rezolva probleme de optimizare discretă. Azi, în foarte multe cazuri, prin algoritm genetic se înţelege orice model de tip evolutiv;
- programarea evolutivă, introdusă de Fogel cu scopul de a genera un comportament inteligent pentru un sistem artificial, folosind mutaţia ca principal mijloc de evoluţie. Variantele actuale de programare evolutivă au foarte multe lucruri în comun cu strategiile evolutive.
Cartea de faţă tratează aspectele de bază ale calculului evolutiv, insistând asupra algoritmilor genetici, ale căror principii se regăsesc în toate celelalte modele evolutive.
Capitolul 1 are un caracter introductiv, rolul său fiind de a familiariza cititorul cu terminologia utilizată, cu principiile de funcţionare şi cu domeniile de aplicabilitate.
Capitolul 2 se ocupă de codificarea spaţiului în care se caută soluţia problemei de optimizat şi de construirea funcţiei de adecvare a indivizilor.
Capitolul 3 este consacrat metodelor folosite pentru a selecta indivizii ce vor fi supuşi operaţiilor de evoluţie genetică. Se prezintă
11
principalele tehnici: selecţia după rang, metodele ruletei şi fitnessului proporţionat, selecţiile stochastică universală, trunchiată, turneu şi locală.
Capitolul 4 studiază operatorii de evoluţie genetică. Se începe cu încrucişarea, fiind prezentate diverse metode asociate tipului de reprezentare ales pentru indivizii populaţiei: binară, reală, prin grafuri (pe modelul problemei comis voiajorului). În partea a doua se analizează operatorii de mutaţie corespunzători reprezentărilor de tip binar, întreg, real şi specifice problemei comis voiajorului. În final se prezintă metode de inserare în noua populaţie a descendenţilor.
Capitolul 5 prezintă modele de funcţionare a algoritmilor genetici: maximizarea unei funcţii, problema comis voiajorului, rezolvarea unei ecuaţii diofantice, problema orarului, o problema de proiectare.
Capitolul 6 se ocupă de scheme şi blocuri. După ce se prezintă noţiunile de bază referitoare la scheme, se deduce teorema schemei, comparând rezultatele furnizate de aceasta cu cele obţinute pe un exemplu. În final se prezintă blocul ca un tip special de schemă.
În capitolul 7, după o scurtă analiză a convergenţei algoritmilor genetici, se prezintă mai multe tipuri de algoritmi genetici: versiunea modificată, hillclimbing, călire simulată, algoritmul de tip contracţie, algoritmi cu dimensiunea variabilă a populaţiei, cu constrângeri, dezordonaţi, virali, algoritmul delta.
Capitolul 8 se ocupă de strategii evolutive. După prezentarea operatorilor genetici specifici, se prezintă principalele variante de
12
strategii evolutive: )11( + , )1( +μ , ( )λμ + , ( )λμ, şi o analiză a
convergenţei.
Capitolul 9 studiază programarea evolutivă şi programarea genetică. În cadrul programării evolutive, după ce se explică funcţionarea automatului Turing, se prezintă modul de utilizare în rezolvarea problemelor de optimizare. În cadrul programării genetice se prezintă reprezentarea indivizilor, generarea populaţiei iniţiale şi evoluţia ei şi, în final, un exemplu de utilizare într-o problemă de regresie.
Capitolul 10 realizează o succintă prezentare a principalelor produse soft consacrate utilizării algoritmilor evolutivi: GENESIS, GENEsYs, DGENESIS, Simple GA, GAL, GALIB, SUGAL, GAGA, GENOCOP, Genetic-2, Genetic-2N, GenET, SES, EM, LICE, WinGA, TOLKIEN, Gaucsd, GAC, GAGS, GAMusic, GENALG, GenET, Genie, GENlib, mGA, ParaTSP .
Cartea este o sinteză a informaţiilor despre Calculul evolutiv, existente în literatura de specialitate. Ea se adresează studenţilor, cadrelor didactice şi specialiştilor din diferite domenii care, în activitatea curentă, se confruntă cu probleme de optimizare. De asemenea, îmi exprim convingerea că ea va fi un instrument util pentru cei care doresc să se iniţieze în acest domeniu al inteligenţei artificiale.
1 INTRODUCERE ÎN CALCULUL EVOLUTIV
1.1 Specificul calculului evolutiv
În matematică optimizarea este înţeleasă ca însemnând găsirea unei soluţii optime. În acest scop s-au obţinut rezultate importante în calculul diferenţial, calculul variaţional, controlul optimal, cercetări operaţionale. Drumul de la rezultatele teoretice, referitoare la teoreme de existenţă, unicitate, caracterizare a soluţiei, etc., la optimizarea efectivă este de multe ori prea lung, fie datorită complexităţii prea mari a problemelor reale faţă de modelul matematic utilizat, fie datorită complexităţii (timp, memorie) algoritmilor utilizaţi.
La mijlocul anilor '70, odată cu creşterea performanţelor calculatoarelor şi, implicit, a complexităţii problemelor reale ce se puteau rezolva cu ajutorul calculatorului, au devenit frecvente situaţiile în care modelele clasice de optimizare nu mai conduceau la soluţii acceptabile pentru probleme modelabile pe calculator. Tot mai frecvent, probleme din biologie, climatologie, chimie, mecanică, analiza datelor, etc., probleme ale căror modele includ sute sau mii de
14
variabile, ale căror funcţii de optimizat prezintă multiple optime locale şi neregularităţi nestudiate din punct de vedere numeric, rămâneau nerezolvate sau cu soluţii aproximate grosier.
Studiindu-se excelenta adaptare a fiinţelor vii, în ceea ce priveşte forma, structura, funcţiile şi stilul de viaţă, numeroşi cercetători au ajuns la concluzia că natura oferă soluţii optimale la problemele sale, soluţii superioare oricăror performanţe tehnologice. S-a demonstrat, chiar matematic, optimalitatea unor sisteme biologice: raportul diametrilor ramificaţiilor arterelor, poziţia punctelor de ramificare a vaselor de sânge, valoarea hematocritului (procentul volumului particolelor solide din sânge). În consecinţă, au apărut primele încercări de imitare a procesului de evoluţie naturală. Încă din perioada anilor 1950, oameni de ştiinţă precum Turing şi von Neumann au fost interesaţi în modelarea şi înţelegerea fenomenelor biologice în termeni de procesări naturale ale informaţiei. Începutul erei calculatoarelor a promovat tendinţa de simulare a proceselor şi a modelelor naturale şi a condus la dezvoltarea unor modele evolutive artificiale.
În anul 1970 profesorii Hans-Paul Schwefel (Dortmund) şi Ingo Rechenberg (Berlin) având de rezolvat o problemă de mecanica fluidelor, referitoare la optimizarea formei unui corp ce se deplasează într-un fluid, au căutat o nouă tehnică de optimizare deoarece metodele cunoscute până în acel moment nu conduceau la o soluţie acceptabilă. Ideea lor a întruchipat conjectura lui Rechenberg, rămasă până azi justificarea fundamentală a aplicării tehnicilor evolutive: ''Evoluţia naturală este, sau cuprinde, un proces de optimizare foarte
15
eficient, care, prin simulare, poate duce la rezolvarea de probleme dificil de optimizat''.
Modelul de simulare propus de Rechenberg şi Schwefel [71,
76, 77] este cunoscut azi sub numele de ''strategii evolutive'' şi iniţial se aplica doar problemelor de optimizare de variabilă continuă. Soluţiile candidat x se reprezintă în virgulă mobilă iar individul i , căruia i se aplică procesul evolutiv, constă din această reprezentare şi dintr-un parametru al evoluţiei, notat σ , reprezentat tot in virgulă
mobilă: ( )σ,xi = . La fiecare pas soluţia curentă este modificată pe
fiecare componentă conform lui σ şi în cazul unei îmbunătăţiri este înlocuită cu cea nou obţinută. Parametrul σ joacă rolul pasului din metodele iterative clasice şi este astfel folosit încât să fie respectat principiul "mutaţiilor mici". Pentru strategiile evolutive au fost dezvoltate scheme de adaptare a parametrilor de control ( auto-adaptare ).
A doua direcţie de studiu s-a conturat la Universitatea San Diego; punctul de pornire a fost tot simularea evoluţiei biologice iar structura de date aleasă a fost maşina cu număr finit de stări. Urmând această abordare, Fogel [25, 28] a generat programe simple, anticipând "programarea genetică". Populaţia este reprezentată de programe care candidează la rezolvarea problemei. Există diverse reprezentări ale elementelor populaţiei, una dintre cele mai utilizate fiind aceea în care se utilizează o structură arborescentă. În anumite
16
aplicaţii, cum este regresia simbolică, programele sunt de fapt expresii. De exemplu, programul expresie ( )"*" cba + poate fi descris
prin . O astfel de structură poate fi uşor codificată în Lisp,
astfel că primele implementări din programarea genetică foloseau acest limbaj.
(( cba ∗+ ))
După mai mulţi ani de studiere a simulării evoluţiei, John
Holland de la Universitatea Michigan a propus în 1975 [44] conceptul de "algoritm genetic". Au fost abordate probleme de optimizare discretă iar structura de date aleasă a fost şirul de biţi. Într-o accepţiune strictă, noţiunea de algoritm genetic se referă la modelul studiat de Holland şi de studentul său De Jong. Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populaţie şi care foloseşte operatori de selecţie şi recombinare pentru a genera noi puncte în spaţiul de căutare.
O altă direcţie o constituie „programarea evolutivă”. Iniţial, ea
a avut ca obiectiv dezvoltarea unor structuri automate de calcul printr-un proces de evoluţie în care operatorul principal este cel de mutaţie. Bazele domeniului au fost puse de către Fogel [28]. Ulterior, programarea evolutivă a fost orientată către rezolvarea problemelor de optimizare având aceeaşi sferă de aplicabilitate ca şi strategiile evolutive.
17
Calculul evolutiv foloseşte algoritmi ale căror metode de căutare au ca model câteva fenomene naturale: moştenirea genetică şi lupta pentru supravieţuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt cele amintite anterior: algoritmii genetici, strategiile evolutive, programarea genetică şi programarea evolutivă. Există şi alte sisteme hibride care încorporează diferite proprietăţi ale paradigmelor de mai sus; mai mult, structura oricărui algoritm de calcul evolutiv este, în mare măsură, aceeaşi. Calculul evolutiv este un domeniu al calculului inteligent în care rezolvarea unei probleme este văzută ca un proces de căutare în spaţiul tuturor soluţiilor posibile. Această căutare este realizată prin imitarea unor mecanisme specifice evoluţiei în natură. În scopul găsirii soluţiei, se utilizează o populaţie de căutare. Elementele acestei populaţii reprezintă soluţii potenţiale ale problemei. Pentru a ghida căutarea către soluţia problemei, asupra populaţiei se aplică transformări specifice, inspirate din evoluţia naturală, precum:
Selecţia. Elementele populaţiei care se apropie de soluţia problemei sunt considerate adecvate şi sunt favorizate în sensul că au mai multe şanse de a supravieţui în generaţia următoare precum şi de a participa la generarea de “descendenţi”.
Încrucişara. La fel ca în înmulţirea din natură, pornind de la două sau mai multe elemente ale populaţiei (numite părinţi), se generează noi elemente (numite descendenţi). În funcţie de calitatea acestora
18
(apropierea de soluţia problemei) descendenţii pot înlocui părinţii sau alţi indivizi din populaţie.
Mutaţia. Pentru a asigura diversitatea populaţiei se aplică, la fel ca în natură, transformări cu caracter aleator asupra elementelor populaţiei, permiţând apariţia unor trăsături (gene) care doar prin încrucişare şi selecţie nu ar fi apărut în cadrul populaţiei.
În continuare, un algoritm de rezolvare bazat pe aceste idei va fi numit algoritm evolutiv. Principalele caracteristici ale algoritmilor evolutivi, comparativ cu cei tradiţionali sunt:
• sunt algoritmi probabilişti ce îmbină căutarea dirijată cu cea aleatoare; • realizează un echilibru aproape perfect între explorarea spaţiului stărilor şi găsirea celor mai bune soluţii; • în timp ce metodele clasice de căutare acţionează la un moment dat asupra unui singur punct din spaţiul de căutare, algoritmii evolutivi menţin o mulţime (numită populaţie) de soluţii posibile; • algoritmii evolutivi nu acţionează direct asupra spaţiului de căutare ci asupra unei codificări a lui; • sunt mai robuşti decât algoritmii clasici de optimizare şi decât metodele de căutare dirijată; • sunt simplu de utilizat şi nu cer proprietăţi importante ale funcţiei obiectiv precum continuitate, derivabilitate, convexitate, ca în cazul algoritmilor clasici;
19
• furnizează, cu o mare probabilitate, o soluţie apropiată de cea exactă.
1.2 Noţiuni de bază
Principalele noţiuni care permit analogia între rezolvarea problemelor de căutare şi evoluţia naturală sunt următoarele:
Cromozomul este o mulţime ordonată de elemente, numite gene, ale căror valori determină caracteristicile unui individ. În genetică, poziţiile pe care se află genele în cadrul cromozomului se numesc loci, iar valorile pe care le pot lua se numesc alele. În calculul evolutiv cromozomii sunt, de obicei, vectori ce conţin codificarea unei soluţii potenţiale şi sunt numiţi indivizi. Astfel, genele nu sunt altceva decât elementele acestor vectori.
Populaţia. O populaţie este constituită din indivizi care trăiesc într-un mediu la care trebuie să se adapteze. În calculul evolutiv, un individ este de cele mai multe ori identificat cu un cromozom şi reprezintă un element din spaţiul de căutare asociat problemei de rezolvat.
Genotipul este ansamblul tuturor genelor unui individ sau chiar a întregii populaţii. În calculul evolutiv genotipul reprezintă codificările corespunzătoare tuturor elementelor populaţiei.
20
Fenotipul este ansamblul trăsăturilor determinate de către un anumit genotip. În calculul evolutiv fenotipul reprezintă valorile obţinute prin decodificare, adică valori din spaţiul de căutare.
Generaţia este o etapă în evoluţia unei populaţii. Dacă vedem evoluţia ca un proces iterativ în care o populaţie se transformă în altă populaţie atunci generaţia este o iteraţie în cadrul acestui proces.
Selecţia. Procesul de selecţie naturală are ca efect supravieţuirea indivizilor cu grad ridicat de adecvare la mediu (fitness mare). Acelaşi scop îl are şi mecanismul de selecţie de la algoritmii evolutivi şi anume de a favoriza supravieţuirea elementelor cu grad mare de adecvare. Aceasta asigură apropierea de soluţia problemei întrucât se exploatează informaţiile furnizate de către cele mai bune elemente ale populaţiei. Unul dintre principiile teoriei evoluţioniste este acela că selecţia este un proces aleator şi nu unul determinist. Acest lucru este întâlnit în majoritatea mecanismelor de selecţie utilizate de către algoritmii evolutivi.
Reproducerea este procesul prin care, pornind de la populaţia curentă, se construieşte o nouă populaţie. Indivizii noii populaţii (generaţii) moştenesc caracteristici de la părinţii lor, dar pot dobândi şi caracteristici noi ca urmare a unor procese de mutaţie care au un caracter întâmplător. În cazul în care în procesul de reproducere intervin cel puţin doi părinţi, caracteristicile moştenite de descendenţi se obţin prin combinarea (încrucişarea) caracteristicilor părinţilor.
21
Mecanismele de încrucişare şi mutaţie asigură explorarea spaţiului soluţiilor prin descoperirea de noi configuraţii. Fitnessul sau adecvarea. În evoluţia naturală fiecare individ al populaţiei este adaptat mai mult sau mai puţin mediului iar unul dintre principiile teoriei evoluţioniste este acela că supravieţuiesc doar cei mai buni indivizi. Fitnessul (adecvarea) este o măsură a gradului de adaptare a individului la mediu. Scopul evoluţiei este ca toţi indivizii să ajungă la o adecvare cât mai bună la mediu, ceea ce sugerează legătura între un proces de evoluţie şi unul de optimizare. În calculul evolutiv, gradul de adecvare al unui element al populaţiei este o măsură a calităţii acestuia în raport cu problema care trebuie rezolvată. Dacă este vorba de o problemă de maximizare atunci gradul de adecvare va fi direct proporţional cu valoarea funcţiei obiectiv (un element este cu atât mai bun cu cât valoarea acestei funcţii este mai mare).
Noţiunile de adecvare şi evaluare sunt folosite în general cu acelaşi sens; totuşi se poate face o distincţie între ele. Funcţia de evaluare, sau funcţia obiectiv, reprezintă o măsură a performanţei în raport cu o mulţime de parametri, în timp ce funcţia de adecvare transformă această măsură a performanţei în alocare de facilităţi reproductive. Evaluarea unui şir reprezentând o mulţime de parametri este independentă de evaluarea altor şiruri. Adecvarea unui şir este, însă, definită în raport cu alţi membri ai populaţiei curente; de
22
exemplu, prin ff i , unde este evaluarea asociată şirului i iar este
evaluarea medie a tuturor şirurilor populaţiei.
if f
Funcţia de evaluare şi codificarea sunt, de obicei, singurele
componente ale algoritmilor evolutivi care depind de problema de rezolvat. Un algoritm evolutiv, folosit pentru rezolvarea unei probleme de optimizare, poate fi privit ca o ''cutie neagră'' cu o serie de butoane de control reprezentând diverşi parametri. Ieşirea cutiei negre este valoarea unei funcţii indicând în ce măsură o anumită distribuţie a parametrilor rezolvă problema dată. În termeni tradiţionali, dorim să minimizăm (maximizăm) o funcţie
. De cele mai multe ori este imposibil de tratat
independent fiecare parametru. Apariţia interacţiunilor face necesară considerarea efectelor combinate ale parametrilor în vederea optimizării cutiei negre. În limbajul algoritmilor genetici, interacţiunea dintre variabile este numită epistasis.
( nxxxF ,,, 21 L )
Variabilele reprezentând parametrii sunt, de obicei, codificate
prin şiruri binare, dar există şi alte codificări: numere întregi, numere reale, codul Gray, codificare alfabetică, arbori. Condiţiile pe care trebuie să le îndeplinească o reprezentare bună sunt: independenţa relativă a genelor, includerea a cât mai multe restricţii ale problemei direct în reprezentare, complexitate scăzută a decodificării/codificării cromozomilor. Rezolvarea problemelor de codificare este considerată,
23
de obicei, ca parte a construcţiei funcţiei de evaluare. Funcţia de evaluare este parte a descrierii problemei. Precizarea funcţiei de evaluare poate implica o simulare şi poate fi aproximativă sau parţială. De exemplu, să considerăm o problemă de control optimal, în care mulţimea stărilor în care se poate afla sistemul poate fi exponenţial de mare. Folosirea unui algoritm evolutiv pentru găsirea unei strategii optime de control presupune reducerea spaţiului stărilor (prin eşantionare) şi, astfel, evaluarea realizată este aproximativă şi afectată de perturbaţii. Funcţia de evaluare trebuie să fie uşor de calculat, având în vedere că fiecare generaţie trebuie evaluată; deci, funcţia de evaluare este apelată de foarte multe ori. La aplicarea unui algoritm evolutiv pentru rezolvarea unei probleme concrete trebuie alese în mod adecvat: modul de codificare a elementelor, funcţia de adecvare şi operatorii de selecţie, încrucişare şi mutaţie. Unele dintre aceste elemente sunt strâns legate de problema de rezolvat, iar altele mai puţin. Structura unui algoritm evolutiv este următoarea
Procedure AE begin 0:=t iniţializare )(tP
evaluare )(tP
while (not condiţie terminare) do begin
24
1: += tt selectare din )(tP )1( −tP
modificare )(tP
evaluare )(tP
end end.
1.3. Domenii de aplicabilitate Sistemele evolutive se utilizează atunci când nu există altă
strategie de rezolvare a problemei şi este acceptat un răspuns aproximativ. Se utilizează în special atunci când problema poate fi formulată ca una de optimizare, însă nu numai. Algoritmii evolutivi sunt utilizaţi în diverse domenii, precum:
Planificare. Majoritatea problemelor de planificare (de exemplu, alegerea traseelor optime ale unor vehicule, rutarea mesajelor într-o reţea de telecomunicaţii, planificarea unor activităţi, etc.) pot fi formulate ca probleme de optimizare cu sau fără restricţii. Multe din acestea sunt de tip NP, necunoscându-se algoritmi de rezolvare care să aibă complexitate polinomială. Pentru astfel de probleme algoritmii evolutivi oferă posibilitatea obţinerii, în timp rezonabil, a unor soluţii sub-optimale de calitate acceptabilă.
25
Proiectare. Algoritmii evolutivi au fost aplicaţi cu succes în proiectarea circuitelor digitale, a filtrelor dar şi a unor structuri de calcul cum sunt reţelele neuronale. Ca metode de estimare a parametrilor unor sisteme ce optimizează anumite criterii, algoritmii evolutivi se aplică în diverse domenii din inginerie cum ar fi: proiectarea avioanelor, proiectarea reactoarelor chimice, proiectarea structurilor în construcţii, etc.
Simulare şi identificare. Simularea presupune să se determine modul de comportare a unui sistem pornind de la un model al acestuia. Identificarea este sarcina inversă, a determinării structurii sistemului pornind de la modul de comportare. Algoritmii evolutivi sunt utilizaţi atât în simularea unor probleme din inginerie dar şi din economie. Identificarea unui model este utilă în special în efectuarea unor predicţii în diverse domenii ( economie, finanţe, medicină, ştiinţele mediului, etc.).
Control. Algoritmii evolutivi pot fi utilizaţi pentru a implementa controlere on-line asociate sistemelor dinamice (de exemplu pentru a controla roboţii mobili ).
Clasificare. Se poate considera că din domeniul calculului evolutiv fac parte şi sistemele de clasificare. Un sistem de clasificare se bazează pe o populaţie de reguli de asociere (reguli de producţie) care evoluează pentru a se adapta problemei de rezolvat (calitatea unei reguli se stabileşte pe baza unor exemple). Evoluţia regulilor are acelaşi scop ca şi la învăţarea în reţelele neuronale. Algoritmii
26
evolutivi sunt aplicaţi cu succes în clasificarea imaginilor, în biologie (pentru determinarea structurii proteinelor) sau în medicină (pentru clasificarea electrocardiogramelor).
2 SPAŢIUL DE CĂUTARE ŞI FUNCŢIA DE ADECVARE La proiectarea unui algoritm evolutiv trebuie să se stabilească:
• Modul de codificare. Se specifică modul în care fiecărei configuraţii din spaţiul de căutare i se asociază un cromozom.
• Funcţia de adecvare. Se construieşte funcţia care exprimă gradul de adecvare la mediu, pornind de la restricţiile şi funcţia obiectiv asociate problemei.
• Dimensiunea şi modul de iniţializare a populaţiei. Se pot utiliza populaţii de dimensiune fixă sau de dimensiune variabilă. De cele mai multe ori populaţia se iniţializează în manieră aleatoare cu elemente din spaţiul de căutare.
• Mecanismul de selecţie a părinţilor şi supravieţuitorilor.
• Mecanismul de încrucişare a părinţilor pentru a genera urmaşi.
• Mecanismul de mutaţie, care asigură perturbarea indivizilor ce compun populaţia.
28
• Criteriul de oprire. Atunci când nu se cunoaşte un criteriu specific problemei se optează pentru un număr maxim de iteraţii. Se pot folosi informaţii despre populaţie, cum ar fi gradul de diversitate al acesteia.
2.1. Codificarea spaţiului de căutare
Codificarea spaţiului de căutare este una dintre cele mai importante etape ale proiectării unui algoritm evolutiv întrucât determină modul în care se va desfăşura procesul de evoluţie. Se referă la următoarele aspecte: structuri de date folosite, regula de codificare şi regula de decodificare.
2.1.1. Structuri de date
În algoritmii genetici cromozomii sunt reprezentaţi prin structuri liniare cu număr fix de elemente (tablouri) sau cu număr variabil de elemente (liste înlănţuite). Prima variantă este cea mai frecvent folosită. Structuri de alt tip (de exemplu, structuri arborescente ) se folosesc în alte metode evolutive ( de exemplu în programarea genetică ).
2.1.2. Reguli de codificare
Modul în care o configuraţie este codificată într-un cromozom depinde de problema concretă, existând mai multe variante de codificare.
29
2.1.2.1 . Codificarea binară
Aceasta este varianta clasică: cromozomii sunt vectori cu
elemente din iar spaţiul de căutare este , cu
numărul de gene.
}1,0{ nS }1,0{= n
Exemplul 2.1. Problema submulţimii de sumă maximă limitată. Se consideră o mulţime { nwwW ,,1 L }= de valori întregi şi
o valoare întreagă. Se caută o submulţime cu proprietatea că suma elementelor lui este cât mai apropiată de V , dar nu depăşeşte această valoare. Orice submulţime poate fi reprezentată
printr-un vector cu
V WS ⊂
S
0
S
, ns ),,( 21 ss L =is wi dacă S∉ şi 1=is dacă
. Suma elementelor submulţimii este ∑ . S∈wi S=
n
i 1ii sw
Exemplul 2.2. Problema rucsacului. Se consideră o mulţime de obiecte caracterizate de greutăţile n ( )nww ,,1 L
n
şi de valorile
. Se pune problema determinării unei submulţimi de
obiecte pentru a fi introduse într-un rucsac de capacitate C astfel încât valoarea obiectelor selectate să fie maximă. O soluţie a acestei probleme poate fi codificată ca un şir de valori binare în felul
următor: dacă obiectul i este selectat, respectiv
( ,L )nvv ,1
is 1= 0=is dacă
obiectul nu este selectat.
Exemplul 2.3. Problema împachetării. Se consideră o mulţime de obiecte caracterizate de dimensiunile n ( )ndd ,,1 L şi o mulţime de
30
m cutii având capacităţile ( )mCC ,,1 L
m
. Se pune problema plasării
obiectelor în cutii astfel încât capacitatea acestora să nu fie depăşită iar numărul de cutii utilizate să fie cât mai mic. O posibilă reprezentare binară pentru această problemă este următoarea: se utilizează o matrice cu linii şi coloane iar elementul are
valoarea 1 dacă obiectul i este plasat în cutia
A n ija
j şi în caz contrar
(obiectul nu este plasat în cutia
0
i j ). Prin liniarizarea matricei se
ajunge ca fiecare soluţie să fie reprezentată printr-un cromozom conţinând gene. n×m
Exemplul 2.4. Optimizarea unei funcţii definită pe un domeniu continuu. Se consideră o funcţie
[ ] [ ] [ ]ba n →⊂,1 RRnab n×× ,2 Lab ×1D =f : ,2
şi se caută ( )*n
*1 , xx*x = ,L care minimizează pe . Pentru a utiliza
codificarea binară, fiecare componentă ale lui
f
ix ( )nx,x = x ,1 L se
transformă după regulile: • se scalează pentru a fi adusă în intervalul [ ]1,0 :
ii
iii ab
axv−−
=
r • se stabileşte numărul de biţi necesari pentru reprezentare şi se
aduce valoarea în mulţimea { }:1,1,0 −riv 2,L
( )⎣ ⎦1⋅= iv 2 −riu ,
31
unde reprezintă partea întreagă. Valoarea astfel obţinută se
reprezintă în baza 2.
⎣ ⎦
De exemplu, pentru ( ) [ ] [ ]3,22,13.2,25.1 ×∈=x şi 5=r
2
se
obţine iar cromozomul asociat va avea ( 3.0,25.0=x ) 10=⋅ r
componente binare: ( )1,0,0,1,0,1,1,1,0,0 . Este evident că această
codificare are caracter aproximativ, motiv pentru care în cazul variabilelor reale se preferă utilizarea codificării reale.
Utilizarea reprezentării binare în cazul în care configuraţiile corespunzătoare problemei sunt vectori de valori reale prezintă dezavantajul că unele valori reale aflate la distanţă mică au asociate reprezentări binare aflate la distanţă mare (diferă în multe poziţii binare). De exemplu, reprezentarea lui pe biţi este iar reprezentarea lui 8 este 1000 . Se remarcă faptul că trecerea de la reprezentarea lui 7 la cea a lui 8 necesită modificări de biţi. O altă variantă de codificare care evită acest dezavantaj este codificarea de tip Gray caracterizată prin faptul că valori întregi succesive au asociate şiruri de biţi care diferă într-o singură poziţie.
7
4
4 0111
Pornind de la reprezentarea binară ( )nbb ,,1 L (cifrele binare
sunt specificate începând cu cea mai semnificativă), codul Gray, , se construieşte după regula: ( naa ,,1 L )
1i 1i
1⎩⎨⎧
>⊕=
=− ii
ii bb
ba
unde reprezintă adunarea modulo 2. ⊕
32
Reprezentarea clasică
0 1 2 3 4 5 6 7
000 001 010 011 100 101 110 111
Codificarea Gray
0 1 2 3 4 5 6 7
000 001 011 010 110 111 101 100
Tabelul 1: Reprezentări binare: reprezentarea clasică în baza 2 şi codul Gray
În cazul codificării binare clasice a unei valori din intervalul , pentru a obţine valoarea decodificată pornind de la şirul de biţi
obţinut prin codificare se foloseşte relaţia:
[ ba, ]
∂(s1,……,sn)= ∑=
−
−
−+
n
j
jjn saba
1
1212
În cazul codificării de tip Gray decodificarea se bazează pe relaţia:
∂(s1,……,sn)= ∑ ⊕=
−
=−
−+
n
j
jnk
j
kn )s(aba
1 12
12.
În cazul decodificării şirul de biţi se parcurge de la dreapta la stânga.
33
2.1.2.2. Codificarea întreagă
Există mai multe posibilităţi de a reprezenta un număr întreg nenegativ p , în funcţie de mulţimea în care ia valori.
• dacă p ia valori în mulţimea { }12,,1,0 −nL atunci el poate fi
reprezentat ca un şir binar cu nbbb L10 { }bi ni ≤≤∈ 0,1,0 .
• dacă { }12,,1, −++∈ nmmmp L atunci se codifică mp − ca în
cazul anterior
• dacă { 1,,2,1 }−∈ lp L şi nu există astfel încât atunci
sunt posibile mai multe soluţii:
n nl 2=
a) se ia [ ] 12 += llogn
) l≥ 1
şi se transformă fiecare şir binar
în ( bbb n 1010 L −= lp (operaţie numită tăietură); în acest caz
fiecare număr p cuprins între 0 şi 2−l este reprezentat printr-un şir
binar, în timp ce 1−= lp este reprezentat prin şiruri ln −2
b) se ia [ ] 12 += llogn şi se transformă fiecare şir nbbbs L10= în
( )11
−l
s2
10
−=
sp n (operaţie numită scalare), unde reprezintă
scrierea şirului în baza 10.
10s
34
2.1.2.3. Codificarea reală Este adecvată pentru problemele de optimizare pe domenii
continue. Presupunem că se doreşte maximizarea unei funcţii de
variabile ; fiecare variabilă ia valori într-un domeniu
şi
k
RRf k →:
[ ] Rbi ⊂,
ix
aD ii = ( ) 01 >kx,,x Lf pentru orice ii Dx ∈ . Cerând o
precizie de 4 zecimale pentru valorile variabilelor, fiecare interval
va trebui divizat în
iD
( )ii ab −410 subintervale egale. Fie cel mai mic
întreg astfel încât il
( ) 12104 −≤− ilii ab .
Atunci o reprezentare a variabilei ca un şir binar de
lungime va satisface precizia dorită.
ix
il
Acum fiecare cromozom este reprezentat printr-un şir binar de
lungime ; primii biţi reprezintă o valoare din ∑=
=k
iill
11l [ ]11, ba ,
următorii biţi reprezintă o valoare din [ şi aşa mai departe. 2l ]22 , ba
Decodificarea se face cu formula
( )122
−−
⋅+=il
iiii
abstringzecimalax
unde reprezintă valoarea zecimală a şirului binar
.
( 2stringzecimal )string
35
2.1.2.4. Codificarea specifică
Se alege o variantă cât mai apropiată de specificul problemei. Majoritatea codificărilor de acest tip vor fi explicate pentru problema comis voiajorului [60]: se consideră o mulţime de oraşe şi se pune problema găsirii unui traseu care să treacă o singură dată prin fiecare oraş şi care să aibă costul minim (dacă costul este proporţional cu lungimea traseului atunci se caută trasee de lungime minimă). Rezolvarea problemei constă în găsirea celei mai bune permutări a oraşelor , unde
n
( nv,,v L1 ) { }nvi ,,1 L∈ . Pentru a fi respectată
restricţia ca fiecare oraş să fie vizitat o singură dată este necesar ca elementele vectorului ( )nv,,LvV 1= să fie distincte.
2.1.2.4.1. Codificarea prin adiacenţă
Un cromozom (care reprezintă un traseu) este o listă de oraşe: oraşul
nj este plasat în poziţia dacă şi numai dacă există o
muchie de la oraşul i la oraşul
i
j . De exemplu, vectorul
( )6,5,1,7,9,3,8,4,2
reprezintă traseul
769583421 →→→→→→→→ .
Unele liste de adiacenţă pot reprezenta trasee ilegale, ca de exemplu
( )6,7,5,3,9,1,8,4,2
care duce la 1421 →→→ ,
36
adică la o ciclare (prematură) obţinută înainte de terminarea traseului.
2.1.2.4.2. Codificarea ordinală În acest caz un traseu se reprezintă ca o listă de n oraşe,
elementul aflat pe poziţia în listă fiind un număr din intervalul
. Se foloseşte o listă ordonată a oraşelor, care serveşte ca
referinţă pentru reprezentarea ordinală. Considerând lista
i
[ 1,1 +− in ] L
( )9,8,7,6,5,4,3,2,1=L ,
traseul 769583421 →→→→→→→→
va fi codificat ca o listă
( )1,1,3,1,4,1,2,1,1=l
interpretată astfel:
• primul număr din lista l este 1, aşa că primul oraş din lista este luat ca prim oraş al traseului şi este şters din lista ; traseul parţial este (
LL
)1
• următorul oraş din lista l este 1, aşa că se ia primul oraş din lista curentă ca oraşul următor al traseului şi se sterge din lista ; rezultă traseul parţial
L L( )21→
• următorul număr din lista este 2, deci se alege al doilea oraş din lista curentă ca următorul oraş al traseului şi se şterge din listă; în acest moment traseul parţial este
lL
( )421 →→ .
37
În final rezultă traseul
769583421 →→→→→→→→ .
2.1.2.4.3. Codificarea prin drumuri Aceasta este cea mai naturală codificare a unui traseu. De
exemplu, traseul
326498715 →→→→→→→→
este codificat simplu ca
( )326498715 ,,,,,,,, .
2.1.2.4.4. Codificarea prin numerotare
Considerăm din nou problema împachetării. În varianta de codificare binară propusă în Exemplul 2.3 apare dezavantajul că pot fi generate configuraţii care nu sunt fezabile. Acestea sunt de exemplu matricele care conţin mai multe elemente egale cu 1 pe o linie (aceasta ar însemna că un obiect este simultan inclus în mai multe cutii). Pentru a evita astfel de situaţii se poate utiliza un alt tip de reprezentare: un vector cu componente n ( )nv,,L
i
v1 în care
reprezintă cutia în care este inclus obiectul . { mvi ,,1 L∈ }
38
2.1.2.4.5. Codificarea matriceală
Fox şi McMahon [30] au propus reprezentarea unui traseu ca o matrice binară M în are care elementul ijm valoarea 1 dacă şi numai
dacă oraşul i apare înaintea lui j în traseu. De exemplu, traseul
596478213 →→→→→→→→
este reprezentat prin matricea de mai jos.
1 2 3 4 5 6 7 8 9
1 0 1 0 1 1 1 1 1 1 2 0 0 0 1 1 1 1 1 1 3 1 1 0 1 1 1 1 1 1 4 0 0 0 0 1 1 0 0 1 5 0 0 0 0 0 0 0 0 0 6 0 0 0 0 1 0 0 0 1 7 0 0 0 1 1 1 0 0 1 8 0 0 0 1 1 1 1 0 1 9 0 0 0 0 1 0 0 0 0
În această reprezentare matricea M de dimensiune nn× rep
rul valorilor este exact
rezintă un traseu de n oraşe (total ordonate) cu următoarele proprietăţi:
1. numă 1 ( )2
1−nn
2. 0= pentru orice i cu niiim ≤≤1
39
3. dacă 1=ijm şi 1=jkm atu ci 1=ikmn .
ai mic decât Dacă numărul valorilor 1 din matrice este m ( )2
1−nn
iar parţia
fost folosită de Seniw [84] şi Ho
celelalte două condiţii sunt satisfăcute atunci oraşele sunt l ordonate, adică există cel puţin o modalitate de completare a matricei astfel încât să se obţină un traseu legal.
O altă reprezentare de tip matriceal amaifar şi Guan [45] . În această reprezentare, elementul ijm ia
valoarea 1 dacă şi numai dacă există un traseu de la oraşul i direct la oraşul j (matricea de adiacenţă).
1 2 3 4 5 6 7 8 9 1 0 1 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 3 0 0 0 0 0 0 0 1 0 4 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 1 0 0 6 0 0 0 0 1 0 0 0 0 7 0 0 0 0 0 0 0 0 1 8 0 0 0 0 0 1 0 0 0 9 1 0 0 0 0 0 0 0 0
stfel, matricea anterioară reprezintă un traseu care vizitează oraşele
, în această ordine. Această
reprezentare nu specifică oraşul de start, fiind valide şi alte trasee:
A( )975683421 ,,,,,,,,
40
( )197568342 ,,,,,,,, , ( )219756834 ,,,,,,,, ,
avân
etc.
Un traseu complet este reprezd un singur 1 pe fiecare lin
atrice cu aceste proprietăţi repmatrice
entat printr-o matrice binarăi fiecare coloană. Totuşi, nu orice zintă un traseu complet. Unele
ie ş rem
pot reprezenta subtrasee care nu sunt conectate între ele. De exemplu, matricea următoare reprezintă două subtrasee: ( )75421 ,,,, şi ( )9683 ,,, .
1 2 3 4 5 6 7 8 9 1 0 1 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 3 0 0 0 0 0 0 0 1 0 4 0 0 0 0 1 0 0 0 0 5 0 0 0 0 0 0 1 0 0 6 0 0 0 0 0 0 0 0 1 7 1 0 0 0 0 0 0 0 0 8 0 0 0 0 0 1 0 0 0 9 0 0 1 0 0 0 0 0 0
41
2.2. Construirea funcţiei de adecvare
esul de evoluţie naturală se urmăreşte maximizarea gradulu folosi de analogi te util să
ul
În proci de adecvare a indivizilor la mediu. Pentru a ne a dintre procesele de căutare şi cele de evoluţie es
reform ăm problemele de optimizare ca probleme de maximizare (orice problemă de minimizare poate fi transformată într-una de maximizare prin schimbarea semnului funcţiei obiectiv). Pentru o
problemă de minimizare de forma: să se determine Dx ∈* cu
proprietatea că ( ) ( )xfxf ≤* pentru orice Dx∈ , funcţia de adecvare
poate fi chiar funcţia obiectiv )()( xfxF = . Lucrurile devin mai
complicate în cazul problemelor cu restricţii.
Să consid lemă de minim cu restricţii:
să se determine Dx ∈* cu a că minimizează funcţia
obiectiv RDf →: şi satisface restricţiile:
erăm o prob izare
proprietate
O variantă de a trata restricţiile este de a folosi tehnica enalizării, care permite inc cţiei de
adecvare:
110 kj,)x(g *j ≤≤= ( restricţii de tip egalitate )
20 k,)x(h * ≥ ( restricţii de tip inegalitate ) 1 jj ≤≤
p luderea acestora în cadrul fun
a)x(f)x(F += ( )( )∑=
1
1
2k
jj xg b+ ( )( )∑
=
2
1
k
jj xhϕ
unde
42
şi sunt parametri pozitivi care reflectă importanţa relativă a înc ă stricţiilor (cu cât şi sunt mai mari cu atât restricţia este a ncă ă mai mult). Dacă se
ieri între restricţii atunci se pot utiliza mai multe valori
. Funcţia de adecvare depinde de starea
vectorului (adm
Modul de specificare a funcţiei de adecvare sugerează că dacă o soluţie este acceptabilă atunci ea este cu atât mai bună cu cât se apropie mai mult de optim ( în cazul nostru înseamnă că suma este cu atât mai apropiată de M ). Dacă soluţia nu este admisibilă atunci ea este cu
( )⎩⎨⎧
≥<
=0u 0u u
u0
2
ϕ
iar a brii re
ţ
ălc m
fac diferen
a blcarea ei este penalizati importantă şi î
(11 ,, kaa L şi
21 ,, kbb L în loc de a si respectiv b ).
Exemplul 2.5. Problema submulţimii. Un vector ( )nsss ,,L= este admisibil (adică este o soluţie potenţială) dacă 1
satisface relaţia ∑ ≤n
ii Msw=i 1
isibil sau nu):
⎪⎨
⎧
−=
∑ da sw
admisibil este s ădac )s(F n
⎪⎩
⎪⎪∑
=
=
admisibil estenu s ăc
sw
iii
n
iii
1
1
atât mai bună cu cât abaterea faţă de o soluţie admisibilă este mai mică. Această tehnică de a trata diferit soluţiile admisibile şi cele
43
neadmisibile permite compararea între ele a soluţiilor. Regulile naturale sunt următoarele:
• orice soluţie admisibilă este mai bună decât o soluţie care nu este admisibilă;
• dintre două soluţii admisibile este mai bună cea care are adecvarea
mentelor submulţimii este mai mare)
ţin pragul M ).
u sunt admisibile. O posibilă funcţie de adecvare este:
. Problema comis-voiajorului. În acest caz, dacă se foloseşte o reprezentare de tip permutare restricţia problemei (trecerea o singură dată prin fiecare oraş) este implicit satisfăcută. Dacă ma
mai mare (în cazul problemei submulţimii aceasta înseamnă că suma valorilor ele
• dintre două soluţii neadmisibile cea mai bună este cea care încalcă mai puţin restricţiile (în cazul acestei probleme înseamnă că suma elementelor este mai mică, adică depăşeşte cu mai pu
Exemplul 2.6. Problema rucsacului. Fiind o problemă cu restricţii, trebuie luat în considerare şi cazul configuraţiilor care n
⎪⎪
⎨
⎧≤
=∑∑==
n
1j
n
1jjj Cswdacă sv
sF )(
⎪⎪
⎩>−− ∑∑∑
===
n
1jjj
n
1jjj
n
1jjj
jj
Cswdacă Cswbsv )(
Exemplul 2.7
tricea C conţine costurile ( ),( jic reprezintă costul trecerii de la
oraşul i la oraşul j ) atunci funcţia de cost poate fi descrisă prin:
44
),(), 11
1 n
n
iiin +=∑
=+ (),........,(
1
1 sscsscssf−
multe probleme ne interesează nu numai g sirea optimului
lobal ci şi mulţimea tuturor soluţiilor acceptabile. Dacă există un ptim g
seşte funcţia de par
1)
În ăgo lobal şi mai multe optime locale, populaţia va migra spre zona optimului global. De aceea trebuie găsit un mecanism care să favorizeze apariţia unor subpopulaţii corespunzătoare diferitelor puncte de optim. Soluţia este oferită de conceptul biologic de nişă ecologică, conform căruia indivizii unei populaţii se grupează în nişe ecologice iar indivizii unei nişe împart între ei resursele.
Aplicarea acestui principiu la algoritmi genetici presupune modificarea funcţiei de adecvare. Pentru aceasta se folo
tajare care defineşte faptul că doi indivizi ai populaţiei îşi împart resursele. Deoarece cu cât indivizii sunt mai apropiaţi cu atât îşi impart mai mult resursele, înseamnă că funcţia de partajare trebuie să fie descrescătoare în raport cu distanţa dintre cromozomi.
O funcţie de partajare ]1,0[: →Rp trebuie să verifice
condiţiile: p este descrescătoare
2) )0( =p 1
3) 0)( =∞
dp . lim→d
Un exemplu de astfel de funcţie este
45
⎪⎩
⎪⎨⎧ − pentrud1
≥
<=
adpentru
adadp
0)(
unde este diametrul nişei, adică distanţa maximă dintre doi zo
ţa dintre doi cromozomi se poate defini în mai multe feluri:
anţa euclidiană, care realizează nişe sferice
oziţiilor în care cei
, care reprezintă numărul de ştergeri, adăugări
re individ din populaţie se calculează valoarea
iar funcţia de adecvare partajată se defineşte prin
acromo mi.
Distan
• dist
• distanţa Hamming, care reprezintă numărul pdoi cromozomi diferă
• distanţa Levensteinsau modificări efectuate asupra elementelor unui şir pentru a-l face identic cu celălalt.
Pentru fieca ix
iv a nişei corespunzătoare lui:
( )n
( )∑=
=j
jii xxdpv1
,
i
ixfxf
)()(* = i v
unde este dimensiunea populaţiei iar este funcţia obiectiv.
ctelor de optim care au puţini reprezentanţi în populaţie. Fie
n f
Funcţia de adecvare partajată favorizează menţinerea punM mulţimea
indivizilor unui astfel de punct; avem
46
( ) axxd ji <, pentru Mxx ji ∈, şi
( ) axxd ki ≥, pentru MxMx ki ∉∈ ,
( )( ) 0, =ki xxdpceea ce implică pentru k MxMxi ∉∈ , .
Deoarece M are puţini indivizi, valoarea a nişei
corespunză
iv
toare individului Mxi ∈ va fi mică în rapo valorile
corespunzătoare altor puncte de optim. Rezultă că valorile funcţiei de
adecvare partajat
rt cu
ă vor fi mai mari pentru indivizii din *f M ceea ce
face ca în generaţia următoare să se obţină mai mulţi indivizi corespunzători acestui optim.
3 METODE DE SELECŢIE
3.1. Introducere
Selecţia are ca scop determinarea populaţiei intermediare ce conţine părinţii care vor fi supuşi operatorilor de încrucişare şi mutaţie precum şi determinarea indivizilor ce vor face parte din generaţia următoare. Criteriul de selecţie se bazează pe gradul de adecvare al indivizilor la mediu, exprimat prin valoarea funcţiei de adecvare. Nu este obligatoriu ca atât părinţii cât şi supravieţuitorii să fie determinaţi prin selecţie, fiind posibil ca selecţia să fie folosită într-o singură etapă. Există două clase principale de metode de selecţie [98]:
• Metode deterministe. Acestea se caracterizează prin faptul că elementele cu grad mai mare de adecvare sunt întotdeauna selectate în defavoarea celor cu un grad mai mic de adecvare. Un exemplu de astfel de metodă este selecţia prin trunchiere.
• Metode aleatoare. Acestea se caracterizează prin faptul că în procesul de selecţie intervin elemente aleatoare. Variantele cel mai
48
frecvent întâlnite se bazează pe stabilirea unor probabilităţi de selecţie care depind de gradul de adecvare. În felul acesta elementele cu grad mai mare de adecvare au şanse mai mari de a fi selectate, astfel că numărul de copii ale acestora este mai mare decât al celor cu grad mai mic de adecvare. Metodele cele mai reprezentative sunt selecţia proporţională, selecţia pe baza rangurilor şi selecţia de tip turneu.
Calitatea selecţiei este definită de o serie de parametri [98], dintre care amintim
• presiunea selectivă = probabilitatea celui mai bun individ de a fi selectat, comparativ cu media probabilităţii de selecţie a tuturor indivizilor
• abaterea = diferenţa în valoare absolută dintre fitnessul normalizat al individului şi probabilitatea sa aşteptată de reproducere
• întinderea = plaja de valori posibile pentru numărul de descendenţi ai individului
• pierderea diversităţii: proporţia de indivizi din populaţie care nu sunt selectaţi
• intensitatea selecţiei: valoarea medie aşteptată a fitnessului populaţiei după aplicarea metodei de selecţie la distribuţia Gauss-iană normalizată
• varianţa selecţiei: varianţa aşteptată a distribuţiei fitnessului populaţiei după aplicarea metodei de selecţie la distribuţia Gauss-iană normalizată.
49
3.2. Selecţia după rang
Indivizii sunt sortaţi descrescător după valorile funcţiei obiectiv, fitnessul atribuit fiecărui individ depinde numai de poziţia sa în şir şi nu de valoarea funcţiei obiectiv. Fiecărui individ i se asociază
probabilitatea de a fi selectat astfel încât ip ∑ = 1ip . Există două
tipuri standard de probabilităţi [98]:
• liniară: biapi +⋅= , cu 0<a
• exponenţială: . cibi eap +⋅⋅=
Avantajele selecţiei după rang constă în faptul că nu duce la convergenţă prematură şi nici la stagnare.
Fie notaţiile:
• Nind - numărul de indivizi din populaţie
• Pos - poziţia unui individ în populaţie (individul cel mai neconvenabil are Pos=1, iar cel mai bun are Pos=Nind )
• SP – presiunea selecţiei
Fitnessul unui individ se calculează astfel:
• aranjarea liniară: )Nind/()Pos)(SP(SP)Pos(Fitness 11122 −−−+−=
Aranjarea liniară permite valori ale parametrului SP în intervalul . [ ]0.2,0.1
• aranjarea neliniară:
50
Fitness ∑=
−−⋅=Nind
i
iPos x/xNind)Pos(1
11
unde x este rădăcina ecuaţiei
.
a neliniară permite valori ale lui SP din intervalul
Probabilitatea unui individ de a fi selectat este dată de fitnessul său
3.3. Metoda ruletei
Principiul ruletei reprezintă cea mai simplă metodă de selecţie,
tfel încât
conţine
când este selectat numărul dorit de
ceastă tehnică este similară cu cea a ruletei, în care fiecare segmen
1 1 ⋅+− − XSPX)SP( Nind 02 =+⋅++− SPXSPNind L
Aranjare[ ]2,0.1 −Nind .
normalizat prin fitnessul total al populaţiei.
fiind un algoritm stochastic ce foloseşte următoarea tehnică:
• indivizii sunt văzuţi ca segmente continuie pe o dreaptă, asfiecare segment asociat unui individ este egal cu fitnessul său;
• se generează un număr aleator şi individul al cărui segment numărul respectiv va fi selectat
• se repetă pasul anterior pânăindivizi.
At este proporţional cu fitnessul unui individ.
51
Exemplul 3.1. [98]Tabelul următor arată probabilitatea de selecţie pentru 11 indivizi, folosind aranjarea liniară şi presiunea selectivă 2. Individul 1 este cel mai bun şi ocupă intervalul cel mai mare, în timp ce individul 10 este penultimul în şir şi ocupă intervalul cel mai mic; individul 11, ultimul din şir, având fitnessul 0 nu poate fi ales pentru reproducere.
nr 4
Probabilitatea în acest tabel se calculează ca fiind raportul dintre fitnessul unui individ şi suma fitnessurilor tuturor indivizilor.
Număr individ
1 2 3 4 5 6 7 8 9 10
Fitness 2.0 1.8 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2
Proba- bilitate selecţie
0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02
Dorind să selectăm indivizi, se generează 6 numere aleatoare
uniform distribuite în intervalul
6
( )1,0 . Fie acestea , , ,
, , . Aşezând cei 10 indivizi pe o dreaptă, în ordinea
810. 32.0 96.0
01.0 650. 420.
individ nr 2 nr 6 nr 5 nr 1 nr 3
52
1, 2, ... ,10, individul 1 va ocupa segmentul cuprins între 0.0 şi 0.18, individul 2 segmentul dintre 0.18 şi 0.34, individul 3 segmentul dintre 0.34 şi 0.49, etc. Deoarece individul 6 corespunde segmentului delimitat de 0.73 şi 0.82 iar primul număr generat (= 0.81) cade în acest segment, individul 6 va fi selectat pentru reproducere. În mod similar se selectează indivizii 1, 2, 3, 5, 9; deci, populaţia selectată este formată din indivizii 1, 2, 3, 5, 6, 9.
3.4. Metoda fitnessului proporţionat Este metoda cea mai des utilizată şi funcţionează astfel:
• se calculează fitnessul al fiecărui individ şi fitnessul mediu al
populaţiei if i
nf
f i∑=
• individul i este selectat pentru reproducere cu probabilitatea
fnf
ffp i
i
ii ⋅
==∑
.
• dacă trebuie selectaţi N indivizi, numărul N l indivizilor ce vor fi
selectaţi cu probabilitatea ip a fi apoximativ egal cu N
i a
v ip⋅ .
Metoda fitnessului proporţionat poate fi implementată cu ajutorul algoritmului ruletei.
53
Exemplul 3.2. Fie 4=n indivizi având 1021 == ff , 153 =f
şi . În practică, metoda ruletei poate fi implementată folosind
un vector cu componente şi un index aleator
254 =f
v m r , urmând ca individul să fie selectat la fiecare „măturare”. Luând )(rv 12=m în
exemplul nostru, deoarece
61
21 == pp , 41
3 =p , 125
4 =p şi ii pmN ⋅= ,
rezultă ) . Pentru 444443332211(=v 6=r va fi selectat
individul . 3)6( =v
La terminarea selecţiei este posibil ca un individ să fie selectat de mai multe ori (să aibă mai multe copii). Dacă se selectează un număr de indivizi egal cu dimensiunea a populaţiei, deoarece numărul aşteptat de copii ale individului i este
n
ffnpN i
ii == ,
înseamnă că indivizii pentru care ff i > tind să aibă mai mult de o
copie. Un individ cu
maxfff i ≤≤
va fi selectat într-o generaţie timpurie iar către sfârşitul rulării toţi indivizii tind să aibă valori ale fitnessului relativ mari şi similare, adică iff i ∀≈ max . În acest moment
11 ≈≈≈ nNN L ,
astfel că există o presiune selectivă foarte mică.
54
3.5. Selecţia stochastică universală
Acest tip de selecţie furnizează abaterea zero şi întinderea minimă. Indivizii sunt văzuţi ca segmente aşezate pe dreaptă ca la metoda ruletei. Pointeri, egal depărtaţi, sunt plasaţi pe această dreaptă, indicând indivizii ce vor fi selectaţi. Dacă este numărul indivizilor
ce vor fi selectaţi, atunci distanţa dintre pointeri este
N
N1 iar poziţia
primului pointer este un număr generat aleator în intervalul [ ]N,10 .
De exemplu [98], pentru a selecta indivizi, distanţa dintre pointeri este 1/6=0.167. Considerând că numărul generat aleator în intervalul [0, 0.167] este 0.1 şi plasând pointerii pe exemplul de la metoda ruletei se obţin următorii indivizi selectaţi: 1 .
6
8,6,4,3,2,
individ
număr aleator
pointer 1 pointer 2 pointer 3 pointer 4 pointer 5 pointer 6
3.6. Selecţia trunchiată
Este o metodă de selecţie artificială utilizată de crescătorii de animale pentru a efectua selecţia la nivelul populaţiilor de dimensiuni mari. Indivizii sunt ordonaţi după fitnessul lor şi sunt selectaţi ca părinţi cei mai buni. Parametrul folosit pentru selecţie este pragul de
55
trunchiere Trunc. El indică proporţia populaţiei ce va fi selectată ca părinţi şi ia valori în intervalul 50% - 10%. Indivizii aflaţi sub pragul de trunchiere nu vor produce descendenţi. Intensitatea selecţiei este un termen utilizat frecvent în selecţia trunchiată. Relaţia dintre pragul de trunchiere şi intensitatea selecţiei rezultă din tabelul următor
Prag 1% 10% 20% 40% 50% 80% Intensitate 2.66 1.76 1.2 0.97 0.8 0.34
3.7. Selecţia de tip turneu
În acest tip de selecţie, un număr de indivizi (Tur) este ales aleator din populaţie şi, apoi, cel mai bun individ din acest grup este selectat ca părinte. Acest procedeu este repetat ori de câte ori trebuie ales un nou individ. Parametrul Tur al selecţiei dă dimensiunea turneului şi ia valori din intervalul [2, Nind], unde Nind este numărul de indivizi din populaţie.
Tabelul următor [98] dă relaţia dintre dimeniunea turneului şi intensitatea selecţiei.
dimensiunea turneului
1 2 3 5 10 30
intensitatea selecţiei
0 0.56 0.85 1.15 1.53 2.04
56
3.8. Selecţia locală
În selecţia locală fiecare individ acţionează în interiorul unui mediu restrâns numit vecinătate locală. Indivizii interacţionează numai în interiorul unei vecinătăţi. Vecinătatea este definită de structura în care este distribuită populaţia şi poate fi văzută ca un grup de potenţiali parteneri de încrucişare. Indivizii se selectează folosind una din metodele discutate anterior, apoi se defineşte vecinătatea locală pentru fiecare individ. În interiorul vecinătăţii se selectează un singur individ: cel mai bun, aleator, etc.
Structura unei vecinătăţi poate fi [98]
• liniară: grup complet sau grup incomplet
vecinătate liniară ( distanţa =2 )
grup complet
grup incomplet
57
• bidimensională : cruce completă sau cruce incompletă
Vecinătate bidimensională ( distanţa =1 )
cruce completă cruce incompletă
• tridimensională : stea completă sau stea incompletă
Vecinătate tridimensională ( distanţa =1 )
stea completă stea incompletă
58
Distanţa dintre vecini împreună cu structura aferentă determină dimensiunea vecinătăţii. Tabelul următor dă exemplu de dimensiuni ale vecinătăţii pentru o structură dată, în funcţie de valorile distanţei
distanţastructura
grup complet
grup incomplet
cruce completă
cruce incompletă
stea completă
stea incompletă
Între indivizii unei populaţii există o izolare prin distanţă.
Totuşi, datorită suprapunerii vecinătăţilor au loc schimburi de informaţii între toţi indivizii. Dimensiunea vecinătăţii determină viteza de propagare a informaţiei între indivizii unei populaţii, trebuind ales între propagarea rapidă şi menţinerea unei diversităţi crescute în cadrul populaţiei. O diversitate mare este adesea dorită, prevenindu-se astfel probleme cum ar fi convergenţa prematură spre un minim local.
Selecţia locală într-o vecinătate mică este mai performantă decât cea într-o vecinătate mare. Vecinătatea bidimensională cu structură stea incompletă şi distanţa 1 este recomandată în majoritatea cazurilor. Dacă populaţia este mare (peste 100 indivizi) se recomandă o distanţă mai mare şi o altă vecinătate bidimensională.
59
3.9. Compararea metodelor de selecţie
Numărul de generaţii necesar asigurării convergenţei unui algoritm genetic este invers proporţional cu intensitatea selecţiei şi
direct proportional cu n , unde n este dimensiunea funcţiei obiectiv.
Această cerinţă sugerează o intensitate a selecţiei mare, pentru a avea o schemă de selecţie bună. Totuşi, o intensitate mare duce la o convergenţă prematură şi la o calitate slabă a soluţiei.
Numărul de generaţii necesar atingerii convergenţei, pentru câteva scheme de selecţie, este [98]:
• selecţia după rang: ( )12 −=
RangRang esSelPr
nGenConv π
• selecţia trunchiată: Trunc
Ttrunc IntSelnGenConv
∗=
2π
• selecţia turneu:
)log(14.4log)log(22 TurTurnGenConvTur
∗−=π
unde am folosit notaţiile:
- GenConv = numărul de generaţii care asigură convergenţa
- PresSel = presiunea selecţiei
- IntSel = intensitatea selecţiei.
4 OPERATORI GENETICI
4.1. Încrucişarea Încrucişarea permite combinarea informaţiilor provenite de la
doi sau mai mulţi părinţi pentru generarea unuia sau mai multor urmaşi. Încrucişarea depinde de modul de codificare a datelor, aplicându-se direct asupra cromozomilor [15, 16, 60, 98].
4.1.1. Încrucişarea binară Acest operator crează descendenţi prin combinarea unor părţi alternative ale părinţilor. 4.1.1.1. Încrucişarea simplă
Dacă N este numărul poziţiilor binare ale unui individ, poziţia de încrucişare { }121 −∈ N,,,k L este selectată uniform şi aleator iar
valorile situate la dreapta acestui punct sunt schimbate între cei doi indivizi, rezultând doi descendenţi.
62
}
părinţi descendenţi
Figura 4.1
Ca exemplu [98], considerăm următorii părinţi, având 11 biţi fiecare, şi poziţia de încrucişare 5
p1: 0 1 1 1 0 0 1 1 0 1 0 p2: 1 0 1 0 1 1 0 0 1 0 1
Rezultă descendenţii :
d1: 0 1 1 1 0| 1 0 0 1 0 1 d2: 1 0 1 0 1| 0 1 1 0 1 0
4.1.1.2. Încrucişarea multiplă
În acest caz, se folosesc puncte de încrucişare
alese aleator, diferite între ele şi sortate crescător.
Valorile aflate între puncte de încrucişare consecutive sunt schimbate între cei doi părinţi pentru a obţine doi descendenţi.
1>m
{ 121 −∈ N,,,ki L
63
părinţi descendenţi
Figura 4.2
De exemplu [98], indivizii p1: 0 1 1 1 0 0 1 1 0 1 0 p2: 1 0 1 0 1 1 0 0 1 0 1
cu 3 puncte de încrucişare date de poziţiile : 2, 6, 10 generează descendenţii
d1: 0 1| 1 0 1 1| 0 1 1 1| 1 d2: 1 0| 1 1 0 0| 0 0 1 0| 0
Ideea încrucişării multiple este aceea că părţi ale cromozomilor care contribuie la îmbunătăţirea performanţei unui individ nu este necesar să fie conţinute în subşiruri adiacente. Mai mult, încrucişarea multiplă pare să încurajeze explorarea în spaţiul de căutare mai degrabă, decât să favorizeze convergenţa rapidă către indivizii de elită.
4.1.1.3. Încrucişarea uniformă Încrucişarea simplă sau multiplă permite ca punctele de încrucişare să fie plasate de la prima la penultima poziţie a
64
cromozomului. Încrucişarea uniformă generalizează această schemă permiţând şi ultimei poziţii să fie punct de încrucişare. O mască de încrucişare, de aceeaşi lungime cu a indivizilor este creată aleator, iar paritatea biţilor din mască indică părintele care va furniza descendentul corespunzător biţilor respectivi. Considerăm părinţii [98]
p1: 0 1 1 1 0 0 1 1 0 1 0 p2: 1 0 1 0 1 1 0 0 1 0 1
Descendentul 1 este obţinut luând bitul din părintele 1 dacă bitul corespunzator din mască este 1 şi bitul din părintele 2 dacă bitul corespunzător din mască este 0. Descendentul 2 este creat inversând masca. Considerând măştile
masca 1: 0 1 1 0 0 0 1 1 0 1 0 masca 2: 1 0 0 1 1 1 0 0 1 0 1
indivizii anteriori dau următorii descendenţi:
d1: 1 1 1 0 1 1 1 1 1 1 1 d2: 0 0 1 1 0 0 0 0 0 0 0
Spears şi De Jong [87] au emis ipoteza că încrucişarea uniformă poate fi parametrizată prin aplicarea unei probabilităţi interschimbării biţilor.
65
4.1.1.4. Încrucişarea amestecată Acest tip de încrucişare este similar celei simple: se selectează
o singură poziţie de încrucişare, dar înainte ca valorile să fie schimbate între ele sunt amestecate aleator în ambii părinţi.
4.1.1.5. Algoritmul de încrucişare
Fie populaţia curentă şi )(tP sP populaţia aleasă în urma
operaţiei de selecţie. Asupra indivizilor din sP se aplică operatorul de încrucişare cu probabilitatea (indicele c provine de la termenul
crossover, folosit în limba engleză pentru încrucişare ). cp
Algoritmul
P1. Pentru fiecare individ din sP : • se generează un număr aleator [ ]1,0∈q
• dacă atunci individul respectiv este reţinut pentru cpq <
încrucişare; în caz contrar nu participă la această operaţie.
P2. Fie m numărul indivizilor reţinuţi la pasul P1.
• dacă este număr par, se formează aleator m2m perechi.
• dacă este impar atunci, în mod aleator, se şterge un individ m
selectat sau se adaugă unul nou la sP , apoi se formează
66
perechile.
P3. Perechile formate anterior sunt supuse operaţiei de încrucişare. • pentru fiecare pereche se stabilesc aleator punctele de încrucişare lkk ii <≤1, , unde l este lungimea unui
cromozom. • se execută încrucişarea pentru perechea curentă, descendenţii devenind membri ai generaţiei urmatoare )1( +tP , iar părinţii se
şterg din ( )tP
• se adaugă la )1( +tP indivizii rămaşi în . )(tP
Observaţie
Probabilitatea de încrucişare are valori mici, de regulă în intervalul [0.2, 0.95]; 3.0=cp înseamnă că 30% din indivizi vor
suferi încrucişări.
4.1.2. Încrucişarea reală
4.1.2.1. Încrucişarea discretă
Acest operator efectuează un schimb de valori între variabilele părinţilor şi poate fi folosit cu orice tip de variabile (binare, reale sau simboluri). Considerăm următorii părinţi [98]
p1: 12 25 5
67
p2: 123 4 34 Pentru fiecare variabilă, părintele care contribuie cu variabilă la generarea descendenţilor, este ales aleator cu probabilitate egală; de exemplu
alegere pentru descendentul 1: 2 2 1 alegere pentru descendentul 2: 1 2 1
Noii indivizi creaţi după încrucişare sunt d1: 123 4 5 d2: 12 4 5
În figura următoare sunt prezentate poziţiile posibile ale descendenţilor după încrucişarea discretă :
descendent posibilvariabila 1
părinţi
variabila 2
Figura 4.3
68
4.1.2.2. Încrucişarea intermediară
Este o metodă aplicabilă numai variabilelor reale; în acest caz
valorile variabilelor descendenţilor sunt alese în jurul şi între valorile corespunzătoare ale părinţilor [98]. Descendenţii sunt generaţi după regula: descendent = părinte1 + α (părinte 2 - părinte1) unde α este un factor de scalare ales uniform şi aleator în intervalul
. În încrucişarea intermediară simplă [ +1 ]dd− , 0=d iar în
încrucişarea intermediară extinsă ; o alegere bună este
0>d25.0=dFiecare variabilă din descendent este rezultatul combinării
variabilelor corespunzătoare ale părinţilor conform formulei anterioare, cu o nouă valoare α pentru fiecare variabilă. În figura următoare se prezintă zonele în care iau valori părinţii şi descendenţii lor :
părinte 2 părinte 1
aria părinţilor zona posibilă a descendeţilor
Figura 4.4
69
Considerăm următorii părinţi, cu trei variabile fiecare:
p1: 12 25 5 p2: 123 4 34 şi următoarele valori ale lui α corespunzătoare celor doi descendenţi:
exemplul 1: 0.5 1.1 - 0.1 exemplul 2: 0.1 0.8 0.5
Rezultă următorii descendenţi
d1: 67.5 1.9 2.1 d2: 23.1 8.2 19.5
Încrucişarea intermediară este capabilă să producă orice punct în interiorul unui hipercub mai mare decât cel definit de părinţi, aşa cum arată figura următoare
zona descendentilor
posibil descendent variabila 2
părinte
variabila 1
Figura 4.5
70
4.1.2.3. Încrucişarea liniară Încrucişarea liniară este similară celei intermediare, cu
deosebirea că o singură valoare a lui α este utilizată pentru toate variabilele. Considerând părinţii [98]
p1: 12 25 5 p2: 123 4 34
şi α corespunzător celor doi descendenţi dat de
exemplul 1: 0.5 exemplul 2: 0.1
rezultă următorii descendenţi
d1: 67.5 14.5 19.5 d2: 23.1 22.9 7.9
Încrucişarea liniară poate genera orice punct aflat pe linia definită de părinţi:
Figura 4.6
variabila 2
variabila 1
posibil descendent
părinte
linia posibilului descendent
71
4.1.3. Încrucişarea adiacentă Acest tip de încrucişare [60] este specific reprezentării
adiacente, iar o problemă tipică pentru care se utilizează este cea a comis voiajorului.
4.1.3.1. Încrucişarea prin muchii alternante
Acest tip de încrucişare construieşte un descendent prin
alegerea aleatoare a unui nod (oraş) din primul părinte apoi selectează nodul corespunzător din al doilea părinte; adică, traseul se extinde prin alegerea nodurilor în mod alternativ din cei doi părinţi. Dacă un nod nou introduce un ciclu în traseul curent, operatorul de încrucişare va selecta în locul lui – în mod aleator – un nod dintre cele rămase şi care nu introduce cicluri. De exemplu, din părinţii
p1: 651497832
p2: 348296157
care reprezintă treseele
746958321 −−−−−−−−
şi respectiv
395264871 −−−−−−−−
se obţine descendentul
72
d1: 346197852
care reprezintă traseul
674839521 −−−−−−−− .
Se procedează astfel: oraşul 2 aflat pe poziţia 1 în p1 se introduce în d1 pe poziţia 1. Pe poziţia 2 în p2 se află oraşul 5, care va ocupa poziţia 2 în d1. Pe poziţia 5 în p1 se află oraşul 9, care se introduce în descendent pe poziţia 5, şi aşa mai departe; în final se introduce aleator muchia ( )6,7 în loc de ( )8,7 care ar fi introdus un ciclu
prematur. 4.1.3.2. Încrucişarea prin subtrasee
Specificul acestei încrucişări constă în faptul că generează un
descendent alegând alternativ câte un subtraseu din fiecare părinte; lungimea fiecărui subtraseu este aleatoare. Frecvent se lucrează cu subtrasee de lungime 1, deci traseul se extinde prin alegerea alternativă a muchiilor din cei doi părinţi. Dacă ultima muchie selectată introduce un ciclu prematur, se selectează în locul ei una nouă dintre cele rămase şi care nu introduce cicluri.
4.1.3.3. Încrucişarea euristică Aceasta construieşte un descendent prin alegerea aleatoare a
unui oraş ca punct de start pentru traseul descendentului. Apoi
73
compară cele două muchii (din cei doi părinţi) care pleacă din acest oraş şi selectează pe cea mai bună (scurtă). Oraşul de la celălalt capăt al muchiei selectate va deveni punct de start pentru selectarea următoarei muchii. Dacă la un anumit moment, o muchie nouă introduce un ciclu în traseul parţial atunci aceasta se va înlocui cu alta aleasă aleator din cele rămase şi care nu introduce cicluri.
În [49] se modifică încrucişarea euristică astfel: dacă cea mai scurtă muchie a unui părinte introduce un ciclu în traseul descendentului atunci se alege următoarea muchie mai scurtă dintre cele rămase; dacă aceasta nu introduce cicluri se acceptă în vederea extinderii traseului iar în caz contrar se selectează cea mai scurtă muchie dintre muchii selectate aleator, unde q este un parametru al
metodei. Efectul acestui operator constă în “alipirea” drumurilor scurte din traseele părinţilor. Totuşi, această metodă poate duce la încrucişări nedorite; de aceea, în [88] a fost introdus un operator euristic suplimentar care acţionează astfel:
q
• selectează aleator două muchii ( )ji, şi ( )lk,
• dacă ( ) ( ) ( ) ( jkdlidlkdjid ,,,, )+>+
atunci muchiile ( )ji, şi ( )lk, se înlocuiesc cu muchiile ( )li, şi
. ( )jk,
Principalul dezavantaj al reprezentării adiacente constă în
74
faptul că rezultatele furnizate de operatori sunt relativ sărace. Încrucişarea muchiilor alternante duce, adeseori, la distrugerea traseelor bune. Încrucişarea prin subtrasee este mai bună decât cea a muchiilor alternante deoarece rata distrugerii este mai mică dar performanţele sunt încă slabe. Prin faptul că dintre două muchii se alege cea mai scurtă, încrucişarea euristică este mai bună decât celelalte două. Totuşi, performanţele sale nu sunt spectaculoase: în trei experimente [41] cu 50, 100 şi 200 de oraşe au fost găsite trasee aflate la o distanţă mai mică de 25%, 16% şi 27% de traseul optim, după un număr de 15.000, 20.000 şi respectiv 25.000 generaţii.
4.1.4. Încrucişarea ordinală
Principalul avantaj al reprezentării ordinale constă în faptul că permite încrucişarea clasică. Oricare doi părinţi pot fi încrucişaţi cu orice punct de tăietură şi produc descendenţi care reprezintă trasee legale [60]. De exemplu, părinţii
p1: 1 1 2 1 | 4 1 3 1 1 p2: 5 1 5 5 | 5 3 3 2 1
care corespund traseelor
769583421 →→→→→→→→
236498715 →→→→→→→→
75
dau descendenţii
d1: 1 1 2 1 5 3 3 2 1 d2: 5 1 5 5 4 1 3 1 1
care corespund traseelor
568793421 →→→→→→→→
439268715 →→→→→→→→
Se observă că traseele parţiale situate la stânga punctului de încrucişare (reprezentat prin bara verticală) nu se schimbă în timp ce traseele de la dreapta acestui punct sunt distruse într-un mod destul de aleator. Unele rezultate experimentale ([41]) au arătat că reprezentarea ordinală nu este prea indicată pentru problema comis voiajorului. Rezultatele anterioare au fost obţinute considerăm lista ( )9,8,7,6,5,4,3,2,1=L .
4.1.5. Încrucişarea prin drumuri Trei tipuri de încrucişare sunt utilizate în cazul reprezentării prin drumuri [60]: parţial aplicată (PMX), de ordine (OX) şi ciclică (CX).
4.1.5.1. Încrucişarea PMX A fost propusă de Goldberg şi Lingle [37] şi construieşte un
descendent alegând un subtraseu din unul dintre părinţi şi păstrând
76
ordinea şi poziţia a cât mai multe oraşe din celălalt părinte. Subtraseul este selectat prin alegerea a două puncte aleatoare de taietură care definesc frontierele operaţiei de interschimbare. De exemplu, părinţii
p1: 98|7654|321
şi p2: 39|6781|254
vor produce descendenţi în felul următor. Mai întâi, porţiunea cuprinsă între cele două puncte de tăietură este schimbată între cei doi părinţi, obţinându-se descendenţii:
d1: ∗∗∗∗∗ |6781|
şi d2: ∗∗∗∗∗ |7654|
În acelaşi timp, se obţine aplicaţia
41↔ , 58 ↔ , 67 ↔ şi 76 ↔ .
Apoi, se copiază în locurile libere din cei doi descendenţi elementele corespunzătoare din părinţi, dacă acestea nu generează conflicte; rezultă
d1: 9|6781|32 ∗∗
şi d2: 39|7654|2∗∗
Primul din descendentul d1 (care ar trebui să fie 1, dar această valoare este interzisă deoarece ea există deja în descendent) este
∗
77
înlocuit cu 4, datorită aplicaţiei 41↔ . În mod similar, al doilea ∗ din descendentul d1 este înlocuit cu 5 iar caracterele ∗ din celălalt descendent sunt înlocuite cu 1 şi 8. În final rezultă descendenţii
d1: 95|6724 81|3
54|2
54|3
81|
şi d2: 39|7681
4.1.5.2. Încrucişarea OX
A fost propusă de Davis [12] şi construieşte un descendent alegând un subtraseu în unul dintre părinţi şi păstrând ordinea relativă a oraşelor din celălalt părinte. De exemplu, părinţii
p1: 98|7621
şi p2: 39|67254
vor produce descendenţi în felul următor. Mai întâi, porţiunile dintre punctele de tăietură sunt copiate în cei doi descendenţi
d1: ∗∗∗∗∗ |76| 54
d2: ∗∗∗∗∗ |67| 81
Apoi, pornind de la al doilea punct de tăietură al unuia dintre părinţi se copiază oraşele din celălalt părinte, păstrând ordinea şi omiţând oraşele care sunt deja prezente; când se ajunge la sfârşitul traseului se
78
continuă cu primul oraş. Şirul oraşelor din al doilea părinte, începând cu al doilea punct de tăietură, este
678125439 −−−−−−−− ;
Eliminând oraşele 4, 5, 6 şi 7, care sunt deja prezente în primul descendent, se obţine
81239 −−−−
Aseastă secvenţă este plasată în primul descendent, începând cu al doilea punct de tăietură, şi rezultă
d1: 39|7654|812 .
Similar se obţine celălalt descendent:
d2: 29|6781|543 .
Pentru încrucişarea OX este importantă ordinea oraşelor şi nu poziţia lor în reprezentare.
4.1.5.3. Variante ale încrucişării OX Este posibil să se definească şi alţi operatori pentru
reprezentarea unui drum. Syswerda [89] a definit două variante ale încrucişării de ordine. Prima modificare ( bazată pe ordine) selectează aleator câteva poziţii iar ordinea oraşelor aflate în poziţiile selectate în
79
unul din părinţi este impusă oraşelor corespunzătoare din celălalt părinte. Ca exemplu, considerăm părinţii
p1: 987654321
p2: 539678214 .
Presupunem că au fost selectate poziţiile 3, 4, 6 şi 9; oraşele aflate pe aceste poziţii în părintele p2 sunt 2, 8, 6 şi 5. Primul descendent se obţine copiind elementele lui p1, cu excepţia poziţiilor 2, 5, 6 şi 8:
d1: 97431 ∗∗∗∗ .
Elementele rămase libere se completează cu elementele din p2, în ordinea stabilită anterior, adică 2, 8, 6, 5; în final rezultă
d1: 957684321 .
În mod similar se obţine celălalt descendent:
d2: 596478213 .
A doua modificare (încrucişarea bazată pe poziţie) seamănă şi
mai mult cu încrucişarea de ordine originală. Singura diferenţă constă în faptul că în locul unui subtraseu ce trebuie copiat în descendent se selectează în mod aleator câteva oraşe.
Este interesant de observat că aceşti doi operatori sunt, în unele cazuri, echivalenţi. Astfel, dacă au ca puncte de încrucişare mulţimi complementare, ei vor produce acelaşi rezultat. Înseamnă că
80
dacă numărul mediu al punctelor de încrucişare este 2m (unde este
numărul oraşelor), cei doi operatori vor avea aceleaşi performanţe.
m
4.1.5.4. Încrucişarea CX A fost propusă de Oliver şi colaboratorii săi [67] şi
construieşte descendenţii astfel încât fiecare oraş (şi poziţia sa) provine din unul din părinţi. Să considerăm părinţii
p1: 987654321
p2: 539678214
Pentru a obţine primul descendent se selectează primul oraş din primul părinte:
d1: ∗∗∗∗∗∗∗∗1
Pe prima poziţie din p2 este 4, ceea ce spune că se introduce în descendent elementul aflat pe poziţia 4 în primul părinte; rezultă
d1: ∗∗∗∗∗∗∗ 41
În continuare, valoarea 8 aflată pe poziţia 4 în p2 determină introducerea elementului aflat pe poziţia 8 în p1:
d1: ∗∗∗∗∗∗ 841
81
Urmând această regulă se introduc oraşele 3 şi 2; dar oraşul 2 determină selectarea lui 1 care este deja introdus în descendent. În acest moment se încheie ciclul de introducere de oraşe din p1:
d1: ∗∗∗∗ 84321
Poziţiile rămase libere se completează cu oraşe din celălalt părinte, obţinându-se
d1: . 589674321
În mod similar se construieşte celălalt descendent
d2: . 937658214
4.1.6. Încrucişarea prin muchii Whitley, Starkweather şi Fuquay [95] au dezvoltat un nou
operator de încrucişare: încrucişarea prin muchii (edge recombination = ER), care explorează informaţia despre muchiile unui traseu transferând peste 95% din muchiile părinţilor într-un singur descendent. Pentru traseul
596478213 −−−−−−−−
definit de părintele
(3, 1, 2, 8, 7, 4, 6, 9, 5),
muchiile sunt
82
( )13 , , , ( )21 ( )82 ( )78 , ( )47 , ( )64 , ( )96 , ( )59 şi ( )35 .
Direcţia dată de o muchie nu este importantă; de exemplu, muchiile şi semnalează faptul că oraşele 1 şi 3 sunt conectate
direct.
( 13 ) ( 31 )
Ideea metodei este de a utiliza pentru fiecare oraş o listă a oraşelor conectate cu el, aflate în cel puţin unul din părinţi. Evident, o listă conţine cel puţin două şi cel mult patru oraşe. De exemplu, pentru părinţii
p1: 987654321
p2: 539678214
listele sunt următoarele oraşul 1: 9, 2, 4 oraşul 2: 1, 3, 8 oraşul 3: 2, 4, 9, 5 oraşul 4: 3, 5, 1 oraşul 5: 4, 6, 3 oraşul 6: 5, 7, 9 oraşul 7: 6, 8 oraşul 8: 7, 9, 2 oraşul 9: 8, 1, 6, 3.
Construirea unui descendent începe prin selectarea unui oraş iniţial al unuia dintre părinţi; în [95] autorii selectează unul din oraşele aflate pe prima poziţie ( 1 sau 4 în exemplul nostru). Se introduce în descendent oraşul care are mai puţine muchii în lista asociată lui; dacă
83
au acelaşi număr atunci se alege unul în mod aleator. Presupunem că am selectat oraşul 1; el este conectat cu 9, 2 şi 4, aşa că următorul oraş este selectat dintre acestea. Oraşele 4 şi 2 au trei muchii iar 9 are 4. Are loc o alegere aleatoare între 4 şi 2; presupunem ca a fost selectat 4. Candidatul pentru noul oraş este ales dintre 3 şi 5; este selectat oraşul 5 care are mai puţine muchii în lista sa. Continuând în acest mod se obţine descendentul
, 932876541
compus în întregime din muchii aflate în cei doi părinţi. O serie de experimente [95] au scos în evidenţă faptul că o muchie ilegală apare destul de rar (cu o rată de 1% până la 1.5%).
4.1.7. Încrucişarea matriceală Acest tip de încrucişare (numit MX) a fost definit în [45], foloseşte unu sau două puncte de încrucişare şi este folosit în cazul reprezentării cu un singur 1 pe fiecare linie şi coloană. După operaţia de încrucişare propriu zisă sunt necesari doi algoritmi de reparare:
• unul pentru a şterge duplicările astfel încât fiecare linie şi coloană să conţină un singur 1
• iar celălalt pentru a lega între ele eventualele subtrasee şi a produce un traseu legal.
84
Următorul exemplu ilustrează încrucişarea cu două puncte. Cei doi părinţi sunt daţi de matricele
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
2 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 1 0 0 0 4 0 0 1 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 1 0 0 5 0 0 0 0 0 0 1 0 0 6 0 0 0 0 1 0 0 0 0 6 0 0 0 0 1 0 0 0 0 7 0 0 0 0 0 0 0 0 1 7 0 1 0 0 0 0 0 0 0 8 0 0 0 0 0 1 0 0 0 8 0 0 0 0 0 0 0 0 1 9 1 0 0 0 0 0 0 0 0 9 1 0 0 0 0 0 0 0 0
şi reprezintă traseele ( )975683421
şi ( )982756341 .
Alegem punctele de încrucişare între coloanele 2 şi 3 şi respectiv între 6 şi 7. Părinţii vor schimba între ei porţiunile cuprinse între cele două puncte şi rezultă următorii descendenţi intermediari:
85
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 1 0 3 0 0 0 0 0 1 0 1 0 3 0 0 0 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 5 0 0 0 0 0 0 1 0 0 5 0 0 0 0 0 0 1 0 0 6 0 0 0 0 1 0 0 0 0 6 0 0 0 0 1 0 0 0 0 7 0 0 0 0 0 0 0 0 1 7 0 1 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 1 0 0 1 9 1 0 0 0 0 0 0 0 0 9 1 0 0 0 0 0 0 0 0
Ambii descendenţi sunt ilegali, deşi numărul total de 1-uri
din fiecare este corect. Primul pas al algoritmului de reparare mută unele valori 1 astfel încât în fiecare linie şi fiecare coloană să fie un singur 1. Astfel:
• pentru primul descendent: se mută 1 din poziţia în poziţia
iar 1 din se mută în 14m
84m 38m 28m
• pentru al doilea descendent: se mută 1 din în iar 1 din
se mută în .
24m 34m
86m 16m
După acest pas al algoritmului de reparare, primul descendent reprezintă traseul valid
( )975634821
iar al doilea descendent defineşte două subtrasee:
86
( )9827561 şi ( )43 .
Al doilea pas al algoritmului de reparare se aplică numai celui de-al doilea descendent. Pentru aceasta se selectează o muchie existentă în unul dintre părinţi şi se utilizează pentru a face joncţiunea între cele două subtrasee; fie aceasta ( . Traseul legal pentru al
doilea descendent este:
)42
( )983427561 .
4.2. Mutaţia
Mutaţia este cel mai simplu operator genetic şi constă în
schimbarea aleatoare a unor valori ale cromozomului pentru a introduce noi soluţii. Scopul său este de a împiedica pierderea ireparabilă a diversităţii, evitând, astfel, convergenţa prematură. Diversitatea permite explorarea unor zone largi din spaţiul de căutare. Mutaţia foloseşte ca parametru probabilitatea de mutaţie , care ia
valori mici; de obicei în intervalul
mp
[ ]01.0,001.0 .
4.2.1. Mutaţia binară
Dacă este dimensiunea populaţiei iar l este lungimea unui cromozom atunci numărul mediu de biţi ce vor suferi mutaţie este
n
87
mplnN ⋅⋅= . Mutaţia binară poate fi implementată sub mai multe
forme [16].
4.2.1.1. Mutaţia tare
Pentru fiecare poziţie a fiecărui cromozom se execută paşii: P1: se generează un număr aleator [ ]1,0∈q
P2: dacă atunci se schimbă poziţia respectivă, în caz contrar mpq <
nu se efectuează nimic.
4.2.1.2. Mutaţia slabă
Pentru fiecare poziţie a fiecărui cromozom se execută paşii: P1: se generează un număr aleator [ ]1,0∈q
P2: dacă atunci se alege aleator una din valorile sau 1 şi se mpq <
t
0
atribuie poziţiei curente, în caz contrar nu se efectuează nimic.
4.2.1.3. Mutaţia neuniformă
Probabilitatea de mutaţie depinde de generaţie, descrescând cu indicele al acesteia. Dacă este probabilitatea de mutaţie la prima
generaţie iar 0p
1≥β este un parametru real atunci probabilitatea de
mutaţie la generaţia t va fi t
m eptp β−= 0)( .
88
Bäck şi Schütz [10] au definit o nouă probabilitate de mutaţie:
tT
ltpm 22
1)(−
+= ,
unde este lungimea unui cromozom iar l T este numărul maxim de generaţii.
4.2.1.4. Mutaţia auto-adaptivă
Bäck şi Schütz [10] au definit un mecanism de auto-adaptare pentru probabilitatea de mutaţie . Ideea constă în încorporarea
parametrului de mutaţie în genotipul indivizilor. Un genotip mp
g are
forma , unde ( mpxg ,= ) { }l1,x 0= este vectorul de căutare iar
. [ ]1,0∈mp
Prin mutaţie, genotipul ( )mpx, se transformă în ( )mpx ','
conform relaţiilor
( )1,011
1'N
m
mm
ep
pp⋅−−
+=
γ,
⎩⎨⎧
<−≥
=mi
mii pqdacăx
pqdacăxx
'1'
'
unde
89
) • este o realizare a variabilei aleatoare de medie 0 şi
dispersie 1
( 1,0N
• γ este rata de învăţare; o valoare recomandată este 2.0=γ
• este componenta vectorului ix x care este supusă mutaţiei
• este un număr aleator. [ 1,0∈q ]
)
Schema anterioară poate fi generalizată prin alocarea pentru fiecare variabilă a unei probabilităţi de mutaţie proprie . În acest
caz genotipul este de forma cu
ix ip
( pxg ,= ( )lpp ,Lp ,1= .
Probabilitatea de mutaţie se modifică după regula
( ){ }l,,,i,
ep
p'p,N
i
ii
i
L2111
110
∈−
+=
⋅−γ.
4.2.1.5. Mutaţia cromozomială
În această variantă, mutaţia are loc la nivelul a una sau mai
multe gene dintr-un singur cromozom. Se poate utiliza oricare din variantele de mutaţie prezentate anterior.
90
)
4.2.2. Mutaţia reală Considerăm cromozomi cu gene exprimate prin numere reale, pentru fiecare genă cunoscându-se domeniul valorilor posibile.
n
4.2.2.1. Mutaţia uniformă
Acest tip de mutaţie înlocuieşte o singură genă a unui cromozom selectat cu un număr real generat aleator în domeniul parametrului reprezentat de acea genă [16]. Se consideră că toate genele au aceeaşi probabilitate de mutaţie. Dacă ,,( 1 nxxx L= este
un cromozom părinte, se alege aleator gena i ce va fi supusă mutaţiei
şi se obţine descendentul ),',,(' 1 ni xxxx L ,L= , unde valoarea
este aleasă aleator din domeniul parametrului de pe poziţia i . ix'
O variantă de mutaţie uniformă este cea care perturbă toate genele cromozomului. Această operaţie se poate efectua în mai multe moduri:
• mutaţia aditivă normală:
( )iiii Nxx σα ,0' ⋅+= , { }ni ,,1 L∈
unde iα este un parametru real iar ( iN )σ,0 reprezintă un număr
aleator cu repartiţia normală de medie 0 şi dispersie iσ . De obicei se
lucrează cu σσ =i şi ,αα =i { }n,i ,1 L∈ .
• mutaţia multiplicativă:
91
( )iii Nxx σ,0' ⋅= , { }ni ,,1 L∈
• mutaţia multiplicativă lognormală:
( )i,Nii ex'x σβ 0⋅⋅= , { }ni ,,1 L∈
cu β parametru real.
4.2.2.2. Mutaţia neuniformă
Prin această operaţie, genele suferă modificări importante în primele generaţii şi descresc treptat, până la atenuare, în generaţiile următoare. Astfel se permite o explorare uniformă a spaţiului de căutare în primele generaţii şi o căutare locală, datorată variaţiilor mici, în ultimele generaţii [16].
Creşterea sau descreşterea valorii unei gene este dată de un parametru aleator 1: =pp indică o creştere a valorii iar 1−=p
indică o descreştere. Amplitudinea schimbării este dată de funcţia
{ } [ )1,0,,1,0: →Th L
cu proprietăţile 1) este descrescătoare h2) 0)( =Th
unde T este numărul maxim de iteraţii. Un exemplu de astfel de funcţie este
92
b
Tt
rth⎟⎠⎞
⎜⎝⎛ −
−=1
1)( ,
unde r este un parametru aleator din ar este un parametru
ce determină gradul de neuniformitate. În acest tip de mutaţie gena se transformă astfel:
]1,0[ i 1≥b
i
( ) )(' max thxxxx iii ⋅−+= dacă 1=p
( ) )(' min thxxxx iii ⋅−−= dacă 1−=p
unde şi reprezintă cea mai mare şi respectiv cea mai mică
componentă a lui maxx minx
x .
4.2.2.3. Mutaţia auto-adaptivă
Acest tip de mutaţie este specific strategiilor evolutive şi lucrează la nivelul unui genotip ( )σ,xg = , unde x este variabila
obiect (fenotipul) iar σ este vectorul parametrilor strategiei. Mutaţia de acest tip se poate efectua în mai multe feluri [16]:
• parametrii strategiei se modifică folosind metoda multiplicativă lognormală
( ) ( )1010 ,Nb,Naii
ie' ⋅+⋅= σσ ,
sau folosind metoda aditivă ( )iiii N σασσ ,0' +=
93
unde , b şi a iα sunt parametrii reali ai metodei
• variabilele obiect se modifică folosind metoda aditivă
( )iii Nxx ',0' σ+= .
4.2.3. Mutaţia întreagă Este similară mutaţiei uniforme din cazul real şi se poate
aplica astfel:
• prin înlocuirea unei valori cu alta aflată în domeniul genei care suferă mutaţia
• prin adăugarea sau scăderea la fiecare genă a unei valori mici, fără a se depăşi domeniul de valori al genei respective.
4.2.4. Mutaţia specifică
În cazul reprezentării specifice [ 60] mutaţia nu mai poate acţiona independent asupra fiecărei gene. Cele mai cunoscute tipuri de mutaţie folosite în acest caz sunt:
• mutaţia prin schimbare, prin care se selectează aleator două gene ale cromozomului şi se schimbă între ele valorile; de exemplu, plecând de la cromozomul
( )9865421 73
94
şi alegând genele (poziţiile) 3 şi 7 rezultă cromozomul
( )9865421 37
• mutaţia prin inserare: se aleg aleator două gene şi apoi una dintre ele se inserează lângă cealaltă; de exemplu, din
( )9865421 73
şi poziţiile 3 şi 7 se obţine
( )9865421 73 .
• mutaţia prin amestec: se alege în mod aleator o porţiune din cromozom şi se amestecă valorile din această zona; de exemplu, plecând de la cromozomul
( )98721 6543
se poate obţine
( )98721 4635 .
• mutaţia prin inversiune: se aleg aleator două poziţii din cromozom şi se inversează valorile situate în zona definită de acestea; de exemplu, alegând cromozomul
( )98721 6543
şi poziţiile 3 şi 6 se obţine
( )98721 3456 .
95
4.3. Reinserţia
Odată ce un nou descendent a fost obţinut prin operaţiile de selectie, încrucişare şi/sau mutaţie trebuie decis dacă el va face parte sau nu din noua generaţie; pentru aceasta se utilizează o schemă de reinserţie. Metoda de selecţie utilizată determină schema de inserţie ce va fi folosită: reinserţie locală pentru selecţia locală şi reinserţie globală în cazul tuturor celorlalte metode de selecţie.
4.3.1. Reinserţia globală Există diferite scheme de reinserţie globală:
• reinserţia pură: se produce un număr de descendenţi egal cu cel al părinţilor, ceea ce determină înlocuirea tuturor părinţilor cu descendenţii lor
• reinserţia uniformă: se produc mai puţini descendenţi decât părinţi şi se înlocuiesc unii părinţi uniform şi aleator
• reiserţia elitistă: se produc mai puţini descendenţi decât părinţi, iar părinţii mai puţin performanţi sunt înlocuiţi de descendenţi
• reinserţia bazată pe fitness: se produc mai mulţi descendenţi decât sunt necesari şi se reinserează descendenţii cei mai buni.
Reinserţia pură este cea mai simplă metodă, fiecare individ trăind o singură generaţie. Combinarea între reinserţia elitistă şi cea
96
bazată pe fitness previne pierderea de informaţie şi este metoda recomandată. La fiecare generaţie, un număr dintre părinţii cei mai neperformanţi sunt înlocuiţi cu descendenţii cei mai buni. Schema de inserţie bazată pe fitness implementează selecţia trunchiată între descendenţi, indivizii elitişti putând trăi mai multe generaţii. Totuşi, la fiecare generaţie sunt inseraţi câţiva indivizi noi. Deoarece părinţii pot fi înlocuiţi prin descendenţi cu fitness mic, fitnessul mediu al populaţiei poate descreşte. Totuşi, dacă descendenţii inseraţi sunt extrem de neperformanţi ei vor fi înlocuiţi în generaţiile următoare.
4.3.2. Reinserţia locală
În selecţia locală indivizii sunt căutaţi într-o vecinătate mărginită. Reinserţia descendenţilor are loc exact în aceeaşi vecinătate şi, astfel, caracterul local al informaţiei se păstrează. Structurile de vecinătate sunt aceleaşi ca la selecţia locală. Pentru selectarea părinţilor ce vor fi înlocuiţi şi a descendenţilor de inserat sunt posibile următoarele scheme:
• se inserează orice descendent şi se înlocuiesc indivizii din vecinătate în mod uniform şi aleator
• se inserează orice descendent şi se înlocuiesc indivizii cei mai neperformanţi din vecinătate • se inserează individul mai bun decât cel mai slab individ din vecinătate şi se elimină individual cel mai slab
97
• se inserează descendentul mai bun decât individul cel mai neperformant din vecinătate şi se înlocuiesc indivizii din vecinătate uniform şi aleator
• se inserează indivizii mai buni decât părinţii şi se înlocuiesc părinţii.
5 FUNCŢIONAREA ALGORITMILOR GENETICI
Pentru a rezolva o problemă cu ajutorul algoritmilor genetici, trebuie ţinut cont de următoarele observaţii.
• Problema trebuie transformată mai întâi într-una de optimizare, adică să se minimizeze sau să se maximizeze o valoare.
• Algoritmii genetici sunt algoritmi euristici, adică soluţia găsită de ei nu este întotdeauna cea mai bună, dar se află într-o vecinătate a soluţiei optime. Deci, dacă avem de ales între un algoritm polinomial care rezolvă sigur problema şi un algoritm genetic, ar fi de preferat să folosim algoritmul polinomial.
• Algoritmii genetici, de obicei, au complexitate polinomială. De aceea ei sunt foarte des utilizaţi pentru a rezolva problemele dificile (NP-complete). Rezultatele obţinute sunt foarte apropiate de cele furnizate de algoritmii siguri, dar care au rulat un timp foarte mare.
100
• Dacă problema este complexă se recomandă un algoritm genetic şi nu o strategie evolutivă. De obicei mutaţia este un operator de căutare slab, deci, dacă se foloseşte doar acesta, există şanse mari să se obţină soluţii locale şi nu globale.
5.1. Maximizarea unei funcţii
Explicăm funcţionarea algoritmilor genetici pentru o problemă de maximizare deoarece minimizarea funcţiei este echivalentă cu
maximizarea funcţiei
f
fg −= . În plus, presupunem că funcţia obiectiv
ia valori pozitive, în caz contrar putându-se aduna o constantă
pozitivă C şi maximizându-se
f
Cf + .
Presupunem că se doreşte maximizarea unei funcţii de variabile
k
RRf k →: ;
fiecare variabilă ia valori într-un domeniu ix
[ ] RbaD iii ⊂= ,
şi ( ) 0,,1 >kxxf L pentru ii Dx ∈∀ .
Cerând o precizie de p zecimale pentru valorile variabilelor, fiecare
interval va trebui divizat în iD ( ) pii ab 10⋅− subintervale egale. Fie
cel mai mic întreg astfel încât il
( ) 1210 −≤⋅− ilpii ab .
101
ntare a variabilei ca un şir binar de
lungim
Atunci, o repreze i x
e il va satisface precizia dorită. În plus, are loc formula
( )12
2−
−⋅+= ii
iiabstringzecimalax
il
unde ) reprezintă valoarea zecimal şirului binar (strinzecimal ă a 2g
string .
Acum fiecare cromozom este reprezentat printr-un şir binar de
lungime ∑=k
ill ; primii 1l biţi reprezintă o valoare din =i 1
[ ]11, ba ,
următorii eprezintă valoare din 2l biţi r o [ ]22 , ba şi aşa mai d .
Populaţia iniţială constă din n cromozomi ale leator. Totuşi dacă avem informaţii despre optim l potenţial, ele pot fi utilizate pentru a genera populaţia iniţială. În continuare algoritmul funcţionează astfel:
• se evaluează fiecare cromozom al fiecărei generaţii, utilizând
eparte
şi au
se ectează noua populaţie conform distribuţiei de probabilitate
ozomii din noua populaţie prin operatori de
de generaţii, când nu mai sunt observate îmbunătăţiri substanţiale, cel mai bun cromozom este selectat ca
funcţia f
• se lbazată pe fitness
• se modifică crommutaţie şi încrucişare
• după un număr
102
rocesul de selecţie vom utiliza tehnica ruletei:
se calculează fitnessul
soluţie optimă; deseori algoritmul se opreşte după un număr finit de iteraţii. Pentru p
( )veval • i
niv
pentru fiecare cromozom
• ăseşte fitnessul total
• se calculează probabilitatea de selecţie pentru fiecare
romozom
i ,,2,1, L=
se g
( )∑=
=n
iivevalF
1
ip
nivi ,,2,1, L= :
( )c
Fveval
ip i=
• se calculează probabilitatea cumulată pentru fiecare cromozom
Procesul de selecţie constă în f losirea ruletei de ori; de fiecare dată se selectează un singur cromozom astfel:
• se g
iq
nivi ,,2,1, L= :
∑=
=j
ji pq1
i
o n
enerează un număr aleator [ ]1,0∈a
103
mul cromozom; altfel se selectează • dacă 1qa < , se selectează pri
cromozom niul vi ≤≤2 , astfel încât ii qaq, ≤<−1 .
Este evident că unii cromozomi vor fi selectaţi de mai multe
ori, cromozomii cei mai buni generând mai multe copii. După selecţie se aplică operatorul de încrucişare. Folosind
probabilitatea de încrucişare cp se determină numărul npc ⋅ de
cromozomi supuşi încrucişării. Se procedează astfel, pentru fiecare cromozom din noua populaţie:
• se generează un număr aleator [ ]1,0∈a
• dacă cpa < , cromozomul curent se selectează pentru
ntinuare se împerechează aleator cromozomii şi pentru
încrucişare.
În cofiecare pereche se generează un numar aleator întreg [ ]1,1 −∈ lpos , l
fiind lungimea unui cromozom iar pos este poziţia
Doi cromozomi
de încrucişare.
lpospos bbbbb LL 121 +
şi
sunt înlocuiţi prin descen ţii
lpospos ccccc LL 121 +
den
bb L21 lpospos ccb L1+
104
şi .
Se aplică, apoi, operatorul de mutaţie. Probabilitatea de mutaţie dă
romozom
lpospos bbccc LL 121 +
mp
numărul nlpm ⋅⋅ al biţilor ce vor suferi mutaţie. Pentru fiecare bit al
fiecărui c au loc operaţiile:
• se generează un număr aleator [ ]1,0∈a
• dacă mpa < , bitul va suferi mutaţie.
În urma operaţiilor de selecţie, încrucişare şi mutaţie, noua popula
Următorul exemplu [60] ne arată modul de funcţionare. Presup
ţie este gata pentru următoarea evaluare.
unem că vrem sa maximizăm funcţia
( ) ( ) ( )22 20sin x1121 4sin5.21, xxxxxf π +⋅+= ⋅ π
unde 1.120.3 1 ≤≤− x şi 8.51.4 2 ≤≤ x .
Vom lucra cu o populaţie de dime nensiu 20=n
mutaţie
, cu probabilitatea de
încrucişare 25.0=cp şi probabilitatea de 01.0=mp .
Cerem ca p fie de patru zecimale pentr varecizia să u fiecare riabilă. Deoarece domeniul lui 1x are lungimea 1.15 , precizia cerută implică
divizarea intervalului [ ]1.12,0.3− în cel p 4101.15 ∗ subintervale uţin
ţegale. Înseamnă că bi ezenta prima sun necesari t 18 i pentru a repr
105
i: omeniul
i
.
parte a cromozomulu 1821000 ≤ . D lui 2x are
lungimea 7.1 iar precizia impusă etermină împărţirea intervalului
[ ]8.5,1.4 în cel puţin 7.1 ∗ gale. Înseamnă că ntru
partea a doua a cromozomului vor fi utilizaţi 15 biţi: 15200 ≤ . L totală a unui cromozom este
331518 =+=l biţi; Primii 18 biţi codifică pe 1x iar ult 15 pe
, cromozomu
17 152 <
d410 subintervale e
gimea
l
11100101001101000011
110100000100010010
( )
pe
i
14 1702 <
2x .
Fie, de e
tă
un
mi
xemplu
0100100010010
Primii 18 biţi
reprezin pe ( )
=−
−−⋅110100000100010010 2+−= 031 .x
10312 ..
21
18zecimal
052426.1262143
.15 . 052426.40.3 =+−=
000101111100101
170352
15 bi
e
0.3 +−=
Următorii
⋅
ţi
reprezintă p
= 4. =+11481 152
-.-
25) .000101111100101(2x zecimal
5.75533.31906 1.6553304.132767
1.7+=4.1= =+
106
Astfel cromozomul
corespunde valorilor
010111001010011010000110100010010
)75533050524261()( 21 .,.x,x = .
Valoarea fitnessului pentru acest cromozom este
052421( .f 2526420)75533056 .., = .
Iniţializăm o populaţie cu 20 de cromozomi şi 33 de biţi fiecare, aleşi aleator, şi obţinem
)111101001101100001111111001101000(1 = v
)010101010001100110111001110001001(2 =v
1101)01010111010110010000(0000100003 =v
0010)11000001111011010011(1000110004 =v
0101)10111111000010100110(0001110115 =v
1011)01010111110100101010(0001010006 =v
1011)11011011110001101011(0010001007 =v
0111)10110101100011101000(1000011008 =v
1100)10000001111011000101(0100000009 =v
1011)11010000110001100000(00000111110 =v
1000)00001101111101101011(01100111111 =v
0000)00101010001111011010(11010001012 =v
107
0110)10000001000100010001(11101111113 =v
1001)00111100100000010101(01001001114 =v
1110)00011111011011100001(111011101v15 =
1011)00001101000000111111(11001111016 =v
1101)10001101111110011110(01101011117 =v
1101)00111110100000011101(01110100018 =v
1100)10000110000111111111(00010101019 =v
1110)11000101111100111100(10111001020 =v
Decodificând fiecare cromozom şi evaluând fitnessul obţinem:
( ) 01960026)65224250844926(1 ..,.fveval ==
( ) 5800157)380264434843410(2 ..,.fveval ==
( ) 52632919)39038145166032(3 ..,.-fveval ==
( ) 40672517)59346052786385(4 ..,.fveval ==
( ) 34116025)73445842551731(5 ..,.-fveval ==
( ) 10041718)39193748117251(6 ..,.-fveval ==
( ) 02081216)68025859914710(7 ..,.-fveval ==
( ) 95970117)70301849106184(8 ..,.fveval ==
( ) 12779916)38147257954060(9 ..,.fveval ==
( ) 21.2784354.793707),(-2.55485110 == fveval
108
( ) 23.4106694.996097)(3.130078,11 == fveval
( ) 15.0116194.239457)(9.356179,12 == fveval
( ) 27.3167025.378671),(11.13464613 == fveval
( ) 19.8762945.151378)(1.335944,14 == fveval
( ) 30.0602055.054515),(11.08902515 == fveval
( ) 23.8672274.993762)(9.211598,16 == fveval
( ) 13.6961654.571343)(3.367514,17 == fveval
( ) 15.4141285.158226)(3.843020,18 == fveval
( ) 20.0959035.395584),(-1.74663519 == fveval
( ) 13.6669164.757338)(7.935998,20 == fveval
Se observă că cromozomul este cel mai bun iar este cel
mai neperformant. Utilizăm metoda ruletei pentru selecţie. Fitnessul total al populaţiei este
selecţie pentru fiecare cromozom
este:
15v 2v
( )∑=
= 776822.387i
ivevalF
Probabilitatea de
=20
1
ip
20}...,2,1,{ , ∈ivi
( )0.0670991
1 ==( )
0.01954722 ==
Fvevalp
Fvevalp
( ) ( )0.0448894
4 ==F
vevalp 0.3 = 0503553 = Fveval
p
109
( )0.0466776
6 ==F
vevalp
( ) 0.0653505
5 ==F
vevalp
( ) 0.0413157
7 ==F
vevalp
( )0.0463158
8 ==F
vevalp
( ) 0.0415909
9 ==F
vevalp
( )0.05487310
10 ==F
vevalp
( ) 0.06037211
11 ==F
vevalp( )
0.03871
21212 ==
Fvevalp
( ) 0.07044413
13 ==F
vevalp
( )0.05125714
14 ==F
vevalp
( ) 0.07751915
15 ==F
veval ( )0.06154916
16 ==F
vevalpp
( ) 0.03532017
17 ==F
vevalp
( )0.03975018
18 ==F
vevalp
( ) 0.05182319
19 ==F
vevalp
( )0.03524420
20 ==F
vevalp
Probabilităţile cumulate tru fiecare cromozom sun
, , ,
, , ,
, , ,
, , ,
iq pen t
0.067090=1q 0.086647=2q 0.137001=3q
0.181890=4q 0.247240=5q 0.293917=6q
0.335232=q 7 8 9 0.381546=q 0.423137=q
0.47800910 =q 0.538381=11q 0.577093=12q
110
um se poate aplica tehnica ruletei de de ori, selectând de
fiecare dată câte un cromozom. Presupunem au fost generate ere aleatoare din
0.647537=13q , , , 0.698794=14q 0.776314=15q
0.837863=16q , q , q , 0.873182=17 0.912932=18
0.964756=19q , 1.000000=20q
Ac 20 că
[ ]1,0 : următoarele num
0.513870 , , , , ,
Primul număr
0.175741 0.308652 0.534534 0.9476280.171736 , 0.702231 , 0.226431 , 0.494773 , 0.424720 , 0.703899 , 0.389647 , 0.277226 , 0.368071 , 0.983437 , 0.005398 , 0.765682 , 0.646473 , 0.767139 , 0.780237 .
0.513870=a 10 11qaq << satisface relaţia , deci
cromozomul entru no popula oilea
număr 11v e at ua e. dste select p
0.175741 avem
ţi Pentru al
=a 43 qaq << , deci se selectează
cromozom
noua populaţie
ul 4v , etc.
În final, va conţine indivizii
111' vv = , 42'v , 73' vvv= = , 114' vv = , 195' vv = , 46' vv = , 157' vv = ,
58' vv = 30 v, , 119' vv = 1'v = , 11'v 15v= 12'v 9v, = , 613' vv = , 814' vv = ,
2015' vv = , 11' vv , 6 = 1017' vv = , 1318 v'v = , 1519' vv = , 1620' vv = .
111
put aplica eratorul încrucnoua populaţie. Luăm probabilitatea de încruciş
Acum em op de işare indivizilor din are 25.0=cp .
aProcedăm stfel:
pentru fiecare cromozom din noua populaţie, se generează un număr •
aleator [ ]1,0∈a
• dacă 25.0<a , individul respectiv va fi selectat.
Presupunem ca au fost selectate următoarele secvenţe de
, , , , ,
, , , , Înseamnă că, pentru crucişare, se selectează in vizii
Indivizii selectaţi perec ză aleat ; de
şi
numere:
0.822951 0.151932 0.625477 0.314685 0.346901 , 0.9 0.519760 , 0.401154 , 0.60675817204 , 0.785402 , 0.031523 , 0.869921 , 0.166525 , 0.674520 , 0.758400 , 0.581893 0.389248 0.200232 0.355635 0.826927 .
în di
1813112 ',',',' vvvv
exemplu ( )2 ',' vv
. se îm hea or
( )1813 ',' vv
, care indică
11 . Pentru fiecare pereche se generează
poziţia punctului de încrucişare.
rezultă de
numărul ,1∈pos [ ]32
Pentru prima pereche
001011000001111011010011 |00011000
111000011111011100001
şi 9=pos scendenţii
( )1'2 =v
( )101 |111011101'11 =v
112
( )111000011111011011100001 |100011000"2 =v
( )001011000001111011010011 |111011101"11 =v
A doua pereche de indivizi este
( )0111010111111 |10010101000001010000'13 =v
( )1100000001000 |10001000111110111110'18 =v
rin descendenţii şi 20=pos . Ei vor fi înlocuiţi p
( )1100000001000|10010101000001010000"13 =v
( )0111010111111|10001000111110111110"18 =v
Ac laţia curentă este: um, popu
, , , , , , , , , , , ,
, , , , , ,
rul de mutaţie cu probabilitatea alea r
1'v 2"v 3'v 4'v 5'v 6'v 7'v 8'v 9'v 10'v 11"v 12'v
13"v 14'v 15'v 16'v 17'v , 18"v 19'v 20'v .
În continuare se aplică operato [ ]1,0∈a 01.= 0mp . Pentru fiecare bit se generează un număr to
şi dac 01. ţia d m
ă <a 0 atunci el va suferi opera e utaţie.
Generăm 6602033 =⋅=⋅ nl numere aleatoare; dintre ele 5 sunt mai 01.0 : aceste valori sunt prezentate în tabelul care u
Tabelul al doilea arată numărul individului şi poziţiamari decâ rmreză.
bitului ce va uferi operaţia de mutaţie.
t
s
113
Poziţia bitului numărul aleator 112 0.000213 349 0.009945 418 0.008809 429 0.005425 602 0.002836
poziţie bit nr. individ Nr. bit în individ 112 4 13 349 11 19 418 13 22 429 13 33 602 19 8
Deci, patru cromozomi sunt afectaţi de operatorul de mutaţie, unul dintre ei având doi biţi schimb
final rezultă următoarea populaţie:
)
aţi.
În
( 101101100111111 =v 0000001101111010110
( )1100011111011011100001010001100012 =v
)0111011011111111 00110100010001000(3 =v
( )11011110001010110000 |0|1001100111114 =v
114
( )1000000110001111111111100010101005 =v
( )0101000001110011010011110001100016 =v
( )1100011111011011100001011101110117 =v
( )1010111111000010100110100011101108 =v
0000001101111101101011001100111119 =v
( )10110101110111100100000000010000010 =v
( )00101100000111 |0 |01101001111011101111 =v
( )10000000011110110001011010000000112 =v
( )1 |0000100011 |1 |01001010100000101000013 =v |
( )11101101011000111010001100001100014 =v
( )11010001011111001111001101110010115 =v
( )11110100110110000111111100110100016 =v
( )01110100001110011000001000001111017 =v
( )01110101111111000100011111011111018 =v
( )111000011111011011100001 |0 |1110111019 =v
( )01100011010010001111110110011110020 =v
unde biţii cuprinşi între linii verticale sunt cei care au rezultat în urma mutaţiei. S-a încheiat o iteraţie a algoritmului, putându-se trece la următoarea.
115
ntăm o nouă aplicaţie a algoritmilor genetici [101]: “Fiind dată o colecţie de oraşe şi costul trecerii între fiecare
ereche de oraşe, atunci, problema comis voiajorului este de a găsi el mai ieftin mod de a vizita toate oraşele şi de întoarcere în oraşul
de startceasta este o binecunoscută problemă NP-completă, echivalentă cu
găsirea
l global.
ri de
aluare:
5.2. Problema comis voiajorului
Preze pc
”. A
, într-un graf, a unui circuit hamiltonian de cost minim. O problemă NP-completă nu poate fi rezolvată într-un timp rezonabil decât prin folosirea unor algoritmi nedeterminişti. Există, însă, riscul de a găsi un minim local, apropiat mai mult sau mai puţin ca valoare de minimu
Specificul problemei comis voiajorului a dus la crearea unor noi modalităţi de reprezentare a cromozomilor şi noi tipuoperatori genetici, aşa cum s-a precizat anterior.
Reprezentarea problemei:
Funcţia de ev m lVo ua ca funcţie de evaluare suma distanţelor euclidiene dintre
două oraşe consecutive:
∑ −− iiii )yy()xx(Fitness 211 −+−=
N2
=i 1
Reprezentarea datelor:
116
izitate; de exemplu
sau
O reprezentare a traseului este cea în care oraşele sunt listate în ordinea în care ele sunt v
5,2,4,1,0,3 3,2,4,1,5,0 .
Operatori genetici:
Încrucişarea
Încruc ă nu eişarea tradiţional ste potrivită pentru problema ui deoarece descendenţii pot să nu respecte restricţia
de a se trece o singură dată prin fiecare oraş. De exemplu, din părinţii
şi 2 0 5 3 1 4
işare
comis voiajorul
1 2 3 4 5 0
3=posluând poziţia de încruc , rezultă descendenţii
Fie doi părinţi 0 şi
• pentru a genera un descendent utilizând al doilea părinte ca şablon selectăm prim şi
muchiile care au ca primă extremitate oraşul 4 în ambii ai scurtă: dintre
1 2 3 3 1 4 şi 2 0 5 4 5 0. Vom folosi o încrucişare de tip euristic, inventată de Grefenstette în 1985 [38].
1 2 3 4 5 4 1 3 2 0 5
ul oraş din şablon ca prim oraş al descendentului obţinem 4 x x x x x
• apoi găsimpărinţi, comparăm lungimile lor şi reţinem pe cea m
117
x x x x
urtă, selectăm oraşul 0: 4 1 2 0 x x
), oraş
todă, generăm celălalt descendent: 1 2 0 5 4 3
(4, 5) şi (4, 1), presupunând că oraşul 4 este mai apropiat de 1, alegem muchia (4, 1) şi selectăm oraşul 1 ca fiind următorul oraş al descendentului 1: 4 1
• găsim apoi muchiile ce pleacă din oraşul 1: acestea sunt (1, 2) şi (1, 3). Dacă oraşul 1 este mai apropiat de oraşul 2 , selectăm oraşul 2 ca următorul oraş al traseului: 4 1 2 x x x
• din oraşul 2 pleacă muchiile (2, 3) şi (2, 0). Dacă distanţa dintre oraşul 2 şi oraşul 0 este mai sc
• muchiile ce au ca primă extremitate oraşul 0 sunt (0, 1) şi (0, 5). Deoarece oraşul 1 apare deja în descendent, selectăm oraşul 5 ca oraş următor: 4 1 2 0 5 x
• muchiile ce au ca primă extremitate oraşul 5 sunt (5, 0) şi (5, 4dar oraşele 4 şi 0 apar ambele în descendent. Selectăm un neselectat, care este oraşul 3 şi astfel producem un descendent legal: 4 1 2 0 5 3
Utilizând aceeaşi me
Mutaţia
Din acelaşi motiv ca la încrucişare, nu putem utiliza mutaţia tradiţională. De aceea vom folosi mutaţia prin interschimbare: selectăm aleator doi biţi dintr-un cromozom şi le interschimbăm
. valorile. De exemplu, din 1 2 3 4 5 0 obţinem 1 5 3 4 2 0
118
Selecţia
Când folosim metoda tradiţională de selecţie bazată pe principiul ruletei, cel mai bun individ are cea mai mare probabilitate de supravieţuire, dar nu supravieţuieşte neapărat. De aceea, vom utiliza lecţia CHC [17] care ne asigură că cel mai bun individ va supravi eauna în noua generaţie.
seeţui întotd
.
Figura 5.1. Comparaţie între selecţia pe modelul ruletei şi selecţia CHC
lung
imea
generaţii
modelul ruletei
119
ocedeul este următorul:
• dacă dimensiunea populaţiei este N, se generează N descendenţi
• se sortează după fitness mulţimea formată din părinţi şi descen • se aleg cei mai buni N indivizi, care vor forma generaţia
ţletei. Pentru a preveni convergenţa la un optim local,
mai buni indivizi iniţializând aleator restul populaţiei şi reluând procesul.
upa de rezolvarea unei ecuaţii diofantice [58]. O ecuaţie diofantică este o ecuaţie cu mai multe necunoscute, coeficienţi înt şi soluţie întreagă. Să luăm ca exemplu ecuaţia
turor
Pr
folosind metoda ruletei
denţi
următoare. Selecţia CHC asigură o convergenţă mai rapidă în compara ie
cu metoda rumetoda se va modifica astfel: după ce s-a ajuns la convergenţă, se salvează cei
5.3. Aplicaţii în probleme de algebră
Ne vom oc
regi 3043 =++ tz . Se poate obţine soluţia prin încercarea tu2+ yx
valorilor tzyx ,,, ce satisfac restricţia 301 ≤≤ t,z,y,x . Algoritmii
genetici permit ca soluţia să fie obţinută mai rapid, deoarece soluţiile „mai bune” au şanse mai mari de supravieţuire şi reproducere, în
120
fiecăreia. m lucra
opoziţie cu parcurgerea tuturor soluţiilor posibile şi testarea validităţii
Vo cu o populaţie de 5 indivizi ce satisfac restricţia precizată anterior:
individul1: ( )3,15,28,11 =v
individul2: ( )4,2,9,142 =v
( )3,3,5,13individul3: 3 =v
( )19,16,8,234 =v individul4:
( )2,5,13,95 =v individul5:
( )dcba ,,,v = Fiind dat cromozomul def fitnessul său ca
fiind
inim
304321
−+++( ) =
aveval
dcb
şi obţinem
( ) 011904.0841
301141
1 ==−
=veval
( ) 041666.0241
30541
2 ==−
=veval
( )
038461.0261
30561
3 ==−
=veval
121
( ) 007518.0133
130163
14 ==
−=veva l
( ) 035714.0281
30581
5 ==−
=veval .
Fitnessul total al populaţiei este
0.135266
iar probabilităţile de selecţie asociate fiecărui individ sunt:
∑=
==5
1)(
iivevalF
( ) ( )
308.022 ==
Fvevalp , 088.01 ==
vevalp , 1 F
( )284.03 ( )
056.04
3 F==
vevalp , 4 F
==vevalp ,
( )264.05
5 ==F
vevalp .
Folosind metoda rulete tăm următoarele cinci perechi de i selecindivizi:
( )1,3 , ( )2,5 , ( )5,3 , , ( )5,2 ( )3,5 .
Încrucişăm cei doi părinţi ai fiecărei perechi şi, pentru a menţin
ţi. De exemplu, plecând de la părinţii e dimensiunea populaţiei, reţinem doar unul din cei doi
descenden
( )c1,1,a1 şi ( )d2cb2, | d1b | 2,a2
122
şi luând punctul de încrucişare în poziţia precizată de bara verticală, reţinem descendentul
( )d2c2,b2, | a1 .
Astfel obţinem:
• părinţii ( )37,5, | 13 şi ( )315,28, | 1 dau descendentul
( )315,28,13,
• părinţii şi ( )25, |139, ( )42, | 914, dau descendentul ( )42,13,9,
• părinţii şi ( )3 | 75,13, ( )2 | 513,9, dau descendentul ( )27,5,13,
• părinţii şi ( )42,9, | 14 ( )25,13, | 9 dau descendentul ( )25,13,14,
• părinţii ( şi )3 7, | 513, ( )2 5, | 139, ( )25,5,13, dau descendentul
Nu m muta descendenţii obţin zăai folosim ţia, aşa că uţi formea noua populaţie; aceasta va fi supusă în continuare aceloraşi prelucrări.
termină la irea unei s mai multe. , i
Algoritmul se găs oluţii, ecuaţia avândDe exemplu ş ( )31,4,7, ( )0,6,2, 4 sunt soluţii ale in ecuaţiei d
exemplul nostru.
re cele mai cunoscute probleme ă în prezent necunoscându-se nici un algoritm
ficient pentru rezolvarea ei. Formularea ei este următoarea:
5.4. Orarul unei şcoli
Problema orarului este una dintde algoritmică, pâne
123
Se dă ând pentru fiecare profesor numărul de ore la fiecare clasă. Cerinţa principală este aceea de a se obţine
ită zi a
• : numărul de profesori; • ma este dată printr-o
ice . Profesorii vor fi codificaţi cu ere
matricea încadrărilor, preciz
un orar, adică o repartizare a profesorilor la clase, pentru fiecare dintre zilele săptămânii şi, în cadrul fiecărei zile, pentru fiecare oră, astfel încât într-o aceeaşi oră (dintr-o anumsăptămânii) fiecare profesor să intre la cel mult una din clasele asociate lui prin matricea de încadrare şi la fiecare clasă să intre cel mult câte unul din profesorii asociaţi clasei.
Vom considera următoarele date de intrare: • NrC : numărul de clase din şcoală; • NrO : numărul maxim de ore pe zi ale unui elev; • NrZ : numărul de zile în care sunt ore;
NrP
tricea încadrărilor: încadrarea profesorilor matr A cu NrP linii şi NrC coloane num { }NrP,,,i 21∈ , iar clasele cu numere { }NrC,,L2 ; ,j 1∈L
• elevii din clasele 9-10 învaţă după-amiaza, iar cei din clasele 11-
; 40 de clase - acestea ar pu
re pe zi); nci zile pe săptămână);
12 dimineaţa. Exemplu • tea fi clasele 9A, ..., 9J, 10A, 40=NrC
..., 10J, 11A, ..., 11J, 12A, ..., 12J; • 6=NrO (şase o • 5=NrZ (ci
124
• (80 de profesori - se păstrează şi o listă cu numele lor: Aldea, Andrei, ..., Voicu);
80=NrP
Un rmaţie conţinută de o linie a matricei rărilor 5 ore la 10B, 4 ore la 11A, 3
e se poate modela printr-o matrice cu ii ş
exemplu de infoîncad este: profesorul Aldea are:ore la 12 C, 3 ore la 12D, 3 ore la 12E. Orarul de funcţionar NrP lin i NrZNrO ∗∗2 coloane. Indicele liniei reprezintă codul profesorului, iar indicele coloanei reprezintă un anumit moment de timp (zi şi oră). Un element al acestei matrice va fi codul unei clase. O
ult un profesor;
e între două ore la care li se
orar ca fiind un orar valid. Pe lângă rii să aibă
şi disciplină în aceeaşi zi. Un orar valid cu număr mic de
linie a matricei va indica programul pe zile al unui profesor, iar o coloană va indica profesorii ce au ore la momentul respectiv. Condiţiile pe care trebuie să la îndeplinească un orar sunt următoarele: • trebuie să fie conform cu încadrarea (linia de orar trebuie să exprime exact încadrarea profesorului); • la un anumit moment de timp (zi şi oră), la o anumită clasă trebuie să predea cel m • un profesor nu poate preda simultan la mai multe clase; • elevii nu vor avea ferestre (ore liberpredă). Vom numi un astfel de cele patru condiţii absolut necesare ar fi de dorit ca profesoun număr cât mai mic de ferestre, iar elevii să aibă cel mult două ore la aceea
125
ferestre pentru profesori va fi numit un orar bun. Vom prezenta o posibilitate de întocmire a orarului folosind algoritmi genetici [91]. Pentru început va trebui să găsim un orar valid de pornire. Vom prefera o variantă de generare aleatoare a unui asemenea orar de pornire. Pentru fiecare linie se utilizează un algoritm de generare a unui aranjament aleator de ore conform cu matricea încadrărilor. După generarea orarului de pornire, acesta trebuie optimizat în raport cu numărul de ferestre. Un orar valid poate fi considerat ca fiind o matrice B cu NrP linii şi NrZNrO ∗∗2 coloane. Pentru exemplul considerat vor fi 80 de linii şi 60 de coloane; 30 dintre
pe linia profesorului
coloane vor reprezenta ore de dimineaţă iar celelalte 30 ore de după-amiază. Un element al acestei matrice va fi codul unei clase (de la 1 la NrC ) sau valoarea 0 dacă p , la timpul t nu este
planificată desfăşurarea unei ore. O linie a matricei B va fi considerată cromozom. Pentru exemplul ales, lungimea cromozomului este 60. O genă va putea lua
ri cuprinse între 0 şi NrC . Vor putea fi 41 de valori distincte pentru gene. Dimensiunea populvalo
aţiei este egală cu . În cazul estui e
tim
NrP
ac exemplu, valoarea est 80. Ca operator de evoluţie se foloseşte mutaţia încrucişată. Fie profesorii 1p şi 2p care la pii 1t şi 2t au ore la clasele 1c şi 2c ;
cu alte cuvinte avem ( ) ( ) 12211 ct,pBt,pB == şi ( ) ( ) 21221 ct,pt,pB B= = ;
cromozomii corespunzători liniilor 1p şi
ă c a
2p se vor încrucişa
interschimbând genele de pe poziţiile 1t şi 2t ; operaţia poate fi reprezentat grafi stfel:
126
Observăm că prin astfel de mutaţii se păstrează validitatea orarelor. Este greu de găsit un tip de mutaţie simplă care să conserve proprietatea unui orar de a fi valid . Funcţia de minimizat este funcţia
numărul de ferestre ale unui profesor. Această funcţie
ări care ar
care calculeazăse poate eventual pondera, în sensul ca o fereastră de două ore să fie echivalentă, de exemplu, cu trei ferestre de câte o oră. Construirea unui orar bun va însemna optimizarea prin algoritmul genetic a unui orar valid de pornire. Optimizarea are ca scop reducerea numărului de ferestre ale profesorilor. În cele ce urmează vom prezenta câteva modificputea fi aduse algoritmului prezentat. Fie 0P , 1P , 2P ......, şirul de orare
generate de algoritm. gP va reprezenta populaţia din generaţia g . O
posibilitate de optimizare implică introducerea a încă doi parametri tregi în pozitivi p şi δ . Fie g generaţia curentă. În cadrul buclei
repetitive se vor executa următoarele operaţii: • salvarea populaţiei corespunzătoare generaţiei curente gP ;
127
• generarea a δ noi populaţii conform algoritmului prezentat; noile orare vor fi identificate prin δ+++ ggg P,,PP L21 ;
• păstrarea celei mai valoaroase generaţii, care va
,
deveni generaţia
ă
1+gP ;
• creşterea num rului de generaţii: 1+← gg .
O a doua posibilitate de optimizare implică introducerea parametrului întreg δ şi a unui parametru S care este un şir descrescător de num re naturale care conţine elemente. În cadrul
toarele operaţii: e Ne
buclei repetitive se vor executa urmă • salvarea populaţiei corespunzătoare generaţiei curente gP ;
• generarea a δ noi populaţii conform algoritm lui prezentat; noile orare vor fi identificate prin δ+++ ggg P,,P,P L21
• repetarea pasului anterior până când numărul total
u
de ferestre scade ra
ă
;
sub valoarea ( )gS ; populaţia corespunzătoare devine gene ţia 1+gP
• creşterea num rului de generaţii: 1+← gg .
5.4. O problemă de proiectare
Considerăm o cutie de conserve cilindrică, cu doi parametri: diametrul i înălţimea (evident, pot fi consideraţi şi alţi param ăţi ale materialului, for i parametri pentru a ilus
d ş h etri, cum ar fi grosimea, propriet
ma, e t c . , dar sunt suficienţi doar cei dotra modul de lucru) [42].
128
st
izeze valoarea funcţiei
Să considerăm că acea ă conservă trebuie să aibă un volum de cel puţin 300 ml şi obiectivul este de a minimiza costul materialului folosit la fabricarea conservei. Putem formula problema astfel: să se minim
( ) ⎟⎟⎠
⎞⎜⎜⎝
⎛+= dhdch,df ππ
2
2
unde c reprezintă costul materialului conservei pe , iar expresia din paranteză reprezintă suprafaţa conservei. Mai trebuie îndeplinită şi condiţia ca volumul cutiei să fi cel puţin 300 ml:
2cm
e
( ) 3004
≥=hdh,dg ,
u parametrii d şi h variind între anumite limite:
2π
c
maxmin ddd ≤≤ şi maxmin hhh ≤≤ .
Reprezentarea soluţiei
e 5 biţi pentru a are din param i şi De exemplu, şirul
reprezintă o conserv etrul de 8 cm (cores biţi) şi înălţimea de 10 cm
Vom folosi reprezentarea binară, utilizând câtreprezenta fiec etri d
ăh .
cu diam0100001010punzător primilor 5
(corespunzătoare ultimilor 5 biţi). În aceste condiţii,
0== minmin hd şi 31== maxmax hd .
Lungimea unui cromozom fiind 10, există 102 soluţii posibile ale
129
problemei.
tness
F
Funcţia fi
uncţia de optimizat va fi f , unde vom lua 143.=π şi 06540.c = .
entru valorile paP rametr şi din ex te cutiei este de 23 de unit copu roblem ec ie să nţa i
lizate c exempluţ 6
ilor ăţi.
d S
satisfac
hl p
ă ceri
emplul anei este d
mpusă de func
rior , costul a minimiza ţia g ; celeostul. O soluţie trebu
care încalcă această restricţie vor fi pena a în l următor. Considerăm o popula ie de indivizi având evaluările
23, 26, 30, 24, 11, 9;
cutiile corespunzătoare ultimelor două valori nu satisfac restricţia impusă de funcţia g , de aceea vor fi penalizate astfel încât să devină
mai puţin promiţătoare decât oricare dintre soluţiile acceptabile. După penalizare noile evaluări
Folosim selecţia de tip turneu cu mărimea turneului egală cu 2: • se aleg aleator d • se calculează performanţele lor,
• se ază cel mai bun, introducându-se în populaţia
e 23 şi 30 se selectează cel cu
sunt:
23, 26, 30, 24, 11+28, 9+35.
Selecţia
oi cromozomi,
selecteintermediară. De exemplu, • dintre cromozomii cu evaluăril
130
mozomii cu evaluările 26 şi 11+28 se selectează cel cu
ediară.
ori de evoluţie
încrucişare în poziţia 3, din cromozomii ce definesc cutiile cu
evaluarea 23 • dintre croevaluarea 26 • dintre cromozomii cu evaluările 24 şi 9+35 se selectează cel cu evaluarea 24 • dintre cromozomii cu evaluările 24 şi 26 se selectează cel cu evaluarea 24 • dintre cromozomii cu evaluările 11+28 şi 23 se selectează cel cu evaluarea 23 • dintre cromozomii cu evaluările 9+35 şi 30 se selectează cel cu evaluarea 30.
Se observă că soluţiile cele mai promiţătoare au mai multe copii în populaţia interm
Operat
Vom folosi încrucişarea cu un singur punct de tăietură. De exemplu, considerând punctul de
fitness 10823 === d,h,
şi respectiv 61426 === d,h,fitness
vor rezulta descendenţii cu 61022 === d,h,fitness
şi respectiv 101238 === d,h,fitness :
131
mutaţia tare: de exemplu, din soluţia cu fitnessul 22 prin mutaţia bitului din poziţia 4 se obţine o soluţie cu fitnessul 16.
0001010010M1000110011M
⇒00010100111000110010M
M
Se foloseşte
6 SCHEME ŞI BLOCURI
O problemă importantă în studiul algoritmilor genetici este
legată de similitudinile care există între diferiţi cromozomi ai unei populaţii. Mai precis, ne interesează în ce măsură un cromozom este reprezentativ pentru o clasă de cromozomi, la nivelul poziţiilor genelor.
6.1. Scheme: definiţie, proprietăţi
O schemă este un şablon care descrie o submulţime de cromozomi având asemănări în anumite poziţii. Schema se obţine prin introducerea caracterului ∗ (cu semnificaţia indiferent, nu ştiu care, etc.) în alfabetul general, obţinând astfel o cale compactă de a analiza similitudinile bine definite între cromozomi. Vom considera, în continuare, că lucrăm cu alfabetul binar { }1,0 şi cu cromozomi de
lungime ; atunci, un cromozom este un element al spaţiului m { }m,10
iar schema este un element al spaţiului { . }m,∗,10
134
Un cromozom este o instanţă a unei scheme dacă fiecărei poziţii din cromozom diferită de ∗ îi corespunde o poziţie din schemă având aceeaşi valoare. De exemplu, schema ∗∗∗10 defineşte cromozomi. În general, pentru un alfabet de cardinalitate k există
scheme, fiind lungimea cromozomului. De asemenea, un
cromozom de lungime aparţine la scheme diferite, deoarece fiecare poziţie a sa poate lua fie valoarea curentă fie simbolul
8
( )mk 1+ m
m m2∗ .
Unui şir de lungime îi corespund scheme posibile iar
într-o populaţie de dimensiune pot fi reprezentate între şi scheme diferite. În acest fel, populaţii cu dimensiune moderată aduc o informaţie importantă cu privire la similitudinile semnificative dintre indivizi.
m
n
m3m2 mn 2⋅
Dacă este lungimea cromozomilor, aceştia pot fi priviţi ca puncte într-un spaţiu de căutare de dimensiune m ; cu alte cuvinte sunt vârfurile unui hipercub, vârfurile vecine fiind reprezentate prin şiruri ce diferă printr-un bit. Ca exemplu să considerăm cromozomi de lungime 3 (Figura 6.1). Planul din faţă conţine toate punctele ce încep cu , şirul “ ” reprezentând originea. Acest plan poate fi reprezentat prin schema “
m
0 000∗∗0 ”; deci o schemă corespunde unui
hiperplan în spaţiul de căutare.
Trecerea la un hipercub de dimensiune mai mare se face [93] ca în Figura 6.2, unde este ilustrat un spaţiu 4-dimensional reprezentat ca un cub “atârnând” în interiorul altui cub.
135
000 001
100
010
110
011
101
111
Figura 6.1
0000 0001
0101
01110110
0010
0100
0011
1000 1001
1010 1011
1110 1111
11011100
Figura 6.2
136
Etichetarea punctelor se face astfel: punctele cubului interior şi punctele cubului exterior se reprezintă ca în cazul 3-dimensional apoi punem 1 în faţa fiecărui şir din cubul interior şi în faţa fiecărui şir din cubul exterior. În felul acesta, două şiruri adiacente diferă printr-un bit. Cubul interior aparţine schemei “
0
∗∗∗1 ”, în timp ce cubul exterior corespunde schemei “ ∗∗∗0 ”. Este uşor de văzut că “ ∗∗∗0
∗
” corespunde planului din faţă al fiecărui cub iar schema “ ∗10 ” corespunde planului din faţă al cubului interior.
Un şir de biţi aparţine unei scheme particulare dacă poate fi obţinut din aceasta prin înlocuirea semnului ∗ cu biţi corespunzători. Fiecare şir binar este un cromozom ce aparţine unui vârf al
hipercubului. Un şir binar aparţine la hiperplane diferite, unde este lungimea cromozomilor; şirul cu toate simbolurile ∗
corespunde întregului spaţiu şi nu se consideră hiperplan. Cum fiecare poziţie din cele poate conţine un bit sau caracterul
12 −m
m
m ∗ , înseamnă că
sunt hiperplane pe întreg spaţiul de căutare. 13 −m
Faptul că un şir aparţine la hiperplane nu aduce foarte multă informaţie dacă fiecare punct este examinat izolat. Acesta este motivul pentru care noţiunea de căutare bazată pe populaţie este esenţială în algoritmi genetici.
12 −m
Vom folosi următoarele notaţii:
• ( )Sθ = ordinul schemei , adică numărul poziţiilor fixate; deci S
ocupate cu 0 sau 1. De exemplu, pentru schemele
137
( )1100011 ∗∗∗∗=S
( )∗∗∗∗∗∗∗= 0002S
( )001111013 ∗∗=S
avem ( ) ,61 =Sθ ( ) ,32 =Sθ ( ) 83 =Sθ ; deci este cea mai specifică.
O schemă de ordin
3S
θ reprezintă şiruri diferite. θ−m2
• ( )Sδ = lungimea schemei şi reprezintă distanţa dintre prima şi
ultima poziţie fixate. Pe exemplul anterior avem:
S
( ) 64101 =−=Sδ , ( ) 4592 =−=Sδ şi ( ) 91103 =−=Sδ .
O schemă cu o singură poziţie fixată are lungimea . Lungimea unei scheme este o măsură a numărului de puncte de încrucişare aflate în porţiunea semnificativă a schemei. Dacă se foloseşte încrucişarea
simplă, atunci
0
( )1−m
Sδ este o măsură a probabilităţii ca punctul de
încrucişare să aparţină porţiunii semnificative a schemei.
O populaţie cu cromozomi de lungime m conţine între
şi
n m2
( )mmn 3,2min ⋅
6=m
scheme, astfel că algoritmii genetici operează
implicit pe un număr de scheme mult mai mare decât dimensiunea populaţiei (proprietate numită paralelism intrinsec). De exemplu, pentru şi 20=n
100=m
numărul de scheme este cuprins între 64 şi 729
iar pentru şi 300=n va fi între şi
.
3010267650×.13210802951×.3
138
6.2. Teorema schemei
Simularea procesului de evoluţie într-un algoritm genetic constă în repetarea a patru paşi:
1: += tt
selectează ( )tP din ( )1−tP
recombină ( )tP
evaluează ( )tP
Principalul fenomen din procesul de evoluţie apare în paşii de selecţie şi recombinare; de aceea discutăm efectul lor [60]. Considerăm o populaţie de dimensiune 20=PopSize şi lungimea
unui individ . Considerăm că populaţia curentă (la iteraţia ) constă din următorii indivizi
33=m t
( )1111010011011000011111110011010001 =v
( )0101010100011001101110011100010012 =v
( )1011010111011110010000000001000003 =v
( )0101000001110011010011110001100014 =v
( )1010111111000010100110100011101105 =v
( )0111010111111100101010000010100006 =v
139
( )0111011011111001101011100100010007 =v
( )1110110101100011101000110000110008 =v
( )1000000001111011000101101000000019 =v
( )01110100001110011000001000001111010 =v
( )00000011011111011010110011001111111 =v
( )00001010100001110110100110100010112 =v
( )11000000010001000100011111011111013 =v
( )00101111001010000101010010010011014 =v
( )11000111110110111000010111011101115 =v
( )01100011010010001111110110011110016 =v
( )10100011011111100111101011010111117 =v
( )10101111101010000111010011101000018 =v
( )10000001100011111111111000101010019 =v
( )11010001011111001111001101110010120 =v
Notăm cu ( tS , )ξ numărul indivizilor din populaţie care se potrivesc
cu schema la momentul t . De exemplu, pentru schema S
( )∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗= 1110S
140
( ) 3,0 =tSξ deoarece , şi se potrivesc cu schema . 13v 15v 16v 0S
O altă proprietate a schemei este evaluarea la momentul ,
, definită ca fiind media evaluărilor indivizilor din populaţie
care se potrivesc cu schema . Dacă
t
( tSeval , )S p indivizi { }
pii vv ,,1L se
potrivesc cu schema la momentul atunci S t
( )( )
p
vevaltSeval
p
jji∑
== 1, .
În timpul selecţiei este creată o nouă populaţie, fiecare individ fiind copiat de 0, 1 sau mai multe ori, în funcţie de evaluarea sa. Notând cu evaluarea întregii populaţii la momentul , ( )tF t
( ) ( )∑=
=PopSize
iivevaltF
1,
probabilitatea ca individul să fie selectat este iv
( )( )tF
vevalp ii = .
Deoarece
• probabilitatea de selectare a indivizilor care se potrivesc cu schema este S
( )( )tF
tSeval ,
141
• numărul indivizilor ce se potrivesc cu schema la momentul t
este
S
( )tS ,ξ
• numărul indivizilor selectaţi este PopSize
rezultă că numărul indivizilor care se potrivesc cu schema la momentul este
S1+t
( ) ( ) ( ))(
,,1,tF
tSevalPopSizetStS ⋅⋅=+ξξ .
Ţinând seama că evaluarea medie a populaţiei este
( ) ( )PopSize
tFtF = ,
formula anterioară devine
( ) ( ) ( )( )tF
tSevaltStS ,,1, ⋅=+ξξ
adică numărul indivizilor care se potrivesc cu schema la momentul creşte în funcţie de raportul dintre evaluarea schemei şi evaluarea
medie al populaţiei. Înseamnă că o schema “deasupra mediei” duce la creşterea numărului de indivizi iar una “sub medie” determină scăderea numărului lor. Presupunând că schema rămâne deasupra mediei cu
1+t
ε %, adică
( ) ( )tFtSeval =, ( )tF⋅+ ε ,
atunci
( ) ( )( ) t,St,S εξξ += 10 ,
142
adică schema aflată “deasupra mediei” duce chiar la o creştere exponenţială a numărului de indivizi care se potrivesc cu ea în
a teorema schemei, considerăm exemplul de funcţionare a algoritmilor genetici prezentat în capitolul anterior. Întorcâ
generaţiile următoare.
Pentru a explic
ndu-ne la schema 0S , deoarece trei şiruri se potrivesc cu
schema, avem
( ) 081378.273
867227.23060205.30316702.27=
+,0+
=tSeval
iar evaluarea medie al întregii populaţii este
( )( )tF 388841.19
20776822.387
20
1 ===∑ veval i=
PopSizei .
Raportul dintre evaluarea schemei şi evaluarea medie a populaţiei 0S
este
396751.1)(
),( 0 =tF
tSeval
adică schema este deasupra mediei. 0S
La momentul 1 vor fi +t 19.4396751.13 =×
, probabil 4 sau 5) iar la m
şiruri ce se potrivesc
omentul cu S (adică0 2+t vor fi
Simulând procesul de selecţie, rezultă următoarea populaţie 85.53 2 =× şiruri (deci, foarte probabil 6). 396751.1
143
, 42' vv = , 73' vv = , 114' vv = , 195' vv = , 46' vv = ¸ 157' vv =111' vv = ,
58' vv = , 119 v= ¸'v 10'v 3v= , 1511' vv = , 912' vv = , 613' vv = , 814' vv = ,
20 , 1015' vv = ¸ 116' vv = 17' vv = , 118' vv 3= , 119' vv 5= , 1620' vv = .
Într-adev în noua popula există şiruri : şi
roduce şiruri noi în populaţie, determ
)
ar, ţie 5 8 ,' 191117 '',', vvvv
20'v , care se potrivesc cu schema 0S .
Totusi, selecţia singură nu intinând doar copierea unor şiruri pentru a forma populaţia
intermediară. Sarcina introducerii de şiruri noi revine recombinării, prin operatorii de încrucişare şi mutaţie. Pentru a analiza încrucişarea considerăm schemele
( ∗∗∗∗= 1110S ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
( )101111 ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗=S
Presupunând că şirul a fost ales pentru încrucişare cu poziţia 18'v
va
20=pos , schema 0S supravieţui încrucişării deoarece unul din
ţi va conţin secvenţa “111”. Şirurile descenden e
( )1101000
vor produce descendenţii
0000000111101000100111111018 |v' =
( )01110101111111001010100000101000013 |'v =
( )0111010111111011| 1101000100111111018"v =
144
( )11000000010001001010100000101000013 |"v = .
Pe de altă parte, schema va fi distrusă deoarece secvenţele
fixate principal în distrugerea sau supravieţuirea unei scheme îl are lungimea
1S
“111” şi “10 ” vor fi plasate în descendenţi diferiţi. Rolul
de definire; ( ) 20 =Sδ iar ( ) 321 =Sδ . În general, punctul de
încrucişare este uniform r dintre cele 1 s at elect şi aleato −m poziţii.
( )
Rezultă probabilitatea de distrugere a schemei este că S
( )1−
=SSpd m
δ
iar probabilitatea de supravieţuire este
( )1−m
Sδ( ) 1−=Sps .
Pe exemplul anterior avem
( )322
0 =Spd , ( )3230 ( ) 1
3232
1 ==Spd , ( ) 01 =Sps , 0Sps = ,
rezultate ce corespund cu predicţia.
i vor fi supuşi încrucişării, dacă este probabilitatea de încrucişare, rezultă că probabilitatea ca
schem
Deoarece numai unii indiviz
cp
a să supravieţuiască este de fapt
( ) ( )1−m
Sδ1−= pSp cs
145
Pentru schema ş 0S i 250.pc = avem
( ) 984375.06463
3250 =⋅Ss
22.01 =−=p .
Chiar dacă punctul de încrucişare este selecta între poziţiile fixate ale schemei, este posibil ca schema să supravieţuiască. De exempl
t
u, dacă ambele şiruri 18'v şi 13'v încep cu “111” şi se termină
cu “10”, atunci schema 1S va supravieţui încrucişării. Rezultă că
formula care dă probabilitatea de supravieţuire a unei scheme trebuie modificată în
( ) ( )1
1−≥SpSp−mcs
δ .
Combinând efectele selecţiei şi încruc rii rezultă formula işă
( ) ( ) ( )( )
( )⎟⎠
⎜⎝ −−≥+
11,1,
mp
tFtStS cξξ ⎞⎛, StSeval δ
Pentru schema avem 0S
( )( )
( ) 374927.1984375.0396751.11
1,0 =×=⎟⎠⎞
⎜⎝⎛
−−
mp
tF cStSeval δ
şi deci
• la generaţia 1+t ne aşteptăm să avem 12437492713 .. =×
ai mică decât
şiruri
r potrivi ; se obţine, deci, o valoare m
când se consideră numai selecţia.
cu S0 194. ce se vo
146
şiruri ce se vor
t este mutaţia. Considerăm
)
Se observ
• la generaţia t avem 67537492713 2 .. =× potrivi
cu 0S ; se obţine o valoare mai mică decât 855. .
Următorul operator considera
2+
schema 0S şi şirul
( 11000111110110111000010111011101119 ='v .
ă că orice mutaţie care afectează biţii 41− sau 338−
permite supravieţuirea schemei , în timp ce oric ţ
din biţ sau va distruge schema. Biţii care d c la distru0S e muta
u
ncide
ie pe unul
gerea
rdinul
ii 65, 7
schemei sunt cei “importanţi” iar numărul lor coi cu o schemei. Probabilitatea de alterare a unui bit fiind mp , rezultă că
probabilitatea de supravieţuire a unui bit este mp−1 ; deci
probabilitatea de supravieţuire a schemei este
( ) ( ) ( )Sms pSp θ−= 1 .
Deoarece 1≤mp , probabilitatea poate fi aproximată prin
( ) ( ) ms pSSp ⋅−≈ θ1 .
Referindu-ne la schema şi luând obţinem S 0 m 010.p =
( ) 970010310 ..Sps =×−≈
Combinând efectele selecţiei, încrucişării şi mutaţiei rezultă
147
( ) ( ) ( )( )
( ) ( ) ⎟⎠⎞
⎜⎝⎛ ⋅−
−−≥+ mc pS
mSp
tFtSevaltStS θδξξ
11,,1, ,
relaţie ce constituie teorema schemei.
Pentru schema avem 0S
( )( )
( ) ( )10 pSSpt,Seval=⎟
⎞⎜⎛ ⋅−− θδ 3330241954375039675110 ...mc =×
⎠
şi deci
• la generaţia
1mtF ⎝ −
1+t ne aşteptăm ca 433302413 ≈× .
ult de 194.
lt de 124.
şiruri să se
ă cu ă nu mai m cât au rezultat
considerând num ţia şi nu mai mu cât au rezultat prin şi a
potriveasc 0S , adic
ai selecfolosirea selecţiei încrucişării
• la generaţia 2+t vom avea 3333302413 2 ..× astfel de şiruri, deci nu mai mult de 855. respectiv
5≈ 675.
Observaţ Formula sta în cazul când funcţia de optimizat numai valo
ie. bilită funcţioneazăia ri positive.
h n mic, lungime de definiţie mică şi fitness peste media populaţiei sunt reprezentate în genera mozomi; creşterea
f
Relaţiile de mai sus ne permit să formulăm
Teorema sc emei. Schemele de ordi
ţiile successive de un număr crescând de cro
148
este ex
necesar să se micşoreze efectul distructiv al încrucişării şi mutaţie
c l
e. O altă problemă legată de conver
O categorie specială de scheme sunt blocurile. Acestea sunt scheme cu valori mari ale evaluării, ordin mic şi lungime de definire
ponenţiată dacă fitnessul schemei este constant peste media populaţiei.
Teorema schemei pune un mare accent pe rolul încrucişării în selecţia hiperplanelor. Pentru a maximiza păstrarea hiperplanelor după selecţie este
i. Pentru aceasta trebuie ca mutaţia să fie folosită puţin sau de loc. După câteva generaţii este posibil ca selecţia să conducă la fixarea unei singure valori pentru o anumită poziţie: fie 0 fie 1; aceasta duce la convergenţa prematură, situaţie întâlnită frecvent când se lucrează cu populaţii de dimensiune mică.
Fără mutaţie este imposibil să se reintrodu ă va oarea pierdută a bitului; mutaţia acţionează ca un operator de reamintire, permiţând recuperarea unor valori pierdut
genţa prematură este necesitatea scalării fitnessului populaţiei. Când evaluarea medie a şirurilor creşte, dispersia în fitness scade. Între cel mai bun şi cel mai slab individ din populaţie poate fi o diferenţă mică după câteva generaţii iar presiunea selecţiei bazată pe fitness va fi corespunzător redusă. În acest caz se calculează valoarea medie a şirurilor şi fitnessul, folosind evaluarea ajustată, crescând presiunea selecţiei. Alternativ, se poate folosi selecţia după rang.
6.3. Blocuri
149
redusă. r afirmă că încrucişarea orientează căutarea către găsirea blocurilor (soluţii parţiale) pe care le combină în soluţii globale
Ipoteza blocurilo
mai bune. Totuşi, ipoteza blocurilor poate fi violată. Să considerăm schemele
( )∗∗∗∗∗∗∗∗= 1111S
( )112 ∗∗∗∗∗∗∗∗∗=S
situate deasupra mediei şi să presupunem că schema
( )111113 ∗∗∗∗∗∗=S
rezultată prin încrucişare este mai puţin potriv decât ită
( )000004 ∗∗∗∗∗∗=S .
Dacă şirul optim este
( )111111111110 =v ,
care se potriveşte cu , un algoritm geneti ea dificultăţi în a
ce va tinde să găsească şirul
3S
re
c va av
converge către 0v deoa
( )00001111110 .
etici, înseamnă o interacţiune puternică între genele unui cromozom. O posibilitate de a înlătura decepţia constă în folosirea altui operator genetic: inversiunea, care va inversa biţii dintre două poziţii selectate aleator.
Acest fenomen poartă numele de decepţie şi este strâns legat de cel numit epistasis care, în termenii algoritmilor gen
150
De exemplu, schema
( )111113 ∗∗∗∗∗∗=S
poate fi regrupată prin inversiune în
( )∗∗∗∗∗∗= 111113'S ,
care reprezintă un bloc important.
7 VARIANTE DE ALGORITMI GENETICI
7.1. Probleme de convergenţă
Studiul convergenţei algoritmilor genetici este una din cele mai dificile probleme. De aceea s-au încercat diferite metode de soluţionare a ei. Pentru a evalua a priori viteza de convergenţă şi precizia unui algoritm genetic s-au introdus mărimi care să măsoare omogenitatea spaţiului de căutare şi corelaţia fitness-distanţă. În ambele cazuri se consideră că funcţia fitness coincide cu cea de evaluare.
a) Omogenitatea spaţiului de căutare
Dificultatea funcţiei de optimizat este reflectată de deviaţia standard care arată modul în care este acoperit spaţiul soluţiilor admisibile
s
( ) ( )( )( )xf
xfxfn
s
n
ii∑
=−
= 1
21
152
unde
( )
n
xf)x(f
n
ii∑
== 1
iar este dimensiunea populaţiei. nStudiile empirice asupra mărimii lui au arătat că o funcţie
pentru care are o valoare apropiată de
s
s 1.00 =s este uşor de
optimizat prin algoritmi genetici. Valoarea se calculează o singură dată, de obicei înaintea
rulării programului, pe o populaţie generată aleator. Pentru valori ale lui mult mai mari sau mai mici decât sunt necesare tehnici de
scădere sau de mărire a presiunii de selecţie.
s
s 0s
b) Corelaţia fitness-distanţă
Jones şi Forrest [50] au propus o altă mărime pentru predicţia comportării unui algoritm genetic: corelaţia dintre valoarea funcţiei fitness şi distanţa dintre cromozom şi soluţia optimală.
Dezavantajul metodei constă în faptul că nu se cunoaşte soluţia optimală. Pentru a depăşi acest impas, Schoenauer a propus să se utilizeze ca optim cromozomul cel mai bun din generaţia respectivă. Fie mulţimea valorilor fitness pentru populaţia
curentă şi
{ nfffF ,,, 21 L= }{ }nd,LddD ,, 21= mulţimea distanţelor de la fiecare
cromozom la cel mai bun din generaţia respectivă. Pentru şiruri de biţi
153
este uşor de lucrat cu distanţa Hamming care numără biţii pe care diferă cele două şiruri. Corelaţia fitness-distanţă se defineşte prin
DF
FD
sscr⋅
=
unde
( )( )ddffn
c i
n
iiFD −−= ∑
=1
1
este covarianţa DF − , Fs şi sunt deviaţiile standard iar Ds f şi d
sunt mediile lui şi respectiv . Mărimea F D r măsoară dificultatea rezolvării unei probleme de maximizare: o valoare a lui r apropiată de (valoarea minimă) indică o problemă uşor de rezolvat folosind algoritmi genetici iar o valoare apropiată de
1−1+ indică o problemă
foarte dificilă. Semnificaţiile lui r sunt inversate pentru probleme de minimizare. Toate studiile experimentale au confirmat aceste ipoteze.
Diverşi autori au studiat problema convergenţei algoritmilor genetici din diverse perspective. Majoritatea au utilizat lanţuri Markov finite, alţii au definit probabilitatea de convergenţă.
O altă abordare posibilă constă în folosirea tehnicilor de punct fix. Primul pas în această direcţie a fost făcut de Szalas şi Michalewicz [90] care au demonstrat matematic o idee intuitivă a convergenţei: singura cerinţă este o îmbunătăţire a populaţiei, fără să fie necesară o îmbunătăţire a celui mai bun individ.
Deşi teoria algoritmilor genetici oferă explicaţii cu privire la atingerea optimului căutat, aplicaţiile practice nu urmează întotdeauna teoria datorită următoarelor motive:
154
• codificarea problemei determină algoritmul să lucreze într-un spaţiu diferit de cel al problemei; • există limite cu privire la numărul iteraţiilor şi dimensiunea populaţiei.
Una din implicaţiile observaţiilor de mai sus este incapacitatea algoritmilor genetici de a găsi, în anumite condiţii, soluţia optimă, ducând la convergenţă prematură. Există unele metode de a combate convergenţa prematură: utilizarea încrucişării uniforme, detectarea indivizilor duplicaţi din populaţie.
Un rol important în determinarea vitezei de convergenţă îl are diversitatea populaţiei, care depinde de metoda de selecţie. Este recomandată selecţia după rang în detrimentul celei după fitness care promovează superelitele.
7.2. Algoritmul genetic modificat
Rudolph [72] a demonstrat că algoritmul clasic nu converge niciodată la soluţia optimă, dar versiunea modificată, care menţine cea mai bună soluţie în populaţie, face acest lucru.
Algoritmul genetic modificat (modGA) se obţine din cel clasic, prin modificarea pasului de selecţie. algoritmul modGA begin 0:=t iniţializează )(tP
155
evaluează )(tP
while not (condiţie-terminare) do begin 1: += tt selectează părinţii din )1( −tP
selectează indivizii ce vor fi eliminaţi din )1( −tP
formează ) prin reproducerea părinţilor (tP
evaluează )(tP
end end
În cei doi paşi de selecţie se selectează r cromozomi (nu neapărat distincţi) pentru a fi reproduşi şi r cromozomi distincţi care vor fi eliminaţi. Metoda de selecţie este cea a fitnessului relativ. Noua populaţie va consta din adăugarea la , în locul indivizilor
eliminaţi, a descendenţi rezultaţi din cei părinţi.
)1( +tP
r
)(tP
r Se procedează astfel: Pasul 1. Se selectează r părinţi din . Fiecare individ selectat
este marcat ca aplicabil la exact o operaţie genetică.
)(tP
Pasul 2. Se selectează rN − indivizi distincţi din şi se copiază
în , unde este dimensiunea populaţiei.
)(tP
)1( +tP N
156
Pasul 3. Cei părinţi selectaţi dau naştere la descendenţi care vor fi incluşi în .
r(tP
r)1+
Selectarea din paşii 1 şi 2 se face după fitness; astfel, un individ deasupra mediei are şanse mari de a fi selectat ca părinte şi în acelaşi timp de a face parte din noua populaţie. Pentru a aplica un tratament uniform tuturor operatorilor genetici, nu vom aplica doi operatori asupra aceluiaşi cromozom.
7.3. Algoritmul hillclimbing
Spaţiul de căutare este format din cromozomi de lungime . Există mai multe versiuni ale algoritmului hillclimbing, care diferă între ele prin modul de selectare a unui nou individ. O versiune a acestui algoritm (pentru o problemă de maximizare), folosind iteraţia MAX, este următoarea [60]:
L
algoritmul hillclimbing begin 0:=t iniţializează )(tP
repeat local:= FALSE selectează aleator un individ curent ci
evaluează ci
157
repeat generează descendenţi ai lui prin mutaţia unui bit în L ci ci
selectează dintre descendenţi individul care are cea mai ni
mare valoare a funcţiei obiectiv if ( ) ( )nc ifif <
then nc ii =:
else local:= TRUE until local 1: += tt until MAXt =end
Iniţial toţi cei descendenţi sunt luaţi în consideraţie, dar numai este selectat pentru a concura cu . Dacă
L
ni ci ( ) ( )nc ifif <
atunci noul individ ia locul celui curent. Altfel nu este posibilă o îmbunătăţire locală: algoritmul îşi atinge optimul (local sau global), adică . În acest caz se trece la iteraţia următoare pentru a selecta aleator un nou individ.
TRUE=:local
Succesul sau eşecul algoritmului depinde de cromozomul de start. Justificăm această afirmaţie pe exemplul următor. Spaţiul de căutare este format din cromozomi de lungime 30 iar funcţia ce urmează a fi maximizată este
( ) ( ) 15011 −⋅= vunuvf ,
unde funcţia întoarce numărul de cifre 1 ce apar în vectorul
ataşat unui cromozom. De exemplu, următoarele 3 şiruri
)v(unu
v
158
( )1011011011101011111111011010111 =v
( )1010100011001101110011100010012 =v
( )0010001000110010000000001000003 =v
vor avea evaluările
( ) 9215022111 =−⋅=vf ( )( )221 =vunu
( ) 1515015112 =−⋅=vf ( )( )152 =vunu
( ) 841506113 =−⋅=vf ( )( )63 =vunu
Funcţia are un maxim global pentru ( )111111111111111111111111111111=gv
egal cu
( ) 1801503011 =−⋅=gvf
şi un maxim local pentru ( )000000000000000000000000000000=lv
egal cu
( ) 150150011 =−⋅=lvf .
Dacă cromozomul iniţial are cel mult 13 de 1 atunci algoritmul se termină prin găsirea unui maxim local, deoarece: • dacă sunt 13 de 1, valoarea funcţiei obiectiv este 7 • dacă se creşte numărul de 1-uri la 14 atunci valoarea funcţiei obiectiv descreşte la 4 • un cromozom cu 12 de 1 dă valoarea 18 iar unul cu 11 dă valoarea 29, etc. Deci, trecând de la o iteraţie la alta cu paşi ”mici” se merge într-o direcţie greşită, către un maxim local.
159
7.4. Algoritmul călire simulată Structura acestui algoritm este următoarea [60]:
algoritmul călire simulată begin 0:=t iniţializează )(tP
iniţializează temperatura T selectează aleator un individ curent ci
evaluează ci
repeat repeat selectează un nou individ prin mutaţia unui bit în ni ci
if ( ) ( )nc ifif <
then nc ii =:
else if [ ) ( ) ( )⎭⎬⎫
⎩⎨⎧ −
<T
ififrandom cnexp1,0
then nc ii =:
until (condiţie-terminare) ( )tTgT ,:=
1: += tt until (criteriu de oprire) end
160
Funcţia [ )1,0random întoarce un număr aleator din [ )1,0
k
.
Condiţia de terminare verifică dacă a fost atins echilibrul termic, adică distribuţia de probabilitate a noului individ aproximează distribuţia Boltzmann. Totuşi, în multe aplicaţii, acest pas este executat de ori,
fiind un parametru al metodei. kTemperatura este micşorată în pasul
( )tTgT ,:= unde ( ) tTtTg ∀<, .
Algoritmul se termină pentru valori mici ale lui T : criteriul de oprire verifică dacă sistemul „îngheaţă”. Algoritmul de călire simulată poate evita optimul local. Considerăm aceeaşi funcţie ca la algoritmul hillclimbing. Fie individul definit de şirul 4i
( )1010100000001101110011100000014 =v
cu 12 de 1, având evaluarea
( ) 1815012114 =−⋅=vf .
Aşa cum am arătat anterior, algoritmul hillclimbing găseşte maximul local
( )000000000000000000000000000000=lv .
Pe de altă parte, algoritmul de călire simulată va accepta un şir cu 13 de 1 ca un şir curent, cu probabilitatea
( ) ( )⎟⎠⎞
⎜⎝⎛ −
=⎟⎠⎞
⎜⎝⎛ −
=T
expT
ififexpp cn 187
161
care, pentru temperatura 20=T dă
5769502011 .expp =⎟
⎠⎞
⎜⎝⎛−=
adică schimbarea este acceptată cu mai mult de 50%. Două şiruri relativ sărace
( )1110100000001101110011111000005 =v
şi ( )0101111111011011100100000000006 =v ,
fiecare având evaluarea 16, pot produce descendenţi mult mai buni dacă încrucişarea are loc între a 5-a şi a 12-a genă:
( )0101111111011011100111111000007 =v .
Noul descendent are evaluarea 7v
( ) 5915019117 =−⋅=vf .
7.5. Algoritmi de tip contracţie
O posibilitate de studiere a proprietăţilor de convergenţă a algoritmilor genetici constă în folosirea teoremei de punct fix a lui Banach, care lucrează cu aplicaţii de tip „contracţie” pe spaţii metrice.
Definiţia 7.1. Dacă R este mulţimea numerelor reale, o mulţime X cu o aplicaţie
RXXd →×: este spaţiu metric, notat ( )dX , , dacă următoarele
162
condiţii sunt verificate pentru orice : Xyx ∈,
i) şi ( ) 0, ≥yxd ( ) 0, =yxd yx =⇔
ii) ( ) ( )xydyxd ,, =
iii) ( ) ( ) ( )zxdzydyxd ,,, ≥+ .
Definiţia 7.2. Fie un spaţiu metric. O aplicaţie este contracţie
dacă şi numai dacă există o constantă
( dX , ) XXf →:
( )1,0∈c astfel încât pentru
orice :, Xyx ∈ ( ) ( )( ) ( )y,xdcyf,xfd ∗≤ .
Definiţia 7.3.
Şirul de elemente din spaţiul metric L,, 10 xx ( )dX , este şir Cauchy
dacă şi numai dacă pentru orice 0>ε există astfel încât pentru
orice ,
k
knm >, ( ) ε<nm xxd ,
L ,,,, 10 nxxx
. Un spaţiu metric este complet dacă
orice şir Cauchy are o limită L nxn
x∞→
= lim .
Teorema 7.1. Fie un spaţiu metric complet şi o contracţie de ( dX , ) XXf →:
constantă c . Atunci:
i) are un punct fix unic f ( ) *** : xxfx =
ii) dacă este un element oarecare din 0x X atunci şirul
aproximaţiilor succesive ( ) ( ) LL ,,,, 1010 −== nn xxxfx
*x .
fx este
convergent şi are ca limită pe
163
iii) are loc estimarea
( ) ( )10* ,
1, xxd
ccxxd
n
n −≤
Algoritmii genetici pot fi definiţi ca transformări între
populaţii. Dacă construim un spaţiu metric ( )dX , , având populaţii ca
elemente, şi o aplicaţie care satisface condiţiile unei teoreme de
punct fix atunci putem demonstra convergenţa unui algoritm genetic la un punct fix, indiferent de alegerea populaţiei iniţiale [90].
f
Fără a restrânge cu nimic generalitatea, presupunem că lucrăm cu probleme de maxim, adică probleme pentru care o soluţie este
mai bună decât soluţia dacă şi numai dacă
ix
jx ( ) ( )jixeval > xeval ,
unde funcţia eval dă fitnessul unui individ din populaţie. Pentru o populaţie considerăm funcţia de evaluare ; de
exemplu, pentru
P Eval
{ }nppP ,,2 Lp ,1= putem defini
( ) ( )∑=
=n
iipeval
nPEval
1
1 .
Teorema 7.2.
Fie X mulţimea tuturor populaţiilor P şi aplicaţia RXXd →×: definită prin
( ) ( ) ( )⎩⎨⎧
≠−++−+
==
2121
2121 ,11
,0,
PPpentruPEvalMPEvalMPPpentru
PPd
164
unde M este limita superioară a funcţiei eval în domeniul de interes.
Atunci este spaţiu metric complet. ( d, )X
Demonstraţie. Din pentru orice individ Mxeval ≤)( x , rezultă MPEval ≤)( pentru
orice populaţie P . Proprietăţile de spaţiu metric se verifică imediat: • pentru orice populaţii şi ; în plus, ( ) 0, 21 ≥PPd 1P 2P
dacă şi numai dacă ( ) 0, 21 =PPd 21 PP =
• ( ) ( )1221 ,, PPdPPd =
• ( ) ( ) ( ) ( ) +−++−+=+ 213221 11,, PEvalMPEvalMPPdPPd
( ) ( ) ≥−++−+ 32 11 PEvalMPEvalM
( ) ( ) ( )3131 ,11 PPdPEvalMPEvalM =−++−+
În plus, spaţiul metric ( )dX , este şi complet, deoarece: pentru orice
şir Cauchy de populaţii există astfel încât pentru orice
, ; ultima egalitate rezultă din faptul că algoritmii
genetici lucrează cu spaţii finite, deci există un număr finit şi mărginit de populaţii. Înseamnă că orice şir Cauchy este convergent.
L,, 21 PP
kP=
k
kn > nP
În continuare vom defini pe mulţimea tuturor populaţiilor o
aplicaţie care să fie contracţie. Pentru aceasta, plecând de la o
populaţie vom rula selecţia şi încrucişarea până când se obţine o
populaţie ce satisface o anumită relaţie în raport cu şi vom
lua ' .
f
(P
'P
)1 =
)t
P
)(tP
(tP +
165
Teorema 7.3. Fie spaţiul metric complet definit în teorema precedentă
şi aplicaţia
( dX , ) definită prin XXf →: ( )( ) ( )1+= tPtPf dacă şi numai
dacă ( ( )) ( )( )1+< Evalt tPPEval .
Atunc şi acesta poate fi obi are un punct fix unic ţinut prin metoda
Demonstr ie. Considerăm două iteraţii consecutive în care funcţia
f
aaproxim ţiilor succesive plecând de la orice populaţie iniţială XP ∈)0( .
aţf realizează o îmbunătăţire a populaţiei în raport cu funcţia Eval :
( )( ) ( )( )( ) ( )( )1111 +=< tPEvaltPfEvaltPEval
( )( ) ( )( )( ) ( )( )1222 +=< tPEvaltPfEvaltPEval ;
atunci
( )) ( )( )) ( )(( ( )( ) ( )( )( ) <−++−+= tPfEvalMtPfEvalMtPftPfd 2121 11, ( )( ) ( )( ) ( ) ( )( )tPtPdtPEvalMtPEvalM 2121 ,11 =−++−+ .
Înseamnă că funcţia
( ) ( )1+⎯→⎯ tPtP f
este contracţie şi, conform Teoremei 7.1, avem
( )( )0lim* PfP ii ∞→
= ,
unde cu am notat aplicarea funcţiei de ori. Rezultă că
algoritmul genetic care funcţionează ţiei converge
la populaţ
if
ia
f
pe principiul contrac
i
*P , care este unicul punct fix din mulţ ea populaţiilor. im
166
Observaţie. Din definiţia funcţiei Eval rezultă că punctul fix
*P este obţin când toţi indivizii acestei populaţii dau aceeaşi valoare, ut are coincide cu maximul global.
urm
algoritmul C-GA begin
luează
whil not (condiţie-terminare) do con ruieşte contracţia}
din
c
Structura algoritmului de tip contracţie (C-GA) este ătoarea
0:=t )(tP iniţializează
)(tP eva
e begin { se st selectează
1: += tt )(tP )1( −tP
recombină )(tP
)(tP evaluează
if (( )) ( )( )EvtPEval ≥ tPal−1
then 1: t= −t end end Alte abordări pot fi găsite în [46, 47].
167
7.6. Algoritmi cu dimensiunea variabilă a
diversi resiunea selecţiei, care la rândul lor sunt influen te de mărimea populaţiei. Diverse studii efectuate asupra dimens
neraţia anterioară
populaţiei Performanţele metodelor bazate pe evoluţie depind de
tatea populaţiei şi de pţaiunii populaţiei au arătat că algoritmii cu dimensiunea variabilă
a populaţiei dau rezultate destul de bune. Grefenstette [39] a aplicat un meta-algoritm genetic pentru a controla parametrii altui algoritm, inclusiv dimensiunea populaţiei. Goldberg [32] a efectuat un studiu teoretic al dimensiunii optime a populaţiei. Studii experimentale au fost efectuate în [49] .
Vom discuta acest tip de algoritmi genetici urmând rezultatele din [1]. Numărul indivizilor de la generaţia t , notat )(tPopSize , va fi
influenţat de cel de la ge
( ) ( ) ( ) ( )tDtAuxPopSizetPopSizetPopSize −+=+1 ,
unde AuxPopSize reprezintă populaţia intermediară care apare în
inare iar pasul de recomb ( )tD reprezintă numărul de indivizi ce nu
vor supravieţui în generaţia următoare. Dimensiunea populaţiei intermediare se calculează cu formula
( ) ( ) ρ∗= tPopSizetAuxPop , Size
168
unde ρ este un parametru al algoritmului, numit rată de reproducere.
parame
ra algoDimensiunea Variabila a Popula
ializează
ţie-terminare) do
pentru fiecare individ din populaţie
bină
ţi indivizii pentru care
Toţi indivizii unei generaţii au aceeaşi probabilitate de a fi selectaţi pentru reproducere.
Deoarece fitnessul nu influenţează selecţia, vor fi folosiţi alţi
tri: VÂRSTA şi AVIAŢ . VÂRSTA reprezintă numărul de
generaţii în indi p r AVIAŢ se atribuie o
singură dată unui individ, după iniţializare sau combinare, şi păstrează o valoare constantă. Un individ este menţinut în populaţie
atâta timp cât VÂRSTA nu depăşeşte AVIAŢ .
Structu ritmului AG-DVP (Algoritm Genetic cu
care un vid a su ravieţuit ia
după re
ţiei) este următoarea.
algoritmul AG-DVPbegin
0= :tţ ini )(tP
evaluează P )(t
while not (condi begin 1: += tt
1: +=VÂRSTAVÂRSTA
recom )(tP
elimină din to)(tP
AVVÂRSTA > IAŢ
169
evaluează
etrul depinde de starea curentă a căutării genetice;
ta se u
eraţia curentă
nimă nessului, ob tă până în
oate fi definită în mai
multe forţională:
)(tP
end end
Param AVIAŢ
pentru aceas tilizează următorii parametri: • AvgFit = media fitnessului populaţiei curente
• = valoarea maximă a fitnessului în genMaxFit • = valoarea minimă a fitnessului în generaţia curentă MinFit • ax şi AbsFitMin = valoarea maximă şi respectiv miAbsFitMa fit ţinu momentul curent.
Pentru un individ i , viaţa lui )(iAVIAŢ p
eluri: • alocare prop
( )⎟⎟⎠
⎞⎜⎜⎝
⎛+( ) =iAVIAŢ min MaxLT
AvgFitifitnessMinLT ,η
• alocare liniară
) ( )AbsFitMinAbsFitMax
AbsFitMinifitnessMinLT −(iAVIAŢ−
+= η2
• alocare biliniară
170
( )
( )
( )
( ) ( )
( )⎪⎪⎪⎪⎪
⎩
⎪⎪⎪⎪⎪
⎨
⎧
<
−−
++
≥−−
+
=
21
ifitnessAvgFită dac
AvgFitMaxFitAvgFitifitnessMaxLTMinLT
ifitnessAvgFită dacMinFitAvgFitMinFitifitnessMinLT
iAVIAŢ η
η
unde şi reprezintă v aloarea maximă şi respectiv minimă a parametrului iar
MaxLT MinLTVIAŢA
( )MinLTMaxLT −=21η .
Alocarea proporţională este inspirată din selecţia după metoda ruletei: valoarea parametrului este proporţională cu fitnessul,
în limitele şi . În cazul alocării liniare, este
calculată prin raportare la fitnessul cel mai bun până în momentul prezent. În cazul când în populaţie există indivizi al căror fitness este egal sau apropiat de fitnessul maxim absolut, va lua valori
mari, ceea ce duce la mărirea dimensiunii populaţiei. Alocarea biliniară face un compromis între celelalte două, luând în considerare valorile extreme din generaţia curentă.
AVIAŢ
MinLT MaxLT AVIAŢ
AVIAŢ
Funcţii recomandate pentru a testa algoritmul AG-DVP sunt: • ( ) ( ) 12,110sin1 ≤≤−+−= xxxxf π
care este o funcţie cu multe maxime locale
171
• ( ) ( ) 10,8/82 ≤≤= xxegerintxf , care nu poate fi optimizată prin
metode de tip gradient
• , care reprezintă o problemă
„deceptivă”.
21),()(3 ≤≤−⋅= xxsignxxf
Se pot alege următoarele valori pentru parametri: • dimensiunea populaţiei =20 • 4.0=ρ
• probabilitatea de mutaţie: 015.0=mp
• probabilitatea de încrucişare: 65.0=cp
• lungimea unui cromozom = 20 • , 7=MaxLT 1=MinLT
Algoritmul se poate opri când nu se mai obţin ameliorări ale celei mai bune valori într-un număr precizat de iteraţii.
7.7. Algoritmi cu constrângeri Există mai multe modalităţi de a mânui constrângerile:
1) rezolvarea problemei făcând abstracţie de constrângeri şi eliminarea, apoi, a soluţiilor care nu verifică constrângerile. Aceste soluţii vor determina o penalizare a funcţiei de evaluare; cea mai simplă formă de penalizare constă în eliminarea soluţiilor nerealizabile
2) utilizarea unor metode de „reparare” a soluţiei nerealizabile
172
dar, uneori, aceste metode sunt la fel de dificile ca şi rezolvarea problemei
3) utilizarea unor metode de decodificare care să garanteze sau să mărească foarte mult şansele de obţinere a unor soluţii realizabile.
Exemplificăm rezolvarea unor astfel de probleme considerând problema rucsacului [56]: „fiind date ponderile [ ]iW , profiturile
şi capacitatea , să se găsească vectorul binar
[ ]iP
C [ ] [ ]( )nx,,Lxx 1= astfel
încât
[ ] [ ] CiWixn
i≤⋅∑
=1
şi
( ) [ ] [ ]∑=
⋅=n
iiPixx
1P
are valoarea maximă.” Trei tipuri de algoritmi sunt frecvent utilizaţi: algoritmi bazaţi pe
funcţii de penalizare ( ), algoritmi bazaţi pe metode de reparare
(
][iAp
][iAr ) şi algoritmi bazaţi pe decodificare ( ), unde este
indicele unui algoritm particular din clasa respectivă.
][iAd i
Algoritmii ][iAp
În cadrul acestor algoritmi soluţia este reprezentată printr-un şir binar de lungime . Funcţia de evaluare a unui şir n x este
[ ] [ ] ( )∑=
−⋅=n
ixPeniPixxeval
1)(
173
unde functia de penalizare are valoarea zero pentru soluţiile
realizabile
)(xPen
x , adică pentru soluţiile care satisfac relaţia
[ ] [ ]∑=
≤⋅n
iCiWix
1,
şi este mai mare ca zero în caz contrar.
Sunt mai multe posibilităţi de definire a funcţiei de penalizare; vom prezenta trei metode:
• metoda logaritmică [ ]( )1pA :
( ) [ ] [ ] ⎟⎟⎠
⎞⎜⎜⎝
⎛⎟⎟⎠
⎞⎜⎜⎝
⎛−⋅+= ∑
=
n
iCiWixxPen
12 1log ρ
• metoda liniară [ ]( )2pA :
( ) [ ] [ ] ⎟⎟⎠
⎞⎜⎜⎝
⎛−⋅= ∑
=
n
iCiWixxPen
1ρ
• metoda pătratică [ ]( )3pA :
( ) [ ] [ ]2
1
2 ⎟⎠
⎞⎜⎝
⎛−⋅= ∑
=
n
iCiWixxPen ρ
În toate cazurile,
[ ][ ]⎭⎬⎫
⎩⎨⎧
== iW
iPni ,1
maxρ .
174
Algoritmii ][iAr
La fel ca în cazul anterior, soluţia este reprezentată printr-un şir binar de lungime . Fitnessul unui şir n x se defineşte ca fiind
[ ] [ ]∑=
⋅=n
iiPixxeval
1')(
unde vectorul este versiunea reparată a vectorului original 'x x . Apar două probleme: • există mai multe metode de reparare • numai o parte din cromozomii reparaţi îi vor înlocui pe cei originali în populaţie. Orvosh şi Davis [68] au aratat că cea mai bună rată de înlocuire este . %5
Procedura generală de reparare este Algoritm repar ( )x
begin rucsac-plin:= false xx =:'
if [ ] [ ]∑=
>⋅n
iCiWix
1'
then rucsac-plin:=true while (rucsac-plin) do begin un obiect selectat din rucsac =i
schimbă valoarea obiectului selectat: [ ] 0:' =ix
175
if [ ] [ ]∑=
≤⋅n
iCiWix
1'
then rucsac-plin:=false end end
Există două variante ale acestui algoritm, în funcţie de modul de efectuare a selecţiei: • repararea aleatoare [ ]( )1rA : se alege, în mod aleator, un obiect din
rucsac • repararea greedy [ ]( )2rA : obiectele se ordonează descrescător
după raportul pondereprofit şi se selectează ultimul element.
Algoritmii ][iAd
Aceştia folosesc o reprezentare de tip întreg, componenta a -a, , a unui cromozom fiind un întreg din intervalul
i
[ ]ix [ ]1,1 +− in . De
fapt, reprezentarea este de tip ordinal, în sensul că pe lângă vectorul x se foloseşte şi o listă de obiecte; vectorul este decodificat prin selectarea obiectului corespunzător din lista curentă. De exemplu, pentru lista vectorul este decodificat
în următoarea secvenţă: 4, 3, 6 (deoarece 6 este al 4-lea element din lista curentă după ce au fost eliminate elementele de pe poziţiile 4 şi 3), 1, 2 şi 5. Operatorii genetici acţionează ca în cazul general, cu mici
( )6,5,4,3,2,1=L ( 1,1,1,4,3,4 )
176
adaptări. De exemplu, mutaţia elementului de pe poziţia va determina înlocuirea acestuia cu un număr din intervalul
i
[ ]1,1 +− in .
Algoritmul de decodificare este următorul:
Algoritm decod ( )x
begin construct lista de obiecte L 1:=i 0:=ofitPrSum
0:=SumPonderi while do ni ≤ begin [ ]ixj =:
elimină elementul aflat pe poziţia j în lista L
if [ ] CjWSumPonderi ≤+ then
begin [ ]jWSumPonderiSumPonderi +=:
[ ]jPofitPrSumofitPrSum +=:
end 1: += ii end end În funcţie de modul de definire a procedurii construct există două tipuri de algoritmi:
177
• , în care lista [ ]1dA L este construită în mod aleator
• , în care lista [ ]2dA L se construieşte ordonând descrescător
elementele după raportul pondereprofit ; de exemplu, [ ] 23=ix este
interpretat ca al 23-lea element (în ordinea descrescătoare a raportului pondereprofit ) din lista curentă.
7.8. Algoritmi genetici dezordonaţi Algoritmii de acest tip au fost introduşi pentru a creşte
performanţele algoritmilor genetici prin păstrarea blocurilor în urma aplicării operatorilor de evoluţie. Aşa cum am văzut, blocul este o succesiune de gene (biţi) cu semnificaţie specială în cadrul cromozomului. Pentru a evita distrugerea, legăturile dintre gene trebuie să fie suficient de puternice în interiorul blocului.
Goldberg, Korb şi Deb [34] au propus o generalizare a algoritmilor genetici, cunoscută sub numele de algoritmi genetici dezordonaţi (messy genetic algorithms), care folosesc cromozomi de dimensiune variabilă cu gene care pot fi aranjate în orice ordine; de aici denumirea de dezordonaţi. Fiecare genă este reprezentată printr-o pereche de forma (poziţia genei, valoarea genei). De exemplu, cromozomul codificat binar
( )01001=c
se transformă în noua reprezentare în
178
( ) ( ) ( ) ( ) ( )( )0,51,40,30,21,1'=c .
Această reprezentare are următoarele avantaje:
• ordinea perechilor poate fi schimbată fără ca semnificaţia cromozomului să aibă de suferit
• se poate lucra cu informaţie incompletă, dată de absenţa unor gene – fenomen numit subspecificare. În acest caz apare următoarea întrebare: cum se evaluează un cromozom incomplet? Un posibil răspuns este următorul: se asimilează acest cromozom cu cel complet aflat cel mai aproape
• permite prezenţa multiplă a unei gene în cromozom, fenomen numit supraspecificare; de exemplu, în cromozomul
( ) ( ) ( ) ( ) ( )( )1,31,40,30,21,1=c
gena de pe poziţia 3 apare de două ori cu valorile contradictorii 0 şi 1.
Acest conflict poate fi rezolvat în mai multe feluri; de exemplu, se ia în consideraţie apariţia cea mai din stânga a genei.
Operatorii evolutivi utilizaţi de algoritmii genetici dezordonaţi derivă din cel clasici.
Incrucişarea se desfăşoară astfel [15]:
• în fiecare din cei doi părinţi se stabileşte câte un punct de încrucişare care „taie” cromozomul în două subşiruri; cele două puncte de încrucişare se aleg independent
• subşirurile obţinute anterior se „alipesc” în orice ordine sau combinaţie pentru a obţine un nou individ
179
Fie cromozomii
432121 |: bbbbaax şi 1321 |: dcccy
unde simbolul „|” reprezintă punctul de încrucişare (taietură). Prin încrucişare rezultă următorii descendenţi
121 |: daada −
32121 |: cccaaca −
21321 |: aacccac −
4321321 |: bbbbcccbc −
211 |: aadad −
43211 |: bbbbdbd −
3211 |: cccdcd −
214321 |: aabbbbab −
3214321 |: cccbbbbcb −
14321 |: dbbbbdb −
unde prin şi am notat subşirurile definite de punctele de
tăietură din cei doi cromozomi. Încrucişarea de acest tip implică şi un anumit tip de inversiune: cromozomii şi
cba ,, d
ab − cd − se obţin inversând subşirurile determinate de punctele de tăietură.
Mutaţia acţionează ca în cazul clasic, folosind oricare din variantele utilizate în acest caz.
Diverse experimente [35] au scos în evidenţă faptul că algoritmii dezordonaţi găsesc întotdeauna soluţia optimă chiar dacă
180
timpul de căutare creşte polinomial în raport cu numărul de variabile.
7.9. Algoritmi virali
Cunoscuţi şi sub numele de metoda VEGA (Virus – Evolutionary Genetic Algorithm) , algoritmii virali au fost introduşi [85] pentru a preveni convergenţa prematură generată de absenţa diversităţii populaţiei. Algoritmii virali lucrează simultan cu două populaţii: • populaţia gazdă, care, la fel ca în cazul algoritmilor clasici, reprezintă mulţimea soluţiilor posibile • populaţia virală, care este o mulţime de subşiruri ale indivizilor din populaţia gazdă; rolul său este de a realiza infecţia virală.
Un virus este un subşir ce conţine trei caractere { }∗,1,0 şi are
aceeaşi lungime cu individul gazdă. Caracterele diferite de * reprezintă informaţia transportată de virus.
Există doi operatori de infecţie virală [53]:
• transcrierea inversă: virusul scrie informaţia sa peste cea a individului gazdă pentru a genera un nou individ. De exemplu, individul gazdă 11001
şi virusul 001 ∗∗
181
dau un nou individ gazdă 01011
• încorporarea, care are rolul de a genera noi viruşi şi se realizează în două moduri:
- prin copierea într-un virus a unor gene dintr-un individ gazdă infectat, folosind o probabilitate de copiere. De exemplu, virusul 001 ∗∗
şi individul gazdă 11001
generează, prin copiere, un nou virus 001 ∗1
- prin înlocuirea unor gene din virus cu caracterul *, folosind o probabilitate de înlocuire. De exemplu, virusul 001 ∗∗
generează, prin încorporarea de tip înlocuire, un nou virus 00 ∗∗∗
Fiecare virus este caracterizat de puterea de infectare .
Notăm cu şi valorile fitness ale individului
i ifitv
jfithinit jfithfin j
înainte şi respectiv după infectare. Îmbunătăţirea obţinută prin infectarea individului j cu virusul i este
jjji fithinitfithfinfitv −=, .
Acum puterea de infectare a virusului i se calculează ca fiind
182
∑∈
=Sj
jii fitvfitv ,
unde este mulţimea indivizilor gazdă infectaţi cu virusul i . Un alt
parametru important este rata de infecţie , care se defineşte prin
una din formulele
S
irinf
( )⎩⎨⎧
⋅−
>⋅+=+ contrarcazînrinf)(
fitvdacărinfrinf
t,i
it,it,i α
α1
011
⎪⎩
⎪⎨⎧
⋅
>⋅=
−
+ contrarcazînrinffitvdacărinf
rinft,i
it,it,i α
α 01
1
unde α este un coeficient pozitiv iar este numărul generaţiei. În plus,
t
dacă ratăMaxrinf ti _1, >+
atunci ratăMaxrinf ti _1, ←+ .
Fiecare virus are o putere de supravieţuire în generaţia următoare dată de
ititi fitvliferlife +⋅=+ ,1,
unde r este rata de reducere a vieţii. După infectarea indivizilor gazdă, viruşii evoluează prin încorporare: • dacă , virusul evoluează prin operaţia de copiere
(extinderea încorporării) aplicată unui individ infectat
0>ifitv
• dacă 0 , se execută operaţia de înlocuire (micşorarea
încorporării).
≤ifitv
183
Lungimea unui virus se modifică în concordanţă cu probabilitatea de încorporare . După calcularea puterii de viaţă,
dacă 0 , virusul elimină un nou subşir dintr-un individ gazdă
infectat, selectat aleator (generarea încorporării). Infecţia virală se desfăşoară conform schemei din figura de mai jos.
Pinc
1, <+tilife
Algoritmul metodei VEGA este următorul:
Algoritmul VEGA begin iniţializare repeat selecţie încrucişare mutaţie infecţie virală înlocuire until (condiţie terminare) end.
184
EVALUARE INDIVIZI GAZDA
CRESTE RATA DE INFECTIE
DESCRESTE RATA DE INFECTIE
GENEREAZA INCORPORAREA
MICSOREAZA INCORPORAREA
EXTIDE INCORPORAREA
SELECTIE INDIVIZI GAZDA
INFECTIE
ilife CALCULEAZA ilife CALCULEAZA
0IF >ifitvDA NU
DA NU
ilifeIF
ifitv CALCULEAZA
Figura 7.1. Schema infecţiei virale
185
Prin iniţializare se generează aleator populaţia gazdă iar
indivizii de tip virus se obţin ca subşiruri ale indivizilor gazdă. Arhitectura de bază a metodei se bazează pe modelul SSGA ( Steady-State Genetic Algorithm) care înlocuieşte indivizii cei mai slabi cu o pereche de descendenţi obţinuţi prin încrucişare şi mutaţie. După infecţie, părintele va fi înlocuit cu individul virusat dacă fitnessul său este mai bun decât al părintelui.
7.10. Algoritmul delta
Algoritmul delta are rolul de a îmbunătăţii performanţele referitoare la timp şi precizie. Fiecare soluţie posibilă, reprezentată
printr-un vector , are asociat un vector al perturbaţiilor care pot îmbunătăţi soluţia curentă. Se lucrează cu două tipuri de populaţii: cea a soluţiilor posibile şi cea a perturbaţiilor, ceea ce impune câte un nivel de căutare pentru fiecare populaţie. Un mecanism similar se întâlneşte şi la strategiile evolutive, dar în acest caz cele două nivele sunt mai puţin separate.
nRx∈ nR∈δ
Modul de lucru este dat de următorul algoritm [16].
Algoritmul delta begin • se iniţializează o populaţie de soluţii potenţiale while (not condiţie terminare) do
186
begin • se foloseşte un algoritm genetic (notat AGS) pentru a obţine o
soluţie *x • se iniţializează o populaţie de perturbaţii aleatoare • se foloseşte un algoritm genetic (notat AGP) pentru a obţine
perturbaţia optimă *δ
• se actualizează soluţia : *x ***1 δ+= xx
• se compară cu şi se reţine soluţia mai performantă *x *1x end end
În majoritatea implementărilor algoritmii genetici AGS şi AGP sunt identici, din motive de simplitate. În anumite situaţii este mai convenabil ca ei să fie diferiţi sau chiar să fie înlocuiţi (ambii sau doar unu) cu strategii evolutive.
7.11. Studiul calitativ al algoritmilor genetici
Algoritmii genetici, fiind algoritmi nedeterminişti, nu pot fi studiaţi cu instrumentele specifice algoritmilor clasici. În general, studiul agoritmilor evolutivi se face cu metode statistice [55], care • evaluează acurateţea şi robusteţea algoritmului studiat
187
• compară performanţele a doi algoritmi genetici folosiţi pentru a rezolva aceeasi problemă.
Prima direcţie implică studiul unor statistici ale uneia sau mai multor variabile aleatoare, care dau informaţii cu privire la valoarea medie a soluţiei optimale şi la robusteţea sa (constanţa aproximării în rulări diferite). Generaţia a unui algoritm genetic poate fi
interpretată ca fiind un eşantion al unei variabile aleatoare , pentru
care se pot lua în calcul diferite statistici
n
nX
( )nXt
k
: fitnessul celui mai
bun cromozom, fitnessul mediu al populaţiei, etc. După rulări ale
algoritmului (în condiţii identice) se obţin valori
k
( )kYY ,,L1 ale
variabilei . Pentru aceste valori se pot calcula: ( nXtY = )
• media: Yk
YM
k
ii
==∑=1
• dispersia: ( )
11
2
2
−
−=∑=
k
MYD
k
ii
• deviaţia standard: 2Ds = • intervalul de încredere pentru medie • intervalul de încredere pentru dispersie.
Intervalul de încredere pentru medie se calculează cu statistica Student cu grade de libertate: intervalul de încredere pentru media
1−kμ cu nivelul de încredere α este
⎥⎦
⎤⎢⎣
⎡ ⋅+
⋅−
ksaY
ksaY ,
188
unde se obţine din tabelele distribuţiei Student astfel încât să fie îndeplinită condiţia
a
αμ=⎟⎟
⎠
⎞⎜⎜⎝
⎛<
−<− a
ksYaP .
Intervalul de încredere pentru dispersie se calculează cu
statistica : pentru nivelul de încredere 21−kχ α şi valorile şi extrase
din tabelele distribuţiei astfel încât
a b2
1−kχ
( )2
121
αχ −=>− aP k şi ( )
212
1αχ −
=<− bP k
intervalul de încredere pentru dispersie este
( ) ( )⎥⎦
⎤⎢⎣
⎡ −−a
Dkb
Dk 22 1,1 .
Pentru a rezolva o problemă dată se pot folosi diverşi algoritmi genetici, diversitatea fiind determinată de: structura generală a algoritmului, modul de codificare, populaţia iniţială, funcţia fitness, condiţia de oprire, metoda de selecţie, operatorii genetici, valorile parametrilor. În mod firesc, apare întrebarea: care este cel mai bun algoritm genetic pentru rezolvarea unei probleme date? Se pot comparea doi algoritmi genetici verificând ipoteze statistice cu privire la medie şi dispersie. Fie X şi Y variabilele aleatoare ce descriu evoluţia a doi algoritmi genetici, ambele obţinute prin calcularea aceleeaşi statistici
în generaţia : n ( )nXX t= , ( )nYtY = . Pentru valori 1k ( )1,,1 kXX L
ale variabilei X şi valori 2k ( )2k,,1 YY L ale variabilei Y calculăm
189
1
1
1
k
XX
k
i
i∑== ,
2
1
2
k
YY
k
i
i∑== ,
( )∑−
−−
=1
1
2
1 11 k
i
iX XX
kS , ( )∑
−
−−
=2
1
2
2 11 k
i
iY YY
kS
( ) ( )2121
22
21 11
211
kkkkSkSk
S YXYX +
−+
−+−=
−.
Asupra mediei, se verifică ipotezele:
H : 0 YX μμ = , care spune că cei doi algoritmi dau, în medie, aceleaşi
valori ale soluţiei optimale; deci nu există, din punct de vedere statistic, o diferenţă de comportament între cei doi algoritmi.
H : 1 YX μμ ≠ , adică cei doi algoritmi dau, în medie, soluţii optimale
diferite pentru problema în discuţie.
Pentru verificarea acestor ipoteze se foloseşte statistica
( ) ( )
YX
YX
SYX
−
−−− μμ
a cărei distribuţie este . Pentru a verifica cele două ipoteze se
foloseşte algoritmul următor
221 −+kkt
Algoritmul: ipoteze asupra mediei
P1. Se stabileşte nivelul de încredere α , cu următoarea semnificaţie:
dacă ipoteza este adevărată atunci din 100 de teste, în ( )α−1100
cazuri ipoteza poate fi respinsă
190
P2. Pentru nivelul de încredere α şi 221 −+ kk grade de libertate se
găseşte, din tabelele corespunzătoare statisticii t , valoarea a
P3. Se calculează valoarea ( )YXS
YXt−
−−=
0 , deoarece se verifică
ipoteza H . 0
P4. Dacă ata <<− atunci se acceptă ipoteza H ; în caz contrar se 0
acceptă ipoteza H 1 .
Asupra dispersiilor se verifică ipoteze similare mediilor
H : , 022YX σσ =
H : , 122YX σσ ≠
unde şi sunt dispersiile corespunzătoare variabilei 2Xσ 2
Yσ X şi
respectiv Y ; se foloseşte statistica 2
2
Y
X
SS
care are distribuţia cu
grade de libertate. Se urmează paşii algoritmului
următor.
F
( ,1 2k )1−1 −k
Algoritmul: ipoteze asupra dispersiei
P1. Se stabileşte nivelul de încredere α
P2. Pentru nivelul de încredere α şi gradele de libertate ( )1,1 21 −− kk
se determină, din tabelele corespunzătoare distribuţiei , valorile F şi b astfel încât a
( )2
1 α−=< aFP şi ( )
21 α−
=> bFP
191
P3. Se calculează valoarea 2
2
Y
X
SS
f = , prin raportarea dispersiei mai
mari la cea mai mică P4. Dacă atunci se acceptă ipoteza H 0 ; în caz contrar se bfa <<
acceptă ipoteza H 1 .
Acceptarea ipotezei H spune că cei doi algoritmi au dispersii
statistic egale, deci sunt la fel de robuşti. Acceptarea ipotezei H 1
spune că dispersiile celor doi algoritmi sunt statistic diferite, deci cel cu dispersia mai mică este mai robust.
0
Evident aceleaşi metode pot fi folosite pentru a compara orice algoritmi evolutivi.
8 STRATEGII EVOLUTIVE
8.1 Generalităţi
Strategiile evolutive (SE) au apărut din necesitatea de a
rezolva probleme de optimizare de tipul: “se cere cu nRDx ⊆∈*
( ) ( ) Dxxfxf ∈∀≤* , unde şi este o regiune
mărginită determinată de restricţiile impuse asupra lui
RRDf n →⊆: D
x ”. Pentru o astfel de problemă strategiile evolutive sunt mai potrivite decât algoritmii genetici deoarece nu necesită codificarea binară a datelor, care are dezavantajul că limitează precizia. Strategiile evolutive reprezintă indivizii sub forma unor vectori cu componente reale şi folosesc mutaţia ca principal operator de evoluţie.
În strategiile evolutive avansate reprezentarea indivizilor încorporează în ea şi parametrii de control ai strategiei. Un individ se reprezintă ca o pereche ( )σ,xv = , unde vectorul x este un element
din spaţiul de căutare iar este vectorul dispersie; reprezintă
dispersia perturbaţiei pe care o suferă componenta a vectorului
2σ 2iσ
ix x
194
în procesul de mutaţie. Vectorul σ reprezintă parametrul de control al strategiei.
Primul algoritm de tip strategie evolutivă a fost propus în 1964, la Universitatea Tehnică din Berlin, de către Rechenberg şi Schwefel în scopul rezolvării unei probleme care cerea amplasarea unei conducte flexibile într-o zonă de o anumită formă astfel încât costul să fie cât mai mic. Ideea rezolvării era: pornind de la o aproximaţie curentă se genera alta printr-o perturbaţie aleatoare bazată pe o repartiţie normală şi se alegea cea mai bună dintre cele două. Această strategie, numită ( )11+ , nu opera cu populaţii ci urmărea
adaptarea unui singur individ sub acţiunea mutaţiei. Limitele acestui model au dus la căutarea unor mecanisme care să implice în evoluţie mai mulţi indivizi [5, 6, 7, 8, 9, 15, 16, 81, 82]. Dintre acestea amintim:
• Strategia ( )λμ, : pornind de la cei μ indivizi ai populaţiei curente,
se generează prin încrucişare şi mutaţie μλ > indivizi noi, iar dintre
aceştia se aleg μ , care vor forma noua populaţie; dacă 1=μ , se alege
idul cel mai bun ( cel pentru care funcţia obiectiv este cea mai mică). indiv
) • Strategia ( λμ + : pornind de la cei μ indivizi ai populaţiei
curente, se generează prin încrucişare şi mutaţie un număr de λ indivizi noi care se adaugă la populaţia curentă; din populaţiile reunite se selectează μ indivizi care vor forma noua populaţie. Dacă 1=μ ,
195
se foloseşte doar mutaţia pentru a genera indivizi noi, fiind evident că încrucişarea nu poate fi utilizată. Dacă 1=λ , selecţia urmăreşte eliminarea celui mai slab individ (cel care dă cea mai mare valoare a funcţiei obiectiv) din populaţiile reunite. Este evident că dacă individul nou generat este mai slab decât toate elementele populaţiei curente atunci aceasta rămâne nemodificată. • Strategia ( )pk ,,, λμ : este o extindere a strategiei ( )λμ, şi se
caracterizează prin: a) 1≥k reprezintă durata de viaţă a indivizilor, măsurată în
generaţii. Valoarea lui se micşorează cu 1 la fiecare nouă generaţie iar un individ va fi selectat doar dacă .
k0>k
b) operaţiile de mutaţie şi încrucişare sunt controlate de probabilităţile şi respectiv , la fel ca în cazul algoritmilor
genetici. mp cp
c) numărul părinţilor folosiţi în operaţia de încrucişare este p
d) se pot folosi şi operatori de încrucişare specifici algoritmilor genetici, ca de exemplu încrucişarea multiplă.
• Strategia evolutivă rapidă: este o variantă, încadrată de autorii ei la programarea evolutivă, caracterizată prin:
a) foloseşte o mutaţie specifică bazată pe perturbarea elementelor cu valori generate în conformitate cu distribuţia Cauchy a cărei funcţie de densitate este:
( )1
22 +=
σπϕ ,
x)x( 0>σ
196
Acest tip de perturbaţie prezintă avantajul că poate genera descendenţi îndepărtaţi de părinţi cu o probabilitate mai mare decât perturbaţia normală (asigurând o probabilitate mai mare de evadare din minime locale şi o accelerare a procesului de găsire a optimului). Diferenţa dintre cele două funcţii de densitate (normală şi Cauchy) este ilustrată în figura 8.1.
b) perturbaţiile sunt independente iar parametrii iσ sunt
determinaţi prin autoadaptare (cu perturbare log-normală) la fel ca în cazul strategiilor evolutive clasice.
c) nu se foloseşte încrucişare nici asupra componentelor propriu-zise nici asupra parametrilor de control.
d) selecţia este de tip turneu.
Figura 8.1: Funcţiile de distribuţie ale repartiţiilor normală (linie întreruptă) şi Cauchy (linie continuă)
197
8.2 Operatori de evoluţie
8.2.1 Încrucişarea Operatorul de încrucişare selectează, cu o probabilitate
uniformă, cei p părinţi. Cel mai des se utilizează cazurile 2=p şi
μ=p . Datorită similarităţii dintre reprezentarea indivizilor în
strategii evolutive şi în algoritmi genetici, există similaritate şi între tipurile de încrucişare.
8.2.1.1 Încrucişarea discretă
În cazul 2=p fie şi părinţii selectaţi aleator; pentru 1x 2x
fiecare componentă { }ni ,,2,1 L∈ se generează un număr aleator
, urmând distribuţia uniformă. Componenta a
descendentului va fi
[ 1,0∈iq ] iy
⎪⎩
⎪⎨⎧
>
≤=
5.0
5.02
1
ii
iii
qdacăx
qdacăxy
În cazul când se încrucişează p părinţi { }pxx LL,,1 , componenta
a descendentului iy y este componenta a părintelui ix
∈x { }pxx LL,,1 ales aleator. În cazul μ=p , părintele care dă
componenta a descendentului este ales din întreaga populaţie;
de aceea încrucişarea se numeşte globală. iy y
198
8.2.1.2 Încrucişarea intermediară
În acest caz componenta a descendentului este o iy y
combinaţie convexă a componentelor corespunzătoare din cei p
părinţi , aleşi aleator: pxx ,,1 L
nixyp
j
jiji ,,2,1
1L== ∑
=λ
şi
0,11
≥=∑=
j
p
jj λλ .
În general se lucrează cu doi părinţi , : 1x 2x
( ) { }nixxy iii ,,2,1,1 21 L∈−+= λλ
cu [ 1,0∈ ]λ ales ca fiind valoarea unei variabile aleatoare cu
distribuţie uniformă şi păstrând aceeaşi valoare pentru toate componentele.
Încrucişarea intermediară poate fi extinsă schimbând părinţii şi parametrul λ pentru fiecare componentă a descendentului. Toate tipurile de încrucişare se aplică similar şi pentru dispersie sau alţi parametri de control.
199
Experimental, s-a observat că se obţin rezultate bune dacă pentru vectorii de poziţie se utilizează încrucişarea discretă iar pentru parametrii strategiei se foloseşte încrucişarea intermediară.
8.2.2. Mutaţia
) Mutaţia este cel mai important operator al strategiilor evolutive.
Am văzut că un individ este o pereche ( σ,x , unde vectorul σ indică
modul în care vectorul de poziţie x se transformă prin mutaţie. Parametrul de control σ este supus şi el operaţiei de mutaţie.
Individul ( )σ,x se transformă prin mutaţie în ( )',' σx :
( ) ( )σσ ,',' xmutx = .
Vectorul se obţine după legea 'x
( )1,0' Nxx ⋅+= σ
sau, pe componente,
( )1,0'' iiii Nxx σ+= , { }ni ,,2,1 L∈
unde şi ( 10,N ) ( )1,0iN sunt variabile aleatoare de medie 0 şi
dispersie 1.
Mutaţia asupra lui σ acţionează diferit, după cum 1=λ sau
1>λ , în modelele ( )λμ, şi λμ + .
200
8.3. Funcţionarea strategiilor evolutive Structura generală a unei strategii evolutive este cea a unui
algoritm evolutiv, apărând, în funcţie de strategie, unele diferenţe la nivelul operatorilor.
8.3.1 Strategia )11( +
Modelul iniţial al lui Rechenberg consideră populaţia formată dintr-un singur individ supus operatorului de mutaţie. După obţinerea descendentului, cei doi membri ai populaţiei sunt comparaţi între ei prin intermediul funcţiei de adecvare şi este reţinut individul cel mai bun. Folosim următoarele notaţii:
• = un număr de generaţii consecutive; de obicei se ia k nk 10= , unde este dimensiunea spaţiului de căutare n
• = numărul mutaţiilor de succes din ultimele generaţii )(ks k
consecutive
• kkskp )()( = = frecvenţa mutaţiilor de succes din ultimele k
generaţii
• C= constantă, aleasă (la sugestia lui Schwefel [79]) ca fiind 0.817, această valoare fiind obţinută pentru modelul sferei.
201
Algoritmul SE(1+1)
begin , 1:=t { })(),()( ttxtP σ=
evaluează )
)
(xf
while not do ))(( tPcond
begin calculează (kp
calculează
( ) ( )( )
( )
( )
( ) ( )⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
<⋅
=
>
==+
5151)(
51)(
1
kpdacăct
kpdacăt
kpdacăct
tmutt
n
n
σ
σ
σ
σσ
calculează ( ) ( )( ) ( ) ( ) ( )1,011 Nttxtxmuttx ⋅++==+ σ
evaluează ( )( )1+txf
if ( )( ) ( )( )txftxf ≤+1 {selecţia}
then ( ) ( ) ( ){ }1,11 ++=+ ttxtP σ
else )(:)1( tPtP =+
1: += tt end end
202
Observaţii.
1) ))(( tP reprezintă condiţia de oprire, dată de obicei prin cond
numărul de generaţii 2) Schwefel a propus [79] o altă versiune a mutaţiei pentru
parametrul σ
( )
( )
( )
( ) ( )⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
<⋅
=
>
=+
5151)(
51)(
kpdacătc
kpdacăt
kpdacăct
nt
σ
σ
σ
σ
3) Strategia (1+1) lucrează cu populaţii formate dintr-un singur individ şi nu foloseşte încrucişarea. Regulile, folosite anterior, pentru modificarea parametrului σ
sunt versiuni ale “regulii de succes 51 ” propusă de Rechenberg, care
afirmă că:
• raportul dintre numărul mutaţiilor de succes şi numărul mutaţiilor totale trebuie să fie 51
• dacă acest raport este mai mare decât 51 atunci valoarea lui σ
trebuie să crească
• dacă raportul este mai mic decât 51 atunci valoarea lui σ
trebuie să descrească.
203
8.3.2 Strategia )1( +μ
Strategia (1+1) poate fi generalizată prin mărirea numărului părinţilor fiecărui descendent şi/sau a numărului descendenţilor unui părinte. În strategia ( )1+μ , 1>μ părinţi vor genera un singur
descendent folosind încrucişarea şi mutaţia. Încrucişarea se aplică atât vectorului de poziţie cât şi dispersiei şi se poate folosi oricare din operatorii prezentaţi anterior. Mutaţia se aplică urmând principiul strategiei , dar nu există o metodă de control a dispersiei, regula ( 11+ )
51 nemaifiind aplicabilă în acest caz. Acest dezavantaj face ca
strategia ( )1+μ să fie puţin folosită.
8.3.3 Strategii multidescendent
Aceste strategii au apărut din dorinţa de a folosi metode mai robuste şi mai generale pentru a controla parametrii mutaţiei. Din această categorie fac parte strategiile ( )λμ + şi ( )λμ, care lucrează
cu populaţii formate din 1>μ părinţi şi μλ > descendenţi, ceea ce
determină o creştere a vitezei de convergenţă. Cei μ indivizi ai noii
generaţii se selectează din : • populaţia intermediară obţinută reunind cei μ indivizi ai
generaţiei curente cu cei λ descendenţi ai ei, în cazul strategiei
( )λμ +
204
• din cei λ descendenţi ai populaţiei curente, în cazul strategiei
( )λμ, .
Deoarece strategia ( )λμ, îşi schimbă complet populaţia la
fiecare nouă generaţie, ea nu este elitistă. Această calitate permite ieşirea din zona unui optim local şi evoluţia către optimul global. În schimb, strategia ( )λμ + permite supravieţuirea unor indivizi
neperformanţi din vechea generaţie. În felul acesta procesul de căutare tinde să favorizeze minimele locale în defavoarea celor globale. De aceea se recomandă folosirea strategiei ( )λμ, .
Încrucişarea. Iniţial strategiile ( )λμ + şi ( )λμ, au fost
aplicate folosind doar operatorul de mutaţie. Ulterior s-a constatat că se obţin rezultate mai bune dacă se foloseşte şi încrucişarea, aplicată înaintea mutaţiei. În mod empiric, s-a ajuns la concluzia că folosirea încrucişării discrete pentru vectorii de poziţie şi a celei convexe pentru parametrii strategiei conduce la cele mai bune rezultate. Operatorul de încrucişare se aplică de λ ori populaţiei de μ părinţi, obţinându-se o
populaţie intermediară de μλ ≥ indivizi. Un descendent se obţine
prin încrucişarea a p părinţi, μ≤≤ p1 ; de obicei se ia 2=p sau
μ=p .
Mutaţia. Considerăm indivizii reprezentaţi prin perechi de
forma ( )σ,x , unde este vectorul de poziţie iar este
vectorul dispersie. Notăm cu
nRx∈ 2σ
( )1,0N un număr aleator ce urmează
205
distribuţia normală de medie 0 şi dispersie 1. Mutaţia standard înlocuieşte individul ( )σ,x cu ( )',' σx
1,0(1Npie
obţinut după regulile:
)1,0() 2 iNp+=σ'iσ
( )1,0' ii N'iixx σ+=
cu . Parametrii şi controlează mărimea pasului
mutaţiei şi respectiv schimbările individuale. Schwefel [77] a propus pentru aceşti parametri următoarele valori
{ ni ,,2,1 L∈ } 1p p2
şi n
c
nc21p1 =
22
2 =p
unde şi iau de obicei valoarea 1. 1c 2c
Mutaţia, aşa cum rezultă din formulele anterioare, acţionează întâi asupra dispersiei şi apoi asupra vectorului de poziţie. Se poate lucra cu vectorul dispersie având toate componentele egale; fie σ valoarea lor comună. În acest caz mutaţia funcţionează după regulile
),' 10σ (pNeσ=
'i Nx
( )1,0i'ix σ+=
adică toate componentele vectorului de poziţie se modifică folosind
aceeaşi dispersie; parametrul ia valoarea n
cp = . p
Strategiile multidimensionale funcţionează după următorul algoritm
206
begin 0:=t iniţializează populaţia )(tP
evaluează indivizii din )(tP
while not do ))(( tPcond
begin încrucişare ( ) =:t'P ))(( tP
mutaţie ( ) =:t"P ))('( tP
evaluează )t("P
selecţie=+ :)1(tP ( )( )Mt"P ∪
1: += tt end end
Populaţia iniţială se construieşte alegând aleator , cu o
probabilitate uniformă, μ puncte , ni Rx ∈ { }μ,,2,1 L∈i . Dacă se
cunoaşte un punct x aflat în vecinătatea celui de optim atunci x va fi unul dintre indivizi iar ceilalţi 1−μ se obţin prin mutaţii asupra lui. O
adaptare eficientă a parametrilor strategiei necesită o diversitate suficient de mare a populaţiei de părinţi. Deci, numărul μ trebuie să
fie mai mare ca 1 iar raportul dintre numărul descendenţilor şi cel al părinţilor trebuie să fie în favoarea descendenţilor. Se recomandă un
raport 7=μλ şi, în mod frecvent, se foloseşte strategia ( )100,15 .
207
Kursawe [54] a arătat că asigurarea convergenţei este influenţată de operatorul de încrucişare folosit; acesta depinde de forma funcţiei obiectiv, de dimensiunea spaţiului de căutare şi de numărul de parametri ai strategiei.
Condiţia de oprire se referă, de obicei, la numărul maxim condde generaţii dar pot fi luate în consideraţie şi alte criterii, printre care cele de mai jos:
1) diversitatea populaţiei a scăzut sub o anumită limită, semn că ne aflăm în vecinătatea unui optim global; diversitatea poate fi măsurată prin diferenţa calităţilor asociate celui mai bun individ şi celui mai neperformant.
2) nu se mai obţin îmbunătăţiri semnificative ale funcţiei obiectiv
Mulţimea M poate lua una din valorile: ) pentru strategia (tPM = ( )λμ +
pentru strategia ∅=M ( )λμ, .
8.3.4 Utilizarea mutaţiilor corelate Fiecare individ din populaţie este caracterizat nu numai de
vectorul x al variabilelor ci şi de parametrul σ al strategiei. Reprezentarea poate fi extinsă [72] introducând valorile de varianţă
( 2iiic σ= ni ≤≤1 ) şi valorile de covarianţă ijc
208
( njini ≤≤+−≤≤ 1,11 ) ale distribuţiei normale −n dimensionale
având densitatea de probabilitate
( )
Azz
n
T
eA 21
2)det( −
=π
zp )(
Pentru a asigura pozitiv-definirea matricei de covarianţă
( )ijcA =−1 se utilizează unghiurile de rotaţie jα în locul coeficienţilor
. Acum un individ se va reprezenta sub forma ijc ( )ασ ,,a x= unde
• este vectorul variabilelor obiectiv nRx∈σσ nR+∈
nn ≤≤ σ1
[ ] αππα n,−∈
• este vectorul deviaţiilor standard ale distribuţiei
normale;
• este vectorul unghiurilor ce definesc mutaţiile
corelate ale lui ; ( )12
−⎟⎠⎞− σ
σ nn⎜⎝⎛=α nnx .
Vectorul α permite căutarea în orice direcţie; altfel erau favorizate direcţiile paralele cu axele sistemului de coordonate. Parametrii α şi σ ai strategiei se modifică prin mutaţie iar tipul
acestei operaţii depinde de valorile lui şi . Astfel, pentru σn αn
• şi 1=σn 0=αn se obţine mutaţia standard, când o singură
valoare a deviaţiei standard controlează mutaţia tuturor componentelor lui x .
209
• şi nn =σ 0=αn se obţine mutaţia standard, când valorile
nσσ ,,L1 controlează mutaţia componentelor corespunzatoare ale
vectorului x
• şi nn =σ 2)1( −
=nnnα se obţin mutaţiile corelate
• şi 2=σn 1−= nnα : valoarea este folosită pentru a efectua
căutarea într-o direcţie arbitrară iar este utilizată pentru toate
direcţiile perpendiculare pe aceasta.
21σ
σ 22
Mutaţia asupra unui individ
( )nnnxxa αασσ ,,,,,,,, 111 LLL=
acţionează astfel:
)1,0()1,0('' iNNii e ⋅+= ττσσ , σni ≤≤1
)1,0(' jjj N⋅+= βαα , αnj ≤≤1
),(' ασcovxx +=
unde vectorul cov este calculat astfel:
Tzcov = , ( )nzzz ,,1 L= ,
( )( )2',0 ii Nz σ= ,
( )∏ ∏−
= +==
1
1 1'
σ σ
αn
p
n
pqjpqTT ,
210
( )( ) qnppnj +−+−= σσ 21221 .
Matricea de rotaţie ( )jpqT 'α este matricea unitate exceptând
( )jqqpp tt αcos== şi ( )jqppq tt αsin−=−= .
Pentru factorii ', ττ şi β , Schwefel a sugerat următoarele valori:
n
c
21=τ ,
nc2
' 2=τ , )5(0873.0 o=≅β
8.4. Analiza convergenţei Folosindu-se instrumente din teoria lanţurilor Markov s-au
obţinut condiţii suficiente de convergenţă în sens probabilist pentru strategiile evolutive. Condiţii suficiente (nu şi necesare) simplu de verificat sunt: i) repartiţia utilizată pentru mutaţie are suport infinit ( este satisfăcută atât de repartiţia normală cât şi de repartiţia Cauchy); ii) selecţia este elitistă (strategiile de tip )( λμ + satisfac această
proprietate); iii) recombinarea se aplică cu o anumită probabilitate pr.
Din punct de vedere practic convergenţa în timp infinit nu este de mare folos ci mai degrabă testează abilitatea algoritmului de a găsi elemente din ce în ce mai bune prin trecerea de la o generaţie la alta
211
(algoritmul progresează în procesul de căutare). O situaţie nedorită este aceea în care acest progres este stopat. Există două manifestări ale acestui fapt:
• Convergenţa prematură. Algoritmul se blochează într-un optim local datorită faptului că populaţia nu mai este suficient de diversă pentru a susţine procesul de explorare.
• Stagnare. Algoritmul s-a blocat în condiţiile în care populaţia este încă diversă, însă mecanismele evolutive nu sunt suficient de puternice pentru a susţine explorarea.
Soluţionarea acestor probleme se bazează pe alegerea adecvată a operatorilor şi a parametrilor de control; încă nu există rezultate teoretice care să furnizeze soluţii de evitare a situaţiilor de convergenţă prematură sau stagnare.
Studiul teoretic al vitezei de convergenţă se bazează pe estimarea unor rate de progres în cazul unor funcţii test simple (funcţia sferă şi perturbaţii ale acesteia). Prin estimarea ratei de progres s-au obţinut informaţii referitoare la alegerea parametrilor de control astfel încât rata să poată fi maximizată. Există diverse abordări şi diferite măsuri ale progresului strategiilor evolutive. Din punct de vedere practic este util faptul că strategiile evolutive au cel mult viteză liniară de convergenţă.
În absenţa unei teorii complete a domeniului, multe dintre proprietăţile şi regulile de proiectare sunt deduse pornind de la studii
212
experimentale. Acestea se efectuează pe probleme de optimizare construite în aşa fel încât să ridice dificultăţi metodelor de rezolvare (de exemplu cu multe minime locale sau cu un minim global greu de atins din cauza prezenţei unor "platouri"). Multe dintre funcţiile de test utilizate în analiza strategiilor evolutive au fost construite pentru a testa metode tradiţionale de optimizare şi au ridicat dificultăţi pentru acestea.
Cum strategiile evolutive implică prezenţa unor elemente aleatoare, la rulări diferite ale algoritmului se vor obţine rezultate diferite. Din acest motiv studiul experimental nu poate fi decât unul statistic caracterizat prin faptul că se vor efectua mai multe rulări independente şi se va determina frecvenţa situaţiilor în care strategia a avut succes. Se consideră că strategia a avut succes atunci când cel mai bun element întâlnit de-a lungul generaţiilor (sau cel mai bun element din ultima generaţie) este suficient de apropiat de optim.
Studiile statistice sunt folosite pentru a analiza influenţa operatorilor şi a parametrilor de control asupra eficacităţii strategiei evolutive. Valoarea lor este limitată datorită faptului că rezultatele obţinute pe funcţii test nu pot fi extrapolate pentru orice problemă de optimizare. Coroborate însă cu rezultatele teoretice (obţinute pentru funcţii test simple, cum este modelul sferei) au condus la criterii euristice care au un oarecare succes în practică.
Din punct de vedere statistic prezintă interes valoarea medie şi dispersia valorii optime descoperite la fiecare rulare.
213
8.5. Domenii de aplicabilitate
Câteva dintre aplicaţiile strategiilor evolutive sunt:
• Biologie şi biotehnologie: simularea evoluţiei proteinelor, proiectarea lentilelor optice, optimizarea parametrilor unui model al transmiterii semnalelor genetice bazat pe transcriere a ADN-ului, optimizarea proceselor de fermentare.
• Chimie şi inginerie chimică: determinarea compoziţiei optimale de electroliţi în procesele de galvanizare, minimizarea energiei clusterilor în moleculele gazelor rare, estimarea parametrilor modelelor de analiză cinetică a spectrelor de absorbţie, identificarea benzilor în spectrele obţinute prin rezonanţă magnetică nucleară.
• Proiectare asistată de calculator: determinarea parametrilor unui amortizor pneumatic de şocuri, optimizarea volumului unor construcţii în vederea minimizării instabilităţii, determinarea formei optimale a unor dispozitive, adaptarea parametrilor unor modele de tip element finit pentru proiectarea optimală a structurilor, optimizarea eficienţei, senzitivităţii şi lărgimii de bandă a convertoarelor cu ultrasunete, proiectarea optimală a arcelor utilizate în dispozitivele de suspensie de la vehicule.
• Fizică şi analiza datelor: determinarea configuraţiei optime a defectelor în materialele cristaline, estimarea parametrilor în probleme
214
de dinamica fluidelor, determinarea stărilor stabile în sistemele disipative.
• Procese dinamice, modelare şi simulare: optimizarea unui sistem socio-economic complex, identificarea parametrilor unui model de răspândire a unei infecţii virale.
• Medicină şi inginerie medicală: controlul optimal al protezelor, identificarea parametrilor modelelor folosite în farmacologie.
• Inteligenţă artificială: controlul inteligent al vehiculelor autonome, determinarea ponderilor reţelelor neuronale.
9 PROGRAMARE EVOLUTIVĂ ŞI PROGRAMARE GENETICĂ Programarea evolutivă şi Programarea genetică lucrează cu populaţii care nu mai sunt reprezentate prin şiruri binare sau reale, ca în cazul algoritmilor genetici şi al strategiilor evolutive, ci prin structuri mai complicate: programe, automate finite, etc. Din punct de vedere al operatorilor folosiţi, programarea evolutivă este mai apropiată de strategiile evolutive (foloseşte mutaţia ca operator principal, încrucişarea fiind foarte rar sau deloc folosită) în timp ce programarea genetică este mai apropiată de algoritmii genetici (operatorul principal este cel de mutaţie).
9.1. Programare evolutivă 9.1.1. Generalităţi
Programarea evolutivă a fost iniţiată de Fogel [26, 28] cu scopul de a genera un comportament inteligent pentru un sistem artificial. Comportamentul inteligent se referă la abilitatea sistemului
216
de a realiza predicţii asupra mediului informaţional în care se află. Sistemele sunt modelate prin automate Turing iar mediul informaţional este reprezentat printr-o succesiune de simboluri de intrare.
Un automat Turing este un automat finit înzestrat cu o bandă de ieşire cu următoarea funcţionare: aflându-se în starea p şi citind
simbolul de intrare x , va trece într-o altă stare şi va înscrie pe
banda de ieşire un simbol . Prin acest mecanism, automatul Turing
transformă o secvenţă de simboluri de intrare într-o secvenţă de simboluri de ieşire.
q
y
Comportamentul automatului este considerat inteligent dacă poate prezice simbolul următor. Populaţia este dată de diagramele de tranziţie ale automatului iar gradul de adecvare al unui individ este cu atât mai mare cu cât şirul de simboluri produs de automat este mai aproape de un şir „ţintă”. Diagrama de tranziţie a unui automat finit determinist este reprezentată printr-un multigraf orientat şi etichetat, în care nodurile sunt etichetate cu stările automatului iar arcele reprezintă tranziţiile şi sunt etichetate cu simbolul de intrare şi cel de ieşire corespunzător. Ca exemplu, să considerăm automatul din Figura 9.1, care verifică dacă un şir de biţi conţine un număr par sau impar de poziţii egale cu 1. Alfabetul de intrare este { }1,0 iar ieşirea unei tranziţii va fi
0 sau 1, după cum şirul conţine un număr par respectiv impar de cifre
217
egale cu 1. Mulţimea stărilor este mulţimea { }imparpar, iar starea
iniţială este par .
Figura 9.1
9.1.2. Funcţionarea automatului Turing
Populaţia este formată din 1>μ indivizi, fiecare fiind un
automat Turing. Să considerăm exemplul din figura următoare [9].
Figura 9.2
218
Automatul are stările { }CBAS ,,= , alfabetul de intrare { }1,0=I ,
alfabetul de ieşire { }cba ,,O = . Tranziţia între două stări este data de
funcţia OSIS ×→×:δ
definită printr-o etichetă de forma care apare pe o latură între
două stări şi , însemnând că
oi /
ks ls
( )( ) ( )osis lk ,, =δ ;
adică dacă maşina este în starea şi primeşte la intrare simbolul
atunci ea trece în starea şi produce la ieşire simbolul
ks
Ii∈ ls Oo∈ .
Prin acest mecanism, automatul transformă un şir format din simboluri de intrare ( interpretat ca mediul maşinii) într-un şir format din simboluri de ieşire. Performanţa automatului în raport cu mediul poate fi măsurată pe baza capacităţii predictive a ei: se compară fiecare simbol de ieşire cu următorul simbol de intrare şi se măsoară valoarea predicţiei cu ajutorul unei funcţii de câştig.
Paradigma programării evolutive a fost implementată de Fogel lucrând cu o populaţie de 1>μ părinţi care generează μ descendenţi
prin mutaţii asupra fiecărui părinte. Mutaţia a fost implementată ca o schimbare aleatoare a componentelor automatului; o schimbare se poate realiza în cinci moduri: schimbarea unui simbol de ieşire, modificarea unei tranziţii, adăugarea/eliminarea unei stări, modificarea stării iniţiale.
Pentru fiecare individ al populaţiei se alege uniform şi aleator unul din cei cinci operatori de mutaţie. Este, însă, posibil ca asupra
219
aceluiaşi individ să se aplice mai mulţi operatori de mutaţie, numărul mutaţiilor putând să fie fix sau ales conform unei distribuţii de probabilitate. După evaluarea descendenţilor se selectează cei mai buni μ indivizi dintre părinţi şi descendenţi; deci se efectuează o
selecţie de tip ( )μμ + .
Fogel nu a folosit încrucişarea, de aceea mulţi cercetători din domeniul algoritmilor genetici au criticat metoda lui, considerând că nu e suficient de puternică. Totuşi, rezultatele teoretice şi empirice din ultimii 30 de ani au arătat că rolul mutaţiei în algoritmi genetici a fost subestimat iar cel al încrucişării a fost supraestimat [3, 19, 21, 52].
9.1.3. Optimizare folosind programarea evolutivă
Variantele curente de programare evolutivă folosite în
probleme de optimizare cu parametri continui au multe lucruri în comun cu strategiile evolutive, în special în privinţa reprezentării indivizilor, al modului de efectuare a mutaţiei şi al autoadaptării parametrilor [97].
Iniţial programarea evolutivă a lucrat cu spaţii mărginite
, cu [ ] nn
iii Rvu ⊂∏
=1, ii vu < .
Mai târziu domeniul de căutare a fost extins la nRI = , un individ fiind un vector Ixa ∈= . În [22] se introduce conceptul de
220
metaprogramare evolutivă, care presupune un mecanism de auto-adaptare similar celui de la strategii evolutive. Pentru a încorpora
vectorul varianţelor , spaţiul indivizilor este extins la
. Funcţia de evaluare
nRv +∈
nn RRI +×= ( )aΦ se obţine din funcţia obiectiv
prin scalare la valori pozitive şi, eventual, prin impunerea unor
modificări aleatoare k ale parametrilor; deci
)(xf
( )( )kxfa ,)( δ=Φ , unde
δ este functia de scalare. În cazul programării evolutive standard
mutaţia transformă pe x în , 'x )(,,1x
nγγ L' ,,,xnβL1
mutβ= , după regula
)1,0(ii N'x iix σ+=
( ) iγi xβ +Φ⋅= iσ
unde constantele de proporţionalitate iβ şi iγ sunt alese în funcţie de
problema de rezolvat; totuşi, de obicei se consideră 1=iβ şi 0=iγ ,
astfel că mutaţia devine
,0()( iNx ⋅Φ' ii xx += )1
,(xa
.
În cazul meta-programării evolutive individul )v= se
transformă prin mutaţie în 'a = ,'()( xamut = )'vα astfel:
)1,0(ii Nv ⋅+' ii xx =
( )1,0ii Nv ⋅⋅α' ii vv +=
221
unde α are rolul de a asigura că primeşte o valoare pozitivă.
Totuşi, dacă varianţa devine negativă sau zero atunci i se atribuie o valoare mică
iv'
0>ε .
Se consideră că în programarea evolutivă se codifică mai degrabă specii decât indivizi; şi cum încrucişarea nu acţionează la nivelul speciilor, programarea evolutivă nu foloseşte acest tip de operator. După crearea a μ descendenţi din μ părinţi, prin aplicarea
mutaţiei o singură dată asupra fiecărui părinte, se selectează μ
indivizi din mulţimea părinţilor reunită cu cea a descendenţilor
. Se utilizează o variantă stochastică a selecţiei turneu cu
parametrul care constă în: pentru fiecare individ
se selectează aleator indivizi din şi
se compară evaluarea lor cu cea a lui a . Numărul
)(tP
)(' tP
ak ∈
1>q
)(' t)( PtP ∪ q
k
)(')( tPtP ∪
{ }q,,1,0 Lwk ∈ al
indivizilor mai puţin performanţi decât constituie scorul lui . ka ka
Formal, acesta se poate scrie
( ) ( )∑= ⎩⎨⎧ Φ≤Φ
=q
j
ii altfel
aadacăw i
1 0
1 χ
unde indicii { }μχ 2,,2,1 L∈j sunt valori aleatoare uniforme,
calculate pentru fiecare comparare. După ce se efectuează această operaţie pentru toţi cei μ2 indivizi, ei se ordonează descrescător după
scorul , iw μ21 ≤≤ i , şi se aleg cei mai buni μ indivizi care vor
forma generaţia următoare )1( +tP . Rezultă următorul algoritm
222
begin 0:=t
iniţializează ( ){ } μμ IaaP ∈= 0,),0(:)0( 1 L ,
unde , nn RRI +×= ),( iii vxa = { }ni ,,1 L∈∀
evaluează ( ) ( )( ){ }0,,)0(:)0( 1 μaaP ΦΦ L
unde ( )( ) ( )( )( )jjj kxfa ,00 δ=Φ
while ( ( )( ) truetPT ≠ ) do
begin aplică mutaţia: ( )( ) { }μα ,,1:)(' L∈∀= itamutta ii
evaluează ( ){ }tatatP μ',),(':)(' 1 L= calculând
( )( )( ){ }tata μ',),('1 ΦΦ L cu ( )( ) ( )( )( )iii ktxfta ,'' δ=Φ
selectează ( ))(')(:)1( tPtPturntP q ∪=+
1: += tt end end
Am evidenţiat anterior similaritatea dintre strategiile evolutive şi programarea evolutivă. Există, totuşi, şi diferenţe, cele mai evidente fiind la nivelul:
• codificării: strategiile evolutive codifică indivizi iar programarea evolutivă codifică specii
223
• selecţiei: strategiile evolutive aleg cei mai buni indivizi dintre părinţi şi descendenţi, pe când programarea evolutivă face această alegere dintr-un număr de indivizi selectaţi anterior din populaţia curentă reunită cu cea a descendenţilor.
Programarea evolutivă are numeroase aplicaţii, dintre care amintim: optimizarea numerică continuă, dezvoltarea sistemelor de clasificare, antrenarea reţelelor neuronale, proiectarea sistemelor de control ce pot fi modelate prin automate finite, controlul deplasării roboţilor.
9.2. Programare genetică Programarea genetică reprezintă o nouă direcţie în cadrul
calculului evolutiv, dezvoltată de către J. Koza [52] în jurul anilor 1990. Programarea genetică este, de fapt, o variantă a algoritmilor genetici care operează cu populaţii constituite din „structuri de calcul”, din acest punct de vedere fiind similară programării evolutive. Structurile care constituie populaţia sunt programe care atunci când sunt executate sunt soluţii candidat ale problemei. Programarea genetică a fost dezvoltată iniţial cu scopul de a genera automat programe care să rezolve (aproximativ) anumite probleme.
Ulterior aria de aplicaţii s-a extins către proiectarea evolutivă, un domeniu aflat la intersecţia dintre calculul evolutiv, proiectarea
224
asistată de calculator şi biomimetism (subdomeniu al biologiei care studiază procese imitative din natură). Programarea genetică urmează structura generală a unui algoritm genetic, folosind încrucişarea ca operator principal şi mutaţia ca operator secundar. Particularităţile programării genetice sunt legate de modul de reprezentare a indivizilor, fapt ce necesită şi alegerea adecvată a operatorilor.
9.2.1 Reprezentarea indivizilor În programarea genetică indivizii sunt văzuţi nu ca o succesiune de linii de cod ci ca arbori de derivare asociaţi „cuvântului” pe care îl reprezintă în limbajul formal asociat limbajului de programare utilizat. În practică se lucrează cu limbaje restrânse, bazate pe o mulţime mică de simboluri asociate variabilelor şi o mulţime de operatori; în aceste condiţii, orice program este de fapt o expresie în sens general. Alegerea simbolurilor şi a operatorilor este strâns legată de problema de rezolvat. Această alegere determină esenţial rezultatele ce se vor obţine; nu există, însă, reguli generale care să stabilească legătura dintre o problemă de rezolvat şi mulţimile de simboluri şi operatori folosite, rolul important revenindu-i programatorului.
Koza a propus ca modalitate de reprezentare scrierea prefixată a expresiilor, care corespunde parcurgerii în preordine a arborelui de structură al expresiei. Pentru a simplifica descrierea, considerăm că se operează cu „programe” care sunt expresii ce conţin operatori
225
aritmetici, relaţionali şi logici precum şi apeluri ale unor funcţii matematice. În acest caz, limbajul formal asociat este independent de context şi fiecărui cuvânt (expresie) i se poate asocia un arbore de descriere. Nodurile interioare ale arborelui sunt etichetate cu operatori sau nume de funcţii iar cele terminale sunt etichetate cu nume de variabile sau constante. De exemplu, expresia )5,max( yxyx ∗+∗
va fi reprezentată prin
Figura 9.3 Mulţimea nodurilor interioare se numeşte mulţimea funcţiilor
},,,{Ffnfff L21= ; în exemplul nostru { }∗+= ,max,F . Fiecare
funcţie are aritatea (numărul argumentelor) cel puţin 1.
Funcţiile din pot fi de diferite tipuri:
F∈if
F
226
• aritmetic: /,,, ∗−+
• matematic: logexp,cos,sin,
• boolean: NOTORAND ,,
• condiţional: elsethenif −−
• repetitiv: repeatwhilefor ,,
Mulţimea nodurilor terminale din arborele de derivare se numeşte muţimea terminalelor { }
tnttt ,,, 21 L=T
F T
; în exemplul nostru
. Mulţimile şi pot fi reunite într-un grup uniform
, dacă se consideră că terminalele sunt funcţii de aritate zero. Pentru ca programarea genetică să funcţioneze eficient, mulţimile şi T trebuie să respecte două condiţii [102]:
{ 5,, yx=T
TFC ∪=
F
}
}
• cea de închidere, adică fiecare funcţie din F este aptă să accepte ca argument orice valoare sau tip de dată ce poate fi returnat de orice funcţie din C ; această proprietate previne erorile din timpul rulării
• cea de suficienţă, care cere ca funcţiile din C să poată exprima soluţiile problemei, adică cel puţin o soluţie aparţine mulţimii tuturor compunerilor posibile ale funcţiilor din C .
Câteva exemple de mulţimi C închise sunt: • , unde { trueyxNOTORAND ,,,,,=C x şi y sunt variabile
booleene • , cu { 0,1,,,,, yx∗−+=C } x şi y variabile întregi
• , cu { yx,exp,cos,sin,,, −+=C } x şi y variabile reale.
227
}
Există mulţimi pentru care proprietatea de închidere nu este verificată; de exemplu: • , cu { 0,1,,/,,,, yx∗−+=C x şi variabile reale, nu este închisă
deoarece se pot genera împărţiri prin zero, cum sunt
y
0x ,
xxyx
−+ , etc
• , cu { yx,log,cos,sin,,, −+=C } x şi y variabile întregi, nu este
închisă deoarece se pot genera valori negative pentru logaritm; de exemplu, . )log( x−
Mulţimea { }x,,, −+=C poate fi închisă sau nu, în funcţie de
domeniul valorilor lui x . Închiderea poate fi forţată prin folosirea funcţiilor „protejate”. Astfel de funcţii sunt:
• ⎩⎨⎧
≠=
=0ydacăyx0ydacă
yx 1
, operaţie ce va fi notată în continuare cu
div
• ( )⎩⎨⎧ =
=altfelx
0xdacăx
log0
)log(
• xx = .
Dacă nu vrem să folosim funcţii de protecţie atunci trebuie redusă foarte mult adecvarea (fitness-ul) expresiilor nevalide; problema este similară funcţiilor de penalizare din cazul problemelor de optimizare.
Suficienţa este garantată numai pentru unele probleme, când teoria sau alte metode ne spun că o soluţie poate fi obţinută
228
}
}
combinând elementele lui C . De exemplu, logica ne spune că permite implementarea oricărei funcţii
booleene, deoarece conţine o multime completă de conectori. Dacă C nu este suficientă, programarea genetică poate doar să dezvolte programe care să realizeze o aproximare cât mai bună. De exemplu, mulţimea
{ yxNOTORAND ,,,,=C
{ 0,/,,,, x 2,1,∗−+=C
)exp(x
nu poate să dea decât o aproximare
pentru , ştiind că aceasta este o funcţie transcedentală (nu poate
fi aproximată exact cu ajutorul unor expresii algebrice finite). În acest caz programarea genetică nu poate decât să realizeze aproximări algebrice finite de tipul 1)exp( =x
xx +=1)exp(
2
1)exp( xxx ++=
32
2211
121)exp( xxxx
+++
+++=
9.2.2 Populaţia iniţială
Arborii iniţiali sunt generaţi alegând aleator funcţii din C . De exemplu, pentru { }3,2,1,0,,/,,,, yx∗−+=C putem avea
229
*
2 x
*
- /
*
/
- +
*
+
x 3
2
x 2 3 1
x
x y 0 y Figura 9.4
Dimensiunea şi forma programelor iniţiale sunt controlate selectând noduri din şi , în funcţie de adâncimea lor în arbore. Arborii pot fi reprezentaţi şi ca liste de liste. De exemplu, pentru primii doi arbori anteriori avem
F T
[ ]x2∗ , [ ][ ]23x* + .
Din acest motiv, iniţializarea populaţiei în programarea genetică este bazată, de obicei, pe proceduri recursive care returneaza liste.
Metoda „full” selectează noduri din dacă adâncimea lor nu depăşeşte o valoare maximă şi noduri din în caz contrar. Această tehnică duce la obţinerea unei populaţii iniţiale cu frunzele la acelaşi nivel (Figura 9.5).
F
T
230
Figura 9.5
Metoda „grow” selectează noduri din C dacă adâncimea lor este mai mică dacât o valoare minimă şi din în caz contrar. Cum C conţine şi elemente terminale, această metodă produce arbori iniţiali de diferite forme şi adâncimi, ca în Figura 9.6
T
Figura 9.6
Metoda „ramped half and half” combină cele două metode anterioare, pentru a da o mai mare diversitate populaţiei iniţiale. Ea lucrează după următorul algoritm
231
for to do 1=i adâncimemax _
begin
generează %
1_50
⎟⎟⎠
⎞⎜⎜⎝
⎛−adâncimemax
din populaţie folosind metoda
„full” cu adâncimea maximă i
generează %
1_50
⎟⎟⎠
⎞⎜⎜⎝
⎛−adâncimemax
din populaţie folosind metoda
„grow” cu adâncimea maximă i end Metodele „full” şi „grow” pot fi implementate cu următoarea procedură recursivă [102] Generează_expresie(F ,T , max_adâncime, metodă) begin if 0_ =adâncimemax
then begin selectează ∈t T inserează t în arbore end else begin
232
if metoda = full then selectează ∈f F
else selectează ∈f F ∪ T
inserează în arbore f
if ∈f F
then begin aritatea lui =:n f
for 1=i to n do generează_expresie( , , max_adâncime-1, metodă) F T
end end end La apelul [ ] [ ]( )fullyxresieexpgenerează ,3,3210,/_ ∗−+
se poate genera expresia [ ][ ][ ] [ ][ ][ ][ ]xyx 23/021 −+−∗+∗
care corespunde arborelui următor
233
Figura 9.7 La apelul [ ] [ ]( )grow,,yx,expresie-generează 332101∗−+
se generează expresia [ ] [ ][ ][ ]yx 1/23 −∗+
care corespunde arborelui
Figura 9.8
234
9.2.3 Operatori de evoluţie Încrucişarea constă în selectarea aleatoare a punctului de
încrucişare (nod sau arc în arbore) în fiecare părinte şi schimbarea subarborilor care încep de la punctul de încrucişare. Este indicat ca punctele de încrucişare să nu fie selectate uniform aleator ci să fie favorizate nodurile interioare; de exemplu, în 90% din cazuri se aleg noduri neterminale. Este posibil ca numărul încrucişărilor să fie controlat de probabilitatea de încrucişare. Un exemplu de încrucişare este dat în figura următoare.
părinţi descendenţi Figura 9.9
235
Deşi este un operator secundar, mutaţia permite modificarea
structurilor arborescente în moduri în care încrucişarea nu o poate face. În funcţie de efectul pe care îl are asupra structurii, există trei variante de mutaţie: • mutaţia simplă: modifică eticheta unui nod selectat aleator
Figura 9.10
• mutaţia de expandare: constă în înlocuirea unui nod terminal cu un subarbore, construit după aceleaşi reguli dar care nu face parte neapărat din populaţia curentă, aşa cum se întâmplă în cazul încrucişării
Figura 9.11
236
• mutaţia de reducere: constă în înlocuirea unui subarbore cu un nod terminal
Figura 9.12
În general se poate alege un nod al arborelui şi subarborele dominat de acel nod este înlocuit cu altul generat aleator. Astfel, mutaţia poate fi văzută ca încrucişarea cu un arbore generat aleator.
9.2.4 Rularea programelor în Programarea genetică
În programarea genetică programele sunt reprezentate prin
arbori sau liste; întotdeauna este posibil să transformăm o astfel de structură într-un cod C, C++, Java, Lisp, etc. Dar, în majoritatea cazurilor o asemenea operaţie este ineficientă deoarece • iniţial, majoritatea programelor au un fitness foarte mic şi vor supravieţui puţine generaţii
237
• multe programe (bune sau mai puţin bune) vor fi schimbate prin încrucişare sau mutaţie şi vor trebui recompilate.
O abordare mai bună este de a interpreta programele, în loc de a le compila. Unele limbaje de programare, cum este Lisp, au deja un interpretor în mediul de dezvoltare a programelor. Pentru a-l utiliza trebuie să ne asigurăm că sintaxa este corectă; de exemplu, să utilizăm paranteze rotunde în locul celor pătrate. Pentru toate celelalte limbaje de programare este necesară construcţia unui astfel de interpretor. A interpreta un program înseamnă a-l parcurge în adâncime şi a evalua toate nodurile începând cu frunzele. Parcurgerea în adâncime permite evaluarea nodurilor numai după ce valorile argumentelor lor sunt cunoscute. De exemplu,
-
**
+ - --
2 0
2
1 x 2 x x 2
1
-1
-1
4
2
51−=x
Figura 9.13
În urma interpretării, valoarea nodului rădăcină este valoarea programului. Aplicaţiile posibile ale programării genetice sunt multe şi variate, singura problemă fiind definirea unei funcţii fitness
238
corespunzătoare. Tehnicile de scalare şi penalizare folosite în algoritmi genetici sunt aceleaşi, cu diferenţa că pentru a decide dacă un program este bun sau nu, trebuie executat odată sau de mai multe ori cu date de intrare diferite sau în diferite contexte.
O clasă de probleme în care programarea genetică s-a dovedit foarte utilă este regresia simbolică. Aceasta este o tehnică folosită foarte des în interpretarea datelor şi constă în găsirea coeficienţilor unei funcţii, obţinute ca o combinaţie de funcţii elementare astfel încât aceasta să aproximeze cât mai bine o funcţie cunoscută prin valorile ei în puncte date. Termenul „simbolic” semnifică faptul că nu suntem interesaţi în găsirea parametrilor optimi (numere) ci a funcţiilor optime (expresii, reprezentări simbolice). Pentru a folosi programarea genetică în rezolvarea problemelor de regresie simbolică este necesar: • să avem o mulţime de puncte date, unde fiecare punct reprezintă valorile luate de anumite variabile la un anumit moment • să selectăm variabilele pe care le considerăm dependente de altele • să definim o funcţie fitness care să măsoare capacitatea fiecărui program de a determina valorile variabilelor independente când sunt date valorile celor dependente • să selectăm mulţimile adecvate de funcţii şi terminale; terminalele trebuie să includă toate variabilele dependente şi poate şi altele iar funcţiile trebuie selectate pe baza cunoştintelor despre domeniu.
Ca exemplu [102] să găsim expresia simbolică ce aproximează cel mai bine mulţimea de date
239
( ){ } ( ) ( ) ( ) ( ){ }0.4,0.1,,2624.0,8.0,1629.0,9.0,0.0,0.1, L−−−−−=ii yxcare a fost generată folosind funcţia
( ) 432 xxxxxfy +++== , [ ]1,1−∈x .
Parametrii programului genetic sunt • dimensiunea populaţiei = 1000 • mulţimea funcţiilor = { }divcos,sin,exp,log,*,,, −+
• mulţimea terminalelor = { }x
• adâncimea maximă = 4 • metoda de generare a populaţiei iniţiale = full • număr de generaţii = 50 • probabilitatea de încrucişare = 0.7 • pobabilitatea de mutaţie = 0
• funcţia fitness = ( )∑ −i
ii xprogevaly ,
Câteva din programele optime obţinute la diverse generaţii sunt [102]: • la generatia 1
[+ [- [log [exp x] ] [+ [sin x] [- x x] ] ] [+ [exp [log x] ] [sin [log x] ] ] ] cu fitnessul 8.20908
• la generaţia 2 [* [+ [+ [+ x x] [div x x] ] x ] [log [exp [* x x] ] ] ] cu fitnessul 7.0476
• la generaţia 3 [* [log [- [sin x] [exp x] ] ] [+ [cos [* x x] ] [+ [+ x x] [cos x] ] ] ] cu fitnessul 4.74338
240
• la generaţia 6 [* [+ [+ [+ x [exp [log x] ] ] [div x x] ] x ] [log [exp x] ] ] cu fitnessul 2.6334 Se observă că fitnessul descreşte, ceea ce înseamnă că programul
tinde spre găsirea combinaţiei optime de funcţii; de exemplu, la iteraţia 26 se obţine fitnessul 0.841868.
10 SOFTWARE DE ALGORITMI
EVOLUTIVI
Vom descrie câteva din cele mai cunoscute pachete de
programe folosite pentru a rezolva probleme cu ajutorul algoritmilor evolutivi.
GENESIS:GENEtic Search Implementation System (autor, John Grefenstette) este scris în limbajul C şi poate fi utilizat sub Linux sau MsDos. Uşurinţa sa în utilizare a făcut ca, mult timp, să fie cel mai utilizat pachet de programe în probleme de optimizare a funcţiilor. Totuşi, are şi limitări importante: nu admite decât reprezentări binare sau vectori de numere reale, implementează doar încrucişarea dublă şi este dificil de extins.
Pachetul este însoţit de un ghid de utilizare foarte clar şi concis, care prezintă principalele opţiuni de utilizare şi modul cum se setează diverşi parametri. GENESIS a fost, şi încă mai este, important ca material didactic.
242
GENEsYs (autor, Thomas Bäck) este o extensie a programului GENESIS, modul de utilizare fiind aproape identic. El elimină o parte din limitările programului de bază; de exemplu, permite încrucişarea multiplă, introduce diverse metode de selecţie, permite autoadaptarea ratei de mutaţie. Totuşi, nici această versiune nu aduce noutăţi în privinţa reprezentării datelor. Sunt utilizate o mulţime de funcţii obiectiv: funcţii De Jong, funcţii continue complicate, funcţii binare, funcţii fractale.
DGENESIS: Distributed GA (autor, Erick Cantu-Paz) este bazat pe GENESIS 5.0 şi are scopul de a implementa un algoritm genetic distribuit pentru o reţea de staţii de lucru. Fiecare subpopulaţie este prelucrată printr-un process UNIX iar utilizatorul poate fixa rata de migrare, intervalul de migrare şi topologia comunicării dintre subpopulaţii.
Simple GA (autor, Stephen J. Hartley) este scris în Java şi este mai complex decât programele anterioare. Principala slăbiciune constă în absenţa unor clase care să implementeze structuri de date complexe (de exemplu, arbori) dar structura ierarhiei de clase permite utilizatorului să-şi creeze cu uşurinţă astfel de reprezentări.
243
GAL: Simple GA in Lisp (autor, Bill Spears) este un program în Common Lisp bazat pe pachetul GENESIS. Foloseşte încrucişarea multiplă aplicată la 60% din indivizi dar este posibil să se utilizeze şi încrucişarea uniformă; mutaţia este bazată pe fitnessul proporţionat.
GALIB (autor, Matthew Wall) este scris în C++ şi poate fi rulat sub diverse sisteme de operare (Win 9.x, Win NT, Linux, MAC, etc). Este un pachet deosebit de complex: conţine clase predefinite pentru reprezentarea cromozomilor ca şiruri binare, matrice binare, vectori reali, matrice reale, arbori, etc. şi defineşte un mare număr de operatori de evoluţie pentru fiecare din aceste reprezentări. Documentaţia este foarte detaliată, conţinând peste 190 de pagini în format html. SUGAL (autor, Andrew Hunter) este scris în C şi poate fi utilizat sub Linux şi Windows. Pentru cei care nu cunosc foarte bine limbajul C++, SUGAL este o alternativă la pachetul GALIB. La fel ca şi acesta dispune de o gamă largă de reprezentări şi de operatori evolutivi. Documentaţia este foarte bogată, ghidul de utilizare având în jur de 145 de pagini html. De asemenea, conţine un mare număr de exemple, ceea ce permite ca de fiecare dată să se găsească printre ele unul destul de apropiat de problema de rezolvat.
GAGA: A Genetic Algorithm for General Application este un algoritm general folosit pentru a minimiza funcţii obiectiv
244
dificile.Versiunea originală, scrisă de Hilary Adams, a fost modificată de Ian Poole şi rescrisă în C de Jon Crowcroft .
GENOCOP, Genetic-2, Genetic-2N: (autor, Zbigniew Michalewicz) sunt pachete de algoritmi genetici folosiţi pentru optimizări numerice.
GENOCOP: GEnetic algorithm for Numerical Optimization for COnstrained Problems, optimizează funcţii cu orice număr de restricţii liniare de tip egalitate sau inegalitate.
Genetic-2 : rezolvă problema de transport liniară, minimizând costul transportului.
Genetic-2N : rezolvă problema de transport neliniară, minimizând costul transportului.
GenET: (autor, Cezary Z. Janikow) este un pachet de programe , scrise în C++, care permite dezvoltarea rapidă de aplicaţii, idependent de domeniu. GenET a fost scris cu intenţia de a deveni o bibliotecă de reprezentări şi operatori ce pot fi utilizaţi ca un mecanism de a compara diferite modele şi strategii. Conţine multe exemple de implementări pentru probleme cu structuri omogene sau heterogene şi furnizează diverse modele ale populaţiei, caracteristice algoritmilor genetici şi programării evolutive. Permite adaptarea automată a probabilităţilor operatorilor şi un mecanism de selecţie dinamic.
245
SES: Simple Evolution Strategy (autor, Joachim Sprave) este un program (în limbajul C) de optimizare parametrică bazat pe strategii evolutive. SES este o implementare tradiţională a strategiilor evolutive, dar are şi unele deficienţe: - mutaţiile corelate şi încrucişarea globală nu sunt implementate - încrucişarea discretă operează simultan asupra ambilor parametri:
iσ şi sunt luaţi din acelaşi părinte pentru fiecare poziţie i . ix
EM: Evolution Machine (autori: Hans-Michael Voigt,
Joachim Born, Jens Treptow) reprezintă o colecţie de algoritmi genetici şi strategii evolutive, aplicabili problemelor de optimizare cu codificare reală. EM tratează în principal algoritmi genetici dar are şi abordări ale căutării evolutive. O caracteristică este reprezentarea grafică (în una, două şi trei dimensiuni) a rezultatelor, ceea ce permite analiza funcţiei fitness şi a evoluţiei procesului de optimizare.
LICE (autor, Joachim Sprave) este un program de optimizare
parametrică bazat pe strategii evolutive; foloseşte o schemă de selecţie locală pentru a preveni stagnarea prematură.
WinGA: Simple Genetic Algorithm for Windows (autor, Jason H. Moore) este o demonstraţie interactivă de utilizare a algoritmilor genetici. Programul permite utilizatorului să varieze parametrii algoritmului genetic şi să analizeze performanţele.
246
TOLKIEN: TOoLKIt gENetics-based applications (autor, Anthony Yiu-Cheung Tang) este o bibliotecă de clase C++ pentru utilizarea algoritmilor genetici şi a sistemelor de clasificare. Pachetul include textul sursă, un manual de utilizare, un tutorial şi câteva programe demonstrative.
GAucsd: Genetic Algorithm Software Package (autor, Nici Schraudolph) este bazat pe GENESIS, dar se deosebeşte prin numeroase îmbunătăţiri; cele mai importante se referă la simplificarea scrierii evaluării funcţiilor şi la codificarea parametrilor. Aceste modificări duc la creşterea performanţei căutării în spaţii continue.
GAC: Simple GA in C (autor, Bill Spears) foloseşte încrucişarea cu puncte aplicată la 60% din populaţie ( fiind mai mic decât lungimea unui cromozom), dar este posibil să se folosească şi încrucişarea uniformă. Mutaţia este foarte puţin folosită iar selecţia este de tip fitness proporţionat.
n n
GAGS: Genetic algorithm application generator and C++
class library (autor, J.J. Merelo Guervos) . GAGS 0.92 (Genetic Algorithms from Granada, Spain) este un generator, scris în C++, de aplicaţii de tip algoritm genetic. GAGS oferă următoarele posibilităţi: • lucrul cu indivizi de dimensiune variabilă • selecţia de tip turneu, ruletă • încrucişarea cu două puncte • mutaţia la nivel de bit
247
GAMusic: Genetic Algorithm to Evolve Musical Melodies
(autor, Jason H. Moore) generează melodii scurte iar utilizatorul le asociază fitnessul corespunzător. Operaţiile de mutaţie şi încrucişare la nivelul frecvenţelor sunt controlate de utilizator. Fiecare serie de note muzicale este reprezentată în binar într-un tablou de dimensiune 128, ceea ce permite 30 note pe melodie şi furnizează un spaţiu al
soluţiilor de aproximativ melodii. 38104.3 ∗
GENALG: Genetic Algorithm package written in Pascal
(autor, Wesley R. Elsberry) este un program care demonstrează lucrul cu algoritmi genetici. Pornind de la o populaţie de numere reale generate aleator, încearcă să găsească un număr suficient de aproape de un număr dat.
GenET: Domain-independent generic GA software package (autor, Cezary Z. Janikow) permite dezvoltarea rapidă de aplicaţii, fiind o bibliotecă de reprezentări şi operatori. Permite lucrul cu diverse modele: algoritmi genetici, steady-state, modele ( )mn, şi
de programare evolutivă. ( mnn +, )
Genie: GA-based modeling/forecasting system (autor, Lance Chambers) este utilizat în planificarea pe termen lung: construieşte un model al unui “mediu” şi prognozează cum va evolua mediul în viitor.
248
GENlib: Genetic Algorithms and Neural Networks (autor, Jochen Ruhland) este o bibliotecă ce conţine funcţii pentru algoritmi genetici şi două aplicaţii pentru antrenarea reţelelor neuronale. Prima aplicaţie utilizează algoritmi genetici pentru a antrena o reţea feed-forward cu trei nivele ca să poată lucra ca funcţia cosinus. Un astfel de antrenament este foarte dificil de efectuat cu un algoritm de tip „propagare înapoi”, în timp ce algoritmii genetici dau rezultate foarte bune. A doua aplicaţie dezvoltă o reţea neuronală care imită funcţia XOR. Pentru aceasta sunt folosiţi doi algoritmi genetici: primul stabileşte topologia reţelei iar al doilea ajustează ponderile.
mGA: C and Common Lisp implementations of a messy GA (autori: Kalyanmoy Deb, David E. Goldberg, T. Kerzic) este o implementare în C a algoritmilor genetici dezordonaţi. De asemenea, este disponibilă şi o versiune în Common Lisp. Testele prezentate scot în evidenţă faptul că aceşti algoritmi găsesc întotdeauna optimul global, într-un timp polinomial.
ParaTSP: Parallel GA with Simulated Annealing to solve TSP's (autor, Holger Totzke) este un pachet software (bazat pe GENEsYs) folosit pentru a rezolva problema comis voiajorului, cu ajutorul algoritmilor genetici şi a călirii simulate.
BIBLIOGRAFIE [1] Arabas J., Michalewicz Z., Mulawka J. – GAVaPS – A Genetic Algorithm with Varying Population Size, in [62], pp. 73-78
[2] Bäck T.- The interaction of mutation rate, selection and self adaptation within a genetic algorithm, in [57], pp. 85-94
[3] Bäck T.- Optima mutation rates in genetic search, in [28] , pp. 2-8
[4] Bäck T., Hoffmeister F., Schwefel H.-P. - A survey of evolution Strategies, in [11], pp. 2-9
[5] Bäck T., Rudolpf G., Schwefel H.-P. – Evolutionary Programming And Evolution Strategies: Similarities and Differences, in [23], pp. 11-22
[6] Bäck T., Schwefel H .-P. – An Overview of Evolutionary Algorithms for Parameter Optimization, Evolutionary Computation, 1(1)(1993), pp. 1-23
[7] Bäck T., Schwefel H.-P. – Evolution Strategies I: Variants and their computational implementation, in [96], pp. 111-126
[8] Bäck T., Schwefel H.-P. – Evolution Strategies II: Theoretical Aspects , in [96], 1995, pp. 127-140
250
[9] Bäck T., Schwefel H. -P. – Evolutionary computation. An Overview, in [31], pp. 20-29
[10] Bäck T., Schütz M. – Intelligent Mutation rate control in
canonical genetic algorithms, in [69], pp. 158-167
[11] Belew R. K., Booker L. B. (Eds.) – Proc. 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, CA, 1991
[12] Davis L. – Applying Adaptive Algorithms to Epistatic Domains, Proc. of the Int. Joint Conf. on Artificial Intelligence, 1985, pp. 162-164
[13] Davis, L.(Ed) - Handbook of Genetic Algorithms , Van Nostrand Reinhold, New York, 1991
[14] De Jong K. A. - An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, Ann Arbor, MI, 1975.
[15] Dumitrescu D. - Algoritmi genetici şi strategii evolutive -
Aplicaţii în inteligenţa artificială şi în domenii conexe, Editura
Albastră, Cluj-Napoca, 2000
[16] Dumitrescu D., Lazzerini B., Jain L. C., Dumitrescu A. – Evolutionary Computation, CRC Press, Boca Raton, Florida, 2000
[17] Eshelman L. J. – The CHC Adaptive Search Algorithm: How to Have Safe Search when Engaging in Nontraditional Genetic
251
Recombination, in [70], pp. 265-283
[18] Eshelman L. J. (Ed.) – Proc. of the Sixt Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1995
[19] Eshelman L. J., Schaffer J. D. – Crossover’s niche, in [29], pp. 9-14 [20] Fitzpatrick J. M., Grefenstette J. J. – Genetic algorithms in noisy environments, Machine Leraning 3 (1988), pp 101-120
[21] Fogarty T. C. – Varying the probability of mutation in the genetic algorithm, in [74], pp. 104-109
[22] Fogel D. B. - Evolving Artifcial Intelligence. PhD thesis, University of California, San Diego, 1992.
[23] Fogel D. B. – Evolutionary computation : Toward a New Philosophy of Machine Intelligence, IEEE Press, Piscataway, NJ, 1995
[24] Fogel D. B., Atmar W. (Eds.) – Proc. Second Annual Conf. Evolutionary Programming (EP’93), San Diego, CA, 1993
[25] Fogel L. J. – Autonomous automata, Industrial Research 4 (1962), pp. 14-19
[26] Fogel L. J. – Toward inductive inference automata, Proc. Int. Federation for Information Processing Congress, Munich, 1962, pp. 395-399
[27] Fogel L. J., Angeline P. J., Bäck T. (Eds.) – Proc. 5th Conf. on
Evolutionary Programming, MIT Press, Cambridge, MA, 1996
252
[28] Fogel L. J., Owens A. J., Walsh M. J. – Artificial Intelligence through Simulated Evolution, John Wiley, New York, 1966
[29] Forrest S. ( Ed.) – Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1993
[30] Fox B. R., McMahon M. B. – Genetic operators for Sequencing Problems, in [70], pp. 284-300
[31] Fukuda T., Furuhashi T., Fogel D. B. (Eds.) – Proc. 1996 IEEE Int. Conf. Evolutionary Computation (ICEC’96), Nagoya, IEEE Press, Piscataway, NJ, 1996
[32] Goldberg D. E. – Optimal Initial Population Size for Binary- Coded Genetic Algoritms, TCGA Report No. 85001, Tuscaloosa, Univ. of Alabama, 1985
[33] Goldberg D. E. – Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989
[34] Goldberg D. E., Korb B., Deb K. – Messy genetic algorithms: Motivation, analysis and first results, Complex Systems, 3(1989), pp. 493-530
[35] Goldberg D. E., Deb K., Korb B. – Messy genetic algorithms revisited : nonuniform size and scale, Complex Systems, 4(1990), 415-444
[36] Goldberg D. E., Deb K., Korb B. – Don’t worry, be messy, in [11], 24-30
253
[37] Goldberg D. E., Lingle R. – Alleles, Loci and the TSP, in [38], pp. 154-159
[38] Grefenstette J. J. (Ed.) – Proc. of the First Int. Conf. on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985
[39] Grefenstette J. J. – Optimization of Control Parameters for Genetic Algorithms, IEEE Transactions of Systems, Man and Cybernetics, Vol. 16, No. 1, pp. 122-128, 1986
[40] Grefenstette J. J. (Ed.) – Proc. of the Second Int. Conf. on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, 1987
[41] Grefenstette J. J., Gopal L., Rosmata B., Van Gucht D. – Genetic Algoritm for The TSP, in [38], pp. 160-168
[42] Groşan C., Oltean M., – Algoritmi evolutivi, Gazeta de informatică, Vol 11/8, 2001, pag.30-36
[43] Herrera F., Verdegay J. L. (Eds.) – Genetic Algorithm and Soft Computing, Physica-Verlang, Heidelberg, 1996
[44] Holland J. H. – Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, 1975
[45] Homaifar A., Guan S. – A new Approach on the Traveling Salesman Problem by Genetic Algorithm, Technical Report, North Carolina A&T State University, 1991
[46] Iancu I. – A Contractive Genetic Algorithm, Proc. of 4-th Int. Conf. on Artificial Intelligence and Digital Communication,
254
Craiova, June 2004, pp. 38-43
[47] Iancu I. – A Ciric's Fix Point Theorem in Genetic Algorithms. Proc. of 5-th Int. Conf. on Artificial Intelligence and Digital Communications, Craiova, september 2005, pp. 53-60
[48] Iancu I. – Algoritmi genetici, Editura SITECH, Craiova, 2008
[49] Jog P., Suh J. Y., Gucht D. V. – The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Traveling Salesman Problem, in [74], pp. 110-115
[50] Jones T., Forrest S. – Fitness Distance Correlation as a Measure Problem Difficulty for Genetic Algorithms, in [18], pp. 81-87
[51] Joza J. R. – Hierarchical genetic algorithms operating on Populations of computer programs, in [86], pp. 768-774
[52] Koza J. R. – Genetic Programming, MIT Press, Cambridge, MA, 1992
[53] Kubota N., Kojima F., Hashimoto S., Fukuda T. – Information Transformation by virus-evolutionary genetic programming, Artificial Life Robotics, 4(2000), 171-174
[54] Kursave F. – A variant of Evolution Strategies for vector optimization, in [80], pp. 193-197
[55] Luchian H., Luchian S. – Clasificare evolutivă, Editura Integral,
Iaşi, 1999
[56] Martello S. , Toth S., – Knapsack Problems, John Wiley,
255
Chichester, UK, 1990
[57] Männer R., Manderick B. (Eds.) – Proc. 2nd Conf. on Parallel Problem Solving from Nature, North-Holland, Amsterdam, 1992
[58] Matthews J. – Diophantine Equation Solver, http://www.generation5.org/content/2000/diophantine_ga.asp
[59] McDonnell J.R., Reynolds R. G., Fogel D. B. (Dds.)- Proc. of the Fourth Annual Conference on Evolutionary Programming, the MIT Press, 1985
[60] Michalewicz, Z. - Genetic Algorithms + Data Structures =Evolution Programs Springer-Verlag, Berlin, 1994
[61] Michalewicz Z. - Genetic Algorithms, Numerical Optimization and Constraints, Proc. of the 6th Int. Conf. on Genetic Algorithms, Pittsburgh, July 15-19, 1995, pp. 151-158
[62] Michalewicz Z., Attia N. – Evolutionary Optimization of Constrained Problems, in [83], pp. 98-108
[63] Michalewicz Z., Schaffer D., Schwefel H.-P., Fogel D., Kitano H.
(Eds.) - Proceedings of the First IEEE International Conf. on
Evolutionary Computation, Service Center, Piscataway, NJ, Vol.
1, Orlando, 1994
[64] Michalewicz Z., Schoenauer M. – Evolutionary Algorithms for Constrainted Parameter Optimization Problems, Evolutionary Computation, Vol.4, No.1, 1996, pp. 1-32
[65] Mitchell M. – An introduction to Genetic Algorithms, MIT
256
Press, Cambridge, MA, 1996
[66] Morán, F., Moreno A., Morelo J. J., Chacón P. (Eds.) – Advances in Artificial Life, Proc. Third European Conf. Artificial Life (ECAL’95), Springer, Berlin, 1995
[67] Oliver I. M., Smith D. J. , Holland J.R.C. – A study of Permutation Crossover Operators on the Traveling Salesman Problem, in [38], pp. 159-166
[68] Orvosh D., Davis L. – Shall We Repair ? Genetic Algorithms, Combinatorial Optimization and Feasibility Constraint, in [29], p. 650
[69] Ras Z. W., Michalewicz M. (Eds.) – Foundations of Intelligent systems, Lectures Notes in Artificial Intelligence, 1079, Springer, Berlin, 1996
[70] Rawlins G. (Ed.) - Foundations of Genetic Algorithms, First Workshop on the Foundations of Genetic Algorithms and Classifier Systems, Morgan Kaufmann Publishers, San Mateo, CA, 1991
[71] Rechenberg I. – Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biolobischen Evolution, Frommann- Holzboog Verlang, 1973
[72] Rudolpf G. – On correlated mutations in evolution strategies in [57], pp. 105-114
[73] Rudolpf G. – Convergence Analysis of Canonical Genetic Algorithms, IEEE Transactions on Neural Networks, special issue
257
on evolutionary computation, vol. 5, no. 1, 1994
[74] Schaffer J. (Ed.) – Proc. of the Third Int. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, CA, 1989
[75] Schaffer J., Caruana R., Eshelman L., Das R. – A study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization, in [74], pp. 51-60
[76] Schwefel H. –P. – Evolutionsstrategie und Numerische Optimierung, Ph. D. Thesis, Technische Universität Berlin, 1975
[77] Schwefel H. –P. – Numerische Optimierung von Computer- Modellen Mittels der Evolutionsstrategie, Birchäuser, Basel, 1977
[78] Schwefel H. –P. – Numerical Optimization of Computer Models, John Wiley, Chichester, UK, 1981
[79] Schwefel H. –P. - Evolution and Optimum Seeking, John Wiley, New York, 1995
[80] Schwefel H. –P , Männer R. (Eds.) – Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 496, Springer, Berlin, 1991
[81] Schwefel H.-P., Rudolpf G. – Contemporary evolution strategies, in [66], pp. 893-907
[82] Schwefel H.-P., Rudolpf G., Bäck T. - Contemporary evolution strategies, Technical Report of the Systems Analysis Research Group SYS-6/95 University of Dortmund, Dept. of Computer
258
Science, December, 1995
[83] Sebald A. V., Fogel L. J. (Eds.) - Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scientific Publishing, River Edge, NJ, 1994
[84] Seniw D. – A Genetic Algorithm for the Traveling Salesman Problem, MSc Thesis, Univ. Of North Carolina at Charlotte, 1991
[85] Shimojima K., Kubota N., Fukuda T. – Virus-evolutionary genetic algorithm for fuzzy controller optimization, in [40], 369-388
[86] Shridharan K. E. (Ed.) - Proc. 11th Int. Joint Conf. on Artificial Intelligence, Morgan Kaufmann, San Francisco, CA, Vol. 1, 1989
[87] Spears W. M., De Jong K. A. – On the virtutes of parametrized uniform crossover, in [11], pp. 230-236
[88] Suh J. – Y., Gucht Van D. – Incorporating Heuristic Information into Genetic Search, in [40], pp. 100-107
[89] Syswerda G. – Schedule Optimization Using Genetic Algorithms, in [12], pp. 332-349
[90] Szalas A., Michalewicz Z. – Contractive Maping Genetic Algorithms and Their Convergence, Department of Computer Science, Univ. of North Carolina al Charlotte, Technical Report 006-1993
[91] Vişinescu R. – Un model genetic pentru problema orarului, Gazeta de informatică, Vol. 11/6, 2001, pag. 34-37
259
[92] Whitley D. (ED.) - Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, Saint Louis, Missouri, U.S.A, 1993
[93] Whitley D. – Genetic Algorithm Tutorial, Statistics and Computing (4): 65-85, 1994.
[94] Whitley D., Rowe J. - Foundations of Genetic Algorithms (FOGA): Eighth International Workshop, LNCS 3469, pp. 21-36.
[95] Whitley D., Starkweather T., Fuquay D. A. – Scheduling Problems and Traveling Salesman; The Genetic Edge Recombination Operator, in [74], pp. 133-140
[96] Winter G., Périaux J., Galán M., Cuesta P. (Eds.) – Genetic Algorithms in Engineering and Computer Science, Wiley, NY, 1995
[97] Yao X., Liu Y. – Fast evolutionary programming, in [27], pp. 451- 460 [98] *** – GEATbx - The Genetic and Evolutionary Algorithm Toolbox for Matlab, http://www.geatbx.com/download.html
[99] *** – http://cs.felk.cvut.cz/~xobitko/ga/ [100] *** – http://labo.algo.free.fr/pvc/algorithme_genetique.html [101] *** – http://lancet.mit.edu/~mbwall/presentations/IntroToGAs/
