Proiect la disciplina Tehnici Informatice de Optimizare

Tema: Algoritmi genetici și problema comis-voiajor

Student: Profesor:Tomulescu Ionut Prof.dr.ing Serbencu Adrian

1

Cuprins

Capitolul 1: Introducere

Capitolul 2: Algoritmi genetici

2.1 Introducere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Explicație bază. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Codificare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Crossover. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Mutatie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

Capitolul 3: Problema Calatoriile Salesman

3.1 Introducere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Diferite forme de problema. . . . . . . . . . . . . . . . . . . . . . 3.3 Metode de rezolvare a TSP. . . . . . . . . . . . . . . . . . . . . . . . 

Capitolul 4: Algoritmi genetici ca metodă de soluționare a călătorieiSalesman

4.1 Introducere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Compararea metodelor. . . . . . . . . . . . . . . . . . . . . . . . . . 

Capitolul 5: Concluzia

1. Introducere

2

Ca aplicații practice, algoritmii genetici sunt cel mai adesea utilizați în rezolvarea problemelor de optimizare, planificare ori căutare. Condiția esențială pentru succesul unei aplicații cu agenți inteligenți este ca problema de rezolvat să nu ceară obținerea soluției optime, ci să fie suficientă și o soluție apropiată de optim.

În problema comis-voiajor dorim a găsi un tur pentru toate nodurile într-ungrafic ponderat, astfel încât greutatea totală sa fie redusă la minimum. Mulți operatori de crossover și mutații diferite au fost concepute pentru problema comis-voiajor și fiecare dau rezultate diferite.Algoritmii genetici sunt o tehnica relativ noua de optimizare, care poate fiaplicata la diferite probleme, inclusiv cele care sunt NP-hard. Tehnica asigură o soluție optimă, cu toate acestea, de obicei, dă aproximări bune într-o cantitate rezonabilă de timp. Acest lucru, prin urmare, este un algoritm bun pentru a încerca pe problema comis-voiajor, una dintre cele mai renumite probleme NP-dure.

Algoritmi genetici se bazează vag pe evoluția naturală și prin a folosi tehnica "supraviețuirea celui mai adaptat ", în cazul în care cele mai bune soluții sunt variate până când vom obține un rezultat bun.

Capitolul 2: Algoritmi genetici

3

2.1 Introducere

Algoritmii genetici sunt tehnici de optimizare bazat pe o evoluție naturală. Eiinclud supraviețuirea celui mai adaptat într-un algoritm de căutare, care oferă ometodă de căutare ce nu are nevoie de a explora fiecare soluție posibilă pentru a obține un rezultat bun. Algoritmii genetici se bazează pe un proces natural de evoluție.Procedeul algoritm genetic constă din următoarele etape:• Codare• Evaluarea• Crossover• Mutația• DecodingO codificare adecvata este gasirea soluției la problema noastră, astfel încât fiecare soluție are o codificare unică și codificarea este sub formă de șir.Populația inițială este apoi selectată, de obicei la întâmplare.De asemenea, au fost propuse tehnici folosind euristica Fitness a fiecărui individîn populație si apoi calculat cât de bine se potrivește probabilitatea individului.Acest fitness este folosit pentru a găsi probabilitatea individului de legătură. Dacă un individ are o probabilitate mare (ceea ce indică faptul că este semnificativ mai aproape optimului decât restul producerii lor). Crossover este în cazul în care cele două persoane sunt recombinate pentru a crea noi persoane care sunt copiate în noua generație. Unele persoane sunt alese aleator pentru a suferi mutatii si apoi o mutație punctiformă. Caracterul din poziția corespunzătoare a șirului esteschimbat. Odată ce se face acest lucru, o nouă generație a fost format, iar procesul se repetă până cand criteriul de oprire a fost atins. În acest moment individulcare este cel mai apropiat de optim este decodat iar procesul este complet.

2.2 Explicație bază

Algoritmii genetici variază de la a fi foarte simplu pana la a fi destul de dificil deai întelege. Înainte de a continua o explicație de bază a algoritmilor genetici este necesar a înțelege modul de lucru. Vom folosi următoarea problemă pe parcursul acestei secțiuni. Vrem să maximizeze f = -2x funcția 2+ 4x - 5 pe numerele întregi din mulțimea {0,1, ..., 15}. Prin calcul sau brute force vedem că f este maximizată atunci cândX = 1

4

2.3 Codificare

Procesul de codare este adesea cel mai dificil aspect al rezolvarii unei probleme folosind algoritmi genetici. Aplicarea lor la o anumită problemă este de multe ori greu de realizat,deoarece cu greu se poate găsi o reprezentare corespunzătoare a soluției care va fi ulterior ușor de utilizat în procesul de trecere. Amintiți-vă că pentru codificare avem nevoie de multe soluții posibile pentru a crea o populație. Modul tradițional de a reprezinta o solutie este cu un șir dezero-uri.Cu toate acestea algoritmi genetici nu sunt limitati la acest sistem de codare dar pentru moment vom folosi o reprezentare șir binar.Luați în considerare problema definit mai sus. Solutiile noastre sunt, evident, doar posibile numere, asa reprezentarea este pur și simplu o forma binară a fiecărui număr. De exemplu, reprezentările binare ale lui 12 și 7 sunt 1100 și respectiv 0111.Rețineți că am adăugat un zero la începutul șirului 0111, chiar dacă aceasta nu arenici un sens adevărat. Am făcut acest lucru, astfel încât toate numerele din mulțimea {0, ..., 15} au aceeași lungime. Aceste siruri de caractere sunt numite cromozomi și fiecare element (sau biți) dinșir se numește genă.

2.4 Crossover

Crossover poate fi o procedură destul de simplă. În exemplul nostru, se folosestecel mai simplu caz de încrucișare, alegem la întâmplare doi cromozomi pentru incrucisare si alegem aleator un punct de crossover, și apoi trecem toate genele dupa acel punct. Pentru exemplu, folosind cromozomii: v1= 0111 v2= 1,100am putea alege la întâmplare punctul de crossover a doua gena după: v1=  01 | 11 v2= 11 | 00Comutarea genele după punctul de crossover-ar da: v1= 0100 = 4 v2= 1111 = 15Avem acum doi noi cromozomi care ar fi mutat în populații următoare, numit generația următoare. Nu orice cromozom este utilizat în legătură. Funcția de evaluare dă fiecărui cromozomul un "scor", care este folosit pentru a decide probabilitatea de a fi cromozom de încrucișat.

5

2.5 Mutatie

Mutațiile sunt folosite astfel încât să nu fie prins într-o optim local. Din cauzadezordinei procesului vom avea ocazional cromozomi in apropiere de un localnicoptim dar nici unul nu aproape de optimul global. Prin urmare, în apropiere de cromozomul optim local va fi ales pentru crossover deoarece acesta va avea o mai bună sansa de fitness și nu vor mai fi foarte puține șanse de a găsi optimul global. Deci mutația este un mod complet aleator de a ajunge la soluții posibile care nu ar putea fi altfel gasite.

Mutatie este realizată după încrucișare prin alegerea la întâmplare a unui cromozom în noua generație a evolua, apoi alegem la întâmplare un punct de a evolua șischimbam acel punct.

Capitolul 3: Problema Calatoriile Salesman

6

3.1 Introducere

Ideea problemei comis-voiajorului (TSP) este de a găsi un tur de un anumit număr de orașe, care vizitează fiecare oraș exact o dată și se întorc în oraș.Lungimea acestui tur este redusă la minim.Prima instanță a problemei comis-voiajorului a fost data de Euler în 1759 a cărui problemă a fost să se mute un cavaler pentru fiecare pozitie pe o tablă de șah exact o dată.Problema standard sau simetric comis-voiajorului poate afirma automat după cum urmează:Având în vedere un grafic ponderat G = (V, E) în cazul în care greutatea C la marginea dintre nodurile i și j este o valoare non-negativă, găsi tur de toate nodurile care au minim costul total.În prezent, singura metodă cunoscută garantat pentru a rezolva optim problema vanzator de orice dimensiune, este de a enumera fiecare posibil tur și căutarea turneului cu cel mai mic cost cu o schimbare. Fiecare turneu are posibil o permutare de 123 ... n, unde n este numărul de orașe, astfel încât prin urmare, numărul de tururi este n !. Când n devine mare, devine imposibil de a găsi costul de fiecare turneu în timp polinomial.Multe metode diferite de optimizare au fost folosite pentru a încerca să rezolve TSP.

3.2 Diferite forme de problema

Există mai multe variante diferite ale problemei comis-voiajorului. În primul rând cea mai scurtă cale este problema hamiltonian.Dacă avem un grafic în care fiecare margine are o greutate și două noduri vSși vT sunt date trebuie să găsim pe termen scurt o cale Est Hamiltonian de la vSla vT.Dacă adăugăm o margine de vT la vS și da -M greutate în cazul în care M este mare și pozitiv, turul nostru TSP optimă întotdeauna va duce la aceasta margine (deoarece va reduce costurile de tur) și, prin urmare va rezolva problema Hamiltonian.Asimetric Problema comis-voiajorului, este atunci când costul călătorieidin orasul I la oraș J nu este la fel ca si costul de oraș i la costul de oras j. Aceasta poate fi rezolvată în același mod ca și standard TSP dacă vom aplica anumite greutăți de margine care să se asigure că există un ciclu hamiltonian în grafic.Problema timpului vânzător ambulant dependentă este aceeași ca standard călătoresc problemă vanzator, excepția fiind perioade de timp. Costul c IJT estecostul de călătorie de la nodul i la nodul j în timp perioada t.

3.3 Metode de rezolvare a TSP

Homaifar prevede că „o abordare care ar găsi cu siguranță optima

7

soluție de orice TSP este aplicarea tip enumerare și evaluare exhaustivă”.Procedura constă în generarea tuturor excursii posibile și evaluarea si corespondența lor răspunzând lungime tur. Turneul cu cea mai mică lungime este selectat ca cel mai bun,care este garantat de a fi optimă. Daca am putea identifica și evalua un tur pe nanosecunde (sau un miliard de excursii pe secundă), ar fi nevoie de aproape zece milioane deani (număr de posibile excursii = 3,2 × 10 23) Pentru a evalua toate excursii într-un oraș de 25 de TSP. Evident, trebuie să găsim un algoritm care ne va da o soluție într-o scurtaperioadă de timp. Așa cum am spus mai înainte, problema comis-voiajor este NP-hard, astfel nu există nici un algoritm cunoscut că va rezolva în timp polinomial.Vom justifica probabil ca trebuie să-și sacrifice optimalitatea în scopul de a obține un răspuns cat mai bun intr-un interval scurt de timp. Multialgoritmi au fost judecati pentru problema comis-voiajorului. 

Capitolul 4: Algoritmi genetici ca metodă de soluționare a călătoriei Salesman

8

4.1 Introducere

Diferitele forme de codare, de crossover și mutație care le-am vazut pana acumpot fi combinate pentru a da diverși algoritmi genetici care pot fi utilizate pentru a rezolva problema vanzator. Evident, unele rutine de crossover poate fi utilizat numai cu o anumită formă de codificare așa că nu avem prea multi algoritmi genetic diferiti pentru a explora. De asemenea, doar anumite metode au fost încercate, așa că se va uita doar la astea. În cele din urmă, vom păstra în vedere faptul că aceste programe au fost testate pe diferite probleme și, prin urmare, va fi dificil de a le compara unul altul.

4.2 Compararea metodelor

În primul rând, vom nota cele mai cunoscute soluții pentru probleme specifice menționate .Pentru problema de 25 de oraș, cel mai cunoscut este soluția 1711, problema 30 orașului este 420,problema oraș 42 este 699, problema 50 orașului este 425, problema 75 orașului este 535, problema oras 100 este 627, problema oraș 105 este 14383, iar problema oraș 318 este 41345. Aceste probleme sunt probleme standard cu costuri stabilite vârf, care pot fi utilizatepentru a testa noi algoritmi.Vom lua în considerare acum algoritmi genetici pure fără informații euristicfolosit.Luați în considerare crossover modificat parțial (PMX) cu notația de turism și operator de mutație. Jog a constatat că acest algoritm dat un tur care lungime a fost cu zece procente mai mare decât am cunoscut optimul pentru problema oraș 33. Pentru orașul 100problemă, rezultatul a fost 210 la sută mai mare decât cunoscut optimul. Homaifar prevede că cea mai bună tur lungimea a aceluiași algoritm este 498 pentru oraș 30 problemă.Algoritmul folosind comanda de legătură oferă o performanță mai bună, oferind un rezultat de lungime 425 pentru problema 30 orașului, în timp ce ciclul de trecere doar oferă un tur de Lungimea 517 pentru aceeași problemă. Soluția cel mai bine cunoscuta pentru problema 30 oraș este de 420 astfel de legătură pare a fi cel mai bun de până acum.

Deci vedem că algoritmi genetici funcționează cel mai bine pentru problema comis-voiajorului atunci când vom folosi o reprezentare cu matrice de trecere matrice sau un crossover euristic.În ambele cazuri, operatorul de mutație 2-opt îmbunătățește soluția.

Capitolul 5

9

Concluzia

Algoritmii genetici par a găsi soluții bune pentru problema vanzator de călătorie, cu toate acestea, depinde foarte mult de modul în care problema este codificata și cu trei căi se folosesc metode de mutatie.În general, se pare că algoritmi genetici s-au dovedit adecvati pentru rezolvarea problemă vanzator de calatorie. Până acum, algoritmi genetici nu au găsit o mai bună soluție la problema comis-voiajor decât ce este deja cunoscut, dar multe dintrecele mai bune soluții deja cunoscute s-au găsit printr-o metodă de algoritm geneticde asemenea,.Se pare că cea mai mare problemă cu algoritmi genetici conceput pentruproblema comis-voiajor este faptul că este dificil să se mențină structura din cromozomii ORL și termina cu un tur legal în cromozomii copilului.

10