Academia de Studii Economice Bucureti

Facultatea de Cibernetic, Statistic i Informatic Economic

ALGORITMI GENETICI
PENTRU
PROBLEMA COLORRII
HRILOR

n aceast lucrare se contureaz o abordare a problemei

colorrii hrilor folosind c culori prin algoritmi gertetici.
Obiectivul acestei probleme este de a umple fiecare regiune
a hrii cu una dintre cele c culori astfel nct regiunile
adiacente s fie distincte cromatic.

Ancua-Roxana Vochescu

Bucureti, 2017
 1. Enunul problemei

Utilizai un algoritm genetic pentru rezolvarea problemei colorrii hrilor, definit

astfel: Se d o hart cu n (n>15) ri (se cunosc vecintile pe hart, prin intermediul
matricei de adiacen). Sunt disponibile c culori distincte pentru colorarea hrii. Se cere s
se determine o modalitate de colorare a hrii astfel nct fiecare ar s fie colorat cu alt
culoare dect toi vecinii si. Care este numrul minim de culori necesare pentru colorarea
hrii?

Problema de colorare a hrii a fost propus la nceputul anilor 1850. Ideea este s se
foloseasc numrul minim de culori pentru a umbra diferitele ri, care sunt de culoare diferit
fa de vecinii adiaceni, pe harta lumii. Problema este considerat dificil deoarece nu se
impune nici o restricie asupra numrului de regiuni din harta care mprtesc aceeai limit.
Muli matematicieni, inclusiv Augustus De Morgan, Arthur Kempe i Peter Tait, au dovedit
c problema oricrui grafic simplu poate fi colorat cu cel puin patru culori [1].

Soluia de colorare a hrii poate fi reprezentat n structura genetic cromozomal, astfel

nct cele c culori vor fi exprimate prin c alele.

De exemplu, galben, verde, albastru , etc. sunt reprezentate prin 1,2,3,..,c, unde c
.Fiecare regiune va fi reprezentat de ctre o gen. De exemplu, o soluie posibil pentru
colorarea a celor 42 de judee din Romnia, inclusiv Bucureti, poate fi reprezentat printr-un
cromozom compus din 42 de gene, fiecare lund valorile 1,2,..,c. Un cromozom A, care
reprezinta colorarea a n regiuni ale unei harti, este notat astfel :

A = (c1,c2,c3, , cn), ci {1,2, , c}, i =

1,

unde ci este alela reprezentand culoarea regiunii i din harta.

Vom alege pentru implementare reprezentarea cu numere ntregi pentru a putea asocia facil
soluia cu realitatea.

Informaiile despre adiacena a n regiuni din hart pot fi pstrate ntr-o matrice de n n
elemente, cunoscut sub denumirea de matricea adiacenelor.

11 1
Fie M o matrice de adiacenta : M = ( ),
1

1,
unde mij = { , unde i,j =
1, cu i j
0,

De exemplu, pentru Figura 1, regiunea r1 este adiacena fa de r2, adic au o grani

comun. Codificarea culorilor folosite se regasete n Figura 2, iar matricea de adiacen
pentru Figura 1 se afl n Tabelul 1.

Considernd exemplul de mai jos, pentru n = 4, c = 3 i matriea de adiacen m, o posibil

soluie este reprezentat n Figura 3, notata ca A = (1, 2, 1, 3).
 Aadar, colorarea hrii A, avnd n ri, cu cele c culori este valid dac i,j =
1, cu i

j si mij = 1 atunci ci cj. Daca i j, i,j = 1, i mij = 1, dar i ci = cj atunci spunem c i i j
sunt n conflict. (1)

1 2 3 4
1 0 1 0 0
2 1 0 1 1
3 0 1 0 1
s4 0 1 1 0

Tabelul 1. Matricea de adiacen

2. Structura general a algoritmului utilizat

Spunem ca am rezolvat o problem de colorare a hrii de fiecare dat cnd gsim

valori conforme cu (1). Procesul consta in:

Porinim cu un numar de c culor i n ri pentru care generm populaia iniial:

pop = (c1,c2,c3, , cn), reprezentnd asocierea aleatoare a unei culori fiecrei ri/
regiuni din cele n.
Considerm o funcie obiectiv n ceea ce privete numrul de conflicte pentru
fiecare numr c de culori fixat, pentru ca la fiecare etap numrul de conflicte s
ncercm sl reducem la zero, ceea ce corespunde unei solutii valide.
Capacitatea de fitness corespunde urmtoarei sume de conflicte:
f = =1 =+1 , daca i j, i,j =
1, , mij = 1 i ci = cj
Aadar vom urmri minimizarea funciei obiectiv f.
Algoritmul cautarii unei solutii a problemei generale de colorare a hartii cu c
culori, folosind Algoritmii Genetici, poate fi descris astfel:
1) generam aleator populatia initiala pop0 cu dim indivizi, unde dim este
dimensiunea populaiei, dat.
2) repet
3) k k + 1
4) popt reproducere ( popt -1)
5) popt recombinare(popt , pr), unde pr = probabilitatea de recombinare
6) popt mutaie(popt , pm), unde pm = probabilitatea de mutaie
7) evalueaz(popt)
8) pn cnd numrul de populaii generate este mai mic sau egal dect k
 3. Specificarea fiecrei componente a algoritmului genetic utilizat pentru rezolvarea
problemei
I. Funcia obiectiv urmrete minimizarea conflictelor ntre regiunile cu aceeai
culoare i este calculat ca:

II. La fiecare moment de timp populaia este format din dim indivizi reprezentai
aa cum a fost explicat mai sus. Populia iniial este generat aleator folosind
urmtoarea funcie:

Pe ultima poziie din reprezentarea fiecrui individ se afl valoarea funciei obiectiv.

III. Selecia prinilor este realizat prin urmtorul procedeu: de dim ori sunt alese
perechi de cromozomi din populaia curent i este selectat cel mai bun dintre
ei, din punctul de vedere al funciei de evaluare.
IV. Recombinarea este realizat astfel: pentru fiecare pereche de doi indivizi
aflai pe poziii generate aleator i care nu au mai fost selectai n procesul
curent de recombinare - x i y din populaia curent sunt obinute
progeniturile c1 i c2 prin recombinarea uniform:

Consultarea fiecrei gene n mod independent i atribuirea valorii corespunztoare din

gena unuia dintre prini. Pentru fiecare gen este generat aleator din distribuia uniform
valoarea r. Dac r<pr atunci primul descendent direct motenete valoarea genei de la al
doilea printe, iar cel de-al doilea descendent de la primul printe.[2]

Pe ultima poziie din reprezentarea fiecrui individ se afl valoarea funciei obiectiv.
 Dac o pereche de prini nu este selectat pentru ncruciare, aceasta este meninut n
populaia urmtoare.

V. Operatorul de mutaie este aplicat cu probabilitatea pm unui individ x i

revine la resetarea aleatoare a alelelor, generarea aleatoare a unei valori din
mulimea vaorilor admisibile pentru gena respectiv.
VI. Algoritmul genetic utilizat este prezentat n continuare. Condiia de oprire
este dac a fost depit numrul maxim de generaii k.
4. Teste

Un prim test realizat este pentru harta prezentat anterior, la punctul 1.

La apelul GA_Harti("[Link]",3,4,4,5,0.65,0.25); se obin urmtoarele:
Matricea de adiacen a hrii este:
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
Populaia iniial generat aleatorpentru colorarea hrii este:
3 3 4 1 1
4 3 3 1 1
4 4 3 1 1
n urma recombinrii pot rezulta prinii:
4 4 3 1 1
4 3 3 1 1
Urmaii:
4 3 3 1 1
4 4 3 1 1
Mutaia s-a realizat pentru individul:
3 3 4 1 1
Individul rezultat:
3 3 4 2 1
Dup ali pai pn ce numrul de populaii a ajuns la k=5, rezultatele au fost:
Cea mai bun valoare a funciei fitness n fiecare generaie:
Generatia: 1 2 3 4 5
1 1 1 0 0
Indivizii cu cea mai bun valoarea a funciei fitness:
Din generaia 4
4 3 4 2 0

Pentru apelul GA_Harti("[Link]",3,7,4,10,0.65,0.25); i matricea de adiacen

de mai jos, am obinut:

Matricea de adiacen a hrii este:

0 1 1 0 1 1 0
 1 0 0 1 1 0 1

1 0 0 1 1 1 0

0 1 1 0 1 0 1

1 1 1 1 0 0 0

1 0 1 0 0 0 1

0 1 0 1 0 1 0

Populaia iniial generat aleatorpentru colorarea hrii este:

4 3 2 4 1 1 2 0

2 3 3 1 3 4 2 2

3 2 2 4 2 1 1 3

n urma recombinrii pot rezulta prinii:

4 3 2 4 1 1 2 0

4 3 2 4 1 1 2 0

Urmaii:

4 3 2 4 1 1 2 0

4 3 2 4 1 1 2 0

Mutaia s-a realizat pentru individul:

4 3 2 4 1 1 2 0

Individul rezultat:

4 3 3 4 1 1 2 0

etc.

n urma a zece iteraii celemai bune rezultate ale funciei de evaluare au fost:

Functia fitness:

0 1 2 2 4 3 2 2 2 1

Indivizii cu cea mai buna valoarea a functiei fitness:

 Din generatia 1

4 3 3 4 1 1 2 0

n urma apelrii aceleai funcii, dar pentru generarea a 20 de populaii am obinut diferenele:

Se observ faptul c numrul crescut de generaii nu eficientizeaz algoritmul, n acest caz.

Pentru a reveni la problema propus iniial, aceea de colorare a celor 42 de judee

din Romnia, respectnd cerinele problemei de colorare a harilor, am creat
matricea de adiacen a acestora (n urma numerotrii proprii ca n imaginea de
mai jos):
n urma rulrii algoritmului pentru 10 populaii, am obinut:

Se observ ct de puin eficient este n acest caz generarea unui numr mic de generaii.

Vom apela funcia pentru 100 de generaii albastru i 200 de generaii portocaliu.

n graficul de mai jos putem urmri evoluia n urma a 500 de generaii albastru i a 1000 de
generaii rou i portocaliu.
>> GA_Harti("[Link]",3,42,4,4000,0.6,0.01);

>> GA_Harti("[Link]",3,42,4,10000,0.6,0.01);

>> GA_Harti("[Link]",3,42,15,300,0.6,0.01);

Se observ c pentru un numr destul de mic de generaii 300, dar mare de culori, se obine
soluia optim.
Bibliografie

1. K. Appel and W. Haken. "The Solution of the Four-Colour-Map Problem," Scientific

AnLevcian, pp. 108-121. Oct.1977.
2. Cocianu C., Uscatu C. Programare Evolutiv i Algoritmi Genetici, Ed. ASE,
Bucureti 2015