Algoritmi Genetici Vol I [631568]

0

ALGORITMI GENETICI
Vol.I

S L A T I N A
2014

VOL.I

ISBN 978 -973 -0-16089 -5

ALGORITMI GENETICI
LUȚĂ COSTINA CLAUDIA

1

ALGORITMI GENETICI
Vol.I

Tehnoredactare : Luță Costina Claudia

Referent științific:
Profesor gradul I ~ Gabriela Raluca Ionică ~
Inspector școlar de specialitate I.S.J. Olt

Autor:
Profesor gradul I ~Luță Costina Claudia ~
Colegiul Tehnic “Alexe Marin” Slatina

2

ALGORITMI GENETICI
Vol.I
CERCETARE ȘTIINȚI FICĂ

CAPITOLUL I

Noțiuni int roductive

1.1 Istoric

Rezolvarea problemelor care implică folosirea unor expresii m atematice a
fost intens studiată în ultimele decenii. In matematică optimizarea este înțeleasă
ca însemnând găsirea unei soluț ii optime. In acest scop s -au obținut rezultate
importante în calculul diferențial, calculul variaț ional, controlul optimal,
cercetări operaț ionale. Drumul de la rezultatele teoretice, re feritoare la
teoreme de existență , unicitate, caracterizare a soluț iei, etc., la optimizarea
efectivă este de multe ori prea lung, fie datorită complexităț ii prea mari a
problemelor reale față de modelul matematic utilizat, fie datorită complexităț ii
(timp, memorie) algoritmilor utiliza ți.
La mijlocul anilor ’70, odată cu cre șterea performan țelor calculatoarelor
și, implicit, a complexităț ii problemelor reale ce se puteau rezolva cu
ajutorul calculatorulu i, au devenit frecvente situațiile î n care modelele clasice
de opti mizare nu mai conduceau la soluț ii acceptabile pentru probleme
modelabile pe calculator. Tot mai frecvent, probleme din biologie, climatologie,
chimie, mecanica, analiza datelor, etc., probleme ale că ror modele includ sute
sau mii de variabile, ale căror funcții de optimizat prezintă multiple optime
locale și neregularităț i nestudiate din punct de vedere numeric, rămâneau
nerezolvate sau cu soluț ii aproximate grosier.

3

ALGORITMI GENETICI
Vol.I
Studiin du-se excele nta adaptare a ființelor vii, în ceea ce priveș te fo rma,
structura, funcțiile și stilul de viața, numeroș i cercet ători au ajuns la concluzia că
natura oferă soluț ii op timale la problemele sale, soluț ii superioare oric ăror
performanț e tehnologice. S-a dem onstrat chiar matematic optimalitatea unor
sisteme biologice: raportul diametrelor ramificaț iilor arterelor, pozi ția punctel or
de ramificare a vaselor de sâ nge, valoarea hematocritu lui (procentul volumului
particulelor solide din sânge). În consecință au apărut primele încercă ri de
imitare a procesului de evoluție naturală .
In anul 1970 profesorii H ans-Paul Schwefel (Dortmund) și Ingo
Rechenberg (Berlin) având de rezolvat o problemă de mecanica fluidelor,
referitoare la optimizarea for mei unui corp ce se deplasează într -un fluid, au
căutat o noua tehnica de optimizar e deoarece metodele cunoscute până î n acel
moment nu conduceau la o solu ție acceptabilă. Ideea lor a î ntruchipat conj ectura
lui Rechenberg, ramasă până azi justificar ea fundamentală a aplică rii
tehnicilor evolutive: ”Evoluția naturală este, sau cuprinde, un proces de
optimizare foarte eficient, care, prin simulare, poate duce la rezolvarea de
probleme dificil de optimizat” . Modelul de simulare propus de Rech enberg ș i
Schwefel este cunoscut azi sub numele de ”strategii evolutive” și iniț ial se
aplica doar problemelor de optimiza re de variabila continua. Soluț iile candidat x
se reprezintă în virgulă mobilă iar individul i căruia i se aplica procesul evolutiv
consta din aceasta reprezentare ș i dintr -un parametru al evolu ției, notat s,
reprezentat tot în virgula mobila: i = (x, s). La fiecare pas solu ția curentă este
modificată pe fiecare componentă conform lui s și în cazul unei îmbun ătățiri
este înlocuit ă cu cea nou obț inută. Parametrul s joaca rolul pasului din
metodele iterative clasice și este astfel folosit încât să fie respectat principiul
”mutaț iilor mici” .
A doua direcț ie de studiu s -a conturat la Universitatea San Diego;
punctul de pornire a fost tot simularea evoluț iei biologice iar structura de
date aleas ă a fost mașina cu număr finit de stări. Urmâ nd aceasta abordare,

4

ALGORITMI GENETICI
Vol.I
Fogel generează programe simple, anticipâ nd ”programarea genetica”.
După mai mul ți ani de studiere a simulării evo luției, John Holland de la
Universitatea Michigan a propus in 1973 conceptul de ”algoritm genetic” .
Au fost abordate probleme de optimizare discretă iar structura de date aleasa a
fost șirul de biți. Într -o accepțiune strictă, noț iunea de a lgoritm genetic se
refera la modelul studiat de Holland si de studentul sau De Jong. Î ntr-un
sens mai larg, algoritm genetic est e orice model bazat pe ideea de
populație și care folosește operatori de selecție ș i recombin are pe ntru a genera
noi puncte în spațiul de că utare.

5

ALGORITMI GENETICI
Vol.I
1.2 Importanta temei in actualitate

În acesta carte am prezentat principalele direcții ale algori tmilor
evolu tivi, în special al algorit milor genetici. Aplica țiile practice ale acestor
algorit mi sunt nenumărate.
Principalele caracteristici ale algoritmilor gen etici, comparativ cu cei
tradiț ionali sunt:
– sunt algoritmi probabiliș ti ce îmbină căutarea dirijată cu cea aleatoare;
– realizeaz ă un echilibru aproape perfect între explorarea spaț iului st ărilor și
găsirea celor mai bu ne soluț ii;
– în timp ce metodele clasice de căutare acț ioneaz ă la un moment dat a supra
unui singur punct din spațiul de căutare, algoritmii genetici mențin o mulțime (=
populaț ie) de soluții posib ile;
– algoritmii genetici nu acționează direct asupra spa țiului de că utare ci asupra
unei codific ări a lui;
– sunt mai robuști decâ t algoritmii clasici de optimizare și decât metodele de
cautare dirijată ;
– sunt simplu de utilizat și nu cer propriet ăți im portante ale funcț iei obiectiv,
precum continuitate, derivabilitate, convexitate, ca in cazul algoritmilor clasici;
– pot gă si soluții optime sau aproape optime cu o mare probabilitate.

Caracteristicile lor au fă cut ca algoritmii genetici să fie utilizați î n cele
mai diverse domenii:
– optimizare:
– optimizare numerică și combinatorică ,
– proiectarea circuitelor, a sistemelor de conducte și a liniilor
de comunicaț ie,

– proiectarea avioanelor;
– planificarea proceselor de producț ie;
– programare automata;

6

ALGORITMI GENETICI
Vol.I

– scrierea programului LISP pentru o problema data;
– obținerea de algoritmi de sortare;
– instruirea mași nilor = machine learning ;
– deplasarea î ntr-un labirint,
– controlul deplasă rii unui robot ;
– proiectarea rețelelor neuronal e;
– deducerea regulilor pentru rezolvarea diferitelor
probleme;
– rezolvarea un or probleme dificile de tip joc;
– proiectarea controlorilor inteligenți;
– probleme de predicție a sistemelor haotice, vremii,
evoluției pieț ei financiare ;
– modelar ea unor procese complexe din: economie,
politica, ecologie, etc.

Ei sunt folosiți în do menii tot mai neașt eptate cum ar fi proiectare a
aripilor de avion sau la proie ctarea formei stațiilor orbitale. Dacă ați ales să
rezolva ți o proble mă genetic, trebuie să țineți cont de câteva sfaturi.
 Pentru a rezolva o probl emă cu algorit mi genetici trebui e să o
transformați mai întâi într-o probl emă de optimizare, adică să se
minimizeze sau să se maximizeze o valoare (cel mai scurt lanț
hamiltonian, c ea mai mare componentă intern stabil ă etc.).
 Algori tmii genetici sunt algoritmi euristici, adică soluția găsită de ei
nu este întotde auna cea mai bun ă, dar se află într-o vecinătate a
soluției optime. Deci, dacă aveți de ales între un algoritm
polino mial care rezolvă sigur proble ma și un algorit m genetic, ar fi de
preferat să folosiți algorit mul polino mial.
 Algorit mii genetici, de obicei, au complexitate polino mială. De aceea ei

7

ALGORITMI GENETICI
Vol.I
sunt foarte des utilizați pentru a rezolva proble mele dificile (NP-
complete). Rezultatele obținute sunt foarte apropiate de cele obținute de
algorit mii siguri, dar care au rulat mii de ore.
 Dacă probl ema este complexă folosiți un algorit m genetic și nu o
strategie evolutivă . De obicei mutația este un operator de căutare
slab, deci, dacă se folosește doar acesta, există șanse mari să se
obțină o soluții locale și nu globale.
Concluzie – Puterea algoritmilor genetici constă în ușurința cu care sunt
implementați și în faptul că dau de multe ori rezultate bune, chiar dacă nu
găsesc întotdeauna optimul global.

8

ALGORITMI GENETICI
Vol.I
CAPITOLUL II

Aspecte teoretice de baza

2.1 Calcul evolutiv

În general, orice sarcină abstractă care trebuie îndeplinită, poate fi privită
ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi percepută ca o
căutare în spațiul soluțiilor potențiale. Deoarece, de obicei, căutăm cea mai bună
soluție, putem privi acest proces ca fiind unul de optimizare. Pentru spații mici,
metodele clasice exhaustive sunt suficiente; pentru spații mari, pot fi folosite
tehnicile speciale ale inteligenței artificiale.
Rezolvarea problemelor folosind metode evo lutive est e un domeniu de
tradiț ie. El î și are ră dăcinile în anii '50, când mai mulți cercetă tori au preluat
metafora evolutivă din natură , aplicând -o la rezolvarea problemelor din diverse
domenii. Met afora evolutivă este transpusă, informatic, într -un numă r foarte
mare de algoritmi. Totu și, câteva considerente generale pot fi indicate.
Se lucrează cu o populație (vector, listă ) de posibile soluții . Acestea se
mai numesc uneori și indivizi, cromozomi e tc. Indivizii populației inițiale sunt
generați aleator. Cu ajutor ul selecț iei și al operatori lor genetici indivizii
evoluează și, eventual, vor converge către soluț ie.
Indivizii sunt evalua ți pe baza unei așa -zise funcț ii de fitness (calitate).
Fitness în seamnă speranță de via ță. Cu cât un individ este mai performant, c u
atât speranța lui de viață este mai mare.
Asupra indivizilor din popula ție se aplică operatori genetici. Acești
operatori sunt dependenț i de reprezentare. Dintre cei mai răspândiț i operato ri
genetici amintim încruciș area și mutația. Prin încrucișare, de obicei, doi părinț i

9

ALGORITMI GENETICI
Vol.I
dau naștere a doi fii. Prin mutație se aplică o mică "perturba ție" a valorii unui
individ. De obicei, nu to ți indivizii sunt ale și pentru aplicarea operatorilor
genetici. Modul și ordinea în care se aplic ă operatorii gen etici asupra indivizilor
variază foarte mult. De exemplu, într -un algoritm genetic din populație sunt
selectați indivizi în funcț ie de fitness -ul lor. Indivizii sele ctați sunt introduș i
într-o populaț ie inte rmediară . Indivizii din această populație intermediară sunt
supu și operatorilor genetici de încruci șare și mutaț ie. Indivizii rezulta ți în urma
acestor opera ții constituie "urmă toarea genera ție", adică o nouă populație care va
fi din nou supusă selecț iei și anumit num ăr de genera ții.
Metodele calculului evolutiv se numără printre aceste tehnici; ele folosesc
algoritmi ale căror metode de căutare au ca model câteva fenomene
naturale: moștenirea genetică și lupta pentru supraviețuire. Cele mai
cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici,
strategiile evolutive, programarea genetică și programarea evolutivă. Există și
alte sisteme hibride care încorporează diferite proprietăți ale paradigmelor de
mai sus; mai mult, structura oricărui algoritm de calcul evolutiv este, î n mare
măsură, aceeași.
Ín ultimii 30 de ani, s -a manifestat un mare interes în rezolvarea
problemelor de sistem bazate pe principiile evoluției și eredit ății. Astfel de
sisteme mențin o populație de soluții potențiale, ele au unele procese de selecție
bazate pe fitness individual, și câ țiva operatori genetici. Un astfel de sistem este
o clasa a evoluției strategice i.e, algoritmi care imita principiile evoluției
naturale pentru problemele de optimizare de parametru(Rechembe rg,
Schwefel). Evolu ția programă rii lui Fogel este o tehnica de c ăutare într-un
spațiu finit, mi c de mașini. Tehnologiile de că utare a mașinii lui Glover Scatter
mențin o populație de puncte de referință, generâ nd o stare speciala
prin greutatea combinațiilor liniare.

10

ALGORITMI GENETICI
Vol.I
Alte tipuri de sisteme evoluționare sunt Holland‘s Genetic Algorithms. În
1990 Koza a propus un astfel de sistem evoluțional, ge netic programming,
pentru a că uta cel mai potrivit program de computer sa rezolve o
problema particular a . Folosind un termen comun E.P pentru toate
sistemele(incluzând sistemele descrise mai sus). Structur a evoluției
programului este ară tat astfel:

procedura
algorit m_evolutiv
t  0
creare P(t)
evaluare P(t)
cât timp nu condi ția de terminare
t  t + 1
selectare
P(t) din P(t-1)
modifi care P(t)
evaluare P(t)
sfârșit
sfârșit pro cedura

În cele ce urmează voi explica algorit mul gener al propus mai sus.
Evoluția progr amului este un algorit m probabilistic ce conține
elemente distincte, P(t)={x 1t, x 2t, …xnt}. Algorit mii evolutivi mențin o
popul ație de indivizi la fiecare iterație t. O popul ație poate fi privi tă ca fiind
un vector de valori. Fiecare element distinct reprezintă o soluț ie poten țială a
problemei în cauza și în orice progra m, este interpretat ca S structura de date.
Fiecare solutie x1t, x2t,.., xnt este evaluata pentru a da o oarecare măsura a
„fitness -ului“ său.
Fiecare individ (element al vectorului) repre zintă o soluție
poten țială a probl emei și este implementată sub forma unei structuri de
date S. Un individ este uneori numit și cromozom. Fiecare solu ție este
evaluată ca fiind o măsură a "fitness -ului" său (speranței de viață). Acest
fitness reprezintă c alitatea individulu i. De obicei, cu cât indiv idul este mai

11

ALGORITMI GENETICI
Vol.I
promițător, cu atât fitness-ul său este mai mare.
Există unele proble me în cazul c ărora fitness -ul trebu ie să fie minimizat.
O nouă popula ție (itera ția t + 1) se formează prin selectar ea mai multor
potriviri individuale , alegând cei mai promițători indivi zi (pasul de selecție)
din popula ția curentă. O parte din membri popul ației nou formate suferă
transfor mări (pasul de modificare) prin „operarea —genetica“ a noilor soluții .
Vorbim despre o trans formare unica e evoluției progra mului.

12

ALGORITMI GENETICI
Vol.I
2.1.2 Operatori genetici – calculul evolutiv

Oper atorii genetici sunt, de fapt, proceduri care opere ază asupra
elementelor vectorului popula ție. Există doi operatori g enetici prin cipali:
 un operator unar mi de transformare numit muta ție, care creează un nou
individ printr -o mică modificare a unui ind ivid ales (mi: S  S);
 un operator mai puternic cj numit încrucișare, care creează noi indivizi
combinând părți din doi sau mai mulți indivizi (cj: S  …  S S) (de
cele mai multe ori se folosesc do i părin ți).
După un anumit număr de generații algorit mul converge: se speră că cel
mai promițător indiv id ajunge la o valoare cât mai apropi ată de soluția
optimă. În ciuda similarită ților puternice între diferitele tehnici de calcul
evolutiv, există și multe diferenț e. Acestea sunt date, în princip al, de
structurile de date folosite pentru a repre zenta un individ și de ordine a în
care se aplică operatorii geneti ci. De ex emplu, cele două linii din algorit mul
de mai sus:

selectare P(t) din P(t-1)
modificar e P(t)

pot apărea în ordine inversă: (în strategiile evolutive , întâi se modifică
popula ția și apoi este formată o nouă popula ție prin procesul de selecție, in
timp ce într-un algorit m genetic întâi se aplică selec ția, iar apo i intră în
acțiune operatorii geneti ci de trans formare). Decembrie 2001
31Exist ă, de asem enea, și alte diferențe între metode. Una dintre
acestea ar fi cea referitoare la metodele de selecție care includ:
 selecția proporțională , unde șansa (probabilit atea) ca un individ să fie
selectat este proporțion ală cu fitness -ul lui;
 metoda rangului , în care toți indivizii din populație sunt sortați în funcție de
fitness, iar probabi litatea

13

ALGORITMI GENETICI
Vol.I
(șans a) ca ei să fie selectaț i este fixată de întreg proc esul de evoluție(de
exemplu, probabilit atea de selecție a celui mai promițător individ este 0.15, a
individului ur mător este 0.14, etc.; cel mai promițător individ are cea mai
mare probabilitate și suma totală a probabilită ților indiv izilor este1);
 selecția prin turnir (prin concurs) unde un anumit număr de indivizi (de
obicei doi) luptă pentru a fi selecta ți în nou a generație.
Aceast ă competiție (turnir) este repetată până sunt selectați un
număr de indivizi egal cu dimensiune a popula ției. Pentru fiecare dintr e
aceste categorii de selecție există și alte detalii i mportant e. Câteva
exemple sunt:
 selecția propor țională poate necesita folosir ea unor metode de trun chiere;
 exist ă diferite moduri pentru stabilire a probabilită ții în metoda rangului ;
 dimensiune a mulțimii alese pentru concurs poate juca un rol semnificativ
în metoda selecției prin turnir.
Trecerea de la o gener ație la alta poate fi efectuată în două variante:
 algoritm g eneraționa l (noua popula ție este formată doar din descenden ți ai
vechii generații);
 algoritm non-gene rațional (în noua popula ție sunt introduș i, de obicei, cei
mai promițători indivizi din cele două populaț ii, cea a părin ților și cea a
descendenților).
Este posibil, de asemenea, să creăm puțini (în particular, unul
singur) descendenți, care înlocui esc câțiva (cei mai puțin promițători)
indivi zi. Ca o regul ă generală trebuie reținut faptul că, în ma joritatea
cazurilor, este de preferat să se utilizeze un model elitist, care păstreaz ă cei
mai promițători indiv izi dintr-o generație și îi adaug ă automat generației
următoare (aceasta înseamnă că, dacă cel mai pro mițător individ din generația
curen tă este pierdut datori tă selecției sau operatorilor genetici, sistemul
forțează apariția lui într-o genera ție următoare). Un astfel de model este

14

ALGORITMI GENETICI
Vol.I
foart e folositor pentru re zolvar ea multor proble me de optimizare. Totuși,
structurile de date folosite pentru proble me parti culare, împreună cu o
mulțime de operatori geneti ci, constituie componenta esențială a oricărui
algorit m evolutiv . Acestea sunt elementele cheie care ne permit să distinge m
între variatele paradigme ale metodelor evolutive.

15

ALGORITMI GENETICI
Vol.I
2.2. Algoritmi genetici paradigme ale calculului evolutiv

Algoritmii genetici utilizează un vocabular î mprumut at din genetica
naturala. Mulțimea punctelor de căutare pă strate de al goritm la un moment
dat se numeș te populaț ie, iar ind ivizii unei populaț ii se numesc cromozomi .
Cromozomii sunt alcatuiți din unităț i numite gene , aranjate într -o
succesiune liniară; fiecare genă controlează moștenirea a una sau mai multe
caracte re. Unele gene pot fi plasate î n anumite locuri ale cromozomului, numite
locus iar val orile posibile pentru o gena formează setul de alele ale genei.
Odată populația inițială creată, fiecare șir este evaluat ș i i se at ribuie un
fitness dat de o funcț ie f , numită funcț ia fitness=funcț ia de evaluare .
Noțiunile de fitness ș i evaluar e sunt folosite în general cu acela și
sens; totuși se poate face o distincție între ele. Funcția de evaluare, sau
funcția obiectiv, reprezintă o măsură a performanței în raport cu o mulț ime de
parametri, în timp ce funcția fitness transformă aceasta măsură a performanț ei
în alocare de facilităț i reproductive. Evaluarea unui ș ir reprezent ând o mul țime
de parametri este independentă de evaluarea altor șiruri. Fitness -ul unui șir
este, însă , definit în raport cu alți membri ai populaț iei curente. Fitness -ul
poate fi definit, de exemplu, prin fi/f unde fi este evaluarea asociata ș irului i
iar f este evaluarea medie a tuturor șirurilor popula ției.

Funcț ia de evaluare si codificarea sunt, de obicei, singurele componente
ale algoritmilor genetici care depind de problema de rezolvat.
Un algoritm genetic, folosit pentru rezolvarea unei probleme de
optimizare, poate fi privit ca o ”cutie neagra” cu o serie de butoane de control
reprezent ând diverși parametri. Ieș irea cutie i negre este valoarea unei funcț ii
indic ând î n ce m ăsură o anumită distribuț ie a pa rametrilor rezolva problema
dată. In termeni tradiționali dorim să minimizăm (maximizam) o funcț ie F (x 1,
x2, …, x n ). De cele mai multe ori este imposibil de tratat independent fiecare
parametru. Apariția interacț iunilor face necesara considerarea efectelor
combinate ale parametrilor in vederea optimiz ării cutiei negre.

16

ALGORITMI GENETICI
Vol.I
In limbajul algoritmilor genet ici, interac țiunea dintre variabile este
numita epistasis .
Variabilele reprezentâ nd parametrii su nt, de obicei, codificate prin
șiruri binare, dar există si alte codificări: numere î ntregi, numere reale, codul
Gray, codificare alfabetica, arbori. Condițiile pe care trebuie să le
îndeplinească o reprezentare buna sunt: independenta relativa a genelor,
includerea a cat mai multe restricții ale problemei direct î n reprezentare,
complexitate scăzută a decodific ări/codific ării cromozomilor.
Rezolvarea problemelor de codificare este considerata, de obicei, ca
parte a construcției funcției de evaluare. Funcț ia de evaluare este parte a
descrieri i problemei. Precizarea funcț iei de evaluare poate implica o
simulare si po ate fi aproximativa sau parțială . De exemplu, sa consideram
o problema de control optimal, în care mulțimea stărilor î n care se poate afla
sistemul poate fi exponenț ial de mare.
Folosirea unui algoritm genetic pen tru gă sirea unei strategii optime
de control presupune reducerea spațiului stărilor (prin eș antionare) și, astfel,
evaluarea realizată este aproximativă ș i afectata de perturba ții. Funcț ia de
evaluare trebuie sa fie ușor de calculat avâ nd in vedere ca fieca re generație
trebuie evaluata; deci funcț ia de evaluare este apelata de foarte multe ori.

Exista o mare clasa a proble melor interesante pentru care încă nu au
fost dezvoltaț i algorit mi rapizi. Multe dintre acestea sunt probl eme sunt
proble me optimizate care intervin frecvent în aplicații. Dându-se o probl ema
prost optimizată este posibil mereu sa găsim un algoritm eficient a cărui
soluție este aprox imativ optimala. Pentru unele probleme prost optimizate
putem folosi algorit mi prob abilisti ci:
-acești algorit mi nu garantează valoarea optima, dar prin alegeri
aleatoare , suficient de multe
—slăbiciuni a erorilor pot fi făcute astfel încât sa putem trece peste ele.
Exista multe proble me importante practic optimizate pentru care
asemenea algoritmi, de o înalta calitate, devenind disponibili. În orice caz

17

ALGORITMI GENETICI
Vol.I
putem aplica simultan rular ea mai multe fire de execuție si co mpetenta
amplasării proble melor VLSI design pentru proble mele gen agent
comercial. In plus multe alte probl eme aparținând unei game largi de
probl eme optimizate combinatorial pot fi rezolvate aproxi mativ în ziua d e
astăzi prin computer d e genul tehnicilor Mont e Carlo.
Ín general, orice pro ces abstr act pentru a fi îndeplinit poate fi gândit ca
o rezolvare a probl emei, care , in schimb, poate fi perceputa ca o căutare
prin spațiul soluții lor potenț iale. Cum suntem in căutarea celei mai bune
soluții , putem privi aceasta sarcina ca un proces optimizat. Pentru spatiile
mici, metodele clasice executive sunt suficiente; pentru spațiile largi
tehnica speciala a inteligenței arti ficiale trebuie sa fie luata in veder e.
Algorit mii genetici sunt print re aceste tehnici; ei sunt algori tmi stohastici a
căror metode de căutare modele ază unele fenomene naturale. Ideea in spatele
algorit milor geneti ci este de a face ceea ce natura face.
Începuturile algorit milor genetici se situează undev a în jurul anului
1950, când mai mulți biologi au folosit calcul atoarele pentru simularea
sistemelor biologi ce. Rezultatele muncii au început să ap ară după 1960, când
la Universit atea din Michig an, sub directa îndru mare a lui John Holland,
algorit mii gen etici au apărut în forma în care sunt cunoscu ți astăzi.
După cum sugerează și numele, algorit mii genetici folosesc principii
din genetica naturală . Câteva princip ii funda mentale ale geneticii sunt
împrumutate și folosite artificial pentru a constru i algorit mi de căutare care
sunt robuș ti și cer informații minime despre proble mă.
Algorit mii genetici au fost inventați folosind modelul procesului de
adaptare. Ei operează, în principal, cu șiruri binare și folosesc un operator
de recombinare și unul de mutație. Prin mutație se schimbă un element
(genă) dintr -un cromozom, iar prin încrucișare se schimbă material genetic
între doi părinți; dacă părinții sunt reprezenta ți prin șiruri de cinci biți, de
exemplu (0, 0, 0, 0, 0) și (1, 1, 1, 1,1), încruciș area celor doi vectori poate

18

ALGORITMI GENETICI
Vol.I
duce la obținerea descendenților (0, 0, 1, 1, 1) și (1, 1, 0, 0, 0)(acesta este un
exemplu al așa-numitei încruc ișări cu un punct d e tăietură).
Fitnes s-ul unui individ este atribuit proporțion al cu valoarea
funcției criteriu corespunz ătoare indiv idului ; indivizii sunt selectați pentru
genera ția următoare pe baza fitness-ului lor.
Vom ilustra modul de lucru al algoritmilo r genetici cu ajutorul unei
proble me simple: proie ctarea unei cutii de conserve. Consid erăm o cutie de
conserve cilindrică, cu numai doi parametri: diametrul d și înălțimea h
(evident , pot fi considerați și alți parametri, cum ar fi grosi mea,
proprietă ți ale materialului, forma, dar sunt suficien ți doar cei doi
parametri pentru a ilustra lucrul cu algoritmii geneti ci).
Să consid erăm că această conservă trebui e să aibă un volum de
cel puțin 300 ml și obiectivul pro iectului este de a minimiza costul
materialului folosit la fabricarea conservei. Putem formula proble ma
noastră astfel:

să se minimizeze valoare a funcției unde c repre zintă costul materialului
conserv ei per cm2, iar expresia din parante ză reprezint ă suprafața conservei.
Funcția f se mai numește și funcție criteriu (sau funcție obiectiv ). Mai
trebuie îndeplinită și condi ția ca volumul cutiei să fie cel puțin 300 ml și
vom formula aceasta astfel:

Parametrii d și h pot varia între anumite limite:
dmin  d  dmax și hmin  h  hmax.

19

ALGORITMI GENETICI
Vol.I
Reprezentarea soluției

Primul pas în utiliz area unui algoritm genetic este stabilir ea unei
codificări a proble mei. Codificarea binară este cea mai obișnuită dintre
tehni cile de codificare; ea este simplu de manipul at și conferă robuste țe
probl emei.
Reprezentarea binară poate codifica aproape orice situa ție, iar
operatorii nu includ cunoș tințe despre domeniul proble mei. Este motivul
pentru care un algorit m genetic se poate aplica unor proble me foarte diferite.
Ín cazul codifi cării binare, fiecare valoare se reprezintă printr -un șir de
lungi me speci ficată care conține valorile 0 și 1. Ín anumite situații este
necesar să utilizăm codificarea "natura lă" a probl emei, în locul
reprezentării binar e. Un exemplu de codificare naturală ar fi codific area real ă,
care utilizează numere reale pentru repre zentare. Pentru a folosi algorit mii
genetici la găsirea unor valori optime pentru parametri d și h, care să
satisfacă condiția prezentată sub forma funcției g și care să minimizeze
funcția f, vom avea în primul rând nevoi e de repre zentare a valorilor
parametrilor în șiruri bin are (vom folosi, așadar, o codificare binară a
problemei).
Algorit mii genetici nu ne impun numai valori întregi dintr-un anumit
inteval; în general, putem folosi orice altă valoare întreagă sau reală, prin
schimbarea lungi mii șirulu i binar

20

ALGORITMI GENETICI
Vol.I
2.2.1 Atribuirea fitness -ului

Am afirmat anterior că algoritmii genetici lucrează cu șiruri de
biți reprezentând valorile para metrilor și nu cu parametrii înșiși. După ce a
fost creat un nou șir (o nouă soluț ie) prin operatori geneti ci, trebuie să-l
evaluăm. În majoritatea cazurilor , fitness -ul este chiar valoare a funcției
criteriu pentru soluția respectivă. Dacă obiectivul nostru este de a minimiza
funcția criteriu, atunci vom spune c ă o soluție este mai bun ă decât alta, dacă
fitness-ul celei de-a doua este mai mare.

2.2.2 Structura unui algoritm genetic

Vom descrie în continu are structura
algorit milor geneti ci. Pentru început vom
stabili următoarele:
 cromozomii utiliz ați au lungi me constantă ;
 popula ția (gener ația) P(t + 1) de la momentul t + 1 se obține reținând toți
descendenții popul ației P(t)
și ștergând ulterior cromozomii gener ației precedente (P(t));
 numărul cromozomilor este constant.

Putem prezenta acum structur a algorit mului geneti c fundamental:
Pasul 1 : t  0.
Pasul 2 : Se inițializează aleator popula ția P(t).
Pasul 3 : Se evaluează cromozomii popul ației P(t).
Ín acest scop se utilizează o funcție de performanță ce depind e de
probl emă.
Pasul 4 : Cât timp nu este îndepl inită cond iția de terminare se execută pașii

21

ALGORITMI GENETICI
Vol.I
următori:
Pasul 4.1: Se selectează cromozomii din P(t) care vor contribui la formarea
noii generații. Fie P1 mulțimea cromozomilor selectați (P1 reprezin tă
o popula ție intermediară).
Pasul 4.2 : Se aplică cromozomilor din P1 oper atorii g enetici. Cei mai utiliz ați
sunt operatorii de mutație și încrucișare.
În funcție de proble mă se pot alege și alți operatori (inversiune,
reordon are, operatori speciali). Fie P2 popul ația astfel obținu tă (descendenții
popula ției P(t)). Se șterg din P1 părinții descendenților obț inuți. Cromozomii
rămași în P1 sunt incluși în popula ția P2. Se construi ește noua gener ație,
astfel: P(t + 1)  P2; se șterg toți cromozomii din P(t); se execută
atribuir ea t  t + 1; se evaluea ză P(t). Condiț ia de terminare se referă,
de regulă, la atinger ea numărului de generații speci ficate. Dacă nu mărul
maxim admis de generații este N, atunci condiț ia de oprire este t > N. Se
admite că rezult atul algorit mului este dat de cel mai promițător individ din
ultima generație. Ín realit ate, nimic nu ne garante ază că un individ mai
performant nu a fost obținut într-o generație anterioară. De aceea, este
normal ca la fiecare pas (la fiecare gener ație t) să reținem cel mai promițător
indiv id care a fost generat până atunci. Acest proces se numește elitism.

22

ALGORITMI GENETICI
Vol.I
2.2.3 Selecția

Un rol important în cadrul unui algorit m genetic îl ocupă operatorul de
selecție. Acest operator de cide care dintre indivizii unei populații vor putea
participa la formarea popula ției următoare . Scopul selec ției este de a asigura
mai multe șanse de reprodu cere celor mai performanți indivizi dintr-o
popula ție dată.
Prin selecție se urmărește maximizarea performanței indivi zilor.
În continuar e vom prezenta succint cele mai importante mecanisme de
selecție.
Selecția propor țională

În cazul selecției proporț ionale, probabilitatea de selecție a unui
individ depind e de valoarea per formanței acestuia. Să presupun em că avem o
mulțime de cromozomi x1, x2, …, xn. Pentru fiecare cro mozom xi vom
calcula performanța sa f(xi). Se impune condiția ca f(xi)  0. Suma
performanțelor tuturor cromozomilor din popula ție va constitui performanța
totală și o vom nota cu F.

Selecția bazată pe ordonare

Aceast ă modalit ate de selecție constă în a calcula (pentru fiecare
gene rație) valorile funcției de fitness și de a aranja indiv izii în ordinea
descrescătoare a acestor valori. Se va atribui fiecărui individ i o probabilit ate
de selecție pi care depinde de rangul său în șirul stabilit. Probabil itățile
depind acum doar de poziția cromozomului. Cel mai promițător individ are
probabilit atea 1.

23

ALGORITMI GENETICI
Vol.I

Selecția prin concurs

Selecția prin concurs sau selecția turnir se bazează pe comparar ea directă a
câte doi cromozomi și selectare a celui mai performant.
Opera țiile implicate sunt ur mătoarele:
 se aleg în mod aleator doi cromozomi;
 se calculeaz ă performanțele cromozomilor selectați;
 cromozomul mai performant este selectat (copiat în popula ția intermediară
asupra căreia se aplică operatorii geneti ci).

Alte mecanism e de selecție

Un alt tip de selecț ie este selecția elitistă. În acest caz, la fiecare
generație se păstreaz ă cel mai pro mițător sau cei mai promițători indivizi. O
altă idee ar fi ca, la fiecare gener ație, să fie înlocuită doar o parte restrânsă a
popula ției.

2.2.4 Operatorii genetici

Descriu în continuar e operatorii geneti ci folosi ți, de obicei, într-un algoritm
genetic.
Operato rul de reproduc ere
Rolul operatorului de reprodu cere este de a menține soluțiile
promițătoare din popula ție și de a le eli mina pe cele mai puțin pro mițătoare,
păstrând constantă dimensiun ea populației.
Aceasta se realizează astfel:

24

ALGORITMI GENETICI
Vol.I
 se identi fică soluțiile pro mițătoar e din popula ție;
 se creează mai multe copii ale soluțiilor pro mițătoare;
 se elimină soluțiile mai puțin pro mițătoare din popul ație astfel încât
multipl ele copii ale soluțiilor promițătoare să poată fi plas ate în popula ție.
Există mai multe moduri de a realiza acest lucru. Cele mai
uzuale metode sunt selecția proporțion ală, selecția prin turnir și selecția
prin ordonare . Este ușor de observat că soluțiile pro mițătoare au mai
mult de o copie în popula ția intermediară

Opera torul de încrucișare

Operatoru l de încrucișare este aplicat asupra indivi zilor din popula ția
intermediară .
Ín exemplul nostru, va fi aplicat asupra repre zentării binare a celor șase
elemente pe care le avem în popula ția intermediară. Operatorul de
încru cișare acționeaz ă în felul următor: sunt aleși aleator doi indiv izi din
popul ația intermediar ă (care se mai nu mește și
piscină de încruciș are) și anumite porțiun i din cei doi indiv izi sunt
inters chimbate. Operatorul imită încrucișar ea int ercromozomială naturală .De
regulă, se utilizează operatori de încruc ișare de tipul (2, 2), adică doi părin ți
dau naștere la doi des cenden ți.
Încruciș area realizează un schimb de infor mație între cei doi
părinți. Descenden ții obținuți prin încrucișare vor avea caracteristi ci ale
ambilor părin ți.
Dată fiind importanța majoră a încruc ișării, au fost propus e mai multe modele
de încrucișare. Vom enumera aici c âteva dintre cele utiliz ate atunci când s e
folose ște codificarea bin ară.

25

ALGORITMI GENETICI
Vol.I
Încruc ișarea cu un pun ct de tă ietură

Fie r lungi mea cromozomilor. Un punct de tăietură este un număr
întreg k  {1, 2,…, r – 1}. Nu mărul k indică poziția din interiorul
cromozomului unde secvența cromozomială se rupe pentru ca segmentele
obținu te să se recombine cu alte segmente provenite de la alți cromozomi.
Consid erăm doi cromozomi:
x=x1x2…xkxk+1…xr și
y = y1y2…ykyk+1…yr.
Ín urma recombinării se schimbă între cei doi cromozomi secvenț ele
aflate în dreapta punctului de tăietură k.
Cromozomii fii vor fi:
x' = x1x2…xkyk+1…yr și
y' = y1y2…ykxk+1…xr.

De exemplu, dacă avem o repre zentare mai sugestivă a celor doi
cromozomi:

descenden ții vor fi:

26

ALGORITMI GENETICI
Vol.I

Încruc ișarea cu mai multe puncte de tăietură

Ín cazul utilizării mai multor puncte de tăietur ă, segmentele obținute se
combină după o regulă dată. Consideră m încrucișarea cu două puncte de
tăietur ă. Acest tip de încruc ișare se realizează conform s chemei de mai jos.
Din cromozomii:

vor rezulta doi descendenți de tipul:

În cazul a trei puncte de tăietur ă, descendenții vor fi de forma :

Revenind la exemplul nostru, vom consid era încrucișarea cu un singur punct
de tăietură. De exemplu, din încrucișarea a două soluții reprezentate prin
cutia care are fitness-ul 23, h = 8 și d = 10, respe ctiv cuti a cu fitness-ul 26, h
= 14 și d = 6, vor rezulta doi descenden ți care vor avea fitness-ul 22, h = 10 și
d= 6, respectiv fitness-ul 38, h = 12 și d = 10 după modelul de mai jos:

Trebuie r eținut faptul că încrucișarea nu gener ează descendenți ale atori. D eși

27

ALGORITMI GENETICI
Vol.I
este improbabil ca fiecare încrucișare între două soluții din popula ție să
gener eze soluții fii mai promițătoare decât soluțiile părin te, totuși în scurt
timp devin e clar că șansa de a crea soluții mai pro mițătoare este mai mare
decât în cazul căutării aleatoare. Din încrucișarea cu un singur punct de
tăietură a unei perechi de șiruri binare, se pot crea doar două șiruri pereche
diferite care vor avea în co mponen ță biți combinați din ambii părin ți;
soluțiile fiu create sunt, probabil, șiruri cel puțin la fel de pro mițătoare. Prin
urmare, nu fiecare încrucișare poate crea soluț ii la fel de promițătoare, dar nu
vor fi mai puțin promițătoare decât părinții. Dacă a fost obținută o soluție
mai puțin promițătoare, atunci aceasta nu va mai apărea când se va aplica
următorul operator de reprodu cere și astfel va avea o viață scurtă.
Dacă este creată o soluție mai promițătoare, atun ci este probabil ca ea să
aibă mai multe copii la următoare a aplicare a operatorulu i de reprodu cere.
Pentru a păstra o astfel de selecție a șirurilor promițătoare în timpul
aplicării operatorului de reprodu cere, nu to ate șiruril e din popul ație sunt
folosite pentru încrucișare.

Opera torul de mutație

Operatorul de încruc ișare este, în principal, responsabil cu aspectul de
căutare al algorit milor geneti ci, în timp ce operatorul de mutație este folosit
pentru alte scopuri . Mutația este cel de-al doilea operator geneti c în ordinea
importan ței și folosirii sale. Efectul acestui operator este schimbarea valorii
unei singure poziții dintr -un cromozom.
Prin mutație se introduc în populație indivi zi care nu ar fi putut fi
obținu ți prin alte mecanis me. Op eratorul de mutație acționea ză asupra biților
indiferent de poziția lor în cromozom. Fiecare bit al cromozomului poate
suferi o mutație. Într-un cromozom pot exista, așadar, mai multe poziții care
suferă o mutație. Muta ția este un operator probabilist (adică nu se aplică cu

28

ALGORITMI GENETICI
Vol.I
siguranță). Consid erăm o popula ție de n indivizi (cromozomi), fiecare având
lungi mea r. Fiecare bit are aceeași probabilitate pm de a suferi mutația.
Există mai multe variante ale operatorului de mutație. Una dintre ele ar
fi mutația în forma tare . În această situa ție se procedează în felul următor: se
genereaz ă un număr aleator q în intervalul [0, 1). Da că q < pm, atunci se
execută mutația poziției respe ctive schimbând 0 în 1 sau 1 în 0. Ín caz
contrar, poz iția respect ivă nu se sch imbă.
Revenind la exemplul nostru , dacă aplicăm operatorul de mutație unei
soluții obținute în urma pro cesului de încrucișare, și anume soluției care are
fitness -ul 22, vom obține o altă soluție care va av ea fitness-ul 16.

Soluția obținută este mai promițătoare decât soluț ia origin ală. Ín
conse cință, operatorul de reprodu cere selectează cele mai promițătoare
șiruri, operatorul de încrucișar e combină subșiruri din două șiruri
promițătoare pentru a forma șiruri mai promițătoare, iar operatorul de
mutație schimbă șiruril e local, de asemenea, pentru a îmbună tăți soluț ia.

29

ALGORITMI GENETICI
Vol.I

2.3. Strategii evolutive

Strategiile evolutive au fost dezvoltate ca metode de rezolvare pentru
proble mele de optimizare a parametrilor . Prima strategie evolutivă a fost
bazată pe o popula ție constând dintr-un singur individ. De asemenea, este
folosit un singur operator în procesul de evolu ție: mutația. Aceasta este
în concordan ță cu conc eptul biologic potrivit căruia modificări mici au
loc mai frecvent decât o modificare mare. D e obicei această strategie
conform căreia un părin te dă naștere prin mutație unui singur de scendent
este cunoscută sub numele de strategie evolu tivă 1 + 1. Felul în care se apli că
practic acest algoritm este simplu: se gene rează o soluție aleatoare pe
domeniul de căutare și se efectuează mutații asupra ei. Este acceptat cel
mai bun dintre părinte și descendent. Opera torul de mutație se aplică
repetat până când se ajunge la soluție.
Un alt tip de strategie este strategia ( + ):  părinți produc 
descenden ți. Noua popula ție (temporară) de (+ ) indivizi este redusă din
nou – printr -un proces de selecție – la  indivizi. Pe de alt ă parte, in strategia
(, ),  indiv izi produc  descenden ți ( > ) și prin procesul de selecție
se aleg e o nouă popula ție de  indivizi numai din mulțimea celor 
descenden ți. Astfel, viața fiecărui indiv id este limitată la o genera ție.

30

ALGORITMI GENETICI
Vol.I
2.3.1 Programare evolutivă

Tehnicile progr amării evolutive originale au fost dezvoltate de
Lawrenc e Fogel. El urmărea o dezvoltare a inteligenței artificiale în sensul
dezvoltă rii abilității de a prezice schimbările într-un mediu încon jurător.
Mediul înconjurător a fost descris ca o secve nță de simboluri, iar
evolu area algorit mului presupun ea obținere a unui nou produ s, și anume a
unui nou simbol. Simbolul obținut va maximiza funcția finală care măsoară
acuratețea predicției.
De exemplu, putem consid era o serie de eveni mente notate a1, a2,
…, an; un algoritm va deter mina ur mătorul simbol (an+1), b azându-se pe
simbolurile cunoscute a1, a2,…, an.
Ideea care stă la baza progr amării evolutive este de a evolua un algorit m. Ca
și în strategiile evolutive, și în tehni ca progr amării evolutive se creează mai
întâi descendenții și apoi se vor selecta indivi zii pentru generația următoare.
Fiecare părinte produ ce un singur descendent; deci dimensiunea
popula ției intermediare se duble ază (ca în strategia evolutivă (n, n), unde n
este dimensiune a popula ției). Descendentul este creat printr -o mutație
aleatoare a părintelu i (este posibil să se aplice mai mult de o mutație unui
individ). Un nu măr de indivizi (cei mai promițători) egal cu dimensiun ea
popul ației sunt reținuți pentru noua gener ație.
Ín versiun ea origina lă acest proces este repetat până se obține un
nou simbol care este disponibil . După ce s-a obținu t un nou simbol,
acesta este adăugat listei simbolurilor cunos cute și întregul proces se
repetă. Recent, tehnicil e de progra mare evolutivă au fost folosite pentru
rezolvarea proble melor d e optimizare numerică precum și în nu meroase alte
scopuri.

31

ALGORITMI GENETICI
Vol.I
2.3.2 Programarea genetică

O altă abordar e interesantă a fost descoperit ă relativ recent de John Koza.
Koza sugerează că progr amul dorit va evolua el însuși pe parcursul
unui proces de evoluție. Cu alt e cuvint e, în loc de a rezolva o proble mă și în
loc de a construi un progr am evolutiv care să rezolve pr oblema, vom încerca
să găsim un cod sursă care să o rezolve.
Koza a dezvoltat o nouă metodologi e care furnizează un mod de a
efectua această căutare. De ex emplu, se dorește obținere a unui progr am
Pascal sau C++ care să rezolve probl ema drumului ha miltoni an sau
proble ma ieșirii dintr-un labirin t. Deci, nu ne interesează să obținem o
soluție pentru un set oarecare de date, ci, mai degra bă, ne intere sează să
obținem un progr am sursă care să gener eze o solu ție corectă pentru orice
intrare dată. Cu alte cuvinte, ne interesează să obținem ca rezultat un
progra m asemănător cu cel pe care l-am fi putut s crie noi d acă am fi știut să
rezolv ăm probl ema.
Din punct de vedere evolutiv abordar ea unor astfel de probl eme se
face generând o mulțime (popul ație) aleatoare de coduri sursă care apoi sunt
selectate pe baza funcției de fitness și evoluate cu ajutorul unor operatori
genetici specifici. Ín primul rând tr ebuie să atribui m o funcție de calitate
(func ția fitness) fiecărui progra m gener at. Aceast ă funcție de fitness trebui e să
reflecte per formanțele progr amului c ăruia îi este atașată.
De obicei atașarea unei funcții de fitness se face rulând progra mul
respectiv și măsurând calitatea solu ției în raport cu o soluție care se cuno aște
a fi optimă. Un progra m va avea o calitate mai mare dacă solu ția generată va
fi mai asemănătoare cu cea a soluției corecte. Nu este grav dacă o soluție
optimă nu se cuno aște anterior, deoarece noi dorim să obținem soluții cu un
fitness cât mai mare (sau cât mai mic).

32

ALGORITMI GENETICI
Vol.I
Evoluarea progra melor sursă se realizează prin operatori genetici
specifici. De exemplu, un operator de recombinare poate însemna alipire a
secven țelor dintr -un cod sursă cu secven țe din alt cod sursă . Un operator de
mutație ar putea îns emna inser area de noi instru cțiuni în codul sursă, ștergerea
de instruc țiuni, trans formarea de instrucțiuni. Evident, în urma aplicării
acestor operatori genetici se gener ează cod sursă care conține greșeli de
sintaxă. De asemenea, sunt gener ate secven țe de cod sursă ne folositoare.
Exemple în acest sens sunt s ecven ța de instruc țiuni:
i := i + 1;
i := i – 1;
sau secven ța:
a := 0;
b := c / a;
De obicei, se evoluează reprezentări mai simple ale progr amelor
de calculator și anume repre zentările arbores cente. Există limbaje de
progra mare (de exemplu LISP) în care progra mele sunt s crise sub forma unor
liste ușor trans formabile în arbori.

33

ALGORITMI GENETICI
Vol.I
Aplicatie

În cele ce urmează voi prezenta rezolvarea unei proble me folosind algorit mii
genetici:

Enunț: (Submulțime de sumă dată)
Se consideră o mulțime M de n numere și un număr S. Să se deter mine o
submulțime a mulțimii.
M care are suma elementelor cât mai aprop iată de numărul S.

Rezolva re
Determinarea unei submulțimi de sumă dată este o probl emă NP-completă
Aceasta înseamnă că nu se știe dacă exist ă sau nu un algorit m de
complexitate polino mială pentru rezolvar ea acestei proble me. Până în
prezent, algori tmii folosiți au complexitate exponenția lă, iar pentru anumite
cazuri particulare au complexit ate pseudopolino mială. De exemplu, putem
rezolva re zonabil a ceastă proble mă, dacă datele de intrare îndeplinesc
următoarele cond iții:
 sunt cel mult 100 de numere natur ale;
 suma numerelor nu depă șește 500 (mai exact, produsul dintre numărul
numerelor și suma acestora nu trebu ie să depășească dimensiunea maximă
admisă pentru alocarea unei matrice (presupune m că aceasta este alocată
static).

Dacă aceste condiții ar fi îndeplinite am putea rezolva ușor această
probl emă prin metoda progra mării dinamice, folosind un algorit m de
complexitate O(n ‡ S) ). Însă, dacă numerele nu ar fi întregi ci reale, sau
suma lor ar fi mai mare decât 500, sau diferențele între ele ar fi mari etc.,

34

ALGORITMI GENETICI
Vol.I
atunci algorit mul prin progr amare dinamică nu mai poate fi folosit.
Am enumerat aici doar cazurile i mportante, dar pot fi imaginate și alte
dificultăți.
Din aceste motive vom rezolva această proble mă cu ajutorul unui
algoritm genetic. Va trebui să găsi m o repre zentare a soluției și, de
asemenea, o funcție de fitness. Modul în care vom reprezenta solu ția ne este
dat chiar în enun țul probl emei: se cere o submulțime a unei mulțimi M cu n
elemente. Deci , o soluție a probl emei este o submulțime. Vom codific a o
submulțime printr-un șir de lungi me n care conțin e doar valorile 0 și 1. Dacă
o poziție k va avea valoare a 1, atunci submulțimea respect ivă va con ține
elementul Mk (al k-lea element din mulțimea M), iar dacă pe poziția k este
valoarea 0, atunci ele mentul respectiv nu aparține submulțimii. Această
reprezentare a unei submulțimi este specifică tipului set din Turbo Pascal.
Modul de calcul al fitness-ului (calității) unei soluții (submulțimi) este
simplu. Calculă m suma elementelor submulțimii, iar fitness -ul va fi
diferen ța (în valoare absolută) dintre suma obținută și numărul dat S. Ín
aceste condiții fitness -ul va trebui minimizat, deoarece noi dorim să
deter minăm o submulțime pentru care suma elementelor este cât mai apropiată
de valoarea dată S.
Structura algorit mului genetic propus pentru rezolvare a acestei
proble me a fost prezentată mai sus. Vom folosi selec ția turnir pentru
obținere a popula ției intermediare. Operatorii genetici folosiți sunt speci fici
codific ării binare (încrucișar e cu un singur punct de tăietură, mutație cu
probabilitate pm=0.1).

35

ALGORITMI GENETICI
Vol.I

2.4 Sisteme hibride

Așa cum am mai precizat, algoritmi genetici sunt o familie de modele
inspirate de teoria evoluției, sunt programe inteligente capabile să soluționeze
probleme folosind un conceptul al evoluției speciilor. Acești algoritmi codifică
soluțiile posibile ale uno r probleme specifice într -o structură de date de tip
cromozom și aplică acestor structuri operatori de recombinare, pentru a păstra
informația utilă.
Un cromozom este un vector sau un șir de gene. Poziția unei gene este
numită locusul ei. Valorile pe care le poate lua o genă sunt numite alele, sunt
mulțimi finite de numere întregi, intervale de numere reale, sau chiar structuri
complexe de date. Alele variază de la un locus la altul.
Sarcina unui algoritm genetic e să descopere cromozomi din ce în ce mai b uni,
până la atingerea unei valori a raportului dintre evaluarea asociată unui șir și
evaluarea medie a tuturor șirurilor populației (fitness) despre care se știe că este
optimală, sau până când algoritmul genetic nu mai poate aduce îmbunătățiri.
Implementarea unui algoritm genetic începe cu o populație de cromozomi
(aleasă aleator). Se evaluează, apoi, aceste structuri și se alocă facilități
reproductive astfel încât acei cromozomi, care reprezintă o soluție mai bună
pentru problema țintă, să aibă mai multe șanse de a se reproduce decât acei
cromozomi care sunt soluții mai puțin bune. Definirea unei soluții bune se face
în raport cu populația curentă.
Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de
populație și care folos ește selecție și operatori de recombinare pentru a genera
noi puncte într -un spațiu de căutare. Multe modele au fost introduse de
cercetători dintr -o perspectivă experimentală. Cercetătorii sunt orientați spre
aplicații, fiind interesați de algoritmii gene tici doar ca mijloace de optimizare.

36

ALGORITMI GENETICI
Vol.I
Ei sunt recomandați pentru aflarea soluțiilor neliniare ale unor probleme
atunci când nu este posibilă modelarea matematică și nici euristică în domeniu.
Adevărații profesioniști combină adesea cele mai variate tehnolo gii
inteligente în scopul exploatării avantajelor fiecăreia, obținând așa -numitele
sisteme hibride . Sunt posibile combinări de genul:
1. folosirea rețelelor neuronale la ajustarea parametrilor în sistemele
expert fuzzy,
2. extragerea cunoașterii din rețele neuro nale pentru a fi utilizată în
sistemele expert,
3. folosirea algoritmilor genetici la crearea unor rețele neuronale mai
compacte și mai eficiente,
4. folosirea unei rețele neuronale pentru asistarea funcționării unui
algoritm genetic,
5. folosirea algoritmilor genetici la reglarea parametrilor unui sistem
expert fuzzy pentru controlul proceselor,
6. îmbunătățirea performanței unui sistem expert prin încorporarea
raționamentului bazat pe cazuri, etc.
Asemenea cercetări sunt în prezent în mare vogă în cele mai specializate
laboratoar e ale lumii științifice.

Câteva subiecte ale conceptelor de bază :
 probleme de optimizare – doar două componente principale sunt
dependente de
problema de rezolvat : codificarea și funcția de evaluare. Scopul este de a fixa
parametrii în așa fel încât ieșirea să fie optimă.
Variabilele desemnând parametrii sunt reprezentați prin șiruri binare iar funcția
de evaluare este parte a descrierii problemei.
 algoritmul genetic canonic – constă în generarea populației i nițiale. Se
aplică

37

ALGORITMI GENETICI
Vol.I
acestei populații selecția pentru a obține o populație intermediară. Apoi se aplică
recombinarea și mutații pentru a crea o populație următoare (next population).
Acest proces de trecere de la populația curentă la populația următoare re prezintă
o generație în execuția unui algoritm genetic.
 selecția hiperplanelor – nu este afectată de extremele locale. Creșterea
ratei de selecție a hiperplanelor peste medie nu garantează convergența
către un optim global, ce ar putea fi un vârf relativ izolat.
 teorema schemei – furnizează o margine inferioară a schimbării ratei de
selecție pentru un singur hiperplan de la generația t la generația t+1.
 alfabetele binare – utilizarea lor va rezulta în urma unor calcule simple.
Un alfabet minimal maximize ază numărul de hiperplane utilizabile pentru
codificarea procesării
 critica teoremei schemei – inexactitatea inegalității face ca încercarea de a
prezice pe baza teoremei reprezentarea unui anumit hiperplan de -a lungul
generațiilor, să fie fără succes.

2.4.1 Aplicații ale algoritmilor genetici

Algoritmii genetici reprezintă o metodă cu care pot fi atacate relativ ușor
probleme dificile de optimizare sau control, cu rezultate bune sau chiar
optimale.
Când se vorbește de aplicarea unei idei din software, se referă în general
la un prototip care arată cum ar putea fi folosită respectiva idee într -un domeniu
practic.
Un exemplu îl constituie sistemul care funcționează la instalația de
maleabi lizare a unui laminor de platbande de oțel, unde operatorul unei macarale

38

ALGORITMI GENETICI
Vol.I
este ajutat să decidă unde să pună oțelul laminat înainte de maleabilizare, cum să
grupeze șarjele în cuptorul de maleabilizare și cum să aranjeze oțelul laminat
maleabilizat pentru a fi expediat în funcție de comenzile primite. Un alt exemplu
este aceea de a realiza optimizarea unor obiective variate în alcătuirea orarelor
pentru cursuri sau examene.
Aplicații ale algoritmilor genetici este de exemplu controlul curgerii de
gaz printr -o conductă, în regim staționar și în regim tranzitoriu. De -a lungul
conductei, presiunea gazului descrește în mod natural și trebuie mărită cu
ajutorul unor compresoare. Obiectivul constă în menținerea presiunii în punctele
de livrare la nivelul dorit, cu minimizarea energiei folosite în compresoare și
îndeplinirea altor restricții. De asemenea, este necesară detectarea, pe baza
măsurării presiunii, a scurgerilor probabile, evitând, pe cât posibil, alarmele
false.
Alți cercetători descriu o aplicație în pr oiectarea rețelelor de comunicații
între stații aflate la mare distanță.
Optimizarea planificărilor – utilizarea algoritmilor pentru planificarea
examenelor – se dau un set de examene și un număr fix de căsuțe libere în orar :
obiectivul e de a așeza fieca re examen într -una dintre căsuțe, astfel încât nici un
student să nu aibă examene aflate în căsuțe consecutive, nici prea multe
examene în aceeași zi. De asemenea, anumite exam ene nu pot fi puse în anumite
căsuțe.

39

ALGORITMI GENETICI
Vol.I
Reprezentarea folosită este naturală : e xistă o genă pentru fiecare examen,
altele fiind date de mulțimea căsuțelor din orar. Evident, majoritatea
cromozomilor generați aleator vor încălca mai multe restricții. Funcția de fitness
conține termini de penalizare pentru fiecare restricție încălcată și se dovedește
stabilă față de valorile efective ale acestor termeni. Algoritmul genetic are deci
o formă convențională, cu excepția unui operator de mutație mai deosebit.
Acesta exercită o ușoară presiune pentru îmbunătățirea orarului. Implementarea
unui operator mai tare, care efectuează acea schimbare care duce la cea mai
bună îmbunătățire a unui cromozom, se dovedește extrem de dăunătoare.
Algoritmul genetic a găsit o soluție în care doar unul dintre studenți a avut de
susținut două examene consecut ive. Algoritmul a obținut o astfel de soluție, nu
întotdeauna aceeași, în 50% din rulări.
S-au aplicat metode similare pentru a genera orarul cursurilor; aici un
cromozom reprezintă, pentru fiecare curs, ora de începere și locul de
desfășurare, e xistând penalizări pentru lipsa de spațiu în sala de curs, pentru
distanțe prea mari între sălile unde se desfășoară două cursuri consecutive.
Metodele t radiționale de planificare, sun mai rapide dacă restricțiile sunt de tip
“aceste evenimente nu pot avea loc simultan”, dar algoritmii genetici reprezintă
o soluție superioară dacă există și alte restricții mai complicate.

40

ALGORITMI GENETICI
Vol.I

2.4.2 Sisteme inteligente bazate pe algoritmi genetici

Mecanismul specific acestor sisteme este inspirat din funcționare
sistemelor biologice, în sensul că încurajează soluțiile candidat capabile să
rezolve o problemă și penalizează soluțiile fără succes. În felul acesta se obțin,
după mai multe generații, soluții foarte bune pentru probleme de optimizare
complexe, cu un mar e număr de parametri.
Ideea de bază a unui algoritm genetic constă în a începe cu o populație de
soluții, fiecare mai performantă decât precedentele. Fazele ciclului prin care
operează un asemenea algoritm sunt:
1. crearea unei populații de “membri”,(soluții candidat la rezolv area unei
probleme),
2. selecția membrilor care s -au adaptat cel mai bine necesităților problemei
de soluționat,
3. reproducerea (se folosesc operatorii genetici de încrucișare și mutație,
pentru a obține noi membri),
4. evaluarea gradului în car e noii membri corespund mai bine soluționării
problemei,
5. abandonarea populației vechi prin înlocuirea ei cu populația nouă din
noua generație.
Un asemenea ciclu se repetă până când este identificată cea mai bună
soluție la problema în cauză.

41

ALGORITMI GENETICI
Vol.I

fazele ciclului algoritmilor genetici

Datorită structurii lor inerent paralele, sisteme inteligente bazate pe
algoritmi genetici s -au dovedit performante în problemele de căutare și
identificare a structurilor și relațiilor specifice în cadrul bazelor de date și
bazelor de cunoștințe voluminoa se (data mining). Un succes particular s -a
obținut cu ele în problemele de optimizare referitoare la selectarea personalului
și selectarea portofoliilor.
Și aceste sisteme, deoarece pot învăța relații și structuri complexe în
cadrul seturilor de informații și cunoștințe incomplete, se pot adapta
schimbărilor survenite în mediile în care funcționează, și pot fi utilizate ca
instrumente pentru descoperirea unor cunoștințe noi. Ele pot oferi explicații la
deciziile luate într -un format perceptibil de către om.
Abandonarea

Populația
Evaluarea
Reproducerea Selecția

42

ALGORITMI GENETICI
Vol.I
Aplicațiile acestor sisteme s -au diversificat rapid și s -au dovedit utile
domeniul afacerilor financiare, comerțului cu titluri, evaluării creditelor,
detecției fraudelor și predicției falimentului. De exemplu, unii cercetători au
folosit asemen ea sisteme la inferarea unor reguli pentru predicția falimentului
întreprinderilor, pe baza indicatorilor financiari obținuți din bilanț (financial
ratios). Alți cercetători descriu modul de utilizare a algoritmilor genetici în
alocarea bugetară, în vedere a asistării guvernelor și administrațiilor locale la
adoptarea celor mai bune decizii.

43

ALGORITMI GENETICI
Vol.I
BIBLIOGRAFIE:

1. Ion Iancu, Algoritmi genetici, Craiova 2004
2. Dumitrescu D., Algorit mi genetici și strategii evolu tive – Aplicații în
inteligența artificială și în do menii conexe, Editura Albastră , Cluj-
Napoca, 2000;
3. Oltean M., Proie ctarea și implementarea algorit milor, Computer Libris
Agora, Cluj-Napoca, 2000.
4. Genetic Algorith ms + Data Structures = Evolu tion Progra ms, Zbign iew
Michalewicsz, Second, Extended Edition
5. Beasley D., Bull D.R., Martin R.R., An Overview of Geneti c
Algorith ms, Part 1, Foundations, University Computing, Vol.15, No .4,
pp. 170 -181, 1993;
6. Goldberg D.E., Genetic Algorith ms in Search, Optimization and
Machine Learning, Addison – Wesley, Reading,MA,1989;
7. Garey M .R., Johnson D.S ., Computers and Intractability:A Guide to NP –
completenes s, W.H. Freeman and Company, New York, 1978.
8. Koza J.R., Genetic Progra mming, MI T Press, Cambridg e, MA, 1992;

44

ALGORITMI GENETICI
Vol.I
CUPRINS:

CAPITOLUL I
NOTIUNI INTRODUCTIVE

1.1 Istoric
1.2 Importanta temei in actualitate

CAPITOLUL II
ASPECTE TEORETICE DE BAZA

2.1 Cal cul evolutiv
2.1.2 Operatori gen etici – calculul evolutiv
2.2 Algoritmi gen etici paradig me ale calculului evolutiv
2.2.1 Atribuir ea fitness-ului
2.2.2 Struct ura unui algoritm genet ic
2.2.3 Selecția
2.2.4 Operatorii genetici
2.3 Strategii evolutive
2.3.1 Programare evolutivă
2.3.2 Programarea genetică
2.4 Sisteme hibride
2.4.1 Aplicatii ale algoritmilor genetici
2.4.2 Sisteme inteligente bazate pe algoritmi genetici

BIBLIOGRAFIE