5/11/2018 Algoritmi genetici referat - slidepdf.com

http://slidepdf.com/reader/full/algoritmi-genetici-referat 1/3

 

Algoritmi genetici în rezolvarea problemelor de

programare matematică  Algoritmii genetici (AG), introduşi de J. Holland în

1975, fac parte dintr-o serie de metode moderne de căutare,care abordează cu succes probleme de optimizare complexe.Sunt bazaţi pe paradigma biologică a evoluţiei vieţii, pe„mecanica selecţiei naturale şi a geneticii, rezultând algoritmi în care este implicat şi flerul inovator al căutării umane”. AG operează cu o popula ţ ie iniţială  – corespunde, deexemplu, valorilor numerice ale unei anumite variabile (unuianumit element programabil). Dimensiunea acestei populaţiinu este constantă şi este în general dependentă de problema derezolvat. Membrii acestei populaţii sunt de regulă şirurialcătuite din 0 şi1, adică şiruri binare. Exemplu de populaţieiniţială  într-o primă generaţie şi având dimensiune mică (10):110001010100001000101000000001000110001011011101010001000100111111100000000000011100001000

1111111111

În practică: dimensiune mai mare a polulaţiei + şiruri delungime mai mare. Şirurile binare pot reprezenta valorile codateale unei sau unor variabile de interes.

5/11/2018 Algoritmi genetici referat - slidepdf.com

http://slidepdf.com/reader/full/algoritmi-genetici-referat 2/3

 

Popula ţ ia ini ţ ială – generată aleator , iar pentrucaracterizarea acesteia poate fi utilizată terminologia specifică 

geneticii. Astfel, fiecare şir în cadrul populaţiei corespunde

unui cromozom şi fiecare bit (element binar) al şiruluicorespunde unei gene.Cromozomii = variabilele PO = elemente ale unei

structuri funcţionale, genom. Fiecare genom î şi începe ciclulde viaţă ca o mulţime de cromozomi generaţi aleator. Colecţiagenomilor alcătuieşte popula ţ ia.

Un AG efectuează operaţii specifice în cadrul unuiproces de reproducere guvernat de către operatori genetici.

Soluţiile noi sunt create prin selecţia şi recombinareacromozomilor existenţi, în vederea optimizării unei func ţ ii de

evaluare ( func ţ ie de performan ţă, “fitness”), aleasă pentrufiecare problemă  în parte. De exemplu, dacă problema derezolvat este o problemă de optimizare, funcţia de evaluare arputea fi funcţia obiectiv sau inversul acesteia. Semnificaţiafuncţiei respective este irelevantă pentru algoritm, ceea ce

contează fiind doar valoarea sa.Plecând de la populaţia iniţială, trebuie dezvoltată o popula ţ ie nouă, fiecare populaţie nouă generată prinreproducere înlocuind generaţia anterioară. În acest procesfuncţia de evaluare globală se va îndrepta spre optim şi vaoferi soluţii din ce în ce mai bune ale PO. Procesul este analogteoriei neo-darwiniste a evoluţiei în biologie, care afirmă că 

organismele (sistemele) adaptate continuu la schimbările demediu au şansele cele mai mari de supravieţuire.

Operatori genetici (asupra genomilor, cromozomilor):1. Selec ţ ia (naturală) – destinat alegerii unui set de

cromozomi (şiruri) din populaţie pentru a-i (a le) reproduce.

5/11/2018 Algoritmi genetici referat - slidepdf.com

http://slidepdf.com/reader/full/algoritmi-genetici-referat 3/3

 

Membrii populaţiei sunt aleşi pentru reproducere pe baza

valorii func ţ iei lor de evaluare, iar membrilor populaţiei leeste acordată o probabilitate de reproducere proporţională cu

valoarea funcţiei lor de evaluare fiind preferaţi cei cu ovaloare cât mai mare a funcţiei de evaluare.

Tehnici de selecţie:……..