desideratumsyntaxhighlighter

DependencyInjectionforProgrammingbyOptimizationZoltanA.
Kocsis1andJerrySwan21.
SchoolofMathematics,UniversityofManchester,OxfordRoad,ManchesterM139PL,UK.
zoltan.
kocsis@postgrad.
manchester.
ac.
uk2.
ComputerScience,UniversityofYork,DeramoreLane,York,YO105GH,UK.
July14,2017AbstractProgrammingbyOptimizationtoolsperformauto-maticsoftwarecongurationaccordingtothespeci-cationsuppliedbyasoftwaredeveloper.
Developersspecifydesignspacesforprogramcomponents,andtheoneroustaskofdeterminingwhichcongurationbestsuitsagivenusecaseisdeterminedusingau-tomatedanalysistoolsandoptimizationheuristics.
However,incurrentapproachestoProgrammingbyOptimization,designspacespecicationandexplo-rationreliesonexternalcongurationalgorithms,ex-ecutablewrappersandfragile,preprocessedprogram-minglanguageextensions.
HereweshowthatthearchitecturalpatternofDependencyInjectionprovidesasuperioralterna-tivetothetraditionalProgrammingbyOptimizationpipeline.
WedemonstratethatcongurationtoolsbasedonDependencyInjectiontnaturallyintothesoftwaredevelopmentprocess,whilerequiringlessoverheadthancurrentwrapper-basedmechanisms.
Furthermore,thestructuralcorrespondencebetweenDependencyInjectionandcontext-freegrammarsyieldsanewclassofevolutionarymetaheuristicsforautomatedalgorithmconguration.
Wefoundthatthenewheuristicssignicantlyoutperformexistingcongurationalgorithmsonmanyproblemsofinter-est(inonecasebytwoordersofmagnitude).
WeanticipatethatthesedevelopmentswillmakePro-grammingbyOptimizationimmediatelyapplicabletoalargenumberofenterprisesoftwareprojects.
1IntroductionPropercongurationofsoftwareisaparticularlychallengingissueinbothresearchandindustry.
In-teractionsbetweendesigndecisionshaveeectsonperformanceandfunctionalitythatarediculttopredict.
Theobservationthatautomatedalgorithmcongurationandparametertuningtoolscansim-plifythistaskhasledtoanewsoftwaredevelopmentparadigm:ProgrammingbyOptimization(PbO)[10].
DevelopmentinthePbOparadigmconsistsofspec-ifyinglargedesignspacesofprogramcomponentimplementations:theoneroustaskofdeterminingwhichcomponentsworkbestinagivenusecaseisachievedviaautomatedanalysistoolsandoptimiza-tionheuristics.
ThestandardProgrammingbyOptimizationtoolsoperateondesignspacesspeciedinaspecializedextensionofatargetprogramminglanguage,trans-formedintothetargetlanguagebyaspecializedweavertool.
Theoptimizationchoicesoverthecom-bineddesignspacearemadebyaseparatealgorithmcongurationtool,whichhashistoricallybeenap-1arXiv:1707.
04016v1[cs.
AI]13Jul2017pliedtotheresultingexecutableprogram.
Theweaver-basedarchitectureseverelylimitstheapplicabilityofProgrammingbyOptimization.
TherelianceonmarkupextensionshinderstheadoptionofPbOforexistingcodebases.
Inaddition,theex-ternalcongurationtoolshavetooperateontheexe-cutableviaabrittletextualinterface(commandlinearguments),whichintroducessignicantoverheadandmakeson-lineoptimizationdicult.
Despitetheseshortcomings,nonewalternativetoweavertoolshasbeenintroducedsincetheinitialPbOpro-posal.
WedevelopedContainAnt,asoftwarelibraryforProgrammingbyOptimizationthataddressestheselimitationsbyreplacingsyntacticextensionsandweaverswiththeDependencyInjectionarchitecturalpattern[18].
Byexploitingastructuralcorrespon-dencebetweenDependencyInjectionandcontext-freegrammars,weobtainanewclassofgrammar-basedevolutionaryheuristicssuitableforautomatedalgorithmconguration.
Wedeterminedthatthesenewheuristicssignicantlyoutperformexistingcon-gurationalgorithmsonseveralcommoncongura-tiontasksandoptimizationproblems,bothintermsofsolutionqualityandexecutionspeed(inonecasereducingtheoptimizationtimefromfourhoursto46seconds).
Thispaperdiscussesthetheoryandimplementa-tionoftheContainAntlibraryanditsgrammar-basedheuristics.
Sections1.
1and1.
2introduceDe-pendencyInjectionandreviewtheexistingworkonProgrammingbyOptimization.
Section2describesthetheoreticalcorrespondencebetweenDependencyInjectionandoptimizationproblemsovercontext-freegrammars,whileSection3givesnovelheuristicsforsolvingtheresultinggrammaticaloptimizationproblemsusinggeneticalgorithmsandantcolonytechniques.
TheremainderofthepaperanalyzesvedierentexperimentsusedtoevalutetheperformanceoftheContainAntheuristics.
1.
1DependencyInjectionObject-orientedsoftwareprovidesfunctionalityviamultipleinterdependentcomponents.
Softwareengi-neeringeortstohandletheproblemsofdependencyinstantiationandreferenceacquisitionbetweenthesecomponentshasledtothewidespreadadoptionofanewtypeofmiddlewarelibrary,theso-calledDepen-dencyInjection(DI)container[18].
Theterm"De-pendencyInjection"wascoinedbyFowler[7]in2004andDIcontainershaveseenincreasinglywidespreaduseoverthelastdecade,withpopularframeworksincludingtheJavaTMSpringframework1andGoogleGuice2.
SoftwarewrittenusingDIinherentlyexposeshighlystructuredcongurationparameters:compo-nentsareconguredbysearchingoverthespaceofde-pendencies,withoutmodifyingthesourcecodeofthecomponentsthemselves.
ThetraditionaloperationofaDIcontaineristoperformthewiringbetweentheconstructorsofdependentobjects(alsoknownasthe'objectgraph')byconsultingacongurationobjectorlethatcontainsalistofbindingsbetweenab-stracttypesandtheirconstructorarguments.
Thecontainerthenselectsatargetclassandgreedilysup-pliesthedependenciestoasuitableconstructorofthetargetclass.
Atthispoint,itisworthnotingasignicantlimitationofsomepopularDIcontainers(e.
g.
Guice):congurationisnotpossibleiftheobjectgraphcontainsambiguitiessuchasachoiceofmul-tiplesubtypesofanabstractclass.
AsdescribedindetailinSection3,theoptimizationbasedapproachofContainAntremovesthislimitation.
1.
2RelatedWorkIntheirseminalworkonProgrammingbyOptimiza-tion,Hoosetal.
[10]delineatedvelevelsofPbO,ranginginsophisticationfromtuningtheexposedparametersofanapplication(Level0)totheuseofevidence-basedmethodsforexploringlargedesignspacesasthedrivingactivityforthesoftwaredesignprocess(Level4).
TorealizethehigherlevelsofPbO,theyintroducedtheconceptofaPbO-enhancedlanguage:asupersetofanexistingprogramminglanguage(e.
g.
PbO-JavaorPbO-C)whichincludesconstructsfordeclaringthepossibledesignchoicesforparametersandblocks1http://projects.
spring.
io/spring-framework2https://github.
com/google/guice2ofcode.
Thecodewritteninthismarkuplanguageistranslatedintothetargetlanguageviaasyntac-tictransformationperformedbyaspecializedPbOweavertool,reminiscentofamacropreprocessor.
Theoptimizedchoices(asdeterminedoverthecombineddesignspacesonasetoftrainingcases)aremadebyanexternalautomaticcongurationtool.
Congurationoptimizershavebeenproposedthatusevariousheuristics,e.
g.
iteratedlocalsearch[12],geneticalgorithms[1]anditeratedracing[14].
Ano-tableachievementofPbOisthedevelopmentanduseoftheSMACcongurationtool[11]toimproveuponthestate-of-the-artinSATsolvingbytuningparam-etersoftheSpearSATsolver.
Whilethemajorityofcongurationoptimizersaremodel-free,SMACal-ternatesbetweenbuildingaregressionmodeltopre-dictcongurationperformanceandgatheringaddi-tionalperformancedatabasedonthismodel.
Theregressionmodelisobtainedviarandomforests,amethodwhichisknowntoperformwelloncategori-calvariablesandalsoallowsquanticationofuncer-tainty.
SearchBasedSoftwareEngineering(SBSE)[9]istheapplicationofheuristicsearchtovariousaspectsofthesoftwaredevelopmentprocess,withastronghistoricalemphasisonsoftwaretesting.
Muchre-centinterestwithinSBSEhasfocusedon'embeddedadaptivity'[8],i.
e.
allowingsoftwaredeveloperstodelegatetheconguration/generationofspeciedas-pectsofprogramfunctionalitytoheuristicsearchpro-cedures[4].
SuchSBSEactivityisthereforestronglyalignedwiththepreviouslystatedgoalsofPbO,butoftenwithemphasisonagenerationprocesswhichcanresponddynamicallytochangesintheoperat-ingenvironmentoftheprogram.
PreviousworkinthisareaincludesGen-O-Fix[26]andECSELR[29],bothofwhichareembeddedmonitorsystemsthatsupportsearchviaEvolutionaryComputation.
Tem-plarandPolytopearetwoalternativeapproachestosoftwarecomponentgeneration:Templar[25]providesa'top-down'frameworkfororchestratingoneormore'variationpoints'generatedbyGeneticProgramming,whilePolytope[27]usesmethodsfromdatatypegenericprogrammingtosupportthe'bottomup'generationofindividualvariationpointsinsourcecode.
SinceDependencyInjectioncontainersalreadyau-tomateanon-trivialpartoftheSoftwareEngineeringprocess,theyprovideanaturalentrypointfortheapplicationofheuristicmethodsfromSBSE.
2GrammaticalOptimizationBackus-NaurForm(BNF)isawidelyadoptedsyn-taxfordescribingcontext-freelanguages.
Forthesakeoftechnicalconvenience(theabilitytohavedierentrewriteruleswithidenticalbodies),wepresentaslightvariationoftheusualnotion,thelabeledBNFformalismintroducedbyFors-bergandRanta[6].
Formally,suchagrammarGconsistsofthefollowingcomponents:AsetofterminalsymbolsGT.
Thesearetheliteralsorwordsthatmakeupthelanguage.
Apointedsetofnon-terminalsymbolsGN,withadistinguishedstartsymbols∈GN.
Thesecategorizethesub-expressionsofthelan-guage.
AsetofrewriterulesGR.
Normally,eachrewriterulehastheform(a,b)wherea∈GNandbisasequenceofsymbolsfromGT∪GN.
SincewearedealingwithlabeledBNF,rewriteruleshavetheform(,a,b)whereisauniquelabel,theleft-handsideaisanon-terminalandtheright-handsidebisanitesequenceofsymbolsfromGT∪GN.
Atthispoint,itiscustomarytointroducetheno-tionofsentence:asequenceofterminalsymbolsob-tainedfromthestartsymbolsbyapplyingasequenceofrewriterules,i.
e.
byreplacingnon-terminalswiththeright-handsidesofthecorrespondingrewriterules.
Suchasequenceofrulescanberepresentedasarootedtreeknownasaderivationtree.
Agrammarisunambiguousifeachofitssentenceshasauniquecorrespondingderivationtree.
Inpractice,theactualsentencesofthelanguageturnouttobeimmaterialfromtheperspectiveofagrammaticaloptimizationproblem,soitissimplertoworkfromadirectdenitionofderivationtrees.
Thusweignoretheunderlyingsentencesaltogether3andinductivelydeneaderivationtreeofsortx∈GNtoconsistofthefollowingdata:Arewriteruleoftheform(,x,b),Aderivationtreeofsorta∈GNforeverynon-terminalsymbolainthesequenceb.
Fromhereon,allderivationtreesareassumedtohavesorts(thestartsymbolofthegrammarG).
ThesetofallsuchderivationtreesisdenotedD(G).
Grammarscanbespeciedbylistingtheirrewriterulesinthefollowingformat:Label.
::=RHSwhereangledbracketsareusedtodistinguishbe-tweenterminalsandnon-terminals.
Twoelementaryexamplesfollow:2.
0.
1BinaryStringsThegrammarofbinarystringsisgivenby:GT={0,1,e},GN={s},GR={(0,s,0s),(1,s,1s),(e,s,e)}.
Usingtheshorthanddenedabove,therewriterulescouldalsobewrittenas0.
::=01.
::=1e.
::=eDerivationtreesforthisgrammarcorrespondtonitesequencesofbinarydigits(withebeingtheterminatingcharacter).
Agrammarofstringsoveranygivennitealphabetcanbedenedanalogously.
2.
0.
2FiniteSetsAnynitesetSgivesrisetoagrammarbysettingGT=S,GN={s},GR={(x,s,x)|x∈S}.
Thederivationtreesofthisgrammarareinbijec-tivecorrespondencewithelementsofthesetS.
2.
1ProblemStatementAninstanceofthegrammaticaloptimizationproblemisgivenbythefollowingdata:AgrammarGandAnobjectivefunctionf:D(G)→RdenedonthederivationtreesofthegrammarG.
Withoutlossofgenerality,weassumethatourgoalismaximizingtheobjectivefunction,i.
e.
solvingthegrammaticaloptimizationproblemconsistsofndingagloballyoptimalderivationtree:x=argmaxx∈D(G)f(x).
Thedenitionaboveisextremelygeneral:indeed,everydiscreteoptimizationproblemcanbereducedtothegrammaticaloptimizationproblemoverthegrammarofbinarystrings.
2.
2SemanticsOnecanreduceanoptimizationprobleminstancewithcandidatesolutionsSandobjectivefunctionf:S→Rtoaninstanceofthegrammaticaloptimiza-tionproblembygivinganencodinggrammarGandasurjectivefunctionk:D(G)→→Swithsurjectivityensuringthateverycandidateso-lutionisdescribedbyatleastonesentenceofthelanguage.
Toforbidad-hocencodings(e.
g.
theencodingofanydiscreteoptimizationproblemintothegrammarofbinarystringsdiscussedabove),oneshouldthinkofthefunctionkasgivingasemanticstothesen-tencesofthelanguagedenedbythegrammarG.
Fromhereon,wedemandthatthesemanticsbecom-positional:themeaningofaderivationtreeshouldbegivenintermsofthemeaningsofitsparts(directsub-trees).
Thecompositionalityrequirementprovidesaformalcounterparttotheintuitivedesideratumthatthestructureofthegrammarberelatedtothestruc-tureofthesearchspaceS,withoutrulingoutanyinterestinggrammaticalrepresentations.
4Wewillshortlyseethatbothdependencyinjec-tionandthealgorithmcongurationproblemhavesensible,compositionalrepresentationsasinstancesofthegrammaticaloptimizationproblem.
What'smore,thesameholdsformanyproblemsofinterestinbothcontinuousandcombinatorialoptimization.
2.
3RosettaStoneAnalyzingtheprocessofdependencyinjectionleadstoapowerful"dictionary"correlatingtheterminol-ogyofgrammarswiththeterminologyofobject-orientedprogramming.
IfthegoalistoinstantiateanobjectofsomegivenclassC,onersthastondaconstructorofC(iftheclasshasnoconstructors,instantiationisimpossible).
Inturn,theselectedcon-structorwillexposezeroormoreclassesasdepen-dencies.
Iftheselectedconstructorc()hasnodepen-dencies,theobjectcanbeinstantiateddirectlybycallingc().
However,ifthereareoneormoredepen-denciesD1,D2,onehastorecursivelyinstantiateobjectsd1,d2,.
.
.
compatiblewiththegivenclassesbeforecallingc(d1,d2,toinstantiateanobjectofclassC.
Now,letGbeagrammar.
Toconstructaderiva-tiontreeofsomegivensorts∈GN,onestartsbychoosingarewriterulewithleft-handsides(nosuit-abletreecanexistintheabsenceofsucharule).
Iftheright-handsideofthechosenrewriterulecon-tainsnonon-terminals,theconstructionisnished.
However,iftheright-handsidecontainsoneormorenon-terminalsn1,n2,GN,onehastorecursivelyconstructaderivationtreeforeachsortnibeforeconstructingthederivationtreeforthetargetsorts.
Thestructureofthealgorithmsfordependencyinjectionandderivationtreeconstruction(Algo-rithms1and2)turnouttobenigh-identical.
Thissuggestsananalogybetweendependencyinjectionandgrammaticaloptimization,withclassescorre-spondingtonon-terminals,constructorscorrespond-ingtorewriterulesandconstantscorrespondingtoterminals.
Thus,thegrammaticalrewriterulecorre-spondingtotheconstructor(Javasyntax)Tctor(T1a1,T2a2,underthisassignmentissimplyctor.
::=ctor[.
.
.
]Withthiscorrespondenceinmind,wecannowrecastdependencyinjectionasagrammaticaldeci-sion/optimizationproblem.
GivenagrammarG,decidingwhetherD(G)=amountstosolvingadependencyinjectionproblem.
Thecorrespondencegivesrisetoasemanticsassign-ingtheconstructedobjecttoeachderivationtreeofthegrammar.
Inthesequel,thisisreferredtoastheusualsemantics.
Algorithm1ClassinstantiationusingDependencyInjectionfunctioninstantiate(t:Class)forcint.
constructors{trytoconstructeachargumentrecursively}fori:=0toc.
arguments.
lengthargs[i]:=instantiate(classOf(a))endfor{ifrecursivecallssucceed}if!
args.
contains(null)returnc(args){callconstructor}endif{elsetrythenextconstructor}endforreturnnullendfunctionAlgorithm2RecursiveDerivationTreeConstruc-tionfunctionconstruct(t:Sort)forcint.
rewriteRules{trytoconstructeachsubtreerecursively}fori:=0toc.
nonterminals.
countsubtrees[i]:=construct(sortOf(i))endfor{ifrecursivecallssucceed}if!
subtrees.
contains(null)returnTree(c,subtrees)endif{elsetrythenextrewriterule}endforreturnnullendfunction53HeuristicsContainAntis,rstandforemost,aDependencyInjectionlibrary.
InordertobeaswidelyapplicableasProgrammingbyOptimization,thedefaultheuris-ticsofContainAntcannotbeproblem-specic:theyhavetooperateatthelevelofproblemde-scriptions.
Metaheuristicsthatonlyexistasnature-inspiredmetaphorsorinformalalgorithmtemplates(i.
e.
withouttheabilitytoautomaticallytransformaproblemspecicationintoaworkingimplementation)areinsucientforthis.
Theserequirementsleaveuswitharathersmallclassofsuitablemetaheuristics,whichwenowdescribe.
3.
1GeneticProgramming:GrEvoIncorporatingcontext-freegrammarsintogeneticprogrammingwasproposedbyRyanetal.
[21].
TheirseminalworkonGrammaticalEvolutionallowedtheeliminationoftheclosurerequirement,amajordraw-backofuntypedGeneticProgramming,whichre-quiredallfunctionstobeabletoacceptasinputtheoutputsofallotherfunctions.
Thegenotypesarenumericalsequences,translatedintosentencesofaBNFgrammarusingthemappingofAlgorithm3.
TranscribedintothederivationtreeformalismofSec-tion2,thegenotypesencodethechoiceofrewriteruleateachrecursivestepofthederivationtreeconstruc-tion(Algorithm1).
Algorithm3GrEvoGenotype-PhenotypeMap-pingfunctiongetPhenotype(g:List[Int],t:Sort){chooserewriterulebasedongenotype}c:=t.
rewriteRules[g.
head]g:=g.
tailfori:=0toc.
nonterminals.
countsubtrees[i]:=getPhenotype(g,sortOf(i))endforreturnTree(c,subtrees)endfunctionSinceGrammaticalEvolutionallowsthegenerationofsyntacticallycorrectsentencesinanarbitrarylan-guage,itsimplementationsarenottiedtoanyspe-cicproblem,andareabletooperateonanyfor-malgrammarspecication.
GrammaticalEvolutionremainsthemostpopularmetaheuristicofitskind,generallyoutperformingderivatealgorithmssuchasGrammaticalSwarm[17].
TheContainAntdistributionincludesanimple-mentationoftheGrammaticalEvolutionmetaheuris-ticwithxed-lengthgenotypesforsolvingthegram-maticaloptimizationproblem.
ThisimplementationishenceforthcalledGrEvo.
Theperformanceanal-ysis(Section5.
3)showsthatsomecharacteristicsofGrEvo,suchasitsprematureconvergenceandpoorlocality,makeitsuboptimalfortacklingthegram-maticaloptimizationproblem.
Thislimitationmoti-vatesthenovelgrammar-basedheuristicintroducedbelow.
3.
2AntProgramming:GrAntAntcolonyoptimizationmethodsarethemainal-ternativetoGeneticProgrammingfortheauto-matedproductionofcomputerprogramsviastochas-ticsearch.
AntProgrammingbasedonBNFgram-marshasbeeninvestigatedbyKeberandSchus-ter[13]underthenameGeneralizedAntProgram-ming(GAP)inthecontextofoptionpricing,andlaterbySalehi-AbariandWhite[22]forgeneralau-tomaticprogramming(EGAP).
Thedevelopmentoftheseheuristicsledtowhathasbeencalledan"up-hillbattle"betweenthetwomethods,whilegeneticprogrammingwasfoundtobestatisticallysuperiortoEGAP[23].
Here,wedescribeanovelantcolonyalgo-rithm(GrAnt)forsolvingthegrammaticalop-timizationproblemthatsignicantlyoutperformsGrammaticalEvolutionondiverseoptimizationproblems.
ThenewheuristicisbasedontheMIN-MAXAntSystem[24],butdiersfrompreviousAntProgrammingalgorithmsontwokeypoints:1.
Thepheromonelevels(associatedwithrewriterules)areboundedbetweenaminimumandmaximumpheromonevalue.
However,themax-imumistreatedasasoftboundthatcanbechangedbyspeciceventsoverthecourseofthesearch.
62.
Eachantconstructsacompletederivationtreeinadepth-rst,targetedfashion(cf.
EGAP'auseofpartialsentencesandnon-terminals).
GrAnt(Algorithm4)maintainsapheromonetable,holdingapheromonelevellyingbetweenahardminimumlevelτmin,andasoftmaximumτmaxforeveryrewriterule.
Asearchiterationbe-ginswitheachantconstructingaderivationtreeofthetargetsort.
Theconstructionproceedsbyrecur-sivelychoosingrewriterulesusingsimplepheromone-proportionalselection.
Thetnessoftheconstructedtreesiscalculated,pheromonesareupdatedbyap-plyingevaporation.
Theiteration-bestantisallowedtodepositpheromonesbyaddingthetnessvaluetothepheromonelevelofeachrewriteruleusedinthederivation.
Iftheiteration-besttnesseverexceedsτmax,thenτmaxisupdatedtothehighervalue.
Themotivationforthisbehaviorisassigningmoreweighttopheromoneincreasescausedbyndingtsolu-tionsvs.
pheromonebuildupcausedbyrepeatedlyexploringanareaofthesearchspace.
Asanaddi-tionalbenet,thiseliminatestheneedfornormaliz-ingtheamountofpheromonesontheedges(shaking).
Uponreachingthestoppingcondition,thealgorithmreturnstheoverallbestsolutionfound.
4ImplementationContainAntisimplementedasaDependencyIn-jectionlibraryfortheScalaprogramminglan-guage.
Thestaticallytyped,object-orientedna-tureofScalamakesitwell-suitedforDepen-dencyInjection,anditsrun-timereectionfacili-tiestremendouslysimplifytheContainAntarchi-tecture.
Moreover,ScalarunsontheJavaVirtualMachine,allowingthelibrarytoworkwithcodebaseswritteninanyJVMlanguage(includingClojureandJava).
ContainAnt'sjobisassemblingobjectsandob-jectgraphs.
Ineect,thelibrarytakesoverobjectin-stantiation.
Insteadofusingthenewkeywordwithaconstructortoinstantiateclasses,theprogrammerre-questsaninstanceofagivenclassfromContainAnt(ContainAntcreate[ClassName]).
ThecontainerAlgorithm4GrAntHeuristicfunctiongrant(t:Sort)while(!
stopped)solv:=construct(p,t){wlog1ant}iter:=fitnessOf(solv)evaporatePheromone()forruleinsolvaddPheromone(rule,iter)endfor{updatemaxpheromone}ifiter>taumaxthentaumax:=iterendif{updatebestsolution}iffitnessOf(best)>iterthenbest:=solvendifendwhilereturnbestendfunction{recursivepathconstruction}functionconstruct(p:Pheromones,t:Sort){pheromoneproportionalruleselection}c:=p.
select(rewriteRules(target)){constructsubtreeforeachnonterminaloftheselectedrule}fori:=0toc.
nonterminals.
countsubtrees[i]:=construct(p,sortOf(i))endforreturnTree(c,subtrees)endfunction7thenheuristicallydetermineswhattobuildbyresolv-ingdependencies,choosingappropriateconstructorsandwiringeverythingtogether.
Totakeadvantageoftheheuristiccapabilities,theprogrammerhastosupplyanobjectivefunc-tion.
Withtheexceptionofthisobjectivefunc-tion,thecongurationofContainAntismodeledonGoogle'spopularGuicedependencyinjectionli-brary.
TheprogrammerprovidesaModule(aplainobjectimplementingamarkertrait)containingtheconstructorsandhelperfunctionstobeuseddur-ingDependencyInjection.
IfthesoftwaretobeoptimizedusesDependencyInjection,thesemod-uleswillalreadybepresent,readytobeusedbyContainAnt.
ThisisinstrictcontrastwiththeweaverapproachtoProgrammingbyOptimization:weaverrulesarenotpresentinprogramsthatwerenotdesignedwiththecorrespondingPbOtoolsetinmind.
ContainAntparsesmodulespecicationsusingScala'sreectioncapabilities,turningtheDepen-dencyInjectionproblemintoagrammaticalopti-mizationinstance.
Ouranalysis(Section5.
3)indi-catesthatthedefaultGrAntsearchheuristicsucestosolvemanyoptimizationandalgorithmcongura-tionproblemswithoutproblem-specictuning.
ThismeansthatusingContainAntdoesnotrequirethepractitionertodealwithgrammars,orevenbeingawareoftheheuristicsworking"underthehood".
SinceContainAntactslikeanordinarydepen-dencyinjectioncontainer,takingovertheinstantia-tionofobjectsandresolutionofdependencies,itneednotdistinguishbetweeno-lineandon-lineadaptiveoptimization:thedistinctioncanbemadebyusinganembeddedwrappertoselectbetween'constructonrstuse'ordynamic/periodicreconstruction[4].
Therearenomajorobstaclestoturningthecon-tainerintoadrop-inreplacementforGuicebyim-plementingthecompleteGuiceAPI,thusmakingPbOimmediatelyavailabletohundredsofenterprisesoftwareprojects.
Thisispossiblythemostim-portantapplicationofthecorrespondencedetailedinSection2,andthemainfuturetargetofCon-tainAntdevelopment.
5CaseStudiesTodemonstratethegeneralbehaviorofCon-tainAntandSMAC[11],andtocomparetheper-formanceoftheirheuristics,weimplementedtwoclassicaloptimizationproblems(Braninfunction,SubsetSum)andthreealgorithmcongurationprob-lems(D-aryheaps,skiplistsandsyntaxhighlighting).
Forcomparisonpurposes,oneproblemofeachclasswasalsoimplementedforusewithSMAC.
Inthissection,weoeradetailedlookateachproblem,followedbyaperformancecomparisonshowingthatGrAntsignicantlyoutperformtheotherheuristicsinallbutoneoftheseproblems.
5.
1ClassicalProblems5.
1.
1BraninFunctionInthisrstcasestudy,wecompareContainAntwithSMAConaglobaloptimizationproblem.
ThegoalistominimizethevalueoftheBraninfunctiononagivenboundedsubsetoftheEuclideanplane.
TheBraninfunction(introducedbyDixonandSzegointheirtraditionaloptimizationtestsuit[5])haslongbeenapopularbenchmarkforcontinuousoptimiza-tionheuristics.
Thefunctionhastheformbranin(x1,x2)=x25.
14π2x21+5πx162+10118πcos(x1)+10withthedomainrestrictedsothatx1∈[5,10]andx2∈[0,15].
Therearethreeglobalminimaonthisdomain,eachwithvalue0.
397=2.
481.
TheBraninfunctionprovidesanidealcontextforcomparingthebehaviorandtheperformanceofSMACandContainAnt,sincetheSMACdistri-butionalreadyincludesacongurationforoptimiz-ingtheBraninfunctioninoneofthedefaultexamplescenarios.
Therearemanypracticaltechniquesforrepresent-ingacontinuoussolutionspaceasaBNFgrammar.
Themostintuitivewayisincludingasucientlyne"uniformgrid"ofconstantsfromthedomainaster-minalsofthegrammar.
Alternatively,thegrammar8ofbinarystringspresentedinSection2canrepresenteverydyadicfractioninacompactinterval.
Dyadicfractionsformadensesubsetoftheintervalandpro-videarbitrary-precisionapproximationstoanygivennumber.
Wedecidedtogowiththeformer,morein-tuitivegrammarforthisexperiment.
Theresultisalargegrammarwithmanyterminals,butonethatalignsverywellwithSMAC'ssolutionrepresenta-tion,therebyensuringthatbothheuristicsexploresearchspacesofthesamesize,whichleadstoacom-pletelyfaircomparison.
5.
1.
2SubsetSumGivenanitesetofintegersSZandtargetnum-berc∈Z,isthereasubsetISsuchthati∈Ii=cKnownas"subsetsum",thisisoneoftheur-examplesofanNP-completedecisionproblem.
Re-castasanoptimizationproblem,wewillattempttomaximizethefunctionf(I)=|cI|1withf(I)=2ifI=c.
Weusetwosubsetsumbench-markinstances(P01andP03)fromBurkardt'sSci-enticComputingDataset[2]forthiscasestudy.
ThegrammarforthisinstanceconsistsofthenitegrammargeneratedbythenumbersinS,alongwiththefollowinggenericrewriterulesforconstructingsetsofnumbers:empty.
::=emptyadd.
::=addwiththeobviouscompositionalsemanticsk(empty)=k(addyz)={k(y)}∪k(z)Noticethattheargument-passingsystemofSMACwouldnotbecapableofsupplyingargumentsofthiscomplexity.
TheexperimentislimitedtotheCon-tainAntheuristics,with100runsandtheheuristicscappedat1000objectivefunctionevaluations.
5.
2ProgrammingbyOptimization5.
2.
1D-aryHeapsAmin-heap(resp.
max-heap)structureisarootedtreeinwhicheverynodehasavaluelarger(smaller)thanthevalueofitsparent.
AD-aryheapisaheapstructurebuiltonacompleteD-arytree.
Thefamil-iarbinaryheapsareD-aryheapswithD=2.
Gen-eralD-aryheapsallowfasterkeyupdateoperationsthanthebinarycase—O(logDn)vs.
O(log2n).
ThismakesD-arymin-heaps(resp.
max-heaps)ap-propriateforalgorithmswheredecrease(increase)operationsaremorecommonthanminimum(max-imum)extraction.
Generalizingthebinarycase,theunderlyingtreecanalwaysbeimplementedasanarray,withthechil-drenoftheithnodeplacedatindicesiD+1,iD+2,iD+D.
Thisimplementationstrategyim-provescacheeciencyandenablesrandomaccess.
Thereisaperformancetrade-o,however:thearraywilleventuallyllup,triggeringanexpensiveresizeoperation.
AD-aryheapdatastructureimplementedwithar-rayshasthreeparameters:theinitialsizeofthear-ray,theexpansionfactoroftheresizeoperation,and(ofcourse)thearityD.
Theoptimalvaluesoftheseparametersdependontheexpectednumberofvaluestobestoredinthestructure,aswellastheexpecteddistributionofdecrease/increaseandminimum/max-imumextractionoperations.
TheoptimizationofD-aryheapswasimplementedbyHoosandHsuasatestinstancefortheoriginalProgrammingbyOptimizationproposal.
Theorig-inalcodeiswritteninanextendeddialectoftheJavaprogramminglanguage,designedforusewithaPbOweaver.
Theweaver-specicdeclarationshavetobefactoredoutintoconstructorarguments-amerethreelinesofchanges,oneforeachparame-terdescribedabove.
TheresultingstandardJavaisdirectlyusablebyContainAnt.
Thegrammarforthedatastructurecongurationproblemconsistsoftheconstructorforthedynamicheapclassastheonlyproperrewriterule;thereareclassesandconstantsforheaps,theirarities,expan-sionfactorsandinitialsizes,allofthemequipped9Figure1:Aternarymin-heapanditsarrayrepresen-tation.
withtheirusualsemantics.
Theobjectivefunctioncountsthenumberofaccessestotheunderlyingar-ray(witheachresizeoperationcountingastwoac-cessesforeachindex,inlinewiththeusualamortizedanalysisforarraylists)underagiventestload.
Eval-uatingtheobjectivefunctionforthistaskisveryex-pensive,sotheexperimentislimitedto10runs,withtheheuristicscappedat1000objectivefunctioneval-uations.
5.
2.
2SkiplistsSkiplistsareaprobabilitisticalternativetobalancedbinarysearchtrees[19].
Skiplistsareessentiallyor-deredlinkedlistswhereeachnodemaycontainmul-tipleforwardlinks.
Inthefamiliarlinkedlist,anodeconsistsofavalue(apieceofdata)andalinktothenextnode.
Nodesinaskiplistcontainawholehierar-chyoflinks,eachonepointingtoafarthersubsequentnodethantheonebelowit.
Theseauxiliarylinksprovidean"expresslane"fornavigatingthestruc-tureandcanbeexploitedtoimplementallthreedic-tionaryoperations(insertion,lookupanddeletionofvalues)withlogarithmicexpectedtimecomplexity.
Thus,theperformanceofskiplistsiscomparabletothatofbalancedbinarysearchtrees.
Skiplistsareparametrizedbytwonumericvalues:thetransitionprobabilityp∈Randthemaximalheightofthehierarchyh∈N.
Tondagivenvaluevinaskiplist,startbyfollowingthehighestlevellinksFigure2:Skiplistwithathree-layerhierarchy.
ofthehierarchy,advancinguntileithervisencoun-tered,orthevalueofthenextnodeisgreaterthanv.
Inthelattercase,continuethesearchbyfollow-inglinksoneleveldowninthehierarchy.
Toinsertagivenvaluevintoaskiplist,startbyndingitslocationusingthemethoddescribedabove.
Createanodeforstoringv.
Now,generateauniformran-domrealx∈[0,1]andlinkthenewlycreatednodetoitsneighborsinlevelofthehierarchyifandonlyifpk>.
Whenp=0.
5,onecanintuitivelythinkofthisprocessasaseriesofcoinips.
Ifyougetheads,youlinkthenodetoitsneighborsonlevelofthehierarchy,thenrepeattheprocedureonlevel+1.
Ifyougettailsorreachthemaximumheight=h,theinsertionoperationends.
Insteadofhavingaxedparameterp,wheretheprobabilityofinsertingavalueintolevelkofthehier-archyisalways1pk,onecanconsideramoregeneralskiplistarchitecture,wherethisprobabilityisgivenby1Pk,whereP:N→R+isanarbitrarymonotonesequence.
Intheexperiment,wewillfocusonthreedierenttypesofsequences:Geometric:Pk=akforsomea>1,Arithmetic:Pk=a+kforsomea>0andSumsoftheprevioustwotypes.
Hence,ourskiplistswillhavetwoparameters:themaximumheighth,andtheprobabilitysequenceP.
Theexpectedtimecomplexityoflookupsisindepen-dentofthedistributionofthevalues[15].
However,theoptimalchoicesoftheparametersPandhdode-pendontheexpectednumberofitemstobestoredintheskiplist.
Skiplistsareoftenstoredinadistributedfashion,wheretheoptimalcongurationmayfurtherdependonvariablessuchasnetworklatency,givingrisetoanon-linedatastructurecongurationprob-lem.
10ContainAntisreadilyabletosolvethisparame-tertuningproblem—indeed,wehavealreadyevalu-atedthiscapabilityonamuchlargersearchspaceinSection5.
2.
1.
However,wecanuseoptimizationtoexploreamoreinterestingsearchspacebyconsider-ingageneralizedvariantofskiplists.
Letpdenotethe(non-terminalcorrespondingto)theclassofintegersequences.
Thegrammarforthisdatastructurecongurationproblemhasarewriterulecorrespondingtotheconstructoroftheskiplistclass,aswellasthreespecialrewriterulesforcon-structingtheprobabilitysequences:geom.
::=geomarit.
::=aritsum.
::=sumThecompositionalsemanticsassignsk(geomy)=(1,k(y),k(y)2,k(y)3k(arity)=(1,1+k(y),1+2k(y)k(sumyz)=k(y)k(z)wherethesymboldenotesthetermwisesumoftwosequences.
Asintheothergrammars,thereareconstructorsforskiplistsandconstantsforthenu-mericalparameters,allofthemequippedwiththeirusualsemantics.
Thisshowsthatthegrammati-calapproachcanconvenientlyrepresentsophisticatedsearchspacesthatwouldbedicultandsometimesimpossibletodescribeviaSMAC'stext-basedcong-urationles.
Theobjectivefunctionllstheskipliststructurewith1000randomvalues,andperforms100randomlookups,measuringthetotalnumberofcom-parisonsperformed.
Allheuristicsarecappedat100objectivefunctionevaluations.
Thesearchisfastenoughtomake100runsoftheexperimentfeasible.
5.
2.
3SyntaxHighlightingThisnalcasestudyservestoshowcaseapracticalusecaseforProgrammingbyOptimizationingen-eralandContainAntinparticular:thecreationofsoftwarewithsearch-based"dynamicadaptive"fea-tures.
Ourminimalexampleisasyntaxhighlighterthatautomaticallyadjustsitselftodierentdisplayenvironments.
Thepotentialapplicationsincludebattery-savingcolorschemescompatibleacrossdif-ferentdevices(usingthetechniqueofBurlesetal.
[3]toincorporateenergyconsumptionintotheobjectivefunction)andschemesthatremainreadablewhentransplantedtodierentenvironments(e.
g.
embed-dedintosocialmediaordisplayedbythexedback-groundcolor"webview"ofamobileapplication).
AgdaisanincreasinglypopulardependentlytypedprogramminglanguagedesignedbyUlfNorell[16].
TheAgdacompilercangeneratedocumenta-tionwebpageswhichincludethenavigable,syntax-highlightedsourcecodeofthecompiledsoftware.
Un-fortunately,thedefaultcolorschemeforthesyn-taxhighlightingisunreadableondarkbackgrounds,whichcausesproblemswhenembeddingthegener-ateddocumentationintoalargerwebsite.
OurtestprogramgeneratesareadablecolorschemeforAgdadocumentationgivenatargetback-groundcolorasinput.
Theprogramconsistsoflittlemorethananaivetnessfunctionquantifyingthereadabilityofacolorschemebypenalizinglowcon-trastandbyrewardingcolorschemesbasedaroundasmallnumberofcomplementarycolors.
AllofthesearchisrelegatedtoeitherSMACorContainAnt.
Theformerrequiresacongurationlewith27cat-egoricalvariables,eachwith27options.
Inaddition,about100linesofboilerplatecodehadtobewrittenforhandlingcommandlineargumentsandinterfac-ingwithSMAC.
ForContainAnt,thegrammarspecication,consistingoftheconstructorsfortheColorSchemeandRGBValueclasses,takes37linesal-together.
Theheuristicsarecappedat1000objectivefunctionevaluations.
5.
3AnalysisAllexperimentswereperformedonthefollowingsys-tem:CPU:IntelXeonE5-2676clockedat2.
40GHzwith30MBLevel3cache,RAM:1019280ktotal,Swap:disabled,JVMversion:1.
8.
0121.
11ThedataandcodethatactuallyconductedthisanalysisarepublishedinthecompanionGitHubrepository3ofthearticle.
TheContainAntimple-mentationisdeterministic,andtherepositorybun-dlesaconvenientbuildscript,allowinganyonetoex-ecutethesameanalysisandreplicate/duplicateourresults.
Theperformanceoftheheuristicswascomparedonthreevariables:1.
Themeanquality(avg)achievedbythebestofrunsolutionreturnedbytheheuristic,averagedoverallruns.
2.
Theoptimumquality(max)achievedbythebestofrunsolutionreturnedbytheheuristic,takenoverallruns.
3.
Thevariance4(var)ofthequalityachievedbythebestofrunsolutions,takenoverallruns.
ThesignicanceofthedierencesbetweentheperformanceofthetopheuristicsischeckedusingthenonparametricprotocolofWinebergandChris-tensen[28].
Thenalp-valuesarereportedinTa-ble1.
Eachexperimentisperformedwithaxednumberofruns(thatnumberdependingonthecasestudy,asexplainedintherespectivesubsections).
Ourgoalistopickthetechniquethatachievesthesolutionofthehighestqualitypossible,givenasinglerunwithaxedbudgetof"computationaleort".
Toensurefaircomparison,weneedtolimitthenumberofob-jectivefunctionevaluationsidenticallyforallheuris-tics.
Fortheconstructiveheuristics(randomsearchandGrAnt),thiscaneasilybeachievedbycappingthenumberofiterations.
ForGrEvo,thenumberofevaluationsdependsonlyonthepopulationsizeandthenumberofgenerations,allowingustolimitthenumberofevaluationsbycappingtheproductofthesetwoparameters.
SMAChasamechanismforimposingthiscapdirectlyviathecongurationle.
3https://github.
com/zaklogician/ContainAnt4Importantforon-lineoptimization,wheretheheuristicswillberunalargenumberoftimes.
Atechniquewithhighmeanbutlowvariancemaywellloseouttoanothertechniquewithlowermeanbuthighvarianceoveralargenumberofruns.
TheGrEvoheuristichassometunable(hyper)-parameters,includingpopulationsizeandthenum-berofgenerations.
Wehand-selectedthebest-performingratiooftheseparametersfromtheset{(100:10),(40:25),(25:40),(10:100)}separatelyforeachcasestudy.
ContainAntiscapableoftuningthehyper-parametersofitsownheuristics.
InprincipleContainAntcouldbeusedasitsownhyper-heuristictoself-improveGrEvo.
Weexperi-mentedwiththesecapabilitiesduringtheearlydaysofdevelopment.
However,weabandonedthisavenueonceevidenceemergedthatsignicantimprovementtotheseparameterswouldnotbepossiblewithintheconstraintsofthecasestudies(seetheparagraphded-icatedtoGrEvobelow).
Table1summarizestheresultsachievedbySMACandtheContainAntheuristicsonallvecasestud-iespresentedabove.
GrAntTheGrAntheuristicsignicantlyoutperformedallothersinthemajorityofexperiments.
Theonlyexceptionisthesyntaxhighlightingstudy,whereGrEvosystematicallyhadthehighestnominalmean.
However,hypothesistestingrevealsthatthedierencesarenotsignicant.
GrAntistheonlyheuristictoperformequallywellacrossbothcom-binatorialoptimizationandalgorithmcongurationproblems,andtheonlyonetondgloballyoptimalsolutionstoboththeBraninfunctionandbothsubsetsuminstances.
GrEvoThepoorperformanceoftheGrEvoheuristic,con-sistentacrossparametersettings,iscryingoutforanexplanation.
Ourinvestigationsuggeststhatthemainculpritmaybeearlylossofdiversity(visibleintheSkipliststudy,wherethealgorithmconvergesinamerevegenerations),causedbythefactthattherstfewelementsofthegenomehaveadis-proportionatelyhighinuenceonthephenotypeinGrammaticalEvolution[20].
Increasingthepopula-tionsizeisnotpossiblewithoutmovingbeyondthestrictcomputationalboundsofourcasestudies,ren-12Table1:PerformanceofSMAC,ContainAntheuristicsandrandomsearchonthevecasestudies.
Branin:GrAntGrEvoRand.
SMACmax:2.
481.
552.
452.
48avg:1.
800.
871.
371.
47var:0.
240.
080.
320.
35p:<.
001SubsetSumP02:GrAntGrEvoRand.
SMACmax:2.
001.
001.
00-avg:0.
910.
650.
03-var:0.
450.
220.
02-p:<.
001SubsetSumP03:GrAntGrEvoRand.
SMACmax:2.
000.
000.
00-avg:0.
380.
000.
00-var:0.
620.
000.
00-p:<.
001DHeap:GrAntGrEvoRand.
SMACmax:468014680146801-avg:468014675246594-var:01067152919-p:0.
168Skiplist:GrAntGrEvoRand.
SMACmax:0.
330.
250.
27-avg:0.
280.
250.
25-var:0.
010.
000.
00-p:<.
001SyntaxH.
Blue:GrAntGrEvoRand.
SMACmax:37.
8238.
0237.
57-avg:34.
3634.
5032.
18-var:5.
858.
737.
46-p:0.
663SyntaxH.
Yellow:GrAntGrEvoRand.
SMACmax:34.
9234.
6833.
8534.
44avg:31.
5132.
3329.
2230.
92var:4.
023.
305.
675.
22p:0.
082deringGrammaticalEvolutionunsuitableformanyreal-timeapplications.
Solvingthisissuecouldbeanavenueoffurtherresearch.
SMACAsexpected,thequalityoftheresultsreturnedbySMACsignicantlyoutperformedrandomsearchinallcases.
However,theaveragequalitylingeredbe-neaththatofGrAntinthecaseoftheBraninfunc-tion(althoughthebestsolutionfortheBraninfunc-13tionwasgloballyoptimal)andbeneathbothCon-tainAntheuristicsinthealgorithmcongurationcase.
Anothermajorissueisspeed:SMACspendsoverfourhoursonlatterproblem,whiletheCon-tainAntheuristicsnishbothin46seconds.
6ConclusionDependencyInjectioncanbeusedtoimprovetheexistingweaver-basedProgrammingbyOptimizationtools.
Wehavedescribedalibrarythatimplementsseveralgrammaticaloptimizationmetaheuristics,in-cludinganovelAntProgrammingapproach.
Theli-braryprovidesbettersupportforProgrammingbyOptimizationthanspecializedlanguageextensionsandweavertools,whiledoingawaywithseverallim-itationssuchasdicultieswithon-lineoptimization.
Furthermore,regardingDependencyInjectionasaninstanceofagrammaticaloptimizationproblemleadstoawholenewclassofheuristicsforautomaticalgorithmconguration.
TheproposedgrammaticalAntProgrammingheuristicGrAntsignicantlyout-performsexistingalgorithmsonveproblemsofin-terest,inonecasereducingafourhourlongSMACoptimizationtaskto46secondswhilesignicantlyimprovingonthesolutionquality.
ProgrammingbyOptimizationlibrariescanactasdrop-inreplacementforexistingDependencyInjec-tioncontainers,makingPbOimmediatelyapplicabletoalargenumberofenterprisesoftwareprojects.
ThedevelopmentofContainAntinthisdirectionisapromisingtargetoffuturework.
References[1]CarlosAnsotegui,MeinolfSellmann,andKevinTierney.
AGender-basedGeneticAlgorithmfortheAutomaticCongurationofAlgorithms.
InProceedingsofthe15thInternationalConferenceonPrinciplesandPracticeofConstraintPro-gramming,CP'09,pages142–157,Berlin,Hei-delberg,2009.
Springer-Verlag.
[2]J.
Burkardt.
DatafortheSubsetSumProblem.
Availableathttps://people.
sc.
fsu.
edu/~jburkardt/datasets/subset_sum/subset_sum.
html,2013.
AccessedApril12,2017.
[3]N.
Burles,E.
Bowles,B.
R.
Bruce,andK.
Sriv-isut.
SpecialisingGuava'sCachetoReduceEn-ergyConsumption.
InSearch-BasedSoftwareEngineering-7thInternationalSymposium,SS-BSE2015,Bergamo,Italy,September5-7,2015,Proceedings,pages276–281,2015.
[4]NathanBurles,JerrySwan,EdwardBowles,AlexanderE.
I.
Brownlee,ZoltanA.
Kocsis,andNadarajenVeerapen.
EmbeddedDynamicIm-provement.
InProceedingsoftheCompan-ionPublicationofthe2015AnnualConfer-enceonGeneticandEvolutionaryComputation,GECCOCompanion'15,pages831–832,NewYork,NY,USA,2015.
ACM.
[5]L.
C.
W.
DixonandG.
P.
Szego.
Theglobalopti-mizationproblem:anintroduction.
InL.
C.
W.
DixonandG.
P.
Szego,editors,TowardsGlobalOptimisation,volume2.
NorthHolland,Amster-dam,TheNetherlands,1978.
[6]M.
ForsbergandA.
Ranta.
TheLabelledB.
N.
F.
GrammarFormalism.
Technicalreport,ChalmersUniversityofTechnology,Gothen-burg,Sweden,022005.
[7]M.
Fowler.
InversionofControlContain-ersandtheDependencyInjectionpattern.
http://martinfowler.
com/articles/injection.
html,retr.
10April,2015.
[8]MarkHarman,YueJia,WilliamB.
Langdon,JustynaPetke,ImanHematiMoghadam,ShinYoo,andFanWu.
GeneticImprovementforAdaptiveSoftwareEngineering(Keynote).
InProceedingsofthe9thInternationalSymposiumonSoftwareEngineeringforAdaptiveandSelf-ManagingSystems,SEAMS2014,pages1–4,NewYork,NY,USA,2014.
ACM.
[9]MarkHarman,S.
AfshinMansouri,andYuanyuanZhang.
Search-basedSoftwareEngi-neering:Trends,TechniquesandApplications.
ACMComput.
Surv.
,45(1):11:1–11:61,Decem-ber2012.
14[10]HolgerH.
Hoos.
Programmingbyoptimization.
Commun.
ACM,55(2):70–80,2012.
[11]F.
Hutter,H.
H.
Hoos,andK.
Leyton-Brown.
SequentialModel-BasedOptimizationforGen-eralAlgorithmConguration.
InProc.
ofLION-5,page507523,2011.
[12]FrankHutter,HolgerH.
Hoos,KevinLeyton-Brown,andThomasSt¨utzle.
ParamILS:AnAu-tomaticAlgorithmCongurationFramework.
J.
Artif.
Int.
Res.
,36(1):267–306,September2009.
[13]C.
KeberandM.
G.
Schuster.
OptionValuationwithGeneralizedAntProgramming.
InProceed-ingsofthe4thAnnualConferenceonGeneticandEvolutionaryComputation,GECCO'02,SanFrancisco,CA,USA,2002.
MorganKauf-mannInc.
[14]ManuelLopez-Ibanez,JeremieDubois-Lacoste,LesliePerezCaceres,ThomasSt¨utzle,andMauroBirattari.
Theiracepackage:Iteratedracingforautomaticalgorithmconguration.
OperationsResearchPerspectives,3:43–58,2016.
[15]R.
MotwaniandP.
Raghavan.
RandomizedAlgo-rithms.
CambridgeInternationalSeriesonPar-allelComputation.
CambridgeUniversityPress,Cambridge,UK,1995.
[16]U.
Norell.
DependentlyTypedProgramminginAgda.
InProceedingsofthe4thInternationalWorkshoponTypesinLanguageDesignandIm-plementation,TLDI'09,NewYork,NY,USA,2009.
ACM.
[17]M.
O'NeillandA.
Brabazon.
GrammaticalSwarm:Thegenerationofprogramsbysocialprogramming.
NaturalComputing,5(4):443–462,2006.
[18]D.
R.
Prasanna.
DependencyInjection.
ManningPublications,1stedition,2009.
[19]W.
Pugh.
SkipLists:AProbabilisticAlterna-tivetoBalancedTrees.
CommunicationsoftheACM,33(6):668–676,1990.
[20]F.
RothlaufandM.
Oetzel.
OntheLocal-ityofGrammaticalEvolution.
InP.
Col-let,M.
Tomassini,M.
Ebner,S.
Gustafson,andA.
Ekart,editors,Proceedings,GeneticProgramming:9thEuropeanConference(Eu-roGP2006),Berlin,Heidelberg,2006.
Springer-Verlag.
[21]C.
Ryan,J.
J.
Collins,andM.
O'Neill.
Gram-maticalEvolution:EvolvingProgramsforanArbitraryLanguage.
InW.
Banzhaf,RPoli,M.
Schoenauer,andT.
C.
Fogarty,editors,Pro-ceedingsoftheFirstEuropeanWorkshoponGeneticProgramming,volume1391ofLNCS,Berlin,Germany,1998.
Springer-Verlag.
[22]A.
Salehi-AbariandT.
White.
EnhancedGen-eralizedAntProgramming(EGAP).
InPro-ceedingsofthe10thAnnualConferenceonGe-neticandEvolutionaryComputation,GECCO'08,NewYork,NY,USA,2008.
ACM.
[23]A.
Salehi-AbariandT.
White.
TheuphillbattleofAntProgrammingvs.
GeneticProgramming.
InProceedingsoftheInternationalJointCon-ferenceonComputationalIntelligence(IJCCI),2009.
[24]T.
St¨utzleandH.
H.
Hoos.
MAX-MINAntSystem.
FutureGenerationComputerSystems,2000.
[25]JerrySwanandNathanBurles.
GeneticPro-gramming:18thEuropeanConference,EuroGP2015,Copenhagen,Denmark,April8-10,2015,Proceedings,chapterTemplar–AFrameworkforTemplate-MethodHyper-Heuristics,pages205–216.
SpringerInternationalPublishing,Cham,2015.
[26]JerrySwan,MichaelG.
Epitropakis,andJohnR.
Woodward.
Gen-O-Fix:Anembed-dableframeworkforDynamicAdaptiveGeneticImprovementProgramming.
(CSM-195):1–12,01/20142014.
[27]JerrySwan,KrzysztofKrawiec,andNeilGhani.
PolytypicGeneticProgramming.
InGiovanni15Squillero,editor,20thEuropeanConferenceontheApplicationsofEvolutionaryComputation,volume10200ofLNCS,pages66–81,Amster-dam,19-21April2017.
Springer.
[28]M.
WinebergandS.
Christensen.
StatisticalAnalysisforEvolutionaryComputation:Intro-duction.
InProceedingsofthe11thAnnualCon-ferenceCompaniononGeneticandEvolutionaryComputationConference:LateBreakingPapers,GECCO'09,pages2949–2976,NewYork,NY,USA,2009.
ACM.
[29]KwakuYeboah-AntwiandBenoitBaudry.
Em-beddingAdaptivityinSoftwareSystemsUsingtheECSELRFramework.
InProceedingsoftheCompanionPublicationofthe2015AnnualCon-ferenceonGeneticandEvolutionaryComputa-tion,GECCOCompanion'15,pages839–844,NewYork,NY,USA,2015.
ACM.
16