An agent-Oriented Hierarchic Strategy for Solving Inverse Problems

In . J. Appl. Ma h. Compu . Sci., 2015, Vol. 25, No. 3, 483–498
DOI: 10.1515/amcs-2015-0036
AN AGENT–ORIENTED HIERARCHIC STRATEGY FOR SOLVING INVERSE
PROBLEMS
MACIEJ SMOŁKAa,∗,ROBERT SCHAEFERa,MACIEJ PASZY ´
NSKIa,DAVID PARDOb,c,d,
JULEN ´
ALVAREZ-ARAMBERRIb,e
aDepa men o Compu e Science
AGH Uni e si y o Science and Technology, Al. Mickiewicza 30, 30-059 K ak´ow, Poland
e-mail: {smolka,schae e ,paszynsk}@agh.edu.pl
bDepa men o Applied Ma hema ics, S a is ics, and Ope a ional Resea ch
Uni e si y o he Basque Coun y (UPV/EHU), Ba io Sa iena S/N, 48940 Leioa (Bizkaia), Spain
e-mail: {dzubiau ,julen.al a ez.a ambe i}@gmail.com
cBasque Cen e o Applied Ma hema ics (BCAM), Alameda de Maza edo 14, 48009 Bilbao, Spain
dIke basque (Basque Founda ion o Sciences), Ma ia Diaz de Ha o 3, 48013 Bilbao, Spain
eLabo a o y o Ma hema ics and Thei Applica ions
Uni e si y o Pau (UPPA), A enue de l’Uni e si ´e BP 576, 64012 Pau cedex, F ance
The pape discusses he complex, agen -o ien ed hie a chic meme ic s a egy (HMS) dedica ed o sol ing in e se pa ame -
ic p oblems. The s a egy goes beyond he idea o wo-phase global op imiza ion algo i hms. The global sea ch pe o med
by a ee o dependen demes is dynamically al e na ed wi h local, s eepes descen sea ches. The s a egy o e s excep-
ionally low compu a ional cos s, mainly because he di ec sol e accu acy (pe o med by he hp-adap i e ini e elemen
me hod) is dynamically adjus ed o each in e se sea ch s ep. The compu a ional cos is u he dec eased by he s a egy
employed o solu ion in e -p ocessing and i ness de e io a ion. The HMS e iciency is compa ed wi h he esul s o a s an-
da d e olu iona y echnique, as well as wi h he mul i-s a s a egy on benchma ks ha exhibi ypical in e se p oblems’
di icul ies. Finally, an HMS applica ion o a eal-li e enginee ing p oblem leading o he iden i ica ion o oil deposi s by
in e ing magne o ellu ic measu emen s is p esen ed. The HMS applicabili y o he in e sion o magne o ellu ic da a is
also ma hema ically e i ied.
Keywo ds: in e se p oblems, hyb id op imiza ion me hods, meme ic algo i hms, mul i-agen sys ems, magne o ellu ic
da a in e sion.
1. In oduc ion
In e se p oblems o m an impo an a ea o con empo a y
esea ch ela ed o undamen al p oblems in science and
enginee ing. Among i s nume ous applica ions one
can ind non-in asi e geophysical explo a ion, umo
cha ac e iza ion, and analysis o unknown ma e ials.
Pa ame ic in e se p oblems a e usually o mula ed
as op imiza ion ones, whe e he objec i e is o minimize
he mis i be ween he simula ed and measu ed o wa d
solu ions. When sol ing such p oblems, one usually
∗Co esponding au ho
aces some signi ican obs acles such as ill-condi ioning,
exis ence o mul iple local minima (mul i-modali y), and
possibly low egula i y o he mis i unc ional. All
o hem signi ican ly educe he use ulness o con ex
op imiza ion me hods (such as g adien -based ones), as
well as simple s ochas ic mechanisms (Mon e Ca lo and
simple e olu iona y schemes) because o
• he lack o gua an ee o inding all solu ions,
•eno mous compu a ional cos .
The main goal o his wo k is o ob ain a global
in e se sol e capable o inding many global and/o local
484
M. Smołka
e al.
solu ions (mis i minima) wi h a sa is ac o y accu acy and
an accep able compu a ional cos . In o de o achie e his
goal, he pape combines se e al di e en ideas: he hi-
e a chic gene ic s a egy (HGS) (see, e.g., Schae e and
Kołodziej, 2003; Wie zba e al., 2003) o dec ease he
cos o he main pa o a global sea ch (which consis s o
inding he basins o a ac ion), clus e -based i ness de-
e io a ion (see, e.g., Beasley e al., 1993; Obuchowicz,
1997; Wolny and Schae e , 2011), meme ic algo i hms
(see, e.g., Ne i e al., 2012) composing a ious echniques
in o a single popula ion-based s ochas ic s a egy in o de
o gain e iciency and lexibili y, and he e olu iona y
mul i-agen sys em (EMAS) (see, e.g., Ce na owicz e al.,
1996), allowing mo e lexible, asynch onous p ocessing
and easy embedding o local con ex sea ches. The wo k
p esen ed in his pape is an ex ension o he hyb id
model in ol ing he global gene ic sea ch phase ollowed
by he local g adien phase, as applied o he in e se
esis i i y logging measu emen simula ions wi h di ec
cu en elec odes (Gajda-Zag´o ska e al., 2015), as well
as o he iden i ica ion o he Young modulus o imp in
nanoli hog aphy (Ba abasz e al., 2014).
The p oposed s a egy de elops dynamically a ee
o dependen popula ions (demes) sea ching wi h a ious
le els o accu acy ha g ow om he oo o he
lea es. Two ypes o indi iduals a e u ilized: passi e
indi iduals, con aining candida e solu ions only, and
ac i e indi iduals, consis ing o compu a ional so wa e
agen s. Bo h ac i e and passi e indi iduals a e ga he ed
in demes go e ned by s uc u al agen s assigned o
he nodes o he popula ion ee. Demes o passi e
indi iduals a e adi ionally e ol ed by using common
selec ion and gene ic ope a o s. Ac i e indi iduals
(agen s) compe e inside a deme one wi h ano he o
pe o m hei ac ions p oducing o sp ing agen s wi h
geno ypes de e mined by adi ional gene ic ope a o s o
by a con ex op imiza ion p ocess. The sea ch accu acy
is ha associa ed o he solu ion o di ec p oblems using
an hp-adap i e ini e elemen me hod (hp-FEM), whe e h
(heigh ) e e s o he elemen size, and p o he polynomial
o de o app oxima ion, which can be adap ed/modi ied
h oughou he compu a ional g id (Demkowicz, 2006).
The low compu a ional cos is ob ained p ima ily
by an economical global sea ch pe o med by he ee
o demes, because he mo e de ailed local sea ches
a e ac i a ed mainly in he p omising egions ound
by he pa en al popula ions. The o al numbe o
indi iduals is signi ican ly lowe han in he case o he
adi ional, single popula ion e olu iona y sea ch. The
main compu a ional cos dec emen is achie ed ia he
common in e se and o wa d e o scaling, i.e., he
ough global sea ch is pe o med wi h a low mis i
accu acy whe eas he accu acy inc eases in he e ined
sea ches pe o med by b anches and lea es. Such a
policy minimizes he numbe o expensi e hp-FEM sol e
calls, which a e necessa y o accu a e mis i e alua ion.
Finally, he agen -o ien ed a chi ec u e based on he
EMAS idea allows economic and lexible in oca ion
o local g adien me hods a leas once o a single
solu ion and only i hey ou pe o m he s ochas ic sea ch.
Mo eo e , he agen -based a chi ec u e acili a es pa allel
e olu ion o deme popula ions.
We ha e e i ied ou s a egy by a se ies o
benchma k p oblems ha mimic he op imiza ion
landscape ob ained in eal-li e in e se p oblems. The i s
phase o benchma k es s leads o es ablishing he se o
he s a egy’s pa ame e s ha assu e i s mos economic
ope a ion. In he second phase, we compa e esul s o ou
p oposed s a egy wi h hose o o he global op imiza ion
me hods execu ed using a compa able budge (compu e
esou ces). In his pape , we compa e he HMS wi h wo
s anda d global op imiza ion me hods, i.e., he simple
e olu iona y algo i hm (SEA) and mul i-s a . We ha e
al eady pe o med a benchma k-based compa ison wi h a
e sion o he HGS (Smołka and Schae e , 2014).
We conclude he pape wi h he applica ion o
ou agen -based sys em o sol e an in e se p oblem
consis ing in iden i ying he esis i i y o he unde g ound
o ma ion by using magne o ellu ic measu emen s. The
magne o ellu ic (MT) me hod is a passi e elec omagne ic
(EM) explo a ion echnique which allows us o de e mine
he esis i i y dis ibu ion in he subsu ace o he a ea
o in e es on scales a ying om a ew me e s o
hund eds o kilome e s. Comme cial applica ions include
hyd oca bon, geo he mal, unde g ound wa e moni o ing,
and, mo e ecen ly, moni o ing CO2seques a ion in
he subsu ace. The me hod does no equi e a i icial
powe sou ces. Ins ead, na u al powe sou ces a e used
o induce he phenomena. These na u al sou ces a e
no hing bu elec ic cu en s wi hin he ionosphe e c ea ed
by de o ma ions o he magne osphe e. The mo i a ion
o he choice o he MT p oblem was he de ec ion o
se e al local minima in an MT in e sion pe o med by
means o a classical g adien me hod ( ´
Al a ez-A ambe i
e al., 2013).
The esul s o all compa a i e es s show a much
highe quali y and numbe o ex emes ound by he
p oposed agen -based sys em han by o he e e ence
me hods. Single popula ion e olu iona y algo i hms
a e able o ind only a single solu ion wi hin he
assumed budge . A mul i-s a me hod, which consis s in
pa allel execu ion o local g adien - ype me hods om a
numbe o andom s a ing poin s, canno in gene al ind
sa is ac o y solu ions, because wi hin he assumed budge
only a small numbe o local p ocesses can be in oked.
The pape concen a es on he algo i hmic aspec s o
he HMS, so we do no discuss implemen a ion- ela ed
issues he e. Some no es on a sample implemen a ion can
be ound in he wo k o Smołka and Schae e (2014) and
we e e he in e es ed eade he e.
An agen -o ien ed hie a chic s a egy o sol ing in e se p oblems
485
2. HMS a chi ec u e
The main idea o he HMS is o p o ide a global
op imiza ion ool especially sui ed o sol ing di icul
in e se p oblems. The conside ed p oblems a e di icul
because o hei inhe en mul i-modali y accompanied
by he non i ial compu a ional cos o di ec p oblem
solu ion, which is necessa y o e alua ing he objec i e
ha is he mis i be ween he obse ed and compu ed
alues o a quan i y o in e es . Ne e heless, in e se
p oblems ha e also some ad an ageous ea u es. Fi s ,
hei heo e ical global minimum alue is well known
(and equal o ze o). Al hough in p ac ice his heo e ical
alue is ne e a ained because o noise, modeling e o s,
e c., we know a leas ha he objec i e unc ion is
bounded om below by ze o and ha i s akes alues
close o his bound. This knowledge can be used, e.g.,
in he cons uc ion o s opping condi ions o s ochas ic
e olu ion. Second, in some impo an cases, he cos o he
di ec p oblem solu ion can be modula ed by an assumed
accu acy o he solu ion: i is he case o hp-FEM di ec
sol e s (Demkowicz e al., 2007).
As a global op imiza ion ool, he HMS ies
o combine he high-le el explo a o y abili y wi h he
accu acy and e iciency o a local op imiza ion me hod.
In con as o wo-phase me hods in which local sea ches
a e execu ed igh a e he comple ion o he global
phase, he HMS ollows he o e all idea o meme ic
algo i hms, i.e., i in e mixes local-op imiza ion-o ien ed
mechanisms in o a global s ochas ic sea ch machine y.
The global pa ollows he mul i-popula ion e olu iona y
app oach in oduced by he HGS (Schae e and Kołodziej,
2003). Namely, he global sea ch is pe o med by
a collec ion o gene ic popula ions. The popula ions
can e ol e in pa allel, bu hey a e no mu ually
independen . The s uc u e o he dependency ela ion
is hie a chical (i.e., ee-like; see Fig. 1) wi h a
es ic ed numbe o le els. The HGS p o ed o ha e
Le el 1
Le el 2
Le el 3
oo deme
b anch demes
lea demes
U1
gene ic spaces
low accu acy
high accu acy
U2
U3
Fig. 1. HGS-like e olu iona y popula ion ee.
conside able explo a o y capabili ies oge he wi h a good
sea ch accu acy, especially wi h loa ing-poin pheno ype
encoding (Wie zba e al., 2003). The HMS na u ally
ies o e ain hese abili ies while going beyond he
HGS in some aspec s. Fi s o all, i adds local
op imiza ion o he se o ope a ions applied o he gene ic
indi iduals. Bu his is pe o med ca e ully in o de
o a oid he p ema u e popula ion con e gence on he
one hand and high cos o unning ins ances o a local
me hod om inapp op ia e poin s on he o he . Namely,
some gene ic indi iduals (bu no necessa ily all o hem)
ecei e an iden i y and some in elligence, hence becoming
independen agen s in a mul i-agen sys em (MAS). The
decision o pe o ming he local sea ch becomes hei
own esponsibili y. Mo eo e , he demes a e managed
by special con olle agen s. The idea o u ning a
passi e gene ic indi idual in o an in elligen agen has
some u he consequences. We ha e o ede ine he
gene ic ope a ions in such a way ha hey can be applied
o agen s. While i is s aigh o wa d o he mu a ion
and he c osso e (al hough in his case a new agen is
ac i a ed), he selec ion canno be pe o med in he simple
gene ic (o e olu iona y) way. Ins ead, we ollow he
lines o he EMAS (Ce na owicz e al., 1996; By ski
e al., 2013), hus pe o ming an ope a ion analogous
o he ou namen selec ion bu ealized as a wo-agen
endez ous.
In he sequel, we shall p esen he s uc u e o he
HMS s a ing wi h a desc ip ion o HMS agen ypes.
2.1. HMS agen ypes. The main HMS agen ypes
along wi h hei in e ela ions a e shown in Fig. 2. The
Mas e Agen (MA) is a global sys em coo dina o .
Deme Agen s (DAs) manage e olu iona y popula ions
a a ious le els o he deme ee. DA specializa ions
di e p ima ily in he ype o popula ion hey can
own. E olu iona y Agen s (EAs) hold simple passi e
collec ions o ch omosomes, whe eas Local Agen s
(LAs) coo dina e g oups o Compu a ional Agen s (CAs).
Any CA, apa om holding an immu able geno ype,
can pe o m one o he a ailable ac ions, such as
local op imiza ion me hod execu ion. The p ima y
esponsibili y o he Objec i e Agen (OA) is objec i e
compu a ion, which ypically in ol es calling an ex e nal
di ec p oblem sol e . In he ollowing, we p o ide
de ailed desc ip ions o HMS agen ypes.
Mas e Agen
Objec i eAgen
cache
DemeAgen
accu acyLe el
E olu iona yAgen
passi ePopula ion
LocalAgen Compu a ionalAgen
geno ype { eadOnly}
li eEne gy
*
1
*
Ex e nalSol e
Fig. 2. HMS agen ypes (UML class diag am).
486
M. Smołka
e al.
Mas e Agen (MA). As a global sys em coo dina o ,
i is s a ed as a i s agen in he HMS MAS. I s
esponsibili ies include pe o ming sys em ini ializa ion
such as he ac i a ion o o he essen ial agen s, i.e., he
Objec i e Agen and a Deme Agen o he deme- ee
oo . A e he ini ializa ion, he Mas e Agen s a s he
global loop o deme coo dina ion and checks i he global
s opping condi ion is sa is ied. The deme coo dina ion
ollows he lines o FIPA Con ac -Ne (FIPA, 2002). I
begins by sending a call o p oposals (CFP) o all ac i e
Deme Agen s. Then, he MA wai s o DA p oposals and
accep s hose ha a e no in con lic . This is shown in
Algo i hm 1. DA p oposals a e in con lic when hei
Algo i hm 1. Mas e Agen (MA) algo i hm.
1: c ea e OA
2: c ea e oo loca ion DA
3: epea
4: send CFP o all ac i e DAs
5: ecei e p oposals om DAs
6: accep all non con lic ing p oposals
7: eques i ness de e io a ion om OA
8: un il global s op condi ion is sa is ied.
co esponding ac i i ies canno be execu ed in pa allel.
Using he e minology o By ski e al. (2013), hey a e
no local. In he cu en HMS ealiza ion, all ac ions a e
local (no e ha , in con as o By ski e al. (2013), we do
no conside he mig a ion), so all DA p oposals can be
accep ed by he MA.
Deme Agen (DA). I is a deme- ee node coo dina o .
Each deme has an associa ed le el o compu a ional
accu acy s o ed as a p ope y o he co esponding Deme
Agen . In ac , he Deme Agen is an abs ac class wi h
wo di e en specializa ions: he E olu iona y Agen and
he Local Agen .
E olu iona y Agen (EA). This is a simple (passi e)
e olu iona y popula ion owne . Pe iodically, a e
ecei ing he pe mission om he Mas e Agen , i
e ol es i s popula ion o a ixed numbe o gene a ions
( his sequence o gene ic epochs is called a me aepoch),
and hen sp ou s a new deme om he cu en bes
indi idual unless he sp ou condi ion is no sa is ied
(see Algo i hm 2). No e ha simila agen s o m he
s uc u e o he globally balanced HGS (Jojczyk and
Schae e , 2009). C ea ing he ini ial popula ion in Line 2
has wo di e en meanings. I an EA con ains he ee
oo deme, hen he ini ial popula ion is sampled using
he uni o m p obabili y dis ibu ion. O he wise, he EA is
i sel sp ou ed using i s pa en ’s bes indi idual as a seed.
In such a case, he ini ial popula ion is sampled using he
Algo i hm 2. E olu iona y Agen (EA) algo i hm.
1: se accu acy le el
2: c ea e ini ial deme popula ion
3: epea
4: send p oposal o MA
5: i MA has accep ed p oposal hen
6: o all epochs in me aepoch do
7: pe o m selec ion
8: pe o m c osso e and mu a ion
9: o all c ea ed indi idual do
10: eques objec i e compu a ion om OA
wi h s o ed accu acy
11: end o
12: end o
13: i bes indi idual sa is ies sp ou condi ion hen
14: sp ou new child DA om bes indi idual
15: end i
16: end i
17: un il local s op condi ion is sa is ied
no mal dis ibu ion cen e ed in he seed indi idual wi h
he s anda d de ia ion depending upon he ee le el.
Local Agen (LA). The Local Agen owns a popula ion
o Compu a ional Agen s and ac s as a local schedule o
hei ac ions. Namely, i ecei es ac ion p oposals om
Compu a ional Agen s, selec s one o hem acco ding
o a p obabili y dis ibu ion, sends a p oposal o he
Mas e Agen and, i he p oposal is accep ed, le s
he selec ed Compu a ional Agen pe o m i s ac ion
(see Algo i hm 3). The Local Agen ’s esponsibili ies
include also some ac ion coo dina ion, such as checking
i a selec ed sp ou ac ion is allowed. C ea ing he
ini ial popula ion is pe o med analogously as in he
case o an E olu iona y Agen , i.e., by sampling using
a p ope p obabili y dis ibu ion (di e en o oo and
non- oo demes). The only di e ence is he ype c ea ed
indi iduals: passi e ch omosomes in he case o an
E olu iona y Agen and ac i e Compu a ional Agen s in
he case o Local Agen s.
Compu a ional Agen (CA). I is an ac i e indi idual
o he HMS gene ic popula ion. I owns an immu able
geno ype consis ing o an encoded domain poin (a
ch omosome) and a le el o compu a ional p ecision. The
p ecision le el mus be consis en wi h he owning Local
Agen ’s le el. The mu able pa o a Compu a ional
Agen ’s s a e includes a nonnega i e meme ic pa ame e
called li e ene gy. I is exchanged du ing he
Compu a ionalAgen ’s ac ion execu ion such ha he o al
ene gy emains cons an wi hin each deme. Only agen s
wi h posi i e li e ene gy a e conside ed ac i e (ali e) and
ake pa in sys em e olu ion. The e exis s a se o ac ions
An agen -o ien ed hie a chic s a egy o sol ing in e se p oblems
487
Algo i hm 3. Local Agen (LA) algo i hm.
1: se accu acy le el
2: c ea e ini ial deme popula ion
3: epea
4: send CFP o all ac i e CAs
5: ecei e ac ion p oposals om CAs and choose one
6: send co esponding p oposal o MA
7: i MA has accep ed he p oposal hen
8: i CA ac ion c ea es new indi idual hen
9: c ea e new CA
10: else i chosen ac ion is SPROUT hen
11: i sp ou ing can be pe o med hen
12: c ea e new child DA
13: end i
14: end i
15: end i
16: un il local s op condi ion is sa is ied
om which an ac i e Compu a ional Agen chooses one
a a ime o pe o m. Which ac ions a e ac ually a ailable
depends on pa ame e s such as li e ene gy, he objec i e
alue, he p ecision le el, and o he s. Finally, he ac ion
is pe o med only i pe mi ed by he owning Local Agen
(see Algo i hm 4).
Algo i hm 4. Compu a ional Agen (CA) algo i hm.
1: se accu acy le el acco ding o LA’s le el
2: eques objec i e compu a ion om OA wi h s o ed
accu acy
3: epea
4: emain empo a ily inac i e
5: un il objec i e alue is ob ained
6: while li e ene gy >0do
7: ecei e CFP om owning LA
8: choose an a ailable ac ion
9: send he co esponding p oposal o LA
10: i ecei ed pe mission om LA hen
11: pe o m chosen ac ion
12: upda e li e ene gy
13: end i
14: end while{CA pe manen ly inac i e}
The e is an ene gy quan um ela ed o each ac ion,
which is spen (du ing GET i can some imes be gained)
by a Compu a ional Agen du ing ac ion execu ion.
Cu en ly, he ollowing ac ions a e conside ed (c . By ski
e al., 2013): GET, MUTATE, CROSSOVER, LOCOPT
and SPROUT. In all es s p epa ed o his pape , we se
all ac ion ene gies o 1and he ini ial CA ene gy o 5.
The GET ac ion is a wo-agen s ochas ic duel du ing
which p ope quan um ene gy mo es om he lose
o he winne . A Compu a ional Agen wi h a lowe
(i.e., close o he global minimum) objec i e alue has
mo e chances o win. MUTATE and CROSSOVER
a e s aigh o wa d coun e pa s o he co esponding
gene ic (o e olu iona y) ope a ions such as, e.g., he
no mal mu a ion and he a i hme ic c osso e . The
SPROUT ac ion is inspi ed by he child b anch sp ou ing
ope a ion, which is undamen alin he HGS (Schae e and
Kołodziej, 2003). In he HMS, i p oduces a new deme
oge he wi h i s Deme Agen and an ini ial popula ion o
Compu a ional Agen s. Ob iously, SPROUT makes no
sense a he lea le el, whe e i can be op ionally eplaced
wi h LOCOPT. LOCOPT is local op imiza ion me hod
execu ion s a ed om he agen ’s decoded ch omosome.
In he cu en ealiza ion, LOCOPT is allowed only a he
lea es.
Ac ion selec ion is de e mined by a gi en p obabili y
dis ibu ion. The p obabili y o LOCOPT can be
compu ed using a o mula like he ollowing:
pLOCOPT =p0+(1−p0)s
1+objec i e,(1)
whe e 0≤p0<1is he gua an eed p obabili y and
s>0is close bu no equal o 1 o allow selec ing
o he ac ions. Thus, he be e he objec i e alue, he
mo e s ongly LOCOPT is p e e ed. O he ac ions
a ailable acco ding o he cu en li e ene gy ecei e equal
emaining p obabili y. The same o mula can also be used
o compu ing SPROUT p obabili y a non-lea le els.
Objec i e Agen (OA). In a eal HMS applica ion
(i.e., in sol ing in e se p oblems), he objec i e alue is
compu ed ex e nally by a specialized di ec sol e . The
esponsibili y o an Objec i e Agen ( ypically, one in
he whole sys em) is o p o ide a p ope sol e ga eway,
i.e., o execu e he sol e p ocess (o se e al pa allel
p ocesses) p ope ly and o ans e he inpu da a o he
sol e and he ou pu back o he HMS. O special in e es
o us is he case o compu ing he objec i e by means o
a di ec hp-FEM sol e when he di ec p oblem solu ion
is Lipschi z con inuous wi h espec o he pa ame e s.
This p ope y is no s aigh o wa d and has o be p o ed
in any pa icula case. In Sec ion 4.4 his is shown o
he magne o ellu ic p oblem (see Rema k 1), which is
ou eal-wo ld es case. Then, we can adap he sol e
accu acy o he assumed accu acy o HMS ee demes;
see Algo i hm 5. Finally, we know he dependency
be ween he sol e accu acy and he compu a ional cos
o he di ec p oblem solu ion ( o de ails, see Ba abasz
e al., 2014; Gajda-Zag´o ska e al., 2015) which in u n
is he main uni componen o he o e all HMS cos .
The e o e, we can op imize he o e allcos by modula ing
he deme accu acy.
Addi ional Objec i e Agen ac i i ies may include
caching sol e esul s, sol e ins ance pooling (in he
case o pa allel execu ion) and scheduling objec i e
compu a ions acco ding o a sophis ica ed op imizing

488
M. Smołka
e al.
Algo i hm 5. Objec i e compu a ion wi h hp-FEM di ec
sol e (see Sec ion 4.4).
1: inpu : ee le el j, pa ame e alue
2: compu e ela i e FEM e o e el
3: while e el <Ra io(j)do
4: execu e 1s ep o hp adap a ion
5: sol e p oblem on new ine and coa se meshes
6: compu enew alueo e el
7: end while
8: e u n objec i e compu ed by means o inal mesh
policy (e.g., a di usion-based one (G ochowski e al.,
2006)).
Qui e a special kind o addi ional OA ac i i y
is he de e io a ion o he objec i e unc ion. The
la e is a p ope objec i e modi ica ion ha leads o
he le eling o cen al egions o a ac ion basins o
al eady ound local and global minima (Beasley e al.,
1993; Obuchowicz, 1997). The idea is o discou age
he e olu iona y indi iduals om explo ing al eady
well- ecognized a eas. In his pape , we adop he
clus e -based i ness de e io a ion echnique desc ibed
by Wolny and Schae e (2011). Namely, a e a eques
om he MA, all ga he ed objec i e da a (in his case,
he poin s a which he objec i e has been compu ed) a
selec ed accu acy le els a e clus e ed (cu en ly, using he
DBSCAN algo i hm (Es e e al., 1996)). A e wa ds, o
each ecognized clus e , we cons uc he ellipsoidal clus-
e ex ension
CE ={x∈RN:(x−x)TΣ−1(x−x)≤1}
de e mined by i s cen e xand a symme ic ma ix
Σ, which in ou case is he clus e unbiased sample
co a iance ma ix (c . Wolny and Schae e , 2011). Then,
each clus e ex ension con ibu es o he de e io a ion by
he ollowing o mula:
(x):= (x)+ maxΨ(x),(2)
whe e Ψis a well-known bump unc ion
Ψ(x)
=⎧
⎨
⎩
exp 1−1
1−(x−x)TΣ−1(x−x) o x∈CE,
0o he wise.
(3)
and max is he maximal objec i e alue o e he clus e .
Ψis an in ini ely smoo h unc ion and i s suppo is
exac ly he conside ed ellipsoid. No e ha , in con as
o he s anda d (c . Wolny and Schae e , 2011), we
do no make use o simple Gaussian unc ions because
hey a e posi i e e e ywhe e, which des oys he desi ed
ze o- alue ea u e o in e se p oblem global minima.
2.2. Popula ion s uc u e. As s a ed be o e, he HMS
gene ic popula ion is decomposed in o dependen demes
o ming a dynamically changing ee o he ixed maximal
dep h m. Gene ic indi iduals, i.e., compu ing agen s,
loca ed a he ee le els close o he oo , pe o m he
chao ic and inaccu a e sea ch. When app oaching he
lea es, he sea ch becomes mo e and mo e ocused and
he accu acy is inc eased (see Fig. 1). The a iabili y
o he sea ch accu acy esul s om he di e si y o he
geno ype encoding p ecision used a di e en ee le els.
The la e depends on he encoding ype. In he case o
bina y encoding (as in he simple gene ic algo i hm), i
can be achie ed by he bina y geno ype leng h a ia ion,
whe eas in he case o eal numbe encoding (as in he
simple e olu iona y algo i hm), i can be ealized by
app op ia e pheno ype scaling. The la e case is used
in he p o o ype implemen a ion o he HMS, so he e
we p esen some de ails. The desc ip ion ollows hose
p esen ed in exis ing pape s (Wie zba e al., 2003; Jojczyk
and Schae e , 2009).
In eal numbe encoding, bo h pheno ypes and
geno ypes a e ec o s om RN. We assume ha he
solu ion domain is a box
D=[a1,b
1]×···×[aN,b
N],
and we ake a sequence o scaling ac o s ηi∈Rsuch
ha η1>η
2> ...η
m−1>η
m=1. Then, he gene ic
uni e sum a he ee le el jis
Uj=0,b1−a1
ηj×···×0,bN−aN
ηj,(4)
and he encoding mapping a he le el jis de ined as
Dx−→ xk−ak
ηjN
k=1
∈Uj.(5)
Mo eo e , we de ine he scaling mapping,
scalei,j :Uix→ ηi
ηj
x∈Uj.
In such gene ic uni e sa, he sea ch a lowe le els is
mo e chao ic because he mu a ion ac s s onge , and
less p ecise because o limi a ions in he eal numbe
ep esen a ion. I is possible o use a ious gene ic
ope a o s in such encoding. Among he mos impo an
ones, we selec he no mal mu a ion
yi=xi+N(0,σmu
j),i=1,...,N,
whe e N(0,σmu
j)is a no mally dis ibu ed andom
a iable wi h s anda d de ia ion σmu
jse sepa a ely o
each le el j, and he a i hme ic c osso e
yi=x1
i+U([0,1])(x2
i−x1
i),i=1,...,N,
An agen -o ien ed hie a chic s a egy o sol ing in e se p oblems
489
whe e U([0,1]) is a andom a iable dis ibu ed uni o mly
o e he in e al [0,1]. Bo h ope a o s a e used
in ou sample implemen a ion. Fu he mo e, we
exploi he classical i ness-p opo ional ( oule e-wheel)
selec ion in passi e popula ions(on E olu iona y Agen s),
addi ionally p ese ing he bes indi idual o each
gene a ion. A newly sp ou ed deme’s popula ion
is sampled acco ding o he N-dimensional Gaussian
dis ibu ion cen e ed a he p ope ly encoded i es
indi idual o he pa en p ocess wi h he diagonal
co a iance ma ix aking alues (σsp ou
j)2on he diagonal.
The sp ou canno be pe o med in popula ion Pa le el j
i he e exis s a popula ion Pa le el j+1such ha
|y−scalei,i+1(y)|<c
j,(6)
whe e yis he bes indi idual in P,yis he a e age
pheno ype o P,andcjis a b anch compa ison cons an .
Finally, i should be men ioned ha u he u iliza ion
o he knowledge ga he ed du ing mul i-le el enhanced
gene ic e olu ion is possible by means o he clus e ing
echnique, in which be e app oxima ion o a ac ion
basins o he local minima can be de eloped, allowing ye
mo e p ecise applica ion o local op imiza ion me hods.
3. Benchma k es s
In o de o p o e HMS abili ies o ind he global
minimum in mul i-modal cases, we pe o med wo
benchma k es s. The es se up in bo h he cases was as
ollows. The HMS ee had h ee le els wi h E olu iona y
Agen s a he oo and middle le els, and Local Agen s
a he lea le el, which seems o be qui e a s anda d
layou o an o e all op imiza ion. The p opo ional
( oule e-wheel) selec ion, he no mal mu a ion and he
a i hme ic c osso e we e chosen as gene ic ope a o s.
Fi s , we an he HMS agains bo h unc ions 30 imes
ill he global minimum was eached wi h he assumed
accu acy o 10−4. The choice o such a ype o es
in luenced he se ing o he HMS s opping condi ions.
Namely, he global s opping condi ion was sa is ied i
a lea app oached he global minimum wi h he gi en
accu acy, whe eas a lea s opping condi ion was sa is ied
i he lea app oached he global minimum o i a ixed
numbe o i s consecu i e me aepochs we e ine ec i e,
i.e., he e was no signi ican a ia ion in he lea ’s
popula ion a e age i ness. To make his s opping
condi ion applicable o ac i e popula ions, we need o
adap he no ion o he gene ic epoch. Namely, in he case
o an LA popula ion, i is simply a CA ac ion execu ion
sequence o he leng h equal o he ini ial popula ion size.
A e he HMS e mina ed, we coun ed i s objec i e calls,
which se he compu a ional budge o wo compa a i e
classical s ochas ic op imiza ion me hods: he simple
e olu iona y algo i hm (SEA) and he mul i-s a . The
compa a i e me hods we e also un 30 imes.
The i s benchma k was he 10-dimensional Ackley
pa h unc ion wi h domain [−5,5]10. I is a s anda d
global op imiza ion es wi h one ha d- o- ind global
ze o- alued minimum su ounded by nume ous o he
local minima wi h g ea e alues. This makes i simila
o a ew impo an in e se p oblem objec i es, such as he
magne o ellu ic p oblem (see Sec ion 4). A special ea u e
o he Ackley unc ion is i s la ness ou side he na ow
a ac ion basin o he global minimum, which makes i
s ill mo e simila o he MT p oblem. The execu ion
pa ame e s o he 10D Ackley unc ion a e summa ized
in Table 1. No e ha he me aepoch leng h pa ame e is
specially adap ed o Local Agen s (see abo e). Simila ly,
he popula ion size in his case is no cons an ; in ou
simula ions i a ied be ween 4and 8.
Table 1. HMS execu ion pa ame e s (Ackley 10D).
Roo Middle Lea
Popula ion (ini ial) 50 10 4
Me aepoch leng h 2 2 2
Encoding scale 4.0 2.0 1.0
Mu a ion a e 0.2 0.05 0.01
C osso e a e 0.5 0.5 0.5
Mu a ion s d. de . 5.0 1.0 0.2
Sp ou s d. de . –2.0 1.0
Sp ou min. dis . –2.0 1.0
The ob ained HMS objec i e call means a e shown
in Table 2. The cos o local me hod applica ion is
included in he lea le el cos . The a e ages om Table 2
Table 2. A e age numbe o objec i e e alua ions (Ack-
ley 10D).
Roo Middle Lea To al
1022.8584.74493.66101.1
allowed us o compu e he p edic ed cos o he SEA and
mul i-s a . Taking he a e age cos o unning he local
me hod om HMS execu ions, we se he s a ing pool
size o mul i-s a o 70. Simila ly, es ima ing he a e age
cos o unning he e olu iona y algo i hm, also on he
basis o HMS uns, we se he ini ial SEA popula ion size
o 100. The SEA gene ic pa ame e s we e se acco ding
o he co esponding HMS pa ame e s om he lea le el,
i.e., he c osso e a e was se o 0.5, he mu a ion a e o
0.01, and he mu a ion s anda d de ia ion o 0.2.Table3
shows he a e age ob ained minimum alues o all he
h ee me hods. Nei he he SEA no he mul i-s a e e
succeeded in eaching he ac ual global minimum, which
he HMS managed o do in e e y un. Full s a is ics a e
shown in a concise way in Fig. 3. Ho izon al ba s indica e
minimum, mean and maximum, espec i ely. The wid h
o he ‘ iolin’ indica es he dis ibu ion o alues.
The second benchma k was he p oduc o h ee
e lec ed and e ically ansla ed Gaussian unc ions o e
490
M. Smołka
e al.
Table 3. A e age alues o compu ed global minimum (Ack-
ley 10D).
HMS Mul i-s a SEA
A e age 5.27 ·10−93.17 2.57
Bes 1.96 ·10−10 1.65 1.3
Fig. 3. Global minima s a is ics (Ackley 10D).
he 4-dimensional box [−5,5]4,
2(x)=
3

i=1 1−exp −(x−mi)TAi(x−mi),(7)
whe e m1=(3,2,1,0),m2=(1,−3,−1,3),m3=
(−2.5,2,2,2) and
A1=⎡
⎢
⎢
⎣
1000
0100
0010
0001
⎤
⎥
⎥
⎦
,
A2=⎡
⎢
⎢
⎣
0.2000
00.10 0
000.10
0000.2
⎤
⎥
⎥
⎦
,
A3=⎡
⎢
⎢
⎣
1.50 0 0
0200
001.50
0001
⎤
⎥
⎥
⎦
.
Benchma k 2has h ee sepa a e ze o- alued global
minima m1,m2and m3wi h no o he local minima.
The di icul y o inding he global minima is g aded.
He e m2has he b oades a ac ion basin, so i is ai ly
easily eachable. Then m1is s eepe , hence mo e di icul
o ind. The main p oblem is eaching m3. Ou side
hei a ac ion basins, one can ind qui e la ge pla eaus,
which can cause se ious ouble o g adien op imiza ion
me hods. Thus, he aim o his es is o check he
compa ed me hods’ abili ies o inding all global minima.
The HMS execu ion pa ame e s o benchma k 2
a e ga he ed in Table 4. The ob ained HMS objec i e call
Table 4. HMS execu ion pa ame e s ( h ee Gaussians).
Roo Middle Lea
Popula ion (ini ial) 50 10 4
Me aepoch leng h 2 2 2
Encoding scale 4.0 2.0 1.0
Mu a ion a e 0.4 0.1 0.01
C osso e a e 0.5 0.5 0.5
Mu a ion s d. de . 10.0 1.0 0.1
Sp ou s d. de . –2.0 1.0
Sp ou min. dis . –2.0 1.0
means a e shown in Table 5. This ime, o make hings
Table 5. A e age numbe o objec i e e alua ions ( h ee Gaus-
sians).
Roo Middle Lea To al Weigh ed
6901.51135.11655.29691.83183.8
s ill mo e simila o MT compu a ions, ins ead o a simple
sum o di e en -le el cos s, we used a weigh ed cos
c=clea +cmiddle
3+c oo
6,(8)
exp essing he ac ha in eal p oblems he lea
compu a ions a e he mos expensi e ones, whe eas he
oo calls a e he cheapes . The denomina o s in (8)
a e aken om MT simula ions, c . see Sec ion 5. As
he compa a i e me hods ope a ed a he op le el o
accu acy, i.e., he lea le el, based on Table 5 we se
he mul i-s a s a e pool size o 50 and he SEA ini ial
popula ion o 70. As in he Ackley 10D case, we se he
SEA gene ic pa ame e s acco dingly o he co esponding
HMS lea -le el pa ame e s. We s opped he SEA igh
a e exceeding 4000 calls. The main esul s o he es
a e shown in Table 6. The HMS success ully ound all
Table 6. S a is ics o inding all global minima ( h ee Gaus-
sians).
HMS Mul i-s a SEA
Fully success ul uns 30/30 16/30 0/30
A g. numbe o mins 32.47 0
h ee minima in e e y execu ion. The mul i-s a ailed in
almos hal o he uns. Mo eo e , in wo uns i ound
only one global minimum. The SEA ne e succeeded,
ob aining an a e age compu ed global minimum o 0.57
and a bes ound solu ion wi h he alue o 0.18.As
he esul s show, he h ee Gaussians benchma k is qui e
An agen -o ien ed hie a chic s a egy o sol ing in e se p oblems
491
a di icul op imiza ion es , despi e i s ela i ely low
dimensionali y. The sou ce o he di icul y is he small
olume o global minima’s a ac ion basins and he
p esence o signi ican pla eaus.
4. Magne o ellu ic in e se p oblem
The sola wind p oduces a adia ion p essu e ha causes a
comp ession on he day-side and a ail on he nigh -side
on o he magne osphe e. Due o his in e ac ion,
hyd omagne ic wa es a e c ea ed. When hose wa es
each he ionosphe e, hey induce an EM ield ha wo ks
as a powe sou ce in magne o ellu ics. Depending upon
he ype o sou ce we a e dealing wi h, he geomagne ic
luc ua ions ange be ween he equencies o 10−3−
105Hz, which allows us o make measu emen s wi h a
esolu ion ha anges om a ew me e s o hund eds o
kilome e s (Vozo , 1972)
The magne o ellu ic (MT) echnique is used o
de e mine a esis i i y map o he Ea h’s subsu ace
by pe o ming elec omagne ic (EM) measu emen s.
The main di e ence o MT wi h espec o o he
geophysical measu emen acquisi ion scena ios (e.g.,
ma ine con olled elec omagne ic measu emen s)
is ha MT uses na u al elec omagne ic adia ion
sou ces gene a ed wi hin he ionosphe e, ins ead o
human powe ed an ennas. Thus, acquisi ion o MT
measu emen s is a he inexpensi e, and can co e
la ge a eas. Applica ions o MT measu emen s include
hyd oca bon (oil and gas) explo a ion and inding sui able
egions o s o age o CO2.
4.1. Fo wa d p oblem. MT measu emen s a e
go e ned by elec omagne ic phenomena, which can
be desc ibed by Maxwell’s equa ions. When he
elec ical ield depends only upon wo spa ial a iables
(x, z), hen wo independen and uncoupled modes a e
de i ed om hese equa ions, namely, ans e se elec-
ic (TE) and ans e se magne ic (TM). The TE mode
in ol es (Ey,H
x,H
z) ield componen s while TM uses
(Hy,E
x,E
z). We ocus on he TE mode and we sol e he
equa ion o Ey.
We decouple Maxwell’s equa ions by
p e-mul iplying bo h sides o Fa aday’s law by μ−1
and applying he cu l ope a o . Then, a e inco po a ing
Ampe e’s law, we subs i u e componen by componen
he esul in o he double cu l ope a o on he elec ic ield
o ob ain he equa ion o he y-componen o he elec ic
ield:
−Δu−k2u= in Ω⊂R2,(9)
whe e Ωis a simply connec ed bounded domain wi h a
Lipschi z bounda y and u(x, z)=Ey(x, z),(x, z)∈Ω.
σ,(σ>σ
0>0in Ω) is he elec ical conduc i i y ield,
k2=ω2μ −jμωσ,whe eω=0is he wa e equency,
, μ ∈R,,μ > 0s and o he pe mi i i y and
pe meabili y o he medium conside ed. =−jωμJimp
y,
whe e Jimp
yis a p esc ibed, imp essed elec ic cu en
densi y adia ing in he y-di ec ion.
To ob ain he co esponding a ia ional o mula ion,
we p e-mul iply Eqn. (9) by a es unc ion ∈
H1
0(Ω; C). A e in eg a ing by pa s and inco po a ing
he Di ichle bounda y condi ions o e ΓD=∂Ω, he
ollowing abs ac a ia ional o mula ion (sui able o
ini e elemen compu a ions) is ob ained:
Find u(σ)∈H1
0(Ω; C)such ha
b(σ;u(σ), )=F( ),∀ ∈H1
0(Ω; C),(10)
wi h
b(σ;u, )=Ω
∇ ∇u−Ω
k2 u (11)
F( )=Ω
, (12)
whe e now we assume ha σ∈L∞(Ω) and Jimp
y∈
L2(Ω; C). The exac solu ion u(σ)=Ey o he p oblem
(10) is called he p imal o wa d solu ion.
Le us de ine now he unc ionals Li:H1
0(Ω; C)→
Cassocia ed wi h he ecei ing an ennas occupying Ωi
domains, espec i ely, i=1,...,M,
Li( )= 1
meas(Ωi)Ωi
. (13)
Now, we a e able o de ine he se o dual o wa d
p oblems,
Find G(σ)∈H1
0(Ω; C)such ha
b(σ; ,G(σ)) = Li( ),∀ ∈H1
0(Ω; C),(14)
o each ecei ing an enna, i=1,...,M.
4.2. hp-FEM app oxima ion. Using an hp-FEM
ini e dimensional in e nal app oxima ion Vhp ⊂
H1
0(Ω; C)(see Demkowicz, 2006), we ob ain he disc e e
e sions o bo h p imal and dual o wa d p oblems (10),
(14)
Find uh,p(σ)∈Vhp such ha
b(σ;uh,p(σ), )=F( ),∀ ∈Vhp,(15)
Find Gi
h,p(σ)∈Vhp such ha
b(σ; ,Gi
h,p(σ)) = Li( ),∀ ∈Vhp,(16)
o each ecei ing an enna, i=1,...,M.
To con ol he disc e iza ion e o by pe o ming
g id e inemen s, we use he wo-dimensional (2D)
hp-adap i e algo i hm desc ibed by Demkowicz (2006).
I inco po a es wo basic componen s:
498
M. Smołka
e al.
ions), adap i e ini e-elemen and discon inuous Pe o –Gale kin me h-
ods, mul ig id sol e s, image es o a ion algo i hms, and mul iphysics
and in e se p oblems.
Julen ´
Al a ez-A ambe i comple ed his deg ee
in physics a he Uni e si y o he Basque Coun-
y in 2007. A e ha , he s udied o an M.Sc. in
quan i a i e inance and an M.Sc. in ma hema -
ical modeling, s a is ics and compu a ion a he
Uni e si y o he Basque Coun y. Since 2011 he
has been a Ph.D. s uden wi hin he Depa men
o Applied Ma hema ics, S a is ics and Ope a-
ional Resea ch a he Uni e si y o he Basque
Coun y unde he supe ision o Da id Pa do
and wi hin he Team P ojec MAGIQUE-3D a he Uni e si y o Pau un-
de he supe ision o H´el`ene Ba ucq. He cu en ly is in he las yea
o his Ph.D. wo king a he Basque Cen e o Applied Ma hema ics
(BCAM). His Ph.D. is expec ed o be inished in 2015. His esea ch
in e es include e icien implemen a ion o nume ical schemes, me h-
ods, and ools. In pa icula , he is ocused on sol ing di ec and in e se
p oblems a ising in applica ions o he magne o ellu ic echnique, which
is used o e ie e in o ma ion abou he esis i i y dis ibu ion o he
Ea h’s subsu ace.
Recei ed: 5 Sep embe 2014
Re ised: 8 No embe 2014