(μ+λ)EA算法关于最多叶子生成树问题的近似性能
来源期刊：江西理工大学学报2016年第3期
论文作者：夏小云 郭肇禄 杨书新 王吉源
文章页码：91 - 95
关键词：演化算法;最多叶子生成树问题;近似性能;运行时间分析;
摘 要：为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的（μ+λ）演化算法（（μ+λ）EA）在NP难的最多叶子生成树问题（MLST）上的近似性能,证明了对于最多叶子生成树问题,（μ+λ）EA算法从任意初始解出发,能够分别在期望多项式时间O（（μ/λ）nm2+μmlogn+n）和O（（μ/λ）nm4+μmlogn+n）内获得5和3近似比.并证明了如果选取λ>2μ,基于种群的（μ+λ）EA算法要优于基于单个个体的（1+1）EA算法.
夏小云1，郭肇禄2，杨书新1，王吉源1
1. 江西理工大学信息工程学院2. 江西理工大学理学院
摘 要：为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的（μ+λ）演化算法（（μ+λ）EA）在NP难的最多叶子生成树问题（MLST）上的近似性能,证明了对于最多叶子生成树问题,（μ+λ）EA算法从任意初始解出发,能够分别在期望多项式时间O（（μ/λ）nm2+μmlogn+n）和O（（μ/λ）nm4+μmlogn+n）内获得5和3近似比.并证明了如果选取λ>2μ,基于种群的（μ+λ）EA算法要优于基于单个个体的（1+1）EA算法.
关键词：演化算法;最多叶子生成树问题;近似性能;运行时间分析;
