当前位置：文档之家 › Developing Efficient Metaheuristics for Communication Network Problems by using Problem-spe

Developing Efficient Metaheuristics for Communication Network Problems by using Problem-spe

  • 格式：pdf
  • 大小：267.81 KB
  • 文档页数：30

下载文档原格式

  / 30

合集下载

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

DevelopingEfficientMetaheuristicsforCommunication

NetworkProblemsbyusingProblem-specificKnowledge

FranzRothlaufandArminHeinzl

WorkingPaper9/2004

August2004

WorkingPapersinInformationSystemsDevelopingEfficientMetaheuristicsfor

CommunicationNetworkProblemsbyusing

Problem-specificKnowledge

FranzRothlauf

Dept.ofBusinessAdministrationandInformationSystems

UniversityofMannheim

D-68131Mannheim/Germany

rothlauf@uni-mannheim.de

ArminHeinzl

Dept.ofBusinessAdministrationandInformationSystems

UniversityofMannheim

D-68131Mannheim/Germany

heinzl@uni-mannheim.de

August24,2004

Abstract

Metaheuristics,suchasevolutionaryalgorithmsorsimulatedannealing,arewidelyapplicableheuristicoptimizationstrategiesthathaveshownencouragingresultsforalargenumberofdifficultoptimizationproblems.Toshowhighperformance,metaheuristicsneedtobeadaptedtothepropertiesoftheproblemathand.Thispaperillustrateshowefficientmetaheuristicscanbedevelopedforcommunicationnetworkproblemsbyutilizingproblem-specificknowledgeforthedesignofahigh-qualityprob-lemrepresentation.Theminimumcommunicationspanningtree(MCST)problemfindsacommunicationspanningtreethatconnectsallnodesandsatisfiestheircommunicationrequirementsforaminimumtotalcost.Aninvestigationintothepropertiesoftheproblemrevealsthatoptimumso-lutionsaresimilartotheminimumspanningtree(MST).Consequently,aproblem-specificrepresentation,thelinkbiased(LB)encoding,isdevel-oped,whichrepresentstreesasalistoffloats.TheLBencodingmakesuseoftheknowledgethatoptimumsolutionsaresimilartotheMST,andencodestreesthataresimilartotheMSTwithahigherprobability.Experimentalresultsfordifferenttypesofmetaheuristicsshowthatmeta-heuristicsusingtheLB-encodingefficientlysolveexistingMCSTprobleminstancesfromtheliterature,aswellasrandomlygeneratedMCSTprob-lemsofdifferentsizesandtypes.

1Introduction

Theproblemofdesigningacommunicationnetworkforagivensetofrequire-

mentsisrelevantforcommunicationproviders,aswellasforcompaniesand

1institutionswhowanttobuilduptheirowncommunicationinfrastructureby

renting,orbuying,communicationcapacitiesfromcommunicationproviders.

Theproblemconsideredinthispaperinvolvesselectingaspanningtreeforthe

networkonwhichallcommunicationwillbeperformed.Treestructuresare

especiallyimportantforthedesignofsmallernetworkslikecorporatenetworks,

accessnetworks,orlocalareanetworks.Theproblemofbuildingupcost-

minimalcommunicationspanningtreeswasformalizedbytheminimumcom-

municationspanningtree(MCST)problem.TheMCSTproblem(Hu,1974)

findsaspanningtreethatconnectsallgivennodesandsatisfiestheircommu-

nicationrequirementsforaminimumtotalcost.Thenumberandpositionsof

thenetworknodesaregivenaprioriandthecostofthenetworkisdetermined

bythecostofthelinks.Likeotherconstrainedspanningtreeproblems,the

OCSTproblemisNP-hard(Garey&Johnson,1979).

ThepurposeofthispaperistodemonstratehowtheMCSTproblemcan

efficientlybesolvedbyusingmetaheuristicswhenproblem-specificknowledge

isconsideredforthedesignofanappropriatetreerepresentation.Previous

work(Rothlaufetal.,2003)hasshownthatoptimalsolutionsforMCSTprob-

lemsareonaveragesimilartotheminimumspanningtree(MST)definedon

thedistanceweightsofthelinks.Thisproblem-specificknowledgeaboutthe

MCSTproblemcanbeutilizedbycombiningmetaheuristicslikeevolutionary

algorithms(EA),orsimulatedannealing,withthelink-biased(LB)encoding,

whichisarepresentationfortrees.TheLBencodingdoesnotrepresentall

possibletreeswiththesameprobability,butrandomlychosenLB-encodedso-

lutionsencodetreesthataresimilartotheMSTwithhigherprobabilitythan

randomlychosentrees.Performanceevaluationsarepresentedforacollection

ofexistingprobleminstancesfromtheliteratureaswellasrandomlygenerated

MCSTprobleminstances.Theexperimentalresultsshowthatduetotheover-

representationofMST-liketrees,metaheuristicsusingthelink-biasedencoding

showhigherperformancethanmetaheuristicsthatuserepresentationswhich

encodeallpossibletreesuniformly.Thepresentedworkisanexampleonhow

theefficiencyofmetaheuristicscanbeincreasedinasystematicwaybymak-

inguseofadditionalproblem-specificknowledgeregardingtheproblemtobe

solved.

Thepaperisstructuredasfollows:Thefollowingsectiongivesashortde-

scriptionoftheMCSTproblem,reviewsexistingapproximationalgorithms,

andgivesanoverviewofearlierworkwhichdemonstratesthatoptimalsolu-

tionsforMCSTproblemsaresimilartotheMST.Section3demonstrateshow

metaheuristicsandespeciallyEAscanbeadoptedforsolvingtheMCSTprob-

lem.ItdescribesthefunctionalityandrelevantdesignparametersofEAsand

introducestheLB-encoding,whichallowstorepresenttreessimilartotheMST

withahigherprobability.Section4presentsexperimentalresultsforexist-

ingprobleminstancesfromtheliteratureaswellasforrandomlycreatedtest

problems.Thepaperendswithconcludingremarks.

2