Do you think you can beat my “perfect” score in this god forsaken penguin hitting game? I think not!

Grand Slam Penguins!

Evolutionary Computation Theory and Paradigms

The chapter begins by exploring some of the history of evolutionary computation. They take a look at the four areas of evolutionary computation (genetic algorithms, evolutionary programming, evolution strategies, and genetic programming) in terms of people rather than technologies (during history). First they talk about genetic algorithms and contributions made by A.S. Frasier, and then work their way to John Holland who is the main focus. From Holland they start talking about his students, Bagley, K. A. De Jong, and David E. Goldberg. Additionally, there is discussion of Steve Smith, and John Grefenstette’s contributions (both students of De Jong). The next discussion is on evolutionary programming where they examine the work of Larry J. Fogel and his colleagues. They also mention work by Don Dearhold and his students. Ingo Rechenberg and Hans-Paul Schwefel are illustrated as the pioneers of evolution strategies, the section focuses only on their contributions. The genetic programming section highlights the work of Friedberg, Dunham, and North. John Koza did extensions of their work. The section ends by discussing emerging trends towards the unification of the four fields.

The following section provides and overview of evolutionary computing. They first discuss the primary three things that are present in all four types. After which they begin discussing the evolutionary computing paradigm attributes. Where they discuss issues in relation to other existing search paradigms. This discussion provides the foundation for implementation concepts, where they explore the five steps of implementation that are found in all the systems. From this point they begin looking at specific implementation of the four areas of evolutionary computing.

Genetic algorithms are the most practiced, and perhaps relevant to swarm intelligence so they are addressed at length. The section begins with a quick primer on the various terms used within GAs. This explanation is followed by an overview of GAs. Here they discuss the five steps of implementation tailored towards GAs. The main difference is that crossover is so important. A simple GA problem is then examined to illustrate the key points. This study is attempting to optimize a value of x based on a sine function. In this example they illustrate simple implementations of crossover and mutation. After the sample they give a review of GAs where they discuss the representation of variables, population sizes, population initialization, fitness calculations, roulette wheel selection, crossover, and mutation in detail. Having established the basics they begin to look at schemata and the schema theorem. First they discuss what exactly a schemata is and how to implement, and perform various procedures on them (such as crossover). Then, they provide the schema theorem that predicts the number of times a specific schema will appear in the next generation of a GA, given the fitness of the population members in the schema. The section is ended with the authors’ thoughts on GAs as a whole.

Evolutionary programming is examined in the next section. The section begins with a primer on evolutionary programming. They then go into an explanation of how the five-implementation steps are tailored for EP. Since EP is essentially a top down approach they describe it in terms of the evolution of a finite state machine. They give design level implementation concepts for dealing with problems such as the addition and removal of states. There is also discussion of the five types of mutation that can occur. Another type of problem that EPs are used for is, function optimization. From this they illustrate how one might use this to solve the prisoner’s “dilemma.” As in the previous section, this ends with their thoughts on EPs as a whole.

Evolution strategies—an expansion of evolutionary programming—are examined in the following section. Once again, the section begins with an explanation of what exactly, evolution strategies, is. Then, they jump into an explanation of mutation in terms of an entire population. From the biological explanation they begin to discuss the foundations of how this is implemented. The next issue they address is recombination. After establishing how alterations are made, they discuss how selection is performed. This section ends with an explanation of the implementation procedure, and a brief summary of ES.

The final section examines genetic programming, which is often thought of as a subset of genetic algorithms. The section begins by explaining that genetic programming focuses on tree structures. From this they explain the five preparatory steps of implementation. After those five steps have been completed the program continues on the “real” implementation steps. They talk about different methods that are used to make the tree “grow.” This section is ended with a summary of GP, and problems that you are most likely to encounter when trying to implement it.

Grimm, Wilhelm and Grimm, Jacob. “The Shoes That Were Danced to Pieces.” Grimm’s Complete Fairy Tales. Barnes and Noble Books, 1993: 336-339.

A king had twelve daughters, but no son. All of the princesses slept in the same chamber, which was locked every night. Upon opening the room every morning the king found that their shoes had been worn out during the night. Utterly perplexed, and in need of an heir, the king decided that if someone could figure out where the princesses went during the night they would be allowed to wed the princess of their choice and would become the heir apparent. However, if they failed to figure it out within three days they were beheaded.

Soon sons of kings, and other attempted to figure out what the princesses were up to. But, they all failed and were beheaded in the end. Eventually an old soldier wondered into the kingdom. He happened upon an old woman who asked why he came to the kingdom. He explained that he was past his prime, and thought it would be nice to spent his last days as king. The old woman instructed him not to drink the wine from the princesses, and to wear an invisible cloak—that she provided—to follow them.

Once his chance had come he did as the old woman instructed. Once the princesses thought he was asleep they begin their routine, opening a magic doorway that revealed a staircase. The soldier followed them down, to where the princesses met twelve princes that they danced with each night. The soldier returned before the princesses, and for each of the three nights he did the same thing, each time collecting a token from the underworld. Upon the morning of the fourth day the king called the man before him. The soldier explained what had happened and showed the tokens. The princesses confessed, and he married the eldest. The king died shortly thereafter and the old soldier took his place upon the throne.