1

I. STRATEGII N REZOLVAREA PROBLEMELOR

Goldstein i Levin (1987) au definit rezolvarea problemelor ca fiind procesul cognitiv de ordin nalt care necesit modulaia i controlul mai multor capaciti / ndemnri fundamentale, considernd-o cea mai complex dintre toate funciile intelectuale. Rezolvarea problemelor apare atunci cnd un organism sau un sistem ce posed inteligen artificial nu cunoate drumul de la o stare dat, ctre o stare scop dorit.

Procesul rezolvrii problemelor difer n funcie de domeniul de cunoatere i de nivelul de expertiz. Rezultate obinute n laboratoare de multe ori nu pot fi extinse pentru situaii reale, complexe. Din acest motiv, cele mai noi studii se concentreaz pe probleme ct mai complexe iar utilizarea calculatoarelor a devenit o necesitate.

n rezolvarea de probleme cu ajutorul calculatorului sunt utilizate dou strategii: abordarea determinist (care cuprinde algoritmi determiniti exaci i euristici) i abordarea probabilist.

Algoritmii determiniti produc aceeai soluie i urmeaz aceeai secven de stri pe o instan dat la execuii repetate.

Algoritmii determiniti exaci obin soluii exacte dar nu sunt tot timpul utilizabili n practic deoarece, de cele mai multe ori realizeaz o cutare exhaustiv n spaiul problemei. Considernd pentru rezolvare clasa algoritmilor determiniti, a fost stabilit ierarhia de complexitate a problemelor. Astfel, o problem are complexitatea dat de cel mai bun algoritm determinist precis cunoscut spre a o rezolva.

Euristicile sunt algoritmi determiniti care obin soluii aproximative. Cu ct precizia soluiei este mai bun, cu att complexitatea timp este mai mare.

Algoritmii probabiliti implic mcar un pas n care decizia se ia n mod aleatoriu. Acetia sunt algoritmi impredictibili, la repetri succesive se obin soluii diferite datorit unor pai ce depind de valori generate aleatoriu n timpul execuiei. Soluiile obinute sunt aproximative.

Un algoritm probabilist poate fi privit ca o distribuie de probabilitate peste o mulime de algoritmi determiniti. Dac este uor s se gseasc o instan a unei probleme care s ridice dificulti pentru unul sau mai muli algoritmi determiniti din aceast mulime, este dificil s se gseasc o singur intrare cu anse mari de a bate un algoritm ales aleatoriu. Aceast paradigm st la baza succesului oricrui algoritm probabilist (R. Motwani, P. Raghavan).

Din clasa algoritmilor probabiliti fac parte algoritmi precum Monte Carlo, Las Vegas i metaeuristicile (algoritmi evolutivi, clirea simulat1 etc.). Complexitatea timp pentru astfel de algoritmi crete odat cu precizia soluiilor. Algoritmii genetici utilizeaz o schem polinomial. De aceea unele strategii evolutive au o probabilitatea egal cu 1 s gseasc soluia exact.

Calitatea unei soluii aproximative se apreciaz cu ajutorul a doi indici: acurateea - care msoar distana fa de optim a valorii acelei soluii, i precizia - care msoar apropierea variabilelor soluiei de punctul n care se obine optimul (Fig.1.1.).

1 n literatura strin termenul este simulated annealing, termen care n limba romn a fost preluat i tradus, n diverse lucrri, n mai multe variante, normalizare, regenerare, recoacere, clire simulat.

2

Fig. 1.1. Fig. Precizia i acurateea unei soluii aproximative: f este funcia de evaluare; x reprezint parametrii funciei.

Metodele convenionale de rezolvare de probleme precum calculul diferenial, calculul integral, analiza numeric .a. sunt denumite tehnici hard computing. Aceste modele sunt rigide, statice, fr posibilitate de adaptare; ele sunt complet formulate n prealabil i nu se pot modifica cu nimic pe parcursul rezolvrii. Doar sisteme relativ simple pot fi descrise i analizate cu astfel de metode.

Existena sistemelor complexe din domenii precum biologia i medicina, a dus la apariia metodelor soft computing (Fig. 2.1.)care prezint posibilitate de auto-adaptare. Aceste metode sunt bazate pe feed-back-ul intern al algoritmului i al structurilor de date iar proprietile individuale ale instanei problemei sunt exploatate la maxim. Spre deosebire de metodele hard-computing care pun accent pe exactitate, tehnicile soft-computing exploateaz adevrul parial fcnd uz de modelarea i raionarea probabilist.

Principalele modele soft-computing sunt reelele neuronale artificiale, sistemele fuzzy (vagi) i calculul evolutiv. Dac primele dou modele sunt dezvoltri moderne ale unor tehnici din statistic i teoria mulimilor, calculul evolutiv a adus o abordare i un set de idei fundamental noi n modelare, n conceptul de calcul i n paradigma general de rezolvare a problemelor de optimizare.

Fig. 2.1. Calculul soft este situat ntre calculul convenional (hard) i sistemele de inteligen artificial.

3

II. ALGORITMI GENETICI I EVOLUTIVI. PRINCIPII GENERALE

Ideile inspirate de mecanismele evoluiei i seleciei naturale au condus la clase importante de algoritmi de cutare i optimizare. Astfel s-au pus bazele principiilor algoritmilor genetici i evolutivi.

II.1. Metafora evolutiv

Punctul de vedere acceptat n modelarea sistemelor n general este acela c ndeplinirea oricrei sarcini poate fi privit ca rezolvarea unei probleme. La rndul ei, rezolvarea unei probleme poate fi gndit ca o cutare n spaiul soluiilor posibile (spaiul strilor problemei). Aceast cutare poate fi ghidat de o funcie de performan (fitness). Procesul de cutare este n acest caz nsoit de un proces de optimizare: dintre soluiile posibile suntem interesai ntotdeauna de cea mai bun sau, uneori, ne putem mulumi doar cu o soluie suficient de bun (aproximativ optim).

Pentru probleme de mare complexitate, gsirea soluiei optime, sau chiar a uneia acceptabile, este dificil de realizat. Tehnicile clasice fie nu sunt aplicabile, fie necesit un timp de lucru prohibitiv. Algoritmii genetici (AG) sunt adecvai tocmai pentru soluionarea unor astfel de probleme dificile.

Algoritmii genetici (Holland, 1975) reprezint tehnici de cutare i optimizare avnd ca punct de pornire o metafor biologic. Aceast metafor biologic este reprezentat de motenirea genetic i evoluia natural.

n cursul evoluiei, toate organismele sunt confruntate cu problema adaptrii la un mediu complicat, n continu schimbare, sau ostil. n acest proces, fiecare specie nva, iar cunoaterea1 pe care a ctigat-o este codificat n cromozomii speciei. Evoluia este aadar un proces care are loc la nivelul cromozomilor. Caracteristicile unei fiine vii sunt stabilite printr-un proces de decodificare a cromozomilor si. Codificarea i decodificarea informaiei genetice la nivelul cromozomilor nu este nc pe deplin elucidat.

Din perspectiva care ne intereseaz n acest context, reinem doar cteva caracteristici eseniale ale procesului de evoluie genetic:

1. Cromozomii sunt purttorii informaiei genetice. 2. Fiecare individ al unei specii posed un numr determinat de cromozomi. Totalitatea cromozomilor unui individ reprezint genotipul su. 3. Cromozomii sunt structuri liniare alctuite din gene. Genele poart caracteristicile ereditare. O gen controleaz una sau mai multe caracteristici. Genele unei anumite caracteristici ocup locuri determinate n cromozom, numite loci. O gen poate fi n mai multe stri, numite alele (valori ale caracteristicilor). 4. Evoluia este un proces ce opereaz la nivelul cromozomilor. 5. Selecia natural reprezint legtura dintre cromozomi i performanele indivizilor (structurilor decodificate respective). Procesul seleciei naturale favorizeaz reproducerea acelor cromozomi ce codific structuri de succes. 6. Evoluia se realizeaz n procesul reproducerii. n evoluie acioneaz procese de selecie i mutaie. Foarte importante sunt procesele de recombinare a materialului genetic ce caracterizeaz prinii.

1 Selecie, ctig adaptativ.

4

n 1965, John Holland de la Universitatea Michigan a avut ideea de a aplica modelul genetic al evoluiei n rezolvarea unor probleme de cutare i optimizare. Sistemele construite n acest fel utilizeaz o populaie de cromozomi ce reprezint o mulime de soluii poteniale. Prin procese de selecie, mutaie i recombinare sistemul evolueaz spre stri mai apropiate de optim. Selecia cromozomilor pentru modificare se face folosind o funcie de evaluare (adecvare). Putem admite c aceast funcie descrie aciunea mediului.

Originea algoritmilor evolutivi poate fi pus n legtur cu unele lucrri din anii 50, cum ar fi cele ale lui Box (1957) i Fraser (1957).

Algoritmii genetici reprezint o clas de algoritmi evolutivi. Algoritmii evolutivi implementeaz proceduri care imit procesele de adaptare / cutare aprute n evoluia natural. Toi algoritmii evolutivi folosesc populaii n care fiecare individ reprezint un punct din spaiul de cutare. Algoritmii evolutivi se bazeaz pe principiul nvrii colective n cadrul unei populaii.

Programarea evolutiv (Fogel, Owens, Walsh, 1966), strategiile evolutive (Rechenberg, 1973; Schwefel, 1981) i algoritmii genetici sunt cele mai cunoscute tipuri de algoritmi evolutivi.

II.2. Algoritmul evolutiv

Algoritmii evolutivi reprezint mai multe clase de metode aleatorii de cutare. Fiecare individ al populaiilor implicate n procesul de cutare se descrie printr-un singur cromozom. Considerm aadar c genotipul fiecrui individ conine un singur cromozom.

Orice algoritm evolutiv (sau program evolutiv) folosete o populaie de indivizi (cromozomi) care este modificat prin intermediul unor operatori genetici cum ar fi cei de selecie, mutaie, recombinare etc. Timpul variaz discret. Notm cu P(t) populaia de cromozomi de la momentul t, unde t = 0, 1, 2,

Fie X spaiul de cutare (spaiul strilor problemei)1. Fiecare individ (cromozom) reprezint un element din X, adic o soluie posibil a problemei. Un cromozom este un ir finit peste elementele unui vocabular2. Evaluarea calitii indivizilor din spaiul de cutare se face cu ajutorul unei funcii de performan (fitness). n literatur apar diverse denumiri pentru aceast funcie, dar cu acelai sens, cum ar fi: funcie de potrivire, funcie de adecvare sau funcie de evaluare. Fie f: X R, funcia de performan (sau funcia de adecvare). Fiecare individ (soluie) este evaluat prin intermediul acestei funcii.

Dac considerm P(t) = { xt1, xt2, , xtn } populaia la momentul t, atunci, n acest caz P(t) reprezint o generaie. Noua generaie P(t+1) se formeaz selectnd cei mai performani indivizi din P(t) aplicnd asupra lor operatorii genetici de recombinare, mutaie etc.

II.2.1. Operatorii Operatorul de recombinare este folosit pentru a crea noi indivizi folosind segmente (subiruri) a doi sau mai muli cromozomi. Operatorul de recombinare se poate defini ca o aplicaie R : Xp Xq. n acest caz spunem c operatorul R realizeaz o transformare de tipul (p, q) n care p prini dau natere la q descendeni.

Operatorul de mutaie reprezint o transformare unar3 m : X X. Operatorul de mutaie m creeaz noi indivizi prin schimbri (mici) ale unui singur individ. De exemplu m permite schimbarea

1 Mulimea tuturor cromozomilor. 2 Toate combinaiile posibile ale caracterelor unui alfabet. 3 O modificare care nu implic un al doilea element. Ex. operaia logic de negare schimb valoarea elementului creia i se aplic. De aceea mutaia este considerat un operator unar pentru c transform coninutul cromozomului fr intervenia unui alt element suplimentar. Adunarea este un operator binar, ea necesit cel puin dou elemente.

5

unei singure gene a individului (cromozomului) respectiv, mutaia realiznd astfel mici perturbri ale cromozomilor obinui prin recombinare.

Operatorul de supravieuire decide care cromozomi (prinii i descendenii lor obinui prin recombinare i mutaie) vor forma efectiv noua generaie. Fiecare tip de algoritm evolutiv are un mecanism propriu ce realizeaz supravieuirea.

Populaia iniial se genereaz de regul prin selectarea aleatorie a unor puncte din spaiul de cutare. n unele cazuri cunotinele specifice despre domeniul problemei pot servi pentru a ghida cutarea. Criteriul de oprire pentru un algoritm evolutiv este de regul legat de numrul de generaii. Cel mai performant individ al ultimei generaii (sau cel mai performant individ din ntreaga istorie a procesului) reprezint soluia obinut pentru problema n discuie.

Consideraiile de mai sus conduc la urmtoarea structur a unui algoritm evolutiv:

II.2.2. Structura general a unui algoritm evolutiv O procedur evolutiv se desfoar n urmtorii pai.

P1. Se stabilete t = 0 ; P2. Se iniializeaz populaia P(t) ; P3. Se evalueaz P(t) utiliznd o funcie de performan f ; P4. Pn cnd (condiie) se execut { t = t + 1 ; Selecia P(t) ; Recombinarea asupra lui P(t) ; Mutaia asupra lui P(t) ; Evaluarea lui P(t ) ; Supravieuirea n P(t) ; }

Observaie: La pasul P4 apare o condiie de oprire a algoritmului. De regul, aceast condiie se refer la atingerea numrului de generaii prescris.

Orice procedur evolutiv trebuie s furnizeze urmtoarele elemente:

1. O reprezentare genetic a spaiului de cutare (spaiul strilor problemei sau spaiul soluiilor poteniale ale problemei). 2. O populaie iniial de soluii poteniale1. De regul, populaia iniial se alege n mod arbitrar. 3. O funcie de evaluare ce msoar performana fiecrui individ n raport cu scopul urmrit. 4. O metod de selectare a cromozomilor pentru modificare i recombinare (reproducere). 5. Operatorii genetici pentru crearea de noi cromozomi prin recombinare, mutaie, inversiune etc. 6. Valorile parametrilor ce apar n algoritmul evolutiv (dimensiunea populaiei, probabilitile de aplicare a diferiilor operatori genetici, numrul total de generaii etc.).

1 Se favorizeaz o populaie iniial capabil s genereze soluia convenabil.

6

II.2.3. Modulele unui algoritm evolutiv Din cele prezentate anterior rezult c un algoritm evolutiv are mai multe componente. Ele pot fi grupate n trei module:

Modulul Populaie; Modulul Evaluare; Modulul Recombinare i Mutaie.

Modulul Populaie Conine o metod pentru iniializarea unei populaii de cromozomi. Modulul conine tehnica de reprezentare a cromozomilor i tehnici pentru crearea i manipularea noilor generaii ale populaiei. n acest modul se specific felul n care se trece de la o populaie la alta. Aceast trecere se poate face prin nlocuirea total sau parial a cromozomilor generaiei vechi cu noua generaie de cromozomi. Modulul indic metoda de selecie a cromozomilor, dimensiunea populaiei i numrul total de generaii.

Modulul Evaluare Conine funcia de performan folosit pentru compararea cromozomilor.

Modulul Recombinare i Mutaie Conine metodele folosite pentru a crea noi cromozomi. Sunt specificai parametrii operatorilor genetici utilizai, cum ar fi probabilitatea de mutaie, probabilitatea de ncruciare etc.

II.3. Algoritmul genetic

ntr-un algoritm genetic, fiecare element al spaiului de cutare se poate reprezenta ca un individ (sau un cromozom) al unei populaii. Dup cum s-a precizat anterior, fiecare cromozom este constituit dintr-o mulime de elemente numite caracteristici sau gene. Fiecare gen se poate afla n mai multe stri, numite alele. Acestea din urm indic valori (nu neaprat numerice) ale caracteristicilor (genelor). n abordrile standard numrul de gene dintr-un cromozom este constant pentru o problem dat, iar numrul genelor definete lungimea cromozomului. Se va nota cu r lungimea cromozomilor unei populaii.

Fie V alfabetul1 ce corespunde valorilor alelelor. Un cromozom se reprezint printr-o secven de lungime r format cu elemente ale lui V. Rezult c orice cromozom este un element din Vr. Alfabetul V depinde de clasa de probleme la care se aplic algoritmul genetic. Lungimea cromozomilor este stabilit n funcie de natura problemei. Cea mai rspndit este codificarea binar a valorilor genelor. n acest caz, alfabetul este V = {0, 1}, iar un cromozom este o secven binar de lungime r 1.

II.3.1. Echilibrul explorare exploatare Fiecare cromozom reprezint o soluie potenial a problemei. Un algoritm genetic realizeaz cutarea n spaiul soluiilor problemei prin modificarea unei populaii de cromozomi. Cutarea soluiei ntr-un spaiu complex implic realizarea unui compromis ntre dou obiective aparent contradictorii: exploatarea celor mai bune soluii disponibile Ia un moment dat i explorarea eficient a spaiului soluiilor posibile. Cele dou aspecte corespund cutrii locale i respectiv cutrii globale n spaiul soluiilor problemei.

Obinerea unui echilibru ntre exploatarea informaiei obinute pn la momentul curent i explorarea spaiului strilor pentru a obine soluii noi, mai bune, este specific tuturor metodelor puternice de optimizare. Dac soluiile obinute sunt exploatate prea mult atunci se atinge o convergen prematur, iar procedura se oprete cu o soluie care poate s nu fie acceptabil. Pe 1 n cazul concret al macromoleculei de ADN alfabetul este limitat la ACGT

7

de alt parte, dac accentul cade prea mult pe explorare, este posibil ca informaia deja obinut s nu fie utilizat n mod corespunztor. Acest lucru face ca timpul de cutare s creasc foarte mult, ceea ce apropie procedurile respective de metodele aleatorii de cutare. Se va indica n continuare felul n care unele clase de metode rezolv problema echilibrului dintre exploatare i explorare.

Metodele de coborre (de tip gradient) reprezint o situaie extrem n compromisul explorare-exploatare. Ele sunt strategii care exploateaz cea mai bun soluie pentru mbuntiri ulterioare ale acestei soluii. Se neglijeaz ns explorarea spaiului de cutare i, n consecin, metoda sufer din cauza caracterului local al optimului gsit.

n mod similar, metoda Box (Box, 1957), dei este bazat pe utilizarea unei populaii de soluii poteniale, nu are nici un mecanism de explorare. Din acest motiv metoda nu este foarte eficient.

Metodele de cutare aleatorii reprezint cealalt situaie extrem. Cutarea pur aleatorie este un exemplu tipic de strategie care exploreaz spaiul de cutare, ignornd exploatarea regiunilor promitoare ale spaiului. Metodele de acest tip sunt lente i aceasta le face inaplicabile pentru probleme practice dificile.

Metoda clirii simulate (simulated annealing) reprezint o procedur de cutare aleatorie n care este prezent i exploatarea. Acest lucru se realizeaz printr-un mecanism ce asigur stabilirea unui echilibru la fiecare valoare a unui parametru care are semnificaia temperaturii termodinamice (Pentru detalii se poate consulta monografia Dumitrescu i Costin, 1996).

n contrast cu cele descrise, algoritmii genetici reprezint o clas de strategii de cutare general (strategii independente de domeniu) care realizeaz un compromis rezonabil ntre explorarea i exploatarea spaiului soluiilor. Studii teoretice (Holland, 1975) au artat c algoritmii genetici realizeaz acest compromis de o manier aproape optimal. Exploatarea i explorarea sunt aspecte ce pot fi controlate aproape independent, ceea ce permite o mare flexibilitate n proiectarea algoritmilor genetici.

II.3.2. Rezolvarea problemelor utiliznd algoritmi genetici Pentru rezolvarea unei probleme folosind un algoritm genetic este necesar definirea de ctre utilizator a unei funcii care msoar performana (adecvarea) fiecrui cromozom. Funcia de performan (adecvare) depinde de abilitatea utilizatorului de a codifica n mod adecvat problema sa. Dac se rezolv o problem clasic de optimizare sau una de optimizare combinatorial, funcia de adecvare poate coincide cu funcia criteriu (funcia obiectiv) asociat problemei sau se obine prin transformri simple (de exemplu prin scalare) aplicate funciei criteriu. n alte situaii funcia de evaluare reprezint o funcie de cost, o funcie de ctig etc., sau este dedus dintr-o astfel de funcie.

Un algoritm genetic este o procedur iterativ de cutare global avnd drept scop optimizarea funciei de evaluare. Algoritmul lucreaz n paralel asupra unei populaii de soluii poteniale (cromozomi) distribuite peste ntreg spaiul de cutare. n mod obinuit, valoarea performanei unui cromozom este independent de performanele celorlali indivizi ai populaiei. O alt posibilitate este de a considera o funcie de adecvare implicit ale crei valori depind i de restul populaiei prin intermediul anumitor interaciuni ntre indivizi. n acest caz putem vorbi de o adaptare intrinsec (Packard, 1988) ce asigur co-evoluia indivizilor (Kaufman i Johnsen, 1991).

Dinamica procesului de cutare generat de un algoritm genetic se ilustreaz prin combinarea i modificarea cromozomilor. Scopul este gsirea combinaiei optime, adic a acelei combinaii ce corespunde adecvrii maxime. La fiecare iteraie a algoritmului se creeaz o nou populaie, numit generaie. Toate generaiile au acelai numr de indivizi. Se admite c, n general, noua

8

generaie const din indivizi mai performani, adic mai bine adaptai la mediul reprezentat de funcia de adecvare. Pe msur ce se succed generaiile se va nregistra o tendin de evoluie a indivizilor spre optimul global al funciei de adecvare.

Obinerea unei noi generaii plecnd de la precedenta are loc n trei etape:

1. Evaluarea: algoritmul genetic calculeaz valoarea funciei de adecvare pentru fiecare individ al vechii populaii. 2. Selecia: algoritmul genetic selecioneaz indivizii unei populaii P(t) n funcie de performanele lor. Indivizii selecionai vor reprezenta o populaie intermediar P1. Cromozomii populaiei P1 devin prinii noii generaii P(t+1). 3. Recombinarea i modificarea: Algoritmul genetic recombin i modific indivizii selecionai. n acest scop se utilizeaz operatorii genetici de ncruciare (recombinare), mutaie, inversiune etc. Din punct de vedere algoritmic, operatorii genetici reprezint metode de a schimba local soluiile reprezentate de prini (mutaia i inversia) sau de a combina aceste soluii (ncruciarea), aceasta din urm constnd ntr-un transfer de gene ntre doi cromozomi.

Fiecrui operator genetic i corespunde o probabilitate de aplicare. Aceste probabiliti sunt parametri ai algoritmului. Operatorii genetici de recombinare i modificare se aplic, cu probabilitile respective asupra populaiei intermediare. Aplicnd operatorul de ncruciare asupra populaiei P1 se obine o populaie P2. Asupra indivizilor din P2 se aplic operatorii de mutaie, inversie etc. Indivizii din P2 mpreun cu acei indivizi din P1 care nu au suferit recombinarea vor constitui noua generaie P(t+1). Sunt posibile numeroase alte modaliti de a selecta cromozomii populaiei P(t+1).

II.3.3. Algoritmul genetic fundamental (AGF) Etapele implementrii i utilizrii unui algoritm genetic sunt urmtoarele:

- definirea elementelor algoritmului (reprezentarea, funcia de performan (fitness), mecanismul de selecie, operatorii genetici, parametrii). - proiectarea experimentului. - execuia experimentului. - interpretarea rezultatelor.

Analiza unui algoritm evolutiv se face empiric, pe baza rezultatelor unor experimente ce urmresc fie performana de calcul absolut a algoritmului studiat, fie compararea algoritmului genetic studiat cu un alt algoritm ce rezolv aceeai problem (studiu relativ). De aceea, n faza de proiectare a experimentului trebuie avut n vedere optimizarea algoritmului genetic, iar pentru faza de comparare, trebuie luate n considerare i alte tipuri de algoritmi dect cei genetici pentru efectuarea de comparaii.

n algoritmul genetic clasic, funcia de evaluare trebuie s fie strict pozitiv, iar asupra ei s se realizeze maximizare. Ambele condiii sunt uor de satisfcut atunci cnd funcia de performan este dat de o funcie real: funcia de evaluare poate fi uor modificat prin translarea cu o constant iar, dac este cazul, problema de minimizare poate fi exprimat ca problem de maximizare prin nmulirea cu -1 a funciei de performan.

Nu orice problem poate fi exprimat ca problem de optimizare a unei funcii reale. Pentru situaii n care funcia de performan nu are o expresie algoritmic sau este necunoscut (n unele aplicaii de inteligen artificial) se poate folosi evaluarea interactiv n care utilizatorul stabilete on-line performana fiecrui individ sau ierarhia generaiei.

Algoritmii genetici clasici sunt formulai pentru optimizarea uni-criterial. n practic ns, sunt numeroase probleme n care trebuie urmrite mai multe obiective. Un exemplu este problema

9

orarului n care, n afara constrngerilor de natur material care trebuie satisfcute (suprapunerea a dou cursuri n aceeai sal, resursele materiale ce trebuie distribuite ntre profesori sunt limitate: videoproiector, laptop etc.), sunt necesare i optimizri din punct de vedere al timpului alocat (ct mai puine ferestre n orarul unui profesor/student).

Soluia preferat n rezolvarea unor astfel de probleme este construirea unui criteriu global (modele liniare sau neliniare) n care fiecrui subcriteriu i se acord mai mult sau mai puin importan.

Algoritmii genetici sunt algoritmi care mbuntesc soluia pas cu pas de-a lungul mai multor generaii. Exist probleme ns de tipul acul n carul cu fn care prin formulare nu permit o mbuntire pas cu pas. Un exemplu n acest sens este problema satisfiabilitii1 n care, fiind dat o formul n logica boolean, peste un numr de k variabile booleene, se cere o asignare a acestora astfel nct ntreaga formul sa fie satisfiabil (rezultatul evalurii s fie 1 ca echivalen a valorii booleene adevrat). Pentru o astfel problem poate fi scris un algoritm genetic clasic n care reprezentarea soluiilor se face sub forma unui ir de k bii, iar operatorii genetici sunt cei standard. Funcia de performan (fitness) d valoarea de adevr a expresiei booleene sub asignrile date de cromozomi. Dificultatea rezid n faptul c evalund cromozomii cu o funcie de performan (fitness) ce are doar dou valori, nu se poate face o mbuntire pas cu pas, iar nvarea devine imposibil. Trebuie gsit o modalitate de a ierarhiza indivizii ne-satisfiabili iar acest lucru este posibil utiliznd cunotine suplimentare din domeniul problemei. O soluie este exprimarea problemei n form normal conjunctiv echivalent. Pentru o astfel de formulare a problemei, mbuntirea soluiilor poate fi realizat pas cu pas considernd ca funcie de performan numrul de termeni care se evalueaz la valoarea boolean adevrat.

Structura unui algoritm genetic este identic, n esen, cu cea a unei proceduri evolutive. Cromozomii utilizai au lungime constant. Populaia (generaia) P(t+1) la momentul (t+1) se obine reinnd toi descendenii populaiei P(t) i tergnd apoi complet cromozomii generaiei precedente (P(t)). Numrul cromozomilor n fiecare generaie este constant. Principalii operatori genetici utilizai sunt cei de mutaie, ncruciare i inversiune. Algoritmul genetic standard (algoritmul canonic) are ca operatori principali ncruciarea i mutaia. Structura acestui algoritm genetic se poate reprezenta astfel:

P1. Se stabilete t = 0 ; P2. Se iniializeaz aleatoriu populaia P(t) ; P3. Se evalueaz. cromozomii populaiei P(t) ; n acest scop se utilizeaz o funcie de performan ce depinde de problema dat. P4. Ct timp (nu se ntrunete condiia C) execut:

P4.1. Selecteaz cromozomii din P(t) care vor contribui la formarea noii generaii. Fie P1 mulimea cromozomilor selectai. (P1 reprezint o populaie intermediar) ; P4.2. Se aplic cromozomilor din P1 operatorii genetici. Cei mai utilizai sunt operatorii de mutaie i ncruciare. n funcie de problem se pot alege i ali operatori (inversiune, reordonare, operatori speciali) ; Fie P2 populaia astfel obinut (descendenii populaiei P(t)). Se terg din P1 prinii noilor indivizi obinui. Cromozomii rmai n P1 sunt atribuii populaiei P2. Se construiete noua generaie: P(t+1) = P2 ;

1 n logica matematic, satisfiabilitatea i validitatea sunt concepte elementare de natur semantic. O formul este satisfiabil dac exist posibilitatea de a gsi o interpretare (model) care s o fac adevrat. O formul este valid dac toate interpretrile sale sunt adevrate.

10

Se terg toi cromozomii din P(t) ; Se modific t = t+1 ; Se evalueaz P(t) ;

Sfrit Ct timp ;

Observaii:

1. Condiia de oprire C se refer, de regul, la atingerea numrului de generaii specificate. Dac numrul maxim admis de generaii este N, atunci condiia de oprire C este t > N.

2. De obicei se admite c rezultatul algoritmului este codificat de cel mai performant individ din ultima generaie. n realitate, nimic nu ne garanteaz c un individ mai performant nu a fost obinut ntr-o generaie anterioar. Este deci natural ca la fiecare pas (la fiecare moment t) s reinem cel mai bun individ care a fost generat pn atunci. Pentru a implementa aceast strategie sunt necesare cteva mici modificri n algoritmul de mai sus.

3. Modificarea propus n observaia precedent poate fi extrem de util. n acest fel suntem siguri c cea mai bun soluie gsit nu s-a pierdut pe parcurs. Natura acestei modificri este similar cu cea propus de Gallant n raport cu algoritmul de instruire al perceptronului1 (vezi, Dumitrescu i Costin, 1996).

4. Sunt posibile i numeroase alte variante de supravieuire. Putem de exemplu s considerm c cei mai buni q indivizi din generaia P(t) vor fi inclui n mod automat n generaia urmtoare. Totodat ei vor putea s sufere i operaiile de recombinare, mutaie etc.

I.3.4. Modulele unui algoritm genetic Implementarea unui algoritm genetic se poate face utiliznd modulele POPULAIE, EVALUARE i RECOMBINARE-MODIFICARE specifice algoritmilor evolutivi. Structura acestor trei module corespunztoare Algoritmului Genetic Fundamental (AGF) poate fi descris sintetic astfel:

MODULUL POPULAIE

Metoda de reprezentare: codificare binar sau codificare real. Lungimea cromozomului: r . Metoda de iniializare: iniializare aleatorie. Metoda de tergere: terge vechea populaie n ntregime (sau alt metod). Metoda de nlocuire: nlocuire cu noua generaie. Metoda de selecie pentru modificare i reproducere: metod probabilistic (de exemplu selecia uniform cu metoda Monte Carlo). Metoda de apreciere a adecvrii: evaluarea cu o funcie de evaluare. Dimensiunea populaiei: n1 . Numrul maxim de generaii: n2 .

MODULUL EVALUARE

Funcia de evaluare:

MODULUL RECOMBINARE-MODIFICARE

Operatorii genetici utilizai: mutaia, ncruciarea, inversiunea. Parametrii algoritmului: - probabilitatea de mutaie: pm

1 n cadrul nvrii automate (machine learning), perceptronul este un tip de clasificator linear. Acesta ia o decizie de clasificare pe baza unei valori obinut dintr-o combinaie liniar de caracteristici.

11

- probabilitatea de ncruciare: pc - probabilitatea de inversiune: Pi

I.3.5. Scheme i blocuri constructive Algoritmii genetici utilizeaz operatori coninnd copierea cromozomilor, schimbarea unor subiruri i modificarea unor poziii. Astfel se poate realiza o cutare eficient. Modelul descris n continuare se bazeaz pe observarea anumitor similariti ntre cromozomii care reprezent dou populaii succesive obinute prin aplicarea unui AG. n general este de ateptat ca performana medie a populaiei s creasc de la o generaie la alta. Similaritile ntlnite ar putea fi corelate cu aceast cretere a performanei. n literatura de specialitate, similaritile dintre cromozomi se numesc scheme. Mai precis, o schem reprezint o mulime de cromozomi avnd anumite poziii identice.

n codificarea binar, o schem este un ir format cu simbolurile 0, 1 i *. Simbolul * ntr-o poziie a irului nseamn c aceast poziie poate fi ocupat de orice simbol al alfabetului binar {0, 1}.

Exemplul 1: fie schema S = (1 * * 0)

Aceast schem reprezint patru cromozomi, avnd 1 pe prima poziie i 0 pe ultima poziie. Aceti cromozomi vor fi:

x1 = 1 0 0 0 x2 = 1 0 1 0 x3 = 1 1 0 0 x4 = 1 1 1 0

Exemplul 2: pornind de la o soluie cunoscut, avem cromozomul:

x = 1 0

Acesta este reprezentat de 22 scheme. Aceste scheme sunt urmtoarele:

S1 = * * S2 = * 0 S3 = 1 0 S4 = 1 *

Cromozomul x considerat este o instan1 sau un reprezentant al fiecreia dintre schemele S1 - S4. Pentru noiunile introduse mai sus pot fi enunate urmtoarele definiii:

O schem de lungime r este un element al mulimii {0, 1 ,*}r

Fie S o schem de lungime r. Spunem c un cromozom x {0, 1}r este o instan a schemei S dac oricrei poziii diferite de * din S i corespunde o poziie din x avnd aceeai valoare.

Se numete poziie specific a schemei S orice poziie din S diferit de *. Simbolul * are semnificaia indiferent, adic poziia respectiv poate fi, cu egal ndreptire, 0 sau 1.

O schem S reprezint toi acei cromozomi x pentru care toate poziiile specifice ale lui S coincid cu poziiile corespunztoare din x. Cromozomul x este un reprezentant al (o instan a) schemei S.

Exemple:

Schema S1 = (* * *) reprezint toi cromozomii de lungime 3. Schema S2 = (1 0 1) reprezint un singur cromozom i anume x = (1 0 1).

1 Altfel spus, instana este un caz concret (particular) pentru o schem.

12

Deoarece o schem reprezint anumii cromozomi similari rezult c o schem poate fi identificat cu o anumit regiune a spaiului X al cromozomilor de lungime r. Aadar, schemele reprezint submulimi ale spaiului de cutare. Din punct de vedere geometric, schemele reprezint drepte, varieti liniare, sau hiperplane1 n spaiul de cutare.

Urmtoarea propoziie stabilete un rezultat elementar privind numrul reprezentanilor unei scheme: Fiecare schem S reprezint 2m cromozomi (S are 2m instane), unde m este numrul simbolurilor * (numrul poziiilor nespecifice) din schema S.

Demonstraia se face prin inducie matematic:

m = 1 avem S1 = {*} => (x = 0 i x = 1) => 2 instane deci 21. m = 1 avem S2 = {* *} => (x = 1 1; x = 1 0; x = 0 1; x = 0 0) => 4 instane deci 22.

m = n avem Sn = {* *} => 2n instane (considerm adevrat) m = n + 1 avem Sn+1 = {* *, *} => 2n+1 instane pentru c atunci cnd x = ** (de n ori) dac adugm nc o poziie (n+1 ori), aceast poziie conform schemei nu poate lua dect dou valori 1 sau 0. Deci dac x = ** = 2n instane, adugnd nc o poziie, relaia devine x = **1 sau x = **0 deci matematic se poate scrie c 2n2 = 2n+1 instane.

Exemplu:

Schema: S = 1 * 0 * are patru instane: x1 = 1 0 0 0; x2 = 1 0 0 1; x3 = 1 1 0 0; x4 = 1 1 0 1. Aadar, schema S descrie mulimea {x1, x2, x3, x4} din spaiul de cutare.

I.3.6. Teorema schemelor Ordinul unei scheme este dat de numrul de poziii specifice, iar lungimea util este diferena dintre ultima i prima poziie specific a schemei.

Adecvarea (performana, calitatea) unei scheme ntr-o populaie poate fi definit ca fiind adecvarea medie a reprezentanilor (instanelor) ei n acea populaie.

Teorema schemelor indic tocmai faptul c evoluia generaiilor are loc n sensul creterii performanei, iar rezultatul stabilit de teorema schemelor are un caracter probabilistic.

Teorema schemelor:

O schem avnd o adecvare (performan) peste medie, valori mici ale ordinului i lungimii utile, tinde s apar mai frecvent n cromozomii generaiei urmtoare. Dimpotriv, o schem avnd o adecvare sub medie tinde s apar mai puin frecvent (s aib mai puini reprezentani) n generaiile urmtoare.

I.3.7. Blocuri constructive i paralelismul intrinsec Un algoritm genetic manipuleaz simultan un mare numr de scheme. Aceast caracteristic reprezint paralelismul intrinsec al algoritmilor genetici. Teorema schemelor ne asigur c paralelismul intrinsec este asociat cu creterea adecvrii n generaiile succesive.

O categorie special de scheme o reprezint blocurile constructive. Astfel, o schem ce are o calitate peste medie, dar are un ordin i o lungime util mici se numete bloc constructiv.

1 n geometrie, hiperplanul este un subspaiu cu o dimensiune mai mic (n-1) dect spaiul fa de care este definit. De ex. un punct este un hiperplan ntr-un spaiu 1-dimensional, o linie este un hiperplan ntr-un spaiu 2-dimensional, un plan este un hiperplan ntr-un spaiu 3-dimensional. O linie nu este ns un hiperplan ntr-un spaiu 3-dimensional, ea nu poate s separe spaiul n dou pri.

13

Conform teoremei schemelor, prin aciunea operatorilor genetici, blocurile constructive se combin dnd natere la blocuri constructive tot mai performante, care vor converge spre soluia optim.

I.3.8. Caracteristicile algoritmilor genetici Algoritmii genetici reprezint o clas important de metode de cutare i optimizare. Aceste metode se bazeaz pe principiile geneticii i seleciei naturale. Din consideraiile expuse anterior se pot desprinde principalele caracteristici ale algoritmilor genetici. Aceste caracteristici se refer mai ales la particularitile acestora n raport cu alte metode de cutare i optimizare.

1. Algoritmii genetici reprezint o clas de algoritmi probabiliti care combin elemente de cutare dirijat i cutare aleatorie. Ei realizeaz un echilibru aproape optimal ntre explorarea spaiului strilor i exploatarea celor mai bune soluii gsite.

2. Algoritmii genetici sunt mai robuti dect alte metode existente de cutare dirijat i dect algoritmii clasici de optimizare.

3. Metodele de cutare bazate pe algoritmii genetici sunt caracterizate de faptul c ele menin o populaie de soluii poteniale. Metodele clasice de cutare acioneaz la un moment asupra unui singur punct din spaiul de cutare.

4. De regul, algoritmii genetici lucreaz cu o codificare a elementelor din spaiul strilor problemei i nu acioneaz direct asupra elementelor acestui spaiu.

5. Algoritmii genetici folosesc funcii de performan obinute prin transformri simple ale funciei obiectiv. Nu este necesar ca funcia obiectiv s fie derivabil. Nu sunt necesare nici proprieti speciale de convexitate ale funciei obiectiv.

6. Algoritmii genetici sunt simplu de folosit.

7. Algoritmii genetici pot gsi soluiile optime (sau aproape optime) cu o mare probabilitate.

BIBLIOGRAFIE

Box G. E. P. (1957), Evolutionary operation: a method of increasing industrial productivity, Applied Statistics, 6, 81-101.

Davis L. (1991), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York.

FogeI L. J., Owens A. J., Walsh M. J. (1966), Artificial lntelligence Through Simulated Evolution, Wiley, New York.

Fraser A. S. (1957), Simulation of genetic systems by automatic digital computers, Australian Journal of Biological Science, 10, 484-491.

Holland J. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.

Rechenberg I. (1973), Evolutionstrategic: Optimierung Technischen Systeme nacht Prinzipen der Biologischen Evolution, Fromman Holzboog, Stuttgart.

Schwefel H. P. (1981), Numerical Optimization for Computer Models, Wiley, Chicester, U.K.

I. STRATEGII N REZOLVAREA PROBLEMELORII. ALGORITMI GENETICI I EVOLUTIVI. PRINCIPII GENERALEII.1. Metafora evolutivII.2. Algoritmul evolutivII.2.1. OperatoriiII.2.2. Structura general a unui algoritm evolutivII.2.3. Modulele unui algoritm evolutiv

II.3. Algoritmul geneticII.3.1. Echilibrul explorare exploatareII.3.2. Rezolvarea problemelor utiliznd algoritmi geneticiII.3.3. Algoritmul genetic fundamental (AGF)I.3.4. Modulele unui algoritm geneticI.3.5. Scheme i blocuri constructiveI.3.6. Teorema schemelorI.3.7. Blocuri constructive i paralelismul intrinsecI.3.8. Caracteristicile algoritmilor genetici