Evolving Evolutionary Algorithms

horizontal rule

Home
People
Description
Papers
Source Code
Links

 

    Evolutionary Algorithms (EAs) are powerful tools used for solving difficult real-world problems. They have been developed in order to solve some real-world problems that the classical (mathematical) methods failed to successfully tackle. Many of these unsolved problems are (or could be turned into) optimization problems. The solving of an optimization problem means finding solutions that maximize or minimize a criteria function.

    Many Evolutionary Algorithms have been proposed for dealing with optimization problems. Many solution representations and search operators have been proposed and tested within a wide range of evolutionary models. There are several natural questions to be answered in all these evolutionary models:

    What is the optimal population size?

    What is the optimal individual representation?

    What are the optimal probabilities for applying specific genetic operators?

    What is the optimal number of generations before halting the evolution?

    A breakthrough arose in 1995 when Wolpert and McReady unveiled their work on No Free Lunch (NFL) theorems for Search and Optimization. The No Free Lunch theorems state that all the black-box algorithms have the same average performance over the entire set of optimization problems. (A black-box algorithm does not take into account any information about the problem or the particular instance being solved.) The magnitude of the NFL results stroke all the efforts for developing a universal black-box optimization algorithm capable of solving all the optimization problems in the best manner.

    In their attempt for solving problems, men delegated computers to develop algorithms capable of performing certain tasks. The most prominent effort in this direction is Genetic Programming (GP), an evolutionary technique used for breeding a population of computer programs. Instead of evolving solutions for a particular problem instance, GP is mainly intended for discovering computer programs capable of solving particular classes of optimization problems. (This statement is only partially true since the discovery of computer programs may also be viewed as a technique for solving a particular problem input. For instance, the problem may be here: "Find a computer program that calculates the sum of the elements of an array of integers.").

    There are many such approaches in literature concerning GP. Noticeable effort has been dedicated for evolving deterministic computer programs capable of solving specific problems such as symbolic regression,  classification etc.

    Instead of evolving such deterministic computer programs we will evolve a full-featured evolutionary algorithm (i.e. the output of our main program will be an EA capable of performing a given task). Thus, we will work with EAs at two levels:

    The first (macro) level consists in a steady-state EA which uses a fixed population size, a fixed mutation probability, a fixed crossover probability etc.

    The second (micro) level consists in the solutions encoded in a chromosome of the first level EA.

    The rules employed by the evolved EAs are not preprogrammed. These rules are automatically discovered by the evolution. The evolved EA is a generational one.

    This research was motivated by the need of answering several important questions concerning Evolutionary Algorithms. The most important question is

Can Evolutionary Algorithms be automatically synthesized by using only the information about the problem being solved?.

And, if yes, which are the genetic operators that have to be used in conjunction with an EA (for a given problem)? Moreover, we are also interested to find the optimal (or near-optimal) sequence of genetic operations (selections, crossovers and mutations) to be performed during a generation of an Evolutionary Algorithm for a particular problem. For instance, in a standard GA the sequence is the following: selection, recombination and mutation. But, how do we know that scheme is the best for a particular problem (or problem instance)? We better let the evolution to find the answer for us.

horizontal rule

Home | People | Description | Papers | Source Code | Links

 
contact:
Last updated: miercuri mai 03, 2006.