Algoritmi genetici
Cuprins: Argument | Principiul | Implementari ale algoritmilor
genetici: Problema damelor si Problema existentei unui ciclu
hamiltonian
Argument
Ca si celelalte discipline exacte, informatica încearca sa modeleze
lumea reala cu mijloace abstracte. Desi fiecare "stiinta exacta",
pare sa existe prin ea însasi (fiecare dispune de un set de notiuni
fundamentale, definitii si teoreme care împreuna dau caracterul de
"autosuficienta"), originea comuna tuturor acestor discipline, este
localizata în nevoia acuta de pârghii necesare rezolvarii
problemelor practice ale universului cotidian. În cazul algoritmilor
genetici, legatura cu lumea fizica (si modelul de inspiratie) este
Teoria Evolutionista a lui Darwin. Vom parcurge, în acest articol,
câteva dintre principiile fundamentale ale Teoriei Evolutioniste, cu
implementarile similare oferite de Teoria Algoritmilor. Ne propunem
sa amintim pe scurt câteva dintre principiile celebrei Teorii
Evolutioniste si sa punem accent pe exemple practice ale
algoritmilor genetici, realizate cu ajutorul limbajului de
programare C++.
Principiul
Solutia unei probleme rezolvabile cu ajutorul algoritmilor genetici,
este o constructie foarte asemanatoare cu un cromozom: ea are mai
multe componente care sunt asimilate genelor care formeaza
cromozomul.
Se porneste de la o populatie initiala de cromozomi care evolueaza
în timp. Dupa mai multe generatii (stari ale populatiei, în diferite
momente de timp), prin îmbunatatiri succesive ale calitatii
cromozomilor (acestia se transforma în timp), se ajunge la solutia
problemei.
O noua generatie de cromozomi este construita în urma unui proces de
selectie care are rolul de a alege cromozomii supravietuitori.
Acestia vor forma o piscina de încrucisare. În acest scop, se va
implementa o functie de calitate (adaptabilitate) a cromozomilor. În
toate problemele rezolvate cu ajutorul algoritmilor genetici,
functia de calitate este cel mai important criteriu cu ajutorul
caruia se construieste piscina de încrucisare.
Pe lânga functia de calitate, în practica, sunt acceptate si alte
metode cu ajutorul carora se realizeaza selectia cromozomilor care
vor face parte din piscina de încrucisare; turneul si ruleta sunt
doua astfel de tehnici de selectie.
Turneul (sau "lupta dreapta") presupune, în esenta, ca din generatia
curenta se aleg câte doi cromozomi si numai cel mai performant este
inclus în piscina de încrucisare. Se pot imagina variante diverse de
turneu, specifice problemei date.
Ruleta este folosita în special atunci când numarul cromozomilor din
piscina de încrucisare trebuie sa fie egal cu numarul de cromozomi
din populatia curenta. Aceasta nu înseamna ca piscina de încrucisare
va fi identica cu generatia curenta: cromozomii mai bine adaptati
vor fi prezenti în mai multe exemplare în piscina, iar cei slabi nu
vor mai fi inclusi. Si în cazul ruletei se pot implementa maniere
multiple de creare a piscinei de încrucisare, toate bazate pe
scenariul urmator: fiecarui cromozom din generatia curenta îi va
corespunde, pe ruleta, o zona de marime proportionala cu performanta
lui; ruleta va fi învârtita (prin generarea unei valori aleatoare)
si cromozomul corespunzator zonei pe care s-a oprit acul ruletei, va
fi lansat în piscina de încrucisare.
Asupra multimii de cromozomi din piscina de încrucisare se aplica
operatori genetici (cum ar fi mutatia sau încrucisarea), astfel
încât, din cromozomii supravietuitori ai generatiei curente, se
obtin cromozomii generatiei urmatoare.
Daca mutatia este definita ca fiind alterarea minora a unui
cromozom, încrucisarea presupune crearea a doi fii, din doi
cromozomi (parinti) ai piscinei de încrucisare în urma unor operatii
de transfer de gene între acestia din urma. Trebuie amintit ca
mutatia si încrucisarea sunt operatorii genetici cei mai folositi.
În consecinta, evolutia populatiei de cromozomi, poate fi descrisa
de urmatorii pasi:
crearea populatiei initiale (o singura data);
stabilirea calitatii cromozomilor (la fiecare generatie);
selectia cromozomilor din piscina de încrucisare (la fiecare
generatie);
efectuarea mutatiilor (la fiecare generatie);
efectuarea încrucisarilor (la fiecare generatie);
crearea noii generatii (la fiecare generatie);
oprirea evolutiei (o singura data).
Implementari ale algoritmilor genetici
Trebuie sa amintim ca nu întotdeauna implementarile cu ajutorul
algoritmilor genetici sunt cele mai eficiente (în fond si procesul
de evolutie în lumea vie, este foarte îndelungat, conform Teoriei
Evolutioniste!). De regula, lipsa de eficienta îsi are originea în
procesul de selectie care este unul anevoios si consumator de timp.
Sub rezerva acestei observatii, propunem urmatoarele aplicatii:
determinarea existentei unui ciclu hamiltonian si problema damelor.
Ambele sunt probleme clasice de programare rezolvabile si prin
backtracking.
Problema damelor: fiind data o tabla de sah de dimensiuni nXn, sa se
aranjeze n dame (regine) astfel încât nici una sa nu fie amenintata
de o alta dama (sa nu fie pozitionate pe aceeasi linie, coloana sau
diagonala).
Pentru întelegerea facila a algoritmului propus mai jos, sunt
necesare urmatoarele observatii:
matricea v retine generatia curenta, în v[k][0] fiind retinuta
calitatea unui cromozom;
p reprezinta piscina de încrucisare, în care se introduc automat
cel mai slab, precum si cel mai bun cromozom;
s este o variabila care devine nenula daca se ajunge la o solutie,
si deci se opreste executia programului;
i, j, k, min, max, p1, p2, c, aux sunt variabile auxiliare care
pot avea sau nu mai multe întrebuintari;
executia programului se opreste daca dupa o anumita perioada de
timp nu se ajunge la o solutie.
#include <fstream.h>
#include <time.h>
#include <stdlib.h>
ifstream f("genetic.in");
ofstream g("genetic.out");
int n, s, v[100][100], p[100][100], i, j, k, min=0, max=0, p1,
p2, c, aux;
clock_t start=clock(), stop;
struct ruleta
r[100];
int calitate(int k)
int cautare(int k, int x)
void mutatie(int k, int x)
void evolutie()
if(i!=p2 && (!min || v[i][0]<min))
r[i].i=r[i-1].s+1;
r[i].s=r[i].i+v[i][0];
}
/*selectia cromozomilor pentru piscina de incrucisare*/
if(!s)
for(i=3; i<=n; i++)
/*efectuarea mutatiilor*/
for(k=1; k<=n; k++)
randomize();
if(!c && rand()%2)
}
/*efectuarea incrucisarilor*/
for(i=1; i<=n/2; i++)
}
}
/*stabilirea noii generatii*/
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
v[i][j]=p[i][j];
stop=clock();
if(stop<start+2000)
evolutie();
}
}
int main()
else
g<<"Nu s-a ajuns la o solutie in timp acceptabil";
g<<endl;
f.close();
g.close();
return 0;
}
Problema existentei unui ciclu hamiltonian: se da un graf neorientat
si se cere sa se verifice daca acesta este graf hamiltonian (daca
acesta are un ciclu hamiltonian). În caz afirmativ sa se genereze un
astfel de ciclu.
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
ifstream f("f.in");
ofstream g("f.out");
char *gen[100], *newgen[100];
int mat[100][100], n;
/*functia pop_init() construieste populatia initiala de
cromzomi*/
void pop_init()
/*functia detcal() determina calitatea fiecarui cromozom*/
int detcal(char *p)
if(a)
c++;
else
c--;
}
return c;
}
/*functia sf_gen() stabileste daca sa ajuns la rezultatul
final, utilizand drept conditie calitatea cromozomilor din
generatia actuala*/
int sf_gen()
/*functia det_new_gen() construieste noua generatie; ea
foloseste in piscina de incrucisare toti vechii cromozomi;
altfel, nu se mai realizeaza o generatie intermediara intrucat
det_new_gen() face si mutatii pe cromozomii noi obtinuti*/
void det_new_gen()
while(a!=i);
for(j=0; j<n; j++)
if(gen[i][j]=='1' && gen[a][j]=='1')
newgen[i][j]='1';
else
newgen[i][j]=random(2)+48;
}
for(i=0; i<n; i++)
strcpy(gen[i], newgen[i]);
}
int main()
if(a)
g<<"Exista un ciclu hamiltonian";
else
g<<"Nu exista ciclu hamiltonian";
f.close();
g.close();
return 0;
}
cautarestop
|
