_EA算法关于最多叶子生成树问题近似性能_夏小云.pdf

第 卷 第 期 Vol.37, No.3 37 3 江西理工大学学报 年 月 Journal of Jiangxi University of Science and Technology Jun. 2016 2016 6 文章编号： （ ） 2095-3046 2016 03-0091-05 DOI: 10.13265/j.cnki.jxlgdxxb.2016.03.016 （ ）A 算法关于最多叶子生成树问题的近似性能 μ +λ E 夏小云a ， 郭肇禄b ， 杨书新a ， 王吉源a 江西理工大学 信息工程学院 理学院 江西赣州 （ ， ； ， ） a. b. 341000 摘 要 为了更好地理解演化算法的运行机制及其在求解 难问题上的性能 研究了基于种群 ： NP ， 的 演化算法 在 难的最多叶子生成树问题 上的近似性能 证明 （ ） （（ ） ） （ ） ， μ +λ μ +λ EA NP MLST 了对于最多叶子生成树问题 算法从任意初始解出发 能够分别在期望多项式时 ，（ ） ， μ +λ EA 间 μ 2 μ 4 获得 似比 证明了如果选取 （（ ） ）和 （（ ） ） 内 和 近 并 O nm +μ mlogn +n O nm +μ mlogn +n 5 3 . λ λ ，基于种群的（ ） A 算法要优于基于单个个体的（ 1） A 算法 λ 2μ μ +λ E 1+ E . 关键词 演化算法 最多叶子生成树问题 近似性能 运行时间分析 ： ； ； ； 中图分类号： 文献标志码： TP18 A Approximation performance of the (μ +λ) EA on the maximum leaf spanning tree problem XIA Xiaoyuna, GUO Zhaolub, YANG Shuxina,