Comparing Two Local Searches in a (1+1) Restart Memetic Algorithm on the Clique Problem

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Wei, K en
dc.contributor.author Dinneen, MJ en
dc.date.accessioned 2014-01-05T22:48:17Z en
dc.date.available 2014-01-05T22:48:17Z en
dc.date.issued 2013 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-447 (2013) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/21346 en
dc.description.abstract In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm to solve one problem (a single fitness function), has been verified in many successful experiments. However, theoretical studies cannot explain why Memetic Algorithms with multiple local searches often outperform Memetic Algorithms with a single local search in these experiments. In this paper, we will formalize a (1+1) Restart Memetic Algorithm and two different local searches, and run them on a single fitness function to solve the Clique Problem. We then show that there are two families of graphs such that, for the first family of graphs, Memetic Algorithms with one local search drastically outperform Memetic Algorithms with the other local search, and vice versa for the second family of graphs. Furthermore, we propose a (1+1) Restart Memetic Algorithm with an Alternative Local Search, and show that the proposed algorithm is expected to solve the Clique Problem on both families of graphs efficiently. Lastly, we verify our theoretical results by experiments. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series 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. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial en
dc.title Comparing Two Local Searches in a (1+1) Restart Memetic Algorithm on the Clique Problem en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en
dc.rights.holder The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en


Full text options

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Advanced Search

Browse