Algoritmi genetici [611921]
Algoritmi genetici
/xrhombusPreliminarii
/xrhombusNoțiuni elementare
/xrhombusSelecția
/xrhombusMutația
/xrhombusÎncrucișarea
/xrhombusEvoluția
/xrhombusConcluzii
/xrhombusRezumat
/xrhombusImplementări sugerate Capitolul
15
În cadrul acestui capitol vom prezenta una dintre cele mai interesante metode probabi-
listice cu ajutorul căreia pot fi rezolvate problemele NP-complete. Vom introduce al-goritmii genetici și vom prezenta modul în care pot fi implementați aceștia.
15.1. Preliminarii
Algoritmii genetici sunt inspirați din teoria evoluționistă a lui Darwin . Selecția natura-
lă este adaptată pentru a permite identificarea soluțiilor unor probleme. O posibilă soluție este considerată a fi un cromozom. Elementele soluției sunt con-siderate a fi gene. Cromozomii vor evolua în așa fel încât vor ajunge să descrie soluția
problemei.
La început vom avea o populație de cromozomi care, de obicei, este generată alea-tor. În timpul unei generații cromozomii se vor transforma. De-a lungul generațiilor, ei
se vor îmbunătăți și vor descrie din ce în ce mai bine soluția căutată.
În cadrul acestui capitol vom exemplifica mecanismul algoritmilor genetici folo-sind ca exemplu problema determinării clicii maximale a unui graf.
15.2. Noțiuni elementare
Așa cum am afirmat anterior, algoritmii genetici folosesc cromozomi (formați din ge-
ne) pentru a caracteriza soluțiile candidate. Spre deosebire de algoritmii clasici, nu
vom încerca să căutăm soluția, ci vom genera soluții și vom verifica cât de bune sunt acestea.
15. Algoritmi genetici 205
Totalitatea cromozomilor utilizați pentru găsirea soluției poartă denumirea de po-
pulație . Starea populației la un moment dat poartă denumirea de generație .
La fiecare generație, asupra cromozomilor sunt aplicați operatorii genetici. Cei mai
cunoscuți și mai des utilizați astfel de operatori sunt mutația și încrucișarea .
Pentru a construi generația următoare vom aplica un proces de selecție care ne va permite să alegem cromozomii supraviețuitori (cei mai promițători cromozomi). Pen-
tru această alegere vom calcula o funcție care va caracteriza gradul de adaptabilitate
sau calitatea cromozomilor. Termenul în limba engleză folosit pentru această funcție este fitness function .
15.2.1. Cromozomii
Așadar, cromozomii sunt formați din gene. Un cromozom va caracteriza o posibilă so-
luție, în timp ce o genă va caracteriza o componentă a soluției.
De exemplu, pentru problema clicii maximale, este c onvenabil să considerăm cro-
mozomul ca fiind o secvență de N biți. Fiecare bit va corespunde unui nod al grafului.
Valoarea unui bit va fi 1, dacă nodul face parte din clică și 0 în caz contrar.
Așadar, fiecare cromozom va caracteriza a clică. În acest moment nu ne punem problema dacă clica respectivă este validă deci, din acest punct de vedere, nu ne inte-
resează dacă există două noduri între care nu există muchie dar cărora le corespunde o
genă cu valoarea 1. Populația va fi formată din mai multe astfel de secvențe, fiecare caracterizând o clică. La fiecare generație, clicile vor evolua și, în final, vom alege o soluție.
Evident, structura unui cromozom va depinde de problema care trebuie rezolvată.
Șirul de biți nu va putea fi utilizat, de exemplu, pentru problema ciclului hamiltonian. Pentru această problemă este posibil să considerăm cromozomii ca fiind permutări ale
mulțimii nodurilor. Ordinea nodurilor în ciclul hamiltonian va fi dată de ordinea aces-
tora în permutare.
15.2.2. Calitatea
Potrivit teoriei darwiniste, în natură supraviețuiesc indivizii cel mai bine adaptați. Crite-
riile naturale sunt complexe și dificil de simulat. Totuși, ideea de bază rămâne: pentru fi-
ecare cromozom vom încerca să stabilim cât de performant este. Pentru aceasta vom in-
troduce o funcție de calitate care depinde de configurația (structura) unui cromozom. Pentru problema clicii maximale, alegerea evidentă este dată de numărul nodurilor
care fac parte din clică. Așadar, funcția de calitate ar putea fi egală cu numărul biților
care au valoarea 1 în reprezentarea cromozomului. Din nefericire, de data aceasta trebuie să fim siguri că performanțele indivizilor sunt corect evaluate. Din acest motiv nu mai putem ignora faptul că anumite clici (de
fapt, marea majoritate) nu sunt valide.
206 II. Probleme NP
De aceea, va trebui să introducem o funcție de penalizare care să indice cât de "de-
parte" se află cromozomul respectiv față de o clică validă. Valoarea funcției de penali-
zare va fi scăzută din valoarea calității cromozomului.
Evident, se pot obține rezultate negative, dar acest aspect nu este important pentru moment.
15.3. Selecția
După stabilirea calității cromozomilor dintr-o anumită generație vom începe "construi-
rea generației următoare". Pentru aceasta va trebui să stabilim criteriile potrivit cărora
vom alege cromozomii care vor participa la crearea următoarei generații.
Acești cromozomi vor forma o așa-numită piscină de încrucișare și vor fi utilizați
pentru crearea indivizilor din cea mai bună generație.
Evident, criteriul de selecție cel mai convenabil este calitatea cromozomilor. Cu
toate acestea, există mai multe metode care pot fi utilizate pentru a crea piscina de în-crucișare. Câteva dintre ele vor fi prezentate în cele ce urmează.
15.3.1. Ruleta
În marea majoritate a cazurilor, numărul cromozomilor din piscina de încrucișare tre-
buie să fie egal cu numărul cromozomilor din populație. S-ar putea trage imediat con-
cluzia că, în acest caz, întreaga populație va fi inclusă în această piscină. Din fericire, adevărul este cu totul altul: piscina va fi creată pe baza calității cromozomilor; la fie-
care pas se va alege un cromozom care va face parte din piscina de încrucișare; după
alegerea unui cromozom, acesta nu este eliminat din populație, deci are șanse să fie ales din nou; așadar, numărul de copii ale unui cromozom în piscina de încrucișare va depinde de calitatea acestuia. Ca urmare, vom avea cromozomi care vor apărea de mai
multe ori și cromozomi care nu vor apărea nici o dată.
Principiul ruletei va fi prezentat în continuare. Fiecărui cromozom îi va corespunde o "regiune" a ruletei. Regiunea va fi cu atât mai mare, cu cât calitatea cromozomului
este mai mare. Vom învârti apoi ruleta (vom genera un număr aleator) și vom selecta
cromozomul care corespunde regiunii în dreptul căreia s-a oprit acul ruletei. Practic, mai întâi vom normaliza funcția de calitate astfel încât să avem doar valori strict pozitive (chiar și cei mai slab adaptați indivizi trebuie să aibă șansa lor, indife-
rent cât de mică este aceasta) și valorile mai mari să corespundă unor indivizi mai bine
adaptați. O variantă este să adunăm valoarea absolută a calității celui mai puțin per-formant cromozom la calitatea tuturor cromozomilor. Evident, operația are sens doar
dacă avem cromozomi pentru care valoarea funcției de calitate este negativă. Cel mai
puțin performant cromozom va avea acum calitatea 0. Din acest motiv, vom mai adu-na o mică valoare pentru a obține doar valori pozitive.
După obținerea calităților strict pozitive pentru toți cromozomii, vom stabili regiuni-
le de pe ruletă. Există două variante: prima dintre ele este determinarea sumei S a calită-
15. Algoritmi genetici 207
ților tuturor cromozomilor și apoi atribuirea pentru fiecare cromozom al unui subinter-
val al intervalului [0, 1). Subintervalele vor fi disjuncte, iar lungimea unui subinterval
corespunzător unui cromozom cu calitatea q va fi q / S. În cazul în care avem doar cali-
tăți care sunt numere naturale, nu este eficient să introducem numere reale. De aceea, pentru cea de-a doua variantă, vom atribui subintervale ale intervalului [0, S], iar lun-
gimea unui subinterval corespunzător unui cromozom cu calitatea q va fi chiar q. Se
simplifică astfel calculele care trebuie efectuate pentru stabilirea regiunilor.
După stabilirea regiunilor vom învârti ruleta de N ori. La fiecare pas, vom alege
cromozomul corespunzător regiunii în dreptul căreia se va opri acul. Pentru a simula
învârtirea ruletei, vom genera un număr aleator cuprins între 0 și 1, sau între 0 și S, în
funcție de modul în care au fost stabilite regiunile. În final, vom avea N cromozomi (în
marea majoritate a cazurilor aceștia nu vor fi distincți) care vor face parte din piscina
de încrucișare.
15.3.2. Turneul
O a doua posibilitate de realizare a selecției este "lupta dreaptă" dintre cromozomi.
Avantajul acestei metode constă în simplitatea prin care ea poate fi implementată. Practic, la fiecare pas vom alege în mod aleator doi cromozomi și îi vom introduce în
piscina de încrucișare pe cel mai adaptat dintre ei.
Există și unele dezavantaje ale acestei metode și anume: cel mai slab cromozom nu va fi niciodată ales și se introduce o ușoară notă de determinism. Bineînțeles, putem construi diverse variante de turnee. De exemplu, putem alege
patru cromozomi care "luptă" într-un turneu cu semifinale și finale. Evident, procedeul
se poate extinde pentru orice putere a lui 2; putem avea turnee cu sferturi, optimi, șai-sprezecimi etc. Chiar dacă nu alegem o putere de-a lui 2, tot putem simula turneul.
Vor exista câțiva cromozomi norocoși care vor trece direct în turul 2.
De asemenea, este posibil să alegem un număr arbitrar k de cromozomi și să simu-
lăm un turneu în care fiecare luptă cu fiecare.
Pentru a introduce o notă de nedeterminism, putem stabili faptul că victoria într-o
"luptă" nu va reveni imediat celui mai bine adaptat dintre cei doi "combatanți", ci în-vingătorul va fi stabilit aleator, dar șansele de a fi ales ale unui cromozom vor depinde de calitatea sa. Astfel, într-o "bătălie" dezechilibrată, cel mai bine adaptat cromozom
va avea șanse foarte mari, dar în una echilibrată cei doi vor avea șanse aproape egale.
Putem merge și mai departe simulând turnee cu partide tur-retur în care cromozomul "gazdă" beneficiază de "ajutorul publicului" (primește un bonus) și orice altceva ne-am
putea imagina. Deși, imaginația poate să conceapă tot felul de turnee, este recomandat ca
acestea să fie cât mai simple, deoarece simularea lor consumă timp prețios.
208 II. Probleme NP
15.3.3. Selecție preferențială
În anumite situații, nu toate "locurile" din piscina de încrucișare sunt stabilite în mod
echitabil. De exemplu, putem presupune că este de dorit ca cromozomul cel mai per-formant să rămână în populație, indiferent de modul în care acționează șansa.
De asemenea, în cazul reprezentărilor pe biți, se obișnuiește să fie incluși doi cro-
mozomi speciali și anume cel pentru care toți biții au valoarea 0 și cel pentru care toți biții au valoarea 1.
15.3.4. Alte tipuri de selecție
După cum ați văzut și în cazul selecției turneu, se pot imagina tot felul de modalități de selecție. Datorită caracterului nedeterminist al algoritmilor genetici, implementarea unor astfel de algoritmi este considerată o "artă" în care imaginația "artistului" este esențială.
Deși selecțiile descrise sunt cele clasice, vă puteți imagina tot felul de criterii potri-
vit cărora puteți stabili care sunt cromozomii norocoși. Iată câteva exemple:
•un număr de cromozomi (cei mai adaptați) intră direct în piscina de încrucișare, iar
ceilalți sunt aleși în mod aleator (sau potrivit unuia dintre celelalte principii de se-
lecție);
•un număr dintre cel mai puțin adaptați cromozomi este inclus în piscină;
•cromozomii sunt incluși în piscină în perechi de tipul (cel mai bun cu cel mai rău,
al doilea cu penultimul etc.).
15.4. Mutația
Vom începe descrierea operatorilor genetici cu cel mai simplu dintre ei. Mutația este
definită ca fiind o alterare minoră a unui cromozom. Pentru exemplul nostru, o mutație ar putea consta în modificarea valorii unuia din-
tre biți. Practic, printr-o astfel de mutație un nod intră sau iese din clică. Evident, în
urma mutației avem un alt cromozom, cu o semnificație diferită și cu o altă calitate. Este important ca modificarea cromozomului să fie minoră; în caz contrar algorit-
mul genetic va degenera într-un algoritm probabilist clasic. Evident, modul de realiza-
re a mutației depinde de reprezentarea cromozomului. De exemplu, pentru problema determinării ciclului hamiltonian, o mutație ar putea consta într-o inversiune (inter-
schimbarea a două valori) în permutarea reprezentată de cromozom.
15.5. Încrucișarea
Cel de-al doilea operator genetic este încrucișarea. Aceasta constă în alegerea a doi
cromozomi (părinți) din piscina de încrucișare și crearea altor doi (fii) pe baza unor reguli. Cele mai des utilizate metode de încrucișare sunt:
15. Algoritmi genetici 209
•încrucișare cu un punct de tăiere;
•încrucișare cu două puncte de tăiere,
•încrucișare cu mai multe puncte de tăiere;
•încrucișare prin distribuția aleatoare a genelor.
15.5.1. Încrucișarea cu un punct de tăiere
Acest tip de încrucișare constă în alegerea unei poziții aleatoare k în cromozomii pă-
rinți. Primul fiu va conține primele k gene ale primului părinte și ultimele N – k gene
ale celui de-al doilea, unde N este numărul total de gene. Similar, al doilea cromozom
va conține primele k gene ale celui de-al doilea părinte și ultimele N – k gene ale pri-
mului părinte. Încrucișarea cu un punct de tăiere este ilustrată în figura 15.1.
Părinte #1
Părinte #2
Fiu #1
Fiu #2
Figura 15.1: Încrucișarea cu un punct de tăiere
15.5.2. Încrucișarea cu două puncte de tăiere
Acest al doilea tip de încrucișare constă în alegerea a două poziții aleatoare p și q (p <
q) în cromozomii părinți. Primul fiu va conține primele p gene ale primului părinte,
următoarele q – p gene ale celui de-al doilea părinte și primele N – q gene ale primului
părinte. Al doilea cromozom va conține primele p gene ale celui de-al doilea părinte,
următoarele q – p gene ale primului părinte și primele N – q gene ale celui de-al doi-
lea. Încrucișarea cu două puncte de tăiere este ilustrată în figura 15.2.
Părinte #1
Părinte #2
Fiu #1
Fiu #2
Figura 15.2: Încrucișarea cu două puncte de tăiere
210 II. Probleme NP
15.5.3. Încrucișarea cu mai multe puncte de tăi ere
Procedura este asemănătoare în cazul în care se aleg mai multe puncte de tăiere. Gene-
le sunt preluate alternativ de la cei doi părinți. În anumite situații nu este recomandată alegerea unui număr mare de puncte de tă-
iere, deoarece comportamentul populației devine mult prea randomizat (aleator).
15.5.4. Distribuția aleatoare a genelor
O altă abordare constă în distribuirea aleatoare a genelor părinților. Pentru fiecare po-
ziție, este ales (în mod aleator) unul dintre părinți. Primul fiu va prelua gena părintelui
ales, iar al doilea fiu va prelua gena celuilalt părinte.
Din nou, este posibil ca, datorită acestei metode de încrucișare, comportamentul populației de cromozomi să devină mult prea randomizat.
15.6. Evoluția
După prezentarea noțiunilor fundamentale, putem descrie principalii pași care trebuie
efectuați de un algoritm genetic pentru ca populația de cromozomi să evolueze spre
soluție:
•crearea populației inițiale (o singură dată);
•stabilirea calității cromozomilor (la fiecare generație);
•selecția cromozomilor pentru piscina de încrucișare (la fiecare generație);
•efectuarea mutațiilor (la fiecare generație);
•efectuarea încrucișărilor (la fiecare generație);
•crearea noii generații (la fiecare generație);
•oprirea evoluției (o singură dată).
15.6.1. Populația inițială
În cele mai multe situații cromozomii din populația inițială (prima generație) sunt ge-
nerați aleator. Pentru exemplul problemei clicii maximale, se vor genera șiruri de biți de lungime N.
În unele situații este posibil ca prima generație să fie construită pe baza altor crite-
rii. De exemplu, se pot aplica metode euristice pentru a determina cromozomi cât mai bine adaptați. Avantajul acestei metode constă în faptul că vom avea încă de la început
cromozomi performanți, ceea ce ar putea duce la scurtarea timpului necesar evoluției.
15.6.2. Calitatea cromozomilor
După crearea populației inițiale, va începe procesul de evoluție, care se va desfășura
pe parcursul unui anumit număr de generații.
15. Algoritmi genetici 211
La fiecare generație se vor efectua mai multe operații, dintre care prima este stabili-
rea calității cromozomilor care fac parte din generația curentă. Pentru aceasta se va
utiliza o funcție de fitness adecvată problemei care trebuie rezolvată.
15.6.3. Selecția
În momentul în care cunoaștem calitățile cromozomilor din generația curentă putem
începe procesul de selecție. Pentru a crea piscina de încrucișare putem utiliza orice metodă de selecție care poate fi aplicată pentru problema care trebuie rezolvată.
În funcție de situație, putem combina mai multe metode de selecție dacă se dove-
dește că o astfel de abordare este utilă.
15.6.4. Mutația
În ciuda faptului că mutațiile reprezintă alterări minore ale cromozomilor, ele sunt
foarte importante în evoluția genetică. O mutație permite apariția unei caracteristici
noi care nu este găsită la nici un alt cromozom din populație și care poate duce la solu-ție. Evident, majoritatea mutațiilor vor fi inutile, dar numărul mic al celor care se do-
vedesc cu adevărat folositoare nu este un motiv pentru care acest operator genetic să
poată fi ignorat. Se va stabili o probabilitate de mutație pentru generația curentă (un număr real cu-
prins între 0 și 1 sau un număr natural cuprins între 0 și o valoare dată). Șansa ca un
cromozom să sufere o mutație va depinde de probabilitatea de mutație. Practic, pentru fiecare cromozom se va genera un număr aleator și, în cazul în care acesta este mai mic decât probabilitatea de mutație, cromozomul va suferi o mică modificare.
Pentru cromozomii aleși pentru mutație se va aplica operatorul (o mică modificare)
și noii cromozomi îi vor înlocui pe cei vechi în piscina de încrucișare.
15.6.5. Încrucișarea
Pentru realizarea încrucișării sunt aleși doi cromozomi din piscina de încrucișare și asupra lor se aplică operatorul de încrucișare. Cromozomii fii vor face parte dintr-o generație intermediară. Procesul se repetă până în momentul în care numărul cromo-
zomilor din generația intermediară devine N.
Se observă faptul că, datorită alegerii aleatoare a părinților, este posibil ca anumiți cromozomi din piscină să nu participe la nici o încrucișare, iar alții să participe la mai multe.
15.6.6. Noua generație
Pe baza generației intermediare se construiește noua generație. În foarte multe cazuri, generația intermediară devine, de fapt, noua generație (direct).
212 II. Probleme NP
Există posibilitatea ca cel mai performant cromozom obținut la generațiile trecute
să fie introdus automat în noua generație. De asemenea, anumiți cromozomi cu struc-
turi speciale pot fi și ei introduși automat în următoarea generație.
În unele cazuri, cromozomii fii vor fi inserați în noua generație numai dacă au o ca-litate mai mare decât părinții lor. În caz contrar, părinții își pot păstra locul în popula-ție.
De fapt, există o multitudine de variante care pot fi utilizate. Se pot alege o mulți-
me de valori probabilistice care să indice dacă un cromozom va fi sau nu înlocuit, dacă el va participa sau nu la încrucișare etc.
15.6.7. Oprirea evoluției
Mai devreme sau mai târziu evoluția trebuie să se încheie. În cazul în care cunoaștem anumite date despre soluție (cum ar fi numărul elementelor care trebuie să facă parte din clica maximală), atunci cunoaștem exact momentul în care ne vom opri. În caz
contrar (de exemplu, când trebuie să rezolvăm o problemă de optim) nu vom ști cu si-
guranță când am obținut o soluție acceptabilă. Câteva variante în care se poate decide momentul încheierii evoluției sunt:
•scurgerea unei perioade de timp față de momentul începerii evoluției;
•generarea unui anumit număr de generații;
•inexistența unor îmbunătățiri în ultimele k generații;
•a fost identificată o soluție care pare acceptabilă.
15.7. Concluzii
Algoritmii genetici au numeroase avantaje și numeroase dezavantaje. Dacă avem o
implementare corectă, atunci cu siguranță se va găsi soluția optimă după o perioadă de timp. Evident, nimeni nu poate determina această perioadă (ar putea fi miliarde de
ani).
Cel mai mare dezavantaj al acestor algoritmi este timpul relativ mare necesar atât implementării lor (dimensiunile codului sursă sunt considerabile), cât și rulării lor
(evoluția poate dura inacceptabil de mult).
Există câteva aspecte care trebuie luate în considerare în momentul în care se deci-de utilizarea unui algoritm genetic. În primul rând, probabilitatea de mutație poate fi fixă pe parcursul generațiilor, dar
în majoritatea cazurilor trebuie să varieze. Este recomandabil ca probabilitatea de mu-
tație să crească dacă nu se mai realizează îmbunătățiri și să scadă în cazul în care îm-bunătățirile sunt relativ frecvente (sau să fie resetată la valoarea inițială atunci când se
detectează o îmbunătățire).
O populație prea mare va necesita multe operații la fiecare generație, dar o popula-ție mai mică poate să își oprească evoluția foarte repede.
15. Algoritmi genetici 213
Există șanse să determinăm un optim local și evoluția să nu mai conducă la îmbu-
nătățiri. În această situație, pentru determinarea optimului global trebuie mutații mai
frecvente.
Există și variante ale optimizărilor locale. De exemplu, în momentul în care identi-ficăm o îmbunătățire, putem încerca să o îmbunătățim și mai mult folosind tehnici de-terministe. De exemplu, pentru problema clicii, în momentul în care determinăm o no-
uă clică, putem verifica dacă nu există vreun nod care să fie legat prin muchii de toate
nodurile din clică; în acest caz nodul respectiv poate fi și el introdus în clică. Algoritmii genetici reprezintă un subdomeniu deosebit și interesant de studiat al in-
teligenței artificiale. Pot fi obținute rezultate surprinzătoare, dar inspirația programato-
rului joacă un rol destul de important. Nu se recomandă utilizarea lor la concursurile de programare decât dacă participantul cunoaște foarte bine tehnicile necesare imple-
mentării și dacă nu se descoperă o abordare mai simplă a problemei.
15.8. Rezumat
În cadrul acestui capitol am prezentat algoritmii genetici; ei pot fi utilizați pentru a re-
zolva orice problemă de algoritmică, dar rezultatele depind foarte mult de parametrii
aleși în timpul implementării. Am prezentat modul în care teoria supraviețuirii celui mai bine adaptat poate fi uti-
lizată pentru a rezolva anumite probleme. Am introdus noțiunile elementare cu care
operăm în momentul în care construim un algoritm genetic și anume: populație, cro-mozom, genă, fitness, selecție, mutație, încrucișare, evoluție etc.
În final, am concluzionat că algoritmii genetici ascund mai multe "capcane" și pen-
tru utilizarea lor eficientă este necesară o bună cunoaștere a mecanismelor acestora.
15.9. Implementări sugerate
Dacă doriți să vă testați capacitățile de a implementa un algoritm genetic, vă sugerăm
să încercați să rezolvați următoarele probleme folosind această tehnică: 1. problema clicii;
2. problema drumului hamiltonian;
3. problema comis-voiajorului; 4. problema celor N dame;
5. problema colorării.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Algoritmi genetici [611921] (ID: 611921)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.