8. Algoritmi genetici

[11, 27, 33, 54]

Pentru a înţelege algoritmii genetici, în primul rând trebuie să

înţelegem şi să cuantificăm modelul evoluţiei naturale (darwiniste). Modelul

evolutiv presupune existenţa unui habitat (a unui spaţiu de evoluţie)

guvernat de legi locale (condiţiile de mediu) în care speciile (populaţiile

reprezentate de indivizi) se supun următorului mecanism:

1. Pe baza selecţiei, un număr restrâns de indivizi din populaţia

iniţială vor constitui populaţia intermediară de părinţi (algoritmul

de selecţie trebuie să respecte paradigma conform căreia un

individ mai bine adaptat să aibe şanse mai mari de supravieţuire).

2. Dintre indivizii selectaţi ca şi părinţi, pe baza operatorilor

genetici (mutaţie, încrucişare, ...), se va reconstitui o nouă

populaţie.

Pentru a creea din modelul evolutiv un algoritm genetic (J. Holland,

1970), vom înlocui în primul rând spaţiul de evoluţie (habitatul) cu

problema dată, indivizii din populaţie cu posibile soluţii la problema în

cauză şi urmărind mecanismul evolutiv, ne vom aştepta ca după un timp să

găsim cele mai bune (optime) soluţii.

Acest capitol va prezenta pe larg teoria din spatele algoritmilor

genetici, precum şi două probleme rezolvate cu ajutorul acestora.

CUPRINS

8.1. Descrierea algoritmilor genetici .............................................................. 3

8.2. Problema găsirii unei expresii ............................................................... 10

8.3. Rezolvarea sistemelor de ecuaţii .......................................................... 15

1.1. Descrierea algoritmilor genetici

a) Căutarea în spaţiul soluţiilor

În acest paragraf vom aprofunda modul de construcţie a unui

algoritm genetic, setările şi variantele acestuia, modulele folosite în

rezolvarea de probleme şi câteva elemente conexe încadrate de regulă în

conceptele de inteligenţă artificială.

Pentru a putea rezolva o problemă prin algoritmi genetici este

necesară transformarea acesteia într-o problemă de căutare sau optimizare

a soluţilor. Ca o analogie cu modelul evoluţionist, vom numi în continuare

soluţiile cromozomi, iar spaţiul tuturor soluţiilor îl vom nota cu Crom.

În primul rând avem nevoie de o funcţie sau un criteriu de selecţie,

care va arăta cât de adaptat este un cromozom soluţie, sau dacă cromozomul

curent este chiar o soluţie acceptabilă, asociind acestora, de regulă, o valoare

reală. Această funcţie se numeşte funcţie de adecvare (en. fitness function)

şi o vom nota cu fadec şi avem:

În conceptul algoritmilor genetici trebuie acceptat că orice element

din spaţiul soluţiilor este o posibilă soluţie, doar că funcţia de adecvare

stabileşte dacă această soluţie este acceptabilă sau nu. Să luăm de exemplu

ecuaţia (cu caracter demonstrativ): . Spaţiul soluţiilor este R şi

x = 17 este o soluţie, însă, evident, nu este cea mai bună, dar este mai bună

decât x = 46, de exemplu. Continuând căutarea în spatiul soluţiilor vom găsi

la un moment dat x = 2, această soluţie fiind cea mai bună.

În general, vom accepta o eroare ( ), iar

va fi una din condiţiile de oprire a algoritmului.

Graficul din figura 8.1.1. a fost obţinut reprezentând valoarea

funcţiei de adecvare pentru fiecare cromozom în parte pentru o problemă

oarecare P. Funcţia de adecvare este în aşa fel construită încât:

Fig. 8.1.1. – Căutarea în spaţiul soluţiilor

înseamnă că c1 este soluţia cea mai bună (optimul global), iar pentru

,

x1 este soluţie mai bună (mai acceptabilă) decât x2.

În acest caz spunem că minimizăm funcţia obiectiv.

Există două concepte fundamentale de căutare în spaţiul soluţiilor:

1. explorarea spaţiului soluţiilor: căutarea complet aleatorie în

spaţiul soluţiilor atâta timp cât nu se găseşte o valoare

acceptabilă (în cazul nostru, atâta timp luăm câte o valoare

aleatorie pe axa reprezentată de spaţiul soluţiilor, până când

aceasta este în unul din intervalele de soluţii acceptabile).

2. exploatarea unor potenţiale soluţii: reprezentată în general de

metodele de coborâre (gradient, Newton) care vor minimiza

succesiv graficul funcţiei de adecvare. Exploatarea unor

potenţiale soluţii se referă la condiţiile iniţiale asociate metodei

de coborâre. În exemplul nostru, o metodă de coborâre pornită

din punctul A va ajunge la optimul local, dar pentru datele de

intrare stabilite în punctul B nu va găsi nicio soluţie (Fig. 8.1.2.)

Pentru a avea posibilitatea ajungerii la o soluţie globală, este

necesară stabilirea unui punct de pornire a unei metode de coborâre în

intervalul I.

Fig. 8.1.2.

Acest mod se poate realiza cel mai eficient prin procesarea mai

multor posibile soluţii simultan, cu diferite puncte de plecare aleatoare.

Conceptul asociat cu îmbinarea celor două metode de căutare în

spaţiul soluţiilor se numeşte echilibrul explorare – exploatare şi tratarea

celor două concepte simultan reprezintă principalul avantaj al algoritmilor

genetici relativ la celelalte metode de optimizare.

b) Algoritmul genetic fundamental

În primul rând, pentru a construi un model general al unui algoritm

genetic, trebuie să luăm în calcul timpul de evoluţie (notat în continuare

tEvol). Considerăm valoarea iniţială tEvol = 0, ce corespunde cu pasul de

initializare a populaţiei. Apoi, la fiecare etapă de selecţie – generare, acest

timp de evoluţie îl incrementăm.

1. tEvol = 0

2. Se iniţializează o populaţie iniţială de soluţii (cromozomi)

Se verifică dacă prin metoda aleatoare de iniţalizare a

populaţiei nu s-a obţinut o soluţie acceptabilă, caz în care se

incheie algoritmul.

3. Pe baza funcţiei de adecvare se selectează cele mai optime soluţii

(se formează populaţia de soluţii-părinţi).

4. Pe baza operatorilor genetici se generează soluţiile copii din

populaţia intermediară.

5. tEvol++

6. Se verifică condiţiile de oprire în funcţie de tEvol = tEvolMAX

sau dacă s-a găsit o soluţie acceptabilă

Dacă da algoritmul se încheie.

Altfel se revine la pasul 3.

Paşii 3 şi 4 reprezintă nucleul algoritmului genetic.

c) Selecţia

Există mai multe tipuri de selecţie, toate acestea având scopul ca

implementarea capacităţii de supravieţuire a unei soluţii să fie proporţională

cu valoarea funcţiei de adecvare, aici fiind de fapt implementată paradigma

evoluţiei darwiniste survival of the fittest. Una dintre cele mai simple

metode de selecţie este selecţia bazată pe ordonare (ierarhie), în care se

ordonează populaţia de soluţii astfel încât adaptarea lor să fie

descrescătoare, după care se selectează primii n indivizi doriţi.

Metoda cea mai naturală de selecţie este metoda de selecţie Monte

Carlo (proporţională). Această metodă presupune construirea unei rulete,

fiecare individ din populaţie fiind reprezentat sub forma unui sector de cerc

proporţional cu o pondere. Pentru a avea sens din punct de vedere evolutiv,

ponderea trebuie să fie cu atât mai mare cu cât adecvarea individului soluţie

este mai bună. În figura 8.1.3. avem o populaţie formată din cinci indivizi şi

adaptarea cea mai bună o are crom5.

Fig. 8.1.3. – Ruleta Monte Carlo

În mod uzual, un algoritm de selecţie Monte Carlo are ca date de

intrare o matrice formată din simboluri şi ponderi asociate. De exemplu să

cuantificăm aruncarea unui zar: simbolurile sunt feţele notate cu 1, 2, ..., 6,

reprezentate de numărul de puncte, iar ponderile (de apariţie a unei feţe) ar

trebui să fie identice (1). Astfel avem matricea de intrare:

Cu aceasta construim modelul grafic al ruletei: alegem un punct de

referinţă şi învârtim ruleta. (Fig. 8.1.4.) Simbolul extras este acela a cărui

sector de cerc asociat se opreşte în dreptul puctului de referinţă. Se păstrează

astfel modelul natural al unui zar perfect (fiecare simbol are aceeaşi

probabilitate de apariţie):

Fig. 8.1.4. – Ruleta Monte Carlo pentru un zar perfect

Algoritmul de selecţie Monte Carlo poate fi exprimat astfel:

Fie suma ponderilor.

Se generează un număr aleator t între 0 şi S – 1.

Se parcurg ponderile şi atâta timp cât t >= 0, se scade din t

ponderea curentă.

int AMC (int ponderi[], int n)

{

int s = 0;

for ( int i = 0 ; i < n; i++ ) s += ponderi[i];

int t = rand() % s, symbol_poz = 0;

do

{

t -= ponderi[symbol_poz];

symbol_poz++;

} while (t >= 0);

return symbol_poz - 1;

}

Există mai multe tipuri de selecţie, pe lângă cele două amintite

anterior. Avantajele, dezavantajele, modul lor de implementare şi

particularităţile acestora le vom trata într-un manual dedicat inteligenţei

artificiale.

d) Operatorii genetici

Pentru a continua construcţia unui algoritm genetic funcţional, avem

nevoie de o modalitate de generare a soluţiilor-copii din populaţia de

soluţii-părinţi. Aceasta se realizează prin operatorii genetici. Există doi

operatori genetici fundamentali: mutaţia (notată în continuare opM),

respectiv încrucişarea (opI). Avem:

şi

Se observă că mutaţia este un operator unar şi acţionează prin

schimbarea uneia sau a mai multor valori din cromozomul părinte: în forma

cea mai simplă fie un cromozom cu valorile

. Atunci un operator de mutaţie ar genera o valoare aleatoare t

între 0 şi n – 1, iar valoarea corespunzătoare lui t ar fi schimbată cu o altă

valoare.

Să considerăm cromozomul 1110001010011111, în codificarea

binară. pentru a obţine diversitatea populaţiei este necesar să ţinem cont că

vom modifica în 1 bitul ales aleator dacă valoarea acestuia este 0, respectiv

în 0 dacă această valoare este 1.

Toate variantele operatorilor de mutaţie au ca scop diversificarea

populaţiei, în efect contrar cu selecţia.

Operatorul de încrucişare este un operator binar şi are ca scop

schimbarea valorilor existente între cromzomii părinţi. În forma cea mai

simplă (numită încrucişarea cu un punct de tăietură) se generează un

număr aleator t, acesta reprezentând punctul în care se rup cei doi

cromozomi şi se recombină.

sau

Forma cea mai întâlnită a operatorului de încrucişare este aceea în

care se generează un şir de numere aleatoare (ti), care vor reprezenta

punctele de tăietură:

Un exemplu în codificare binară:

Operatorii genetici de mutaţie şi încrucişare sunt necesari într-un

algoritm genetic pentru a asigura procesul evolutiv. Pe lângă aceşti operatori

se pot construi şi alţii, în funcţie de cerinţele problemei.

Există şi posibilitatea căutării unor soluţii pentru care lungimea

cromozomilor să fie variabilă, sau informaţia reţinută de aceştia să fie

supusă anumitor restricţii, caz în care trebuie adaptaţi şi operatorii genetici

în consecinţă.

Algoritmii genetici sunt foarte eficienţi atunci când dorim soluţii

apropiate de un optim global într-un timp scurt, dar dacă dorim optime

globale atunci aceştia pot fi mai puţin eficienţi decât alte abordări.

Prezentăm în continuare două probleme care se pot rezolva în mod

natural cu ajutorul algoritmilor genetici: o problemă în care se cere o

expresie a cărei rezultat să fie un număr dat şi o problemă în care se cere

rezolvarea unui sistem de ecuaţii. Sperăm ca rezolvările prezentate în cadrul

acestora să vă ajute să înţelegeţi atât logica din spatele algoritmilor genetici,

cât şi modul de implementare al acestora.

1.2. Problema găsirii unei expresii

Se dau N – 1 operatori matematici O1, O2, ..., ON – 1 din mulţimea

{+, -, *}, având semnificaţia lor obişnuită şi un număr S.

Scrieţi un program care găseşte un şir de N numere naturale

X1, X2, ..., XN din intervalul [1, N], astfel încât expresia formată prin

alăturarea numerelor găsite cu operatorii daţi (adică X1O1X2O2 ... ON-1XN)

să dea, modulo 16 381, rezultatul S.

Datele de intrare se citesc din fişierul expresie.in, iar soluţia se scrie

în fişierul expresie.out. Fişierul de intrare conţine pe prima linie numerele

N şi S, separate printr-un spaţiu, iar pe a doua linie N-1 operatori matemtici

din mulţimea specificată în enunţ. În fişierul de ieşire se afişează, separate

printr-un spaţiu, pe prima linie, elementele şirului X.

Exemplu:

expresie.in expresie.out

4 18

* * +

4 4 1 2

Explicaţie: 4 * 4 * 1 + 2 = 18. 18 mod 16 381 = 18. Pot exista şi alte

soluţii.

O primă idee de rezolvare este să folosim metoda backtracking.

Trebuie să generăm toate posibilităţile de a completa N poziţii cu numere

din intervalul [1, N]. Acest lucru se poate face cu un algoritm similar cu cel

al generării permutărilor unei mulţimi, doar că acuma nu ne interesează dacă

folosim un element de două sau mai multe ori. Complexitatea unui astfel de

algoritm este O(NN), deoarece pentru fiecare dintre cele N poziţii care

trebuie completate, avem N posibilităţi de completare (N resurse şi N

poziţii).

Complexitatea este foarte mare, iar algoritmul este ineficient şi în

practică pentru valori mari ale lui N. Există diverse optimizări care pot fi

făcute, dar nici acestea nu vor mări cu mult viteza algoritmului.

O altă idee este să generăm aleator numere până când găsim o

expresie care dă rezultatul S. În practică, nici această metodă nu

funcţionează pentru valori mari ale lui N.

Gândiţi-vă ce se întâmplă dacă generăm un şir de numere a cărui

rezultat este foarte aproape de S. Asta înseamnă că şirul respectiv ar putea fi

o soluţie validă, cu mici modificări. În cazul algoritmului anterior însă, acest

şir se va pierde la pasul următor, generându-se alt şir, care va avea mai

multe şanse să fie mai îndepărtat de soluţie decât mai apropiat ca şirul

curent

Ideea din spatele algoritmilor genetici este să reţinem mai multe

astfel de şiruri (o populaţie sau ecosistem) generate aleator, pe care să le

sortăm după o funcţie de adecvare (funcţie de fitness) care ia valori tot mai

apropiate de 0 pentru şiruri (indivizi sau cromozomi) care tind spre o

soluţie. Când am găsit un şir pentru care funcţia de adecvare ia exact

valoarea 0, am găsit o soluţie.

Algoritmul nu se opreşte însă la sortarea unor şiruri generate aleator.

Vom genera un anumit număr de şiruri o singură dată, după care vom aplica

anumiţi operatori genetici asupra lor. Aceşti operatori asigură faptul că

informaţia dintr-o generaţie nu se va pierde în generaţiile următoare. O

generaţie este o stare a populaţiei la un moment dat.

Se pune problema alegerii indivizilor asupra cărora vom aplica

operatorii genetici şi alegerii indivizilor a căror informaţie dorim să o

păstrăm şi în generaţia următoare. Evident, dacă un individ a fost foarte

aproape de soluţie într-o generaţie, acesta va merita păstrat aşa cum e şi în

generaţia viitoare. Vom menţine o listă cu elite pentru fiecare generaţie,

elite care vor trece nemodificate în generaţia următoare. Operatorii genetici

se vor aplica asupra elitelor, combinând calităţile acestora în speranţa

obţinerii unor soluţii din ce în ce mai bune.

Operatorii genetici se aplică, fiecare, cu o anumită probabilitate, în

funcţie de necesitatea aplicării lor.

Operatorii cei mai des întâlniţi sunt operatorii de recombinare şi de

mutaţie. Operatorul de recombinare combină informaţia reţinută de doi

cromozomi A şi B ce fac parte din elite într-un singur cromozom ce va face

parte din generaţia următoare. Modul de desfăşurare al operaţiei este similar

cu procedeul biologic: se alege un punct (o genă) oarecare P de pe unul

dintre cei doi cromozomi din elite. Cromozomul C rezultat prin recombinare

va avea primele P gene identice cu primele P gene ale cromozomului A, iar

următoarele gene identice cu genele de după poziţia P a cromozomului B

Pentru problema de faţă, lucrând pe exemplul dat, recombinarea s-ar putea

face astfel:

Cromozom Informaţie

A 4 * 4 * 2 + 3

B 1 * 4 * 1 + 2

C 4 * 4 * 1 + 2

Fig. 8.2.1. – Operatorul de recombinare aplicat problemei prezentate

Operatorul de mutaţie modifică aleator valoarea unei gene alese tot

aleator. În cazul problemei de faţă, operatorul de mutaţie trebuie să fie

implementat în aşa fel încât să nu modifice valoarea unui operator.

Exemplu:

Înainte de mutaţie După mutaţie

4 * 3 * 1 + 2 4 * 4 * 1 + 2

Fig. 8.2.2. – Operatorul de mutaţie aplicat problemei prezentate

Funcţie de adecvare este, în acest caz, foarte simplu de construit.

Aceasta va calcula, pentru fiecare cromozom, diferenţa în modul dintre

suma S şi valoarea expresiei reţinute de cromozomul curent.

Astfel, algoritmul de rezolvare este următorul:

Iniţializează aleator maxpop cromozomi / indivizi.

Execută:

o Creează o nouă populaţie aplicând operatorii de

recombinare şi de mutaţie (fiecare cu probabilităţi

prestabilite).

o Sortează indivizii crescător după funcţia de adecvare.

Cât timp valoarea funcţiei de adecvare pentru primul cromozom

este diferită de 0.

Afişează operanzii primului cromozom.

Pentru mai multe detalii despre funcţia de evaluare a unei expresii,

vedeţi capitolul Algoritmi generali.

#include <fstream>

#include <algorithm>

#include <cstdlib>

using namespace std;

const int maxN = 1001; const int maxpop = 400;

const int maxlg = 2*maxN + 1;

const int maxeli = 50;

const int prob_recomb =

(int)((double)0.80 * RAND_MAX);

const int prob_mutatie =

(int)((double)0.95 * RAND_MAX);

const int mod = 16381;

struct info

{

int P[maxlg], fitness;

};

void citire_init(int &N, int &S,

info A[])

{

ifstream in("expresie.in");

in >> N >> S;

char x;

int ops[maxN];

for ( int i = 1; i < N; ++i )

{

in >> x;

if ( x == '-' ) ops[i] = -1;

else if ( x == '+' ) ops[i] = -2;

else ops[i] = -3;

}

ops[N] = -100;

in.close();

for ( int i = 1; i < maxpop; ++i )

{

for ( int j=1, k=1; j < 2*N;

j += 2, ++k )

{

A[i].P[j] = 1 + rand() % N;

A[i].P[j+1] = ops[k];

}

}

}

void calc_fitness(int N, int S, info A[])

{

for ( int cr = 1; cr < maxpop; ++cr )

{

// <EVALUARE> int paran(int &k, int cr,

info A[])

{

return A[cr].P[k++];

}

int inm(int &k, int cr, info A[])

{

int ret = paran(k, cr, A);

while ( A[cr].P[k] == -3 )

{

++k;

ret *= paran(k, cr, A);

ret %= mod;

}

return ret;

}

int eval(int &k, int cr, info A[])

{

int ret = inm(k, cr, A);

while (A[cr].P[k] == -1 ||

A[cr].P[k] == -2)

{

if ( A[cr].P[k++] == -1 )

ret -= inm(k, cr, A);

else

ret += inm(k, cr, A);

ret %= mod;

while ( ret < 0 )

ret += mod;

}

return ret;

}

// </EVALUARE> bool operator<(const info &x, const info &y)

{

return x.fitness < y.fitness;

int k = 1;

A[cr].fitness = abs(eval(k, cr, A) - S);

}

sort(A+1, A+maxpop);

}

void noua_gen(int N, info A[])

{

for ( int i = maxeli + 1; i < maxpop; ++i )

{

if ( rand() < prob_recomb ) // recombinare

{

int i1, i2;

do

{

i1 = 1 + rand() % maxeli;

i2 = 1 + rand() % maxeli;

} while ( i1 == i2 );

int poz;

do

{

poz = 1 + (rand() % (2*N - 1));

} while ( poz % 2 == 0 );

for ( int j = 1; j < poz; j += 2 )

A[i].P[j] = A[i1].P[j];

for ( int j = poz; j < 2*N; j += 2 )

A[i].P[j] = A[i2].P[j];

}

if ( rand() < prob_mutatie ) // mutatie

{

int poz;

do

{

poz = 1 + (rand() % (2*N - 1));

} while ( poz % 2 == 0 );

A[i].P[poz] = 1 + (rand() % N);

}

}

}

}

void start(int N, int S, info A[])

{

do

{

noua_gen(N, A);

calc_fitness(N, S, A);

} while ( A[1].fitness != 0 );

ofstream out("expresie.out");

for ( int i = 1; i < 2*N;

i += 2 )

{

out << A[1].P[i] << " ";

}

out << endl;

out.close();

}

int main()

{

int N, S;

info *A = new info[maxpop];

srand((unsigned)time(0));

citire_init(N, S, A);

start(N, S, A);

delete[] A;

return 0;

}

Exerciţii:

a) Comparaţi performanţa algoritmului cu performanţa celorlalţi

doi algoritmi menţionaţi.

b) Cum afectează constantele de la începutul programului timpul de

execuţie şi memoria folosită?

c) Cum am putea modifica operatorii genetici dacă numerele

folosite în expresie ar trebui să fie distincte?

1.3. Rezolvarea sistemelor de ecuaţii

Se dă un sistem cu M ecuaţii şi N necunoscute. Considerăm ca

necunoscutele se notează cu A1, A2, ..., AN, iar o soluţie validă este o

permutare a mulţimii {1, 2, ..., N} care verifică fiecare ecuaţie.

Datele de intrare se găsesc în fişierul sistem.in, iar soluţia se scrie în

fişierul sistem.out. Fişierul de intrare are următoarea structură: pe prima

linie N şi M, iar pe următoarele M linii câte o ecuaţie în care operanzii sunt

despărţiţi de operatori prin câte un spaţiu, aşa cum se poate vedea în

exemplu.

Se presupune că sistemul are întotdeauna cel puţin o soluţie şi că, in

cazul unei operaţii de împărţire, se reţine doar partea întreagă a rezultatului.

În ecuaţii nu apar paranteze.

Exemplu:

sistem.in sistem.out

3 2

A1 + A2 - A3 = 2

A1 * A2 / A3 = 1

3 1 2

Explicaţie:

3 + 1 – 2 = 2

3 * 1 / 2 = 1

Se poate observa că şi permutarea (1, 3, 2) ar fi fost validă.

Problema se poate rezolva folosind metoda backtracking. Mai

exact, se foloseşte algoritmul de generare a tuturor permutărilor unei

mulţimi. Folosind algoritmul respectiv, putem verifica, pentru fiecare

permutare P, rezultatul fiecărei expresii date, în care înlocuim fiecare

necunoscută Ai cu numărul Pi (1 ≤ i ≤ N). Dacă am găsit o permutare care

verifică toate ecuaţiile date, am găsit o soluţie a sistemului şi putem opri

căutarea.

Această metodă are avantajul de a fi relativ uşor de implementat şi

de a găsi rapid o soluţie pentru un sistem oarecare. Alt avantaj este

posibilitatea găsirii tuturor soluţiilor unui sistem.

Dezavantajele acestei metode constau în eficienţă. Complexitatea

asimptotică va fi întotdeauna O(N!) deoarece trebuie să generăm toate

permutările. Totuşi, există optimizări care pot face ca algoritmul să ruleze

foarte rapid în practică. Câteva astfel de optimizări sunt:

Sortarea ecuaţiilor după numărul de necunoscute care apar în

acestea şi rezolvarea ecuaţiilor cu număr mai mic de variabile

mai întâi.

Verificarea ecuaţiilor înainte de generarea unei permutări întregi,

fapt ce ne poate ajuta să respingem o permutare mai devreme.

Diverse optimizări legate de modul de generare al permutărilor.

Aceste optimizări nu garantează însă întotdeauna o îmbunătăţire şi

pot fi dificil de implementat.

Problema se poate rezolva mai eficient folosind algoritmi genetici.

Deoarece se cere o singură permutare care să verifice anumite constrângeri

(ecuaţiile sistemului), putem începe cu un număr prestabilit (populaţia) de

permutări generate aleator (indivizi), pe care vom aplica apoi anumiţi

operatori genetici şi pe care le vom sorta după o funcţie de adecvare.

Procedeul se repetă până când se ajunge la o soluţie.

Corectitudinea şi eficienţa acestei metode stă aşadar în alegerea

operatorilor genetici şi a funcţiei de adecvare (fitness).

Propunem următoarele două funcţii de adecvare:

1. Prima funcţie, F1, calculează, pentru fiecare individ, numărul de

ecuaţii ale sistemului pe care permutarea le verifică. Evident, am

găsit o soluţie atunci când există un individ X pentru care

F1(X) = M.

2. A doua funcţie, F2, calculează, pentru fiecare individ,

unde f(i) este rezultatul evaluării expresiei i dacă înlocuim

fiecare necunoscută cu permutarea reprezentată de individul

curent, iar g(i) este rezultatul pe care trebuie să îl aibă expresia i,

adică numărul din dreapta egalului expresiei i. Am găsit o soluţie

atunci când există un individ X pentru care F2(X) = 0.

Ambele funcţii de adecvare se comportă similar din punct de vedere

al timpului de execuţie. Acelaşi lucru nu poate fi spus însă şi despre

operatorii genetici.

Primul lucru care trebuie observat este că nu putem păstra modelul

clasic al algoritmilor genetici, deoarece nu putem folosi nici operatorul de

recombinare (în caz contrar am genera permutări invalide, cu elemente care

se repetă), nici operatorul clasic de mutaţie (din acelaşi motiv).

O primă idee ar fi să folosim un operator de inversare: alegem

aleator două poziţii x1 şi x2, cu 1 ≤ x1 < x2 ≤ N şi inversăm secvenţa

cuprinsă între x1 şi x2. Acest lucru încalcă însă ideea principală din spatele

algoritmilor genetici: păstrarea unor trăsaturi ale elitelor din generaţia

curentă pentru a îmbunătăţi generaţiile următoare. Folosind operatorul de

inversare, se pierde informaţia din generaţia curentă.

Propunem următorul operator genetic, similar cu operatorul de

recombinare: se alege un individ oarecare din elitele generaţiei precedente,

din care se copiază primele x gene în cromozomul curent. Următoarele gene

se completează aleator, având grijă să nu avem două gene (o genă

reprezintă, practic, un element al permutării) identice. Astfel, generaţiile

următoare au şanse mai mari să fie mai aproape de rezolvarea problemei

decât generaţia curentă, iar îmbunătăţirea timpului de execuţie este evidentă

pentru un volum mai mare al datelor de intrare.

Putem folosi şi operatorul de mutaţie, dar şi acesta trebuie modificat

pentru necesităţile problemei. Mutaţia nu va mai avea loc asupra unei

singure gene, ci asupra a două gene. Vom alege două gene pe care le vom

interschimba, păstrând astfel proprietatea de permutare.

Structura de bază a algoritmilor genetici rămâne la fel. În consecinţă,

prezentăm doar acele funcţii care suferă modificări.

void calc_fitness()

{

for ( int cr = 1; cr < maxpop; ++cr )

{

A[cr].fitness = 0;

for ( int i = 1; i <= M; ++i )

{

int k = 1;

A[cr].fitness += abs(eval(k, cr, A, i) - egal[i]);

}

}

sort(A + 1, A + maxpop);

}

void noua_gen()

{

int v[maxn];

for ( int i = 1; i <= N; ++i )

v[i] = 0;

for ( int i = maxeli + 1; i < maxpop; ++i )

{

if ( rand() < prob_recomb )

{

int x1 = 1 + rand() % maxeli;

int poz = 1 + rand() % N;

for ( int j = 1; j <= poz; ++j )

{

v[ A[x1].var[j] ] = i;

A[i].var[j] = A[x1].var[j];

}

for ( int j = 1; j <= N; ++j )

if ( v[j] != i )

{

++poz;

A[i].var[poz] = j;

}

}

if ( rand() < prob_mutatie )

{

int x1 = 1 + rand() % N;

int x2 = 1 + rand() % N;

swap(A[i].var[x1], A[i].var[x2]);

}

}

}

Precizăm că implementarea aceasta foloseşte funcţia de adecvare

descrisă anterior ca F2.

Funcţia eval() evaluează expresia numărul i, înlocuind necunoscutele

cu valorile date de cromozomul cr. Aceasta a fost descrisă în cadrul

capitolului Algoritmi generali şi în cadrul problemei precedente.

Exerciţiu:

Implementaţi în întregime un program care rezolvă problema,

folosind, pe rând, ambii operatori genetici menţionaţi, precum şi ambele

funcţii de adecvare descrise. Comparaţi, pe mai multe date de intrare,

performanţele acestora.