Introduction to evolutionary computation

If you have not been in another planet (and without interplanetary Internet connection), you probably have a (maybe vague) idea of what evolutionary computation is all about.

The basic idea is surprisingly simple, but incredibly powerful: an algorithm that tries to obtain good enough solutions by creating a population of data structures that represent them, and evolves that population by changing those solutions, combining them to create new ones, and, on average, making the better-suited survive and the worst-suited perish. That is the way Evolution of Species, as described by Darwin, has worked for a long time, so, why shouldn't it work for us?

It so happens that it does: evolutionary computation spans a family of optimization salgorithms, differing in details such as the way of selecting the best, how to create new solutions from existing ones, and the data structures used to represent those solutions. Those algorithms are called evolution strategies, genetic algorithms, genetic programming, or evolutionary programming, although they correspond to the same basic algorithmic skeleton.

Applications of evolutionary algorithms are found everywhere, even in the real world, and range from entertainment (playing Mastermind), to generating works of art like the eArtWeb does, to more mundane, but interesting nonetheless, things like assigning telecommunication frequencies, designing timetables, or scheduling tasks in an operating system.

This tutorial will be divided in two parts: the first will be devoted to explaining the guts (and glory) of an evolutionary algorithm, by programming it from scratch, introducing new elements, until we arrive at the canonical classical genetic algorithm. The second part will use an existing evolutionary computation library, called Algorithm::Evolutionary, to design evolutionary computation applications by using XML, Perl, and taking advantage of the facilities Perl modules afford us.