资源描述：
《早稻田大学遗传算法PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、7.MinimumSpanningTreeProblemGraduateSchoolofInformation,ProductionandSystems,WasedaUniversity7.MinimumSpanningTreeProblemMulticriteriaMinimumSpanningTree(mc-MST)1.1BasicConceptofmc-MST1.2GeneticAlgorithmsApproach1.3GAprocedureformc-MST1.4NumericalExperiments2.Degree-constrainedMinimu
2、mSpanningTree(dc-MST)2.1BasicConceptofdc-MST2.2GeneticAlgorithmsApproach2.3GAprocedurefordc-MST2.4NumericalExperiments3.Degree-basedPermutationGAfordc-MST3.1ConceptonDegree-basedPermutationGA3.2GeneticAlgorithmsApproach3.3Degree-basedPermutationGAfordc-MST3.4NumericalExperimentsLeaf-
3、constrainedMinimumSpanningTree4.1BasicConceptoflc-MST4.2GeneticAlgorithmsApproach4.3GAprocedureforlc-MST4.4NumericalExperimentsSoftComputingLab.2WASEDAUNIVERSITY,IPS7.MinimumSpanningTreeProblemTheMinimumSpanningTree(MST)problemwasfirstformulatedbyBoruvkain1926whenhedevelopedasolution
4、tofindingthemosteconomicallayoutofapower-linenetwork.Graham,R.&P.Hell:Onthehistoryoftheminimumspanningtreeproblem,AnnalsoftheHistoryofComputing,vol.7,pp.43-57,1985.Sincethentheminimumspanningtreeformulationhasbeenwidelyappliedtomanycombinatorialoptimizationproblems:Transportationprob
5、lemsTelecommunicationnetworkdesignDistributionsystemsetc.Kershenbaum,A.:TelecommunicationsNetworkDesignAlgorithms,McGrawHill,NewYork,1993.IntroductionSoftComputingLab.3WASEDAUNIVERSITY,IPS7.MinimumSpanningTreeProblemMinimumSpanningTree(MST)problemisoneofthetraditionaloptimizationprob
6、lems.Givenafiniteconnectedgraph,theproblemistofindaleast-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)3DatatableofexamplenetworkBasicConceptofMinimumSpanningTreeProblem126837954253674132461282ijwi
7、jTavakoly.,B.:GeneExpressionDataClusteringWithMinimumSpanningTree,DepartmentofInformationSystemsandComputing,BrunelUniversity,May2003.Tablefornon-directedgraphFig.7.1ExampleofnetworkmodelSoftComputingLab.4WASEDAUNIVERSITY,IPS7.MinimumSpanningTreeProblemNotationsIndicesi,j:theindexofn
8、ode,i,j=1,2,
