µGP is a tool for cultivating a set of individuals, divided into one or more subsets called populations, trough discrete steps called generations. It is an evolutionary algorithm since it mimics some principles of the Darwinian theory of natural selection such as mutation, inheritance, and survival of the fittest.
µGP was frequently exploited to generate Turing-complete programs able to maximize user-defined metrics. It routinely handled problems whose solutions have quite complex structures, such as assembly language programs including functions, interrupt handlers and data. In 2004 µGP evolved a corewar program able to top SAL tiny hill at University of Alberta, CA. It was the first king of the hill not written by a human, and the success was awarded by the silver medal (and $1,000) at the 2005 Human-Competitive Awards. More mundane applications included test and validation of microprocessors and microcontrollers, ranging from toy devices like DLX to real Pentium® 4 (in collaboration with Intel under the grant GP-Based Test Program Generation).
More generally in µGP the solution of a problem is encoded into an individual through a set of rules and constraints, while the problem itself is indirectly defined through a script that evaluates each solution and feeds back the tool with a measure of its goodness. In its typical usage, µGP manipulates such individuals selecting the most promising ones and discarding the others. The fittest individual of the last generation encodes the optimal solution found. A wide range of problems can be tackled, including optimization of mathematical functions represented as trees (almost GP-like), integer and combinatorial optimization (almost GA-like), and real value optimization (almost ES-like).
For an evolutionary computation scholar µGP may present some interesting features: the possibility to shape the behavior smoothly from pure steady-state to generational, including several degree of elitism; self adaptation (of operator strength, operator activation probability, tournament size, population size and number of applied operators); diversity protection (population entropy and delta-entropy of individuals); fitness holes; clone detection (with optional scaling or extermination); support for different population topology (from panmictic to lattice); multiple populations (including migration); support for dynamic fitness functions; support for parallel fitness evaluation; multiple fitness (either priority-based or multiobjective)...
µGP was originally developed in Politecnico di Torino (CAD Group) in 2002. The first version was merely a prototype composed of a few hundred lines of C code and a collection of scripts. The second version was developed in 2003 and maintained since 2006; it consisted of about 10,000 lines in C. µGP v2 added several new features and significantly broadened the applicability of the tool. The development of the third version started in 2006 with the intent to provide a clean, highly versatile, customizable and portable implementation. At the moment it consists of more than 50,000 lines of C++. It must be noted that the last version can be tweaked to behave quite differently from the typical usage described above.
µGP is copyrighted by Giovanni Squillero and distributed under GNU Public License (GPL). The project is kindly hosted by sourceforge on http://sourceforge.net/projects/ugp3/, you can download the latest version of µGP3 and some superseded snapshots of µGP v2 from http://prdownloads.sourceforge.net/ugp3.
Updated information may be found at http://www.cad.polito.it/ugp3/. If you wish to get involved, submit a bug report or simply if you need help please contact ugp3 @ cad . polito . it (the address is slightly mangled to prevent spamming).