µGP (
MicroGP)
is a versatile optimizer able to outperform both human experts and conventional heuristics in finding the optimal solution of hard problems.
Given a task, it first fosters a set of random
solutions, then iteratively refines and enhance them.
Its heuristic algorithm uses the result of the evaluations, together with
some internal structural information, to efficiently explore the search space,
and eventually to produce the optimal solution. µGP has been devised in
2002
in the
CAD Group at Politecnico di Torino,
and subsequently developed thanks to the effort
of
several
people.
µGP original application was the creation
of
assembly-language programs for
testing different microprocessors,
hence the Greek letter µ (micro) in its name.
Afterward, it has been used on a wider range of problems, such as:
creation of
test programs
for
pre- and
post-silicon validation;
design of
bayesian networks;
creation of
mathematical functions represented as
trees;
integer and
combinatorial optimization;
real-value parameter optimization;
and even creation of
corewar warriors.
Results reported in the scientific literature demonstrate that
it is consistently able to outperform both human experts and conventional
heuristics.
µGP is an
evolutionary algorithm,
hence the GP acronym (genetic programming) in its name.
A population of different solutions
is considered in each step of the search process, and new individuals
are generated through mechanisms that ape both
sexual and
asexual
reproduction. New solutions
inherit
distinctive traits from existing ones, and may
coalesce the good characteristics of different
parents. Better solutions have a greater chance to reproduce and to
succeed in the simulated
struggle for existence.
The current implementation of the toolkit is version 3,
also known as µGP
3, ugp3 (due to typographic limitations)
and MicroGP++ (being written in C++).
The project is kindly hosted on
Sourceforge 2.0, and it
is distributed under the
GNU Public License (GPL).
Comprehensive
instructions and
the updated
documentation can be found online in the
µGP wiki.
For the practitioner, the wiki's
step-by-step tutorials help understanding the gory details
of
configuring the tool,
running it and
tweaking its many parameters.
For the programmer, the wiki explains the
design rationale,
and details the
internal architecture of the toolkit.
