Co-evolving memetic algorithms: Initial investigations

Smith, Jim

Abstract

This paper presents and examines the behaviour of a system whereby the rules governing local search within a Memetic Algorithm are co-evolved alongside the problem representation. We describe the rationale for such a system, and the implementation of a simple version in which the evolving rules are encoded as (condition:action) patterns applied to the problem representation, and are effectively self-adapted. We investigate the behaviour of the algorithm on a test suite of problems, and show significant performance improvements over a simple Genetic Algorithm, a Memetic Algorithm using a fixed neighbourhood function, and a similar Memetic Algorithm which uses random rules, i.e. with the learning mechanism disabled. Analysis of these results enables us to draw some conclusions about the way that even the simplified system is able to discover and exploit different forms of structure and regularities within the problems. We suggest that this “meta-learning” of problem features provides a means both of creating highly scaleable algorithms, and of capturing features of the solution space in an understandable form.

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Parallel Problem Solving from Nature — PPSN VII
• Start Date: Sep 7, 2002
• End Date: Sep 11, 2002
• Online Publication Date: Oct 4, 2002
• Publication Date: Jan 1, 2002
• Publicly Available Date: Jun 9, 2019
• Pages: 537-546
• Series Title: Lecture Notes in Computer Science
• Series Number: 2439
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature — PPSN VII
• ISBN: 9783540441397
• DOI: https://doi.org/10.1007/3-540-45712-7_52
• Keywords: computation by abstract devices, algorithm analysis and problem complexity, processor architectures, artificial intelligence, programming techniques, evolutionary biology
• Public URL: https://uwe-repository.worktribe.com/output/1083971