1 Principii generale despre algoritmi genetici  si evolutivi 3 1.1 De nirea algoritmilor evolutivi . . . . . . . . . . . . . . . . [628795]

Cuprins
Introducere 1
1 Principii generale despre algoritmi genetici  si evolutivi 3
1.1 Denirea algoritmilor evolutivi . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Directii ale calculului evolutiv . . . . . . . . . . . . . . . . 5
1.2 Strucutura unui algoritm evolutiv . . . . . . . . . . . . . . . . . . 5
1.3 Algoritm general pentru o procedur a evolutiv a . . . . . . . . . . 6
2 Structura unui algoritm genetic 9
2.1 Denirea algoritmului genetic . . . . . . . . . . . . . . . . . . . . 9
2.2 Rezolvarea unor probleme cu ajutorul algoritmilor genetici . . . . 9
2.3 Structura algoritmului genetic . . . . . . . . . . . . . . . . . . . . 9
2.4 Scheme constructive a unui algoritm genetic . . . . . . . . . . . . 9
2.5 Caracteristicile unui algoritm genetic . . . . . . . . . . . . . . . . 9
3 Aplicat ii 11
3.1 Sect iunea 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.1 Subsect iunea 3.1.1 . . . . . . . . . . . . . . . . . . . . . . 11
Bibliograe 12
1

Introducere
^In acest a lucrare …..
1

Introducere 2

Capitolul 1
Principii generale despre
algoritmi genetici  si evolutivi
1.1 Denirea algoritmilor evolutivi
^Incep^ and cu anii '70 s-a manifestat un interes pentru algoritmii care se bazeaz a
pe un principiu evolutiv. Un termen comun adoptat care s a se refere la tehnicile
folosite este acela de metode de calcul evolutiv.
Calculul evolutiv reprezint a un domeniu de cercetare al informaticii, ^ n care
sunt implicate calcule,^ ns a domeniul este inspirat din evolut ia speciilor ^ n natur a.
Ca surs a de inspitat ie, au folosit teoria evolut iei a speciilor biologice(teoria
darwinist a). Evolut ia defapt reprezint a modicarea caracterelor mo stenite ale
populat iei unei specii de la o generat ie la alta.. Aceste schimb ari sunt determinate
de combinarea a trei procese principale: select ia, reproducere  si variat ie. [17]
Aceste tr as aturi variaz a^ n cadrul populat iei, ale c aror indivizi prezint a variat ii
genetice. Urma sii pot avea tr as aturi noi sau modicate( datorit a mutat iilor ge-
netice).
Principalul mecanism care dirijeaz a evolut ia este select ia natural a, procesul
care face ca acele caractere ereditare care sunt mai ecace pentru supraviet uire
 si reproducere s a devin a mai r asp^ andite ^ n cadrul acelei populat ii, cu scopul de a
se putea adapta solicit arii mediului. Pentru ca aceste tr as aturi s a se transmit a la
urma si, care la r^ andul lor s a se reproduc a, probabilitatea joac a un rol important.
Algoritmii care apar^ n acest domeniu se numesc algoritmi evolutivi, ce reprezint a
mai multe clase de metode aleatoare de c autare. Orice algoritm evolutiv folose ste
o populat ie de indivizi (reprezentat i prin cromozomi), care e modicat a cu aju-
torul unor operatori genetici, cum ar : select ia, recombinarea  si mutat ia. Fiec arui
individ al populat iei ^ i este asociat a o m asur a a adapt arii sale la mediu. Select ia
favorizeaz a indivizii care au o adaptare ^ nalt a la mediu  si se face ^ n doi pa si:
select ia p arint ilor  si supraviet uirea. Select ia p arint ilor decide ce indivizi vor
p arint ii noii generat ii  si c^ at i urma si va avea ecare pereche de p arint i. Urma sii
sunt creat i prin recombinarea informat iei genetice a p arint ilor  si mut atie (care va
3

1.1. Denirea algoritmilor evolutivi 4
perturba materialul genetic al descendentului). Descendent ii vor  evaluat i, iar
pragul de supraviet uire (select ia natural a) decide ce indivizi din noua populat ie
(p arint i  si copii) vor forma noua generat ie. Mai bine spus vor supraviet ui cei mai
puternici.[4]
Metafora fundamental a a calculului evolutiv leag a evolut ia natural a de un
anumit tip de rezolvare de probleme: ^ ncercare  si eroare. Analogia ^ ntre contextul
rezolv arii de probleme de tip ^ ncercare  si eroare  si evolut ia natural a se face astfel:
1. Mediul ^ n care se a
 a indivizii se identic a cu problema de rezolvat.
2. Indivizii sunt potent iale solut ii ale problemei.
3. M asura de performant  a (sau adaptare) va contoriza ^ n acest caz c^ at de bun a
este solut ia g asit a ^ n rezolvarea problemei.
Solut iile problemei sunt generate init ial, iar cele care sunt mai bune calitativ
au cele mai mari  sanse s a e p astrate  si s a participe la procesul de recombinare.
Performant a in
uent eaz a  sansele de reproducere  si supraviet uire, iar calitatea
in
uent eaz a  sansele de a forma noi solut ii.[17]
EVOLUT  IE REZOLVAREA PROBLEMEI
Mediu() Problem a
Indivizi () Solut ii candidat
Preformant a indivizilor () Calitatea indivizilor
Algoritmii genetici ^ mprumut a urm atoarele caracteristici din principiile geneticii
[4]:
1. Cromozomii sunt purtatorii informat iei genetice.
2. Fiecare individ al unei specii posed a un num ar determinat de cromozomi.
Totalitatea cromozomilor unui individ reprezint a genotipul s au.
3. Cromozomii sunt sructuri liniare alc atuite din gene. Genele poart a carac-
teristicile ereditare  si le poate controla. Genele unei anumite caracteristici
ocup a locuri bine determinate ^ n cromozom, numite loci. O gen a poate
^ n mai multe st ari, ce reprezint a caracteristicile dominante sau recesive ale
genelor, numite alele.
4. Evolut ia este un proces ce opereaz a la nivelul cromozomilor.
5. Select ia natural a reprezint a leg atura dintre cromozomi  si performant ele in-
divizilor. Procesul select iei naturale favorizeaz a reproducerea acelor cromo-
zomi ce codic a structuri de succes.
6. Evolut ia se realizeaz a ^ n procesul reproducerii, unde act ioneaz a  si procese
de select ie, recombinare  si mutat ie a materialului genetic al p arint ilor.

1.2. Strucutura unui algoritm evolutiv 5
1.1.1 Directii ale calculului evolutiv
1. Programarea evolutiv a (L.Fogel, D.Fogel, 1960-1970) Codicare: real a/ di-
agrame de st ari
Mutat ia: operator principal
^Incruci sarea: operator secundar
Aplicat ii: optimizare continu a
2. Strategii evolutive ()Rechenberg, Schwefel, 1965) Codicare: real a
Mutat ia: operator principal
^Incruci sarea: operator secundar
Aplicat ii: optimizare ^ n domeniu continuu
3. Algoritmi genetici (Holland, 1962-1967) Codicare: binar a
^Incruci sarea: operator principal
Mutat ia: operator secundar
Aplicat ii: optimizare combinatorial a
4. Progrramare genetic a(Koza, 1990) Codicare: structuri arborescente
^Incruci sarea: operator principal
Mutat ia: operator secundar
Aplicat ii: proiectare modele de calcul
1.2 Strucutura unui algoritm evolutiv
Algoritmii evolutivi reprezint a mai multe clase de metode aleatoare de c autare.
Fiecare individ al populat iei implicate ^ n procesul de c autare se descrie printr-un
cromozom.
Orice algoritm evolutiv cont ine elemente distincte P(t) =fa1(t); a2(t);


; an(t)g
ce reprezint a populat ia de cromozomi. Algoritmii evolutivi ment in aceast a populat ie
de indivizi la care moment t.
O populat ie poate  privit a ca ind un vector de valori, iar ecare element
distinct reprezint a o solut ie posibil a a problemei. Un individ este numit uneori  si
cromozom. Un cromozom este un  sir format din elemente din vocabular. Evalu-
area calit at ii indivizilor se face cu ajutorul unei funct ii de adecvare (evaluare sau
adaptare), denit a ca: f:A!R, unde Aeste spat iul de c autare al solut iilor. De
obicei, cu c^ at cromozomul este mai promit ator, cu at^ at funct ia lui de adaptare
este mai mare. Exist a  si probleme ^ n cazul c arora funct ia de adaptare trebuie s a
e minimizat a (problema reginelor).

1.3. Algoritm general pentru o procedur a evolutiv a 6
P(t) =fa1(t); a2(t);


; an(t)greprezint a generat ia selectat a la momentul t.
O nou a generat ie se formeaz a la iterat ia t+1 prin selectarea celor mai promit  atori
indivizi (ale si la pasul de select ie) din populat ia P(t). O parte din membrii
populat iei nou formate sufer a transform ari (efectuate la pasul de modicare),
aplic^ and asupra lor opeatori genetici de recombinare  si mutat ie.
Operatorii genetici sunt proceduri care opereaz a asupra elementelor vectorului
populat ie. Operatorul de recombinare se dene ste ca o aplicat ie: r:Ap!Ad si
realizeaz a o transformare ^ n care pp arint i dau na stere la dcopii. Operatorul este
folosit pentru a crea noi indivizi folosind segmente a doi sau mai mult i cromozomi.
Operatorul de mutat ie reprezint a aplicat ia unar a (dimensiunea 1) m:A!A.
Aceasta creaz a noi descendent i prin schimbarea unei singure gene a unui individ
ales  si realizeaz a mici modic ari ale cromozomilor obt inut i prin recombinare.
Operatorul de supraviet uire decide care dintre cromozomii, mai bine spus,
p arint ii  si descendent ii lor obt inut i prin ^ ncruci sare  si mutat ie vor forma noua
generat ie. Populat ia init ial a se alege de obicei prin selectarea ^ nt^ ampl atoare a
unor indivizi din spat iul de c autare.
Criteriul de oprire pentru un algoritm evolutiv este dat de num arul de generat ii.
Cel mai performant individ din ultima generat ie reprezint a solut ia problemei.[17]
[4] [18]
1.3 Algoritm general pentru o procedur a evo-
lutiv a
1. Init ializeaz a momentul t= 0  si populat ia de indivizi generat i aleator P(t)
2. Se evalueaz a populat ia de indivizi P(t) folosind funct ia de adaptare f.
3. C^ at timp (condit ia de terminare nu e satisf acut a) execut a
(a)t=t+ 1
(b) Se selecteaz a p arint ii din P(t).
(c) Se recombin a perechi de p arint i din P(t)
(d) Se aplic a mutat ia asupra descendent ilor obt inut i dup a recombinare
(e) Se evalueaz a ecare descendent din P(t)
(f) Se selecteaz a indivizii care vor supraviet ui  si vor forma urm atoarea
generat ie.
[4]
OBS!: Condit ia de terminare a algoritmului se refer a la atingerea num arului
de generat ii ce trebuie parcurs.

1.3. Algoritm general pentru o procedur a evolutiv a 7
Orice algoritm evolutiv trebuie s a furnizeze urm atoarele elemente:
1. O reprezentare genetic a a spat iului solut iilor potent iale ale problemei.
2. O populat ie init ial a de solut ii potent iale, care se alege ^ n mod arbitrar.
3. O funct ie de adecvare fce m asoar a performant a ec arui individ ^ n raport
cu scopul urm arit.
4. O metod a de selectare a cromozomilor pentru modicare  si reproducere a
lor.
5. Operatori genetici pentru crearea de noi cromozomi prin recombinare  si
mutat ie.
6. Valorile parametrilor ce apar ^ n algoritmul evolutiv, cum ar :
– dimensiunea populat iei
– probabilitatea de aplicare a operatorilor genetici
– num arul total de generat ii
Un algoritm evolutiv cuprinde urm atoarele componente:
1.Reprezentarea
– solut iile candidat ale problemei de rezolvat trebuie reprezentate (cod-
icate) sub form a de indivizi (cromozomi).
– orice element din spat iul solut iilor trebuie s a aib a corespondent ^ n
spat iul cromozomilor  si invers.
– pentru ecare problem a trebuie aleas a o reprezentare c^ at mai potrivit a.
2.Populat ia
– cont ine o metod a pentru init ializarea unei mult imi de indivizi ce nu
sunt neap arat tot i diferit i ^ ntre ei.
– operatorii de select ie iau^ n considerare^ ntreaga populat ie de la generat ia
curent a.
– populat ia este cea care evolueaz a de-a lungul generat iei, nu indivizii
^ n particular.
3.Select ia p arint ilor
– metoda de select ie apare de dou a ori ^ n cursul unei parcurgeri a buclei
c^ at timp a algoritmului evolutiv
a) Select ia pentru reproducere: sunt ale si p arint ii generat iei urm atoare.

1.3. Algoritm general pentru o procedur a evolutiv a 8
b) Select ia pentru ^ nlocuire: sau select ia pentru supraviet uire, c^ and
indivizii care vor forma populat ia din urm atoarea generat ie sunt
ale si dintre copii  si p arint i.
4.Evaluarea
– cont ine funct ia de performant  a (adaptare) ce m asoar a adaptarea indi-
vizilor la mediu.
– funct ia de evaluare (adaptare) atribuie ec arui cromozom o valoare
real a care reprezint a c^ at de bun este cromozomul respectiv.
5.Operatori variat ionali
– ace stia reprezint a recombinarea  si mutat ia, ce cont ine metode pentru
a crea noi cromozomi, ^ n care sunt specicat i parametrii operatorilor
genetici.
Ex: probabilitatea de mutat ie, de incruci sare, etc.
6.Init ializarea  si condit ia de terminare
– de obicei init ializarea se face ^ n mod aleator
– condit ia de terminare se veric a la ecare generat ie  si poate reprezenta:
a) atingerea unei performant e
b) atingerea unui anumit num ar de generat ii cu sau f ar a s a se
c^ a stigat performant a.

Capitolul 2
Structura unui algoritm genetic
2.1 Denirea algoritmului genetic
2.2 Rezolvarea unor probleme cu ajutorul algo-
ritmilor genetici
2.3 Structura algoritmului genetic
2.4 Scheme constructive a unui algoritm genetic
2.5 Caracteristicile unui algoritm genetic
Urmatoarele caracteristici prezint a anumite particularit at i ale acestora compara-
tiv cu alte metode de c autare  si optimizare. Acestea sunt:
1. Algoritmii genetici sunt o clas a de algoritmi probabili sti care combin a ele-
mente de c autare dirijat a  si c autare aleatoare.
2. Algoritmii genetici sunt mai robu sti dec^ at alte metode de c autare dirijat a
 si dec^ at algoritmii clasici de optimizare.
3. Modelele de c autare bazate pe algoritmi genetici sunt caracterizate de fap-
tul c a ele ment in o populat ie de solut ii potent iale. Metodele clasice de
c autare act ioneaz a la un moment dat asupra unui singur punct din spat iul
de c autare.
4. Algoritmii genetici folosesc funct ii de performant  a obt inute prin transform ari
simple ale funct iei obiectiv. Nu e necesar ca funct ia obiectiv s a e derivabil a
 si nici s a aibe propriet at i speciale de convexitate.
5. Algoritmii genetici sunt simplu de folosit.
9

2.5. Caracteristicile unui algoritm genetic 10
6. Algoritmii genetici pot g asi solut ii optime (sau aproape optime) cu o mare
probabilitate.

Capitolul 3
Aplicat ii
3.1 Sect iunea 3.1
3.1.1 Subsect iunea 3.1.1
11

Bibliografie 12

Bibliograe
[1]J. E. Baker ,Adaptive Selection Methods for Genetic Algorithms ,
https://books.google.ro/books?hl=ro&lr=&id=lI17AgAAQBAJ&oi=
fnd&pg=PA101&dq=adaptive+selection+methods+for+genetic+
algorithms+baker+1985&ots=0KsX87Q40A&sig=ard5PKniSg2_
-F8zKDDDDywOoME&redir_esc=y#v=onepage&q=adaptive%20selection%
20methods%20for%20genetic%20algorithms%20baker%201985&f=false ,
1985, 101-111.
[2]George E. P. Box ,Evolutionary Operation: A Method for Increasing
Industrial Productivity ,https://www.jstor.org/stable/2985505?seq=1#
page_scan_tab_contents , Vol. 6, No. 2 (Jun., 1957), pp. 81-101.
[3]Cristian Constantinescu , Algoritmi genetici. In-
troducere , https://www.scribd.com/doc/251139787/
Cristian-Constantinescu-Algoritmi-Genetici-Introducere
[4]D. Dumitrescu ,Algoritmi genetici  si strategii evolutive – aplicat ii ^ n
Inteligent a Articial a  si ^ n domenii conexe , Editura Albastr a, 2006.
[5]L. J. Eshelman, R. A. Caruana, J. D. Schaer ,Biases in the crossover
landscape, in Proceedings of the Third International Conference on Genetic
ALgorithms ,https://www.researchgate.net/publication/220885629_
Biases_in_the_Crossover_Landscape , Morgan Kaufmann Publisers, 1989.
[6]A. S. Fraser ,Simulation of genetic systems bu automatic digital computers ,
http://www.publish.csiro.au/bi/pdf/BI9600150 , Australian Journal of
Biological Science, 1957.
[7]F. Glover, M. Laguna Tabu Search ,http://www.lsi.upc.es/ ~bejar/
aia/aia-web/laguna.pdf , Kluwer Academic Publishers, Boston, 1997.
[8]D. E. Goldberg Genetic Algorithms in Search, Optimization and Machine
Learning , http://www2.fiit.stuba.sk/ ~kvasnicka/Free%20books/
Goldberg_Genetic_Algorithms_in_Search.pdf , Addison Wesley Publish-
ing Company, 1989.
13

BIBLIOGRAFIE 14
[9]D. E. Goldberg, K. Deb, D. Theirens ,Toward a better understanding of
mixing in genetic algorithms ,https://www.jstage.jst.go.jp/article/
sicejl1962/32/1/32_1_10/_pdf , Journal of SICE, 32, 1991.
[10]M. D. Jose, G. E. Liepins ,Schema disruption ,https://www.
researchgate.net/publication/220885694_Schema_Disruption , Mor-
gan Kaufmann Publisers, 1991.
[11]S. A. Kaufman, S. Johnsen ,Co-evolution at the edge of
the chaos:coupled tness landscapes, poised states and co-evolutionary
avalanches, in Articial Life ,https://pdfs.semanticscholar.org/d70b/
cfcff0f881e98dc8af657a8cd31f349c1010.pdf , Addison Wesley, Redwood
City, 1991.
[12]Z. Michalawicz ,Genetic Algorithms + Data Structes = Evo-
lution Programs , http://web.ist.utl.pt/adriano.simoes/tese/
referencias/Michalewicz%20Z.%20Genetic%20Algorithms%20+
%20Data%20Structures%20=%20Evolution%20Programs%20(3ed).PDF ,
Springer Verlag, Berlin, 1992.
[13]J. Schaer, R. Caruana, L. Eshelman, R. Das ,A study of control pa-
rameters aecting online performance of genetic algorithms for function op-
timization , in Proceedings of the Third International Conference on Genetic
Algorithms, https://www.researchgate.net/publication/220885653_
A_Study_of_Control_Parameters_Affecting_Online_Performance_of_
Genetic_Algorithms_for_Function_Optimization , Morgan Kauman
Publisers, 1989, 51-60.
[14]W. M. Spears, De Jong ,On the Virtues of Parameterized Uniform
Crossover ,http://www.mli.gmu.edu/papers/91-95/91-18.pdf , Morgan
Kauman Publisers, 1991, 230-236.
[15]J. D. Schaer, A. Morishima ,An adapptive crossover dis-
tibution mechanism for genetic algorithms, in Proceedings of the
Second International Conference on Genetic Algorithms ,https:
//www.researchgate.net/publication/201976386_An_Adaptive_
Crossover_Distribution_Mechanism_for_Genetic_Algorithms ,
Lawrence Erlbaum Associates, Hillsdale, NY, 1987.
[16]Victor Neagoe ,http://www.victorneagoe.com/university/prai/
lab5a.pdf
[17]Constantin Stoean ,inf.ucv.ro/documents/cstoean/c6/A_14.pdf
[18]Algoritm genetici: cursuri ,andrei.clubcisco.ro/cursuri/5master/
sptrm/curs/Algoritmi%20genetici.pdf