论文部分内容阅读
为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的(μ+λ)演化算法((μ+λ)EA)在NP难的最多叶子生成树问题(MLST)上的近似性能,证明了对于最多叶子生成树问题,(μ+λ)EA算法从任意初始解出发,能够分别在期望多项式时间O((μ/λ)nm~2+μmlogn+n)和O((μ/λ)nm~4+μmlogn+n)内获得5和3近似比.并证明了如果选取λ>2μ,基于种群的(μ+λ)EA算法要优于基于单个个体的(1+1)EA算法.