Aplicații ale algoritmilor genetici în management - problema comis voiajorului

1. REZUMAT

Un algoritm genetic efectuează operaţii specifice în cadrul unui proces de reproducere guvernat de operatori genetici. Noile soluţii sunt create prin selecţia şi recombinarea cromozomilor existenţi, în vederea optimizării unei funcţii de evaluare specifice fiecărei probleme în parte. Semnificaţia acestei funcţii nu este relevantă pentru algoritm, ceea ce contează fiind numai valoarea sa.

În general se pleacă de la o populaţie de cromozomi generată aleator şi fiecare nouă populaţie generată prin reproducere înlocuieşte parţial sau total generaţia anterioară. Funcţia de evaluare globală se îndreaptă spre optim şi oferă soluţii din ce în ce mai bune problemei. Procesul este analog teoriei neo-darwiniste a evoluţiei biologice, care afirmă că organismele adaptate continuu la schimbările de mediu au şansele cele mai mari de supravieţuire.

Problema analizata in cadrul acestui proiect este problema comis voiajorului, care in cazul de fata consta in determinarea traseului optim de deplasare intre 8 localitati, care trebuie parcurse toate o singura data.

2. INTRODUCERE

2.1. Formulare succinta a problemei

Problema comis voiajorului prezinta un caz classic de optimizare in cadrul caruia presupunem acesta are de parcurs un anumit numar de orase, destinatia finala si punctul initial de plecare fiind cunoscute. Pentru a avea costuri de transport cat mai mici, el nu trebuie sa treaca de 2 ori prin acelasi oras, sis a parcurga cel mai scurt traseu care sa le include pe toate.

2.2. Importanta practica

Sub acest nume este cunoscută o problemă, semnificativă, prin care ne propunem să

determinăm un drum de cost minim într-un graf. Formularea acesteia se face prin referire la

următoarea situaţie practică:

Se presupune că un comis-voiajor trebuie să viziteze un număr de n oraşe, pornind

din oraşul A şi având ca destinaţie finală oraşul B. Deplasarea între oricare două

oraşe este condiţionată de un anumit cost. Se cere să se determine traseul optim,

adică acel traseu care parcurge toate oraşele, costul total al deplasării fiind minim.

Pentru început, vom observa că numărul total de trasee este egal cu n! ceea ce face ca

determinarea traseului optim, printr-o metodă exhaustivă, să fie imposibilă, chiar pentru valori

modeste ale lui n.

Problema poate fi modelată în conformitate cu principiile genetice, deja expuse.

2.3. Inventarierea tipurilor de metode proiectate pentru rezolvarea acestei probleme

Pentru modelare se utilizeaza tehnici genetice. Obiectele identificate în proiectarea aplicatiei sunt: Această problemă poate fi rezolvată cu ajutorul algoritmilor genetici, folosind sau nu diferite limbaje de programare (Delphi, C++, MatLab, etc), prin programare liniara, backtraking sau prin metode euristice de tip Greedy.

În continuare, metoda aleasă este cea a algoritmilor genetici. Ulterior, aceasta rezolvare poate fi codată şi introdusă în limbajele de programare menţionate.

2.4. Raport tehnic (asupra metodei descrise anterior)

Structura unui algoritm genetic

2.5. Formularea problemei – model matematic

Un comis voiajor trebuie sa parcurga un numar de 8 orase, reprezentate printr-un graf neorientat, avand distante variabile intre varfuri (orase). Fiecare oras trebuie parcurs o singura data.

In cadrul aceste probleme avem In problema data avem 8!=1*2*3*4*5*6*7*8 =40320 solutii posibile.

Distantele dintre orase sunt prezentate sub forma unui tabel, cu precizarea ca distanta de la A la B nu este neaparat egala cu distanta de parcurs de la B la A.