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

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
4 Aplicatii 19
Bibliograe 20
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 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 ([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 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.([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.
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 ([17]).
Algoritmii genetici ^ mprumut a urm atoarele caracteristici din principiile ge-
neticii ([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 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 ([17],
[4], [18]).
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
([4])
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, [21]).
^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 ([4] [20]):
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 din-
tre 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([19]):
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.([19])

3.1. Select ia 17
Algoritmul Monte Carlo
Algoritmul select iei proport ionate e inspirat de algoritmul Monte Carlo, cunoscut
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 ([4]):
^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 ca-
pacitatea acestei a de a favoriza exploatarea indivizilor performant i ai populat iei.
Dezavantajul select iei poate  ^ nt^ alnit ^ n 2 situat ii([4],[19]):
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

3.1. Select ia 18
^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.
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([19]):
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

Capitolul 4
Aplicatii
19

Bibliografie 20

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. Introducere ,

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.
21

BIBLIOGRAFIE 22
[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

BIBLIOGRAFIE 23
[19] C. Rotar, Modele naturale  si Algoritmi Evolutivi , Editura Accent, 2008.
[20] http://www.scritub.com/stiinta/informatica/retele/
Algoritmi-Genetici-Studiu-de-c24232.php : Algoritmi Genetici.
Studiu de caz: Optimizarea tracului intr-o retea .
[21] Holland Genetics Algorithm