Advertisement
Published in:
2010 | OriginalPaper | Chapter
Runtime Analysis of (1+1) Evolutionary Algorithm for a TSP Instance
Authors : Yu Shan Zhang, Zhi Feng Hao
Published in: Swarm, Evolutionary, and Memetic Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Evolutionary Algorithms (EAs) have been used widely and successfully in solving a famous classical combinatorial optimization problem-the traveling salesman problem (TSP). There are lots of experimental results concerning the TSP. However, relatively few theoretical results on the runtime analysis of EAs on the TSP are available. This paper conducts a runtime analysis of a simple Evolutionary Algorithm called (1+1) EA on a TSP instance. We represent a tour as a string of integer, and randomly choose 2-opt and 3-opt operator as the mutation operator at each iteration. The expected runtime of (1+1) EA on this TSP instance is proved to be
O
(
n
4
), which is tighter than
O
(
n
6
+ (1/
ρ
)
n
ln
n
) of (1+1) MMAA (Max-Min ant algorithms). It is also shown that the selection of mutation operator is very important in (1+1) EA.