Editura Sfântul Ierarh Nicolae ISBN 978-606-577-027-0noii populatii are loc prin procesele de...
45
Editura Sfântul Ierarh Nicolae ISBN 978-606-577-027-0
Transcript of Editura Sfântul Ierarh Nicolae ISBN 978-606-577-027-0noii populatii are loc prin procesele de...
Editura Sfântul Ierarh Nicolae
ISBN 978-606-577-027-0
1
Cap.I Consideratii generale
1) Introducere Algoritmii genetici sunt o parte a calculului evolutiv care, la rândul său, este o parte a
foarte actualului domeniu al inteligenţei artificiale. Dacă algoritmii clasici cum sunt greedy, backtracking, divide et impera s.a. fac parte
din categoria algoritmilor deterministi (pentru aceleasi date de intrare dau intotdeauna aceeasi solutie), algoritmii genetici pot fi caracteriziati ca fiind niste algoritmi nedeterministi (pentru aceleasi date de intrare ofera solutii diferite). Din acest punct de vedere ei pot fi usor incadrati in larga categorie a algoritmilor euristici.
Asa cum sugerează si numele, acesti algoritmi sunt inspirati din legile geneticii, avand insa ca punct de plecare teoriile lui Charles Darwin despre evolutie. Spus intr-un mod foarte simplist, solutia unei probleme rezolvate de catre un algoritm genetic evolueaza.
Ideea calculului evolutiv a fost introdusa pentru prima oara in anul 1960 de catre I. Rechenberg in lucrarea sa “Evolution strategies”, ideea lui fiind dezvoltata apoi si de catre alti cercetatori. Algoritmii genetici au fost inventati de catre John Holland. Acesta si-a expus ideile in cartea sa ”Adaptation in Natural and Artificial Systems”, publicata in 1975. In 1992 John Koza a folosit algoritmii genetici pentru a dezvolta programe destinate anumitor scopuri precise. Metoda folosita de el a primit denumirea de programare genetica.
In practica se intalnesc nenumarate probleme cu un volum foarte mare de date de intrare cum ar fi: probleme de recunoastere (a vocii, a scrisului etc.), de coordonare a miscarii robotilor, de previziune statistica in meteorologie etc. De cele mai multe ori mintea umana abordeaza cu succes astfel de probleme, dar gasirea unor algoritmi adecvati pentru rezolvarea lor, astfel incat ele sa poata fi abordate eficient (din punctul de vedere al timpului de executie si al necesarului de memorie) cu ajutorul calculatorului, este destul de dificil de realizat. Se pune problema, cum pot entitatile naturale (nu neaparat inteligente) sa rezolve fara un efort prea mare aceste probleme combinatoriale masive, un exemplu elocvent in acest sens fiind cel al albinei care poate sa urmeze rute complexe, rute care chiar si pentru un supercalculator reprezinta o piatra de temelie in incercarea de a le gasi in timp real. De aceea, pentru astfel de probleme, s-a incercat imitarea “inteligentei” gasita in natura prin incercarea de a “simula soft” lumea reala, copiind caile de rezolvare pe care le-a gasit natura pentru solutionarea lor, si de a prelucra datele de o maniera “cat mai naturala”.
2) Notiuni de genetica Toate organismele vii sunt alcatuite din celule. In nucleul fiecarei celule exista
aceeasi multime de cromozomi. Cromozomii sunt siruri de A.D.N. (acid dezoxiribonucleic) si servesc ca model pentru intregul organism, A.D.N.-ul codificand sub forma chimica informatiile genetice pentru toate caracterele ereditare. Un cromozom este alcatuit din gene, fiecare gena codificand o caracteristica (spre exemplu culoarea ochilor). Ea are o pozitie fixa in cromozom.
2
In timpul reproducerii apar doua tipuri de transformari: incrucisarea (engl. crossover) si mutatia. Mult simplificat, procesul de incrucisare ar arata astfel: doi cromozomi se “lovesc” unul de celalalt, isi schimba intre ei “fragmente” de informatii genetice (printr-o recombinare a genelor, insa fara a-si schimba numarul de gene) si apoi se indeparteaza. Mutatia reprezinta modificarea unor elemente dintr-un cromozom (apar elemente care nu apartin nici unuia dintre cei doi cromozomi parinti), si apare de obicei din cauza erorii copierii de gene de la parinti.
O specie se caracterizează prin: numărul de gene, ordinea genelor în cromozom şi semnificaţia fiecărei gene.
Populaţia este o mulţime de n indivizi (in cazul algoritmilor genetici notiunea de individ se va confunda cu cea de cromozom), din aceeaşi specie, care ocupă un teritoriu cu resurse limitate şi care se reproduc între ei. Orice populatie evolueaza in timp prin aplicarea transformarilor mai sus amintite.
Mediul cuprinde, in afara de teritoriu si resurse, totalitatea regulilor prin care se cre-ează relaţiile de concurenţă între indivizii din populaţie.
Speranta de viata (engl. fitness) este o valoare care se ataseaza fiecarui individ (cromozom), si care reprezinta in esenta valoarea adaptabilitatii la regulile impuse de mediu.
3) Algoritmul general (schema logica si pseudocod) Asa cum am mai spus, solutia pentru o problema rezolvata prin algoritmi genetici
evolueaza. Algoritmul incepe cu o multime de solutii (solutieindividcromozom), numita populatie. Aceasta populatie (denumita uneori si generatia 0) se genereaza aleator.
Solutiile dintr-o populatie existenta la un anumit moment dat sunt luate si folosite pentru a forma o noua populatie pe baza unor anumite criterii. Acest lucru este motivat de faptul ca noua populatie are sanse foarte mari sa fie mai buna decat cea veche. Formarea noii populatii are loc prin procesele de incrucisare (crossover) si mutatie. Cu cat speranta de viata (fitness) a unui cromozom este mai mare, cu atat sansa ca acesta sa supravietuiasca in populatia urmatoare este mai mare. Totodata, la incrucisare, sansa unui cromozom de a fi ales pentru acest proces este direct proportionala cu fitness-ul lui.
Algoritmul de mai sus este repetat pana cand o conditie este satisfacuta. Conditia este de obicei repetarea de un numar de ori al ciclului, imbunatatirea solutiei cu un anumit grad etc.
In figura de mai jos se reprezinta schema logica care ilustreaza, la modul general, mecanismele descrise mai sus.
3
criteriude oprire
inserţie
nu
da
(populaţia iniţială)
rezultat
evaluare
P0
Pt
P't
P''t
Pt
selecţie
reproducere
t = t + 1
(urmaşi)
(părinţi)
Pt+1
Pt
Pt
In blocul de instructiuni “evaluare” se calculeaza fitness-ul fiecarui cromozom,
aceste valori ajutand mai apoi la selectia (blocul “selectie”) cromozomilor ce se vor incrucisa, formand astfel noua populatie.
Blocul “reproducere” efectueaza cele 2 procese de crossover si mutatie. In secventa “insertie” are loc inlocuirea populatiei vechi cu populatia noua obtinuta
prin reproduceri succesive. Algoritmul se repeta pana cand se indeplineste criteriul de oprire, care reprezinta de
obicei creerea unui anumit numar de populatii (lucru contorizat de variabila t). Sageata care duce la “insertie” fara a trece prin “selectie” si “reproducere” reprezinta
fenomenul de elitism, fenomen ce va fi explicat in capitolul urmator. In continuare vom prezenta codificarea in pseudocod a modului de functionare a unui
algoritm genetic.
// incepe cu un timp initial(se porneste de la generatia 0) t := 0; // initializeaza o populatie aleatoare de n cromozomi (care reprezinta solutii posibile pentru problema) InitializeazaPopulatie(); // calculeaza fitness-ul fiecarui cromozom din populatia initiala CalculFitness (); // testeaza pentru criteriul de oprire;
4
// cat timp nu este indeplinit criteriul de oprire creeaza o populatie noua pe baza celei vechi;
// incrementeaza contorul de timp; t := t + 1;
// selecteaza doi parinti cromozomi pe baza unor reguli prestabilite;
SelectieParinti();
// recombina genele cromozomilor selectati prin crossover;
Crossover();
// modifica noii cromozomi formati prin mutatie; Mutatie();
// insereaza cromozomii noi formati in populatia noua; Insert();
// populatia noua o inlocuieste pe cea veche; // daca se indeplineste conditia de final afiseaza solutia;
//sfarsit algoritm.
5
Cap.II Codificarea informaţiilor
Precum se poate observa, algoritmul de mai sus (ilustrat prin schema logica si pseudocod) este foarte general. Pentru fiecare problema particulara in parte trebuie sa se raspunda la urmatoarele intrebari: 1. Cum codificam cromozomii, si cum este reprezentata o solutie in cromozom? 2. Cum initializam cromozomii? Care este populatia initiala? Cat de mare este ea? 3. Cine este fitness-ul unui cromozom? 4. Cum selectam parintii pentru incrucisare? 5. Cum se face incrucisarea? 6. Cum se face mutatia? 7. Daca noua populatie este formata doar prin crossover, atunci este posibil sa se piarda
cele mai bune solutii din actuala populatie. Cum evitam acest lucru? 8. Cat de des apare mutatia? Daca apare prea des, ar insemna ca facem o cautare
aleatoare in spatiul solutiilor. Daca nu apare nici o data, atunci s-ar putea sa cadem intr-un extrem local.
9. Cand se termina algoritmul? La toate aceste intrebari si la multe altele care se leaga de ele vom raspunde in
paragrafele care urmeaza.
1) Codificarea cromozomilor Exista multe variante de codificare, totul depinzand de problema pe care dorim sa o
rezolvam. Trebuie avuta mare grija in aceasta etapa deoarece o codificare buna poate duce la o implementare usoara a operatiilor de incrucisare si mutatie. Exemple: a) Codificarea binara
Fiecare cromozom este reprezentat ca un sir de 1 si 0: Cromozomul A 1001100101011101011010011 Cromozomul B 1111110011000000110101101 Problema clasica care foloseste acest tip de codare este problema discreta a
rucsacului. Aici fiecare obiect este codificat cu 1 daca este in rucsac si cu 0 daca nu este in rucsac. b) Codificarea sub forma de permutare
Fiecare cromozom este reprezentat sub forma unei permutari: Cromozomul A 1 5 3 2 6 4 7 9 8 Cromozomul B 8 5 6 7 2 3 1 4 9 Aceasta codificare se face in cazul problemei comis voiajorului. O permutare
reprezinta ordinea in care comis-voiajorul viziteaza orasele. c) Codificarea sub forma de valori
Fiecare cromzom este un sir de valori: Cromozomul A 1.234 5.3243 0.4456 2.3293 2.4545 Cromozomul B ABDJEIFJDHDHDGKDFLDPIRW Cromozomul C (back),(back),(right),(forward),(left)
6
2) Populatia initiala Populatia este o multime de cromozomi care trebuie sa fie suficient de mare pentru a
se putea realiza un numar multumitor de combinatii intre cromozomii componenti, dar nu prea mare, deoarece acest lucru va incetini algoritmul.
Populatia initiala este una aleatoare. Spre exemplu, pentru determinarea unui drum hamiltonian de cost minim, se poate incepe cu generarea aleatoare a catorva permutari.
O parte din populatia initiala poate fi generata prin metode euristice, spre exemplu in cazul problemei comis-voiajorului se pot genera cativa cromozomi prin metoda greedy. In acest fel se poate ajunge la o solutie mai rapid.
3) Fitness-ul unui cromozom
Fitness-ul unui cromozom este speranta lui de viata. Pe noi ne intereseaza sa obtinem cromozomi cu fitness-ul cat mai mare, sau cat mai mic, in orice caz, cu un fitness la o extrema.
In cazul problemei comis-voiajorului, fitness-ul este costul drumului codificat de respectivul cromozom. Aici ne intereseaza sa obtinem un cromozom cu un fitness cat mai mic.
In cele ce urmeaza presupunem, pentru simplitate, ca dorim sa obtinem un cromozom cu fitness-ul cat mai mare.
4) Selectarea cromozomilor parinti
Cromozomii sunt selectati din populatie pentru a fi parinti intr-o incrucisare (crossover). Conform teoriei lui Darwin, cei mai buni parinti supravietuiesc si se inmultesc creand noi urmasi.
Dintre metodele cele mai des intalnite de selectie amintim: a) Selectia aleatoare Doi parinti sunt alesi aleator din populatie. Acest lucru se face generand un numar
aleator intre 1 si dimensiunea populatiei. b) Selectarea cu ajutorul ruletei ponderate Parintii sunt selectati in conformitate cu fitness-ul lor. Cu cat sunt mai buni, cu atat
sansa lor de a fi alesi este mai mare. Imaginati-va o ruleta in care sunt dispusi toti cromozomii din populatie. Fiecarui cromozom ii corespunde un sector al ruletei, direct proportional, ca marime, cu fitness-ul cromozomului respectiv. In acest fel cromozomii cu fitness mai mare au atasate sectoare mai mari iar cei cu fitness mic au atasate sectoare mai mici. La aruncarea bilei pe ruleta exista mai multe sanse de alegere pentru cromozomii cu fitness mare. Figura de mai jos reprezinta un exemplu de ruleta ponderata pentru opt cromozomi.
7
87
5
4
3
2
1
6
Simularea rotii de ruleta se face in felul urmator: se calculeaza suma tuturor fitness-urilor cromozomilor. Fie aceasta S; se genereaza un numar aleator intre 1 si S. fie acesta r; se parcurge populatia ordonata crescator dupa fitness si se calculeaza suma
fitness-urilor cromozomilor parcursi pana depasim valoarea r. Se alege cromozomul la care s-a ajuns.
c) Selectia aranjata Selectia anterioara nu este recomandata in cazul in care fitness-ul cromozomilor
difera foarte mult. De exemplu daca unul din cromozomi are fitness-ul de 100 de ori mai mare decat suma fitness-urilor celorlalti cromozomi, sansele cromozomilor cu fitness mic sunt aproape nule. Pentru a evita aceasta situatie, se ordoneaza cromozomii crescator dupa fitness, apoi se renumeroteaza cu numere intregi din intervalul [1,..,dimensiunea populatiei]. Cromozomul cu fitness-ul cel mai mic are numarul 1 etc., iar cromozomul cu fitness-ul cel mai mare are numarul egal cu dimensiunea populatiei. Aceste numere se considera fitness-uri si pe ele se aplica selectia rotii de ruleta. Observam ca cromozomii cu fitness-ul cel mai mare au tot cele mai mari sanse de a fi alesi, dar de data aceasta nu mai sunt asa mari in comparatie cu sansele celorlalti.
d) Selectia cu starea consolidata Aceasta nu este o metoda particulara. Ideea esentiala este urmatoarea: cromozomii
nou generati vor inlocui, daca sunt mai buni, o parte din cromozomii vechii populatii. In acest fel nu mai este necesar sa se lucreze cu mai multe populatii deodata, ci doar cu una singura.
e) Elitism Cand cream o noua populatie prin incrucisare si mutatii, exista o sansa mare de a
pierde cei mai buni cromozomi. De aceea se recomanda copierea celor mai buni cromozomi in noua populatie, fara a-i schimba. Acest proces se numeste elitism si el creste rapid performantele algoritmilor genetici.
5) Incrucisarea (crossover)
Incrucisarea depinde de tipul de codificare a cromozomilor si de problema particulara pe care o rezolvam. Iata cateva exemple:
8
Codificarea binara a) Incrucisare intr-un singur punct
Un punct de incrucisare este ales. Din primul parinte este copiata secventa de la inceput pana la punctul de incrucisare, iar din al doilea parinte este copiata secventa de la punctul de incrucisare pana la final.
11001011+110111111 110011111 b) Incrucisarea in doua puncte
Sunt alese doua puncte de incrucisare. Secventa dintre cele doua puncte este aleasa dintr-unul din parinti, iar ce a ramas din celalalt parinte:
11001001+1101111111011101 c) Incrucisarea uniforma
Bitii sunt copiati aleator din primul si al doilea parinte.
11001011+1101110111011111
d) Incrucisarea aritmetica Operatii aritmetice sunt efectuate pentru a crea noi urmasi.
11001011+1101111111001001 (AND) Codificarea sub forma de permutare
Metodele folosite aici sunt asemanatoare cu cele de la codificarea binara. Trebuie avuta grija sa se pastreze consistenta permutarii, adica sa nu apara un numar de doua ori, iar altele nici o data.
(1 2 3 4 5 6 7 8 9)+(4 5 3 6 8 9 7 2 1)(1 2 3 4 5 6 8 9 7) Codificarea sub forma de valoare
Metodele de la codificarea binara pot fi folosite si aici. Observatii
Probabilitatea de incrucisare indica cat de des trebuie sa apara aceasta operatie intr-o populatie. De obicei are valoare mare, cuprinsa intre 60% si 90%.
Metodele de incrucisare prezentate mai sus sunt destul de generale. De obicei sunt alese metode specifice problemei care se doreste a fi rezolvata si care genereaza o populatie mai buna. Spre exemplu in cazul problemei generarii unei componente intern stabile maximale (submultime de noduri a unui graf neorientat cu un numar maxim de elemente cu proprietatea ca oricare doua noduri din submultime nu sunt legate printr-o muchie) se aleg doi cromozomi care codifica doua componente intern stabile. Aceste componente sunt de fapt multimi, reprezentate ca un sir de biti. In acest caz se poate folosi, de exemplu incrucisarea intr-un singur punct, sau cu doua puncte, dar s-ar putea ca
9
in acest caz componentele noi formate sa fie mai mici decat parintii lor. De aceea putem lua unul din parinti si ii vom adauga noduri din al doilea parinte, rezultand in acest fel un cromozom cu fitness-ul mai mare sau egal decat cel al parintilor. Este repetata aceeasi operatie si pentru celalalt parinte. Acest tip de incrucisare se numeste incrucisare inteligenta.
6) Mutatia
Mutatia apare in principal pentru a evita caderea solutiilor intr-un optim local. Efectuarea de prea multe ori a acestei operatii va transforma algoritmul intr-o cautare aleatoare in spatiul solutiilor posibile. De aceea probabilitatea de mutatie trebuie sa fie mica, circa 0,5-1%.
Codificarea binara a) Inversarea bitilor
Bitii selectati sunt inversati 10.
1100110001 b) Interschimbarea bitilor
Se aleg doi biti si se schimba valorile intre ei.
1100100110001101 Codificarea sub forma de permutare a) Transpozitie
Este efectuata o transpozitie asupra permutarii respective. Acest lucru este echivalent cu interschimbarea bitilor de la codificarea binara.
(1 2 3 4 5 6 8 9 7)(1 8 3 4 5 6 2 9 7)
Codificarea sub forma de valori
Un numar mic este adaugat sau scazut din valorile selectate. (1.29 5.68 2.86 4.11 5.55)(1.29 5.68 2.73 4.22 5.55)
7) Cand se termina algoritmul? Algoritmii genetici se termina, de obicei, dupa ce s-a creat un numar predefinit de
populatii noi. In alte cazuri se poate determina daca solutia s-a imbunatatit de la o populatie la alta. In caz afirmativ se continua cu creerea de noi populatii, in caz negativ se afiseaza cel mai bun cromozom din populatia curenta.
10
Cap.III Implementarea algoritmului
Dupa cele doua capitole pregatitoare suntem in masura de a da o forma generala a programului ce rezolva o problema prin algoritmi genetici.
Vom incepe prin a da forma generala a programului principal, forma care sufera foarte mici modificari de la o problema la alta.
Comentariile la nivel de cod sursa sunt suficiente pentru a intelege mecanismul algoritmului.
void main() { int i; Citire(); /*citeste datele de intrare ale problemei*/ randomize(); InitializeazaPopulatie(); /*genereaza populatia initiala*/ OrdoneazaDupaFitness(); /*ordoneaza cromozomii descrescator(crescator) dupa fitness*/ for(i=1;i<=MaxIteratii;i++) /*i>MaxIteratii este conditia de iesire din program, i fiind echivalentul lui t din pseudocod*/ { NrPop=0;
/*variabila globala care contorizeaza numarul de cromozomi adaugati la noua populatie*/ Elitism(MaxElitism); /*copie cei mai buni MaxElitism cromozomi din populatia veche in cea noua*/ for(co=1;co<=MaxCrossover;co++) /*MaxCrossover este o constanta ce arata numarul de incrucisari care au loc intr-o generatie*/ { SelectieParinti(r1,r2); /*selecteaza 2 cromozomi care se vor incrucisa*/
Crossover(PopulatieVeche[r1],PopulatieVeche[r2], PopulatieNoua[++NrPop],PopulatieNoua[++NrPop]);
/*se incruciseaza cei doi cromozomi*/ } MutaRestul(MaxPopulatie-NrPop);
/*completeaza populatia noua cu cromozomi din populatia veche pana cand ele au acelasi numar de cromozomi(=MaxPopulatie)*/
for(co=1;co<=MaxPopulatie;co++) PopulatieVeche[co]=PopulatieNoua[co];
/*inlocuieste populatia veche cu cea noua*/ for(co=1;co<=MaxMutatie;co++) Mutatie(PopulatieNoua[1+random(MaxPopulatie)]); /*modifica prin mutatie un numar de MaxMutatie cromozomi*/ CalculFitness();
/*calculeaza fitness-ul fiecarui cromozom din populatia noua*/ OrdoneazaDupaFitness(); } Afiseaza();
11
/*afiseaza cea mai buna solutie gasita*/ }
Algoritmii genetici au o structura foarte generala, care permite folosirea lor pentru
majoritatea problemelor. Ceea ce se schimba sunt urmatoarele: - codificarea cromozomilor; - initializarea populatiei; - incrucisarea; - mutatia. Vom da in continuare sursa completa ce implementeaza forma generala a
programului. Pentru o mai buna lizibilitate a codului, toate functiile care se folosesc in acest program au fost mai intai declarate prin antetul lor inaintea programului principal, si dezvoltate apoi dupa acesta. Inca o data, comentariile la nivelul codului sursa sunt suficiente pentru a intelege ce se intampla.
#include<iostream.h> #include<conio.h> #include<stdlib.h> /*aici isi au prototipul functiile randomize() si random(int)*/ const MaxPopulatie=100, /*numarul de cromozomi in populatie*/ MaxIteratii=100, /*numarul de iteratii ale algoritmului*/ MaxElitism=2, /*cati cromozomi sunt copiati prin elitism*/ MaxCrossover=37, /*de cate ori apare incrucisarea intr-o populatie*/ MaxMutatie=1; /*de cate ori apare mutatia intr-o populatie*/ typedef struct{ int gena[22]; /*depinde de la problema la problema*/ float fitness; }TCromozom; /*tipul care codifica un cromozom*/ typedef TCromozom TPopulatie[MaxPopulatie+1]; /*tipul care codifica o populatie*/ TCromozom CelMaiBunCromozom; /*cea mai buna solutie in orice moment*/ TPopulatie PopulatieVeche, PopulatieNoua; /*se lucreaza cu doua populatii*/ int i,j,k,contor,co,r1,r2; int NrPop; void citire(); void CalculFitness(); void InitializeazaPopulatie(); void Elitism(int NrMutati); void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2); void Mutatie(TCromozom &mutant); void MutaRestul(int NrMutati); void OrdoneazaDupaFitness(); void SelectieParinti(int &r1, int &r2);
12
void Afiseaza(); void main() { /*programul principal dat mai sus*/ } void citire() { /*se citesc datele de intrare*/ } void InitializeazaPopulatie() { int i,j; for(i=1;i<=MaxPopulatie;i++) /*sunt initializati cromozomii din populatie*/ CalculFitness(); CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void CalculFitness() { /*fitness-ul poate fi calculat si in momentul in care se creeaza populatia*/ } void Elitism(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[MaxPopulatie-i+1]; } void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2) { /*incrucisarea cromozomilor parinti g1 si g2 din care rezulta doi cromozomi fii rez1 si rez2*/ } void Mutatie(TCromozom &mutant) { /*se efectueaza o mutatie asupra unui cromozom ales aleator si se returneaza cromozomul mutant*/ } void MutaRestul(int NrMutati) { /*dupa ce s-a efectuat incrucisarea, mutatia si elitismul mai raman NrMutati pozitii libere in noua populatie care vor fi completate cu cromozomi alesi aleator din vechea populatie*/ int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]= PopulatieVeche[1+random(MaxPopulatie-MaxElitism)]; } void OrdoneazaDupaFitness() { /*ordonarea cromozomilor dintr-o populatie crescator dupa fitness prin metoda bulelor*/ int i,sw=1; TCromozom aux; while (sw) {
13
sw=0; for(i=1;i<=MaxPopulatie-1;i++) if (PopulatieVeche[i].fitness>PopulatieVeche[i+1].fitness) { aux=PopulatieVeche[i]; PopulatieVeche[i]=PopulatieVeche[i+1]; PopulatieVeche[i+1]=aux; sw=1; } } /*cautarea unei solutii mai bune si retinerea ei*/ if (PopulatieVeche[MaxPopulatie].fitness> CelMaiBunCromozom.fitness) CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void SelectieParinti(int &r1, int &r2) { /*selecteaza doi parinti din populatie folosind una din metodele descrise in capitolul II*/ } void Afiseaza() { /*se va afisa CelMaiBunCromozom*/ }
Sa vedem cum implementam selectia. Metodele cele mai importante pe care le-am prezentat mai sus sunt:
1. Selectia uniforma void SelectieParintiUniforma(int &r1, int &r2) { r1=1+random(MaxPopulatie); r2=1+random(MaxPopulatie); } 2. Selectia folosind ruleta ponderata void SelectieParintiAranjata(int &r1, int &r2) { int s=0,r; for(i=1;i<=MaxPopulatie;i++) s+=PopulatieVeche[i].fitness; /*pentru primul parinte*/ r=1+random(s); r1=0; while (r>0) { r1++; r-=PopulatieVeche[r1].fitness; } /*pentru al doilea parinte*/ r=1+random(s); r2=0; while (r>0) { r2++;
14
r-=PopulatieVeche[r2].fitness; } } 3. Selectia aranjata void SelectieParintiAranjata(int &r1, int &r2) { int s,r; s=MaxPopulatie*(MaxPopulatie+1)/2; /*pentru primul parinte*/ r=1+random(s); r1=0; while (r>0) { r1++; r-=r1; } /*pentru al doilea parinte*/ r=1+random(s); r2=0; while (r>0) { r2++; r-=r2; } }
15
Cap.IV Aplicatii 1. Ecuatie diofanica
Se citeste de la tastatura un numar natural nenul n si coeficientii naturali a1,a2,…,an si
b ai ecuatiei diofanice a1x1+a2x2+…+anxn=b. Se cere sa se gaseasca o solutie naturala a ecuatiei date.
Analiza problemei
0) Datele de intrare
n – int; a – vector de tip int; b – int.
1) Codificarea cromozomilor Vom folosi codificarea sub forma de valoare. Fiecare cromozom va contine n biti,
un bit oarecare i reprezentand valoarea lui xi. Codificarea tipului cromozom este urmatoarea:
typedef struct{ int gena[15]; float fitness; }TCromozom; 2) Populatia initiala
Generarea populatiei initiale are o importanta foarte mare in cadrul acestui algoritm, de aceea alegerea multimii din care se vor genera aleator cromozomii populatiei initiale trebuie sa fie facuta cu atentie. In cadrul problemei de fata observam ca exista sanse mari ca o solutie x1,x2,…,xn sa fie formata din numere ce se afla in apropierea valorii b/(a1+a2+…+an). Pentru ca populatia initiala sa contina cromozomi formati din numere ce se afla in jurul acestei valori, solutiile vor fi generate aleator din multimea {0,1,…,[2*b/(a1+a2+…+an)]}. Secventa care codifica generarea populatiei initiale este:
for(i=1;i<=MaxPopulatie;i++) for(j=1;j<=MaxGena;j++) PopulatieVeche[i].gena[j]=random(2*b/InitVar); unde InitVar reprezinta suma coeficientilor necunoscutelor si se calculeaza la citirea lor. 3) Fitness
Un cromozom codifica o solutie (x1,x2,…,xn). Fitness-ul lui va fi dat de expresia |V-b|, unde V reprezinta valoarea expresiei a1x1+a2x2+…+anxn. Evident, cromozomii mai buni vor fi cei cu fitness-ul mai mic.
16
4) Selectarea cromozomilor parinti Cromozomii formati intr-o populatie se ordoneaza descrescator dupa fitness. Metoda
de selectie folosita este cea prin selectie aranjata.
5) Crossover-ul Incrucisarea se realizeaza intr-un singur punct, acesta fiind ales aleator.
r=1+random(MaxGena-1); for(i=1;i<=MaxGena;i++) if (i<=r) { rez1.gena[i]=g1.gena[i]; rez2.gena[i]=g2.gena[i]; } else { rez1.gena[i]=g2.gena[i]; rez2.gena[i]=g1.gena[i]; }
6) Mutatia
Mutatia are o probabilitate de 1% si se realizeaza prin adaugarea sau scaderea unei valori aleatoare mici la fiecare din genele cromozomului.
{ r1=1+random(b/(10*InitVar)); r2=random(2); if (r2) mutant.gena[i]+=r1; else mutant.gena[i]-=r1; }
Valoarea b/(10*InitVar) a fost determinata in mod euristic.
7) Cel mai bun cromozom Se initializeaza in functia InitializeazaPopulatie() si intr-o generatie se calculeaza in
functia OrdoneazaDupaFitness(), dupa ordonare, astfel: if (PopulatieVeche[MaxPopulatie].fitness< CelMaiBunCromozom.fitness) CelMaiBunCromozom=PopulatieVeche[MaxPopulatie];
In continuare vom da codul sursa complet care rezolva aceasta problema.
#include<iostream.h> #include<conio.h> #include<stdlib.h> #include<math.h> const MaxPopulatie=100, MaxIteratii=1000, MaxElitism=3, MaxCrossover=35, MaxMutatie=1;
17
typedef struct{ long int gena[22]; float fitness; }TCromozom; typedef TCromozom TPopulatie[MaxPopulatie+1]; TCromozom CelMaiBunCromozom; TPopulatie PopulatieVeche, PopulatieNoua; int i,j,k,contor,co,r1,r2; int NrPop, MaxGena; int InitVar=0; int a[50]; long int b; void citire(); void CalculFitness(); void InitializeazaPopulatie(); void Elitism(int NrMutati); void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2); void Mutatie(TCromozom &mutant); void MutaRestul(int NrMutati); void OrdoneazaDupaFitness(); void SelectieParintiAranjata(int &r1, int &r2); void Afiseaza(); void main() { int i,sw=1; citire(); randomize(); InitializeazaPopulatie(); OrdoneazaDupaFitness(); for(i=1;i<=MaxIteratii&&sw;i++) { NrPop=0; Elitism(MaxElitism); for(co=1;co<=MaxCrossover;co++) { SelectieParintiAranjata(r1,r2); Crossover(PopulatieVeche[r1],PopulatieVeche[r2], PopulatieNoua[++NrPop],PopulatieNoua[++NrPop]); } MutaRestul(MaxPopulatie-NrPop); for(co=1;co<=MaxPopulatie;co++) PopulatieVeche[co]=PopulatieNoua[co]; for(co=1;co<=MaxMutatie;co++) Mutatie(PopulatieNoua[1+random(MaxPopulatie)]); CalculFitness(); OrdoneazaDupaFitness(); if (CelMaiBunCromozom.fitness==0) sw=0; } Afiseaza(); } void citire() { int i; clrscr(); cout<<"Numarul de necunoscute:"; cin>>MaxGena;
18
for(i=1;i<=MaxGena;i++) { cout<<"a["<<i<<"]="; cin>>a[i]; InitVar+=a[i]; } cout<<"b="; cin>>b; } void InitializeazaPopulatie() { int i,j; for(i=1;i<=MaxPopulatie;i++) for(j=1;j<=MaxGena;j++) PopulatieVeche[i].gena[j]=random(2*(b+1)/InitVar); CalculFitness(); CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void CalculFitness() { int i,j; float s; for(i=1;i<=MaxPopulatie;i++) { s=0; for(j=1;j<=MaxGena;j++) s=s+a[j]*PopulatieVeche[i].gena[j]; PopulatieVeche[i].fitness=abs(s-b); } } void Elitism(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[MaxPopulatie-i+1]; } void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2) { int i,r; r=1+random(MaxGena-1); for(i=1;i<=MaxGena;i++) if (i<=r) { rez1.gena[i]=g1.gena[i]; rez2.gena[i]=g2.gena[i]; } else { rez1.gena[i]=g2.gena[i]; rez2.gena[i]=g1.gena[i]; } } void Mutatie(TCromozom &mutant) { int r1,r2,i; for(i=1;i<=MaxGena;i++)
19
{ r1=1+random(b/(10*InitVar)); r2=random(2); if (r2) mutant.gena[i]+=r1; else mutant.gena[i]-=r1; } } void MutaRestul(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[1+random(MaxPopulatie-MaxElitism)]; } void OrdoneazaDupaFitness() { int i,sw=1; TCromozom aux; while (sw) { sw=0; for(i=1;i<=MaxPopulatie-1;i++) if (PopulatieVeche[i].fitness<PopulatieVeche[i+1].fitness) { aux=PopulatieVeche[i]; PopulatieVeche[i]=PopulatieVeche[i+1]; PopulatieVeche[i+1]=aux; sw=1; } } if (PopulatieVeche[MaxPopulatie].fitness<CelMaiBunCromozom.fitness) CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void SelectieParintiAranjata(int &r1, int &r2) { int s,r; s=MaxPopulatie*(MaxPopulatie+1)/2; r=1+random(s); r1=0; while (r>0) { r1++; r-=r1; } r=1+random(s); r2=0; while (r>0) { r2++; r-=r2; } } void Afiseaza() { int i; if (CelMaiBunCromozom.fitness==0) cout<<"O solutie este:"<<endl;
20
else cout<<"Cea mai apropiata solutie gasita are o eroare de "<< (CelMaiBunCromozom.fitness/b)*100<<"%"<<endl<<"Aceasta este:"; for(i=1;i<=MaxGena;i++) cout<<CelMaiBunCromozom.gena[i]<<" "; getch(); }
Exemplu
Pentru n=10 si urmatoarele valori ale coeficientilor:
a1 a2 a3 a4 a5 A6 a7 a8 a9 a10 b
147 258 369 123 456 789 159 753 268 842 10000
programul afiseaza la trei apeluri succesive urmatoarele solutii:
- 2 3 3 3 3 2 3 2 0 3 cu o eroare de 0.01%; - 2 3 2 1 3 1 2 3 3 3 cu o eroare de 0.07%; - 1 0 3 2 2 3 3 3 3 2 cu o eroare de 0.03%.
2. Problema discreta a rucsacului
Cu ajutorul unui rucsac avand capacitatea maxim admisibila G trebuie sa se
transporte o serie de obiecte din n disponibile avand greutatile g1,g2,…,gn si utilitatile c1,c2,…,cn. Presupunand ca obiectele nu se pot diviza, gasiti o metoda optima de umplere a rucsacului (o solutie care maximizeaza utilitatea totala a obiectelor).
Analiza problemei
0) Datele de intrare
Capacitate – float; NrObiecte – int; GreutateObiect – vector de tip float; UtilitateObiect – vector de tip float.
1) Codificarea cromozomilor Cromozomii vor fi codificati binar. Fiecare cromozom va contine NrObiecte biti, un
bit oarecare i luand valoarea 1 daca obiectul i se gaseste in rucsac si 0 in caz contrar. Codificarea tipului cromozom este urmatoarea:
typedef struct{ int gena[15]; float fitness; }TCromozom;
21
2) Populatia initiala Cromozomii fiind codificati binar, populatia initiala se va genera prin completarea
aleatoare a bitilor cromozomilor initiali cu valorile 0 sau 1. Secventa de instructiuni care realizeaza acest lucru este urmatoarea:
for(i=1;i<=MaxPopulatie;i++) for(j=1;j<=MaxGena;j++) //MaxGena=NrObiecte PopulatieVeche[i].gena[j]=random(2); 3) Fitness
O solutie este cu atat mai buna cu cat utilitatea totala pe care o are este mai mare, deci la prima vedere utilitatea totala ar trebui sa fie fitness-ul unui cromozom. In afara de aceasta conditie insa, mai avem una: greutatea totala a obiectelor trebuie sa fie mai mica decat capacitatea rucsacului. Notand cu Ut – utilitatea totala a obiectelor unei solutii si cu Gt – greutatea totala a lor, vom cauta sa avem o solutie cu Ut cat mai mare si cu |Capacitate-Gt| cat mai apropiat de 0.
Vom lucra cu 3 fitness-uri definite astfel: - fitness1 = Ut; - fitness2 = Gt; - fitness = |Capacitate-Gt|/Ut.
Primele doua fitness-uri vor folosi la aflarea celui mai bun cromozom dintr-o generatie, iar cel de-al treilea este cel dupa care facem ordonarea (vom cauta sa obtinem cromozomi cu fitness-ul cat mai mic). Din aceasta cauza tipul cromozom va trebui modificat prin inlocuirea liniei “float fitness;” cu “float fitness1, fitness2, fitness;”. In continuare vom da secventa ce codifica calcularea fitness-urilor cromozomilor dintr-o populatie.
for(i=1;i<=MaxPopulatie;i++) { f1=f2=0; for(j=1;j<=MaxGena;j++) { f1=f1+PopulatieVeche[i].gena[j]*UtilitateObiect[j]; f2=f2+PopulatieVeche[i].gena[j]*GreutateObiect[j]; } PopulatieVeche[i].fitness1=f1; PopulatieVeche[i].fitness2=f2; f2=abs(Capacitate-f2); if (f1) PopulatieVeche[i].fitness=f2/f1; else PopulatieVeche[i].fitness=100; }
Conditia de final apare pentru ca exista posibilitatea ca la initializare sau prin mutatii sa se formeze cromozomi cu toate genele egale cu 0, avand astfel fitness1=0.
4) Selectarea cromozomilor parinti
Cromozomii formati intr-o populatie se ordoneaza descrescator dupa fitness. Metoda de selectie folosita este cea prin selectie aranjata.
22
5) Crossover-ul Incrucisarea se realizeaza intr-un singur punct, acesta fiind ales aleator.
r=1+random(MaxGena-1); for(i=1;i<=MaxGena;i++) if (i<=r) { rez1.gena[i]=g1.gena[i]; rez2.gena[i]=g2.gena[i]; } else { rez1.gena[i]=g2.gena[i]; rez2.gena[i]=g1.gena[i]; }
6) Mutatia
Mutatia are o probabilitate de 1% si se realizeaza prin inversarea bitilor.
for(i=1;i<=MaxGena;i++) if (mutant.gena[i]==1) mutant.gena[i]=0; else mutant.gena[i]=1; 7) Cel mai bun cromozom
Se initializeaza in functia InitializeazaPopulatie() si intr-o generatie se calculeaza in functia OrdoneazaDupaFitness(), dupa ordonare, astfel: for(i=1;i<=MaxPopulatie;i++) if ((PopulatieVeche[i].fitness1>CelMaiBunCromozom.fitness1)&&(PopulatieVeche[i].fitness2<=Capacitate)) CelMaiBunCromozom=PopulatieVeche[i];
In continuare vom da codul sursa complet care rezolva aceasta problema.
#include<iostream.h> #include<conio.h> #include<stdlib.h> #include<math.h> const MaxPopulatie=100, MaxIteratii=1000, MaxElitism=2, MaxCrossover=20, MaxMutatie=1; typedef struct{ int gena[15]; float fitness1, fitness2, fitness; }TCromozom; typedef TCromozom TPopulatie[MaxPopulatie+1]; TCromozom CelMaiBunCromozom; TPopulatie PopulatieVeche, PopulatieNoua; int i,j,k,contor,co,r1,r2; int NrPop, NrObiecte, MaxGena; float Capacitate, GreutateObiect[100], UtilitateObiect[100]; void citire();
23
void CalculFitness(); void InitializeazaPopulatie(); void Elitism(int NrMutati); void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2); void Mutatie(TCromozom &mutant); void MutaRestul(int NrMutati); void OrdoneazaDupaFitness(); void SelectieParintiAranjata(int &r1, int &r2); void Afiseaza(); void main() { int i; citire(); randomize(); InitializeazaPopulatie(); OrdoneazaDupaFitness(); for(i=1;i<=MaxIteratii;i++) { NrPop=0; Elitism(MaxElitism); for(co=1;co<=MaxCrossover;co++) { SelectieParintiAranjata(r1,r2); Crossover(PopulatieVeche[r1],PopulatieVeche[r2], PopulatieNoua[++NrPop],PopulatieNoua[++NrPop]); } MutaRestul(MaxPopulatie-NrPop); for(co=1;co<=MaxPopulatie;co++) PopulatieVeche[co]=PopulatieNoua[co]; for(co=1;co<=MaxMutatie;co++) Mutatie(PopulatieNoua[1+random(MaxPopulatie)]); CalculFitness(); OrdoneazaDupaFitness(); } Afiseaza(); } void citire() { int i; clrscr(); cout<<"Capacitatea rucsacului:"; cin>>Capacitate; cout<<"Numarul de obiecte:"; cin>>NrObiecte; MaxGena=NrObiecte; for(i=1;i<=NrObiecte;i++) { cout<<"Greutate obiect "<<i<<":"; cin>>GreutateObiect[i]; cout<<"Utilitate obiect "<<i<<":"; cin>>UtilitateObiect[i]; } } void InitializeazaPopulatie() { int i,j;
24
for(i=1;i<=MaxPopulatie;i++) for(j=1;j<=MaxGena;j++) PopulatieVeche[i].gena[j]=random(2); CalculFitness(); CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void CalculFitness() { int i,j; float f1,f2; for(i=1;i<=MaxPopulatie;i++) { f1=f2=0; for(j=1;j<=MaxGena;j++) { f1=f1+PopulatieVeche[i].gena[j]*UtilitateObiect[j]; f2=f2+PopulatieVeche[i].gena[j]*GreutateObiect[j]; } PopulatieVeche[i].fitness1=f1; PopulatieVeche[i].fitness2=f2; f2=abs(Capacitate-f2); if (f1) PopulatieVeche[i].fitness=f2/f1; else PopulatieVeche[i].fitness=100; } } void Elitism(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[MaxPopulatie-i+1]; } void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2) { int i,r; r=1+random(MaxGena-1); for(i=1;i<=MaxGena;i++) if (i<=r) { rez1.gena[i]=g1.gena[i]; rez2.gena[i]=g2.gena[i]; } else { rez1.gena[i]=g2.gena[i]; rez2.gena[i]=g1.gena[i]; } } void Mutatie(TCromozom &mutant) { int i; for(i=1;i<=MaxGena;i++) if (mutant.gena[i]==1) mutant.gena[i]=0; else mutant.gena[i]=1; } void MutaRestul(int NrMutati) {
25
int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[1+random(MaxPopulatie-MaxElitism)]; } void OrdoneazaDupaFitness() { int i,sw=1; TCromozom aux; while (sw) { sw=0; for(i=1;i<=MaxPopulatie-1;i++) if (PopulatieVeche[i].fitness<PopulatieVeche[i+1].fitness) { aux=PopulatieVeche[i]; PopulatieVeche[i]=PopulatieVeche[i+1]; PopulatieVeche[i+1]=aux; sw=1; } } for(i=1;i<=MaxPopulatie;i++) if ((PopulatieVeche[i].fitness1>CelMaiBunCromozom.fitness1) &&(PopulatieVeche[i].fitness2<=Capacitate)) CelMaiBunCromozom=PopulatieVeche[i]; } void SelectieParintiAranjata(int &r1, int &r2) { int s,r; s=MaxPopulatie*(MaxPopulatie+1)/2; r=1+random(s); r1=0; while (r>0) { r1++; r-=r1; } r=1+random(s); r2=0; while (r>0) { r2++; r-=r2; } } void Afiseaza() { int i; cout<<"O umplere optima a rucsacului este formata din obiectele:"; for(i=1;i<=MaxGena;i++) if (CelMaiBunCromozom.gena[i]) cout<<i<<" "; cout<<endl; cout<<"Ele au greutatea "<<CelMaiBunCromozom.fitness2<< " si utilitatea "<<CelMaiBunCromozom.fitness1; getch(); }
26
Exemplu
Pentru urmatoarele date de intrare:
Capacitate=22; NrObiecte=6;
Obiect 1 2 3 4 4 6 Utilitate 500 770 690 1000 480 630 Greutate 5 7 6 8 4 6
Programul va afisa: O umplere optima a rucsacului este formata din obiectele:2 3 4. Ele au greutatea 21 si utilitatea 2460.
De remarcat faptul ca pentru aceleasi date de intrare un algoritm greedy care pune obiectele in rucsac in ordinea descrescatoare a raportului utilitate/greutate va afisa: O umplere optima a rucsacului este formata din obiectele:3 4 5. Ele au greutatea 18 si utilitatea 2170.
3. Problema comis-voiajorului
Un comis-voiajor are de vizitat un numar de n orase. Oricare doua orase sunt legate
intre ele si costul deplasarii de la orasul i la orasul j este citit in elemetul ai,j al matricei Anxn. Comis-voiajorul pleaca din orasul 1 si trebuie sa treaca prin toate celelalte orase o singura data, intorcandu-se in final in orasul 1. Gasiti un drum care minimizeaza costul total al deplasarii.
Analiza problemei
0) Datele de intrare n – numarul de orase; a – matricea costurilor.
1) Codificarea cromozomilor Un cromozom va fi reprezentat printr-o “permutare” de tipul 1 (2) (3) … (n) 1. Codificarea tipului cromozom este urmatoarea:
typedef struct{ int gena[15]; int fitness; }TCromozom; Orice cromozom va avea gena[1]=gena[MaxGena]=1.
27
2) Populatia initiala
Dificultatea in aceasta etapa consta in generarea unor “permutari” in mod aleator. Pentru aceasta ne vom folosi de o functie care genereaza prin backtracking o permutare. Functia are prototipul void GenereazaPermutare(int i, int j), unde i va reprezenta indicele cromozomului care este generat iar j este un parametru care sporeste caracterul aleatoriu al permutarii.
Secventa care initializeaza populatia este:
for(i=1;i<=MaxPopulatie;i++) GenereazaPermutare(i, 1+random(50)); unde functia GenereazaPermutare(i,j) este: void GenereazaPermutare(int i, int j) { int k=2; st[1]=1; st[2]=random(MaxGena-1); while(j&&(k>1)) { if (k==MaxGena) { CopieSolutie(i); j--;k--; } else if (st[k]<MaxGena-1) { st[k]++; if (Valid(k)) st[++k]=0; } else k--; } }
Functia CopieSolutie(int i) retine o posibila permutare.
3) Fitness Fitness-ul unui cromozom va reprezenta costul total al drumului pe care il codifica.
Astfel, vom cauta sa obtinem cromozomi cu un fitness cat mai mic.
for(i=1;i<=MaxPopulatie;i++) { PopulatieVeche[i].fitness=0; for(j=1;j<MaxGena;j++) PopulatieVeche[i].fitness+= a[PopulatieVeche[i].gena[j]][PopulatieVeche[i].gena[j+1]]; }
4) Selectarea cromozomilor parinti
Cromozomii formati intr-o populatie se ordoneaza descrescator dupa fitness. Metoda de selectie folosita este cea prin selectie aranjata.
28
5) Crossover-ul
O alta dificultate a acestei probleme este gasirea unui mod de incrucisare care pastreaza consistenta permutarii dupa transformare. Acest lucru poate fi realizat prin urmatoarea forma de incrucisare: cei doi cromozomi parinti ( si ) se inmultesc intre ei prin regula de inmultire dintre permutari, mai intai primul cu al doilea si apoi invers. Se vor obtine doi cromozomi copii x si x. Avand in vedere faptul ca inmultirea permutarilor este in general necomutativa, cei doi cromozomi rezultati vor fi diferiti.
for(i=1;i<=MaxGena;i++) { rez1.gena[i]=g1.gena[g2.gena[i]]; rez2.gena[i]=g2.gena[g1.gena[i]]; } 6) Mutatia
Mutatia are o probabilitate de 1-3% si se realizeaza printr-o transpozitie (i,j) asupra cromozomului dat, unde i si j sunt doua numere diferite generate aleator si cuprinse intre 2 si n (MaxGena=n+1).
{ r1=1+random(MaxGena-1); do r2=1+random(MaxGena-1); while (r1==r2); aux=mutant.gena[r1]; mutant.gena[r1]=mutant.gena[r2]; mutant.gena[r2]=aux; } 7) Cel mai bun cromozom
Se initializeaza in functia InitializeazaPopulatie() si intr-o generatie se calculeaza in functia OrdoneazaDupaFitness().
In continuare vom da codul sursa complet.
#include<iostream.h> #include<conio.h> #include<stdlib.h> #include<math.h> const MaxPopulatie=100, MaxIteratii=200, MaxElitism=4, MaxCrossover=36, MaxMutatie=3; typedef struct{ int gena[33]; float fitness; }TCromozom; typedef TCromozom TPopulatie[MaxPopulatie+1]; TCromozom CelMaiBunCromozom; TPopulatie PopulatieVeche, PopulatieNoua; int i,j,k,co,r1,r2, st[100]; int NrPop, MaxGena, a[30][30];
29
void Citire(); void CalculFitness(); void GenereazaPermutare(int i, int j); int Valid(int k); void CopieSolutie(int i); void InitializeazaPopulatie(); void Elitism(int NrMutati); void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2); void Mutatie(TCromozom &mutant); void MutaRestul(int NrMutati); void OrdoneazaDupaFitness(); void SelectieParintiAranjata(int &r1, int &r2); void Afiseaza(); void main() { int i; Citire(); randomize(); InitializeazaPopulatie(); OrdoneazaDupaFitness(); for(i=1;i<=MaxIteratii;i++) { NrPop=0; Elitism(MaxElitism); for(co=1;co<=MaxCrossover;co++) { SelectieParintiAranjata(r1,r2); Crossover(PopulatieVeche[r1],PopulatieVeche[r2], PopulatieNoua[++NrPop],PopulatieNoua[++NrPop]); } MutaRestul(MaxPopulatie-NrPop); for(co=1;co<=MaxPopulatie;co++) PopulatieVeche[co]=PopulatieNoua[co]; for(co=1;co<=MaxMutatie;co++) Mutatie(PopulatieNoua[1+random(MaxPopulatie)]); CalculFitness(); OrdoneazaDupaFitness(); } Afiseaza(); } void Citire() { int i,j,n; clrscr(); cout<<"Numarul de orase:"; cin>>n; MaxGena=n+1; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { cout<<"Costul deplasarii "<<i<<"<->"<<j<<" :"; cin>>a[i][j]; a[j][i]=a[i][j]; } a[i][i]=0;
30
} } void GenereazaPermutare(int i, int j) { int k=2; st[1]=1; st[2]=random(MaxGena-1); while(j&&(k>1)) { if (k==MaxGena) { CopieSolutie(i); j--;k--; } else if (st[k]<MaxGena-1) { st[k]++; if (Valid(k)) st[++k]=0; } else k--; } } void CopieSolutie(int i) { int j; for(j=2;j<MaxGena;j++) PopulatieVeche[i].gena[j]=st[j]; PopulatieVeche[i].gena[1]=PopulatieVeche[i].gena[MaxGena]=1; } int Valid(int k) { int i,v=1; for(i=1;i<k&&v;i++) if (st[i]==st[k]) v=0; return v; } void InitializeazaPopulatie() { int i; for(i=1;i<=MaxPopulatie;i++) GenereazaPermutare(i, 1+random(50)); CalculFitness(); CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void CalculFitness() { int i,j; for(i=1;i<=MaxPopulatie;i++) { PopulatieVeche[i].fitness=0; for(j=1;j<MaxGena;j++) PopulatieVeche[i].fitness+= a[PopulatieVeche[i].gena[j]][PopulatieVeche[i].gena[j+1]]; } } void Elitism(int NrMutati) {
31
int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[MaxPopulatie-i+1]; } void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2) { int i; for(i=1;i<=MaxGena;i++) { rez1.gena[i]=g1.gena[g2.gena[i]]; rez2.gena[i]=g2.gena[g1.gena[i]]; } } void Mutatie(TCromozom &mutant) { int r1,r2,aux; r1=1+random(MaxGena-1); do r2=1+random(MaxGena-1); while (r1==r2); aux=mutant.gena[r1]; mutant.gena[r1]=mutant.gena[r2]; mutant.gena[r2]=aux; } void MutaRestul(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[1+random(MaxPopulatie-MaxElitism)]; } void OrdoneazaDupaFitness() { int i,sw=1; TCromozom aux; while (sw) { sw=0; for(i=1;i<=MaxPopulatie-1;i++) if (PopulatieVeche[i].fitness<PopulatieVeche[i+1].fitness) { aux=PopulatieVeche[i]; PopulatieVeche[i]=PopulatieVeche[i+1]; PopulatieVeche[i+1]=aux; sw=1; } } if ((PopulatieVeche[MaxPopulatie].fitness<CelMaiBunCromozom.fitness) &&(PopulatieVeche[MaxPopulatie].fitness)) CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void SelectieParintiAranjata(int &r1, int &r2) { int s,r; s=MaxPopulatie*(MaxPopulatie+1)/2; r=1+random(s);
32
r1=0; while (r>0) { r1++; r-=r1; } r=1+random(s); r2=0; while (r>0) { r2++; r-=r2; } } void Afiseaza() { int i; cout<<"Un drum optim este:"; for(i=1;i<=MaxGena;i++) cout<<CelMaiBunCromozom.gena[i]<<" "; cout<<endl; cout<<"Drumul are costul total de: "<<CelMaiBunCromozom.fitness; getch(); }
Exemplu
Pentru urmatoarele date de intrare: n=12; - matricea costurilor - 0 1 2 3 4 5 6 7 8 9 1 2 1 0 3 4 5 6 7 8 9 1 2 3 2 3 0 4 5 6 7 8 9 1 2 3 3 4 4 0 4 5 6 7 8 9 1 2 4 5 5 4 0 3 4 5 6 7 8 9 5 6 6 5 3 0 1 2 3 4 5 6 6 7 7 6 4 1 0 7 8 9 1 2 7 8 8 7 5 2 7 0 3 4 5 6 8 9 9 8 6 3 8 3 0 7 8 9 9 1 1 9 7 4 9 4 7 0 1 2 1 2 2 1 8 5 1 5 8 1 0 3 2 3 3 2 9 6 2 6 9 2 3 0
programul ce rezolva problema prin backtracking va afisa dupa aproximativ 10 min drumul 1 2 10 3 5 8 9 6 7 11 4 12 1 de cost total 26.
Pentru aceleasi date de intrare programul scris mai sus afiseaza la 3 apeluri succesive urmatoarele drumuri: - 1 11 2 10 3 4 12 7 6 9 8 5 1 de cost 29; - 1 2 3 10 6 8 9 5 4 12 7 11 1 de cost 30; - 1 2 11 3 10 8 9 6 7 12 4 5 1 de cost 29.
Timpul mediu de rulare pentru un exemplu este de 2 s.
33
4. Maximul unei functii n-dimensionale Considerandu-se o functie in n nedeterminate definita pe un produs cartezian
[a,b]x[a,b]x..x[a,b] de n intervale identice se cere sa se afle maximul ei si un set de valori din domeniul de definitie pentru care acest maxim este atins.
Analiza problemei
0) Datele de intrare Dat fiind gradul ridicat de dificultate pe care il necesita citirea expresiei functiei de la
tastatura, aceasta va fi scrisa intr-o functie care va returna valoarea ei intr-un set de puncte (x1,x2,…,xn).
Singurele date care se citesc de la tastatura sunt capetele intervalului [a,b]. 1) Codificarea cromozomilor
Dificultatea acestei probleme consta in faptul ca punctele (x1,x2,…,xn) iau valori reale, si deci trebuie sa gasim o modalitate eficienta de codificare a cromozomilor. Daca vom incerca sa codificam o gena a unui cromozom printr-un numar real (un cromozom va contine n gene), vom observa ca prin transformarile cunoscute (crossover, mutatie) nu se obtine un numar multumitor de combinatii, spatiul solutiilor fiind foarte slab acoperit. Codificarea binara ridica iarasi probleme la transformarea unui numar real in baza 2 si reciproc. Cea mai buna solutie in acest caz o reprezinta o imbinare a celor doua metode. O gena va consta dintr-un vector de lungime NrBiti format din cifrele 0 si 1. Astfel o gena va putea codifica (2^NrBiti)-1 numere naturale prin transformarea numarului format din elementele binare ale vectorului intr-un numar din baza 10. Decodificarea unei gene va fi realizata in modul urmator: intervalul [a,b] este impartit in (2^NrBiti)-1 diviziuni. O gena i ce contine un numar y in baza 2 va fi transformata in numarul xi astfel: y xi=a+(b-a)*[y]10/[(2^NrBiti)-1], unde [y]10 reprezinta numarul y in baza 10.
2) Populatia initiala
Va fi creata prin generarea aleatoare de valori binare pentru fiecare vector al fiecarei gene al fiecarui cromozom al populatiei initiale.
3) Fitness Fitness-ul unui cromozom va reprezenta valoarea functiei in punctele (x1,x2,…,xn) codificate de acesta. Petru a-l calcula vom avea nevoie de o functie float transf(int i, int j) care realizeaza decodificarea genei j a cromozomului i. 4) Selectarea cromozomilor parinti
Cromozomii formati intr-o populatie se ordoneaza crescator dupa fitness. Metoda de selectie folosita este cea prin selectie aranjata.
5) Crossover-ul
Incrucisarea se realizeaza intr-un singur punct, acesta fiind ales aleator.
34
6) Mutatia Mutatia are o probabilitate de 1% si se realizeaza prin inversarea valorilor bitilor
tuturor genelor unui cromozom ales in mod aleator. 7) Cel mai bun cromozom
Se initializeaza in functia InitializeazaPopulatie() si intr-o generatie se calculeaza in functia OrdoneazaDupaFitness().
In continuare vom da codul sursa complet al problemei care afla maximul unei functii in 6 nedeterminate, expresia ei aflandu-se in functia float Functia(float Nedet[MaxGena+1]).
#include<iostream.h> #include<conio.h> #include<stdlib.h> #include<math.h> const MaxPopulatie=100, MaxIteratii=200, MaxElitism=3, MaxCrossover=30, MaxMutatie=1, MaxGena=6, NrBiti=15; typedef struct{ int gena[MaxGena+1][NrBiti+1]; float fitness; }TCromozom; typedef TCromozom TPopulatie[MaxPopulatie+1]; TCromozom CelMaiBunCromozom; TPopulatie PopulatieVeche, PopulatieNoua; int i,j,k,contor,co,r1,r2; float LungDiv=0; int NrPop,a,b; void Citire(); float Functia(float Nedet[MaxGena+2]); float Transf(TCromozom g,int j); void CalculFitness(); void InitializeazaPopulatie(); void Elitism(int NrMutati); void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2); void Mutatie(TCromozom &mutant); void MutaRestul(int NrMutati); void OrdoneazaDupaFitness(); void SelectieParintiAranjata(int &r1, int &r2); void Afiseaza(); void main() { int i,j; Citire(); randomize(); InitializeazaPopulatie(); CelMaiBunCromozom.fitness=0; OrdoneazaDupaFitness(); for(i=1;i<=MaxIteratii;i++)
35
{ NrPop=0; Elitism(MaxElitism); for(co=1;co<=MaxCrossover;co++) { SelectieParintiAranjata(r1,r2); Crossover(PopulatieVeche[r1],PopulatieVeche[r2], PopulatieNoua[++NrPop],PopulatieNoua[++NrPop]); } MutaRestul(MaxPopulatie-NrPop); for(co=1;co<=MaxPopulatie;co++) PopulatieVeche[co]=PopulatieNoua[co]; for(co=1;co<=MaxMutatie;co++) Mutatie(PopulatieNoua[1+random(MaxPopulatie)]); CalculFitness(); OrdoneazaDupaFitness(); } Afiseaza(); } void Citire() { int i; clrscr(); cout<<"a="; cin>>a; cout<<"b="; cin>>b; for(i=1;i<=NrBiti;i++) LungDiv=2*LungDiv+1; } float Functia(float Nedet[MaxGena+2]) { float x1,x2,x3,x4,x5,x6; x1=Nedet[1]-1.123; x2=Nedet[2]-1.234; x3=Nedet[3]-1.345; x4=Nedet[4]-1.456; x5=Nedet[5]-1.567; x6=Nedet[6]-1.678; return (1/(1+x1*x1+x2*x2+x3*x3+x4*x4+x5*x5+x6*x6)); } void InitializeazaPopulatie() { int i,j,k; for(i=1;i<=MaxPopulatie;i++) for(j=1;j<=MaxGena;j++) for(k=1;k<=NrBiti;k++) PopulatieVeche[i].gena[j][k]=random(2); CalculFitness(); } float Transf(TCromozom g, int j) { int k; float nr=0,x; for(k=1;k<=NrBiti;k++) nr=2*nr+g.gena[j][k]; x=a+(b-a)*(nr/LungDiv);
36
return x; } void CalculFitness() { int i,j,co; float Nedet[MaxGena+2]; for(i=1;i<=MaxPopulatie;i++) { co=0; for(j=1;j<=MaxGena;j++) { Nedet[++co]=Transf(PopulatieVeche[i],j); } PopulatieVeche[i].fitness=Functia(Nedet); } } void Elitism(int NrMutati) { int i; for(i=1;i<=NrMutati;i++) PopulatieNoua[++NrPop]=PopulatieVeche[MaxPopulatie-i+1]; } void Crossover(TCromozom g1, TCromozom g2, TCromozom &rez1, TCromozom &rez2) { int r,j,k; for(j=1;j<=MaxGena;j++) { r=1+random(NrBiti-1); for(k=1;k<=NrBiti;k++) if (k<=r) { rez1.gena[j][k]=g1.gena[j][k]; rez2.gena[j][k]=g2.gena[j][k]; } else { rez1.gena[j][k]=g2.gena[j][k]; rez2.gena[j][k]=g1.gena[j][k]; } } } void Mutatie(TCromozom &mutant) { int r,j; for(j=1;j<=MaxGena;j++) { r=1+random(NrBiti-1); if (mutant.gena[j][r]) mutant.gena[j][r]=0; else mutant.gena[j][r]=1; } } void MutaRestul(int NrMutati) { int i; for(i=1;i<=NrMutati;i++)
37
PopulatieNoua[++NrPop]=PopulatieVeche[1+random(MaxPopulatie-MaxElitism)]; } void OrdoneazaDupaFitness() { int i,sw=1; TCromozom aux; while (sw) { sw=0; for(i=1;i<=MaxPopulatie-1;i++) if (PopulatieVeche[i].fitness>PopulatieVeche[i+1].fitness) { aux=PopulatieVeche[i]; PopulatieVeche[i]=PopulatieVeche[i+1]; PopulatieVeche[i+1]=aux; sw=1; } } if (PopulatieVeche[MaxPopulatie].fitness>CelMaiBunCromozom.fitness) CelMaiBunCromozom=PopulatieVeche[MaxPopulatie]; } void SelectieParintiAranjata(int &r1, int &r2) { int s,r; s=MaxPopulatie*(MaxPopulatie+1)/2; r=1+random(s); r1=0; while (r>0) { r1++; r-=r1; } r=1+random(s); r2=0; while (r>0) { r2++; r-=r2; } } void Afiseaza() { int i; cout<<"Maximul gasit este:"<<CelMaiBunCromozom.fitness; cout<<endl<<"El este atins pentru valorile:"; for(i=1;i<=MaxGena;i++) { cout<<endl<<"X"<<i<<"="; cout<<Transf(CelMaiBunCromozom,i); } getch(); }
38
Exemplu Pentru a=1, b=2 programul va afisa la trei apeluri succesive:
Apel X1 X2 X3 X4 X5 X6 f 1) 1.125034 1.233894 1.375286 1.456343 1.562487 1.681814 0.999044 2) 1.125248 1.251106 1.341746 1.477798 1.578448 1.753929 0.993365 3) 1.122288 1.234077 1.376080 1.501999 1.499985 1.624378 0.989659
39
Cap.V Consideratii finale
Urmarind exemplele de aplicatii care s-au dat in capitolul anterior putem da niste caracteristici generale ale problemelor pe care le poate rezolva un algoritm genetic. Este recomandat astfel ca problemele date sa aiba un volum mare de date de prelucrat.
Din punctul de vedere al spatiului solutiilor, problemele se impart in 2 categorii:
1. Probleme cu spatiul solutiilor finit. Aici sunt incluse problema discreta a rucsacului si cea a comis-voiajorului. In general,
orice problema care se poate rezolva prin backtracking are si o rezolvare prin algoritmi genetici. Cele doua probleme mentionate mai sus, impreuna cu altele de acest gen, fac parte din categoria problemelor NP-complete, adica a acelor probleme pentru care nu exista la ora actuala algoritmi polinomiali deterministi de rezolvare a lor. Algoritmii genetici reprezinta o alternativa viabila celor deterministi exponentiali care rezolva aceste probleme, pentru ca, spre exemplu, in cazul problemei comis voiajorului, testarea tuturor drumurilor posibile care leaga n orase ar presupune n! operatii matematice. Un tur ce cuprinde 30 de orase ar presupune aproximativ 2.65X1032 operatii. Presupunand ca un procesor ar realiza un miliard de operatii pe secunda, timpul de rezolvare a problemei ar fi in jur de 8,000,000,000,000,000 de ani! Adaugarea unui singur oras creste numarul de operatii de 31 de ori.
2. Probleme cu spatiul solutiilor infinit.
In aceasta categorie se include problema maximului unei functii n-dimensionale. De remarcat ca in cazul maximului unei functii unidimensionale exista metode clasice de rezolvare (metoda coardei, cea a tangentei), dar care se pot aplica numai functiilor care indeplinesc anumite conditii (continuitate, derivabilitate). Aceste metode insa se limiteaza la functii intr-o singura nedeterminata.
Desi problema rezolvarii unei ecuatii diofanice ar putea fi inclusa foarte bine in prima categorie, am preferat sa o mentionez aici, deoarece ea reprezina prin caracterul ei o probema aflata la granita dintre cele doua tipuri de probleme.
Optimizari Pentru o mai buna intelegere a algoritmilor genetici, s-a incercat in lucrarea de fata o
prezentare cat mai fixa a lor, variatiile de la o aplicatie la alta limitandu-se la strictul necesar.
In realitate insa, se poate spune fara exagerare ca numarul lor este egal cu cel al problemelor care implementeaza un algoritm genetic. Cauzele diversitatii lor sunt urmatoarele: Proiectarea unui algoritm genetic incepe cu alegerea caracteristicilor individului. Deci
doua probleme de optimizare conduc la doua programe diferite; Deciziile pe care le ia proiectantul de programe la implementarea unui algoritm
genetic sunt in mare masura echivalente intre ele, situatie în care intervine stilul programatorului;
Rezultatul rularii unui algoritm genetic depinde de alegerea parametrilor de control ai algoritmului genetic, deci depinde de optiunile experimentatorului.
40
In continuare vom da cateva optimizari care se pot face algoritmilor prezentati mai sus.
In primul rand, prin numarul parametrilor de control si prin operatiile aleatoare care se fac in cadrul programului (generarea populatiei initiale, alegerea punctului de incrucisare, mutatia, alegerea supravietuitorilor), acesti algoritmi au un caracter “semialeator”. De aceea pentru o problema data se recomanda schimbarea valorilor parametrilor de control si observarea diferentelor dintre solutiile afisate. Principalii parametri care pot fi schimbati (se pot considera chiar date de intrare) sunt urmatorii: - numarul cromozomilor unei populatii; - numarul de generatii create; - numarul de cromozomi copiati prin elitism; - numarul de incrucisari pe populatie; - numarul de mutatii pe populatie.
Pentru ca majoritatea lucrarilor din literatura de specialitate recomanda rularea de mai multe ori a unui algoritm genetic si apoi notarea celei mai bune solutii gasite, sugerez introducerea unui alt parametru fata de cei prezentati mai sus. Acesta va ajuta la simularea rularii multiple a programului. In programul dat mai jos parametrul este denumit MaxReIteratii.
void main() { int i,j; Citire(); /*aici se va initializa CelMaiBunCromozom*/ for(j=1;j<=MaxReIteratii;j++) { randomize(); InitializeazaPopulatie(); /*din aceasta functie se va scoate initializarea celui mai bun cromozom*/ OrdoneazaDupaFitness(); for(i=1;i<=MaxIteratii;i++) { /*aici nu se modifica nimic*/ } } Afiseaza(); }
Dupa cum se observa, modificarile care intervin sunt minore. Alte optimizari care se pot face au legatura cu functiile care alcatuiesc programul,
dupa cum urmeaza: Selectia realizata in aplicatiile de la capitolul precedent s-a bazat numai pe metoda
selectiei aranjate. Se pot folosi si celelalte metode sau chiar se pot realiza unele noi; Pentru o intelegere mai usoara a algoritmului, am preferat folosirea celei mai simple
metode de ordonare, si anume cea a bulelor. Avand in vedere faptul ca ordonarea dupa fitness se face de un numar mare de ori, si ca populatia are un numar relativ mare de indivizi recomand o varianta mai buna de ordonare, cum ar fi quicksort-ul;
Generarea populatiei initiale se poate face si prin metode euristice, multe din solutiile generate aleator fiind departe de optimul cautat.
41
In sfarsit, un al treilea tip de optimizare care se poate face este cel legat de conditia de oprire a algoritmului. Este posibil ca in cadrul unor probleme solutia sa evolueze rapid in primele generatii si apoi evolutia ei sa fie nesemnificativa. De aceea, in cadrul acestui tip de probleme, se recomanda monitorizarea evolutiei solutiei pe parcursul rularii algoritmului si terminarea lui in momentul in care aceasta devine lenta.
In finalul acestui capitol vom introduce doua notiuni care permit compararea performantelor a doi algoritmi genetici.
Timpul de stabilizare a populaţiei şi viteza de convergenţă
Pentru a compara performanţele a doi algoritmi genetici care rezolva aceeaşi problema, sau pentru a evalua influenta parametrilor de control asupra unui algoritm genetic, se fo-losesc cativa indicatori de performanta cum sunt: timpul de stabilizare a populatiei, viteza de convergenta, etc..
Timpul de stabilizare a populatiei este timpul necesar aglomerarii indivizilor în vecinatatea punctului optim.
Viteza de convergenta a algoritmului genetic este cresterea valorii medii a fitness-ului )1t(f)t(ff PP la trecerea de la o generatie la alta.
In figura de mai jos s-a reprezentat grafic evolutia in timp a trei functii: )t(fopt , valo-area curenta a maximului fitness-ului, )t(fP , valoarea curenta a mediei fitness-ului si
)t(f viteza de convergenta. Pe figura se observa ca din generatia a 20-a valoarea medie a fitness-ului, )t(fP , nu
sufera variatii importante. Viteza de convergenta a algoritmului genetic este panta valorii medii a fitness-ului, )t(fP . Se observa ca pana in generatia a 15-a viteza de convergenta este semnificativa, iar dupa aceea viteza de convergenta scade si ramane oscilanta in jurul valorii 0f .
42
Evolutia in timp a functiilor )t(fopt , )t(fP si )t(f .
In principiu, urmarirea evolutiei in timp a valorii curente a maximului fitness-ului nu este un indicator de calitate decat daca algoritmul genetic rezolva o problema test cunoscuta. Timpul de stabilizare a populatiei si viteza de convergenta a algoritmului genetic sunt doua criterii in functie de care experimentatorul poate aprecia tendintele care se manifesta in evolutia populatiei.
43
BIBLIOGRAFIE Oltean, M. – Proiectarea si implementarea algoritmilor, Editura Computer Libris
Agora, Cluj, 1999; Aspru, O. – Tehnici de programare, Editura Adias, Rm. Valcea, 1997; Andonie, R., Garbacea, I. – Algoritmi fundamentali, o perspectiva C++, Editura
Libris, Cluj, 1995; Johnson, G. – Computers and Itractability; A Guide to the Theory of NP-
Completeness, W. H. Freeman & co., 1979; Colectia Gazetei de informatica;
44
CUPRINS
Capitolul I. Consideraţii generale…………………………… 1
1. Introducere………………………….…………………... 2. Notiuni de genetica…….……………………………..… 3. Algoritmul general (schema logica si pseudocod)……...
1
1 2
Capitolul II. Codificarea informatiei………………………… 5
1. Codificarea cromozomilor……………………………... 2. Populatia initiala………………………………………. 3. Fitness-ul unui cromozom……………………………… 4. Selectarea cromozomilor parinti………………………... 5. Incrucisarea (crossover)………………………………… 6. Mutatia………………………………………………….. 7. Cand se termina algoritmul?…………………………….
5 6 6 6 7 9 9
Capitolul III. Implementarea algoritmului…………………… 10
Capitolul IV.
Aplicatii………………………………………….. 15
1. Ecuatia diofanica……………………………………... 2. Problema discreta a rucsacului……………………….. 3. Problema comis-voiajorului..………………………… 4. Maximul unei functii n-dimensionale………………...
15 20 26 33
Capitolul V. Consideratii finale……………………………….. 39
Bibliografie…………………………………………………………. 43
