MicroGP

µGP (MicroGP)

µGP original application was the creation of assembly-language programs for testing different microprocessors, hence the Greek letter µ (micro) in its name. It routinely handles problems that require solutions in the form of full-fledged assembly programs, including functions, interrupt handlers and data. But it has also 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.

µGP is an evolutionary algorithm, hence the GP acronym (genetic programming) in its name. Different candidate solutions are considered in each step of the search process, and the process mimics some principles of the Neo-Darwinian paradigm, such as variation, inheritance, and selection. 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.

Given a task, µGP first fosters a set of random solutions, then iteratively refines and enhance them. µGP's heuristic algorithm uses the result of the evaluations, together with other internal information, to efficiently explore the search space, and eventually to produce the optimal solution. Thus, the user is not required to set out possible improvements, but simply to evaluate the candidate solutions proposed by the toolkit.

Candidate solutions are internally encoded as directed multigraphs (i.e., with multiple edges between the same pair of nodes). During the search process, multigraphs are constrained by a user-defined set of rules to conform to sensible structures. Each node encode a specific macro defined in the constraints file. Macro parameters are stored in the graph either as tags (post-it notes) or additional edges. Individuals are transformed to text files according to user-defined rules, and fed to a user-defined evaluation program. As noted before, the user is only required to describe the appearance of the solutions to his problem, and to provide a program able to evaluate them (i.e., to assign a numeric value to each candidate solution expressing its goodness). Thus, no knowledge about the problem being solved is included in µGP itself.

µGP was specifically designed to create realistic assembly code and to support all assembly peculiarities, such as various conditional branches, different addressing modes, and instruction asymmetries. When the constraints are correctly defined, µGP generated programs take advantage of complex syntactic structures, such as global and local variables, subroutines and interrupts.

The following figure shows a fragment of assembly language represented as a graph of 5 nodes. Each macro represents a single instruction.

During the evolution, one or more instructions can be added; one or more instructions may be removed; the operands of certain instructions can be modified. New programs may also be obtained by mixing, in different ways, existing ones. The multigraph representation helps ensuring that the result of the crossover is still a sensible program, resembling to both parents and, thus, inheriting potentially good characteristics from both of them.

Additionally, µGP presents some features that may be considered of interest for an evolutionary computation scholar:

• Possibility to smoothly shape the behavior from pure steady-state to pure generational, including several degrees of elitism

• Variable genetic operators' ''strength''

• Variable population's size and offspring's size

• Self adaptation of: operator strength, operator activation probability, tournament size, population size and number of applied operators (offspring size)

• Multiple fitness values, either priority-based or multi-objective

• Diversity protection, trough the concept of ''population entropy''

• Fitness holes

• Clone detection, with optional scaling or extermination

• Multiple populations, including migrations

• Support for dynamic fitness functions

• Support for parallel fitness evaluation