//img.uscri.be/pth/2d363228d97caa859258d11b3a37e9ab6495ad3b
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Evolutionary computation in stochastic environments [Elektronische Ressource] / von Christian Schmidt

148 pages
Christian SchmidtEvolutionary Computation in Stochastic Environments Evolutionary Computation in Stochastic Environments von Christian SchmidtDissertation, genehmigt von der Fakultät für Wirtschaftswissenschaften der Universität Fridericiana zu Karlsruhe, 2006Referenten: Prof. Dr. H. Schmeck . K.-H. Waldmann Prof. S. E. Chick, Ph.D.ImpressumUniversitätsverlag Karlsruhec/o UniversitätsbibliothekStraße am Forum 2D-76131 Karlsruhewww.uvka.deDieses Werk ist unter folgender Creative Commons-Lizenz lizenziert: http://creativecommons.org/licenses/by-nc-nd/2.0/de/Universitätsverlag Karlsruhe 2007 Print on DemandISBN: 978-3-86644-128-6meiner FrauDanksagungDie vorliegende Arbeit entstand w¨ahrend meiner T¨atigkeit als wissenschaft-licher Mitarbeiter des Instituts AIFB der Universit¨at Karlsruhe (TH) imRahmendesKooperationsprojektes“SupplyChainPlanning”mitderFirmaLOCOM Consulting GmbH, Karlsruhe.Mein Dank gilt meinem Betreuer Professor Schmeck, der mir das Ver-trauen, die Freir¨aume und die organisatorischen und finanziellen Rahmenbe-dingungen gab, mich in meinem Forschungsthema so zu entfalten, dass icheine mich erfullende¨ und faszinierende Promotion anfertigen konnte.Weiterhin danke ich dem Grunder¨ der Firma LOCOM, Volker Klohr,dass er den Kontakt zum AIFB seit vielen Jahren durch Vortr¨age, Seminareund Diplomarbeiten pflegt und sich im Rahmen der Kooperation zur Fi-nanzierung meiner Promotionsstelle bereit erkl¨arte.
Voir plus Voir moins

Christian Schmidt

Evolutionary Computation in Stochastic Environments

Evolutionary Computation

in Stochastic Environments

von

Christian Schmidt

Dissertation, genehmigt von der Fakultät für Wirtschaftswissenschaften der

Universität Fridericiana zu Karlsruhe, 2006

Referenten: . H. SchmeckProf. Dr

Impressum

aldmann. K.-H. WProf. Dr

Prof. S. E. Chick, Ph.D.

Universitätsverlag Karlsruhe

c/o Universitätsbibliothek

Straße am Forum 2

D-76131 Karlsruhe

.uvka.dewww

erk ist unter folgender Creative Commons-Lizenz Dieses W

lizenziert: http://creativecommons.org/licenses/by-nc-nd/2.0/de/

Universitätsverlag Karlsruhe 2007

Print on Demand

ISBN:

978-3-86644-128-6

meiner

aurF

Danksagung

DievorliegendeArbeitentstandw¨ahrendmeinerT¨atigkeitalswissenschaft-
licherMitarbeiterdesInstitutsAIFBderUniversit¨atKarlsruhe(TH)im
RahmendesKooperationsprojektes“SupplyChainPlanning”mitderFirma
LOCOMConsultingGmbH,Karlsruhe.
MeinDankgiltmeinemBetreuerProfessorSchmeck,dermirdasVer-
trauen,dieFreir¨aumeunddieorganisatorischenundfinanziellenRahmenbe-
dingungengab,michinmeinemForschungsthemasozuentfalten,dassich
einemicherf¨ullendeundfaszinierendePromotionanfertigenkonnte.
WeiterhindankeichdemGr¨underderFirmaLOCOM,VolkerKlohr,
dasserdenKontaktzumAIFBseitvielenJahrendurchVortr¨age,Seminare
undDiplomarbeitenpflegtundsichimRahmenderKooperationzurFi-
nanzierungmeinerPromotionsstellebereiterkl¨arte.IchhabegroßeAchtung
vorderBereitschaftsichalskleinesmittelst¨andischesUnternehmeninder
ForschungindiesemUmfangzuengagieren.Umsomehrfreueichmich,
dassLOCOMdieKooperationalseinengroßenErfolgbetrachtet.Auchf¨ur
michwardieErfahrung,OptimierungsproblemeinderPraxiszul¨osen,zu-
gleichlehrreichundinspirierend.Sehrwichtigwarauchdiemireinger¨aumte
Zeit,ummehralsnureine“Freizeit”-Promotionanzufertigenundvorallen
DingendieAnteilnahmeundAnerkennung,dieichdurchVolkerKlohrund
meineKollegen(“wirsindDoktor”)erfahrendurfte.
GanzbesondersdankeichJ¨urgenBrankef¨urdieintensiveBegleitung
beiderPromotion,dievielenangeregtenDiskussionenunddiegemeinsamen
Publikationen.ErverstandesstetsmeinenkreativenAusschweifungenden
n¨otigenwissenschaftlichenUnterbauzuverpassenunddenBlickf¨urdasZiel
zubewahren.Aberamallermeistendankeichihmdaf¨ur,michmitdem

iii

“Forscher-Virus”lebensl¨anglichinfiziertzuhaben.
Abig“Dankesch¨on”toSteveChickfortheintensiveandrefreshingre-
searchworkwehavedonetogether,forrealtimeemailcorrespondenceat
nightandespeciallyforsurprisinginsightsintoBayesianstatistics.Thanks
forservingasareferentofmythesis.
MeinenKollegenanderUnidankeichnichtnurf¨urdasNicht-verdursten-
lassenmeinerPflanzen,sondernauchf¨urdieBereitschaft,meineLeidenschaft
f¨urt¨urkischesEssenundAbneigunggegenMensaessenzuakzeptieren.Ich
habedieAtmosph¨areamInstitutunddasZusammenseinimmeraußeror-
dentlichgenossen.
IchdankemeinenEltern,dasssiedieGeduldfu¨rmeinelangeAusbildung
aufgebrachthaben,dasssiemirdasGef¨uhlgeben,aufmichstolzzusein,mich
best¨arkthabenindemGedankenzupromovierenunddasssiedieElternsind,
d.inssiedieMeingr¨oßterDankgiltderFrau,dieichliebeundderichdieseArbeit
gewidmethabe.SiehatmichinderstressigenPhasederArbeitphysisch
undpsychischamLebengehalten,miralldie“Trivialit¨aten”,diedasLeben
bereith¨alt,abgenommenunddabeigleichzeitigVerst¨andnisundR¨ucksicht
.thebracaufg

Karlsruhe,imFebruar2007

hmidtScChristian

Contents

Danksagung

1Introduction
1.1Scope...............................
1.2RelatedApproaches........................
1.3Motivation.............................
1.4Structure.............................

2SelectingaSelectionProcedure
2.1Overview..............................
2.2TheProcedures..........................
2.2.1EvidenceforCorrectSelection..............
2.2.2IndifferenceZone(IZ)..................
2.2.3ValueofInformationProcedure(VIP).........
2.2.4OCBAProcedures....................
2.2.5Optimalallocation....................
2.2.6ComputationalIssues...................
2.2.7SummaryofTestedProcedures.............
2.3EvaluationCriteria........................
2.4TestBedStructure........................
2.5EmpiricalResults.........................
2.6Discussion.............................
2.7FutureWork............................
2.7.1RemovingapproximationsinOCBA..........
2.7.2ImprovingStoppingRulesforBayesianProcedures..

vii

iii

12359

1111141523262932323536374061636364

3

4

2.7.3NonnormalDistributions.................65
2.7.4Non-IndependentSimulations..............65

IntegratingRankingintoEA67
3.1RelatedWork...........................70
3.2StatisticalRanking........................72
3.3ReplacementOperators......................75
3.3.1Comma-andPlus-Replacement.............75
3.3.2CompleteReplacementandElitism...........76
3.4SelectionOperators........................77
3.4.1RandomSelection.....................78
3.4.2TournamentSelection...................78
3.4.3StochasticTournamentSelection............80
3.4.4LinearRanking......................81
3.4.5ExponentialRanking...................81
3.4.6FurtherSelectionOperators...............82
3.4.7StochasticUniversalSampling..............82
3.5RankingProcedureforEA....................83
3.6EmpiricalEvaluation.......................86
3.7ErrorProbability.........................89
3.8Conclusion.............................94
3.9FutureWork............................94

UsingNoise97
4.1Introduction............................97
4.1.1StochasticTournamentSelection............98
4.1.2BasicNotations......................98
4.2EffectofNoise...........................100
4.2.1StandardApproach....................100
4.2.2ASimpleCorrection...................102
4.2.3NoiseAdjustedTournamentSelection..........104
4.2.4SequentialSampling...................107
4.3Results...............................108

4.3.1Samplesizecomparisons...........
4.3.2Dependencyonselectionpressureparameter
4.3.3ApplicationtoGenerational-EA.......
4.4ConclusionandFutureWork.............

5SummaryandOutlook

yaphgrioBibl

....

....

....

....

....

108.109.110.115.

171

211

1erChapt

Introduction

EvolutionaryAlgorithms(EA)areiterativeoptimizationheuristics,which
areinspiredbynaturalevolution.Theyhaveproventobeverysuccessfulin
manydifferentapplicationareasincludinglogistics,telecommunicationand
productionplanning.Oneoftheirparticularadvantagesisthewideapplica-
bility,astheydonotimposestrongrestrictionslikecontinuityorconvexity
onthemodelusedforoptimization.Normally,EAareappliedtodetermin-
isticproblems,i.e.problemswithallparametersandoutputsknownexactly.
Inreality,decisionmakersareoftenconfrontedwithproblemswherethisis
notthecase.Uncertaintiesmightarise,iftheproblemcontainsparameters
thatareoutcomesoffuturedevelopmentsandthereforeunpredictable,e.g.
weatherorcustomerdemand.Furtheruncertaintiesarisefromparametersor
outputsthatmightbedeterminedexactly,butatcostsexceedingthepossible
gaininvalue.
Inpractice,theseuncertainparametersareoftenreplacedwiththeirex-
pectedvaluesandtheproblemissolvedasadeterministicproblem.Ifthe
unknownparameteriscritical,thenthesolutionmightbeverysensitiveto
deviationsoftheuncertainparameterfromitsexpectedvalue,andtherefore
thesolutionmighthaveabadvaluewhenimplemented.
Problemswithuncertainparameterscanbemodeledasstochasticprob-
lems.Theuncertainparametersarereplacedbystochasticvariableswith
distributionsrepresentingthedecisionmaker’sbeliefinthepossiblerealiza-

1

epSco1.1

1.Introduction

tions.Thesolutionforthestochasticproblemwillbeoptimizedforhaving
thebestexpectedvalueorutilityoveralluncertainparameters.
Theapplicationofoptimizationproceduresdesignedfordeterministic
problemstostochasticproblemsisnotstraightforward,because,ingeneral,
thevalueofasolutioncannotbedeterminedexactly.Itcanonlybees-
timatedbyrepeatedevaluationsofdifferentscenarios,whereascenarioin
thiscontextmeansapossiblerealizationoftheuncertainparameters.For
complexproblemsthisevaluationisoftendonebysimulatingthebehavior
ofasolutionforthegivenscenario.Simulationisaverypowerfultool,asit
allowstomodelcomplexsystemsinanaturalandrealisticway.
AdaptingEAforstochasticproblemsisonepromisingpossibilitytocom-
bineoptimizationandstochasticsimulationforsolvingcomplexandflexible
modelsofrealworldproblemswithcombinatoriallylargesearchspaces.Two
specialtiesofEAfurtherincreasetheeleganceofthiscombination:Firstly,
EAcanoptimizemultiplecriteriainonerun,sodecisionmakersarenot
forcedtogiveana-prioriweightingofconcurringmeasuresofperformance
liketimeandcost.Secondly,theevaluationofsolutionscanbedistributed
easilyondifferentnodesofacomputernetworkwithmodestrequirements
oncommunicationamongthenodes,whichallowstheuseofstandardPC
componentstoimprovethespeedoftheoptimizationprocess.
InthisthesisitisshownhowtodesignEAforsolvingstochasticopti-
mizationproblemsbycombiningfeaturesofstatisticalrankingandselection
procedureswithfeaturesofstochasticoptimizationprocedures.

11.epSco

Thegeneralsettingofthisthesisistofindtheconfiguration

∗x=argxma∈XxEω[f(x,ω)],(1.1)
wherexdenotesaconfiguration(representedbyavectorofinputvariables)
fromthesearchspaceX,ωarandomscenario(representedbyavectorofen-
vironmentvariables)andftheperformancemeasureofagivenconfiguration

2

1.Introduction

1.2RelatedApproaches

inacertainscenario.Theobjectiveistofindtheconfigurationwiththebest
expectedperformanceoverallscenarios.Invariouscontextsconfigurations
arecalledsettings,designs,systemsorsolutions.Thismodelisequivalentto
theformulationof“SimulationOptimization”usedby[Fu2002].
Thegivenformulationindicatesthatthefocusisonfindingthebest
configurationx∗ratherthantheexactvalueoftheobjectivefunction,which
conformstotheneedsofpractitioners.Forthesearchspaceitisassumed
thatconfigurationscanbegeneratedeasilyasopposedtofeasibilityproblems,
whereconsiderableeffortgoesintofindingvalidconfigurations.Theobjective
mustbeestimatablebyrepeatedevaluationsoftheperformancemeasurefor
differentscenarios,i.e.thesampleaverageisaconsistentestimatorforthe
qualityofaconfiguration.Iftheperformanceofcompetingconfigurations
canbedistinguishedeasilybyfewevaluations,theproblemcanbesolvedas
aquasi-deterministicproblemandtheapproachpresentedhereprovidesno
enefit.blionaadditAlthoughnoproofsforconvergenceofEAonstochasticproblems,ex-
ceptforfewspecialcases,areknownyet,manycommercialsoftwarepack-
agesforsimulationmakeuseofEAandrelatedapproachestogenerateand
selectgoodsolutions.ForsimulationoptimizationtheEA’sabilitytoper-
form“black-box”optimization,i.e.optimizationwithfewassumptionson
theproblemstructure,isadvantageous.

1.2RelatedApproaches
Themodelusedintheformulationofthestochasticoptimizationproblem
aboveisverygeneral.TheapproachestosolveEquation1.1differinthe
importancegiventocertainaspectsoftheproblemandintheassumptions
madeonthestructureoftheperformancemeasureandthesearchspace.

StatisticalDecisionTheoryStatisticaldecisiontheorydevelopedby
[Wald1950]isthebasisformanyrankingandselectionprocedures.They
areintroducedinmoredetailinChapter2.Foragivensetofalternative
systemsaprobabilityofcorrectselectionisguaranteedapproximatelyoron

3

1.2RelatedApproaches

1.Introduction

average.Theseapproachesaresuitable,whenthenumberofalternatives
issmallandanevaluationoftheperformanceisexpensive.Ourapproach
combinesEAwithrankingandselectionproceduresinordertoallowsearch
spacesofcombinatorialsizeinsteadofafewalternatives.

MarkovDecisionProcessesAnotherapproachconsidersdynamicpro-
grammingandMarkovdecisionprocesses(see[KallandWallace1994]foran
introduction).Here,onesearchesforoptimalactionstoexecuteatdiscrete
pointsintime.Theactionsgeneraterandomoutcomeandtransformthecur-
rentstatetothenextstageprobabilistically.Thenumberofactions,states
andstagesneedstobelow,asthegeneralapproachistoformabackward
recursiontoidentifyoptimalactionsforeachstate.

StochasticProgrammingIntheoperationsresearch(OR)community
typicallyproblemsaresolvedbyStochasticProgramming(see[Birgeand
Louveaux1997]).Themodelsusedaregenerallyrestrictedtolinearobjective
functionsandconstraints,butnonethelessmanyreal-worldproblemsaretoo
complextobesolved.Forstochasticoptimizationproblemstheoptimality
ofasolutioncannotbeguaranteedanymoreasopposedtodeterministic
ones,butonlyaprobabilitythatthesolutionisneartheoptimalsolution.
Thenumberofscenarios(realizationsoftherandomparameters)isusually
i.a-priorfixedStochasticProgrammingasintroducedby[BirgeandLouveaux1997]
isthebasisformanyalgorithmsinclassicalOR.Thegeneralformulation
isgivenbytwonestedlinearprograms,wherethesecondstageproblems
aresolvedconditionalonagivenscenarioandlinkedtothefirststageby
theexpectedvalue,aconvex,non-linearfunctionthatcannotbecalculated
.lyexactTheSampleAverageApproximation(SAA)by[Kleywegt,Shapiro,and
deMello2001]estimatestheexpectedvalueofthesecond-stageproblemsby
approximatingitwithafixednumberNofscenariosandsolvingtheresulting
problemwithBenders’Decomposition([Benders1962]).
FortheSAAtoachievean-optimalsolutionwithprobabilityatleast

4

1.Introduction

natiotivMo1.3

1−α,thenumberofscenariosmustbeN≥σ22log|αY|withσ2beingthe
problemspecificvarianceand|Y|theproblemsize.Thatmeansthedeviation
decreaseswithO(N−0.5)orinotherwords:todoubletheaccuracythe
numberofscenariosmustbequadrupled.

1.3Motivation

InthissectionwewillmotivatewhywebelievethatEAarewellsuited
forsolvinglargescalestochasticoptimizationproblemsandwhichresearch
resultsmightpositivelyinfluencetheefficiencyofEAontheseproblems.
Fortheproblemsemphasizedinthisthesis,itisassumedthattheevalua-
tionofaconfigurationorsolutionisexpensiveintermsoftimeandcost.So
tosolveproblemswithlargesearchspacesitisindispensablethatthenum-
berofscenariosrequiredformeasuringasolution’sperformanceisreducedas
muchaspossiblewithoutdeterioratingtheoptimizationprocedure’smech-
anisms.Usingtoofewscenarioswouldresultinanon-effectiveprocedure
whiletoomanywouldleadtoaninefficientprocedure.
Severalideasforanefficientallocationofthenumberofnecessarysce-
nariosorsamplesareknownfromotherareasofresearch.Combiningthese
approachesgivesreasontohopethatthenumberofscenariosneededfor
optimizationcanbereducedsignificantlycomparedtotheusualstrategy,
wherethenumberofsamplesisfixeda-priori,basedonthevarianceofthe
meanestimator.Thefollowingenumerationsketchesthesesideasinshort.

1.OrdinalOptimization
[Ho,Sreenivas,andVakili1992]notedthatitiseasiertocompare
solutionsthantoestimatetheirperformanceprecisely.Actuallythe
probabilitythatthemeansoftworandomvariablesXandYdifferis
P(X¯n<Y¯n)∈O(e−n),i.e.itconvergesexponentially,whilethemean
X¯n∈O(n−0.5)convergespolynomiallyonly.
Thereforeoptimizationproceduresbasedonthecomparisonofconfig-
urations(ordinaloptimization)ratherthanthevalueoftheobjective
function(cardinaloptimization)shouldusesamplesmoreefficiently.

5

natiotivMo1.3

1.Introduction

2.AdaptiveAllocation
[Rinott1978]developedatwo-stageselectionprocedurethatallocates
moresamplestosystemswithhigheruncertaintyinsteadofsampling
allsystemsequally.Thisapproachcandrasticallyreducethenumber
ofrequiredsamplestoachieveagivenlevelofconfidenceaboutthe
selectionofthebestoutofseveralsystems.Furtherimprovementswere
madelateronbyallocatingmoresamplesofagivenbudgetofoverall
samplestoconfigurationsthathaveahigherprobabilityofbeingthe
.tesbTheefficiencyofsamplesisincreasedbyallocatingthemadaptivelyto
moreuncertainandmoreimportantconfigurations.

AnalysisialtSequen3.[Wald1947]developedstatisticalteststhatsequentiallydecide,based
ontheobservationssofar,iffurthersamplesneedtobetakeninorder
toselectahypothesiswithagivenlevelofconfidence.Thereforethe
numberofsamplesisnotpredetermined,butdependentontheobser-
vations.Thesequentialtestgenerallyachievesthesameaccuracyasa
testhavingafixednumberofsamples,butusingonaverageonlyhalf
thenumberofsamples.
Inprincipal,allowingforavariablenumberofsamplestoselectthe
bestsystemincreasestheefficiencyonaverage.

4.BayesianApproach([ChickandInoue2001b])
Traditionalselectionproceduresensureaprobabilityofcorrectselec-
tionwithinanindifferencezone.Toachievethis,samplesneedtobe
allocatedamongthealternativesasiftheleastfavorablesituationis
encountered,i.e.allinferiorsystemsdifferexactlybytheindifference
zonefromthebestsystem.Inpracticeaselectionprocedureseldom
encountersthissituation.AprocedurebasedontheBayesianapproach
wouldallocatesamplesforthemostprobablesituation(withrespect
tosomepriordistribution)andshouldthereforebemoreeffective.The
drawbackisthattheprocedurecannotguaranteeaprobabilityofcor-

6

1.Introduction

natiotivMo1.3

rectselection.Ontheotherhand,theBayesianapproachallowsto
integratepriorinformationintotheprocedure,whicheventuallymight
improveefficiency.

5.Usingnoise
Stochasticoptimizationalgorithmsdeliberatelyintroducenoiseintothe
searchprocess,whichallowstoescapefromlocaloptima.Instochas-
ticenvironmentstheobjectivefunctionisdisturbedbynoise.Sothere
shouldbeachancetousethenoisefromtheproblemtoreplacesomeof
thenoiseintroducedbytheprocedure,thereforereducingtheneedfor
noise-reductionbysampling.Additionally,[FitzpatrickandGrefen-
stette1988]observedthatmoderatenoisedoesnothurttheperfor-
manceofanEAsignificantly,makingEArobustagainstnoisetoa
e.edegrncertai

6.VarianceReductionTechniques
Techniquestoincreasetheaccuracyofestimation,reducetheestima-
tor’svariancebyintroducingcorrelationbetweenthesamplesofasys-
tem.Thisisachievedbyusingvariancereductiontechniqueslikequasi-
randomnumbers(seee.g.[Niederreiter1992])orantitheticrandom
variables.Theincreaseinaccuracystronglydependsonthestructure
oftheperformancecriteria.
Ingeneral,whencomparingestimationsofindependentsystems’per-
formances,usingcommonrandomnumberspositivelycorrelatesthe
estimationsandthereforeallowsforanincreasedcomparabilitywith
thesamenumberofsamples.
Bothapproacheshavethenecessitytomanipulatethesourceofran-
domnessintheperformanceestimation,ingeneraltherandomnumber
.torgenera

Exceptforthelast,theaboveapproachescannotbecombinedwithtra-
ditionaloptimizationsprocedureslikeStochasticProgramming,becausethey
arebasedontheobjectivefunctionratherthancomparisonofconfigurations,

7

natiotivMo1.3

1.Introduction

theydeterminetheperformanceonana-priorifixednumberofsamplesand
theyaredeterministicoptimizationprocedures.
WhereaseachoftheseideascanbecombinedwithEA:IngeneralEA
arerank-based,i.e.theycompareconfigurationsonly,sotheybelongtothe
classofordinaloptimizationproceduresleadingtoanimprovedconvergence
behaviorovercardinaloptimizationregardingthenumberofsamples.Fur-
thermorethisallowsforadaptiveandsequentialselectionproceduresthat
canbeusedwithinEA.
AsEAcannotgiveaperformanceguaranteeforthesolutionfoundany-
way,theusedselectionproceduresdonotneedtoguaranteealevelofcon-
fidence,either.ThereforeEAarenotaffectedbythisBayesianprocedures’
disadvantage,butbenefitfromtheirincreasedefficiency.Therepeateduse
ofselectionprocedureswithintherunofanEAgivestheopportunityto
acquireinformationthatcanbeusedaspriorinformationfortheBayesian
cedures.proEAarestochasticoptimizationproceduresthatintroducerandomnessat
severalstages.Besidestheirrobustnessagainstmoderatenoisetheygive
thepossibilitytouseatleastsomeoftherandomnessoriginatingfromthe
performanceestimationofconfigurationstoreplacethedesiredrandomness.
Alloftheideas–includingvariancereductiontechniques–canbeused
simultaneouslyinEA,thereforeEAshouldhavethepotentialtosolvereal-
worldstochasticoptimizationproblems.
ThisthesisdevelopsthetoolsforapplyingEAinstochasticenvironments
byderivingproceduresthatincorporatemostoftheideasgivenabove.The
achievementsdonotonlyadvanceEA,butalsostatisticalrankingandse-
lectionandotherordinaloptimizationprocedureslikesimulatedannealing.
Themethodspresentedimprovetheexistingonesbyordersofmagnitude.
Allmethodsareconstructedtodeliveragivenaccuracywithlesseffort
thantheexistingones.Thequestiononhowmucheffort–intermsofnumber
ofsamples–shouldbespenttoincreasetheaccuracywithinasingleiteration
ofEA(ageneration)versusthenumberofiterationsexecutedoverall,remains
stillopen.NeverthelessmostexistingchoicesofaccuracywithinEAon
stochasticoptimizationproblemscanbeachievedmoreefficientlywiththe

8

1.Introduction

St1.4ructure

methodspresentedinthisthesis.
Improvementsnotconsideredherearevariancereductiontechniques.Us-
ingcommonrandomnumbersfortheperformanceestimationwithinEAwill
improvetheefficiencyfurther,whilequasi-randomnumbersshouldnotbe
usedastheyleadtoanunderestimationofthevarianceandthereforedete-
rioratethemethodspresentedhere.

ructureSt41.

Thisthesisisstructuredasfollows.Forordinaloptimizationprocedures
comparisonofpotentialsolutionsisanelementaryoperation.Statistical
selectionproceduresprovideefficientcomparisonmechanisms.Anoverview
ofexistingproceduresforstatisticalselectionisgiveninChapter2.The
proceduresareexaminedinacomprehensivestudyandideas2-4fromabove
areintegrated,improvingtheperformanceofthebestknownproceduresso
far.Chapter3showshowoneofthemostefficientproceduresforstatistical
selectioncanbeintegratedintodifferentvariantsofEA,combiningstatisti-
calrankingandselectionwithordinaloptimization.Allpopularrank-based
selectionandreplacementoperatorsareaddressedtoefficientlyperformop-
timizationonstochasticproblems.Additionally,theoreticalconditionsfor
theoptimalchoiceofstoppingparametersarederived.
InChapter4,noiseoriginatingfromthestochasticproblemisusedto
partlyreplacetherandomizationthatEAandSimulatedAnnealingusually
introduceintothesearchprocess.Forthat,theappliedselectionprobabilities
aredeliberatelymodified,resultinginhigheraccuracyforagivennumberof
samplesorlesssamplesforagivenaccuracy.Thesavingsinthenumberof
samplesarequantifiedfordifferentparametersettings.
Thethesisconcludeswithasummaryofthemostimportantresultsand
pointsoutpromisingareasoffuturework.

9

1.4

ructureSt

10

1.

troIn

ionuctd

2erChapt

SelectingaSelectionProcedure

Selectionproceduresareusedinavarietyofapplicationstoselectthebest
ofafinitesetofalternatives.‘Best’isdefinedwithrespecttothelargest
mean,butthemeanisinferredwithstatisticalsampling,asinsimulation
optimization.Thereisawidevarietyofprocedures,whichgivesrisetothe
questionofwhichselectionproceduretoselect.Themaincontributionof
thischapteristoidentifythemosteffectiveselectionprocedureswhensam-
plesareindependentandnormallydistributed.Wealso(a)summarizethe
mainstructuralapproachestoderivingselectionprocedures,(b)derivenew
procedures,(c)formalizenewstoppingrulesforthem,(d)identifystrengths
andweaknessesoftheprocedures,and(e)presentaninnovativeempirical
testbedwiththemostextensivenumericalcomparisonofselectionproce-
durestodate.Themostefficientandeasiesttocontrolproceduresallocate
sampleswithaBayesianmodelforuncertaintyaboutthemeans,anduse
newadaptivestoppingrulesproposedhere.

2.1Overview

Selectionproceduresareintendedtoselectthebestofafinitesetofalterna-
tives,wherebestisdeterminedwithrespecttothelargestsamplingmean,
butthemeanmustbeinferredviastatisticalsampling([Bechhofer,Sant-
ner,andGoldsman1995]).Selectionprocedurescaninformmanagershow

11

2.1Overview

2.SelectingaSelectionProcedure

toselectthebestofasmallsetofalternativeactionstheeffectsofwhich
areevaluatedbysimulation([NelsonandGoldsman2001])andareimple-
mentedincommercialsimulationproductslikeARENA([Kelton,Sadowski,
andSadowski1998]).Selectionprocedureshavealsoattractedinterestin
combinationwithtoolslikemultipleattributeutilitytheory([Butler,Mor-
rice,andMullarkey2001]),evolutionaryalgorithms([BrankeandSchmidt
2004]),anddiscreteoptimizationviasimulation([Boesel,Nelson,andKim
a]).0320Threemainapproachestosolvingtheselectionproblemaredistinguished
bytheirassumptionsabouthowtheevidenceforcorrectselectionisdescribed
andsamplingallocationsaremade:theindifferencezone(IZ,[KimandNel-
son2005]),theexpectedvalueofinformationprocedure(VIP,[Chickand
Inoue2001b]),andtheoptimalcomputingbudgetallocation(OCBA,[Chen
1996])approaches.Eachapproachoffersanumberofdifferentsamplingas-
sumptions,approximations,stoppingrulesandparametersthatcombineto
defineaprocedure.Withsomanyvariations,thequestionarisesofhow
toselectaselectionprocedure.Thequestionisimportantbecausethede-
mandsplaceduponsimulationoptimizationalgorithmstoassistsystemde-
signchoicesareincreasing.
Onlyfewpapersthoroughlyassesshowthosevariationscomparewith
eachother,butthereareafewexceptions.SpecialcasesoftheVIPout-
performspecificIZandOCBAprocedures(inacomparisonoftwo-stage
procedures),andspecificsequentialVIPandOCBAproceduresaremore
efficientthantwo-stageprocedures([Inoue,Chick,andChen1999]).[He,
Chick,andChen2005]deriveanOCBA-typeprocedure,OCBALL,thatuses
anexpectedopportunitycost(EOC)lossfunction,thenshowthattheorig-
inalOCBAprocedure,thenewOCBALLandtheVIP-basedLL(described
below)performbetterthansomeotherproceduresinseveralempiricaltests.
ProcedureKN++isveryeffectiveamongIZprocedures([KimandNelson
2005]).Buteventhosepapersstudyalimitednumberofprocedureswith
respecttoalimitedexperimentaltestbed.
Thischaptersummarizesthemainapproachestoselectionprocedures,
derivesnewproceduresandformalizesnewstoppingrulesfortheVIPand

12

2.SelectingaSelectionProcedure

2.1Overview

OCBAprocedures,thenaddressestheunmetneedforanextensivecompar-
isonofthenewproceduresandthetopexistingIZ,VIPandOCBAproce-
dures.Eachproceduremakesapproximations,andnoneprovidesanoptimal
solution,soitisimportanttounderstandthestrengthsandweaknessesof
eachapproach.Section2.3describesnewmeasurementstoevaluateeach
to:ectrespwith•Efficiency:Themeanevidenceforcorrectselectionasafunctionofthe
meannumberofsamples.
•Controllability:Theeaseofsettingaprocedure’sparameterstoachieve
atargetedevidencelevel(asopposedtoapotentiallyconservativeguar-
anteethatthetargetedevidencelevelisexceeded).
•Robustness:Thedependencyofaprocedure’seffectivenessontheun-
derlyingproblemcharacteristics.
•Sensitivity:Theeffectoftheparametersonthemeannumberofsam-
needed.plesTheproceduresarecomparedempiricallyonalargevarietyofselectionprob-
lemsdescribedinSection2.4.Thetestbedisuniquenotonlybecauseofits
size,butalsoitsinclusionofrandomizedprobleminstances,whichmaybe
morerealisticinpracticethantheusualstructuredprobleminstancesfound
intheliterature.
Eachprocedureiscomparedforeachmetricwhenappliedtobroadclasses
ofselectionproblemsdescribedinSection2.4.Thefocushereisonappli-
cationswherethesamplesarejointlyindependentandnormallydistributed
withunknownandpotentiallydifferentvariances,orarenearlynormally
distributedasisthecaseinstochasticsimulationwithbatching([Lawand
]).0020KeltonSection2.5indicatesthatProcedureKN++ismoreefficientthanthe
originalVIPandOCBAformulations,butappearstobedifficulttocontrol.
CertainVIP(LL)andOCBA(OCBAandOCBALL)procedures,whenused
withnewstoppingrulesbelow,appeartoimprovefurtherwithrespectto
13

The2.2ceduresPro

2.SelectingaSelectionProcedure

efficiency,controllabilityandrobustness.Section2.6addressesfurtherissues
thatmaybeimportantwhenselectingaselectionprocedure.

2.2TheProcedures
Wefirstformalizetheproblem,summarizeassumptionsandestablishnota-
tion.Section2.2.1describesmeasuresoftheevidenceofcorrectselection
and,basedthereon,introducesnewstoppingrulesthatimproveefficiency.
Sections2.2.2-2.2.4describeexistingandnewvariationsonsequentialpro-
ceduresfromtheIZ,VIPandOCBAapproaches.
Thebestofksimulatedsystemsistobeidentified,where‘best’meansthe
largestoutputmean.Analogousresultsholdifsmallestisbest.LetXijbe
arandomvariablewhoserealizationxijistheoutputofthej-thsimulation
replicationofsystemi,fori=1,...,kandj=1,2,....Letµiandσi2bethe
unknownmeanandvarianceofsimulatedsystemi,andletµ[1]≤µ[2]≤...≤
µ[k]betheorderedmeans.Inpractice,theordering[∙]isunknown,andthe
bestsystem,system[k],istobeidentifiedbysimulation.Theprocedures
consideredbelowarederivedfromtheassumptionthatsimulationoutput
isindependentandnormallydistributed,conditionalonµiandσi2,fori=
1,...,k.
{Xij:j=1,2,...}ii∼dNormalµi,σi2
Althoughthenormalityassumptionisnotalwaysvalid,itisoftenpossibleto
batchanumberofoutputssothatnormalityisapproximatelysatisfied.Vec-
torsarewritteninboldface,suchasµ=(µ1,...,µk)andσ2=(σ12,...,σk2).
Aprobleminstance,denotedconfigurationinthischapter,isgivenbyχ=
(µ,σ2).
Letnibethenumberofreplicationsforsystemirunsofar.Letx¯i=
jni=1xij/nibethesamplemeanandsi2=jni=1(xij−x¯i)2/(ni−1)bethe
samplevariance1.Letx¯(1)≤x¯(2)≤...≤x¯(k)betheorderingofthesample
meansbasedonallreplicationsseensofar.Equalityoccurswithprobability
1Infactweusedthenumericallymorestablevariantsi2[ni]=ni1−1Σi2[ni],where
Σi2[ni]=Σi2[ni−1]+nin−i1(xini−x¯i[ni])2andx¯i[ni],si2[ni]denotemeanandvariance
ofthefirstnioutputsofsystemi.

14

2.SelectingaSelectionProcedure2.2TheProcedures

0incontextsofinteresthere.(i)denotestheobservedorderingbasedonthe
observedmeansx¯∙,while[i]denotesthetrueorderingofsystemsbasedon
theunknowntruemeansµ∙.Thequantitiesni,x¯i,si2and(i)maychangeas
morereplicationsareobserved.
Eachselectionproceduregeneratesestimatesµˆiofµi,fori=1,...,k.
Fortheproceduresstudiedhere,µˆi=x¯i,andacorrectselectionoccurs
whentheselectedsystem,systemD,isthebestsystem,[k].Usuallythe
systemD=(k)withthebestobservedmeanx¯∙isselectedasbest,although
ProcedureKN++belowmightrarelychooseasystemthatdoesnothavethe
bestsamplemean,duetoscreening.TheStudenttdistributionwithmeanµ,
precisionκ=σ−2,andνdegreesoffreedomisdenotedSt(µ,κ,ν).Ifν>2
thevarianceisκ−1ν/(ν−2).Denotethecumulativedistributionfunction
(cdf)ofthestandardt(µ=0,κ=1)andstandardGaussiandistributionby
Φν(∙)andΦ(∙)andprobabilitydensityfunction(pdf)byφν(∙)andφ(∙).

2.2.1EvidenceforCorrectSelection

Thissectionprovidesaunifiedframeworkfordescribingbothfrequentistand
Bayesianmeasuresofselectionprocedureeffectivenessandtheevidenceof
correctselection.Theyarerequiredtoderiveandcomparetheprocedures
below,andarealsousedwithintheBayesianprocedures(VIPandOCBA)
todecidewhentheevidenceofcorrectselectionissufficienttostopsampling.
Themeasuresaredefinedintermsoflossfunctions.Thezero-oneloss
function,L0−1(D,µ)=11µD=µ[k],equals1ifthebestsystemisnot
correctlyselected,andis0otherwise.Thezero-onelossfunctionwithin-
differencezone,Lδ∗(D,µ)=11µD<µ[k]−δ∗,relaxesthelossonlyto1
iftheselectedsystemisnotwithinδ∗ofthebest.Theopportunitycost
Loc(D,µ)=µ[k]−µDis0ifthebestsystemiscorrectlyselected,andisoth-
erwisethedifferencebetweenthebestandselectedsystem.Theopportunity
costmakesmoresenseinbusinessapplications.
15

ceduresProThe2.2

FrequentistPerspective

2.SelectingaSelectionProcedure

TheIZprocedurestakeafrequentistperspective.Thefrequentistprobability
ofcorrectselection(PCSiz)istheprobabilitythatthesystemselectedasbest
(systemD)isthesystemwiththehighestmean(system[k]),conditionalon
theprobleminstance.Theprobabilityiswithrespecttothesimulation
outputXijgeneratedbytheprocedure(therealizationsxijdetermineD).
PCSiz(χ)=def1−E[L0−1(D,µ)|χ]=PrµD=µ[k]|χ
IndifferencezoneproceduresattempttoguaranteealowerboundonPCSiz,
subjecttotheindifference-zoneconstraintthatthebestsystemisatleast
δ∗>0betterthantheothers,

PCSiz(χ)≥1−α∗,forallχ=(µ,σ2)suchthatµ[k]≥µ[k−1]+δ∗.(2.1)
[NelsonandBanerjee2001]showedthatsomeIZproceduressatisfyfrequen-
tistprobabilityofgoodselectionguarantees,
PGSiz,δ∗(χ)=defPrµD+δ∗≥µ[k]|χ≥1−α∗,
forallconfigurations.LetPICSiz=1−PCSizandPBSiz,δ∗=1−PGSiz,δ∗
denotetheprobabilityofincorrectandbadselections.
Thefrequentistexpectedopportunitycost([ChickandWu2005])is
EOCiz(χ)=defE[Loc(D,µ)|χ]=Eµ[k]−µD|χ.


BayesianPerspective

Bayesianproceduresusetheposteriordistributionoftheunknownparame-
terstomeasurethequalityofaselection.GiventhedataEseensofar,three
16

2.SelectingaSelectionProcedure

2.2ceduresProThe

measuresofselectionqualityare
PCSBayesdef=1−E[L0−1(D,M)|E]=PrMD≥i=maxDMi|E
defPGSBayes=1−E[Lδ∗(D,M)|E]=PrMD+δ∗≥i=maxDMi|E
defEOCBayes=E[Loc(D,M)|E]=Ei=1max,...,kMi−MD|E,(2.2)
theexpectationtakenoverbothDandtheposteriordistributionMofµ
givenE.MistheuppercaseletterofµtoindicatetheBayesianperspective
thatµisarealizationofitscorrespondingrandomvariableM.Assuming
anoninformativepriordistributionfortheunknownmeanandvariance,the
posteriormarginaldistributionfortheunknownmeanMigivenni>2sam-
plesisSt(x¯i,ni/si2,νi)whereνi=ni−1([deGroot1970]).EachBayesian
procedurebelowselectsthesystemwiththebestsamplemeanafterallsam-
plingisdone,D=(k).
Equations2.2canbecalculatednumericallywiththefollowingapproach:
FirstfixMDtoavaluex,thendeterminethevaluesfortheotherMiand
integrateoverallx,weightedbythedensityofMD.Fromorderstatisticswe
havePr(maxiXi≤x)=iPr(Xi≤x)iftheXiareindependent.LetFi(∙)
andfi(∙)denotethecdfandpdfofXithenthecdfandpdfofmaxiXiare
iFi(x)andifi(x)j=iFj(x).
∞PGSBayes=Fi(x+δ∗)fD(x)dx
x=∞−∞i=D∞
EOCBayes=x=−∞y=x(y−x)fi(y)Fj(y)dyfD(x)dx(2.3)
i=Dj=i,D
whereFi(x)=Φνi(x−x¯i)ni/si2,fi(x)=φνi(x−x¯i)ni/si2ni/si2.

TohaveagoodselectionforagivenMD=x,theothervaluesmustbeat
mostx+δ∗,whichleadstotheexpressionforPGSBayes.FixingMD=x
splitsEOCBayesintwocases:Ifmaxi=DMi<xthereisnoloss.Otherwise
thelossistheexpecteddifferenceconditionalonmaxi=DMi≥x.
17

ceduresProThe2.2

2.SelectingaSelectionProcedure

Equations2.2canalsobecalculatedwiththeproceduresdescribedin
[GenzandBretz2002],ifthedifferenceofStudentvariablesisassumedtobe
Studentdistributed,again.Thecorrelationbetweenthe2pairwisedifferences
/nsDwiththeselectedsystemDisapproximately√si2/ni+s2D/nDD√sj2/nj+s2D/nD.The
procedurescanbeevenadaptedtothecaseofcorrelatedXi.

onsmatixiApproTheaboveapproachesarecomputationallyveryexpensive.Intheapplication
ofselectionprocedurestheeffortforhighnumericalaccuracymightbebetter
reducedinreturnformoretimetosimulatesystems.Thereforewegivesome
approximationsneededforthefastcalculationofPGSBayesandEOCBayes.

DifferenceofStudentvariablesTheBayesianproceduresneedtocalcu-
latetheprobabilitythattwoindependentStudentvariablesti∼St(µi,κi,νi),
tj∼St(µj,κj,νj)differbyatleastδ∗.Thereareseveralwaystocalculate
y:bilitprobathis

•NumericalIntegration:
Pr(ti+δ∗<tj)=1−Φνj(x−µj)κj
∞√
−∞√√φνi((x−µi−δ∗)κi)κidx
1√=Φνj−(Φν−i1(t)κi+δ∗+µi−µj)√κjdt
0.4)(2

•Welch’sapproximation([Welch1938])forthedegreesoffreedomof
thedifference(see[LawandKelton2000],p.599):
ti−tj≈Stµi−µj,(κi−1+κj−1)−1,νij,where
νij=(κi−1+κj−1)2/(κi−2/νi+κj−2/νj)
Pr(ti+δ∗<tj)≈Φνij(−d∗ij)(2.5)
withd∗ij=(δ∗+µi−µj)κi−1+κj−1setforconvenience.Ourexperi-
18

2.SelectingaSelectionProcedure

ceduresProThe2.2

mentsindicatethatthisapproximationisalowerbound,althoughwe
couldnotprovethisobservation.

•Wilson’sapproximation([WilsonandPritsker
Welch’sforthedegreesoffreedomasabove:
νij=(κi−1+κj−1)2/(κi−2/(νi+2)+κj−2/(νj+2))−2
Pr(ti+δ∗<tj)≈Φνij(−d∗ij)

•Gaussianapproximationofthedifference:
ti−tj≈N(µi−µj,κi−1+κj−1)
Pr(ti+δ∗<tj)≈Φ(−d∗ij)

•Chernoff’sinequalityfortheGaussian-appro
20<xfor2)/xexp()xΦ(−≤

19xima])84tion:inseadtof(2.6)

(2.7)

Φ(x)≤exp(−x2/2)forx<0
2∗Pr(ti+δ∗<tj)≈Φ−d∗ij=µi>µj:≤exp(−dij/2)
µi<µj:≥1−exp(−d∗ij2/2)
.8)(2

Bonferroni’sBoundBonferroni’sinequality(see[LawandKelton1991])
givesPr(ik=1Xi<0)≥1−ik=1[1−Pr(Xi<0)],whichcanbeappliedto
givealowerboundforPCSBayes
PCSBayes≥1−[1−PrM(k)<M(j)|E].
j:(j)=(k)
ApproximatingtherighthandsidewithWelch’sapproximationdefines
∗PCSBonf=1−j:(j)=(k)Φν(j)(k)(djk),
whichmightdelivernegativevaluesforPCSBonf.
ThetermEOCBayesmaybeexpensivetocomputeifk>2.Summing
19

2.2ceduresProThe

2.SelectingaSelectionProcedure

Figure2.1:Differentmeasuresandapproximationsforcorrectselection
(Equalsamplesfork=10systemswithapairwisedifferenceofδ=0.5
andequalvariances).

thelossesfrom(k−1)pairwisecomparisonsbetweenthecurrentbestand
eachothersystemgivesaneasilycomputedupperbound([ChickandInoue
2001b;ChickandInoue2002]).Letf(j)(k)(∙)betheposteriorpdfforthe
differenceM(j)−M(k)givenalldataE(approximatelySt−d(j)(k),λjk,ν(j)(k)
distributed),andset
∞ν+s2
Ψν[s]=(u−s)φν(u)du=ν−1φν(s)−sΦν(−s).(2.9)
s=u

Then

∞EOCBayes≤w=0wf(j)(k)(w)dw
j:(j)=(k)
≈λj−k1/2Ψν(j)(k)dj∗k=EOCBonf.(2.10)
j:(j)=(k)

ThedeviationbetweentheFrequentistloss(EOCiz),theBayesianloss
(EOCBayes)anditsapproximationwiththeBonferroni-likeboundisshown
inFigure2.1.Thetwodefinitionsoflossdifferclearly.AlthoughBonferroni’s
boundisanupperboundfortheBayesianloss,EOCBonfisbelowEOCBayes,
whichthereforemustbeoriginatedinWelch’sapproximation.

20

2.SelectingaSelectionProcedure

ceduresProThe2.2

Slepian’sBoundApproximationsintheformofboundsontheabove
lossesareusefultoderivesamplingallocationsandtodefinestoppingrules.
Slepian’sinequality([Tong1980])statestheposteriorevidencethatsystem
(k)isbestsatisfies
PCSBayes≥PrM(k)≥M(j)|E.(2.11)
j:(j)=(k)
TherighthandsideofInequality(2.11)isapproximately(Welch)
∗PCSSlep=j:(j)=(k)Φν(j)(k)(djk),
wheredj∗kisthenormalizeddistanceforsystems(j)and(k),
22dj∗k=d(j)(k)λj1k/2withd(j)(k)=x¯(k)−x¯(j)andλj−k1=s(j)+s(k),
n(j)n(k)
[s(2j)/n(j)+s(2k)/n(k)]2
ν(j)(k)=[s(2j)/n(j)]2/(n(j)−1)+[s(2k)/n(k)]2/(n(k)−1).
PCSSlep≥PCSBonf,whereequalityonlyholdsfork=2andPCSSlepis
strictlytighterthanPCSBonfformorethan2systems.2Wethereforemostly
usedPCSSlep.
Thefollowingvariationincorporatesanindifferencezoneparameterδ∗to
approximatetheprobabilitythatthedifferencebetweentheselectedsystem
andthetruebestsystemisnomorethanδ∗(PGSforprobabilityofgood
selection).NotethatPCSSlep=PGSSlep,0.
PGSSlep,δ∗=Φν(j)(k)(λj1k/2(δ∗+d(j)(k))).(2.12)
j:(j)=(k)

2Fork=2,PCSBonfandPCSSlepareequal.For3systems,iftheadditionalΦν(∙)=1
thenPCSBonf=PCSSlep.AsΦν(∙)isalwaysbelow1andPCSBonfdecreasesfasterthan
PCSSlepforlowerΦν(∙),PCSBonf<PCSSlepholdsforallk>2.
21

The2.2ceduresPro

2.SelectingaSelectionProcedure

Figure2.2:Differentmeasuresandapproximationsforcorrectselection
k=(Equa10lwithsamplesafordifferencek=2δ=0systems.5ofwithneighaboringdifferencesysteofmsδ(r=igh0.t)25.The(left)vaandri-
ancesofallsystemsareequal).

[ChenandKelton2005]usedmaxinsteadof+,
PCSSlep,δ∗=Φν(j)(k)(λj1k/2max{δ∗,d(j)(k)}),
j:(j)=(k)
whichcanbeinterpretedasamaximum-likelihood-likeestimatorforPGSiz,δ∗
conditionalonµ(k)≥µ(j)+δ∗forall(j)=(k).
ThedeviationbetweenPCSiz,PCSBayes,PCSSlepandPCSBonfisshown
inFigure2.2.Evenfor10systems,thereisnovisibledifferencebetween
PCSSlepandPCSBonf.Thedifferenceisonlysignificantforafewsamples.
ObviouslyPCSSlepisnotalowerboundforPCSBayes,whichfurthersupports
theclaim,thatEquation2.5underestimatesPr(ti+δ∗<tj).

esRulppingStoTheVIPandOCBAproceduresdefinedbelowwillmakeuseofEOCBonf
andPGSSlep,δ∗todecidewhentostopsampling.Inparticular,thefollowing
stoppingrulesareconsidered:
1.Sequential(S):Repeatsamplingwhileik=1ni<Bforsomespecified
.Bbudgettalto2.Probabilityofgoodselection(PGSSlep,δ∗):RepeatwhilePGSSlep,δ∗<
22

2.SelectingaSelectionProcedure

ceduresProThe2.2

1−α∗foraspecifiedprobabilitytarget1−α∗andgivenδ∗≥0.
3.Expectedopportunitycost(EOCBonf):RepeatwhileEOCBonf>β∗,
foraspecifiedEOCtargetβ∗.
TheIZrequiresδ∗>0,butweallowδ∗=0fortheVIPandOCBAto
allowforapurePCS-basedstoppingcondition.WeusePCSSleptodenote
PGSSlep,0.PreviouslypublishedsequentialVIPandOCBAworkusedthe
Sstoppingrule.Theotherstoppingruleswillbeshowntoimprovethe
efficiencyofbothapproaches.

2.2.2IndifferenceZone(IZ)
TheIZapproach([Bechhofer,Santner,andGoldsman1995]seekstoguaran-
teePCSiz≥1−α∗,wheneverthebestsystemisatleastδ∗betterthanthe
othersystems.Theindifference-zoneparameterδ∗istypicallyelicitedasthe
smallestdifferenceinmeanperformancethatissignificanttothedecision-
er.makEarlyIZprocedureswerestatisticallyconservativeinthesenseofexcess
samplingunlessunfavorableconfigurationsofthemeanswerefound.The
KNfamilyofproceduresimprovessamplingefficiencyoverabroadsetof
configurations[KimandNelson2001].WhileaPCSguaranteeinthesense
ofEquation(2.1)wasnotproven,anasymptoticguaranteeasδ∗→0was
shown.Onememberofthefamily,KN++[Goldsman,Kim,Marshall,and
Nelson2002],mightbeconsideredtobethestateoftheartfortheIZap-
h.acpro

KimNelsonThatprocedurecanhandlethemoregeneralcaseofcor-
relatedsimulationoutput.HerewespecializeProcedureKN++forinde-
pendentoutput.Theprocedurescreensoutsomesystemsasmorerunsare
observed,andeachnoneliminatedsystemissimulatedthesamenumberof
times.Weusedξ=1replicationperstagepernoneliminatedsystemand
samplevarianceupdatesineverystage.
ProcedureKN++(independentsamples)
23

ceduresProThe2.2

2.SelectingaSelectionProcedure

1.Specifyaconfidencelevel1−α∗>1−1/k,anindifference-zoneparam-
eterδ∗>0,afirst-stagesamplesizen0>2persystem,andanumber
ξofsamplestorunpernoneliminatedsystempersubsequentstage.
2.Initializethesetofnoneliminatedsystems,I←{1,...,k},setn←
0,τ←n0,β←1−(1−α∗)1/(k−1).
3.WHILE|I|>1DOanotherstage:
(a)Observeτadditionalsamplesfromsystemi,foralli∈I.Set
n←n+τ.Setτ←ξ.
(b)Update:Setη←21(2β)−2/(n−1)−1andh2←2η(n−1).Forall
i∈I,updatethesamplestatisticsx¯iandsi2.
(c)Screen:Forall∗i,jh∈2(Isi2+sandj2)i>j,setdij←x¯j−x¯iand
ij←max0,2δnδ∗2−n.Ifdij>ijthenI←I\{i}.If
dij<−ijthenI←I\{j}.
4.Returnremainingsystem,systemD,asbest.
Forcorrelatedsamples,e.g.whenusingcommonrandomnumbersbe-
differencen−11kn=1(xik−xjk−x¯i+x¯j)2.
tweensystems,si2+sj2isreplacedbytheestimatedcommonvarianceofthe
IntheliteraturesomevariationsonKN++arefound.In[Kimand
Nelson2001]β=α∗/(k−1)isused.[Goldsman,Kim,Marshall,andNelson
2002]replacedηby−ln(2β)/(n−1),whichisapproximatelyequaltotheη
chosenabove.

Wald’sSequentialProbabilityRatioTest[Wald1947]wasthefirst
tousesequentialsamplinginconnectionwithHypothesestests.Wald’sSe-
quentialProbabilityRatioTest(SPRT)isdesignedtodecidebetweensimple
hypotheses.Theteststops,iftheratiooftheprobabilitiesunderthehy-
pothesesexceedsgivenbounds.ForarandomvariableXdependingona
parameterθletthenullhypothesisH0:θ=θ0,thealternativehypothesis
H1:θ=θ1,theerrorprobabilityoftypeI(wronglyrejectingH0)equalα
andtheerrorprobabilityoftypeII(wronglyrejectingH1)β.

24

2.SelectingaSelectionProcedure2.2TheProcedures

Thetestdecides,whichhypothesistoselectonthebasisofobservations
x1,x2,....Morespecifically,itcontinuessamplingaslongas
B<f1(x1,x2,...)<A(2.13)
f0(x1,x2,...)
forgivenconstantsA,Bandfi(∙)beingthepdfforallobservationsunder
Hi.Iftheratiois≤BthenH0isselected,if≥A,H1isselected.Waldshows
thatthistestminimizesthemeannumberofsamplesforbothθ=θ0and
θ=θ1approximatelyandguaranteesthattheerrorprobabilitiesarebelow
αandβ,ifA=1α−βandB=1−βα.

[BaumandVeeravalli1994]extendtheSPRTformultipledisjointhy-
pothesis.TheMSPRTselectshypothesisHi,if
j=1..kfj(x1,x2,...)
1−fi(x1,x2,...)≤αi,(2.14)
whereαiistheerrorprobabilityforerroneouslyselectingHi.MSPRTequals
Wald’sSPRTfork=2systems.

ToapplytheSPRTforselection,wecantestthehypothesisthatsys-
temiisatleastδ∗betterthanallothersystems,i.e.Hi:∀j=i:
µi≥µj+δ∗.ThedifferenceoftheobservedmeansunderHiisapproxi-
matelyStδij,(si2/ni+sj2/nj)−1,νij-distributed,whereνijisapproximated
withWelchandδij≥δ∗.Assumingindependenceoftheobservedmeans,
fi(x1,x2,...)canbeapproximatedby
fi(x1,x2,...)≈φνij√si2i/nij+sj2ij/nj√si2/ni1+sj2/nj.(2.15)
x¯−x¯−δ
i=jWesetδij=max{δ∗,x¯i−x¯j}inthecalculationoftheselectioncrite-
rion,sothepdfusedisthemaximalpdfconditionalonthehypothesisHi:
25

ProThe2.2cedures

2.SelectingaSelectionProcedure

maxδij≥δ∗fi(∙).Wefurthersetαi=αequally.Thestoppingruleisthen
j=(k)φν(k)jqs(2k)/n(k)+sj2/nj
max{x¯(k)−x¯j−δ∗,0}
1−max{x¯i−x¯j−δ∗,0}≤α(2.16)
i=1..kj=iφνij√si2/ni+sj2/nj
andthesystemwiththebestmeanx¯kistheselected.MSPRTcanbe
usedasastoppingruleforanyoftheBayesianproceduresorasavariantfor
allocationinanOCBA-likeprocedure.

2.2.3ValueofInformationProcedure(VIP)
TwoVIPsin[ChickandInoue2001b]allocatesamplestoeachalternativein
ordertomaximizetheexpectedvalueofinformation(EVI)ofthesamples,
subjecttoasamplingbudgetconstraint.Procedures0-1(S)andLL(S)are
sequentialvariationsofthoseproceduresthatimproveBonferroniboundsfor
PCSBayes(theexpected0-1loss)andEOCBayes(LLforlinearloss),respec-
tively.TheyallocateτreplicationsperstageuntilatotalofBreplications
run.earWhiletheoriginalstoppingruleallowsforfullcontrolofthenumberof
replications,theproceduresoutlinedbelowallowtochoosefromanyofthe
stoppingrulesdefinedinSection2.2.1.Aswewilldemonstratelater,alter-
nativestoppingrulesmaketheproceduresignificantlymoreefficient.Fur-
thermore,newproceduresareintroducedthatusedifferentapproximations
samples.ofEVIthefor.0-1ecedurPro

1.Specifyafirst-stagesamplesizen0>2,andatotalnumberofsam-
plesτ>0toallocatepersubsequentstage.Specifystoppingrule
ameters.par

2.RunindependentreplicationsXi1,...,Xin0,andinitializethenumber
ofreplicationsni←n0runsofarforeachsystem,i=1,...,k.
26

2.SelectingaSelectionProcedure

ProThe2.2cedures

3.Determinethesamplestatisticsx¯iandsi2,andtheorderstatistics,so
thatx¯(1)≤...≤x¯(k).
4.WHILEstoppingrulenotsatisfiedDOanotherstage:
(a)Initializesetofsystemsconsideredforadditionalreplications,S←
{1,...,k}.
(b)Foreach(i)inS\{(k)}:If(k)∈Sthensetλik−1←s(2i)/n(i)+
s(2k)/n(k),andsetν(i)(k)withWelch’sapproximation.If(k)∈/S
thensetλik←n(i)/s(2i)andν(i)(k)←n(i)−1.
(c)Tentativelyallocateatotalofτreplicationstosystems(i)∈S
(setτ(j)←0for(j)∈/S):
122τ(i)←(τ+j∈Snj2)(s(i1)γ(i))−n(i),
j∈S(sjγj)2
whereγ(i)←λikd∗ikφν(i)(k)(d∗ik)for(i)=(k)
(j)∈S\{(k)}γ(j)for(i)=(k).
(d)Ifanyτi<0thenfixthenonnegativityconstraintviolation:re-
move(i)fromSforeach(i)suchthatτ(i)≤0,andgotoStep4b.
Otherwise,roundtheτisothatik=1τi=τandgotoStep4e.
(e)Runτiadditionalreplicationsforsystemi,fori=1,...,k.Up-
datesamplestatisticsni←ni+τi;x¯i;si2,andtheorderstatistics,
sox¯(1)≤...≤x¯(k).
5.Selectthesystemwiththebestestimatedmean,D=(k).
TheformulasinStep4busetheWelchapproximation,andtheformulas
inStep4carederivedfromoptimalityconditionstoimproveaBonferroni-like
boundontheEVIforasymptoticallylargeτ([ChickandInoue2001b]).
Dependingonthestoppingruleused,theresultingproceduresarenamed
0-1(S),0-1(PGSSlep,δ∗),0-1(EOCBonf),withthestoppingruleinparentheses.
Theinclusionofaparameterδ∗≥0forPGSSlep,δ∗permitsearlystopping
27

ceduresProThe2.2

2.SelectingaSelectionProcedure

ifthedifferencebetweenstronglycompetingalternativesisnegligible.The
IZrequiresδ∗>0,butweallowδ∗=0fortheVIPandOCBAtoassessa
purePCS-basedstoppingcondition.Ifδ∗=0wedenotethestoppingrule
PCSSlep,whichisalgebraicallyequivalentwhenδ∗=0,toemphasizethe
PCS.toionrelatProcedureLLisavariantof0-1wheresamplingallocationsseektomin-
imizeEOCBonf.TheinitialsLL(linearloss)areusedratherthanOC(op-
portunitycost)toavoidnamingconflictswithOCBA.
ProcedureLL.SameasProcedure0-1,exceptsetγ(i)inStep4cto
λ1ik/2ν(iν)((ik)()k+()−d∗1ik)2φν(i)(k)(d∗ik)for(i)=(k)
(j)∈S\{(k)}γ(j)for(i)=(k)
γ(i)←(2.17)
NewSmall-SampleProcedures.Procedures0-1andLLallocateaddi-
tionalreplicationsusinganEVIapproximationbasedonasymptoticallylarge
numberofreplications(τ)perstage.ThatEVIapproximationalsousesa
Bonferroni-likebound,andnecessitatestheWelchapproximation.
AnimprovementmightbeobtainedbybetterapproximatingEVIwhen
thereareasmallnumberofreplicationsperstagethatareallrunforone
system.TheProcedureLL1isderivedbyremovingtheasymptoticapprox-
imationfromthederivationofLL,aswellastheBonferroniandWelchap-
proximations.Theprocedure’snameisdistinguishedfromitslarge-sample
counterpartbythesubscript1(1systemgetsallreplicationsperstage).The
procedureusesthefollowingvariables.
d{∗jk}=λ{1j/k2}d(j)(k)
−1τ(k)s(2k)τ(j)s(2j)
λ{jk}=n(k)(n(k)+τ(k))+n(j)(n(j)+τ(j))(2.18)
ProcedureLL1.SameasProcedure0-1,exceptreplaceSteps4a-4dby:
•Foreachi∈{1,2,...,k},seeifallocatingto(i)isbest:
–Tentativelysetτ(i)←τandτ←0forall=(i);setλ{−j1k},d{∗jk}
28

2.SelectingaSelectionProcedure

ceduresProThe2.2

withEquation(2.18)forallj.
–ComputetheEVI,
λ{−ik1}/2Ψn(i)−1d{∗ik}if(i)=(k)
EVILL,(i)=
λ{−k1−/12,k}Ψn(k)−1d{∗k−1,k}if(i)=(k).
•Setτ(i)←τforthesystemthatmaximizesEVILL,(i),andτ←0for
others.the

ThesamplingallocationinProcedure0-1isbasedontwoasymptotic
approximations.Procedure0-11avoidsoneofthem,aswellastheBonferroni
andWelchapproximations.

Procedure0-11.SameasProcedureLL1,excepttheEVIisapproximated
withrespecttothe0-1loss,
EVI0−1,(i)=Φn(i)−1(−d{∗ik})if(i)=(k)(2.19)
Φn(k)−1(−d{∗k−1,k})if(i)=(k)
Variationsforthestoppingrulesarenamedanalogouslyassummarizedin
.7.2.2Section

2.2.4OCBAProcedures

TheOCBAisaclassofproceduresthatwasinitiallyproposedby[Chen1996]
andthathasseveralvariations(e.g.[Inoue,Chick,andChen1999;Chen,
Y¨ucesan,Dai,andChen2005]).Thevariationsinvolvedifferentapproxi-
mationsforPCSBayes,anddifferentthoughtexperimentsforhowadditional
samplesmightimprovetheprobabilityofcorrectselection.Herewespec-
ifytheideabehindtheOCBAandthevariationsusedforthisthesis.The
OCBAassumesthatifanadditionalτreplicationsareallocatedforsystem
i,butnoneareallocatedfortheothersystems,thenthestandarderroris
scaledbackaccordingly.TheusualOCBAassumesnormaldistributionsto

29

ceduresProThe2.2

2.SelectingaSelectionProcedure

approximatetheeffect,butweuseStudentdistributions,
M˜i∼Stx¯i,(ni+τ)/si2,ni−1+τ
M˜j∼Stx¯j,nj/sj2,nj−1forj=i,
forconsistencywithaBayesianassumptionfortheunknownσi2.[Chen,
Y¨ucesan,Dai,andChen2005]and[Branke,Chick,andSchmidt2005b]found
nonotabledifferenceinperformancewhencomparingnormalversusStudent
distributionsfortheM˜i.
Theeffectofallocatinganadditionalτreplicationstosystemi,butno
replicationstotheothers,leadstoanestimatedapproximateprobabilityof
correctselection(EAPCS)evaluatedwithrespecttoM˜=(M˜1,...,M˜k),and
withM˜(j)−M˜(k)approximatedusingWelch’sapproximation.
EAPCSi=PrM˜(j)<M˜(k)|E
j:(j)=(k)
≈(1−Φν˜(j)(k)(λ˜j1k/2d(j)(k)))
j:(j)=(k)
22λ˜−1=s(k)+s(j)(2.20)
jkn(k)+τ11{(k)=i}n(j)+τ11{(j)=i}
where11{∙}is1iftheargumentistrue,and0otherwise.
TheseapproximationsresultinasequentialOCBAalgorithmthatgreed-
ilyallocatessamplestosystemsthatmostincreaseEAPCSi−PCSSlepat
eachstage.AninnovationforOCBAhereisthatsamplingcontinuesuntila
stoppingrulefromSection2.2.1issatisfied.
ProcedureOCBA.
1.Specifyafirst-stagesamplesizen0>2,anumberqofsystemstosim-
ulateperstage,asamplingincrementτ>0toallocatepersubsequent
stage,andstoppingruleparameters.

2.RunindependentreplicationsXi1,...,Xin0,andinitializethenumber
ofreplicationsni←n0runsofarforeachsystem,i=1,...,k.
30

2.SelectingaSelectionProcedure

The2.2ceduresPro

3.Determinethesamplestatisticsx¯iandsi2andthesamplemeanorder-
ing,sothatx¯(1)≤...≤x¯(k).
4.WHILEstoppingrulenotsatisfiedDOanotherstage:

(a)ComputeEAPCSifori=1,...,k.
(b)Setτi←τ/qfortheqsystemswithlargestEAPCSi−PCSSlep,
setτj←0fortheothers.
(c)Runτiadditionalobservationsfromsystemi.
(d)Foralliwithτi>0,updateni←ni+τi,thesamplestatisticsx¯i,
si2,andorderstatistics,sothatx¯(1)≤...≤x¯(k).
5.Selectthesystemwiththebestestimatedmean,D=(k).

[He,Chick,andChen2005]proposedanOCBAvariationthataccounts
fortheexpectedopportunitycost.DefineAEOCtobetheapproximationto
EOCBonfintherighthandsideofEquation(2.10),andset
EEOCSi=˜λj−k1/2Ψν˜(j)(k)λ˜j1k/2d(j)(k).
j:(j)=(k)
ProcedureOCBALLisavariationofOCBAthatallocatesreplicationsto
systemsthatmaximizetheimprovementinexpectedopportunitycost(linear
loss),AEOC−EEOCSiinStep4b.
YetanotherOCBAheuristicincorporatestheindifferencezoneparameter
δ∗intothesamplingallocation(notjustthestoppingrule).LetEAPGSi,δ∗
generalizePGSSlep,δ∗bycomputingitwithrespecttoM˜.ProcedureOCBAδ∗
allocatesreplicationstosystemsthatmostimproveanestimatedprobability
ofagoodselection,EAPGSi,δ∗−PGSSlep,δ∗,inStep4b.Thisdiffersfrom
howδ∗wasincorporatedintoOCBAby[ChenandKelton2005].Wedenote
thelatterbyOCBAmax,δ∗.
AllOCBAvariationsabovewereimplementedasfullysequentialproce-
dureshere(q=1andτ=1).

31

ceduresProThe2.2

2.SelectingaSelectionProcedure

2.2.5Optimalallocation
Fork=2systemsandequalvariancesitisoptimaltoallocatesamples
equallyamongthesystems.Wewillnowderivean“optimal”allocation
scheme.Forthederivation,weassumethemeansandvariancestobeknown
andallocatenewsamples,sothattheprobabilityforthebestsystemto
havethelargestobservedmeanismaximized.Theallocationisdetermined
independentlyoftheobservationsmade,soit’sstatically.Thepurposeofthis
allocationistogiveatheoreticalboundonthemaximaleffect,allocationcan
cedures.proselectiontoadd

maxn1,...,nkPr(X¯[k]>X¯i∀i=[k])
kn=ns.t.i=1ini≥0,(2.21)
whereX¯iisthedistributionoftheobservedmeansafternisamples.
Theprobabilitycanbecalculatedby−∞∞i=kFi(√x,n[i])fk(x,n[k])dx,where
Fi(x,n)=Φ(xσ−[iµ][i]√n)andfi(x,n)=φ(xσ−[iµ][i]√n)σ[in]arethecdfandpdfof
X¯iforagivennumberofsamplesn.
Weimplementedoptimalallocationbygreedilyallocatingsamplesforthe
systemthatincreasestheobjectiveatmost.

2.2.6ComputationalIssues
Theimplementationthatgeneratedtheanalysisandgraphsinthischap-
terusedtheGnuScientificLibary(gsl)forcalculatingcdfs,theMersenne
twisterrandomnumbergenerator[MatsumotoandNishimura1998,(with
2002revisedseeding)]andFILIB++([Lerch,Tischler,vonGudenberg,Hof-
schuster,andKraemer2001])forintervalarithmetic.Calculationswererun
onamixedclusterofupto120nodes.ThenodeswererunningLinux2.4
andWindowsXPwithIntelP4andAMDAthlonprocessorsrangingfrom2
to3GHz.TheprogramiswritteninC++andjobsweredistributedwith

32

2.SelectingaSelectionProcedure

ceduresProThe2.2

theJOSCHKA-System([Bonn,Toussaint,andSchmeck2005]).
NumericalstabilityproblemsmayariseinimplementationsoftheOCBA,
0-11andLL1allocationsevenwithdouble-precisionfloatingpointarithmetic
asthetotalnumberofreplicationsgetsquitelarge.Forexample,Ψν[s]in
Equation(2.9)isstrictlypositiveforfinitesbutmayevaluatetononpositive
values(e.g.−10−300)forlargesifsomestandardmathlibraryfunctionsfor
thetdistributionareused(e.g.tpdfandtcdfinMatlabv.6release12).
Tobetterdistinguishwhichsystemshouldreceivesamplesinagivenstage
(OCBA,0-11andLL1),numericalstabilitywasincreasedbyevaluatingthe
systemthatmaximizeslog(EAPCSi−APCS)(forOCBA)andlogEVI(i)
(for0-11andLL1).Inparticular,forOCBA,setpj=Φν(j)(k)(dj∗k),p˜j=
Φν˜(i)(k)(λ˜1ik/2d(i)(k))andj=j:(j)=(k)forconvenience.Then
APCS)(EAPCSlogi−fori=(k):jlog(1−pj)−log(1−pi)+logpi+
.22)(2.=+log[−(exp(logp˜i−pi)−1)]
fori=(k):jlog(1−p˜j)+
+log−expjlog(1−pj)−jlog(1−p˜j)−1
Thesetransformationsareuseful,becauselog(1+x)=log1p(x)andexp(x)−
1=expm1(x)haveincreasedaccuracyforxnear0.Inrarecases,wecom-
putedEAPCSi<APCS,whichwehandledbysettinglog(EAPCSi−APCS)
.to−∞ForcalculatinglogEVI,weneedlogΦν(t)andlogΨν(t).Ifthenumeri-
calstabilitydoesnotsufficetocalculatelogΦν(t)(underflowerror)wede-
riveboundsforlogΦν(t)basedonthefollowingpropertyofthecdfofa
t-distribution([Evans,Hastings,andPeacock1993]),
Φ(t)=21βreginc(2ν,21,ν+νt2)ift≤0(2.23)
ν1−21βreginc(2ν,21,ν+νt2)ift>0,
whereβreginc(a,b,x)=β(a,b)−10xua−1(1−u)b−1duistheincompletebeta
function,andβ(a,b)=Γ(a)Γ(b)/Γ(a+b)denotesthebetafunction.A
33

2.2ceduresProThe

2.SelectingaSelectionProcedure

lowerboundforlogΦν(−t)fort>0canbederivedasfollows.Iff(u)=
ua−1(1−u)b−1,thenf(0)=0,f(u)≥0andf(u)>0fora=2ν>1,b=21
andallu∈[0,1].Sotheareabelowf(u)over[0,x]isalwayslargerthanthe
areabelowthetangentat(x,f(x)).

ν1ννlogΦν(−t)≥2logt2+ν+2log(1−t2+ν)(2.24)
−log(2−1)(1−t2+ν)+2t2+ν−log2
νν1ν
Fortheupperbound,recallEquation(2.9).AsΨν(t)>0forallt>0we
2obtainΦν(−t)<t1νν+−t1φν(t),so
νt+/tlogΦν(−t)<logν−1+logφν(t)(2.25)

TheboundsinEquation(2.24)andEquation(2.25)helpforΦνbutcan-
notdirectlybeusedforboundsonΨν(t).Butthenumericalstabilitycanbe
increasedbybringingtheloginsidethecalculationoflogΨν(t):
logΨν(t)=logtν2−+1ν+logφν(t)
+log1−(tt(2ν+−ν1))exp(logΦν(−t)−logφν(t))(2.26)
AllocatingbaseduponlogEVIratherthanEVIfor0-11andLL1improved
performancewhenextremeguaranteesofcorrectselectionaresought(α∗or
β∗closeto0),butrequired50%moreCPUtimetodeterminetheallocation,
ge.eravaonCollisions,duetotheEVIbeingnotnumericallyuniquebecauseofthe
intervalboundsinEquation(2.22)throughEquation(2.26),occurredalmost
alwayswith0-11(thelowerboundisloose)ifhighevidencelevelsforcorrect
selectionwererequired.CollisionsoccurredoftenwithLL1.Inthenumerical
experimentsforOCBA,0-11andLL1,iftherewasnoclearlydefinedbest
(acollision),andtheEVIorEAPCSi−APCSwasnotnumericallydifferent
from0foranysystem(withintervalarithmetic),thenwerepeatedlydoubled
τforpurposesofcalculatingEVIorEAPCSi−APCS,untilatleastone
systemwasnumericallygreaterthan0.The‘winner’thenreceivedτ=1

34

2.SelectingaSelectionProcedure

ceduresProThe2.2

replication.Usually,atmost3doublings(τ=8)weresufficienttoselecta
winner.Iftherewasnoclearlydefinedbestbecausetwoormoresystems
whoseEVIorEAPCSi−APCShadoverlappingintervalsbuttheintervals
didnotcontain0,thenweallocatedτ=1replicationtothesystemwiththe
highestupperboundfortheinterval.
Theperformanceof0-11andLL1doesnotappeartobesignificantly
hurtbythecollisions,asthecurvesinthe(E[N],log(1−PCSiz))and(E[N],
logEOCiz)planesappearrelativelystraight.Collisionsoccurrarelywith
OCBAandOCBALL,butthereissomeslightbendtotherightforlow
valuesofα∗orEOCbounds.Thatmaysuggestapotentialinefficiencydue
toanothernumericalissuethatwehavenotyetidentified.
ProceduresKN++,LL,and0-1didnotexperiencenumericalstability
problemswithcollisions.

2.2.7SummaryofTestedProcedures
InadditiontoKN++,wetestedeightdifferentallocationprocedures,namely
•Equal,whichallocatesanequalnumberofsamplestoeachalternative,
•twoVIPproceduresthatallocatewithaPCS(denoted0-1)orEOC
(denotedLL)criterion,
•twocorrespondingsmall-sampleEVIallocation(denoted0-11andLL1),
•threeOCBAproceduresthatallocatewithaPCS(denotedOCBA),
PGS(denotedOCBAδ∗),andEOC(denotedOCBALL)criterion.
EachallocationexceptforKN++wasusedincombinationwitheachof
threestoppingrulesdefinedinSection2.2.1(S,PGSSlep,δ∗,andEOCBonf).
Overall,thisresultedin25differentprocedures.Somanyvariationswere
tested(a)tobeinclusiveandmatchallcombinationsinordertobetter
understandtherelativeinfluenceofeach,(b)tounifyseparatestreamsof
literaturewheresmallnumbersofvariantsarecomparedatatimeandnu-
mericaltestsdonottendtobecomparable,and(c)showtheimprovement

35

2.3EvaluationCriteria2.SelectingaSelectionProcedure

inbothVIPandOCBAprocedureswithstoppingrulesotherthanS(the
defaultinallpastVIPandOCBAwork).
Wealsotestedtheeffectofincludingpriorinformationaboutthemeans
andvariancesintheVIPandOCBAconfigurations,asdiscussedinSec-
tion2.4below.

2.3EvaluationCriteria
Thereareseveralwaystoevaluateselectionprocedures,includingthetheo-
retical,empirical,andpracticalperspectives.Section2.2indicatesthatthe
threeapproachesmakedifferentbasicassumptions,andthatthemosteffi-
cientrepresentativesofeachapproacheachmakeapproximationsofonesort
oranother.Theorythatdirectlyrelatesthedifferentapproachesistherefore
p.elodevtodifficultWeturntotheempiricalandpracticalperspectives.Theefficiencyofa
procedureisafrequentistmeasureofevidenceforcorrectselection(PCSiz,
PGSiz,δ∗andEOCiz)asafunctionoftheaveragenumberofreplicationsE[N].
Asafunctionofeachprobleminstanceandsamplingallocation,thestopping
ruleparametersimplicitlydefineefficiencycurvesinthe(E[N],PCSiz)plane.
[Dai1996]provedexponentialconvergenceforordinalcomparisonsincertain
conditions,soefficiencycurvesmightbeanticipatedtoberoughlylinear
onalogarithmicscale,(E[N],log(1−PCSiz)),where1−PCSiz=PICSiz.
EfficiencycurvesforEOCizandPGSiz,δ∗aredefinedsimilarly.‘Moreefficient’
procedureshavecurvesthatarebelowthoseofotherprocedures.
Efficiencycurvesignorethequestionofhowtosetaprocedure’sparam-
eterstoachieveaparticularPCSizorEOCiz.Asapracticalmatter,oneex-
pectssomedeviationbetweenastoppingruletarget,sayPCS≥1−α∗,and
theactualPCSizachieved.Thedeviationbetweenthedesiredandrealized
performanceismeasuredwithtargetcurvesthatplot(logα∗,log(1−PCSiz))
forPCS-basedtargets1−α∗,and(logβ∗,logEOCiz)foropportunitycost
targetsβ∗.Procedureswhosetargetcurvesfollowthediagonaly=xover
arangeofproblemsare‘controllable’inthatitispossibletosetparameter
valuestoobtainadesiredlevelofcorrectselection.‘Conservative’procedures
36

2.SelectingaSelectionProcedure2.4TestBedStructure

havetargetcurvesthattendtobebelowy=x,andaresaidto‘overdeliver’
becausethefrequentistmeasureforcorrectselectionexceedsthedesiredtar-
get.AnIZproceduremaythereforenotbecontrollableifitisconservative
inanunpredictableway.AcontrollableproceduremaynothaveaPCSiz
guaranteeifthetargetcurvegoesslightaboveorbelowthediagonal.

2.4TestBedStructure
Alargenumberofprobleminstancesassessedthestrengthsandweaknesses
ofeachprocedure.Wevariedthenumberofsystems,thefirststagesampling
size,andtheconfigurationofthemeansandvariances.Wetestedrandom
probleminstancesandtheabilitytousepriorinformationabouttheunknown
means.

ClassicProblemInstancesInaslippageconfiguration(SC),the
meansofallsystemsexceptthebestaretiedforsecondbest.ASCis
identifiedbythenumberofsystems,thedifferenceinmeansofthebestand
eachothersystem,andthevariancesofeachsystem.Theparametersδ,ρ
describetheconfigurationswetested.
X1jii∼dNormal0,σ12
Xijii∼dNormal−δ,σ12/ρforsystemsi=2,...,k
Ifρ=1,thenallsystemshavethesamevariance,andρ<1meansthat
thebestsystemhasasmallervariance.Wesetσ12=2ρ/(1+ρ)sothat
Var[X1j−Xij]isconstantforallρ>0.
Inamonotonedecreasingmeans(MDM)configuration,themeans
ofallsystemsareequallyspacedout,sothatsomesystemsarequiteabit
inferiortothebest.Theparametersδ,ρdescribetheconfigurationsthatwe
tested.Theoutputswerejointlyindependent,andwesetσ12likeinSC.
X1j∼Normal0,σ12
Xij∼Normal−(i−1)δ,σ12/ρi−1forsystemsi=2,...,k
37

2.4TestBedStructure2.SelectingaSelectionProcedure

Valuesofρ<1meanthatbettersystemshaveasmallervariance.Forsuffi-
cientlysmallρ,theprobabilitythattheworstsystemhasthebestobserved
meanishigherthantheprobabilityforthesecondbestsystem.
FortheSCandMDMconfigurationswetestedmany(hundreds),butnot
allofthefollowingparametercombinations:k∈{2,5,10,20,50},δ∈{0.25,
0.354,0.5,0.707,1},andρ∈{0.125,0.177,0.25,0.354,0.5,0.707,1,1.414,
2,2.828,4},withn0∈{4,6,10}.WetestedB∈{kn0,...,2kδ1Φ−1αk∗2}
forthebudgetstoppingrule(S),variedtheindifferencezoneparameter
relativetothedifferenceinmeansδ∗∈{0,0.05,0.1,...,0.6}andα∗∈
[0.001,0.5]forPGS-basedstoppingrules(PGSSlep,δ∗)andKN++,andvar-
iedβ∗∈[0.001,0.5]for(EOCBonf).Forsomeconfigurations,wevaried
α∗∈[0.001,1/k]forKN++astheachievedPICSforα∗=0.5wasbelow
.01.0

RandomProblemInstancesAssessmentsofselectionproceduresinthe
literatureusuallyapplyprocedurestoaspecificsetofstructuredproblems,
asabove.ARandomprobleminstance(RPI)maybemorerealistic
inthesensethatproblemsfacedinpracticearetypicallynotintheSCor
MDMconfiguration.IneachRPIexperimentbelow,theoutputisagain
jointlyindependent,Xijii∼dNormal(µi,σi2)fori=1,...,k,conditionalon
theprobleminstance.Theprobleminstanceχissampledrandomlypriorto
applyingaselectionprocedure.Correctselectionmetricsaregeneralizedto
beexpectationsoverthesamplingdistribution,e.g.PCSiz=Eχ[PCSiz(χ)].
ThefirstRPIexperiment(RPI1)samplesχfromthenormal-inverse
gammafamily.Arandomχisgeneratedbysamplingtheσi2independently,
thensamplingtheMi,givenσi2,

p(σi2)∼InvGamma(α,β)(2.27)
p(Mi|σi2)∼Normalµ0,σi2/η.
IfS∼InvGamma(α,β),thenE[S]=β/(α−1),S−1∼Gamma(α,β),E[S−1]=
αβ−1andVar[S−1]=αβ−2.Increasingηmakesthemeansmoresimilar
andthereforetheproblemharder.Wesetβ=α−1>0tostandardize
38

2.SelectingaSelectionProcedure2.4TestBedStructure

themeanofthevariancetobe1,andsetµ0=0.Increasingαreduces
thedifferencebetweenthevariances.Wetestedmanycombinationsout
ofk∈{2,5,10,20},η∈{0.0625,0.0884,0.125,...,4},α∈{2.5,100},and
n0∈{4,6,10}.ThederivationsoftheVIPandOCBAprocedurescorrespond
0.ηto→TheRPI1experimentpermitsatestofwhethertheVIPandOCBA
procedurescanbenefitfromusingthesamplingdistributionofχinEqua-
tion(2.27)todescribepriorjudgementaboutthemeansandvariancesofeach
system.Section2.2doesnotallowforthisdirectly,butthemathematical
developmenttodosowasprovidedelsewherefortheVIP([ChickandInoue
1998;ChickandInoue2001b]).Insummary,theposteriordistributionofMi,
giventhepriordistributioninEquation(2.27)anddataEi=(xi1,...,xini),
is

p(σi2|Ei)∼InvGamma(α,β),
p(Mi|σi2,Ei)∼Normalµ0,σi2/η
whereα=α+ni/2,β=β+(ηη+nnii(µ0−x¯i)2+jni=1(xij−x¯i)2)/2,µ0=
ηµη0++nniix¯i,andη=η+ni.ToapplythatresulttoallVIPproceduresinSec-
tion2.2.3,substituteeachx¯iwithµ0;replaceeachsi2withβ/α;andreplace
eachniwithη,exceptinthedegreesoffreedom,whereni−1shouldbe
replacedwith2α.TheOCBAhaspreviouslyalwaysassumedanoninforma-
tivepriordistribution.AnalogoussubstitutionsallowOCBAandOCBALL
touseotherpriordistributionsfortheunknownmeansandvariances.
AsecondRPIexperiment(RPI2)samplesprobleminstancesfromadis-
tributionotherthannormal-invertedgammatoremoveanypotentialadvan-
tagefortheVIPandOCBAapproaches.Thereisnoobjectivelybestdis-
tributionforsamplingprobleminstances.WechoseRPI2toindependently
from:sample

σi2∼InvGamma(α,β)
Mi|σi2∼(−1)aExponential(η/σi2)1/2,
39

2.5EmpiricalResults2.SelectingaSelectionProcedure

wherethemeanofanExponential(λ)distributionis1/λ.−Exponential(λ)
isanotationalabbreviationforadistribution,wheretherealizationsofan
exponentialareinverted.Therearetypicallyseveralcompetitorsforthebest
ifa=1andfewcompetitorsforthebestifa=0.Alargerηmakesforharder
problemswithclosermeans.Heterogeneityinthevariancesiscontrolledwith
αandβ.WetestedthesameparametersasinRPI1.

SummaryofConfigurationsTheSCfavorsIZproceduresinthatIZ
proceduresprovideaminimaltargetperformancewithrespecttoaleastfa-
vorableconfiguration(LFC),andformanyIZproceduresanSCwithδ=δ∗
isaLFC.TheRPI1(ηnear0)mayfavortheVIPandOCBA,asthederiva-
tionofthoseproceduresassumepriorprobabilitymodelsthataresimilarto
thesamplingdistributionoftheprobleminstances.TheMDM,RPI1(larger
η)andRPI2experimentsdonotfavoranyprocedureinthischapter.

2.5EmpiricalResults
Thissectionsummarizesthequalitativefeaturesoftheanalysis.Plotswere
generatedwith105macroreplicationsforeachcombinationofproblemin-
stance,samplingallocation,andstoppingruleparametervalue.Toimprove
thesignificanceofcontrastsbetweendifferentprocedures,commonrandom
numbers(CRN)wereusedtogeneratecommonconfigurationsforRPIex-
periments,andtosynchronizethesamplesobservedacrossprocedures.CRN
werenotusedbetweensystems.KN++δ∗referstoKN++withthegiven
indifferencezoneparameter.Bydefault,n0=6unlessspecifiedotherwise.

TwoSystems,SC/MDM.Whentherearek=2systems,theSCand
MDMconfigurationsareequivalent,andPICSizisproportionaltoEOCiz.
Whenthevariancesareequal,itisoptimaltosampleequallyoftenfrom
bothsystems(e.g.[GuptaandMiescke1994]),soProcedureEqualsamples
optimally.Figure2.3demonstratestheeffectofdifferentstoppingruleson
efficiency(similareffectfordifferentδ).TheEOC-basedstoppingruleismore
efficientthanthePCS-basedstoppingrule.Botharemuchmoreefficientthan

40

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.3:EfficiencyofEqualalloca-Figure2.4:Efficiencyofdifferental-
KtioNn++withwithdifferenδ∗t=δstopping(SC,krules=and2,δlo∗cat=δion(SC,prok=cedures2,δa=nd0.K5,Nρ+=+1).with
δ=0.5,ρ=1).

stoppingafterafixedbudget(S)becauseanyadditionalsamplingisadapted
tothelevelofevidenceobservedsofar.
Ifk=2,thenKN++sampleseachsystemequallyoftenuntilthestop-
pingcriterionismet,soitisequivalenttotheEqualallocationwithaspecial
stoppingrule.ForhigherPICS,Equal(EOCBonf)inthiscaseismoreefficient
thanKN++,whileforverylowPICS,KN++beatsEqual(EOCBonf).Fig-
ure2.3alsoshowsthattheefficiencycurveforKN++andEqualallocation
withtheSandWaldstoppingruleisstraighterthanforthePCSorEOC
stoppingrules.TheBayesianstoppingrulescauseaslightcurvature.
AllocatingequallyandstoppingwithWald’sSPRTisthemostefficient
procedure.Itoutperformsallotherproceduresforeachstoppingvalue.
Figure2.4showsthatofallallocationswiththeEOCBonfstoppingrule,
Equalperformsmostefficiently(itisoptimalforthisparticularsetting),with
LL1,0-1andOCBAfollowing.LLperformsidenticalto0-1,and0-11isvery
similarto0-1forthisproblem(notshown).Asimilarprecedenceisobserved
forthePCSSlepandPGSSlep,δ∗stoppingrules.FortheSstoppingrule,all
VIPandOCBAallocationsperformaboutthesameasEqual(notshown).
Therelativeorderingofthestoppingrulesfortheequalallocation,namely
EOCBonfbeatsPCSSlepwhichbeatsS,isalsoobservedforallVIPand
OCBAallocationswithasimilarorderofmagnitudedifference(notshown).
Withadaptivestoppingrules(EOCBonf,PCSSlep,PGSSlep,δ∗),alarge
41

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.5:Influenceofn0(SC,k=2,δ=0.5,ρ=1).

numberofinitialsamplespersystem,n0,limitstheopportunitytomakean
earlyselection,butasmalln0increasestheprobabilityofpoorestimates
oftheoutputmeanandvariance.Fortheposteriormarginaldistributions
oftheunknownmeanstohaveafinitevariance,werequiren0≥4(see
textafterEquation(2.2)).Figure2.5showsthatincreasingn0inProcedure
Equal(EOCBonf)increasesthenumberofsamplesrequiredtoreachrelatively
lowlevelsofevidenceforcorrectselection,butincreasestheefficiencyof
theproceduretoreachhighlevelsofevidenceforcorrectselection.The
differencesinthecurvesarepredominantlyattributedtooutputthatcauses
samplingtostopafterveryfewsamples,duetomisleadinglylowvarianceand
PICSestimates.TheOCBAandVIPproceduresbehavesimilartoEqual
inthisrespectforeachstoppingrule.Withthenonadaptivestoppingrule
(S),theyseeminsensitiveton0.ProcedureKN++isquiteinsensitiveton0
(regardlessofk,notshown).
Thetestsaboveuseδ∗=δforKN++andδ∗=0forPGSSlep,δ∗.That
choiceseemsnaturalforKN++,sinceδ∗=δisaLFCformanyIZpro-
cedures.ForPGSSlep,δ∗,thechoiceδ∗=0seemsthenaturalchoicefor
PCSizefficiency.Buttheparameterδ∗hasastrongeffectonefficiencyand
targetcurves.Settingδ∗toobtainadesiredPICSizseemschallenging(an
observationformostconfigurationstested,notjustSC).
Figure2.6showstheinfluenceofδ∗onPCSizefficiency(themeannumber
ofsamplesrequiredtoobtainaspecifiedlevelPICSiz).ForsmallPICSiz,
theremayexistsettingsforδ∗sothatKN++andEqual(PGSSlep,δ∗)are
42

2.SelectingaSelectionProcedure2.5EmpiricalResults

moreefficientthanEqual(EOCBonf).Toseethis,notethatwhenPICSiz=
0.005and0.01,thecurvesforKN++andEqual(PGSSlep,δ∗)gobelowthe
horizontallines.Thehorizontallinesshowmeannumberofsamplesrequired
byEqual(EOCBonf)toreachthecorrespondingPICSizlevel.Thevalueofδ∗
thatisneededtoobtaintheminimalmeannumberofsamplesdependsonthe
probleminstance.Thecurvatureisinducedbytwoconcurringeffects:For
agivenlevelofPICSiz,α∗hastobedecreasedifδ∗isincreased.Themean
numberofsamplesareincreasedbydecreasingα∗butarealsodecreased
byincreasingδ∗.Botheffectsarenonlinear,whichgivesthecurvaturein
.6.2eFigurSincetheprobleminstanceisunknowninpractice,itisnotclearhowto
setδ∗ingeneral.Figure2.7illustratesthatδ∗alsohasastrongeffectonthe
targetperformance.Thereisnoobviouswaytosetδ∗,α∗toreliablyachieve
agivenPICSizgoal.Choosingasmallδ∗mayresultinsamplingwaybeyond
whatisactuallyneeded,inparticularforKN++andWald.Whileδ∗=δ
wouldyieldverygoodtargetperformanceforKN++,δisusuallyunknown.
Equal(PGSSlep,δ∗)significantlyunderdeliversforδ∗≥0.3,i.e.valuessmaller
thanthetruedifferencebetweenthebestandsecondbestsystem.
TheEOCBonfstoppingruleisquitesensitivetothedifferencebetween
thetwosystems,δ(seeFigure2.8).ItslightlyunderdeliversEOCizforsmall
δ,andsignificantlyoverdeliversforlargeδ.Asimilarbehaviorisobserved
forKN++herewhencontrolforEOCizisattemptedwithβ∗=δ∗α∗.
Overall,forSCwithk=2,Equal(EOCBonf)andKN++seemthemost
efficient.NoprocedureisfullycontrollableforSC,k=2.Theremarksso
farpresumeacommonvariance(ρ=1).Whenρ=1,theequalallocationis
notoptimal,andKN++andEqualallocationareslightlylessefficient(not
.wn)sho

SCwithk>2systems.Itisnotoptimaltosampleeachsystemequally
oftenifk>2.Figure2.9showstheefficiencyofdifferentallocationrulesfor
theEOCBonfstoppingruleandk=10systems.Thesettingsarecomparable
toFigure2.4withk=2systems.WhileEqualisoptimalfork=2,it
performsworstfork=10.ThemostefficientallocationsareOCBALL
43

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.6:Influenceofδ∗onFigure2.7:Influenceofδ∗onKN++
meannumberofsamplestoobtainandEqual(PGSSlep,δ∗)targetperfor-
adesiredPICSiz,forKN++andmance.(SC,k=2,δ=0.5,ρ=1).
Equal(PGSSlep,δ∗)(SC,k=2,δ=
0.5,ρ=1).

andOCBA,thenLLcloselybehind.KN++ismuchlessefficientthan
OCBALL,OCBAandLL(eachwithEOCBonfasastoppingrule).The
differencebetweentheefficiencyoftheBayesianproceduresrelativetothe
EqualandKN++proceduresincreaseswithk(testedk=2,5,10,20).The
qualitativenatureoftheclaimdoesnotchangeasδandρareindividually
variedfromthevaluesusedfortheplot.
ProceduresLL1and0-11wouldperformsimilarlytoKN++inFigure2.9
(notshown).Infact,thesmallsampleproceduresturnedouttobegenerally
lessefficientthantheircounterpartsLLand0-1.Theimplicationisthatthe
useoftheBonferroniandWelchapproximationsbyLLand0-1causesless
deviationfromoptimalsamplingthanmyopicallyallocatingsamplesoneat
atimetoreduceEVIinLL1and0-11.
Otherobservationsfork=2alsoholdfork=5,10and20,including:
theprecedenceoftheeffectivenessofstoppingrules(EOCBonfbeatsPCSSlep
whichbeatsS);theimportanceofasufficientlylargen0fortheVIPand
OCBAprocedures;thesensitivityofKN++toδ∗butnotn0.
MonotoneDecreasingMeans.ForMDMandk>2equalallocation
isnolongeroptimal.Figure2.10showstheoptimalallocationcompared
toOCBAandLL.Thecurvesfortheloss-basedprocedures(OCBALLnot
44

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.8:InfluenceofδontargetFigure2.9:EfficiencywithEOCBonf
performance(SC,k=2,ρ=1).stoppingrule(SC,k=10,δ=0.5,
1).=ρ

Figure2.10:ComparisonofOCBAwiththeoptimalallocationrule.Theline
foroptimalallocationismoreruggedduetofewersimulations(104instead
of105);MDM(k=10,δ=0.5,ρ=1).

shown)arenearlyparalleltotheoptimalallocation,whichindicatesthat
theseproceduresallocatealmostoptimalaftertheinitialn0samples.
MDMaddsthecomplicationthatEOCizisnotproportionaltoPCSiz
whenk>2.Figure2.11illustratesthatfortheEqualallocation,the
EOCBonfstoppingruleoutperformsPCSSlep,whichbeatsS,anorderob-
servedforallVIPandOCBAallocations,andallMDMconfigurationstested.
Notably,theEOCBonfstoppingruleoutperformsPCSSlepnotonlyforEOCiz
efficiency,butalsoforPCSizefficiency.AsforSC,thePGSSlep,δ∗stopping
rulecanbemoreefficientthantheEOCBonfstoppingruleforsome(butnot
.∗δall)

45

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.11:DifferentstoppingrulesFigure2.12:Targetgraphsfor
(line(symbtyopls)es)(aMndDaM,llokcat=ion10,proδ=cedures0.5,0K.5,N+ρ+=an1).d0-1(MDM,k=10,δ=
1).=ρ

Figure2.11alsoexemplifiesanobservationforMDMrunsthatKN++
withδ∗=δistypicallymoreefficientthantheoriginalVIPandOCBA
procedures,whichusedtheSstoppingrule.However,theoriginalVIPand
OCBAallocationswiththenewEOCBonfstoppingrulearemoreefficient
thanKN++.AlthoughstoppingwithWaldwasthemostefficientfork=2,
itistheworststoppingruleinMDM.ThisholdsforWaldusedintheallo-
cation,too(notshown).ThemostefficientallocationsareLLandOCBALL
(alongwith0-1andOCBA,notshown).Thesmallsampleprocedures,0-11
andLL1,wereonlycompetitiveforhighPICSvalues.
ForMDM,theEOC-basedallocationstypicallyoutperformthecorre-
sponding0-1-basedallocationsforallstoppingrules,thedifferencebeing
particularlysizablefortheSstoppingrule(notshown).Thisistruenot
onlyforefficiencywithrespecttoEOCiz,butalsotoPCSiz.ForeachMDM
configurationtested,LL(EOCBonf)andOCBALL(EOCBonf)arenotstatis-
ticallydifferentforefficiency.Thosetwoproceduresalsoperformroughly
similarintargetplotsformostconfigurationsandfollowthetargetdiagonal
reasonablywellinmostcases,althoughsomedifferenceswithnodiscernable
patternwereobservedinsometargetplots.
Figure2.12illustratesthatKN++isagainverysensitivetotheparam-
eterδ∗(difficulttocontrol).WhileKN++adherestothetargetquitewell
46

2.SelectingaSelectionProcedure

2.5EmpiricalResults

pFigurerformae2.13nce:(Efferightctofpanel).var(ianceMDMratio,kρ=on10,δ=efficiency0.5).P(leftrocedurespanel)OandCBtAargandet
OCBALLusePCSSlepstoppingrule.ProceduresOCBALLandLLperform
me.asthe

forSCwhenδ∗=δ,itsignificantlyoverdeliversevenforthissettingforthe
MDMconfiguration.ProcedureOCBALL(PGSSlep,δ∗)isalsosensitivetothe
parameterδ∗.WhilethetargetcurvesforOCBALL(PGSSlep,δ∗)shiftroughly
paralleltothediagonal,thetargetcurvesofKN++changeinslope.Asfor
SC,KN++andPGSSlep,δ∗arequitesensitivetoδandthusnotcontrollable.
Figure2.13illustratestheeffectoftheoutputvarianceratioρondifferent
proceduresforMDMwithk=10.Withρ=1(equalvariance),thebest
PCSSlepproceduresperformsomewhatmoreefficientlythanKN++.In-
creasingρ(bestsystemshavelargervariance)haslittleeffectontherelative
performanceoftheprocedures.Decreasingρto0.5(verylargevariancefor
theworstsystems)increasesthetotalnumberofsamplesforallprocedures,
butparticularlydeterioratestheefficiencyofKN++(infarrightofefficiency
plot)relativetothePCSSlepprocedures.ProcedureKN++alsooverdeliv-
ersmorethansomeotherprocedures(rightpanel).Thetargetcurvesforall
proceduresarerelativelyinsensitivetoρ(thetargetreliesprimarilyonthe
differencebetweenthetwosystemscompetingmostforbest,soefficiencyis
affectedmorethanthetargetcurve).
ProceduresOCBALLandLLaresomewhatmoreefficientthanOCBA
and0-1athighPICSlevels,butthereversemaybetrueinmanyMDMand
SCconfigurationsforverylowPICSlevels(notshown).
ForallSCandMDMconfigurationsandalmostallsamplingprocedures,
47

2.5EmpiricalResults

2.SelectingaSelectionProcedure

theefficiencycurvesexhibitacertaincurvature.Wefoundseveralexplana-
tionsforcurvedefficiencylinesfortheOCBAandVIPprocedures.One,
asmalln0leadstopoorervarianceestimatesinitially,withapotentialfor
either(a)earlystoppingifPICSisstronglyunderestimated,or(b)amas-
sivenumberofsamplesbeingrequiredifanextremelylowPICSorEOC
isdesired,initialestimatessuggestthatthebestsystemisworst,andthe
procedurethentriestodistinguishbetweentheequalsystemsintheSC.
Bothcasesarealleviatedbyincreasingn0.Two,thetestbedpushedthe
procedurestonewlimitsfornumericalstability.Preliminaryefficiencyplots
forsomeproceduresweresomewhatmorecurvedthanthosepresentedhere.
Section2.2.6describescomputationaltechniquestoreducethatcurvature.
Webelievethatthiscausewaseliminated.Three,exponentialconvergence
resultsforordinalcomparisonsareasymptoticandavailableforonlysome
procedures,sostraightlinesmightnotbeexpectedatalllevelsofPICSiz
andEOCizforallprocedures.

RandomProblemInstances1.FortheRPIexperiments,itisnecessary
tochooseδ∗>0forthePGSSlep,δ∗stoppingrulebecausethereisareasonable
probabilitythatthetwobestsystemshaveverysimilarmeans,inwhichcase
δ∗=0resultsinexcessivesampling.Thereforeδ∗=0(orPCSSlep)isto
beavoidedinpractice.Weexamineefficiencyfortheprobabilityofabad
selection,PBSiz,δ∗,insteadofPICSiz,inthissection.
ForbasicallyallRPIsettings,theLL,OCBALLandOCBAδ∗allocation
rulesaremoreorlessequallyefficient.The0-1allocationisgenerallyless
efficient(itisderivedwithmoreapproximations,andwastessamplestrying
todistinguishbetweentwoveryclosecompetitorsintheRPI)andEqualis
worst.SeeFigure2.14fortheSstoppingrule(whichmaybeneededifan
analysishasastricttimeconstraint).
WhilethedifferencesamongtheallocationrulesarerathersmallforRPI,
theperformanceofthestoppingrulesvarieswidely.Figure2.15comparesdif-
ferentstoppingrulesincombinationwithEqualallocationbasedonPGSiz,δ∗
efficiency.PGSSlep,δ∗stoppingruleand‘matching’δ∗clearlyperformsbest.
Bymatching,wemeanthattheδ∗chosenforthestoppingruleequalsthe

48

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.14:PBSδ∗Efficiencyofallo-Figure2.15:PBSδ∗Efficiencyof
cationswithSstoppingrule(RPI1,Equalallocation(RPI1,k=5,η=1,
k=5,η=1,α=100).α=100).

valueofδ∗chosentomeasurePGSiz,δ∗.Whilethisisnotnecessarilythe
mostefficientsetting,itseemsthemostsensible.ForRPI,theeffectof
δ∗onefficiencyisrelativelysmall(inFigure2.15,Equal(PGSSlep,0.2)and
Equal(PGSSlep,0.4)arealmostidentical),andthechosenmatchingsetting
yieldsaverygoodPGSiz,δ∗targetperformance.
ForEOCizefficiency,settingsforδ∗existsothatPGSSlep,δ∗ismoreeffi-
cientthantheEOCBonfstoppingrule,seeFigure2.16(leftpanel).Whether
thatfindingisofpracticalrelevanceremainstobeseen,asitisnotyetclear
howtosetδ∗inPGSSlep,δ∗tocontrolEOCizviaβ∗=δ∗α∗(rightpanel).
Severalefficiencycurves,inparticularEqual(S)inFigure2.15andFig-
ure2.16,aremorecurvedforRPI1thanfortheSCandMDMconfigurations.
Thatcurvatureislargelyduetoaverylargenumberofsamplesforafew
very“hard”configurations(thebesttwosystemshaveveryclosemeansand
riances).avgelarFigure2.17comparesthreeselectionprocedureswithadaptivestopping
rules,KN++,Equal(PGSSlep,δ∗),andOCBAδ∗(PGSSlep,δ∗).Asistypical
fortheRPI1problemstested,OCBAδ∗(PGSSlep,δ∗)outperformsKN++for
efficiency(leftpanel)andcontrollability(rightpanel).Whenmovingfrom
α=100(verysimilarvariancesforeachsystem)toα=2.5(verydifferent
variances),theefficiencyofOCBAδ∗(PGSSlep,δ∗)improvesandtheefficiency
ofKN++isbasicallynotaffected.
AscanbeseeninFigure2.18,thesensitivitywithrespecttoηinthe
49

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.16:Efficiency(left)andtarget(right)forEqualallocationand
differentstoppingrulesw.r.t.EOCiz(RPI1,k=5,η=1,α=100).For
PGSSlep,δ∗stopping,β∗isapproximatedbyα∗δ∗

Figure2.17:EfficiencyandtargetforPCS-basedprocedures(RPI1,k=5,
η=1,α=2.5,100).

50

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.18:InfluenceofηonefficiencyandtargetforPCS-basedprocedures
(RPI1,k=5,α=100).

RPIexperimentsismuchsmallerthanthesensitivitywithrespecttoδob-
servedfortheSCandMDMconfigurationsinFigure2.8.Notethatthe
differencebetweenthebestandsecondbestsystemisproportionaltoη−2.
Forefficiency(leftpanel)OCBALL(PGSSlep,δ∗)slightlyoutperformsKN++.
Regardingtargetperformance,KN++consistentlyandstronglyoverdeliv-
ers,whileOCBALL(PGSSlep,δ∗)meetsthetargetratherwelloverallηtested.
Also,procedureswiththeEOCBonfstoppingrulefollowanEOCiztargetwell
wn).shot(noObservationsfromSCandMDMthatapplytoRPI1aswellinclude:
TheBayesianproceduresaregenerallyquitesensitiveton0,whileKN++is
not;KN++becomeslessefficientrelativetotheBayesianproceduresasthe
numberofsystemskincreases.
Ifpriorknowledgeonthedistributionofmeansandvariancesisavail-
able,thiscanbeintegratedintotheBayesianproceduresasdescribedin
Section2.4.Thebenefitofdoingso,whenpossible,isapparentinFig-
ure2.19(leftpanel).Thetoplineshowstheefficiencyofthestandardpro-
cedurewithEqualallocationandabudgetstoppingrule.Thiscanbeim-
provedbyswitchingtoaflexibleallocationprocedure(OCBALL(S)),using
anadaptivestoppingrule(OCBALL(EOCBonf)),andusingpriorinformation
(OCBAprLLior(EOCprBonfior)).Thesechangesreducethemeannumberofsamples
requiredtoachievealossof0.01from291to164,to94andto79.Thetar-
getperformance(rightpanel)isonlyslightlyaffectedbyincorporatingprior

51

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.19:Effectofallocation,stoppingruleandpriorinformation(RPI,
k=5,η=1,α=100).

n.atioinform

RandomProblemInstances2.TheRPI2experimentgeneratedrandom
probleminstancesthatdonotmatchtheunderlyingassumptionsoftheVIP
andOCBAproceduresregardinganoninformativedistributionofmeansand
variances.Inonesetting,therearefewverygoodsystems(a=0).Inan-
other,therearelikelytobeseveralgoodsystems(a=1).ProcedureLLand
OCBALLagainperformalmostidenticallyforefficiencyandcontrollability,
soonlythelatterisshowninplots.
Figure2.20comparestheefficiencyandtargetcurvesforOCBALL(PGSSlep,δ∗)
andKN++.ProceduresOCBALLandLLaresomewhatlessefficientthan
KN++ifthereareseveralgoodsystems(a=1,leftpanel).Thedifference
issmallerforlargerδ∗.ProceduresOCBALLandLLmeetthetarget,and
KN++significantlyoverdeliversPBSiz,0.2.TheRPI2configurationwithfew
goodsystems(a=0)isquitesimilartoRPI1withrespecttothelongtail
distributionofthegoodsystems,soitisnotsurprisingthatresultsarevery
similar.Butevenformanygoodsystems(a=1),mostoftheresultsfrom
RPI1carryover(notshown).
Onthewhole,OCBALLandLLperformverywellforRPI2eventhough
theprobleminstancesdonotfollowthenormal-invertedgammadistribution
thatisimplicitinthederivationofthoseprocedures.Asmalldegradation
inefficiencyrelativetoKN++maybeexpectediftherearemultiplevery
goodsystems,butcontrollabilityremainswithPGSSlep,δ∗.Procedures0-1,
52

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.20:EfficiencyandtargetforRPI2(k=5,η=1,α=100).LLand
OCBALLperformalmostidentically.
0-11andLL1arelesseffective.
AdditionalSupportingGraphs
Theprevioussectionpresentedasummaryofthegeneralconclusionsfrom
thestudy.Thissectioncontainsasubsetofadditionalresultsthatexplorethe
ideasfurther.Itisnotpracticaltodisplayallresultsfromtheexperiments,as
wetestedover150problemconfigurationsdefinedbycombinationsofk,{SC,
MDM,RPI1,RPI2},andconfigurationparameters(δ,ρforSC,MDM;η,α,β
forRPI1,RPI2).Togetherwithcombinationsofn0,samplingallocations,
andstoppingruleparameters,over104differentcombinationswererun.We
developedagraphicalvisualizationtooltoallowaneasynavigationthrough
theresults.Thattoolwasusedtogeneratemostofthefiguresinthischapter.

2>kSC,Figure2.21(leftpanel)illustratestheobservationthattheadvantageofadap-
tiveBayesianprocedures,relativetoEqual,increaseswithk.Thequalitative
natureofthegraphdoesnotchangeasδandρareindividuallyvariedfrom
thevaluesusedfortheplot.Forallotherprocedureswiththenewstop-
pingrules,thereisatendencytooverdeliveraskincreases,butOCBALLis
moresensitivethanEqual(rightpanel).Thetendencytooverdeliverwith
increasingkmightbeattributedtotheslackintroducedbySlepian’sand
.litiesinequani’sBonferro

53

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.21:Influenceofthenumberofsystemskonefficiency(rightpanel)
andtarget(leftpanel).EqualandOCBAallocationareusedincombinaton
withEOCBonfstoppingrule(SC,δ=0.5,ρ=1).

ingFiguronethe2.22n:CumobermparisoofsynsteofmsKNk++(SC,aδnd=O0C.B5,Aρ=(EOC1).Bonf)efficiencydepend-

SimilartoEqual,KN++alsolosesefficiencyrelativetoOCBA(EOCBonf)
asthenumberofsystemskincreases(Figure2.22).
Figure2.23showstheimportanceofasufficientlylargen0alsofork>2.
Therightpanelindicatesthatincreasingn0increasesthetendencytooverde-
liver.WhileLL(EOCBonf)isslightlyclosertothetargetthanOCBALL(EOCBonf),
itisslightlylessefficient.KN++isquiteinsensitiveton0(notshown).
Alargervarianceforthebestsystemrelativetotheothersystems(larger
ρ)makescorrectselectionseasier(Figure2.24,leftpanel).Differentalloca-
tionfunctionsresponddifferentlytoρ,asillustratedforOCBAandOCBALL,
representativesforthe0-1-andEOC-basedallocations.Withρ=4,the
EOC-basedallocationisclearlysuperior,buttheadvantagediminishesfor
lowPICSasρdecreases,andthePCS-basedallocationpartiallyoutperforms
54

2.SelectingaSelectionProcedure

2.5EmpiricalResults

(left)Figureand2.23tar:getEffect(righoft)vario(SC,uskn=0,10,withδ=0EOC.5,ρBonf=1).stoppingruleonefficiency

Figure2.24:InfluenceofvarianceratioρonOCBAandOCBALL(SC,k=
10,δ=0.5,EOCBonf).

theEOC-basedallocation.Largerρoverdeliverslightlymoreonthetarget
plots,andOCBAoverdeliversslightlymorethanOCBALL(rightpanel).

2>k,MDMFigure2.25showsPBSiz,δ∗efficiencyandtargetperformancefordifferent
δ∗.Theparameterδ∗forKN++andPGSSlep,δ∗stoppingrulehavethereby
beensettotheindifferencezoneusedformeasuringperformance.ForMDM
withδ=0.5,anindifferencezoneofδ∗=0.2orδ∗=0.4areequivalent
forPBSiz,δ∗efficiency,asonlythebestsystemisconsideredtobeagood
selection.Forδ∗=0.6,thetwobestsystemsareconsideredgood.Onthe
efficiencyplot(leftpanel),itcanbeseenthattheproblemwithPBSiz,0.6is
significantlyeasier.Theefficiencycurvesforδ∗=0.2and0.4areverysimilar
55

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.25:PBS∗efficiencyandtargetforOCBA(PGS∗)and
KN++fordifferenizt,δsettingsofδ∗(MDM,k=10,δ=LL0.5,ρSle=p,δ1).In
thisconfigurationPBSiz,0.2=PBSiz,0.4=PCSiz.

forOCBALL,whileKN++losesefficiencyforδ∗=0.4.Onthetargetplot
(rightpanel),thetargetperformanceofbothproceduresisaffectedbyδ∗.
Overall,thePGSSlep,δ∗stoppingruleisclosertothetargetthanKN++,
whichverymuchoverdeliversineachcase(thecurveforδ∗=0.2isalmost
plot).theidesout

RPI1Onequestioniswhethertheδ∗oftheselectionprocedurecanbeselectedin
acleverwaytoachieveagivendesiredperformancefortheprobabilityof
agoodselection.Figure2.26illustratestheinfluenceofδ∗onthePGSiz,0.2
efficiencyofKN++andOCBALL(PGSSlep,δ∗).ForRPI,settingtheproce-
dure’sparameterδ∗totheδ∗asspecifiedintheefficiencygoal(0.2)yields
reasonable,thoughnotoptimal,efficiencyforbothprocedures.Thetarget
performanceisgoodforOCBALL(PGSSlep,δ∗),whileKN++significantly
overdelivers(seeFigure2.17,rightpanel).
Figure2.28extendsthisobservationbylookingatdifferentδ∗,butalways
keepingtheδ∗parameteroftheprocedureequaltotheδ∗usedtomeasureeffi-
ciencyortargetperformance.TheleftpanelshowsthatOCBALL(PGSSlep,δ∗)
ismoreefficientforPBSiz,δ∗thanKN++forallsettingsofδ∗,whilethe
rightpanelshowsthatOCBALL(PGSSlep,δ∗)followsthetargetbetterthan
KN++.Thecombinedeffectoflowerefficiencyandoverdeliveryisvisualized
56

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.26:Influenceofδ∗onthere-Figure2.27:Numberofsamplesused
aquireddesirednumPBbSeriz,0of.2=samα∗plesfortoKNobta+in+bdepyeOnCdBAonLLthe(PGSsettingSlep,δo∗f)paraandKmeterN+α+∗
taandlOlinesCBAshoLLwt(PGSheSlnepum,δ∗b).erofHorizosam-n-(RPI1,k=5,η=1,α=100).
asplesreqreferenceuiredby(RPI1,OCBkA=LL5,(EOCη=Bonf1,)
0).10=α

inFigure2.27,whichshowsthenumberofsamplestakendependingonthe
parameterα∗,againforthreedifferentδ∗configurations.Forexample,ifδ∗=
0.4andadesiredaccuracyofα∗=0.01ischosen,OCBALL(PGSSlep,δ∗)usesa
totalof57samples,whileKN++uses161.Bothmethodsdeliveratleastthe
desiredtargetaccuracyinthisexample,althoughforOCBALL(PGSSlep,δ∗),
thisisnottrueforallsettingsofα∗andδ∗(seeFigure2.28rightpanel).
SomeotherobservationsfromSCandMDMalsocarryovertoRPI:The
Bayesianproceduresaregenerallyquitesensitiveton0,whileKN++isnot
(Figure2.29),andKN++becomeslessefficientrelativetotheBayesian
proceduresasthenumberofsystemskincreases(Figure2.30).
Figure2.31showsthatthebenefitofincludingpriorinformationinthe
VIPandOCBAproceduresismoreorlessindependentofαandηforthe
sted.etaluesv

RPI2InSection2.5theparagraphon”‘RandomProblemInstances2”’statesthat
mostobservationsmadeforRPI1carryovertoRPI2eveninthecaseof
57

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.28:PBSiz,δ∗efficiencyandtargetforOCBALL(PGSSlep,δ∗)and
KN++fordifferentsettingsofδ∗(RPI1,k=5,η=1,α=100).

Figure2.29:Influenceofn0ontheFigure2.30:Efficiencydependingon
efficiencyofOCBALLandKN++thenumberofsystemsk(RPI1,η=
(RPI1,k=5,η=1,α=100).1,α=100).

Figure2.31:Benefitofprovidingpriorinformationdependingonproblem
configurationparametersα,η(RPI1,k=5,α=100,unlessspecifiedother-
.)wise

58

2.SelectingaSelectionProcedure

2.5EmpiricalResults

Figure2.32:Efficiency(left)andtarget(right)forEqualallocationand
differentstoppingrulesw.r.t.EOCiz(RPI2,k=5,a=1,η=1,α=100).
ForPGSSlep,δ∗stopping,β∗isapproximatedbyα∗δ∗

a=1,i.e.manygoodsystems.Someevidenceforthisclaimisgivenbelow.
Figure2.33showsthatthemainconclusionsaboutallocationrulesalso
holdforRPI2.TheLL,OCBALLandOCBAδ∗allocationsaremoreorless
equallyefficient.Procedures0-1andEqualareclearlylessefficient.
TherelativeorderingofthestoppingruleswithrespecttoEOCizeffi-
ciencyincombinationwiththeEqualallocationremainsthesame:PGSSlep,δ∗
ismoreefficientthanEOCBonfwhichismoreefficientthanSstoppingrule
(Figure2.32).Figure2.34comparestargetplotsforRPIwithnegativeex-
ponential(RPI2,a=1),Gaussian(RPI1)andpositiveexponential(RPI2,
a=0)distributionofthemeans,intheorderofdecreasingnumberofgood
systems.Ifthesamplingdistributionforthemeansmatchesthetypeof
priordistributionusedfortheBayesianprocedures,thetargetismatched
closely.Modifyingthedistributiontowardsmoregoodsystems(negativeex-
ponential)orfewergoodsystems(positiveexponential)leadstoover-and
underdelivery,respectively.

ImplementationIssuesFigure2.35comparesOCBAδ∗andOCBAmax,δ∗
withboththePGSSlep,δ∗andPCSSlep,δ∗stoppingrules.Theresultistypical,
namelythatOCBAδ∗isthebetterallocationandPGSSlep,δ∗isthebetter
rule.gstoppinWenowturntotwoimplementationissues.[Chen,Y¨ucesan,Dai,and
Chen2005]wrotethattheefficiencyofOCBA(S)wasnotsignificantlydiffer-
59

2.5EmpiricalResults

2.SelectingaSelectionProcedure

Figure2.33:PBSiz,δ∗efficiencyofal-Figure2.34:Influenceofthesampling
klo=cat5,ionsa=with1,ηS=1,stoppinα=g10rule0).(RPI2,getdistribut(RPI1,ionsRofPI2,configk=urat5,ηions=1on,αtar-=
100,Equal(EOCBonf)).

Figure2.35:Differentwaystouseδ∗(RPI,k=5,η=1,α=100).

60

2.SelectingaSelectionProcedure

cussionisD2.6

apprFiguroex2.3imatio6:nAlloisascatioefficiennwithtast,Normabutl(W&FigurPe)2.37degr:eeofWilsonfreedomandPcorrreitskctioer’sn
Norcientmal(SC,fork=2,stoppingδ=r0.ule5,ρis=less1).effi-w(SC,asknot=2,morδe=0.efficie5,ρnt=t1).hanWelch’s

entwhetheratoranormaldistributionisusedforEAPCSi(bysubstituting
inthesamplevariancefortheunknownactualvarianceintoanormaldistri-
butionversionofEAPCSi),butdidnotpublishresults.Figure2.36confirms
thoseclaimsandgeneralizestootherstoppingrules.Anormaldistribution
intheallocationisdenotedOCBAGaussian.Ontheotherhand,usinganormal
distributionforthestoppingrule(PCSSlep,Gaussian)doesdegradeperformance.
Theprobablecauseisthatabsolutevaluesareimportantforstopping,but
forallocation,relativevaluesfordifferentsystemsarecompared.
Arefinedestimatorofthedegreesoffreedomthatgavegoodconfidencein-
tervalcoverageforqueueingexperimentswithsmallnumbersofobservations
([WilsonandPritsker1984])didn’timproveuponWelch’sapproximationfor
theSCinFigure2.37.Theassociatedtargetplotgaveasmall(statistically
significant)decreaseinPCSizforW&PrelativetoWelch.

onscussiDi62.

ChoicesregardingIZguarantees,probabilityofcorrectselectiongoals,or
expectedopportunitycostgoalsmakeapracticaldifferenceintheperfor-
manceofselectionprocedures.Thenewexperimentalsetup(randomprob-
leminstancesaswellasstylizedconfigurations)andmeasurementdisplays
(efficiencyandtargetcurves,asopposedtotabularresultsofPCSizandthe
61

cussionisD2.6

2.SelectingaSelectionProcedure

numberofreplications),provedusefulforassessingthevolumesofdata,and
foridentifyingstrengthsandweaknessesofprocedures.
Forafixedbudgetconstraintonthenumberofsamples,e.g.duetoproject
deadlines,ProceduresLL(S),OCBALL(S)andOCBAδ∗(S)weremosteffi-
t.cienIntheabsenceofafixedbudgetconstraint,theresultsdependonthe
problemclass.ForSCandMDMconfiguration,LLandOCBALLtogether
withtheEOCBonfstoppingruleweregenerallythemostefficient.KN++
andWaldwerealsoveryefficientwhenk=2,withsimilarvariancesand
lowPICSvalues.Proceduresbasedonanindifferencezone(KN++,Wald
andPGSSlep,δ∗stoppingrule)wereverysensitivetotheparameterδ∗.While
KN++andWaldfollowedthetargetverywellfortheSCwhenδ∗=δ,the
differenceδinthebestandsecondbestisusuallyunknown,sothisdoesn’t
helpinpractice.NoprocedurewasparticularlycontrollablefortheSCand
tions.nfiguracoMDMAnarbitraryconfigurationencounteredinpracticeisnotlikelytobestyl-
izedlikeSCorMDMconfigurations.Whenconfigurationsarerandomized
(RPI1andRPI2),thePGSSlep,δ∗andEOCBonfstoppingrulescanbeconsid-
eredtobereasonablycontrollableforadesiredPGSiz,δ∗andEOCiz,respec-
tively.ForRPI,anindifferencezoneseemsimportantforefficiency.Proce-
duresLL(PGSSlep,δ∗),OCBALL(PGSSlep,δ∗)andKN++werethemosteffi-
cient,withOCBAδ∗(PGSSlep,δ∗)stronglycompetitiveforPGSiz,δ∗efficiency.
ProcedureKN++tendstooverdeliverandisnotcontrollableforPGSiz,δ∗in
RPIexperiments.ThecurrentimplementationofWald’sprocedurecannot
berecommendedformorethan2systems.
StrengthsofKN++includealowsensitivitytothenumberoffirststage
samples(n0),anditsnaturalabilitytoaccountforcorrelatedoutput.Itis
theonlymethodtestedherewithaprovenasymptoticguaranteeforPCSiz≥
1−α∗,ifthatisdesiredratherthanPCSiz=1−α∗.Thepotentialcostof
thatpreferenceisstrongconservativenessandlackofcontrollability.
WesuggestcombiningtheBayesianallocationprocedureswithanadap-
tivestoppingruletosubstantiallyimproveefficiency.Independentofthe
stoppingrule,theloss-basedallocationsLLandOCBALLareamongthe
62

2.SelectingaSelectionProcedure

2.7FutureWork

mostefficientallocations.Themostefficientandcontrollablestoppingrule
dependsonthedesiredgoal(EOCBonforPGSSlep,δ∗).Thestrongefficiency
isrelativelyrobustw.r.t.differentconfigurations,andcontrollabilityisrel-
ativelyrobustforRPI.Theseproceduresalsoallowfortheincorporation
ofpriorinformationaboutprobleminstanceswhenthatisavailable.Weak
pointsofthoseproceduresareadependencyontheinitialnumberofsamples
foreachsystem,n0,andthepotentialforasmalldegradationinperformance
iftherearemanysystemsthatareclosetothebest.
ExperimentsshowedthattheBonferroniandWelchapproximationsused
byLLarealesssignificantsourceofpotentialsuboptimalitythanthegreedy
one-steplookaheadEVIproceduresderivedhere(LL1,0-11).Thosenew
proceduresarenotrecommendedforgeneraluse,norareEqualand0-1.
Thereareseverallimitstoourstudy.Wedidnottesttheeffectofauto-
correlationfromsteady-statesimulations,butdonotseewhybatchingwould
affectoneproceduredifferentlythananother.Wedidnottestcommonran-
domnumbers(CRN),atechniquethatcansharpencontrastsbetweensys-
tems.AstrengthofKN++isthatitcandirectlyaccountforCRN.CRN
canbeaccountedforintheOCBA[Fu,Hu,Chen,andXiong2005]andVIP
[ChickandInoue2001a]frameworks,butmoreworkremains.Thisthesis
assumedthatthenumberofsamplesdeterminesefficiency,butthemean
CPUtimeofdifferentsystemsmaydifferingeneral.ThederivationofLL
accountsfordifferentCPUtimes,andtheOCBAisamenabletodifferent
samplingcoststoo.Two-stageproceduresarepreferredinsomecontexts.
[Inoue,Chick,andChen1999]suggeststhatLLrunsveryeffectivelyintwo
stages.TheEOCBonfstoppingrulecanbeadaptedtotwostagesbyfinding
asecond-stagesamplingbudgetthatachievesadesiredpredictedEOCBonf.

2.7FutureWork

2.7.1RemovingapproximationsinOCBA
TheOCBAproceduresarebasedontheassumptionthatthemeanand
varianceestimateswillnotchangeforafewadditionalsamples.Withthe

63

2.7FutureWork

2.SelectingaSelectionProcedure

conjugateandnoninformativeposteriorpredictivedistributionsforasingle
observableXigivenin[BernardoandSmith1994]theposteriordistribution
ofAPCSiforτiadditionalsamplescanbeestimated.
ni−1
p(Xi|xijwithj=1,...,ni)=Stx¯i,2,ni−1,(2.28)
(ni+1)si
wherethemeanandvarianceareE[Xi]=x¯i,Var[Xi]=nnii−+13si2.The
updatedstatisticsincludingτinew,yetunknownvaluesXiareni=ni+τi
independentofXi,x¯i=n+1τ(nix¯i+τiXi)andsi2=n+τ1−1[(ni−1)si2+
nix¯i2+τiXi2−n+1τ(nix¯i+τiXi)2].Theirexpectedvalueswithrespect
iiiiii
tothedistributionofXiareEXi[x¯i]=x¯i,EXi[si2]=nn+iτ−1−1si2.
iiAPCSiisafunctionofXi.TheideaofOCBAistoevaluatethesystem
thathasthebestPCSSlepafterdrawingXi,sowechoosethesystemthat
maximizesEXi[APCSi].OCBAapproximatesEXi[APCSi]=APCSi(E[Xi]).
Abetterapproximationshouldbegivenbythesecondtaylorpolynomial(see
)97]19[Rinnee.g.

EXi[APCSi]≈APCSi(E[Xi])+Var[Xi]∂∂X2i2APCSi(E[Xi])
RemovingthisapproximationinOCBAshouldmaketheallocationmore
stableintheearlyphaseoftheprocedure,whereestimationofthemeans
andespeciallythevariancesarestillunstable.

2.7.2ImprovingStoppingRulesforBayesianProce-
sdure

ThestoppingcriteriaPGSSlep,δ∗andEOCBonfarerealizationsofBrownian
motionprocesseswithanexponentiallydecreasingdrift.
Currentlytheproceduresstop,iftheobservedvaluefallsbelowagiven
bound.Twoproblemsmayarise:1)Theruleistooconservative,i.e.the
currentdecisioniscorrect,buttheruledoesnotindicatetostop.2)The
ruleistoooptimistic,i.e.therulestopsalthoughthedecisioniswrong.
TheBayesianprocedureswithadaptivestoppingruleshaveacurvature

64

2.SelectingaSelectionProcedure

2.7FutureWork

forlowvaluesofPBSiz,δ∗andastrongdependenceonn0indicatingthatat
leastproblem2isrelevant.Apartoftherunsstoptooearlyandmakeerrors
thatcannotbecorrectedanymore.Oneimprovementwouldbetoaddan
uncertaintyestimatorinthestoppingrule,sothattheprocedurestops,ifit
iscertainthatthePBSiz,δ∗isbelowagivenbound.

2.7.3NonnormalDistributions
Theprocedurespresenteduptonowarebasedontheorderprecedence
relationXY:<=>E(X)<E(Y).Theycanbeapplied,iftheex-
pectedvaluesexist.Fromapractionist’spointofview,theseprocedures
mightrunintotroubles,ifthevariancesareverylargeorthedistributions
arestronglyskewed.Ifbatchingseveralreplicationsdoesnotleadtosuf-
ficientlyGaussiandistributedreplications,thereexisttwostatisticaltests,
whichhelpinthecaseofstronglynonnormaldistributions:Therankedt-
testandWilcoxon’ssignedt-test.Theyarebasedontheprecedencerelation
XY:<=>P(X<Y)>P(X>Y).Therandomvariablewhichdelivers
alowervaluemoreoftenispreferred.
Forsymmetricaldistributionsthisprecedencerelationisequivalenttothe
expectedvalueprecedencerelation.Adecisionmakerwillingeneralbasehis
decisionsontheexpectedvalue3.Butifthedistributionofthesimulation
outputsdonothaveaGaussian-likedistributionatall,onemightbeforced
tochangetotheorderbasedprecedencerelation.

2.7.4Non-IndependentSimulations
Manysimulationsusedinpracticearesteady-statesimulations,wherethe
outputsarenotindependent,butdependent,i.e.theoutputsofasimulation
areinfluencedbypreviousoutputs.
Anothersourceofnon-independentsimulationsariseswiththeuseofvari-
ancereductiontechniqueslikeantitheticrandomvariables,LatinHypercube
SamplingorQuasiRandomNumbers.
3risk-aversedecisionmakerswillbasetheirdecisionontheexpectedutility

65

2.7FutureWork

2.SelectingaeSlectionProecedurKimandNelsonsuggesttocombineseveraloutputstoabatch,andtreat
thebatchedvaluesasapproximatelyindependent.Ignoringtheexistenceof
non-independentsimulationsleadstoanunderestimationofthevarianceand
thereforetotooearlystoppinginstatisticalselection.
Theuseofcommonrandomnumbers(CRN)betweensystemsintroduces
anotherdesiredcauseofdependence.Ingeneraltheprocedurespresented
workinthepresenceofCRN,butwillbetooconservative.Theefficiency
mightbeimprovedbyestimatingthecorrelationandcalculatingPGSSlep,δ∗
withtheformulasgivenin[GenzandBretz2002].KN++alreadyallowsfor
CRN.Theincorporationofvariancereductiontechniquesisonepromising
areaforfurtherresearch.

66

erChapt3

IntegratingStatisticalRanking
intotheEvolutionary
Framework

EvolutionaryAlgorithms(EA)areiterativeandprobabilisticsearchalgo-
rithmsthatmakeuseofDarwinianevolutiontofindgoodsolutionstodif-
ficultoptimizationproblems.Ineachiteration(“generation”)fromaset
ofsolutions(“population”)someindividualsareselectedasparents(“selec-
tion”or“matingselection”).Theseparentsarerecombinedbycrossoverand
mutatedtoproducenewoffspring(“reproduction”).Theoffspringreplaces
someorallindividualsfromtheoldpopulationtoformanewpopulation
(“replacement”or“environmentalselection”).Betteror“fitter”solutions
haveeitherahigherprobabilityofbeingselectedasparents,orofsurviving
tothenewpopulation,orboth.Inthesearchprocess,goodcharacteris-
tics(buildingblocks)emergeinthepopulation.ThecourseofanEAwith
it’sthreephases(selection,reproduction,andreplacement)canbeseenin
.1.3eFigurAftereachgeneration,somestatisticsofthenewpopulationarecalcu-
lated,likebest,meanandvarianceofthefitnessvaluesinthepopulation
orthediversityofthepopulation.Thesearchstopsifoneofthestatistics
fulfillsacertaincriterion,e.g.thediversityorfitnessvarianceislow.Other

67

3.IntegratingRankingintoEA

Figure3.1:Schemaoftheevolutionaryframework

stoppingcriteriaareamaximalnumberofiterations,evaluationsortime
overallorwithoutimprovementinthebestsolution’sfitness.Whenusing
anEAinteractivelythealgorithmcanbestoppedbythedecisionmaker,as
soonassheissatisfiedwiththeresult.Ifthereplacementoperatorensures
thatthebestsolutionalwayssurvives,thenthebestsolutionfromthelast
solutionisreturnedas“thesolution”.Ifnot,thebestsolutionfoundsofar
issavedexternallyandreturnedintheend.
AninstanceofanEAisdeterminedbythechoiceofaselectionoperator,
recombinationoperators,areplacementoperator,andeventuallybyastop-
pingcriterion.Inthefollowing,thenumberofindividualsinthepopulation
isdenotedbyp,thenumberofselectedparentsbymandthenumberof
offspringbyo.IntheEAliteraturenormallyµandλarechosenforthe
populationandoffspringsize.Wechangedthenotationtopreventconfu-
sionwithmeanandprecisionfromthepreviouschapter.Someexamplesof
algorithmsthatfitintothisschemearegivenbelow.

EvolutionStrategiesA(p,m)-EvolutionStrategyselectsmparentsfrom
thepopulationofsizep(withreplacement)withequalprobability,mutates
eachparenttoproducenewoffspringandthenthepbestoffspringforma
newpopulation.A(p+m)-EvolutionStrategyselectsthepbestoutofthe

68

3.IntegratingRankingintoEA

offspringandtheoldpopulation.

GenerationalEAGenerationalEAhaveapopulationofsizep.Todeter-
minetheparents,ptournamentsofseveralindividualsaremadeandthewin-
nerofeachtournamentisselected.Twoparentsarecombinedbycrossover
andmutationtoformtwonewoffspring.Allpoffspringreplacetheparent
generation.OftengenerationalEAarecombinedwithelitism,whichmeans
thatthereplacementismodifiedsuchthattheoffspringreplaceallindivid-
ualsfromtheoldpopulationexceptthebest.

Steady-StateEASteady-StateEAhaveapopulationofsizep,too,but
onlytwoparentsareselectedpergenerationtoformonlyonenewoffspring
bycrossoverandmutation.Thenewoffspringreplacestheworstindividual
intheoldpopulation.

IslandEAAnIslandEAconsistsofseveralindependentpopulations.The
populationsinterchangeindividualsfromtimetotime(migration).Innon-
migratinggenerations,theislandsbehavesimilarlytoindependentEA.Dur-
ingmigration,anadditionalselectionoccursoneachislandtoselectthein-
dividualstomigratetotheotherpopulations,wheretheyreplacetheworst
ls.individua

SimulatedAnnealingEvenSimulatedAnnealingandLocalSearchare
coveredbythisframework:Thepopulationisofsizeone,thereforethese-
lectionistrivial.Therecombinationoperatorproducesanoffspringinthe
neighborhoodoftheparentandthenreplacestheparentifit’sfitnessis
higherorinthecaseofSimulatedAnnealingreplacestheparentevenfor
lowerfitness,butwithdecreasingprobability.
Thealgorithmsgivenabovearejustsometypicalconfigurations.In
practiceseveralfurthervariantsexist.Anoverviewisgivenforexample
in[MichalewiczandFogel1999].

69

3.1RelatedWork

3.1RelatedWork

3.IntegratingRankingintoEA

Manyreal-worldoptimizationproblemsarenoisy,i.e.asolution’squality
(andthusthefitnessfunction)isarandomvariable.Examplesincludeall
applicationswherethefitnessisdeterminedbyarandomizedcomputersimu-
lation,orwherefitnessismeasuredphysicallyandpronetomeasuringerror.
Alreadymanyyearsago,researchershavearguedthatEAshouldberela-
tivelyrobustagainstnoise([FitzpatrickandGrefenstette1988]),andrecently
anumberofpublicationshaveappearedwhichsupportthatclaimatleast
partially([MillerandGoldberg1996;ArnoldandBeyer2000a;Arnoldand
Beyer2000b;ArnoldandBeyer2003]).Arecentsurveyonthistopicis[Jin
andBranke2005].
Formostnoisyoptimizationproblems,theuncertaintyinfitnessevalu-
ationcanbereducedbysamplinganindividual’sfitnessseveraltimesand
usingtheaverageasestimateforthetruemeanfitness.Samplingntimes
reducesarandomvariable’sstandarddeviationbyafactorof√n,butonthe
otherhandincreasesthecomputationtimebyafactorofn.Thus,thereis
agenerallyperceivedtrade-off:eitheronecanuserelativelyexactestimates
butonlyevaluateasmallnumberofindividuals(becauseasingleestimate
requiresmanyevaluations),oronecanletthealgorithmworkwithrelatively
crudefitnessestimates,butallowformoreevaluations(aseachestimate
requireslesseffort).
TheapplicationofEAinnoisyenvironmentshasbeenthefocusofmany
researchpapers.Thereareseveralpaperslookingatthetrade-offbetween
populationsizeandsamplesizetoestimateanindividual’sfitness,withsome-
timesconflictingresults.[FitzpatrickandGrefenstette1988]concludethat
forthegeneticalgorithmstudied,itisbettertoincreasethepopulationsize
thantoincreasethesamplesize.Ontheotherhand,[Beyer1993]shows
thatfora(1,o)evolutionstrategyonasimplesphere,oneshouldincrease
thesamplesizeratherthano.[HammelandB¨ack1994]confirmtheseresults
andempiricallyshowthatitalsodoesn’thelptoincreasetheparentpopula-
tionsizep.Finally,[ArnoldandBeyer2000a;ArnoldandBeyer2000b]show
analyticallyonthesimplespherethatincreasingtheparentpopulationsize

70

3.IntegratingRankingintoEA

3.1RelatedWork

pishelpfulincombinationwithintermediatemulti-recombination.[Miller
1997]and[MillerandGoldberg1996]havedevelopedsomesimplifiedthe-
oreticalmodelswhichallowtosimultaneouslyoptimizethepopulationsize
andthesamplesize.AgoodoverviewoftheoreticalworkonEAappliedto
noisyoptimizationproblemscanbefoundin[Beyer2000]or[Arnold2002].
Allpapersmentionedsofarassumethatthesamplesizeisfixedforallin-
dividuals.[AizawaandWah1994]wereprobablythefirsttosuggestthatthe
samplesizecouldbeadaptedduringtherun,andsuggestedtwoadaptation
schemes:increasingthesamplesizewiththegenerationnumber,andusing
ahighersamplesizeforindividualswithhigherestimatedvariance.[Albert
andGoldberg2001]lookataslightlydifferentproblem,butalsoconclude
thatthesamplesizeshouldincreaseovertherun.For(p,o)or(p+o)selec-
tion,[Stagge1998]hassuggestedtobasethesamplesizeonanindividual’s
probabilitytobeamongthepbest(andthusshouldsurvivetothenextgen-
eration).[HedlundandMollaghasemi2001]useanindifference-zoneselection
proceduretoselectthebestpoutofoindividualswithinageneticalgorithm.
Fortournamentselection,[BrankeandSchmidt2003;BrankeandSchmidt
2004]and[Cantu-Paz2004]usesequentialsamplingtechniquestoreducethe
numberofsamplestotheminimumrequiredtodiscriminatebetweenindi-
vidualsinatournament.Adaptivesamplingstrategieshavebeenexamined
forsituationswherethenoisestrengthvariesoverspace([DiPietro,While,
andBarone2004]).[Boesel1999]arguesthatforlinearrankingselection,
itissufficienttogroupindividualsofsimilarqualityintoonerank,anda
correspondingmechanismisproposed.
To“cleanup”afteroptimization(toidentifythebest,withhighproba-
bility,ofallvisitedsolutions),[Boesel,Nelson,andKim2003b]usearanking
andselectionprocedureaftertheEAisfinished.Recently,[Buchholzand
Th¨ummler2005]usedastatisticalselectiontechniqueforselectioninap+o
strategyaswellastomaintainapoolofpromisingcandidatesthroughout
therunfromwhichattheendthefinalsolutionisselected.
Noneoftheaboveworksprovidethegeneralframeworkandtightinte-
grationofselectionalgorithmsandEAthatissuggestedhere.
Acomprehensiveoverviewandextensivecomparisonofdifferentselection

71

3.2StatisticalRanking

3.IntegratingRankingintoEA

procedureswasgiveninChapter2,whichconcludesthatOCBAtogether
withanappropriatestoppingruleisamongthebestperformingstatistical
selectionprocedures.OurapproachforadaptingEAonnoisyproblemsis
basedonOCBA.

3.2AStatisticalRankingProcedure

Ingeneral,thereproductionoperatorsareindependentofanindividual’sfit-
ness1.So,bynoise,onlyselectionandreplacementoperatorsareaffected.
Generallyrankbasedselectionandreplacementoperatorsareconsideredto
performbetterthanfitnessproportionalones(see[Whitley1989]).Ifwe
defineacorrectfunctioningoftheEAasmakingthesameselectionand
replacementdecisionsasinthedeterministiccase,onlytheranksofindivid-
ualsintheunionofthesetofoffspringandthesetofindividualsintheold
populationneedtobedetermined(inthiscontextthesetscanhavedupli-
cates,sotheyarenotsetsinthemathematicalsense,butfamilies).Inthe
deterministiccase,theorderingofallindividualscanbegiveneasilyafter
theevaluationofeachindividual.Inthestochasticcase,theorderingcan
onlybegivenwithacertaindegreeofcertainty.Notethatafterreproduction
thepindividualsfromtheoldpopulationhavealreadybeenevaluatedsev-
eraltimes,whereastheooffspringarenotyetevaluated.Theproceduresin
Chapter2canbeusedrepeatedlytoobtainthep+oranksofeachindividual
onebyone,butthismightbeveryexpensiveintermsofsamples.Notall
procedurescanbenefitfrompreevaluatedsystems.
Inthissectionwederiveaprocedureforthecompleterankingofaset
ofindividuals.Letthesizeofthissetbek.Analogouslytotheprobability
ofcorrectorgoodselection(PCS,PGS)andtheexpectedopportunitycost
(EOC),lettheprobabilityofcorrectorgoodranking(PCR,PGR)andthe
1muExtationceptiandonssomearekinmedsmeticofevalolugorithtionmstrats,ewhgiesich,waddherehilltheclimmubingtationafteitserrlfeiscombbiasedinatitoonwardsand
prlatteromiscinaseg,ofareastenofthethesestimateearchsfspaceortheandfitnenotssvalonlyuesselefromctiontheandselec/ortionpreplacemhasesenut.fficeF.orThethe
evmealchaniuationsmspresneedenedted.forthehillclimbinginthefirstcasewillnotbeintegratedintothe

72

3.IntegratingRankingintoEA

3.2StatisticalRanking

expectedopportunitycostofaranking(EOCR)forthefrequentistperspec-
tive(IZ),giventheconfigurationχ=(µ,σ2)bedefinedas

kdefPCRiz=Prµ(i)=µ[i]|χ
=1ikdefPGRiz,δ∗=Prµ(i)≥µ[i]−δ∗|χ
=1ikEOCizRank=defEµ[i]−µ(i)|χ(3.1)
=1iandtheBayesianperspective,giventhedataseensofarE,respectively

kdefPCRBayes=PrM(i)≥M<i;k>|E
=1ikPGRBayes=defPrM(i)+δ∗≥M<i;k>|E
=1ikEOCBaRankyes=defEM<i;k>−M(i)|E,(3.2)
=1iwhereM<i;k>denotesthei-thorderstatistic2,(i)theorderbasedonthe
observedmeansx¯iand[i]theorderbasedontruemeansµi.TheOCBA
procedurescaneasilybeadoptedfortherankingproblem,giventheapprox-
imationstotheBayesianmeasuresaboveandthestochasticdominanceof
maxj<iM(j)M<i;k>3,

2Thei-thorderstatisticisthedistributionofthei-thbestvalueoutoftheobservations
ofkrandomvariables([Rinne1997]).
3maxj<iM(j)isjustonecombinationoutofallpossiblecombinationsforthei-thorder
statistic,soPr(maxj<iM(j)≤x)<Pr(M<i;k>≤x)∀x
73

3.2StatisticalRanking

3.IntegratingRankingintoEA

kPGRBayes≥PrM(i)+δ∗>M(j)|E(3.3)
i<j=1ik≈Φν(i)(j)(λ1ij/2(δ∗+d(i)(j)))=PGRSlep,δ∗
i<j=1ikEOCBaRankyes≤EM(j)−M(i)|M(j)>M(i)(3.4)
i<j=1ik≈λij−1/2Ψν(i)(j)d∗ij=EOCBonfRank.
i<j=1iWedenotetheOCBAprocedurebasedonPGRSlep,δ∗-allocationOCBAδ∗Rank
andonEOCBonfRank-allocationOCBALLRank.PICRandPBRdenotetheproba-
bilitiesforincorrectandbadrankingsanalogouslytothedefinitionsinChap-
ter2.PGRSlep,δ∗andEOCBonfRankcanbeusedasstoppingrules,too.Further-
more,OCBAcanbenefitfrompreevaluatedindividuals,whichwedohave
fromtheoldpopulationasnotedabove.
Figure3.2showsthatefficiencyandtargetfortherankingvariantof
OCBAareworsethanOCBAfortheselectionproblem–whichwasexpected,
becausetheproblemoffindingacorrectrankingincludestheproblemoffind-
ingthebestsolutionasasubproblem.Nevertheless,OCBAδ∗Rank(PGRSlep,δ∗)
andOCBALLRank(EOCBonfRank)allowtodetermineacorrectrankingwithhigher
efficiencythanequalallocationandallowtoadaptthenumberofsamples
foragivenerrorprobability.
ActuallyanEAdoesnotneedacompleterankingforthecorrectfunc-
tioning.Itsuffices,ifonlyacertainsetofcomparisonsarecorrect,indepen-
dentlywhetherallranksarecorrect.DenotethissetofcomparisonsbyC.
Whichcomparisonsareneededdependsonthechosenselectionandreplace-
mentoperatorsoftheEA.Acomparisonisgivenbythetuplei,j,where
∀i,j∈C:i,j∈{1,...,k}∧i=j.Iftheobservedrankofindividuali
ishigher/lowerthanthatofindividualjandiistrulybetter/worsethanj,
thenthecomparisoni,jiscorrect.
74

3.IntegratingRankingintoEA

3.3ReplacementOperators

RankforFigur10esy3.2st:ems,Efficieequallyncyandtspacedarget(δfor=0O.C5)BaAndδ∗equa,OlCvBaAriance.andEqualallocation

Inthefollowingsections,wegivethenecessarycomparisonsthatneedto
beaddedtoCforsomepopularreplacementandselectionoperators.

3.3ReplacementOperators
Thereplacementstepdetermines,whichpindividualsoutofthek=p+o
individualsfromtheoldpopulationandtheoffspringmakeitintothenew
population.EachindividualcanbeatmostonceinthenewpopulationP4.
TheindividualsintheoldpopulationarenumberedP={1,...,p}andthe
offspringO={p+1,...,k}.ThenewpopulationisatruesubsetP⊂
{1,...,k}.Theorder(.)overallindividualsisdefinedbyx¯(1)≤...≤x¯(k),
(.)Ooveralloffspringand(.)Poverallindividualsinthenewpopulation.
Theranks(.)−1aredefinedastheinversionoftheorder((r)−1=r).The
orders(i)Oand(i)Pcanbedeterminedfromtheoverallorder(.)byfinding
thei-thindividualhaving(j)∈Oor(j)∈Pforj=1,...,k.
3.3.1Comma-andPlus-Replacement
In(p,o)-and(p+o)-replacementsimplythepbestindividualsoutoftheo
offspringoroutofthep+oindividualsfromtheoldpopulationandoffspring
areselected.Typicallycomma-andplus-evolutionstrategiesmakeuseof
4Neverthelessweallowforindividualswithidenticalgenesinthepopulation
75

3.3ReplacementOperators3.IntegratingRankingintoEA

thisreplacementoperator,butsteady-stateEAuse(p+1)-replacementand
localortabusearchuse(1+1)-replacement,too.
Thesetoperationsfor(p,o)-replacementwitho>p≥1are
oC←C∪{(i)O,(1)O,...,(i)O,(o−p)O}
i=o−p+1
P={(o−p+1)O,...,(o)O},
for(p+o)-replacementwithp,o≥1
o+pC←C∪{(i),(1),...,(i),(o)}
+1o=iP={(o+1),...,(p+o)},
andarevisualizedinaTable3.1.
Indivi-IndividualjIndivi-Individualj
duali(1)...(o−p)O...(p)Oduali(1)...(o)...(o+p)
(1.)O(1.)
....(o−p.+1)O.×∙.∙∙.×(o.+1)×.∙.∙∙×.
................
(p)O×∙∙∙×(o+p)×∙∙∙×
“T×a”ble3means.1:tCohatmpartheisocompansforrisonbcommaetw-een(left)individuaandlsplus-iandreplajcisementneeded,(righi,t)j.∈A
C.offspringNote,thatwhileforforcoplus-remma-replaplacecmenementtforthetheoldcompapoprisonsulatioanreandonlytheaoffsmongpring.the

Plus-replacementensuresthatthebestsolutionfoundsofaralwayssur-
vivestothenextiteration,whilecomma-replacementwillreplaceit’sbest
solutioneveryiteration.

3.3.2CompleteReplacementandElitism
Generational-EAreplacetheoldpopulationcompletelybythepoffspring
produced,whereasgenerational-EAwithelitismonlyproducep−1offspring
76

3.IntegratingRankingintoEA3.4SelectionOperators

andreplaceallbutthebestintheoldpopulation.Withoutelitism,thebest
solutionfoundsofarmightgetlostandthusthegenerational-EAismostly
combinedwithelitism.
Forcompletereplacementnocomparisonsareneeded,thereforeCisnot
modifiedatallandthenewpopulationisthesetofthepoffspring

P={p+1,...,2p}.
Generational-EAwithelitismaddcomparisonsbetweenthebestandall
othersinthenewpopulation.Wedeterminetheeliteindividual(p)Pfor
thenextiterationinthecurrentiteration,sowecanbenefitfromother
comparisonsneededinthecurrentiterationduetoselection.Thenumberof
offspringgeneratedisp−1andtheelitistindividualis(p)P.
P={(p)P,p+1,...,2p−1}
1p−C←C∪{(p)P,(i)P}
=1i3.4SelectionOperators
Theselectionstepdetermineswhichmindividualsfromthenewpopulation
Pareselectedasparents.ThesetofparentsisdenotedMand,aseach
individualmaybeselectedseveraltimes,canhaveduplicates.
FortheselectionoperatorofanEAseveralimplementationsexist.The
rank-baseddetermineaprobabilityprfortheselectionofanindividualwith
rankr.Thisrankisdefinedwithrespecttothenewpopulationwithsize
p.Asnotallreplacementoperatorsselectthetoppindividualsoutofthe
ooffspringandpindividualsintheoldpopulation,therankusedforde-
terminationofindividuali’sselectionprobabilitydoesnotnecessarilyequal
(i)−−11.Insteadwedenotethenewranksrelatedtothenewpopulationby
(i)P.Onlycomparingindividualsiandjisnotaffectedbythenewranks,
as(i)P−1>(j)P−1followsdirectlyfrom(i)−1>(j)−1.So,onlyselectionoper-
atorsthatexplicitlyrelyontherankareaffected.
77

3.4SelectionOperators3.IntegratingRankingintoEA

Theexpectednumberoftimesanindividualiisselectedcanbecalculated
bymultiplyingp(i)P−1withthenumberofoverallselectionspergeneration
m.Ingeneral,selectionsareindependentofeachother,sothenumberof
selectionsfollowamultinomialdistribution.

3.4.1RandomSelection
Eachindividualhasthesameprobabilityofbeingselected.Thisoperator
isnormallyusedinEvolutionStrategies.Theoptimizationpressureisonly
introducedbythereplacementoperator.Theindividualsdonothavetobe
evaluatedforrandomselection,butcanbejustrandomlyselectedfromthe
populationPindependentlyofthefitness.
1=pipRandomselectionthereforedoesnotaddanycomparisonstoC,andMis
theresultofmrandomsamplesfromP.DenotearandomsampleofPby
thenπjM={π1,...,πm}.
Toapplystochasticuniversalsampling,eachindividualinPisselected
m/p-timesandtheremainingm−pm/pparentsaredeterminedbychoos-
ingrandomlyfromPwithoutreplacement,i.e.withoutduplicates.
3.4.2TournamentSelection
Tournamentselection(TS,see[Goldberg,Korb,andDeb1989])choosestwo
individualsrandomlyfromthepopulationPandselectsthebetterofthe
twoasparent.Thisselectionoperatorismostlyusedwithgenerational-and
steady-state-EA.Forgenerational-EAmparentsareselectedbymtourna-
mentselectionsandonlytwotournamentsareperformedtoselecttwoparents
forsteady-state-EA.
Avariantoftournamentselectionist-tournamentselection,wherethe
parentisdeterminedasthebestoutoftinsteadoftworandomlychosen
individuals.ThetindividualsarechosenfromPwithoutreplacement,sothat
78

3.IntegratingRankingintoEA3.4SelectionOperators

anindividualcannotparticipateinatournamentwithitself.Theselection
probabilityofindividuali∈Pwithrankris
p=r≥t:(r(−r−1)!t()!pp−!t)!t.
rr<t:0
Denotethechosenttournamentparticipantsoftournamentjbyπj1,...,πjt
andbyπj(i)theorderedtournamentparticipants,wherex¯πj(1)<...<x¯πj(t).
Thenthesetofcomparisonsisextendedasfollowsandtheselectedparents
ear

mC←C∪πj(t),πj(1),...,πj(t),πj(t−1)
=1jM={π1(t),...,π(mt)}
AnexampleofthecomparisonsfortournamentselectionisgiveninTa-
.2.3blejlIndividuaIndivi-duali(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)P(10)P
)(1P)(2P)(3P)(4P)(5P)(6P(7)××××
(8)PP×××××
)(9××(10)PP×××××
Table3.2:Comparisonsfor10randomlychosen3-tournaments({1,6,10},
{3,6,7},{3,7,9},{2,7,8},{3,6,7},{5,7,10},{2,5,7},{3,6,10},{3,7,8},
{{74,,76,,78,}8),,8,8,9assuming,10,10(,i)10P}.=i∈P.ThesetofparentsisM=
Localselectionisaselectionoperatorwherethebestindividualfroma
neighborhoodofsizetisselected.Forthestatisticalrankingprocedure,this
79

3.4SelectionOperators

3.IntegratingRankingintoEA

isjustaspecialformoft-tournamentselection,wherethetournamentpar-
ticipantsarenotchosenrandomly,buttheindividualsintheneighborhood.

3.4.3StochasticTournamentSelection
Stochastictournamentselection(STS,[GoldbergandDeb1991])isarather
simpleselectionschemewheretwoindividualsarerandomlychosenfromthe
population,andthenthebetterisselectedwithprobability(1−γ),γ∈
[0,0.5].Ifthepindividualsinthepopulationaresortedfromrankr=
1(worst)torankr=p(best),theexpectedprobabilityprtoselectan
individualwithrankrcanbecalculatedas
pr=p21−γ−(1−2γ)pp−−1r.
Thiscorrespondstoalinearlyincreasingselectionprobabilitydepending
onanindividual’srankr,withtheslopeofthelinebeingdeterminedbythe
selectionprobability(1−γ)(cf.Figure3.3).

Figure3.3:ExpectednumberofselectionsE[Sr]ofanindividualwithrankr
forp=100individualsandptournamentselections;STSforγ∈{0,0.1,0.2}
(left)andTSfort∈{2,3,5}(right).
Inthisrespect,STSisequivalenttolinearrankingselection.Butwhile
rankingselectionisbasedonafullorderingoftheindividuals,STSonly
requirespairwisecomparisonsandiseasiertoimplement.Foreachstochas-
tictournamentithecomparisonbetweentworandomlychosentournament

80

3.IntegratingRankingintoEA3.4SelectionOperators

participantsπi1andπi2isneeded.Theparticipantwiththehigherrank,indi-
vidualπi(2)isselectedwithprobability1−γandπi(1)withprobabilityγ.The
samebehaviorcanbeachievedbyselectingoneoftheparticipantsrandomly
withprobability2γandthebetterofthetwowithprobability1−2γ.Sofor
STSthefollowingcomparisonisrequiredonlywithprobability1−2γ.
mC←C{(πi(2),πi(1))}
=1iInChapter4amethodisgiventhatincreasestheaccuracyofSTSina
stochasticenvironmentbyusingthenoiseintheevaluationtoreplacepar-
tiallytherandomizationintroducedbyselectingthebetteronlywithproba-
bility1−γ.
3.4.4LinearRanking
Linearrankingselectsindividualrwithlinearlyincreasingprobabilityinr
pr=p12−t+2(t−1)r−1,
1p−

witht∈[1,2].
Tocalculatetheselectionprobabilitiesexplicitly,acompleterankingis
needed,butstochastictournamentselection(seeSection3.4.3)withγ=
0.5(2−t)implementsthesameselectionprobabilitieswithouttheneedofa
ing.rankcomplete

3.4.5ExponentialRanking
Forexponentialrankingtheselectionpressureishigherthanforlinearrank-
ing.Theselectionprobabilitiesareexponentiallydecreasingintherankr

pr=Z1cp−r

withc∈(0,1)andZ=11−−ccp.
Toexactlymatchthedesiredselectionprobabilities,thecompleteranking
81

3.4SelectionOperators3.IntegratingRankingintoEA

needstobedetermined.Ifanapproximationtotheselectionprobabilities
isacceptable,thenexponentialrankingcanbereplacedbyt-tournament
selectionwitht=p11−−ccp,whichonlyneedst−1comparisonsperselection.
3.4.6FurtherSelectionOperators
Truncationselectionselectsthemparentsrandomly(withreplacement)
amongthetbestindividualsfromthepopulation.Findingthetbestin-
dividualsneedsthefollowingcomparisons
pC←C{(i)P,(1)P,...,(i)P,(t)P}.
i=p−t+1
Selectionoperatorsthatneedanexplicitorderingofallindividualsina
populationareveryexpensive,intermsofevaluationsandshouldtherefore
beavoided.Neverthelessthecomparisonsaregiven
pC←C{(i)P,(1)P,...,(i)P,(i−1)P}
=1i3.4.7StochasticUniversalSampling
Oneofthedrawbacksoftournamentselectionisitspossiblyhighsampling
error:theactualnumberoftimesanindividualisselectedmaydiffersignif-
icantlyfromtheexpectednumberoftimes.Forexample,ifonewouldlike
toselectmparents,andtheprobabilitytoselectanindividualrispr,then
theexpectednumberoftimesthatindividualischosenisE[Sr]=m∙pr,
buttheactualnumbersrcanbeanywherebetween0andmfortournament
(TS).nctioseleSuchasamplingerrorisundesiredandisoftenalsocalledgeneticdrift.
Thesamplingerrorcanbeminimizedbyselectingtheparentsnotindepen-
dently,butinsteadusingamethodcalledStochasticUniversalSampling
(SUS,[Baker1987]).Ifpristheprobabilityforselectingindividualwith
rankr,thenSUSensuresthattheactualnumberofselectionssriswithin
[m∙pr,m∙pr].

82

3.IntegratingRankingintoEA3.5RankingProcedureforEA

TheeffectcanbeseeninFigure3.4,whichshowsthestandarddeviation
ofthenumberoftimesanindividualisselecteddependingonitsrankin
apopulationof100individuals.Ascanbeseen,thestandarddeviationis
muchlowerforSUSthanforthestandardrandomTS.
However,thestandarddeviationfort-TScanbereducedaswellbymak-
ingsurethateveryindividualparticipatesinexactlyttournaments,i.e.the
individualsforthetournamentsarenolongerchosenindependently,butare
generatedbylatinrectangles(see[Byers1991]).Hencethisselectionscheme
isdenotedlatinTS.LatinSTSisimplementedbyalatin2-TS,wherethe
firstparticipantischosenwithprobability2γandthebetterofthetwowith
probability1−2γ.
LatinTSandSTShaveexactlythesameexpectedbehaviorasthestan-
dardrandomschemes,butreducetheselectionvariancesignificantly,inpar-
ticularforthebetterindividuals(seeFigure3.4).Forworseindividuals,the
standarddeviationofallthreesamplingschemesisalmostequally.For2-TS,
latinTSandSUSareidentically(seedottedlineinleftfigure:thecrossesof
latinTSareinsidetheboxesofSUS),butforhigher(rightfigure)orlower
selectionpressure(γ=0.1,leftfigure)latinTSisnotabletoreducethe
standarddeviationintothedeepvalleysofSUSexceptforthehighestrank.
Nevertheless,thestandarddeviationforlatinTSisclearlybelowrandomTS
andalmostequaltoSUS.
Intheabovesections,itwasshownthattheselectionprobabilitiesof
mostrank-basedselectionschemescanbeachievedbytournamentselection.
Theuseoflatintournamentselectionallowstoreducethesamplingvariance
similarlytoSUSwithouttheneedforfurthercomparisons.

3.5AStatisticalRankingProcedureforEvo-
lutionaryAlgorithms

OneofOCBA’sadvantagesisitsflexibility.Itcanbeeasilyadaptedtonot
onlyselectthebestoutofagivensetofindividualsordetermineacomplete
ranking,butforarbitraryqualitymeasures.TointegrateitintoanEA,

83

3.5RankingProcedureforEA

3.IntegratingRankingintoEA

plingFiguresc3.4heme:sStaforpndard=10de0viatioindivnofidualsnumabnderpoftoseurnamenlectionstSrselecfortions;differeSTSntwithsam-
γ∈{0,0.1}(left)andt-TSwitht∈{3,5}(right).

wewanttomakesurethattheEAoperates“correctly”,meaningthatthe
orderrelationsrequiredbytheEA’sselectionandreplacementoperatorshave
beendeterminedcorrectlywithasufficientlyhighconfidence.Theprevious
sectionsexplainedhowtodeterminetherequiredsetofcomparisonsC.As
aqualitycriterion,wedefinetheprobabilityofgoodgeneration(PGGBayes)
asprobabilitythatallpairwisecomparisonsinCarecorrect.Thefollowing
equationapproximatestheprobabilitythatforallpairsinC,theindividual
withthehigherobservedrankalsohasahighertruemeanvalue.Itassumes
ranki>rankjforalli,j∈C.Ifrankj>ranki,simplyreplacei,jby
j,iinCbeforecalculation.

PGGiz,δ∗=defPrµi≥µj−δ∗|χ
i,jC∈EOCizGen=defE[µj−µi|µj>µi,χ]
i,j∈C
defPGGBayes=PrMi≥Mj−δ∗|E
i,jC∈EOCBaGenyes=defE[Mj−Mi|Mj>Mi,E].
i,jC∈84

.5)(3

.6)(3

3.IntegratingRankingintoEA3.5RankingProcedureforEA

NotethatthedefinitionsofEOCGenslightlydifferfromEOCandEOCRank.
Theyarebasedonthesumofthepairwiselossesandnottherankwiselosses.
AsforOCBAδ∗RankandOCBALLRank,theBayesianmeasurescanbeap-
proximatedbySlepianandBonferroniboundsandweobtaincriteriaforthe
OCBAδ∗EAandOCBALLEAvariantsofOCBAfortherankingneededforEA.

PGGBayes≥Pr(Mi+δ∗>Mj|E)
i,jC∈≈Φνij(λ1ij/2(δ∗+dij))=PGGSlep,δ∗
i,jC∈EOCBaGenyes≤E[Mj−Mi|Mj>Mi]
i,jC∈≈λij−1/2Ψνijd∗ij=EOCGenBonf.(3.7)
i,jC∈Theproceduresareoutlinedbelow.

ProceduresOCBAδ∗EA(α)andOCBALLEA(β)
1.Makeaninitialnumberofevaluationsn0ofeachindividualwithout
evaluationssofar.Estimatetheranksbyorderingtheindividualsbased
ontheobservedmeanvalues.
2.DetermineC:initializeC←∅andaddcomparisonsfromtheoperators
asgiveninSections3.3–3.4.
3.WHILEtheobservedresultsarenotsufficientlysure,i.e.PBGSlep,δ∗>
αorEOCGenBonf>β,DO

(a)AllocatenewevaluationstotheindividualswiththeOCBA-allo-
cationrule.IndividualsleavingthecurrentpopulationPdueto
newobservationsarereplacedbytheenteringindividuals.This
waycomparisonsbasedonpositioninP(liketournamentselec-
tion)othersthantheonedirectlyaffectedarenotchanged.
85

3.6EmpiricalEvaluation

3.IntegratingRankingintoEA

(b)Ifrankshavechangedfromthepreviousiterationoftheranking
procedure,updateC:initializeC←∅andaddcomparisonsfrom
theoperatorsasgiveninSections3.3–3.4.

OCBAδ∗EAiscalledineveryiterationoftheEAaftertheoffspringhasbeen
generatedandbeforereplacement.Then,theEAproceedssimplyusingthe
orderinggivenbythesamplemeans.
ThenumberofsamplestakenbyOCBAδ∗EAdependsontheproblemcon-
figurationandthesettingsofα∗andδ∗.Itmaybeusefultovaryα∗over
time,ashigheraccuracymaybeneededtowardstheearlyandlatephasesof
thealgorithm(cf.[Branke2001]).

3.6EmpiricalEvaluation

Weempiricallycomparedifferentsamplingmechanismsbasedontheirability
tominimize“incorrectiterations”oftheEA.Theproposedintegrationof
rankingandselectionwithEAneedsamoreexhaustiveevaluationinfuture
k.orwWestochasticallygeneratedk=10individualswithmeansdistributed
accordingtothenegativeofanexponentialdistributionwithmean1andvari-
ancesdistributedaccordingtoaninvertedgammadistributionwithα=100
andβ=99(Figure3.5).ThiscorrespondstotheRPI2configurationin
Chapter2.Suchadistributionwithmoregoodthanbadindividualsseems
commoninanEArun,atleasttowardstheendoftherun,whentheal-
gorithmproducesmanysolutionsclosetotheoptimum,andafewoutliers.
Toachievestatisticallysignificantresultsweaveragedover100,000suchran-
domlysampledpopulations.Thisisthesamenumberofmacroreplications
2.inelikWecomparethefrequentistprobabilityofagoodgenerationPGGiz,δ∗
dependingontheexpectednumberofevaluationsusedbydifferentproce-
dures.TocalculatePGGiz,δ∗,werunthesamplingmechanismandlookat
theresultingorderaccordingtosamplemeans.Ifalldecisionsrequiredby
thescenario(i.e.,thosedefinedbyC)havebeenidentifiedcorrectlytaking
86

3.IntegratingRankingintoEA

3.6EmpiricalEvaluation

Figure3.5:Empiricaldistributionofmeans(left)andvariances(right)for
theempiricaltests.

intoaccounttheindifferencezone,theruniscountedassuccessful.Other-
wise,itisnotsuccessful.PGGiz,δ∗isthepercentageofcorrectruns.The
parametersα∗andδ∗notonlyaredeterminantsofPGGiz,δ∗,butalsoofthe
expectedtotalnumberofsamples,E[N],foragivennumericalexperiment.
Thesamplingmechanismsconsideredare:
1.Astandardallocationschemewhichsamplesallindividualsequally
often.ThisisdenotedbyEqual.
2.OCBAδ∗EAforasteady-stateEAwithpopulationsizeµ=9andone
atedrenegoffspring3.OCBAδ∗EAforanevolutionstrategywith(5,10)replacement.
4.OCBAδ∗toselectthebestofthe10individuals.
5.OCBAδ∗togiveacompleterankingofthe10individuals.
Foralltests,anindifferencezoneofδ∗=0.2isused,i.e.theorderingofa
pairofindividualsisacceptedascorrectifthehigherrankedindividualisnot
morethan0.2worsethanthelowerrankedindividual.Weusethestopping
rulePGGSlep,δ∗>1−α∗,whereα∗isvariedtogeneratelinesinFigure3.6.
Acompleterankingoftheindividualsisthemostchallengingtaskand
requiresthehighestnumberofsamplestoreducetheerror1−PGGiz,δ∗.
Thecurvesforsteady-stateEAand(5,10)ESaresignificantlybelowthe

87

3.6EmpiricalEvaluation

3.IntegratingRankingintoEA

Figure3.6:Efficiency(left)andtarget(right)ofdifferentsamplingmecha-
nisms(expectednumberofsamplesrequired,E[N]andstoppingparameter
α∗,toreachacertainlevelofPGGiz,δ∗).

curveforthecompleteranking,whichshowsthatanEAindeedrequires
onlypartialinformation,andthatalotofsamplescanbesavedbygenerating
onlytherequiredinformation.Interestingly,thesteady-stateEAoperation
evenrequireslesssamplesthanidentifyingonlythebestindividual(OCBA0.2
Select).Thisisduetothefactthatwegeneratethemeansaccordingtoa
negativeexponentialdistribution,i.e.thereareseveralgoodbutfewbad
individuals,andthusitisrelativelyeasiertoidentifytheworstindividual
andthebetteroftworandompairsforthesteady-stateEAthanitisto
identifythebestindividual.
Figure3.7comparesournewOCBA-basedEAwithstandardEAsusing
thesamenumberofsamplesforeachindividual.TheOCBA-basedsampling
allocationschemesaremuchmoreefficientthanthecorrespondingEqual
allocationvariants,whichshowsthatintegratingastatisticalrankingand
selectionprocedureisbeneficial.
Forexample,toreducetheprobabilityofanerroneousgeneration,1−
PGGiz,δ∗,to0.02,thestandard(5,10)-ESwouldrequireanaverageof1160
evaluationspergeneration.OurOCBA-basedESachievesthesameaccuracy
with385evaluationspergeneration.Forthesteady-stateEA,thedifferences
areevenlarger:thestandardsteady-stateEAwouldrequireanaverageof
845evaluationspergeneration.whileourOCBA-basedEAonlyrequires
240evaluations.Thatis,ourmethodsaves67-71%ofthesamples,andthe

88

3.IntegratingRankingintoEA

3.7ErrorProbability

Figure3.7:ComparisonofthenewOCBA-basedEA(boldlines)andthe
standardEAwithEqualsampling(thinlines).

benefitofournewlyproposedmethodsincreaseswithanincreasingdesired
.PGG∗,δizThecontrollability,i.e.theabilitytoachieveagivenlevelofPGGiz,δ∗
isveryhigh,whereasthetargetcannotbeguaranteed.Thisholdsforall
procedureswithrespecttothechosenconfiguration.
Whilethisonlylooksatasingleexampleofanartificiallygenerated
iteration,itistobeexpectedthatthebenefitofourproposedmethodwillbe
evenlargerforlargerpopulations(becausetherequiredinformationbecomes
anevensmallerportionoftheinformationrequiredforafullranking)and
inaniterativeEAsetting(becauseOCBAwillbeabletore-usethesamples
ofsurvivingindividuals,andthosearetheindividualsthatwereallocated
relativelymanysamples).
Toimproveefficiency,priorinformationaboutthedistributionofmeans
andvariancescanbeacquiredfromthepreviousiterationandintegratedinto
theestimationasshowninSection2.4.

3.7SettingtheErrorProbability

Withtheproceduresderivedintheprevioussectionanefficientandcontrol-
lableprocedureisavailableforuseinEA.Theopenquestionishowtoset

89

3.7ErrorProbability

3.IntegratingRankingintoEA

theindifferencezoneδ∗andtheerrorprobabilityαorthelossβ.This
settingdependsontheuseoftheEAinthestochasticenvironment.

orneratGe1.TheEAisusedasgeneratorforsolutions,whereeverysolutionvisited
isstoredinadatabaseandthebestsolutionisdeterminedafterthe
“optimization”processviaselectionofthebestoutofthedatabase.
Theselectionstepmightbechallenging,asalargenumberofalter-
nativesneedtobecompared.Theadvantageofthisapproachisthe
guarantee,thatthebestoutofthevisitedsolutionsisreturned.The
disadvantageisthatduringthesearchonlyuncertaininformationon
thecurrentbestsolutioncanbegiven.Therankingprocedureonly
needstoensurethattheoptimizationdoesnotturnintoarandom
search.Thisapproachwaschosenby[Boesel1999]andisnotfurther
investigatedinthisthesis.
zermiOpti2.TheEAisusedanalogouslytotheuseinadeterministicenvironment,
wherethedecisionmakerexpectsthebestsolutioninthelatestpopu-
lationofarun.Ifthereplacementoperatorensuresthatthebest(or
perceivedbest)solutionsurvivestothenextgenerationwithahigh
probability,thenthereturnedsolutioncanbedeterminedfromthelat-
estpopulationwithoutspendingmuchefforttofindthesolutionfrom
alargedatabaseofpotentialsolutions,butinsteadfromasmallpopu-
ion.lat

EAthatcanbeusedforthesecondpurposearegenerationalEAwith
elitism,steady-stateEAandPlus-ES.Thelattertworeplacetheworstin-
dividual(s),soiftheprobabilityforcorrectgenerationisPGGiz,δ∗,thenthe
probabilitydenotedbyPGSiz,δ∗thatthebestindividualsurvivestothenext
generationissignificantlylargerthanPGGiz,δ∗.
Notethattheprobabilityforthebestindividualtosurvivetgenerations
islargerthan(PGSiz,δ∗)t,becausethePGSiz,δ∗ofsuccessivegenerationsare
positivelycorrelated.

90

3.IntegratingRankingintoEA

3.7ErrorProbability

Figure3.8:TypicalconvergencecurveofanEAdependingonnumberof
.ttionsitera

IftheEAisusedinteractively,itmightbenecessarytokeepthedecision
makerinformedonthecurrentlybestsolution.Thereforeineachgeneration
–oratleastforagiveninterval–theoverallbestsolutionfoundneedsto
beavailable(online).ThiscanbeeasilyintegratedintoOCBAδ∗EA,butwill
modifythebehavioroftheEA,assamplesareusedforinformationthat
isnotneededwithintheEA.Fornon-interactiveEAthechoiceofthebest
solutioninthelastpopulationmightbedelayedforaftertheoptimization
ffline).(oIngeneraltheoptimalchoiceofα,δ∗andβnotonlydependsonthe
problem,butalsoontheparametersoftheEAlikepopulationsize,selection
pressure,mutationrateandothers.Evenworse,theoptimalsettingmay
varyovertherunofanEA.
Inthefollowingwederivetheoreticalconditionsfortheoptimalsetting
ofαorβbymakingassumptionsonthetrade-offbetweenthebenefitof
additionalaccuracyandthepriceofachievingadditionalaccuracy.
GenerallyEAconvergeexponentiallyfasttotheoptimum(seeFigure3.8).
Thespeedoftheconvergenced=−∂∂tlog(ft−f)dependsontheparameter
settings.Assumethattheconvergencespeedislocallyconstant.Thecon-
vergencespeed,whenappliedtoacertaindeterministicproblemisdenoted
d0.Inastochasticenvironment,d0couldonlybeachievedforanerrorprob-

91

3.7ErrorProbability

3.IntegratingRankingintoEA

Figure3.9:Improvementperitera-Figure3.10:Convergencespeeddin-
tionfordifferenterrorprobabilitiesα.creasingmonotonicallytothemaxi-
theThecsolonvpeerongencethisspeescaleddαcorr.espondstoromalrprconobavbilitergenceyα.d0fordecreasinger-

abilityα=0,whichdemandsaninfinitenumberofsamplesn.Ahigher
errorprobabilitywillresultinlessselectionpressureandthereforethecon-
vergencespeedisreduced.Intheextremecase,ifnosamplesaretakenatall,
theEAhasnoinformationwhichindividualsarebetteranddegradestoa
randomwalkwithoutanyimprovement(d1=0).Theconvergencespeeddα
fortheerrorprobabilityαisthereforeintherange[d1,d0](seeFigure3.9).
Reasonably,theconvergenceshouldincreasemonotonicallywithdecreasing
α.Assumetheconvergenceincreasespolynomiallywithexponentq(see
..10)3eFigur

dα=d0(1−α)q(3.8)
Withtheseassumptions,wecangiveafunctionalrelationbetweenthe
errorprobabilityαineachiterationandthequantitativebenefitofadditional
accuracyfortiterations:Δt=ft0−ft0+t=(ft0−f)(1−e−dαt).InFigure3.7
theerrorprobabilitydecreasesexponentiallyinthenumberofsamplesper
generationn.Ifnosamplesareused(n=0),weassumetheerrorprobability
α=1,sothefunctionalrelationisapproximatelyn=−clogα,wherec
determinestheefficiency.
GivenabudgetofNsamplesavailableforoptimization,thequestion
arises,howmanysamplesshouldbespendfortheaccuracyofasingleitera-
92

3.IntegratingRankingintoEA

3.7ErrorProbability

tionandhowmanyiterationsshouldbeperformed.Themoreiterationsthe
EAruns,thebettertheresultandthemoreaccuracyperiteration,thehigher
theconvergenceperiteration.Butmoreaccuracyperiterationinvolvesmore
samplesperiterationandthereforebudgetforlessiterationsoverall.

Takingnosamplesperiterationallowsforaninfinitenumberofiterations,
butresultsinnoimprovementperiterationandthereforenoimprovement
overall.UsingthebudgetofNsamplesinoneiterationwouldmaximize
theimprovementinthisiteration,butwouldonlyallowforoneiteration,
againresultingin(almost)noimprovement.Sothereisatrade-offbetween
thenumberofsamplespergenerationandthetotalnumberofiterations.
Assumingthatthenumberofsamplesperiterationnisapproximatelycon-
stant,thenumberofiterationsisT=N/n.Insertingthistogetherwiththe
relationforsamplesanderrorprobabilityintotherelationforaccuracygives
NΔT(α)=(ft0−f)1−e−d0(1−α)q−clogα
=(ft0−f)1−ed0cNlogα(3.9)
(1−α)q
foratotalbudgetofNsamplesfortheoptimization.MaximizingΔTis
qequivalenttominimizing(1log−αα).Itisindependentofthedeviationbetween
bestandcurrentsolutionft0−f,thebudgetN,themaximalconvergence
speedd0andtheefficiencyoftherankingprocedurec.Thefunctionhasits
uniqueminimumforq=−α1−logαα>0.Figure3.11showsΔT(α)
Tochoosetheerrorprobabilityαperiterationoptimally,theranking
procedureneedstosampleuntiltheerrorprobabilityαholds−α1−logαα<q.
Notethatαdecreaseswithadditionalsamples.

Howeverinpractice,theconvergenceexponentqisunknownanddepends
onthecurrentpopulation.Furtherresearchisneededtogetadeeperun-
derstandingoftherelationshipbetweenerrorprobabilityandconvergence
ed.esp

93

Co3.8nionclus

3.IntegratingRankingintoEA

Figure3.11:ImprovementΔTforTiterationswithvaryingerrorprobability
periterationα.

3.8Conclusion
Optimizationinnoisyenvironmentsischallenging,becausethenoisemakes
itdifficulttodecidewhichoftwosolutionsisbetter,whichisaprerequisite
foreveryoptimizationalgorithm.Whilenoisecanusuallybereducedby
averagingovermultiplesamples,thisisacostlyprocess.Inthischapter,we
haveproposedanewadaptivesampleallocationmechanismthatattempts
tominimizethenumberofsamplesrequiredtowarrantaproperfunctioning
ofanEA.Theapproachisbasedontwoideas:

1.Restrictionofthefocusonthosepairwisecomparisonsthatareactually
usedbytheEA.Astheempiricalresultshaveshown,thesecomparisons
mayrequirelesssamplesthanevenonlyidentifyingthebestindividual.

2.TheuseofOCBA,asampleallocationprocedurefromstatisticalrank-
ingandselection.Thisallowedtodistributetheadditionalevaluations
tothoseindividualswheretheypromisethehighestbenefit,andtostop
samplingwhenthereissufficientevidenceforcorrectselection.

3.9FutureWork
Acomprehensivestudyontheeffectsofpopulationsize,selectionpressure
andaccuracyhastobedonefordifferentproblems.Thecurrentapproach

94

3.IntegratingRankingintoEA

3.9FutureWork

onlyallowsfortheimitationofexistingmethodswithhigherefficiency.Im-
itatingthebehaviorofanEAinadeterministicenvironmentresultsinex-
cessivesamplingfortypicalparameters.Usingafixedsamplesizescheme
asoftenusedinstochasticenvironmentshasproventobesuboptimalin
.2reChaptAnapproachforchoosinganear-optimalerrorprobabilityistomaximize
theimprovementpersampleΔ1/n.TheimprovementperiterationΔ1can
beestimatedbycomparingthemeanfitnessoftheoldpopulationP,with
themeanfitnessofthenewparentsM.Aslongastheratioofestimatedim-
provementandsamplesdoesnotdecreasesignificantly,therankingprocedure
keepsonsampling.
Weightedcomparisons,suchthatthegeometricmeanoverallcomparisons
holdsthetarget,allowstheintegrationofahigherprobabilityforthebestto
surviveorformoreimportantcomparisons.Theidentificationofthesewill
bebothpromisingandchallenging.
OnefurtherareaoffutureresearchcanbetheadaptationofOCBAδ∗EAfor
multipleobjectives,allowingtooptimizeproblemswithmultipleperformance
criteriainstochasticenvironments.

95

3.9

euturF

orkW

3.96

tegratingInRankingtoinAE

Chapt4er

seNoingiUs

Fornoisyoptimizationproblems,thereisgenerallyatrade-offbetweenthe
effortspenttoreducethenoise(inordertoallowtheoptimizationalgorithm
torunproperly),andthenumberofsolutionsevaluatedduringoptimiza-
tion.However,forstochasticsearchalgorithmslikeevolutionaryoptimiza-
tion,noiseisnotalwaysbad.Onthecontrary,inmanycases,noisehasan
effectverysimilartotherandomnesswhichispurposefullyanddeliberately
introducede.g.duringselection.Attheexampleofstochastictournament
selection,weshowthatthenoiseinherentintheoptimizationproblemcan
beusedtopartiallyreplacetherandomnessinselection,therebyreducing
therequiredsamplingeffortbyapproximately50%fortypicalparameter
settings.

4.1Introduction

Generally,noiseisconsideredharmful,asitmaymisleadtheoptimization
algorithm.However,noiseisnotalwaysbad.EAarerandomizedsearch
algorithms,andmostofthemusedeliberatelyrandomnesstopurposefully
introduceerrorsintotheselectionprocess,primarilyinordertogetoutof
ptima.ocalloTherefore,inthischapterwearguethatitshouldbepossibletoacceptthe
noiseinherentintheoptimizationproblemandtouseitto(atleastpartially)

97

4.1Introduction

4.UsingNoise

replacetherandomnessintheoptimizationalgorithm.Weproposenoise-
adjustedtournamentselection(NATS)wheretheprobabilityofaccepting
thebetterindividualistunedtoreflecttheuncertaintyinevaluation.As
aresult,itispossibletodramaticallyreducetheeffectofnoisewithout
requiringanexcessivenumberofsamples.
Experimentsonasimplesphereindicatethattheeffortintermsofsam-
plesforachievingahighselectionpressureisnotworththegaininaddi-
tionalsolutionimprovementpergeneration.Itseemsthatatleastforsome
parametersettings,thebestresultsareobtainedwithrelativelylowselection
pressurelikeobtainede.g.withstochastictournamentselection.

4.1.1StochasticTournamentSelection
Stochastictournamentselection(STS)hasbeendescribedindetailinSec-
tion3.4.3.Selectingthebetteroftwoindividualswithprobability(1−γ)
inanoisyenvironmentcanbeachievedintwofundamentalways:Thestan-
dardwaywouldbetoeliminatethenoiseasmuchaspossiblebyusinga
largenumberofsamples,andthenselectingthebetterindividualwithprob-
ability(1−γ).Thenoise-adjustedtournamentselectionproposedherehas
adifferentphilosophy:insteadofeliminatingthenoiseandthenartificially
introducingrandomness,weproposetoacceptahigherlevelofnoise,and
onlyaddalittlebitofrandomnesstoobtainthedesiredbehavior.

4.1.2BasicNotations
Letusdenotethetwoindividualstobecomparedasiandj.Ifthefitnessis
noisy,weassumethatthefitnessofindividualiresp.jisarandomvariable
Xiresp.XjwithXi∼N(µi,σi2)resp.Xj∼N(µj,σj2).However,µiand
µjareunknown,wecanonlyestimatethembysamplingeachindividual’s
fitnessanumberofniresp.njtimesandusingtheaveragesx¯iandx¯jas
estimatorsforthefitnesses,andthesamplevariancessi2andsj2asestimators
forthetruevariances.
Iftheactualfitnessdifferencebetweenthetwoindividualsisdenoted
asδ=µi−µj,theobservedfitnessdifferenceisagainarandomvariable
98

4.UsingNoise

4.1Introduction

D=x¯i−x¯j∼N(δ,σd2).ThevarianceofDdependsonthenumberof
samplesdrawnfromeachindividual,niandnj,andcanbecalculatedas
σd2=σi2/ni+σj2/nj.
Wedefineδ∗=δ/√σi2+σj2asthestandardizedfitnessdifferenceandσ∗=
σi2/(σi2+σj2)astheratioofthevariances.Weestimateδ∗by
d∗=x¯i−x¯j
s2i+sj2
ThecorrespondingrandomvariableD∗canbeapproximatedbyanon-central
t-distribution,wherethedegreesoffreedomνaregivenbyWelch’sapproxi-
mation.Dividingthenominatoranddenominatorofd∗byσi2+σj2shows
thatthenominatorisaGaussianrandomvariablewithmeanδ∗andvari-
ancenσi∗+1n−jσ∗.Thedenominatoristherootofthesumoftwoweightedχ2-
distributions.Thesumisapproximatedbythefractionofaχ2-distribution
anditsdegreesoffreedom∗2ν,whicharedeterminedbyWelch’sapproxima-
tion:ν−1=nσi∗−21+(1n−jσ−1).ThefractionofaGaussianrandomvariablewith
non-zeromeanandtherootofaχ2randomvariabledividedbyitsdegrees
offreedomisaStudentrandomvariablewiththedegreesoffreedomfrom
theχ2randomvariable.

jiD∗≈tνδ∗,η1withη−1=nσ∗+1n−σ∗(4.1)
Thedegreesoffreedomνrangein[min{ni−1,nj−1},ni+nj−2].They
areminimalfortheextremevalues0and1ofσ∗andreachamaximumfor
σ∗=nin+in−j1−2.Theeffectivesamplesizeηliesin[ni,nj].Forequalallocation
ofnsamplesamongtheindividualsiandj,theeffectivesamplesizeηisn/2,
independentofthevarianceratioσ∗andforsimilarvariances(σ∗≈0.5)the
degreesoffreedomareν≈n−2.
TheimportantconclusionfromEquation4.1isthatthedistributionof
d∗primarilydependsonδ∗(besidesniandnj),apropertywhichwewillbe
usinglater.Also,theaboveconsiderationsshowthatd∗isanasymptotically
unbiasedestimatorforδ∗.

99

Effect4.2iseNoof

4.UsingNoise

Forstochastictournamentselection,if1−γisthedesiredselectionprob-
abilityforthetrulybetterindividual,thedesiredselectionprobabilityfor
isilindividuaπi(δ∗)=δ∗≥0:1−γ.
δ∗<0:γ
ForSimulatedAnnealingthedesiredselectionprobabilitynotonlyde-
pendsonthesignofδ∗,butalsoonthevalue.TheMetropolisacceptance
criterionatthetemperaturelevelθdefinestheselectionprobability
∗δ∗≥0:1
πi(δ)=δ∗<0:eδ∗/θ.
Wedenotewithπˆi(d∗)theimplementedprobabilityforchoosingindivid-
ualibasedontheestimatedstandardizedfitnessdifferenced∗,andwith
pi(δ∗)=E[πˆi(D∗)]theactualselectionprobabilityforindividualigivena
truestandardizedfitnessdifferenceofδ∗.AsshownaboveD∗dependsbesides
δ∗onni,njandweaklyonσ∗.

4.2TheEffectofNoise

4.2.1StandardApproach
Thesimplest(andstandard)waytoapplystochastictournamentselection
orsimulatedannealingwouldbetoignoretheuncertaintyinevaluationby
makingthefollowingassumption:
Assumption1:Theobservedfitnessdifferenceisequaltotheactual
fitnessdifference,i.e.δ∗=d∗.
Individualiisselectedwithprobability1−γ,ifd∗≥0andwithproba-
∗bilityγ,ifd∗<0.
πˆi(d∗)=dd∗<≥00::γ1−γ
However,therecanbetwosourcesoferror:Eitherweobserveafitness
differenced∗>0whenactuallyδ∗<0,orviceversa.Thecorresponding
010

4.UsingNoise

Effect4.2iseNoof

Figure4.1:Trueselectionproba∗bilityofindividualidependingontheactual
standardizedfitnessdifferenceδfordifferentsamplesizesnandequalvari-
ances.Thedottedhorizontallinerepresentsthedesiredselectionprobability
).γ(1−

errorprobabilityαcanbecalculatedas
δ≤0:P(D>0)=1−Φσ−dδ=Φσδd
α=δ>0:P(D<0)=Φσ−dδ
=Φ−|δ|=Φ(−|δ∗√η|).(4.2)
σdTheoverallselectionprobabilityforindividualiiscomposedoftheprob-
abilitytoobserveadifferenced∗>0correctlyandthenselectingindividual
i(withprobability1−γ)orelseerroneouslyobserved∗>0andselecting
individuali(withprobabilityγ).Thereforetheactualselectionprobability
ispi(δ∗)=(1−α)(1−γ)+αγ.
Tovisualizetheeffectoftheerrorprobabilityontheactualselection
probabilitypi,letusconsideranexamplewithγ=0.2.
Figure4.1depictstheresultingtrueselectionprobabilityofindividual
idependingontheactualstandardizedfitnessdifferenceδ∗.Thedotted
horizontallinecorrespondstothedesiredbehaviorinthedeterministiccase,
theboldlineslabeled“standard”aretheactualselectionprobabilitiesdueto
thenoiseforsamplesizesn=80,40,20,10forbothindividualstogether,i.e.
110

iseNoofEffect4.2

4.UsingNoise

ni=nj=40,20,10,5perindividual.Ascanbeseen,theactualselection
probabilityforthebetterindividualapproachesapproximatelythedesired
probabilityforδ∗=0.35,0.50,0.70and1.00,respectively1.Forδ∗→0it
approaches0.5.Thelatterfactisunavoidable,sinceforδ∗→0,thesignal-to-
noiseratioapproacheszero,anditbecomesbasicallyimpossibletodetermine
thebetterofthetwoindividuals.Theinterestingquestionishowquicklypi
approaches1−γ,andwhetherthisbehaviorcanbeimproved.Notethatwe
onlyshowthecurvesforδ∗≥0(assumingwithoutlossofgeneralitythat
µi≥µj).Forδ∗<0thecurvewouldbesymmetricto(0,0.5).
Inpreviouspapers,ithasbeennotedthattheeffectofnoiseonEAis
similartoasmallerselectionpressure(e.g.[Miller1997]).Figure4.1demon-
stratesthatthereisanotabledifference:Alowerselectionpressureinform
ofahigherγwouldchangethelevelofthedottedline,butitwouldstillbe
horizontal,i.e.theselectionprobabilityforthebetterindividualwouldbein-
dependentoftheactualfitnessdifference.Withnoise,onlythetournaments
betweenindividualsofsimilarfitnessareaffected.Thatway,adependence
ontheactualfitnessvaluesisintroducedwhichsomehowcontradictstheidea
ofrank-basedselection.

4.2.2ASimpleCorrection
Ifweknowthatourconclusionaboutwhichofthetwoindividualshasabetter
fitnessispronetosomeerror,itseemsstraightforwardtotakethiserror
probabilityintoaccountwhendecidingwhichindividualtoselect.Instead
ofalwaysselectingtheperceivedbetterindividualwithprobability(1−γ),
wecouldtrytoreplacetheselectionprobabilityofindividualibyafunction
πˆi(∙)whichdependsonthestandardizedobservedfitnessdifferenced∗.Let
usmakethefollowingassumption:
Assumption2:Itispossibletoaccuratelyestimatetheerrorprobability
.αWithoutlossofgeneralityweassumeindividualiasthebetterindividual.
−Φ1−1The0.01(1−deviatγ)√ionη.atthatpointfallsbelow1%.Itcanbecalculatedby
γ2−1

210

4.UsingNoise

ofEffect4.2iseNo

πˆiFigurfores4.2:electingImplemenindividuatedliprodepenbabilitdingypiFigurofine4.3:dividualTrueisedepelectionndingproonthebabilitac-y
∗ondifferencethedobserv∗andedn=standa40rdizedsamples.fitnesstuaandlnsta=40ndardizedsamples.fitnessdifferenceδ

Itisselectedeitherifwerecognizeitasthebetter(probability(1−α))and
selecttheperceivedbetterindividual(probabilityπˆi),orifwethinkitis
worse(probabilityα),butdecidetochoosetheworseindividual(probability
1−πˆi).Thus,sincewewouldliketohaveanoveralltrueselectionprobability
of(1−γ),anappropriateπˆi-functioncouldbederivedas
(1−α)πˆi+α(1−πˆi)=!1−γ
πˆi=1−γ−α.
α21−πˆiisaprobabilityandcannotbesmallerthan0,i.e.theaboveequation
assumesα≤γ<0.5.Forα>γwesetπˆi=1.
Unfortunately,αcannotbecalculatedusingEquation4.2,becausewe
don’tknowδ∗.Itseemsstraightforwardtoestimateδ∗bytheobserved
differenced∗.Then,αisestimatedasαˆ=Φ(−|d∗|√η),whichisonlya
biasedestimatorduetothenon-lineartransformations.Nevertheless,this
mayserveasareasonablefirstapproximationofanoptimalπˆi-function.
√∗1−2Φ−|d|η
πˆi(d∗)=1−γ−Φ−|∗d√|η(4.3)
Figure4.2visualizesthisπˆi-function(labeledas“corr”)forn=40sam-
310

iseNoofEffect4.2

4.UsingNoise

plesandγ=0.2.Ascanbeseen,theprobabilitytoselectthebetterin-
dividualsincreaseswhenthestandardizeddifferenced∗becomessmall,and
is1for|d∗|<−Φ−1(γ)(i.e.theobservedbetterindividualisalwaysse-
lectediftheobservedstandardizedfitnessdifference|d∗|issmall).Assuming
thesameparametersasintheexampleabove,theresultingselectionprob-
abilitiespi(δ∗)aredepictedinFigure4.3(labeledas“corr”).Theselection
probabilityapproachesthedesiredselectionprobabilityfasterthanwiththe
standardapproach,butthenitovershootsbeforeitconvergestowards1−γ.
Nevertheless,theapproximationisalreadymuchbetterthanthestandard
approach(assumingauniformdistributionofδ∗).

4.2.3NoiseAdjustedTournamentSelection
Animprovementmightbyachievedbymodifyingthefunctionˆπi(d∗)such
thattheresultingselectionprobabilitypimatchesπiexactlyoratleastbetter.
Anabstractformulationforthisis:Givenafunctionf(.)andarandom
variableZdependentonx,welookforafunctiong(∙),sothattheexpected
valueofthetransformedrandomvariableequalsthevalueofthefunctionat
.xmeterparatheE[g(Zx)]=f(x)
Itisobviousthatg(∙)equalsf(∙)ifZx=x,butiftheZxarerandomly
disturbedandxisunknownforagivenrealizationz,ingeneralnoexactso-
lutionexists.g(∙)canbechosentominimizea(weighted)deviationbetween
theexpectedandthedesiredvalue,
+∞g(min∙)−∞w(x)d(E[g(Zx)],f(x))dx(4.4)
foradistancemetricd(∙,∙).ThelessZxvaries,themorelikelyagoodfitting
functiong(∙)canbefound.Letp(z,x)denotetheprobabilitydensityfunction
(pdf)ofZxforagivenparameterx.Ifthepdfisn-timesdifferentiableinx,
thenE[g(Zx)]isn-timesdifferentiableinx,too2,independentoftheshapeof
2(dxdn)nE[g(Zx)]=(dxdn)n∞−∞g(z)p(z,x)dz=∞−∞g(z)(dxdn)np(z,x)dz
410

4.UsingNoise

iseNoofEffect4.2

g(∙).Thisholdsfordiscreterandomvariablesaslongastheyarecontinuous
intheparameters,too.Fromthisitfollowsthatonlycontinuousf(∙)canbe
hed.cmatTosolveEquation4.4wechoosetheEuclideandistancemetricd(x,y)=
x−y2andg(∙)asastepwisedefinedfunctiononm+1intervals(x0,x1],
...,(xm,xm+1),wherex0andxm+1are±∞andgjisthevalueofg(∙)in
thej-thinterval.Furtherwedenotethesetofnsupportivepointsbyx˜i.
nshouldbechosenlargerthanmandsomex˜i∈/[x1,xm]tocircumvent
boundaryeffectsandforceconvergenceofg(∙)towardstheboundaries.pij=
Pr(Zx˜i∈(xj−1,xj])istheprobabilityofobservingavalueinthej-thinterval,
iftheparameterisx˜i,wiistheweightorthelossofadeviationatx˜iand
jm=1+1pijgj.NowEquation4.4canbeapproximatedby
ti=f(x˜i)thetargetvalue.ThemeanisthenapproximatedbyE[g(Zx˜i)]≈
+1mngj,j=0min,...,mwi(pijgj−ti)2(4.5)
=1j=1iThisisaquadraticprogramming21gTQg+cTgwithQ=2PTWP,c=
−2tTWP,whereWisthediagonalmatrixoftheweightswi.Itcanbe
solvedbyanyquadraticprogramsolver3.
Intheapplicationsbelow,weinterpretg(∙)asanappliedselectionprob-
ability,sog(∙)∈[0,1]addsboundsforthevariables.Forg(∙)hittingapprox-
imatelythetarget,thevarianceoftherandomvariableZxshouldbelow.If
Zxistheresultofasamplingprocess–asitisbelow–thevariancecanbe
reducedbyadditionalsamples.
Toapplytheseresultswesetx=δ∗,Zx=D∗,f(∙)=πi(∙)andreceive
πˆi(∙)=g(∙).Anexamplecurveofπˆi(∙)isshowninFigure4.4.
Thecalculationofπˆifor2000supportivepointstakesroughly90seconds
ona3GHzPC.Theefficiencycanbeimprovedbyintegratingthecondition
thatg(∙)hastobepointsymmetric:g(x)=1−g(−x).Forcalculationofthe
cdfofthenoncentralt-distributionthealgorithmfoundin[Krishnamoorthy
andBenton2003]wasused.
3WeusedthefreelyavailableOOQP,describedindetailin[GertzandWright2003].
510

4.2iseNoofEffect

4.UsingNoise

bilitFiguryeof4.4:individuAppliedalidepselecentdingionoprontheba-piFigurofine4.5:dividualTrueisedepelectiondingnproonthebabilitac-y
observedstandardizedfitnessdiffer-tualstandardizedfitnessdifferenceδ∗
enced∗forγ=0.2,n=20andequalandn=20samples.
allocation.2000supportivepoints
arandeπˆi(∙equally)consistsspacedofb10etw00eenin[−terv15als,15in]
[−10,10].

Tournamentselectionbasedonthisoptimizedacceptancefunctionisde-
notednoise-adjustedtournamentselection(NATS).Notethatoncetheap-
propriateacceptancefunctionπˆi(∙)hasbeendetermined,NATSiscomputa-
tionallyjustasefficientasstandardSTS.Andsincetheacceptancefunction
primarilydependsonγandthesamplesizen,typicalacceptancefunctions
couldbeprovidedbyapublicrepository,makingNATSalmostassimpleto
STS.sauseTheresultingacceptancefunctionisdepictedinFigure4.4.Atfirstsight,
thestrongfluctuationsseemsurprising.However,asteeperascentofthe
selectionprobabilitycanonlybeachievedbykeepingπˆi=1foraslongas
possible.Theresultingovershootthenhastobecompensatedbyavery
lowπˆietc.suchthatintheend,anoscillatingacceptancepatternemerges
asoptimal.Forobserveddifferencesuptoapproximately0.35,thebetter
individualisalwaysselected,whileforadifferencearound0.47theworse
individualisselectedwithhighprobability.Theprobabilitiesvarylargely
untiltheyconvergetothedesiredprobability.
AscanbeseeninFigure4.5,despitetheoscillatingacceptancefunction

610

4.UsingNoise

iseNoofEffect4.2

πˆi(∙),thecurveofachievedselectionprobabilitiesisverysmooth,andmuch
closertotheactuallydesiredselectionprobabilityofγresp.(1−γ)than
eitherthestandardapproachofignoringthenoise,orthefirstapproxima-
tionofanappropriateacceptancefunctionpresentedintheprevioussection.
SimilarresultscanbeobtainedforSimulatedAnnealing,whichisnotfurther
here.seddiscus

4.2.4SequentialSampling
ThesequentialselectionprocedurespresentedinChapter2showedalarge
savingcomparedtothesimpleequalsamplingschemewithafixedbudgetof
samples.Theproceduresaredesignedfortheselectionofoneoutofmany
systems.Regardingasingletournament,onlythebetteroftwoindividuals
hastobedetermined.Althoughingeneral,individualsparticipateinseveral
tournaments,weprescindfromthatandtreatthetournamentsasbeing
t.nendeindepRepresentativeforothersequentialselectionproceduresweuseKimand
Nelson’sproceduretoidentifythebetteroftwosystemsandcompareittoa
newsequentialprocedurespecializedonthecomparisonofjusttwosystems.
Theproceduredenotedwithαcisbasedontheassumptionthattheerror
probabilityoneachstageshouldbeaconstantαc.Notethatbecausethe
proceduremaystoponanystageduetoalargeobservedfitnessdifference,
theunderlyingprobabilitydistributionsaretruncatedandbecomerather
skewedwithanincreasingnumberofiterations.Therefore,wedeterminethe
thresholdskandthetotalactualerrorprobability(whichalsodependson
theprobabilitytomakeadecisioninstagek)empiricallybysimulation.This
methodisdescribedasAlgorithm1,whereΦδ∗,k(x)denotesthecumulative
probabilitydistributionfortheobservedstandardizedfitnessdifferencein
stagek,basedonatruefitnessdifferenceδ∗.Thetotalnumberofstagesis
.KtolimitedWeusebinarysearchtofindaper-stageerrorprobabilityαcwhichyields
atotalerrorprobabilityofαatthereferencevalueδr∗.Notethattheproce-
duretodeterminethekiscomputationallymoredemandingthanKimand
710

tsulesR4.3

4.UsingNoise

Algorithm1Determiningthresholdsandtotalerrorprobability
Input:constanterrorperstageαc
Generatealargenumberofpairsofindividualswithstandardizedfitness
∗δdifferenceSamplereachindividualn0=4times
EstimateΦδr∗,0fromtheobservedd∗ofallpairsofindividuals
FORk=0TOK−1DO{
k=max{0,−Φδ−r∗1,k(αc)}∗
DetermineprobabilitypkδrtogotonextstagebasedonkandΦδr∗,k
EstimateΦδr∗,k+1bytruncatingatk,−k,andresamplingremaining
lsindividua}RETURNtotalerrorprobabilityα=αc+kK=1αcik=0−1piδr∗andthresh-
oldsk

Nelson’smethod.However,thisefforthastobespentonlyonceforagiven
indifferencethresholdδr∗anderrorprobabilityα,andcouldinprinciplebe
bvidedprotables.y

34.tsResul

4.3.1Samplesizecomparisons

Clearly,themethodsproposedintheprevioussectionconstituteasignifi-
cantimprovementcomparedtothestandardSTS.Inthissection,wetryto
quantifytheimprovementintermsofcomputationaleffortsaved,whichis
probablythemostrelevantmeasure.Tothisend,wecheckhowmanysamples
arenecessaryincombinationwithstandardSTStoobtainactualselection
probabilitiessimilartowhenweusetheacceptancefunctiongeneratedby
d.methoTSNAourFigure4.6showstheactualselectionprobabilitiesforstandardSTSfor
differentnumberofsamplestaken(thinlineslabeledwith10,20,40,80,160).
Ontopofthat,wehavedrawnsomedashedlinesresultingfromNATS.As
canbeseen,thecurveobtainedfromourmethodcombinedwith10sam-

810

4.UsingNoise

tsulesR4.3

Figure4.6:ComparisonofstandardSTSandourproposedNATSmethod
fordifferentsamplesizes.

plescloselymatchesthecurveobtainedwithstandardSTSand20samples.
Thesesavingsseemtobeindependentofthenumberofsamples:forall
curves,NATSallowstocutthenumberofsamplesbyapproximately50%,
stillyieldingthesameaccuracyinselection.Sincesamplingisusuallythe
time-determiningfactorforcomplicatedreal-worldoptimizationproblems,
thismeanstherun-timeofthealgorithmisreducedby50%aswell.

4.3.2Dependencyonselectionpressureparameter
Sofar,wehaveassumedaselectionprobabilityforthetournament’sbetter
individualof80%,i.e.γ=20%.AswehaveexplainedinSection3.4.3,
theparameterγallowsthealgorithmdesignertochoosetheselectionpres-
sure.Nowweexaminehowthesettingofγinfluencestheeffectivenessour
h.coaapprAswehaveshownintheprevioussubsection,withγ=0.2,ourmethod
allowstosave50%oftheevaluations.Forγ=0,themethodisboundto
fail,becausetheunderlyingtrickistocompensatethenoisebyincreasingthe
probabilitytoselectthebetterindividual.Obviously,ifthebetterindividual
isalwaysselectedthatideacannotbeapplied.Ontheotherhand,for
γ=0.5,weobviouslydon’tneedtoevaluateatall,butcanjustselect
randomlyinstead.Inthatcase,wecouldthussave100%ofallevaluations.

910

R4.3tsules

4.UsingNoise

Figure4.7:Percentageofsamplesthatcanbesavedbyusingourproposed
noise-adjustedSTS,comparedtostandardSTS,withoutsacrificingselection
.cyaccura

Figure4.7showsthepercentageofsamplesthatcanbesavedusingour
noise-adaptedSTSwhencomparedtothestandardSTS.Thesavingshave
beendeterminedsimilarlytothelastsubsection,bycomparingcurveswith
differentsamplesizes,andchoosingthenumberofsamplesn∗forthestan-
dardSTSsuchthattheresultingselectionprobabilitiespiareassimilaras
possible(differenceintegral)tothenoise-adjustedSTSwithagivennumber
ofsamplesn.Thesavingsarethencomputedas1−n/n∗.Resultsareshown
forasamplesizeofn=20,butseemtobeindependentofthesamplesize,as
theresultsforsamplesizesof10,40,or80lookalmostidentical(notshown).
Ascanbeseen,intheinterestingrangeofγ∈[0.0,0.3]thesavings
resultingfromthenoise-adjustedSTSrisequicklywithγ,andsignificant
savingscanbeobtainedevenforrelativelysmallγvalues.

4.3.3ApplicationtoGenerational-EA
Wepresenttwokindsofexperiments.Inallcases,weassumetheuseof
stochastictournamentselection,wheretwoindividualsarechosenrandomly,
andthebetterindividualistobechosenwithprobability1−γ=80%.
Inthefirstsetofexperiments,wecomparetheerrorprobabilitiesofdif-
ferentmethodsforasingletournament,dependingonthe(standardized)
truefitnessdifference.Inthesecondset,wetesttheapproachesonasim-
ple1000bitonemaxproblem,andcomparetheobtainedfitnessbasedon

110

4.UsingNoise

R4.3tsules

n11020304050
P(S)0.5820.7200.7650.7840.7920.796
Table4.1:ActualselectionprobabilityforbetterindividualP(S),depending
onthenumberofsamplesperindividualnandassumingatruestandardized
fitnessdifferenceof0.35.

thetotalnumberofevaluations.Fortheoptimizationruns,weassumea
simpleGAwithgenerationalreproduction,populationsizeof20,one-point
crossoverwithprobability0.6,andbit-flipmutationwithmutationprobabil-
ity1/(chromosomelength).Unlessstatedotherwise,weassumeaGaussian
noisewithmean0andstandarddeviationσ=2.
Wecomparethedifferentmethodsbasedontheaveragepopulationfit-
ness,asthetruebestisgenerallyunknowninastochasticenvironment.
Resultsareaveragedover40runs.

SelectionErrorThesmallestobservablefitnessdifferencepossibleforthe
onemaxproblemis1(solutionsdifferinonly1bit).GivenaGaussiannoise
withstandarddeviationσ,√thestandardizedfitnessdifferencebetweentwo
suchindividualsisδ∗min=1/2σ2.Ifwewanttoeliminatetheeffectofnoise,
wethusrequirethattheselectionerrorisclosetozeroforδ∗>δ∗min.
Letusfirstconsiderthecaseofstandardstochastictournamentselection,
wheretheobservedbetterindividualisacceptedwith(1−γ)=80%proba-
bility.FortheassumedGaussiannoisewithσ=2,wegetδ∗min≈0.35.Table
4.1thenshowstheactualprobabilityofselectingthetrulybetterindividual
ifthetruestandardizedfitnessdifferenceisequalto0.35,dependingonthe
numberofsamplesusedperindividual.Anydeviationfromthedesired80%
noise.thetodueisAscanbeseen,about40samplesperindividualarerequiredtoreducethe
effectofnoisetolessthan1%deviation.Figure4.8confirmsthatindeedthis
issufficienttoeliminatetheeffectofnoise.Itshowstheaveragefitnessofthe
populationovertime,fordifferentlevelsofnoise,assuming80samplesper
tournament(40perindividual).Asexpected,anoiseofσ=2hasbasically
noeffect(thelinesforσ=2andσ=0areindistinguishable),whilelarger

111

4.3tsulesR

4.UsingNoise

Figure4.8:Averagefitnessofpopulationfordifferentlevelsofnoise,with
bars.rerro

noiseleadstoinferiorperformance(seeσ=5orσ=10).
Asthisexampleshows,theeffectofnoisecanbeeliminatedbymultiple
sampling.However,italsodemonstratestheexcessivecomputationalburden
(80samplespertournamentinsteadof2iftheenvironmentwouldbedeter-
ministic).Inthefollowing,weshowhowthiscomputationalburdencanbe
.icallyamatdrreducedUsingNATS,atotalof40samplespertournament(20samplesperindi-
vidual)shouldbesufficienttoeliminatetheeffectofnoise.Forthismethod,
theonlyrelevantissueiswhentheselectionerror(probabilityofobserving
d<0althoughδ>0orviceversa)fallsbelowthethresholdofγ=20%.
Using40samplespertournament,thisisthecaseforδr∗=0.188(seeFigure
4.9,line“Standard40”).Thus,inthefollowing,wearelookingforsequen-
tialsamplingprocedureswhichguaranteeanerrorprobabilityoflessthan
α=20%forδ∗>δr∗=0.188,becausethesesamplingplansshouldallow
ustoobtainaselectionbehaviorveryclosetostandardtournamentselec-
tionbasedon80samplespertournament(andthuscompleteeliminationof
noise).UsingKimandNelson’sprocedureandournewproposedsequentialsam-
plingprocedurewithconstantαc,forthegivenδr∗=0.35andα=0.2,we
observetheerrorprobabilitiesdepictedinFigure4.9.Ascanbeseen,the

211

4.UsingNoise

tsulesR4.3

Figure4.9:ErrorprobabilitycurvesFigure4.10:Averagenumberofsam-
fordifferentsamplingtechniques.plestakenpertournamentfordiffer-
entsamplingtechniques.

errorboundsareobservedinallthreecases.Forδ∗>δr∗,KimandNelson’s
procedureresultsinaslightlyhighererrorprobabilitythanthestandard
method.OursamplingprocedureisbetterthanKimandNelson’s,butthe
errorisstillhigherthanwhentheconstantsamplesizeisused.Thissmallin-
creaseinerrormightslightlyimpacttheoptimizationifthesamplingmethod
wereusedinisolation.Inourcase,however,itisofnoimportance,because
weuseitincombinationwithNATS,whichiscapableofcompletelycom-
pensatinganerroroflessthanγ=20%.
Ontheotherhand,thesavingsintermsofsamplesacquiredaredepicted
inFigure4.10.Ascanbeseen,savingsaredramaticforbothsequential
samplingmethods,inparticularifthetruestandardizedfitnessdifferenceδ∗
islarge.OurmethodsignificantlyoutperformsKimandNelson’sprocedure,
yieldingsavingsofabout14-24%ofthesamplesandlowererrorprobabilities.
Thereforeintherestofthepaperweonlyuseoursequentialsamplingmethod
.αcAshasbeenstatedabove,allmethodscannowbecombinedwithNATS.
Figure4.11comparestheactualselectionprobabilityofthebetterindividual
dependingontheactualstandardizedfitnessdifferenceδ∗,forthefollowing
ns:atioconfigurthree

1.Thestandardstochastictournamentselectionwith80samplespertour-
tnamen

311

ulesR4.3ts

4.UsingNoise

izedFigurefitness4.11:Rdifferenceesultingδ∗seleforctiothenstaprobandardbilityapprdepoachendingwitho8n0tsheatrmplesuepstaertondard-ur-
binednamenwt,iththethestaαcndardsequenapproatialchsamplingwith40scheme.samplesandNATS,andNATScom-

2.ThetournamentselectionprobabilitiesmodifiedaccordingtoNATS
and40samplespertournament

3.Oursequentialsamplingprocedurewithconstanterrorαcperstage
andselectionprobabilitiesmodifiedbyNATS

Ascanbeseen,allcurveslookmoreorlessidentical.Overall,thismeans
thatinordertoeliminatetheeffectofnoise,insteadof80samplespertour-
nament,weonlyneedbetween8and29samplesonaverage(dependingon
theactualfitnessdifferenceoftheindividuals)byusingournewsequential
samplingmechanismtogetherwithNATS.

BehaviorduringoptimizationIntheprevioussection,ithasbeenshown
thatbyusingappropriatesamplingtechniques,itispossibletoavoidtheef-
fectofnoisewithamuchsmallernumberofsamplesthanifeachindividual
wouldjustbesampledthesamenumberoftimes.Toshowthatthesecon-
siderationsalsoholdduringoptimization,Figure4.12empiricallycompares
theconvergencecurvesofthedifferentsamplingtechniquesonthe1000bit
onemaxproblem.Theyareallvirtuallyidenticaltothedeterministiccase
withoutnoise.Thecorrespondingnumbersofevaluationspergenerationare

411

4.UsingNoise

4.4ConclusionandFutureWork

Figure4.12:Fitnessovergenera-Figure4.13:Averagenumberofsam-
tions,fordifferentsamplingtech-plesrequiredpergeneration,relative
niques,witherrorbars.Forcompari-tothedeterministiccase,fordifferent
son,theEA’sbehaviorinadetermin-samplingtechniquesused.
isticenvironmentisalsoshown.

showninFigure4.13Naturally,thestandardapproachessamplethesame
numberoftimesindependentofthegeneration.Surprisingly,thenumberof
samplesisalsoquiteconstantforthesequentialsamplingprocedure.Only
intheverybeginning,thenumberofsamplesissignificantlysmallerthan
laterintherun.Forourconstantαcmethod,thesamplingeffortisnever
morethan19%ofthestandardapproach,i.e.byintegratingthenoiseinto
theselectionprocess,wesaveapproximately81%ofthesamples.

4.4ConclusionandFutureWork

Inthischapter,wehavearguedthatthenoisepresentinmanyreal-world
optimizationproblemsmaybeusedtoatleastpartiallyreplacetheran-
domnessinstochasticselectionschemes.Insteadoftryingtoestimatean
individual’sfitnessasaccuratelyaspossible,acertainlevelofselectionerror
maybeacceptableandcanbeaccountedforsimplybyadjustingtheselection
cedure.proAttheexampleofstochastictournamentselection,wehavederivedtwo
modelswhichdeterminetheselectionprobabilityforthebetterindividual
dependingontheobservedfitnessdifference.Thesimplemodelisbasedon

511

4.4ConclusionandFutureWork

4.UsingNoise

somesimplifyingassumptionsregardingthedistributionoftheerrorproba-
bility;thesecondmodelisbasedonamodifiedacceptancefunction.
Astheresultsontheonemaxproblemshow,usingtheproposednoise-
adaptedtournamentselectionallowstoreducethenumberofsamplessig-
nificantly(around50%foratypicalsetting)withoutcompromisingselection
quality.Wefurtherreducedthenumberofsamplesdrastically(upto81%)
bycombiningNATSwithsequentialselectionprocedures.
Futureworkwillincludeadditionalimprovementsresultingfromsam-
plingonlyoneindividualatatime(insteadofbothindividualsparticipating
inatournament),andfromre-usingsamplesforindividualsparticipating
inseveraltournaments,i.e.tointegratetheOCBAprocedurederivedin
.3reChaptOnefurtherdirectionofourresearchistheintegrationofappropriate
populationsizingandselectionpressure,asitmaybecrucialtothesuccess
ofanEAinnoisyenvironments.

611

5erChapt

SummaryandOutlook

Inthisthesis,wehavedevelopedefficientmethodsfortheapplicationof
EAonstochasticproblems.Toachievethis,weanalyzedproceduresfor
statisticalselectionsystematicallywithrespecttodifferentmeasuresand
improvedthemsignificantly.Weshowedhowtoadaptoneoftheprocedures
fortheneedsofEAandidentifiedandmodifiedoperatorstoapplythem
efficientlyinstochasticenvironments.
Forstatisticalselectionwedevelopedaunifiedexperimentalsetupwith
standardizedconfigurationsallowingforcomparisonwithresultsfromother
researchers.Opposedtootherpublications,whereonlyfewvaluesaretabu-
lated,weprovideresultsforawholerangeofparametersettingsinaneasily
interpretablegraphicalform.Thenewrandomprobleminstancesmodelthe
requirementsofselectionproceduresinpracticemorerealistically.Measure-
mentdisplaysforindifferencezoneorexpectedopportunitycostmeasures
aregiventocomparetheprocedureswithrespecttodifferentcriterialike
efficiencyandtarget.
WeidentifiedtheexpectedopportunitycostbasedproceduresOCBALL(S)
andLL(S)tobethemostefficient,whenafixedbudgetofsamplesisgiven.
IntheabsenceofabudgetconstraintonaveragetheOCBAδ∗,OCBALLand
LLproceduresprovidethebestresultsforawidevarietyofconfigurations,
withrespecttocontrollabilityandefficiency.Theproceduresbasedonthe
indifferencezoneapproach(KN++andWald)sufferfromthestrongdepen-

711

5.SummaryandOutlook

denceontheindifferencezoneparameterandarehardtocontrol.Nonetheless
ifagivenlevelofconfidencehastobeguaranteed,KN++istheprocedureof
choice.ThenumberofinitialsamplesisacriticalparameterfortheBayesian
procedures,whileKN++islesssensitive.KN++allowsforcorrelatedout-
putbetweensystems.
FromourresultswesuggestcombiningtheBayesianallocationprocedures
withanadaptivestoppingruletosubstantiallyimproveefficiencycompared
totheoriginalpublicationswithafixedbudget.Themostefficientandcon-
trollablestoppingruledependsonthedesiredgoal(EOCBonforPGSSlep,δ∗).
TheBayesianproceduresalsoallowfortheincorporationofpriorinformation
aboutprobleminstanceswhenthatisavailable.
Preliminaryworkontheanalysisandimprovementofstatisticalselection
hasbeenpresentedattheWinterSimulationConference([Branke,Chick,
andSchmidt2005a]).MorecomprehensiveresultsofChapter2havebeen
submittedtoManagementScience([Branke,Chick,andSchmidt2005c]).
Comparedtoselection,optimizationinnoisyenvironmentsisevenmore
challenging,becausenotonlyafew,butcombinatoriallymanyalternatives
needtobecompared.ForthattheOCBAprocedureisadaptedtoonly
includethosepairwisecomparisonsthatareactuallyusedbytheEA.Most
popularselectionandreplacementoperatorsarecovered.Werecommend
thenewlydevelopedlatintournamentselectionasitcombinesthelowsam-
plingerrorofstochasticuniversalsamplingwitharbitraryselectionpressure
anditspairwisestructureallowsforefficientimplementationinastatistical
procedure.Forreplacementoperatorswedorecommendthosevariantsthat
ensuresurvivalofthebestknownsolution,likeevolutionstrategies,steady-
stateEAorgenerationalEAwithelitism,toreducetheeffortofidentifying
thebestsolutiontothelastpopulationinsteadofallvisitedsolutions.
Progressoftheoptimizationisensuredbyouradaptedstatisticalselec-
tionprocedureasitisappliedineachgeneration.Theadditionalsamples
aredistributedtothesolutionsthatpromisethehighestbenefitforthecor-
rectfunctioningofanEA.Withtheadaptivestoppingrulesdeveloped,the
numberofsamplesautomaticallyvarieswiththecomplexityfacedineach
tion.genera

811

5.SummaryandOutlook

TheproposedmethodimprovesexistingapproachesforEAonstochastic
problemsintwoaspects:First,itallowstoimitate–uptoanarbitrarylevel
–thebehaviorofEAwithknownfitnessvalues,efficientlyandself-adaptive.
Second,EAusingafixednumberofsamplesperindividualcanbeimproved
byallocatingsamplestoindividuals,whicharemoreimportantforthecourse
ofanEAthanothers.Atheoreticalrelationshipforthetradeoffbetween
samplesusedinasinglegenerationandnumberofgenerationsoverallis
derived,whichcouldbeusedtoobtainoptimalsettingsforthestopping
rule.Unfortunately,thenecessaryvaluescannotbedeterminedeasilyin
.icetcpraSomefirstresultsfortheintegrationofstatisticalselectionandEAhave
beenpublishedin[Schmidt,Branke,andChick2006].
Tuningthetradeoffbetweenmoreeasilytoachievelowerselectionpres-
sureandontheotherhandlessprogressoftheoptimizationpergeneration,
oftenresultsinrelativelylowselectionpressurescomparedtothosetypically
usedindeterministicenvironments.Stochastictournamentselectionisable
toimplementsuchlowselectionpressures.Wederiveamethodthatinte-
gratestheremainingnoisefromtheindividual’sfitnessintotheprobabilistic
comparisonofstochastictournamentselectionbymodifyingtheacceptance
function.Fortypicalsettingstherequirednumberofsamplescanbereduced
by50%.Combiningthemethodwithasequentialcomparisonprocedure
allowsforafurtherreductionupto81%withoutcompromisingselection
.ylitquaThegeneralideaforthenoise-adjustedtournamentselectionhasbeen
publishedin[BrankeandSchmidt2003]andreceivedabestpaperaward.
Inthisthesisanimprovedapproachbasedonquadraticprogrammingwas
presented.Thecombinationwithsequentialcomparisonhasbeenpublished
in[BrankeandSchmidt2004].
Withrespecttotheachievementsobtainedinthisthesisforthefield
ofevolutionarycomputation,empiricalexperimentsonalargevarietyof
stochasticproblemsneedtobecarriedout,inordertorealizetheimprove-
ments.Adeeperunderstandingoftheeffectsofpopulationsizingandselec-
tionpressureisneededtotunetheparametersofthestatisticalprocedures.

911

okoOutl

and

Summary

5.

high

hitw

binedmco

lelev

certain

a

to

siebabilitpro

orerr

het

fixing

r,fa

So

ling.samp

nctiosele

sure,pres

klyquic

leads

to

ivexcesse

012

aphgrioBibly

Aizawa,A.N.andB.W.Wah(1994).Schedulingofgeneticalgorithmsin
anoisyenvironment.EvolutionaryComputation,97–122.

Albert,L.A.andD.E.Goldberg(2001).Efficientevaluationgenetical-
gorithmsunderintegratedfitnessfunctions.TechnicalReport2001024,
IllinoisGeneticAlgorithmsLaboratory,Urbana-Champaign,USA.
Arnold,D.V.(2002).NoisyOptimizationwithEvolutionStrategies.
er.wKluArnold,D.V.andH.-G.Beyer(2000a).Efficiencyandmutationstrength
adaptationofthe(µ/µi,λ)-ESinanoisyenvironment.Volume1917of
LNCS,pp.39–48.Springer.
Arnold,D.V.andH.-G.Beyer(2000b).Localperformanceofthe(µ/µi,λ)-
ESinanoisyenvironment.InW.MartinandW.Spears(Eds.),Foun-
dationsofGeneticAlgorithms,pp.127–142.MorganKaufmann.

Arnold,D.V.andH.-G.Beyer(2003).Acomparisonofevolutionstrategies
withotherdirectsearchmethodsinthepresenceofnoise.Computa-
tionalOptimizationandApplications24,135–159.

Baker,J.E.(1987).Reducingbiasandinefficiencyintheselectionalgo-
rithm.InJ.Grefenstette(Ed.),InternationalConferenceonGenetic
Algorithms,pp.14–21.LawrenceErlbaumAssociates.
Baum,C.W.andV.V.Veeravalli(1994).Asequentialprocedureformul-
tihypothesistesting.IEEETransactionsonInformationTheory40(6),
.007–29419

112

PHYABLIOGRBI

IBLIOGRAPHYB

Bechhofer,R.E.,T.J.Santner,andD.M.Goldsman(1995).Design
andAnalysisforStatisticalSelection,Screening,andMultipleCom-
parisons.NewYork:JohnWiley&Sons,Inc.
Benders,J.F.(1962).Partitioningproceduresforsolvingmixed-variables
programmingproblems.NumerischeMathematik4,238–252.
Bernardo,J.M.andA.F.M.Smith(1994).BayesianTheory.Chichester,
.WileyUK:Beyer,H.-G.(1993).Towardatheoryofevolutionstrategies:Someasymp-
toticalresultsfromthe(1,+λ)-theory.EvolutionaryComputation1(2),
8.185–16Beyer,H.-G.(2000).Evolutionaryalgorithmsinnoisyenvironments:The-
oreticalissuesandguidelinesforpractice.Computermethodsinapplied
mechanicsandengineering186,239–267.
Birge,J.R.andF.Louveaux(1997).IntroductiontoStochasticProgram-
ming.NewYork:Springer.
Boesel,J.(1999).SearchandSelectionforLarge-ScaleStochasticOpti-
mization.Ph.D.thesis,NorthwesternUniversity,Evanston,Illinois,
USA.Boesel,J.,B.L.Nelson,andS.-H.Kim(2003a).Usingrankingand
selectionto‘cleanup’aftersimulationoptimization.OperationsRe-
search51,814–825.
Boesel,J.,B.L.Nelson,andS.H.Kim(2003b).Usingrankingandse-
lectionto”cleanup”aftersimulationoptimization.OperationsRe-
search51,814–825.
Bonn,M.,F.Toussaint,andH.Schmeck(2005).JOSCHKA:Job-
SchedulinginheterogenenSystemenmitHilfevonWebservices.In
E.Maehle(Ed.),PARSWorkshopL¨ubeck,pp.inpress.Gesellschaft
f¨urInformatik.
Branke,J.(2001).EvolutionaryOptimizationinDynamicEnvironments.
er.wKlu

212

PHYABLIOGRBI

IBLIOGRAPHYB

Branke,J.,S.Chick,andC.Schmidt(2005a,December).Newdevelop-
mentsinrankingandselection:Anempiricalcomparisonofthethree
mainapproaches.InM.E.K.etal.(Ed.),Proc.WinterSimulation
Conference,pp.708–717.IEEE,Inc.
Branke,J.,S.E.Chick,andC.Schmidt(2005b).Newdevelopmentsin
rankingandselection,withanempiricalcomparisonofthethreemain
approaches.InM.Kuhl,N.Steiger,F.Armstrong,andJ.Joines(Eds.),
Proc.2005WinterSimulationConference,Piscataway,NJ,pp.inpress.
.IncE,IEEBranke,J.,S.E.Chick,andC.Schmidt(2005c).Selectingaselection
procedure.TechnologyandOperationsManagementArea,INSEAD,
er.apPorkingWBranke,J.andC.Schmidt(2003).Selectioninthepresenceofnoise.In
E.Cantu-Paz(Ed.),GeneticandEvolutionaryComputationConfer-
ence,Volume2723ofLNCS,pp.766–777.Springer.
Branke,J.andC.Schmidt(2004).Sequentialsamplinginnoisyenviron-
ments.InX.Yaoetal.(Ed.),ParallelProblemSolvingfromNature,
Volume3242ofLNCS,pp.202–211.Springer.
Buchholz,P.andA.Th¨ummler(2005).Enhancingevolutionaryalgorithms
withstatisticalsselectionproceduresforsimulationoptimization.In
N.Kuhl,M.N.Steiger,F.B.Armstrong,andJ.A.Joines(Eds.),
WinterSimulationConference,pp.842–852.IEEE.
Butler,J.,D.J.Morrice,andP.W.Mullarkey(2001).Amultipleat-
tributeutilitytheoryapproachtorankingandselection.Management
Science47(6),800–816.
Byers,J.(1991).Basicalgorithmsforrandomsamplingandtreatment
randomization.ComputersinBiologyandMedicine112(21),69–77.
Cantu-Paz,E.(2004).Adaptivesamplingfornoisyproblems.InK.Deb
etal.(Eds.),GeneticandEvolutionaryComputationConference,Vol-
ume3102ofLNCS,pp.947–958.Springer.

312

PHYABLIOGRBI

IBLIOGRAPHYB

Chen,C.-H.(1996).Alowerboundforthecorrectsubset-selectionproba-
bilityanditsapplicationtodiscreteeventsimulations.IEEETransac-
tionsonAutomaticControl41(8),1227–1231.
Chen,C.-H.,E.Y¨ucesan,L.Dai,andH.Chen(2005).Efficientcomputa-
tionofoptimalbudgetallocationfordiscreteeventsimulationexperi-
ment.IIETransactions,toappear.
Chen,E.J.andW.D.Kelton(2005).Sequentialselectionprocedures:
Usingsamplemeanstoimproveefficiency.EuropeanJournalofOper-
ationalResearch166,133–153.
Chick,S.E.andK.Inoue(1998).Sequentialallocationproceduresthat
reduceriskformultiplecomparisons.InD.J.Medeiros,E.J.Watson,
M.Manivannan,andJ.Carson(Eds.),Proc.1998WinterSimulation
Conference,Piscataway,NJ,pp.669–676.IEEE,Inc.
Chick,S.E.andK.Inoue(2001a).Newproceduresforidentifyingthe
bestsimulatedsystemusingcommonrandomnumbers.Management
Science47(8),1133–1149.
Chick,S.E.andK.Inoue(2001b).Newtwo-stageandsequential
proceduresforselectingthebestsimulatedsystem.OperationsRe-
search49(5),732–743.
Chick,S.E.andK.Inoue(2002).Corrigendum:Newselectionprocedures.
OperationsResearch50(3),566.
Chick,S.E.andY.Wu(2005).Selectionprocedureswithfrequentistex-
pectedopportunitycostbounds.OperationsResearch,toappear.
Dai,L.(1996).Convergencepropertiesofordinalcomparisoninthesimu-
lationofdiscreteeventsystems.J.OptimizationTheoryandApplica-
tions91(2),363–388.
deGroot,M.H.(1970).OptimalStatisticalDecisions.NewYork:McGraw-
Hill.DiPietro,A.,L.While,andL.Barone(2004).Applyingevolutionary
algorithmstoproblemswithnoisy,time-consumingfitnessfunctions.
InCongressonEvolutionaryComputation,pp.1254–1261.IEEE.

412

PHYABLIOGRBI

IBLIOGRAPHYB

Evans,M.,N.Hastings,andB.Peacock(1993).StatisticalDistributions
(2ed.).NewYork:Wiley.
Fitzpatrick,J.M.andJ.J.Grefenstette(1988).Geneticalgorithmsin
noisyenvironments.MachineLearning3,101–120.
Fu,M.C.(2002).Optimizationforsimulation.INFORMSJournalon
Computing14(3),192–215.
Fu,M.C.,J.-Q.Hu,C.-H.Chen,andX.Xiong(2005).Simulational-
locationfordeterminingthebestdesigninthepresenceofcorrelated
sampling.INFORMSJournalonComputing,toappear.
Genz,A.andF.Bretz(2002).Comparisonofmethodsforthecomputation
ofmultivariatetprobabilities.JournalofComputationalandGraphical
Statistics11(4),950–971.
Gertz,E.M.andS.J.Wright(2003).Object-orientedsoftwarefor
quadraticprogramming.ACMTransactionsonMathematicalSoft-
ware29,58–81.
Goldberg,D.,G.Korb,andK.Deb(1989).Messygeneticalgorithms:
Motivation,analysis,andfirstresults.ComplexSystems3,493–530.
Goldberg,D.E.andK.Deb(1991).Acomparativeanalysisofselection
schemesusedingeneticalgorithms.InG.Rawlins(Ed.),Foundations
ofGeneticAlgorithms,SanMateo,CA,USA.MorganKaufmann.
Goldsman,D.,S.-H.Kim,W.S.Marshall,andB.L.Nelson(2002).Rank-
ingandselectionforsteady-statesimulation:Proceduresandperspec-
tives.INFORMSJournalonComputing14(1),2–19.
Gupta,S.S.andK.J.Miescke(1994).Bayesianlookaheadonestage
samplingallocationsforselectingthelargestnormalmean.Statistical
Papers35,169–177.
Hammel,U.andT.B¨ack(1994).Evolutionstrategiesonnoisyfunctions,
howtoimproveconvergenceproperties.InY.Davidor,H.P.Schwefel,
andR.M¨anner(Eds.),ParallelProblemSolvingfromNature,Volume
866ofLNCS.Springer.

512

PHYABLIOGRBI

IBLIOGRAPHYB

He,D.,S.E.Chick,andC.-H.Chen(2005).Theopportunitycostand
OCBAselectionproceduresinordinaloptimization.submitted.
Hedlund,H.E.andM.Mollaghasemi(2001).Ageneticalgorithmand
anindifference-zonerankingandselectionframeworkforsimulation
optimization.InWinterSimulationConference,pp.417–421.IEEE.
Ho,Y.C.,R.S.Sreenivas,andP.Vakili(1992).Ordinaloptimizationof
deds.JournalofDiscreteEventDynamicSystems2(2),61–88.
Inoue,K.,S.E.Chick,andC.-H.Chen(1999).Anempiricalevaluation
ofseveralmethodstoselectthebestsystem.ACMTOMACS9(4),
7.401–38Jin,Y.andJ.Branke(2005).Evolutionaryoptimizationinuncertainen-
vironments–asurvey.IEEETransactionsonEvolutionaryComputa-
tion9(3),303–317.
Kall,P.andS.W.Wallace(1994).StochasticProgramming.Chichester,
UK:JohnWileyandSons.
Kelton,W.D.,R.P.Sadowski,andD.A.Sadowski(1998).Simulation
withArena.Boston:McGraw-Hill.
Kim,S.-H.andB.L.Nelson(2001).Afullysequentialprocedurefor
indifference-zoneselectioninsimulation.ACMTOMACS11,251–273.
Kim,S.-H.andB.L.Nelson(2005).Selectingthebestsystem.InS.G.
HendersonandB.L.Nelson(Eds.),HandbookinOperationsResearch
andManagementScience:Simulation.Elsevier.(toappear).
Kleywegt,A.J.,A.Shapiro,andT.H.deMello(2001).Thesampleaver-
ageapproximationmethodforstochasticdiscreteoptimization.SIAM
JournalonOptimization12(2),479–502.
Krishnamoorthy,K.andD.Benton(2003).Computingdiscretemixtures
ofcontinuousdistributions:noncentralchisquare,noncentraltandthe
distributionofthesquareofthesamplemultiplecorrelationcoefficient.
ComputationalStatisticsandDataAnalysis43,249–267.

612

PHYABLIOGRBI

IBLIOGRAPHYB

Law,A.M.andW.Kelton(1991).SimulationModelingandAnalysis.New
w-Hill.McGraork:YLaw,A.M.andW.D.Kelton(2000).SimulationModeling&Analysis
(3rded.).NewYork:McGraw-Hill.
Lerch,M.,G.Tischler,J.W.vonGudenberg,W.Hofschuster,and
W.Kraemer(2001).Theintervallibraryfilib++2.0-design,features
andsampleprograms.Preprint2001/4,UniversityofWuppertal.
Matsumoto,M.andT.Nishimura(1998).Mersennetwister:A623-
dimensionallyequidistributeduniformpseudorandomnumbergener-
ator.ACMTOMACS8(1),3–30.
Michalewicz,Z.andD.B.Fogel(1999).Howtosolveit:ModernHeuris-
Springer..ticsMiller,B.L.(1997).Noise,Sampling,andEfficientGeneticAlgorithms.
Ph.D.thesis,Dept.ofComputerScience,UniversityofIllinoisat
Urbana-Champaign.availableasTR97001.
Miller,B.L.andD.E.Goldberg(1996).Geneticalgorithms,selection
schemes,andthevaryingeffectsofnoise.EvolutionaryComputa-
tion4(2),113–131.
Nelson,B.L.andS.Banerjee(2001).Selectingagoodsystem:Procedures
andinference.IIETransactions33(3),149–166.
Nelson,B.L.andD.Goldsman(2001).Comparisonswithastandardin
simulationexperiments.ManagementScience47(3),449–463.
Niederreiter,H.(1992).Randomnumbergenerationandquasi-montecarlo
.SIAMds.methoRinne,H.(1997).TaschenbuchderStatistik.FrankfurtamMain:Harri
h.DeutscRinott,Y.(1978).Ontwo-stageselectionproceduresandrelatedproba-
bilityinequalities.CommunicationsinStatistics,799–811.
Schmidt,C.,J.Branke,andS.Chick(2006).Integratingtechniquesfrom
statisticalrankingintoevolutionaryalgorithms.Springer.

712

BLIOGRBIPHYA

IBLIOGRAPHYB

Stagge,P.(1998).Averagingefficientlyinthepresenceofnoise.InA.E.
Eiben,T.Ba¨ck,M.Schoenauer,andH.-P.Schwefel(Eds.),Parallel
ProblemSolvingfromNatureV,Volume1498ofLNCS,pp.188–197.
er.SpringTong,Y.L.(1980).ProbabilityInequalitiesinMultivariateDistributions.
NewYork:Academic.
Wald,A.(1947).SequentialAnalysis.NewYork:JohnWiley.
Wald,A.(1950).StatisticalDecisionFunctions.NewYork:JohnWiley,
Inc.Welch,B.L.(1938).Thesignificanceofthedifferencebetweentwomeans
whenthepopulationvariancesareunequal.Biometrika25,350–362.
Whitley,D.(1989).TheGENITORalgorithmandselectionpressure:Why
rank-basedallocationofreproductivetrialsisbest.InJ.D.Schaffer
(Ed.),ProceedingsoftheThirdInternationalConferenceonGenetic
Algorithms,SanMateo,CA.MorganKaufman.
Wilson,J.R.andA.A.B.Pritsker(1984).Experimentalevaluationof
variancereductiontechniquesforqueueingsimulationusinggeneralized
concomitantvariables.ManagementScience30,1459–1472.

812