Analiza Algoritmilor Genetici

Proiect
4.5/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 60 în total
Cuvinte : 17630
Mărime: 98.55KB (arhivat)
Cost: 5 puncte

Extras din document

I. Analiza algoritmilor genetici

1.1. Algoritmi evoluţionişti

Algoritmii evoluţionişti au la bază câteva principii ale evoluţiei: supravieţuirea celor mai buni şi modelează câteva fenomene naturale cum ar fi transmiterea informaţiei genetice şi combinarea acesteia între mai mulţi indivizi, constituie una din categoriile moderne de căutare a soluţiilor.

Aici sunt prezentate principalele paradigme ale algoritmilor evoluţionişti (algoritmi genetici, strategii evolutive, programare evolutivă şi programarea genetică). Algoritmi evoluţionişti au fost larg utilizaţi în ultima vreme în ştiinţă şi inginerie pentru rezolvarea unor probleme complexe.

În ultimele două decenii interesul în algoritmi bazaţi pe pricipiile evoluţiei a crescut. Un termen acceptat recent ca definitoriu pentru acest tip de tehnici este metoda evoluţiei computaţionale ( EC ). În această clasă pe lângă algoritmii genetici, strategiile evoluţive, programarea evolutivă şi programarea genetica sunt incluşi şi o mulţime de algoritmi şi sisteme hibride care împrumută tehnici şi operatori ale acestei paradigme şi ca urmare sunt greu de clasificat.

1.2. Evoluţia computaţională

În general orice metodă de rezolvare a unei probleme poate fi privită în ultima instanţă ca o căutare în mulţimea potenţialelor soluţii. Mai mult, această căutare urmăreste găsirea soluţiei optime în contextul problemei şi ca urmare căutarea poate fi văzută ca o problemă de optimizare. Pentru probleme ale căror soluţii se afla într-un spaţiu, mic metodele exhaustive clasice sunt mulţumitoare, dar pentru spaţii largi de cautare sunt necesare tehnici de inteligenţă artificiala. Printre acestea se afla şi metodele evoluţiei computaţionale şi care folosesc drept model câteva fenomene naturale: moştenirea genetică şi "Darwinian strife for survival". Cele mai bune metode de evoluţie computaţională sunt algoritmii genetici şi ca urmare de foarte multe ori termenii sunt utilizaţi interschimbaţi.Structura programelor bazate pe această tehnică este foarte asemănătoare. În continuare sunt prezentate în comparaţie structurile a trei algoritmi: "hillclimber", "simulated annealing" şi "evolutionary algorithm".

procedure iterated hillclimber

begin

t <- 0

repeat

local <- FALSE

selecteaza Vc aleator

evalueaza Vc

repeat

selecteaza N noi posibile solutii în vecinatatea lui Vc prin modificarea unui singur bit al lui Vc

selecteaza din aceste N valori Vn cu valoarea cea mai "buna" a lui f în conditiile problemei

if f ( Vc ) < f ( Vn ) then Vc <- Vn

else local <- TRUE

until local t <- t + 1

until t = MAX

end

Exista mai multe tipuri de "hillclimber", diferenţiate de metoda alegerii noii populaţii. Găsirea soluţiei într-un pas în acestă metodă depinde foarte mult de punctul de pornire. Se poate întampla ca algoritmul în cautarea să să ajungă într-un punct de optim local şi care este returnat ca soluţie a problemei, caz în care algoritmul esuează.

Structura algoritmului "simulated annealing" este urmatoarea:

procedure simulated annealing

begin

t <- 0

initializarea temperaturii T

selectarea unui element Vc aleator evalueaza Vc

repeat

repeat

selecteaza o noua solutie in vecinatatea lui Vc prin modificarea unui singur bit al lui Vc

if f ( Vc ) < f ( Vn ) then Vc <- Vn

else

if random [ 0, 1 ) < exp ( ( f ( Vn ) - f ( Vc ) ) / T ) then Vc <- Vn

until ( termination-condition )

T <- g ( T, t )

t <- t + 1

until ( stop-criterion )

end

"Termination-condition" verifică dacă "echilibrul termic" s-a stabilit, dar poate fi şi un simplu test dacă ciclul s-a executat de un număr k ori dorit. Cu ajutorul lui T se urmăreşte dacă în sistem mai au loc schimbări sau acesta a "înghetat", caz în care algoritmul se încheie. Algoritmul chiar dacă ajunge într-un maxim local poate avea şansa de a părăsi acest punct şi de a găsi maximul global datorită funcţiei random. Teoretic pare posibil, dar practic algoritmul poate esua în anumite situatii.

Structura unui algoritm evoluţionist este în mare următoarea:

procedure evolutionary algorithm

begin

t <- 0

initializare P ( t )

evaluare P ( t )

while ( not termination-condition ) do

t <- t + 1

selecteaza P ( t ) din P ( t - 1 )

efectuaza transformari aupra lui P ( t )

evalueaza P ( t )

end

end

Algoritmul evoluţionist mentine o populaţie de indivizi, P ( t ) = { xt1, , xtn }pentru iteraţia t. Fiecare individ reprezintă o potenţială soluţie şi fiecare xti este evaluat pentru a măsura capacitatea sa de generare a altor indivizi. O nouă populaţie este formată din unii indivizi selectaţi din pasul anterior. Dupa crearea noii populaţii o parte o să sufere o serie de transformări (mutaţii = modificarea unui singur bit ( m: S -> S ) sau încrucişări = formarea unui nou individ din doi sau mai mulţi părinţi ( c:S x x S -> S ). După un număr oarecare de iteraţii algoritmul converge către o soluţie optimă. Pe această schemă generală se pot implementa o gamă variată de algoritmi în care fiecare îmbină altfel diferitele date ale problemei. Ei pot îngloba sau nu anumite informaţii pentru controlul procesului de căutare a indivizilor. Sau poate fi schimbată ordinea în care au loc operaţiile:

selectează P ( t ) din P ( t - 1 )

efectuază transformări aupra lui P ( t )

Preview document

Analiza Algoritmilor Genetici - Pagina 1
Analiza Algoritmilor Genetici - Pagina 2
Analiza Algoritmilor Genetici - Pagina 3
Analiza Algoritmilor Genetici - Pagina 4
Analiza Algoritmilor Genetici - Pagina 5
Analiza Algoritmilor Genetici - Pagina 6
Analiza Algoritmilor Genetici - Pagina 7
Analiza Algoritmilor Genetici - Pagina 8
Analiza Algoritmilor Genetici - Pagina 9
Analiza Algoritmilor Genetici - Pagina 10
Analiza Algoritmilor Genetici - Pagina 11
Analiza Algoritmilor Genetici - Pagina 12
Analiza Algoritmilor Genetici - Pagina 13
Analiza Algoritmilor Genetici - Pagina 14
Analiza Algoritmilor Genetici - Pagina 15
Analiza Algoritmilor Genetici - Pagina 16
Analiza Algoritmilor Genetici - Pagina 17
Analiza Algoritmilor Genetici - Pagina 18
Analiza Algoritmilor Genetici - Pagina 19
Analiza Algoritmilor Genetici - Pagina 20
Analiza Algoritmilor Genetici - Pagina 21
Analiza Algoritmilor Genetici - Pagina 22
Analiza Algoritmilor Genetici - Pagina 23
Analiza Algoritmilor Genetici - Pagina 24
Analiza Algoritmilor Genetici - Pagina 25
Analiza Algoritmilor Genetici - Pagina 26
Analiza Algoritmilor Genetici - Pagina 27
Analiza Algoritmilor Genetici - Pagina 28
Analiza Algoritmilor Genetici - Pagina 29
Analiza Algoritmilor Genetici - Pagina 30
Analiza Algoritmilor Genetici - Pagina 31
Analiza Algoritmilor Genetici - Pagina 32
Analiza Algoritmilor Genetici - Pagina 33
Analiza Algoritmilor Genetici - Pagina 34
Analiza Algoritmilor Genetici - Pagina 35
Analiza Algoritmilor Genetici - Pagina 36
Analiza Algoritmilor Genetici - Pagina 37
Analiza Algoritmilor Genetici - Pagina 38
Analiza Algoritmilor Genetici - Pagina 39
Analiza Algoritmilor Genetici - Pagina 40
Analiza Algoritmilor Genetici - Pagina 41
Analiza Algoritmilor Genetici - Pagina 42
Analiza Algoritmilor Genetici - Pagina 43
Analiza Algoritmilor Genetici - Pagina 44
Analiza Algoritmilor Genetici - Pagina 45
Analiza Algoritmilor Genetici - Pagina 46
Analiza Algoritmilor Genetici - Pagina 47
Analiza Algoritmilor Genetici - Pagina 48
Analiza Algoritmilor Genetici - Pagina 49
Analiza Algoritmilor Genetici - Pagina 50
Analiza Algoritmilor Genetici - Pagina 51
Analiza Algoritmilor Genetici - Pagina 52
Analiza Algoritmilor Genetici - Pagina 53
Analiza Algoritmilor Genetici - Pagina 54
Analiza Algoritmilor Genetici - Pagina 55
Analiza Algoritmilor Genetici - Pagina 56
Analiza Algoritmilor Genetici - Pagina 57
Analiza Algoritmilor Genetici - Pagina 58
Analiza Algoritmilor Genetici - Pagina 59
Analiza Algoritmilor Genetici - Pagina 60

Conținut arhivă zip

  • Analiza Algoritmilor Genetici.doc

Alții au mai descărcat și

Rezolvarea Problemei Comis - Voiajorului cu Ajutorul Algoritmilor Genetici

Algoritmi genetici Tehnici adaptive de cautare euristica, bazate pe principiile geneticii si ale selectiei naturale Lucreaza cu o populatie de...

Modele Teste Licenta Programarea Sistemelor Informatice

1. Care definiţie este corectă: a) Un sistem reprezintă un ansamblu de elemente (componente) interdependente, între care se stabileşte o...

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

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

Structuri de Date și Algoritmi

1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...

Programarea Calculatoarelor

Lucrarea nr. 1 Determinarea experimentala a timpului de execuţie al unui program 1. Scopul lucrării - lucrarea prezintă aspecte legate de...

Limbaje de Programare

1.1. Introducere în bazele de date Sistemele de baze de date pot fi considerate ca cea mai importantă realizare în domeniul ingineriei...

Sisteme Integrate de Proiectare și Programare

Capitolul 1 Probleme a caror rezolvare depinde esential de ingineria sistemelor soft …Sistemele care se adapteaza usor la conditiile de mediu...

Ai nevoie de altceva?