Problema Comisului Voiajor

Scaiceanu Luiza Carmen

Universitatea din Craiova, Facultatea de Matematica si Siinte ale Naturii

Abstract

Charles Darwin a afirmat teoria evolutiei naturale n originea speciilor. De-a lungul generatiilor, organ-ismele biologice evolueaza pe principiul selectiei naturale - "supravietuirea celui mai adaptat". Formeleperfecte de albatros, similitudinea dintre rechini si delfini si asa mai departe, sunt cele mai bune exemplede realizare a evolutiei aleatoare peste inteligenta. Asadar, aceasta functioneaza att de bine n natura,de aceea ar trebui sa fie interesant efectuarea simularii evolutiei naturale si dezvoltarea unei metode, carerezolva concret, si cauta probleme de optimizare. n natura, individual, ct si ntr-o populatie, indiviziiconcureaza unii cu altii pentru resurse vitale, cum ar fi hrana, adapost si asa mai departe. De asemenea,la aceeasi specie, indivizii concureaza pentru a atrage parteneri pentru reproducere. Datorita aceasteiselectii, indivizii ce au performante slabe au mai putine sanse de a supravietui, si cel mai adaptat sau"potrivit" individ produce un numar relativ mare de urmasi. Se poate, de asemenea, remarca faptulca n timpul reproducerii, o recombinare a caracteristicilor bune ale fiecarui stramos poate produce "celmai bun" descendent, ale carui caracteristici sunt mai bune dect cele ale unui parinte. Dupa ctevageneratii, speciile evolueaza n mod spontan pentru a deveni mult mai mult adaptate la mediul lor.

n algoritmii genetici, indivizii reprezintanumerele binare dintr-o multime de sim-boluri extrasa dintr-o multime finita. Asacum memoria calculatorului este facuta dinsiruri de biti, orice poate fi stocat n calcula-tor si poate fi codificat printr-un sir de biti deo lungime suficienta. Fiecare individ codificatdin populatie poate fi vazut ca o reprezentaren concordanta cu o codare corespunzatoare aunei situatii particulare a problemei. Pentru caalgoritmii genetici sa gaseasca solutia optimaeste necesar sa se efectueze anumite operatiiasupra acestor indivizi.

Procesul de cautare nseamna initializareapopulatiei si apoi nmultirea populatiei pen-tru a obtine noi indivizi pna cnd conditiade finalizare este ndeplinita. Pot exista ctevateluri pentru procesul de cautare, unul putndfi de a gasi optimul global. Acest lucru nupoate fi niciodata asigurat, datorita modelelor

cu care algoritmul genetic lucreaza. Existaposibilitatea ca urmatoarea iteratie din cautaresa produca o solutie mai buna. n anumitecazuri, procesul de cautare ar putea sa durezeani de zile, si sa nu produca nicio solutie maibuna dect cea furnizata n prima iteratie maimica. Un alt tel este convergenta rapida. Cndfunctia obiectiva necesita multe resurse pen-tru a functiona, convergenta rapida este depreferat a fi folosita, nsa sansa de a convergela un local si este posibil ca optima de substandard sa creasca.

n afara de acestea, mai exista un tel sianume acela, de a produce un spectru divers,dar n acelasi timp si solutii optime. Cndspatiul solutiei contine cteva optime dis-tincte, care sunt similare n fitness, este folos-itor sa existe posibilitatea de a selecta unadin ele, din moment ce anumite combinatiide valori factoriale din model, ar putea fi mai

1

folositoare dect altele. De asemenea, anumitesolutii ar putea fi mai fiabile dect altele.

Codificarea este procesul de reprezentarea genelor individuale. Procesul poate fi pusn functiune folosind biti, numere, liste denumere, liste sau orice alt tip de obiect. Cod-ificarea depinde, n mare parte, de rezolvareaproblemei. De exemplu, se pot codifica, nmod direct, numere reale sau ntregi.

Definitia problemei Comis VoiajoruluiEste una dintre cele mai cunoscute prob-

leme de optimizare combinatoriala putnd fienuntata dupa cum urmeaza: se considera omultime de n orase si un comis voiajor caretrebuie sa viziteze toate orasele, trecnd o sin-gura data prin fiecare si sa se ntoarca n orasulde pornire astfel nct costul total al circuitu-lui sa fie ct mai mic.

Din punct de vedere formal, n variantaclassica problema este echivalenta cu cea agasirii unui circuit Hamiltonian de cost minimntr-un graf complet. Problema este impor-tanta att din punct de vedere teoretic ct sidin punct de vedere practic ntruct o serie deprobleme concrete pot fi formulate ca TSP:

- Identificarea rutei optime pentru mijloacede transport (persoane, marfuri)

-Generarea traseelor urmate de dispozi-tivele de producere a circuitelor integrate Ex-ista diferite variante ale problemei:

- Varianta asimetrica: costul trecerii de laun nod la altul depinde de sensul circuitului(Assymetric TSP)

- Variante cu restrictii de precedenta; re-strictiile specifica faptul ca un anumit nod tre-buie vizitat naintea altuia (Sequential Order-ing Problem - SOP)

- Variante cu mai multe mijloace detransport cu anumite capacitati care asiguraaprovizionarea (Capacitated vehicle routingproblem - CVRP)

- Variante generalizate n care exista maimulte trasee directe ntre doua noduri saunodurile sunt nlocuite cu clustere de noduri(Generalized TSP)

Problema poate fi rezolvata exact (prinanaliza tuturor circuitelor posibile) pentru val-

ori mici ale numarului de orase, nsa cumnumarul de circuite este (n1)!2 , pentru valorimari ale lui n nu exista metode exacte efi-ciente. De altfel, este cunoscut ca TSP faceparte din clasa problemelor NP-complete.

Pentru dimensiuni mari problema poatefi rezolvata utilizend metode euristice. Ma-joritatea metodelor euristice se bazeaza petransformarea iterativea a unuia sau mai mul-tor trasee initiale. Una dintre medelele eu-risticile cel mai frecvent folosite este euristicaLin-Kernighan care se bazeaza pe ideea dea nlocui unele arce ale traseului cu altele nscopul reducerii costului traseului. Cazul celmai simplu este cel n care se nlocuiesc douaarce ceea ce echivaleaza cu schimbarea or-dinii de parcurgere a unei portiuni din traseu(transformarea 2-opt).

Rezolvarea problemei Comis VoiajoruluiPrincipalele caracteristici ale acestei abor-

dari:- Retelele de tip Kohonen au o arhitec-

tura constituita din doua unitati de intrare sim unitati de iesire plasate n nodurile uneitopologii de tip inel: vecinatatea de dimen-siune 2s a unui neuron i contine multimeade neuroni {i s, i (s 1), , i 1, i, i+ 1, , i+(s 1), i + s}. Numarul de unitati functionaletrebuie sa fie mai mare dect numarul de oraseale problemei (de exemplu m=5n) .

- Fiecare unitate functionala are asociatedoua ponderi initializate aleator cu valori dindomeniul coordonatelor oraselor.

- Procesul de antrenare consta n parcurg-erea de mai multe ori a listei cu coordonate aleoraselor si ajustarea ponderilor folosind reg-ula specifica. Pentru fiecare vector de intrarex (pereche de doua coordonate) se efectueazaurmatoarele prelucrari:

- Se determina unitatea nvingatoare,i?,(cea avnd vectorul de ponderi cel maiapropiat de x)

- Se ajusteaza ponderile tuturor unitatilorfolosind regula: Wi(k + 1) = Wi(k) + (X Wi(k))(i, i?) unde functia de vecinatate este(i, i?) = exp((I i?)2(2s2))

2

Fiind data o colectie de orase si costul tre-cerii ntre fiecare pereche de orase, atunci, problemacomis voiajorului este de a gasi cel mai ieftin modde a vizita toate orasele si de ntoarcere n orasul destart.

Numele problemei provine din analogiacu un vanzator ambulant care pleaca dintr-un oras, care trebuie sa viziteze un numar deorase dat si care apoi trebuie sa se ntoarca lapunctul de plecare, cu un efort minim (deexemplu timpul minim, caz n care costulfiecarei laturi este egal cu timpul necesar par-curgerii drumului).

Metode de solutionare

Functia de evaluare este reprezentata desuma distantelor euclidiene dintre doua oraseconsecutive:

Fitness =N

i=1

(xi xi1)2 + (yi yi1)2

O reprezentare a traseului este cea n careorasele sunt listate n ordinea n care ele suntvizitate.

ncrucisarea traditionala nu este potriv-ita pentru aceasta problema, deoarece descen-dentii pot sa nu respecte restrictia de a se treceo singura data prin fiecare oras.

Mutatia - nici aici nu se va folosi ceatraditionala, n schimb se va putea utiliza mu-tatia prin interschimbare.(Se selecteaza aleatordoi biti dintr-un cromozom si se interschimbavalorile).

Selectia - folosind metoda traditionalabazata pe metoda ruletei, cel mai bun in-divid are cea mai buna probabilitate desupravietuire, dar aceasta nu reprezintaneaparat o certitudine. De aceea, se va folosiselectia CHC, care asigura ca individul cel maibun va supravietui ntotdeauna n noua gener-atie.

Selectia CHC asigura o convergenta mairapida n comp[aratie cu metoda ruletei. Pen-tru a preveni convergenta la un optim local,

metoda se va modifica astfel: dupa ce s-a ajunsla convergenta, se salveaza cei mai buni indi-vizi initializnd aleator restul populatiei si re-lund procedeul.

- daca dimensiunea populatiei este N, segenereaza N descendenti folosindmetoda ruletei.

- se sorteaza dupa fitness, multimea formatadin parinti si descendenti.

- se aleg cei mai buni N indivizi, ce vor formageneratia urmatoare.

Algoritmul simulatet annealing

Structura acestui algoritm este urmatoarea:Algoritmul simulated annealingt:=0initializeaza P(t)initializeaza temperatura Tselecteaza aleator un individ curent icevalueaza icrepeat

repeatselecteaza un nou individ in prin

prin mutatia unui bit n icif f (ic) < f (in)

then ic := inelse if random[0,1)

Algoritmul se termina pentru valori miciale lui T: criteriul de oprire verifica daca sis-temul "ngheata". Algoritmul de calire simu-lata poate evita optimul local.

Drumul parcurs de catre comisul voiajor l-am denumit tur. Testnd fiecare probabilitatepentru un traseu cu N orase, rezultatul esteN fasctorial. Astfel o ruta ce va contine 30 deorase, ar avea po distanta totala de 2.65 1032rute diferite. adaugnd doar un singur oras laacest traseu, timpul ar creste cu 31 factorial.

Utilizarea unui algoritm genetic estefolosita pentru a gasi oi solutie ntr-un timpmult mai scurt. Desigur, aceasta ar putea sa fiecea mai buna solutie, dar poate gasi o solutieapropiata de cea optima pentru 100 de orasen mai putin de 1 minut.

Pentru a rezolva problema comisului voia-jor, trebuie urmati ctiva pasi:

- n primul rnd, trebuie creat un grup aleatorde rute numit populatie. Acest algoritmutilizeqaza o populatie initiala greedy, ceofera posibilitatea de a alatura oraseleapropiate.

- se aleg cele mai bune doua rute (cele maiscurte) ce vor deveni parintii din popu-latie, si combinndu-le vom genera douarute noi(copiii).

- n scurt timp, rutele noi obtinute vor suferiimutatii. Astfel, se reduce posibilitatea canoile rute obtinute sa coincida.

- noile rute obtinute sunt introduse n pop-ulatie, nlocuind pe cele mai lungi,astfel dimensiunea populatiei ramneneschimbata.

- noile rute sunt create n mod repetat pna seajunge la solutia dorita.

Cele mai mari probleme n folosirea al-goritmilor genetici pentru rezolvarea proble-mei comisului voiajos le reprezinta codificarearutelor si algoritmul de ncrucisare folosit pen-tru a combina rutele "parinti" pentru a generanoile rute "copii".

ntr-un algoritm genetic standard, codifi-carea reprezinta o simpla secventa numerica,iar ncrucisarea este realizata prin alegereaaleatorie a unui punct n secventa parinte siinterschgimbnd fiecare numar din secventadupa acest punct.

Dificultatea problemei comisului voiajoreste reprezentata de faptul ca fiecare oraspoate fi utilizat o singura data ntr-o ruta.Daca o noua ruta generata contine de doua orinumele unui oras din ruta parinte, aceasta esteinvalida. Codificarea nu poate fi reprezentataca o lista a oraselor vizitate. Alte metode decodificare au fost create pentru a rezolva prob-lema ncrucisarii . Desi aceste metode nu vorcrea rute invalide, nu pot lua n considerarefaptul ca, de exemplu, ruta "A B C D E F G"este aceeasi cu ruta "G F E D C B A".

Pentru a rezolva corect problema, algorit-mul de ncrucisare va trebui sa fie ceva maicomplicat. n cazul aplicatiei, se stocheazalegaturile n ambele sensuri pentru fiecareruta. Operatia de ncrucisare nu se rezumadoar la combinarea a doua siruri. Aceastava lua fiecare legatura ce exista ntre parintisi o va plasa si n noile rute generate. Apoi,pentru primul "copil" va alterna ntre alegerealegaturilor de la al doilea parinte si apoide la primul. Pentru al doilea "copil", vaalterna ntre al doilea parinte si primul nalegerea altei multimi de legaturi. Pentrualti copii exista probabilitatea ca o legatura sacreeze o ruta, astfel nct n locul unei sin-gure cai de acces, sa existe mai multe de-conectate. Aceste legaturi trebuie respinse.Pentru a completa legaturile ramase, oraselesunt alese aleator. Deoarece ncrucisarea nu seefectueaza complet aleator, aceasta este con-siderata a fi greedy.

n cele din urma, algoritmul genetic vagenera solutii identice. Acest lucru nu sedoreste. O data ce fiecare ruta este identica,algoritmul nu va putea gasi solutia optima.Exista doua posibilitati pentru a evita acest lu-cru. Prima este aceea de a folosi o populatieinitiala ce contine uin numar foarte mare deindivizi, ceea ce va necesita o cantitate de timpsemnificativa pentru ca algoritmul sa genereze

4

solutii identice. A doua este reprezentata demutatie, unde cteva rute "copii" sunt alteratealeator pentru a produce o noua ruta unica.

Algoritmul folosit n aplicatie utilizeaza opopulatie initiala greedy. Legaturile dintreorase nu sunt complet aleatoare. Acesta vacrea legaturi ntre orasele cele mai apropiate.Acest lucru nu se ntmpla tot timpul, pentrucde fiecare data pornind de la populatia in-itiala se vor genera rute identice.

References

[1] I. Iancu, Calcul Evolutiv, Ed. Universitaria,Craiova, 2009

[2] S.N. Sivanandam, S.N. Deepa, Introduc-tion to Genetic Algorithms, Springer-VerlagBerlin Heidelberg, New York, 2008

[3] D. Seniw, A Genetic Algorithm for the Trav-eling Salesman Problem, MSc Thesis, Univ.OfNorth Carolina at Charlotte, 1991

5