Rezolvarea Problemei Comis-Voiajorului cu Algoritmi Genetici

Problema comis-voiajorului

Una dintre cele mai cunoscute probleme de optimizare este problema comis-voiajorului, o problemă NP-completă care nu poate fi rezolvată într-un timp rezonabil decât prin folosirea unor algoritmi nedeterminiști. Comis voiajorul trebuie să viziteze n orașe și încearcă să găsească drumul cel mai scurt trecând prin fiecare oraș o singură dată și revenind la punctul de plecare. Problema comis voiajorului are echivalentul matematic de găsire a unui circuit hamiltonian de cost cât mai mic într-un graf etichetat (costul total al drumului este determinat de suma costurilor trecerii de la un oraș la altul).

Fiind date orașe, dimensiunea spațiului soluțiilor admisibile ale problemei comis voiajorului este , pentru . Acesta este numărul drumurilor hamiltoniene într-un graf complet cu noduri.

Pentru problema comis voiajorului toți algoritmii care găsesc soluția optimă sunt exponențiali. Cea mai directă soluție ar fi sa considerăm toate permutările (care reprezintă drumurile hamiltoniene) și sa vedem care este costul cel mai mic.

Algoritmi genetici

Inteligența artificială are din ce în ce mai numeroase aplicații în tehnică și în multe alte domenii. În cadrul acesteia, algoritmii evolutivi joacă un rol important în rezolvarea problemelor de optimizare. Algoritmii genetici fac parte din clasa mai generală a algoritmilor evolutivi care sunt metode de rezolvare a problemelor bazate pe o căutare în spațiul soluțiilor, în care se folosesc populații de “căutători” supuse unui proces de evoluție oarecum similar celui întâlnit în natură. Punctul de pornire în conceperea algoritmilor genetici îl reprezintă analogia care se poate face între rezolvarea unei probleme și procesul natural de evoluție al unei populații.

Algoritmii genetici iau ca model procesele naturale precum ar fi selecția, încrucișarea, mutația, migrația, influența mediului local și a vecinătăților. Este de remarcat aici că algoritmii evolutivi lucrează asupra unei întregi populații de indivizi (soluții) și nu asupra unei singure soluții. În acest mod este clar că procesul de căutare are loc în manieră paralelă.

Structura generală a unui algoritm genetic

Algoritmii genetici sunt procese iterative prin care o populație inițializată în manieră aleatoare este transformată succesiv prin selecție, mutație și încrucișare până la atingerea unui anumit număr de iterații (generații) sau până la îndeplinirea unui alt criteriu de oprire.

Inițializări: P(0) = ( ), t=0

Proces iterativ:

Repetă

Evaluarea populației curente: calcul pentru

Selecția părinților:

Generarea urmașilor prin încrucișare:

Modificarea urmașilor prin mutație:

Evaluarea populației de urmași: calcul valori ale lui f pentru

Selecția supraviețuitorilor:

Incrementarea contorului de generații:

Până când

P(0) = ( ), t=0 – populația generației t

- gradul de adecvare (fitness-ul) elementului