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

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

Cuprins 2
5 Aplicatii 35
Bibliograe 36

Introducere
^In acest a lucrare …..
^Incep^ and cu anii '70 s-a manifestat un interes pentru algoritmii care se
bazeaz a pe un principiu evolutiv. Un termen comun adoptat care s a se refere la
tehnicile folosite este acela de metode de calcul evolutiv.
Paleta de aplicat ii ale algoritmilor genetici este nelimitat a. Conceput i
ca instrumente de optimizare, algoritmii genetici sunt aplicabili  si ^ n probleme
de alt gen, prin reformularea problemelor respective ca probleme de c autare a
solut iilor optime ^ n spat iul de c autare. Identicarea corect a a obiectivelor prob-
lemei date, delimitarea spat iului solut iilor posibile, determinarea unei maniere de
reprezentare a solut iilor, construirea unei funct ii de evaluare corespunztoare  si
alegerea inspirat a a operatorilor de variat ie, sunt c^ ateva dintre ingredientele care
asigur a aplicabilitatea algoritmilor genetici. ([9])
Cele mai reprezentative probleme cu aplicat ii ^ n viat a real a pentru care algo-
ritmii genetici s-au dovedit ecient i sunt:
– probleme de combinatoric a;
– optimiz ari ^ n proiectarea compozit iei materialelor  si a formei aerodinamice
a vehiculelor (auto, aeriene, navale, trenuri);
– optimiz ari ^ n proiectarea structural a  si funct ional a a cl adirilor (locuint e,
fabrici, etc)
– proiectarea  si optimizarea ret elelor neuronale;
– proiectarea automat a a sistemelor;
– planicarea sarcinilor;
– probleme din domeniul telecomunicat iilor;
– optimiz ari ^ n robotic a;
– problema comis-voiajorului;
– optimiz ari ^ n proiectarea circuitelor digitale;
1

Introducere 2

Capitolul 1
Principii generale despre
algoritmi evolutivi  si genetici
1.1 Denirea algoritmilor evolutivi
Algoritmii evolutivi cu cele trei direct ii( strategiile evolutive, programarea evolu-
tiv a  si algoritmii genetici([6], [5])) sunt cei mai vechi algoritmi probabili sti  si au
ca surs a de inspirat ie evolut ia biologic a.
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 ([2]).
Algoritmii evolutivi utilizeaz a un vocabular ^ mprumutat din teoria evolut iei
a speciilor biologice(teoria darwinist a). Un algoritm genetic simuleaz a evolut ia
printr-o succesiune de generat ii (proces iterativ) ale unei populat ii (mult ime) de
solut ii candidat. O solut ie candidat este reprezentat a ca un  sir de gene (genotip)
 si poart a numele de cromozom . Gena este informat ia atomic dintr-un cromo-
zom. Pozit ia pe care o ocup a o gen a se numete locus iar toate valorile posibile
pentru o gen a formeaz a setul de alele ale genei. Evolut ia populat iei ment inut a de
algoritmul genetic este condus a de dou elemente: operatorii genetici  sifunct ia
de evaluare a calit at ii cromozomilor. Select ia ,^ ncruci sarea  si mutat ia sunt
operatorii genetici uzuali, ind inspirat i de procesele naturale care stau la baza
evolut iei. Cromozomul asupra c aruia se aplic a un operator genetic poart a nu-
mele de p arinte iar cromozomul rezultat ^ n urma acelui operator este numit
descendent . Un proces (aleator) de select ie ofer a indivizilor mai bine adaptat i
 sanse mai mari pentru a supraviet ui n generat ia urmtoare. Gradul de adaptare la
mediu al indivizilor este msurat de funct ia tness obt inut a pornind de la funct ie
matematic de optimizat. ^Incruci sarea (recombinarea) are ca scop schimbul de
informat ie genetic a ^ ntre doi sau mai mult i cromozomi  si mutat ia care const a ^ n
3

1.2. Explorare  si exploatare 4
modicarea aleatoare a unei gene. Solut ia returnat a de un algoritm genetic este
cel mai bun individ din ultima generat ie ([4], [9]).
1.2 Explorare  si exploatare
Tehnicile calculului evolutiv sunt metode slabe de optimizare de oarece sunt apli-
cabile unor clase largi de probleme. Pentru a putea  abordat cu aceste tehnici,
problema de rezolvat trebuie pus sub forma unei probleme de optimizare.
Comportamentul algoritmului evolutiv ^ n rezolvarea problemelor de opti-
mizare este str^ ans legat a de conceptul de explorare  si exploatare a spat iului de
c autare. Atunci cand rezolvam o anumita problema, cautam o solutie care sa e
cea mai buna printre alte solutii. Spatiul tuturor solutiilor posibile se numeste
spatiul de cautare. Fiecare punct din spatiul de cautare este de fapt o solutie
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 ce se dovedesc a  promit  atoare
(in care sunt  sanse mai mari ca solutia s a se g aseasc a). Cele dou a concepte
corespund c aut arii locale (exploatarea) si c aut arii globale(explorarea) ([5] [4]).
Dac a explorarea are un grad ridicat, acesta reduce gradul de exploatare a
zonelor de interes mare (promit  atoare), deci va reduce capacitatea algoritmu-
lui de a converge(tinde) ^ nspre puncte optime. Reciproc, exploatarea accen-
tuat a a zonelor de interes reduce capacitatea de exporare ecient a a spat iilor
solut iilor posibile, respectiv capacitatea algoritmului de a descoperi  si alte zone
promit  atoare.
O alt a interpretare a echilibrului explorare-exploatare poate  furnizat a prin
prisma a dou a concepte specice problematicii algoritmilor evolutivi, respectiv
convergent a  si diversitatea populat iei. Dac a explorarea ecient a a spat iului de
c autare este tradus a printr-un grad ridicat al diversit at ii populat iei, exploatarea
intens a a teritoriilor privilegiate ale spat iului de c autare este tradus a prin con-
vergent a populat iei ^ nspre solut iile optime.
Deci obt inerea unui echilibru ^ ntre explorare  si exploatare este indicat a pen-
tru ca metoda de optimizare s a e foarte bun a, iar parametrizarea algoritmului
evolutiv permite persoanei (factorului uman) s a ajusteze echilibrul explorare-
exploatare pe o problem a concret a.
1.3 Strucutura general a unui algoritm evolutiv
O procedur a evolutiv a e alc atuit din urm atoarele elemente:
1. O reprezentare a spat iului de c autare (spat iul st arilor problemei  si spat iul
solut iilor posibile ale problemei)

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

1.4. Denirea algoritmului genetic 6
1.4 Denirea algoritmului genetic
Algoritmul genetic reprezint a o clas a a algoritmilor evolutivi  si este ^ n esent  a un
algoritm de c autare  si optimizare ^ n spat iul solut iilor posibile. O populat ie de
solut ii posibile este generat a, mai apoi, asupra indivizilor acesteia se vor aplica
operatori precum ^ ncruci sarea, mutat ia  si select ia natural a. Noua generat ie este
alc atuit a din descendent ii populat iei vechi, ace stia din urm a devenind noi solut ii
posibile . De-a lungul evolut iei se ^ nregistreaz a o cre stere a performant elor in-
divizilor populat iei curente, fapt care asigur a convergent a algoritmului ^ nspre
solut iile reale ale problemei considerate. Ace stia au ^ nceput s a e recunoscut i ca
tehnici de optimizare datorit a lucrarii lui John Holland (Holland, 1975, [6]) si a
lui David Goldberg(Goldberg, 1989, [5]).
Conceperea unui algoritm genetic de rezolvare a unei probleme concrete pre-
supune evident ierea urm atoarelor componente:
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
stabilim la ^ nceput  si reprezint a un parametru important al algoritmului
dezvoltat. Percis, 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.

1.5. Caracteristicile unui algoritm genetic 7
3.Funct ia de evaluare
Evaluarea calit at ii indivizilor se face cu ajutorul unei funct ii de adecvare
(evaluare sau adaptare), denit a ca: f:S !R, undeSeste spat iul de
c autare al solut iilor. De obicei, cu c^ at cromozomul este mai promit ator,
cu at^ at funct ia lui de adaptare este mai mare. Exist a  si probleme ^ n cazul
c arora funct ia de adaptare trebuie s a e minimizat a (problema reginelor).
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 (recombinarea  si mutat ia). Scopul select iei este de a asigura  sanse
mai mari de reproducere a celor mai buni indivizi dintr-o populat ie dat a,
ce vor contribui la crearea generat iei urm atoare.
5.Operatorii de variat ie
Select ia nu este sucient a pentru g asi solut ia optim a din spat iul de c autare.
E nevoie ca indivizii selectat i sufere modic ari cu ajutorul operatorilor de
variat ie pentru a permite obt inerea unor descendent i diferit i, respectiv pen-
tru a permite o explorare bun a a spat iului de c autare. Operatorii de variat ie
sunt reprezentat i de operatorii de recombinare  si mutat ie.
Operatorul de recombinare se dene ste ca o aplicat ie: r:Ap!Ad si real-
izeaz a o transformare ^ n care pp arint i dau na stere la dcopii. Operatorul
este folosit pentru a crea noi indivizi folosind segmente a doi sau mai mult i
cromozomi de la momentul t.
Operatorul de mutat ie reprezint a aplicat ia m:A!A. Aceasta creaz a
noi descendent i prin schimbarea unei singure gene a unui individ ales  si
realizeaz a mici modic ari ale cromozomilor obt inut i prin recombinare.
6.Init ializarea  si condit ia de terminare
Init ializarea  si condit ia de terminare sunt criterii esent iale ^ n vederea
funct ion arii algoritmilor genetici. De obicei init ializarea se face ^ n mod
aleator, iar condit ia de terminare se veric a la ecare generat ie cu ajutorul
unor criterii, cum ar : atingerea unei performant e, atingerea unui anumit
num ar de generat ii cu sau f ar a s a se  c^ a stigat performant a, gradul de
uniformitate a populat iei, etc.
1.5 Caracteristicile unui algoritm genetic
Urmatoarele caracteristici prezint a anumite particularit at i ale acestora compara-
tiv cu alte metode de c autare  si optimizare. Acestea sunt:
1. Cromozomii utilizat i au lungime constant a;

1.6. Structura algoritmului genetic 8
2. Populat ia (generat ia) P(t+1) se obt ine ret in^ and tot i descendent ii populat iei
P(t), nu neap arat distinct i,  si sterg^ and complet cromozomii generat iei an-
terioare P(t);
3. Num arul cromozomilor este constant;
4. Algoritmii genetici ment in o populat ie constant a P(t) de indivizi la ecare
iterat ie t.
5. Algoritmii genetici pot g asi solut ii optime (sau aproape optime) cu o mare
probabilitate.
1.6 Structura algoritmului genetic
T  in^ and cont de structura unui algoritm evolutiv ment ionat mai sus, se poate
descrie structura unui algoritm genetic, av^ and ^ n vedere urmatoarele caracteris-
ticile prezentate mai sus.
^In acest caz, structura algoritmului genetic fundamental este ([4], [12], [9]):
Algorithm 2 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;
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
Rezultatul algoritmului este de regul a cel mai promit  ator individ din ultima
generat ie. Deoarece, ^ n realitate, nimic nu garanteaz a faptul c a un individ mai

1.6. Structura algoritmului genetic 9
performant nu a fost obt inut ^ ntr-o generat ie anterioar a, este normal ca la ecare
pas (la ecare generat ie t) s a ret inem cel mai promit  ator element care a fost
generat p^ an a la momentul curent. Acest proces se numeste elitism .

1.6. Structura algoritmului genetic 10

Capitolul 2
Operatori genetici
Operatorii genetici joac a un rol important ^ n modelarea algoritmilor ge-
netici.
Exist a 3 tipuri de operatori: operatori de select ie, operatori de ^ ncruci sare
 si operatori de mutat ie.
2.1 Select ia
Operatorul de select ie este cel mai important operator genetic deoarece
alege ce indivizi din populat ie supraviet uiesc, se reproduc sau mor. Pentru a
realiza select ia este necesar a folosirea (introducerea) funct iei de adecvare asupra
indivizilor.
Rolul select iei ^ n cadrul unui algoritm genetic este acela de a decide
care dintre indivizii unei populat ii vor putea participa la formarea populat iei
urm atoare.
Scopul select iei este de a asigura mai multe  sanse de reproducere celor mai
performant i indivizi din populat ia dat a. Prin select ie se urm are ste maximizarea
performant ei indivizilor. C autarea se concentreaz a ^ n spat iul solut iilor, ^ n acest
fel realiz^ andu-se exploatarea celor mai bune solut ii g asite.
2.1.1 Select ia proport ional a
Select ia proport ional a este una dintre cele mai populare tehnici de select ie.
^In cazul select iei proport ionale, probabilitatea de select iea unui individ depinde
de valoarea funct iei de adecvare (evaluare, performat a) a acestuia.
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.
11

2.1. Select ia 12
Aceast a funct ie re
ect a calitatea cromozomilor.
Funct ia de evaluare (adecvare) fittrebuie s a^ ndeplineasc a urm atoarele cerint e([ ?]):
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):
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([9]):
pi=fi
Fit(t)=fi
nP
i=1fi=fit(ci)
nP
i=1fit(ci)
O variant a a procedurii de select ie proport ional a este aceea ^ n care sunt ex-
trase elementele populat iei de nori,nind dimensiunea populat iei, form^ and o
populat ie intermendiar a.
Populat ia intermediar a este format a din copii ale indivizilor generat iei P(t).
Asfel vom avea dou a situat ii: unii indivizi vor  reperzentat i de mai multe ori ^ n
populat ia intermediar a  si alt ii ce nu vor  select ionat i deloc.
Cunosc^ and dimensiunea populat iei n si probabilitatea de select ie ale indi-
vizilor, se poate determina 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);
unde fitmediu(ci)este performat a medie a populat iei.([9])

2.1. Select ia 13
Algoritmul Monte Carlo
Algoritmul select iei proport ionate e inspirat de algoritmul Monte Carlo, cunos-
cut ca  si algoritmul ruletei.
Ruleta este reprezentat a de un disc ^ np art it ^ n nsectoare, unde ecare sec-
tor corescpunde unui cromozom. La o utilizare a ruletei se selecteaz a individul
corespunz ator sectorului indicat. Probabilitatea de a indica un sector oarecare
e direct proportional a cu dimensiunea (lungimea) sectorului respectiv. Rotirea
denori a ruletei conduce la formarea populat iei intermediare de indivizi, notat a
Pinterm , asupra c arora se vor aplica ulterior ^ ncruci sarea  si mutat ia.
Algoritmul Monte Carlo de select ie este urm atorul ([4]):
Algorithm 3 Algoritmul Monte Carlo de select ie
funct ie Monte Carlo (n; c)
Initializ am performant a total a  si probabilitatea cumulat a cu 0
F=0; q(0)=0
pentru i= 1lanexecut a
F=F+f(c(i));
sf^ ar sit pentru
Calcul am probabilitatea de select ie conform denit iei de mai sus
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
Avantaje  si dezavantaje ale select iei proport ionale

2.1. Select ia 14
Avantajul utiliz arii select iei proport ionale ^ ntr-un algoritm genetic este capaci-
tatea acestei a de a favoriza exploatarea indivizilor performant i ai populat iei.
Dezavantajul select iei poate  ^ nt^ alnit ^ n 2 situat ii([4],[9]):
Situat ia 1: populat ia cont ine un num ar mic de indivizi cu performant e mult
mai mari dec^ at performant ele celorlalt i. ^In acest caz ruleta arat a 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
Figura 2.2: Reprezentarea sectoarelor ruletei pentru situat ia 2
^In situat ia aceasta, operatorul de select ie nu reu seste s a fac a o distinct ie clar a
^ ntre indivizii performant i  si cei slabi. Probabilit at ile de select ie ale indivizilor
au valori apropiate, ceea ce conduce la o convergent  a ^ nceat a a populat iei ^ nspre
optimele problemei.

2.1. Select ia 15
Dep a sirea impedimentelor ^ nt^ alnite ^ n situat a prezentat a anterior, se poate
face prin tehnici de scalare a funct iei de performant  a. Prin modicarea valorilor
funct iei de performant  a se urm are ste ca populat ia curent a s 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  a-
toare.
Literatura de specialitate ofer a diferite variante de scalare a funct iei de perfor-
mant  a (tness). Scalarea poate  static a sau dinamic a (^ n funct ie de independent a,
respectiv, dependent a de num arul generat iei).
Prezent am ^ n continuare c^ ateva dintre metodele de scalare utilizate ^ n mod
frecvent([9]):
bf 1.Scalarea liniar a
Asupra funct iei de performant  a se aplic a legea: S(y=a
y+b, unde a sib
sunt parametri prestabilit i. Astfel,funct ia transformat a de performant  a devine:
fittransformta (c) =a
fit(c) +b
bf 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 rangul acestuia, ^ n concordant  a cu valoarea funct iei
tness  si stabilirea unei probabilit at i de select ie dependent a de rangul atribuit.
Practic, populat ia va  supus a unei proceduri de ordonare descresc atoare dup 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 .([9])
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.
Spre deosebire de procedura de select ie proport ional a, nu performant a, ci val-
oarea etichetei riva in
uent a probabilitatea de select ie a individului ci. Aceast a
diferent  a va induce un avantaj major ale select iei prin ordonare fat  a de select ia
proport ional a cu tness-ul.
Scenariile defectuoase ale select iei proport ionale:

2.1. Select ia 16
ˆpopulat ia relativ omogen a
ˆdiferent ele mari ^ ntre performant ele indivizilor
Aceste scenarii nu vor mai  un impediment ^ n cazul select iei prin ordonare.
Ordonarea produce o scalare uniform a ^ n cadrul populat iei, fapt pentru care
situat iile c aut arii de a nu progresa sau convergent a prematur a ^ nt^ alnite la select ia
proport ional a sunt dep a site. Dependent a probabilit at ii de select ie poate  liniar a
sau neliniar a ^ n funct ie de rangul individului.
Dependent a liniar a a probabilit a2tii de select ie pia cromozomului cipoate
formulat a astfel:
pi=1
n
g2(ri1)(g1)
(n1)
[4]
unde: greprezint a num arul mediu de descendent i a steptat i ai celui mai perfor-
mant individ.
Probabilitatea de selectare a celui mai performant individ din populat ie, etichetat
cu rangul neste dat a de valoarea:
pbun=g
n
Probabilitatea de select ie a celui mai slab individ este dat a de:
pslab=2g
n
Num arul mediu de select ii ale celui mai bun individ se poate deduce astfel:
nbun=n
pbun;adic a nbun=g
Presiunea de select ie exprimat a ca num arul mediu de descendent i ai celui mai per-
formant individ este o constant a a procedurii de select ie  si in
uent eaz a ^ n mod
direct echilibrul dintre c autarea global a  si exploatarea zonelor promit  atoare. Ast-
fel, o presiune de select ie mare va produce o exploatare accentuat a a vecin at at ii
celui mai performant individ  si o sc adere a diversit at ii globale a populat iei([4]).
Presiunea mic a a select iei va avea ca efect ment inerea diversit at ii populat iei
 si favorizarea explor arii spat iului de c autare.
O variant a de etichetare neliniar a a populaiei genereaz a probabilit at i de select ie
formulate astfel:
pi=a
(1a)nri
unde: areprezint a un parametru subunitar al procedurii, av^ and semnicat ia
probabilit at ii de select ie a celui mai bun individ din populat ie.

2.2. ^Incruci sarea 17
2.1.3 Select ia nestandard
Acest tip de select ie a fost conceput a de Michalewicz ([7])  si const a ^ n alegerea
^ n mod independent a rcromozomi pentru reproducere, care nu sunt neap arat
distinct i  si rcromozomi distinct i pentru reproducere. Aceste select ii se realizeaz a
^ n funct ie de performant ele cromozomilor.
Un individ cu o performant  a peste medie are o probabilitate mai mare de a
selectat pentru ^ ncruci sare, iar cei cu o performant  a mai mic a dec^ at media au o
probabilitate mai mare de a  selectat i pentru  stergere.
Noua populat ie P(t+ 1) este format a din ( nr) cromozomi din vechea
populat ie, tot i provenit i din P(t) cu except ia celor selectat i pentru  stergere  si
rdescendent i ai celor rp arint i selectat i. De ment ionat c a ecare cromozom se-
lectat pentru modicare este utilizabil doar pentu o singur a operat ie genetic a
(^ ncruci sare, mutat ie).
^In urma select ie apar 3 populat ii intermediare:
P1: cont ine cei rp arint i
P2: cont ine rcromozomi ce vor   ster si
P3: cont ine (n-r) cromozomi care vor  copiat i ^ n P(t+1)
Populat iile P1 siP3nu sunt neap arat disjuncte; un cromozom care are o per-
formant  a peste medie poate  selectat at^ at ^ n P1c^ at  si ^ 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,de-
oarece ^ n cazul select iei nestandard, operatorul de mutat ie se aplic a unui cromo-
zom ^ ntreg  si nu doar unei singure gene ca in cazul celorlalte tipuri de select ie
(proport ional a  si prin etichetare).
2.2 ^Incruci sarea
2.2.1 Considerat ii privind ^ ncruci sarea
Select ia nu asigur a dinamica populat iei. Practic, prin aplicarea operatorului
de select ie, f ar a apelul vreunui operator de variat ie a structurii cromozomilor
populat iei curente, spat iul de c autare nu poate  explorat.
Pentru a provoca migrarea indivizilor ^ nspre zone avantajoase ce corespund
solut iilor globale, este necesar a modicarea structurii acestora. ^Incruci sarea r as-
punde cu succes acestei cerint e. Sursa de inspirat ie a acestui operator genetic o
reprezint a ^ ncruci sarea intercromozomial a natural a ([9]).

2.2. ^Incruci sarea 18
Operatorul de ^ ncruci sare (recombinare) permite permite combinarea seg-
mentelor de cromozomi corespunz^ and p arint ilor, asfel obt in^ andu-se noi indivizi,
numit i descendent i ([4]).
^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 ([6]). 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 ([4], [6], [13]).
Pentru a ^ ntelege mai bine acest mecanism, vom da un exemplu concret. Vom
lua doi indivizi c1 sic2. Ambii au lungimea n= 8. Punctul de t aietur a ales se
a
 a pe pozit ia k= 4. Ace stia sunt reprezentat i ^ n gura 2.3:
Figura 2.3: Reprezentarea p arint ilor ^ n cazul ^ ncruci sarii cu un punct de t aietur a
^In urma^ ncruci s arii, vor ap area doi descendenti, ce vor^ mprumuta caracteristi
ale ambilor p arinti, ca ^ n gura 2.4:
Figura 2.4: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu un punct de t aietur a

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

2.2. ^Incruci sarea 20
Figura 2.6: Reprezentarea descendentilor ^ n cazul ^ ncruci sarii cu doua puncte de
t aietur a
Algorithm 5 ^Incruci sare prin 2 puncte de t aietur a
funct ie ^Incrucis are2Puncte (c1; c2)
fk;tg2f1;2; :::;ng
dac 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.2.3 ^Incrucisarea cu mai multe puncte de t aietur a
Acest operator reprezint a varianta generalizat a a operatorului cu dou a puncte de
t aietur a.
Acest tip de ^ ncruci sare const a ^ n alegera unui num ar arbitrar de puncte de
t aietur a, iar descendent ii se obt in prin concatenarea secvent elor rezultate ^ n urma
deviz arii cromozomilor p arint i. Mention am c a num arul maxim de t aieturi permise
este dat de lungimea cromozomilor.
Ordinea secvent elor ce intr a ^ n component a reprezent arii unui descendent este
stabilit a astfel: se alterneaz a o secvent  a de gene preluate din primul p arinte cu
secvent  a de gene din cel de-al doilea p arinte.
^In cazul unui num ar mare de t aieturi, experimental se poate observa c a apli-
carea acestui operator de ^ ncruci sare cu un num ar mare de puncte de t aietur a
^ ncetine ste convergent a populat iei^ nspre solut ia global a. ^In practic a este preferat a

2.2. ^Incruci sarea 21
varianta cu 2 t aieturi sau o variant a a operatorului cu t aieturi multiple ^ n care
num arul acestora este variabil (generat aleator)  si nu prexat ca un parametru
al algoritmului.
Algoritmul penru ^ ncruci sarea cu mai multe puncte de t aietur a arat a ^ n felul
urm ator: ([9]):
Algorithm 6 ^Incruci sare prin M puncte de t aietur a
funct ie ^Incrucis areMPuncte (c1; c2)
fk1;k2; :::;kmg2f1;2; :::;ng
pentru i= 1lam1execut a
pentru j= 1lamexecut a
dac a kj< k iatunci
interschimb a (kj; ki)
sf^ ar sit dac a
sf^ ar sit pentru
sf^ ar sit pentru
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
sf^ ar sit funct ie

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

2.3. Mutat ia 23
^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 ([4]).
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.
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
([4]):
N=n
l
pm:
Exist a dou a variante a operatorului de mutat ie, acestea ind mutat ia tare
 simutat ia slab a, ce vor  descrise ^ n cele ce urmeaz a print-un algoritm.
2.3.2 Mutat ia tare
Algorithm 7 Mutat ia tare
funct ie MutatiaTare (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 funct io-
neze, adica s a nu produc a o schimbare a valorii pozit iei considerate. ^I 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 ([9]). Astfel, algoritmul mutat iei
slabe este urm atorul:

2.3. Mutat ia 24
Algorithm 8 Mutat ia slab a
funct ie MutatiaSlaba (c; d)
pm2[0;1] .init ializare probabilitatea de mutat ie
pa= 0;5 .init ializare probabilitatea de alocare
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. Com-
portarea algoritmilor genetici se bazeaz a pe observarea anumitor similarit at i ^ ntre
cromozomii ce apart in unor dou a operat ii succesive obt inute prin aplicarea algo-
ritmilor genetici. Similarit at ile ment ionate conduc la o cre stere a performant ei
medii a populat iei de la o generat ie la alta.
Conform literaturii de specialitate ([4]), schema reprezint a o mult ime de cro-
mozomi av^ and anumite pozit ii identice. Mai bine spus, similarit atile dintre cro-
mozomi se numesc scheme.
3.1 Codicarea binar a
Mult imea, ce e alc atuit a din simbolurile 0 si1formeaz a cel mai scurt alfabet,
numit alfabet binar. Codicarea binar a e o funct ie C:D![0;1] ce tranform a
un num ar spat iul de c autare D^ ntr-un sir de valori alc atuite din 0 si1.
Noi vom studia codicare binar a ^ n funct ie de tipul spat iului de c autare, deci
vom avea doua situat ii:
3.1.1 Codicarea binar a ^ n spat iul de c autare unidimen-
sional
Codicarea binar a^ n spat iul de c autare unidimensional se aplic a cusucces^ n cazul
problemelor de optimizare a funct iilor reale de o singur a variabil a ([ ?]).
FieDRce reprezint a spat iul de c autare a solut iilor unei probleme, s2Do
solut ie posibil a a problemei considerate  si c2P(t) reprezentarea binar a a solut iei
25

3.1. Codicarea binar a 26
s.
Domeniul Dreprezint a un interval D= [x; y],x siyreprezint a limitele lui D.
Pentru a obt ine secvent a din codicarea binar a a cromozomului c, se aplic a
funct 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
Pentru aceast a situat ie vom da urm atorul exemplu:
Exemplul 3.1.1 FieD= [3;8], un punct oarecare s= 4;23, are codicarea se
va face cu precizia de p= 102.
Funct ia de transformare devine:
C(s) =s3
83=4;233
5= 0;246
Num arul de cifre binare se deduce cu relat ia:
2n15
1022n
2n15002n
Rezolv^ and inecuat iile, obt inem n= 9.
Se va aplica metoda ^ nmult irilor succesive valorii 0;246, rezult^ and conversia
in binar: 0;00111110111110 :::. Astfel, cromozomul ceste format din primele 8
cifre din reprezentarea binar a a num arului 0:246:c= (0 0 1 1 1 1 1 0 1) .
Procedura invers a codic arii binare const a ^ n convertirea din binar ^ n real al
valorii s0, apoi se aplic a transformarea invers a:
C1(s0) =s0
(yx) +x
pentru a obt ine s2[x; y].

3.2. Scheme  si not iuni conexe 27
Exemplul 3.1.2 Fiec= (0 0 1 1 1 1 1 0 1) cromozomul din exemplul anterior,
la care dorim s a-i a
 am valoarea real a.
^In prima faz a vom converti num arul 0;001111101 ^ n baza 10, unde vom obt ine
valoarea s0= 0;244140625 , ca mai apoi s a se aplice transformarea C1luis0:
C1(s0) =s0
(83) + 3 = 0 ;244
5 + 3 = 4 ;22:
Se constat a c a precizia codic arii este cea impus a ^ n exemplul anterior
p= 0;2460;244 = 0 :002 = 0 ;2
102
, iar valoarea C1(s0) = 4 ;22este valoarea aproximativ a a lui sconsiderat init ial
^ n exemplul anterior.
3.1.2 Codicarea binar a^ n spat iul de c autare multidimen-
sional
^In general, metoda de codicare binar a ^ n spat iul de c autare multidimensional se
aplic a ^ n optimizarea funct iilor reale de mai multe variabile.
Fie un spat iul de c autare al unei probleme date
DRh;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 cromo-
zomul 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
precedent
c= (c1; c2; :::; c k)
3.2 Scheme  si not iuni conexe
Pentru aceasta vom deni urm atoarele not iuni.
Denit ia 3.1 O schem a de lungime reste un element al mult imii f0;1;gr.

3.2. Scheme  si not iuni conexe 28
Denit ia 3.2 FieSo schem a de lungime r. Spunem c a un cromozom x2
f0;1greste o instant  a a schemei Sdac a oric arei pozit ii diferite de * d in S^ i
corespunde o pozit ie din xav^ and aceea si valoare
Denit ia 3.3 Se nume ste pozit ie specic a a schemei Sorice pozit ie din Sdiferit a
de*. Pozit ia respectiv a simbolului *va  ^ nlocuit in egal a m asur a cu valorile 0
sau 1.
Denit ia 3.4 O schem a Sreprezint a tot i acei cromozomi xpentru care toate
pozit iile specice ale lui Scoincid cu pozit iile corespunz atoare din x. Cromozomul
xeste un reprezentant al schemei S.
Urm atoarele exemple vor contura denit iile ment ionate anterior:
Exemplul 3.2.1 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);

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

3.3. Teorema schemelor  si blocuri constructive 30
S3= (   1 1 01);
Ordinul unei scheme se calculeaz a num ar^ and de c^ ate ori se g asesc valorile 0
 si 1 ^ n acea schema. Pentru cele trei scheme date mai sus ordele acestora sunt
urm atoarele:
O(S1) = 6; O(S2) = 5; O(S2) = 4;
Lungimea util a (denitorie) a schemelor este diferent a dintre ultima si prima
pozit ie a unui caracter binar. Pentru cele trei scheme lungimea :
L(S1) = 8; L(S2) = 6; L(S2) = 5;
Vom considera algoritmul genetic standard av^ and urm atoarele caracteristici:
codicarea este binar a  si se aplic a select ia proport ional a, ^ ncruci sarea este cu un
singur punct de t aietur a  si mutat ia tare.
Analiz^ and efectul operatorilor asupra algoritmului, studiat i de Holland ([6])
vom deduce teorema schemelor.
Propozit ia 3.2 Cosider am un algoritm genetic ^ n care act ioneaz a select ia proport ional a.
Daca schema Sarem(S,t) reprezentant i ^ n generat ia P(t) atunci vom avea,
m(S; t+ 1) = m(S; t)F(S)
fmediu
reprezentant i ai schemei S^ n generat ia P(t+1) , 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 ^ ncruci 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);
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).
Probabilitatea 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.

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

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

Capitolul 4
Aplicatii
33

34

Capitolul 5
Aplicatii
35

Bibliografie 36

Bibliograe
[1] Baker J. E. , Adaptive Selection Methods for Genetic Algorithms ,
https://books.google.ro/books?hl=ro&lr=&id=lI17AgAAQBAJ&
oi=fnd&pg=PA101&dq=adaptive+selection+methods+for+genetic+
algorithms+baker+1985&ots=0KsX87Q40A&sig=ard5PKniSg2_
-F8zKDDDDywOoME&redir_esc=y#v=onepage&q=adaptive%20selection%
20methods%20for%20genetic%20algorithms%20baker%201985&f=false ,
1985, 101-111.
[2] Breab an Mihaela, Henri Luchian , Algoritmi genetici ,
http://students.info.uaic.ro/ ~vladut.ungureanu/
Algoritmi-genetici-ID.pdf
Algoritmi-Genetici-Introducere
[3] Constantinescu Cristian , Algoritmi genetici. Introducere ,

Algoritmi-Genetici-Introducere
[4] Dumitrescu D., Algoritmi genetici  si strategii evolutive – aplicat ii ^ n
Inteligent a Articial a  si ^ n domenii conexe , Editura Albastr a, 2006.
[5] Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine
Learning ,
http://www2.fiit.stuba.sk/ ~kvasnicka/Free%20books/Goldberg_
Genetic_Algorithms_in_Search.pdf , Addison Wesley Publishing Com-
pany, 1989.
[6] Holland J. Adaptation in Natural and Articial Systems ,The University of
Michigan Press, 1975.
[7] Michalawicz Z., 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 .
[8] Neagoe Victor, http://www.victorneagoe.com/university/prai/lab5a.
pdf
37

BIBLIOGRAFIE 38
[9] Rotar Cristina, Modele naturale  si Algoritmi Evolutivi , Editura Accent, 2008.
[10] Stoean Constantin, inf.ucv.ro/documents/cstoean/c6/A_14.pdf
[11] Algoritm genetici: cursuri, andrei.clubcisco.ro/cursuri/5master/
sptrm/curs/Algoritmi%20genetici.pdf
[12] Algoritmi Genetici. Studiu de caz: Optimizarea tracului intr-
o retea : http://www.scritub.com/stiinta/informatica/retele/
Algoritmi-Genetici-Studiu-de-c24232.php .
[13] Algoritmi Genetici: Capitolul 15 :https://olidej.wikispaces.com/
file/view/1115+Algoritmi+genetici.pdf .