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

Cuprins referat Cum descarc?

1. Rezumat
2. Introducere
2.1. Formulare succinta a problemei 
2.2. Importanta practica
2.3. Inventarierea tipurilor de metode proiectate pentru rezolvarea acestei probleme 
2.4. Raport tehnic (asupra metodei descrise anterior) 
2.5. Formularea problemei, model matematic 
2.6. Justificarea pentru alegerea metodei ce va fi analizata in continuare
3. Descrierea componentelor metodei 
4. Exemplu numeric
5. Seturi de date de test provenind din instante practice, reale ale problemei 
6. Concluzii si sfaturi practice 
7. REFERINTE BIBLIOGRAFICE

Extras din referat Cum descarc?

1. REZUMAT
Un algoritm genetic efectueaza operatii specifice in cadrul unui proces de reproducere guvernat de operatori genetici. Noile solutii sunt create prin selectia si recombinarea cromozomilor existenti, in vederea optimizarii unei functii de evaluare specifice fiecarei probleme in parte. Semnificatia acestei functii nu este relevanta pentru algoritm, ceea ce conteaza fiind numai valoarea sa. 
In general se pleaca de la o populatie de cromozomi generata aleator si fiecare noua populatie generata prin reproducere inlocuieste partial sau total generatia anterioara. Functia de evaluare globala se indreapta spre optim si ofera solutii din ce in ce mai bune problemei. Procesul este analog teoriei neo-darwiniste a evolutiei biologice, care afirma ca organismele adaptate continuu la schimbarile de mediu au sansele cele mai mari de supravietuire.
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 cunoscuta o problema, semnificativa, prin care ne propunem sa
determinam un drum de cost minim intr-un graf. Formularea acesteia se face prin referire la
urmatoarea situatie practica:
Se presupune ca un comis-voiajor trebuie sa viziteze un numar de n orase, pornind
din orasul A si avand ca destinatie finala orasul B. Deplasarea intre oricare doua
orase este conditionata de un anumit cost. Se cere sa se determine traseul optim,
adica acel traseu care parcurge toate orasele, costul total al deplasarii fiind minim.
Pentru inceput, vom observa ca numarul total de trasee este egal cu n! ceea ce face ca
determinarea traseului optim, printr-o metoda exhaustiva, sa fie imposibila, chiar pentru valori
modeste ale lui n.
Problema poate fi modelata in 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 in proiectarea aplicatiei sunt: Aceasta problema poate fi rezolvata 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.
In continuare, metoda aleasa este cea a algoritmilor genetici. Ulterior, aceasta rezolvare poate fi codata si introdusa in limbajele de programare mentionate. 
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.

Fisiere in arhiva (1):

 Aplicatii ale Algoritmilor Genetici in Management - Problema Comis Voiajorului.doc