Genetic Programming
In genetic programming, normal genetic operations of crossover, mutation and reproduction are applied to computer code to create steadily improving and functioning computer code.
PANDOR
PANDOR is both a 7-node network computer system and a
machine language genetic programming system. Given data sets and an evaluation
function the system evolves machine code for the x86 processor using a closely
related virtual machine. This virtual machine, in addition to providing
assembly language operators, also provides instructions for:
- Selection of the data set a
genome selects to evolve upon
- Parameters for the genome's
own evolution (mutation rate, crossover rate, etc.)
- Mappings of subsets of
input and output data
Processors exchange program descriptions between themselves to develop a better overall solution.
How does Genetic Programming differ from AI?
Someone asked how does Genetic Programming differ from
Artificial Intelligence? I am going to assume AI means either heuristic search
based AI (like chess systems) or Expert Systems.
- Both use search processes.
Heuristic AI systems represent their search as changes in configurations
of data. GP searches and changes entire programs or routines. The field of
Genetic Algorithms is related to GP but uses data like AI. In fact a GP
program is just data, only it is data that is interpreted as a program.
- Heuristic search AI and
Expert Systems focus on abstract knowledge, while genetic search methods
use methods inspired from biological genetic operations, and focuses more
on operational sequencing.
- Genetic systems explore
multiple paths simultaneously; each individual in a population is a
potential solution to the problems the environment poses. The population
is the GP system memory. AI systems tend to focus on paths one at a time,
and explore variations in rapid succession.
- Genetic systems combine
information between individuals to create possible new solutions. AI
systems tend to modify single solutions by addition and deletion, not
combination with other solutions.
- AI systems tend to be
deterministic. GP processes have a basic element of randomness.
- Good GP systems test their
potential solutions over multiple environmental conditions. The best
solutions survive and get a chance at improvement.
- GP tends to be an ‘any
time’ algorithm. You can always run it longer, and if you need something
now, you can pick the current best solution and use that until something
better evolves.
- A basic assumption is that
genetic processes worked in nature and thus is worth exploring. Even
though bacteria can take several minutes for a generation, a computer can
simulate a genome in milliseconds, and be combined in clusters to simulate
large populations.
- Genetic processes are
adaptive. Nothing weeds out bad ideas like survival pressure.
- GP is not limited to just
natural genetic processes. AI search and other processes can be used to
change evolved program design. Such changes are viewed as “macro-mutations”
(many mutations that occurred all at once). Such manipulation does not
violate the algorithm, since eventually the GP would discover the genome
on its own (but maybe after a few million generations). They get evaluated
just like any other genome.
- Multiple computers can be
configured to model environments with barriers or varying conditions, and
thus promotes both robustness and solution diversity.
The short answer is: if you can describe how to
solve a problem, then AI, expert systems, and regular programming work just
fine. However, if you do not know how to solve a problem, but you do know how
to recognize good versus bad solutions to the problem, then genetic methods are
worth looking at.
Genetic Programming Links
Genetic Programming Tutorial Gives a basic
overview of the Genetic Programming operations.
Genetic
Programming Inc. John Koza is a pioneer in the field of genetic
programming. Genetic Programming Inc. is currently doing research and
development aimed at producing human-competitive results, with emphasis on the
areas of:
- Automated synthesis of
analog electrical circuits
- Automated synthesis of controllers
- Problems in computational
molecular biology, including metabolic pathways and genetic networks
- Various other problems
involving cellular automata, multi-agent systems, operations research, and
other areas of design
- Using genetic programming
as an automated "invention machine" (for creating new and useful
patentable new inventions)
He is the author of numerous patents and books, plus he has a 1000 node cluster. His really is bigger!
Genetic
Programming ORG has general information on conferences, references
and the field in general.
AIM Learning Technologies by Bazhalf and Peter Nordin utilize the similar operations on the machine language level with a 100x speed-up.
An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming by Bazhalf and Nordin evolve real-time obstacle avoiding behavior from sensorial data on a running robot.
An Evolutionary Architecture for a Humanoid Robot (PDF) by Bazhalf and Nordin gives an overview of their plans to expand to a humanoid robot.
Evolving Hand-Eye Coordination for a Humanoid Robot with
Machine Code Genetic Programming by W.
B. Langdon and Nordin.
Genetic Programming Bibliography index page by W. B. Langdon contains a list of authors and their genetic programming papers.
Other Genetic-Inspired Projects
Geneobyte
CAM-Brain developed for Advanced Telecommunications Reasearch (ATR)
in Kyoto, Japan to support Hugo de Garis. Evolves FPGA
designs based on a neural network model. de Garis’ original funding organization STARLAB
went bankrupt, so he now has a Professorship at Utah State University, USA. He
also offers a Ph.D. level course in "brain building," and offers
source code to his evolving network simulator.
Evolutionary Electronics Web Links lists
projects around the world interested in developing evolving hardware systems.
EvoWeb Homepage is an online info service for evolutionary computing.