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.