Elektrotehniški vestnih 74(1-2): 55-60, 2007 Electrotechnical Review, Ljubljana, Slovenija Velikost populacije pri algoritmu diferencialne evolucije Janez Brest, Viljem Žumer, Mirjam Sepesy Maučec Univerza v Mariboru Fakulteta za elektrotehniko, računalništvo in informatiko Smetanova 17, 2000 Maribor, Slovenija E-pošta: janež. brest@uni-mb. si Povzetek. V članku obravnavamo algoritem diferencialne evolucije (DE) za numerično optimizacijo. Algoritem DE je v zadnjem desetletju postal popularen in ga uporabljamo v številnih praktičnih aplikacijah na področjih optimizacije. Algoritem ima tri kontrolne parametre (F - faktor skaliranja, CR - kontrolni parameter križanja, NP - velikost populacije). Izbira ustreznih vrednosti kontrolnih parametrov je ponavadi odvisna od problema, ki ga rešujemo, in od uporabnika zahteva predhodno znanje oziroma izkušnje. Čeprav je pri algoritmu DE izbira parametrov zelo pomembna, ni nobene metodologije za določitev njihovih vrednosti. V članku se bomo omejili le na parameter velikosti populacije. Analizirali bomo vpliv velikosti populacije na uspešnost algoritma DE pri reševanju optimizacijskih problemov z omejitvami. Ključne besede: evolucijsko računanje, optimizacija, iskanje globalnega optimuma, velikost populacije Population Size in Differential Evolution Algorithm Extended Abstract. In this paper we present an experimental analysis showing that the population size NP is an important control parameter in the differential evolution algorithm. Differential Evolution (DE) [16, 17, 15, 11, 12, 10, 18] has been proven to be a powerful evolutionary algorithm for global optimization in many real problems [13, 14]. Although the DE algorithm has been proven to be a simple yet powerful evolutionary algorithm for optimizing continuous functions, users are still faced with the problem of preliminary testing and hand-tuning of the evolutionary parameters prior to commencing the actual optimization process [18]. Different problems usually require different settings for the control parameters. Self-adaptation allows an evolution strategy to adapt itself to any general class of problems by reconfiguring itself accordingly and without any user interaction [1, 2, 7]. Based on the experiment in [5], the necessity of changing control parameters during the optimization process is also confirmed. In literature, self-adaptation is usually applied to the F and CR control parameters [5,4], where F is a scaling factor and CR is a crossover rate. In our previous paper [6], a performance of the self-adaptive differential evolution algorithm is evaluated on a set of 24 benchmark functions provided for the CEC2006 Special session on constrained real-parameter optimization [9]. The method in [6] extends individuals that have not only decision variables but also control parameters F and CR. These parameters are changed/optimized by DE, too. The authors utilize lexicographic ordering in which the constraint violation precedes the objective function to solve constrained problems. In [6] the control parameter NP is set to 200. The number of evaluations of an evolutionary algorithm is computed as a product of NP and the number of generations. The third control parameter NP gets usually less attention in literature, mainly because it affects only the finish time of the evolutionary process when the number of generations is fixed. The scenario is quite different when the number of evalua- Prejet25. avgust, 2006 Odobren 24. januar, 2007 tions is fixed (an algorithm stops after the number of performed evaluations has reached the predetermined value). The question is how to determine NP to get the best results. In this paper experimental results of a self-adaptive differential evolution algorithm are evaluated on the set of 24 benchmark functions provided for the CEC2006 Special session on constrained real-parameter optimization. We especially focus on the third DE control parameter, namely NP. The results confirm our assumption that NP is an important parameter of the DE algorithm. For a set of benchmark functions the best value of the population size seems to be about 120. The optimal value depends on the nature of the problem being solved. The results show that it would be reasonable to include the NP parameter into the adaptation or even self-adaptation scheme as well. Key words: evolutionary computation, optimization method, global optimum search, population size 1 Uvod V članku predstavljamo algoritem diferencialne evolucije (DE) (ang. Dijferential Evolutiori) [17] za numerično optimizacijo funkcij. Algoritem DE je v zadnjih letih postal popularen in ga uporabljamo v številnih praktičnih aplikacijah, predvsem zato, ker algoritem odlikuje dobra konvergenca [16, 17, 15, 11, 12, 10, 18, 5], Za optimizacijo računsko težkih problemov se danes uporabljajo različne tehnike, kot so simulirano ohlajanje, nevronske mreže, optimizacija s pomočjo roja delcev (ang. Partical Swarm Optimization - PSO) in različne evolucijske tehnike. Algoritem DE lahko prištevamo k evolucijskim algoritmom, ki imajo nekatere prednosti v primerjavi z drugimi metodami. Evolucijski algoritmi potrebujejo le funkcijo, ki jo želimo optimirati. Ponavadi govorimo o iskanju globalnega minimuma. Izbira ustreznih kontrolnih parametrov je ponavadi odvisna od problema, ki ga rešujemo, in od uporabnika zahteva predhodno znanje oziroma izkušnje. Čeprav je izbira parametrov zelo pomembna, ni nobene metodologije za določitev njihovih "optimalnih" vrednosti. Pri optimizaciji funkcije je cilj poiskati vektor xm^n, za katerega velja: Vx, /(xm^n) < /(x). Funkcija / ni treba, da je zvezna ali odvedljiva, mora pa biti navzdol omejena. Algoritem DE ima tri kontrolne parametre (F - faktor skaliranja, CR - kontrolni parameter križanja, NP -velikost populacije), ki se pri originalnem algoritmu DE med optimizacijskim postopkom ne spreminjajo [16, 12, H]. Mehanizem samoprilagajanja omogoča, da se evolucijska strategija (sama) prilagodi naravi problema, tako da se ustrezno rekonfigurira. Ta prilagoditev se opravi brez aktivne vloge uporabnika [1, 2, 7]. Eksperimenti v [5, 4, 3] so pokazali, da s spreminjanjem kontrolnih parametrov med optimizacij skim postopkom lahko izboljšamo rezultate. V literaturi zasledimo, da avtorji ponavadi uporabljajo samoprilagajanje pri kontrolnih parametrih F in CR [12, 11, 5]. V našem predhodnem prispevku [6] smo opravili študijo zmogljivosti samoprilagodljivega algoritma diferencialne evolucije na testnih funkcijah, ki so bile posebej izbrane za CEC2006 Special session on constrained real parameter optimization [9]. Metoda, ki smo jo predstavili pri reševanju optimizacijskih problemov z omejitvami, uporablja leksikografsko ureditev, pri kateri je dopustnost rešitve pomembnejša od njene ocenitvene vrednosti. V omenjenem članku smo uporabljali samoprilagajanje kontrolnih parametrov F in CR, vrednosti kontrolnega parametra N P pa nismo spreminjali. Nastavili smo ga na 200. V tem članku želimo ugotoviti vpliv kontrolnega parametra NP na kakovost rešitve pri optimizacijah z omejitvami. Število ovrednotenj nevals evolucijskega algoritma izračunamo kot produkt NP in števila generacij. Tretji kontrolni parameter NP ponavadi ni zbudil pozornosti pri raziskovalcih, ki uporabljajo algoritem DE. Po našem mnenju je razlog v tem, da omenjeni kontrolni parameter vpliva le na trajanje evolucijskega postopka, ko fiksiramo število generacij. Včasih raziskovalci primerjajo uspešnost algoritmov le pri vnaprej izbranem številu generacij. Popolnoma drugačen scenarij nastopi, ko fiksiramo nevals (algoritem ustavimo, ko doseže vnaprej predpisano fiksno število ovrednotenj). Poraja se vprašanje, kako naj določimo/izberemo velikost populacije NP, da bo algoritem dajal najboljše rezultate. V tem članku prikazujemo eksperimentalne rezultate samoprilagodljivega algoritma diferencialne evolucije na 24 testnih funkcijah [9], s poudarkom na velikosti populacije NP. Samih testnih funkcij v tem članku ne prikazujemo, ker so preobsežne. Nadaljevanje prispevka je organizirano takole: V 2. poglavju opišemo algoritem diferencialne evolucije. 3. poglavje govori o optimizaciji z omejitvami in kako omejitve vključimo v algoritem DE. V 4. poglavju predstavimo naš samoprilagodljivi algoritem DE. Rezultati, ki smo jih dobili s pomočjo samoprilagodljivega algoritma na optimizacij skih primerkih, so prikazani v 5. poglavju. V 6. poglavju podajamo razpravo o kontrolnem parametru NP. Sledi še sklepno, 7. poglavje, kjer podamo tudi smernice za nadaljnje raziskave. 2 Algoritem diferencialne evolucije Algoritem diferencialne evolucije (DE) ustvari novega posameznika s kombinacijo starša in izbranih posameznikov iste populacije. Nov posameznik zamenja starša, če ima boljšo ocenitveno vrednost. Pri algoritmu DE [16, 17, 15] populacija vsebuje NP D-dimenzionalnih vektorjev oziroma posameznikov: = Xi,2,G, — j ¿ = 1,2, ..., N P. Z G označimo generacijo. V eni generaciji algoritem DE uporabi mutacijo in križanje na vsakem vektorju in ustvari nov vektor (novega posameznika): U i,G = (Ui,l,G, Uii2,G, Ui,D,G), « = 1,2, N P. V eni generaciji algoritem DE ustvari NP novih posameznikov. Nato uporabi selekcijo, da izbere vektorje za naslednjo generacijo (G + 1). Začetna populacija je izbrana naključno (po enakomerni porazdelitvi) med spodnjo (xjjow) in zgornjo (%j,upp) mejo, ki sta definirani za vsako spremenljivko Xj. Spodnjo in zgornjo mejo definira uporabnik glede na naravo problema, ki ga rešuje. Po inicializaciji algoritem DE izvede več transformacij (operacij) v postopku, ki ga imenujemo evolucija. 2.1 Mutacija Mutacija za vsak vektor iz populacije ustvari mutiran vektor: => = (Vi^cVi^G, —,ViiDiG), i = 1,2,..., NP. Algoritem DE ustvari mutiran vektor z uporabo ene izmed strategij mutacije. Originalni algoritem DE pozna naslednje strategije: 1. "rand/1": vi?G = + F • (xr2?G - xr3,G) 2. "best/1": vi?G = *best,G + F • (xri>G - Xr2,cO 3. "current to best/1": Vi,g = + ^ • (x&esi,G - Xi?G) + F • (xri>G - xr2,G) 4. "best/2": Vi,g = X6esi?G + ^'(xri,G-Xr2?G)+^-(xr3,G-xr4>, 4,g) 5. "rand/2": Vi,g = Xri,G + ^ • (xr2,G ~ Xrs,G) + ^ ' (xr4,G ~ Indeksi ri, 7*2,7*3,7*4,7*5 predstavljajo naključna in paroma različna naravna števila na intervalu [1, NP]. Indeksi so različni tudi od indeksa i. F je mutacijski skalirni faktor (realno število) na intervalu [0, 2], ponavadi manjši kot 1. ~X-best,G je vektor z najboljšo ocenitveno vrednostjo oziroma najboljši posameznik generacije G. 2.2 Križanje Po končani mutaciji sledi križanje, ki iz posameznika i in pripadajočega mutiranega vektorja ustvari novega posameznika i: uiJ,G = j v i, j,g če rand( 0,1) < CR ali j = jrand, sicer ¿ = 1,2,..., NP in j = 1, 2,..., D. CR je kontrolni parameter križanja ali faktor na intervalu [0,1) in pomeni verjetnost, da se komponenta vektorja pri novem posamezniku ustvari iz komponente mutiranega vektorja. Indeks jrand je naključno izbrano naravno število na intervalu [1, NP]. Njegova naloga je, da je vsaj ena komponenta vektorja pri novem posamezniku izbrana iz mutiranega vektorja. 2.3 Selekcija Glede na ocenitveno vrednost posameznika iz populacije in ocenitveno vrednost pripadajočega novega poza-meznika z operacijo selekcije izberemo, kateri od obeh omenjenih posemeznikov bo preživel in bo uvrščen v naslednjo generacijo. Ce na primer iščemo globalni minimum, uporabimo za selekcijo naslednje pravilo: Xf,G+l Ui?G Če/(ui?G) < /(Xi,G), Xi?G sicer. 3 Omejitve V zadnjih letih so bile na področju genetskih algoritmov razvite različne metode za obravnavanje omejitev pri optimizaciji. Avtorji [14, 8] so metode razvrstili v naslednje kategorije: • Metode, ki ohranjajo dopustne rešitve. Ideja teh metod temelji na specializiranih operatorjih, ki trans-formirajo posameznike z dopustnimi rešitvami spet v posameznike z dopustnimi rešitvami. Metode predpostavljajo le linearne omejitve in dopustne startne točke v začetni populaciji. • Metode, ki temeljijo na kazenski funkciji. Precej evolucijskih algoritmov vključuje pri obravnavi omejitev metode, ki temeljijo na principu zunanje kazenske funkcije, ki kaznuje nedopustne rešitve. Metode se razlikujejo v pomembnih podrobnostih, kako je kazenska funkcija načrtovana in kako jo uporabimo pri nedopustnih rešitvah. • Metode, ki razlikujejo med dopustnimi in nedopustnimi rešitvami. Obstaja nekaj metod, ki poudarjajo razlikovanje med dopustnimi in nedopustnimi rešitvami preiskovalnega prostora. Ena od metod razlikuje med posameniki z dopustnimi in nedopustnimi rešitvami: za vsakega posameznika z dopustno rešitvijo x in za vsakega posameznika z nedopustno rešitvijo y velja: /(x) < /(y), t.j. vsak posameznik z dopustno rešitvijo je boljši od posameznika z nedopustno rešitvijo. • Druge hibridne metode. Te metode združujejo tehnike evolucijskega računanja z determinističnimi postopki numerične optimizacije. Algoritem DE ne potrebuje posebne razširitve, da bi ga lahko uporabili pri reševanju nalog z omejitvami [19]. Pri reševanju večine problemov z omejitvami lahko uporabimo kazensko funkcijo. Rešitev x je dopustne1, če 9i(x) < 0, za i = 1, in I M*) I -e < °> zai = +1, kjer omejitve z enakostmi transformiramo v omejitve z neenakostmi. V okviru CEC2006 [9] je (bil) e postavljen na 0, 0001. Povprečje kršitev omejitev (ang. mean viola-tions) v je definirano takole: v =--1-, kjer m r ( \ - če^x) > G O, O če \hj(x)\ — e <0. Vsota vseh kršitev omejitev je enaka nič pri dopustnih rešitvah. Omenjena vsota je pozitivna, ko je kršena vsaj ena omejitev. Očitna uporaba kršitev omejitev je pri usmeritvi postopka iskanja proti dopustnim področjem v iskalnem prostoru. Precej raziskav je bilo narejenih na tem področju in bralcu priporočamo pregled tehnik za obravnavanje omejitev v knjigi avtorjev Michalewicz in Fogel [13]. 4 Samoprilagodljivi algoritem diferencialne evolucije V [5] je predstavljen samoprilagodljivi mehanizem, ki med evolucijo spreminja kontrolna parametra F in CR. *1.G rt rt AG CR2rG rt rt CR2.C ... XNP.G F1 NPjG CR 1 F2 NP.G CRXP. C f3 VV/VT CRXPrt7 populacija tretja slrclcgi ja Slika 1. Samoprilagajanje, ko imamo tri strategije Figure 1: Self-adapting: encoding aspect of three DE strategies Slika 1 prikazuje, kako lahko kontrolna parametra treh originalnih strategij algoritma DE shranimo v vsakega posameznika. Vsaka strategija ima svoja kontrolna parametra. Brez težav lahko v naš algoritem vključimo še več strategij. Pri algoritmu v prispevku [5] je uporabljena le ena strategija, na sliki 1 pa prikazujemo razširitev samoprilagajanja na tri strategije. Nove kontrolne parametre 1,2,3 izračunamo takole: 1 in 1, k — F? i,G+1 CR? Fi + randi * Fu če rand2 < T\, F£G sicer, i,G+l randz če v and4 < t2, CR\g sicer. Tako dobimo kontrolna parametra F in CR pri novem posamezniku, k pomeni izbrano strategijo algoritma DE. Ko se ustvarja nov posameznik, je aktivna le ena strategija. V vsaki iteraciji se izbere ena strategija, ki je aktivna, r and j, j G {1,2,3,4} so naključne realne vrednosti na intervalu [0,1). T\ in t