Runtime analysis of (1+1) evolutionary algorithm for two combinatorial optimization instances

Evolutionary Algorithms (EAs) have been used widely and successfully in solving classical combinatorial optimization problems. There are many experimental results in literature concerning combinatorial optimization problems and some theoretical runtime analyses on toy problems, e.g., pseudo-Boolean functions. However, relatively few theoretical results on the runtime analysis of EAs on classical combinatorial optimization problems are available. In this paper, we first conduct a runtime analysis of a simple Evolutionary Algorithm called (1+1)EA on a TSP instance. We represent a tour as a string of integers, and randomly choose either the 2-opt or 3-opt operator as the mutation operator in each iteration. The expected runtime of (1+1)EA on this TSP instance is proved to be O(n ⁴), which is tighter than O(n ⁶+(1/ρ)nlnn) of (1+1) MMAA (Max-Min ant algorithms). A similar approach is then applied to tackle a classical assignment problem instance, where we prove that (1+1)EA needs an average runtime of O(n ³). This article demonstrates the feasibility of the proposed algorithms and runtime analysis approach. © 2009 by Binary Information Press.