Extras din proiect
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.
Preview document
Conținut arhivă zip
- Documentatie.doc
- ico.ico
- Project1.cfg
- Project1.dof
- Project1.dpr
- Project1.exe
- Project1.res
- Unit1.dcu
- Unit1.ddp
- Unit1.dfm
- Unit1.pas