Cuprins
- Algoritmi genetici
- Problema comis-voiajorului
- Rezolvarea problemei comis-voiajorului cu ajutorul algoritmilor genetici
Extras din proiect
Algoritmi genetici
Tehnici adaptive de cautare euristica,
bazate pe principiile geneticii si ale selectiei
naturale
Lucreaza cu o populatie de indivizi (cromozomi – compusi din gene) care sunt solutii potentiale ale problemei
Realizeaza o evolutie simulata: la fiecare
generatie solutiile relativ bune se reproduc
in timp ce solutiile mai putin bune nu supravietuiesc
Etape
Populatie initiala
Fitness
Crossover
Mutatia
Structura unui algoritm genetic
Componente
modalitate de a reprezenta solutiile sub
forma genetica (cromozomi)
modalitate de generare a populatiei initiale
de solutii potentiale
functia de evaluare fitness
operatorii genetici
valorile parametrilor algoritmului genetic
criteriul de oprire
Solutia
Tehnica de explorare a spatiului solutiilor:
mostenirea genetica
lupta pentru supravietuire
Solutia se evalueaza in functie de:
supravietuirea celor mai puternici
adaptarea la mediu
evolutia speciei
Problema comis-voiajorului
Dandu-se n orase, un comis
voiajor trebuie sa viziteze
fiecare oras o singura
data si apoi sa revina la
punctul de plecare.
Obiectiv: Minimizarea
distantei parcurse
PCV si algoritmii genetici
Problema NP-completa
Solutii reprezentate sub forma genetica (cromozomi)
Spatiul de cautare este
imens: pentru 30 de orase sunt 30! ≈ 1032 tururi posibile!
Preview document
Conținut arhivă zip
- PCV.ppt
- Proiect.doc
Alții au mai descărcat și
1. Specificarea cerintelor sistemului software La o agentie de zboruri un client poate, prin intermediul unor terminale instalate in sediul...
Conceptul de evoluţie a fost propus de savantul englez Charles Darwin în 1859 în celebra sa carte “Originea speciilor prin selecţie naturală”....
1. Introducere Recrutarea și selecția resurselor umane reprezintă două subprocese vitale în cadrul procesului de management al capitalului uman...
Rezumare In aceasta lucrare mi-am propus o metodologie hibrida pentru rezolvarea unei problem de optimizare, mai exact problema rucsacului....
Capitolul I: Proces economic. Tehnologii inteligente Domeniul inteligenţei artificiale, sau IA, îşi propune să inţeleagă entităţile inteligente....
Problema comis-voiajorului Una dintre cele mai cunoscute probleme de optimizare este problema comis-voiajorului, o problemă NP-completă care nu...
Chişinău 2014 1.Scrieţi un program care calculează suma cifrelor pentru fiecare număr din consecutivitatea de 100 de numere aleatoare. Listing:...
Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...
Te-ar putea interesa și
1. REZUMAT Un algoritm genetic efectuează operaţii specifice în cadrul unui proces de reproducere guvernat de operatori genetici. Noile soluţii...
Problema comis-voiajorului Una dintre cele mai cunoscute probleme de optimizare este problema comis-voiajorului, o problemă NP-completă care nu...