ALTE DOCUMENTE
|
|||||||
Algoritmi Genetici
(Studiu de caz: Optimizarea traficului intr-o retea
Inceputurile algoritmilor geneticise situeaza undeva in jurul anului 1950, cand mai multi biologi au folosit calculatoarele pentru simularea sistemelor biologice. Rezultatele muncii au inceput sa apara dupa 1960, cand la Universitatea din Michigan, sub directa indrumare a lui John Holland, algoritmii genetici au aparut in forma in care sunt cunoscuti astazi.
Dupa cum sugereaza si numele, algoritmii genetici folosesc principii din genetica naturala. Cateva principii fundamentale ale geneticii sunt imprumutate si folosite artificial pentru a construi algoritmi de cautare care sunt robusti si cer informatii minime despre problema.
Algoritmii genetici au fost inventati folosind modelul procesului de adaptare. Ei opereaza, in principal, cu siruri binare si folosesc un operator de incrucisare si un operator de mutatie.
Mare parte din teoria algoritmilor genetici se aplica in principal modelului introdus de Holland sau a unor variante denumite algoritmi genetici canonici. Progresele teoretice recente in modelarea algoritmilor genetici se refera, de asemenea, la algoritmul genetic canonic (Vose, 1993). Notiunea generala de algoritm genetic este cea prezentata mai sus (model bazat pe ideea de populatie si care foloseste operatori de selectie si recombinare pentru a genera noi puncte intr-un spatiu de cautare); multe modele bazate pe algoritmi genetici au fost introduse de cercetatori dintr-o perspectiva experimentala. Multi astfel de cercetatori sunt orientati spre aplicatii, fiind interesati de algoritmii genetici doar ca mijloace de optimizare.
Algoritmii genetici sunt o familie de modele computationale inspirate de teoria evolutiei. Acesti algoritmi codifica solutiile posibile ale unor probleme specifice intr-o structura de tip cromozom si aplica acestor structuri operatori de recombinare si mutatie pentru a pastra informatia utila. Desi algoritmii genetici sunt priviti deseori ca optimizand functii, domeniul de probleme la care au fost aplicati este destul de larg.
Implementarea unui algoritm genetic incepe cu o populatie de cromozomi (in general aleasa aleator). Se evalueaza apoi, aceste structuri si se aloca facilitati reproductive astfel incat acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta sa aiba mai multe sanse de a se reproduce decat acei cromozomi care sunt solutii mai proaste. Definirea unei solutii bune se face, in general, in raport cu populatia curenta.
Algoritmii genetici sunt algoritmi de tip evolutiv.
Structura generala a unui algoritm de tip evolutiv este :
t=0
creare P(t)
evaluare P(t)
cat timp nu (conditia de terminare)
t=t+1
selectare P(t) din P(t-1)
modificare P(t)
evaluare P(t)
sfarsit cat timp
Tinand cont de structura unui algoritm evolutiv se poate descrie structura unui algoritm genetic, tinand cont de urmatoarele aspecte :
Algoritmii genetici mentin o populatie P(t) de indivizi la fiecare iteratie t. O populatie poate fi privita ca fiind un vector de valori. Fiecare individ (element al vectorului) reprezinta solutia potentiala a problemei si este implementata sub forma unei structuri S. Un individ este numit uneori si cromozom.
Structura algoritmului genetic fundamental este :
Pasul 1. t=0;
Pasul 2. se initializeaza aleator populatia P(t);
Pasul 3. se evalueaza cromozomii populatiei P(t); in acest scop se utilizeaza o functie de performanta ce depinde de problema;
Pasul cat timp nu este indeplinita conditia de terminare se executa pasii urmatori :
Pasul 1 se selecteaza cromozomii din P(t) care vor contribui la formarea noii generatii; fie P1 multimea cromozomilor selectati (P1 reprezinta o populatie intermediara);
Pasul 2 se aplica cromozomilor din P1 operatorii genetici : cei mai utilizati sunt operatorii de incrucisare si mutare. In functie de problema se pot alege si alti operatori. Fie P2 populatia alstfel obtinuta (descendentii populatiei P(t)). Se sterg din P1 parintii descendentilor obtinuti. Cromozomii ramasi in P1 sunt inclusi in populatia P2.
Se construieste noua generatie astfel P(t+1)=P2.
Se sterg toti cromozomii din P(t).
t=t+1;
Se evalueaza P(t).
Conditia de terminare se refera, de regula, la atingerea numarului de generatii.
Daca numarul maxim admis de generatii este N, atunci conditia de terminare este t>N.
Rezultatul algoritmului este de regula cel mai promitator individ din ultima generatie. Deoarece, in realitate, nimic nu garanteaza faptul ca un individ mai performant nu a fost obtinut intr-o generatie anterioara, este normal ca la fiecare pas (la fiecare generatie t) sa retinem cel mai promitator element care a fost generat pana la momentul curent. Acest proces se numeste elitism.
Un rol important in cadrul unui algoritm genetic il ocupa operatorul de selectie. Acest operator decide care dintre indivizii unei populatii vor putea participa la formarea populatiei urmatoare. Scopul selectiei este de a asigura mai multe sanse de reproducere celor mai performanti indivizi dintr-o populatie data. Prin selectie se urmareste maximizarea performantei indivizilor. In continuare voi prezenta succint cele mai importante mecanisme de selectie care au fost implementate in proiect.
Selectia prin ordonare
Aceasta modalitate de selectie consta in a calcula (pentru fiecare generatie) valorile functiei fitness si de a aranja indivizii in ordinea descrescatoare a acestor valori. Se va atribui fiecarui individ i o probabilitate de selectie pi care depinde de rangul sau in sirul stabilit. Probabilitatile depind acum doar de pozitia cromozomului. Cel mai promitator individ (cromozomul avand cel mai bun fitness) are probabilitatea 1.
Selectia prin confruntare
Aceasta modalitate de selectie se bazeaza pe compararea directa a cate doi cromozomi si selectarea celui mai performant. Operatiile implicate sunt urmatoarele : se aleg in mod aleator doi cromozomi, se calculeaza performantele cromozomilor selectati. Cromozomul cel mai performant este selectat (copiat in populatia intermediara asupra careia se aplica operatorii genetici).
Alte mecanisme de selectie
Un alt tip de selectie este selectia elitista. In acest caz, la fiecare generatie se pastreaza cel mai promitator sau cei mai promitatori indivizi. O alta idee ar fi ca, la fiecare generatie, sa fie inlocuita doar o parte restransa a populatiei.
Operatorul de reproducere
Rolul operatorului de reproducere este de a mentine solutiile promitatoare din populatie si de a le elimina pe cele mai putin promitatoare, pastrand constanta dimensiunea populatiei.
Aceasta se realizeaza astfel : se identifica solutiile promitatoare din populatie, se creaza mai multe copii ale solutiilor promitatoare, se limina solutiile mai putin promitatoare din populatie astfel incat multiplele copii ale solutiilor promitatoare sa poata fi plasate in solutie.
Exista mai multe moduri de a realiza acest lucru. Cele mai uzuale metode sunt selectia prin ordonare si selectia prin confruntare.
Operatorul de incrucisare este aplicat asupra indivizilor din populatia intermediara Operatorul de incrucisare actioneaza in felul urmator : sunt alesi aleator doi indivizi din populatia intermediara (care se mai numeste piscina de incrucisare) si anumite portiuni din cei doi indivizi sunt interschimbate. Operatorul imita incrucisarea intercromozomiala naturala. De regula se utilizeaza operatori de incrucisare de tipul (2 ), adica doi parinti dau nastere la doi descendenti. Incrucisarea realizeaza un schimb de informatie intre cei doi parinti. Descendentii obtinuti prin incrucisare vor avea caracteristici ale ambilor parinti. Data fiind importanta majora a incrucisarii, au fost propuse mai multe metode de incrucisare. Voi enumera aici cateva din cele mai utilizate atunci cand se foloseste codificarea binara.
Incrucisarea cu un punct de taietura
Fie r lungimea cromozomilor. Un punct de taietura estre un numar intreg 1<=k<=r-1. Numarul k indica pozitia din interiorul cromozomului unde secventa cromozomiala se rupe pentru ca segmentele obtinute sa se recombine cu alte segmente provenite de la alti cromozomi.
Consideram doi cromozomi
x=x1x2 xkxk+1 xr
y=y1y2 ykyk+1 yr
In urma recombinarii se schimba intre cei doi cromozomi secventele aflate in dreapta punctului de taietura k.
Cromozomii vor fi :
x'=x1x2 xkyk+1 yr
y'=y1y2 ykxk+1 xr
Incrucisarea cu mai multe puncte de taietura
In cazul utilizarii mai multor puncte de taietura, segmentele obtinute se combina dupa o regula data. Consideram incrucisarea cu doua puncte de taietura.
Acest tip de incrucisare se realizeaza conform schemei de mai jos.
Din cromozomii :
|
|
x
|
|
y
vor rezulta doi descendenti de tipul :
x
y
Figura 11
In cazul a trei puncte de taietura, descendentii vor fi de forma :
x'
y
Figura 12
Incrucisarea nu genereaza descendenti aleatori. Desi este improbabil ca fiecare incrucisarea intre doua solutii din populatie sa genereze solutii fii mai promitatoare decat solutiile parinte, totusi in scurt timp devine clar ca sansa de a crea solutii mai promitatoare este mai mare decat in cazul cautarii aleatoare. Din incrucisarea cu un singur punct de taietura a unui perechi de siruri binare, se pot crea doar doua siruri pereche diferite care vor avea in compinenta biti combinati din ambii parinti; solutiile fiu create sunt probabil, siruri cel putin la fel de promitatoare. Prin urmare, nu fiecare incrucisare poate crea solutii la fel de promitatoare, dar nu vor fi mai putin promitatoare decat parintii. Daca a fost obtinuta o solutie mai putin promitatoare, atunci aceasta nu va mai aparea c6and se va aplica urmatorul operator de reproducere si astfel el va avea o viata scurta. Daca este creata o solutie mai promitatoare, atunci este probabil ca ea sa aiba mai multe copii la urmatoarea aplicare a operatorului de reproducere. Pentru a pastra o astfel de selectie a sirurilor promitatoare in timpul aplicarii operatorului de reproducere, nu toate sirurile din populatie sunt folosite pentru incrucisare.
Operatorul de incrucisare este in principal responsabil cu aspectul de cautare al algoritmilor genetici, in timp ce operatorul de mutatie este folosit in alte scopuri. Mutatia este cel de-al doilea operator genetic in ordinea importantei si folosirii sale. Efectul acestui operator este schimbarea valorii unei singure pozitii dintr-un cromozom. Prin mutatie se introduc in populatie indivizi care nu ar fi putut fi obtinuti prin alte mecanisme.
Operatorul de mutatie actioneaza asupra bitilor indiferent de pozitia lor in cromozom. Fiecare bit al cromozomului poate suferi o mutatie. Intr-un cromozom pot exista asadar mai multe pozitii care sufera o mutatie.
Mutatia este un operator probabilist (adica nu se aplica cu siguranta). Consideram o populatie de n indivizi (cromozomi), fiecare avand lungimea r. Fiecare bit are aceeasi propabilitate pm de a suferi mutatia.
Exista mai multe variante ale operatorului de mutatie. Una dintre ele ar fi mutatia in forma tare. In aceasta situatie se procedeaza in modul urmator : se genereaza un numar aleator in intervalul [0,1). Daca q<pm, atunci se executa mutatia pozitiei respective schimbiband 0 in 1 si 1 in 0. In caz contrar, pozitia respectiva nu se schimba.
In concluzie, operatorul de reproducere selecteaza cele mai promitatoare siruri, operatorul de incrucisarecombina subsiruri promitatoare pentru a forma siruri mai promitatoare, iar operatorul de mutatie schimba sirurile local, de asemenea, pentru a imbunatati situatia.
La inceput trebuie stabilit:
Modul de configurare. Se specifica modul in care fiecarei configuratii din spatiul de cautare i se asociaza un cromozom
Functia de adecvare. Se construieste functia care exprima gradul de adecvare la mediu
Dimensiune si modul de initializare a populatiei. Populatiile pot avea dimensiune fixa(standard) sau variabila(hibrid).
Mecanismul de selectie a parintilor si supravietuitorilor.
Mecanismul de incrucisare a parintilor pentru a genera urmasi.
Mecanismul de mutatie care asigura perturbarea elementelor.
Supravietuirea determina in ce masura cromozomii unei generatii supravietuesc in urmatoarea.
Criteriul de oprire. Cand nu se cunoaste un criteriu se opteaza pentru numar maxim de iteratii. Se pot folosi informatii despre populatie (ex: gradul de diversitate).
Modul de configurare
Structuri de date folosite. In algoritmii genetici cromozomii sunt reprezentati prin structuri liniare cu numar fix(tablouri) sau cu numar variabil (liste inlantuite).
Reguli de codificare:
1. Codificare binara (cromozomii sunt vectori cu valori )
2.Codificare reala (vectori cu elemente reale).
Decodificarea este necesara pentru (1).
Pregateste evaluarea configurarii
using System;
using System.Collections;
using System.Windows.Forms;
namespace AlgGen
public void Afiseaza()
System.Diagnostics.Trace.WriteLine('');
}
}
public void CitesteDate()
catch
string line='';
char[] splitter = new char[1];
splitter[0] = ',';
bool isFirstLine = true;
while((line=sr.ReadLine())!=null)
isFirstLine = false;
}
else
populatie.Add(cromozom);
}
}
}
}
public void AlgGen()
if(!Valid(d2prim))
Evaluare(r1,r2,d1,d2,d1prim,d2prim);
}
}
else
foreach(int i in d2)
Evaluare(r1,r2,d1,d2,d1prim,d2prim);
}
}
}
public void Evaluare(int poz1, int poz2, ArrayList d1, ArrayList d2, ArrayList d1prim, ArrayList d2prim)
if(d2prim!=null)
int[,] matrix = new int[4,2];
matrix[0,0] = sd1;
matrix[0,1] = 1;
matrix[1,0] = sd2;
matrix[1,1] = 2;
matrix[2,0] = sd1p;
matrix[2,1] = 3;
matrix[3,0] = sd2p;
matrix[3,1] = 4;
Sort(ref matrix);
int i1 = matrix[0,1];
int i2 = matrix[1,1];
switch(i1)
switch(i2)
}
public void Sort(ref int[,] matrix)
}
}
}
public int Total(ArrayList cromozom)
}
return suma;
}
public int Mutatie ( int i )
public void Incrucisare (ArrayList d1, ArrayList d2, out ArrayList d1prim, out ArrayList d2prim)
for(int i = k; i<dimensiune;i++)
}
public bool Valid ( ArrayList cromozom )
}
if(valid)
}
return false;
}
}
}
|
