Implementarea Algoritmilor Evolutivi

CUPRINS

INTRODUCERE

Conceptul de evoluție a fost propus de savantul englez Charles Darwin în 1859 în celebra sa carte “Originea speciilor prin selecție naturală”. Principala sa teză este:

“Speciile evoluează prin variații aleatoare urmate de selecție naturală în care cel mai potrivit supraviețuiește” .

Calculul Evolutiv (“Evolutionary computation”) reprezintă o direcție de cercetare nouă și de mare importanță atât din punct de vedere teoretic, cât mai ales, din punctul de vedere al aplicațiilor. Putem considera Calculul Evolutiv ca fiind un domeniu de sine stătător al Inteligenței Artificiale.

Din punctul de vedere al ideilor de pornire și aplicațiilor Calculul Evolutiv (sau adaptiv) evidențiază două aspecte:

-utilizează idei și concepte referitoare la sistemele adaptive complexe pentru a rezolva probleme computaționale (în special de optimizare și căutare)

-utilizează calculatoarele și metodele computaționale pentru a modela sisteme adaptive complexe.

Tehnicile calcului evolutiv au fost inițial dezvoltate pentru rezolvarea unor probleme de optimizare complicate, a căror abordare prin mijloace tradiționale era imposibilă.

Calculul Evolutiv s-a dezvoltat în mai multe direcții, cele mai cunoscute fiind:

Algoritmii Genetici

Strategiile Evolutive

Programarea Evolutivă

Programarea Genetică

Sistemele de Clasificare Instruibile

Metodele dezvoltate în Calculul Evolutiv sunt generale, independente de problemă și de funcția ce se dorește a fi optimizată (funcția criteriu). Proprietățile de continuitate, convexitate, derivabilitate sau de netezime ale funcției criteriu nu mai influențează alegerea metodei de optimizare. Aceste metode au o comportare bună, sunt robuste și, contrar unei păreri răspândite, nu sunt mari consumatoare de timp. Multe probleme care nu pot fi abordate cu tehnici tradiționale au putut fi soluționate utilizând metodele Calcului Evolutiv.

De regulă algoritmii genetici, strategiile evolutive și celelalte tehnici ale Calculului Evolutiv sunt utilizate pentru a optimiza o funcție criteriu. Există însă probleme pentru care nu este simplă formularea explicită (analitică) a unei funcții criteriu. Însă, de regulă, și în aceste cazuri se poate atașa un anumit scor fiecărei soluții găsite. Scorul măsoara calitatea soluției respective.

Calculul Evolutiv folosește concepte și metode care au punct de plecare o metaforă biologică. O populație (aleatoare) de soluții inițiale (cromozomi sau indivizi) este modificată prin operatori de tip biologic (selecție, încrucișare, mutație). Procesul de modificare favorizează soluțiile cele mai bune. Cei mai buni indivizi (cromozomi) vor fi selectați ca părinți ai unei noi generații de soluții. În felul acesta calitatea soluțiilor obținute se îmbunătățește. Cel mai bun individ obținut într-un număr fixat de generații va constitui soluția finală a problemei.

Lucrarea este structurată în patru capitole.

Capitolul 1 – “Algoritmi Evolutivi” – prezentare generală” – prezintă ideile de bază ale algoritmilor evolutivi, se evidențiază principiile evoluției și a selecției naturale, se prezintă structura generală a unui algoritm evolutiv.

Capitolul 2 – ”Algoritmi Genetici” – prezintă ideile fundamentale referitoare la algoritmii genetici. Se descriu operatorii genetici utilizati de un algoritm genetic (selecție, încrucișare, mutație). În finalul capitolului se prezintă algoritmul genetic fundamental.

Capitolul 3 – “ Strategii Evolutive” – prezintă ideile de bază referitoare la strategiile evolutive. Se descriu diferite modele de strategii evolutive. Sunt prezentați principalii operatori din cadrul unei strategii evolutive (selecție, recombinare, mutație).În finalul capitolului se prezintă structura generală a unei strategii evolutive.

Capitolul 4 – “Descrierea aplicației” – este consacrat prezentării aplicației.

CAP.1 Algoritmi evolutivi – prezentare generală

În acest capitol se prezintă principiile de bază ale algoritmilor evolutivi.Se evidențiază ideile evoluției și selecției naturale care au condus la clase importante de algoritmi de căutare și optimizare. Se prezintă structura generală a unui algoritm evolutiv.

1.1.Evoluția

Punctul de vedere acceptat in Inteligența Artificială este că îndeplinirea oricărei sarcini poate fi privită ca rezolvarea unei probleme. La rândul său, rezolvarea unei probleme poate fi gandită ca o căutare în spațiul soluțiilor posibile (spațiul starilor problemei). Această căutare poate fi ghidată de o funcție de performanță. Procesul de căutare este în acest caz însoțit de un proces de optimizare: dintre soluțiile posibile suntem interesați de cea mai bună. Uneori ne putem mulțumi cu o soluție suficient de bună (aproximativ optimă).

Pentru probleme de mare complexitate, găsirea soluției optime, sau chiar a uneia acceptabile, este dificil de realizat. Tehnicile clasice fie nu sunt aplicabile, fie necesită un timp de lucru prohibitiv. Algorimii evolutivi sunt adecvați tocmai pentru soluționarea unor astfel de probleme dificile.

Algoritmii evolutivi reprezintă tehnici de căutare și optimizare având ca punct de pornire o metaforă biologică. Această metaforă biologică este cea a moștenirii genetice și a evoluției naturale.

În cursul evoluției, toate ființele sunt confruntate cu problema adaptării la un mediu complicat, in continuă schimbare. In acest proces fiecare specie “invață”, iar cunoașterea pe care a caștigat-o este codificată in cromozomii speciei. Evoluția este așadar un proces care are loc la nivelul cromozomilor.

Din perspectiva care ne intereseaza aici reținem doar câteva caracteristici esențiale ale procesului de evoluție genetică:

Cromozomii sunt purtătorii informației genetice.

Fiecare individ al unei specii posedă un număr determinat de cromozomi.Totalitatea cromozomilor unui individ reprezintă genotipul său.

Cromozomii sunt structuri liniare alcătuite din gene. Genele poartă caracteristicile ereditare. Genele ocupă locuri determinate , numite loci , în cromozom.

Evoluția este un proces ce operează la nivelul cromozomilor.

Selecția naturală reprezintă legatura dintre cromozomi și performanșele indivizilor.

Evoluția se realizează în procesul reproducerii. In evoluție acționează procese de selecție, recombinare și mutație.

În 1965, John Holland de la Universitatea Michigan a avut idea de a aplica modelul genetic al evoluției în rezolvarea unor probleme de căutare și optimizare. Sistemele construite în acest fel utilizează o populație de cromozomi ce reprezintă o mulțime de soluții potențiale. Prin procese de selecție, mutație și recombinare sistemul evoluează spre stări mai apropiate de optim. Selecția cromozomilor pentru modificare se face folosind o funcție de evaluare (adecvare). Originea algoritmilor evolutivi poate fi pusă în legatură cu unele lucrari din anii ’50, cum ar fi cele ale lui Box (1957) și Fraser (1957).

Algoritmii evolutivi implementează proceduri care imită procesele de adaptare / căutare apărute in evolutia naturală. Toți algoritmii evolutivi folosesc populații în care fiecare individ reprezintă un punct din spațiul de căutare. Algoritmii evolutivi se bazează pe principiul invățării colective într-o populație.

Cele mai cunoscute tipuri de algoritmi evolutivi sunt programarea evolutivă, strategiile evolutive și algoritmii genetici.

1.2 Principii generale

Algoritmii evolutivi (AE) utilizează o populație de soluții potențiale ce evoluează după regulile stabilite de un operator de selecție și de alți operatori cum ar fi recombinarea și mutația. Fiecărui individ al populatiei îi este asociată o măsură a adecvării sale la mediu (calitatea soluției reprezentată de individ). Selecția favorizează indivizii având o adecvare înaltă, exploatând așadar informația disponibilă in privința adecvării. Recombinarea și mutația perturbă indivizii, furnizând euristici generale pentru explorare. Inspirați din ideile evoluției și selecției biologice, acești algoritmi sunt, din punct de vedere biologic, proceduri simpliste. Cu toate acestea, algoritmii evolutivi sunt proceduri destul de complexe pentru a furniza mecanisme de selecție adaptive, robuste și eficace.

Un algoritm evolutiv stabilește în mod aleator o populație de soluții inițiale. Uneori selecția se face în doi pași: selecția părinților și supraviețuirea. Selecția părinților decide care indivizi vor fi parinții noii generații si câți descendenți va avea fiecare pereche de parinți. Descendenții sunt creați prin recombinare (care schimba între parinți informația genetica) și mutație (care perturbă descendenții). Descendenții sunt evaluați. Pasul de supraviețuire decide care din indivizi (părinți și copii) vor forma noua generație (vor supraviețui).

1.3 Structura unui algoritm evolutiv

Algoritmii evolutivi reprezintă mai multe clase de metode aleatoare de căutare. Fiecare individ al populațiilor implicate in procesul de căutare se descrie printr-un singur cromozom.

Orice algoritm evolutiv folosește o populație de indivizi (cromozomi) care este modificată prin intermediul unor operatori genetici cum ar fi cei de selecție, mutație, recombinare. Timpul variază discret. Notăm cu P(t) populația de cromozomi de la momentul t, unde t=0,1,2,… .

Fie X spațiul de căutare (spațiul stărilor problemei). Fiecare individ (cromozom) reprezintă un element din X, adică o soluție posibilă a problemei. Evaluarea calității indivizilor din spațiul de căutare se face cu ajutorul unei funcții de performanță. Alte denumiri utilizate sunt: funcție de potrivire, functie de evaluare sau funcție de adecvare. Fie f:X R, funcția de performanță (sau funcția de adecvare). Fiecare individ (soluție) este evaluat prin intermediul acestei funcții.

Fie P(t) = { xt1 , xt2 , …, xtn} populația de la momentul t. P(t) reprezintă o generație.

Noua generație P(t+1) se formează selectând cei mai performanți indivizi din P(t) și aplicând asupra lor operatorii genetici de selecție, recombinare, mutație.

1.3.1 Operatorii

Selecția

Operatorul de selecție este utilizat în scopul de a asigura mai multe șanse de reproducere celor mai performanți indivizi dintr-o populație dată. Acțiunea operatorului de selecție stabilește indivizii din populația curentă ce vor contribui la constituirea generației următoare. Pentru a realiza selecția este necesară introducerea unei măsuri a calității (performanței , adecvării) indivizilor. Prin selecție se urmărește maximizarea performanței indivizilor.

Recombinarea

Operatorul de recombinare (încrucișare) este folosit pentru a crea noi indivizi folosind segmente (subșiruri) a doi sau mai mulți cromozomi. Operatorul de recombinare se poate defini ca o aplicație R:Xp Xq . În acest caz spunem că operatorul R realizează o transformare de tipul (p , q) în care p părinți dau naștere la q descendenți.

Mutația

Operatorul de mutație reprezintă o transformare unară m:X X. Operatorul de mutație crează noi indivizi prin schimbări (mici) ale unui singur individ. De exemplu permite schimbarea unei singure gene a individului (cromozomului) respectiv. Mutația realizează mici perturbări ale cromozomilor obținuți prin recombinare.

Supraviețuirea

Operatorul de supraviețuire decide care cromozomi (părinți și descendentii lor obținuti prin recombinare și mutație) vor forma efectiv noua generație. Fiecare tip de algoritm evolutiv are un mecanism propriu ce realizează supraviețuirea.

Populația inițială se generează de regulă prin selectarea aleatoare a unor puncte din spațiul de căutare. În unele cazuri cunoștințele specifice despre domeniul problemei pot servi pentru a ghida căutarea.

Criteriul de oprire pentru un algoritm evolutiv este de regulă legat de numărul de generații. Cel mai performant individ al ultimei generații ( sau cel mai important individ din întreaga istorie a procesului ) reprezintă soluția obținuta pentru problema în discuție. Mai putem utiliza ca și criteriu de oprire faptul că valorile funcției obiectiv nu s-au modificat semnificativ în ultimele generații.

1.3.2 Structura generală a e generații.

1.3.2 Structura generală a unui algoritm evolutiv

P1. Se pune t:=0

P2. Se inițializează populația P(t)

P3. Se evaluează P(t) utilizând o funcție de performanță f.

P4. Până când (condiție) se execută

{

Selecția P(t) P1(t) ;

Recombinarea P1(t) P2(t) ;

Mutația P1(t) P(t+1);

t:=t+1;

}

Observație:

La pasul P4 apare o condiție de oprire a algoritmului. De regulă aceasta condiție se referă la atingerea numărului de generații prescris.

Orice procedură evolutivă trebuie să furnizeze următoarele elemente:

O reprezentare genetică a spațiului de căutare (spațiul stărilor problemei sau spațiul soluțiilor potențiale ale problemei).

O populație inițiala de soluții potențiale. De regulă, populația inițială se alege în mod arbitrar.

O funcție de evaluare ce masoară performanța fiecărui individ în raport cu scopul urmărit.

O metodă de selectare a cromozomilor pentru modificare și recombinare(reproducere).

Operatorii genetici pentru crearea de noi cromozomi prin recombinare, mutație etc.

Valorile parametrilor ce apar in algoritmul evolutiv (dimensiunea populației , probabilitățile de aplicare a diferiților operatori genetici, numărul total de generații).

1.4 Domenii de aplicabilitate

Algoritmii evolutivi pot fi folosiți pentru o mare varietate de scopuri, în special în sistemele inteligente de rezolvare a problemelor. Aplicarea unor clase de algoritmi evolutivi pentru rezolvarea problemelor de optimizare permite obținerea de rezultate interesante, care nu ar putea fi obținute prin metodele standard de optimizare.

În continuare indicăm câteva domenii specifice de aplicare a algoritmilor evolutivi:

1. Optimizare

optimizare numerică și combinatorială

proiectarea circuitelor, a sistemelor de conducte și a liniilor de comunicație

proiectarea avioanelor

planificarea proceselor de producție

2. Programare automată

obținerea de algoritmi de sortare

obținerea programelor Lisp pentru o problemă dată

3. Instruirea mașinilor

controlul deplasării unui robot

deplasarea într-un labirint

proiectarea rețelelor neuronale

deducerea regulilor pentru rezolvarea diferitelor probleme

abordarea unor jocuri dificile

obținerea de modele economice, politice, sociale.

4. Analiza datelor complexe și predicția seriilor de timp

predicția sistemelor haotice

predicția vremii

predicții financiare

predicții asupra evoluției pieței

predicția structurii proteinelor.

5. Modele ale unor procese complexe din:

economie

politică

neurologie

ecologie

genetica populațiilor .

CAP2. Algoritmi genetici

2.1 Introducere

În acest capitol sunt prezentate noțiunile fundamentale referitoare la algoritmii genetici, componentele și structura acestora.

Într-un algoritm genetic, fiecare element al spațiului de căutare se poate reprezenta ca un individ (cromozom) al unei populații. Fiecare cromozom este constituit dintr-o mulțime de elemente numite caracteristici sau gene. În abordările standard numărul de gene dintr-un cromozom este constant pentru o problemă dată. Numărul genelor definește lungimea cromozomului. Lungimea cromozomilor este stabilită in funcție de natura problemei. Cea mai raspandită este codificarea binară a valorilor genelor.

Algoritmii genetici au fost inventați de John Holland în 1960 și au fost dezvoltați de el, studenții și colegii săi de la Universitatea din Michigan între anii 1960 – 1970. În contrast cu strategiile evolutive și programarea evolutivă, scopul inițial al lui Holland nu a fost să proiecteze algoritmi care să rezolve probleme specifice ci mai degrabă să studieze fenomenul adaptării așa cum apare el in natură și să dezvolte moduri în care mecanismul natural al adaptării să poată fi importat în sistemele de calcul. Cartea lui Holland din 1975 “Adaptarea în sistemele naturale și artificiale” prezintă algoritmul genetic ca o abstracție la evoluția biologică. Algoritmul genetic al lui Holland este o metodă pentru a trece de la o populație de cromozomi (șiruri de unu și zero) la o nouă populație folosind un fel de selecție naturală împreună cu operatori genetici de încrucișare, mutație, inversiune.Fiecare cromozom constă dintr-un număr de gene, fiecare genă fiind o instanță a unei alele particulare (0 sau 1). Operatorul de selecție alege acei cromozomi din populatie cărora le este permis să se reproducă. Incrucișarea shimbă parți din doi cromozomi, mutația schimbă aleator valorile genelor din unele locații din cromozom.Operatorul de inversiune inversează valorile a doua poziții ale cromozomului, poziții care sunt alese in mod aleator.Faptul ca Holland a introdus un algoritm bazat pe o populație împreună cu operatorii genetici a fost o mare inovație.

2.2 Principii generale

Pentru rezolvarea unei probleme folosind un algoritm genetic este necesară definirea de către utilizator a unei functii care masoară performanța (adecvarea) fiecărui cromozom. Funcția de performanță (adecvare) depinde de abilitatea utilizatorului de a codifica în mod adecvat problema sa. Dacă se rezolvă o problemă clasică de optimizare sau una de optimizare combinatorială, funcția de adecvare poate coincide cu funcția criteriu (funcția obiectiv) asociată problemei sau se obține prin transformări simple aplicate funcției criteriu.

Un algoritm genetic este o procedură iterativă de căutare globală având drept scop optimizarea funcției de evaluare. Algoritmul lucrează în paralel asupra unei populații de soluții potențiale (cromozomi) distribuite peste întreg spațiul de căutare. În mod obișnuit, valoarea performanței unui cromozom este independentă de performanțele celorlalți indivizi ai populației.

Dinamica procesului de căutare generat de un algoritm genetic se realizează prin combinarea și modificarea cromozomilor. Scopul este găsirea combinației optime, adică a acelei combinații ce corespunde adecvării maxime. La fiecare iterație a algoritmului se creeaza o noua populație, numita generație. Toate generațiile au același număr de indivizi. Se admite că, în general, noua generație consta din indivizi mai performanți, adică mai bine adaptați la mediul reprezentat de funcția de adecvare. Cu succesiunea generatiilor se va înregistra o tendința de evoluție a indivizilor spre optimul global al funcției de adecvare..

Obținerea unei noi generații plecând de la precedenta are loc în trei etape:

1. Evaluarea

Algoritmul genetic calculează valoarea funcției de adecvare pentru fiecare individ al vechii populații.

2. Selecția

Algoritmul genetic selecționeaza indivizii unei populații P(t) in funcție de performanțele lor. Indivizii selectionați vor reprezenta o populație intermediară P1. Cromozomii populației P1 devin parinții noii generații P(t+1).

3. Recombinarea și modificarea

Algoritmul genetic recombina și modifică indivizii selecționați. În acest scop se utilizează operatorii genetici de încrucișare, mutație, inversiune. Din punct de vedere algoritmic, operatorii genetici reprezintă metode de a schimba local soluțiile reprezentate de părinți (mutația și inversiunea) sau de a combina aceste soluții (încrucișarea). Încrucișarea constă într-un transfer de gene între doi cromozomi.

Fiecărui operator genetic îi corespunde o probabilitate de aplicare. Aceste probabilitați sunt parametri ai algoritmului. Operatorii genetici de recombinare și modificare se aplică, cu probabilitațile respective, asupra populației intermediare. Aplicând operatorul de incrucișare asupra populației P1 se obține o noua populație P2. Asupra indivizilor populației P2 se aplică operatorii mutație, inversiune, etc. Indivizii din P2 împreună cu acei indivizi din P1 care nu au suferit recombinarea vor constitui noua generație P(t+1). Sunt posibile numeroase alte modalitati de a selecta cromozomii populației P(t+1).

2.3 Structura unui algoritm genetic

Primul pas în utilizarea unui algoritm genetic este stabilirea unei codificări a problemei. Cea mai obișnuită dintre tehnicile de codificare este codificarea binară. Ea este simplu de creat și de manipulat. În plus, această modalitate de reprezentare permite stabilirea unor rezultate teoretice interesante, cum ar fi teorema schemelor.

Codificarea binară oferă robustețe algoritmilor genetici, asigurând obținerea unor performanțe bune pentru diferite clase de probleme. Reprezentarea binară poate codifica aproape orice situație, iar operatorii nu include cunoștințe despre domeniul problemei. Este motivul pentru care un algoritm genetic se poate aplica unor probleme foarte diferite.

În codificarea binară fiecare cromozom este un șir de biți de 0 sau 1.

Exemplu de cromozomi codificați binar

Codificarea binară este codificarea specifică pentru algoritmii genetici.

Un alt tip de codificare este codificarea permutațională.. Această codificare este potrivită în special pentru rezolvarea unor probleme de ordonare, ca de exemplu problema comis-voiajorului. În acest tip de codificare fiecare cromozom este un șir de numere într-o anumită secvență. Acest tip de codificare este folositor doar pentru probleme de ordonare.

Un exemplu clasic de problemă în care se folosește aceasta codificare este problema comis voiajorului. (“Travelling Salesmam Problem” (TSP)).

Exemplu de cromozomi codificați permutațional

Mai există și alte tipuri de codificare cum ar fi codificarea arborescentă (“tree encoding”) care se folosește pentru programare genetică.

Structura unui algoritm genetic este identică, in esență, cu cea a unei proceduri evolutive. Cromozomii utilizați au lungime constantă și sunt codificați binar. Populația (generația) P(t+1) la momentul (t+1) se obține reținând toți descendenții populației P9t) și ștergând apoi complet cromozomii generației precedente (P(t)).

Numărul cromozomilor în fiecare generație este constant. Principalii operatori genetici utilizați sunt cei de selecție, mutație, încrucișare și inversiune.

Algoritmul genetic standard (algoritmul canonic) are ca operatori principali încrucișsarea și mutația.

Structura acestui algoritm genetic se poate reprezenta ca mai jos:

Algoritmul genetic fundamental (canonic)

P1. Se pune t:=0

P2. Se inițializează aleator populația P(t).

P3. Se evaluează cromozomii populației P(t).

P4. Cât timp (non C) execută:

P4.1. Selectează cromozomii din P(t) care vor contribui la formarea noii generații. Fie P1 mulțimea cromozomilor selectați. (P1 reprezintă o populație intermediară).

P4.2. Se aplică cromozomilor din P1 operatorii genetici. Cei mai utilizați operatori genetici sunt operatorii de mutație și încrucișare. În funcție de problemă se pot alege și alți operatori (inversiune, reordonare, operatori speciali).

Fie P2 populația astfel obtinută (descendenții populației P(t)).

Se șterg din P1 parinții noilor indivizi obținuți.

Cromozomii rămași în P1 sunt atribuiți populației P2.

Se construiește noua generatie, punând:

P(t+1) := P2

Se șterg toți cromozomii din P(t).

Se pune t:=t+1

Se evaluează P(t)

Sfarsit cât timp.

Observații:

1. Condiția de oprire C se referă, de regulă, la atingerea numărului de generații specificate. Dacă numărul maxim admis de generații este N, atunci condiția de oprire C este t > N.

De obicei se admite că rezultatul algoritmului este codificat de cel mai performant individ din ultima generatie. În realitate, nimic nu ne garantează că un individ mai performant nu a fost obținut într-o generație anterioară. Este deci natural ca la fiecare pas (la fiecare moment t) să reținem cel mai bun individ care a fost generat până atunci. Pentru a implementa această strategie sunt necesare câteva modificări în algoritmul de mai sus.

Modificarea propusă în observația precedentă poate fi extrem de utilă. În acest fel suntem siguri că cea mai bună soluție găsită nu s-a pierdut pe parcurs.

Sunt posibile și numeroase alte variante de supraviețuire. Putem de exemplu să considerăm că cei mai buni q indivizi din generația P(t) vor fi incluși în mod automat în generatia următoare. Totodată ei vor putea să sufere și operațiile de recombinare, mutație,etc.

2.4 Operatorii genetici ai AG

2.4.1 Selecția

Scopul selecției este de a asigura mai multe șanse de reproducere celor mai performanți indivizi dintr-o populație dată. Acțiunea operatorului de selectie stabilește indivizii din populația curentă ce vor contribui la constituirea generației următoare.

Pentru a realiza selecția este necesara introducerea unei măsuri a calității (performanței, adecvării) indivizilor. Prin selecție se urmărește maximizarea performanței indivizilor. Căutarea se concentrează așadar în regiunile spațiului soluțiilor ce corespund adecvării maxime. Această concentrare realizează exploatarea celor mai bune soluții găsite, ceea ce constituie sarcina selecției.

În continuare vom prezenta diferite mecanisme de selecție, subliniind avantajele și limitele fiecăruia.

Selecția proporțională

Există mai mulți algoritmi de selecție. Cel mai uzual tip de selecție este selecția proporțională. În acest caz, selecția unui individ depinde de valoarea performaței acestui individ.

Fie X mulțimea tuturor cromozomilor posibili (pentru o problemă și o codificare date) și fie f : X R funcția de adecvare (evaluare, performanță).

Funcția de adecvare f trebuie să indeplinească cerințele:

f trebuie să fie pozitivă

f(x) 0 , x X.

f trebuie să reflecte calitatea cromozomilor, în sensul optimizării funcției obiectiv

Dacă f are și valori negative, atunci efectuăm o scalare prin care valorile lui f se deplasează în domeniul pozitiv.

Selecția se face asupra cromozomilor din populația curentă P(t).Admitem că această populație conține n cromozomi:

P(t) = {x1 , x2 , x3 , … , xn}

Fie F performanța totală a populației definite ca suma performanțelor individuale:

F =

În cazul selecției proporționale, probabilitatea de selecție a cromozomului xi este numărul pi = , i=1,2,..,n

Deoarece operatorul de selecție se aplică de n ori, valoarea medie a numărului descendenților individului i este:

ni = n pi

Rezultă că avem:

ni=

Prin urmare mecanismul de selecție asigură în medie :

ni =

copii ale cromozomului xi unde este performanța medie a populației.

Algoritmul Monte Carlo de selecție (algoritmul ruletei)

Pentru a realiza selectarea lui xi cu probabilitatea pi (adică o distribuție de probabilitate uniformă) se poate utiliza o metoda de tip Monte Carlo. Se construiește o ruletă imparțita în n sectoare. Fiecare sector corespunde unui cromozom. Dimensiunea sectorului i este proporțională cu probabilitatea pi de selecție a cromozomului xi. Ruleta este rotită de n ori. La fiecare rotire este selectat un cromozom. Cromozomul selectat este copiat în populația intermediară. Fiecare cromozom ocupă un loc în ruleta cu atât mai mare cu cât este mai mare probabilitatea sa de selecție, ca și în figura următoare:

Selecția bazată pe principiul ruletei funcționează conform următorului algoritm:

P1. Pentru fiecare cromozom xi , i = 1, 2, … , n, se calculează numărul:

qi = , i = 1, 2, …, n

P2. Pentru i = 1, 2, …, n execută:

P2.1. Se generează aleator un număr g în intervalul [0,1]

P2.2 Regula de selecție:

Dacă 0 g q1 atunci este selectat primul cromozom (x1).

Dacă qi-1 g qi atunci este selectat cromozomul xi.

Observație:

Schema de selecție prezentată permite ca un cromozom să fie selectat de mai multe ori. Așadar, cei mai performanți cromozomi pot avea mai multe copii în populația intermediară deci mai mulți descendenți.

Deși există versiuni mai stabile ale algoritmului ruletei (Goldberg, 1989) în mod uzual se folosește pentru selecție varianta standard dată mai sus a acestui algoritm. În paragrafele următoare vom indica diferite modalităti de ameliorare a selecției.

Selecția bazată pe ordonare

O altă idee de selectie constă în a calcula (pentru fiecare generație) valorile funcției de adecvare și de a aranja indivizii în ordinea descrescătoare a acestor valori. Se va atribui fiecărui individ i o probabilitate de selecție pi ce depinde de rangul său in șirul stabilit. În acest scop se utilizează presiunea de selecție.

Presiunea de selecție se definește ca fiind numărul mediu de descendenți ai celui mai performant individ. Presiunea de selectie este o constantă a metodei. De regulă presiunea de selecție se exprimă printr-un număr q din intervalul [1,2].

Fie n mumarul de indivizi ai populației și ri rangul individului i. Probabilitatea de selecție pentru individul i este pi = , unde q este presiunea de selcție.

Aceasta strategie de selectie se numește selecția prin ordonare. Ea este o alternativă al carei scop este de a preveni convergența prea rapidă. Se observă că probabilitățile de selecție depind acum doar de poziția relativă a cromozomilor și nu de valorile funcției de adecvare. În acest fel se evită inconvenientele selecției proporționale. Probabilitatea de selecție a primului cromozom, obținuta punând r1 = 1, este:

p1=

Pentru individul ultim clasat, rn = n, avem probabilitatea de selecție:

pn = .

Numărul mediu de selectări ale individului i este npi.

Având în vedere că np1 = q rezultă că cel mai performant individ va fi selectat, în medie, de q ori.

Pentru ultimul cromozom avem

npn = 2 – q.

Rezultă că cel mai puțin performant individ va avea in medie (2 – q) selectări, deci un numar mediu de (2-q) descendenți.

Creșterea presiunii de selecție orientează căutarea celor mai performanți indivizi, determinând micșorarea diversitații populației. Prin urmare, o presiune de selecție ridicată poate fi asociată cu o convergența prematură a căutării. O presiune de selecție scăzută poate duce la uniformizarea selecției, căutarea devenind puțin eficientă. Trebuie astfel menținut un echilibru între diversitatea populației și presiunea de selecție.

Creșterea presiunii de selecție focalizează căutarea asupra celor mai performanți indivizi. Această exploatare a celor mai bune soluții găsite este însoțită de o pierdere a diversității genetice, ceea ce antrenează reducerea capacității de exploatare a spațiului stărilor. Reducerea presiunii de selecție crește capacitățile de exploatare, deoarece în procesul de căutare vor fi incluși mai mulți cromozomi.

Orice funcție descrescătoare f : N R, poate fi utilizată pentru o selecție bazată pe ordonare. De exemplu, alegând un parametru h în intervalul (0,1) putem defini o probabilitate de selecție indusă de funcția neliniară:

f (i) = h(1-h)I –1 , i = 1, 2, …, n

În acest caz vom avea:

pi = f (i) , i = 1,2, …, n

Intuitiv, acest tip de selecție este prezentat în figurile următoare:

Situația înainte de ordonare

Situația după ordonare

Alte mecanisme de selecție

Elitism

Ar putea fi interesant ca la fiecare generație cel mai bun individ al unei populații să fie păstrat. O astfel de strategie se numește elitistă. Pare natural ca cel mai bun individ al unei generatii să fie selectat ca un candidat pentru următoarea faza (cea de incrucișare). Elitismul a fost introdus prima dată de Kenneth De Jong (1975) ca o adăugare la diferite metode de selecție astfel incât să se rețină un număr de cei mai buni indivizi la fiecare generație.

Selecția prin concurs sau selecția turnir (tournament selection)

Acest tip de selecție se bazează pe compararea directă a câte doi cromozomi și selectarea celui mai performant. Operațiile implicate în acest tip de selecție sunt următoarele:

Se aleg în mod aleator doi cromozomi

Se calculează adecvările cromozomilor selectați

Cromozomul mai performant este selectat (copiat în populația intermediară asupra căreia vor acționa operatorii de incrucișare și modificare).

Pentru a genera o populație intermediară formată din n cromozomi (copii nu neapărat distincte ale cromozomilor de la momentul t) este necesar ca mecanismul descris să fie aplicat de n ori.

2.4.3 Încrucișarea

Selecția este folosită pentru a concentra căutarea asupra celor mai promițătoare regiuni ale spațiului stărilor. Selecția singură nu poate însă introduce in populație indivizi care nu apar în populația intermediară. În acest scop se folosesc alți operatori, care perturbând indivizii existenți asigură explorarea zonelor învecinate. Dintre aceștia, cei mai folosiți sunt operatorii de încrucișare, mutație și inversiune.

Operatorul de încrucisare (crossover operator) realizează recombinarea indivizilor selectați. Operatorul permite combinarea segmentelor (subșirurilor) de cromozomi corespunzând părintilor. Operatorul imită încrucișarea intercromozomială naturală. De regulă se utilizează operatori de incrucișare de tipul (2,2), adică din doi părinți se obțin doi descendenți.

Încrucișarea (recombinarea) realizează un schimb de informație între cromozomii părinți. Descendenții obținuți prin recombinare vor avea caracterisici ale ambilor părinți. Încrucișarea are rolul de a face să progreseze căutarea, asigurând explorarea spațiului stărilor.

Dată fiind importanța majoră a recombinării, au fost propuse numeroase variante de încrucișare. Vom indica în continuare cele mai utilizate variante.

Încrucișarea cu un singur punct de tăietură (“one point crossover”)

Recombinarea materialului genetic a doi cromozomi se poate face în diferite moduri. John Holland (1975) a considerat un operator numit încrucișare cu un singur punct de tăietură.

Fie r lungimea cromozomilor unei populații. Un punct de tăietură este un număr întreg k {1 , 2, …, r-1}. Numărul k indică poziția din interiorul cromozomilor unde secvența cromozomială se rupe pentru ca segmentele obținute să se recombine.

Considerăm doi cromozomi:

x = x1 x2 x3 … xk xk+1 xk+2 …xr

și

y = y1 y2 y3 … yk yk+1 yk+2 …yr .

În urma recombinării se schimbă între cei doi cromozomi secvențele aflate la dreapta punctului de tăietură k. Cromozomii copii vor fi:

x’ = x1 x2 x3 … xk yk+1 yk+2 …yr

și

y’ = y1 y2 y3 … yk xk+1 xk+2 …xr

De exemplu, fie cromozomii:

În urma încrucișării cu punctul de tăietură k = 2 rezultă succesorii:

Pentru o pereche dată de cromozomi alegerea punctului de tăietură se face în mod aleator.

Fie X mulțimea tuturor cromozomilor de lungime fixată r. Notăm cu C operatorul de încrucișare C : X x X X x X. Putem descrie acțiunea operatorului C considerând din nou doi cromozomi:

x = x1 x2 x3 … xk xk+1 xk+2 …xr

și

y = y1 y2 y3 … yk yk+1 yk+2 …yr

În acest caz avem:

C(x , y) = (x’ , y’)

unde:

x’ = x1 x2 x3 … xk yk+1 yk+2 …yr

și

y’ = y1 y2 y3 … yk xk+1 xk+2 …xr

iar k este un numar aleator din mulțimea {1, 2, … , r-1}. Numărul k este așadar o valoare a unei variabile aleatoare cu valori întregi uniform distribuite.

Încrucisarea cu mai multe puncte de tăietură (“many point crossover”)

Încrucișarea se poate face (la fel ca în natură) utilizând unul sau mai multe puncte de tăietură. În cazul utilizării mai mulor 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 încrucișare se face conform schemei 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:

Pentru patru puncte de tăietură se vor obține descendenți de forma:

Generalizarea pentru un număr m, m < r, de puncte de tăietură este evidentă. Încrucișarea cu mai multe puncte de tăietură este justificată de faptul că utilizând un singur punct de tăietură, anumite combinații de gene nu pot fi realizate. Un alt argument în favoarea considerării mai multor puncte de tăietură este existența unei asimetrii între încrucișare și mutație. Numărul mediu de cromozomi care vor suferi o mutație crește cu lungimea cromozomilor. Încrucișarea cu un punct de tăietură nu este în nici un fel sensibilă la creșterea lungimii cromozomului.

Alte variante ale operatorului de încrucișare

Încrucișarea adaptivă

Încrucișarea adaptivă a fost propusă de către Shaffer și Morishima (1987). Ideea este de a găsi un mecanism prin care se ține seama de calitatea descendentilor obținuți prin încrucișarea cu diferite puncte de tăietură. Distribuția punctelor de încrucișare se adaptează în funcție de rezultatele deja obținute. Acest lucru se realizează inregistrând pozitiile punctelor de tăietură din cromozom. Dacă un anumit punct de tăietură a generat un descendent foarte slab, atunci acest punct de tăietură nu va mai fi considerat (punctul moare). Dacă adecvarea descendentului este bună, punctual de tăietură respectiv este menținut activ. În felul acesta punctele de tăietură vor suferi un proces de evoluție prin care ele se adaptează la procese care deja au avut loc.

Încrucișarea segmentată

Încrucișarea segmentată (Eshelman, Caruna si Shffer, 1989) este o variantă a încrucișării cu mai multe puncte. Numărul punctelor de tăietură poate să varieze. Se consideră o probabilitate s ca un segment să aibă extremitatea dreaptă in oricare din pozițiile ce urmează inceputului său. Numărul mediu de segmente va fi sr. Pornind de la prima poziție i =1 a cromozomului se generează un numar aleator q [0 , 1] și un număr natural i < j r. Putem considera q ca fiind probabilitatea de acceptare a punctului de tăietură j. În funcție de relația existentă între s și q punctul j este sau nu acceptat. În acest fel, numărul de puncte de tăietură poate să varieze.

Încrucișarea cu amestec

Încrucișarea cu amestec (shuffle crossover) urmărește să introducă o diversitate mai mare a descendenților. Încrucișarea cu amestec se aplică împreună cu oricare alt operator de incrucișare, fiind un mecanism suplimentar.

Procesul decurge dupa rețeta următoare:

Se amestecă aleator genele celor doi cromozomi x și y retinând însă pozțtia inițială a fiecărei gene. Rezultă cromozomii x1 și y1.

Se încrucișează cei doi cromozomi x1 și y1 folosind un operator de încrucișare (cu mai multe puncte de tăietură, de exemplu). Fie x2 și y2 cei doi descendenți obtinuți.

Se realizează dezamestecarea (reordonarea) pozițiilor cromozomilor x2 și y2. Rezultă descendenții x3 și y3.

Încrucișare uniformă

Încrucișarea uniformă (Syswerda, 1989) nu folosește puncte de tăietură. Pentru fiecare genă a unui descendent un parametru global va indica probabilitatea ca această genă să provină din primul (sau al doilea) părinte. Așadar se presupune că fiecare pozitie a unui decendent se calculează separat. Pentru fiecare pozitie a primului descendent se alege (cu o probabilitate dată p) părintele care va da valoarea poziției respective. Pentru al doilea descendent se ia valoarea poziției corespunzătoare din celălalt părinte. Putem considera și un mecanism în care genele fiecărui decendent se calculează în mod independent. Un părinte poate da astfel valoarea unei gene în ambii descendenți. Încrucișarea uniformă cu probabilitatea p generează un numar mediu de p r puncte de tăietură, unde r este lungimea cromozomului. Încrucișarea uniformă este o generalizare a încrucișării cu mai multe puncte de tăietură. Avantajul încrucișării uniforme este că poate să combine caracteristici indiferent de poziția lor relativă. Pentru anumite probleme, această abilitate compensează neajunsul de a distruge blocurile constructive. S-a constatat că în anumite cazuri încrucișarea uniformă are performanțe mai slabe decât încrucișarea cu două puncte de tăietură.

Eshelman, Caruna si Shaffer (1989) au realizat un studiu experimental comparativ al diferiților operatori de încrucișare. Rezultatele nu au reușit să stabilească o ierarhie a operatorilor de încrucișare. S-a putut observa că fiecare operator este mai potrivit pentru anumite clase de probleme, având rezultate slabe pentru altele. Rezultatele obținute au mai arătat că operatorul de încrucișare cel mai slab este cel cu un singur punct de tăietură.

Operatorul de încrucișare se aplică asupra indivizilor determinați prin operatorul de selecție. Notăm cu pc probabilitatea de aplicare a încrucișării. Probabilitatea de încrucișare pc este unul din parametrii importanți ai unui algoritm genetic.

Algoritmul de încrucișare

Prin operatorul de încrucișare se introduc în populație noi cromozomi. Acest lucru se realizează dupa următoarea schemă:

P1. Pentru fiecare cromozom din populația intermediară P1 se execută pașii P1.1 si P1.2.

P1.1. Se generează un număr aleator q în intervalul [0,1]. Generarea urmează o distribuție uniformă în intervalul considerat.

P1.2. Dacă q < pc , unde pc este probabilitatea de încrucișare, cromozomul respectiv este reținut pentru încrucișare. În caz contrar acest cromozom nu participă la încrucișare.

P2. Fie m numărul cromozomilor reținuți la pasul P1. Dacă numărul m este par, atunci cu cromozomii selectați se formează m / 2 perechi. Perechile se formează în mod aleator.

Dacă m este impar, atunci fie se șterge un cromozom selectat, fie se adaugă unul nou dintre cei existenți în populația intermediară.

Se optează pentru adăugare sau ștergere în mod aleator, prin generarea unui număr aleator suplimentar.

P3. Asupra perechilor formate la pasul P2. se aplică încrucișarea. În acest scop se execută pașii următori:

P3.1. Pentru fiecare pereche se generează aleator un număr întreg k, 1k <r, unde r este lungimea cromozomilor.

Numărul k indică punctul de tăietură. Dacă se dorește încrucișarea cu t2 puncte de tăietură, se generează aleator numerele k1, k2, k3, …, kt. Aceste numere vor indica punctele de tăietură.

Se execută încrucișarea perechii curente folosind punctul de tăietură găsit (sau punctele de tăietură)

P3.2 Descendenții obtinuți la pasul P3.1. devin membri ai populației P(t+1).

P3.3. Se șterg din P1 părinții cromozomilor nou obținuți la pasul P3.1.

P3.4. Se adaugă la populația P(t+1) cromozomii încă rămași in P1.

Probabilitatea de încrucișare

Probabilitatea de încrucișare are, de regulă, valori de ordinul 10-1. Stabilirea valorii parametrului pc depinde de problema curentă. Este rezonabil să admitem că, de regulă, valorile probabilității de încrucișare se situează în domeniul [0.2 , 0.95].

Dacă avem, de exemplu, pc = 0.3 înseamnă că 30% din indivizii populației vor suferi încrucișarea.

Orice algoritm genetic trebuie să precizeze în ce măsură indivizii generației P(t) se regăsesc în generația P(t+1) (adică supraviețuiesc nemodificați). Trebuie așadar să indicăm în ce măsură indivizii supraviețuiesc de la o generație la alta.În mod standard se consideră că generația P(t+1) va fi formată din cromozomii nou obținuți plus acei cromozomi ai populației intermediare care nu au fost încrucișați. Numărul de indivizi la fiecare generație rămâne constant și egal cu n.

Altă posibilitate este de a copia nemodificați în P(t+1) un număr fixat de indivizi din P(t). Indivizii copiați vor fi cei mai buni din generația P(t). Indivizii astfel copiați vor putea participa și la selecția pentru recombinare și mutație.

Cosiderații generale privind încrucișarea

Nu există o teorie și nici euristici convingătoare pentru a justifica utilizarea unui operator de încrucișare având un singur punct de tăietură sau mai multe. Alegerea numărului de puncte de tăietură se face pentru fiecare problemă în parte și se bazează pe rezultatele obținute în legătură cu acea problemă.

Operatorii de încrucișare, indiferent de forma lor, au câteva caracteristici care îi fac extrem de utili în procesul de căutare. Discuția de mai jos evidențiază rolul încrucișării în căutare și optimizarea genetică.

a) Prin încrucișare se pot obține decendenți total diferiți de părinții lor. Rezultă că operatorii de încrucișare sunt, într-un grad înalt, responsabili pentru mărirea diversității într-o populație dată.

b) Operatorul de încrucișare este o componentă extrem de importantă a unui algoritm genetic. Dacă eliminăm dintr-un algoritm genetic operatorul de încrucișare, atunci procedura rezultată pierde, în bună măsură, caracterul de algoritm genetic. Este, de regulă, admis că folosirea unui operator de încrucișare distinge algoritmii genetici de ceilalți algoritmi de căutare și optimizare.

c) Într-un algoritm genetic, renunțarea la încrucișare induce, de regulă, o descreștere a performanței.

d) Încrucișarea este considerată o caracteristică esențială a algoritmilor genetici, responsabilă pentru accelerarea în mod semnificativ a procesului de căutare.

e) Mutația, celălalt operator de modificare important, este mai degrabă o metodă pentru a reintroduce diversitatea într-o populație în care, din întâmplare, o poziție are aceeași valoare în toți indivizii.

f) Componenta de căutare de mare performanță este încrucișarea. Ea acționează prin combinarea rapidă a ceea ce este bun în populația inițială.

g) Unele rezultate experimentale evidențiază faptul că importanța probabilității de încrucișare este mai mică decât ne-am putea aștepta.

2.4.3 Mutația

Mutația este cel de-al doilea operator genetic, în ordinea importanței și folosirii sale. Efectul acestui operator este schimbarea valorii unei singure poziții (gene) dintr-un cromozom. Prin mutație se introduc în populație indivizi care nu ar putea fi generați prin alte mecanisme.

Considerăm o reprezentare binară a cromozomilor. În acest caz, efectul operatorului de mutație este complementarea unei singure poziții (bit) din cromozomul asupra căruia operatorul se aplică.

Mutația este un operator de tip probabilistic. Probabilitatea de aplicare a operatorului se numește probabilitate de mutație și se notează cu pm. Probabilitatea de mutație reprezintă un parametru al algoritmului genetic. Valoarea sa este mică (de ordinul 10-3).

Operatorul de mutație acționează asupra biților, indiferent de poziția lor în cromozom. Fiecare bit al populației poate suferi o mutație. Într-un cromozom pot exista așadar mai multe poziții ce suferă o mutație.

Considerăm o populație de n indivizi (cromozomi), fiecare având lungimea r. Fiecare poziție (bit) are aceeași probabilitate pm de a suferi mutația. Cum numărul total de biți în populație este n r, rezultă că numărul mediu de biți ce vor suferi o mutație este:

N = n r pm .

Există variante ale operatorului de mutație. Vom considera mai jos unele dintre aceste variante. În forma tare a operatorului de mutație poziția selectată pentru mutație se schimbă în mod automat. În forma slabă se consideră o anumită probabilitate de schimbare a poziției selectate.

Operatorul de mutație actionează după următorul algoritm:

Mutația tare

Forma tare a operatorului de mutație poate fi descrisă de următorul algoritm:

P1. Pentru fiecare cromozom al populației curente și pentru fiecare poziție a cromozomului se execută:

P1.1. Se generează un număr aleator q în intervalul [0 ,1].

P1.2. Dacă q < pm atunci se execută mutația poziției respective, schimbând 0 în 1 și 1 in 0.

În caz contrar (q pm), poziția respectivă nu se schimbă.

Mutația slabă

Algoritmul de mutație – forma slabă

Există implementări în care condiția q < pm nu atrage automat schimbarea valorii pozitiei considerate. Putem considera un mecanism în care noua valoare a poziției ce îndeplinește condiția de mutație se generează în mod aleator. Valoarea obținută poate să coincidă cu vechea valoare și în acest caz nu are loc nici o schimbare efectivă.

În acest caz pasul P1.2. din varianta precedentă se înlocuiește cu pasul P’1.2.:

P’1.2. Dacă q < pm atunci se alege aleator una din valorile 0 sau 1. Se atribuie poziției curente valoarea astfel selectată.

Dacă q pm atunci poziția curentă nu se schimbă.

Mutația unui singur cromozom

În această variantă, fiecare aplicare a operatorului afectează o genă (sau eventual mai multe) dintr-un singur cromozom (care a fost selectat pentru mutație). Se poate utiliza atât varianta slabă cât și cea tare a operatorului de mutație.

Mutația neuniformă

Se poate considera o probabilitate de mutație care depinde de generație. La primele generații, probabilitatea de mutație poate fi mare, ea descrescând cu indicele t al generației. În felul acesta se asigură schimbări mari în primele etape ale căutării. Această strategie asigură progresul căutării în faza inițială.

Descreșterea probabilității de mutație în fazele avansate ale căutării generează schimbări mai mici, ceea ce asigură o căutare locală mai eficientă. Cu alte cuvinte, în vecinătatea punctului de optim căutarea devine mai fină. Acesta este un exemplu de felul în care prin acțiunea unui singur operator explorarea din fazele inițiale este înlocuită cu exploatarea locală a soluțiilor găsite, spre fazele finale ale căutării.

Putem realiza mecanismul propus admițând că la pasul t probabilitatea de mutație are forma:

pm(t) = pm e(1 – t) ,

unde pm este probabilitatea de mutație la prima generație, iar 1 este un parametru real. Cu cât valoarea lui este mai mare, cu atât mai repede descrește probabilitatea de mutație.

Operatorul descris mai sus poate fi considerat un operator de mutație neuniform, din cauza dependenței sale de vârsta populației.

Mutația neuniformă adaptivă

Modalitatea de codificare binară poate induce o asimetrie in acțiunea operatorului de mutație. Dacă o genă este poziționată la începutul unui cromozom, atunci schimbarea ei provoacă o modificare semnificativă a cromozomului.

Făcând ca probabilitatea de mutație să depindă de poziția în cromozom și de generatie, am putea realiza o căutare globală în primele etape și o căutare locală în ultima parte a procesului iterativ. Pentru aceasta este suficient să facem ca pe masură ce indicele generației crește probabilitatea de mutație a primelor gene în cromozom să descrească, iar cea a ultimelor gene să crească.

Încrucișare versus mutație

Într–un algoritm genetic, operatorului de încrucișare îi revine rolul căutării globale în spațiul problemei. Operatorul de mutație are rolul de a evita o pierdere ireparabilă a diversității. Să presupunem că toți indivizii unei populații au pentru prima genă aceeași valoare. Această valoare nu s-ar putea schimba pentru nici un individ doar prin acțiunea operatorului de încrucișare.

Operatorul de mutație previne așadar o convergență prematură, generând o diversitate suplimentară a indivizilor unei populații. Această diversitate permite explorarea unor zone mai largi din spațiul de căutare.

Unele rezultate experimentale au subliniat importanța operatorului de mutație. Astfel, rezultatele obținute de Shaffer, Caruana, Eshelman si Das (1989), par să indice o perspectivă ușor modificată asupra raportului dintre încrucișare și mutație. Aceste rezultate sugerează că rolul mutației este mai important decât era admis de către specialiști ca rezultat al primelor cercetări strategiile de căutare bazate doar pe selecție și mutație ar putea fi proceduri de căutare puternice, chiar fără considerarea încrucișării.

2.4.4 Operatorul de inversiune

Operatorii genetici considerați inițial (Holland, 1975) au fost încrucișarea, mutația și inversiunea. Implementările curente ale algoritmilor genetici folosesc cu precădere primii doi operatori și foarte rar pe cel de-al treilea.

Operatorul de inversiune actionează asupra unui singur cromozom. El inversează valorile a două poziții ale cromozomului. Cele două poziții se aleg aleator. Operatorul de inversiune a fost inspirat de procese bilogice.

S-a constatat că operatorul de inversiune este de puțin folos în practica algoritmilor genetici. Se admite că acest operator ar fi util dacă am avea cromozomi cu cel puțin un ordin de mărime mai lungi decât se folosesc în implementările curente.

2.5. Algoritmul genetic fundamental (canonic)

Suntem acum în măsură să indicăm mai exact felul în care acționează un algoritm genetic. Operatorii genetici considerați pentru realizarea modificărilor sun încrucișarea și mutația.

Notăm P(0) o populație inițială formată din n indivizi (cromozomi) de lungime r. Varianta de bază a unui algoritm genetic cu încrucișare și mutație este dată mai jos:

P1. Se alege un mecanism de selecție.

Se inițializează populația P(0) în mod aleator și se stabilesc valorile probabilităților de încrucișare (pc) și de mutație (pm).

P2. Se pune t:=0.

P3.Se evaluează cromozomii populației P(t)

Se reține cel mai performant individ din P(t).

P4. Se aplică operatorul de selecție de n ori. Cromozomii selectați formează o populație intermediară P1 (având tot n membri). În P1, unii cromozomi din P(t) pot avea mai multe copii (vor apare de mai multe ori), iar alții nici o copie.

P5. Asupra cromozomilor din populația intermediară P1, se aplică operatorul de încrucișare. Cromozomii nou obținuți formează o populație intermediară P2.

Se șterg din populația intermediară P1 părinții cromozomilor obținuți prin încrucișare.

Cromozomii rămași în P1 devin și ei membri ai populației P2.

P6. Asupra populației P2 se aplică operatorul de mutație. Rezultatul este noua generație P(t+1).

P7. Se pune t:=t+1

Dacă t N, unde N este numărul maxim de generații, atunci se merge la pasul P3.

În caz contrar STOP.

Acest algoritm poate fi ușor modificat pentru a include și operatorul de inversiune sau operatori de alt tip.

Recomandări:

probabilitatea de încrucișare (pc) trebuie să fie ridicată (0.8 – 0.95).

probabilitatea de mutație (pm) trebuie să fie scăzută ( sub 0.01)

volumul populației (N) – deși pare surprinzător un volum mare al populatiei nu îmbunătățește performanța algoritmului genetic. Un volum destul de bun este de 30 – 60.

trebuie folosit elitismul

CAP.3 Strategii evolutive

3.1 Introducere

Strategiile evolutive (“Evolution Strategies”) reprezintă una dintre cele trei mari paradigme ale algoritmilor evolutivi. Punctul de plecare a fost legat de necesitatea de a construi sisteme capabile să rezolve probleme dificile de optimizare și căutare cu parametri reali variabili.

Prima strategie evolutivă a fost dezvoltată la Universitatea Tehnică din Berlin în 1964 de către Rechenberg și Schwefel ca o tehnică experimentală de optimizare. Primele aplicații au fost legate de rezolvarea unor probleme de mecanica fluidelor. Ulterior strategiile evolutive au putut fi extinse pentru a rezolva probleme de optimizare cu parametri discreți.

Strategiilor evolutive le este specifică reprezentarea indivizilor sub forma unor vectori cu componente reale. Operatorul principal este cel de mutație.

În strategiile evolutive avansate reprezentarea indivizilor încorporează și parametrii de control ai strategiei. Acești parametri sunt în principal legați de amplitudinea perturbatiilor generate prin acțiunea operatorului de mutație.

Primul și cel mai simplu model de strategie evolutivă este strategia (1 + 1), în care avem un părinte și un descendent per generație. În această strategie lipsește aspectul de învațare colectivă. Schimbările vizează adaptarea unui singur individ care se schimbă prin acțiunea operatorului de mutație. Mutațiile sunt perturbații normale cu o amplitudine definită, caracterizată de vectorul dispersie . Rata de convergență a strategiei (1 + 1) se studiază în cazul a două funcții model (modelul sferei și modelul coridor). Aceste funcții permit stabilirea unei reguli empirice (regula 1/5 a lui Rechenberg) pentru controlul parametrului dispersie.

Limitele modelulului (1+1) au dus la căutarea unor mecanisme care să implice în evoluție mai mulți indivizi. În strategia ( ), părinți dau naștere unui descendent. Operatorii utilizați sunt cei de recombinare și mutație.

În alte modele ( () și ( ) numărul descendenților este >1. Caracteristica acestor modele este încorporarea parametrilor strategiei în reprezentarea indivizilor. Acest lucru permite ca parametrii strategiei să se poată auto-adapta. Putem considera că suntem în prezența unui proces de învățare cu două nivele: primul nivel corespunde schimbării vectorului de stare ca răspuns la particularitățile locale ale funcției criteriu (suprafeței de căutare). Al doilea nivel corespunde auto-adaptării parametrilor de control asociați strategiei. Schimbarea parametrilor poate fi interpretată ca un reglaj fin al procesului de căutare, fără intervenția unui mecanism de monitorizare a procesului.

3.2 Strategia (1+1)

Strategiile evolutive au debutat cu un model de populație extrem de simplu. În abordarea inițială (Rechenberg, 1973) se consideră o populație formată dintr-un singur individ, reprezentat print-un vector cu componente reale. Dinamica modelului este și ea foarte simplă. Singurul operator genetic utilizat este cel de mutație.

Operatorul de mutație acționează asupra tuturor componentelor vectorului părinte, inducând o mică perturbație a acestora. Se admite că perturbația indusă respectă o lege normală. Această presupunere este în corcondanță cu observațiile biologice care atestă că , în general, descendenții sunt asemănători părinților iar schimbările mici sunt mai frecvente decât variațiile mari.

Se consideră că perturbația aplicată unei componente a vectorului părinte se descrie printr-o variabilă aleatoare normală având media zero. Disipersia este aceeași pentru toți indivizii ce vor fi generați. Așadar dispersia perturbației reprezintă un parametru al algoritmului. Amplitudinea perturbației nu este însă obilgatoriu aceeași pentru toate componentele. Așadar componentele vectorului dispersie nu sunt neaparat egale.

După obținerea prin mutație a unui descendent cei doi membri ai populației sunt comparați prin intermediul unei funcții de adecvare. Va fi selectat cel mai bun dintre cei doi. Individul mai puțin performant va fi șters. Acest mecanism simplu de selecție este desemnat ca selecția (1+1). Este evident că, de fapt, această strategie simplă nu lucrează cu o populație de soluții intermediare.

În mod uzual un individ se reprezintă ca o pereche de v = (x, ). Vectorul x reprezintă un punct din spațiul de căutare, iar este vectorul dispersie. Dacă spațiul de căutare este o submulțime a lui Rn atunci x și sunt vectori cu n componente reale. reprezintă dispersia perturbației pe care o suferă componenta xi a vectorului x.

Prin perturbarea individului vt = (xt , ) se obține un nou individ vt+1 = xt + y, unde y este un număr aleator ce respectă legea normală cu media m = 0 și dispersia .

Legea de evoluție se mai poate scrie și sub forma:

xt+1 = xt + N(0, ), unde N(0, ) denotă realizarea unei variabile aleatoare n-dimensionale ce urmează distribuția normală cu parametrii respectivi.

Strategia evolutivă (1+1) are unele neajunsuri dintre care amintim:

folosește o singură valoare a dispersiei pentru toate componentele vectorului de căutare

nu folosește o populație veritabilă

nu folosește recombinarea

nu realizează o auto-adaptare

Această strategie poate fi ameliorată introducând o populație veritabilă cu mai mult de un individ. Rechenberg (1973) a propus o strategie evolutivă multi-membru în care mai mulți părinți pot participa la generarea unui descendent (strategia ().

3.3 Strategia (+ 1)

Această strategie introduce noțiunea de populatie la nivelul părinților. Ea facilitează dezvoltarea unor strategii mai complicate, cum ar fi strategiile ( + ) și (,). În aceste noi strategii apare și o populație de descendenți.

Deci strategia (1+1) poate fi generalizată prin creșterea dimensiunilor populației. Populatia poate crește prin:

creșterea numărului părinților fiecărui descendent

creșterea numărului descendenților unui părinte

creșterea numărului părinților și descendenților

Strategiile evolutive corespunzătoare s-au numit (, (1+) și respectiv ( + )

Ele pot fi considerate variante ale unei strategii evolutive numite (,).

În strategia evolutivă (, unde > 1, părinții vor genera un singur decendent la un moment. Operatorii utilizați sunt recombinarea si mutația. Prin recombinare se obține un individ asupra căruia acționează apoi operatorul de mutație. Recombinarea asigură creșterea considerabilă a eficienței strategiei evolutive.

Selecția se asigură comparând cei mai neperformanți dintre cei părinți cu descendentul lor. Descendentul îl înlocuiește cu cel mai slab (neperformant) pedecesor, dacă are o adecvare mai bună decât acesta. Cu alte cuvinte din părinți și un descendent sunt selectați în mod determinist indivizi care vor reprezenta următoarea populație de părinți.

Operatorul de recombinare generează, spre deosebire de cazul algorimilor genetici canonici, un singur descendent la o aplicare. Numărul părinților poate fi mai mare decat 2. Să presupunem că numărul părinților este p (1). Operatorul de recombinare selectează, cu o probabilitate uniformă, cei p părinți. Caracteristicile părinților selectați sunt apoi combinate pentru a crea un singur descendent. Dacă p = 1, un singur individ este ales în mod aleator.

3.4 Strategia (1+)

Această strategie consideră un număr de descendenți la fiecare generație. Creșterea numărului de descendenți de la 1 la asigură o creștere considerabilă a vitezei de convergentă per generație.

Strategia folosește cel mai bun descendent ca părinte pentru următoarea generație. Mecanismul de supraviețuire compară acest părinte cu predecesorul său. Supraviețuiește doar cel mai bun dintre cei doi.

Rezultatele teoretice evidențiază faptul că prin creșterea numărului al succesorilor pasul mutației poate crește. Deoarece doar cel mai bun succesor este important, creșterea numărului de eșecuri (descendenți mai puțin performanți decât predecesorii lor) este complet ignorată.

3.5 Strategiile () și ()

În aceste strategii mecanismul de adaptare este transferat indivizilor, care sunt echipați cu o mulțime de parametri de control. Modelul acestui mecanism este unul biologic. Astfel biologii au evidențiat faptul că genotipul încorporează un mecanism ce controlează propria sa mutabilitate, de exemplu prin intermediul unor gene mutatoare.

Strategiile () și () folosesc populații multiple de părinți și descendenți..Creșterea dimensiunii populației determină o mărire a vitezei de convergență.

În strategia (), un număr de >1 părinți sunt folosiți pentru a genera descendenți. ( > ). Toți indivizi ai populației intermediare astfel obținute intră în competiția pentru supraviețuire. Cei mai buni indivizi sunt selectați ca părinți ai noii generații. Probabilitatea de a fi selectați este aceeași pentru toți indivizii.

În cazul strategiei evolutive () numai cei descendenți concurează pentru supraviețuire. Părinții sunt complet înlocuiți la fiecare generație. Urmează ca timpul de viață al unei soluții este limitat la o singură generație. Din acest motiv strategia evolutivă () este potrivită pentru probleme în care funcția obiectiv este afectată de zgomot. O altă situație în care strategia este aplicabilă este existența unui optim care-și schimbă poziția în timp.

Putem considera () si () și drept două tipuri de selecție a unei aceleași strategii. În strategia () cei mai buni descendenti (<) sunt selectați printr-o procedură deterministă pentru a înlocui generația precedentă. Acest mecanism permite ca cel mai bun membru al generației (t+1) să fie inferior celui mai bun individ din generația t. Selecția nu este așadar una etilistă. Acest lucru face ca strategia să tolereze și momente de recul, ceea ce îi permite să părăsească regiunea de atracție a unui minim local și să evolueze spre optimul global.

În contrast strategia () selectând părinți din întreaga populație de părinți și descendenți asigură evoluția monotonă spre soluția optimă. În ciuda acestui avantaj, strategia () are un serios dezavantaj legat de dificultatea adaptării parametrilor. Mecanismul de supraviețuire permite ca parametrii neadaptați ai strategiei să supraviețuiască un număr relativ mare de generații. Strategia eșuează atunci când căutarea se efectuează într-un mediu ce suferă schimbări dinamice. În plus procesul de căutare ghidat de această strategie tinde să favorizeze minimele locale în defavoarea minimelor globale. Din aceste motive strategiile evolutive cele mai des utilizate sunt strategiile ().

3.6 Structura unei strategii evolutive

În strategiile evolutive indivizii (cromozomii) se reprezintă utilizând codificarea reală. În această codificare se utilizează numere reale pentru reprezentarea valorilor genelor. Această reprezentare este potrivită în special pentru rezolvarea unor probleme de optimizare în care variabilele iau valori într-un domeniu continuu.

În codificarea reală fiecare cromozom este reprezentat (codificat) sub forma unui vector cu componente reale. Dimensiunea cromozomilor este constantă și egală cu dimensiunea vectorului soluție (din spațiul stărilor problemei)

Fie x = {x1, x2, x3, …, xi, xn } codificarea unui cromozom. Poziția i din această codificare reprezintă valoarea genei în cromozomul x. În codificarea reală xiR și deci x este din Rn. Fiecare genă corespunde unui parametru de optimizat (unei variabile). Valorile genei i în diverși cromozomi reprezintă valori ale parametrului corespunzător genei. Fiecare parametru (variabilă) ia valori într-un domeniu precizat și operatorii strategiei evolutive trebuie să mențină valorile în domeniul respectiv. Uneori, pentru simplitate, vom identifica o genă cu valoarea ei.

Pentru a crea noi soluții folosind operatorii de încrucișare și mutație este necesar să considerăm noi strategii de căutare. Codificarea reală presupune definirea unor operatori specifici.

În cele ce urmează să presupunem că dorim să aplicăm strategiile evolutive pentru găsirea maximului global al unei funcții reale.

Fie f : X Rn R. Problema este de a găsi elementul din X care maximizează funcția f. Spațiul de căutare este deci X. În mod evident nu se pune problema codificării tuturor elementelor spațiului de căutare. Vom lucra cu populații reprezentând codificarea a n puncte din acest spațiu.

Populația inițială se crează alegând aleator n puncte din multimea X (din spațiul de căutare). Nu există o metodă generală de alegere a mărimii populației. Intuiția ne spune că o populație mare va face ca strategia evolutivă să lucreze mai încet, dar soluțiile vor fi mai bune decât cele obținute cu o populație mai mică. O astfel de regulă euristică nu funcționează întotdeuna. Dimensiunea optimă a populației depinde de problemă, de reprezentarea folosită și de operatorii utilizați. În general doar experimentele numerice vor putea da un răspuns adecvat.

Ca și la algoritmii genetici și aici avem nevoie de o funcție de adecvare. Dacă f are valori poztive atunci putem alege ca funcție de adecvare chiar funcția obiectiv f. În acest caz avem g(x) = f(c), unde c este cromozomul ce reprezintă elementul c X. Această alegere este justificată deoarece se dorește optimizarea funcției criteriu. În plus g satisface axiomele funcției de adecvare:

g(x) 0 , x X

g reflectă calitatea cromozomilor, în sensul optimizării funcției obiectiv

Dacă f nu are valori pozitive atunci funcția de adecvare se poate obține printr-o scalare a lui f.

În cazul unei scalări liniare avem g = , unde coeficienții și se aleg astfel încât să satisfacă cerințele impuse funcției de adecvare.

3.6.1 Selecția

Pentru fiecare generație P(t) se calculează adecvarea cromozomilor generației. Ca mecanism de selecție se poate utiliza modelul ruletei (vezi algoritmii genetici) sau o variantă a sa. Se poate suplimenta acest mecanism cu o abordare etilistă pentru a asigura păstrarea celui mai bun cromozom al fiecărei generații și pentru a depăși erorile legate de alegere. Populația intermediară obținută prin selecție se notează P1.

În selecția etilistă, dacă cel mai bun individ al unei generatii nu a fost selectat, se înlătură în mod aleator un cromozom din populația P1 și se adaugă acestei populații cel mai bun individ din P(t). În cazul în care cel mai bun individ a fost selectat, populația P1 nu se modifică. În unele situații selecția etilistă se aplică primilor cei mai importanti k indivizi din P(t). Numărul k este un parametru al algoritmului.

3.6.2 Recombinarea

Operatorul de încrucișare cu unul sau mai multe puncte de tăietură prezentat la algoritmii este ușor aplicabil. Din păcate, în cazul strategiilor evolutive, în care se folosește codificarea reală, acest operator nu este adecvat. El nu poate realiza căutarea în raport cu fiecare variabilă. Această căutare ar rămâne complet în sarcina operatorului de mutație. Din acest motiv este necesar să reconsiderăm operatorul de recombinare.

În codificarea reală există mai multe posibilități de a redefini operatorul de încrucișare (recombinare). Dăm mai jos cele mai cunoscute variante ale acestui operator.

Recombinarea discretă

În acest tip de recombinare doi părinți generează doi descendenți. Pentru fiecare poziție i a primului descendent se alege (cu o probabilitate fixată p) părintele a cărui genă (din poziția i) va fi transmisă acestui descendent. Poziția respectivă din al doilea descendent va fi completată cu valoarea genei corespunzătoare din celălalt părinte. Dacă p = 0.5 rolul celor doi părinți este simetric.

De exemplu, fie cromozomii:

x = ( x1 x2 x3x4 x5 )

și

y =( y1 y2 y3 y4 x5 )

Încrucișarea discretă cu p = 0.5 poate conduce, de exemplu, la descendenții:

x1 = ( x1 x2 y3x4 y5 )

și

y1 =( y1 y2 x3 y4 x5 )

Recombinarea continuă (medie)

Operatorul de recombinare continuă (numit si operator de recombinare medie) se aplică cu o probabilitate pc (probabilitate de recombinare). Se aleg aleator (cu o probabilitate fixată p) anumite poziții. Genele corespunzătoare în descendenți vor fi media aritmetică a genelor corespunzătoare ale părinților.

Exemplu:

Considerăm cei doi cromozomi din exemplul precedent. Admitem că au fost selectate genele 3 și 5. În aceste condiții, descendenții obținuți prin încrucișare continuă sunt:

x1 = (x1, x2, (x3+ y3) / 2, x4, (x5+ y5)/2 )

și

y1 = (y1, y2, (x3+ y3) / 2, y4, (x5+ y5)/2 )

Este simplu să imaginăm și alte tipuri de încrucișare. Câteva posibilități vor fi prezentate mai jos.

Recombinarea continuă (medie) completă

Acest tip de încrucișare produce un singur descendent ale cărui gene reprezintă media aritmetică a valorilor genelor corespunzătoare din cei doi părinți.

Fiecare genă i a descendentului va avea forma:

zi = ( xi + yi ).

Recombinarea convexă ( sau intermediară)

Este posibilă și o situație mai generală în care cei doi părinți nu au aceeași pondere în obținerea descendentului. În acest caz genele descendentului pot fi date de o combinație convexă a genelor părinților. Gena de pe poziția i a unicului descendent va avea valoarea:

zi = xi + yi ,

unde [0,1] și cei doi parametri satisfac condiția de convexitate .

Dacă si reflectă calitatea (adecvarea) părinților, atunci acest tip de încrucișare favorizează pe cel mai bun părinte.

Putem stabili un mecanism de încrucișare convexă care să conducă la obținerea a doi descendenți. În acest caz cromozomii x si y vor genera descendenții u și v ale căror gene sunt de forma:

ui = xi + (1-) yi

și respectiv

vi = yi + (1-) xi

În acest caz parametrul nu mai poate fi pus în legatură cu performanțele unuia dintre cromozomi. Dacă parametrul este constant pentru toate generațiile avem o încrucișare convexă uniformă.

Putem stabili un mecanism care să permită ca să depindă de generație (de vârsta populației). În acest caz avem un operator de încrucișare convexă neuniformă.

Este posibil să introducem și un element aleator în încrucișarea convexă. În cazul unui singur decendent genele acestuia se vor putea scrie:

zi = xi + (1-) yi , i = 1,2, …, r

unde r este lungimea cromozomilor, iar este un număr aleator din intervalul [0,1].

Dacă avem doi descendenți, valoarea genelor lor vor fi calculate cu formulele:

ui = xi + (1-) yi , i = 1,2, …, r

și respectiv

zi = yi + (1-) xi , i = 1,2, …, r

Numărul poate fi același pentru toate generațiile sau poate fi stabilit pentru fiecare generatie.

Dacă permitem parametrului să-și schimbe valoarea pentru fiecare genă, atunci obținem un tip special de încrucișare. Putem numi încrucișare locală acest nou tip de operator. Este ușor de observat că încrucișarea locală este de fapt o combinație de încrucișare și mutație. În cazul încrucișării locale genele vor fi:

zi = ixi + (1-i) yi , i = 1,2, …, r

pentru cazul unui singur descendent, și

ui = ixi + (1-i) yi , i = 1,2, …, r

ui = iyi + (1-i) xi , i = 1,2, …, r

pentru cazul a doi descendenți, unde [0,1].

Sunt posibile și alte variante de operatori de recombinare. Putem, de exemplu, să combinăm nu doi, ci mai mulți părinți și să construim descendenți ținând cont de calitatea părinților. Folosirea valorilor de adecvare pentru a orienta recombinarea permite accelerarea căutarii.

Se pot utiliza pentru încrucișare mecanisme axate pe exploatarea locală a spațiului de căutare. Astfel de mecanisme se deosebesc de regulile clasice, care sunt bazate, în principal, pe întâmplare. Apare din nou necesitatea stabilirii unui compromis între explorare/exploatare. Putem aprecia că soluția ideală a acestui compromis este dependentă de problemă, o tratare generală fiind dificilă.

3.6.3 Mutație

Aplicarea operatorului de recombinare este urmată de mutație. Considerăm un cromozom ce codifică n parametri (cromozomul conține n gene). Valorile parametrilor sunt exprimate, după cum am mai spus, prin numere reale. Putem considera diferite forme ale operatorului de mutație. În general putem vorbi de operatori de mutație uniformi și de operatori neuniformi. Acțiunea unui operator neuniform depinde de generație (de vârsta populației).

Mutația este un operator de tip probabilistic. Probabilitatea de aplicare a operatorului se numește probabilitate de mutație și se notează cu pm. Probabilitatea de mutație reprezintă un parametru al strategiei evolutive. Valoarea sa este mică (de ordinul 10-3).

Mutația uniformă

Fie x = (x1, x2, x3, …, xn) elementul (cromozomul) selectat pentru mutație conform pm, (probabilitatea de mutatie). Noul cromozom, x1 se obține astfel:

x1 = x + v , (xi1 = xi + vi)

unde v este o variabilă aleatoare uniform repartizată ( v ~ U[-a,a]).

Mutația normală

Fie x = (x1, x2, x3, …, xn) elementul (cromozomul) selectat pentru mutație conform pm, (probabilitatea de mutatie). Noul cromozom, x1 se obține astfel:

x1 = x + v , (xi1 = xi + vi)

unde v este o variabilă aleatoare normală ( v ~ N(0,) ).

Mutația neuniformă (dependentă de generație)

Cea de-a doua variantă a operatorului de mutatie este inspirată de algoritmul Metropolis de stabilire a echilibrului termic și de algoritmul de recoacere simulata (“simulated annealing”). În această variantă genele suferă modificări importante la primele generații. Modificările descresc apoi treptat. Se realizează astfel un progres important al căutarii în faza inițială și un control fin al procesului de căutare în fazele finale ale acestui proces.

La fiecare generație t se generează aleator doi parametri. Primul parametru p, indică natura schimbării: creșterea sau descreșterea valorii unei gene. Valoarea p = 1 indică o creștere a valorii, iar p =-1 indică o descreștere. Al doilea parametru, r, determină amplitudinea schimbării. Parametrul r este un număr aleator în intervalul [0,1], urmând o distribuție uniformă.

Fie x = (x1, x2, x3, …, xn) un cromozom și fie xi gena aleasă pentru mutație. Valoarea nouă xi1 a genei xi este dată de:

xi1 = xi + (xmax – xi)[1 – r ] , daca p = 1

sau

xi1 = xi + (xi – xmin)[1 – r ] , daca p = – 1

unde:

xmin și xmax semnifică marginea inferioară și respectiv marginea superioară a variabilei (parametrului) xi.

T este numărul maxim de generații (sau indicele pentru care generațiile ulterioare nu vor mai suferi mutații)

t reprezintă generația curentă

Cromozomul obținut în urma acțiunii operatorului de mutație va fi:

(x1, x2, x3, …, xi1, …, xn)

Operatorul de mutație descris mai sus realizează la primele generații o explorare uniformă a spațiului stărilor. Pentru ultimele generații, variațiile fiind mici, explorarea devine locală, realizându-se controlul fin al procesului de căutare.

Ne putem imagina și alta mecanisme de mutație. O primă idee este să fie modificate, la un pas, toate pozițiile unui cromozom. Acest mecanism se poate aplica atât pentru mutația uniformă cât și pentru cea neuniformă.

Mutația este operatorul principal în strategiile evolutive.

3.6.4 Algoritmul general al unei strategii evolutive

P1. Se stabilesc parametrii strategiei evolutive (N, pm , pc , , a).

t:= 0;

Se inițializează populația P(t)

P2. Se evaluează indivizii populației P(t), calculând f(x), unde f este funcția de evaluare a problemei.

P3. Repetă

P’(t):=Selecție P(t)

P’’(t): = Recombinare P’(t)

P(t+1) := Mutație P’’(t)

t:=t+1

Până când este satisfăcut un criteriu de oprire

Criteriul de oprire se referă în general la numărul maxim de generații. Procesul evolutiv este oprit după numărul specificat de generații, independent de caracteristicile intrinseci ale ultimei generații (cum ar fi diversitatea populației sau calitatea membrilor ei).

Sunt posibile și alte metode de oprire a căutarii. Astfel căutarea poate înceta la momentul t dacă diversitatea populatiei P(t) a scăzut sub o anumită limită. În acest caz populația a devenit prea uniformă pentru a asigura progresul căutării. Avem totodată și o indicație că ne aflăm în vecinătatea unui optim global. Diversitatea unei populații poate fi măsurată de diferența dintre calitatea celui mai bun și celui mai neperformant individ al populației. Căutarea poate înceta atunci când această diferență scade sub o anumită valoare. O altă metodă termină căutarea dacă îmbunătățirea valorii funcției criteriu după un număr fixat de generații este inferioară unui prag prestabilit.

CAP.4 Descrierea aplicației

4.1 Prezentare generală

În capitolele anterioare am prezentat algoritmii evolutivi, în general, și variante ale acestora: algoritmii genetici și strategiile evolutive.

Aplicația “AE” (“Algoritmi Evolutivi”), atașată acestei lucrări a fost relizată folosind mediul de dezvoltare a aplicațiilor Visual C++ versiunea 6.0. Această aplicație implementează două dintre cele mai cunoscute tipuri de algoritmi evolutivi, și anume, algoritmii genetici și strategiile evolutive.

Opțiunile se pot selecta din meniuri sau apăsând butonul corespunzător de pe bara de instrumente (Toolbar). Fiecare opțiune este însoțită de un text explicativ, afișat în partea de jos a ferestrei aplicației (în StatusBar).

Prezentăm în continuare meniul aplicației:

File – conține următoarele opțiuni:

New – crează un document nou

Exit – închiderea aplicației

View – conține opțiuni referitoare la fereastra aplicației

Toolbar – ascunde sau arată bara de instrumente, după cum opțiunea este selectată sau nu

Status Bar – ascunde sau arată bara de stare, după cum opțiunea este selectată sau nu

Algoritm Genetic – conține două opțiuni:

Selectare Parametri – se selectează parametrii algoritmului genetic

Start – începerea algoritmului genetic

Strategii Evolutive – conține două opțiuni

Selectare Parametri – se selectează parametrii strategiei evolutive

Start – începerea strategiei evolutive

Help – conține informații despre aplicație

Clasa care implementează funcționalitatea algoritmului genetic este clasa CAG. Această clasă conține:

-membri de date:

int **m_pop – pentru indivizii populației (șiruri de întregi de 0 sau 1)

int m_popvolume – volumul populației

int m_n – dimensiunea unui cromozom

int *m_prob – probabilitățile de selecție

int m_t – generația

int m_pc – probailitatea de încrucișare

int m_pm – probabilitatea de mutație

– metode:

CAG(int n , int volume , double pc ,double pm) – constructorul clasei

virtual ~CAG() – destructorul clasei

void Initializare() – inițializeză populația cu șiruri de 0 și 1, in mod aleator

void CalculProb(int **pop , int vol , int dim) – funcție pentru calculul probabilităților de selecție

int Function(int * x , int dim) – funcția obiectiv

void SelectieMonteCarlo() – slecție bazată pe algoritmul ruletei (Monte Carlo)

void SelectieTurnir() – selecție turnir

void IncrucisareOnePoint() – încrucișare cu un singur punct de tăietură

void Incrucisare2Point() – încrucișare cu două puncte de tăietură

void MutatieTare() – implementează algoritmul de mutație tare

void MutatieSlaba() – implementează algoritmul de mutație slabă

void MutatieNeuniforma() – mutație a cărei probabilitate de mutație depinde de timp (de generație)

Clasa care implementează funcționalitatea strategiei evolutive este clasa CSE.Acestă clasă conține:

– date membre:

double **m_pop – pentru indivizii populației (șiruri de numere reale cu componentele dintr-un anumit interval, interval pe care este definită funcția obiectiv)

int m_popvolume – volumul populației

int m_n – dimensiunea cromozomilor (indivizilor) populației

double * m_prob – probabilitățile de selecție

int m_t – generația

m_theBest – cel mai bun individ al unei generații

double m_pc – probabilitatea de încrucișare

double m_pm – probailitatea de mutație

double m_border – capătul intervalului

int m_disc – variabilă folosită pentru a selecta funcția obiectiv

– metode:

CSE(int n,int volume,double pc,double pm , double border, int disc) – constructorul clasei

virtual ~CSE() – destructorul clasei

void Initializare() – inițializează populația cu șiruri de numere reale din intervalul pe care e definită funcția obiectiv, în mod aleator

void CalculProb(double **pop,int vol,int dim,int disc) – calculează probabilitățile de selecție

double f1(double *x,int dim) – una dintre funcțiile de optimizat

double f2(double *x,int dim) – o altă funcție de optimizat

double f3(double *x , int dim)

void CalculTheBest() – determină individul cel mai bun al unei generații

void Elitism() – înlocuiește cel mai slab individ al unei generații cu cel mai bun individ

void SelectieMonteCarlo() – implementează algoritmul Monte Carlo ( algoritmul ruletei) de selecție

void TurnirSelection() – selecție turnir (selecția prin concurs)

void IncrucisareConvexa() – funcție pentru implementarea algoritmului de recombinare convexă (intermediară)

void IncrucisareMedie() – funcție pentru implementarea algoritmului de recombinare medie

double Normal() – funcție pentru generarea unei variabile cu repartiție normală

void MutatieNormala() – funcție care implementează algoritmul de mutație normală

void MutatieUniforma() – funcție care implementează algoritmul de mutație uniformă

4.2 Mod de utilizare

Utilizatorul trebuie să selecteze prima dată, înainte de a selecta optiunea “Start”, opțiunea “Selectare Parametri”, atât în cazul algoritmilor genetici cât și în cazul strategiilor evolutive. În caz contrar, dacă selectează “Start” apare un “message box” care îi sugerează acest lucru:

Dacă selectează opțiunea “Selectare Parametri” din meniul “Algoritm Genetic” apare un “dialog box modal” care arată astfel:

Dacă apoi utilizatorul selectează din meniul “Algoritm Genetic” opțiunea “Start” se vor afișa pe ecran niște matrici cu căsuțe de culori roșu și albastru care arată la prima generație aproximativ astfel (deoarece inițializarea populației se face în mod aleator):

iar la ultima generație ar putea arăta astfel:

unde un cromozom este reprezentat printr-o linie din matrice, pătratele cu roșu înseamnă că gena de respectivă are valoarea 1, iar cele cu albastru arată faptul că gena respectivă are valoarea 0.

Dacă utilizatorul selectează opțiunea “Selectare Parametri” din meniul “Strategii Evolutive” apare un “dialog box modal” care arată astfel:

Dacă apoi utilizatorul selectează din meniul “Algoritm Genetic” opțiunea “Start” se va afișa pe ecran, ceva de genul:

unde punctele cu negru reprezintă populația de căutători.

Bibliografie

Dumitrescu, D.

Algoritmi genetici și Strategii evolutive – aplicații în Inteligența Artficială și în domenii conexe

Mitchell, M.

An Introduction to Genetic Algorithms

Michalewicz, Z., Hinterding, R., Michalewicz, M.

Evolutionary Algorithms

Periaux, V. , Winter,G.

Genetic Algorithms in Engineering and Computer Science