ERK'2019, Portorož, 215-218 215 Analiza algoritma jDE100 za enokriterijsko globalno optimizacijo z realnimi vrednostmi Janez Brest 1 , Jan Popiˇ c 1 , Mirjam Sepesy Mauˇ cec 2 , Borko Boˇ skovi´ c 1 1 Laboratorij za raˇ cunalniˇ ske arhitekture in jezike, Inˇ stitut za raˇ cunalniˇ stvo, 2 Laboratorij za digitalno procesiranje signalov, Inˇ stitut za elektroniko in telekomunikacije, Fakulteta za elektrotehniko, raˇ cunalniˇ stvo in informatiko, Univerza v Mariboru, Koroˇ ska cesta 46, 2000 Maribor, Slovenija, janez.brest@um.si, jan.popic1@um.si, mirjam.sepesy@um.si, borko.boskovic@um.si An Analysis of the jD100 Algorithm for Real-Parameter Single Objective Global Optimization Abstract. Solving real-parameter single objective problems is a challenging research topic in evolutionary computation community. At the IEEE Congress on Evolutionary Com- putation (CEC) 2019, Special Session on 100-Digit Chal- lenge on single objective numerical optimization was orga- nized, where ten problems were defined and participants of this challenge were required to solve each problem and try to reach the accuracy of 10 digits for each of them. The optimum values were known for all problems. There were no time limit and no limit for maximum number of function evaluations. In this paper, we present a version of Differen- tial Evolution algorithm, which is based on the jDE100 al- gorithm, for tackling 100-Digit Challenge. The main focus of this paper is to find out why many algorithms that par- ticipated in 100-Digit Challenge competition were not able to solve all problems, except jDE100. We provide an ana- lysis to show which mechanisms helped the jDE100 algo- rithm to successfully solve all problems, contrary to other algorithms. 1 Uvod V vsakdanjem ˇ zivljenju se ljudje pogosto sreˇ cujemo z op- timizacijo na vsakem koraku, a se morda tega niti ne zave- damo. Nenehno teˇ zimo k zmanjˇ sevanju stroˇ skov, na poti v ˇ solo ali sluˇ zbo ˇ zelimo po najkrajˇ si poti ali pa po poti, ki naj najhitreje pripelje do cilje, itd. V ˇ clanku obravnavamo numeriˇ cno optimizacijo. Pred- stavili bomo novo verzijo algoritma diferencialne evolucije (DE). DE se v zadnjem ˇ casu uporablja v ˇ stevilnih praktiˇ cnih aplikacijah. Reˇ sevanje enokriterijskih optimizacijskih pro- blemov z realnimi vrednostmi je aktualna raziskovalna te- matika na podroˇ cju evolucijskega raˇ cunanja. Na medna- rodnem IEEE kongresu o evolucijskem raˇ cunanju (CEC 2019) se je odvijala posebna sekcija o enokriterijski glo- balni optimizaciji z realnimi vrednostmi. Znotraj sekcije je bilo tudi tekmovanje ’100-Digit Challenge’, ki je letos pre- koraˇ cilo meje konference CEC in je vkljuˇ cevalo tudi kon- ferenci GECCO 2019 in SEMCCO 2019. V ˇ clanku bomo govorili o optimizacijskih proble- mih, pri katerih nas zanimajo minimumi. Problem glo- balne optimizacije lahko definiramo kot iskanje vektorja ~ x, ki minimizira funkcijsko vrednost f(~ x). Vektor ~ x = fx 1 ;x 2 ;:::;x D g obsega D spremenljivk. Za vsako spre- menljivkox j (j = 1;2;:::;D) je definirana spodnjax j;low in zgornja x j;upp meja. Reˇ cemo tudi, da D oznaˇ cuje di- menzijo optimizacijskega problema. Funkcija f ni nujno, da je zvezna ali odvedljiva, mora pa biti omejena. Algoritem DE [7, 8] sta pred veˇ c kot dvajsetimi leti predstavila R. Storn in K. Price. Dandanes sta ˇ se oba ak- tivna na raziskovalnem podroˇ cju evolucijskih algoritmov, predvsem diferencialne evolucije (omenimo, da nekateri strokovnjaki v Sloveniji uporabljajo tudi izraz diferenˇ cna evolucija). Lahko reˇ cemo, da DE predstavlja uspeˇ sen algoritem, ki se danes uporablja v mnogih raziskavah in praktiˇ cnih aplikacijah [2, 5, 9]. ˇ Clanek ima sledeˇ co strukturo. V drugem poglavju po- damo ozadje treh algoritmov DE. V tretjem poglavju pre- dlagamo novo verzijo (izpeljanko) algoritma in predsta- vimo njegove podobnosti in razlike z algoritmom jDE100. Eksperimenti, rezultati in analiza so podani v ˇ cetrtem po- glavju. Peto poglavje pa zakljuˇ ci ˇ clanek. 2 Ozadje 2.1 Algoritem jDE Algoritem jDE [4], ki je bil prviˇ c predstavljen leta 2006, uporablja samo-prilagodljiv mehanizem krmilnih parame- trov, kjer ima vsak posameznik v populaciji svoji vrednosti za krmilna parametraF i in CR i . Novi vrednosti krmilnih parametrovF i;g+1 inCR i;g+1 se izraˇ cunata pred mutacijo na naslednji naˇ cin: F i;g+1 = ( F l +rand 1 F u ; if rand 2 < 1 ; F i;g ; otherwise; CR i;g+1 = ( rand 3 ; if rand 4 < 2 ; CR i;g ; otherwise; 216 Tabela 1: Parameteri in njihove vrednosti pri algoritmu jDE100-ver2.0. F l inCR l sta parametra, ki smo ju lahko nastavili posebej za vsako funkcijo. Parameter Vrednost Kratek opis F l 0.2 za F4, F7 spodnja meja skalirnega faktorja F l 0.1 za F8 spodnja meja skalirnega faktorja F l 0.001 za F9 spodnja meja skalirnega faktorja F l 0.15 pri ostalih funkcijah spodnja meja skalirnega faktorja F u 1.1 zgornja meja skalirnega faktorja CR l 0.1 za F8 spodnja meja parametra kriˇ zanja CR l 0.9 za F9 spodnja meja parametra kriˇ zanja CR l 0.0 pri ostalih funkcijah spodnja meja parametra kriˇ zanja CR u 1.1 zgornja meja parametra kriˇ zanja F init 0.5 inicialna vrednost skalirnega faktorja CR init 0.5 inicialna vrednost parametra kriˇ zanja 1 0.1 verjetnost samo-prilagajanja skalirnega faktorja 2 0.1 verjetnost samo-prilagajanja parametra kriˇ zanja bNP 1000 velikostP b sNP 25 velikostP s ageLmt 1e9 ˇ st. ovrednotenj, ko se naj zgodi reinicializacija populacije eps 1e 16 majhna vrednost za primerjavo, ˇ ce sta dve vrednosti podobni maxFEs 1e12 en izmed ustavitvenih pogojev (Pogoj ni bil izpolnjen!) myEqs 25 reinicializacija, ˇ ce ima myEps% posameznikov podobno funkcijsko vrednost kjer sorand j ;j2f1;2;3;4g nakljuˇ cne vrednosti, poraz- deljene uniformno na intervalu [0;1]. Vrednosti 1 in 2 sta verjetnosti, s katerima krmilimo krmilna parametra F inCR. Podroben opis algoritma najdemo v literaturi [4, 3]. 2.2 Algoritem jDE100 Algoritem jDE, ki smo ga na kratko opisali v predhodnem podpoglavju, smo nadgradili v algoritem jDE100 [3], ki je sodeloval v tekmovanju 100-Digit Challenge na CEC 2019. jDE100 uporablja dve razliˇ cno veliki populaciji in njima prilagojeni reinicializaciji. V evolucijskem procesu algoritma jDE100 imamo tri ponavljajoˇ ce se korake: 1. Izvede se ena generacija na veliki populaciji,P b . 2. ˇ Ce je potrebno, se najboljˇ si posameznik, ~ x best , ko- pira v manjˇ so populacijoP s . 3. Izvede se veˇ c generacij na majhni populaciji,P s . Velikost velike populacije jem-kratnik (m2 1;2;:::) veli- kosti majhne populacije, kar pomeni, da algoritem razdeli ˇ stevilo evaluacij med obe populaciji: polovica evaluacij za veliko in polovica za majhno populacijo, ˇ ce pri slednji iz- vedem generacij. Pomembna je tudi reinicializacija, ki jo loˇ ceno izve- demo na obeh populacijah, ˇ ce je izpolnjen pogoj, da ima vnaprej predpisano ˇ stevilo najbolje ocenjenih posamezni- kov v dani populaciji zelo podobno funkcijsko vrednost. V tem primeru smo ocenili, da se je populacija ujela v lokalni optimum. Reinicializacijo velike populacije izve- demo tako, da vse posameznike nakljuˇ cno reinicializiramo. Podobno storimo tudi pri majhni populaciji, z razliko da najboljˇ sega posameznika pustimo nespremenjenega (ga ne reinicializiramo). Velika populacija skrbi za veˇ cjo raznolikost posame- znikov, manjˇ sa pa omogoˇ ca hitrejˇ so konvergenco iskanja. Najboljˇ sega posameznika kopiramo iz velike populacije, v kateri je bil najden, v manjˇ so. V obratni smeri pa ne kopi- ramo. Algoritem ima parametre, ki so predstavljeni v tabeli 1. Kot zanimivost omenimo, da smoF u nastavili na vrednost 1:1 (tako jeF 2 [F l ;F l +F u ])), kar pomeni, da je zgor- nja meja parametra veˇ cja od 1. Podobno smo nastavili tudi CR u = 1:1. Podroben opis algoritma bralec najde v prispevku [3], saj je naˇ s glavni namen v tem prispevku analiza mehaniz- mov. Zanima nas, ali lahko nastavitve parametrov algo- ritma jDE100 odloˇ cilno vplivajo na uspeˇ snost reˇ sevanja problemov na tekmovanju. Preden se lotimo analize, v nas- 217 Tabela 2: Opis funkcij za ’100-Digit Challenge’ [6]. funkcija F i =F i (x ) D meje iskalnega prostora 1 Storn’s Chebyshev Polynomial Fitting Problem 1 9 [-8192, 8192] 2 Inverse Hilbert Matrix Problem 1 16 [-16384, 16384] 3 Lennard-Jones Minimum Energy Cluster 1 18 [-4, 4] 4 Rastrigin’s Function 1 10 [-100, 100] 5 Griewank’s Function 1 10 [-100, 100] 6 Weierstrass Function 1 10 [-100, 100] 7 Modified Schwefel’s Function 1 10 [-100, 100] 8 Expanded Schaffer’s F6 Function 1 10 [-100, 100] 9 Happy Cat Function 1 10 [-100, 100] 10 Ackley’s Function 1 10 [-100, 100] Tabela 3: 50 zagonov algoritma a200-25 za vsako funkcijo, ki so v tabeli prikazani glede na ˇ stevilo najdenih pravilnih decimalk. funkcija ˇ stevilo pravilnih decimalk ˇ st. toˇ ck 0 1 2 3 4 5 6 7 8 9 10 F1 0 0 0 0 0 0 0 0 0 0 50 10 F2 0 0 0 0 0 0 0 0 0 0 50 10 F3 0 0 0 0 0 0 0 0 0 1 49 10 F4 0 0 0 0 0 0 0 0 0 0 50 10 F5 0 0 0 0 0 0 0 0 0 0 50 10 F6 0 0 0 0 0 0 0 0 0 0 50 10 F7 0 0 0 0 0 0 0 0 0 0 50 10 F8 0 0 0 0 0 0 0 0 0 0 50 10 F9 0 0 1 26 17 5 0 0 0 0 1 4.36 F10 0 0 0 0 0 0 0 0 0 0 50 10 Skupno ˇ stevilo toˇ ck: 94.36 lednjem podpoglavju na kratko opisujemo ˇ se en algoritem, ki bo vkljuˇ cen v analizo. 2.3 Algoritem rjDE Algoritem rjDE je nadgradnja algoritma jDE z mehaniz- mom reinicializacije populacije. Omenjeni mehanizem je podoben tistemu, ki smo ga opisali v algoritmu jDE100. Opis algoritma rjDE najdemo v [1], kjer je bila nare- jena primerjava zmogljivosti algoritmov na 100-Digit Chal- lenge pri omejitvi najveˇ cjega ˇ stevila vrednotenj funkcije (maxFES = 10 7 ). 3 Hibrid algoritmov jDE100 in rjDE Z namenom, da bi ugotovili, kateri mehanizmi omogoˇ cajo dobro delovanje algoritma jDE100 na 100-Digit Challenge, smo zasnovali novo verzijo algoritma, ki je hibrid med al- goritmom jDE100 in algoritmom rjDE. ˇ Cemu izbrati tak naˇ cin, ˇ ce pa imamo na drugi strani morda bolj trivialno reˇ sitev: v algoritmu jDE100 bi lahko po vrsti izklopili en mehanizem in pognali algoritem. Implementacijsko ideja ni zahtevna, a izvedba enega poskusa (50 zagonov 10 pro- blemov) traja skoraj 4 dni. Izvedba teh eksperimentov bi trajala predolgo, saj ob izvedbi eksperimenta (npr. za ve- liko populacijo, malo populacijo, reinicializacijo velike in majhne populacije, samoprilagajanje krmilnih parametrov F in CR, kopiranje najboljˇ sega posameznika iz velike v majhno populacijo, itd.) in ˇ studiji vpliva parametrov do- bimo preveˇ c kombinacij. Zato smo naˇ crtovali novo verzijo algoritma (poimenujmo ga a200-25), ki ima naslednje me- hanizme in nastavitve: ohranimo inicializacijo, kot jo ima jDE100, ohranimo dve populaciji, a spremenimo velikost ene izmed njiju. Velikost velike populacije je 200 veli- kost majhne populacije pa 25. (Spomnimo, da ima jDE100 velikosti populacij 1000 in 25.), malenkost spremenimo tudi vrednosti nekaterih pa- rametrov, ki so predvsem posledica zmanjˇ sanja veli- 218 kosti velike populacije. VrednostF l = 1:0= p bNP v primeru velike populacije, in F l = 1:0= p sNP v primeru majhne populacije. Vrednosti bNP in sNP oznaˇ cujeta velikost velike in majhne popula- cije. ParameterF l je enak tudi v algoritmu rjDE, kjer imamo le eno populacijo. CR l = 0:0 za vse funkcije, razen za F9, kjer jeCR l = 1:0. 4 Eksperiment in rezultati Rezultati, ki smo jih dobili, ko smo 50-krat pognali algo- ritem a200-25 na funkcijah 100-Digit Challenge, so prika- zani v tabeli 3. Opazimo lahko, da je algoritem uspeˇ sno reˇ seval 9 funkcij in da je bila najteˇ zja F9. Dodatno lahko opazimo, da je v enem primeru uspel najti reˇ sitev le na 9 decimalk natanˇ cno, in sicer pri funkciji F3. Analizirajmo funkcijo F9. ˇ Ce je moˇ znih 10 toˇ ck pri vsaki funkciji, potem je vrednost 4.36 nekoliko niˇ zja od po- lovice. Poudarimo, da je algoritem uspel najti 5 pravilnih decimalk v 5 primerih, v enem primeru je uspel najti vseh 10 decimalk. Primerjava z rezultati ostalih algoritmov, ki so sodelovali v tekmovanju, kaˇ ze, da je algoritem a200-25 dosegel kar solidne rezultate tudi na funkciji F9, ki je pov- zroˇ cala najveˇ c teˇ zav tekmovalnim algoritmom. Omenimo, da je algoritem rjDE dosegel 78,6 toˇ ck na funkcijah s tekmovanja 100-Digit Challenge pri maxFES = 10 7 [1], algoritem DE 42,68 toˇ ck in jDE 66,48 toˇ ck. Ugotovimo lahko, da je vrstni red algoritmov (DE, jDE, rjDE) doloˇ cen s ˇ stevilom mehanizmov – bolj so- fisticiran algoritem je dosegel veˇ cje ˇ stevilo toˇ ck. Ko smo algoritem rjDE pozneje pognali zmaxFES = 10 9 , je do- segel 85 toˇ ck. Primerjava a200-25 z algoritmi DE, jDE in rjDE pa pove, da sta dve populaciji pomembni, saj sta algoritmu a200-25 prinesli veˇ c toˇ ck. Prav tako je pomemben tudi parameter CR. In zadnja, kar pa ni nujno najmanj po- membna, ugotovitev iz eksperimentalnega dela v tem pri- spevku, je parameter velikosti velike populacije. Funkcija F9 oziroma rezultati te funkcije kaˇ zejo, da je vˇ casih po- trebna tudi nekoliko veˇ cja populacija. Zahvala J. Brest in B. Boˇ skovi´ c priznavata financiranje prispevka s strani Javne agencije za raziskovalno dejavnost Republike Slovenije, raziskovalni program P2-0041 – Raˇ cunalniˇ ski sistemi, metodologije in inteligentne storitve. M. S. Mauˇ cec priznava financiranje prispevka s strani Javne agen- cije za raziskovalno dejavnost Republike Slovenije, razi- skovalni program P2-0069 – Napredne metode interakcij v telekomunikacijah. 5 Zakljuˇ cek V prispevku smo naˇ crtovali novo verzijo algoritma za reˇ sevanje problema 100-Digit Challenge z namenom, da smo lahko analizirali in izpostavili mehanizme in nasta- vitve pomembnih vrednosti parametrov, s pomoˇ cjo kate- rih je algoritem jDE100 dokaj uspeˇ sno reˇ seval probleme na omenjenem tekmovanju. Radi bi izpostavili, da je velikost populacije imela tudi vpliv na uspeˇ snost pridobljenih toˇ ck pri najteˇ zji funkciji na tekmovanju, F9, z imenom ”Happy Cat”. Nadaljnje smernice razvoja algoritmov za izziv 100- Digit Challenge vkljuˇ cujejo razvoj novih mehanizmov, s katerimi bi zmanjˇ sali ˇ stevilo potrebnih evaluacij funkcij, predvsem na funkcijah F8 in F9. Literatura [1] Amina Ali´ c, Klemen Berkoviˇ c, Borko Boˇ skovi´ c, and Janez Brest. Population size in differential evolution. In Aleˇ s Za- muda, editor, 7-th Joint International Conferences on Swarm, Evolutionary and MemeticComputing Conference (SEMCCO 2019) & Fuzzy And Neural Computing Conference(FANCCO 2019), 2019. [2] Borko Boˇ skovi´ c and Janez Brest. Protein folding optimization using differential evolution extended with local search and component reinitialization. Information Sciences, 454:178– 199, 2018. [3] J. Brest, M. Sepesy Mauˇ cec, and B. Boˇ skovi´ c. The 100-digit challenge : algorithm jDE100. In IEEE Congress on Evoluti- onary Computation (CEC) 2019, pages 19–26. IEEE, 2019. [4] Janez Brest, Saˇ so Greiner, Borko Boˇ skovi´ c, Marjan Mernik, and Viljem ˇ Zumer. Self-adapting control parameters in diffe- rential evolution: A comparative study on numerical bench- mark problems. IEEE Transactions on Evolutionary Compu- tation, 10(6):646–657, 2006. [5] Mirjam Sepesy Mauˇ cec, Janez Brest, Borko Boˇ skovi´ c, and Zdravko Kaˇ ciˇ c. Improved Differential Evolution for Large- Scale Black-Box Optimization. IEEE Access, 2018. [6] K. V . Price, N. H. Awad, M. Z. Ali, and P. N. Suganthan. Problem Definitions and Evaluation Criteria for the 100-Digit Challenge Special Session and Competition on Single Objec- tive Numerical Optimization. Technical report, Nanyang Technological University, Singapore, November 2018. [7] R. Storn and K. Price. Differential Evolution - a simple and efficient adaptive scheme for global optimization over conti- nuous spaces. Technical Report TR-95-012, Berkeley, CA, 1995. [8] Rainer Storn and Kenneth Price. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11:341– 359, 1997. [9] Aleˇ s Zamuda and Janez Brest. Self-adaptive control parame- ters’ randomization frequency and propagations in differential evolution. Swarm and Evolutionary Computation, 25:72–99, 2015.