2022/03/16 by Samuel Baguley, Tobias Friedrich, Baguley, Samuel +9
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Combinatorics (math.CO) #Evolutionary Algorithms and Applications #FOS: Mathematics #Genome Rearrangement Algorithms #Metaheuristic Optimization Algorithms Research #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.2203.08790
arxiv created 2022/03/16 · openalex publication_date 2022/03/16 · arxiv updated 2022/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size n. Regarding the path we prove that, for a particular initial configuration, the \alg1+1 takes in expectation Θ(n4) iterations while the modification reduces this to Θ(n3), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability 1-1/2Ω(nξ) for every positive constant ξ< 1, which improves the known probability of 1-1/poly(n) for the (1+1) EA..