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

Cuprins
Introducere 1
1 Principii generale despre algoritmi genetici  si evolutivi 3
1.1 Denirea algoritmilor evolutivi . . . . . . . . . . . . . . . . . . . . 3
1.2 Strucutura unui algoritm evolutiv . . . . . . . . . . . . . . . . . . 5
1.3 Algoritm 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Structura algoritmului genetic . . . . . . . . . . . . . . . . . . . . 11
2.4 Scheme constructive a unui algoritm genetic . . . . . . . . . . . . 12
2.5 Caracteristicile unui algoritm genetic . . . . . . . . . . . . . . . . 12
3 Operatori genetici 15
3.1 Select ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Select ia proport ional a . . . . . . . . . . . . . . . . . . . . 15
3.1.2 Select ia bazat a pe ordonare . . . . . . . . . . . . . . . . . 18
3.1.3 Select ia nestandard . . . . . . . . . . . . . . . . . . . . . . 20
3.2 ^Incruci sarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Considerat ii privind ^ ncruci sarea . . . . . . . . . . . . . . . 21
3.2.2 ^Incruci sarea cu puncte de t aietur a . . . . . . . . . . . . . . 21
3.2.2.1 ^Incrucisarea cu un punct de t aietur a . . . . . . . 21
3.2.2.2 ^Incrucisarea cu dou a puncte de t aietur a . . . . . 21
3.2.2.3 ^Incrucisarea cu dou a puncte de t aietur a . . . . . 22
3.2.3 Algoritmi de ^ ncruci sare . . . . . . . . . . . . . . . . . . . 22
3.2.3.1 Algoritm pentru^ ncrucisarea cu un punct de t aietur a 22
3.2.3.2 Algoritm pentru ^ ncrucisarea cu dou a puncte de
t aietur a . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.3.3 Algoritm pentru^ ncrucisarea cu mai multe puncte
de t aietur a . . . . . . . . . . . . . . . . . . . . . 23
4 Aplicatii 25
1

Cuprins 2
Bibliograe 26

Introducere
^In acest a lucrare …..c
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 de fapt 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 ([7]).
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 repre-
zint 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 ajutorul 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.([3])
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.
Metafora evolutiv a prezentat a mai sus poate  descris a  si cu ajutorul urm atoarei
scheme:
EVOLUT  IE REZOLVAREA PROBLEMEI
Mediu() Problem a
Indivizi () Solut ii candidat
Preformant a indivizilor () Calitatea indivizilor
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 ([7]).
Algoritmii genetici ^ mprumut a urm atoarele caracteristici din principiile ge-
neticii ([3]):
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 structuri 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.

1.2. Strucutura unui algoritm evolutiv 5
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.
Principalele direct ii ale calculului evolutiv sunt:
Programarea evolutiv a (L.Fogel, D.Fogel, 1960-1970)
Codicare: real a/ diagrame de st ari
Mutat ia: operator principal
^Incruci sarea: operator secundar
Aplicat ii: optimizare continu a
Strategii evolutive (Rechenberg, Schwefel, 1965)
Codicare: real a
Mutat ia: operator principal
^Incruci sarea: operator secundar
Aplicat ii: optimizare ^ n domeniu continuu
Algoritmi genetici (Holland, 1962-1967)
Codicare: binar a
^Incruci sarea: operator principal
Mutat ia: operator secundar
Aplicat ii: optimizare combinatorial a
Programare 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);


;an(t)gce
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

1.3. Algoritm pentru o procedur a evolutiv a 6
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, undeAeste 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).
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 ([7],
[3], [8]).
1.3 Algoritm pentru o procedur a evolutiv 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.

1.3. Algoritm pentru o procedur a evolutiv a 7
([3])
Observat ie: Condit ia de terminare a algoritmului se refer a la atingerea
num arului de generat ii ce trebuie parcurs.
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

1.3. Algoritm pentru o procedur a evolutiv a 8
– 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.
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
Algoritmii genetici fac parte dintr-o clas a a algoritmilor evolutivi si sunt tehnici
adaptive de c autare (care serve ste la ^ nv at area/descoperirea de lucruri noi….vad
cum ma voi exprima aici) ce se bazeaz a pe principiile genetice, care realizeaz a un
compromis ^ ntre explorarea  si exploatarea spat iilor solut iilor. Ace stia au ^ nceput
s a e recunoscut i ca tehnici de optimizare datorit a lucrarii lui John Holland
(Holland, 1975, [12]).
^Intr-un algoritm genetic,ecare element al spat iului de c autare se reprezint a
ca un cromozom al unei populat ii, ce e format dintr-o mult ime de elemente numite
gene. Fiecare gen a se poate a
a ^ n mai multe st ari, numite alele, ce indic a valorile
genelor.
FieA= alfabetul ce corespunde valorilor alelelor. Un cromozom cont ine
`elemente ce arat a lungimea acestuia, iar elementele fac parte din mult imea
A. Rezult a c a orice cromozom este un element din A`. Cea mai r asp^ ndit a
reprezentare a cromozomilor este codicarea binar a a valorilor genelor.Deci alfa-
betulAare ^ n component  a valorile 0 si1.
Comportamentul algoritmului genetic ^ n rezolvarea problemelor de opti-
mizare este str^ ans legat a de conceptul de explorare  si exploatare a spat iului
de c autare. Explorarea spat iului de c autare se refer a la gradul de parcurg-
ere(acoperire) a spat iilor solut iilor posibile, din care se ia solut ia optim a, pe c^ and
explatarea spat iului de c autare intensic a c autarea ^ n zonele ^ n care de dovedesc
promit  atoare (in care sunt  sanse mai mari ca solutia s a se g aseasc a). Cele dou a
concepte corespund c aut arii locale (explorarea) si c aut arii globale(exploatarea).
Dac a explorarea are un grad ridicat, acesta reduce gradul de exploatare a
zonelor de interes mare (promit  atoare), deci va reduce capacitatea algoritmu-
lui de a converge(tinde) ^ nspre puncte optime. Reciproc, exploatarea accen-
tuat a a zonelor de interes reduce capacitatea de exporare ecient a a spat iilor
solut iilor posibile, respectiv capacitatea algoritmului de a descoperi  si alte zone
promit  atoare.
9

2.2. Rezolvarea unor probleme cu ajutorulalgoritmilor genetici 10
O alt a interpretare a echilibrului explorare-exploatare poate  furnizat a prin
prisma a dou a concepte specice problematicii algoritmilor evolutivi, respectiv
convergent a  si diversitatea populat iei. Dac a explorarea ecient a a spat iului de
c autare este tradus a printr-un grad ridicat al diversit at ii populat iei, exploatarea
intens a a teritoriilor privilegiate ale spat iului de c autare este tradus a prin convergent a
populat iei ^ nspre solut iile optime.
Deci obt inerea unui echilibru ^ ntre explorare  si exploatare este indicat a pen-
tru ca metoda de optimizare s a e foarte bun a, iar parametrizarea algoritmu-
lui genetic permite persoanei (factorului uman) s a ajusteze echilibrul explorare-
exploatare pe o problem concret.
2.2 Rezolvarea unor probleme cu ajutorul
algoritmilor genetici
Paleta de aplicat ii ale algoritmilor genetici este nelimitat a. Conceput i ca instru-
mente de optimizare, algoritmii genetici sunt aplicabili  si ^ n probleme de alt gen,
prin reformularea problemelor respective ca probleme de c autare a solut iilor op-
time ^ n spat iul de c autare. Identicarea corect a a obiectivelor problemei date, de-
limitarea spat iului solut iilor posibile, determinarea unei maniere de reprezentare
a solut iilor, construirea unei funct ii de evaluare corespunztoare  si alegerea in-
spirat a a operatorilor de variat ie, sunt c^ ateva dintre ingredientele care asigur a
aplicabilitatea algoritmilor genetici. ([ ?])
Cele mai reprezentative probleme cu aplicat ii ^ n viat a real a pentru care algo-
ritmii genetici s-au dovedit ecient i :
– probleme de combinatoric a;
– optimiz ari ^ n proiectarea compozit iei materialelor  si a formei aerodinamice
a vehiculelor (auto, aeriene, navale, trenuri);
– optimiz ari ^ n proiectarea structural a  si funct ional a a cl adirilor (locuint e,
fabrici, etc)
– proiectarea  si optimizarea ret elelor neuronale;
– proiectarea automat a a sistemelor;
– planicarea sarcinilor;
– probleme din domeniul telecomunicat iilor;
– optimiz ari ^ n robotic a;
– problema comis-voiajorului;
– optimiz ari ^ n proiectarea circuitelor digitale;

2.3. Structura algoritmului genetic 11
2.3 Structura algoritmului genetic
T  in^ and cont de structura unui algoritm evolutiv ment ionat mai sus, se poate
descrie structura unui algoritm genetic, av^ and !in vedere urmatoarele aspecte :
1. cromozomii utilizat i au lungime constant a;
2. populat ia (generat ia) P(t+ 1) de la momentul t+ 1 se obtine ret in^ and tot i
descendent ii populat iei P(t), nu neap arat distinct i  si sterg^ and ulterior cromozomii
generat iei anterioare P(t);
3. num arul cromozomilor este constant;
4. Algoritmii genetici mentin o populat ie P(t) de indivizi la ecare iterat ie t.
O populat ie poate  privit a ca ind un vector de valori. Fiecare individ (element
al vectorului) reprezint a solut ia potent ial a a problemei  si este implementat a sub
forma unei structuri S. Un individ este numit uneori  si cromozom.
Structura algoritmului genetic fundamental este ([3] [10]):
Pasul 1:t= 0;
Pasul 2: se initializeaz a aleator populat ia P(t);
Pasul 3: se evalueaz a cromozomii populat iei P(t); ^ n acest scop se utilizeaz a o funct ie
de adecvare ce depinde de problem a;
Pasul 4: c^ at timp( nu este ^ ndeplinit a condit ia de terminare ) se execut a :
a)se selecteaz a cromozomii din P(t) care vor contribui la formarea noii
generat ii; e Pimult imea cromozomilor selectati ( Pireprezint a o pop-
ulatie intermediar a);
b)Se utilizeaz a oprat ia de ^ ncruci sare ^ ntre perechi de p arint i din Pi
c)Se aplic a oprat ia de mutat ia asupra descendent ilor obt inut i dup a^ ncruci sare
d)Se selecteaz a indivizii care vor supraviet ui  si vor forma urm atoarea
generat ie.
e)FiePdpopulat ia alstfel obtinut a (descendent ii populat iei P(t)). Se
 sterg dinPiparint ii descendent ilor obtinut i. Cromozomii r ama si ^ n Pi
sunt inclu si ^ n populat ia Pd.
Se construie ste noua generat ie astfel P(t+ 1) =Pd.
Se  sterg tot i cromozomii din P(t).
t=t+ 1;
Se evalueaz a P(t).
Sfarsit c^ at timp() .
Observat ie: Condit ia de terminare se refer a, de regul a, la atingerea num arului de generat ii.

2.4. Scheme constructive a unui algoritm genetic 12
Observat ie: Dac a numarul maxim admis de generat ii este N, atunci condit ia de ter-
minare este t>N .
Observat ie: Rezultatul algoritmului este de regul a cel mai promit  ator individ din ultima
generat ie. Deoarece, ^ n realitate, nimic nu garanteaza faptul ca un individ
mai performant nu a fost obt inut intr-o generatie anterioar a, este normal ca
la ecare pas (la ecare generat ie t) s a retinem cel mai promit  ator element
care a fost generat p^ an a la momentul curent. Acest proces se numeste
elitism.
2.4 Scheme constructive a unui algoritm genetic
(Mai am de lucrat aici…de adaugat foarte multe
exemple si de continuat teoria…)
Teorema schemelor reprezint a unul dintre rezultatele teoretice importante
ale algoritmilor genetici. Recunoscut a ca teorem a fundamental a, aceasta garan-
teaz a convergent a algoritmilor genetici, prin dezvoltarea/^ nmult irea ^ n timp a
acelor cromozomi cont in^ and secvent e de gene cu performant e mari. Noiunea cen-
tral a teoremei o reprezint a schema, aceasta ind denit a astfel:
Schema = secvent  a de caractere peste alfabetul binar extins 0,1,*, de lungime L
(Lreprezint a chiar lungimea reprezent arii cromozomului).
Exemple de scheme de lungime L=8:
s1=100**01* , s2=***11*00, s3=111*000*.
Ordinul schemei s, notatO(s) se dene ste ca num aSrul de aparit ii ale caractere
binare 0 sau 1, respectiv, num arul de caractere diferite de simbolul genetic * din
compunerea schemei.
Exemplu:O(s1) = 5;O(s2) = 4;O(s1) = 6.
Lungime denitorie a schemei, notat a (s) se determin a ca ind distant a (num arul
de caractere) de la prima aparit ie, p^ an a la ultima aparit ie a unui caracter binar
0 sau 1.
Exemplu:(s1) = 7;(s2) = 5;(s3) = 7:
Performant a unei scheme, notat a f(s) este media performant elor cromozomilor
populat iei curente care cont in schema s.
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.5. Caracteristicile unui algoritm genetic 13
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.
6. Algoritmii genetici pot g asi solut ii optime (sau aproape optime) cu o mare
probabilitate.

2.5. Caracteristicile unui algoritm genetic 14

Capitolul 3
Operatori genetici
Operatorii genetici joac a un rol important ^ n modelarea algoritmilor genetici.
Exist a 3 tipuri de operatori: operatori de select ie, operatori de ^ ncruci sare  si
operatori de mutat ie.
3.1 Select ia
Operatorul de select ie este cel mai important operator genetic deoarece alege
ce indivizi din populat ie supraviet uiesc, se reproduc sau mor. Pentru a realiza
select ia este necesar a folosirea (introducerea) funct iei de adecvare asupra indi-
vizilor.
Rolul select iei ^ n cadrul unui algoritm genetic este acela de a decide care dintre
indivizii unei populat ii vor putea participa la formarea populat iei urm atoare.
Scopul select iei este de a asigura mai multe  sanse de reproducere celor mai
performant i indivizi din populat ia dat a. Prin select ie se urm are ste maximizarea
performant ei indivizilor. C autarea se concentreaz a ^ n spat iul solut iilor, ^ n acest
fel realiz^ andu-se exploatarea celor mai bune solut ii g asite.
3.1.1 Select ia proport ional a
Select ia proport ional a este una dintre cele mai populare tehnici de select ie. ^In
cazul select iei proport ionale, probabilitatea de select iea unui individ depinde de
valoarea funct iei de adecvare (evaluare, performat a) a acestuia.
Funct ia de adecvare
FieP(t) =fc1;c2;:::;c ng, ce reprezint a mult imea cromozomilor din generat ia
curent at.
FieF=ff1;f2;:::;f ngmult imea valorilor de performant  a a cromozomilor.
Not am cufit:P(t)!F, funct ia de evaluare a performant elor cromozomilor.
15

3.1. Select ia 16
Aceast a funct ie re
ect a calitatea cromozomilor.
Funct ia de evaluare (adecvare) fittrebuie s a^ ndeplineasc a urm atoarele cerint e([ ?]):
funct iafittrebuie s a e pozitiv a: fit(c)>0;8c2P(t):
dac afitare  si valori negative, atunci se efectueaz a o scalare prin care
valorile lui fittrec (se deplaseaz a) ^ n domeniul pozitiv.
Fiec arui cromozom i se asociaz a prin funct ia de evaluare o valoare de performant  a
fi=fit(ci);pentru8i=f1;2;:::ng:
Performat a total a a generat iei curente Fit(t) e denit a ca suma performat elor
individuale
Fit(t) =nX
i=1fi=nX
i=1fit(ci):
Probabilitatea de select ie
Denit ie 3.1.1 Probabilitatea de select ie a individului ci2P(t)este dat a de
raportul dintre performat a sa  si performant a total a a populat iei curente([9]):
pi=fi
Fit(t)=fi
nP
i=1fi=fit(ci)
nP
i=1fit(ci)
O varinat a a procedurii de select ie proport ional a este aceea ^ n care sunt ex-
trase elementele populat iei de nori,nind dimensiunea populat iei, form^ and o
populat ie intermendiar a.
Populat ia intermediar a este format a din copii ale indivizilor generat iei P(t).
Asfel vom avea dou a situat ii: unii indivizi vor  reperzentat i de mai multe ori ^ n
populat ia intermediar a  si alt ii ce nu vor  select ionat i deloc.
Cunosc^ and dimensiunea populat iei n si probabilitatea de select ie ale indi-
vizilor, se poate determina num2arul mediu de copii (clone) ale ec arui individ.
Denit ie 3.1.2 Valoarea medie de select ie a individului ci2P(t)este dat a de
relat iani=n:pi, respectiv:
ni=n
fi
nP
i=1fi=n
fit(ci)
nP
i=1fit(ci)=fit(ci)
fitmediu(ci);
undefitmediu(ci)este performat a medie a populat iei.([9])

3.1. Select ia 17
Algoritmul Monte Carlo
Algoritmul select iei proport ionate e inspirat de algoritmul Monte Carlo, cunos-
cut ca  si algoritmul ruletei.
Ruleta este reprezentat a de un disc ^ np art it ^ n nsectoare, unde ecare sec-
tor corescpunde unui cromozom. La o utilizare a ruletei se selecteaz a individul
corespunz ator sectorului indicat. Probabilitatea de a indica un sector oarecare
e direct proportional a cu dimensiunea (lungimea) sectorului respectiv. Rotirea
denori a ruletei conduce la formarea populat iei intermediare de indivizi, notat a
Pinterm , asupra c arora se vor aplica ulterior ^ ncruci sarea  si mutat ia.
Algoritmul Monte Carlo de select ie este urm atorul ([3]):
^Inceput algoritm
Date de intrere: n
Pentruide la 1 lan
pentru ecare cromozom se calculeaza urm atorul num ar:
qi=nX
k=1pk;i= 1;2;:::;n
Sf^ ar sit pentru
Pentruide la 1 lan
Se genereaz a aleator g2[0;1]
Regula de select ie:
Dac a 0<g<q 1)se selecteaz a primul cromozom c1
Dac aqi1<g<q i)se selecteaz a cromozomul ci
Sf^ ar sit pentru
Sf^ ar sit algoritm
Avantaje  si dezavantaje ale select iei proport ionale
Avantajul utiliz arii select iei proport ionale ^ ntr-un algoritm genetic este capac-
itatea acestei a de a favoriza exploatarea indivizilor performant i ai populat iei.
Dezavantajul select iei poate  ^ nt^ alnit ^ n 2 situat ii([3],[9]):
Situat ia 1: populat ia cont ine un num ar mic de indivizi cu performant e mult
mai mari dec^ at performant ele celorlalt i.
^In acest caz ruleta arat a astfel:
FIGURA
^In acest caz, probabilitatea extragerii indivizilor de performant  a superioar a
este mare, deci num arul de copii ale acestuia ^ n populat ia intermediar a este de
asemenea mare.

3.1. Select ia 18
Consecint a acestui fenomen este convergent a rapid a a populat iei ^ nspre zona
reprezentat a de individul performant.
Dac a acest individ corespunde unei solut ii optime locale  si nu optime globale
se produce fenomenul nedorit (de evitat) de convergent  a prematur a.
Situat a 2: populat ia este relativ omogen a; performant ele indivizilor sunt apropi-
ate.
^In acest caz ruleta arat a astfel:
FIGURA
^In situat ia aceasta, operatorul de select ie nu reu seste s a fac a o distinct ie clar a
^ ntre indivizii performant i  si cei slabi. Probabilit at ile de select ie ale indivizilor
au valori apropiate, ceea ce conduce la o convergent  a ^ nceat a a populat iei ^ nspre
optimele problemei.
Dep a sirea impedimentelor nt^ alnite ^ n situat iile prezentate anterior, se poate
face prin tehnici de scalare a funct iei de performant  a. Prin modicarea valorilor
funct iei de performant  a se urm are ste ca populat ia curent a s nu cont in a indivizi
mult mai calicat i dec^ at restul, respectiv, gradul de diversitate a performant elor
populat iei s a e sucient de ridicat pentru a favoriza c autarea^ n zonele promit  atoare.
Literatura de specialitate ofer a diferite variante de scalare a funct iei de per for
man t  a (tness). Scalarea poate  static a sau dinamic a (^ n funct ie de independent a,
respectiv, dependent a de num arul generat iei).
Prezent am ^ n continuare c^ ateva dintre metodele de scalare utilizate ^ n mod
frecvent([9]):
1.Scalarea liniar a
Asupra funct iei de performant  a se aplic a legea: S(y=a
y+b, undea sib
sunt parametri prestabilit i. Astfel,funct ia transformat a de performant  a devine:
fittransformta (c) =a
fit(c) +b
2.Scalarea prin ridicare la putere
Legea de transformare este formulat a astfel: S(y) =yn, undenreprezint a
un parametru ^ ntreg supraunitar.
Funct ia transformat a de performant  a devine:
fittransformat (c) =fit(c)n
3.1.2 Select ia bazat a pe ordonare
Principiul select iei prin ordonare const a^ n atribuirea ec arui individ al populat iei
a unei valori reprezent^ and rangul acestuia, ^ n concordant  a cu valoarea funct iei
tness  si stabilirea unei probabilit at i de select ie dependent a de rangul atribuit.
Practic, populat ia va  supus a unei proceduri de ordonare descresc atoare dup
valorile de performant  a,  si pozit ia ocupat a de indivizi ^ n mult imea ordonat a este
cea care determin a probabilitatea de select ie. Aceast a strategie de select ie se mai
nume ste si select ie prin etichetare .([9])

3.1. Select ia 19
Se consider a populat ia Pformat a dintr-un num ar de ncromozomi. Fiecare
individcial populat iei va  etichetat printr-un rang rideterminat de pozit ia
ocupat a ^ n populat ia ordonat a descresc ator dup a valorile de performant  a.
Valorile etichetelor risunt numere naturale din mult imea 1 ;2;:::;n . Astfel cel
mai performant individ al populat iei va primi rangul n, iar cel mai slab individ
este etichetat cu valoarea 1.
Spre deosebire de procedura de select ie proport ional a, nu performant a, ci val-
oarea etichetei riva in
uent a probabilitatea de select ie a individului ci. Aceast a
diferent  a va induce un avantaj major ale select iei prin ordonare fat  a de select ia
proport ional a cu tness-ul.
Scenariile defectuoase ale select iei proport ionale:
populat ia relativ omogen a
diferent ele mari ^ ntre performant ele indivizilor
Aceste scenarii nu vor mai  un impediment ^ n cazul select iei prin ordonare.
Ordonarea produce o scalare uniform a ^ n cadrul populat iei, fapt pentru care
situat iile de stagnare a c aut arii sau convergent a prematur a ^ ntlnite la select ia
proport ional a sunt dep a site. Dependent a probabilit at ii de select ie poate  liniar a
sau neliniar a ^ n funct ie de rangul individului.
Dependent a liniar a a probabilit a2tii de select ie pia cromozomului cipoate
formulat a astfel:
pi=1
n
g2(ri1)(g1)
(n1)
[3]
unde: greprezint a num arul mediu de descendent i a steptat i ai celui mai perfor-
mant individ.
Probabilitatea de selectare a celui mai performant individ din populat ie, etichetat
cu rangulneste dat a de valoarea:
pbun=g
n
Probabilitatea de select ie a celui mai slab individ este dat a de:
pslab=2g
n
Num arul mediu de select ii ale celui mai bun individ se poate deduce astfel:
nbun=n
pbun; bfadicn bun=g
Presiunea de select ie exprimat a ca num arul mediu de descendent i ai celui mai per-
formant individ este o constant a a procedurii de select ie  si in
uent eaz a ^ n mod
direct echilibrul dintre c autarea global a  si exploatarea zonelor promit  atoare. Ast-
fel, o presiune de select ie mare va produce o exploatare accentuat a a vecin at at ii
celui mai performant individ  si o sc adere a diversit at ii globale a populat iei([3]).

3.1. Select ia 20
Presiunea mic a a select iei va avea ca efect ment inerea diversit at ii populat iei
 si favorizarea explor arii spat iului de c autare.
O variant a de etichetare neliniar a a populaiei genereaz a probabilit at i de select ie
formulate astfel:
pi=a
(1a)nri
unde: areprezint a un parametru subunitar al procedurii, av^ and semnicat ia
probabilit at ii de select ie a celui mai bun individ din populat ie.
3.1.3 Select ia nestandard
Acest tip de select ie a fost conceput a de Michalewicz ([5])  si const a ^ n alegerea
^ n mod independent rcromozomi pentru reproducere, care nu sunt neap arat
distinct i  si rcromozomi distinct i pentru reproducere. Aceste select ii se realizeaz a
^ n funct ie de performant ele cromozomilor.
Un individ cu o performant  a peste medie are o probabilitate mai mare de a
selectat pentru ^ ncruci sare, iar cei cu o performant  a mai mic a dec^ at media au o
probabilitate mai mare de a  selectat i pentru  stergere.
Noua populat ie P(t+ 1) este format a din ( nr) cromozomi din vechea
popilat ie, tot i provenit i din p(t) cu except ia celor selectat i pentru  stergere  si
rdescendent i ai celor rp arint i selectat i. De ment ionat c a ecare cromozom se-
lectat pentru modicare este utilizabil doar pentu o singur a operat ie genetic a
(^ ncruci sare, mutat ie).
^In urma select ie apar 3 populat ii intermediare:
P1: cont ine cei rp arint i
P2: cont ine rcromozomi ce vor   ster si
P3: cont ine (n-r) cromozomi care vor  copiat i ^ n P(t+1)
Populat iile P1 siP3nu sunt neap arat disjuncte; un cromozom care are o
performant  a peste medie poate  selectat at^ at ^ n P1c^ at  si ^ nP3. ^ n felul acesta,
unul sau mai mult i descendent i ai cromozomului respectiv vor intra ^ n P(t+1).
Dac a se utilizeaz a trei operatori (^ ncruci sarea, mutat ia  si inversiunea), atunci
asupra unei submult imi din P1se va aplica ^ ncruci sarea, asupra unei alte sub-
multimi se va aplica mutat ia  si asupra celorlalt i cromozomi di P1se va aplica
inversiunea.
Select ia nestandard este diferit a (deosebit a) de celelate tipuri de select ie,
deoarece ^ n cazul select iei nestandard, operatorul de mutat ie se aplic a unui cro-
mozom ^ ntreg  si nu doar unei singure gene ca in cazul celorlalte tipuri de select ie
(proport ional a  si prin etichetare).

3.2. ^Incruci sarea 21
3.2 ^Incruci sarea
3.2.1 Considerat ii privind ^ ncruci sarea
Select ia nu asigur a dinamica populat iei. Practic, prin aplicarea operatorului
de select ie, f ar a apelul vreunui operator de variat ie a structurii cromozomilor
populat iei curente, spat iul de c autare nu poate  explorat.
Pentru a provoca migrarea indivizilor ^ nspre zone avantajoase ce corespund
solut iilor globale, este necesar a modicarea structurii acestora. ^Incruci sarea r aspunde
cu succes acestei cerint e. Sursa de inspirat ie a acestui operator genetic o reprezint
^ ncruci sarea intercromozomial a natural a ([9]).
Operatorul de ^ ncruci sare (recombinare) permite permite combinarea seg-
mentelor de cromozomi corespunz^ and p arint ilor, asfel obt in^ andu-se noi indivizi,
numit i descendent i ([3]).
^In general operatorul de ^ ncruci sare este aplicat asupra a doi indivizi, rezultnd
unu, doi sau mai mult i descendent i. Cu alte cuvinte, descendent ii obt inut i prin
recombinare vor avea caracteristici ale ambilor p arint i.
3.2.2 ^Incruci sarea cu puncte de t aietur a
3.2.2.1 ^Incrucisarea cu un punct de t aietur a
^Incruci sarea cu un singur punct de t aietur a a fost implementat de John Holland^ n
1975 ([12]). Aceasta const a ^ n alegerea unei pozit ii aleatoare k2f1;2;:::;n1g
^ n cromozomii p arint i, numit punct de t aietur a.
Num arul kindic a pozitia din interiorul cromozomilor unde secvent a cromo-
zomial a se rupe pentru ca segmentele s a se recombine, iar nreprezint a num arul
de gene ale cromozomului (lungimea cromozomului).
Primul u va cont ine primele kgene ale primului p arinte si ultimele n-kgene,
pe c^ and cel de-al doilea descendent va cont ine primele kgele ale celui de-al doilea
p arinte  si ultimele n-kgene al primului p arinte ([3], [12], [11]).
EXEMPLU
FIGURA
3.2.2.2 ^Incrucisarea cu dou a puncte de t aietur a
Acest tip de ^ ncruci sare const a ^ n alegerea a dou a pozit ii aleatoare a  si b ( a <
b<n ) ^ n cromozomii p arint i unde secvent ele se vor rupe ^ n segmente.
Astfel, primul u va cont ine primele a gene ale primului p arinte, urm atoarele
a-b gene ale celui de-al doilea p arinte  si primele n-b gene ale primului p arinte,
pe c^ and cel de-al doile u va cont ine primele a gene al celui de-al doilea p arinte,
urm atoarele a-b gene al primului p arinte  si primele n-b gene ale celui de-al doilea
p arinte([11]).
EXEMPLU

3.2. ^Incruci sarea 22
FIGURA
3.2.2.3 ^Incrucisarea cu dou a puncte de t aietur a
Acest operator reprezint a varianta generalizat a a operatorului cu dou a puncte de
t aietur a.
Acest tip de ^ ncruci sare const a ^ n alegera unui num ar arbitrar de puncte de
t aietur a iar descendent ii se obt in prin concatenarea decvent elor rezultate ^ n urma
deviz arii cromozomilor p arint i. Mention am c a num arul maxim de t aieturi permise
este dat de lungimea cromozomilor. Ordinea secvent elor ce intr a ^ n component a
reprezent arii unui descendent este stabilit a astfel: se alterneaz a o secvent  a de
gene preluate din primul p arinte cu secvent  a de gene din cel de-al doilea p arinte.
^In cazul unui num ar mare de t^ eturi, experimental se poate observa c a apli-
carea acestui operator de ^ ncruci sare cu un num ar mare de puncte de t aietur a
^ ncetine ste convergent a populat iei^ nspre solut ia global a. ^In practic a este preferat a
varianta cu 2 t aieturi sau o variant a a operatorului cu t aieturi multiple ^ n care
num arul acestora este variabil (generat aleator)  si nu prexat ca un parametru
al algoritmului.
3.2.3 Algoritmi de ^ ncruci sare
3.2.3.1 Algoritm pentru ^ ncrucisarea cu un punct de t aietur a
Algoritmul penru ^ ncruci sarea cu un punct de t aietur a este urm atorul ([9]):
^Inceput Algoritm ^Incruciare1Punct:
Pasul 1: Se aleg doi p arint i: c1= (a1;a2;:::;a n)  sic2= (b1;b2;:::;b n).
Pasul 2: Se genereaz a punctul de t aietur a k2f1;2;:::;ng.
Pasul 3: Se creaz a cei doi descendent i:
d1= (a1;:::;a k;bk+1;:::;b n)
d2= (b1;:::;b k;ak+1;:::;a n)
Sf^ ar sit Algoritm
3.2.3.2 Algoritm pentru ^ ncrucisarea cu dou a puncte de t aietur a
Algoritmul penru ^ ncruci sarea cu dou a puncte de t aietur a este prezentat ^ n ceea
ce urmeaz a ([9]):
^Inceput Algoritm ^Incruciare2Puncte:
Pasul 1: Se aleg doi p arint i: c1= (a1;a2;:::;a n)  sic2= (b1;b2;:::;b n).

3.2. ^Incruci sarea 23
Pasul 2: Se genereaz a aleator cele dou a puncte de t aietur a k2f1;2;:::;ng sit2
f1;2;:::;ng.
Pasul 3: Dac a (t<k )interschimb a (k,t)
Pasul 4: Se creaz a cei doi descendent i:
d1= (a1;:::;a k;bk+1;:::;b t;at+1;:::;a n)
d2= (b1;:::;b k;ak+1;:::;a n;bt+1;:::;b n)
Sf^ ar sit Algoritm
3.2.3.3 Algoritm pentru ^ ncrucisarea cu mai multe puncte de t aietur a
Algoritmul penru ^ ncruci sarea cu mai multe puncte de t aietur a este prezentat ^ n
ceea ce urmeaz a ([9]):
^Inceput Algoritm ^IncruciareMPuncte
DE SCRIS ALGORITMUL

3.2. ^Incruci sarea 24

Capitolul 4
Aplicatii
25

Bibliografie 26

Bibliograe
[1] Baker J. E. , 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] Constantinescu Cristian , Algoritmi genetici. Introducere ,

Algoritmi-Genetici-Introducere
[3] Dumitrescu D., Algoritmi genetici  si strategii evolutive – aplicat ii ^ n
Inteligent a Articial a  si ^ n domenii conexe , Editura Albastr a, 2006.
[4] Goldberg D. E. 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.
[5] Z. Michalawicz, Genetic Algorithms + Data Structes = Evolu-
tion 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.
[6] Victor Neagoe, http://www.victorneagoe.com/university/prai/lab5a.
pdf
[7] Constantin Stoean, inf.ucv.ro/documents/cstoean/c6/A_14.pdf
[8] Algoritm genetici: cursuri, andrei.clubcisco.ro/cursuri/5master/
sptrm/curs/Algoritmi%20genetici.pdf
[9] Rotar C., Modele naturale  si Algoritmi Evolutivi , Editura Accent, 2008.
27

BIBLIOGRAFIE 28
[10] http://www.scritub.com/stiinta/informatica/retele/
Algoritmi-Genetici-Studiu-de-c24232.php : Algoritmi Genetici.
Studiu de caz: Optimizarea tracului intr-o retea .
[11] Rotar C., https://olidej.wikispaces.com/file/view/1115+
Algoritmi+genetici.pdf :Algoritmi Genetici: Capitolul 15
[12] Holland J. Adaptation in Natural and Articial Systems ,The University of
Michigan Press, 1975.