一种求解多目标最小生成树问题的有效离散粒子群优化算法 (1)..doc

第22卷第4期2009年8月模式识别与人工智能PR&’21(福州大学数学与计算机科学学院福州350108)2(福州大学离散数学及其应用教育部重点实验室福州350003),,,,,多目标优化问题(MOP),最小生成树(MST),粒子群优化(PSO)中图法分类号TP181AnEfficientDiscreteParticleSwarmOptimizationAlgorithmforMulti-,・21(puterSciences,FuzhouUniversity,Fuzhou350108)2(KeyLaboratoryofDiscreteMathematicswithApplicationsofMinistryofEducation,FuzhouUniversity,Fuzhou350003)ABSTRACTAdiscreteparticleswarmoptimization(DPSO),(GA),,Multi-ObjectiveOptimizationProblem(MOP),MinimumSpanningTree(MST),ParticleSwarmOptimization(PSO)・国家973计划项目()、国家自然科学基金项目()、教育部科学技术研究重点项目()、福建省自然科学基金重点项目()和福建省自然科学基金项目()资助收稿日期:2008-07一18;修网日期:2009-02—07作者简介郭文忠,男,,博士研究生,主要研究方向为计算智能、:******@fzu..陈国龙,男,1965年生,教授,博士生导师,主要研究方向为人工智能、网络信息安全等. 万方数据模式识别与人工智能22卷1引言在超大规模集成电路(VeryLargeScaleIntegra—tion,VL5I)的版图设计中,,,在布局时考虑性能优化或时延优化时需将连线延迟考虑在布局或布图规划的目标函数中,从而也使布局中的线长估计更显其重要性。通常,计算一条线网的连线长度有最小斯坦纳、最小生成树(MinimumSpanningTree,MST)、最小链等方法….MST是构造一个带权图的最小代价生成树,,图论中已有一些经典的求解最小生成树算法,如Kruskal算法、,其计算复杂度为多项式时间,但当给MST增加约束条件或问题目标为多个时,相应的问题称为多目标最小生成树(Multi-CriteriaMST,me—MST)问题,,近年来许多启发式算法应运而生,其中最具代表的算法是Zhou和Genpo提出一种