Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor

Proiect
4.5/10 (2 voturi)
Domeniu: Automatică
Conține 1 fișier: doc
Pagini : 35 în total
Cuvinte : 8754
Mărime: 461.26KB (arhivat)
Cost: 10 puncte
Profesor îndrumător / Prezentat Profesorului: Ion Alecu

Extras din document

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).

Preview document

Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 1
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 2
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 3
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 4
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 5
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 6
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 7
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 8
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 9
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 10
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 11
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 12
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 13
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 14
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 15
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 16
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 17
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 18
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 19
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 20
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 21
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 22
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 23
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 24
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 25
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 26
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 27
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 28
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 29
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 30
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 31
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 32
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 33
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 34
Utilizarea algoritmilor genetici la rezolvarea problemei rutării vehiculelor - Pagina 35

Conținut arhivă zip

  • Utilizarea Algoritmilor Genetici la Rezolvarea Problemei Rutarii Vehiculelor.doc

Alții au mai descărcat și

Modelarea Matlab-Simulink a Unei Sere

Cunoasterea duratei de timp de la semanat pâna la rasaritul plantelor mai are însemnatate si pentru obtinerea unor productii cat mai timpurii. Daca...

Circuite logice secvențiale

In multe aplicatii este nevoie de un element care sa prezinte 2 stari diferite, cu posibilitatea de a trece dintr-o stare in cealalta, fara sau in...

Proiectare conceptuală

Cerintele sistemului operational Odata ce a fost definita nevoia si abordarea tehnica, e necesar sa le tranlatam intr-un “scenariu...

Ai nevoie de altceva?