REBL
Download
REBL is a
Genetic Algorithm
engine that implements a
stack machine for
executing program strings. It can generate random functions, mutate existing
functions, and track the fitness of functions. Each function can be specified
with one or more inputs and outputs. The library is written in C and suitable
for embedded linux applications.
Departing from traditional genetic algorithm techniques, REBL allows a series
of functions to be interconnected in a network, with changes propagating
through the network to effect more complex functionality. At the same time,
we restict the complexity of fitness functions to something that can be
expressed with a single variable.
Multi-Objective Optimization
The process of searching for a program string that maximizes a single objective
is complex. There are a set of possible instructions combined in any order and
of any length. The search space is potentially infinite, and involves
optimizing many variables.
When multiple, possibly conflicting objectives are introduced, two things
happen. First, the fitness function become horrifically complex. Second, the
goal state is no longer a single point, but a
Pareto frontier.
Simple searching is no longer efficient, or even useful, in some cases. The
solutions to date have tried to solve this problem by making the fitness
functions rank candidates using a Pareto-based ranking scheme.
My inner lazy programmer realizes that writing horrifically complicated fitness
functions is as bad as just writing the program myself. I want something
simple, as simple as counting; however, I do not wish to forsake the
possibilities provided by multiple objectives.
Networked GA
My solution was born out of inspiration from the field of neural networking. No
one neuron is expected to do it all, and internal neurons often perform some
unseen yet important task, as data propagates from one side to the other.
In REBL, each function takes one or more named variables as input, and can
output one or more named variables. When a variable is the output of one
function, and the input of another, a network is formed. A function is run when
one of its input variables changes. Results propagate through the network
toward the ouput side.
Each function should have only one objective. We can train each function
independantly of the others, as each function has its own metric variable.
Complex results can be achieved by chaining together simple functions. This
reduces the programming effort to the equivalent of drawing a block diagram.
Likewise, the fitness functions should be simple.
Help Wanted
Are you a talented open source C programmer, an AI scientist, an ethusiastic
tester, or a technical writer? Join the team. My next steps with this project
are to integrate the lib into a simulation environment, provide examples,
and write better documentation. Email jessedutton at gmail.