Introduction: an evolutionary algorithm step by step

Warning

The programs in this tutorial have been tested with Perl 5.6.1.633, as downloaded from ActiveState in a Windows 98 system. And yes, I accept condolences for it; I didn't have any Linux machine handy during my holidays. Halfway through writing this tutorial, I downloaded Perl 5.8.0 for CygWin; some examples also work with that version, and I guess the rest should have no problem.

Warning

Download the whole tutorial, in PDF and the original DocBook document

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.