Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» Problema - Algoritm genetic pentru determinarea maximului unei functii pozitive pe un domeniu dat


Problema - Algoritm genetic pentru determinarea maximului unei functii pozitive pe un domeniu dat


Problema - Algoritm genetic pentru determinarea maximului unei functii pozitive pe un domeniu dat.

Date de intrare:

dimensiunea populatiei

domeniul de definitie al functiei

precizia cu care se lucreaza (cu care se discretizeaza intervalul)

probabilitatea de recombinare (crossover, incrucisare)



probabilitatea de mutatie

numarul de etape ale algoritmului

Iesire:

Pe ecran: maximul determinat de algoritm

Un fisier text care evidentiaza operatiile din prima etapa a algoritmului, de tipul fisierului Evolutie.txt (obtinut pentru functia -x2+x+2, domeniul [-1, 2], dimensiunea populatiei 20, precizia 6, probabilitatea de recombinare 0.25, probabilitatea de mutatie 0.01 si 50 de etape)

In fisier se vor scrie

populatia initiala sub forma

i: reprezentare cromozom x = valoarea corespunzatoare cromozomului in domeniul de definitie al functiei f =valoarea corespunzatoare cromozomului (f(Xi))

probabilitatile de selectie pentru fiecare cromozom

probabilitatile cumulate care dau intervalele pentru selectie

evidentierea procesul de selectie, care consta in generarea unui numar aleator u uniform pe (0,1) si determinarea intervalului [qi, qi+1) in care pica acest numar; corespunzator acestui interval se va selecta cromozomul i+1. Procesul se repeta pana se selecteaza numarul dorit de cromozomi. Cerinta: cautarea intervalului corespunzator lui u se va face folosind cautarea binara.

evidentierea cromozomilor care participa la recombinare

pentru recombinarile care au loc se evidentiaza perechile care participa la recombinare, punctul de rupere generat aleator precum si cromozomii rezultati in urma recombinarii

populatia rezultata dupa recombinare

populatia rezultata dupa mutatii

Pentru restul generatiilor (populatiilor din etapele urmatoare) se va afisa doar valoarea maxima .

Clase si metode care pot fi utile la implementare:

Clasa Random din pachetul java.util - pentru generare de numere aleatoare (amintim metodele nextDouble() pentru generarea de numere uniforme pe (0, 1) si nextInt(int n) pentru numere uniforme intre 0 si n-1)

Metodele de tip parseTipPrimitiv din clasele corespunzatoare tipului primitiv de care am amintit ca se folosesc la conversia unui sir de tip String in tipul primitiv dorit pot primi ca al doilea parametru baza in care este privit sirul de caractere. De exemplu

int i=Integer.parseInt('101',2);

System.out.println(i);

va afisa 5

Clasa StringBuffer din pachetul java.util - pentru siruri de caractere de lungime variabila. Are metode pentru inlocuirea unui subsir dintre doua pozitii date cu un alt sir (replace), de setare a unui caracter din sir (setCharAt), care pot fi utile pentru implementarea operatorilor genetici

Observatie: atunci cand se citeste un numar real cu metoda nextDouble() a clasei Scanner, separatorul pentru zecimale trebuie sa fie cel din setarile locale, sau se poate folosi metoda useLocale a clasei Scanner

Scanner sc = new Scanner(System.in);

sc.useLocale(Locale.ENGLISH);

double d=sc.nextDouble(); //1.54 este un numar valid pentru intrare

System.out.println(d);

sc.useLocale(Locale.FRENCH);

d = sc.nextDouble(); /*1,54 este un numar valid pentru intrare, 1.54 nu este valid*/

System.out.println(d);

In ambele cazuri numarul putea fi dat in format stiintific 154e-2

Pentru mai multe detalii consultati documentatia java.sun.com/docs (API pentru versiunea 5)

Cautarea binara



Se considera vectorul a=(a1, ,an) ordonat crescator si o valoare x. Se cere sa se determine daca x apare printre componentele vectorului. In caz contrar se va determina i astfel incat ai-1<x<ai

Tinand cont de faptul ca a este ordonat crescator, vom compara pe x cu elementul din 'mijlocul' vectorului. Daca avem egalitate, algoritmul se incheie; in caz contrar vom lucra fie pe 'jumatatea' din stanga, fie pe cea din dreapta.

Vom adauga a=-∞, an+1=+ ∞. Cautam perechea (b,i) data de:

(true,i) daca ai=x

(false,i) daca ai-1<x<ai

Algoritmul este urmatorul:

procedure CautBin

p 1; u n

while p≤u

i (p+u)/2

case ai>x : u i-1   

ai=x : write(true,i); stop

ai<x : p i+1

write(false,p)

end

Algoritmul necesita o mica analiza, legata de corectitudinea sa partiala. Mai precis, ne intrebam: cand se ajunge la p>u

pentru cel putin 3 elemente : nu se poate ajunge la p>u

pentru 2 elemente, adica pentru u=p+1: se alege i=p. Daca x<ai, atunci u p-1. Se observa ca se iese din ciclul while si ai-1<x<ai=ap

pentru un element, adica p=u: se alege i=p=u. Daca x<ai atunci u p-1, iar daca x>ai atunci p u+1; in ambele cazuri se paraseste ciclul while si se tipareste un rezultat corect.







Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate