Utilizarea Algoritmilor Genetici la Rezolvarea Problemei Rutarii Vehiculelor

Extras din proiect Cum descarc?

1. Algoritmi Genetici
1.1. Introducere
In ultimii ani, metodele bazate pe algoritmi genetici s-au bucurat de succes in domeniul cercetarilor operationale si al inteligentei artificiale, unde sunt utilizate in rezolvarea problemelor de optimizare si de invatare. Aceste metode si-au demonstrat eficacitatea si in alte domenii, precum cel economic, al psihologiei, biologiei si nu in ultimul rand, in domeniul informaticii.
Desi orientarea probabilista a acestor metode au condus la prezentarea lor ca si ,,concurente" ale metodelor de tip ,,Simulated Annealing" sau ,,Tabu Search", in ultimul timp din ce in ce mai multi cercetatori au incercat sa combine aceste metode, obtinand algoritmi hibrizi, cu performante superioare.
1.2. Prezentarea algoritmilor genetici
Ideea care sta la baza functionarii algoritmilor genetici consta in reproducerea evolutiei naturale a organismelor (indivizi), generatie dupa generatie, respectand fenomenele de ereditate si legea de supravietuire enuntata de Darwin. Urmand aceste principii, intr-o populatie de indivizi, numai cei puternici, adica cei mai bine adaptati la mediu, supravietuiesc si se pot reproduce. Astfel de algoritmi au fost dezvoltati in anii 1950 de biologi care au utilizat calculatorul pentru a simula evolutia organismelor [8].
Catre sfarsitul anilor 60, John Holland (1975) si echipa sa, precum si alti autori de mai tarziu, cum ar fi Goldberg (1989) si Davis (1991), au adaptat acesti algoritmi pentru a cauta solutii in probleme de optimizare, prin dezvoltarea unei analogii intre un individ intr-o populatie si o solutie a unei probleme dintr-un spatiu de solutii.
Intr-o populatie, un individ este caracterizat prin amprenta sa genetica (o multime de cromozomi) rezultata din recombinarea amprentelor celor doi parinti ai sai, obtinuta prin incrucisare (sau ,,cross-over") sau modificata prin mutatie. Incrucisarea corespunde reproducerii sexuate a indivizilor intr-o populatie, cu respectarea fenomenelor de ereditate. Astfel, atunci cand doi indivizi considerati indeajuns de puternici se cupleaza, ei vor crea un nou individ, membru al generatiei urmatoare, care va avea si el sanse mari de a fi indeajuns de puternic pentru a rezista selectiei naturale, ceea ce nu se intampla si cazul indivizilor slabi. Mutatia reprezinta modificarea amprentei genetice care poate avea loc pe indivizi de la o generatie la alta si care evita degenerarea populatiei.
Prin analogie, intr-un algoritm genetic, un individ (o solutie) este caracterizat printr-o structura data care reprezinta amprenta sa genetica. Forta unui individ, numita fitness, poate fi masurata prin valoarea functiei obiectiv corespunzatoare. Operatorii genetici de incrucisare si mutatie sunt algoritmi care actioneaza asupra structurilor date asociate indivizilor. Acesti algoritmi permit parcurgerea spatiului de solutii ale problemei. Reinnoirea populatiei (de exemplu a multimii solutiilor curente), sau altfel spus, crearea unei noi generatii, este obtinuta prin iteratii succesive ale algoritmului genetic care creeaza indivizi noi si distruge pe altii (mecanismul de selectie naturala). Executia unui astfel de algoritm trebuie sa conduca, plecand de la o populatie initiala, dupa numeroase generatii, la o populatie in care indivizii sunt foarte puternici, sau, in alti termeni, la o multime de solutii ,,bune" ale problemei considerate. 
Intr-un algoritm genetic, structura utilizata pentru a reprezenta un individ este un lant de biti numit cromozom. Recapituland, pentru a putea folosi un algoritm genetic, avem nevoie de:
- o ,,reprezentare genetica" a problemei, adica de un codaj adecvat al solutiilor sub forma de cromozomi;
- de o modalitate de a crea populatia initiala;
- de o functie de evaluare pentru a masura fitness-ul fiecarui cromozom;
- de o metoda de selectie a cromozomilor pentru reproducere;
- de operatori genetici adaptati problemei;
- de valori adecvate pentru parametrii utilizati de algoritm (de exemplu dimensiunea populatiei, probabilitatea de a aplica un operator).


Fisiere in arhiva (1):

  • Utilizarea Algoritmilor Genetici la Rezolvarea Problemei Rutarii Vehiculelor.doc

Imagini din acest proiect Cum descarc?

Banii inapoi garantat!

Plateste in siguranta cu cardul bancar si beneficiezi de garantia 200% din partea Proiecte.ro.


Descarca aceast proiect cu doar 5 €

Simplu si rapid in doar 2 pasi: completezi adresa de email si platesti.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:



* La pretul afisat se adauga 19% TVA.


Hopa sus!