Heuristic selection for stochastic search optimization Modeling solution quality by extreme

VincentA.Cicirello1andStephenF.Smith2

DepartmentofComputerScience,CollegeofEngineering,DrexelUniversity,3141ChestnutStreet,Philadelphia,PA19104

cicirello@cs.drexel.edu

2

TheRoboticsInstitute,CarnegieMellonUniversity,5000ForbesAvenue,Pittsburgh,PA15213

sfs@cs.cmu.edu

1

Abstract.Thesuccessofstochasticalgorithmsisoftenduetotheirabilitytoeffectivelyamplifytheperformanceofsearchheuristics.Thisiscertainlythecasewithstochasticsamplingalgorithmssuchasheuristic-biasedstochasticsam-pling(HBSS)andvalue-biasedstochasticsampling(VBSS),whereinaheuristicisusedtobiasastochasticpolicyforchoosingamongalternativebranchesinthesearchtree.OnecomplicationingettingthemostoutofalgorithmslikeHBSSandVBSSinagivenproblemdomainistheneedtoidentifythemosteffectivesearchheuristic.Inmanydomains,therelativeperformanceofvariousheuristicstendstovaryacrossdifferentprobleminstancesandnosingleheuristicdomi-nates.Insuchcases,thechoiceofanygivenheuristicwillbelimitinganditwouldbeadvantageoustogainthecollectivepowerofseveralheuristics.Towardthisgoal,thispaperdescribesaframeworkforintegratingmultipleheuristicswithinastochasticsamplingsearchalgorithm.Initsessence,theframeworkusesonline-generatedstatisticalmodelsofthesearchperformanceofdifferentbaseheuristicstoselectwhichtoemployoneachsubsequentiterationofthesearch.Toestimatethesolutionqualitydistributionresultingfromrepeatedapplicationofastrongheuristicwithinastochasticsearch,weproposetheuseofmodelsfromextremevaluetheory(EVT).OurEVT-motivatedapproachisvalidatedontheNP-Hardproblemofresource-constrainedprojectschedulingwithtimewin-dows(RCPSP/max).UsingVBSSasabasestochasticsamplingalgorithm,theintegrateduseofasetofprojectschedulingheuristicsisshowntobecompeti-tivewiththecurrentbestknownheuristicalgorithmforRCPSP/maxandinsomecasesevenimprovesuponbestknownsolutionstodifficultbenchmarkinstances.

1Introduction

ThesuccessofstochasticsamplingalgorithmssuchasHeuristic-BiasedStochasticSampling(HBSS)[1]andValue-BiasedStochasticSampling[2,3]stemsfromtheirabilitytoamplifytheperformanceofsearchheuristics.Theessentialideaunderlyingthesealgorithmsistousetheheuristic’svaluationofvariouschoicesatagivensearchnodetobiasastochasticdecision,and,indoingso,torandomlyperturbtheheuristic’sprescribed(deterministic)trajectorythroughthesearchspace.InthecaseofHBSS,arank-orderingofpossiblechoicesisusedasheuristicbias;inVBSS,alternatively,the

actualheuristicvalueattributedtoeachchoiceisused.Thisstochasticchoiceprocessenablesgenerationofdifferentsolutionsonsuccessiveiterations(orrestarts),andef-fectivelyresultsinabroadersearchinthe“neighborhood”definedbythedeterministicheuristic.HBSShasbeenshowntosignificantlyimprovetheperformanceofaheuris-ticforschedulingtelescopeobservations[1].VBSShasshownsimilarabilitytoim-provesearchperformanceinweighted-tardinessscheduling[2,3],resource-constrainedprojectscheduling[3],andinamulti-roverexplorationdomain[4].

ThedrawbacktostochasticsamplingalgorithmssuchasHBSSandVBSSisthattheyrequireidentificationofanappropriatedomainheuristic,andsearchperformanceisultimatelytiedtothepoweroftheheuristicthatisselected.Heuristics,however,arenotinfallible,andinmostdomainstheredoesnotexistasingledominatingheuristic.Insteaddifferentheuristicstendtoperformbetterorworseondifferentproblemin-stances.Insuchcases,thechoiceofanysingleheuristicwillultimatelybelimitinganditwouldbeadvantageoustogainthecollectivepowerofseveralheuristics.Theideaofexploitingacollectionofheuristicstoboostoverallperformancehasbeenexploredinothersearchcontexts.AllenandMintonusesecondaryperformancecharacteristicsasindicatorsforwhichheuristicalgorithmisperformingmoreeffectivelyforagivenCSPinstance[5].Othershavebeenapplyingrelativelysimplelearningalgorithmstotheproblemofselectingfromamongalternativelocalsearchoperators[6,7].Workonalgorithmportfolios[8]andtherelatedA-Teamsframework[9]takeamoreaggressiveapproach,executingseveraldifferentheuristicsearchalgorithmsinparallel.

Inthispaper,weconsidertheproblemofintegratingmultiplesearchheuristicswithinastochasticsamplingalgorithm.Ratherthancarefullycustomizingavarianttouseacompositeheuristic,theapproachtakenhereistoinsteaddesignasearchcon-trolframeworkcapableofacceptingseveralsearchheuristicsandself-customizingahybridalgorithmonaperprobleminstancebasis.Generallyspeaking,ourapproachviewseachsolutionconstructedbythestochasticsamplingalgorithmasasampleoftheexpectedsolutionqualityofthebaseheuristic.Overmultiplerestartsonagivenprobleminstance,weconstructsolutionqualitydistributionsforeachheuristic,andusethisinformationtobiastheselectionofheuristiconsubsequentiterations.Gomesetal.’sanalysisanduseofruntimedistributionshasledtomuchsuccessinconstraintsatisfactiondomains[10].Inasimilarway,ahypothesisofthispaperisthatsolutionqualitydistributionscanprovideananalagousbasisforunderstandingandenhancingtheperformanceofstochasticsamplingproceduresinsolvingoptimizationproblems.Assuggestedabove,thesearchcontrolframeworkdevelopedinthispaperusesonline-generatedstatisticalmodelsofsearchperformancetoeffectivelycombinemul-tiplesearchheuristics.Considerthatastochasticsearchalgorithmsamplesasolutionspace,guidedbyastrongdomainheuristic.Ourconjectureisthatthesolutionsfoundbythisalgorithmonindividualiterationsaregenerally“good”(withrespecttotheover-allsolutionspace)andthatthese“good”solutionsarerareevents.Thisleadsustothebodyofworkonextremevaluetheory(EVT).EVTisthestatisticalstudyofrareoruncommonevents,ratherthantheusual(e.g.,studyofwhathappensattheextremeofadistributioninthetail).WithourconjecturestatedandwithrespecttoEVT,wecanviewthedistributionofsolutionqualitiesfoundbyastochasticheuristicsearchalgo-rithmasasortofsnapshotofthetailofthedistributionofsolutionqualitiesoftheover-

allsearchspace.WespecificallyemployadistributioncalledtheGeneralizedExtremeValue(GEV)distributiontomodelthesolutionqualitiesgivenbyindividualiterationsofthesearchalgorithm.WeimplementthisEVT-motivatedapproachintwoways:1)usingawell-known,butnumericallyintensivecomputationofamaximumlikelihoodestimationoftheGEV;and2)usingkerneldensityestimationtunedassumingaGEV.

UsingVBSSasabasestochasticsamplingprocedure,wevalidatethisEVT-motivatedheuristicperformancemodelingandheuristicselectionpolicyontheNP-Hardproblemofresource-constrainedprojectschedulingwithtimewindows(RCPSP/max).AsabaselineandtovalidateourEVTassumptions,wecomparetheperformanceoftheapproachwithonethatmakesthenaiveassumptionthatthesolutionqualitiesarenormallydistributed.Wefurtherbenchmarktheapproachagainstseveralwell-knownheuristicalgorithms,findingthatourEVT-motivatedalgorithmiscompeti-tivewiththecurrentbestknownheuristicalgorithmforRCPSP/max;andinsomecasesevenimprovesuponcurrentbestknownsolutionstodifficultprobleminstances.

2ModelingaSolutionQualityDistribution

2.1ExtremeValueTheoryMotivation

Considerthatthesolutionstoahardcombinatorialoptimizationproblemcomputedoneachiterationofastochasticsamplingalgorithmareinfactattheextremewhentheoverallsolution-spaceisconsidered.Ifoneweretosamplesolutionsuniformlyatran-dom,theprobabilityisverylowthatanyofthesolutionsgeneratedbyastochasticsearchthatisguidedbyastrongheuristicwouldbefound.Inotherwords,goodsolu-tionstoanygivenprobleminstancefromtheclassofproblemsofgreatestinteresttousare,inasense,rarephenomenawithinthespaceoffeasiblesolutions.

Forexample,usingBresina’sconceptofaqualitydensityfunction(QDF)[11],weexaminedseveralprobleminstancesofaweightedtardinessschedulingproblem.AQDFisthedistributionofsolutionqualitiesthatonewouldobtainbysamplinguni-formlyfromthespaceofpossiblesolutionstoaprobleminstance.Foreasyprobleminstancesfromourproblemset,wefoundthattheoptimalsolutionwasonaverageover6.4standarddeviationsbetterthantheaveragefeasiblesolutiontotheproblem;thevalueoftheaveragesolutiongivenbyastochasticsamplerguidedbyastrongdomainheuristicwasalsoover6.4standarddeviationsbetterthantheaveragesolutionintheproblemspace[3].Further,forhardprobleminstances,wefoundthattheaveragesolu-tiongivenbyasingleiterationofthestochasticsearchwasover9.1standarddeviationsbetterthantheaveragerandomsolution;thebestknownsolutionwasonaverage9.4standarddeviationsbetterthantheaveragesolutionintheproblemspace[3].2.2GeneralizedExtremeValueDistribution

Withthisnoted,weturntothefieldofextremevaluetheory,whichdealswith“tech-niquesandmodelsfordescribingtheunusualratherthantheusual”[12].Consideranextremevalueanalogtothecentrallimittheory.LetMn=max{X1,...,Xn}whereX1,...,Xnisasequenceofindependentrandomvariableshavingacommondistribu-tionfunctionF.Forexample,perhapstheXiarethemeantemperaturesforeachofthe

365daysintheyear,thenMnwouldcorrespondtotheannualmaximumtemperature.TomodelMn,extremevaluetheoriststurntotheextremaltypestheorem[12]:Theorem1.Ifthereexistssequencesofconstants{an>0}and{bn}suchthatP((Mn−bn)/an≤z)→G(z)asn→∞,whereGisanon-degeneratedistributionfunction,thenGbelongstooneofthefollowingfamilies:

b

I:G(z)=exp(−exp(−(z−a))),−∞b−α

II:G(z)=exp(−(z−)ifz>bandotherwiseG(z)=0a)

z−bα

III:G(z)=exp((a))ifzforparametersa>0,bandinthelattertwocasesα>0.

Theseareknownastheextremevaluedistributions,typesI(Gumbel),II(Fr´echet),andIII(Weibull).ThetypesIIandIIIdistributionsareheavy-tailed–oneboundedontheleftandtheotherontheright.TheGumbeldistributionismedium-tailedandun-bounded.Thesedistributionsarecommonlyreformulatedintothegeneralizationknownasthegeneralizedextremevaluedistribution(GEV):

G(z)=exp(−(1+ξ(

z−b−1/ξ

)))a

(1)

b

where{z:1+ξ(z−a)>0},−∞0,and−∞<ξ<∞.Thecasewhereξ=0istreatedasthelimitofG(z)asξapproaches0toarriveattheGumbeldistribution.UndertheassumptionofTheorem1,P((Mn−bn)/an≤z)≈G(z)forlargeenoughnwhichisequivalenttoP(Mn≤z)≈G((z−bn)/an)=G∗(z)whereG∗(z)issomeothermemberofthegeneralizedextremevaluedistributionfamily.

Themainpointhereisthattomodelthedistributionofthemaximumelementofafixed-lengthsequence(orblock)ofidenticallydistributedrandomvariables(i.e.,thedistributionof“blockmaxima”),oneneedssimplytoturntotheGEVdistributionre-gardlessoftheunderlyingdistributionoftheindividualelementsofthesequence.

2.3ModelingSolutionQualityviatheGEV

Theorem1onlyexplicitlyappliestomodelingthedistributionof“blockmaxima”.Theassumptionwenowmakeisthatthequalitydistributionforastochasticsamplingal-gorithmusingastrongheuristictosamplefromthesolutionspacebehavesthesameas(oratleastsimilarto)thedistributionof“blockmaxima”andthusitscumulativedistributionfunctioncanbemodeledbytheGEVdistribution.

TousetheGEVasourmodel,wemustfirstrecognizethatwehavebeenassumingthroughoutthatourobjectivefunctionmustbeminimizedsoweneeda“blockminima”

󰀃󰀃󰀃󰀃=min{X1,...,Xn}.WewantP(Mn󰀃󰀃󰀃󰀃󰀃󰀃

max{−X1,...,−Xn}.Therefore,Mn=−MnandP(Mn󰀃󰀃󰀃󰀃>−z)=1−P(Mn≤−z).Therefore,assumingthatthedistributionfunctionP(Mn

behavesaccordingtoaGEVdistribution,theprobabilityPioffindingabettersolutionthanthebestfoundsofar(B)usingheuristicicanbedefinedas:

Pi=1−Gi(−B)=1−exp(−(1+ξi(

−B−bi−1/ξi

)))ai

(2)

wherethebi,ai,andξiareestimatedfromthenegativeofthesamplevalues.Tocom-putetheseparameters,weuseHosking’smaximum-likelihoodestimatoroftheGEVparameters[13].InestimatingtheGEVparameters,Hosking’salgorithmiscalledmul-tipletimes,ifnecessary.Thefirstcallusesinitialestimatesoftheparametersasrecom-mendedbyHosking(setassumingaGumbeldistribution).IfHosking’salgorithmfailstoconverge,thenafixednumberofadditionalcallsaremadewithrandominitialval-uesoftheparameters.Ifconvergencestillfails,weusethevaluesoftheparametersasestimatedbyassumingatypeIextremevaluedistribution(theGumbeldistribution).32.4ModelingSolutionQualityusingKernelDensityEstimation

AsecondpossibilityforestimatingthequalitydistributionisKernelDensityEstimation(see[14]).Akerneldensityestimatormakeslittle,ifany,assumptionsregardingtheun-derlyingdistributionitmodels.Itprovidesanon-parametricframeworkforestimatingarbitraryprobabilitydensities.Theadvantageofthisapproachisthatitshouldbepos-sibletomorecloselyestimatearbitrarysolutionqualitydistributions.Kerneldensityestimationtakeslocalaveragestoestimateadensityfunctionbyplacingsmoothedoutquantitiesofmassateachdatapoint.Thekerneldensityestimatorisdefinedas:

󰀃x−Xi

ˆ(x)=1).K(f

nhi=1h

n

(3)

K(·)isakernelfunctionandhiscalledthebandwidth(alsosometimescalledthescale

parameterorspreadingcoefficient).TheXiarethensamplevalues(objectivefunctionvalueofthesolutionsgeneratedbytheniterationsofthestochasticsearchalgorithm).

ThekernelfunctionwehavechosenistheEpanechnikovkernel[15]:

√3x2

√K(x)=45(1−5)for|x|<5andotherwise0.(4)Epanechnikovshowedthatthisistheriskoptimalkernel,butestimatesusingother

smoothkernelsareusuallynumericallyindistinguishable.Thus,theformoftheker-nelcanbechosentobestaddresscomputationalefficiencyconcerns.Inourcase,theEpanechnikovkernelisaclearwinnercomputationallyforthefollowingreasons:–Wearemostinterestedinultimatelycomputingtheprobabilityoffindingabettersolutionthanthebestfoundsofar.Thiskernelfunctionallowsustoeasilycomputethecumulativeprobabilitydistributionforarbitrarysolutionqualitydistributions.√

–Duetothecondition|x|<5,onlyalimitednumberofsamplevaluesmustbeconsidered,reducingthecomputationaloverhead.

Althoughthechoiceofkernelfunctionisnotcriticalintermsofnumericalre-sults,thechoiceofbandwidthcanbeverycrucial.Epanechnikovthatthe󰀂∞showedL1/5

optimalchoiceofbandwidthish=(nM),whereL=−∞K(x)2dxwhere

󰀂∞

M=−∞(f󰀃󰀃(x))2dx,andwherenisthenumberofsamples[15].Unfortunately,this

3

Itshouldbenotedthatthisfallbackconditionappearstorarelyoccur,ifever,inourexperi-ments.

computationdependsonknowingthetruedistribution(Mdependsonf(x)).Weas-sumethattheunderlyingdistributionistheGumbeldistribution.ThereasoningbehindthisassumptionfollowsourEVTmotivation.GiventheGumbeldistributionassump-1

tion,M=4a5,whereaisthescaleparameteroftheGumbel.Notethatthestandard√

πaσ6√deviationoftheGumbeldistributionisσ=6[16].Fromthis,wehavea=π.WecannowwriteMintermsofthesamplestandarddeviation:M=usingtheEpanechnikovkernelsoL=

3√.55

Thisresultsinavalueofhcomputedas:

5

√π5.46σ5

Weare

h=0.79sn−1/5wheres=min{σ,Q/1.34}andwhereQistheinterquartilerange.

Weareinterestedinthecumulativedistributionfunctionforthepurposeofcomput-ingtheprobabilityoffindingabettersolutionthanthebestfoundsofar.Thiscanbeobtainedfromintegratingthekerneldensityestimator.Thus,wehavetheprobabilityPioffindingasolutionbetterthanthebestfoundsofar,B,givenheuristici:4

󰀄Bni

x−Si,j1󰀃

Pi=K()dx.(5)

hi0nihij=1GivenourchoiceoftheEpanechnikovkernel,thisevaluatesto:

Pi=

3

√4nihi5

󰀃

j,|

B−Si,j

hi

√|<5

1B32

−B2Si,j+BSi,j((B−2())−

5hi3

√3

√1(Si,j−hi5)

(Si,j−hi5−2(−

5hi3√2√2

(Si,j−hi5)Si,j+(Si,j−hi5)Si,j)))

(6)

Itshouldbenoted,thatifwemaintainthesamplesinsortedorder,thengiventhat

Bmustbelessthanorequaltothesmallestvalue√inthislist5,wecomputethissum

B−S

untilwereachasampleSi,jsuchthat|hii,j|≥5.Onceasampleforwhichthisconditionholdsisreachedinthelist,thesummationcanend.Actually,ratherthaninasortedlist,wemaintainthesamplesinasortedhistogram,maintainingcountsofthenumberofsampleswithgivendiscretevalues.2.5SelectingaSearchHeuristic

Amethodisneededforbalancingthetradeoffbetweenexploitingthecurrentestimatesofthesolutionqualitydistributionsgivenbythealgorithm’schoicesandtheneedforexplorationtoimprovetheseestimates.Thek-armedbanditfocusesonoptimizingtheexpectedtotalsumofrewardsfromsamplingfromamultiarmedslotmachine.Atanypointduringaniterativestochasticsamplingsearch,thereisacurrentbestfoundso-lution.Futureiterationshavetheobjectiveoffindingasolutionthatisbetterthanthe

45

Thisassumesaminimizationproblemwithlowerboundof0ontheobjectivefunction.Assumingweareminimizinganobjectivefunction.

currentbest.Fromthisperspective,abetteranalogythanthek-armedbanditwouldbetoconsideramultiarmedslotmachineinwhichtheobjectiveistosamplethearmstooptimizetheexpectedbestsinglesample–whatwehavetermedthe“Maxk-ArmedBanditProblem”[3].Elsewhere,weshowedthattheoptimalsamplingstrategysam-plestheobservedbestarmataratethatincreasesapproximatelydoubleexponentiallyrelativetotheotherarms[3].

Specifictoourproblem,thismeanssamplingwiththeobservedbestheuristicwithfrequencyincreasingdoubleexponentiallyrelativetothenumberofsamplesgiventheotherheuristics.Consider,astheexplorationstrategy,Boltzmannexplorationascom-monlyusedinreinforcementlearning[17]andsimulatedannealing[18].WithaBoltz-mannexplorationstrategy,wewouldchoosetouseheuristichiwithprobabilityP(hi):

exp((PiFi)/T)

P(hi)=󰀁H,

exp((PF)/T)jjj=1

(7)

wherePiistheprobabilityoffindingasolutionbetterthanthebestfoundsofar,where

FiistheratioofthenumberoffeasiblesolutionsusedinestimatingPitothetotalnumberofsampleswithi,wherethereareHheuristicstochoosefrom,andwhereTisatemperatureparameter.Togetthedoubleexponentialsamplingincrease,weneedtodecreaseTexponentially.Forexample,letT=exp(−N󰀃)whereN󰀃isthenumberofsamplesalreadytakenandsamplehiwithprobability:

P(hi)=󰀁H

exp((PiFi)/exp(−N󰀃))

󰀃

j=1exp((PjFj)/exp(−N))

.(8)

3ExperimentalDesign

InthisSection,considertheresourceconstrainedprojectschedulingproblemwithtimewindows(RCPSP/max).RCPSP/maxistheRCPSPwithgeneralizedprecedencerela-tionsbetweenstarttimesofactivities.ItisadifficultmakespanminimizationproblemwellstudiedbytheOperationsResearchcommunity.Findingfeasiblesolutionstoin-stancesoftheRCPSP/maxisNP-Hard,makingtheoptimizationproblemverydifficult.RCPSP/maxFormalization.TheRCPSP/maxproblemcanbedefinedformallyasfol-lows.DefineP=asaninstanceofRCPSP/max.LetAbethesetofactivitiesA={a0,a1,a2,...,an,an+1}.Activitya0isadummyactivityrepresent-ingthestartoftheprojectandan+1issimilarlytheprojectend.Eachactivityajhasafixeddurationpj,astart-timeSj,andacompletion-timeCjwhichsatisfythecon-straintSj+pj=Cj.Let∆beasetoftemporalconstraintsbetweenactivitypairs

minmax

,Ti,j].The∆aregeneralizedprecedenceoftheformSj−Si∈[Ti,j

minmax

relationsbetweenactivities.TheTi,jandTi,jareminimumandmaximumtime-lagsbetweenthestarttimesofpairsofactivities.LetRbethesetofrenewableresourcesR={r1,r2,...rm}.Eachresourcerkhasanintegercapacityck≥1.Executionofanactivityajrequiresoneormoreresources.Foreachresourcerk,theactivityajrequiresanintegercapacityrcj,kforthedurationofitsexecution.Anassignmentof

start-timestotheactivitiesinAistime-feasibleifalltemporalconstraintsaresatisfiedandisresource-feasibleifallresourceconstraintsaresatisfied.Ascheduleisfeasibleifbothsetsofconstraintsaresatisfied.TheproblemisthentofindafeasibleschedulewithminimummakespanMwhereM(S)=max{Ci}.ThatiswewishtofindasetofassignmentstoSsuchthatSsol=argminSM(S).Themaximumtime-lagconstraintsarewhatmakesthisproblemespeciallydifficult.Particularly,duetothemaximumtime-lagconstraints,findingfeasiblesolutionsalonetothisproblemisNP-Hard.

Branch-and-BoundApproaches.Therearemanybranch-and-boundapproachesfortheRCPSP/maxproblem.Thoughformanyprobleminstancesitistoocostlytoexecuteabranch-and-boundlongenoughtoproveoptimality,goodsolutionsareoftenobtainedinareasonableamountofcomputationtimethroughtruncation(i.e.,notallowingthesearchtoruntocompletion).Thecurrent(known)bestperformingbranch-and-boundapproachisthatofDorndorfetal.[19](referredtolaterasB&BDPP98).

Priority-RuleMethods.Itshouldbenotedthatapriorityrulemethod,asreferredtohere,isnotthesameasadispatchpolicy.ItactuallyreferstoabacktrackingCSPsearchthatusesoneormorepriority-rules(dispatchheuristics)tochooseanactivitytosched-ulenext,fixingitsstarttimevariable.TheRCPSP/maxisbothanoptimizationproblemandaCSP.Whenastarttimebecomesfixed,constraintpropagationthentakesplace,furtherconstrainingthedomainsofthestarttimevariables.Thespecificpriority-rulemethodthatweconsiderhereisreferredtoasthe“directmethod”with“serialschedulegenerationscheme”[20,21].Francketal.foundthedirectmethodwithserialgenera-tionschemetoperformbetteringeneralascomparedtootherpriority-rulemethods.

Theserialschedulegenerationschemerequiresapriority-ruleoractivityselectionheuristic.Thereareawidevarietyofsuchheuristicsavailableintheliterature.Neu-mannetal.recommendfiveinparticular.Thesefiveheuristicsarethosethatwelaterrandomizeandcombinewithinasinglestochasticsearch:

–LST:smallest“lateststarttime”first:LSTi=1+1LSi.–MST:“minimumslacktime”first:MSTi=1+LS1.i−ESi

–MTS:“mosttotalsuccessors”first:MTSi=|Successorsi|,whereSuccessorsiisthesetofnotnecessarilyimmediatesuccessorsofaiintheprojectnetwork.

–LPF:“longestpathfollowing”first:LPFi=lpath(i,n+1),wherelpath(i,n+1)isthelengthofthelongestpathfromaitoan+1.–RSM:“resourceschedulingmethod”:

1

RSMi=1+max(0,max(ESi+pi−LSg)).g∈eligibleset,g=iLSiandESiintheseheuristicsreferstothelatestandearlieststarttimesoftheac-tivities.NotethatwehaverephrasedafewoftheseheuristicsfromNeumannetal.’sdefinitionssothatforeach,theeligibleactivitywiththehighestheuristicvalueischo-sen.Theeligiblesetofactivitiesarethosethatcanbetime-feasiblyscheduledgivenconstraintsinvolvingalreadyscheduledactivities.

Truncatingthesearchwhenathresholdnumberofbacktrackshasbeenreachedandrestartingwithadifferentheuristiceachrestarthasbeenproposedasanefficientandeffectiveheuristicsolutionprocedure.Later,werefertothefollowingmultipleruntruncatedprioritymethods:

–PRFNS5:Executingthedirectmethodwithserialgenerationscheme5times,oncewitheachoftheheuristicsdescribedabove,andtakingthebestsolutionofthe5asoriginallysuggestedbyFranketal.[20,21].Resultsshownlaterareofourimplementation.

–PRFN10:Similarly,thisisabestof10heuristics.TheresultsshownlaterareasreportedbyDorndorfetal.[19]andCestaetal.[22]ofFranckandNeumann’sbestof10heuristicsmethod[23].6IterativeSamplingEarliestSolutions.Cestaetal.presentanalgorithmforRCPSP/maxthattheycallIterativeSamplingEarliestSolutions(ISES)[22].ISESbeginsbyfindingatimefeasiblesolutionwithamaximumhorizon(initiallyverylarge)ontheproject’smakespan,assumingoneexists.Theresultingtime-feasiblesolution,foranyinterest-ingprobleminstance,isgenerallynotresource-feasible.ISESproceedsbyiteratively“leveling”resource-constraintconflicts.Thatis,itfirstdetectssetsofactivitiesthattemporallyoverlapandwhosetotalresourcerequirementexceedstheresourcecapac-ity.Giventhesetofresource-constraintconflicts,itchoosesoneoftheconflictsusingheuristic-equivalency(i.e.,choosesrandomlyfromamongallresource-conflictswithinan“acceptanceband”inheuristicvaluefromtheheuristicallypreferredchoice).Itthenlevelsthechosenconflictbypostingaprecedenceconstraintbetweentwooftheactivi-tiesintheconflictedset.Itcontinuesuntilatime-feasibleandresource-feasiblesolutionisfoundoruntilsomeresource-conflictcannotbeleveled.Thisistheniteratedsomefixednumberoftimeswithinastochasticsamplingframework.Then,giventhebestso-lutionfoundduringthethestochasticsamplingprocess,theentirealgorithmisrepeatediterativelyforsmallerandsmallerhorizons.Specifically,thehorizonisrepeatedlysettothemakespanofthebestsolutionfoundsofaruntilnofurtherimprovementispossible.Cestaetal.showISEStoperformbetterthanthepreviousbestheuristicalgorithmfortheRCPSP/maxproblem(namelyPRFN10).

PerformanceCriteria.Thesetofbenchmarkprobleminstancesthatweuseintheex-perimentalstudyofthisSectionisthatofSchwindt.7Thereare1080probleminstancesinthisproblemset.Ofthese,1059havefeasiblesolutionsandtheother21areprovablyinfeasible.Eachinstancehas100activitiesand5renewableresources.Intheexperi-mentsthatfollow,weusethefollowingperformancecriteriawhichhavebeenusedbyseveralotherstocomparetheperformanceofalgorithmsfortheRCPSP/maxproblem:–∆LB:theaveragerelativedeviationfromtheknownlowerbound,averagedacrossallprobleminstancesforwhichafeasiblesolutionwasfound.Notethatthisisbasedonthenumberofprobleminstancesforwhichthegivenalgorithmwasabletofindafeasiblesolutionandthusmightbebasedonadifferentnumberofprobleminstancesforeachalgorithmcompared.Thiscriteria,asdefined,isexactlyasusedbyalloftheotherapproachestotheproblemavailableintheliterature.

6

7

FranckandNeumann’stechnicalreportdescribingthisbestof10strategyisnolongeravailableaccordingtoboththelibraryattheirinstitutionaswellasthesecretaryoftheirlab.Wehavebeenunabletofindoutwhatthe10heuristicsarethatproducetheseresults.http://www.wior.uni-karlsruhe.de/

LSNeumann/Forschung/ProGenMax/rcpspmax.html

–NO:thenumberofoptimalsolutionsfound.Currently,thereareknownoptimalsolutionsfor789ofthe1080probleminstances.

–NF:thenumberoffeasiblesolutionsfound.Ofthe1080probleminstances,1059possessatleastonefeasiblesolution.Theother21canbeproveninfeasible(e.g.,bythepreprocessingstepofthepriority-rulemethod).–TIME:CPUtimeinseconds.

Forallstochasticalgorithms,valuesshownareaveragesacross10runs.Valuesinparen-thesesarebestofthe10runs.Intheresults,asanaddedcomparisonpoint,welisttheabovecriteriaforthecurrentbestknownsolutionsasBEST.NotethatBESTisthebestknownpriortothealgorithmspresentedinthispaper.Wefurtherimproveuponthebestknownsolutionstosomeoftheprobleminstances,butthisisnotconsideredinBEST.Value-BiasedStochasticSampling(VBSS).Thefirstpartofourapproachusesanalgo-rithmcalledVBSS[3,2]torandomizethepriority-rulemethod.Ratherthanfollowingapriorityruledeterministicallyduringthecourseofthesearch,webiasastochasticselec-tionprocessbyafunctionoftheheuristicvalues.Thebacktrackingpriority-rulemethodistruncatedasbeforewhenathresholdnumberofbacktrackshasbeenreached;andthenrestartedsomenumberoftimes.Thebestfeasiblesolutionfoundoftheserestartsischosen.Intheresultsthatfollow,werefertousingthestochasticsamplingframeworkVBSSwithinthepriority-rulemethodforNiterationsby:LST[N];MST[N];MTS[N];LPF[N];andRSM[N].ThebiasfunctionsusedwithinVBSSareineachcasepolyno-mial:degree10foreachofLSTandMST;degree2forMTS;degree3forLPF;anddegree4forRSM.Thesewerechosenduringasmallnumberofexploratorysolutionrunsforasmallsampleofprobleminstances.NAIVE[N]referstorandomlysamplinganequalnumberoftimeswitheachofthefiveheuristics(Niterationstotal).

GeneratingandUsingModelsofSolutionQualities.Further,usingthemethodsofmodelingthedistributionofsolutionqualitiespresentedinthispaper,weenhancetheperformanceoftheVBSSpriority-rulemethod,effectivelycombiningmultipleheuris-ticswithinasinglemultistartstochasticsearch.WerefertothisapproachusingtheabovefiveheuristicsforNiterationsaccordingtotheestimationmethodasfollows:NORM[N]usingNormaldistributionestimates;KDE[N]usingkerneldensityesti-mates;andGEV[N]usingGEVdistributionestimates.

4ExperimentalResults

Table1showsasummaryoftheresultsofusingVBSSwiththepriority-rulemethodandTable2showsasummaryoftheresultsofgeneratingandusingmodelsofsolutionqualitytoenhancethesearch.Wecanmakeanumberofobservations:

–ForanynumberofiterationsoftheVBSSenhancedpriority-rulemethod,thebestsingleheuristictouseintermsoffindingoptimalsolutionsisthe“longest-pathfol-lowingfirst”(LPF)heuristic.However,wecanalsoobservethattheVBSSmethodusingLPFisworstintermsofthenumberoffeasiblesolutionsfound.UsingLPFandVBSSappearstoperformverywellontheprobleminstancesforwhichitcan

Table1.SummaryoftheresultsofusingVBSSwiththepriority-rulemethod.

AlgorithmLPF[20]LST[20]MTS[20]MST[20]RSM[20]LPF[100]MTS[100]LST[100]MST[100]RSM[100]LPF[200]MTS[200]LST[200]MST[200]RSM[200]LPF[400]MTS[400]LST[400]MST[400]RSM[400]

∆LBNO4.4(4.2)616(628)6.1(5.7)600.7(612)4.6(4.4)600(617)6.6(6.1)598.3(606)8.5(7.7)447.7(494)4.2(4.0)632.3(642)4.4(4.3)626(638)5.5(5.2)617.3(625)5.9(5.6)609(614)7.4(6.9)510.3(536)4.1(4.0)638.7(647)4.3(4.2)634(648)5.3(5.1)625.3(633)5.7(5.5)614.3(623)7.1(6.5)529.7(555)4.1(4.0)643.3(650)4.3(4.2)641.7(654)5.2(4.9)631(638)5.5(5.3)619(629)6.7(6.3)544(564)

NFTIME942(956)0.41041(1043)0.2953.3(965)0.41038.7(1041)0.31027.3(1031)0.2959.7(969)1.1970(981)1.11044(1044)0.61042(1043)0.81033.3(1035)0.6

965(974)2.1979(986)2.01044.3(1045)1.11043.3(1044)1.51034.7(1036)1.0972.3(980)4.0983.7(989)3.71044.7(1045)1.91043.7(1045)2.81035.7(1037)1.7

findfeasiblesolutions,whileatthesametimehavingdifficultiesfindinganyfeasi-blesolutionforalargenumberofotherprobleminstances.

–Weobservesimilarbehaviorwhenthesecondbestheuristicintermsofnumberofoptimalsolutionsfound(VBSSusingthe“mosttotalsuccessors”(MTS))isconsidered.However,likeVBSSusingLPF,VBSSusingMTSperformspoorlyintermsoffindingfeasiblesolutionstotheproblemsofthebenchmarkset.

–AlthoughVBSSusinganyoftheotherthreeheuristicsdoesnotperformaswellintermsoffindingoptimalsolutionsascomparedtousingLPForMTS,usingtheseotherheuristicsallowsthesearchtofindfeasiblesolutionsformanymoreoftheprobleminstancesascomparedtousingonlyLPForMTS.Thus,wecanseethatbycombiningthefiveheuristicseitherbythenaivestrategyorbyusingqualitymodels,thatwecanfindfeasiblesolutionstonearlyallofthe1059probleminstancesonaverage;whileatthesametimecombiningthestrengthsoftheindividualheuristicsintermsoffindingoptimal,ornear-optimal,solutions.

–Comparingtheuseofqualitymodelstoguidethechoiceofsearchheuristictothenaivestrategyofgivinganequalnumberofiterationstoeachoftheheuristics,weseethatthenaivestrategyisalwaystheworstintermsoffindingoptimalsolutions.Somewhatmoreinterestingly,itisalsoalwaysworstintermsofCPUtime.Despitetheoverheadrequiredforestimatingthesolutionqualitymodels,thenaivestrategyappearstobegenerallyslower–asmuchas2.5secondsslowerinthe2000iterationcase.Thereasonforthisisthatalthoughthereisextracomputationaloverheadinthemodeling,usingthemodelsgiveslessiterationstoheuristicsthatappearlesslikelytofindfeasiblesolutions.Thenaivestrategyresultsinmoreiterationsthatdo

Table2.SummaryoftheresultsofusingVBSSandmodelsofsolutionqualitytoenhancethepriority-rulemethod.

AlgorithmGEV[100]KDE[100]NORM[100]NAIVE[100]KDE[500]NORM[500]GEV[500]NAIVE[500]KDE[1000]GEV[1000]NORM[1000]NAIVE[1000]KDE[2000]NORM[2000]GEV[2000]NAIVE[2000]

∆LBNO5.3(4.9)650.7(667)5.3(4.9)649.7(662)5.3(4.9)648.7(661)5.3(5.0)646.3(650)4.8(4.6)665.7(680)4.9(4.6)662.3(673)4.9(4.6)660(677)4.8(4.6)658.3(666)4.7(4.5)670.3(683)4.8(4.5)667(682)4.8(4.5)666.7(678)4.7(4.5)664.7(673)4.6(4.4)675.7(689)4.7(4.4)672.3(685)4.7(4.4)672.3(685)4.6(4.4)669.7(678)

NFTIME

1050.7(1053)0.81050.7(1053)0.81050.7(1053)0.81050(1052)0.91053(1055)3.11053(1055)3.01053(1055)3.21052.7(1055)3.71054.7(1057)5.81054.7(1057)6.51054.7(1057)5.81054.7(1057)7.01057(1059)11.21057(1059)11.01057(1059)13.01057(1059)13.5

notfindafeasiblesolution,thusperformingthemaximumnumberofbacktrackingstepsallowedbytheserialgenerationschemeforsuchinfeasibleiterations.

–Ofthethreemethodsforestimation,kerneldensityestimationperformsbestfortheRCPSP/maxproblem.ExceptforN=100,KDE[N]findsmoreoptimalsolutionsthantheotherconsideredmethods.Furthermore,KDE[N]requiressignificantlylessCPUtimethandoesGEV[N](atleastfortheparticularestimationprocedureoftheGEVdistributionemployedhere).Also,theadditionaloverheadofKDE[N]comparedtoNORM[N]appearstobenegligiblegiventheCPUtimingresults.Table3liststheresultsofacomparisonoftheenhancedpriority-rulemethodandotheralgorithms,includingbranch-and-boundapproachesandstochasticsearchalgo-rithms.Wecanmakethefollowingobservations:

–ThebestperformingheuristicmethodisclearlyKDE[N].Inapproximately1/6oftheCPUtimeusedbythepreviousbestperformingheuristicmethod–ISES–KDE[1000]findsasmanyoptimalsolutionswithasignificantlyloweraveragedeviationfromtheknownlowerbounds.Inlessthan1/3oftheCPUtimere-quiredbyISES,KDE[2000]consistentlyfindsasmanyfeasiblesolutionsasISES;KDE[2000]consistentlyfindsmoreoptimalsolutionsthanISES;andKDE[2000]onaveragefindssolutionsthatdeviatesignificantlylessfromtheknownlowerboundsascomparedtoISES.

–Inapproximately1/6oftheCPUtime,KDE[2000]onaverageperformsaswellasthecurrentbestbranch-and-boundalgorithm–B&BDPP98–intermsofdeviationfromlowerbounds(andbetterthanB&BDPP98forthebestrunofKDE[2000]).However,B&BDPP98findsmoreoptimalsolutionsthanKDE[2000].KDE[2000]isacompetitivealternativetotruncatedbranch-and-boundifonerequiresgoodsolutionsbutnotnecessarilyoptimalsolutionsinahighlylimitedamountoftime.

Table3.Comparisonoftheenhancedpriority-rulemethodwithotheralgorithmsfortheRCPSP/maxproblem.

Algorithm∆LBNONFTIMEBEST3.37891059–B&BDPP984.6774105966.7aPRFNS56.56039910.2

7.76011053n/acPRFN10

ISES8.0(7.3)669.8(683)1057(1059)35.7bKDE[1000]4.7(4.5)670.3(683)1054.7(1057)5.8KDE[2000]4.6(4.4)675.7(689)1057(1059)11.2

a

b

c

Adjustedfromoriginalpublicationbyafactorof200.300Thebranch-and-boundalgorithmwasimplementedona200MhzPentium,whileweusedforouralgo-rithmsaSunUltra10/300MHz.

Adjustedfromoriginalpublicationbyafactorof266.300ISESwasoriginallyimplementedonaSunUltra-Sparc30/266MHz,whileweusedforouralgo-rithmsaSunUltra10/300MHz.

Timingresultswerenotavailableinsomecases.Thisisindicatedby“n/a”.

Table4.Newbestknownsolutionsfoundbythealgorithmsofthispaper.LBisthelowerboundforthemakespan.Oldisthepreviousbestknown.Newisthenewbestknown.

InstanceC364D65D96D127D277

LB341440434428558

OldNewAlgorithm(s)372365MTS[100]539521KDE[2000],GEV[2000]450445LPF[20]445434LPF[200]575569KDE[2000],GEV[2000]

Table4liststheprobleminstancesforwhichwewereabletoimproveuponthecurrentbestknownsolutions.VBSSusingtheLPFheuristicisabletoimproveuponthebestknownsolutionstoacoupleofprobleminstances.ThesameistrueofVBSSusingMTS.KDE[2000]andGEV[2000]alsoimproveuponacoupleadditionalbestknownsolutions.

5SummaryandConclusions

Inthispaper,weintroducedageneralframeworkforcombiningmultiplesearchheuris-ticswithinasinglestochasticsearch.ThestochasticsearchalgorithmthatthestudyfocusedonwasthatofVBSSwhichisanon-systematictree-basediterativesearchthatusesrandomizationtoexpandthesearcharoundaheuristic’sprescribedsearch-spaceregion.Theapproachrecommendedbythispaper,however,canbeappliedtoothersearchalgorithmsthatrelyontheadviceofasearchheuristicandforanyproblemforwhichthereisnooneheuristicthatisobviouslybetterthanothers.

Indevelopingtheapproachtocombiningmultiplesearchheuristics,wehavecon-jecturedthatthedistributionofthequalityofsolutionsproducedbyastochasticsearchalgorithmthatisguidedbyastrongdomainheuristiccanbestbemodelledbyafamilyofdistributionsmotivatedbyextremevaluetheory.ThisleadstotheuseoftheGEVdistributionwithinourframework.TwomethodsofimplementingtheGEVhavebeenconsidered:1)maximumlikelihoodestimatescomputedbypotentiallycostlynumeri-calmethods;and2)kerneldensityestimationusingabandwidthparametertunedundertheassumptionofaGEVdistribution.

TheeffectivenessofthisapproachwasvalidatedusingtheNP-Hardconstrainedop-timizationproblemknownasRCPSP/max.OnstandardbenchmarkRCPSP/maxprob-lems,ourEVT-motivatedapproachwasshowntobecompetitivewiththecurrentbestknownheuristicalgorithmsfortheproblem.Thebestavailabletruncatedbranch-and-boundapproachiscapableoffindingagreaternumberofoptimalsolutions,butatamuchgreatercomputationalcost.OurEVT-motivatedapproachis,however,abletofindmoreoptimalsolutionsthanISES(thepreviousbestknownheuristicalgorithmforRCPSP/max)andwithlessdeviationthanISESfromtheknownlowerboundsonsolu-tionquality.Theapproachwehavetakeninthispaperhasalsoimproveduponcurrentbestknownsolutionstodifficultbenchmarkinstances.

Onepotentiallyinterestingfuturedirectiontoexploreiswhetherornotthereisanyconnectionbetweentheheavy-tailednatureofruntimedistributionsofCSPsearchalgorithmsnotedbyGomesetal.[10]andtheheavy-tailednatureofthesolutionqualitydistributionsobservedinourownwork–theextremevaluedistributionstypeII&IIIarebothheavy-tailed.Aretheruntimeandsolutionqualitydistributionsinconstrainedoptimizationdomainsatallcorrelated,andifsocanthisbeusedtoenhancesearch?Thisisadirectionthatwillbeworthexploring.

References

1.Bresina,J.L.:Heuristic-biasedstochasticsampling.In:ProceedingsoftheThirteenthNa-tionalConferenceonArtificialIntelligenceandtheEighthInnovativeApplicationsofArti-ficialIntelligenceConference,VolumeOne,AAAIPress(1996)271–278

2.Cicirello,V.A.,Smith,S.F.:Amplificationofsearchperformancethroughrandomizationofheuristics.InVanHentenryck,P.,ed.:PrinciplesandPracticeofConstraintProgramming–CP2002:8thInternationalConference,Proceedings.VolumeLNCS2470ofLectureNotesinComputerScience.,Springer-Verlag(2002)124–138Ithaca,NY.

3.Cicirello,V.A.:BoostingStochasticProblemSolversThroughOnlineSelf-AnalysisofPer-formance.PhDthesis,TheRoboticsInstitute,SchoolofComputerScience,CarnegieMellonUniversity,Pittsburgh,PA(2003)AlsoavailableastechnicalreportCMU-RI-TR-03-27.4.Goldberg,D.,Cicirello,V.,Dias,M.B.,Simmons,R.,Smith,S.,Stentz,A.:Market-basedmulti-robotplanninginadistributedlayeredarchitecture.In:Multi-RobotSystems:FromSwarmstoIntelligentAutomata:Proceedingsofthe2003InternationalWorkshoponMulti-RobotSystems.Volume2.,KluwerAcademicPublishers(2003)27–38Washington,DC.5.Allen,J.A.,Minton,S.:Selectingtherightheuristicalgorithm:Runtimeperformancepre-dictors.In:ProceedingsoftheCanadianAIConference.(1996)

6.Cowling,P.,Kendall,G.,Soubeiga,E.:Hyperheuristics:Atoolforrapidprototypinginschedulingandoptimisation.InCagnoni,S.,Gottlieb,J.,Hart,E.,Middendorf,M.,Raidl,

7.

8.9.10.

11.

12.13.14.15.16.17.18.19.

20.

21.

22.23.

G.R.,eds.:ApplicationsofEvolutionaryComputing:EvoWorkshops2002Proceedings.NumberLNCS2279inLectureNotesinComputerScience,Springer-Verlag(2002)1–10Nareyek,A.:Choosingsearchheuristicsbynon-stationaryreinforcementlearning.InRe-sende,M.G.C.,deSousa,J.P.,eds.:Metaheuristics:ComputerDecisionMaking.KluwerAcademicPublishers(2003)

Gomes,C.P.,Selman,B.:Algorithmportfolios.ArtificialIntelligence126(2001)43–62Talukdar,S.,Baerentzen,L.,Gove,A.,deSouza,P.:Asynchronousteams:Cooperationschemesforautonomousagents.JournalofHeuristics4(1998)295–321

Gomes,C.P.,Selman,B.,Crato,N.:Heavy-taileddistributionsincombinatorialsearch.In:PrinciplesandPracticesofConstraintProgramming(CP-97).LectureNotesinComputerScience,Springer-Verlag(1997)121–135

Bresina,J.,Drummond,M.,Swanson,K.:Expectedsolutionquality.In:ProceedingsoftheFourteenthInternationalJointConferenceonArtificialIntelligence,MorganKaufmann(1995)1583–1590

Coles,S.:AnIntroductiontoStatisticalModelingofExtremeValues.Springer-Verlag(2001)Hosking,J.R.M.:AlgorithmAS215:Maximum-likelihoodestimationoftheparamatersofthegeneralizedextreme-valuedistribution.AppliedStatistics34(1985)301–310

Silverman,B.W.:DensityEstimationforStatisticsandDataAnalysis.MonographsonStatisticsandAppliedProbability.ChapmanandHall(1986)

Epanechnikov,V.A.:Non-parametricestimationofamultivariateprobabilitydensity.TheoryofProbabilityandItsApplications14(1969)153–158

NIST/SEMATECH:e-HandbookofStatisticalMethods.NIST/SEMATECH(2003)http://www.itl.nist.gov/div898/handbook/.

Kaelbling,L.P.,Littman,M.L.,Moore,A.W.:Reinforcementlearning:Asurvey.JournalofArtificialIntelligenceResearch4(1996)237–285

Kirkpatrick,S.,Gelatt,C.D.,Vecchi,M.P.:Optimizationbysimulatedannealing.Science220(1983)671–680

Dorndorf,U.,Pesch,E.,Phan-Huy,T.:Atime-orientedbranch-and-boundalgorithmforresource-constrainedprojectschedulingwithgeneralisedprecedenceconstraints.Manage-mentScience46(2000)1365–1384

Franck,B.,Neumann,K.,Schwindt,C.:Truncatedbranch-and-bound,schedule-construction,andschedule-improvementproceduresforresource-constrainedprojectscheduling.ORSpektrum23(2001)297–324

Neumann,K.,Schwindt,C.,Zimmermann,J.:ProjectSchedulingwithTimeWindowsandScarceResources:TemporalandResource-ConstrainedProjectSchedulingwithRegularandNonregularObjectiveFunctions.LectureNotesinEconomicsandMathematicalSystems.Springer-Verlag(2002)

Cesta,A.,Oddi,A.,Smith,S.F.:Aconstraint-basedmethodforprojectschedulingwithtimewindows.JournalofHeuristics8(2002)109–136

Franck,B.,Neumann,K.:Resource-constrainedprojectschedulingwithtimewindows:Structuralquestionsandpriority-rulemethods.TechnicalReportWIOR-492,Universit¨atKarlsruhe,Karlsruhe,Germany(1998)