IA- Algoritmi genetici Partea 1 [617097]

IA- Algoritmi genetici Partea 1
1 1. Introducere

Programarea Genetica reprezinta o directie de cercetare relativ noua si de mare
importanta atat din punct de vedere teoretic cat si, mai ales, din punctul de vedere al
aplicatiilor, consacrandu -se ca un domeniu de sine statator al Inteligente i Artificiale.
Programarea Genetica reuneste teoriile Calcului Evolutiv, care poate fi considerat o
tehnica pentru rezolvarea unor probleme reputate ca fiind grele, din cele mai diferite domenii:
stiinte, tehnica, medicina, economie, politica, etc. Din ace st punct de vedere se evidentiaza
doua aspecte:
 Calculul Evolutiv utilizeaza idei si concepte referitoare la sistemele adaptive
complexe pentru a rezolva probleme computationale in special de optimizare si
cautare.
 Calculul Evolutiv utilizeaza sisteme de c alcul si metode computationale pentru a
modela sistemele adaptive complexe.

Initial ideile Calculului Evolutiv au fost dezvoltate pentru a rezolva probleme de
optimizare complicate, a caror abordare prin metode traditionale este imposibila. Ulterior

IA- Algoritmi genetici Partea 1
2 aceste idei s -au dovedit a fi utile in toate acele situatii in care ne multumim sa emitem o
solutie a problemei fara a pretinde acesteia sa fie neaparat o solutie optima.
Radacinile Calcului Evolutiv s -au dezvoltat in doua directii principale:
– Algoritmii ge netici si Programare Genetica.
– Programarea Evolutiva si Strategiile Evolutive.

facand astfel ca aceasta directie de cercetare sa marcheze un important punct de cotitura in
abordarea problemelor de optimizare, control si cautare. Metodele astfel dezvolta te sunt
generale, independente de problema si de functia criteriu care se doreste a fi optimizata. Mai
mult, proprietatile de continuitate, derivabilitate, convexitate sau de netezime a functiei
criteriu nu mai influenteaza alegerea metodei de optimizare, facilitand astfel utilizarea acestor
metode in multe domenii. Aceste metode s -au dovedit a fi robuste si nu sunt mari
consumatoare de timp.
Algoritmii genetici si celelalte tehnici ale calcului evolutiv sunt utilizate pentru a
minimiza o functie criteriu. Exista insa probleme pentru care nu este simpla formularea
analitica a unei functii criteriu – dar si in acesta cazuri se poate atasa un anumit factor de
viabilitate fiecarei solutii gasite. Acest factor este stabilit in functie de o multime de exemple
de instruire putandu -se folosi si evaluarea intr -un model al problemei. In acest caz metodele
Calcului Evolutiv pot fi utilizate pentru a obtine solutii tot mai performante pornind de la o
populatie de solutii aleatoare.

IA- Algoritmi genetici Partea 1
3 Calculul Evolutiv se reprezinta a fi u n corpus de concepte si metode, avand ca punct
de pornire o metafora biologica. O populatie (aleatoare) de solutii initiale (cromozomi sau
indivizi) este modificata prin operatori de tip biologic (selectie, incrucisare, mutatie, etc.)
acest proces favoriza nd solutiile cele mai bune (viabile). Astfel cei mai buni indivizi
(cromozomi) vor fi selectati ca parinti a unei noi generatii de solutii. In felul acesta calitatea
solutiilor obtinute se imbunatateste facand ca cel mai bun individ obtinut intr -un numar f ix de
generatii sa constituie solutia finala a problemei.

2. Algoritmi Genetici. Algoritmi Evolutivi.

In continuare vom prezenta principiile de baza ale algoritmilor evolutivi si vom
evidentia ideile evolutiei si selectiei naturale care au condus la cla se importante de algoritmi
de cautare si optimizare. Va fi prezentata deasemenea structura generala a unui algoritm
evolutiv.

IA- Algoritmi genetici Partea 1
4 2.1. Metafora evolutiva.

In cadrul Inteligentei Artificiale, punctul de vedere acceptat este ca indeplinirea
oricarei sarcini p oate fi privita ca rezolvarea unei probleme, care la randul sau poate fi
gandita ca o cautare in spatiul solutiilor posibile ale problemei. Acesata cautare poate fi
ghidata de o functie de performanta, procesul de cautare fiind in acest caz insotit de un p roces
de optimizare, astfel, dintre solutiile posibile ale problemei suntem interesati de cea mai buna
sau de o solutie suficient de buna (aproximativ optima).
In cazul problemelor de mare complexitate, gasirea unei solutii optime sau a uneia
acceptabile e ste dificil de obtinut. Tehnicile clasice fie nu sunt aplicabile, fie necesita un timp
de lucru mare. In acest sens Algoritmii Genetici se dovedesc adecvati la solutionarea unor
astfel de probleme.
Algoritmii Genetici [Holland, J – 1975] reprezinta tehnici de cautare si optimizare
avand a punct de pornire o metafora biologica . Aceasta metafora biologica este cea a
mostenirii genetice si a evolutiei naturale .
In cursul evolutiei, toti indivizii sunt confruntati cu problema adaptarii la un mediu
complicat, in continua schimbare sau ostil, astfel fiecare specie „invata”, iar cunoasterea
astfel castigata este codificata in cromozomii speciei. Asadar evolutia reprezinta un proces ce

IA- Algoritmi genetici Partea 1
5 se desfasoara la nivelul cromozomilor. Caracteristicile unui individ sunt stabili te printr -un
proces de decodificare a cromozomilor sai.
Din aceasta perspectiva retinem caracteristicile esentiale ale procesului de evolutie
genetica:
– Cromozomii sunt purtatorii informatiei genetice.
– Fiecare individ al unei specii poseda un numar determin at de cromozomi,
totalitatea acestora reprezentand genotipul sau.
– Cromozomii sunt structuri liniare alcatuite din gene – care poarta caracteristicile
ereditare . O gena controleaza una sau mai multe caracteristici, genele unei
anumite caracteristici ocupa l ocuri determinate in cromozom numite loci. O gena
poate fi in mai multe stari, numite alele (valori ale caracteristicilor).
– Evolutia este un proces ce opereaza la nivelul cromozomilor.
– Selectia naturala reprezinta legatura dintre cromozomi si performantele
indivizilor . Procesul de selectie naturala favorizeaza reproducerea acelor
cromozomi ce codifica structuri de succes.
– Evolutia se realizeaza in procesul reproducerii, aici actionand procese de selectie
si mutatie . De o importanta deosebita sunt procesele de recombinare a
materialului genetic ce caracterizeaza parintii noului individ.

IA- Algoritmi genetici Partea 1
6

John Holland (1965) a avut ideea de a aplica modelul genetic al evolutiei in rezolvarea
unor probleme de cautare si optimizare. Sistemele construite in acest fel utilizeaz a o polulatie
de cromozomi ce reprezinta o multime de solutii potentiale . Prin procesele de selectie,
mutatie si recombinare sistemul evolueaza spre stari mai apropiate de optim, selectia
cromozomilor pentru fiecare modificare facandu -se folosind o functie de evaluare
(adecvare) sau fitness .
Algoritmii genetici reprezinta o clasa de algoritmi evolutivi. Algoritmii evolutivi
implementeaza proceduri care imita procesele de adaptare / cautare aparute in evolutia
naturala. Toti algoritmii evolutivi folosesc pop ulatii in care fiecare individ reprezinta un
punct din spatiul de cautare. Algoritmii evolutivi se bazeaza pe principiul invatarii colective
intr-o populatie.
Programarea evolutiva, strategiile evolutive si algiritmii genetici sunt cele mai cunoscute
tipur i de algoritmi evolutivi.

IA- Algoritmi genetici Partea 1
7 2.2. Structura unui algoritm evolutiv.

Algoritmii evolutivi reprezinta mai multe clase de metode aleatoare de cautare.
Fiecare individ al populatiilor implicate in procesul de cautare se descrie printr -un singur
cromozom, asa dar genotipul fiecarui individ contine un singur cromozom.
Orice algoritm evolutiv (sau program evolutiv) foloseste o populatie de indivizi
(cromozomi) care se modifica prin intermediul unor operatori genetici cum ar fi cei de
selectie, mutatie, recombinar e, etc. Timpul in cazul algoritmlor evolutivi variaza discret.
Notam cu P(t) populatia de cromozomi de la momentul t, unde t = 0, 1, 2, … .
Fie X spatiul de cautare (spatiul starilor problemei). Fiecare individ (cromozom)
reprezinta un element din X, adica o solutie posibila a problemei. Un cromozom este un sir
finit peste elementele unui vocabular, evaluarea calitatii indivizilor din spatiul de cautare
facandu -se cu ajutorul unei functii de performanta (functie de adecvare sau evaluare), notata
R X :f
.
Fie
} x…, , x,{x P(t)t
nt
2t
1 populatia la momentul t. P(t) reprezinta o generatie . Noua
generatie P(t+1) se formeaza selectand cei mai performanti indivizi din P(t) si aplicand
asupra lor operatori genetici de recombinare, mutatie, etc.

IA- Algoritmi genetici Partea 1
8 2.2.1. Operatori genetici.

Operatorul de recombinare este folosit pentru a crea noi indivizi folosind segmente
(subsiruri) a doi sau mai multi cromozomi. Operatorul de recombinare se poate defini ca o
aplicatie
q pX X:R . In acest caz spunem ca oper atorul R realizeaza o transformare de tipul
(p,q) in care p parinti dau nastere la q descendenti.

Operatorul de mutatie reprezinta o transformare unara de forma
X X:m .
Operatorul de mutatie m creeaza noi indivizi prin schimbari (de regul a mici) ale unui singur
individ. De exemplu m permite schimbarea unei singure gene a individului (cromozomului)
respectiv. Mutatia realizeaza astfel mici perturbari ale cromozomilor obtinuti prin
recombinare.

Operatorul de supravietuire decide care dintre cromozomi – parinti si descendentii
acestora obtinuti prin recombinare si mutatie – vor forma efectiv noua generatie. Fiecare tip
de algoritm evolutiv poseda un mecanism propriu ce realizeaza supravietuirea.

Populatia initiala se genereaza de regula prin selectarea aleatoare a unor puncte din
spatiul de cautare. In unele cazuri cunostiintele specifice despre domeniul problemei pot servi
pentru a ghida cautarea.

IA- Algoritmi genetici Partea 1
9 Criteriul de oprire pentru un algoritm evolutiv este de regula legat de numarul de
generatii. C el mai performant individ al ultimei generatii – sau cel mai performant individ din
intreaga istorie a procesului – reprezinta solutia obtinuta pentru problema in discutie.

2.2.2. Structura generala a unui Algoritm Evolutiv.

Consideratiile de mai sus conduc la urmatoarea structura generala a unui algoritm
evolutiv, descrisa in pasi:

P1. Se pune t = 0.

P2. Se initializeaza populatia P(t).

P3. Se evalueaza P(t) utilizand o functie de performanta f.

P4. Atat timp cat < conditie > se executa
{
Selectia din P(t)  P1(t);
Recombinarea asupra lui P1(t)  P2(t);

IA- Algoritmi genetici Partea 1
10 Mutatia asupra lui P2(t)  P(t+1);
t = t + 1;
Evaluarea lui P(t);
Supravietuirea in P(t).
}

Observatie: La pasul P4 apare o conditie de oprire a algoritmului care se refera, de
regula, la atingerea num arului de generatii prescris.

Orice procedura evolutiva trebuie sa furnizeze urmatoarele elemente:
– O reprezentare genetica a spatiului de cautare – spatiul starilor problemei
sau spatiul solutiilor potentiale ale problemei.
– O populatie initiala de solutii potentiale.
– O functie de evaluare care masoara performanta fiecarui individ in raport
cu scopul urmarit.
– O metoda de selectie a cromozomilor pentru modificare si recombinare.
– Operatorii genetici pentru crearea de noi cromozomi prin recombinatie,
mutatie, inversiune, etc.

IA- Algoritmi genetici Partea 1
11 – Valorile parametrilor care apar in algoritmul evolutiv: dimensiunea
populatiei, probabilitatile de aplicare a diferitilor operatori genetici,
numarul total de generatii, etc.

3. Structura unui Algoritm Genetic.

In continuare vor fi prez entate notiunile fundamentale referitoare la algoritmii
genetici, componentele si structura acestora. Se indica modul in care un algoritm genetic
realizeaza cautarea in spatiul problemei si se analizeaza compromisul intre exploatarea si
explorarea spatiulu i de cautare. Tot aici se va defini notiunea de schema evidentindu -se
modul in care, prin prelucrarea simultana a unui numar mare de scheme, este realizat un
paralelism intrinsec specific algoritmilor genetici.

Intr-un algoritm genetic, fiecare element al spatiului de cautare se poate reprezenta ca
un individ (cromozom) al unei populatii. Dupa cum s -a precizat anterior, fiecare cromozom
este constituit dintr -o multime de elemente numite caracteristici sau gene . Fiecare gena se
poate afla in mai multe stari , numite alele . Acestea din urma indica valori – nu neaparat
numerice – ale caracteristicilor (genelor). In abordarile standard numarul de gene dintr -un

IA- Algoritmi genetici Partea 1
12 cromozom este constant pentru o problema data si defineste lungimea cromozomului ,
valoare pe care o vom nota in continuare cu r.

Fie V alfabetul ce corespunde valorilor alelelor. Un cromozom se reprezinta printr -o
secventa de lungime r formata cu elementele lui V. Rezulta astfel ca orice cromozom este un
element din
rV . Alfabetul V depinde de clasa de probleme la care se aplica algoritmul
genetic. Lungimea cromozomilor este stabilita in functie de natura probelemei, cea mai
raspandita fiind codificarea binara a valorilor genelor. In acest caz alfabetul este de forma
}1 ,0{V
, iar un cromozom este o secventa binara de lungime
1r .

3.1. Echilibrul explorare – exploatare.

Fiecare cromozom reprezinta o solutie potentiala a problemei. Un algoritm genetic
realizeaza cautarea in spatiul solutiilor problemei prin modificarea unei populatii de
cromozomi. Cautarea solutiei intr -un spatiu complex implica realizarea unui compromis intre
doua obiective aparent contradictorii: exploatarea celor mai bune solutii disponibile la un
moment dat si explorarea robusta a s patiului solutiilor posibile. Cele doua aspecte corespund
cautarii locale si respectiv cautarii globale in spatiul solutiilor problemei.

IA- Algoritmi genetici Partea 1
13 Obtinerea unui echilibru intre exploatarea informatiei obtinute pana la momentul
curent si explorarea spatiului starilo r pentru a obtine solutii noi, mai bune, este specifica
tuturor metodelor puternice de optimizare. Daca solutiile obtinute sunt exploatate prea mult
atunci se atinge o convergenta prematura iar procedura se opreste cu o solutie care poate sa
nu fie accepta bila. Pe de alta parte, daca accentul cade prea puternic pe explorare, este posibil
ca informatia deja obtinuta sa nu fie utilizata in mod corespunzator. Acest lucru face ca
timpul de cautare sa creasca foarte mult, ceea ce apropie procedurile respective d e metodele
aleatoare de cautare. Vom indica in continuare procedeul in care unele clase de metode
rezolva problema echilibrului dintre exploatare si explorare.

Metodele de coborare – de tip gradient – reprezinta o situatie extrema in compromisul
explorare – exploatare. Ele sunt strategii care exploateaza cea mai buna solutie pentru
imbunatatiri ulterioare a acesteia. Se neglijeaza explorarea spatiului de cautare si, in
consecinta, metoda sufera din cauza caracterului local al optimului gasit.
Metodele de cautare aleatoare reprezinta cealalta situatie extrema. Cautarea pur
aleatoare este un exemplu tipic de strategie care exploreaza spatiul de cautare, ignorand
exploatarea regiunilor promitatoare ale spatiului. Metodele de acest tip sunt lente acest lucru
facandu -le inaplicabile problemelor practice dificile.
Metoda recoacerii simulate (simulatea annealing) reprezinta o procedura de cautare
aleatoare in care este prezenta si exploatarea. Acest lucru se realizeaza printr -un mecanism ce

IA- Algoritmi genetici Partea 1
14 asigura stabilirea unui echilibru la fiecare valoare a unui parametru avand semnificatia
temperaturii termodinamice.

Algoritmii genetici reprezinta o clasa de strategii de cautare generale – independente
de domeniu – care realizeaza un compromis rezonabil intre explorarea si ex ploatarea
spatiului solutiilor. Studiile teoretice au aratat ca algoritmii genetici realizeaza acest
compromis de o maniera aproape optimala. Explorarea si exploatarea sunt aspecte care pot fi
controlate aproape independent, ceea ce permite o mare flexibil itate in proiectarea acestor
algoritmi.

3.2. Rezolvarea problemelor utilizand Algoritmi Genetici.

Pentru rezolvarea unei probleme folosind un algoritm genetic este necesara definirea
de catre utilizator a unei functii care masoara performanta fiecarui c romozom. Acesta functie
de performanta depinde de abilitatea utilizatorului de a codifica in mod adecvat problema de
rezolvat. Daca se rezolva o problema clasica de optimizare sau una de optimizare
combinatoriala, functia de performanta poate coincide cu f unctia criteriu asociata problemei
sau se obtine prin transformari simple (de exemplu prin scalare) aplicate functiei criteriu. In

IA- Algoritmi genetici Partea 1
15 alte situatii functia de evaluare reprezinta o functie de cost, o functie de castig, etc., sau este
dedusa dintr -o astfel de functie.
Un algoritm genetic este o procedura iterativa de cautare globala avand drept scop
optimizarea unei functii de evaluare. Algoritmul lucreaza in paralel asupra unei populatii de
solutii potentiale – cromozomi – distribuite peste intreg spatiul de c autare. In mod obisnuit
valoarea performantei unui cromozom este independenta de performantele celorlalti indivizi
ai populatiei. O alta posibilitate este de a considera o functie de adecvare implicita ale carei
valori depind si de restul populatiei prin i ntermediul anumitor interactiuni intre indivizi. In
acest caz putem vorbi de o adaptare intrinseca care asigura co-evolutia indivizilor.
Dinamica procesului de cautare generat de un algoritm genetic se realizeaza prin
combinarea si modificarea cromozomilor , scopul fiind gasirea combinatiei optime, adica a
acelei combinatii ce corespunde adecvarii maxime. La fiecare iteratie a algoritmului se
creeaza o noua populatie, numita generatie . Toate generatiile au acelasi numar de indivizi si
se admite ca, in genera l, noua generatie consta din indivizi mai performanti, adica mai bine
adaptati la mediul reprezentat de functia de adecvare (performanta). Cu succesiunea
generatiilor se va inregistra o tendinta de evolutie a indivizilor spre optimul global al functiei
de adecvare.

Obtinerea unei noi generatii plecand de la precedenta are loc in trei etape:

IA- Algoritmi genetici Partea 1
16 1. Evaluarea – algoritmul genetic calculeaza valoarea functiei de adecvare
pentru fiecare individ al vechii populatii.
2. Selectia – algoritmul genetic selectioneaza indivizi i unei populatii P(t) in
functie de performantele lor. Indivizii selectionati vor reprezenta o populatie
intermediara
1P . Cromozomii populatiei
1P devin parintii noii generatii
P(t+1).
3. Recombinarea si modificarea – algoritmul genetic recombina si modifica
indivizii selectionati. In acest scop se utilizeaza operatori genetici de
incrucisare (recombinare), mutatie, inversiune, etc. Din punct de vedere
algoritmic, operatorii genetici reprezinta metode de a schimba loc al solutiile
reprezentate de parinti (mutatia si inversiunea) sau de a combina aceste solutii
(incrucisarea). Incrucisarea consta intr -un transfer de gene intre cromozomi.

Fiecarui operator genetic ii corespunde o probabilitate de aplicare, aceste
probabi litati reprezentand parametrii algoritmului. Operatorii genetici de
recombinare si modificare se aplica, cu probabilitatile respective, asupra
populatiei intermediare. Aplicand operatorul de incrucisare asupra populatiei
1P
se obtine o populatie
2P . Asupra indivizilor din
2P se aplica operatorii de
mutatie, inversiune, etc. Indivizii din
2P impreuna cu acei indivizi din
1P care nu

IA- Algoritmi genetici Partea 1
17 au suferit recombinarea vor constitui noua generatie P(t+1). Sunt posibile
numeroase alte modalitati de a selecta cromozomii populatiei P(t+1).

3.3. Structura Algoritmilor Genetici.

Structura unui algoritm genetic este identica, in esenta, cu cea a unei proceduri
evolutive. C romozomii utilizati au lungime constanta . De asemenea, n umarul cromozomilor
in fiecare generatie este constant, principalii operatori utilizati fiind cei de mutatie,
incrucusare si inversiune.

3.3.1. Algoritmul Genetic fundamental (canonic).

Algoritmul genetic standard (algoritmul canonic) are ca operatori princip ali
incrucisarea si mutatia. Structura acestui algoritm are forma:

P1. Se pune t = 0.
P2. Se initializeaza aleator populatia P(t).

IA- Algoritmi genetici Partea 1
18 P3. Se evalueaza cromozomii populatiei P(t).
In acest scop se utilizeaza o functie de performanta ce depinde de problema
data.
P4. Atat timp cat < non C > se executa
{
P4.1. – selecteaza cromozomii din P(t) care vor contribui la formarea noii
generatii. Fie
1P multimea cromozomilo r selectati, ce reprezinta o
populatie intermediara.
P4.2. – se aplica cromozomilor din
1P operatorii genetici. Cei mai utilizati
sunt operatorii de mutatie si incrucisare, dar in functie de problema
pot fi alesi si alti operatori: inversiune, reordonare, operatori
speciali.
Fie
2P populatia astfel obtinuta – descendentii populatiei P(t).
Se sterg din
1P parintii noilor indi vizi obtinuti.
Cromozomii ramasi in
1P sunt atribuiti populatiei
2P .
Se construieste noua generatie punand:
– P(t+1) =
2P .
– se pune t = t+1.
– se evalueaza P(t)

IA- Algoritmi genetici Partea 1
19 }

Observatii:

1. Conditia de oprire C se refera, de regula, la atingerea numarului de generatii
specificate. Daca numarul maxim admis de generatii este N, atunci conditia de
oprire C este t > N.
2. De obicei se admite ca rezultatul algoritmului este codificat de cel mai
performant individ din ultima generatie. In realitate, insa, nimic nu ne
garanteaza ca un individ mai performant nu a fost obtinut intr -o generatie
anterioara, deci este natural ca la fiecare pas (la fiecare moment t) sa retinem
cel mai bun individ care a fost generat pana atunci. Pentru a implementa
acesta strategie sunt necesare cateva mici modificari in algoritmul de mai sus.
3. Modificarea propusa in observatia precedenta poate fi extrem de utila, astfel
asigurandu -ne ca cea mai buna solutie gasita nu s -a pierdut pe parcurs.
4. Sunt posibile si alte numeroase variante de supravietuire. Putem de exemplu
sa consideram ca cei mai buni q indivizi sin generatia P(t) vor fi inclusi in
mod automat in generat ia urmatoare. Totodata ei vor putea sa sufere si operatii
de recombinare, mutatie, etc.