资源描述：
《清华大学遗传算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、7.MinimumSpanningTreeProblemGraduateSchoolofInformation,ProductionandSystems,WasedaUniversity7.MinimumSpanningTreeProblemMulticriteriaMinimumSpanningTree(mc-MST)1.1BasicConceptofmc-MST1.2GeneticAlgorithmsApproach1.3GAprocedureformc-MST1.4NumericalExperiments2.Degree-constrainedM
2、inimumSpanningTree(dc-MST)2.1BasicConceptofdc-MST2.2GeneticAlgorithmsApproach2.3GAprocedurefordc-MST2.4NumericalExperiments3.Degree-basedPermutationGAfordc-MST3.1ConceptonDegree-basedPermutationGA3.2GeneticAlgorithmsApproach3.3Degree-basedPermutationGAfordc-MST3.4NumericalExperi
3、mentsLeaf-constrainedMinimumSpanningTree4.1BasicConceptoflc-MST4.2GeneticAlgorithmsApproach4.3GAprocedureforlc-MST4.4NumericalExperiments7.MinimumSpanningTreeProblemTheMinimumSpanningTree(MST)problemwasfirstformulatedbyBoruvkain1926whenhedevelopedasolutiontofindingthemosteconomi
4、callayoutofapower-linenetwork.Graham,R.&P.Hell:Onthehistoryoftheminimumspanningtreeproblem,AnnalsoftheHistoryofComputing,vol.7,pp.43-57,1985.Sincethentheminimumspanningtreeformulationhasbeenwidelyappliedtomanycombinatorialoptimizationproblems:TransportationproblemsTelecommunicat
5、ionnetworkdesignDistributionsystemsetc.Kershenbaum,A.:TelecommunicationsNetworkDesignAlgorithms,McGrawHill,NewYork,1993.Introduction7.MinimumSpanningTreeProblemMinimumSpanningTree(MST)problemisoneofthetraditionaloptimizationproblems.Givenafiniteconnectedgraph,theproblemistofinda
6、least-weightsubgraphconnectingallvertices.(i,j)wij(1,2)2(1,6)5(1,8)3(2,3)4(2,8)6(3,4)2(3,9)2(4,5)1(4,9)8(5,6)6(5,7)2(6,7)7(7,8)1(7,9)4(8,9)3DatatableofexamplenetworkBasicConceptofMinimumSpanningTreeProblem126837954253674132461282ijwijTavakoly.,B.:GeneExpressionDataClusteringWith
7、MinimumSpanningTree,DepartmentofInformationSystemsandComputing,BrunelUniversity,May2003.Tablefornon-directedgraphFig.7.1Exampleofnetworkmodel7.MinimumSpanningTreeProblemNotationsIndicesi,j:theindexofnode,i,j=1,2,…,nParametersn:thenumberofnodesinthenetworkV:thefinitesetofnodes(ve
8、rtices)representingterminalsS:thesubsetofnodesw
