Algoritmi genetici - studiu de caz - optimizarea traficului într-o rețea

1 Istoric

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.

2 Preliminarii

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.

3 Structura unui algoritm genetic

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 :

- cromozomii utilizati au lungime constanta;

- populatia (generatia) P(t+1) de la momentul t+1 se obtine retinand toti descendentii populatiei P(t) si stergand ulterior cromozomii generatiei ulterioare P(t);

- numarul cromozomilor este constant;

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.