Analiza Algoritmilor Genetici

I. Analiza algoritmilor genetici

1.1. Algoritmi evoluţionişti

Algoritmii evoluţionişti au la bază câteva principii ale evoluţiei: supravieţuirea celor mai buni şi modelează câteva fenomene naturale cum ar fi transmiterea informaţiei genetice şi combinarea acesteia între mai mulţi indivizi, constituie una din categoriile moderne de căutare a soluţiilor.

Aici sunt prezentate principalele paradigme ale algoritmilor evoluţionişti (algoritmi genetici, strategii evolutive, programare evolutivă şi programarea genetică). Algoritmi evoluţionişti au fost larg utilizaţi în ultima vreme în ştiinţă şi inginerie pentru rezolvarea unor probleme complexe.

În ultimele două decenii interesul în algoritmi bazaţi pe pricipiile evoluţiei a crescut. Un termen acceptat recent ca definitoriu pentru acest tip de tehnici este metoda evoluţiei computaţionale ( EC ). În această clasă pe lângă algoritmii genetici, strategiile evoluţive, programarea evolutivă şi programarea genetica sunt incluşi şi o mulţime de algoritmi şi sisteme hibride care împrumută tehnici şi operatori ale acestei paradigme şi ca urmare sunt greu de clasificat.

1.2. Evoluţia computaţională

În general orice metodă de rezolvare a unei probleme poate fi privită în ultima instanţă ca o căutare în mulţimea potenţialelor soluţii. Mai mult, această căutare urmăreste găsirea soluţiei optime în contextul problemei şi ca urmare căutarea poate fi văzută ca o problemă de optimizare. Pentru probleme ale căror soluţii se afla într-un spaţiu, mic metodele exhaustive clasice sunt mulţumitoare, dar pentru spaţii largi de cautare sunt necesare tehnici de inteligenţă artificiala. Printre acestea se afla şi metodele evoluţiei computaţionale şi care folosesc drept model câteva fenomene naturale: moştenirea genetică şi "Darwinian strife for survival". Cele mai bune metode de evoluţie computaţională sunt algoritmii genetici şi ca urmare de foarte multe ori termenii sunt utilizaţi interschimbaţi.Structura programelor bazate pe această tehnică este foarte asemănătoare. În continuare sunt prezentate în comparaţie structurile a trei algoritmi: "hillclimber", "simulated annealing" şi "evolutionary algorithm".

procedure iterated hillclimber

begin

t <- 0

repeat

local <- FALSE

selecteaza Vc aleator

evalueaza Vc

repeat

selecteaza N noi posibile solutii în vecinatatea lui Vc prin modificarea unui singur bit al lui Vc

selecteaza din aceste N valori Vn cu valoarea cea mai "buna" a lui f în conditiile problemei

if f ( Vc ) < f ( Vn ) then Vc <- Vn

else local <- TRUE

until local t <- t + 1

until t = MAX

end

Exista mai multe tipuri de "hillclimber", diferenţiate de metoda alegerii noii populaţii. Găsirea soluţiei într-un pas în acestă metodă depinde foarte mult de punctul de pornire. Se poate întampla ca algoritmul în cautarea să să ajungă într-un punct de optim local şi care este returnat ca soluţie a problemei, caz în care algoritmul esuează.

Structura algoritmului "simulated annealing" este urmatoarea:

procedure simulated annealing

begin

t <- 0

initializarea temperaturii T

selectarea unui element Vc aleator evalueaza Vc

repeat

repeat

selecteaza o noua solutie in vecinatatea lui Vc prin modificarea unui singur bit al lui Vc

if f ( Vc ) < f ( Vn ) then Vc <- Vn

else

if random [ 0, 1 ) < exp ( ( f ( Vn ) - f ( Vc ) ) / T ) then Vc <- Vn

until ( termination-condition )

T <- g ( T, t )

t <- t + 1

until ( stop-criterion )

end

"Termination-condition" verifică dacă "echilibrul termic" s-a stabilit, dar poate fi şi un simplu test dacă ciclul s-a executat de un număr k ori dorit. Cu ajutorul lui T se urmăreşte dacă în sistem mai au loc schimbări sau acesta a "înghetat", caz în care algoritmul se încheie. Algoritmul chiar dacă ajunge într-un maxim local poate avea şansa de a părăsi acest punct şi de a găsi maximul global datorită funcţiei random. Teoretic pare posibil, dar practic algoritmul poate esua în anumite situatii.

Structura unui algoritm evoluţionist este în mare următoarea:

procedure evolutionary algorithm

begin

t <- 0

initializare P ( t )

evaluare P ( t )

while ( not termination-condition ) do

t <- t + 1

selecteaza P ( t ) din P ( t - 1 )

efectuaza transformari aupra lui P ( t )

evalueaza P ( t )

end

end

Algoritmul evoluţionist mentine o populaţie de indivizi, P ( t ) = { xt1, , xtn }pentru iteraţia t. Fiecare individ reprezintă o potenţială soluţie şi fiecare xti este evaluat pentru a măsura capacitatea sa de generare a altor indivizi. O nouă populaţie este formată din unii indivizi selectaţi din pasul anterior. Dupa crearea noii populaţii o parte o să sufere o serie de transformări (mutaţii = modificarea unui singur bit ( m: S -> S ) sau încrucişări = formarea unui nou individ din doi sau mai mulţi părinţi ( c:S x x S -> S ). După un număr oarecare de iteraţii algoritmul converge către o soluţie optimă. Pe această schemă generală se pot implementa o gamă variată de algoritmi în care fiecare îmbină altfel diferitele date ale problemei. Ei pot îngloba sau nu anumite informaţii pentru controlul procesului de căutare a indivizilor. Sau poate fi schimbată ordinea în care au loc operaţiile:

selectează P ( t ) din P ( t - 1 )

efectuază transformări aupra lui P ( t )