Implementing a Collective Knowledge System for Memetic Algorithms

Overview

Objectives/Goals Memetic algorithms are an agent based artificial intelligence method. Memetic algorithms are unable to effectively distribute information and do not benefit from ideas known in other agents in the simulation. The goal of this project is to design and test a system for the transmission and management of information between agents in a memetic simulation. If the simulation is able to better utilize information, then the efficiency of the simulation will improve. Methods/Materials Memetic algorithms combine principals of evolution and genetics to produce computer programs capable of evolving solutions. Through emulation of the biological process of evolution, algorithms representing possible solutions to a problem interact and undergo recombination to produce offspring algorithms. A heuristic local search mechanism constitutes the primary search method for the algorithms, with the genetic recombination serving as a micro-search mechanism to optimize the local search. A custom memetic algorithm simulation was written in C++ as a multi-threaded, parallel execution application. The knowledge system was written in SQL as a multi-tired database application. Results The memetic algorithm was 16.6 times more efficient than genetic algorithms and 108.2 times more efficient than sequential search algorithms for solving a simple equation. A system for distributing knowledge discovered during the simulation was implemented and shown to improve the efficiency of the memetic algorithm by 18.5%. The information stored in the knowledge system was used as an additional feedback loop for the simulation. This allowed the simulation to bias the areas of the solution space searched. The time required to solve subsequent test cases of the problem type was reduced by a further 9.7%. The simulation had a tendency to be #lazy# and avoid difficult regions of the solution space. Methods were implemented to force the simulation to consider difficult regions of the solution space. Conclusions/Discussion The simulation was able to use the knowledge system and improve the efficiency of the memetic algorithm search. The information contained in the knowledge bank represents a more general description of the problem type with each new test case. The author is working to implement an induction system capable of deriving a general case solution from the data stored in the knowledge system.

Competition history

• CSEF 2002 Mathematics & Software · Entry S1209

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2002 project