基于蚁群系统的双目标最小生成树算法  

Research on bi-criteria minimum spanning tree problem based on ant colony system

作　　者：赵玲[1] 张建科[2] 

机构地区：[1]集美大学理学院,福建厦门361021 [2]西安邮电学院应用数理系,陕西西安710121

出　　处：《西安邮电学院学报》2008年第5期82-84,92,共4页Journal of Xi'an Institute of Posts and Telecommunications

基　　金：福建省自然科学基金项目(2007J0202);陕西省教育厅自然科学研究项目(编号:07JK376)

摘　　要：带有多个目标的最小生成树问题在实际生活中有着广泛的应用,但用传统方法很难有效地解决,本文提出一种基于多目标决策的蚁群系统求解双目标最小生成树算法,利用两个启发信息来构造新的状态转移规则,并改进了信息素更新规则,指导蚂蚁找到Pareto最优解。试验结果表明,该算法能有效解决双目标生成树问题,与Pareto最优枚举法比较,求解时间减少了。It is difficult to solve muti-criteria minimum spanning tree （MCMST）, which is widely used in daily life, by the traditional methods. The multiple objective ant eolony system is proposed to solve MCMST problem in this paper. A novel pseudorandom proportional rule and the update of pheromone trails are constructed in this algorithm to obtain Pareto optimal solutions. Simulation results show that our algorithm can achieve the better performanee than the method of Pareto optimal enumeration.

关 键 词：蚁群系统 双目标 最小生成树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O223[自动化与计算机技术—计算机科学与技术]