Abstract
We revisit the classical analysis of the (1+1) EA for the minimum spanning tree problem in the case that nothing is known about the weights of the underlying graph. Here the original upper bound on the expected running time by Neumann and Wegener [Theor. Comput. Sci. 378(1), 32-40, 2007], which depends on the largest weight of the graph, is of no use. The best upper bound available before in this case is due to Reichel and Skutella [FOGA 2009, 21-28] and is of order O(m3 \log n), where m is the number of edges and n the number of vertices. Using an adaptive drift analysis, we show the improved bound O(m2 (sqrt{c(G)} + \log n)), where c(G) is the circumference (length of the longest cycle) of the graph. This is only by an asymptotic factor of at most sqrt{n}/\log n away from the classical lower bound. Furthermore, an alternative fitness function leading to the bound O(m2\log n) is proposed, and limitations of the adaptive drift analysis are pointed out.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14) |
Publisher | Association for Computing Machinery |
Publication date | 2014 |
Pages | 509-516 |
ISBN (Electronic) | 978-1-4503-2662-9 |
DOIs | |
Publication status | Published - 2014 |
Event | 2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada Duration: 12 Jul 2014 → 16 Jul 2014 http://www.sigevo.org/gecco-2014/index.html |
Conference
Conference | 2014 Genetic and Evolutionary Computation Conference |
---|---|
Country/Territory | Canada |
City | Vancouver |
Period | 12/07/2014 → 16/07/2014 |
Internet address |
Keywords
- Evolutionary Algorithms
- Minimum Spanning Tree Problem
- Runtime Analysis