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

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 Elitism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Strucutura general a unui algoritm evolutiv . . . . . . . . . . . . . . . 5
1.5 Denirea algoritmului genetic . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Caracteristicile unui algoritm genetic . . . . . . . . . . . . . . . . . . 8
1.7 Structura algoritmului genetic . . . . . . . . . . . . . . . . . . . . . . 9
2 Operatori genetici 10
2.1 Select ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Select ia proport ional a . . . . . . . . . . . . . . . . . . . . . . 10
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 . . . . . . . 17
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 . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 Mutat ia slab a . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Scheme constructive a unui algoritm genetic 23
3.1 Codicarea binar a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Codicarea binar a ^ n spat iul de c autare unidimensional . . . 23
3.1.2 Codicarea binar a ^ n spat iul de c autare multidimensional . . 25
3.2 Scheme  si not iuni conexe . . . . . . . . . . . . . . . . . . . . . . . . . 25
1

Cuprins 2
3.3 Teorema schemelor  si blocuri constructive . . . . . . . . . . . . . . . 27
4 Aplicatii 30
4.1 Determinarea maximului unei funct ii de o variabil a . . . . . . . . . . 30
4.2 Determinarea maximului unei funct ii de dou a variabile . . . . . . . . 46
Concluzii 55
Index 55
Bibliograe 57

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 algoritmilor
evolutivi este aceea c a se inspir a din teoria evolut iei speciilor  si se aplic a^ n rezolvarea
problemelor de optimizare. Un algoritm genetic ofer a prin iterat ii o solut ie apropiat a
de optim cu o eroare destul de mic a.
Cel care a ^ nceput s a dezvolte acest domeniu a fost John Holland ^ n lucrarea sa
"Adaptation in Natural and Articial Systems" ([4]), ca mai apoi s a e urmat de
c atre David Goldberg ^ n lucrarea sa "Genetic algorithms in search, optimization,
and machine learning"([3]).
Ca aplicat ii practice, algoritmii genetici sunt cel mai adesea utilizat i^ n rezolvarea
problemelor de optimizare  si c autare ^ n domenii ca de exemplu:
ˆ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  si 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).
Tema lucr arii e interesant a prin gradul de modernitate a folosirii algoritmilor
genetici  si prin faptul  a aplic a ideea de evolut ie din biologie ^ n rezolvarea unor
probleme de optim.
Lucrarea mea este format a din 4 capitole ce cont in urm atoarele:
1

Introducere 2
ˆ^In Capitolul 1 este introdus a not iunea de algoritmi evolutivi, preciz^ and stuc-
tura unui algoritmul evolutiv, ca mai apoi s a particulariz am algoritmii evolu-
tivi la algoritmii genetici, mention^ and caracteristicile unui algoritm genetic  si
stabilind o structur a general a a algoritmului genetic.
ˆ^In Capitolul 2 sunt precizat i operatorii principali ce sunt folosit i ^ n imple-
mentarea unui algoritm genetic. Descriem ce elemetele intr a ^ n alc atuirea lor
 si sunt prezentat i 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 originale ^ n aceast a lucrarea,
aceea de a implementa un algoritm genetic pentru a
area maximului unei
funct ii de o variabil a, respectiv de 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 algo-
ritmi: 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 unitatea de informat ie a cromozomului. 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 ge-
netic este condus a de dou a 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 numele de p arinte iar cromo-
zomul 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 urm atoare. Gradul de adaptare la mediu al indivizilor este m asurat de
funct ia tness obt inut a pornind de la funct ie matematic a de optimizat. ^Incruci sarea
(recombinarea) are ca scop schimbul de informat ie genetic a ^ ntre doi sau mai mult i
3

1.2. Explorare  si exploatare 4
cromozomi  si mutat ia care const a ^ n modicarea aleatoare a unei gene. Solut ia re-
turnat 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 deoarece sunt apli-
cabile unor clase largi de probleme. Pentru a putea  abordat a cu aceste tehnici,
problema de rezolvat trebuie pus a 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 algoritmului de a con-
verge (tinde) ^ nspre puncte optime. Reciproc, exploatarea accentuat a a zonelor de
interes reduce capacitatea de exporare ecient a a spat iilor solut iilor posibile, respec-
tiv capacitatea algoritmului de a descoperi  si alte zone promit  atoare.
O alt a interpretare a echilibrului explorare-exploatare poate  prezentat a de
dou a concepte specice problematicii algoritmilor evolutivi, respectiv convergent a  si
diversitatea populat iei. Explorarea ecient a a spat iului de c autare se interpreteaz a
printr-un grad ridicat al diversit at ii populat iei,pe c^ and exploatarea intens a a teri-
toriilor bune ale spat iului de c autare se reprezint a prin convergent a populat iei ^ nspre
solut iile optime([3],[6]).
Deci obt inerea unui echilibru ^ ntre explorare  si exploatare este indicat a pentru
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 Elitism
^In procesul evolut iei populat iei, indivizi performant i din generat iile intermedi-
are ar putea  pierdut i ^ n urma aplic arii operatorilor genetici specici (^ ncruci sare,
mutat ie). Acest fenomen nu este de dorit, deoarece procesul de convergent  a a
populat iei ^ nspre solut ia optim a este ^ ncetinit.

1.4. Strucutura general a unui algoritm evolutiv 5
Pentru a nu se pierde solut ii bune prin trecerea de la o generat ie la alta, algorit-
mul poate  suplimentat printr-o form a de elitism ([6]).
Cea mai simpl a manier a de implementare a elitismului este aceea de a transfera
nemodicat i cei mai buni indivizi al generat iei curente ^ n noua generat ie.
O alt a form a de elitism o reprezint a aceea prin care nu se permite ca p arint i
performant i s a e ^ nlocuit i ^ n noua generat ie de c atre descendent i proprii mai slabi.
Implementarea acestei forme de elitism are un dezavantaz. Acesta duce la un grad
de explorare a spat iului de c autare mic. Avantajul const a prin faptul c a nu este
permis a ^ ndep artarea populat iei curente de zonele dovedite deja a  favorabile.
1.4 Strucutura general a unui algoritm evolutiv
O procedur a evolutiv a e alc atuit a 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)
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 metod 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.

1.5. Denirea algoritmului genetic 6
^In acest caz putem formula o structura a algoritmului evolutiv ([2]):
Pseudocod 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.5 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 op-
eratori precum select ia , ^ ncruci sarea  si mutat ia. 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 indivizilor populat iei
curente, fapt care asigur a convergent a algoritmului ^ nspre solut iile reale ale proble-
mei considerate. Crearea unui algoritm genetic de rezolvare a unei probleme concrete
presupune evident ierea urm atoarelor componente ([3],[1]):

1.5. Denirea algoritmului genetic 7
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);
unde ai2A;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 sta-
bilim la ^ nceput  si reprezint a un parametru important al algoritmului dez-
voltat. O astfel de populaie se descrie astfel:
P(t) =fc1(t);


; cn(t)g;
unde cmreprezint 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.
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.

1.6. Caracteristicile unui algoritm genetic 8
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 pentru
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.6 Caracteristicile unui algoritm genetic
Urm atoarele caracteristici prezint a anumite particularit at i ale acestora comparativ
cu alte metode de c autare  si optimizare. Acestea sunt:
1. Cromozomii utilizat i au lungime constant a.
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 ante-
rioare P(t).
3. Algoritmii genetici ment in o populat ie constant a P(t) de indivizi la ecare
iterat ie t.
4. Algoritmii genetici pot g asi solut ii optime (sau aproape optime) cu o mare
probabilitate.

1.7. Structura algoritmului genetic 9
1.7 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 caracteristicile
precizate anterior. ^In acest caz, structura algoritmului genetic fundamental este ([2],
[8], [6]):
Pseudocod 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)=Selectie P(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 ie PR(t)
t=t+ 1;
sf^ ar sit c^ at timp
sf^ ar sit funct ie

1.7. Structura algoritmului genetic 10

Capitolul 2
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.
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 val-
oarea 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
curent a t.
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 cromozomilor.
10

2.1. Select ia 11
Aceast a funct ie re
ect a calitatea cromozomilor.
Funct ia de evaluare (adecvare) fittrebuie s a^ ndeplineasc a urm atoarele cerint e([2]):
funct ia fittrebuie s a e pozitiv a: fit(c)>0;8c2P(t):
dac a fitare  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)(2.1)
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 indi-
vizilor, 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 ia ni=n
pi, respectiv:
ni=n
fi
nP
i=1fi=n
fit(ci)
nP
i=1fit(ci)=fit(ci)
fitmediu (ci); (2.2)
unde fitmediu (ci)este performat a medie a populat iei.([6])

2.1. Select ia 12
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
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 ([2]):
Pseudocod 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
pentru i= 1lanexecut a
f(c(i) reprezint a funct ia de adaptare
F=F+f(c(i));
sf^ ar sit pentru
Calcul am probabilitatea de select ie conform denit iei 2.2
pentru i= 1lanexecut a
p(i)=f(c(i))/F;
sf^ ar sit pentru
pentru i= 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
pentru i= 1lanexecut a
g=rand(0,1);
dac a g < 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

2.1. Select ia 13
4. Avantaje  si dezavantaje ale select iei proport ionale
Avantajul utiliz arii select iei proport ionale ^ ntr-un algoritm genetic este capac-
itatea acestei a de a favoriza exploatarea indivizilor performant i ai populat iei.
Dezavantajul select iei poate  ^ nt^ alnit ^ n 2 situat ii([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:
Figura 2.1: Reprezentarea sectoarelor ruletei pentru situat ia 1
^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
apropiate.
^In acest caz ruleta arat a ca ^ n gura 2.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.

2.1. Select ia 14
Figura 2.2: Reprezentarea sectoarelor ruletei pentru situat ia 2
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).
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, unde a sibsunt
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, unde n 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
individ cial 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.

2.1. Select ia 15
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 aduce 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  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.
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
 sircromozomi 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 rdescendent i ai
celor rp arint i selectat i. De ment ionat c a ecare cromozom selectat 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 ^ n P3. ^ 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,deoarece
^ n cazul select iei nestandard, operatorul de mutat ie se aplic a unui cromozom ^ 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 16
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 segmentelor
de cromozomi corespunz^ and p arint ilor, asfel obt in^ andu-se noi indivizi, numit i des-
cendent 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
^ 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:

2.2. ^Incruci sarea 17
Figura 2.4: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu un punct de t aietur a
Astfel algoritmul penru ^ ncruci sarea cu un punct de t aietur a este urm atorul ([6]):
Pseudocod 4 ^Incruci sare printr-un punct de t aietur a
funct ie ^Incrucis are1Punct (c1; c2)
Se aleg doi p arint i: c1= (a1; a2; :::; a n) sic2= (b1; b2; :::; b n)
Se genereaz a aleator puncul de t aietur a
fkg2f1;2; :::;ng
pentru i= 1lakexecut a
Se creaz a cei doi descendent i, ce vor  de forma:
d1= (x1; :::; x n) sid2= (y1; :::; y n)
xi=ai
yi=bi
sf^ ar sit pentru
pentru i=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-b
gene 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

2.2. ^Incruci sarea 18
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:
Figura 2.6: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu doua puncte de
t aietur a
Algoritmul pentru ^ ncruci sarea cu dou a puncte de t aietur a este prezentat ^ n ceea
ce urmeaz a ([6]):
Pseudocod 5 ^Incruci sare prin 2 puncte de t aietur a
funct ie ^Incrucis are2Puncte (c1; c2)
Se aleg doi p arint i: c1= (a1; a2; :::; a n) sic2= (b1; b2; :::; b n)
Se genereaz a aleator cele dou a puncte de t aietur a
fk;tg2f1;2; :::;ng
dac a t < k atunci
interschimb a (k; t)
sf^ ar sit dac a
pentru i= 1lakexecut a
xi=ai
yi=bi
sf^ ar sit pentru
pentru i=k+ 1latexecut a
xi=bi
yi=ai
sf^ ar sit pentru
pentru i=t+ 1lanexecut a
xi=ai
yi=bi
sf^ ar sit pentru
sf^ ar sit funct ie

2.2. ^Incruci sarea 19
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 aplicarea
acestui operator de ^ ncruci sare cu un num ar mare de puncte de t aietur a ^ ncetine ste
convergent a populat iei ^ nspre solut ia global a.
^In practic a este preferat a varianta cu 2 t aieturi sau o variant a a operatorului
cu t aieturi multiple ^ n care num arul acestora este variabil (generat aleator)  si nu
prexat ca un parametru al algoritmului.
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 operatorul
de ^ ncruci sare ^ n cinci puncte de t aietur a.Punctele se a
a pe pozit iile m1= 1,m2=
2,m3= 4,m4= 5  si m5= 7.
Ace stia sunt reprezentat i ^ n gura 2.7.
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 ca ^ n gura 2.8.
Figura 2.8: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu cinci puncte de
t aietur a

2.2. ^Incruci sarea 20
Algoritmul penru ^ ncruci sarea cu mai multe puncte de t aietur a arat a ^ n felul
urm ator: ([6]):
Pseudocod 6 ^Incruci sare prin M puncte de t aietur a
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
pentru i= 1lam1execut a
pentru j= 1lamexecut a
dac a kj< kiatunci
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)
pentru i= 1lak1execut a
xi=ai
yi=bi
sf^ ar sit pentru
pentru i= 1lam1execut a
pentru j= 1lati+1execut a
dac a i 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
pentru i=kmlanexecut a
dac a m 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
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 combate
efectul de convergent  a prematur a a populat iei. Fie prin aplicarea unei presiuni 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]).
^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: (2.3)
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.

2.3. Mutat ia 22
Pseudocod 7 Mutat ia uniform a tare
funct ie MutatiaUniform aTare (c; d)
pm2[0;1] .init ializare probabilitatea de mutat ie
pentru i= 1lanexecut a
Genereaz a aleator k2[0;1]
dac a k < 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 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:
Pseudocod 8 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
pentru i= 1lanexecut a
Genereaz a aleator k2[0;1]
dac a k < p matunci
Genereaz a aleator t2[0;1]
dac a t < 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

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. Comportarea
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 algoritmilor 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 cromo-
zomi av^ and anumite pozit ii identice. Mai bine spus, similarit atile dintre cromozomi
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 unidimensional
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 ([6]).
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 s.
Domeniul Dreprezint a un interval D= [x; y],x siyreprezint a limitele lui D.
23

3.1. Codicarea binar a 24
Pentru a obt ine secvent a din codicarea binar a a cromozomului c, se aplic a
funct ia Cce 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 8cifre
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
valorii s0, apoi se aplic a transformarea invers a:
C1(s0) =s0
(yx) +x
pentru a obt ine s2[x; y].
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
valoarea s0= 0;244140625 , ca mai apoi s a se aplice transformarea C1luis0:
C1(s0) =s0
(83) + 3 = 0 ;244
5 + 3 = 4 ;22:

3.2. Scheme  si not iuni conexe 25
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 multidimensional
^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;unde D=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 cromozomul
c2P(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 prece-
dent
c= (c1; c2; :::; c k)
3.2 Scheme  si not iuni conexe
Pentru aceasta vom deni urm atoarele not iuni ([2]).
Denit ia 3.1 O schem a de lungime reste un element al mult imii f0;1;gr.
Denit ia 3.2 FieSo schem a de lungime r. Spunem c a un cromozom x2f0;1gr
este 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.

3.2. Scheme  si not iuni conexe 26
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 Schema S1= ( )reprezint a tot i cromozomii de lungime 5.
Schema S2= (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);
S3= (0 1);
S4= (1 0 1) :
S5= (1 0);
S6= (11);
S7= (1 );
S8= (0):

3.3. Teorema schemelor  si blocuri constructive 27
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 anu-
mite scheme.
Propozit ia 3.1 Fiecare schem a Sreprezint a 2n, unde neste num arul simbolurilor
*(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 per-
formant 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 );
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;

3.3. Teorema schemelor  si blocuri constructive 28
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 propor-
t 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(3.2)
reprezentant i ai schemei S^ n generat ia P(t+1) , iar fmediu 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 ^ ncru-
ci sare cu un singur punct de t aietur a. Fie pcprobabilitatea de aplicare a ^ ncruci s arii.
Num arul m(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); (3.3)
unde m(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). Prob-
abilitatea qmca schema Ss a supraviet uiasc a aplic arii operatorului de mutat ie este
qm= 1pmO(S);
unde pmeste probabilitatea ca o pozit ie oarecare (o gena a) s a- si schimbe valoarea.
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 operatori, ce va
satisface inegalitatea([2])
m(S; t+ 1)m(S; t)F(S)
fmediu
1pcL(S)
l1
[1pmO(S)] (3.4)
m(S; t+ 1)m(S; t)F(S)
fmediu
1pcL(S)
l1pmO(S) +pcpmL(S)
l1O(S)
(3.5)
 si neglij^ and
pcpmL(S)
l1O(S); (3.6)
obt inem urm atorul rezultat care reprezint a teorema schemelor (Holland,[4]):

3.3. Teorema schemelor  si blocuri constructive 29
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)
(3.7)
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 ([2]). 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.
Recapitul^ and, putem evident ia principalele concluzii obt inute din teoria schemelor
([4], [2]):
1. Conform teoriei schemelor, blocurile constructive vor avea o cre stere exponen-
t 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. Blocurile constructive  si combinat iile lor folosite pentru a forma sub siruri utile
tot mai lungi, reprezint a celmai important mecanisn de lucru al algoritmilor
genetici (Ipoteza blocurilor constructive).
4. Codicarea binar a evinent iaz a num arul mare de scheme prelucrate ^ n paralel
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.

3.3. Teorema schemelor  si blocuri constructive 30

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 de o variabil a, mai apoi adapt^ and  si pentru o funct ie
de 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 ia f
ˆCapetele intervalului: a sib
ˆPrecizia p
ˆNum arul de indivizi din populat ie n
ˆCondit ia de terminare a execut iei programului. Aceasta const a ^ n atin-
gerea 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 sca-
lat, urm^ and ca apoi s a se aleag a partea intreg a a valorii individului. Dup a
ce a fost generat a populat ia init ial a se caut a solut ia optim a pentru generat ia
30

4.1. Determinarea maximului unei funct ii de o variabil a 31
respectiva. Aceasta ne va ajuta mai t^ arziu la implimetarea elitismului. Acest
lucru este ar atat ^ n Algoritmul 4.1:
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 % se genereaza un vector in care vor f i pusi i n d i v i z i i
3 ind=zeros (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 lungime L.
Aceast a lungime se va determina conform relat iei 3.1 ^ n funct ie de intervalul
scalat conform Algoritmului 4.2:
Algoritm 4.2: Determinarea lungimii 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 in 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 Algoritmului 4.3:
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=zeros ( n r i n d i v i z i , Lungime crom ) ;
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

4.1. Determinarea maximului unei funct ii de o variabil a 32
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.
O astfel de subfunct ie este prezentat ^ n Algoritmul 4.4:
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=zeros (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. ^In 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. Probabilitatea
de selectie, calculat a conform Denit iei 2.1, determin a ce cromozomi vor trece
prin operat iile de ^ ncruci sare  si mutat ie. Deci probabilitatea de adecvare joac a
un rol important ^ n alegerea celor mai buni indivizi.
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 binara )
2 % 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
3 F=0;
4 f u n c t i e a d a p t a r e=zeros (1 , nr crom ) ;
5 f o r i =1: nr crom
6 % f u n c t i a de adaptare pentru f i e c a r e cromozom
7 f u n c t i e a d a p t a r e ( i )=f ( d e c o d i f i c a r e b i n a r a ( Pop binara ( i , 1 :
Lcrom ) , L crom , 1 ) ) ;
8 F=F+f u n c t i e a d a p t a r e ( i ) ;

4.1. Determinarea maximului unei funct ii de o variabil a 33
9 end
10 d is p l ay ( f u n c t i e a d a p t a r e )
11 d is p l ay (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=zeros (1 , nr crom ) ;
15 q=zeros (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 is p l ay ( 'p r o b a b i l i t a t e a de adaptare ')
23 d is p l ay (P)
24 d is p l ay ( 'p r o b a b i l i t a t e a cumulata ')
25 d is p l ay ( 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=zeros ( 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 nc 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
^Incruci sarea se va face cu un punct de t aietur a conform Pseudocodului 4.
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,  si se va
forma o populat ie intermediar a. Unul din dicult at ile ce pot  ^ nt^ ampinate 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 dac a sunt impari, se adaug a un indi-

4.1. Determinarea maximului unei funct ii de o variabil a 34
vid ^ n ^ ncruci sare, astfel rezolv^ andu-se aceast a problem a. ^In urma ^ ncruci s arii,
parint ii dinpopulat ia intermedia@ra for  inlocuit i de descendent ii lor. Indi-
vizii din populat ia auxiliar a se vor ^ ncruci sa astfel: primul din prima jumatate
cu primul din a doua jumatate,al doilea din prima jumatate cu al doilea din a
doua jumatate  si tot a sa.
La sfar situl^ ncruci sarii populat iei intermediare impun criterii de^ mbun atat ire
a convergent ei algoritmului. Un criteriu este ca s a se veric a dac a descendent ii
populat iei selectate pentru^ ncruci sarese g asesc^ n intervalul dat (intervalul sca-
lat). Populat ia se degradeaz a la generat ii ulterioare tocmai prin faptul c a un
individ a p ar asit p ar asi spat iul de c autare. Cel de-al doilea criteriu este
ca distant a dintre decendent (cromozomul ^ ncruci sat)  si maxima g asit a din
generat ia anterioar a s a e mai mic a dec^ at distant a dintre parinte (cromozomul
nemodicat)  si acea si maxim a. Acest aspect ne ajut a s a ne apropriem de cea
mai bun a solut ie a problemei de maxim.
La inceput, populat ia nal a cont inea tot i cromozomii rezultat i din algorit-
mul Monte Carlo de select ie. Dac a descendent ii satisfac criteriile impuse, ^ i
vor ^ nlocui pe p arint i  si cu aceast a populat ie trecem la operat iunea urm atoare.
Algoritmul 4.6 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=zeros (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=zeros (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 ( nr crom 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

4.1. Determinarea maximului unei funct ii de o variabil a 35
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 :
Lcrom )=P o p s e l e c t i e (g , 1 : L crom ) ;
31 end
32 di s pl a y ( 'p o z i t i e ')
33 d i sp l a y ( p o z i t i e )
34 d i sp l a y ( 'Populatie de i n c r u c i s a t ')
35 d i sp l a y ( P o p u l a t i e d ei n c r u c i s a t )
36 %incrucisam cu un punct de t a i e t u r a k generat
random
37 %perechi de cromozomi din P o p u l a t i e d ei n c r u c i s a t
38 P o p u l a t i e i n c r u c i s a t a=zeros ( nr crom incrucisat ,
Lcrom ) ;
39 %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
40 %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
41 f o r i =1: n r c r o m i n c r u c i s a t /2
42 j=n r c r o m i n c r u c i s a t /2+ i ;
43 k=round (1+(L crom2) *rand (1 ,1) ) ;
44 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 ) ;
45 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 ) ;
46 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 ) ;
47 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 ) ;
48 end
49 d i sp l a y ( 'Populatie i n c r u c i s a t a ')
50 d i sp l a y ( P o p u l a t i e i n c r u c i s a t a )
51 % se pun l a l o c cromozomii m o d i f i c a t i
52 %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
53 %daca sunt , i i vom introduce in Pop finala
54 %daca nu se gasesc in i n t e r v a l , nu i i vom introduce
55 contor =0;
56 f o r i =1:n
57 i f p o z i t i e ( i )==1
58 contor=contor +1;
59 %decodificam cromozomul pentru a vedea daca se
gasesc in
60 %i n t e r v a l
61 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 : L crom )
, Lcrom , 1 ) ) ;

4.1. Determinarea maximului unei funct ii de o variabil a 36
62 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 ) , L crom
, 1 ) ;
63 %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
64 %distanta d i n t r e valoarea optima s i descendent e
mai mica
65 %decat valoare optima s i parinte , atunci
descendentul se
66 %i n t o a r c e in populatia f i n a l a
67 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 ) )
68 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 ) )
69 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 ) ;
70 end
71 end
72 end
73 end
74 e l s e
75 d i sp 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 ')
76 end
77 end
6. Alegerea operatorului de mutat ie
Operatorul de mutat ie folosit este cel tare uniform (a se vedea Pseudoco-
dul 7). Probabilitat ea de mutat ie schimb a valoarea bitului unui cromozom
 si este dat a de utilizator.De asemenea se impun acelea si condit ii, pe care le-
am prezentat la ^ ncruci sara cu un singur punct de t aietur a. Dac a nu satisfac
condit iile, bitul cromozomului ce a fost mutat va reveni la valoarea init ial a.
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 : L crom )
, Lcrom , 1 ) ) ;

4.1. Determinarea maximului unei funct ii de o variabil a 37
13 mutat decodificat=d e c o d i f i c a r e b i n a r a ( Pop mutata ( i , 1 :
Lcrom ) , 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 %distanta 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 <=mutat decodificat ) && ( mutat decodificat <=
b1 ) )
19 i f ( abs ( aux valoare optima ) <abs ( f ( mutat decodificat )
valoare optima ) )
20 Pop mutata ( i , j )=~Pop mutata ( i , j ) ;
21 end
22 end
23 end
24 end
25 end
26 end
7. Elitismul
Elitismul joac a un rol important ^ n implemetarea unui algoritm genetic.
Ajut a la g asirea mai rapid a  si mai exact a a solut iei optime, precum  si ^ n a
nu pierde solut ii bune prin trecerea de la o generat ie la alta. O metod a de
implemetare a elitismului se compune din urm atorii pa si: ^ n init ializarea elitei
curente cu valoarea elitei din generat ia anterioar a, compararea elitei anterioare
cu indivizii din populat ia rezultat a (dac a se g aseste o solut ie mai bun a, aceasta
devine elit a)  si ^ n introducerea celui mai bun individ din generat ia curent a pe
prima pozit ie.
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 x optim
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

4.1. Determinarea maximului unei funct ii de o variabil a 38
Fiind descri si subalgoritmii care realizeaz operat iile principale, putem prezenta
algoritmul genetic care rezolv a problema de maxim a unei funct ii de o variabil a:
Algoritm 4.9: Algoritmul genetic pentru determinarea maximului unei functii
de o variabila
1 function maxim 1D ( )
2 c l e a r a l l ;
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 % Setam o p r e c i z i e de c o d i f i c a r e , numita p , pentru x ( s o l u t i e
p o t e n t i a l a )
12 % x va avea "p" zecimale
13 p=input ( 'p r e c i z i a (10^(p) ) : p = ') ;
14
15 % i n t e r v a l u l [ a , b ] e s t e s c a l a t cu p r e c i z i a p a s t f e l i n ca t sa nu
avem v i r g u l e cand facem c o d i f i c a r e a
16 %( numerele zecimale devin i n t r e g i )
17 a1=a *10^p ;
18 b1=b *10^p ;
19
20 %determinare lungime cromozomi
21 L=lungime cromozomi ( a1 , b1 ) ;
22 d is p l ay ( 'Lungimea cromozomului ')
23 d is p l ay (L)
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
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 is p l ay ( 'Populatia i n i t i a l a ')
31 d is p l ay ( 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 is p l ay ( 'Populatia i n i t i a l a c o d i f i c a t a ')
36 d is p l ay ( Populatie binara )
37
38 % alegem numarul maximde g e n e r a t i i pe care o va parcurge populatia
39 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 = ')
;
40

4.1. Determinarea maximului unei funct ii de o variabil a 39
41 %determinarea s o l u t i e i optime i n i t i a l e
42 x optim=zeros (1 , n r i t e r a t i i +1) ;
43 val optim=zeros (1 , n r i t e r a t i i +1) ;
44
45 x optim (1)=Populatie numere (1) /10^p ;
46 val optim (1)=f ( x optim (1) ) ;
47 f o r i =2: c a r d i n a l p o p u l a t i e
48 i f ( val optim (1) <f ( Populatie numere ( i ) /10^p) )
49 x optim (1)=Populatie numere ( i ) /10^p ;
50 val optim (1)=f ( x optim (1) ) ;
51 end
52 end
53
54 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 ) ;
55 Pop mutatie=Populatie binara ;
56
57 f o r i =1: n r i t e r a t i i
58 f p r i n t f ( 'Generatia curenta %d nn ', i )
59 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 , Pop mutatie )
60 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 )
61
62 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 ) )
63 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 )
64
65 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 ) )
66 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 ) ;
67 f p r i n t f ( 'Populatia de l a g e n e r a t i a %d nn ', i )
68 di s pl 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)
69
70 %ELITISM
71 %se determina valoarea optima ( x optim , val optim ) din
g e n e r a t i a curenta
72 % 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
73 x optim ( i +1)= x optim ( i ) ;
74 val optim ( i +1)=val optim ( i ) ;
75 f o r k=1: c a r d i n a l p o p u l a t i e
76 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) )
77 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 ;
78 val optim ( i +1)=f ( x optim ( i +1) ) ;
79 end
80 end
81 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 ) ;
82 pause
83 end
84 d is p l ay ( 'v a l o r i optime ')
85 disp ( x optim )

4.1. Determinarea maximului unei funct ii de o variabil a 40
86 disp ( val optim )
87
88 f i g u r e (1)
89 plot ( 0 : n r i t e r a t i i , x optim , 'rx ')
90 t i t l e ( 'Reprezentarea v a l o r i i optime a l u i x in f u n c t i e de i t e r a t i e
')
91 x l a b e l ( 'nr de i t e r a t i i ')
92 y l a b e l ( 'valoarea optima a l u i x ')
93
94 f i g u r e (2)
95 plot ( 0 : n r i t e r a t i i , val optim , 'bx ')
96 t i t l e ( 'Reprezentarea v a l o r i i maxime a f u n c t i e i in rapot cu nr de
i t e r a t i i ')
97 x l a b e l ( 'nr de i t e r a t i i ')
98 y l a b e l ( 'valoare maxima a f u n c t i e i ')
99
100 f i g u r e (3)
101 v=l i n s p a c e ( a , b , 10 0 ) ;
102 plot (v , f ( v ) , 'b ')
103 hold on
104 plot ( x optim , val optim , 'rp ')
105 t i t l e ( 'Reprezentarea v a l o r i i maxime a f u n c t i e i ')
106 xlim ( [ a0.2 b +0.2])
107 ylim ( [ min( f ( v ) ) 0.3 max( f ( v ) ) +0.3])
108 x l a b e l ( 'x ')
109 y l a b e l ( 'f ( x ) ')
9. Analiza rezultatelor
Pentru a pune ^ n evident  a performant a algoritmului genetic prezentat an-
terior, ^ l vom aplica asupra unei funct ii de gradul 2: f(x) =x2+ 6
x1.
Doresc s a g asesc valoarea maxim a reprezentat a cu dou a zecimale,(precizia de
codicare este p= 2) ^ n intervalul [ a; b] = [0 ;6]. Deci codicarea solut iei
potent iale se face pe L= 11 bit i. Pentru ^ nceput am ales ca populat ia s a
cont in a 10 indivizi, ace stia s a e modicat i ^ n 30 de iterat ii. Populat ia init ial a
obtinut a este reprezentat a ^ n Tabelul ??.

4.1. Determinarea maximului unei funct ii de o variabil a 41
Pozit ia Valoareai Cromozomul
individului individului (x)
1 76 00001001100
2 94 00001011110
3 83 00001010011
4 311 00100110111
5 462 00111001110
6 188 00010111100
7 50 00000110010
8 244 00011110100
9 179 00010110011
10 285 00100011101
Tabelul 4.1: Generarea populat iei init iale
Din populat a init ial a se vor alege coromozomii care vor avea  sansa s a formeze
urm atoarea generat ia, dar nu p^ an a ce nu trec prin ^ ncruci sare  si mutat ie.
Cromozomii din populat ia selectat a nu trebuie s a e neap arat distinct i. Cu
c^ at individul e mai performant cu at^ at acesta fa  mai des selectat. Atfel
avem  sanse s a gasim optimul mult mai repede. Tabelul ??prezint a populat ia
obt inut a ^ n urma select iei.
Nr. Pozit ia Valoarea Valoarea funct iei Probabilitatea Cromozomul
crt. individului individului (x) de adaptare de adaptare
1 1 76 -5321 0.00100 00001001100
2 5 462 -82736 0.0156 00111001110
3 5 462 -63926 0.0120 00111001110
4 5 462 -94856 0.1788 00111001110
5 5 462 -210673 0.3971 00111001110
6 5 462 -34217 0.0645 00111001110
7 9 179 -2201 0.0041 00010110011
8 8 244 -58073 0.1095 00011110100
9 8 244 -30968 0.0584 00011110100
10 10 285 -79516 0.1499 00100011101
Tabelul 4.2: Populat ia selectat a
Urmeaz a s a se aleag a ce cromozomi vor  supu si operat iei de ^ ncruci sare
cu ajutorul probabilit at ii de ^ ncruci sare. Ei vor  introdu si ^ n populat ia aux-
iliar a. Populat ia auxiliar a e alcatuit a din 8 indivizi ce se vor ^ ncruci sa iar

4.1. Determinarea maximului unei funct ii de o variabil a 42
descendent ii ce trec de condit iile de convergent a si ^ ndivizii ne@ncruci sat i vor
forma populat ia ^ ncruci sat a.Rezultatul din Tabelul ??ne arat a ca doar doi
descendent i vor face parte din populat ia ^ ncruci sat a.
Nr. Valoarea Cromozomul Valoare Cromozom Valoare ^Indeplinire
crt. individului (x) partener descendent descendent condit ie
1 76 00001001100 462 0000j1001110 78 nu
2 462 00111001110 244 0011100j1100 460 da
3 462 00111001110 285 00111j011101 477 da
4 462 00111001110 462 00111001110 462 da
5 462 00111001110 76 0011j1001100 460 nu
6 244 00011110100 462 0001111j1110 254 nu
7 285 00100011101 462 00100j001110 270 nu
8 462 00111001110 462 00111001110 462 da
Tabelul 4.3: Populat ia auxiliar a ^ mpreun a cu descendent ii lor
Ace stia vor  supu si procedurii de mutat ie. Populat ia rezultat a ^ n urma mu-
tatiei ^ mpreun a cu zonele ^ n care s-au schimbat bit ii se g ase ste ^ n Tabelul ??
.
Nr Cromozomul Valoarea zecimal a
crti individului (x)
1 0001000100 5.80
2 00110011000 4.08
3 00111111010 5.06
4 00110100110 4.22
5 0011100 0110 4.54
6 00001011110 0.94
7 000101100 00 1.74
8 00110101101 4.29
9 00011 011101 2.21
10 00100011 000 2.80
Tabelul 4.4: Indivizii ce rezult a din operat ia de mutat ie
Generat ia actual@este format a din ^ ndivizii mutat i anterior, except^ and prima
pozit ie, care e destinat a solut iei optime specic a acesteia.
Solut iile optime pentru acest a funct ie(punctul^ n care se atinge maximul funct iei
 si valoarea maxim a a a ei) se g asesc la iterat ia 18  si se ating^ n x= 3  si f(x) = 8.

4.1. Determinarea maximului unei funct ii de o variabil a 43
Se poate observa c a de la generat ia init ial a optimele s-au apropiat de solut i
exact a, av^ and o eroare foarte mic a, fapt ce indic a o convergent a bun a a solut iei
 si o aplicare bun a a elitismului. Aceste rezultate sunt prezente ^ n Figurile 4.1a,
4.1b  si 4.2.
(a)G asirea valorii lui x dup a 18 iterat ii
(b)G asirea valorii f(x) dup a 18 iterat ii
Figura 4.1: Reprezentarea valorilor optime^ n func2tie de num arul de iterat ii
Figura 4.2: Reprezentarea valorilor optime g asite pe geacul funct iei f(x) =x2+ 6x1
Sunt situat ii ^ n care algoritmul ofer a din generat ia ^ nit ial a solut ia optim a, a sa
cum arat a ^ n Figurile 4.3a  si 4.3b. Ne a stept am la asemenea lucruri deoarece
alegerea populat iei la ecare generat ie se face pe baza unor probabilit at^ . La
ecare rulare a programului vom aveavalori diferite, dar toate vor conduce la
solut ia optim a.

4.1. Determinarea maximului unei funct ii de o variabil a 44
(a)Punctul ^ n care se atinge maximul funct iei
g asit din populat ia init ial a
(b) Maximul funct iei g asit din populat ia
init ial a
Figura 4.3: Reprezentarea valorilor optime^ n funct ie de num arul de iterat ii
^In situat ia ^ n care nu dorim s a folosim elitismul, solut iile optime nu se vor
apropia una de alta, dar dac a facem media lor, ajungem la o valoare care se
apropie de solut ia optim a, dar nu la fel de mult cum o face un algoritm ^ n care
folosim elitismul. De exemplu, pentru acelea si date de intrare valorile optime
vor :
Algoritm 4.10: Valorile solutiilor optime si media acestora in Matlab
1 x optim =
2
3 Columns 1 through 14
4
5 2.9800 2.9800 3.3800 3.8000 3.0700 3.7000
1.9500 2.7300 3.0700 3.6000 2.9200 3.0400
2.5700 3.3000
6
7 Columns 15 through 28
8
9 3.2700 2.9800 2.7100 2.6500 4.4700 3.1800
2.8900 3.1400 2.9800 2.9800 3.1400 3.4900
3.2400 3.4600
10
11 Columns 29 through 31
12
13 3.7500 2.8300 2.7900
14
15 val optim =
16
17 Columns 1 through 14
18
19 7.9996 7.9996 7.8556 7.3600 7.9951 7.5100
6.8975 7.9271 7.9951 7.6400 7.9936 7.9984

4.1. Determinarea maximului unei funct ii de o variabil a 45
7.8151 7.9100
20
21 Columns 15 through 28
22
23 7.9271 7.9996 7.9159 7.8775 5.8391 7.9676
7.9879 7.9804 7.9996 7.9996 7.9804 7.7599
7.9424 7.7884
24
25 Columns 29 through 31
26
27 7.4375 7.9711 7.9559
28 %se f a c e media v a l o r i l o r l u i x optim s i val optim
29>>mean( x optim )
30
31 ans =
32
33 3.1303
34>>mean( val optim )
35
36 ans =
37
38 7.7815
Figurile 4.4a, 4.4b  si 4.5 prezint a solut iile optime ^ n cazul ^ n care nu folosim
elitismul.
(a) Valorile lui x ^ n cazul ^ n care nu se
folose ste elitism
(b)Maximul funct iei ^ n cazul ^ n care nu se
folose ste elitism
Figura 4.4: Reprezentarea valorilor optime ^ n funct ie de num arul de iterat ii

4.2. Determinarea maximului unei funct ii de dou a variabile 46
Figura 4.5: Reprezentarea valorilor pe gracul funct iei
4.2 Determinarea maximului unei funct ii de dou a vari-
abile
Fie o funct ie f:DD!R, unde Dreprezint a un interval [ a; b] inclus ^ n R.
Scopul aplicat iei este de a determina maximul local al funct iei ^ n domeniul DD
cu o precizie pdat a de utilizator.
Modul de implementare al algoritmului genetic pentu a
area maximului funct iei
de dou a variabile pleac a de la algoritmul genetic pentru o funct ie cu o variabil a
(vezi Algoritmul 4.9), unde ,maniera de codicare, generarea populat iei ,operatorii
de select ie, ^ ncruci sare  si mutat ie se bazeaz a pe acela si principiu(a se vedea Algoritii
4.1, 4.5, 4.6, 4.7), doar c a trebuie s a se t in a cont de urm atoarele aspecte:
ˆ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.
Deci algoritmul genetic pentru a
area maximului unei funct ii cu dou a variabile
arat a ^ n felul urm ator:
Algoritm 4.11: Algoritmul genetic pentru determinarea maximului unei functii de
doua variabile
1 function maxim 2D ( )
2 % 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
3 % 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

4.2. Determinarea maximului unei funct ii de dou a variabile 47
4
5 %Alegem c a p e t e l e i n t e r v a l u l u i [ a , b ]
6 a=input ( 'valoarea minima a i n t e r v a l u l u i : a= ') ;
7 b=input ( 'valoarea maxima a i n t e r v a l u l u i : b= ') ;
8
9 % Setam o p r e c i z i e de c o d i f i c a r e , numita p , pentru x ( s o l u t i e
p o t e n t i a l a )
10 % x va avea "p" zecimale
11 p=input ( 'p r e c i z i a (10^(p) ) : p= ') ;
12
13 %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 ca t sa nu avem
v i r g u l e
14 %( numerele zecimale devin i n t r e g i )
15 a1=a *10^p ;
16 b1=b *10^p ;
17
18 %determinare lungime cromozomi
19 L=lungime cromozomi ( a1 , b1 ) ;
20 d is p l ay ( 'Lungimea cromozomului ')
21 d is p l ay (L)
22
23 % 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
24 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 = ') ;
25 %se generaza populatia i n i t i a l a i n t r e a1 s i b1
26 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 ) ;
27 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 ) ;
28 d is p l ay ( 'Populatia i n i t i a l a ')
29 d is p l ay ( Populatie numere x )
30 d is p l ay ( Populatie numere y )
31
32 %c o d i f i c a r e populatie in binar
33 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 ) ;
34 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 ) ;
35 d is p l ay ( 'Populatia i n i t i a l a c o d i f i c a t a ')
36 d is p l ay ( Populatie binara x )
37 d is p l ay ( Populatie binara y )
38
39 % alegem numarul maxim de g e n e r a t i i pe care o va parcurge populatia
40 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 = ') ;
41
42 %determinarea s o l u t i e i optime i n i t i a l e
43 x optim=zeros (1 , n r i t e r a t i i +1) ;
44 y optim=zeros (1 , n r i t e r a t i i +1) ;
45 val optim=zeros (1 , n r i t e r a t i i +1) ;
46
47 x optim (1)=Populatie numere x (1) /10^p ;
48 y optim (1)=Populatie numere y (1) /10^p ;
49 val optim (1)=f ( x optim (1) , y optim (1) ) ;

4.2. Determinarea maximului unei funct ii de dou a variabile 48
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 x ( i ) /10^p , …
52 Populatie numere y ( i ) /10^p) )
53 x optim (1)=Populatie numere x ( i ) /10^p ;
54 y optim (1)=Populatie numere y ( i ) /10^p ;
55 val optim (1)=f ( x optim (1) , y optim (1) ) ;
56 end
57 end
58
59 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 ) ;
60 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 ) ;
61 Pop mutatie x=Populatie binara x ;
62 Pop mutatie y=Populatie binara y ;
63
64 f o r i =1: n r i t e r a t i i
65 f p r i n t f ( 'Generatia curenta %d nn ', i )
66 [ 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 , …
67 Pop mutatie x , Pop mutatie y ) ;
68 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 x , L , c a r d i n a l p o p u l a t i e )
69 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 y , L , c a r d i n a l p o p u l a t i e )
70
71 [ 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 , …
72 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 ) ) ;
73 d e c o d i f i c a r e b i n a r a ( Pop incrucisare x , L , c a r d i n a l p o p u l a t i e )
74 d e c o d i f i c a r e b i n a r a ( Pop incrucisare y , L , c a r d i n a l p o p u l a t i e )
75
76 [ Pop mutatie x , Pop mutatie y ]= mutatie ( c a r d i n a l p o p u l a t i e , …
77 L , Pop incrucisare x , Pop incrucisare y , a1 , b1 , val optim ( i ) ) ;
78 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 ) ;
79 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 ) ;
80 f p r i n t f ( 'Populatia de l a g e n e r a t i a %d nn ', i )
81 di s p la 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)
82 di s p la 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)
83
84 %ELITISM
85 %se determina valoarea optima ( x optim , val optim ) din g e n e r a t i a
curenta
86 % 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 x optim
87 x optim ( i +1)= x optim ( i ) ;
88 y optim ( i +1)=y optim ( i ) ;
89 val optim ( i +1)=val optim ( i ) ;
90 f o r k=1: c a r d i n a l p o p u l a t i e
91 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) ,…
92 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) ) )
93 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 ;
94 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 ;

4.2. Determinarea maximului unei funct ii de dou a variabile 49
95 val optim ( i +1)=f ( x optim ( i +1) , y optim ( i +1) ) ;
96 end
97 end
98 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 ) ;
99 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 ) ;
100 end
101 d is p la y ( 'v a l o r i optime ')
102 disp ( x optim )
103 disp ( y optim )
104 disp ( val optim )
105
106 f i g u r e (1)
107 plot ( 0 : n r i t e r a t i i , x optim , 'rx ')
108 t i t l e ( 'Reprezentarea v a l o r i i optime a l u i x in f u n c t i e de i t e r a t i e ')
109 x l a b e l ( 'nr de i t e r a t i i ')
110 y l a b e l ( 'valoarea optima a l u i x ')
111
112 f i g u r e (2)
113 plot ( 0 : n r i t e r a t i i , y optim , 'bx ')
114 t i t l e ( 'Reprezentarea v a l o r i i optime a l u i y in f u n c t i e de i t e r a t i e ')
115 x l a b e l ( 'nr de i t e r a t i i ')
116 y l a b e l ( 'valoarea optima a l u i y ')
117
118 f i g u r e (3)
119 plot ( 0 : n r i t e r a t i i , val optim , 'gx ')
120 t i t l e ( 'Reprezentarea v a l o r i i maxime a f u n c t i e i in rapot cu nr de
i t e r a t i i ')
121 x l a b e l ( 'nr de i t e r a t i i ')
122 y l a b e l ( 'valoare maxima a f u n c t i e i f (x , y ) ')
123
124 f i g u r e (4)
125 v=l i n s p a c e ( a , b , 2 0 ) ;
126 [X,Y]= meshgrid (v , v ) ;
127 U =f (X,Y) ;
128 mesh (X,Y,U) ;
129 hold on
130 plot3 ( x optim , y optim , val optim , 'or ', 'MarkerSize ',7 , 'MarkerFaceColor ', '
r ')
131 x l a b e l ( 'x ')
132 y l a b e l ( 'y ')
133 z l a b e l ( 'f (x , y ) ')
134 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. Se
vor genera 100 de indivizi, iar programul va rula pentru 30 de iterat ii.
Am m arit num arul de indivizi , datorit a faptului c a zona de c autare este mai
mare comparativ cu cea unidimensional a. Valorile optime sunt stocate ^ n vectorii

4.2. Determinarea maximului unei funct ii de dou a variabile 50
xoptim ,yoptim  sivaloptim .
Algoritm 4.12: Valorile solutiilor optime pentru o functie de doua variabile
1>>xoptim
2 x optim =
3
4 Columns 1 through 17
5
6 1.1900 1.1900 0.8100 0.8100 0.8100 0.8100 0.8100
1.1100 1.1100 1.1100 1.1100 1.1200 1.1200
1.1200 1.1200 1.1200 1.1200
7
8 Columns 18 through 31
9
10 1.1200 1.1200 1.1200 1.1200 1.0200 1.0200 1.0200
1.0200 1.0200 1.0200 1.0200 1.0200 1.0200
1.0200
11
12>>yoptim
13
14 y optim =
15
16 Columns 1 through 17
17
18 2.3700 2.3700 2.2600 2.2600 2.2600 2.2600 2.2600
1.8200 1.8200 1.8200 1.8200 2.0900 2.0900
2.0900 2.0900 2.0900 2.0900
19
20 Columns 18 through 31
21
22 2.0900 2.0900 2.0900 2.0900 1.9700 1.9700 1.9700
1.9700 1.9700 1.9700 1.9700 1.9700 1.9700
1.9700
23
24>>val optim
25
26 val optim =
27
28 Columns 1 through 17
29
30 8.8270 8.8270 8.8963 8.8963 8.8963 8.8963 8.8963
8.9555 8.9555 8.9555 8.9555 8.9775 8.9775
8.9775 8.9775 8.9775 8.9775
31
32 Columns 18 through 31
33
34 8.9775 8.9775 8.9775 8.9775 8.9987 8.9987 8.9987
8.9987 8.9987 8.9987 8.9987 8.9987 8.9987
8.9987

4.2. Determinarea maximului unei funct ii de dou a variabile 51
(a)G asirea valorii lui x dup a 21 iterat ii
(b)G asirea valorii lui y dup a 21 iterat ii
(c)G asirea maximului funct iei f(x,y) dup a 21
iterat ii
Figura 4.6: Reprezentarea valorilor optime ^ n funct ie de num arul de iterat ii parcurs de
program

4.2. Determinarea maximului unei funct ii de dou a variabile 52
(a)Reprezentarea solut iei optime g asite pe
planul OXYZ
(b) Reprezentarea solut iei optime g asite pe
planul XOY
(c)Reprezentarea solut iei optime g asite pe
planul XOZ
(d) Reprezentarea solut iei optime g asite pe
planul YOZ
Figura 4.7: Reprezentarea solut iei optime g asite pe diferite plane
^In cazul ^ n care nu se folose ste elitismul, solut iile optime se ^ nv^ art ^ n jurul punc-
tului de maxim. Media acestora ne conduce la o valoare apropiat a de cea exact a.
Algoritm 4.13: Valorile solutiilor optime pentru o functie de doua variabile @in
cazul2in care nu aplicam elitismul si media acestora
1>>xoptim
2
3 x optim =
4
5 Columns 1 through 17
6
7 0.7000 0.9500 1.0600 0.7200 0.6900 1.3400 0.9000
0.9100 1.3300 1.0600 1.3000 0.8300 1.2600
0.8300 1.3300 0.7500 0.8900
8
9 Columns 18 through 31

4.2. Determinarea maximului unei funct ii de dou a variabile 53
10
11 0.8700 1.0500 0.8700 1.4600 1.4000 0.8000 0.9900
0.7800 1.3200 1.1200 1.3100 1.0700 0.9600
1.3800
12
13>>yoptim
14
15 y optim =
16
17 Columns 1 through 17
18
19 2.3100 2.2000 2.2400 2.1100 2.0700 2.2700 2.3900
2.3500 1.9700 2.0100 1.9400 1.9100 1.9000
1.9100 2.2600 2.3000 1.8000
20
21 Columns 18 through 31
22
23 1.8400 1.9600 1.8400 2.5300 2.0100 1.8800 2.3600
1.6300 2.3200 2.2100 2.3800 1.9900 2.0500
2.3100
24
25>>val optim
26
27 val optim =
28
29 Columns 1 through 17
30
31 8.8139 8.9575 8.9388 8.9095 8.8990 8.8115 8.8379
8.8694 8.8902 8.9963 8.9064 8.9630 8.9224
8.9630 8.8235 8.8475 8.9479
32
33 Columns 18 through 31
34
35 8.9575 8.9959 8.9575 8.5075 8.8399 8.9456 8.8703
8.8147 8.7952 8.9415 8.7595 8.9950 8.9959
8.7595
36
37>>mean( x optim )
38
39 ans =
40
41 1.0397
42
43>> mean( y optim )
44
45 ans =
46
47 2.1048
48
49>> mean( val optim )
50

4.2. Determinarea maximului unei funct ii de dou a variabile 54
51 ans =
52
53 8.8849
(a) Valorile lui x ^ n cazul ^ n care nu se
folose ste elitism
(b) Valorile lui y ^ n cazul ^ n care nu se
folose ste elitism
(c)Maximul funct iei f(x,y) ^ n cazul ^ n care nu
se folose ste elitism
Figura 4.8: Reprezentarea valorilor optime ^ n funct ie de num arul de iterat ii parcurs de
program

4.2. Determinarea maximului unei funct ii de dou a variabile 55
(a)Reprezentarea solut iei optime g asite pe
planul OXYZ
(b) Reprezentarea solut iei optime g asite pe
planul XOY
(c)Reprezentarea solut iei optime g asite pe
planul XOZ
(d) Reprezentarea solut iei optime g asite pe
planul YOZ
Figura 4.9: Reprezentarea solut iei optime g asite pe diferite plane la nonelitism

Concluzii 56

Concluzii
57

Index
Algoritmi
evolutivi, 3
genetici, 6
Cromozom, 3, 7
58

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

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