Global Optimization Strategies: Analogies to Human Behavior

CIplus Band 2/2018 Global Op imiza ion S a egies: Analogies o Human Beha io Jö g S o k and Thomas Ba z-Beiels ein Global Op imiza ion S a egies: Analogies o Human Beha io Jö g S o k Thomas Ba z-Beiels ein June 25, 2018 Op imiza ion algo i hms [9] a e p esen e e ywhe e in ou daily li e. Wi hou e en no icing hem, hey ensu e ha ou o de s a i e on ime, ou phones ha e he bes connec ion and p oduc s ha e a ce ain quali y. I we walked h ough a mode n company, we would no ice ha nea ly e e y p oduc ion p ocess was op imized and e e y machine was de eloped wi h help o ma hema ical op i- miza ion. Du ing he las decades, se e al new design schemes o op imiza ion algo i hms we e de eloped and new algo i hms a e p oposed e e y day. Pa ic- ula wo g oups o algo i hms a e in he ocus o cu en esea ch. Fi s , he so-called me aheu is ics, which a e capable o sol ing a la ge a ie y o op i- miza ion p oblems wi h s ochas ic s a egies wi hou much knowledge abou he p oblem o sol e [2]. Second, model-based and especially su oga e-assis ed op imiza ion algo i hms, which domina e he ield o cos ly eal-wo ld applica- ions and ha e become he s a e-o - he-a o his ask in e icien algo i hm design [1]. Simila o many mode n echnical de elopmen s, many o hese algo i hms a e na u e-inspi ed [6]. Fo example, hese sea ch s a egies ha e analogies wi h he beha io o animals. To gi e an o e iew o he di e en a ailable op imiza ion me hods, we wan o use a simila app oach and classi y hem based on he na u al human beha io in pa h inding. To es ablish such a comp ehensi e axonomy, we ocus on iden i ying key elemen s o algo i hm design and u ilize hese o de ine a clea sepa a ion be ween a small numbe o algo i hm classes. In con as o o he wo k, by hese means we will keep he le el o de ail on an abs ac , bu s ill aluable le el. This abs ac ion le el allows us o p esen simply comp ehensible ideas on how he indi idual classes di e and mo eo e , how he espec i e algo i hms pe o m hei sea ches. Fo his pu pose, we di ide op imiza ion algo i hms in o in ui i e classes: Wan- de e , Guide, Ca og aphe . The Wande e The in ui i e desc ip ion o a wande e is a single (human) indi idual who wande s h ough he landscape o ind he mos a ac i e place in he neighbo hood. By hese means he only u ilizes local in o ma ion abou his 1 cu en posi ion o ind he bes di ec ion. So i he goal o his indi idual is o ind he highes moun ain, he will likely ollow he ascending way, because he di ec ly sa is ies he cu en objec i e. Fu he mo e, he does no u ilize ga he ed in o ma ion, so ha he e is a chance ha he will e isi he same place. This class esembles classical s ochas ic and g adien -based hill climbing s a egies [8, 5], which a y a single candida e solu ion un il a be e o he bes possible solu ion ( he global op imum) is ound. The selec ion o a classical hill climbe is g eedy, which means ha only imp o ing s eps a e accep ed. The sea ch s a egy is able o sol e con ex p oblems wi h a single op imum e y as and e icien , bu is no sui able o p oblems wi h many op ima. The Guide To gi e an in ui i e idea, a human hike looking o an in e es ing place would y o memo ize he own pa h, ollow a el signs abou in e es ing o o bidden sea ch egions o ask o he people o sha e hei knowledge and gi e di ec ions. Fu he mo e she will pass on he own gained knowl- edge abou he landscape o o he people i asked. Algo i hms om he guide class use se e al simul aneous candida e solu- ions sp ead o e he sea ch space and hus ha e good explo a ion abili ies. E olu iona y algo i hms [3, 7] a e he ou s anding example o his class. They u he combine he in o ma ion o ga he ed solu ions o c ea e new candida es. These sea ch s a egies a e able o sol e complex, mul i-modal p oblems. The Ca og aphe The in ui i e idea is a human-like specialis who sys ema ically measu es a landscape by aking samples o he heigh o c ea e a opological map, which esembles he eal landscape. This map will be exac a he sam- pled loca ions and app oxima es he emaining landscapes by eg ession. I can hen be examined and u ilized by any o he indi idual o ind a desi ed loca ion. One could hink o a guide o wande e using a pape map o digi al na iga ion sys em o ind he highes moun ain. This algo i hm class uses da a-d i en models o all ga he ed solu ions. They a e used o in elligen ly sea ch he space by pu ing candida e so- lu ions in e y p omising a eas o hose whe e no in o ma ion is ga he ed ye [4, 1]. Because o he complexi y o he models and hei la ge com- pu a ion ime, hese algo i hms a e bes o e y complex and expensi e op imiza ion p oblems, whe e solu ions ha e o be ound in a couple o i e a ions. Bene i s o his axonomy can be desc ibed as ollows: No up o da e axonomy is dealing wi h su oga e-assis ed op imiza ion in he la ge scope o con inuous 2 global op imiza ion [10, 9]. This new axonomy o op imiza ion algo i hms based on he isual idea o mo ing indi iduals ills his gap. I is based on selec ed design aspec s o a con inuous op imiza ion algo i hm. They a e he use o in o ma ion,candida e e alua ion, he ype o indi idual,sea ch space and addi ionally he cha ac e is ics o he manageable p oblems. U ilizing hese ea u es, we de i e a se o comp ehensible algo i hm classes. In gene al, i is bene icial o each use o iden i y i an op imiza ion algo i hm is sui able o hei p oblem be o e applying hem. This app oach suppo s use s in hei selec ion o an adequa e algo i hm. Re e ences [1] Ba z-Beiels ein, T., Lasa czyk, C.W., P euß, M.: Sequen ial pa ame- e op imiza ion. In: E olu iona y Compu a ion, 2005. The 2005 IEEE Cong ess on, ol. 1, pp. 773–780. IEEE (2005) [2] Boussaïd, I., Lepagno , J., Sia y, P.: A su ey on op imiza ion me aheu is- ics. In o ma ion Sciences 237, 82–117 (2013) [3] Eiben, A.E., Smi h, J.E.: In oduc ion o e olu iona y compu ing, ol. 53. Sp inge (2003) [4] Jones, D.R., Schonlau, M., Welch, W.J.: E icien global op imiza ion o expensi e black-box unc ions. Jou nal o Global op imiza ion 13(4), 455– 492 (1998) [5] Michalewicz, Z., Fogel, D.B.: How o sol e i : mode n heu is ics. Sp inge Science & Business Media (2013) [6] Rozenbe g, G., Bck, T., Kok, J.N.: Handbook o na u al compu ing. Sp inge Publishing Company, Inco po a ed (2011) [7] Schwe el, H.P.P.: E olu ion and op imum seeking: he six h gene a ion. John Wiley & Sons, Inc. (1993) [8] Shanno, D.F.: Condi ioning o quasi-new on me hods o unc ion mini- miza ion. Ma hema ics o compu a ion 24(111), 647–656 (1970) [9] Tö n, A., Zilinskas, A.: Global Op imiza ion. Sp inge (1989) [10] Zlochin, M., Bi a a i, M., Meuleau, N., Do igo, M.: Model-based sea ch o combina o ial op imiza ion: A c i ical su ey. Annals o Ope a ions Resea ch 131(1-4), 373–395 (2004) 3 Kon ak /Imp essum Diese Ve ö en lichungen e scheinen im Rahmen de Sch i en eihe "CIplus". Alle Ve ö - en lichungen diese Reihe können un e h ps://cos.bibl. h-koeln.de/home abge u en we den. Die Ve an wo ung ü den Inhal diese Ve ö en lichung lieg beim Au o . Da um de Ve ö en lichung: 02.07.2018 He ausgebe / Edi o ship P o . D . Thomas Ba z-Beiels ein, P o . D . Wol gang Konen, P o . D . Bo is Naujoks, P o . D . Ho s S enzel Ins i u e o Compu e Science, Facul y o Compu e Science and Enginee ing Science, TH Köln, S einmülle allee 1, 51643 Gumme sbach u l: www.ciplus- esea ch.de Sch i lei ung und Ansp echpa ne / Con ac edi o ’s office P o . D . Thomas Ba z-Beiels ein, Ins i u e o Compu e Science, Facul y o Compu e Science and Enginee ing Science, TH Köln, S einmülle allee 1, 51643 Gumme sbach phone: +49 2261 8196 6391 u l: h p://www.spo se en.de eMail: homas.ba z-beiels ein@ h-koeln.de ISSN (online) 2194-2870