TOOLBOXBROWSE TOPICS
RESOURCESABOUT THIS SITEpmwiki.org |
Genetic Algorithms & Genetic Programming(a subtopic of Machine Learning)
"[G]enetic algorithms are based on a biological metaphor: They view learning as a competition among a population of evolving candidate problem solutions. A 'fitness' function evaluates each solution to decide whether it will contribute to the next generation of solutions. Then, through operations analogous to gene transfer in sexual reproduction, the algorithm creates a new population of candidate solutions." Now consider the following situations:
Each of these is a variation of the Traveling Salesperson Problem (TSP) which has become a classic genetic algorithm (GA) benchmark. The optimal solution will be the fittest individual of the final generation, being the product of many cycles of selection, reproduction, and even mutation. And keep in mind that GA solutions are not necessarily the very best ones. However, they can be quite useful as you'll discover when you explore the resources offered below. Good Places to StartJohn Koza Has Built An Invention Machine - Its creations earn patents, outperform humans, and will soon fly to space. All it needs now is a few worthy challenges. By Jonathon Keats. Popular Science (April 19, 2006). "Now 62 and an adjunct professor at Stanford University, [John] Koza is the inventor of genetic programming, a revolutionary approach to artificial intelligence (AI) capable of solving complex engineering problems with virtually no human guidance. Koza’s 1,000 networked computers don’t just follow a preordained routine. They create, growing new and unexpected designs out of the most basic code. They are computers that innovate, that find solutions not only equal to but better than the best work of expert humans. His 'invention machine,' as he likes to call it, has even earned a U.S. patent for developing a system to make factories more efficient, one of the first intellectual-property protections ever granted to a nonhuman designer. Yet as impressive as these creations may be, none are half as significant as the machine’s method: Darwinian evolution, the process of natural selection. ... What Koza has done is to automate the creative process. ... Koza’s thesis adviser at the University of Michigan was John Holland, the man widely regarded as the father of genetic algorithms." Genetic Programming. By John R. Koza, Consulting Professor, Stanford University. This entry in the Encyclopedia of Computer Science and Technology (1997) is available in several formats from CiteSeer.IST.
What is Genetic Programming? An excellent introductory tutorial with lots of helpful animations. From Genetic Programming Inc.
Evolutionary Computation. An AI Bite by Simon Colton. Sponsored by, and available from, The Society for the Study of Artificial Intelligence and Simulation of Behaviour. "Wouldn’t it be great if we could evolve a program to do the task rather than writing one ourselves? If we did this, we would be practicing the fascinating art of evolutionary computation. As evolutionary methods can be used to produce programs that we couldn’t write ourselves in a million years, they have a lot of appeal." Scientific American Frontiers with Alan Alda: Robot Independence segment from the Life's Really Big Questions television broadcast (December 19, 2000). "Natural selection is at work in the artificial world, as robots learn to reproduce without us." Evolutionary Design - Computers can provide design variations that no human would have imagined. A six minute video from the Technology Review Video Collection (September 2006). Guest: Eric Bonabeau. The Art of the Possible - Can Eric Bonabeau's Hunch Engine expand your mind? By Wade Roush. Technology Revew (September 25, 2006). "According to the company's publicity materials, the Hunch Engine is software that uses evolutionary algorithms to breed solutions to science, engineering, business, or design problems--solutions that no human mind could have predicted. Icosystem claims that evolutionary algorithms expose ideas to a kind of natural selection, allowing users to 'reach beyond the limits of their imagination.' But the notion that serendipity might produce better results than thinking and planning left me suspicious. That was before I heard about the French letter carriers. ... The astonishing thing, says [Eric] Bonabeau, is that 'the mailmen never say why they like this route or that one.' Bonabeau believes that programs based on the Hunch Engine can help people with a particular class of problems: the kind where they have a hard time expressing exactly what they want, but they know a solution when they see it. Bonabeau is careful to emphasize that evolutionary algorithms are nothing new. Computer scientists have been experimenting with them since the 1980s, and Icosystem has been selling industrial design tools based on them for several years. One tool, for example, helps pharmaceutical researchers breed biological molecules that are likely to interact favorably with receptors in the body. What's new is the use of evolutionary algorithms in programs that laypeople might use to invent things."
Unnatural Selection - Machines using genetic algorithms are better than humans at designing other machines. By Sam Williams. Technology Review (February 2005). "So why not automate trial and error? Antenna design, [Jason] Lohn believes, is one of many engineering problems that could best be solved by evolutionary algorithms, an emerging class of software that produces lots of different designs, rejecting the less fit in order to select the most functional. The resulting designs often seem a little inhuman --- inelegant and uncanny. Evolutionary algorithms, also known as genetic algorithms or GAs, take their cue from biological evolution, which can turn a crawling reptile into a soaring bird without any kind of forward-looking blueprint. In sexual reproduction, the shuffling of each parent’s genes --- combined with random genetic mutation --- creates organisms with new characteristics, and the less fit organisms tend not to pass on their genes to succeeding generations. Evolutionary algorithms work much the same way, but inside a computer. ... Reproducing in microseconds on a computer a process that takes millions of years in nature is an idea that long predates the ability to realize it. John H. Holland, a 76-year-old computer science professor at the University of Michigan, says he first came up with the notion while browsing through the Michigan math library’s open stacks in the early 1950s." #demo1" id="demo1A Demonstration of the Genetic Algorithm. From David Eck, Department of Mathematics and Computer Science, Hobart and William Smith Colleges. "'GA' is a little applet that demonstrates the genetic algorithm, in which methods analogous to the process of natural evolution are applied to solve problems on a computer. This 'artificial evolution' uses reproduction, mutation, and genetic recombination to 'evolve' a solution to a problem."
A Brief Introduction To Genetic Algorithms. By Moshe Sipper, Department of Computer Science, Ben-Gurion University. "The idea of applying the biological principle of natural evolution to artificial systems, introduced more than three decades ago, has seen impressive growth in the past few years. Usually grouped under the term evolutionary algorithms or evolutionary computation, we find the domains of genetic algorithms, evolution strategies, evolutionary programming, and genetic programming." Accelerating Problem Solving. Listen to this presentation about evolutionary machine learning by David Fogel, CEO of Natural Selection, delivered at the Accelerating Change 2005 conference, and made available by IT Conversations: "Experiments in artificial intelligence have focused traditionally on replicating human behaviors in software. Although this approach has achieved some notable successes, including the Deep Blue chess machine that defeated Garry Kasparov in May, 1997, they are limited to addressing problems for which people already have the answers. An alternative approach, using computational intelligence methods such as evolutionary computing, can provide a computer with the ability to learn how to solve complex problems without relying on human expertise. According to Fogel, what works best is the synergistic effect obtained by combining simulated evolutionary learning with human learning. As an example of this latter approach he tells the story of Blondie24, a checkers program supplied with only minimal information that was able to reach high levels of expertise thanks to the application of genetic algorithms. Fogel looks at other real-world applications in industry, medicine, and defense, as well as speculating on the future capabilities offered by these combined learning mechanisms." The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ). Jörg Heitkötter and David Beasley, eds. (2000). Questions include What's a Genetic Algorithm (GA)? and What's Genetic Programming (GP)? Programming with Primordial Ooze. By W. Wayt Gibbs. Scientific American, October 1996. Available from Genetic Programming Inc. Genetic Algorithm Optimizer. From the Artificial Intelligence Lab at the University of Arizona. Marshall Ramsey's introductory demo allows you to view the graphical version of the genetic algorithm described in the text. Readings OnlineGenetic Algorithms - Survival of the Fittest: Natural Selection with Windows Forms. By Brian Connolly. MSDN Magazine (August 2004). "An evolutionary algorithm solves a problem by first generating a large number of random problem solvers (programs). Each problem solver is executed and rated according to a fitness metric defined by the developer. In the same way that evolution in nature results from natural selection, an evolutionary algorithm selects the best problem solvers in each generation and breeds them.Genetic programming and genetic algorithms are two different evolutionary algorithms. Genetic algorithms involve encoded strings that represent particular problem solutions. These encoded strings are run through a simulator and the best strings are mixed to form a new generation. Genetic programming, the subject of this article, follows a different approach. Instead of encoding a representation of a solution, GP breeds executable computer programs. ... The abstract problem I'll deal with is to develop an intelligent strategy to be used by a simple artificial ant." Using Genetic Programming To Evolve Soccer Teams. By Vicente Carlos de Alencar Jr. and Diego Silva Dias. Gamasutra(September 25 2007). "Sometimes, there is not a known optimal strategy that can be used to solve a given problem. In these cases, instead of trying to optimize a fixed strategy that we don’t even know whether it will bring good results or not, would be desirable if we could search for it using the computer and that is exactly the aim of genetic programming, which is an evolutionary technique based on Darwinian concepts of natural selection. We have decided to use a genetic programming approach to develop the artificial intelligence of a 2D soccer team because, as we know, a 'winning strategy' for these games hasn’t been found yet. In our genetic programming approach we’ve generated a 'population' of teams. Our goal was to develop a decision tree to each one of the team’s players." Breeding Race Cars to Win. By Michelle Delio. Wired News (June 18, 2004). "A technology that allows robots to rebuild themselves and computer programs to evolve and become better on their own is now being used to breed super-fast Formula One race cars. ... The breeding was done solely with computer-generated simulations using genetic algorithms -- programs that combine Mother Nature's laws and computer science to mimic the natural process of evolution. Using this sort of programmed procreation, the Digital Biology Interest Group [at University College London] has made self-healing battlefield surveillance robots -- gadgets that look like robotic snakes that can figure out how to wiggle home even when severely damaged, unlike less-evolved robots that typically just give up when one of their critical components goes out of commission." Darwin in a Box - Are you ready for computers that speed up the process of evolution and teach themselves to think? By Steven Johnson. Discover Magazine (August 2003; Vol. 24 No. 8). "This little film won't win an Oscar for Best Animated Short, but the software that generated it stands as a small miracle of computer programming. The figure was not taught how to walk by an offscreen animator; it evolved the capacity for walking on its own. The intelligence to do so came from some clever programming that tries to mimic nature's ability to pass along successful genes. The idea is called a genetic algorithm. It creates a random population of potential solutions, then tests each one for success, selecting the best of the batch to pass on their 'genes' to the next generation, including slight mutations to introduce variation. The process is repeated until the program evolves a workable solution. Originally developed in the 1960s by John Holland at the University of Michigan, genetic algorithms are increasingly being harnessed for real-world tasks such as designing more efficient refrigerators." Don’t invent, evolve - The inventor’s trial-and-error approach can be automated by software that mimics natural selection. Economist.com (October 3, 2007). "Evolutionary design, as it is known, allows a computer to run through tens of millions of variations on an invention until it hits on the best solution to a problem. As its name suggests, evolutionary design borrows its ideas from biology. It takes a basic blueprint and mutates it in a bid to improve it without human input. As in biology, most mutations are worse than the original. But a few are better, and these are used to create the next generation. ... What has changed, in this as in so much else, is the availability and cheapness of computing power. According to John Koza of Stanford University, who is one of the pioneers of the field, evolutionary designs that would have taken many months to run on PCs are now feasible in days. The result is that the range of applications to which the principles of evolutionary design are being applied is growing fast. ... Perhaps the most cunning use of an evolutionary algorithm, though, is by Dr Koza himself. His team at Stanford developed a Wi-Fi antenna for a client...." Bookish Math - Statistical tests are unraveling knotty literary mysteries. By Erica Klarreich. Science News (December 20, 2003; Vol. 164, No. 25). "Stylometry ['the science of measuring literary style'] is now entering a golden era. In the past 15 years, researchers have developed an arsenal of mathematical tools, from statistical tests to artificial intelligence techniques, for use in determining authorship. ... For decades, computers have supported the work of experts in stylometry. Now, computers are becoming experts in their own right, as some researchers apply artificial intelligence techniques to the question of authorship. ... A couple of years later, Holmes and Richard Forsyth of the University of Luton in England used the Federalist Papers to test another artificial intelligence technique. They applied genetic algorithms, which use Darwinian principles of natural selection. The idea is to create a set of rules for determining authorship and then let the most useful, or fit, rules survive." An Introduction to Genetic Algorithms In Java. By Michael Lacy. Java Developer's Journal (Vol. 6, Issue 3; March 1, 2001). "In the January issue of JDJ (Vol. 6, issue 1) I introduced a technique born in the AI community that uses concepts from biological natural selection to solve complex and often highly nonlinear optimization problems encountered in computer science - the genetic algorithm. I examined the building blocks of genetic algorithms and why java is well suited to their implementation. This month I'll discuss the details of a simple genetic algorithm implementation in the hopes that your curiosity will be sparked to pursue further investigation." Evolutionary algorithms now surpass human designers. By Paul Marks. New Scientist (July 28, 2007; Issue 2614: pages 26 -27). "Charles Darwin's theory of evolution has been the source of much controversy since its publication in 1859, most recently involving the intelligent design (ID) lobby in the US. Now the theory is fuelling another debate, although for once the battle lines have nothing to do with religion.Instead of pitting God against science, the emerging spat centres on evolutionary algorithms (EAs), which mimic the processes of natural selection and random mutation by 'breeding', selecting and re-breeding possible designs to produce the fittest ones. ... [Hod] Lipson and other members of the US Association for Computing Machinery's Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) worry that if they can't persuade their fellow engineers to use EAs, then evolved machines, systems and software that work fantastically well risk being lost. ... 'We can now undertake evolutionary problems that were previously too complicated or time-consuming,' says John Koza, a computer scientist and EA pioneer from Stanford University in California. 'Things we couldn't have done in the past, because it would have taken two months to run the genetic program, are now possible in days or less.'" Man Against Machine: Computer-generated method outperforms human-designed program for fingerprint improvement. NSF Discoveries (September 1, 2005). "'Genetic algorithms' are created when computers evaluate and improve a population of possible solutions to a problem in a stepwise fashion. The new program evolves by letting good solutions produce offspring as bad solutions die out. Over time, the individual solutions in the population become better and better, producing a final, best solution. The method uses terms derived from biology, such as generation, inheritance and mutation, to describe the particular program manipulation the computer uses at each step of improvement, hence the name genetic algorithm. A program used to compress fingerprint images--images that may prove guilt or innocence--must not introduce distortion that limits its usefulness. ... [Uli] Grasemann and [Risto] Miikkulainen applied genetic algorithms to solve the fingerprint compression puzzle in work supported by the National Science Foundation's Computer and Information Science and Engineering directorate. They provided their computer with the basic programming instructions needed to compress graphic images and then waited for a better algorithm to be born. The progress of the evolving program was tested at each generation. After 50 generations, the genetic algorithm consistently outperformed the human-derived WSQ." Artificial beings evolve realistically. By Kimberly Patch. Technology Research News (June 4/11, 2003). "For the past couple hundred years, scientists have studied genetics using organisms like peas, fruit flies and viruses, whose lifespans are much shorter than ours. In the past decade or so, computer scientists have worked with genetic algorithms, which can produce many generations much more quickly and can track each change more closely than is possible using real organisms. But these virtual organisms evolve much more simply than the real thing. Researchers from Michigan State University, the California Institute of Technology and the University of California at Los Angeles have found a way to use software to more closely mimic the way real organisms evolve, and have used the model to uncover a long-standing secret of natural selection. ... The method could also improve genetic algorithms, which are modeled after evolution. ... One problem with genetic algorithms is that they can get too complicated before they reach a solution. The addition of natural selection weeds out organisms that are too fragile to self-replicate, which reduces the complexity." Evolutionary learning in mobile robot navigation. By Cory Quammen. ACM Crossroads Student Magazine, 8.2 (Winter 2001). "Evolutionary algorithms have been implemented to solve problems in robot navigation. In particular, EAs have been used to get a robot to learn how to adapt to its limited capabilities. Using GP in this way is termed evolutionary learning." A Theory of Evolution, for Robots. By Lakshmi Sandhana. Wired News (September 5, 2002). "If you can't program a robot to fly, then program it so it will figure out how to fly without your help. Krister Wolff and Peter Nordin, two scientists at the Chalmers University of Technology in Sweden, have designed a winged robot capable of learning flight techniques. ... Scientists still do not fully understand the mechanics of insect flight, especially those aspects controlling balance and motion. As recently as a couple of years ago, what was known about the bumblebee indicated it should not be able to fly. And yet it does. An elegant way around the lack of understanding could be to just give up on understanding altogether and let the machines learn for themselves. Genetic programming is one way to approach this complex problem. Using this technique, Wolff and Nordin evaluated the instructions that were best at producing liftoff. Successful ones were paired up, and "offspring" sets of instructions were generated by swapping instructions randomly between successful pairs. These next-generation instructions were then sent to the robot and evaluated before breeding a new generation." How to Make Software Agents Do the Right Thing: An Introduction to Reinforcement Learning. By Satinder Singh, Peter Norvig, and David Cohn, Adaptive Systems Group, Harlequin Inc. (1996). Sidebar - Genetic Algorithms:"The field of Genetic Algorithms (GA) addresses the same set of problems as RL, but with a different methodology. Instead of learning a utility function, Genetic Algorithms learn the policy directly, representing it as an encoded bit string (or, in Genetic Programming, as a program in some computer language). The approach is to search the space of policies by generating a pool of policies and evaluating each one for a sequence of time steps in a simulated environment. A new pool of policies is constructed by combining the more successful existing policies, along with some random change. The algorithm iterates until a sufficiently good policy is found.The name 'Genetic Algorithms' comes from an analogy with biology: the bits representing a policy are like the bases in a strand of DNA, the creation of new policies is like the process of sexual reproduction, the random change is like mutation, and the propagation of successful policies is like natural selection." NASA Evolutionary Software Automatically Designs Antenna. Press release (June 15, 2004) available from SpaceRef. "NASA artificial intelligence (AI) software - working on a network of personal computers - has designed a satellite antenna scheduled to orbit Earth in 2005. The antenna, able to fit into a one-inch space (2.5 by 2.5 centimeters), can receive commands and send data to Earth from the Space Technology 5 (ST5) satellites. ... NASA scientists have spent two years developing the evolutionary AI software that designed the antenna. 'The AI software examined millions of potential antenna designs before settling on a final one,' said project lead Jason Lohn, a scientist at NASA's Ames Research Center, located in California's Silicon Valley. 'Through a process patterned after Darwin's 'survival of the fittest,' the strongest designs survive and the less capable do not.' The software started with random antenna designs and through the evolutionary process, refined them. The computer system took about 10 hours to complete the initial antenna design process. ... 'Not only can the software work fast, but it can adapt existing designs quickly to meet changing mission requirements,' he said. ... Scientists also can use the evolutionary AI software to invent and create new structures, computer chips and even machines, according to Lohn. ... 'The software also may invent designs that no human designer would ever think of,' Lohn asserted."
Software that Writes Software. By Alexis Willihnganz. Salon.com, August 10, 1999. "And maybe with GP-evolved artificial intelligence, future robots won't just be playing soccer with humans, but teaching their human peers new tricks." Related Web SitesACM Special Interest Group on Genetic and Evolutionary Computation (SIGEVO), formerly the International Society for Genetic and Evolutionary Computation (ISGEC).
EvoCAD, Evolution-Assisted Design, from the DEMO [Dynamical & Evolutionary Machine Organization] site at the Department of Computer Science, Volen National Center for Complex Systems, Brandeis University. "We have built a mini-CAD system to design 2D Lego structures. This application allows the user to manipulate Lego structures, and test their gravitational resistance using a simplified structural simulator. It also interfaces to an evolutionary algorithm that combines user-defined goals with simulation to evolve candidate solutions for the design problems. The results of evolution are sent back to the CAD front-end to allow for further re-design until a satisfactory solution is obtained." And the best part is that you can actually try this program online! EvoWeb, the website of EvoNet, the European Network of Excellence in Evolutionary Computing. "EvoNet aims to foster innovation, training and technology transfer, and to provide a comprehensive information service for everyone interested in the field of evolutionary computing." A Fast TSP solver Using A Genetic Algorithm. In this TSP demo, you can place the cities on the map! From The University of Texas at Arlington's Department of Computer Science and Engineering.
GA Archives. "The Genetic Algorithms Archive is a repository for information related to research in genetic algorithms and other forms of evolutionary computation. Available from this site are past issues of the GA-List digest, source code for many GA implementations, and announcements about GA-related conferences. Also, links are given to many interesting sites around the World with material related to evolutionary computation. This archive is maintained by Alan C. Schultz at The Navy Center for Applied Research in Artificial Intelligence." GECCO, the Genetic and Evolutionary Computation Conference:
Genetic Algorithm Research at AIAI, the Artificial Intelligence Applications Institute at the University of Edinburgh's School of Informatics. "Applications of genetic algorithms include timetabling, scheduling, and adapting models of complex systems to fit new data. Recent work has shown that search control knowledge that controls planning strategy can be learned using genetic algorithm techniques." GenJam. From Al Biles. "GenJam (short for Genetic Jammer) is an interactive genetic algorithm that learns to play jazz solos. It may well be the only evolutionary algorithm that is a 'working musician.'" Be sure to follow his links to the magazine articles about this cool program.
Genetic Programming Inc. - "a source of information about the field of genetic programming and the field of genetic and evolutionary computation." IEEE Transactions on Evolutionary Computation, published by the IEEE Computational Intelligence Society. Aims & Scope: "Papers on application, design, and theory of evolutionary computation, with emphasis given to engineering systems and scientific applications. Evolutionary optimization, machine learning, intelligent systems design, image processing and machine vision, pattern recognition, evolutionary neurocomputing, evolutionary fuzzy systems, applications in biomedicine and biochemistry, robotics and control, mathematical modelling, civil, chemical, aeronautical, and industrial engineering applications." IlliGAL: The Illinois Genetic Algorithms Laboratory. "[W]e study nature's search algorithm of choice, genetics and evolution, as a practical approach to solving difficult problems on a computer." Important Genetic Algorithm Information Sites from the Los Alamos Genetic Algorithms Niche. Maintained by Hillol Kargupta. "NaturalMotion's Active Character Technology (A.C.T.) is based on Oxford University's research on the control of human and animal body motions. In essence, we build a physical, biomechanically-realistic model of a character (e.g. a human or a dinosaur), implant an appropriate brain structure (usually a neural network), and use optimisation techniques (such as artificial evolution) to create the desired behaviour."
Solving Traveling Salesman Problems. From the School of Industrial and Systems Engineering at Georgia Tech. A delightful site with a wonderful Pictorial History of the TSP.
Related AI Topics Pages
More ReadingsBerman, Phyllis. Rocket Science, Applied. Forbes Magazine (December 27, 1999). "Picture an office with ten technicians to make a hundred service calls on Tuesday. How many ways are there to parcel out the assignments? Without even debating what order a given technician ought to make his house calls in, you find that the number of combinations is rather large--a googol. All the PCs Dell ever made, put to work side by side, would have a tough time crunching so many combinations. Some creativity is in order. PointServe uses genetic algorithms to find optimal, or near-optimal, solutions to scheduling problems. In this exotic approach to programming, you let a computer try out random variations in code and then keep the "fittest" formulas." Carlson, Shawn. Algorithm of the Gods. Scientific American (March 1997). Hedberg, Sara Reese. Evolutionary Computing: The Rise of Electronic Breeding. IEEE Intelligent Systems 20(6): 12 - 15 (November / December 2005). "Genetic algorithms and their relations, which fall under the umbrella term evolutionary computing, are being harnessed to optimize designs of all sorts. Genetic programs have duplicated many patented designs; and in January 2005, the US Patent Office granted the first patent to a genetically designed controller." Koza, John R., Martin A. Keane and Matthew J. Streeter. Evolving Inventions. Scientific American (February 2003). "Computer programs that function via Darwinian evolution are creating inventions that are novel and useful enough to be patented. - Evolution is an immensely powerful creative process. From the intricate biochemistry of individual cells to the elaborate structure of the human brain, it has produced wonders of unimaginable complexity. Evolution achieves these feats with a few simple processes--mutation, sexual recombination and natural selection--which it iterates for many generations. Now computer programmers are harnessing software versions of these same processes to achieve machine intelligence. Called genetic programming, this technique has designed computer programs and electronic circuits that perform specified functions." |
