Programare evolutiva si algoritmi genetici

Curs
10/10 (1 vot)
Domeniu: Cibernetică
Conține 4 fișiere: docx
Pagini : 147 în total
Cuvinte : 33672
Mărime: 735.39KB (arhivat)
Cost: Gratis

Extras din document

Introducere

Ideea de a aplica principiile darwiniste ale evolutiei in rezolvarea automata a problemelor (Problem Solving - PS) dateaza din anii 1940, inaintea aparitiei calculatoarelor electronice. In 1948 Turing propunea o tehnica de rezolvare a problemelor numita cautare genetica sau evolutiva. In anii 1960 Fogel, Qwens si Walsh introduceau conceptul de programare evolutiva (sau evolutionista), in timp ce Holland dezvolta algoritmii genetici. In aceeasi perioada, Rechenberg si Schwefel introduceau strategiile evolutive (evolutioniste) ca modalitati alternative de rezolvare automata a problemelor. In anii 1990, Koza dezvolta o noua tehnica de cautare in spatiul solutiilor, programarea genetica. In terminologia actuala, intregul spectru de metode de rezolvare automata de inspiratie darwinista este desemnat prin termenul de calcul evolutiv (evolutionist) si include subdomeniile: programare evolutiva, strategii evolutive, algoritmi genetici si programare genetica.

Calculul evolutiv este un domeniu al informaticii inspirat din procesul evolutiei naturale; ideea care sta la baza calculului evolutiv este conexiunea evolutie naturala - tehnica de rezolvare a problemelor de tip experiment-eroare (sau generare-testare). Cu alte cuvinte, intr-un mediu dat, indivizii constituiti intr-o populatie intra in competitie pentru a supravietui si a se reproduce. Abilitatea indivizilor de a-si atinge aceste scopuri in mediul in care traiesc este strict corelata cu sansele lor de supravietuire si multiplicare si determina evolutia in timp a populatiei. In contextul modalitatii de rezolvare a problemelor de tip generare-testare stochastice, populatia este modelata ca o colectie de elemente candidat la solutie. Calitatea candidatilor la solutie, definita in termenii gradului in care fiecare element rezolva problema, determina sansa lor de a fi mentinuti si utilizati pentru construirea unor noi candidati.

Suportul de natura biologica al calculului evolutiv

Teoria evolutionista a lui Darwin ofera o explicatie a diversitatii biologice si a mecanismului care sta la baza acesteia. In centrul interpretarii macroscopice a evolutiei este plasata selectia naturala. Considerand un mediu care poate sustine un numar limitat de indivizi si instinctul primar al fiecarui individ de a se reproduce, procesul de selectie este esential si inevitabil in controlul dimensiunii populatiei. Selectia naturala favorizeaza indivizii cei mai competitivi in insusirea resurselor, adica acei indivizi care sunt cel mai bine adaptati conditiilor de mediu. Fenomenul este cunoscut drept supravietuirea celor mai bine adaptati/ potriviti (survival of the fittest).

Teoria evolutiei are ca principii fundamentale selectia bazata pe competitie si variatiile de fenotip in randul membrilor populatiei. Fenotipul este ansamblul de insusiri si caractere care se manifesta in mod vizibil la un individ si care este determinat pe baza ereditara si de conditiile de mediu (DEX). Caracteristicile fenotipului unui individ determina gradul lui de adaptabilitate la conditiile de mediu (fitness). Fiecare individ reprezinta o combinatie unica de caracteristici ale fenotipului si este evaluat de conditiile de mediu. Daca evaluarea este favorabila, atunci fenotipul individului este propagat spre urmasi (progenituri), altfel caracteristicile fenotipului dispar si individul moare fara a se putea reproduce. Viziunea lui Darwin despre evolutie este aceea ca, in procesul trecerii de la o generatie la alta prin reproducere, apar mutatii (variatii) mici, aleatoare, in caracteristicile fenotipului. Ca rezultat al acestor variatii, apar si sunt evaluate noi combinatii de caracteristici ale fenotipului. Cele mai bune dintre ele supravietuiesc si se reproduc si in acest mod evolutia conduce la progres.

Modelul primar poate fi deci rezumat dupa cum urmeaza. O populatie este formata dintr-un numar de indivizi, priviti ca unitati de selectie; succesul fiecarui individ in incercarea de a se reproduce depinde de cat de bine este adaptat conditiilor de mediu comparativ cu restul indivizilor. Pe parcursul reproducerii celor mai buni (bine adaptati la mediu) indivizi, apar mutatii ocazionale, care genereaza noi indivizi, ce vor fi ulterior evaluati. In consecinta, pe masura ce timpul trece, se produc schimbari in structura populatiei, cu alte cuvinte populatia reprezinta o unitate a evolutiei. Intregul proces poate fi asimilat din punct de vedere intuitiv cu modelul unui peisaj adaptiv (dinamic) (respectiv o suprafata adaptive) in spatiul 3D (0-x-y-z). Fiecare punct p(x,y,z) al suprafetei este asimilat unui individ, unde in planul x-y este figurata combinatia de caracteristici ale fenotipului individului, iar altitudinea lui p (valoarea lui pe axa 0z) corespunde nivelului de adaptabilitate (fitness) a individului reprezentat de p. In acest context, evolutia este procesul de "avans" al populatiei spre zone aflate la o altitudine mai mare, acest avans fiind realizat pe baza mutatiilor si selectiei naturale. Este obtinuta astfel legatura cu conceptul de probleme multimodale, adica probleme in care exista o multime de puncte de optim local (superioare tuturor solutiilor din vecinatatea lor), cel mai bun element al multimii fiind optimul global. O problema in care exista un singur optim local este numita unimodala.

Legatura dintre procesul evolutiei si un proces de optimizare este pe cat de directa, pe atat de inselatoare, pentru ca evolutia nu presupune intotdeauna cresterea globala a calitatii populatiei (in termenii functiei de fitness). Deoarece, la fiecare epoca, populatia este finita si operatorii de selectie si mutatie includ componente aleatoare, poate fi constatata o inactivitate genetica, manifestata fie prin disparitia din populatie a unor indivizi foarte adaptati conditiilor de mediu, fie prin variatia foarte mica sau chiar lipsa de variatie a unor caracteristici ale fenotipului indivizilor din populatie. Unul din efectele posibile este acela al concentrarii indivizilor intr-o zona de adaptabilitate scazuta. Efectul rezultat prin combinarea procesului de selectie cu inactivitatea genetica poate conduce in egala masura la cresterea nivelului de adaptabilitate globala a populatiei, respectiv la descresterea acestuia. In plus, nu exista nici o garantie ca, daca evolutia duce la cresterea calitatii populatiei, nivelul de optim local nu a fost deja atins inaintea unui fenomen de inactivitate genetica. In scopul evitarii "ciclarii" evolutiei populatiei intr-o regiune de optim local, au fost dezvoltate o serie de teorii, una dintre cele mai cunoscute fiind teoria lui Wright conform careia poate fi determinat optimul global in cazul unei suprafete fixe (teorie referita drept shifting balance).

Tipuri de probleme ce pot fi rezolvate pe baza calculului evolutiv

In literatura de specialitate sunt evidentiate doua clase de metode PS de inspiratie biologica: calculul neuronal (neurocomputing), prin intermediul caruia problemele sunt rezolvate imitand modul de functionare (rationament) a (al) creierului uman si procesele de tip evolutiv, problemele fiind rezolvate prin imitarea crearii creierului uman.

In general, un sistem functional de rezolvare automata a problemelor contine trei componente: datele de intrare, datele de iesire si modulul intern care conecteaza primele doua componente. Modalitatea de functionare a modelului permite explicarea modului de functionare a sistemului, in sensul ca, raspunsul sistemului poate fi calculat pentru orice date de intrare specificate. In functie de componentele din sistem cunoscute, pot fi diferentiate urmatoarele tipuri de probleme:

- Probleme de optimizare: sunt cunoscute modelul si datele de iesire dorite (respectiv o descriere a acestora), iar problema este de a determina datele de intrare care corespund rezultatelor dorite. Un exemplu de astfel de problema este cea a comis voiajorului (in care trebuie determinat cea mai scurta sau ieftina ruta care sa lege un numar dat de orase): modelul este cunoscut si corespunde formulei de calcul a lungimii unei rute date, in care lungimea (sau costul) calculata (calculat) este data de iesire. Proprietatea pe care rezultatul trebuie sa o indeplineasca este un criteriu de optim (lungime minima), iar problema este de a determina acea data de intrare, corespunzatoare unei rute, care sa conduca la rezultatul dorit. O problema de optimizare rezolvata cu succes prin calcul evolutiv este generarea orarului in cadrul unei universitati. In cursul unei zile sunt programate in general mii de activitati, restrictiile pe care trebuie sa la indeplineasca o

Preview document

Programare evolutiva si algoritmi genetici - Pagina 1
Programare evolutiva si algoritmi genetici - Pagina 2
Programare evolutiva si algoritmi genetici - Pagina 3
Programare evolutiva si algoritmi genetici - Pagina 4
Programare evolutiva si algoritmi genetici - Pagina 5
Programare evolutiva si algoritmi genetici - Pagina 6
Programare evolutiva si algoritmi genetici - Pagina 7
Programare evolutiva si algoritmi genetici - Pagina 8
Programare evolutiva si algoritmi genetici - Pagina 9
Programare evolutiva si algoritmi genetici - Pagina 10
Programare evolutiva si algoritmi genetici - Pagina 11
Programare evolutiva si algoritmi genetici - Pagina 12
Programare evolutiva si algoritmi genetici - Pagina 13
Programare evolutiva si algoritmi genetici - Pagina 14
Programare evolutiva si algoritmi genetici - Pagina 15
Programare evolutiva si algoritmi genetici - Pagina 16
Programare evolutiva si algoritmi genetici - Pagina 17
Programare evolutiva si algoritmi genetici - Pagina 18
Programare evolutiva si algoritmi genetici - Pagina 19
Programare evolutiva si algoritmi genetici - Pagina 20
Programare evolutiva si algoritmi genetici - Pagina 21
Programare evolutiva si algoritmi genetici - Pagina 22
Programare evolutiva si algoritmi genetici - Pagina 23
Programare evolutiva si algoritmi genetici - Pagina 24
Programare evolutiva si algoritmi genetici - Pagina 25
Programare evolutiva si algoritmi genetici - Pagina 26
Programare evolutiva si algoritmi genetici - Pagina 27
Programare evolutiva si algoritmi genetici - Pagina 28
Programare evolutiva si algoritmi genetici - Pagina 29
Programare evolutiva si algoritmi genetici - Pagina 30
Programare evolutiva si algoritmi genetici - Pagina 31
Programare evolutiva si algoritmi genetici - Pagina 32
Programare evolutiva si algoritmi genetici - Pagina 33
Programare evolutiva si algoritmi genetici - Pagina 34
Programare evolutiva si algoritmi genetici - Pagina 35
Programare evolutiva si algoritmi genetici - Pagina 36
Programare evolutiva si algoritmi genetici - Pagina 37
Programare evolutiva si algoritmi genetici - Pagina 38
Programare evolutiva si algoritmi genetici - Pagina 39
Programare evolutiva si algoritmi genetici - Pagina 40
Programare evolutiva si algoritmi genetici - Pagina 41
Programare evolutiva si algoritmi genetici - Pagina 42
Programare evolutiva si algoritmi genetici - Pagina 43
Programare evolutiva si algoritmi genetici - Pagina 44
Programare evolutiva si algoritmi genetici - Pagina 45
Programare evolutiva si algoritmi genetici - Pagina 46
Programare evolutiva si algoritmi genetici - Pagina 47
Programare evolutiva si algoritmi genetici - Pagina 48
Programare evolutiva si algoritmi genetici - Pagina 49
Programare evolutiva si algoritmi genetici - Pagina 50
Programare evolutiva si algoritmi genetici - Pagina 51
Programare evolutiva si algoritmi genetici - Pagina 52
Programare evolutiva si algoritmi genetici - Pagina 53
Programare evolutiva si algoritmi genetici - Pagina 54
Programare evolutiva si algoritmi genetici - Pagina 55
Programare evolutiva si algoritmi genetici - Pagina 56
Programare evolutiva si algoritmi genetici - Pagina 57
Programare evolutiva si algoritmi genetici - Pagina 58
Programare evolutiva si algoritmi genetici - Pagina 59
Programare evolutiva si algoritmi genetici - Pagina 60
Programare evolutiva si algoritmi genetici - Pagina 61
Programare evolutiva si algoritmi genetici - Pagina 62
Programare evolutiva si algoritmi genetici - Pagina 63
Programare evolutiva si algoritmi genetici - Pagina 64
Programare evolutiva si algoritmi genetici - Pagina 65
Programare evolutiva si algoritmi genetici - Pagina 66
Programare evolutiva si algoritmi genetici - Pagina 67
Programare evolutiva si algoritmi genetici - Pagina 68
Programare evolutiva si algoritmi genetici - Pagina 69
Programare evolutiva si algoritmi genetici - Pagina 70
Programare evolutiva si algoritmi genetici - Pagina 71
Programare evolutiva si algoritmi genetici - Pagina 72
Programare evolutiva si algoritmi genetici - Pagina 73
Programare evolutiva si algoritmi genetici - Pagina 74
Programare evolutiva si algoritmi genetici - Pagina 75
Programare evolutiva si algoritmi genetici - Pagina 76
Programare evolutiva si algoritmi genetici - Pagina 77
Programare evolutiva si algoritmi genetici - Pagina 78
Programare evolutiva si algoritmi genetici - Pagina 79
Programare evolutiva si algoritmi genetici - Pagina 80
Programare evolutiva si algoritmi genetici - Pagina 81
Programare evolutiva si algoritmi genetici - Pagina 82
Programare evolutiva si algoritmi genetici - Pagina 83
Programare evolutiva si algoritmi genetici - Pagina 84
Programare evolutiva si algoritmi genetici - Pagina 85
Programare evolutiva si algoritmi genetici - Pagina 86
Programare evolutiva si algoritmi genetici - Pagina 87
Programare evolutiva si algoritmi genetici - Pagina 88
Programare evolutiva si algoritmi genetici - Pagina 89
Programare evolutiva si algoritmi genetici - Pagina 90
Programare evolutiva si algoritmi genetici - Pagina 91
Programare evolutiva si algoritmi genetici - Pagina 92
Programare evolutiva si algoritmi genetici - Pagina 93
Programare evolutiva si algoritmi genetici - Pagina 94
Programare evolutiva si algoritmi genetici - Pagina 95
Programare evolutiva si algoritmi genetici - Pagina 96
Programare evolutiva si algoritmi genetici - Pagina 97
Programare evolutiva si algoritmi genetici - Pagina 98
Programare evolutiva si algoritmi genetici - Pagina 99
Programare evolutiva si algoritmi genetici - Pagina 100
Programare evolutiva si algoritmi genetici - Pagina 101
Programare evolutiva si algoritmi genetici - Pagina 102
Programare evolutiva si algoritmi genetici - Pagina 103
Programare evolutiva si algoritmi genetici - Pagina 104
Programare evolutiva si algoritmi genetici - Pagina 105
Programare evolutiva si algoritmi genetici - Pagina 106
Programare evolutiva si algoritmi genetici - Pagina 107
Programare evolutiva si algoritmi genetici - Pagina 108
Programare evolutiva si algoritmi genetici - Pagina 109
Programare evolutiva si algoritmi genetici - Pagina 110
Programare evolutiva si algoritmi genetici - Pagina 111
Programare evolutiva si algoritmi genetici - Pagina 112
Programare evolutiva si algoritmi genetici - Pagina 113
Programare evolutiva si algoritmi genetici - Pagina 114
Programare evolutiva si algoritmi genetici - Pagina 115
Programare evolutiva si algoritmi genetici - Pagina 116
Programare evolutiva si algoritmi genetici - Pagina 117
Programare evolutiva si algoritmi genetici - Pagina 118
Programare evolutiva si algoritmi genetici - Pagina 119
Programare evolutiva si algoritmi genetici - Pagina 120
Programare evolutiva si algoritmi genetici - Pagina 121
Programare evolutiva si algoritmi genetici - Pagina 122
Programare evolutiva si algoritmi genetici - Pagina 123
Programare evolutiva si algoritmi genetici - Pagina 124
Programare evolutiva si algoritmi genetici - Pagina 125
Programare evolutiva si algoritmi genetici - Pagina 126
Programare evolutiva si algoritmi genetici - Pagina 127
Programare evolutiva si algoritmi genetici - Pagina 128
Programare evolutiva si algoritmi genetici - Pagina 129
Programare evolutiva si algoritmi genetici - Pagina 130
Programare evolutiva si algoritmi genetici - Pagina 131
Programare evolutiva si algoritmi genetici - Pagina 132
Programare evolutiva si algoritmi genetici - Pagina 133
Programare evolutiva si algoritmi genetici - Pagina 134
Programare evolutiva si algoritmi genetici - Pagina 135
Programare evolutiva si algoritmi genetici - Pagina 136
Programare evolutiva si algoritmi genetici - Pagina 137
Programare evolutiva si algoritmi genetici - Pagina 138
Programare evolutiva si algoritmi genetici - Pagina 139
Programare evolutiva si algoritmi genetici - Pagina 140
Programare evolutiva si algoritmi genetici - Pagina 141
Programare evolutiva si algoritmi genetici - Pagina 142
Programare evolutiva si algoritmi genetici - Pagina 143
Programare evolutiva si algoritmi genetici - Pagina 144
Programare evolutiva si algoritmi genetici - Pagina 145
Programare evolutiva si algoritmi genetici - Pagina 146
Programare evolutiva si algoritmi genetici - Pagina 147

Conținut arhivă zip

  • Programare evolutiva si algoritmi genetici
    • MUTARE PENTRU REPREZENTARE BINARA.docx
    • Partea a II-a-GA_nou.docx
    • Partea a III-a-optimizarea portofoliilor_nou.docx
    • Partea1-Introducere+ EA.docx

Alții au mai descărcat și

Testarea alpha

Ce este testarea alpha? Testarea Alpha este una dintre cele mai comune strategii de testare software utilizate în dezvoltarea de software. Este...

Analiza informational - decizionala - Departamentul de web developer

. Cunoașterea generală a mecanismului economic Studiul de caz reprezinta o analiza informational - decizionala a sistemului reprezentat prin...

GVMD

DEPOZITE DE DATE Un depozit de date furnizează o sursă integrată şi centralizată de date, separată de sistemul tranzacţional, care conţine datele...

Structuri de date și algoritmi

Înainte de a elabora un algoritm, trebuie să ne gândim la modul în care reprezentăm datele. Structurile fundamentale de date cu care se poate opera...

Teoria recursiilor

Problema 1. Numere Fibonacci. Să se alcatuiască un Program în C++ pentru a determina numerele Fibonacci atit recursiv cît și nerecursiv. #include...

Ai nevoie de altceva?