A (1+1) Adaptive memetic algorithm for the maximum clique problem

Show simple item record

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

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace