Файл: Embedded Robotics (Thomas Braunl, 2 ed, 2006).pdf

20 Genetic Algorithms

Program 20.4: Main program

1int main(int argc, char *argv[])

2{ int i;

3

4GeneInt genes[5];

5Chromosome* chromosomes[5];

6Population population;

7

8population.setCrossover(0.5f);

9population.setDecease(0.2f);

10population.setMutation(0.0f);

12// Initialise genes and add them to our chromosomes,

13// then add the chromosomes to the population

14for(i=0; i<5; i++) {

15genes[i].setData((void*) rand()%32);

16chromosomes[i].addGene(&genes[i]);

17population.addChromosome(&chromosomes[i]);

18}

19

20// Continually run the genetic algorithm until the

21// optimal solution is found by the top chromosome

23i = 0;

24do {

25printf("Iteration %d", i++);

26population.evolveNewPopulation();

27population.printState();

28} while((population.getChromosome(0)).getFitness()!=0);

30// Finished

31return 0;

32}

20.6References

BEASLEY, D., BULL, D., MARTIN, R. An Overview of Genetic Algorithms: Part 1, Fundamentals, University Computing, vol. 15, no. 2, 1993a, pp. 58-69 (12)

BEASLEY, D., BULL, D., MARTIN, R. An Overview of Genetic Algorithms: Part 2, Research Topics, University Computing, vol. 15, no. 4, 1993b, pp. 170-181 (12)

BEAULIEU, J., GAGNÉ, C. Open BEAGLE – A Versatile Evolutionary Computation Framework, Département de génie électrique et de génie informatique, Université Laval, Québec, Canada, http://www.gel.ulaval.

ca/~beagle/, 2006

304

References

DARWIN, C. On the Origin of Species by Means of Natural Selection, or Preservation of Favoured Races in the Struggle for Life, John Murray, London, 1859

GALIB Galib – A C++ Library of Genetic Algorithm Components, http:// lancet.mit.edu/ga/, 2006

GOLDBERG, D. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading MA, 1989

HARVEY, I., HUSBANDS, P., CLIFF, D. Issues in Evolutionary Robotics, in J. Meyer, S. Wilson (Eds.), From Animals to Animats 2, Proceedings of the Second International Conference on Simulation of Adaptive Behavior, MIT Press, Cambridge MA, 1993

IJSPEERT, A. Evolution of neural controllers for salamander-like locomotion, Proceedings of Sensor Fusion and Decentralised Control in Robotics Systems II, 1999, pp. 168-179 (12)

LANGTON, C. (Ed.) Artificial Life – An Overview, MIT Press, Cambridge MA, 1995

LEWIS, M., FAGG, A., BEKEY, G. Genetic Algorithms for Gait Synthesis in a Hexapod Robot, in Recent Trends in Mobile Robots, World Scientific, New Jersey, 1994, pp. 317-331 (15)

RAM, A., ARKIN, R., BOONE, G., PEARCE, M. Using Genetic Algorithms to Learn Reactive Control Parameters for Autonomous Robotic Navigation, Journal of Adaptive Behaviour, vol. 2, no. 3, 1994, pp. 277-305 (29)

VENKITACHALAM, D. Implementation of a Behavior-Based System for the Control of Mobile Robots, B.E. Honours Thesis, The Univ. of Western Australia, Electrical and Computer Eng., supervised by T. Bräunl, 2002

305

enetic programming extends the idea of genetic algorithms discussed Gin Chapter 20, using the same idea of evolution going back to Darwin [Darwin 1859]. Here, the genotype is a piece of software, a directly executable program. Genetic programming searches the space of possible computer programs that solve a given problem. The performance of each individual program within the population is evaluated, then programs are selected according to their fitness and undergo operations that produce a new set of programs. These programs can be encoded in a number of different programming languages, but in most cases a variation of Lisp [McCarthy et al. 1962] is cho-

sen, since it facilitates the application of genetic operators.

The concept of genetic programming was introduced by Koza [Koza 1992]. For further background reading see [Blickle, Thiele 1995], [Fernandez 2006], [Hancock 1994], [Langdon, Poli 2002].

21.1 Concepts and Applications

The main concept of genetic programming is its ability to create working programs without the full knowledge of the problem or the solution. No additional encoding is required as in genetic algorithms, since the executable program itself is the phenotype. Other than that, genetic programming is very similar to genetic algorithms. Each program is evaluated by running it and then assigning a fitness value. Fitness values are the base for selection and genetic manipulation of a new generation. As for genetic algorithms, it is important to maintain a wide variety of individuals (here: programs), in order to fully cover the search area.

Koza summarizes the steps in genetic programming as follows [Koza 1992]:

307307

21 Genetic Programming

308

Lisp

Table 21.1: Initial population sizes

21.2 Lisp

S-Expression Lists may be nested and are not only the representation for data structures, but also for program code as well. Lists that start with an operator, such as (+ 1 2), are called S-expressions. An S-expression can be evaluated by the Lisp interpreter (Figure 21.1) and will be replaced by a result value (an atom or a list, depending on the operation). That way, a program execution in a procedural programming language like C will be replaced by a function call in Lisp:

309