dc.contributor.author |
Dinneen, Michael |
en |
dc.contributor.author |
Wei, Kuai |
en |
dc.coverage.spatial |
Cancun, Mexico |
en |
dc.date.accessioned |
2014-11-21T04:40:33Z |
en |
dc.date.issued |
2013 |
en |
dc.identifier.citation |
2013 IEEE Congress on Evolutionary Computation, CEC 2013, Cancun, Mexico, 20 Jun 2013 - 23 Jun 2013. Evolutionary Computation (CEC) 2013. 1626-1634. 2013 |
en |
dc.identifier.isbn |
9781479904549 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/23556 |
en |
dc.description.abstract |
A memetic algorithm (MA) is an Evolutionary Algorithm (EA) augmented with a local search. We previously defined a (1+1) Adaptive Memetic Algorithm (AMA) with two different local searches, and the comparison with the well-known (1+1) EA, Dynamic (1+1) EA and (1+1) MA on some toy functions showed promise for our proposed algorithm. In this paper we focus on the NP-hard Maximum Clique Problem, and show the success of our proposed (1+1) AMA. We propose a new metric (expected running time to escape a local optimal), and show how this metric dominates the expected running time of finding a maximum clique. Then based on this new metric, we show the above analyzed algorithms are expected to find a maximum clique on graphs, bipartite graphs and sparse random graphs in a polynomial time in the number of vertices. Also based on our new metric, we will show that if an algorithm takes an exponential time to find a maximum clique of a graph, it must have been trapped into at least one local optimal that is extremely hard to escape. Furthermore, we will show that our proposed (1+1) AMA with a random permutation local search is expected to escape these (hard to escape) local optimal cliques drastically faster than the well-known basic (1+1) EA. The success of our experimental results also shows the benefit of our adaptive strategy combined with the random permutation local search. |
en |
dc.publisher |
IEEE |
en |
dc.relation.ispartof |
Congress on Evolutionary Computation (CEC) |
en |
dc.relation.ispartofseries |
2013 IEEE Congress on Evolutionary Computation |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.ieee.org/publications_standards/publications/rights/rights_policies.html |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
A (1+1) Adaptive memetic algorithm for the maximum clique problem |
en |
dc.type |
Conference Item |
en |
dc.identifier.doi |
10.1109/CEC.2013.6557756 |
en |
pubs.begin-page |
1626 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
pubs.end-page |
1634 |
en |
pubs.finish-date |
2013-06-23 |
en |
pubs.start-date |
2013-06-20 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Proceedings |
en |
pubs.elements-id |
406068 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2017-10-17 |
en |
pubs.online-publication-date |
2013-07-15 |
en |