Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/77100
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | A parameterized runtime analysis of evolutionary algorithms for the Euclidean traveling salesperson problem |
Author: | Sutton, A. Neumann, F. |
Citation: | Proceedings of the 26th National Conference on Artificial Intelligence, 2012: pp.1105-1111 |
Publisher: | AAAI |
Publisher Place: | online |
Issue Date: | 2012 |
ISBN: | 9781577355687 |
Conference Name: | AAAI Conference on Artificial Intelligence (26th : 2012 : Toronto, Canada) |
Statement of Responsibility: | Sutton, A. M., Neumann, F. |
Abstract: | We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points k and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time O(n 4k(2k - 1)!). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time O(n 2kk!). |
Rights: | Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved. |
DOI: | 10.999/1234 |
Description (link): | http://www.aaai.org/Conferences/AAAI/aaai12.php |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_77100.pdf Restricted Access | Restricted Access | 218.72 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.