Reprezentare. Un cromozom reprezinta o ordonare a varfurilor grafului de intrare; il voi codifica printr-o permutare. Spre exemplu, pentru un graf G cu 4 varfuri, urmatorii 2 cromozomi sunt valizi: X = (4 2 3 1), Y = (1 3 2 4). Populatia initiala este generata aleator: sunt considerate permutari aleatoare.
Operatori genetici. Am experimentat un singur operator de incrucisare si doi operatori de mutatie. In continuare voi descrie fiecare operator in parte, urmand ca in sectiunea Parametri sa specific ratele acestora.
Operatori genetici. Incrucisarea. Fie X si Y doi cromozomi. Aleg aleator un punct de taiere cx in interiorul lui X si un punct de taiere cy in interiorul lui Y. In urma incrucisarii lui X cu Y vor rezulta doi cromozomi V si W care vor lua locul parintilor in populatie. Cromozomul V se obtine un modul urmator: se copie varfurile din X de pana la pozitia cx, dupa care se adauga varfurile ramase in ordinea in care acestea apar in cromozomul Y. In mod similar se obtine cromozomul W. Iata si un exemplu:
X = (3 1 6 | 2 5 4), Y = (5 2 | 4 1 3 6), V = (3 1 6 | 5 2 4), W = (5 2 | 3 1 6 4)
Operatori genetici. Order Mutation. Operatorul mutatie defineste pentru o solutie cadidat o vecinatate. Doi cromozomi X si Y sunt "vecini" relativ la operatorul Order Mutation daca din X putem obtine pe Y in urma unui numar k de interschimbari de varfuri (sau viceversa). Numarul k de interchimbari depinde de numarul de varfuri din graful de intrare si este stabilit inaintea rularii algoritmului (vezi Parametri pentru mai multe detalii). Iata si un exemplu, pentru k=1: X = (3 1 6 2 5 4), Y = (3 1 4 2 5 6).
Operatori genetici. Block Mutation. Acest operator realizeaza translatii de blocuri de k varfuri consecutive. Lungimea k a unui bloc depinde de numarul varfurilor din graful de intrare si este stabilita inaintea rularii algoritmului (vezi Parametri pentru mai multe detalii). Iata si un exemplu, pentru k=2:
X = (1 2 3 4 5 6 7 8 9 | 10 11 12), Y = (1 4 5 6 7 8 9 2 3 10 11 12).
Evaluare. Pentru a evalua o ordonare a varfurilor grafului de intrare, construiesc o colorare pornind de la aceasta. Numarul de culori necesare obtinut va dicta calitatea ordonarii. Am experimentat doua modalitati de construire a unei colorari pornind de la o ordonare data a varfurilor. In continuare le voi descrie pe amandoua.
Evaluare. Multimi stabile maximale consecutive. Dupa cum sugereaza si numele, o ordonare este evaluata la numarul de multimi stabile maximale consecutive. Avand in vedere faptul ca varfurile dintr-o multime stabila pot fi colorate cu aceeasi culoare, putem spune ca aceasta evaluare ofera numarul de culori necesare. Iata si un exemplu:
X = (2 4 | 1 6 5 | 3 7) este evaluat la 3, daca (2 4), (1 6 5) si (3 7) sunt multimi stabile, iar (2 4 1) si (1 6 5 3) nu.
Evaluare. Euristica. Am aplicat urmatorul algoritm:
Intrare: o ordonare X a varfurilor grafului de colorat G;
Iesire: o aproximare a numarului cromatic al grafului G;
Algoritm:
Viz <- {} // multimea varfurilor vizitatenCulori <- 0 // numarul de culori// G = (V, E)while (Viz != V) do{varfStart <- primul varf nevizitat, in ordinea XB <- bfs(G, varfStart, Viz) // vecinii sunt considerati in ordinea XS <- multimea stabila maximala obtinuta din B (considerand vf. in ordinea B)nCulori++ // varfurile din S sunt colorate cu o noua culoareViz <- Viz reunit S}Selectie. Am utilizat o selectie bazata pe clasament. Cromozomii sunt clasificati in functie de fitness-ul asociat. Vom obtine atatea clase cate valori distincte ale functiei fitness, pentru populatia curenta, avem. Clasele rezultate sunt sortate crescator in functie de fitness-ul reprezentantilor. Construim un camp de probabilitate, dupa formula:
// pi -> probabilitatea asociata clasei i (dupa sortarea claselor)// n -> numarul de clase obtinute// sp -> presiunea selectiei (vezi sectiunea Parametri)// i = 0, .., n-1pi = 2 - sp + 2 * (sp - 1) * (n - i) / nO clasa este aleasa utilizand motoda "Roulette Wheel"; dintr-o clasa se alege aleator un cromozom.
Parametri. In continuare voi enumera parametrii algoritmului genetic impreuna cu valorile cel mai des folosite in testele mele:
dimensiunea populatiei = 100
numarul de generatii = 500
probabilitatea incrucisarii = 0.6
probabilitatea mutatiei = 0.15
presiunea selectiei = 2 (dar, 1.0 ≤ sp ≤ 2.0)
order mutation: numarul de interschimbari este cuprins intre 0.05
si 0.1 din numarul de varfuri
block mutation: lungimea unui bloc este cuprinsa intre 0.05
si 0.2 din numarul de varfuri
Rezultate. Am efectuat teste pe o parte din grafurile de test DIMACS (mi-am procurat fisierele de test de la adresa http://mat.gsia.cmu.edu/COLOR02/). Prezint in continuare tabelul cu rezultate:
| Numele Grafului | |V| | |E| | X(G) | k min | k min (euristica) |
| 2-Insertions_4.col (CAR) | 149 | 541 | ≤4 | 8 | 5 |
| fpsol2.i.1.col (REG) | 496 | 11654 | ≤65 | 75 | 65 |
| homer.col (SGB) | 561 | 1629 | ≤13 | 20 | 13 |
| inithx.i.1.col (REG) | 864 | 18707 | ≤54 | 74 | 54 |
| le450_15d.col (LEI) | 450 | 16750 | ≤15 | 76 | 26 |
| le450_25d.col (LEI) | 450 | 17425 | ≤25 | 80 | 32 |
| le450_5d.col (LEI) | 450 | 9757 | ≤5 | 52 | 7 |
| mugg100_25.col (MIZ) | 100 | 166 | ≤4 | 5 | 4 |
| mulsol.i.1.col (REG) | 197 | 3925 | ≤49 | 49 | 49 |
| myciel7.col (MYC) | 191 | 2360 | ≤8 | 10 | 8 |
| qg.order30.col (GOM) | 900 | 26100 | ≤30 | 98 | 31 |
| queen13_13.col (SGB) | 169 | 6656 | ≤13 | 33 | 16 |
| zeroin.i.1.col (REG) | 211 | 4100 | ≤49 | 50 | 49 |
Concluzii. Algoritmul se comporta bine, insa nu se compara cu rezultatele obtinute de alti algoritmi ce folosesc alte metaeuristici, sau imbina algoritmul genetic cu o alta metaeuristica. Algoritmul este deficitar si din cauza ca functia fitness aleasa are prea putine valori distincte fata de numarul mare de cromozomi (pentru un graf cu N varfuri avem N! solutii candidat - cromozomi - si doar maxim N valori distincte ale functiei fitness aleasa).