54 418 paper6-acta01 rotar corina

7/24/2019 54 418 Paper6-Acta01 Rotar Corina

1/9

C. Rotar- Rezolvarea problemelor de optimizare multicriterialutiliznd

45

REZOLVAREA PROBLEMELOR DE OPTIMIZAREMULTICRITERIALUTILIZND CROMODINAMICA

GENETIC

Corina Rotar

Abstract. One of the main application areas of the evolutionary computation ismultiobjective optimization. There is a variety of approachc trying to solve themultiobjectice optimization problems. Goldberg, Srinivas and Deb, and many otber, proposeevolutive algorithms, which have proved to be a very good instrument for solvingmultiobjective optimization problems. In this article we propose to apply geneticchromodynamics tehniques, developed by Dumitrescu, for solving tbis difficult problems.

Keywords:Evolutive algorithms, Genetic chromodynamics, multiobjective optimization

I. INTRODUCERECalculul Evolutiv reprezintun ansamblu de tehnici i concepte inspirate din teoria

evoluiei biologice, n conformitate cu aceasta, o populaie de soluii iniiale se modificsub aciunea operatorilor biologici: selecie, recombinare, mutaie, etc., nregistrndu-se ocretere a performanei indivizilor de la o generaie la alta. Selectarea celor mai buniindivizi (cromozomi) pentru a deveni prinii generaiei urmtoare, conduce nspre ombuntire a calitii indivizilor descendeni. Dupun numr fixat de generaii, cel mai

bun individ al ultimei populaii sau cel mai bun individ generat in decursul procesuluireprezint soluia problemei. Soluia oferit de tehnicile Calculului Evolutiv nu estentotdeauna soluia globalexacta problemei, nso bunaproximare a acesteia este nmulte situaii satisfctoare.

Direciile Calculului Evolutiv sunt: Algoritmii Genetici, ProgramareaEvolutiv, Strategiile Evolutive, Programarea Genetic, Sisteme de Clasificare Instruibile,

Cromodinamica Genetic, Algoritmi Genetici Dezordonai i Codificarea Delta.Algoritmii evolutivi au la baza modelul evoluiei organismelor, natura fiind sursaprincipalde inspiraie. n conformitate cu legile evoluiei naturale, un Algoritm Evolutivmodeleazadaptarea unei populaii de indivizi, reprezentnd fiecare n parte o soluie

posibil a problemei de rezolvat. Aceast adaptare se face n sensul creteriiperformanelor indivizilor populaiei n raport cu funcia obiectiv.

Spaiul de cutare al problemei poate sfie prea mare sau chiar infinit n aceastsituaie, populaia asupra creia acioneaz algoritmul evolutiv este format dintr-osubmulime finit a spaiului de cutare. Fiecare element al populaiei, numit inliteratura de specialitate cromozom, reprezint o soluie posibil a problemei. Deregul, populaia iniial se construiete prin generarea aleatoare a unor puncte alespaiului de cutare. Performana unui cromozom este calculatcu ajutorul funciei de

evaluare, funcie ce poate coincide cu funcia obiectiv in cazul problemelor deoptimizare sau, in alte situaii, poate fi o funcie de cost, de ctig, etc.


2/9


46

Algoritmii evolutivi sunt n esenproceduri iterative de cutare. La fiecare iteraiesunt selectai cei mai performani indivizi ai populaiei curente P(t), urmnd ca asupra lorsse aplice operatorii genetici specifici pentru a genera noi indivizi. Operatorii geneticiuzuali sunt operatorul de recombinare i cel de mutaie. Recombinarea asigurconstruirea unor noi indivizi prin combinarea materialului genetic (fragmente decromozomi) provenit din indivizii existeni. Mutaia va crea noi indivizi prin executareaunor mici modificri, perturbaii, asupra unui singur cromozom. Descendenii obinui inurma aplicrii operatorilor genetici vor forma noua generaieP(t+1). Se considerclafiecare iteraie, noua generaie conine indivizi mai performani, mai "adaptai" dect ceiai populaiei anterioare.

Terminarea algoritmului evolutiv este fie condiionatde atingerea unui numr dat deiteraii, fie de orice altcondiie specificproblemei. Soluia algoritmului va fi extrasdin populaia final, fiind cel mai bun cromozom al acesteia. Pentru a ne asigura ccelmai bun individ generat nu s-a pierdut prin alternarea genera iilor, algoritmulevolutiv poate fi nzestrat cu un mecanism suplimentar ce permite supravieuirea celormai buni k indivizi ai populaiei de la o generaie la alta. Soluia dat de algoritmulgenetic nu este ntotdeauna i optimul global al problemei rezolvate, ns aceasta seapropie mult de soluia dorit, n cazul problemelor complicate, putem fi mulumii de

gsirea unei soluii bune, ct mai apropiat de optimul global. Prerile sceptice nlegtur cu eficiena procedurilor evolutive au fost nlturate prin obinerea unorrezultate surprinztoare n cazul problemelor complicate pentru care tehnicile clasicenu dau soluii bune sau necesitun timp prea mare de execuie.

Rezolvarea oricrei probleme poate fi privitca un proces de cutare i optimizaren spaiul soluiilor posibile. Din aceste considerente un algoritm evolutiv poate fiadaptat n mod corespunztor oricrei probleme date. S lum spre exemplu cea mai

popularclasa de algoritmi evolutivi, algoritmii genetici. Fiecare cromozom al populaieieste alctuit dintr-o secven de caracteristici sau gene. Valorile genelor sunt preluatedintr-un alfabet A dependent de specificaiile problemei de rezolvat. Lungimeacromozomilor, definit prin numrul de gene constitutive, este de regul un numrconstant. O clas aparte de algoritmi genetici, algoritmii genetici dezordonai,utilizeazo lungime variabila cromozomilor.

Observaie: n orice procedur puternic de cutare i optimizare, stabilirea unuiechilibru ntre explorarea spaiului soluiilor posibile (cutarea global) iexploatarea regiunilor promitoare ale spaiului de cutare (cutarea local), devine ocondiie obligatorie. Cercetrile lui Holland din anii '70 au demonstrat c algoritmiigenetici realizeazacest echilibru ntr-o maniera aproape optimal.

Structura generala unui algoritm genetic:1.

Fie t=0. Iniializare aleatoare P(t);

2.

Evaluarea cromozomilor populaiei P (t).

3.

Repet

3.1.

Selecie cromozomi prini din P(t)


3/9


47

rezultnd populaia intermediarPI.

3.2.

Asupra populaiei P1 se aplic

operatorii genetici (recombinare,

mutaie, inversiune, etc.) rezultnd

populaia P2. Din PI se terg prinii

populaiei P2.

3.3. n P2 se adaugcromozomii rmai n

PI.

P(t+l)=P2; t=t+l; Evaluarea cromozomilor din P(t).

Sfrit.

II. CROMODINAMICA GENETIC

Direcie relativ nou a Calculului Evolutiv, Cromodinamica Genetic a fostiniial dezvoltatpentru rezolvarea problemelor de clasificare. Cromodinamica geneticutilizeaz o populaie de dimensiune variabil

Numrul indivizilor populaiei scade cu fiecare generaie." Fiecare cromozom (individ)

reprezinto soluie posibil din spaiul de cutare. Utilizatorul are libertatea de a optapentru o variantde codificare a cromozomilor: binar, real, etc.Ideea de baza acestei metode este de a realiza o parti ionare a populaiei

ntr-un numr oarecare de subpopulaii. O subpopulaie va corespunde unui punct deoptim.

n procesul de cutare, aceast partiionare a populaiei trebuie sse menin. Subpopulaiile coevolueazi converg n parte spre soluiile optimale ale

problemei. Se admite c indivizii (soluiile) foarte apropiai se vor unifica,determinnd o descretere adimensiunii populaiei, n final fiecare subpopulaie va conine un singur individreprezentnd un punct de optim din spaiul soluiilor posibile ale problemei considerate.Iniial, fiecrui individ i va fi ataat o culoare distinct, n timp se va constata o

descretere a numrului de culori (ceea ce explici numele metodei) i o stabilizare aunei culori dominante pentru fiecare subpopulaie.

Modificrile aduse populaiei la fiecare iteraie sunt modelate cu ajutoruloperatorilor genetici de recombinare i mutaie. Recombinarea este de tipul (2,1), adicdin doi prini selectai va rezulta un unic descendent Fiecare cromozom este selectat

pentru recombinare. Se consider acesta printele dominant Perechea sa esteselectatnumai dintr-o vecintate sferica cromozomului dominant. Din punct devedere biologic, probabilitatea de mperechere a unui individ cu un alt individ dinaceeai subpopulaie este mult mai mare dect mperecherea cu un individ dintr-oalt subpopulaie. Din aceste considerente, Cromodinamica genetic accept doarncruciri locale. Pentru fiecare cromozom selectat a (printele dominant) se

definete o vecintate sferic centrat n a, de raz r: V(a,r) n care va fi cutatpartenerul recesiv b al cromozomului a. Raza r poate constitui o constant aprocedurii sau poate s varieze n funcie de numrul de generaii produse, n


4/9


48

concordancu rolul su, raza r se numete razde interaciune.Cei doi operatori considerai, mutaia i recombinarea se exclud reciproc. Un

cromozom a este perturbat prin mutaie doar n situaia n care vecintatea sa V(a,r) nupermite stabilirea unui partener pentru recombinare. Decizia de alegere aoperatorilor genetici este condiionat att de cadrul problemei concrete ct i demetoda de reprezentare a indivizilor. Spre exemplu, pentru o reprezentare real, putemconsidera ncruciarea convexde tipul (2,1) i o lege aditivde mutaie prin care fiecarevariabila cromozomului sufero perturbaie normal:

Fie a cromozomul selectat pentru recombinare, i m dimensiunea sa (numrul devariabile), n vecintatea sa V(a,r) este determinat partenerul b de recombinare. Uniculdescendent al perechii (a,b) este cromozomul c,pentru care:

iiii bac )1( 1 += , mi ,1= unde ]1,0[i

urmeazo distribuie uniform.Obs: Unicul descendent al perechii (a,b)va moteni culoarea printelui dominant.n cazul in care vecintatea lui c nu ofer nici un partener valid pentru

ncruciare, cromozomul c este supus mutaiei..n general, un descendent mai bun i nlocuiete automat printele n noua

generaie. Aceasta ar putea conduce nspre o convergen prematur a procedurii.Evitarea convergenei premature poate fi fcut prin nzestrarea procedurii cu unmecanism suplimentar de tipul recoacerii simulate. Astfel, un individ mai slab dect

printele su poate fi acceptat n noua generaie cu o anumitprobabilitatep.Un alt aspect specific cromodinamicii genetice este descreterea numrului de

indivizi ai populaiei, n timp anumii indivizi devin foarte apropiai i mai multesubpopulaii ar putea evolua nspre acelai punct de optim. Acest lucru esteneacceptabil dacdorim determinarea numrului corect de optime i avem n vedereaptul cfiecrui punct de optim i va corespunde un unic cromozom. Pentru modelareaacestui aspect se va considera c indivizii foarte apropiai (distana dintre acetia estemai micdect o valoare pre-fixat) se vor unifica devenind unul singur.

Condiia de oprire a algoritmului poate fi dat de atingerea unui numr degeneraii sau poate fi validatn cazul n care dupun numr oarecare de generaii nu semai nregistreazmodificri semnificative ale populaiei. ;

Rezultatele acestei tehnici sunt pe de o parte, determinarea punctelorde optim i pe de altparte stabilirea numrului corect de puncte de optim. Dac,

populaia final este alctuit din s cromozomi atunci numrul de puncte de optimeste s iar fiecare cromozom sixi ,...,2,1, = reprezinto soluie optim(local sauglobal) a problemei.

Dinamica metodei poate fi urmrit pe dounivele. Primul nivel corespundemodificrii cromozomilor iar cel de-al doilea este asociat cu formarea, modificarea istabilizarea subpopulaiilor.

III. OPTIMIZARE MULTICRITERIAL


5/9


49

O clas de probleme cu un grad mare de complexitate admite existena mai

multor funcii obiectiv. Problemele n care mai multe funcii obiectiv trebuieoptimizate simultan se numesc probleme de optimizare multicriterial(optimizare multiobiectiv, optimizare vectorial). De cele mai multe ori criteriile deoptim sunt contradictorii, ngreunnd semnificativ stabilirea unei tehnici de rezolvare a

problemelor de acest gen. O abordare simplist permite convertirea criteriilor ntr-osingurfuncie obiectiv, problema reducndu-se la o problemde optimizare clasiccuun singur obiectiv. Fiecare criteriu i va aduce aportul n aceast funcie printr-o

pondere prestabilit. Alegerea ponderilor pentru definirea unei unice funcii obiectivcunoate adesea o rezolvare subiectivcare ar afecta soluia final. Motivele prezentatencurajeazcercetarea altor tehnici de rezolvare a problemelor multicriteriale.

Optimizare ParetoPentru o problemde optimizare cu m funcii criteriu:fi, i = 1,2,...,m definim

vector criteriu, vectorul m-dimensional cu urmtoarea form, avnd ca i

componente funciilefi, i = 1,2,...,m:

=

mf

f

F M

1

Notnd cu domeniul funciei F, F: mR , iar reprezintspaiul decutare pentru problemadat.

Principalul neajuns al problemelor de optimizare multicriterial const nincompatibilitatea diferitelor criterii i, n consecin, imposibilitatea comparriisoluiilor, n optimizarea Pareto aceast dificultate este nlturatprin definirea unei


6/9


50

relaii de ordine (relaie de dominare) peste mulimea soluiilor.O soluie nedominat sau optimal n sens Pareto se definete intuitiv prin

urmtoarele propoziii:(a)Nu este o soluie mai proastdect celelalte.(b)

Este mai bundect oricare alta n raport cu cel puin un criteriu.Pentru a defini relaia de dominare peste mulimea soluiilor (spaiul ) se

definete n prealabil o relaie de dominare peste mulimea valorilor funciei vector F(spaiulRm).

Fie urmtoarea problemde optimizare multicriterial:

=

x

mixfP

i ,...,1max,)(:

Valorile funciei vector F constituie mulimea V,unde:

V={v mR | x , v =F(x)}Definiie.Fie u i v doi vectori din V. Spunem cvectorul v l dominpe u (notat

up v) n raport cu problema considerat, ddacsunt ndeplinite urmtoarele:(a)

u i, i= 1,2,. . . ,m;(b) j = 1,2,...,m : uj


7/9


51

submultime (subpopulaie) corespunde unei nie n care indivizii partajeaz resurselecomune. Performanele recalculate intervin n selecia cromozomial. n continuareeste dat algoritmul de optimizare vectorialbazat pe metoda niei ecologice.

Algoritmul de optimizare P carete bazat pe metoda niei ecologice - prelucrarea

generaiei P(tl

1. Fie P1- submultimea soluiilor nedominate din P(t)

2. Se genereazo valoare mare de adecvare ce se atribuie fiecrui individ din P1;

3. Se recalculeazperformanele indivizilor nedominai folosind metoda niei;

4.

Fie v1 cea mai micvaloare de adecvare a cromozomilor din P1i i = 2;

5. P(t) = P(t)\P1;

6. Ct timp P(t) execut:

6.1. Fie P' - submultimea soluiilor nedominate din P(t)

6.2. Fie vi, vi< vi-1, o valoare de adecvare ce se atribuie fiecrui individ din

Pi;

6.3.

Se recalculeazperformanele indivizilor nedominai folosind metoda

niei;

6.4.

P(t)=P{t)/P';

6.5. i = i + 1;

7. n = i; numrul de subpopulaiin

8. P(t) =i

n

iP

1= ; refacerea populaieii=i

9. Se aplic operatorii genetici asupra indivizilor populaiei P(t) utiliznd

valorile adecvrilor

recalculate.

IV. OPTIMIZARE MULTICRTTERIALCU CROMODINAMICGENETIC

O interesant abordare a problemelor de optimizare vectorial estefolosirea cromodinamicii genetice pentru determinarea frontului Pareto. n acest

paragraf este propus un algoritm care folosind tehnicile cromodinamicii geneticencearcrezolvarea unei probleme de optim multicriterial.

Componentele oricrui algoritm evolutiv pot fi grupate n 3 module: Modulul Populaie


8/9


52

Modulul Evaluare

Modulul Recombinarei Modificare

n concordan cu aceast mprire pe module, . prezentareaalgoritmului n aceastseciune va urmri schema propus.

ModululPopulaie:

Metoda de reprezentare: Reprezentare realpareadecvatunei astfel de probleme.Fiecare cromozom X este reprezentat printr-o structur: [(x1 xn), r, c, f], n care:vectorul de componente reale (x1 xn), reprezintun punct din spaiul soluiilor , r- reprezintran gul individului (numrul subpopulaiei la care aparine), c - culoarea cu care estenzestrat cromozomul, f - valoarea funciei de performan: f(X).

Metoda de iniializare: Se recurge, ca n majoritatea situaiilor la oiniializare aleatoare a populaiei. Numrul iniial de indivizi este un parametru ala lgor i tmului i poate fi modificat, n general se folosete o valoare cuprins n intervalul[100,200].

Metoda de selecie: Fiecare individ al genera iei curente este selectat pentrurecombinare sau mutaie. Partenerul pentru recombinare este cutat doar ntr-o vecintate acromozomului, respectiv, printre cromozomii cu aceiai culoare ca i printele dominant. Dacnueste posibilstabilirea unu i partenr, crom ozomul dominan t este supus mutaiei.

Metoda de nlocuire: Descendentul mai performant dect printele dominant lnlocuiete automat pe acesta in noua generaie. Nu se utilizeazun mecanism de tipul recoaceriisimulate.

Alte considerente: Raza de interaciune se stabilete la fiecare generaie nfuncie de numrul de submu limi de solu ii nedominate. Astfel, fiind n - numrul de clase(subpopulaii de soluii nedominate) la o generaie dat, raza de interaciune reprezint raportuldintre distana maximntre oricare doi indivizi, primul din clasa de rang l i celalalt din clasa derang maxim n, i numrul de clase n. Pentru fiecare individ nedominat din clasa de rang l seconstruiete o vecintate de raz r. Fiecrei vecint i i este ataat o culoare distinct.Indivizii care nu sunt colorai la o iteraie, nu vor putea fi recombinai sau mutai. Acetiasupravieuiesc trecerii de la o genera ie la alta, astfel nct, la o nou iteraie vor avea din nouansa de a fi colorai, respectiv de a produce descendeni.

Etichetarea indivizilor: se face determinnd toate clasele de soluii nedominate. Fiecruielement dintr-o clas i este ataat o valoare natural ce reprezint numrul clasei respective.Prima submulime de soluii nedominate va forma clasa de rang 1. Prin eliminarea temporar dinpopulaie a acestei prime clase, populaia rmasva putea conine o nousubmulime de soluiinedominate, reprezentnd clasa de rang 2. n mod asem ntor se vor stabili toateclasele de soluii nedominate i toi indivizii populaiei vor primi o etichet.

Modulul EvaluarePerformana fiecrui individ c este calculat folosind funcia de evaluare cu urmtoarea

form:

=

),('

1

)( cxdcf , unde:d(x,c) - distana euclidian dintre punctele din spaiu de cutare reprezentate de cromozomii x i


9/9


53

c;

r- reprezintrangul cromozomului c i suma se calculeazpentru toi cromozomii x care verificcondiia rang(x) = rang(c) (c i x aparin aceleiai submulimi de soluii nedominate).

Modalul Recombinarei Modificare:Operatorii genetici utilizai sunt ncruciarea convex i mutaia. Mutaia provoac

asupra componenei vectorului (x1, ..., xn) perturbaii aleatoare urmeaz legea normal.Astfel, prin mutaie, vectorul (x1, ..., xn)devine: (y 1, ..., yn) unde:yi= xi+ Ni(0,l), i =1,2,..., n. (prin Ni (0, 1) s-a notat instana unei variabile aleatoare cu distribuitnormalavnd m = 1i 0= ).

Algoritmul dat n continuare se dorete a fi o ncercare de aplicare a tehnicilorcromodinamicii genetice pentru rezolvarea problemelor de optimizare vectorial:

1. Iniializare aleatoare populaie P(0); fie t = 1, 2. Ct timp(condiie_continuare = true) execut:

2.1. Stabilirea submulimilor de soluii nedominate (clase) a populaiei P(t);fie nc - numrul de clase; fiecrui cromozom i este ataat o valoarereprezentnd numrul clasei din careface parte (rangul);

2.2.

Calcularea razei de interaciune;2.3.

Ataare culoare pentru fiecare cromozom al populaiei P(t);(stabilirea vecintilor de ncruciare)

2.4.

Ataarea valorii de adecvare fiecrui individ al populaiei Pft);2.5.Pentru fiecare cromozom c se caut un partener compatibil (de aceiai

culoare). Dacs-a gsit un astfel de partener se va aplica operatorul de recombinare, ncaz contrar se aplicmutaia;

2.6.

t = t + 1.

BIBLIOGRAFIE

[1] P. J. Angeline,Evobttionary Algorithms and Emergent Intelligence, Dissertation,Presented in Parial Fulflllment of the Requirements for the Degree Doctor ofPhilosophy in the Graduale School of The Ohio State University, The Ohio StateUniversity, 1993[2] T,B&ck, Evolutionary Algoritkms in Tkeory and Practice, Oxford University Press,1996.[3] D. Dumitrescu,Algoritmi Genetici fi Strategii Evolutive - aplicaii tn Inteligena

Artificialfi tndomenii conexe, Ed Albastr, Cluj Napoca, 2000[4] D. Dumitrescu, B. Lazzerini, L. C. Jain, A. Dumitrescu,Evobttionary computation,CRC Press, 2000.[5] D. E. Goldberg, Genetic Algorithms in Search, Opt'unization, andMaehine

Learning, Addison-Wesley Publishing Company, Inc., 1989.

AutorCorina ROTAR, Universitatea "l Decembrie 1918" Alba lulia Alba lulia.

54 418 paper6-acta01 rotar corina

Documents