位科技与创新管研讨会

2008數位科技與創新管理研討會論文編號：155數位科技組粒子群最佳化演算法求解分散式系統可靠度邱錦清德明財經科技大學資訊管理系摘要本論文提出一個粒子群最佳化演算法求解具容量限制之k-節點集合可靠度，以減少計算時間以及與正解之絕對誤差。此方法在粒子建構其k-節點的過程中，使用一個有效率的目標函數評估其所選擇之節點。由於只須一次的可靠度計算，所以用在可靠度計算的時間極少。而且，本演算法所得到的解，其相對於正解之絕對誤差比k-樹縮減法小。計算結果顯示，本方法對於較大的分散式系統比起傳統的方法有效率。關鍵字：粒子群最佳化演算法、分散式系統、可靠度最佳化2008數位科技與創新管理研討會論文編號：155數位科技組ParticleswarmoptimizationfordistributedsystemreliabilityChin-ChingChiuDept.ofManagementInformationSystem,TakmingUniversityofScienceandTechnologyAbstractInthiswork,wepresentaparticleswarmoptimizationtoreducethecomputationaltimeandtheabsoluteerrorfromtheexactsolutionforobtainingthereliabilityofak-nodesetwithcapacityconstraint.Thismethodusesanefficientobjectivefunctiontoevaluatethechosennodeswhenaparticlederivesitsk-nodesetprocess.Reliabilitycomputationisperformedonlyonce,therebyspendinglesstimetocomputethereliability.Moreover,theabsoluteerrorofproposedalgorithmfromexactsolutionissmallerthanthatofk-treereductionmethod.Computationalresultsdemonstratethattheproposedalgorithmisamoreefficientsolutionforalargedistributedsystemthanconventionalones.Keywords:particleswarmoptimization,distributedsystems,reliabilityoptimization2008數位科技與創新管理研討會論文編號：155數位科技組1.IntroductionParticleswarmoptimization(PSO)wasfirstintroducedbyKennedyandEberhartasanoptimizationtechniqueforcontinuousspaceproblemsin1995[4].Itisakindofevolutionarycomputationtechniquemotivatedbythebehavioroforganismssuchasbirdflocking.Becauseofitssimpleandeasyimplementation,PSOhasbeenwidelyappliedtooptimizationproblemswhichhavebeentackledbyotherevolutionarycomputationtechniquessuchasgeneticalgorithmsandevolutionaryprogramming.ThenetworkreliabilityproblemwithrespecttoanetworkwithageneralstructureisNP-hard[9].Efficientalgorithmseasilyimplementedonacomputerareneededtoanalyzethereliabilityoflargenetworks.Inaddition,suchalgorithmsshouldyieldgoodapproximationsofthereliabilitywhenthenetworksaresolargethatthecomputationaltimebecomesprohibitive.Thisworklargelyfocusesonhowtocomputenearlymaximumsystemreliabilitysubjecttothecapacityconstraint.Inthek-treereductionmethod(KM)[1],thestartingnodeisthefirstnodev1.Toselectotheradequatenodesinasequentialmannerdependsonthemaximumproductofreliabilitybycapacityofthek-nodesetwithanothernodeuntilthecapacityconstraintissatisfied.Thenumberofreliabilitycomputationisstilllarge.Inaddition,theaboveproductheavilyreliesonthetotalcapacityofeachnodebutonlyslightlydependsonthek-nodesetreliability;therefore,itbarelyderivestheoptimalsolution.Thispaperpresentsaparticleswarmoptimizationtoobtainanadequatek-nodeset.ThenSYREL[3]isappliedtocomputethereliability.Foralargedistributedsystem(DS)onvariousDStopologies,ourresultsdemonstratethattheproposedalgorithmismorereliableandefficientthanconventionalalgorithms,theexactmethod(EM)[2]andtheKMintermsofexecutiontime.2.ProblemdescriptionAset,K,ofnodescanbederivedfromthegivenverticessetV(thetotalnumberofvertices|V|=n)thatconstitutesaDSinthatk-nodesetGkreliabilityR(Gk)isadequateandthetotalcapacitysatisfiesthecapacityconstraintCmin.Themainproblemcanbemathematicallystatedasfollows:Object:MaximizeR(Gk)subjecttomin)(CvcsGvks≥∑∈wherec(vs)isthecapacityofthesthnode.Obviously,theproblemforalargeDS,asinametropolitanareanetwork,requiresalargeexecutiontime.3.PSOfork-nodesetreliabilityInthissection,wepresentaPSOalgorithmtomaximizesystemreliability.3.1.TheConceptofProposedAlgorithmThereliabilityofasetofselectednodesdependsontheirlinksandthelinkreliability.Foranynode,thedegreed(vs)ofthatnodevsaffectsthenumberofpathsoftheinformationcanbetransferredfromothers'nodes.Thefollowingformulaisusedtocomputetheweightofnodevsandqs,ddenotestheprobabilityoffailureoflinkes,d.∏=−=)(1,1)(szvdzkssqvw(1)Inthenetwork,twonodesmaycontainmanypathsbetweenthem.Apath’slengthisbetweenoneandn-1.Toreducethecomputationaltime,weconsiderthepathinwhichthelengthisnotgreaterthantwo.Thefollowingformulaisusedtoevaluatetheweightoflinkes,dwhichthe2008數位科技與創新管理研討會論文編號：155數位科技組probabilityofsuccessisps,d.Theys,ddenotesthenumberinwhichthelengthofapathbetweenvsarevdistwo.)(1)(,,1,,,dkksyzdsdszzdspqqew=Π−=(2)Inthesamemanner,ifnodirectlinkexitsbetweenvsandvd,butthereareatleasttwopathswhoselengthistwobetweenthem(denotesthenumberofthosepaths),thefollowingformulaisusedtoevaluatetheweightof.ds,ϕds,ε)(1)(,,1,,dkkszdszzdspqwϕε=Π−=(3)Ineachsetofnodes,ifthenumberofmembersofasetis|k|,thefollowingformulacanbeusedtocomputeitsweightvalue.w(Gk)={[+]/[|k|(|k|-1)/2]+∑∈kdsGedsew,)(,∑∈kdsGvvdsw,,)(ε∑∈ksGvsvw)(/[(n-1)×|k|]}／2||+k(4)Wedefinethepenaltyfunctionofselectedsetasfollows.⎪⎩⎪⎨⎧−≥=∇∑∑∑∈∈∈ksksksGvsGvsGvskCvcifvcCCvcifGminminmin)()()(0)((5)InthestandardPSOalgorithm,allparticleshavetheirposition,velocity,andfitnessvalues.Letpsdenotetheswarmpopulationsize,representspopulationduringtiteration.Theneachparticleintheswarmpopulationhasacurrentpositioninthen-dimensionspaceasacandidatesolution,acurrentvelocitywhichaconstantisusedtolimittherangeof,i.e.,foravoidingtheparticletoconvergetolocaloptima,aparticlebestposition,andaglobalbestpositionoftheswarmpopulationuntilcurrentiteration.],...,,[21tpstttXX