SCI论文模板

Runningtitle:Lietal.On….Animprovedshuffledfrog-leapingalgorithmforknapsackproblemAuthors’nameAffiliationCorrespondenceautuor(通讯作者：):tel/faxXXX;e-mail:XXXAbstractShuffledfrog-leapingalgorithm(SFLA)haslongbeenconsideredasnewevolutionaryalgorithmofgroupevolution,andhasahighcomputingperformanceandexcellentabilityforglobalsearch.KnapsackproblemisatypicalNP-completeproblem.Forthediscretesearchspace,thispaperpresentstheimprovedSFLA,andsolvestheknapsackproblembyusingthealgorithm.Experimentalresultsshowthefeasibilityandeffectivenessofthismethod.Keywords:shuffledfrog-leapingalgorithm;knapsackproblem;optimizationproblem0IntroductionKnapsackproblem(KP)isaverytypicalNP-hardproblemincomputerscience,whichwasfirstproposedandstudiedbyDantzinginthe1950s.Therearemanyalgorithmsforsolvingtheknapsackproblem.ClassicalalgorithmsforKParethebranchandboundmethod(BABM),dynamicprogrammingmethod（分支界定法和动态规划法）,etc.However,mostofsuchalgorithmsareover-relianceonthefeaturesofproblemitself,thecomputationalvolumeofthealgorithmincreasesbyexponentially,andthealgorithmneedsmoresearchingtimewiththeexpansionoftheproblem.IntelligentoptimizationproblemforsolvingNParetheantcolonyalgorithm,greedyalgorithm,etc.Suchalgorithmsdonotdependonthecharacteristicsoftheproblemitself,andhavethestrongglobalsearchability.Relatedstudieshaveshownthatitcaneffectivelyimprovetheabilitytosearchfortheoptimalsolutionbycombiningtheintelligentoptimizationalgorithmwiththelocalheuristicsearchingalgorithm.Shuffledfrog-leapingalgorithmisanewintelligentoptimizationalgorithm,itcombinestheadvantagesofmemealgorithmbasedongeneticevolutionandparticleswarmalgorithmbasedongroupbehavior.Ithasthefollowingcharacteristics:simpleinconcept,fewparameters,thecalculationspeed,globaloptimizationability,easytoimplement,etc.andhasbeeneffectivelyusedinpracticalengineeringproblems,suchasresourceallocation,jobshopprocessarrangements,travelingsalesmanproblem,0/1knapsackproblem,etc.However,thebasicleapfrogalgorithmiseasytoblendintolocaloptimum,andthusthispaperimprovedtheshuffledfrog-leapingalgorithmtosolvecombinatorialoptimizationproblemssuchasknapsackproblem.Experimentalresultsshowthatthealgorithmiseffectiveinsolvingsuchproblems.1ThemathematicalmodelofknapsackproblemKnapsackproblemisaNP-completeproblemaboutcombinatorialoptimization,whichisusuallydividedinto0/1knapsackproblem,completeknapsackproblem,multipleknapsackproblem,mixedknapsackproblem,thelatterthreekindscanbetransformedintothefirst,therefore,thepaperonlydiscussedthe0/1knapsackproblem.Themathematicalmodelof0/1knapsackproblemcanbedescribedas:00max(x10,1,2,...,)niiiniiiixvxwCorinwhere:nisthenumberofobjects;wiistheweightoftheithobject(I=1,2…n);viisthevalueoftheithobject;xiisthechoicestatusoftheithobject;whentheithobjectisselectedintoknapsack,definingvariablexi=1,otherwisexi=0;Cisthemaximumcapacityofknapsack.2Thebasicshuffledfrog-leapingalgorithmItgeneratesPfrogsrandomly,eachfrogrepresentsasolutionoftheproblem,denotedbyUi,whichisseenastheinitialpopulation.Calculatingthefitnessofallthefrogsinthepopulation,andarrangingthefrogaccordingtothedescendingoffitness.Thendividingthefrogsoftheentirepopulationintomsub-groupof,eachsub-groupcontainsnfrogs,soP=m*n.Allocationmethod:inaccordancewiththeprincipleofequalremainder.Thatis,byorderofthescheduled,the1,2,...,nfrogswereassignedtothe1,2,....,Nsub-groupsseparately,then+1frogwasassignedtothefirstsub-group,andsoon,untilallthefrogswereallocated.Foreachsub-group,settingUBisthesolutionhavingthebestfitness,UWisthesolutionhavingtheworstfitness,Ugisthesolutionhavingthebestfitnessintheglobalgroups.Then,searchingaccordingtothelocaldepthwithineachsub-group,andupdatingthelocaloptimalsolution,updatingstrategyis:)minint((),,0maxmaxint(()),,0maxrandUUSUUBWBWrandUUSUUBWBWSqwUUSwhere,Sistheadjustmentvectorofindividualfrog,Smaxisthelargeststepsizethatisallowedtochangebythefrogindividual.Randisarandomnumberbetween0and1.3Theimprovedshuffledfrog-leapingalgorithmforKPAfrogisonbehalfofasolution,whichisexpressedbythechoicestatusvectorofobject,thenfrogU=(x1,x2,…,xn),where,xiisthechoicestatusofthei-thobject;whenthei-thobjectisselectedintoknapsack,definingvariablexi=1,otherwisexi=0;f(i),thefitnessfunctionofindividualfrogcanbedefinedas:3.1ThelocalupdatestrategyoffrogThepurposeofimplementingthelocalsearchinthefrogsub-groupistosearchthelocaloptimalsolutionindifferentsearchdirections,aftersearchinganditeratingacertainnumberofiterations,makingthelocaloptimuminsub-groupgraduallytendtotheglobaloptimumindividual.Definition1Givingafrog’sstatusvectorU,theswitchingsequenceC(i,j)isdefined:where,Uisaidthestateofobjectibecomesfromtheselectedtothecancelstate,orinturn;Ui=Uj,objectiandobjectjexchangeplaces,thatobjectiandobjectjareselectedordeselectedatthesametime.Ui≠Uj,objectiisselectedorcanceled,orinturn.Thenthenewvectorofswitchingoperationis:Definition2SelectinganytwovectorsUiandUjoffrogfromthegroup,D,thedistancefromUitoUjisallexchangesequencesthatUiisadjustedtoUj.where,misthenumberofadjusting.Basedontheabovedefinition,th