SCIENCEANDTECHNOLOGYISSNll1007-0214ll10/11llpp90-99Volume20,Number1,February2015 AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA YiwenZhang,GuangmingCui,YanWang,XingGuo,andShuZhao Abstract:Large-scalepositionhaseanimportanticinService-OrientedComputing(SOC).QualityofService(QoS)hasbeenmostlyappliedtorepresentnonfunctionalpropertiesofwebservicesandtodifferentiatethosewiththesamefunctionality.ManystudiesformeasuringpositionintermsofQoShavepleted.Amongcurrentpopularoptimizationmethodsforposition,theexhaustionmethodhassomedisadvantagessuchasrequiringalargenumberofcalculationsandpoorscalability.Similarly,thetraditionalputationmethodhasdefectssuchasexhibitingslowconvergencespeedandfallingeasilyintothelocaloptimum.Inordertosolvetheseproblems,animprovedoptimizationalgorithm,WSFOA(WebpositionbasedonFruitFlyOptimizationAlgorithm)forposition,wasproposed,onthebasisofthemodelingofpositionandtheFOA.Simulatedexperimentsdemonstratedthatthealgorithmiseffective,feasible,stable,andpossessesgoodglobalsearchingability. Keywords:position;FruitFlyOptimizationAlgorithm(FOA);QualityofService(QoS)index 1Introduction Inthelate1990s,withthedevelopmentofdistributedtechnologyandeXtensibleMarkupLanguage(XML)technology,thepositiontechnologyappeared.Itscoreideaistoserveasthebasicunit,andthenrapidlyconstructalooselycoupled,distributedapplicationbiningbasicservices[1].positionisaprocessthatassemblesacertainnumberofservicesinordancewithbusinesslogic.Itachievesbusinessobjectivesthroughtheimplementationofbinedservice.Webserviceabsorbedtheadvantagesofputing,puting,andXMLtechnologies,andwasappliedessfullytosolvingtheproblemofheterogeneousputing,aswellasthereuseofcodeanddata[2].Inthemeantime,italsohas YiwenZhang,GuangmingCui,YanWang,XingGuo,andShuZhaoarewiththeSchoolofComputerScienceandTechnology,KeyLaboratoryofIntelligentComputingandSignalProcessing,MinistryofEducation,AnhuiUniversity,Hefei230601,China.E-mail:zhaoshuzs2002@.Towhomcorrespondenceshouldbeaddressed.Manuscriptreceived:2014-12-07;epted:2014-12-25 highinteroperability,platformindependence,loosecoupling,andhighlyintegratedcapabilities.However,asinglewebserviceprovideslimitedfunctionality.Service-OrientedComputing(SOC)enablespositionoftheseservicesinalooselycoupledwayinordertoplexfunctionality. Whileacademiaandbusinesshavepaidmuchattentiontopositiontechnologies,numerousexecutablepositionschemeshavebeenproduced.ThesecanbedescribedasbinationofaservicefunctionandQualityofService(QoS),inwhichresearchersmostlyadopttheexhaustiveandevolutionaryalgorithmsasthecalculationmethodbasedonQoSattributes.Exhaustivemethodshavepoorextensionandrequirealargeamountofcalculation[3].Theyaregenerallyapplicabletostaticsituationsandhavesmall-scaleposition.Asthenumberofwebservicepublicationsraisessharply,putationalgorithmsprovideabettersolution.Inparticular,theicAlgorithm(GA)andParticleSwarmOptimization(PSO)algorithmaretwotypicalalgorithmsthatarecurrentlyusedintheresearchofpositionoptimization.Comparedwiththeformer,PSOhasthepositivecharacteristicsof YiwenZhangetal.:AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA 91 possessingfewparametersandfastconvergencespeed.Itshowsgoodsearchcapabilitiesinmanyoptimizationproblems,buthasthedefectofeasilyfallingintothelocaloptimum[4,5].Basedonthis,thepaperputsforwardanoptimizationalgorithmforWebpositionbasedontheimprovedFruitFlyOptimizationAlgorithm(FOA),denotedasWSFOA.ComparedwithPSOalgorithm,thisalgorithmhasafewadvantages:fewerparameters,fasterconvergencespeed,andlessrunningtime.Further,WSFOAhasgoodglobalsearchingability. 2FOA FOAisanewmethodforfindingglobaloptimizationbasedontheforagingbehaviorofthefruitfly.Thefruitflyitselfissuperiortootherspeciesinsensingandperception,especiallyinosphresisandvision.Basedonthefruitflyanditsforagingprocess,FOAwasproposed[6].ThefoodfindingbehaviorofthefruitflyisillustratedinFig.1andtheimplementationofFOAfollows.
(1)Initializeparameters:giventhesizeofswarm(Sizepop)andthemaximumofiterationtimes(Maxgen),initializerandomlyfruitflyswarmlocation(xaxis,yaxis).
(2)Givethedirectionanddistance(Value)forindividualfruitflysearchingforfoodusingosphresis,whichisrandom.(Valuezoneis[1,1]intheFOAtest). (xiDxaxisCValueI(1)yiDyaxisCValue
(3)Sincethefoodlocationcannotbeknown,the distance(Disti)totheoriginisthusestimatedfirst. Thenthesmellconcentrationjudgmentvalue(Smelli) iscalculated,andthisvalueisthereciprocalofdistance. q DistiDxi2Cyi2
(2)
1 SmelliD
(3) Disti
(4)Substitutesmellconcentrationjudgmentvalue (Smelli)intosmellconcentrationjudgmentfunction (alsocalledfitnessfunction)tofindthesmell concentration(Fitnessi)oftheindividuallocationofthe fruitfly. FitnessiDFunction(Smelli/
(4)
(5)Findthefruitflywithminimalsmellconcentration(findingtheminimalvalue)amongthefruitflyswarm. ŒbestFitnessbestindexDmin(Fitnessi/
(5)
(6)Recordandkeepthebestsmellconcentration valueanditscoordinate(x,y),andatthismoment, thefruitflyswarmwillusevisiontoflytowardsthat location.8 ˆˆFitnessbestDbestFitnessI< xaxisDx.bestindex/I
(6) ˆˆ:yaxisDy.bestindex/
(7)EntertheiterativeoptimizationprocesstorepeattheimplementationofSteps2–
5.Then,determineifthesmellconcentrationissuperiortothepreviousiterativesmellconcentrationandthecurrentnumberofiterationsissmallerthanthemaximumnumberofiterations(Maxgen).Ifso,implementStep6. 3TheProblemofModeling Theoptimizationalgorithmproposedinthispaperisbasedontwospecificexperimentalmodels.Oneisthepositionmodel,andtheotheristheWSFOAalgorithmmodel.Byconstructingthewebservicemodel,variousattributesofwebservicecanbeclearlydefinedandusedandaquantitativeindexcanbespecifiedintheexperiment.ThroughtheWSFOAalgorithmmodel,thepracticalsignificanceinpositionofeveryparameterinFOAcanbeclearlydescribed.Thisisconvenientforalgorithmimplementation. 3.1positionmodeling Fig.1Thefoodfindingbehaviorofthefruitfly. Definition1QoSLetQoSDfA;T;C;Rg,whereArepresents availability,Trepresentsresponsetime,Crepresentscost,andRrepresentsreputation[7].
(1)Availability(A)Availabilityreferstotheprobabilitythatawebserviceisessible,namely,theproportionofessfulwebservicevisitsintheperiodoftimet. 92 TsinghuaScienceandTechnology,February2015,20
(1):90-99 LetADess=t,wheretheessrepresentsthetime ofessfullyessingtheservicewithinthetime periodt.Aisanumberintherange[0,1].
(2)Responsetime(T) Responsetimereferstotheexpecteddelaybetween thetimewhenaservicerequestersendsaservice requestandthetimewhentheresultisobtained. Itmainlyincludesthewebserviceexecutiontime Texe,worktransmissiontimeTtrans,andothertime consumptionToth.Hence,theresponsetimeisevaluated asTDTexeCTtransCToth.
(3)Cost(C) Costreferstothefeethataservicerequesterhasto paytotheserviceproviderfortheserviceinvocation. ItmainlyincludestherequisitebasisfeeCserv,such assoftware(SaaS),hardware(IaaS),andplatform (PaaS)[8],andtheservicemanagementfeeCmanag.It canbedescribedasCDCservCCmanag.
(4)Reputation(R) Reputationreferstothetrustworthymeasureofthe webservice,whichismainlybasedontheexperienceof usersafterusingthewebservice.Differentusersmay havedifferentevaluationsonthesamewebservice.Let n XRDRi=n,whereRirepresentstheevaluationof iD1 webservicesofthei-thend-user.Risanumberinthe range[0,1]. Definition2Webservice(s) Webserviceisafour-tuple.LetsDfID;Source; Function;QoSg,whereIDistheuniqueidentification ofawebservice,Sourceisthedescribinginformation ofservicenameandpublisher,etc.,Functionisa functionaldescriptionoftheWebservice,andQoSis thedescriptionofthequalityofthewebservice. Definition3ServiceComposition(SC) LetSCD.s1;s2;s3;;sn1;sn/,wheres1sn representeachwebsubservicerespectively,ands12 S1;s22S2;s32S3;;sn12Sn1;sn2Sn.At thesametime,S1toSnarecalledsetsofsubservicesof position.SubservicesinSihavethesame function,buthavedifferentservicequalities.Thus,itis concludedthatSC2S1S2S3 Sn1Sn. Theexecutionpathsofpositeservicecanbe composedoffourpositionpatterns,suchas sequential,selection,parallel,andloop(seeFig.2)[9]. Theformulasofallpatternsareasfollows.
(1)Sequentialmodel(Fig.2a).QoSisfoundby Eqs.
(7).
(2)Selectionmodel(Fig.2b).Supposethatthe Fig.2Fourpositionpatternsforposition. selectedprobabilityofeachserviceSiis n XiD1.Then,QoSisfoundbyEqs.
(8). i,then iD1
8 n YˆˆˆADAiIˆ ˆ ˆˆ iD1 ˆˆ n ˆXˆˆˆRDRi=nIˆ < iD1n
(7) ˆXˆˆˆCDCiI ˆ ˆˆ iD1 ˆˆ n ˆ ˆ
X ˆˆˆTDTi : iD1
8 n YˆˆˆAD.Aii/Iˆ ˆ ˆˆ iD1 ˆˆ n ˆXˆˆˆRD.Rii/Iˆ < iD1n
(8) ˆXˆˆˆCD.Cii/I ˆ ˆˆ iD1 ˆˆ n ˆ ˆ
X ˆˆˆTD.Tii/ : iD1
(3)Parallelmodel(Fig.2c).Supposenservicesare executedinparallel.Then,QoSisfoundbyEqs.
(9).
(4)Loopmodel(Fig.2d).Supposetheloopmodelis carriedoutÂtimes.Then,QoSisfoundbyEqs.(10).
8 n ˆYˆˆˆADAiI ˆ ˆˆ iD1 ˆˆ n ˆ ˆ
X ˆ(9) ˆˆn ˆXˆˆˆCDCiIˆ ˆ ˆˆ iD1 ˆ ˆ:TDmax.Ti/;i2Œ1;n YiwenZhangetal.:AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA 93
8 n YˆˆˆADAiIˆ ˆ ˆˆ iD1 ˆˆ n ˆXˆˆˆRDRi=nIˆ < iD1n (10) ˆ
X ˆˆˆCDÂCiI ˆ ˆˆˆˆˆˆˆˆˆTD iD1n XTi : iD1 Definition4QoSpretreatment Differenttypesofindexeshavedifferentdimensions. Inordertoeliminatethemensurabilitystemming fromdifferentdimensionsanddifferentdimensional units,allindexesneedtobenormalizedtoa dimensionlessintervalordingtoacertainutility function(usuallyitisnormalizedto[0,1])beforethe cooperativeevaluation.Thispaperonlyconsidersthe discreteindexesandnormalizesthemordingtothe followingformula. (maxqij/=.qjmax qijD.qj.qijqjmin/=.qjmax qjmin/;qjmin/; benefittypeI costtype(11) whereqjmaxandqjminrepresentthecurrentmaximumandminimumvalueofthej-thevaluationindex respectively.Theirvaluewillchangedynamicallywith thejoiningorwithdrawingfromawebservice. 3.2Algorithmmodeling 3.2.1Individualfruitfly Intheexperiment,positionisafive-tuple,namelyeachrecordofSCcontainsfivesubserviceprocesses.Therefore,wheneachsubserviceisregardedasasingleindividualfruitfly,eachSCcontainsfiveindividualfruitflies,whichbelongtodifferentsubservicesets,respectively.Inthisway,wecandoaniterationwiththefivefliesseparatelybyusingFOA,andthenfindtheoptimalsolutionbyusingthefitnessfunctionvalueofposition.Finally,thelocationofthefivefliesintheoptimalservicesetisjustthelocationofeachsubservice.3.2.2Codeofindividualfruitflyandmotion equationoffruitfly Thecodefortheindividualfruitflyusesadiscretemethod;itadoptsthemethodofintegerencoding.Theintegerrepresentsthelocationofthefruitflyinitssetofsubservices.Motionequation(F)isthedirectionandthesizeordingtowhichthefruitflyswarmcanoptimallymove.Thatis,FDVt;.t2Œ1;1/.V denotesthemobilestep,meaningtherangewherethe fruitflycouldmoveonce.Thus,thepositionequation oftheindividualfruitflyisasfollows. PkiC1;jDPi;jbestCF (12) ThePkiC1;jrepresentsthelocationofthek-thfruitfly ofthej-thflyswarminthe.iC1/-thiterativeprocess. Pi;jbestrepresentstheoptimallocationofthej-thfly swarminthei-thiterativeprocess,whichisrecorded astheseedfortheindividualfruitflyofthej-thfly swarminthei-thiterativeprocess.Inotherwords,itis thelocationofthefruitflyswarminthenextiterative process. 3.2.3Definitionofdistance IneachiterationofFOAforeachfruitfly,usethe reciprocaloftheoffsetwhichisthelocationofthefruitflyinitssetofsubservicesrelatedtothe0-threcordas thedistance.Afterthat,thevalueofsmellconcentration judgmentiscalculatedbyusingtherelationbetween distanceandsmellconcentrationjudgmentvalue,and thenthefitnessfunction(Fitness)iscalculated.The distance(Dist)andthesmellconcentrationjudgment value(Smell)aredefinedas(DistkiC1;jD1=PkiC1;jI(13)SmellkiC1;jD1=DistkiC1;j PkiC1;jisthelocationwheretheindividualfruitflyhasshiftedinitssetofsubservices.DistikC1;jdenotesthedistanceofthek-thfruitflyofthej-thflyswarminthe.iC1/-thiterativeprocess.SmellkiC1;jrepresentsthesmellconcentrationjudgmentvalueofthek-thfruitflyofthej-thflyswarminthe.iC1/-thiterativeprocess. 3.2.4Fitnessfunction Thefitnessfunctionisusedtocalculatethefitnessof eachSC.Theadvantagesanddisadvantagesofeach SCarejudgedbythefitnessvalues.Combinedwith theresultsofQoSafterpreprocessinginEqs.(11),the fitnessfunctioncanbedefinedas nm nm fitnessDXXCjWkQjkDXXCjWkSmellik;j jD1kD1 jD1kD1 (14) WhereSmellik;jrepresentstheponentindexof thei-thfruitflyofthej-thswarminthei-thiterative process.Cjrepresentstheweightofthej-thsubservice intheSC.Qjkrepresentstheponentindexof thej-thsubservice.Wkrepresentstheweightofthe ponentindex.ndenotesthenumberofthe subservice.mdenotesthateachsubservicecontainsm QoSindex. 94 4ImplementationofWSFOA TsinghuaScienceandTechnology,February2015,20
(1):90-99 4.1Experimentalscheme WSFOAisexecutedbasedontheiterativeoperationofmultiplefruitflyswarms.Iterativeoperationofeachfruitflyswarmstandsforthecorrelativeoperationofeachsetofsubservices,includingthepositionchangeoffruitfliesandtheoptimizationprocess.Forexample,intheexperiment,anSCisconstitutedoffivesubservices,whicharemarkedass1s5.Therefore,therearefivefruitflyswarmslabeledasG1G5.GiisaswarmwhosepracticalbackgroundandsignificanceareSiandWSFOAalgorithmisexecutedordinglywithGi.IntheWSFOAoptimizationprocess,WSFOAalgorithmisexecutedusingtheswarmsG1G5respectively,andtheneachrecordofSCisconstitutedofthecorrespondingpositioninG1G5.Forexample,then-thindividualfruitflyischoseninG1G5respectively,sobinedrecordforthepositionisSCD.S1G1;S2G2;S3G3;S4G4;S5G5/.SiGidenotesthesubservicecatalogedasGiinthei-thsetofsubservices.Then,calculateeachSCconsistingofG1G5ordingtoEq.(14);theoptimalSCintheiterativeprocesscontainsthesubservicewhichisregardedastheseededindividualfruitflyinthecorrespondingswarm.Finally,calculatethenextfruitflyswarmandproceedtothenextiterationordingtoEq.(12),untiltheiterationisoverortheendconditionismet. 4.2WSFOAalgorithm TheestablishedQoSindexsystemhasdifferentdimensions.Inordertoeliminatethemensurabilitystemmingfromthedifferentdimensionsanddimensionalunits,binedwithDefinition4,theexperimentaldatashouldbepreprocessedbeforetheexperiment.Then,thedataisoptimizedordingtotheWSFOAalgorithm.Thisalgorithmincludestwoparts.ThemainstepsaredescribedasfollowsandtheirimplementationproceduresareillustratedinFigs.3and4.
(1)QoSpreprocessingalgorithmInput:TheoriginalindexinformationofsetofsubservicesOutput:ThenormalizedindexinformationofsetofsubservicesStep1:Obtaintheindexinformationofeachsetofsubservices.Step2:Obtainthemaximumvalueandminimumvalueofeachindexinthesetofsubservices. Fig.3TheimplementprocedureforQoSpreprocessing. Fig.4TheimplementprocedureoftheWSFOA. Step3:Foreachsubservicerecordinsetofsubservices,AandRindexesarecalculatedusingEqs.(11)ordingtotheequationofbenefit,andCandTindexesarecalculatedusingEqs.(11)ording YiwenZhangetal.:AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA 95 totheequationofcost. Step4:RepeatSteps2–4,untileachsetof subservicesistotallydisposed. Step5:Outputtheindexinformationofeachsetof subservicesafternormalization.
(2)DescriptionofWSFOAalgorithm Input:thenormalizedsetofsubservice Output:thelocationofindividualfruitflyinoptimal SCStep1:Initializethelocation(P0;1best P0;nbest)of seededfruitflyineachsetofsubservices. Step2:Calculatethelocationoffruitflyswarm ordingtoEq.(12). Step3:Calculatedistanceandsmellvalueof individualfruitflyineachsetofsubservicesording toEq.(13). Step4:Convertsmellassemblageintoeachrecordof SC. Step5:CalculateeachrecordofSCordingto Eq.(14).RecordtheoptimalSCintheiterativeprocess, andtreateachsubserviceinbinedrecordasseededfruitflyPi;jbestinitscorrespondingswarm. Comparetheoptimalvalueinthisiterationwiththe globaloptimalvalueandreservethebestlocation. Step6:RepeatSteps2–5,untiltheiterationisover orthedemandforuracyismet. Step7:Outputtheposition. 5ComparativeStudy 5.1PSOalgorithm ThePSOalgorithmisaheuristicevolutionary algorithm,whichwasproposedbyEberhartand Kennedyin1995andinspiredbythesocialbehaviorofbirdflockingorfishschooling[10].Eachparticle’s positionrepresentsasolutionofoptimizationproblems inPSO.Theparticle’spositionchangesordingto twoextremevalues:Oneisthehistoricaloptimal solutionoftheparticles(pbest)andtheotheristheglobaloptimalsolutionofspecies[11]. vid.tC1/Dw.t/vid.t/CC1randi.t/.pbestdiC2randi.t/.gbestdxid.t// xid.t//C(15) xid.tC1/Dxid.t/Cvid.tC1/ (16) wherepbesti
D .pbest1i ; pbest 2i ; ;pbestni/and gbestD.gbest1;gbest2;;gbestn/representthebest previouspositionofthei-thparticleandthebest previouspositionamongalloftheparticlesinthe populationrespectively.randi.t/isauniformrandom variablewithintheinterval[0,1]attimet.C1andC2aretwoelerationconstants.Theinitializationprocessforthevelocitiesandpositionsoftheparticlesisconductedbyusingvectorsofrandomnumbersthatareinthecorrespondingrange. 5.2Comparisonofalgorithms BothPSOandFOAbelongtoaclassofintelligentoptimizationalgorithms.Theyareevolutionaryalgorithmsthatarededucedfromanimalforagingrulesinnature.Theyalsohavehighoptimizationefficiencyinthesearchspaceandobtaintheoptimalsolutiononthebasisofthenextevolutionaryparticlepositionchange.However,therearemanydifferencesbetweenthemthataredescribedasfollows.
(1)Differentbackground.TheFOAisanewmethodforglobaloptimization,basedontheforagingbehavioroffruitflies.Instead,thePSOalgorithmisanevolutionaryalgorithmbasedongroupsocialbehaviorinspiredbybirdflockingorfishschooling.
(2)Differentoptimizationpath.WhenafruitflyfindsabetterpositionintheFOA,thewholepopulationmovestothatlocation,whileinthePSOalgorithmeachindividualdynamicallychangestheirpositionbasedontheoptimizationpositionandglobaloptimizationposition.
(3)Differentmotionequation.TheFOAproducesindividualfruitfliesbyusingpopulationlocation,whichbinedwithrandomvalueswhithinacertainrange,whilethePSOalgorithmchangesthespeedandpositionofindividualparticleswithEqs.(15)and(16).
(4)Differentparameter.TheFOAcalculatesthesmellusingthedistancebetweenanindividualfruitflyanditsorigin,usingonlyafewparameters.However,thePSOalgorithmcontainsmanymoreparameters,suchasinertiaweight,learningfactor,etc. 6ExperimentalAnalysis 6.1Experimentsettingsanddatasets ThisexperimentadoptedtheextendibleQoSmodelproposedbyLiuetal.[12]andtheQWSdatasetprovidedbyZengetal.[13,14]ThevalueofCjinEq.(14)andis1,namelyeachsubserviceountsforthesamepercentage.ThevalueofWkisf0.2,0.3,0.2,0.3g,whichcorrespondstothefourQoSindexesinDefinition1.TheexperimentiscarriedoutintheWindows7OS,andtheVisualStudiopilerenvironment.Dataprocessingisessedwiththetextdocument 96 TsinghuaScienceandTechnology,February2015,20
(1):90-99 ascarrier.Anotherexperimentaldatasetisarandomdataset(RWS),wheretherandomfunctionproducesawholenumberintherangeof[0,1000].Thenthewholenumberisdividedbyten,sothedataisintherangeof[0,100],includingadecimal.Afterrepeatingthismanytimes,weobtain2500groupsofexperimentaldata.Thedatasetisdividedequallyintofivecandidateservicesetsthatareusedassubservicesets.Finallythecandidateservicesetsarenormalizedinthefollowingexperiment. 6.2Comparisonofexperimentresults InordertoverifytheperformanceofWSFOA,efficiency,feasibility,andstabilityexperimentshavebeencarriedoutandtheresultsparedwiththoseofthePSOalgorithm.Theresultsoftheexperimentsaredescribedasfollows. 6.2.1Efficiency InordertoanalyzetheefficiencyoftheWSFOAalgorithm,wemakeparisons:theaverageruntimeofoptimizing50times(Fig.5)overdifferentpopulationsizesandthesamenumberofiterations(500),andtheaverageruntimeofoptimizing50times(Fig.6)overthesamepopulationsize(100)anddifferentnumbersofiterations. ShowninFigs.5and6,thegradualincreaseofpopulationsizeandthenumberofiterationsincreasesthedisparityoftimebetweenWSFOAandthePSOalgorithm.Thus,whenthepopulationsizeorthenumberofiterationsislarge,WSFOAexhibitsthecharacteristicsthatPSOdoesnotpossess.Meanwhile,hostsofexperimentshaveindicatedthatinthecaseofthesamepopulationsizeandthenumberofiterations,theWSFOAalgorithmhashigheroperationalefficiencythanPSO. Fig.6Averageruntimesoversamepopulationsizeandthedifferentnumbersofiterations. 6.2.2FeasibilityInordertovalidatetheglobalsearchingcapabilityoftheWSFOAalgorithm,pareittotheoptimizingresultofthePSOalgorithmoverthesamepopulationsize(120)anditerations(500),butwithdifferentservicescale(Fig.7). ItisclearthattheWSFOAoptimizationissuperiortothatoftraditionalPSOinthesameservicescale. Fig.5Averageruntimesoverdifferentpopulationsizesandthesamenumberofiterations. Fig.7Comparativediagramofoptimizingresultsonthesameservicescale. YiwenZhangetal.:AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA 97 ThispapershowsthatnotonlydoesWSFOApossesshighersearchingefficiency,butalsopossessesbetteroptimizingeffectsthanthoseoftraditionalPSO.Therefore,WSFOAhasfinefeasibility. 6.2.3Stability Inorderparethedegreeofdispersionofthe resultsover50trialsinrepeatedexperimentsbetween theWSFOAandPSOalgorithms,theRoot-Mean- SquareError(RMSE)hasbeenproposed[15].The formulaisasfollows: v un uXRMSEDt.Xi X/2=n (17) iD1 TheXrepresentstheaverageofntimesrepeatedtestresults;Xirepresentsthei-thtestresult.ordingtoEq.(17),theresultisshowninFig.8. Obviously,itiseasytoseethestabilityofWSFOAishigherthanthatofPSOinthetwodatasetsabove.CombinedwithFig.7,theresultsshowthattheWSFOA’soptimizationperformanceissignificantlybetterthanPSO. Fig.8AnalysisresultofRMSE. 7RelatedWork AnumberofstudiesofSChavebeenpublishedinrecentyears.Inthissection,wesurveythecurrentapproachforSC.ConventionalSCapproachescanbeclassifiedintothefollowingthreecategories,allofwhichassumeapredefipositionworkflowpattern,exhaustivesearch,classicoptimizationdecisionmethod,andevolutionapproximationalgorithm.
(1)Exhaustivesearch.Thisapproach[16,17]triestoenumerateallbinationsbyusingcandidatewebservicesforeachtask.Asaresult,apositionwiththeoptimalQoSvalueforapredefinedworkflowpatterncanbeselected,ifoneexistsandsatisfiesallglobalQoSconstraints.However,theplexityofthisapproachiseptablyhigh,i.e.,O(mn),wheremandnarethemaximumnumberofcandidateservicesforataskandthenumberoftasksinaworkflow,respectively.Thus,thisapproachisonlysuitableforsmall-scalepositionsituations.
(2)Classicoptimizationdecisionmethod.SCisaprobleminwhichtherearemanypotentialsolutions,amongwhich,oneoralimitednumberofsolutionsareoptimal.Thus,SCisknownasanoptimizationproblem.Sometypesofclassicoptimizationdecisionmethods,suchastheAnalyticHierarchyProcess(AHP)[18],LinearProgramming(LP)[19],dynamicprogramming[20],andTOPSIS[21],canbeusedtosolvethisproblem.Ingeneral,forgeneratingoptimizedpositionusingthismethod,aseveralphaseormulti-layerhierarchicalstructureshouldbedivided.Thenamultiplecriteriadecision-makingprocessisappliedtocalculatetheQoSvalueofcandidateservices,usingtheweightsassignedtoeachQoScriterion.Althoughthisapproachislocallyoptimalandefficientwithalowplexity,itdoesnotguaranteetosatisfyglobalQoSconstraints.Thus,usingclassicalgorithmstosolveoptimizationproblemsispossibleonlywithsomemodificationsandimprovementsfordecreasingtheexecutiontime.
(3)Evolutionapproximationalgorithm.Asthenumberofdistributedservicesisrisingrapidly,particularlyinthecloud,selectingthebestfitservicesforagiventaskesmorechallenging.Todecreasetheplexity,researchersmodeltheSCproblemasbinatorialoptimizationproblem,whichisanpleteproblem.Anevolutionapproximationalgorithmcanbeusedtogeneratea 98 TsinghuaScienceandTechnology,February2015,20
(1):90-99 compositeservicewithasuboptimalQoSvalue,suchasicalgorithm[22],PSO[23],paralleloptimizationalgorithm[24],etc.Thisapproachcanobtaintheapproximateoptimalsolutionwithinaneptablerangeoftime,however,itiseasytofallintoalocaloptimum. 8Conclusions Animprovedoptimizationalgorithmforposition,WSFOA,isputforthinthispaper.ComparedwiththetraditionalPSOalgorithm,theWSFOAhasfasterrunningspeed.TheWSFOAalgorithmreflectstheirreplaceableadvantagesthatPSOdoesnotpossess,especiallyinthecaseoflargeservicescale.Meanwhile,hostsofexperimentsindicatethattheoptimizingeffectsoftheWSFOAalgorithmarebetterthanthoseoftraditionalPSO.Forthetimebeing,itisfarsuperiortothetraditionalPSOalgorithm.Thispaperlaysafoundationforoptimizationresearchofenormouspositioninthebigdataera. Acknowledgements ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(Nos.61402006and61202227),theNaturalScienceFoundationofAnhuiProvinceofChina(No.1408085MF132),theScienceandTechnologyPlanningProjectofAnhuiProvinceofChina(No.1301032162),theCollegeStudentsScientificResearchTrainingProgram(No.KYXL2014060),andthe211ProjectofAnhuiUniversity(No.02303301). References [1]
M.PapazoglouandD.akopoulos,puting,CommunicationsoftheACM,vol.46,no.10,pp.25–28,2003. [2]
J.F.Chen,
H.H.Wang,
D.Towey,
C.Y.Mao,
R.B.Huang,andY.Z.Zhan,Worst-inputmutationapproachtowebservicesvulnerabilitytestingbasedonSOAPmessages,TsinghuaScienceandTechnology,vol.19,no.5,pp.429–441,2014. [3]
T.Wen,
G.J.Sheng,
Q.Guo,andY.Q.Li,Webpositionbasedonmodifiedparticleswarmoptimization,(inChinese),ChineseJournalofComputers,vol.36,no.5,pp.1031–1045,2013. [4]
A.YadavandK.Deep,ShrinkinghyperspherebasedtrajectoryofparticlesinPSO,AppliedMathematicsandComputation,vol.220,no.9,pp.246–267,2013. [5]
S.Panda,
B.Mohanty,andP.K.Hota,HybridBFOAPSOalgorithmforautomaticgenerationcontroloflinearandnonlinearinterconnectedpowersystems,AppliedSoftComputing,vol.13,no.12,pp.4718–4730,2013. [6]
W.T.Pan,Anewfruitflyoptimizationalgorithm:Takingthefinancialdistressmodelasanexample,KnowledgeBasedSystems,vol.26,no.2,pp.69–74,2012. [7]
X.Q.Fan,
C.J.Jiang,
J.L.Wang,andS.C.Pang,RandomQoSawarereliablewebposition,(inChinese),JournalofSoftware,vol.20,no.3,pp.546–556,2009. [8]
S.Xiang,
B.Zhao,
A.Yang,andT.Wei,Dynamicmeasurementprotocolininfrastructureasaservice,TsinghuaScienceandTechnology,vol.19,no.5,pp.470–477,2014. [9]
H.Al-HelalandR.Gamble,Introducingreplaceabilityintowebposition,IEEETransactiononServicesComputing,vol.7,no.2,pp.198–209,2014. [10]
R.EberhartandJ.Kennedy,Anewoptimizerusingparticleswarmtheory,inProceedingsofthe7thInternationalSymposiumonMicroMachineandHumanScience,IEEEServiceCenter,Piscataway,NJ,USA,1995,pp.39–43. [11]
S.MoeinandR.Logeswaran,KGMO:Aswarmoptimizationalgorithmbasedontheicenergyofgasmolecules,InformationSciences,vol.275,pp.127–144,2014. [12]
Y.Liu,
A.H.Ngu,andL.Z.Zeng,putationandpolicingindynamicwebserviceselection,inProceedingsofthe13thInternationalWorldWideWebConferenceonAlternateTrackPapers&Posters,NewYork,USA,2004,pp.66–73. [13]
L.Zeng,
B.Benatallah,andM.Dumas,Qualitydrivenwebposition,inProceedingsofthe12thInternationalConferenceonWorldWideWeb,ACM,NewYork,USA,2003,pp.411–421. [14]
L.Zeng,
B.Benatallah,andA.H.Ngu,QoSawaremiddlewareforwebposition,IEEETransactionsonSoftwareEngineering,vol.30,no.5,pp.311–327,2004. [15]
M.Silic,
G.Delac,
I.Krka,andS.Srbljic,Scalableanduratepredictionofavailabilityofatomicwebservices,IEEETransactiononServicesComputing,vol.7,no.2,pp.252–264,2014. [16]
B.Wu,
C.Chi,andS.Xu.ServiceselectionmodelbasedonQoSreferencevector,inProceedingoftheIEEECongressServices,SaltLakeCity,UT,USA,2007,pp.270–277. [17]
M.AlrifaiandT.Risse,CombiningglobaloptimizationwithlocalselectionforefficientQoS-awareposition,inProceedingofWorldWideWeb,Madrid,Spain,2009,pp.881–890. [18]
A.IshizakaandA.Labib,Reviewofthemaindevelopmentsintheanalytichierarchyprocess,ExpertSystemswithApplications,vol.38,pp.14336–14345,2011. [19]
M.S.Hossain,
M.M.Hassan,
M.AlQurishi,andA.Alghamdi,Resourceallocationforpositionincloud-basedvideosurveillanceplatform,inProceedingofIEEEIntenationalConferenceonMultimediaandExpoWorkshops,Melbourne,Australia,2012,pp.408–412. [20]
D.Worm,
M.Zivkovic,H.vandenBerg,andR.vanderMei,Revenuemaximizationwithqualityassurancepositewebservices,inProceedingofthe5thIEEEInternationalConferenceonService-OrientedComputingandApplications,Taipei,China,2012,pp.1–
9. YiwenZhangetal.:AnOptimizationAlgorithmforServiceCompositionBasedonanImprovedFOA 99 [21]Z.urRehman,
O.KhadeerHussain,andF.KhadeerHussain,ParallelcloudserviceselectionandrankingbasedonQoShistory,InternationalJournalofParallelProgramming,vol.42,no.5,pp.820–852,2014. [22]
A.Klein,
F.Ishikawa,andS.Honiden,San-GAAwork-awareapproachtoposition,IEEETransactionsonServicesComputing,vol.7,no.3,pp.452–464,2014. [23]
S.G.Wang,
Q.B.Sun,
H.Zou,andF.C.Yang,Particleswarmoptimizationwithskylineoperatorforfastcloudbasedwebposition,MobileNetworksandApplications,vol.18,pp.116–121,2013. [24]
F.Tao,
Y.Laili,
L.Xu,andL.Zhang,FC-PACO-RM:Aparallelmethodforpositionoptimal-selectionincloudmanufacturingsystem,IEEETransactionsonIndustrialInformatics,vol.9,pp.2023–2033,2013. YiwenZhangreceivedthemasterdegreeputersoftwareandtheoryin2006andthePhDdegreeinmanagementscienceandengineeringin2013bothfromtheHefeiUniversityofTechnology.HeiscurrentlyanassociateprofessorintheSchoolofComputerScienceandTechnologyatAnhuiUniversity.Hisresearchinterestsincludeputing,puting,andmerce. XingGuoreceivedthemasterdegreeputersciencein2009andthePhDdegreein2013bothfromAnhuiUniversity,China.HeisalecturerintheSchoolofComputerScienceandTechnologyatAnhuiUniversity.Hisresearchinterestsinclude,butarenotlimitedputervision,imageprocessing,puting,andputing. GuangmingCuiisamasterstudentintheSchoolofComputerScienceandTechnology,AnhuiUniversity.Hiscurrentresearchinterestsincludeputingandputing. YanWangisanundergraduatestudentintheSchoolofComputerScienceandTechnologyatAnhuiUniversity.SheismajoringinsoftwareengineeringinAnhuiUniversity.Herresearchinterestsincludeputingandputing. ShuZhaoreceivedherPhDdegreeputersciencefromAnhuiUniversityin2007.SheisnowanassociateprofessorintheDepartmentofComputerscienceandTechnology,AnhuiUniversity.Hercurrentresearchinterestsincludequotientspacetheory,puting,andmachinelearning.