摘要: Abstract—Recently it has been proved that the (1+1)-EAproduces poor worst-case approximations for vertex coverproblem. In this paper result is extended to (1+λ)-EAby proving that, given a polynomial time, algorithm canonly find covers an instance class of bipartite graphs.Although generalisation (μ+1)-EA ismore difficult, hints are in show thisalgorithm may get stuck on local optimum bipartitegraphs as well because premature convergence. However asimple diversity maintenance mechanism can be introduced intothe EA optimising effectively. Itis combined with one pointcrossover change runtime some classes fromexponential number nodes graph. I. I NTRODUCTION Evolutionary Algorithms (EAs) randomised searchheuristics often used solving combinatorial optimisationproblems [1]. Although theoretical analysis EAs isway behindcomparedto amountof practicalapplications,in recent years fair amount work accom-plished study computational complexity ofthe (1+1)-EA optimisation problems [2].However, results about population-based arefewer compared those related (1+1)-EA. Jansen et.al. have analysed (1+λ)-EA pseudo-boolean functionssuch asOnemaxand Leadingones[3]. Similar hasbeenproduced by Witt concerning [4]. He and Yaohave single individuals against populations also onpseudo-booleanproblems [5]. The latter only considerssingle bit mutations. available “real-world” prob-lems even fewer. Some the(1+λ)-EA spanning tree problem [6], the(μ+1)-EA finding Cliques semi-random sparse graphs[7]. An (2N+2N)-EA instances subset sum aboutpopulation-based NP-Hard [8].In we make first step ofpopulation-based cover, known applica-tions fields like scheduling or networking.When analysingan problem, cannot expectedthat every optimal solution found poly-nomial unless P=NP. As consequence, important