(μ+λ)EA算法关于最多叶子生成树问题的近似性能

Approximation performance of the(μ+λ) EA on the maximum leaf spanning tree problem

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

In order to gain more insight into the working mechanism of evolutionary algorithms and the performance on the NP hard problem, the approximation performance of the（μ ＋λ） EA on the maximum leaf spanning tree problem（MLST） has been studied. The results show that the（μ ＋λ） EA can obtain 5-approximation ratio and 3-approximation ratio on this problem in expected runtime O（（μ/λ）nm^2＋μmlogn＋n） and O（（μ/λ）nm^4＋μmlogn＋n）, respectively. It is also proved that if we choose λ2 μ, the（μ＋λ） EA can outperform the（1＋1） EA with only one individual.