Elektrotehniški vestnik 78(5): 275-280, 2011 Existing separate English edition Izbor v diferencialni evoluciji Iztok Fajfar, Janez Puhan, Sašo Tomažič in Arpad Burmen Univerza v Ljubljani, Fakulteta za elektrotehniko, Tržaška 25, 1000 Ljubljana, Slovenija e-pošta: iztok.fajfar@fe.uni-lj.si Povzetek. Diferencialna evolucija je enostaven algoritem za globalno optimizacijo. V grobem je sestavljen iz treh operacij: mutacije, križanja in izbora. Medtem ko obstaja mnogo znanstvenih člankov, ki se ukvarjajo s prvima dvema, je tretja operacija deležna komaj kakšne pozornosti, niti ni zanjo predvidenega mesta v originalnem načinu poimenovanja različic algoritma. V prispevku smo pokazali, da uporaba različnih postopkov izbora v kombinaciji z naključno perturbacijo vektorjev populacije vodi k opazno boljšemu delovanju na večrazsežnostnih problemih Ključne besede: globalna optimizacija, direktni iskalni postopki, diferencialna evolucija, hevristični postopki On Selection in Differential evolution Differential evolution is a simple algorithm for global optimization. Basically it consists of three operations: mutation, crossover and selection. Despite many research papers dealing with the first two, hardly any attention has been paid to the third one nor is there a place for this operation in the algorithm basic naming scheme. In the paper we show that employing different selection strategies combined with some random perturbation of population vectors notably improves performance in high-dimensional problems. 1 Uvod Diferencialna evolucija (DE) je enostaven, a kljub temu učinkovit algoritem za globalno optimizacijo. Razvila sta ga Storn in Price [1]. V zadnjem desetletju postaja algoritem zaradi svoje izjemne enostavnosti in dobrih konvergenčnih lastnosti čedalje bolj priljubljen v raziskovalnih in inženirskih krogih. Algoritem DE pripada razredu evolucijskih algoritmov (EA), katerih obnašanje posnema biološke procese genetskega dedovanja in preživetja najsposobnejših. Ena bistvenih prednosti EA pred ostalimi numeričnimi optimizacijskimi postopki je, da ne zahteva, da je kriterijska funkcija niti odvedljiva niti zvezna. Zato so ti algoritmi primerni za reševanje široke palete problemov. DE se začne z generacijo NP naključno izbranih D-razsežnostnih parametrskih vektorjev. Nove vektorje dobimo tako, da izbranemu vektorju prištejemo uteženo razliko dveh drugih vektorjev. Tej operaciji pravimo mutacija. Parametre mutiranega vektorja nato mešamo s parametri še enega vektorja, ki ga imenujemo ciljni vektor. Rezultat mešanja parametrov je poskusni vektor, operacija pa se v krogih EA običajno imenuje križanje. Na koncu primerjamo poskusni vektor s ciljnim, in če ta predstavlja slabšo rešitev, ga nadomestimo s poskusnim. To zadnjo operacijo poimenujemo izbor. V vsaki generaciji nastopa vsak vektor enkrat kot ciljni vektor. Obstaja veliko različic algoritma DE [2], med katerimi se najpogosteje uporablja različica DE/rand/1/bin. Zato to različico obravnavamo tudi v tem članku. Pred uporabo algoritma je potrebno določiti vrednosti treh parametrov, ki vplivajo na delovanje algoritma DE. Odločiti se moramo za velikost populacije NP ter za vrednosti dveh krmilnih parametrov - skalirnega faktorja F in faktorja križanja CR. Izbira teh parametrov je običajno odvisna od konkretnega problema, kar zahteva od uporabnika določene izkušnje. Raziskovalci so doslej poskušali ugnati problem z mnogimi adaptivnimi ali samoadaptivnimi strategijami za določanje krmilnih parametrov F in CR [3, 4, 5] in celo velikosti populacije NP [6, 7]. Drugi so proučevali in predlagali različne strategije mutacije in križanja [8, 9, 10]. Z izborom -tretjim operatorjem, ki nastopa v DE - ni bilo doslej narejenih nobenih izrecnih raziskav. Niti ni za ta operator določenega mesta v poimenovalnem vzorcu za različne različice algoritma DE (t.j. DE/x/y/z). V tem članku raziskujemo, kako vplivajo različne strategije izbora na obnašanje algoritma DE, še zlasti na njegovo zmožnost izogibanja lokalnim minimumom oz. stagnaciji. Poleg tega smo algoritmu dodali enostavno operacijo, ki bi jo v genetskih algoritmih poimenovali mutacija - z določeno verjetnostjo smo naključno spreminjali parametre vektorjev populacije. Ker je pojem mutacija v algoritmu DE že rezerviran, smo ta poseg poimenovali naključna perturbacija. V naslednjem razdelku na kratko opišemo delovanje algoritma DE, v 3. razdelku pa predlagamo naključno perturbacijo vektorjev in različne strategije izbora. Rezultate preizkusov na testnih funkcijah predstavimo v 4. razdelku. 2 Kratek pregled diferencialne evolucije Imejmo kriterijsko funkcijo /: IRn -> IR, kjer imamo cilj najti minimum a £ IRn, tako da Vb £ IRn: /(a) < f(b). V tem primeru poimenujemo a globalni minimum. V resničnih problemih je redko mogoče najti točen globalni minimum, zato moramo iz praktičnih razlogov sprejeti kandidata, ki ponuja razumno dobro rešitev. Z namenom, da bi našla globalni minimum, uporablja diferencialna evolucija NP Z>-razsežnostnih parametrskih vektorjev xijG, '= 1,2.....NP kot populacijo v generaciji G. NP se iz generacije v generacijo ne spreminja. Začetno populacijo določimo naključno in tako - če niso znani nobeni podatki o kriterijski funkciji - da uniformno pokrije celoten parametrski prostor. Med optimizacij skim postopkom ustvarimo nove parametrske vektorje tako, da prištejemo uteženo razliko dveh naključno izbranih vektorjev tretjemu vektorju: vi:G+i=xri:G+F-(xr2,G-xrs,G) s celoštevilskimi, med sabo različnimi, naključnimi indeksi Crl: ci G Cr2 :ciiG Cr3: ciG ri,r2,r3e {l,2,...,NP}, ki morajo biti prav tako vsi različni od i, ter z realnim konstantnim členom Fe [0,2]. Tej operaciji pravimo mutacija, dobljenemu vektorju pa mutiran vektor. Parametre mutiranega vektorja nato mešamo s tretjim vektorjem, t.i. ciljnim vektorjem. Rezultat je poskusni vektor ui:G+1=(uli:G+1,u2i,G+i,-,uDi:G+1), kjer Uji,G +1 = (vji,G+1 če(randb(j) < CR) ali j = rnbr{i) | Xji G če(randb(J) > CR) in j ^ rnbr(i) 7 = 1.2.....D. (1) Pri tem je randb(j) j-ti izračun uniformnega naključnega generatorja z izhodom e [0,1], CR je uporabniško določena konstanta e [0,1] in rnbr(i) je naključni indeks e {1,2,...,D}. Slednji zagotavlja, da dobi poskusni vektor vsaj en parameter mutiranega vektorja. Ta operacija mešanja parametrov se običajno imenuje križanje. Na koncu se izvede še izbor, v katerem se odloči, ali naj poskusni vektor postane član generacije G+1. Vrednost kriterijske funkcije v poskusnem vektorju «,/,+/ se primerja z njeno vrednostjo v ciljnem vektorju xi:G po principu pohlepa: ciljni vektor zamenjamo le, če dobimo s poskusnim vektorjem boljšo vrednost kriterij ske funkcije. V nasprotnem primeru poskusni vektor zavržemo, ciljnega pa obdržimo. 3 Spremembe originalnega algoritma DE Naše delo je osredotočeno na del algoritma po križanju, t.j. na trenutek, ko je poskusni vektor že oblikovan. Navdih za spremembe smo dobili iz naslednjega opažanja. Kadar se stopnja križanja CR približuje 1, ne preživi prav dosti ciljnega vektorja v njegovem potomcu (poskusnem vektorju). V tem smislu je mogoče sklepati, daje smer iskanja v smeri od ciljnega proti poskusnemu vektorju prav tako dobra (ali slaba) kot katerakoli druga smer. Preizkusiti smo želeli hipotezo, da utegne obstajati kakšen drug (po možnosti boljši) kandidat za zamenjavo kot sam ciljni vektor. V nadaljevanju bomo predlagali in preizkusili tri različna pravila izbora kandidata, ki bo tekmoval s poskusnim vektorjem. Kandidata označimo s c,- G in ga izberemo v skladu z enim od naslednjih treh kriterijev: (2) kjer pomeni d(y) Evklidovo razdaljo. Pripomniti velja, da tu še vedno obstajajo primeri, ko ni izbran noben kandidat. Takrat poskusni vektor zavržemo. Pod pogojem Crl od vseh vektorjev, pri katerih ima kriterijska funkcija slabšo vrednost kot pri poskusnem vektorju, zamenjamo tistega, ki leži geometrično najbliže ciljnemu vektorju. Naj omenimo, da tako kot originalen algoritem tudi ta strategija vedno zamenja ciljni vektor, če je ta slabši od poskusnega. Sicer za zamenjavo išče kandidata, ki je ciljnemu vektorju čim bliže. Tako kot v originalnem algoritmu, obstaja tudi tu večja verjetnost, da zamenjamo ciljne vektorje s slabo vrednostjo kriterijske funkcije, medtem ko bodo tisti z boljšo vrednostjo preživeli. Poleg tega se bo nek bližnji vektor premaknil na mesto, kamor bi se premaknil ciljni vektor, če ne bi bil slabši od poskusnega. To pospeši kopičenje članov populacije okrog članov z relativno boljšo vrednostjo kriterijske funkcije. Po eni strani lahko to znatno pospeši konvergenco, po drugi pa obstaja nevarnost, da prezgodaj izgubimo potrebno raznolikost in zato ne najdemo globalnega minimuma. Pristop s kriterijem Cr2 je precej različen v tem, da išče kandidata, ki je geometrično najbliže poskusnemu vektorju. V tem smislu se izvajajo zamenjave v prid = xnG, 3n: minn (d(xnG,xiG)^ Vn: /(uiG+1) < f{xnG) = x„,G,3n: min„ (d(x„,G,^iG+1)) Vn:/(u^G+1) < /(xn,G) (n = i,f(uiiG+1)