MicroGP (codenamed ugp3) is an evolutionary approach to the generation of Turing-complete programs.
The resulting generated programs are realistic assembly programs tweaked for a target
microprocessor: they take full advantage of the assembly syntax, exploiting the
different addressing modes and instruction set asymmetries.
Despite its generality, μGP has some distinctive features that allow its use
in specific contexts, such as test program generation.
The application is composed of three separated modules: the evolutionary core, the constraints and an external evaluator.
Our earliest attempt to evolve test programs was presented in [date01]. The approach relied on a library of sharp fragments of code, called macros. The optimal sequence of macros was heuristically determined, and then a genetic algorithm optimized their parameters. The approach is quite effective, but hardly scalable. An Intel i8051, a very simple microprocessor, required 213 macros; and the macro list was carefully compiled by an experienced engineer in two working days.
The embryonic idea of the μGP was presented in [cec02]. The paper described a GP-like framework for generating assembly language program with simple instructions tightly connected with a directed acyclic graph. It implemented a straightforward (μ+λ) evolution, with no recombination, nor other enhancements. Remarkably, the overall structure resembled the linear graph GP, developed independently, and concurrently. Shortly after, the naïve approach was used in [ats02] for validating a microprocessor design, and provided effective results with moderate effort by human experts.
Afterwards, the μGP was slightly improved, adding recombination and auto-adaptation. At the same time, the evaluation procedure was expanded and the correlation with hardware strengthened. The enhanced methodology was used on different problems and the results of [date01] were easily outperformed. Paraphrasing Samuel, the μGP was eventually able to do what was needed to be done, without being told exactly how to do it ("Some Studies in Machine Learning Using the Game of Checkers", IBM Journal of Research and Development, 1959). This is true at least in the very specialized context of microprocessor validation.
In 2003, the whole µGP was rewritten from scratch. The latest prototype is in (almost) ANSI C and consists of about 6,500 lines on 29 files. It has the ability to exploit single instructions, complex macros, or their combination. Individual representation has been completely disconnected from assembly specification. The number of different nodes has been reduced, and their expressiveness increased. The directed acyclic graph representation has been transformed to handle generic directed cyclic graphs. A new abstraction level has been added, enabling support for subroutines and software interrupts.
Currently, a new version of the program is being rewritten in ANSI C++ to simplify versioning and improve code reusability.
You may find a list of related papers on this page.
You can download the latest unsupported and mostly undocumented beta version of μGP from sourceforge.net
Other resources:
