1. Bazele teoretice ale calculului evolutiv. Evoluia cutare direct-cutare stochastic. Componentele si clasificarea algoritmilor evoluioniti

IntroducereIdeea de a aplica principiile darwiniste ale evoluiei n rezolvarea automat a problemelor (Problem Solving - PS) dateaz din anii 1940, naintea apariiei calculatoarelor electronice. n 1948 Turing propunea o tehnic de rezolvare a problemelor numit cutare genetic sau evolutiv. n anii 1960 Fogel, Qwens i Walsh introduceau conceptul de programare evolutiv (sau evoluionist), n timp ce Holland dezvolta algoritmii genetici. n aceeai perioad, Rechenberg i Schwefel introduceau strategiile evolutive (evoluioniste) ca modaliti alternative de rezolvare automat a problemelor. n anii 1990, Koza dezvolt o nou tehnic de cutare n spaiul soluiilor, programarea genetic. n terminologia actual, ntregul spectru de metode de rezolvare automat de inspiraie darwinist este desemnat prin termenul de calcul evolutiv (evoluionist) i include subdomeniile: programare evolutiv, strategii evolutive, algoritmi genetici i programare genetic.Calculul evolutiv este un domeniu al informaticii inspirat din procesul evoluiei naturale; ideea care st la baza calculului evolutiv este conexiunea evoluie natural tehnica de rezolvare a problemelor de tip experiment-eroare (sau generare-testare). Cu alte cuvinte, ntr-un mediu dat, indivizii constituii ntr-o populaie intr n competiie pentru a supravieui i a se reproduce. Abilitatea indivizilor de a-i atinge aceste scopuri n mediul n care triesc este strict corelat cu ansele lor de supravieuire i multiplicare i determin evoluia n timp a populaiei. n contextul modalitii de rezolvare a problemelor de tip generare-testare stochastice, populaia este modelat ca o colecie de elemente candidat la soluie. Calitatea candidailor la soluie, definit n termenii gradului n care fiecare element rezolv problema, determin ansa lor de a fi meninui i utilizai pentru construirea unor noi candidai.

Suportul de natur biologic al calculului evolutivTeoria evoluionist a lui Darwin ofer o explicaie a diversitii biologice i a mecanismului care st la baza acesteia. n centrul interpretrii macroscopice a evoluiei este plasat selecia natural. Considernd un mediu care poate susine un numr limitat de indivizi i instinctul primar al fiecrui individ de a se reproduce, procesul de selecie este esenial i inevitabil n controlul dimensiunii populaiei. Selecia natural favorizeaz indivizii cei mai competitivi n nsuirea resurselor, adic acei indivizi care sunt cel mai bine adaptai condiiilor de mediu. Fenomenul este cunoscut drept supravieuirea celor mai bine adaptai/potrivii (survival of the fittest). Teoria evoluiei are ca principii fundamentale selecia bazat pe competiie i variaiile de fenotip n rndul membrilor populaiei. Fenotipul este ansamblul de nsuiri i caractere care se manifest n mod vizibil la un individ i care este determinat pe baz ereditar i de condiiile de mediu (DEX). Caracteristicile fenotipului unui individ determin gradul lui de adaptabilitate la condiiile de mediu (fitness). Fiecare individ reprezint o combinaie unic de caracteristici ale fenotipului i este evaluat de condiiile de mediu. Dac evaluarea este favorabil, atunci fenotipul individului este propagat spre urmai (progenituri), altfel caracteristicile fenotipului dispar i individul moare fr a se putea reproduce. Viziunea lui Darwin despre evoluie este aceea c, n procesul trecerii de la o generaie la alta prin reproducere, apar mutaii (variaii) mici, aleatoare, n caracteristicile fenotipului. Ca rezultat al acestor variaii, apar i sunt evaluate noi combinaii de caracteristici ale fenotipului. Cele mai bune dintre ele supravieuiesc i se reproduc i n acest mod evoluia conduce la progres. Modelul primar poate fi deci rezumat dup cum urmeaz. O populaie este format dintr-un numr de indivizi, privii ca uniti de selecie; succesul fiecrui individ n ncercarea de a se reproduce depinde de ct de bine este adaptat condiiilor de mediu comparativ cu restul indivizilor. Pe parcursul reproducerii celor mai buni (bine adaptai la mediu) indivizi, apar mutaii ocazionale, care genereaz noi indivizi, ce vor fi ulterior evaluai. n consecin, pe msur ce timpul trece, se produc schimbri n structura populaiei, cu alte cuvinte populaia reprezint o unitate a evoluiei. ntregul proces poate fi asimilat din punct de vedere intuitiv cu modelul unui peisaj adaptiv (dinamic) (respectiv o suprafa adaptiv) n spaiul 3D (0-x-y-z). Fiecare punct p(x,y,z) al suprafeei este asimilat unui individ, unde n planul x-y este figurat combinaia de caracteristici ale fenotipului individului, iar altitudinea lui p (valoarea lui pe axa 0z) corespunde nivelului de adaptabilitate (fitness) a individului reprezentat de p. n acest context, evoluia este procesul de avans al populaiei spre zone aflate la o altitudine mai mare, acest avans fiind realizat pe baza mutaiilor i seleciei naturale. Este obinut astfel legtura cu conceptul de probleme multimodale, adic probleme n care exist o mulime de puncte de optim local (superioare tuturor soluiilor din vecintatea lor), cel mai bun element al mulimii fiind optimul global. O problem n care exist un singur optim local este numit unimodal.Legtura dintre procesul evoluiei i un proces de optimizare este pe ct de direct, pe att de neltoare, pentru c evoluia nu presupune ntotdeauna creterea global a calitii populaiei (n termenii funciei de fitness). Deoarece, la fiecare epoc, populaia este finit i operatorii de selecie i mutaie includ componente aleatoare, poate fi constatat o inactivitate genetic, manifestat fie prin dispariia din populaie a unor indivizi foarte adaptai condiiilor de mediu, fie prin variaia foarte mic sau chiar lipsa de variaie a unor caracteristici ale fenotipului indivizilor din populaie. Unul din efectele posibile este acela al concentrrii indivizilor ntr-o zon de adaptabilitate sczut. Efectul rezultat prin combinarea procesului de selecie cu inactivitatea genetic poate conduce n egal msur la creterea nivelului de adaptabilitate global a populaiei, respectiv la descreterea acestuia. n plus, nu exist nici o garanie c, dac evoluia duce la creterea calitii populaiei, nivelul de optim local nu a fost deja atins naintea unui fenomen de inactivitate genetic. n scopul evitrii ciclrii evoluiei populaiei ntr-o regiune de optim local, au fost dezvoltate o serie de teorii, una dintre cele mai cunoscute fiind teoria lui Wright conform creia poate fi determinat optimul global n cazul unei suprafee fixe (teorie referit drept shifting balance).

Tipuri de probleme ce pot fi rezolvate pe baza calculului evolutivn literatura de specialitate sunt evideniate dou clase de metode PS de inspiraie biologic: calculul neuronal (neurocomputing), prin intermediul cruia problemele sunt rezolvate imitnd modul de funcionare (raionament) a (al) creierului uman i procesele de tip evolutiv, problemele fiind rezolvate prin imitarea crerii creierului uman.n general, un sistem funcional de rezolvare automat a problemelor conine trei componente: datele de intrare, datele de ieire i modulul intern care conecteaz primele dou componente. Modalitatea de funcionare a modelului permite explicarea modului de funcionare a sistemului, n sensul c, rspunsul sistemului poate fi calculat pentru orice date de intrare specificate. n funcie de componentele din sistem cunoscute, pot fi difereniate urmtoarele tipuri de probleme: Probleme de optimizare: sunt cunoscute modelul i datele de ieire dorite (respectiv o descriere a acestora), iar problema este de a determina datele de intrare care corespund rezultatelor dorite. Un exemplu de astfel de problem este cea a comis voiajorului (n care trebuie determinat cea mai scurt sau ieftin rut care s lege un numr dat de orae): modelul este cunoscut i corespunde formulei de calcul a lungimii unei rute date, n care lungimea (sau costul) calculat (calculat) este data de ieire. Proprietatea pe care rezultatul trebuie s o ndeplineasc este un criteriu de optim (lungime minim), iar problema este de a determina acea dat de intrare, corespunztoare unei rute, care s conduc la rezultatul dorit. O problem de optimizare rezolvat cu succes prin calcul evolutiv este generarea orarului n cadrul unei universiti. n cursul unei zile sunt programate n general mii de activiti, restriciile pe care trebuie s la ndeplineasc o programare corect a acestora fiind multiple iar soluiile fezabile ale problemei n numr foarte mic relativ la mulimea tuturor programrilor posibile. Probleme de modelare sau de identificare a sistemului: sunt cunoscute datele de intrare i rezultatele corespunztoare lor, iar modelul este necunoscut. Modelul trebuie determinat astfel nct, pentru fiecare intrare dat, s calculeze rezultatul corect. Un exemplu de astfel de problem: clasificarea supervizat n cazul modelului cu dou clase. Problema este de a determina un clasificator care s separe corect elementele celor dou clase. Datele de intrare corespund elementelor celor dou clase, pentru fiecare dat de intrare rezultatul fiind eticheta clasei de provenien. Identificarea modelului revine la determinarea unei funcii de decizie, care, de exemplu, s calculeze valori pozitive pentru exemplele care provin din prima clas, respectiv valori negative pentru celelalte. Cu alte cuvinte, n acest caz scopul este de a determina o formul (n acest caz expresia analitic a unei funcii de decizie) care s lege datele de intrare (cunoscute) de rezultate (cunoscute). Problemele de acest tip apar n medii n care sunt disponibile foarte multe date (observaii, nregistrri etc.), de exemplu n situaii n care exist un set de dimensiuni considerabile de observaii/nregistrri asupra/relative la un fenomen/ eveniment. Identificarea modelului care s explice conexiunile dintre datele de intrare i rezultate trebuie realizat i astfel nct acesta s asigure o capacitate de generalizare rezonabil (pentru noi date de intrare, sistemul trebuie s furnizeze n general rspunsuri corecte). Astfel de probleme sunt cele din domeniile instruirii automate (machine learning) i data mining. Probleme de simulare: sunt cunoscui modelul i o serie de date de intrare i cerina este de a determina datele de ieire corecte, corespunztoare intrrilor date. Un exemplu de probleme de simulare care pot fi rezolvate utiliznd calculul evolutiv sunt cele n care este cutat rspunsul la ntrebri de tipul ce se ntmpl dac (what-if questions), n condiiile n care problema subiectului investigat evolueaz (n termenii operaiilor de variaie i selecie). Economia evolutiv este un domeniu de cercetare relativ nou, care, n principiu, are la baz ideea c jocul i juctorii din arena socio-economic sunt asemenea evoluiei vieii (a jocului i juctorilor ei).

2. Algoritmi evolutivi

n literatura de specialitate sunt prezentate diverse clase de algoritmi evolutivi (EA Evolutionary Algorithms), toate avnd la baz acelai principiu: dat fiind o populaie de indivizi, influena mediului determin un proces de selecie natural (indus de adaptabilitatea fiecrui individ la mediu), care are ca efect creterea global a calitii populaiei, exprimat prin intermediul funciei de fitness.

2.1. Schema general a algoritmilor evolutivi Dac este cunoscut o funcie de tip calitate care trebuie maximizat, setul iniial de candidai la soluie (elemente din mulimea ) poate fi generat aleator, fiind obinut astfel populaia iniial, (). Pentru fiecare , reprezint calitatea candidatului x (ca msur abstract de evaluare funcie de tip fitness). Populaia urmtoare este determinat pe baza funciei de evaluare prin aplicarea urmtorului mecanism. Este selectat , o submulime a lui format din cei mai buni membri ai populaiei curente, adic din acele elemente cu cele mai bune scoruri obinute n urma evalurii prin . Membrii mulimii genereaz populaia urmtoare prin aplicarea operatorilor de recombinare i/sau mutaie. Operaia de recombinare (recombination) este definit pentru doi sau mai muli indivizi din mulimea (numii prini) i are ca rezultat unul sau mai muli noi candidai la soluie (numii copii). Operatorul mutaie este definit pe un element al mulimii i are drept rezultat un nou candidat la soluie. Prin aplicarea operatorilor de recombinare i mutaie sunt generai noi indivizi (numii progenituri ai mulimii ) care intr n competiie, pe baza msurii de fitness (posibil i a vrstei), cu elementele populaiei pentru obinerea unui loc n populaia urmtoare, . Procesul poate fi iterat fie pn la obinerea unui candidat suficient de bun (soluia problemei, corespunznd unui punct de maxim al funciei ), fie pn la atingerea unei limite de calcul date.n cadrul acestui proces intervin dou elemente fundamentale care constituie baza sistemelor evoluioniste: operatorii de variaie (recombinare i mutaie), care asigur diversitatea necesar crerii de indivizi cu caracteristici noi i selecia, care foreaz creterea calitii indivizilor unei populaii.

Combinarea aplicrii operatorilor de variaie i selecie determin n general creterea calitii globale de la o populaie la populaia urmtoare. Un astfel de algoritm poate fi privit ca o evoluie a procesului de optimizare prin apropierea succesiv de valoarea optim. Alternativ, procesul evolutiv poate fi considerat un proces de adaptare. Din aceast perspectiv, msura de adaptabilitate (de fitness) este o expresie a cerinelor mediului n care evolueaz populaia i nu o funcie obiectiv care trebuie optimizat. Msura n care sunt atinse cerinele mediului este direct proporional cu msura de viabilitate i este reflectat n numrul de progenituri. Procesul evolutiv determin obinerea de populaii succesive din ce n ce mai bine adaptate mediului n care triesc.O serie de componente ale unui proces evolutiv sunt stochastice. De exemplu, dei indivizii mai bine adaptai mediului au o ans mai mare s fie selectai pentru generarea de noi candidai soluie, n cele mai multe tipuri de implementri evolutive i indivizii mai slabi au o ans de a deveni printe sau de a supravieui (n sensul selectrii lor n populaia sau generaia urmtoare). De asemenea, n cadrul operaiei de recombinare, alegerea perechilor sau n-tuplurilor (secvene de n elemente) de indivizi care interschimb material genetic, dar i prile (fraciunile) de material genetic interschimbat sunt aleatoare. n mod similar, la efectuarea unei mutaii, att poriunile din individ care vor suferi mutaia ct i noile pri care le nlocuiesc sunt alese aleator. n continuare este prezentat schema general a unui algoritm evolutiv.

Pas1. Iniilizarea populaiei: este obinut prin generarea aleatoare a candidailor la soluiePas2. Evaluarea candidailor: pentru fiecare , determin Pas3. Repet3.1. Selecteaz mulimea de prini 3.2. Recombin perechi (sau n-tupluri) de prini3.3. Efectueaz mutaii asupra progeniturilor rezultate3.4. Evalueaz noii candidai la soluie3.5. Selecteaz indivizii pentru constituirea generaiei urmtoare, ; 3.6. pn cnd (Condiie_terminare este satisfcut)

Observaii1. Schema prezentat mai sus corespunde familiei metodelor PS de tip generare-testare, pe baza urmtoarelor consideraii. n cadrul algoritmilor evolutivi sunt procesai simultan membrii unei ntregi populaii, combinarea informaiilor oferite de doi sau mai muli candidai fiind realizat n principal prin operaia de recombinare. De asemenea, algoritmii evolutivi sunt de tip stochastic. 2. Funcia de evaluare (de fitness) este o estimare de tip euristic a calitii fiecrui membru al populaiei curente, iar procesul de cutare este dirijat de operatorii de variaie i selecie.

Diferitele tipuri de algoritmi evolutivi menionai n partea 1 respect schema general prezentat mai sus i difer ntre ele printr-o serie de detalii tehnice, cum este de exemplu modalitatea de reprezentare a unui candidat la soluie (tipul sau structura de date utilizat/utilizat pentru reprezentarea membrilor populaiei). n cazul clasei algoritmilor genetici (GA Genetic Algorithms), un candidat la soluie este reprezentat prin intermediul unui ir definit pe un alfabet finit. Strategiile evolutive (ES Evolution Strategy) utilizeaz vectori cu numere reale pentru a reprezenta membrii populaiei, n timp ce n programarea evolutiv (EP Evolutionary Programming) sunt utilizate reprezentrile prin maini cu stri finite. Clasa algoritmilor GP (programare genetic) este dezvoltat pe baza reprezentrilor candidailor la soluie prin intermediul structurii de arbore. Selectarea unei reprezentri a membrilor populaiei n detrimentul altor variante posibile este realizat astfel nct s fie cel mai bine potrivit problemei particulare de rezolvat, n sensul c uureaz implementarea algoritmului evolutiv sau este cea mai natural relativ la problema dat. Evident, selectarea operatorilor de recombinare i mutaie ine cont de varianta aleas pentru reprezentarea candidailor la soluie.

2.2. Componentele algoritmilor evolutivi Componentele de baz ale algoritmilor evolutivi sunt: reprezentarea (definirea membrilor populaiei), funcia de evaluare (de tip fitness), populaia, mecanismul de selectare a prinilor (indivizii care interschimb material genetic), operatorii de variaie (recombinarea i mutaia), mecanismul de selectare a membrilor generaiei urmtoare (actualizarea populaiei), definirea modulului de iniializare (modalitatea de determinare a populaiei iniiale) i definirea condiiei terminale.

ReprezentareaPrima etap n dezvoltarea unui algoritm evolutiv este stabilirea unei conexiuni ntre contextul problemei particulare de rezolvat i spaiul n care evolueaz tehnica PS considerat. Obiectele care formeaz soluiile posibile n contextul problemei de rezolvat sunt numite fenotipuri, reprezentarea lor n contextul spaiului EA fiind referit prin genotip. Scopul este de a stabili o coresponden ntre mulimea fenotipurilor i cea a genotipurilor, numit reprezentare. De exemplu, dac problema particular este de optimizare n mulimea numerelor ntregi, un set prestabilit de numere ntregi poate constitui mulimea fenotipurilor, n timp ce setul genotipurilor este constituit din reprezentarea binar a fiecrui fenotip.

Observaie. Spaiul fenotipurilor poate fi foarte diferit de cel al genotipurilor, cel n care evolueaz un EA. O soluie este corespunztoare unui fenotip bun i este obinut prin decodificarea celui mai bun (din punctul de vedere al funciei de evaluare) genotip rezultat n urma aplicrii EA.

Ca terminologie, obiectele aparinnd spaiului problemei particulare de rezolvat sunt referite prin candidai la soluie, fenotipuri sau indivizi. Spaiul pe care este definit problema este numit spaiul fenotipurilor. Obiectele ce aparin spaiului n care este dezvoltat un EA sunt referite prin termenii de genotipuri, cromozomi sau indivizi. Spaiul n care evolueaz EA este numit spaiul genotipurilor. n general, un genotip este constituit din mai multe elemente, numite valori sau alele, fiecare fiind plasat ntr-o anumit poziie, referit prin termenul de variabil sau gen.

Observaie. Termenul reprezentare este utilizat n dou moduri diferite. n unele situaii desemneaz transformarea aplicat spaiului fenotipurilor astfel nct s fie obinut spaiul genotipurilor, caz n care termenul utilizat este i cel de codificare (n exemplul considerat mai sus, fiecare genotip este codificarea binar a unui fenotip). Transformarea invers, aplicat spaiului genotipurilor pentru a obine spaiul fenotipurilor este numit decodificare. Evident, n acest caz reprezentarea trebuie s fie inversabil: fiecrui genotip trebuie s i corespund cel puin un fenotip. n alte situaii, n definirea unei reprezentri accentul este pus cu precdere pe structura de date utilizat pentru definirea spaiul genotipurilor i nu pe transformarea propriu-zis. Aceast interpretare este legat spre exemplu de definirea operatorului mutaie pe spaiul genotipurilor constituite din reprezentrile binare ale fenotipurilor.

Funcia de evaluareRolul funciei de evaluare (de fitness) este de a msura gradul de adaptabilitate a fiecrui individ la mediul n care triete, mai exact este de definire a noiunii de calitate. Funcia de evaluare st la baza procesului de selecie i, din perspectiva tehnicilor PS, reprezint modulul de rezolvare a problemei date n contextul evolutiv. Din punct de vedere tehnic, este o funcie care asociaz fiecrui genotip o msur a calitii i, n general, este derivat pe baza unei funcii de tip calitate definit pe spaiul fenotipurilor. De exemplu, dac este funcia de calitate definit pe spaiul fenotipurilor, format din numere din mulimea i fiecare genotip este reprezentarea binar a unui fenotip, atunci funcia de evaluare n spaiul genotipurilor este definit prin,

De exemplu, pentru , atunci . n cele mai multe situaii, problema de rezolvat utiliznd EA revine la o problem de optimizare. Dac funcia obiectiv trebuie minimizat, atunci este realizat o transformare a ei astfel nct problema de optim s fie una de maxim (din punct de vedere matematic, de exemplu, a minimiza o funcie f este echivalent cu a maximiza funcia f sau, n situaia n care f nu se anuleaz pe spaiul fenotipurilor, cu a maximiza funcia ). n acest caz, funcia de evaluare este definit pe baza funciei obiectiv i innd cont de reprezentarea fenotipurilor n spaiul EA.Observaie. n continuare, prin cel mai bun individ al unei populaii vom nelege acel individ care realizeaz maximul funciei de evaluare pe acea populaie.

PopulaiaRolul populaiei n dezvoltarea EA este de a menine o mulime de genotipuri corespunztoare unor soluii posibile. O populaie este un multiset (o mulime de elemente nu neaprat distincte) de genotipuri. Indivizii unei populaii sunt obiecte statice, n sensul c nu pot fi modificai i nu se pot adapta mediului n care triesc. Aceste proprieti le are, n schimb populaia. Dac este stabilit modul de reprezentare (spaiul genotipurilor), populaia poate fi definit prin specificarea numrului de indivizi care o compun. n situaia unor EA compleci, populaiei i este asociat i o structur spaial adiional, definit prin intermediul unei funcii de tip distan sau prin relaii de tip vecintate. n astfel de cazuri, definirea populaiei trebuie nsoit de specificarea structurii spaiale asociate. Operatorii genetici de selecie (selecia indivizilor care interschimb material genetic prini i selecia populaiei la momentul de timp urmtor) sunt definii la nivelul unei populaii i, n general, construcia lor presupune consultarea ntregii populaii curente. De exemplu, cel mai bun individ al unei populaii date poate fi selectat pentru a genera populaia urmtoare sau cel mai slab individ al unei populaii date este nlocuit cu unul nou. n cele mai multe situaii, EA folosesc populaii de dimensiune constant pe tot parcursul evoluiei. Diversitatea unei populaii este msurat n termenii numrului de indivizi distinci ai populaiei. Exist mai multe variante de definire a msurii de diversitate: numrul valorilor distincte ale funciei de evaluare (dei, dac , nu rezult ), numrul fenotipurilor diferite reprezentate n cadrul populaiei (dei prezena unui fenotip n spaiul iniial nu garanteaz prezena unui singur genotip n spaiul EA: n cadrul populaiei, repetarea unui genotip este echivalent fie cu selectarea pentru includere a unui fenotip de mai multe ori, la generarea populaiei iniiale, respectiv cu selectarea repetat a unui genotip n construirea unei noi populaii, de exemplu datorit valorii mari a funciei de evaluare corespunztoare lui), numrul genotipurilor diferite din populaie (un genotip corespunde unui singur fenotip i valoarea funciei de evaluare corespunztoare lui este unic), msuri bazate pe entropia populaiei .a.m.d.

Mecanismul de selectare a prinilorRolul operatorului de selectare a prinilor este de a distinge ntre indivizii populaiei pe baza calitii acestora, n particular de a permite celor mai buni indivizi s se reproduc, deci s participe la generarea populaiei urmtoare. Alturi de operatorul de selecie a supravieuitorilor (indivizii care vor compune generaia urmtoare), mecanismul de selecie a prinilor foreaz mbuntirea calitii globale a populaiei de la o generaie la alta. n calculul evolutiv, selectarea prinilor este de tip probabilist: alegerea unui individ pentru a se reproduce depinde direct proporional de calitatea lui, deci un individ are anse mai mari de a se reproduce comparativ cu cei inferior lui din punct de vedere calitativ. Observaie. Indivizii slabi (cu valori mici ale funciei de evaluare) nu sunt eliminai din procesul de selectare pentru reproducere, ci doar au asociate probabiliti mici, dar nenule, de selecie. n acest fel algoritmul de cutare nu este de tip greedy i riscul de identifica o valoare de optim local fiind diminuat n acest fel.

Operatorii de variaie: mutaia i recombinareaScopul aplicrii operatorilor de variaie este de a crea noi indivizi, derivai din cei ai populaiei curente. Din punctul de vedere al rezolvrii problemelor prin metode de cutare de tip generare-testare, prin aplicarea operatorilor de variaie este realizat faza de generare. Definirea operatorilor de variaie depinde esenial de modalitatea de reprezentare a spaiului iniial (definirea spaiului genotipurilor).

Operatorul mutaieMutaia este operator unar (cu aritate 1), n urma aplicrii acestuia asupra unui genotip rezult o variant mutant, numit progenitur sau copil. Operatorul mutaie este ntotdeauna stochastic, rezultatul depinznd de o serie de alegeri aleatoare. n general aceste alegeri constau n utilizarea unui generator de numere aleatoare din diferite distribuii de probabilitate i sunt numite extrageri aleatoare. Rolul mutaiei n calculul evolutiv depinde de tipul de algoritm implementat. De exemplu, n cazul algoritmilor genetici, mutaia are rolul de a mprospta structura genetic a unei populaii, n cazul programrii evolutive este unicul operator de variaie care dirijeaz procedura de cutare, n timp ce n cazul programrii genetice n general nu este folosit.Din studiul teoretic al convergenei algoritmilor evolutivi rezult c optimul global al funciei obiectiv poate fi obinut n situaia n care operatorii de variaie utilizai asigur obinerea oricrui genotip soluie potenial a problemei de optim (Eiben, Smith, 2003). Cea mai simpl cale de a asigura ndeplinirea acestei codiii este de a utiliza un operator mutaie care s permit modificarea oricrei alele dintr-un cromozom cu orice variant posibil, cu o probabilitate nenul. n literatura de specialitate exist ns i opinii conform crora rezultatele teoretice relative la comportamentul EA au o importan practic redus i multe implementri EA nu posed proprietile cerute de acestea.

Operatorul de recombinareUn operator de variaie binar (cu aritate 2) este numit operator de recombinare sau ncruciare i are ca efect obinerea unuia sau a dou genotipuri urma direct prin combinarea informaiei purtate de dou genotipuri printe. Recombinarea este un operator stochastic: alegerea acelor pri ale genotipurilor prini care vor fi combinate i modalitatea de recombinare rezult n urma unor extrageri aleatoare. Rolul recombinrii difer de la o clas de algoritmi evolutivi la alta: n cadrul algoritmilor genetici este cel mai utilizat operator de variaie (probabilitatea de efectuarea a unei ncruciri este n general mult mai mare dect probabilitatea apariiei unei mutaii), n programarea genetic este n general unicul operator de variaie folosit, n timp ce n programarea evolutiv nu este implementat.n dezvoltri de tip EA pot fi folosii i operatori de recombinare de aritate mai mare dect 2 (n generarea urmailor sunt folosii mai mult de dou genotipuri printe). Astfel de operatori sunt uor de implementat dar nu au corespondent biologic. Dei o serie de studii indic utilitatea acestora n tratarea unor probleme particulare, aceti operatori sunt rar folosii. Prin mperecherea a dou genotipuri printe cu caracteristici diferite i superioare calitativ pot fi obinute progenituri care s mbine caracteristicile celor doi prini. Acest principiu are un fundament biologic extrem de solid: a fost utilizat de cultivatorii de plante i cresctorii de animale pentru a produce specii cu randament superior sau care s prezinte caracteristici mbuntite. Aplicarea EA determin crearea de urmai direci prin ncruciri aleatoare, fiind acceptat ideea c unii dintre acetia pot avea nsuiri nedorite, majoritatea pot fi calitativ similari sau chiar inferiori prinilor i doar o mic parte dintre ei pot avea caracteristici superioare prinilor. Mecanismul de selectare a supravieuitorilor (nlocuirea populaiei curente)Rolul acestui operator, numit i selecia mediului sau strategia de nlocuire a populaiei curente, este de a diferenia indivizii n funcie de calitatea lor. Din acest punct de vedere este similar procesului de selecie a prinilor dar este utilizat ntr-o etap diferit a evoluiei unui EA. Mecanismul de selecie a membrilor urmtoarei generaii este aplicat dup generarea progeniturilor indivizilor populaiei curente i, deoarece dimensiunea populaiei este n general constant n timp, revine la aplicarea unei funcii de decizie fiecrui individ aparinnd populaiei curente sau mulimii progeniturilor. Funcia de decizie aplicat unui individ exprim proprietatea acestuia de a fi selectat pentru includerea n populaia urmtoare (proprietatea de a fi supravieuitor) i este de obicei construit pe baza funciei de evaluare, lund n calcul calitatea fiecrui individ i, n unele situaii, factorul vrst (de cte generaii este meninut u individ). n general selecia mediului este un proces determinist. Obinerea generaiei urmtoare poate fi realizat, de exemplu, fie prin ordonarea indivizilor multisetului obinut prin reuniunea populaiei curente cu multisetul progeniturilor i selectarea celor mai buni indivizi (funcie de decizie bazat pe funcia de evaluare), fie prin selectarea indivizilor exclusiv din multisetul urmailor direci (funcie de decizie bazat pe factorul vrst).

Iniializarean majoritatea EA, crearea populaiei iniiale este realizat prin generare aleatoare de fenotipuri i apoi obinerea multisetului de genotipuri asociat. De asemenea, n funcie de problema particular de rezolvat, generarea populaiei iniiale poate fi realizat i pe baza unor euristici care s asigure obinerea unor indivizi cu adaptabilitate ridicat.

Condiia terminalCondiia terminal n EA este stabilit n funcie de tipul de problem de rezolvat, n felul urmtor. Dac problema are o valoare de optim cunoscut, atunci un posibil criteriu de oprire este atingerea acelei valori sau atingerea acelei valori cu o eroare dat . Dar, deoarece algoritmii evolutivi sunt stochastici i nu garanteaz atingerea valorii optime, criteriul poate s nu fie satisfcut la nici o iteraie, deci el trebuie reformulat. Cele mai utilizate opiuni sunt: atingerea unui numr maxim de iteraii (generaii); atingerea unui numr maxim de evaluri ale calitii indivizilor; pentru o anumit perioad de timp (un numr de iteraii specificat sau un numr de evaluri specificat) calitatea populaiei curente nu este semnificativ mbuntit (este sub un prag dat); diversitatea populaiei scade sub un prag dat. n situaia n care problema de rezolvat nu are un optim cunoscut, poate fi utilizat oricare din variantele menionate mai sus.

2.3. Evoluia cutare direct-cutare stochastic. Metodele hill climbing i simulated annealing

Evoluia cutare direct-cutare stochastic cuprinde dou tehnici care reduc din dezavantajele cutrilor directe, i anume metode de tip hill climbing i simulated annealing. Metodele de tip hill climbing utilizeaz o tehnic de iterativitate mbuntit. Aceasta se aplic unui singur punct din spaiul de cutare. La o iteraie este selectat un nou punct aflat ntr-o vecintate a punctului curent procesat. Dac acest punct determin o valoare mai bun (din punct de vedere al criteriului de optim considerat) pentru funcia obiectiv, el devine punct curent. n caz contrar, este selectat o alt vecintate a punctului curent, procesul desfurndu-se ulterior similar. Algoritmul se ncheie cnd nici un punct vecin celui curent nu aduce mbuntiri valorilor funciei obiectiv. Metodele de acest tip conduc de obicei la valori de optim local, depinznd de punctul de start. n plus, nu se pot furniza informaii referitoare la eroarea relativ a soluiei calculate. Pentru a crete performanele unor astfel de modele, acestea se utilizeaz pentru un numr mare de punct de start.Metodele de tip simulated annealing elimin o mare parte din dezavantajele algoritmilor hill climbing, n sensul c soluiile nu depind de punctul de start i sunt de obicei apropiate de punctul de optim global. Pentru aceasta, este considerat o probabilitate de acceptare a punctului selectat drept urmtor punct curent, egal cu 1 dac noul punct furnizeaz o valoare mai bun pentru funcia obiectiv considerat. n unele situaii, probabilitatea de a accepta un nou punct este o funcie cu valori corespunztoare funciei obiectiv pentru punctul curent i noul punct selectat. De asemenea, fa de tehnica hill climbing, este considerat un parametru de tip temperatura sistemului, care influeneaz probabilitatea de acceptare a unui nou punct ca punct curent: cu ct acest parametru este mai sczut, cu att ansele de acceptare sunt mai mici. Pe parcursul execuiei algoritmului, temperatura sistemului scade; algoritmul se ncheie pentru o temperatur mic, pentru care nu se mai accept nici o modificare a soluiei (probabilitatea de acceptare a unui nou punct este 0).

Structurile algoritmilor de tip hill climbing i simulated annealingFie f funcia obiectiv care se dorete maximizat (dac principiul de optimalitate este minimul, atunci problema minimizrii funciei obiectiv f n anumite condiii de constrngere revine la maximizarea funciei -f). Considernd reprezentarea cromozomial a unei soluii poteniale de tip binar, ca un ir de nr bii, punctele curent respectiv nou fiind desemnate prin vc respectiv vn, algoritmii hill climbing i simulated annealing sunt descrii dup cum urmeaz.Fie MAX numrul punctelor de start. Procedura urmtoare calculeaz v, un cel mai bun punct din cele MAX puncte obinute n urma aplicrii tehnicii de tip hill climbing (memorate n vectorul V).

procedure hillclimbingbegint=1 repeat local=false selecteaz aleator un punct curent vc evalueaz vc repeat selecteaz nr puncte din vecintatea lui vc prin modificarea fiecrui bit al lui vc selecteaz un punct vn dintre cei nr generai anterior, cu funcia obiectiv maxim if f(vc)val) val=valm; v=vc; timp=t; end; V=[V;vc];end;disp(v);disp(val);disp(timp);plot_obiectiv(V,timp,a,b);end

function [val]=f_obiectiv(x,y);val=exp(-x^2-y^2)+y*cos(5*x)-x*sin(3*y);end

function []=plot_obiectiv(V,timp,a,b);figure[X,Y] = meshgrid([a:0.01:b]);Z = exp(-X.^2-Y.^2)+Y.*cos(5*X)-X.*sin(3*Y);plot3(X,Y,Z,'y');grid onhold on[dim xx]=size(V);disp(dim);for i=1:dim x=V(i,1); y=V(i,2); z=f_obiectiv(x,y); if(i==timp) plot3(x,y,z,'ks'); hold on else plot3(x,y,z,'g.'); hold on end;end;end

Funciile de reprezentare repr_reale i repr_sir_bin sunt similare primului exemplu (asigur transformarea numr real din ir binar).

La un apel hillclimbing(-2,2,5,75);pot fi obinute rezultatele: x=-1.9102, y=-1.6250 valoarea maxim: 3.4989.n urmtoare figur este prezentat un exemplu de evoluie posibil a algoritmului hill climbing aplicat pentru 75 de puncte de start.

2.4. Exemple de aplicare a EA

Rezolvarea unei probleme de optimizare a unei funcii de o variabilFie , definit prin

Problema este de a calcula valoarea maxim a funciei pe intervalul .Spaiul genotipurilor poate fi considerat mulimea numerelor reale din intervalul . La fiecare moment de timp populaia este constituit din dim numere reale din ; la momentul iniial, populaia conine dim numere reale generate aleator pe intervalul .Operatorul de mutaie aplicat unui cromozom x determin obinerea valorii x. (n acest caz este posibil, deoarece, dac ). Operatorul de recombinare aplicat pentru prinii determin obinerea cromozomului . Selecia prinilor este realizat astfel: sunt selectai jumtate din membrii populaiei curente pe baza procedurii de tip turnir. Operaia de ncruciare este aplicat pentru o mperechere aleatoare a cte 2 indivizi prini, cu probabilitatea pc (pentru fiecare pereche de prini selectat este generat un numr aleator n ; dac acesta este inferior valorii pc, este efectuat ncruciarea). Progeniturile sunt supuse mutaiei cu o probabilitate pm. Mecanismul de selectare a noii generaii presupune ordonarea descresctoare a multisetului format din indivizii populaiei curente i progeniturile obinute prin operatorii de variaie i selecie a prinilor i alegerea primilor dim indivizi pentru a forma populaia urmtoare. Condiia terminal este formulat astfel: a fost depit un prag al numrului de generaii sau calitatea populaiei, msurat ca medie a funciei de evaluare n membrii populaiei nu mai poate fi mbuntit semnificativ.n continuare sunt prezentate funciile MATLAB utilizate i cteva exemple de aplicare a cutrii evolutive descrise mai sus.

% generarea populaiei iniialefunction [pop]=genereza_ini(dim);pop=zeros(dim,2);% fiecare membru al populatiei este un numar in [-1,1]% la care este adaugata valoarea functiei obiectiv for i=1:dim pop(i,1)=unifrnd(-1,1); pop(i,2)=f_obiectiv(pop(i,1));end;end

%definirea functiei obiectivfunction [val]=f_obiectiv(x);val=x.^1/3-3*sin(7*x+0.2)+2*cos(x/5-0.4)+1;end

% operatorul mutatiefunction [y]=mutatie(x);y=x;y(1)=-x(1);y(2)=f_obiectiv(y(1));end

% operatorul de incrucisarefunction [y]=crossover(x1,x2);y=x1;y(1)=(x1(1)+x2(1))/2;y(2)=f_obiectiv(y(1));end

% mecanismul de selectie a parintilorfunction [parinti]=selectie(pop);[dim,xx]=size(pop);d=round(dim/2);% dim trebuie sa fie multiplu de 4, pentru ca d sa fie par% va rezulta un singur copil din incrucisareparinti=zeros(d,2);for i=1:d p1=unidrnd(dim); p2=unidrnd(dim); while(p2==p1) p2=unidrnd(dim); end; if(pop(p1,2)>pop(p2,2)) parinti(i,:)=pop(p1,:); else parinti(i,:)=pop(p2,:); end;end;end

%obtinerea unei noi populatii popNou pe baza populatiei curente pop%probabilitatea de incrucisare pc si probabilitatea de mutatie pm% evalmed este valoarea medie a functiei obiectiv pentru noua generatiefunction [popNou,evalmed]=trecere(pop,pc,pm);[parinti]=selectie(pop);[dim,xx]=size(pop);[dd,yy]=size(parinti);d=round(dd/2);popN=zeros(d,2);%aplica operatia de crossovernr=0;for i=1:d j=2*i; prc=unifrnd(0,1); if(prc