Algoritm Genetic

1. Enunţul problemei

Într-un joc în care se aruncă succesiv 4 zaruri, câştigul se calculează pornind de la partea întreagă a mediei aritmetice a valorilor celor 4 zaruri, valoare la care:

• se adaugă 5 pentru fiecare diferenţă mai mare de 3 între valorile a două zaruri aruncate consecutive

• dacă există două sau mai multe valori egale, se scade cu numărul de valori similare.

Exemplu. Pentru individul (2 6 1 2), câştigul aruncării este 10, rezultat din calculul [(2+6+1+2)/4]+5+5-2.

Să se implementeze un algoritm genetic care să determine una sau mai multe soluţii optime (aruncări cu câştig maxim).

2. Datele de intrare specifice problemei şi parametrii de aplicare a algoritmului

Datǎ fiind natura problemei de faţǎ, nu existǎ date de intrare specifice. Un individ se va codifica folosind un vector de 4 numere reprezentand feţele zarurilor, deci singura limitare este ca numerele sǎ fie întregi şi sǎ aparţinǎ intervalului [1,6].

Parametrii de aplicare a algoritmului sunt:

• Numǎrul iniţial de invizi (dimensiunea iniţialǎ a populaţiei)

• Regula de grupare a indivizilor – existǎ 3 reguli de grupare care se pot aplica

• Rata de încrucişare (crossover)

• Dimensiunea turneului (se foloseşte selecţia turneu). Acest parametru reprezintǎ un procent din numǎrul de indivizi ai populaţiei.

• Rata de mutaţie geneticǎ

• Numǎrul maxim de indivizi (dimensiunea maximǎ a populaţiei)

• Numǎrul maxim de generaţii

• Fitness minim (câştigul minim pe care un individ trebuie sǎ îl aibǎ pentru ca algoritmul sǎ se opreascǎ)

3. Estimarea dimensiunii spaţiului de căutare; se poate verifica în timp rezonabil fiecare punct al spaţiului de căutare ?

În cazul acestei probleme este vorba de 4 zaruri, fiecare putând lua valori de la 1 la 6, aşadar dimensiunea spaţiului de cǎutare este 64, adicǎ 1269 indivizi. Algorimul a fost creat pentru a oferi o soluţie optimǎ sau cât mai aproape de optim într-un timp cât mai scurt, fǎrǎ a parcurge în întregime spaţiul de cǎutare, îmbunǎtǎţind în mod continuu soluţiile gǎsite. Dacǎ populaţia ar conţine toţi indivizii posibili, numǎrul de indivizi ar fi foarte mare, întrucât o parte dintre ei ar fi identici. Totuşi, datǎ fiind dimensiunea relativ micǎ a spaţiului de cǎutare, în funcţie de numǎrul iniţial de indivizi, rata de mutaţie geneticǎ şi condiţiile de oprire ale algoritmului, se poate spune cǎ este posibilǎ verificarea în unele cazuri a fiecǎrei combinaţii de zaruri, deşi acest lucru presupune un timp mare de execuţie.

4. Codificarea genetică a soluţiilor candidat şi implementarea sa în limbajul de programare ales

Pentru reprezentarea indivizilor s-a folosit codificarea valoare. Un individ va însemna configuraţia celor 4 zaruri dupǎ aruncarea lor simultanǎ, aşadar forma unui cromozom este:

individ = (z1, z2, z3, z4),

unde cele 4 gene z1, z2, z3, z4 sunt numere naturale între 1 şi 6.

În limbajul de programare Delphi, un cromozom a fost implementat printr-o structura de date individ având 4 variabile de tip întreg, z1, z2, z3, z4, pentru codificarea feţelor zarurilor, o variabilǎ fitness pentru a memora câştigul obţinut în urma aruncǎrii, şi o variabilǎ selectat folositǎ pentru a desemna indivizii din populaţie care au fost aleşi pentru a deveni pǎrinţi la un anumit moment dat. Populaţia a fost implementatǎ folosind un vector de maxim 10000 de elemente, fiecare element fiind un astfel de individ.

const VMAX=10000;

type individ=record

z1,z2,z3,z4:byte;

fitness:longint;

selectat:boolean;

end;

populatie:array[1..VMAX] of individ;

nrind:longint;

5. Evaluarea soluţiilor-candidat şi implementarea funcţiei fitness în limbajul de programare ales

Scopul algoritmului este de a obţine indivizi cu câştig maxim, aşadar funcţia fitness va avea forma funcţiei obiectiv, care trebuie maximizatǎ. Evaluarea soluţiilor candidat se face, conform enunţului, plecând de la partea întregǎ a mediei aritmetrice a feţelor celor 4 zaruri, la care se adaugǎ 5 de fiecare datǎ când diferenţa dintre 2 zaruri consecutive este mai mare sau egalǎ cu 4 şi dacǎ există două sau mai multe valori egale, se scade cu numărul de valori similare. Pentru a simplifica modul de implementare, cele 4 gene au fost introduse intr-un vector. Rezultatul funcţiei fitness va fi un numǎr întreg.