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 -x²+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(X_i))

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 [q_i, q_i+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=(a₁, ,a_n) 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 a_i-1<x<a_i

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=-∞, a_n+1=+ ∞. Cautam perechea (b,i) data de:

(true,i) daca a_i=x

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

Algoritmul este urmatorul:

procedure CautBin

p 1; u n

while p≤u

i (p+u)/2

case a_i>x : u i-1   

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

a_i<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<a_i, atunci u p-1. Se observa ca se iese din ciclul while si a_i-1<x<a_i=a_p

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