Rezolvarea problemei comis-voiajorului cu ajutorul algoritmilor genetici

Rezolvarea problemei comis-voiajorului cu ajutorul algoritmilor genetici

ALGORITMI GENETICI

Algoritmii genetici sunt tehnici adaptive de cautare euristica, bazate pe principiile geneticii si ale selectiei naturale, enuntate de Darwin (supravietuieste cel mai bine adaptat). Mecanismul este similar procesului biologic al evolutiei. Acest proces poseda o trasatura prin care numai speciile care se adapteaza mai bine la mediu sunt capabile sa supravietuiasca si sa evolueze peste generatii, in timp ce acelea mai putin adaptate nu reusesc sa supravietuiasca si cu timpul dispar, ca urmare a selectiei naturale. Probabilitatea ca specia sa supravietuiasca si sa evolueze peste generatii devine cu atat mai mare cu cat gradul de adaptare creste, ceea ce in termeni de optimizare inseamna ca solutia se apropie de optim.

Un algoritm genetic este un model informatic care emuleaza modelul biologic evolutionist pentru a rezolva probleme de optimizare ori cautare. Acesta cuprinde un set de elemente individuale reprezentate sub forma unor siruri binare (populatia) si un set de operatori de natura biologica definiti asupra populatiei. Cu ajutorul operatorilor, algoritmii genetici manipuleaza cele mai promitatoare siruri, evaluate conform unei functii obiectiv, cautand solutii mai bune. Algoritmii genetici au inceput sa fie recunoscuti ca si tehnici de optimizare odata cu lucrarile lui John Holland

Opereaza pe o populatie de solutii potentiale aplicand principiul supravietuirii celui mai bun (teoria evolutionista Darwin) pentru a produce aproximari din ce in ce mai bune ale solutiei.

In fiecare generatie este creat un nou set de indivizi (aproximatori, cautatori) in urma selectiei celor mai adecvati indivizi si combinarea acestora pentru a da nastere la noi indivizi utilizand operatori imprumutati din genetica. Are loc evolutia populatiei de indivizi care astfel devin mai adecvati (potriviti) mediului decat indivizii din care au fost creati, similar cu adaptarea naturala. Sunt modelate procese naturale: selectie, recombinare, mutatie.

ETAPE

Populatia initiala

Trebuie sa fie destul de mare pentru a putea fi realizate un numar suficient de operatii de

incrucisare insa nu prea mare pentru a nu incetini algoritmul.

Poate fi generata:

• Aleator
• Folosind un algoritm simplu (euristic) care construieste cateva solutii (non optime)

Fitness-ul unui cromozom

Fitness-ul reprezinta speranta de viata a unui cromozom. Cu cat fitness-ul este mai mare, cu atat adaptarea cromozomului la conditiile de viata este mai puternica si cromozomul va avea mai multe sanse sa se reproduca avand urmasi in noua populatie.

Cromozomii cu fitness slab vor pieri pe parcurs. Scopul este de a obtine cromozomi cu fitness ridicat.

Crossover: selectia parintilor

Operatia crossover presupune combinarea genelor a 2 parinti pentru crearea de urmasi in noua populatie.

Darwin -> cei mai buni parinti supravietuiesc si se inmultesc pentru a crea noi urmasi.

Selectia poate fi:

• aleatoare (nu tine cont de fitness, performante slabe)
• rezultata aplicand metoda ruletei: cu cat fitness-ul unui cromozom este mai mare, cu

atat este mai mare sansa de a fi ales.

Mutatia

Mutatia apare pentru a evita situatii de blocaj intr-un optim local. Daca apare prea des se ajunge la o cautare aleatoare in spatiul solutiilor (probabilitatea de mutatie trebuie sa fie mica ex: 0.5%).

STUCTURA UNUI ALGORITM GENETIC

De regula lucram cu indivizi cu un singur cromozom. Scopul este de a evolua (spre solutie) o multime de cromozomi numita populatie (fiecare cromozom reprezinta o solutie pentru problema de rezolvat). Principiul evolutionist "noua populatie va fi mai buna decat cea veche".

Noua populatie este obtinuta din cea veche prin:

• Selectia unor parinti care se vor reproduce
• Crearea de urmasi (operatia crossover)
• Aparitia mutatiei (mutation)

Operatia de crossover consta in desfacerea a 2 cromozomi si combinarea partilor rezultate pentru a forma alti doi cromozomi ce vor fi inclusi in noua populatie.

Mutatia modifica un cromozom din noua populatie, alterandu-i una sau mai multe gene.

Fiecare cromozom are o speranta de viata (fitness) care codifica sansa sa de a supravietui in

noua populatie. Un cromozom cu un fitness mai mare va avea mai multe sanse de a se regasi in noua populatie, respectiv de a fi ales pentru operatia de crossover.

Algoritmul genereaza continuu populatii noi pana cand este indeplinita o conditie de oprire:

• ne-am apropiat suficient de mult de solutia dorita
• am parcurs un anumit numar de pasi
• Atingerea unei anumite performante
• Ajungerea la un anumit numar maxim de generatii
• Ajungerea la un nivel foarte mic de diversitate in populatie
• Atingerea unui anumit numar de generatii fara sa se mai fi castigat performanta.

COMPONENTE

Pentru ca o anumita problema sa poata fi rezolvata cu ajutorul unui algoritm genetic, trebuiesc definite:

modalitate de a reprezenta solutiile sub forma genetica (cromozomi)

modalitate de generare a populatiei initiale de solutii potentiale

functia de evaluare fitness

operatorii genetici

valorile parametrilor algoritmului genetic (dimensiunea populatiei,probabilitatile de aplicare a operatorilor - crossover&mutatie, durata evolutiei)

criteriul de oprire (ne-am apropiat suficient de mult de solutia dorita, am parcurs un anumit numar de pasi

SOLUTIA PROBLEMEI

Pentru a evalua o solutie potentiala se foloseste o functie obiectiva (fitness) care joaca rolul mediului.

Algoritmii genetici reprezinta o tehnica de explorare a spatiului solutiilor dirijata dupa

principiile evolutiei naturale:

• mostenirea genetica (cunostintele pe care o specie le-a dobandit la un moment dat sunt transmise urmasilor)
• lupta pentru supravietuire(fiecare specie cauta sa se adapteze la conditiile de mediu)
  
  

Solutia evolueaza catre raspunsul corect urmand reguli bazate pe concepte evolutioniste:

• supravietuirea celor mai puternici
• adaptarea la mediu
• evolutia speciei

PROBLEMA COMIS-VOIAJORULUI

Comis-voiajorul trebuie sa viziteze n orase si incearca sa gaseasca drumul cel mai scurt trecand prin fiecare oras o singura data si revenind la punctul de plecare. Problema are echivalentul matematic de gasire intr-un graf a unui circiut hamiltonian de cost minim.

Pentru calatoria intre doua orase exista un cost reprezentat printr-un numar intreg. Comis-voiajorul trebuie sa parcurga un ciclu al carui cost total sa fie minim.

PCV SI AG

PCV este o binecunoscuta problema NP-completa. O problema NP-completa nu poate fi rezolvata intr-un timp rezonabil, decat prin folosirea unor algoritmi nedeterministi. Problema a fost rezolvata folosind algoritmi evolutivi (AG, strategii evolutive    sau preogramare evolutiva), iar solutiile obtinute depasesc in cel mai rau caz cu 7% lungimea drumului optim.

Specificul problemei a dus la crearea unor noi modalitati de reprezentare a cromozomilor si a aoperatorilor de incrucisare. Cele n orase se numeroteaza intr-o anumita ordine folosind primele n numere naturale. Un cromozom, sau o solutie a problemei, reprezinta un drum inchis ce trece prin toate orasele date.

PCV CU AJUTORUL AG

Reprezentarea unei solutii:

• reprezentare printr-un vector de numere intregi: o lista ordonata de orase care vor fi vizitate (o permutare)

Initializarea populatiei:

• utilizarea unor algoritmi euristici, de exemplu greedy pentru a genera cativa indivizi
• generarea unui numar aleator de permutari, egal cu dimensiunea populatiei

Functia de evaluare

lungimea drumului; obiectivul este de a micsora distanta

OPERATORI

Selectia

• Selectia pentru reproducere (selectia parintilor), cand sunt alesi parintii generatiei urmatoare; are rolul de a alege, in functie de calitatea indivizilor din populatia curenta, care sunt cei considerati, pentru a li se aplica operatori de variatie asupra lor, in vederea obtinerii de noi solutii candidat. indivizii foarte performanti au sanse bune de a fi selectati pentru reproducere, celilalti au sanse mici sa devina parinti.
• Selectia pentru inlocuire (selectia pentru supravietuire), care apare cand indivizii care vor forma populatia din urmatoarea generatie sunt alesi dintre descendentii obtinuti si indivizii din populatia curenta. decide care indivizi din populatia curenta impreuna cu

descendentii obtinuti sunt opriti pentru a forma populatia generatiei urmatoare.

Mutatia

Actioneaza asupra unui individ si produce un altul. Dupa ce se aplica asupra unui individ, rezultatul (descendent) contine mici modificari fata de individul initial. Operatorul face ca toate valorile unei gene sa fie disponibile pentru procesul de cautare. Genele ale caror valori sunt considerate pentru a fi schimbate sunt alese printr-o maniera probabilista.

In PCV Mutatia este o mica variatie intr-o permutare.

Modul in care creste calitatea generala a solutiilor depinde de ambele tipuri de selectie.

Incrucisarea

Incrucisarea implica doi sau mai multi indivizi (parinti) alesi cu o anumita probabilitate de incrucisare in scopul de a genera unul, doi sau mai multi indivizi prin combinarea genelor parintilor.