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
