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

Cuprins
Introducere 1
1 Principii generale despre algoritmi evolutivi  si genetici 3
1.1 Denirea algoritmilor evolutivi . . . . . . . . . . . . . . . . . . . . 3
1.2 Explorare  si exploatare . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Strucutura general a unui algoritm evolutiv . . . . . . . . . . . . . 4
1.4 Denirea algoritmului genetic . . . . . . . . . . . . . . . . . . . . 6
1.5 Caracteristicile unui algoritm genetic . . . . . . . . . . . . . . . . 7
1.6 Structura algoritmului genetic . . . . . . . . . . . . . . . . . . . . 8
2 Operatori genetici 9
2.1 Select ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Select ia proport ional a . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Select ia bazat a pe ordonare . . . . . . . . . . . . . . . . . 14
2.1.3 Select ia nestandard . . . . . . . . . . . . . . . . . . . . . . 15
2.2 ^Incruci sarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Considerat ii privind ^ ncruci sarea . . . . . . . . . . . . . . . 16
2.2.2 ^Incruci sarea cu puncte de t aietur a . . . . . . . . . . . . . . 16
2.2.2.1 ^Incrucisarea cu un punct de t aietur a . . . . . . . 16
2.2.2.2 ^Incruci sarea cu dou a puncte de t aietur a . . . . . 18
2.2.2.3 ^Incrucisarea cu mai multe puncte de t aietur a . . 19
2.3 Mutat ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Principiile mutat iei . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Mutat ia uniform a tare . . . . . . . . . . . . . . . . . . . . 22
2.3.3 Mutat ia slab a . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Scheme constructive a unui algoritm genetic 25
3.1 Codicarea binar a . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Codicarea binar a ^ n spat iul de c autare unidimensional . . 25
3.1.2 Codicarea binar a ^ n spat iul de c autare multidimensional . 27
3.2 Scheme  si not iuni conexe . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Teorema schemelor  si blocuri constructive . . . . . . . . . . . . . 29
1

Cuprins 2
4 Aplicatii 33
4.1 Determinarea maximului unei funct ii de o variabil a . . . . . . . . 33
4.2 Determinarea maximului unei funct ii de dou a variabile . . . . . . 47
Concluzii 50
Bibliograe 51

Introducere
Algoritmii genetici sunt o clas a a algoritmilor evolutivi, ace stia ind algoritmi
^ n care datele problemei se aleg ^ n mod aleator. Principala caracteristic a a algo-
ritmilor evolutivi este aceea c a se inspir a din teoria evolut iei speciilor  si se aplic a
^ n rezolvarea problemelor de optimizare
Cel care a ^ nceput s a cerceteze acest domeniu a fost John Holland, ca mai
apoi s a e dezvoltat i de c atre David Goldberg ^ n lucrarea sa "Genetic algorithms
in search, optimization, and machine learning".
Ca aplicat ii practice, algoritmii genetici sunt cel mai adesea utilizat i ^ n re-
zolvarea problemelor de optimizare  si c autare ^ n domenii precum:
ˆOptimizare numeric a  si combinatoric a;
ˆinteligent  a aticial a( ^ n crearea circuitelor neuronale, deplasarea ^ ntr-un
labirint, controlul deplas arii unui robot;);
ˆ^ n proiectare ( proiectarea circuitelor, a sistemelor de conducte i a liniilor de
comunicat ie, proiectarea avioanelor, reactoarelor chimice sau a structurilor
construct ilor);
ˆ^ n industria jocurilor(rezolvarea unor probleme dicile de tip joc );
ˆmeteorologie( probleme de predict ie a temperaturii, curent ilor de v^ ant);
ˆ^ n transporturi (alegerea traseelor optime ale unor vehicule, controlul rutelor
avioanelor);
ˆ^ n comunicat ii( rutarea mesajelor ^ ntr-o ret ea de telecomunicatii), s.a.
Condit ia esent ial a pentru succesul unui algoritm genetici este ca problema de
rezolvat s a nu cear a obt inerea solut iei optime, ci s a e sucient a  si o solut ie
apropiat a de optim.
Am ales acest a tem a deoarece m-a atras prin noutatea ei ^ n domeniul  stiint ic
Lucrarea mea este format a din 4 capitole principale ce prezint a urm atoarele:
ˆ^In Capitolul 1 am prezentat algoritmii evolutivi, preciz^ and stuctura unui
algoritmul evolutiv, ca mai apoi s a particulariz am algoritmii evolutivi la
algoritmii genetici, mention^ and caracteristicile unui algoritm genetic  si sta-
bilind o structur a general a a algoritmului genetic.
1

Introducere 2
ˆ^In Capitolul 2 preciz am operatorii principali ce sunt folosit i^ n implementarea
unui algoritm genetic. Descriem ce elemetele intr a ^ n alc atuirea lor  si
prezint am algoritmi de creare a ascestora.
ˆ^In Capitolul 3 vorbim despre Teoria Codurilor, cum aceasta garanteaz a
convergent a algoritmului genetic prin folosirea anumitor operatori^ n alc atuirea
lui.
ˆCapitolul 4 este destinat prezent arii contribut iei noastre ^ n aceast a lucrarea,
aceea de crea un algoritm genetic pentru a
area maximului unei funct ii cu o
variabil a, respectiv dou a variabile, analizarea rezultatelor  si a performant ei
algoritmului.

Capitolul 1
Principii generale despre
algoritmi evolutivi  si genetici
1.1 Denirea algoritmilor evolutivi
Algoritmii evolutivi sunt cei mai vechi algoritmi probabili sti  si au ca surs a de
inspirat ie evolut ia biologic a. Algoritmii evolutivi cuprind urm atoarele clase de
algoritmi: strategiile evolutive, programarea evolutiv a  si algoritmii genetici( [3]).
Algoritmii probabili sti implic a m acar un pas ^ n care decizia se ia ^ n mod
aleator. Ace stia sunt algoritmi ce nu pot  prev azut i,deoarece la repet ari succesive
se obt in solut ii diferite datorit a unor pa si ce depind de valori generate^ nt^ ampl ator
n timpul execut iei. Solut iile obt inute sunt aproximative. Scopul algoritmilor
evolutivi este c autarea solut iei optime folosind o mult ime de solut ii din spat iul
tuturor solut iilor potent iale ([1]).
Algoritmii evolutivi utilizeaz a un vocabular ^ mprumutat din teoria evolut iei
a speciilor biologice(teoria darwinist a). Un algoritm genetic simuleaz a evolut ia
printr-o succesiune de generat ii (proces iterativ) ale unei populat ii (mult ime) de
solut ii candidat. O solut ie candidat este reprezentat a ca un  sir de gene (genotip)
 si poart a numele de cromozom . Gena este informat ia atomic dintr-un cromo-
zom. Pozit ia pe care o ocup a o gen a se numete locus iar toate valorile posibile
pentru o gen a formeaz a setul de alele ale genei. Evolut ia populat iei ment inut a de
algoritmul genetic este condus a de dou elemente: operatorii genetici  sifunct ia
de evaluare a calit at ii cromozomilor. Select ia ,^ ncruci sarea  simutat ia sunt
operatorii genetici uzuali, ind inspirat i de procesele naturale care stau la baza
evolut iei. Cromozomul asupra c aruia se aplic a un operator genetic poart a nu-
mele de p arinte iar cromozomul rezultat ^ n urma acelui operator este numit
descendent . Un proces (aleator) de select ie ofer a indivizilor mai bine adaptat i
 sanse mai mari pentru a supraviet ui n generat ia urmtoare. Gradul de adaptare la
mediu al indivizilor este m asurat de funct ia tness obt inut a pornind de la funct ie
matematic de optimizat. ^Incruci sarea (recombinarea) are ca scop schimbul de
informat ie genetic a ^ ntre doi sau mai mult i cromozomi  si mutat ia care const a ^ n
3

1.2. Explorare  si exploatare 4
modicarea aleatoare a unei gene. Solut ia returnat a de un algoritm genetic este
cel mai bun individ din ultima generat ie ([2], [6]).
1.2 Explorare  si exploatare
Tehnicile calculului evolutiv sunt metode slabe de optimizare de oarece sunt
aplicabile unor clase largi de probleme. Pentru a putea  abordat cu aceste
tehnici, problema de rezolvat trebuie pus sub forma unei probleme de optimizare.
Comportamentul algoritmului evolutiv^ n rezolvarea problemelor de optimizare
este str^ ans legat a de conceptul de explorare  si exploatare a spat iului de c autare.
Atunci cand rezolv am o anumita problem a, c autam o solut ie care s a e cea mai
bun a printre alte solut ii. Spat iul tuturor solut iilor posibile se nume ste spat iul de
c autare. Fiecare punct din spat iul de c autare este de fapt o solut ie posibil a.
Explorarea spat iului de c autare se refer a la gradul de parcurgere(acoperire) a
spat iilor solut iilor posibile, din care se ia solut ia optim a, ^ n timp ce exploatarea
spat iului de c autare intensic a c autarea ^ n zonele ^ n care sunt  sanse mai mari ca
solutia s a se g aseasc a. Cele dou a concepte corespund c aut arii locale (exploatarea)
si c aut arii globale(explorarea) ([3] [2]).
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.
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 con-
vergent a populat iei ^ nspre solut iile optime([3],[6]).
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 algoritmului
evolutiv permite persoanei (factorului uman) s a ajusteze echilibrul explorare-
exploatare pe o problem a concret a.
1.3 Strucutura general a unui algoritm evolutiv
O procedur a evolutiv a e alc atuit din urm atoarele elemente([6], [7]):
1. O reprezentare a spat iului de c autare (spat iul st arilor problemei  si spat iul
solut iilor posibile ale problemei)

1.3. Strucutura general a unui algoritm evolutiv 5
2. O populat ie init ial a de solut ii potent iale. De regul a populat ia init ial a se
alege ^ n mod arbitrar.
3. O funct ie de evaluare ce m asoar a performant a ec arui individ ^ n raport cu
scopul urm arit.
4. O meotd a de select ie a cromozomilor pentru modicare.
5.Operatorii genetici pentru crearea de noi cromozomi prin recombinare  si
mutat ie.
6.Valorile parametrilor ce apar^ n algoritm, cum ar : dimensiunea populat iei,
num arul total de generat ii etc.
^In acest caz putem formula o structura a algoritmului evolutiv ([2]):
Algorithm 1 Structura unui algoritm evolutiv
funct ie Algoritm evolutiv
Init ializeaz a momentul t= 0, num arul de indivizi n si populat ia de indivizi generat i
aleator P(t)
t= 0;
nr indivizi=n;
P(t)= Generare populat ie(nr indivizi);
Se evalueaz a populat ia de indivizi P(t)folosind funct ia de adaptare f.
c^ at timp (numarul de generatii nu e atins) execut a
t=t+ 1;
Se selecteaz a p arint ii din P(t).
funct ie Selectie (P(t))
sf^ ar sit funct ie
Se recombin a perechi de p arint i din P(t).
funct ie Incrucis are (P(t))
sf^ ar sit funct ie
Se aplic a mutat ia asupra descendent ilor obt inut i dup a ^ ncruci sare.
funct ie Mutat ie (P(t))
sf^ ar sit funct ie
Se evalueaz a ecare descendent din P(t).
funct ie Evaluare (P(t))
sf^ ar sit funct ie
Se selecteaz a indivizii care vor supraviet ui  si vor forma urm atoarea generat ie.
funct ie Supravietuire (n;c)
sf^ ar sit funct ie
sf^ ar sit c^ at timp
sf^ ar sit funct ie

1.4. Denirea algoritmului genetic 6
1.4 Denirea algoritmului genetic
Algoritmul genetic reprezint a o clas a a algoritmilor evolutivi  si este ^ n esent  a
un algoritm de c autare  si optimizare ^ n spat iul solut iilor posibile. O populat ie de
solut ii posibile este generat a, mai apoi, asupra indivizilor acesteia se vor aplica
operatori precum ^ ncruci sarea, mutat ia  si select ia natural a. Noua generat ie este
alc atuit a din descendent ii populat iei vechi, ace stia din urm a devenind noi solut ii
posibile . De-a lungul evolut iei se ^ nregistreaz a o cre stere a performant elor in-
divizilor populat iei curente, fapt care asigur a convergent a algoritmului ^ nspre
solut iile reale ale problemei considerate. Crearea unui algoritm genetic de re-
zolvare a unei probleme concrete presupune evident ierea urm atoarelor compo-
nente ([3],[1]):
1.Individul
Individul reprezint a o solut ie posibil a din spat iul de c autare.
^In funct ie de specicul soluiei posibile, putem determina mod de codicare
a acesteia. Codicarea unei solut ii formeaz a un cromozom  si e recunoscut
ca un individ al populat iei curente. Fiecare cromozom este format dintr-
un  sir de valori ale unui alfabet dat. Valoarea de pe o pozit ie oarecare a
cromozomului se nume ste gen a. Lungimea  sirului de gene din codicarea
cromozomului este constant a  si depinde de num arul de tr as aturi denitorii
ale unei solut ii posibile a problemei.
Fie c un cromozom oarecare  si Aalfabetul genelor din reprezentarea sa.
Cromozomul c se descrie prin vectorul de n elemente:
c= (a1;a2;:::;a n);
undeai2A;8i2f1;2;:::ng. ^ n cazul algoritmilor genetici, codicare este
binar a, deci alfabetul Aare ^ n component  a valorile 0 si1..
2.Populat ia
O mult ime nit a de cromozomi alc atuiet e populat ia. Dimensiunea populat iei
(num arul de indivizi care o formeaz a) este o valoare constant a pe care o
stabilim la ^ nceput  si reprezint a un parametru important al algoritmului
dezvoltat. O astfel de populaie se descrie astfel:
P(t) =fc1(t);


;cn(t)g;
undecmreprezint a cromozomul.
Prima generat ie se nume ste populat ie init ial a  si construirea acesteia se face
prin alegerea aleatoare a unor solut ii posibile ^ n domeniul de c@utare.

1.5. Caracteristicile unui algoritm genetic 7
3.Funct ia de evaluare
Evaluarea calit at ii indivizilor se face cu ajutorul unei funct ii de adecvare
(evaluare sau adaptare), denit a ca: f:S !R, undeSeste spat iul de
c autare al solut iilor. De obicei, cu c^ at cromozomul este mai bun, 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).
4.Select ia p arint ilor
Evolut ia populat iei, obt inerea generat iilor de indivizi mai performant i
dec^ at predecesorii lor, este cauzat a de operatorul de select ie  si operatorii de
variat ie (^ ncruci sarea  si mutat ia). Scopul select iei este de a asigura  sanse
mai mari de reproducere a celor mai buni indivizi dintr-o populat ie dat a,
ce vor contribui la crearea generat iei urm atoare.
5.Operatorii de variat ie
Select ia nu este sucient a pentru g asi solut ia optim a din spat iul de c autare.
E nevoie ca indivizii selectat i sufere modic ari cu ajutorul operatorilor de
variat ie pentru a permite obt inerea unor descendent i diferit i, respectiv pen-
tru a permite o explorare bun a a spat iului de c autare. Operatorii de variat ie
sunt reprezentat i de operatorii de ^ ncruci sare  si mutat ie.
Operatorul de ^ ncruci sare se dene ste ca o aplicat ie: r:Ap!Ad si real-
izeaz 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 de la momentul t.
Operatorul de mutat ie reprezint a aplicat ia 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.
6.Init ializarea  si condit ia de terminare
Init ializarea  si condit ia de terminare sunt criterii esent iale ^ n vederea
funct ion arii algoritmilor genetici. De obicei init ializarea se face ^ n mod
aleator, iar condit ia de terminare se veric a la ecare generat ie cu ajutorul
unor criterii, cum ar : atingerea unei performant e, atingerea unui anumit
num ar de generat ii cu sau f ar a s a se  c^ a stigat performant a, gradul de
uniformitate a populat iei, etc.
1.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. Cromozomii utilizat i au lungime constant a;

1.6. Structura algoritmului genetic 8
2. Populat ia (generat ia) P(t+1) se obt ine ret in^ and tot i descendent ii populat iei
P(t), nu neap arat distinct i,  si sterg^ and complet cromozomii generat iei an-
terioareP(t);
3. Algoritmii genetici ment in o populat ie constant a P(t) de indivizi la ecare
iterat iet.
4. Algoritmii genetici pot g asi solut ii optime (sau aproape optime) cu o mare
probabilitate.
1.6 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 ^ n vedere urmatoarele caracteris-
ticile precizate anterior. ^In acest caz, structura algoritmului genetic fundamental
este ([2], [8], [6]):
Algorithm 2 Structura unui algoritm genetic
funct ie Algoritm genetic
Init ializeaz a momentul t= 0, num arul de indivizi n si populat ia de indivizi generat i
aleator P(t)
t= 0;
nr indivizi= n;
Se initializeaz a aleator populat ia P(0)
P(0)= Generare populat ie(nr indivizi);
se evalueaz a cromozomii populat iei P(0); ^ n acest scop se utilizeaz a o funct ie de
adecvare ce depinde de problem a;
c^ at timp (numarul de generatii nu e atins) execut a
Se selecteaz a cromozomii din P(0)care vor contribui la formarea noii generat ii
FiePSmult imea cromozomilor selectati ( PSreprezint a o populatie intermediar a).
PS(t)=SelectieP(t)
Se utilizeaz a operat ia de ^ ncruci sare ^ ntre perechi de p arint i din PSunde va rezulta
mult imea cromozomilor ^ ncruci sat i PR
PR(t)=Incrucis are PS(t)
Se aplic a operat ia de mutat ie asupra descendent ilor obt inut i dup a ^ ncruci sare
P(t+ 1)= Mutat iePR(t)
t=t+ 1;
sf^ ar sit c^ at timp
sf^ ar sit funct ie

Capitolul 2
Operatori genetici
Operatorii genetici joac a un rol important ^ n modelarea algoritmilor ge-
netici.
Exist a 3 tipuri de operatori: operatori de select ie, operatori de ^ ncruci sare
 si operatori de mutat ie.
2.1 Select ia
Operatorul de select ie este unul din cei trei operatori ce intr a ^ n alc atuirea
algoritmilor genetici. Este unul din cei mai important i operatori genetici 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
indivizilor.
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.
2.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.
1. Funct ia de adecvare
FieP(t) =fc1;c2;:::;c ng, ce reprezint a mult imea cromozomilor din generat ia
9

2.1. Select ia 10
curent at.
FieF=ff1;f2;:::;f ngmult imea valorilor de performant  a a cromozomilor.
Not am cu fit:P(t)!F, funct ia de evaluare a performant elor cromo-
zomilor. 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):
2. Probabilitatea de select ie
Denit ia 2.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([6]):
pi=fi
Fit(t)=fi
nP
i=1fi=fit(ci)
nP
i=1fit(ci)
O variant a a procedurii de select ie proport ional a este aceea ^ n care sunt
extrase 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 in-
divizilor, se poate determina num arul mediu de copii (clone) ale ec arui
individ.
Denit ia 2.1 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);

2.1. Select ia 11
undefitmediu(ci)este performat a medie a populat iei.([6])
3. 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
sector 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 de nori a ruletei conduce la formarea populat iei in-
termediare 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 ([2]):

2.1. Select ia 12
Algorithm 3 Algoritmul Monte Carlo de select ie
funct ie Monte Carlo (n;c)
Initializ am performant a total a  si probabilitatea cumulat a cu 0
F=0; q(0)=0
pentrui= 1lanexecut a
F=F+f(c(i));
sf^ ar sit pentru
Calcul am probabilitatea de select ie conform denit iei de mai sus
pentrui= 1lanexecut a
p(i)=f(c(i))/F;
sf^ ar sit pentru
pentrui= 1lanexecut a
q(i)=q(i-1)+p(i);
sf^ ar sit pentru
Gener am aleator g  si aplic am urm atoarea regul a de select ie cu ajutorul c areia vom
crea o populat ie intermediar a format a din indivizii crom nou
pentrui= 1lanexecut a
g=rand(0,1);
dac ag<q (1)atunci
crom nou(1) =c(1);
altfel
i=2;
c^ at timp (gq(i) siin)execut a
i=i+1;
sf^ ar sit c^ at timp
crom nou(i) =c(i);
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit funct ie
4. 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([2],[6]):
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 ca
^ n gura 2.1:
^In acest caz, probabilitatea extragerii indivizilor de performant  a supe-
rioar a este mare, deci num arul de copii ale acestuia ^ n populat ia interme-
diar a este de asemenea mare.

2.1. Select ia 13
Figura 2.1: Reprezentarea sectoarelor ruletei pentru situat ia 1
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
apropiate.
^In acest caz ruleta arat a ca ^ n gura 2.2
Figura 2.2: Reprezentarea sectoarelor ruletei pentru situat ia 2
^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 acestei situat ii 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 a 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 ([6])ofer a diferite variante de scalare a funct iei
de performant  a (tness). Scalarea poate  static a sau dinamic a (^ n funct ie de
independent a, respectiv, dependent a de num arul generat iei).

2.1. Select ia 14
Prezent am ^ n continuare c^ ateva dintre metodele de scalare utilizate ^ n mod
frecvent([6]):
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, unden si reprezint a
un parametru ^ ntreg supraunitar. Funct ia transformat a de performant  a devine:
fittransformat (c) =fit(c)n
2.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 ordinea acestuia ^ n concordant  a cu valoarea funct iei
tness  si stabilirea unei probabilit at i de select ie dependent a de valoarea atribuit a.
Practic, populat ia va  supus a unei proceduri de ordonare descresc atoare dup a
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 .([6])
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
Scenariile defectuoase ale select iei proport ionale(populat ia relativ omogen a  si
diferent ele mari ^ ntre performant ele indivizilor) nu vor mai  un impediment
^ n cazul select iei prin ordonare.
Ordonarea produce o scalare uniform a ^ n cadrul populat iei, de aceea situat iile
nefavorabile ^ nt^ alnite la select ia proport ional a sunt rezolvate. Dependent a prob-
abilit at ii de select ie poate  liniar a sau neliniar a ^ n funct ie de rangul individului.

2.1. Select ia 15
Dependent a liniar a a probabilit at ii de select ie pia cromozomului cipoate
formulat a astfel:
pi=1
n
g2(ri1)(g1)
(n1)
[2]
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;adic anbun=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([2]).
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.
2.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 a 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
populat ie, tot i provenit i din P(t) cu except ia celor selectat i pentru  stergere  si

2.2. ^Incruci sarea 16
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 per-
formant  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 submultimi se
va aplica mutat ia  si asupra celorlalt i cromozomi din P1se va aplica inversiunea.
Select ia nestandard este diferit a (deosebit a) de celelate tipuri de select ie,de-
oarece ^ n cazul select iei nestandard, operatorul de mutat ie se aplic a unui cromo-
zom ^ ntreg  si nu doar unei singure gene ca in cazul celorlalte tipuri de select ie
(proport ional a  si prin etichetare).
2.2 ^Incruci sarea
2.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 as-
punde cu succes acestei cerint e. Sursa de inspirat ie a acestui operator genetic o
reprezint a ^ ncruci sarea intercromozomial a natural a ([6]).
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 ([2]).
^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.
2.2.2 ^Incruci sarea cu puncte de t aietur a
2.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 ([4],[3]). Aceasta const a ^ n alegerea unei pozit ii aleatoare k2f1;2;:::;n1g

2.2. ^Incruci sarea 17
^ n cromozomii p arint i, numit punct de t aietur a.
Num arul kindic a pozit ia 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 ([2], [4], [9]).
Pentru a ^ ntelege mai bine acest mecanism, vom da un exemplu concret. Vom
lua doi indivizi c1 sic2. Ambii au lungimea n= 8. Punctul de t aietur a ales se
a
 a pe pozit ia k= 4. Ace stia sunt reprezentat i ^ n gura 2.3:
Figura 2.3: Reprezentarea p arint ilor ^ n cazul ^ ncruci sarii cu un punct de t aietur a
^In urma^ ncruci s arii, vor ap area doi descendenti, ce vor^ mprumuta caracteristi
ale ambilor p arinti, ca ^ n gura 2.4:
Figura 2.4: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu un punct de t aietur a

2.2. ^Incruci sarea 18
Astfel algoritmul penru ^ ncruci sarea cu un punct de t aietur a este urm atorul
([6]):
Algorithm 4 ^Incruci sare printr-un punct de t aietur a
funct ie ^Incrucis are1Punct (c1;c2)
fkg2f1;2;:::;ng
pentrui= 1lakexecut a
xi=ai
yi=bi
sf^ ar sit pentru
pentrui=k+ 1lanexecut a
xi=bi
yi=ai
sf^ ar sit pentru
sf^ ar sit funct ie
2.2.2.2 ^Incruci sarea 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-bgene ale celui de-al doilea p arinte  si primele n-bgene 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([9]).
S i ^ n acest caz vom avea doi cromozomi-p arint i c1 sic2, ambii de lungime
n= 8. De data aceasta vor  doua puncte de t aietur a, alese pe pozit iile k= 1  si
t= 4. Ace stia sunt reprezentat i ^ n gura 2.5
Figura 2.5: Reprezentarea p arint ilor ^ n cazul ^ ncruci sarii cu doua puncte de t aietur a
^In urma ^ ncruci s arii, cei doi descendent i rezultat i vor ar ata ca ^ n gura 2.6:
Algoritmul pentru ^ ncruci sarea cu dou a puncte de t aietur a este prezentat ^ n
ceea ce urmeaz a ([6]):

2.2. ^Incruci sarea 19
Figura 2.6: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu doua puncte de
t aietur a
Algorithm 5 ^Incruci sare prin 2 puncte de t aietur a
funct ie ^Incrucis are2Puncte (c1;c2)
fk;tg2f1;2;:::;ng
dac at<k atunci
interschimb a (k;t)
sf^ ar sit dac a
pentrui= 1lakexecut a
xi=ai
yi=bi
sf^ ar sit pentru
pentrui=k+ 1latexecut a
xi=bi
yi=ai
sf^ ar sit pentru
pentrui=t+ 1lanexecut a
xi=ai
yi=bi
sf^ ar sit pentru
sf^ ar sit funct ie
2.2.2.3 ^Incrucisarea cu mai multe 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 secvent 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 aieturi, 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

2.2. ^Incruci sarea 20
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.
Algoritmul penru ^ ncruci sarea cu mai multe puncte de t aietur a arat a ^ n felul
urm ator: ([6]):
Se aleg doi p arint i : c1= (a1; a2; :::; a n) sic2= (b1; b2; :::; b n)
Se genereaz a aleator cele mpuncte de t aietur a
fk1;k2;:::;kmg2f1;2;:::;ng
Se ordoneaz a cresc ator valorile k1; k2; :::; k m
pentrui= 1lam1execut a
pentruj= 1lamexecut a
dac akj<k iatunci
interschimb a (kj;ki)
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit pentru
Se creaz a cei doi descendent i, ce vor  de forma: d1= (x1; :::; x n)id2= (y1; :::; y n)
pentrui= 1lak1execut a
xi=ai
yi=bi
sf^ ar sit pentru
pentrui= 1lam1execut a
pentruj= 1lati+1execut a
dac ai este par atunci
xj=aj
yj=bj
altfel
xj=bj
yj=aj
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit pentru
pentrui=kmlanexecut a
dac am este par atunci
xj=aj
yj=bj
altfel
xj=bj
yj=aj
sf^ ar sit dac a
sf^ ar sit pentru

2.3. Mutat ia 21
Prin aplicarea acestui algoritm se obt in descendent ii, ce arat a^ n felul urm ator:
d1= (a1;:::;a k1;bk1+1;:::;b k2;ak2+1;:::;a k3;:::)
d2= (b1;:::;b k1;ak1+1;:::;a k2;bk2+1;:::;b k3)
^In aceast a situat ie celor doi cromozomi-p arint i c1 sic2li se vor aplica op-
eratorul de 2incruci sare ^ n cinci puncte de t aietur a.Punctele se a
a pe pozit iile
m1= 1,m2= 2,m3= 4,m4= 5  sim5= 7. Ace stia sunt reprezentat i ^ n
urm atoarea gur a:
Figura 2.7: Reprezentarea p arint ilor ^ n cazul ^ ncruci sarii cu cinci puncte de
t aietur a
Dup a aplicarea operatorului de ^ ncruci sare vor rezulta doi descendent i.Ace stia
vor ar ata astfel:
Figura 2.8: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu cinci puncte de
t aietur a
2.3 Mutat ia
2.3.1 Principiile mutat iei
Mutat ia este cel de-al doilea operator genetic ^ n ordinea important ei  si folosirii
sale. Efectul acestui operator este schimbarea valorii (bitului) unei singure pozit ii
dintr-un cromozom. Fiecare bit al populat iei poate suferi o mutat ie. A sadar, ^ ntr-
un cromozom pot exista mai multe pozitii c aruia i se poate aplica operatorul de
mutat ie ([4],[3]).
Intervent ia operatorului de mutat ie devine extrem de util a ^ n cazurile ^ n care
^ ncruci sarea nu faciliteaz a obt inerea anumitor secvent e de gene sau pentru a com-
bate efectul de convergent  a prematur a a populat iei. Fie prin aplicarea unei pre-
siuni de select ie prea mare, e prin pierderea diversit at ii indivizilor prin aplicarea
neadecvat a a ^ ncruci s arii, ne putem confrunta cu o uniformizare a populat iei, fapt
pentru care c autarea ulterioar a devine decitar a ([6]).

2.3. Mutat ia 22
^In aceste situat ii mutat ia devine factorul principal de revigorare a populat iei.
Mai mult, probabilitatea ca solut ia global a s a e situat a ^ n imediata apropiere a
unui individ performant este mare.
Mutat ia este un operator probabilist, deci exist a o probabilitate de aplicare a
operatorului, ce se nume ste probabilitate de mutat ie , notat a pm si reprezint a un
parametru al algoritmului genetic ([2]).
Consider am o populat ie de ncromozomi, ecare av^ and lungimea l. Fiecare
bit are aceea si probabilitate pmde a suferi mutat ia. Deci num arul total de bit i ai
populat iei este n
l, rezult a astfel c a num arul de bit i ce pot suferi o mutat ie este
([2]):
N=n
l
pm:
Exist a mai multe variante a operatorului de mutat ie,noi pun^ and accent pe
mutat ia uniform atare  si mutat ia neunirm a, ce vor  descrise ^ n cele ce urmeaz a.
2.3.2 Mutat ia uniform a tare
Mutat ia tare const a ^ n schimbarea unei gene a descendentului ^ n funct ei de prob-
abilitatea de mutat ie pma acesteia.
Varianta uniform a a operatorului presupune utilizarea unei valori constante a
probabilit at ii de mutat ie pmpe tot parcursul evolut iei populat iei. Cu c^ at valoarea
parametrului pmeste mai mare, cu at^ at asem anarea descendent ilor cu p arint ii
este mai put in evident a.
Algorithm 6 Mutat ia uniform a tare
funct ie MutatiaUniform aTare (c;d)
pm2[0;1] .init ializare probabilitatea de mutat ie
pentrui= 1lanexecut a
Genereaz a aleator k2[0;1]
dac ak<p matunci
xi= 1ai .valoarea pozit iei se schimb a 0 ^ n 1  si 1 ^ n 0
altfel
xi=ai .valoarea pozit iei respective nu se schimb a
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit funct ie
2.3.3 Mutat ia slab a
Exist a situat ii ^ n care condit ia k<p mdin algoritmul mutat iei tari s a nu produc a
o schimbare a valorii pozit iei considerate. ^In acest caz, se stabilete valoarea

2.3. Mutat ia 23
subunitar a pa= 0:5 reprezent^ and probabilitatea de alocare a valorii 1 pentru
gena ce trebuie modicat a ([6]). Astfel, algoritmul mutat iei slabe este urm atorul:
Algorithm 7 Mutat ia slab a
funct ie MutatiaSlaba (c;d)
init ializare probabilitatea de mutat ie
pm2[0;1]
init ializare probabilitatea de alocare
pa= 0;5
pentrui= 1lanexecut a
Genereaz a aleator k2[0;1]
dac ak<p matunci
Genereaz a aleator t2[0;1]
dac at<p aatunci
xi= 1
altfel
xi= 0
sf^ ar sit dac a
altfel
xi=ai
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit funct ie

2.3. Mutat ia 24

Capitolul 3
Scheme constructive a unui
algoritm genetic
Algoritmii genetici utilizeaz a operatori ce au rol ^ n copiera cromozomilor
(select ia), schimbarea unor sub siruri (incrucisarea)  si modicarea unor pozit ii
(mutat ia).
Ace sti operatori conduc la c autarea ecient a a solut iei problemei. Com-
portarea algoritmilor genetici se bazeaz a pe observarea anumitor similarit at i ^ ntre
cromozomii ce apart in unor dou a operat ii succesive obt inute prin aplicarea algo-
ritmilor genetici. Similarit at ile ment ionate conduc la o cre stere a performant ei
medii a populat iei de la o generat ie la alta.
Conform literaturii de specialitate ([2]), schema reprezint a o mult ime de cro-
mozomi av^ and anumite pozit ii identice. Mai bine spus, similarit atile dintre cro-
mozomi se numesc scheme.
3.1 Codicarea binar a
Mult imea, ce e alc atuit a din simbolurile 0 si1formeaz a cel mai scurt alfabet,
numit alfabet binar. Codicarea binar a e o funct ie C:D![0;1] ce tranform a
un num ar spat iul de c autare D^ ntr-un sir de valori alc atuite din 0 si1.
Noi vom studia codicare binar a ^ n funct ie de tipul spat iului de c autare, deci
vom avea doua situat ii:
3.1.1 Codicarea binar a ^ n spat iul de c autare unidimen-
sional
Codicarea binar a^ n spat iul de c autare unidimensional se aplic a cusucces^ n cazul
problemelor de optimizare a funct iilor reale de o singur a variabil a ([ ?]).
FieDRce reprezint a spat iul de c autare a solut iilor unei probleme, s2Do
solut ie posibil a a problemei considerate  si c2P(t) reprezentarea binar a a solut iei
25

3.1. Codicarea binar a 26
s.
DomeniulDreprezint a un interval D= [x;y],x siyreprezint a limitele lui D.
Pentru a obt ine secvent a din codicarea binar a a cromozomului c, se aplic a
funct iaCce va translata valoarea s^ n intervalul [0 ;1]. Astfel se obt ine valoarea
subunitar a s0:
s0=C(s) =sx
yx
apoi se converte ste s0^ n binar cu precizia p, obt in^ and  sirul de nvalori binare:
(c1;c2;:::;c n)2f0;1gn
Pentru a asigura precizia dorit a a codic arii sunt necesare npozit ii binare.Num arul
de posit ii binare se determin a din urm atoarea relat ie:
2n1yx
p2n(3.1)
Pentru aceast a situat ie vom da urm atorul exemplu:
Exemplul 3.1.1 FieD= [3;8], un punct oarecare s= 4;23, are codicarea se
va face cu precizia de p= 102.
Funct ia de transformare devine:
C(s) =s3
83=4;233
5= 0;246
Num arul de cifre binare se deduce cu relat ia:
2n15
1022n
2n15002n
Rezolv^ and inecuat iile, obt inem n= 9.
Se va aplica metoda ^ nmult irilor succesive valorii 0;246, rezult^ and conversia
in binar: 0;00111110111110 :::. Astfel, cromozomul ceste format din primele 8
cifre din reprezentarea binar a a num arului 0:246:c= (0 0 1 1 1 1 1 0 1) .
Procedura invers a codic arii binare const a ^ n convertirea din binar ^ n real al
valoriis0, apoi se aplic a transformarea invers a:
C1(s0) =s0
(yx) +x
pentru a obt ine s2[x;y].

3.2. Scheme  si not iuni conexe 27
Exemplul 3.1.2 Fiec= (0 0 1 1 1 1 1 0 1) cromozomul din exemplul anterior,
la care dorim s a-i a
 am valoarea real a.
^In prima faz a vom converti num arul 0;001111101 ^ n baza 10, unde vom obt ine
valoareas0= 0;244140625 , ca mai apoi s a se aplice transformarea C1luis0:
C1(s0) =s0
(83) + 3 = 0;244
5 + 3 = 4;22:
Se constat a c a precizia codic arii este cea impus a ^ n exemplul anterior
p= 0;2460;244 = 0:002 = 0;2
102
, iar valoarea C1(s0) = 4;22este valoarea aproximativ a a lui sconsiderat init ial
^ n exemplul anterior.
3.1.2 Codicarea binar a^ n spat iul de c autare multidimen-
sional
^In general, metoda de codicare binar a ^ n spat iul de c autare multidimensional se
aplic a ^ n optimizarea funct iilor reale de mai multe variabile.
Fie un spat iul de c autare al unei probleme date
DRh;undeD=D1D2:::Dh
,iarxi siyilimitele inferioar a, respectiv, superioar a a domeniului
Di= [xi;yi];i=1;h:
Fies2D;s = (s1;s2;::;s k) o solut ie posibil a a problemei considerate  si cromo-
zomulc2P(t) reprezentarea binar a a solut iei s.
Pentru a obt ine secvent a binar a din codicarea cromozomului cse vor efectua
urm atorii pa si:
1. Se determin a secventele binare c1;c2;:::;c kasociate valorilor reale s1;s2;:::;s k.
^In aceast a etap a se recurge la algoritmul de codicare binar a ^ n spat iul de
c autare unidimensional, pentru ecare valoare real a si;i=1;h:
2. Ce creaz a cromozomul cprin concatenarea secvent elor obt inute la pasul
precedent
c= (c1;c2;:::;c k)
3.2 Scheme  si not iuni conexe
Pentru aceasta vom deni urm atoarele not iuni.
Denit ia 3.1 O schem a de lungime reste un element al mult imii f0;1;gr.

3.2. Scheme  si not iuni conexe 28
Denit ia 3.2 FieSo schem a de lungime r. Spunem c a un cromozom x2
f0;1greste o instant  a a schemei Sdac a oric arei pozit ii diferite de * d in S^ i
corespunde o pozit ie din xav^ and aceea si valoare
Denit ia 3.3 Se nume ste pozit ie specic a a schemei Sorice pozit ie din Sdiferit a
de*. Pozit ia respectiv a simbolului *va  ^ nlocuit in egal a m asur a cu valorile 0
sau 1.
Denit ia 3.4 O schem a Sreprezint a tot i acei cromozomi xpentru care toate
pozit iile specice ale lui Scoincid cu pozit iile corespunz atoare din x. Cromozomul
xeste un reprezentant al schemei S.
Urm atoarele exemple vor contura denit iile ment ionate anterior:
Exemplul 3.2.1 SchemaS1= ( )reprezint a tot i cromozomii de lungime
5.
SchemaS2= (0 1 01)reprezint a cromozomi cromozom, ace stia ind
x1= (0 1 0 0 1) :
x2= (0 1 0 1 1) :
Exemplul 3.2.2 Fie schema
S= (1 0 01 0 1):
Aceast a schem a reprezint a patru cromozomi ce cont ine: 1 pe prima, a cincea  si
pe a  saptea pozit ie, iar 0 pe a doua, a treia  si a  sasea pozit ie. Ace sti cromozomi
vor :
x1= (1 0 0 0 1 0 1 0) ;
x2= (1 0 0 0 1 0 1 1) ;
x3= (1 0 0 1 1 0 1 0) ;
x4= (1 0 0 1 1 0 1 1) :
Exemplul 3.2.3 ^In sens invers, avem cromozomul
x= 1 0 1
Acest cromozm este reprezentat de urm atoarele 23scheme:
S1= (   );
S2= (  1);

3.3. Teorema schemelor  si blocuri constructive 29
S3= (0 1);
S4= (1 0 1):
S5= (1 0);
S6= (11);
S7= (1 );
S8= (0):
Constat am c a acest cromozom este un reprezentant al ecareia dintre schemele
prezentate mai sus.
Urm atoarea propozit ie precizeaz a num arul de reprezentant i destinat i unei an-
umite scheme.
Propozit ia 3.1 Fiecare schem a Sreprezint a 2n, unde neste num arul sim-
bolurilor *(num arul pozit iilor nespecicate) din schema S.
3.3 Teorema schemelor  si blocuri constructive
Teorema schemelor reprezint a unul dintre rezultatele teoretice importante ale
algoritmilor genetici. Recunoscut a ca teorem a fundamental a, aceasta garanteaz a
c a evolut ia generat iilor are loc^ n sensul cre sterii performant ei (dezvoltarea^ n timp
a acelor cromozomi cont in^ and secvent e de gene cu performant e mari). Rezultatul
determinat de teoria schemelor are un caracter probabilistic.
Pentru a putea formula teorema schemelor, vom deni urm aroarele m arimi
specice ale schemei([2],[6]):
Denit ia 3.5 Ordinul schemei S, notat O(S) se dene ste ca num arul de aparit ii
ale caractere binare 0 sau 1, respectiv, num arul de caractere diferite de simbolul
genetic * din compunerea schemei.
Denit ia 3.6 Lungime denitorie (util a) a schemei, notat a L(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.
Denit ia 3.7 Denim performant a unei scheme, notat a F(S) ca ind media
performant elor cromozomilor populat iei curente care cont in schema S
Exemplul 3.3.1 Fie urm atoarele scheme de lungime l=8:
S1= (1 0 0 0 1 1);
S2= (1 0 10 0 );

3.3. Teorema schemelor  si blocuri constructive 30
S3= (   1 1 01);
Ordinul unei scheme se calculeaz a num ar^ and de c^ ate ori se g asesc valorile 0
 si 1 ^ n acea schema. Pentru cele trei scheme date mai sus ordele acestora sunt
urm atoarele:
O(S1) = 6;O(S2) = 5;O(S2) = 4;
Lungimea util a (denitorie) a schemelor este diferent a dintre ultima si prima
pozit ie a unui caracter binar. Pentru cele trei scheme lungimea :
L(S1) = 8;L(S2) = 6;L(S2) = 5;
Vom considera algoritmul genetic standard av^ and urm atoarele caracteristici:
codicarea este binar a  si se aplic a select ia proport ional a, ^ ncruci sarea este cu un
singur punct de t aietur a  si mutat ia tare.
Analiz^ and efectul operatorilor asupra algoritmului, studiat i de Holland ([4])
vom deduce teorema schemelor.
Propozit ia 3.2 Cosider am un algoritm genetic ^ n care act ioneaz a select ia proport ional a.
Daca schema Sarem(S,t) reprezentant i ^ n generat ia P(t) atunci vom avea,
m(S;t+ 1) =m(S;t)F(S)
fmediu
reprezentant i ai schemei S^ n generat ia P(t+1) , iarfmediu este performant a
medie a cromozomilor populat iei curente.
Propozit ia 3.3 Consider am un algoritm genetic cu select ia proport ional a  si ^ ncruci sare
cu un singur punct de t aietur a. Fie pcprobabilitatea de aplicare a ^ ncruci s arii.
Num arulm(S;t+ 1) al reprezentant ilor schemei S^ n generat ia P(t+1) satisface
inegalitatea
m(S;t+ 1)
1pcL(S)
l1F(S)
fmedium(S;t);
undem(S;t)este num arul reprezentant ilor schemei ^ n generat ia P(t) ,leste
lungimea schemei, iar L(S) este lungimea sa util a.
Propozit ia 3.4 FieSo schem a de ordinul O(S) (cuO(S) pozit ii specice).
Probabilitatea qmca schema Ss a supraviet uiasc a aplic arii operatorului de mutat ie
este
qm= 1pmO(S);
undepmeste probabilitatea ca o pozit ie oarecare (o gena a) s a- si schimbe valoarea.

3.3. Teorema schemelor  si blocuri constructive 31
Vom considera acum efectul combinat al select iei, ^ ncruci s arii  si mutat iei. Cei
trei opeatori act ioneaz a independent. Probabilitatea de supraviet uire a schemei
este produsul probabilit at ilor de supraviet uire corespunz atoare celor trei opera-
tori, ce va satisface inegalitatea
m(S;t+ 1)m(S;t)F(S)
fmediu
1pcL(S)
l1
[1pmO(S)]
m(S;t+ 1)m(S;t)F(S)
fmediu
1pcL(S)
l1pmO(S) +pcpmL(S)
l1O(S)
Neglij^ and
pcpmL(S)
l1O(S);
obt inem urm atorul rezultat care reprezint a teorema schemelor (Holland,[4]):
Teorema 3.5 Admitem c a operatorii genetici utilizat i sunt select ia proport ional a,
^ ncruci sarea cu un punct de t aietur a  si mutat ia tare. Dinamica num arului de
reprezentant i ai unei scheme Seste caracterizat a de inegalitatea
m(S;t+ 1)m(S;t)F(S)
fmediu
1pcL(S)
l1pmO(S)
Se observ a c a o schem a are cu at^ at mai multe copii ^ n generat ia ( t+ 1) cu
c^ at ordinul ei este mai mic. Acest rezultat evident iaz a faptul c a fracvent a scurt a
a schemelor cu o performant  a peste medie  si cu ordin mic cre ste exponent ial ^ n
generat iile urm atoare.
Schemele care au o performant  a peste medie, ordin  si lungime util a mici,
se numesc blocuri constructive . Blocurile constructive sunt deci acele scheme care
se ^ nmult esc de-a lungul generat iilor.
Prin act iunea operatorilor genetici blocurile constructive se combin a pentru
a forma sub siruri tot mai mari  si cu performant e tot mai bune. ^In nal, acest
proces de combinare converge la solut ia optim a. Acest model este cunoscut ca
Ipoteza Blocurilor Constructive .
Recapitul^ and, putem evident ia principalele concluzii obt inute din teoria schemelor:
1. Conform teoriei schemelor, blocurile constructive vor avea o cre stere expo-
nent ial a ^ n urm atoarele generat ii.
2. Dac a o schem a are o performant  a sub medie, atunci num arul reprezentant ilor
ei ^ n generat iile urm atoare descre ste exponent ial.

3.3. Teorema schemelor  si blocuri constructive 32
3. Blocurile constructive  si combinat iile lor folosite pentru a forma sub siruri
utile tot mai lungi, reprezint a celmai important mecanisn de lucru al algo-
ritmilor genetici (Ipoteza blocurilor constructive).
4. Codicarea binar a evinent iaz a num arul mare de scheme prelucrate ^ n par-
alel de un algoritm genetic. Acest paralelism intrinsec poate  pus ^ n
leg atur a cu ecient a c aut arii  si cu viteza de convegent  a.

Capitolul 4
Aplicatii
Pentru a intelege modul ^ n care funct ioneaz a un algoritm genetic, voi pune ^ n
aplicare not iunile teoretice prezentate anterior ^ n crearea unei aplicat ii Matlab ce
determin a maximul unei funct ie cu o variabil a, mai apoi adapt^ and  si pentru o
funct ie cu dou a variabile.
4.1 Determinarea maximului unei funct ii de o
variabil a
Fie o funct ie f:D!R, unde domeniul de denit ie Dreprezint a un interval
[a;b] inclus ^ n R. Scopul aplicat iei este de a determina maximul global al funct iei
^ n domeniul Dcu o precizie pdat a de utilizator. Pentru acest lucru vom avea ^ n
vedere urm atoarele aspecte:
1.Alegerea datelor de intrare
Datele de intrare al aplicat iei vor :
ˆFunct iaf
ˆCapetele intervalului: a sib
ˆPreciziap
ˆNum arul de indivizi din populat ie n
ˆCondit ia de terminare a execut iei programului nriter
Aceasta const a^ n atingerea unui anumit num ar de generat ii (iteratii).
2.Generarea populat iei
Generarea populat iei init iale se face aleator^ n intervalul impus. Deoarece
aceast a populat ie va  format a din valori zecimale si doresc s a folosesc
codicarea binar a pe numere ^ ntregi, se scaleaz a intervalul dat la precizia la
care doresc sa a
u valoarea optim a. Deci populat ia va  aleas a ^ n intervalul
33

4.1. Determinarea maximului unei funct ii de o variabil a 34
scalat, urm^ and ca apoi s a se aleag a partea intreg a a valorii individului.
Acest lucru este aratat ^ n urm atoarea funct ie:
Algoritm 4.1: Generarea indivizilor in Matlab
1 function [ ind ]= G e n e r a r e i n d i v i z i ( n r i n d i v i z i , a1 , b1 )
2
3 ind=ze ro s (1 , n r i n d i v i z i ) ;
4 % rand (1 ,1) da o matrice cu o l i n i e s i o coloana a c a r e i
valoare
5 %se a f l a i n t r e 0 s i 1
6 % x=round ( a1+(b1 a1 ) *rand (1 , n) )
7 f o r i =1: n r i n d i v i z i
8 % x ( i )=numere a l e a t o a r e i n t r e a1 s i b1
9 ind ( i )=round ( a1+(b1 a1 ) *rand (1 ,1) ) ;
10 end
11 end
3.Maniera de codicare
^In acest sens am ales codicarea binar a, astfel ecare individ din
populat ia generat a anterior va  reprezentat printr-o secvent  a binar a de
lungimeL. Aceast a lungime se va determina conform relat iei 3.1 ^ n funct ie
de intervalul scalat conform urm atorului subalgoritm:
Algoritm 4.2: Determinarea luncimii cromozomilor in Matlab
1 function [ L]= Determinare lungime cromozomi ( a , b , p)
2 % determinam L( p o z i t i i l e binare ) , ca f i i n d c e l mai mic numar
natural
3 %a s t f e l i n c a t (b a ) *10^p <2^L
4 %unde p r e p r e z i n t a p r e c i z i a c o d i f i c a r i i
5 m=(ba ) *10^p ;
6 L=1;
7 while (m >2^L)
8 L=L+1;
9 end
10 L=L+1;
11 end
Astfel determin^ and lungimea secvent ei binare putem implementa codi-
carea binar a pentru populat ia init ial generata potrivit urm atorului subal-
goritm:
Algoritm 4.3: Codicarea binara in Matlab
1 function [ Matrice ]= Codificare Cx ( n r i n d i v i z i , Lungime crom , x )
2 % calculam cromozomii p o p u l a t i e i i n i t i a l e
3 % i i scriem intr o matrice C cu n l i n i i s i r coloane
4 %f i e c a r e l i n i e e s t e un cromozom
5
6 Matrice=ze ro s ( n r i n d i v i z i , Lungime crom ) ;

4.1. Determinarea maximului unei funct ii de o variabil a 35
7 f o r i =1: n r i n d i v i z i
8 % scriem pe l i n i a i pe x ( i ) in baza 2
9 aux=x ( i ) ;
10 j=Lungime crom ;
11 while ( aux >1)
12 Matrice ( i , j )=rem ( aux , 2 ) ;
13 aux=f l o o r ( aux /2) ;
14 j=j 1;
15 end
16 Matrice ( i , j )=aux ;
17 end
18 end
Operat ia invers a codic arii se nume ste decodicare  si este folosit a^ n ved-
erea observ arii populat iei ca num ar dup a ce am supus populat ia codicat a
la operat iile de select ie, ^ ncruci sare  si mutat ie.
Un astfel de subfunct ie este urm atoarea:
Algoritm 4.4: Decodicarea dicarea binara in Matlab
1 function P=d e c o d i f i c a r e b i n a r a ( Pbin , l , n)
2 P=z er os (1 , n) ;
3 f o r i =1:n
4 f o r j =1: l
5 P( i )=P( i ) +2^( l j ) *Pbin ( i , j ) ;
6 end
7 end
8 end
4.Alegerea funct iei de adecvare  si a operatorului de select ie
Alegerea funct iei de adecvare se face conform cerint ei problemei, adic a
de maximizare a funct iei. Deci cu c^ at functia are o valoare mai mare cu at^ at
aceasta va  aleas a pentru select ie. ^ n acest context, funct ia de adaptare
este ^ ns a si funct ia noastr a: fit(x) =f(x).
Algoritmul de select ie folosit este algoritmul Monte Carlo, cu deosebirea
c a acesta va cont ine ca variabil a de intrare  si populat ia decodicat a, pentru
a putea calcula valoarea funct iei de adaptare.
Algoritm 4.5: Algoritmul de selectie Monte Carlo
1 function [ P o p s e l e c t i e ]= s e l e c t i e ( nr crom , L crom , Pop decodificat
, Pop binara )
2
3 % F e s t e suma tuturor v a l o r i l o r f u n c t i e i de adaptare
4 F=0;
5 f u n c t i e a d a p t a r e=z er os (1 , nr crom ) ;
6 f o r i =1: nr crom
7 % f u n c t i a de adaptare pentru f i e c a r e cromozom
8 f u n c t i e a d a p t a r e ( i )=f ( P o p d e c o d i f i c a t ( i ) ) ;

4.1. Determinarea maximului unei funct ii de o variabil a 36
9 F=F+f u n c t i e a d a p t a r e ( i ) ;
10 end
11 %d i s p l a y (F)
12 % P r e p r e z i n t a p r o b a b i l i t a t e a de adaptare
13 % q r e p r e z i n t a p r o b a b i l i t a t e a cumulata
14 P=z er os (1 , nr crom ) ;
15 q=z er os (1 , nr crom ) ;
16 P(1)=f u n c t i e a d a p t a r e (1) /F;
17 q (1)=P(1) ;
18 f o r i =2: nr crom
19 P( i )=f u n c t i e a d a p t a r e ( i ) /F;
20 q ( i )=q ( i 1)+P( i ) ;
21 end
22 %d i s p l a y ( 'p r o b a b i l i t a t e a de adaptare ')
23 %d i s p l a y (P)
24 %d i s p l a y ( 'p r o b a b i l i t a t e a cumulata ')
25 %d i s p l a y ( q )
26
27 % se s e l e c t e a z a noua populatie
28 P o p s e l e c t i e=ze ro s ( nr crom , L crom ) ; % va c o l e c t a noua populatie
29 f o r j =1: nr crom
30 % se genereaza a l e a t o r g in i n t e r v a l u l [ 0 , 1 ]
31 g=rand (1 ,1) ;
32 i f g <=q (1)
33 % daca g din (0 ,1) e s t e mai mic decat q (1)
34 % atunci in noua matrice de cromozomi t r e c e primul
cromozom
35 % din matrice veche
36 P o p s e l e c t i e ( j , 1 : L crom )=Pop binara ( 1 , 1 : L crom ) ;
37 e l s e
38 % caut i a s t f e l i n c a t q ( i 1)<g<=q ( i )
39 i =2;
40 while ( g >q ( i ) ) && ( i <=nr crom ) % cauta primul cromozom
i cu g >q ( i )
41 i=i +1;
42 end
43 % cromozomul i e s t e t r e c u t in matricea noua de
cromozomi
44 P o p s e l e c t i e ( j , 1 : L crom )=Pop binara ( i , 1 : L crom ) ;
45 end
46 end
47 end
5. Alegerea operatorului de ^ ncruci sare
Pentru acest exemplu am decis s a folosesc ^ ncruci sarea cu un singur
punct de t aietur a. Nu tot i indivizii din populat ia selectat a vor  ^ ncruci sat i.
Ace stia vor  ale si cu ajutorul unei probabilit at i de ^ ncruci sare ce e dat de
utilizator.Una din inconvenient e ar  acela c a indivizii ce vor  introdu si
^ n operat ia de ^ ncruci sare s a e impari. ^In acest caz se va verica num arul
lor, iar daca sunt impari, se adaug a un individ ^ n ^ ncruci sare.

4.1. Determinarea maximului unei funct ii de o variabil a 37
La sfar situl ^ ncruci sarii se veric a dac a descendent ii populat iei selec-
tate se g asesc ^ n intervalul dat (intervalul scalat), deoarece populat ia se
degradeaz a tocmai prin faptul c a un individ nu corespunde unei condit ii.
^In situat ia ^ n care un descendent nu apart ine intervalului, acesta nu va face
parte di populat ia ^ ncruci sata  si se va p astra individul anterior.
Urm atorul subalgoritm ne reprezint a acest lucru:
Algoritm 4.6: Operatorul de incrucisare cu un punct de taietura
1 function Pop finala=i n c r u c i s a r e (n , L crom , P o p s e l e c t i e , a1 , b1 ,
valoare optima )
2 % p r o b a b i l i t a t e i n c r u c i s a r e
3 prob =0.5;
4 % n r c r o m i n c r u c i s a t = contor crom de i n c r u c i s a t
5 n r c r o m i n c r u c i s a t =0;
6 % matrice in care se t r e c cromozomii de i n c r u c i s a t
7 P o p u l a t i e d ei n c r u c i s a t=z e ro s (n , L crom ) ;
8 % p o z i t i e = r e t i n e l i n i i l e din matricea de cromozomi
care vor f i i n c r u c i s a t i
9 p o z i t i e=z er os (1 , n) ;
10 f o r i =1:n
11 % se genereaza a l e a t o r g in i n t e r v a l u l [ 0 , 1 ]
12 g=rand (1 ,1) ;
13 i f ( g <prob )
14 % retinem pentru i n c r u c i s a r e crom
CromSelectie ( i , 1 : l c )
15 n r c r o m i n c r u c i s a t=n r c r o m i n c r u c i s a t
+1;
16 P o p u l a t i e d ei n c r u c i s a t (
nrcrom incrucisat , 1 : L crom )=
P o p s e l e c t i e ( i , 1 : L crom ) ;
17 p o z i t i e ( i ) =1;
18 end
19 end
20 % noua populatie dupa s e l e c t i a pentru i n c r u c i s a r e
21 Pop finala=P o p s e l e c t i e ;
22
23 % testam daca a g a s i t cromozomi pentru i n c r u c i s a r e
24 i f ( n r c r o m i n c r u c i s a t ~=0)
25 % adaugam un cromozom daca n c i e s t e impar
26 % am generat random g pentru a adauga un
cromozom din populatia i n i t i a l a
27 i f rem ( nr crom incrucisat , 2 )==1 %n c i%2==1
28 g=round (1+(n 1) *rand (1 ,1) ) ;
29 n r c r o m i n c r u c i s a t=n r c r o m i n c r u c i s a t +1;
30 P o p u l a t i e d ei n c r u c i s a t ( nr crom incrucisat
, 1 : L crom )=P o p s e l e c t i e ( g , 1 : L crom ) ;
31 end
32 %d i s p l a y ( P o p u l a t i e d ei n c r u c i s a t )
33 %incrucisam cu un punct de t a i e t u r a k generat
random

4.1. Determinarea maximului unei funct ii de o variabil a 38
34 %perechi de cromozomi din P o p u l a t i e d ei n c r u c i s a t
35 P o p u l a t i e i n c r u c i s a t a=z er os ( nr crom incrucisat ,
Lcrom ) ;
36 %se vor i n c r u c i s a primul crromozom din prima jumatate a
P o p u l a t i e d ei n c r u c i s a t
37 %cu primul crromozom din a doua jumatate a
P o p u l a t i e d ei n c r u c i s a t
38 f o r i =1: n r c r o m i n c r u c i s a t /2
39 j=n r c r o m i n c r u c i s a t /2+ i ;
40 k=round (1+(L crom2) *rand (1 ,1) ) ;
41 P o p u l a t i e i n c r u c i s a t a ( i , 1 : k )=
P o p u l a t i e d ei n c r u c i s a t ( i , 1 : k ) ;
42 P o p u l a t i e i n c r u c i s a t a ( i , k : L crom )=
P o p u l a t i e d ei n c r u c i s a t ( j , k : L crom ) ;
43 P o p u l a t i e i n c r u c i s a t a ( j , 1 : k )=
P o p u l a t i e d ei n c r u c i s a t ( j , 1 : k ) ;
44 P o p u l a t i e i n c r u c i s a t a ( j , k : L crom )=
P o p u l a t i e i n c r u c i s a t a ( i , k : L crom ) ;
45 end
46
47 % se pun l a l o c cromozomii m o d i f i c a t i
48 %se vor v e r i f i c a daca se gasesc in i n t e r v a l u l dat
49 %daca sunt , i i vom introduce in Pop finala
50 %daca nu se gasesc in i n t e r v a l , nu i i vom introduce
51 contor =0;
52 f o r i =1:n
53 i f p o z i t i e ( i )==1
54 contor=contor +1;
55 %decodificam cromozomul pentru a vedea daca se
gasesc in
56 %i n t e r v a l
57 aux=f ( d e c o d i f i c a r e b i n a r a ( P o p s e l e c t i e ( i , 1 :
Lcrom ) , L crom , 1 ) ) ;
58 i n c r u c i s a t d e c o d i f i c a t=d e c o d i f i c a r e b i n a r a (
P o p u l a t i e i n c r u c i s a t a ( contor , 1 : L crom ) ,
Lcrom , 1 ) ;
59 %daca cromozomul i n c r u c i s a t se a f l a in i n t e r v a l
s i
60 %di s ta nt a d i n t r e valoarea optima s i descendent
e mai mica
61 %decat valoare optima s i parinte , atunci
descendentul se
62 %i n t o a r c e in populatia f i n a l a
63 i f ( ( a1 <=i n c r u c i s a t d e c o d i f i c a t ) && (
i n c r u c i s a t d e c o d i f i c a t <=b1 ) )
64 i f ( abs ( f ( i n c r u c i s a t d e c o d i f i c a t )
valoare optima ) <abs ( auxvaloare optima ) )
65 Pop finala ( i , 1 : L crom )=
P o p u l a t i e i n c r u c i s a t a ( contor , 1 : L crom ) ;
66 end
67 end
68 end

4.1. Determinarea maximului unei funct ii de o variabil a 39
69 end
70 e l s e
71 d i s p l a y ( 'n i c i un cromozom nu a f o s t s e l e c t a t pentru
i n c r u c i s a r e ')
72 end
73 end
6. Alegerea operatorului de mutat ie
Operatorul de mutat ie folosit este cel tare uniform. De asemenea se
va verica dac a cromozomul selectat se a
 a ^ n intervalul selectat  si dac a
distant a dintre valoarea optim a  si cromozomul mutat e mai mic a dec^ at
distant a dintre valoarea optim a  si cromozomul nemutat.
Algoritm 4.7: Operatorul de mutatie uniforma tare
1 function Pop mutata=mutatie (n , L crom , Pop incrucisata , a1 , b1 ,
valoare optima )
2 %prob = p r o b a b i l i t a t e a i n i t i a l a a m u t a t i i l o r
3 prob =0.3;
4 Pop mutata=Pop incrucisata ;
5 f o r i =1:n
6 f o r j =1:L crom
7 g=rand (1 ,1) ;
8 i f ( g <prob )
9 %daca e 0 , devine 1 ; daca e 1 , devine 0
10 Pop mutata ( i , j )=~Pop mutata ( i , j ) ;
11 %aux sa f i e egal cu f ( cromozom curent : pop mutata (
i , 1 : L crom )
12 aux=f ( d e c o d i f i c a r e b i n a r a ( Pop incrucisata ( i , 1 :
Lcrom ) , L crom , 1 ) ) ;
13 m ut a t d ec o d if i ca t=d e c o d i f i c a r e b i n a r a ( Pop mutata ( i
, 1 : L crom ) , L crom , 1 ) ;
14 %daca cromozomul mutat nu se a f l a in i n t e r v a l s i
15 %d i st a nt a d i n t r e valoarea optima s i i n d i v i d u l
nemutat e mai mica
16 %decat valoare optima s i i n d i v i d u l mutat , atunci
i n d i v i d u l mutat se
17 %i n t o a r c e l a valoarea i n i t i a l a
18 i f ~(( a1 <=m u ta t d ec o d if i ca t ) && ( mutat decodificat
<=b1 ) )
19 i f ( abs ( aux valoare optima ) <abs ( f (
m ut a t d ec o d if i c at )valoare optima ) )
20 Pop mutata ( i , j )=~Pop mutata ( i , j ) ;
21 end
22 end
23 end
24 end
25 end
26 end

4.1. Determinarea maximului unei funct ii de o variabil a 40
7. Elitismul
^In aceast a situat^ e, elitismul const a ^ n introducerea celui mai bun individ
din generat ia curent a pe prima pozit ie,doar dac a primul individ nu este cel
mai bun. Acest lucru se face pentru a nu pierde solut ii bune prin trecerea
de la o generat ie la alta.
Algoritm 4.8: Elitismul
1 %ELITISM
2 %se determina valoarea optima ( x optim , val optim ) din
g e n e r a t i a curenta
3 % primul i n d i v i d din g e n e r a t i a curenta se i n l o c u i e s t e cu
xoptim
4 x optim ( i +1)= x optim ( i ) ;
5 val optim ( i +1)=val optim ( i ) ;
6 f o r k=1: c a r d i n a l p o p u l a t i e
7 i f ( val optim ( i +1) <f ( P o p u l a t i e d e c o d i f i c a t a ( k ) /10^
p r e c i z i e ) )
8 x optim ( i +1)=P o p u l a t i e d e c o d i f i c a t a ( k ) /10^ p r e c i z i e ;
9 val optim ( i +1)=f ( x optim ( i +1) ) ;
10 end
11 end
12 Pop mutatie ( 1 , 1 : L)=c o d i f i c a r e b i n a r a ( x optim ( i +1) ,L , 1 ) ;
8. Implementarea algoritmului genetic
Fiind descri si subalgoritmii care realizeaz operat iile principale, putem
prezenta algoritmul genetic care rezolv a problema de maxim:
Algoritm 4.9: Algoritmul genetic pentru determinarea maximului unei func-
tii de o variabila
1 function maxim 1D ( )
2
3 c l o s e a l l ;
4 % Exemplu care determina maximul unei f u n c t i i pe un i n t e r v a l [ a
, b ] cu
5 % p r o b a b i l i t a t e a de c o d i f i c a r e p
6
7 %Alegem c a p e t e l e i n t e r v a l u l u i [ a , b ]
8 a=input ( 'valoarea minima a i n t e r v a l u l u i : a= ') ;
9 b=input ( 'valoarea maxima a i n t e r v a l u l u i : b= ') ;
10
11
12 % Setam o p r e c i z i e de c o d i f i c a r e p r e c i z pentru x ( s o l u t i e
p o t e n t i a l a )
13 p r e c i z i e=input ( 'p r e c i z i a (10^(p) ) : p r e c i z i e = ') ;
14
15
16 %i n t e r v a l [ a , b ] s c a l a t cu p r e c i z i a c o d i f i c a r i i a s t f e l i n c a t sa
nu avem v i r g u l e

4.1. Determinarea maximului unei funct ii de o variabil a 41
17 %( numerele zecimale devin i n t r e g i )
18 a1=a *10^ p r e c i z i e ;
19 b1=b *10^ p r e c i z i e ;
20
21 %determinare lungime cromozomi
22 L=lungime cromozomi ( a1 , b1 ) ;
23 d i s p l a y ( 'Lungimea cromozomului ')
24 d i s p l a y (L)
25
26 % c a r d i n a l p o p u l a t i e r e p r e z i n t a numarul de i n d i v i z i din
p o p u l a t i e i
27 c a r d i n a l p o p u l a t i e=input ( 'numarul de i n d i v i z i din populatie :
c a r d i n a l p o p u l a t i e = ') ;
28 %se generaza populatia i n i t i a l a i n t r e a1 s i b1
29 Populatie numere=g e n e r a r e p o p u l a t i e ( a1 , b1 , c a r d i n a l p o p u l a t i e ) ;
30 d i s p l a y ( 'Populatia i n i t i a l a ')
31 d i s p l a y ( Populatie numere )
32
33 %c o d i f i c a r e populatie in binar
34 Populatie binara=c o d i f i c a r e b i n a r a ( Populatie numere , L ,
c a r d i n a l p o p u l a t i e ) ;
35 d i s p l a y ( 'Populatia i n i t i a l a c o d i f i c a t a ')
36 d i s p l a y ( Populatie binara )
37
38 %t e s t d e c o d i f i c a r e
39 %t e s t=d e c o d i f i c a r e b i n a r a ( Populatie binara , L , c a r d i n a l p o p u l a t i e
) ;
40
41 % alegem numarul maximde g e n e r a t i i pe care o va parcurge
populatia
42 n r i t e r a t i i=input ( 'Numarul maxim de i t e r a t i i e s t e n r i t e r a t i i =
') ;
43
44 %determinarea s o l u t i e i optime i n i t i a l e
45 x optim=ze ro s (1 , n r i t e r a t i i +1) ;
46 val optim=z er os (1 , n r i t e r a t i i +1) ;
47
48 x optim (1)=Populatie numere (1) /10^ p r e c i z i e ;
49 val optim (1)=f ( x optim (1) ) ;
50 f o r i =2: c a r d i n a l p o p u l a t i e
51 i f ( val optim (1) <f ( Populatie numere ( i ) /10^ p r e c i z i e ) )
52 x optim (1)=Populatie numere ( i ) /10^ p r e c i z i e ;
53 val optim (1)=f ( x optim (1) ) ;
54 end
55 end
56
57 %se d e c o d i f i c a populatia , deoarece avem nevoie de v a l o r i l e e i
in s e l e c t i e
58 %( mai exact amen vevoie in f u n c t i a de adaptare )
59 P o p u l a t i e d e c o d i f i c a t a=d e c o d i f i c a r e b i n a r a ( Populatie binara , L ,
c a r d i n a l p o p u l a t i e ) ;
60 Pop mutatie=Populatie binara ;

4.1. Determinarea maximului unei funct ii de o variabil a 42
61
62 f o r i =1: n r i t e r a t i i
63 f p r i n t f ( 'Generatia curenta %d nn ', i )
64 P o p s e l e c t i e=s e l e c t i e ( c a r d i n a l p o p u l a t i e , L ,
P o p u l a t i e d e c o d i f i c a t a , Pop mutatie ) ;
65 % d e c o d i f i c a r e b i n a r a ( P o p s e l e c t i e , L , c a r d i n a l p o p u l a t i e )
66
67 P o p i n c r u c i s a r e=i n c r u c i s a r e ( c a r d i n a l p o p u l a t i e , L ,
P o p s e l e c t i e , a1 , b1 , val optim ( i ) ) ;
68 % d e c o d i f i c a r e b i n a r a ( Pop incrucisare , L , c a r d i n a l p o p u l a t i e )
69
70 Pop mutatie=mutatie ( c a r d i n a l p o p u l a t i e , L , Pop incrucisare , a1
, b1 , val optim ( i ) ) ;
71 %Pop mutatie=mutatie3a ( c a r d i n a l p o p u l a t i e , L , Pop incrucisare
, a1 , b1 , i , n r i t e r a t i i , val optim )
72 P o p u l a t i e d e c o d i f i c a t a=d e c o d i f i c a r e b i n a r a ( Pop mutatie , L ,
c a r d i n a l p o p u l a t i e ) ;
73 f p r i n t f ( 'Populatia de l a g e n e r a t i a %d nn ', i )
74 d i s p l a y ( P o p u l a t i e d e c o d i f i c a t a /10^ p r e c i z i e )
75
76
77 %ELITISM
78 %se determina valoarea optima ( x optim , val optim ) din
g e n e r a t i a curenta
79 % primul i n d i v i d din g e n e r a t i a curenta se i n l o c u i e s t e cu
xoptim
80 x optim ( i +1)= x optim ( i ) ;
81 val optim ( i +1)=val optim ( i ) ;
82 f o r k=1: c a r d i n a l p o p u l a t i e
83 i f ( val optim ( i +1) <f ( P o p u l a t i e d e c o d i f i c a t a ( k ) /10^
p r e c i z i e ) )
84 x optim ( i +1)=P o p u l a t i e d e c o d i f i c a t a ( k ) /10^ p r e c i z i e ;
85 val optim ( i +1)=f ( x optim ( i +1) ) ;
86 end
87 end
88 Pop mutatie ( 1 , 1 : L)=c o d i f i c a r e b i n a r a ( x optim ( i +1) ,L , 1 ) ;
89 end
90 end
9. Analiza rezultatelor
Pentru a pune ^ n evident  a performant a algoritmului genetic creat an-
terior, ^ l vom aplica asupra unor funct ii ce vor  ment ionate ^ n ceea ce
urmeaz a.
Ca prim exemplu, am ales funct ia de gradul 2: f(x) =x2+ 6
x1.
Acest a funct ie are un singur punct de maxim, deoarece f0(x) = 0 are o
singur a solut ie. Doresc s a g asesc valoarea maxim a cu o precizie de dou a
zecimale,p= 2 ^ n intervalul [ a;b] = [0;6]. Am ales ca populat ia s a cont in a
50 de indivizi, iar acest ia s a e modicat i ^ n 30 de iterat ii. ^In acest a situat ie
s-a g asit valoarea maxim a a funct iei aceata ind f(x) = 8, g asit a dup a 4

4.1. Determinarea maximului unei funct ii de o variabil a 43
iterayii, ^ n jurul punctului x= 3, acesta ind g asit dup a 19 iterat ii. A se
vedea Figurile 4.1  si 4.2 de mai jos:
Figura 4.1: G asirea valorii lui x dup a 19 iterat ii
Figura 4.2: G asirea valorii maxime a funct iei dup a 4 iterat ii
Dup a cum se observ a metoda converge rapid  si de duce c atre rezultatul
corect, deoarece avem o populat ie format a din mult i indivizi, deci este de

4.1. Determinarea maximului unei funct ii de o variabil a 44
a steptat ca solut ia optim a s a e g asit a repede. ^In Figura 4.3 am reprezentat
funct ia noastr a impreun a cu valoarile maxime g asite dup a ecare iterat ie.
Se observ a cum acestea se g asesc ^ n jurul maximului funct iei.
Figura 4.3: Reprezentarea valorilor optime g asite pentru funct ia f(x) =x2+ 6x1
Sunt situat ii ^ n care metoda converge prematur, adic a g aseste rezultatul
optim din populat ia generat a init ial, datorit a faptului c a s-au generat mult i
indivizi. Figurile 4.4  si 4.5 reprezint a acest lucru pentru acela si interval,
precizie, num ar de indivizi si iterat ii date ^ n exemplul anterior.
Figura 4.4: Reprezentarea convergent ie premature pentru valoarea punctului x

4.1. Determinarea maximului unei funct ii de o variabil a 45
Figura 4.5: Reprezentarea convergent ie premature pentru valoarea maxim a a funct iei
f(x) =x2+ 6x1
Pentru urm atorul exemplu am ales funct ia: f(x) = sinx+ cosx. Cum
aceasta este o funct ie periodic a, cu perioada T= 2, ea cont ine mai multe
maxime, numite maxime locale. Dorim s a g asim valoarile maxime cu o
precizie de dou a zecimale, p= 2 ^ n intervalul [ a;b] = [0;18]. Populat ia va
cont ine 100 de indivizi, iar acest ia vor  modicat i ^ n 50 de iterat ii. A se
vedea Figurile 4.1  si 4.2 de mai jos:
Figura 4.6: Reprezentarea valorii optime a lui x ^ n funct ie de num arul de iterat ii

4.1. Determinarea maximului unei funct ii de o variabil a 46
Figura 4.7: Reprezentarea valorii maxime a funct iei f(x) = sin x+ cos xdup a un
anumit num ar de iterat ii
^In aceste circumstant e, maximul funct iei a fost atins ^ n jurul valorii
f(x) = 1:4142, ^ n jurul punctului x= 13;36 ^ n primele 5 iterat ii, x= 0:7936
de la iterat ia 6, x= 7:07 de la iterat ia 23  si x= 13;3506 de la iterat ia 40.
Figura 4.8: Reprezentarea valorii maxime a funct iei f(x) = sin x+ cos x

4.2. Determinarea maximului unei funct ii de dou a variabile 47
4.2 Determinarea maximului unei funct ii de dou a
variabile
Fie o funct ie f:DD!R, undeDreprezint a un interval [ a;b] inclus ^ n
R. Scopul aplicat iei este de a determina maximul global al funct iei ^ n domeniul
DDcu o precizie pdat a de utilizator.
Modul de implementare al algoritmului genetic pentu a
area maximului funct iei
cu dou a variabile este inspirat din algoritmul genetic pentru o funct ie cu o vari-
abil a  si are urm atoarele elemente distincte:
ˆIndividul este format dintr-o pereche ( x;y), reprezent^ and pozit ia individului
^ n domeniul DD.
ˆPrincipiul de select ie const a ^ n alegerea perechii ( x;y)  si nu a elementelor
individual.
Operatorii de ^ ncruci sare  si mutat ie sunt la fel ca cei din Algoritmul 4.6  si 4.7.
Deci algoritmul genetic pentru a
area maximului unei funct ii cu dou a variabile
arat a ^ n felul urm ator:
Algoritm 4.10: Algoritmul genetic pentru determinarea maximului unei functii
de doua variabile
1 function maxim 2D ( )
2
3 c l o s e a l l ;
4 % Exemplu care determina maximul unei f u n c t i i de 2 v a r i a b i l e pe [ a , b
] x [ a , b ] cu
5 % p r o b a b i l i t a t e a de c o d i f i c a r e p
6
7 %Alegem c a p e t e l e i n t e r v a l u l u i [ a , b ]
8 a=input ( 'valoarea minima a i n t e r v a l u l u i : a= ') ;
9 b=input ( 'valoarea maxima a i n t e r v a l u l u i : b= ') ;
10
11 % Setam o p r e c i z i e de c o d i f i c a r e p r e c i z pentru x ( s o l u t i e p o t e n t i a l a
)
12 p r e c i z i e=input ( 'p r e c i z i a (10^(p) ) : p r e c i z i e = ') ;
13
14
15 %i n t e r v a l [ a , b ] s c a l a t cu p r e c i z i a c o d i f i c a r i i a s t f e l i n c a t sa nu
avem v i r g u l e
16 %( numerele zecimale devin i n t r e g i )
17 a1=a *10^ p r e c i z i e ;
18 b1=b *10^ p r e c i z i e ;
19
20 %determinare lungime cromozomi
21 L=lungime cromozomi ( a1 , b1 ) ;
22 d i s p l a y ( 'Lungimea cromozomului ')
23 d i s p l a y (L)

4.2. Determinarea maximului unei funct ii de dou a variabile 48
24
25 % c a r d i n a l p o p u l a t i e r e p r e z i n t a numarul de i n d i v i z i din p o p u l a t i e i
26 c a r d i n a l p o p u l a t i e=input ( 'numarul de i n d i v i z i din populatie :
c a r d i n a l p o p u l a t i e = ') ;
27 %se generaza populatia i n i t i a l a i n t r e a1 s i b1
28 Populatie numere x=g e n e r a r e p o p u l a t i e ( a1 , b1 , c a r d i n a l p o p u l a t i e ) ;
29 Populatie numere y=g e n e r a r e p o p u l a t i e ( a1 , b1 , c a r d i n a l p o p u l a t i e ) ;
30 d i s p l a y ( 'Populatia i n i t i a l a ')
31 d i s p l a y ( Populatie numere x )
32 d i s p l a y ( Populatie numere y )
33
34 %c o d i f i c a r e populatie in binar
35 Populatie binara x=c o d i f i c a r e b i n a r a ( Populatie numere x , L ,
c a r d i n a l p o p u l a t i e ) ;
36 Populatie binara y=c o d i f i c a r e b i n a r a ( Populatie numere y , L ,
c a r d i n a l p o p u l a t i e ) ;
37 d i s p l a y ( 'Populatia i n i t i a l a c o d i f i c a t a ')
38 d i s p l a y ( Populatie binara x )
39 d i s p l a y ( Populatie binara y )
40
41 %t e s t d e c o d i f i c a r e
42 %t e s t=d e c o d i f i c a r e b i n a r a ( Populatie binara , L , c a r d i n a l p o p u l a t i e ) ;
43
44 % alegem numarul maximde g e n e r a t i i pe care o va parcurge populatia
45 n r i t e r a t i i=input ( 'Numarul maxim de i t e r a t i i e s t e n r i t e r a t i i = ') ;
46
47 %determinarea s o l u t i e i optime i n i t i a l e
48 x optim=ze ro s (1 , n r i t e r a t i i +1) ;
49 y optim=ze ro s (1 , n r i t e r a t i i +1) ;
50 val optim=z er os (1 , n r i t e r a t i i +1) ;
51
52 x optim (1)=Populatie numere x (1) /10^ p r e c i z i e ;
53 y optim (1)=Populatie numere y (1) /10^ p r e c i z i e ;
54 val optim (1)=f ( x optim (1) , y optim (1) ) ;
55 f o r i =2: c a r d i n a l p o p u l a t i e
56 i f ( val optim (1) <f ( Populatie numere x ( i ) /10^ p r e c i z i e , …
57 Populatie numere y ( i ) /10^ p r e c i z i e ) )
58 x optim (1)=Populatie numere x ( i ) /10^ p r e c i z i e ;
59 y optim (1)=Populatie numere y ( i ) /10^ p r e c i z i e ;
60 val optim (1)=f ( x optim (1) , y optim (1) ) ;
61 end
62 end
63
64 %se d e c o d i f i c a populatia , deoarece avem nevoie de v a l o r i l e e i in
s e l e c t i e
65 %( mai exact amen vevoie in f u n c t i a de adaptare )
66 P o p u l a t i e d e c o d i f i c a t a x=d e c o d i f i c a r e b i n a r a ( Populatie binara x , L ,
c a r d i n a l p o p u l a t i e ) ;
67 P o p u l a t i e d e c o d i f i c a t a y=d e c o d i f i c a r e b i n a r a ( Populatie binara y , L ,
c a r d i n a l p o p u l a t i e ) ;
68 Pop mutatie x=Populatie binara x ;
69 Pop mutatie y=Populatie binara y ;

4.2. Determinarea maximului unei funct ii de dou a variabile 49
70
71 f o r i =1: n r i t e r a t i i
72 f p r i n t f ( 'Generatia curenta %d nn ', i )
73 [ P o p s e l e c t i e x , P o p s e l e c t i e y ]= s e l e c t i e ( c a r d i n a l p o p u l a t i e , L , …
74 P o p u l a t i e d e c o d i f i c a t a x , P o p u l a t i e d e c o d i f i c a t a y ,
Pop mutatie x , Pop mutatie y ) ;
75 % d e c o d i f i c a r e b i n a r a ( P o p s e l e c t i e , L , c a r d i n a l p o p u l a t i e )
76
77 [ Pop incrucisare x , P o p i n c r u c i s a r e y ]= i n c r u c i s a r e (
c a r d i n a l p o p u l a t i e , …
78 L , P o p s e l e c t i e x , P o p s e l e c t i e y , a1 , b1 , val optim ( i ) ) ;
79 % d e c o d i f i c a r e b i n a r a ( Pop incrucisare , L , c a r d i n a l p o p u l a t i e )
80
81 [ Pop mutatie x , Pop mutatie y ]= mutatie ( c a r d i n a l p o p u l a t i e , …
82 L , Pop incrucisare x , Pop incrucisare y , a1 , b1 , val optim ( i ) ) ;
83 %Pop mutatie x=mutatie ( c a r d i n a l p o p u l a t i e , L , Pop incrucisare x , a1
, b1 , i ) ;
84 %Pop mutatie y=mutatie ( c a r d i n a l p o p u l a t i e , L , Pop incrucisare y , a1
, b1 , i ) ;
85 P o p u l a t i e d e c o d i f i c a t a x=d e c o d i f i c a r e b i n a r a ( Pop mutatie x , L ,
c a r d i n a l p o p u l a t i e ) ;
86 P o p u l a t i e d e c o d i f i c a t a y=d e c o d i f i c a r e b i n a r a ( Pop mutatie y , L ,
c a r d i n a l p o p u l a t i e ) ;
87 f p r i n t f ( 'Populatia de l a g e n e r a t i a %d nn ', i )
88 d i s p l a y ( P o p u l a t i e d e c o d i f i c a t a x /10^ p r e c i z i e )
89 d i s p l a y ( P o p u l a t i e d e c o d i f i c a t a y /10^ p r e c i z i e )
90
91 %ELITISM
92 %se determina valoarea optima ( x optim , val optim ) din
g e n e r a t i a curenta
93 % primul i n d i v i d din g e n e r a t i a curenta se i n l o c u i e s t e cu
xoptim
94 x optim ( i +1)= x optim ( i ) ;
95 y optim ( i +1)=y optim ( i ) ;
96 val optim ( i +1)=val optim ( i ) ;
97 f o r k=1: c a r d i n a l p o p u l a t i e
98 i f ( val optim ( i +1) <f ( P o p u l a t i e d e c o d i f i c a t a x ( k ) /(10^
p r e c i z i e ) ,…
99 P o p u l a t i e d e c o d i f i c a t a y ( k ) /(10^ p r e c i z i e ) ) )
100 x optim ( i +1)=P o p u l a t i e d e c o d i f i c a t a x ( k ) /10^ p r e c i z i e ;
101 y optim ( i +1)=P o p u l a t i e d e c o d i f i c a t a y ( k ) /10^ p r e c i z i e ;
102 val optim ( i +1)=f ( x optim ( i +1) , y optim ( i +1) ) ;
103 end
104 end
105 Pop mutatie x ( 1 , 1 : L)=c o d i f i c a r e b i n a r a ( x optim ( i +1) ,L , 1 ) ;
106 Pop mutatie y ( 1 , 1 : L)=c o d i f i c a r e b i n a r a ( y optim ( i +1) ,L , 1 ) ;
107 end
Analiza rezultatelor
Pentru acest caz lu am funct ia f(x;y) =(x1)2(y2)2+9. Maximul funct iei
se va c auta ^ n domeniul [0 ;6][0;6], rezultatul av^ and precizia de dou a zecimale.

4.2. Determinarea maximului unei funct ii de dou a variabile 50
Se vor genera 100 de indivizi, iar programul va rula pentru 50 de iterat ii.

Concluzii
51

Bibliografie 52

Bibliograe
[1] M. Breab an, H. Luchian , Algoritmi genetici ,
http://students.info.uaic.ro/ ~vladut.ungureanu/
Algoritmi-genetici-ID.pdf
[2] D. Dumitrescu, Algoritmi genetici  si strategii evolutive – aplicat ii ^ n
Inteligent a Articial a  si ^ n domenii conexe , Editura Albastr a, 2006.
[3] D. E. Goldberg Genetic Algorithms in Search, Optimization and Machine
Learning ,Addison Wesley Publishing Company, 1989: 1-82.
http://www2.fiit.stuba.sk/ ~kvasnicka/Free\%20books/Goldberg_
Genetic_Algorithms_in_Search.pdf ,
[4] J. Holland Adaptation in Natural and Articial Systems ,The University of
Michigan Press, 1992
https://books.google.ro/books?hl=en&lr=&id=5EgGaBkwvWcC&
oi=fnd&pg=PR7&dq=holland+j+h+1975+adaptation+in+natural+
and+artificial+systems+pdf+free&ots=mIhq6_Kjuj&sig=
C2XQqGpLsaooKOVlt2Pglnc3vdk&redir_esc=y#v=onepage&q=holland\
%20j\%20h\%201975\%20adaptation\%20in\%20natural\%20and\
%20artificial\%20systems\%20pdf\%20free&f=false .
[5] Z. Michalawicz, Genetic Algorithms + Data Structes = Evolution Programs ,
Springer Verlag, Berlin, 1992.
http://web.ist.utl.pt/adriano.simoes/tese/referencias/
Michalewicz\%20Z.\%20Genetic\%20Algorithms\%20+\%20Data\
%20Structures\%20=\%20Evolution\%20Programs\%20(3ed).PDF .
[6] C. Rotar, Modele naturale  si Algoritmi Evolutivi , Editura Accent, 2008.

%9Fi-Algoritmi-Evolutivi
[7] C. Stoean, inf.ucv.ro/documents/cstoean/c6/A_14.pdf
[8]Algoritmi Genetici. Studiu de caz: Optimizarea tracului intr-o retea :
http://www.scritub.com/stiinta/informatica/retele/
Algoritmi-Genetici-Studiu-de-c24232.php .
53

BIBLIOGRAFIE 54
[9]Algoritmi Genetici: Capitolul 15 :https://olidej.wikispaces.com/
file/view/1115+Algoritmi+genetici.pdf .