| Time Complexity of Maximum Matching by an (N + N) Evolutionary Algorithm (2009) | |||||||||||||||||
Abstract | |||||||||||||||||
| An (N +N) evolutionary algorithm is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that the performance of the evolutionary algorithm is the same as classical simulated annealing. That is, the evolutionary algorithm cannot find the maximum matching in polynomial average time for a family of bipartite graphs considered in this paper although there exists a polynomial deterministic algorithm for solving the problem. On the other hand, the evolutionary algorithm can produce matching with nearly-maximum cardinality in polynomial average time for any general graph. These results represent one of the first steps towards analysing population-based evolutionary algorithms for classical combinatorial optimisation problems. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||