Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor

1. Algoritmi Genetici

1.1. Introducere

În ultimii ani, metodele bazate pe algoritmi genetici s-au bucurat de succes în domeniul cercetărilor operaţionale şi al inteligenţei artificiale, unde sunt utilizate în rezolvarea problemelor de optimizare şi de învăţare. Aceste metode şi-au demonstrat eficacitatea şi în alte domenii, precum cel economic, al psihologiei, biologiei şi nu în ultimul rând, în domeniul informaticii.

Deşi orientarea probabilistă a acestor metode au condus la prezentarea lor ca şi „concurente” ale metodelor de tip „Simulated Annealing” sau „Tabu Search”, în ultimul timp din ce în ce mai mulţi cercetători au încercat să combine aceste metode, obţinând algoritmi hibrizi, cu performanţe superioare.

1.2. Prezentarea algoritmilor genetici

Ideea care stă la baza funcţionării algoritmilor genetici constă în reproducerea evoluţiei naturale a organismelor (indivizi), generaţie după generaţie, respectând fenomenele de ereditate şi legea de supravieţuire enunţată de Darwin. Urmând aceste principii, într-o populaţie de indivizi, numai cei puternici, adică cei mai bine adaptaţi la mediu, supravieţuiesc şi se pot reproduce. Astfel de algoritmi au fost dezvoltaţi în anii 1950 de biologi care au utilizat calculatorul pentru a simula evoluţia organismelor [8].

Către sfârşitul anilor 60, John Holland (1975) şi echipa sa, precum şi alţi autori de mai târziu, cum ar fi Goldberg (1989) şi Davis (1991), au adaptat aceşti algoritmi pentru a căuta soluţii în probleme de optimizare, prin dezvoltarea unei analogii între un individ într-o populaţie şi o soluţie a unei probleme dintr-un spaţiu de soluţii.

Într-o populaţie, un individ este caracterizat prin amprenta sa genetică (o mulţime de cromozomi) rezultată din recombinarea amprentelor celor doi părinţi ai săi, obţinută prin încrucişare (sau „cross-over”) sau modificată prin mutaţie. Încrucişarea corespunde reproducerii sexuate a indivizilor într-o populaţie, cu respectarea fenomenelor de ereditate. Astfel, atunci când doi indivizi consideraţi îndeajuns de puternici se cuplează, ei vor crea un nou individ, membru al generaţiei următoare, care va avea şi el şanse mari de a fi îndeajuns de puternic pentru a rezista selecţiei naturale, ceea ce nu se întâmplă şi cazul indivizilor slabi. Mutaţia reprezintă modificarea amprentei genetice care poate avea loc pe indivizi de la o generaţie la alta şi care evită degenerarea populaţiei.

Prin analogie, într-un algoritm genetic, un individ (o soluţie) este caracterizat printr-o structură dată care reprezintă amprenta sa genetică. Forţa unui individ, numită fitness, poate fi măsurată prin valoarea funcţiei obiectiv corespunzătoare. Operatorii genetici de încrucişare şi mutaţie sunt algoritmi care acţionează asupra structurilor date asociate indivizilor. Aceşti algoritmi permit parcurgerea spaţiului de soluţii ale problemei. Reînnoirea populaţiei (de exemplu a mulţimii soluţiilor curente), sau altfel spus, crearea unei noi generaţii, este obţinută prin iteraţii succesive ale algoritmului genetic care creează indivizi noi şi distruge pe alţii (mecanismul de selecţie naturală). Execuţia unui astfel de algoritm trebuie să conducă, plecând de la o populaţie iniţială, după numeroase generaţii, la o populaţie în care indivizii sunt foarte puternici, sau, în alţi termeni, la o mulţime de soluţii „bune” ale problemei considerate.

Într-un algoritm genetic, structura utilizată pentru a reprezenta un individ este un lanţ de biţi numit cromozom. Recapitulând, pentru a putea folosi un algoritm genetic, avem nevoie de:

- o „reprezentare genetică” a problemei, adică de un codaj adecvat al soluţiilor sub formă de cromozomi;

- de o modalitate de a crea populaţia iniţială;

- de o funcţie de evaluare pentru a măsura fitness-ul fiecărui cromozom;

- de o metodă de selecţie a cromozomilor pentru reproducere;

- de operatori genetici adaptaţi problemei;

- de valori adecvate pentru parametrii utilizaţi de algoritm (de exemplu dimensiunea populaţiei, probabilitatea de a aplica un operator).