Algoritmi genetici

prof. Liviu-Constantin  Olaru liviu.olaru@cnpetrurares.ro

Cuprins:   Argument  |  Principiul  |  Implementări ale algoritmilor genetici:  Problema damelor şi Problema existenţei unui ciclu hamiltonian

Argument

Ca şi celelalte discipline exacte, informatica încearcă să modeleze lumea reală cu mijloace abstracte. Deşi fiecare „ştiinţă exactă“, pare să existe prin ea însăşi (fiecare dispune de un set de noţiuni fundamentale, definiţii şi teoreme care împreună dau caracterul de „autosuficienţă“), originea comună tuturor acestor discipline, este localizată în nevoia acută de pârghii necesare rezolvării problemelor practice ale universului cotidian. În cazul algoritmilor genetici, legătura cu lumea fizică (şi modelul de inspiraţie) este Teoria Evoluţionistă a lui Darwin. Vom parcurge, în acest articol, câteva dintre principiile fundamentale ale Teoriei Evoluţioniste, cu implementările similare oferite de Teoria Algoritmilor. Ne propunem să amintim pe scurt câteva dintre principiile celebrei Teorii Evoluţioniste şi să punem accent pe exemple practice ale algoritmilor genetici, realizate cu ajutorul limbajului de programare C++.

Principiul

Soluţia unei probleme rezolvabile cu ajutorul algoritmilor genetici, este o construcţie foarte asemănătoare cu un cromozom: ea are mai multe componente care sunt asimilate genelor care formează cromozomul.

Se porneşte de la o populaţie iniţială de cromozomi care evoluează în timp. După mai multe generaţii (stări ale populaţiei, în diferite momente de timp), prin îmbunătăţiri succesive ale calităţii cromozomilor (aceştia se transformă în timp), se ajunge la soluţia problemei.

O nouă generaţie de cromozomi este construită în urma unui proces de selecţie care are rolul de a alege cromozomii supravieţuitori. Aceştia vor forma o piscină de încrucişare. În acest scop, se va implementa o funcţie de calitate (adaptabilitate) a cromozomilor. În toate problemele rezolvate cu ajutorul algoritmilor genetici, funcţia de calitate este cel mai important criteriu cu ajutorul căruia se construieşte piscina de încrucişare.

Pe lângă funcţia de calitate, în practică, sunt acceptate şi alte metode cu ajutorul cărora se realizează selecţia cromozomilor care vor face parte din piscina de încrucişare; turneul şi ruleta sunt două astfel de tehnici de selecţie.

Turneul (sau „lupta dreaptă“) presupune, în esenţă, că din generaţia curentă se aleg câte doi cromozomi şi numai cel mai performant este inclus în piscina de încrucişare. Se pot imagina variante diverse de turneu, specifice problemei date.

Ruleta este folosită în special atunci când numărul cromozomilor din piscina de încrucişare trebuie să fie egal cu numărul de cromozomi din populaţia curentă. Aceasta nu înseamnă că piscina de încrucişare va fi identică cu generaţia curentă: cromozomii mai bine adaptaţi vor fi prezenţi în mai multe exemplare în piscină, iar cei slabi nu vor mai fi incluşi. Şi în cazul ruletei se pot implementa maniere multiple de creare a piscinei de încrucişare, toate bazate pe scenariul următor: fiecărui cromozom din generaţia curentă îi va corespunde, pe ruletă, o zonă de mărime proporţională cu performanţa lui; ruleta va fi învârtită (prin generarea unei valori aleatoare) şi cromozomul corespunzător zonei pe care s-a oprit acul ruletei, va fi lansat în piscina de încrucişare.

Asupra mulţimii de cromozomi din piscina de încrucişare se aplică operatori genetici (cum ar fi mutaţia sau încrucişarea), astfel încât, din cromozomii supravieţuitori ai generaţiei curente, se obţin cromozomii generaţiei următoare.

Dacă mutaţia este definită ca fiind alterarea minoră a unui cromozom, încrucişarea presupune crearea a doi fii, din doi cromozomi (părinţi) ai piscinei de încrucişare în urma unor operaţii de transfer de gene între aceştia din urmă. Trebuie amintit că mutaţia şi încrucişarea sunt operatorii genetici cei mai folosiţi.

În consecinţă, evoluţia populaţiei de cromozomi, poate fi descrisă de următorii paşi:

1. crearea populaţiei iniţiale (o singură dată);
2. stabilirea calităţii cromozomilor (la fiecare generaţie);
3. selecţia cromozomilor din piscina de încrucişare (la fiecare generaţie);
4. efectuarea mutaţiilor (la fiecare generaţie);
5. efectuarea încrucişărilor (la fiecare generaţie);
6. crearea noii generaţii (la fiecare generaţie);
7. oprirea evoluţiei (o singură dată).

Implementări ale algoritmilor genetici

Trebuie să amintim că nu întotdeauna implementările cu ajutorul algoritmilor genetici sunt cele mai eficiente (în fond şi procesul de evoluţie în lumea vie, este foarte îndelungat, conform Teoriei Evoluţioniste!). De regulă, lipsa de eficienţă îşi are originea în procesul de selecţie care este unul anevoios şi consumator de timp. Sub rezerva acestei observaţii, propunem următoarele aplicaţii: determinarea existenţei unui ciclu hamiltonian şi problema damelor. Ambele sunt probleme clasice de programare rezolvabile şi prin backtracking.

Problema damelor: fiind dată o tablă de şah de dimensiuni nXn, să se aranjeze n dame (regine) astfel încât nici una să nu fie ameninţată de o altă damă (să nu fie poziţionate pe aceeaşi linie, coloană sau diagonală).

Pentru înţelegerea facilă a algoritmului propus mai jos, sunt necesare următoarele observaţii:

1. matricea v reţine generaţia curentă, în v[k][0] fiind reţinută calitatea unui cromozom;
2. p reprezintă piscina de încrucişare, în care se introduc automat cel mai slab, precum şi cel mai bun cromozom;
3. s este o variabilă care devine nenulă dacă se ajunge la o soluţie, şi deci se opreşte execuţia programului;
4. i, j, k, min, max, p1, p2, c, aux sunt variabile auxiliare care pot avea sau nu mai multe întrebuinţări;
5. execuţia programului se opreşte dacă după o anumită perioadă de timp nu se ajunge la o soluţie.

Problema existenţei unui ciclu hamiltonian: se dă un graf neorientat şi se cere să se verifice dacă acesta este graf hamiltonian (dacă acesta are un ciclu hamiltonian). În caz afirmativ să se genereze un astfel de ciclu.