About This Blog
Automating Invention is Robert Plotkin's blog on the impact of computer-automated inventing on the future of invention and patent law.
- Artificial Invention
- Design & Engineering
- Evolutionary Computation
- Genie in the Machine
- History of Computing
- Human Creativity
- Intellectual Property Law
- Philosophy of Computing
- Software Patents
- Technology Industry
- Using Genetic Programming to Repair Software
- Using Genetic Algorithms to Blend a Diesel-Gasoline Cocktail
- Evolving Efficient Transistors for Future Computers
- Meet Me at GECCO 2009
- GA Gaming Coming to the App Store
- Your Desktop Supercomputer
- A New Evolutionary Computing Platform
- Algorithms which Automate Creativity
- AI and Future Enterprise
- Combating Common Diseases with Large-Scale Sequencing Technology
- Genetic Alogrithms on a Cellphone
- GECCO-2009 Car Racing Competition
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- February 2008
- June 2006
- May 2006
- February 2006
- January 2006
- December 2005
- November 2005
- October 2005
- September 2005
- August 2005
- July 2005
- June 2005
November 29, 2009
Using Genetic Programming to Repair Software
Automatic program repair has long been a goal in the software industry. Finding and fixing bugs is currently a manual operation that represents a major portion of the software development life cycle. Now a team of researchers from the University of New Mexico and the University of Virginia have developed an automated method for fixing software bugs. Using off-the-shelf legacy C programs for demonstration purposes, genetic algorithms are used to evolve code variants until a solution is found that both retains the intended functionality and avoids the previously detected error. According to team member Westley Weimer, the methodology has been demonstrated as capable of repairing 20 programs consisting of over 200,000 lines of code in less than 200 seconds on average.
November 2, 2009
Using Genetic Algorithms to Blend a Diesel-Gasoline Cocktail
An engine research team at the University of Wisconsin-Madison is using genetic algorithms as part of an investigation into the possibility of creating an engine that could be programmed to use both diesel and gasoline fuels, harvesting the best properties of each fuel by blending them on the fly. This technique, described as "fast-response fuel blend," would program the fuel injection system of an engine to produce the optimal mix of diesel and gasoline fuels based on a real-time analysis of operating conditions. The team, led by Professor Rolf Reitz, is creating computer models and simulations that use genetic algorithms to determine the best variables for engine performance. Tests have already shown that such an engine would produce significantly lower levels of polluting emissions and provide 20% greater fuel efficiency.
July 25, 2009
Evolving Efficient Transistors for Future Computers
Researchers in the Intelligent Systems Group at the University of York, England, hope to use evolutionary concepts to overcome problems in the manufacturing of computer chips of the future. As transistor components continue to decrease in size at the nanometer level, variations in manufacturing that naturally occur can seriously impact chip performance. The York researchers have used evolutionary algorithms to determine candidate transistor circuit designs that will perform well despite natural variations. The algorithms help narrow down thousands of possible design candidates to a more manageable set. The smaller set of candidate designs are then run through a computer simulator that tests performance. Read the full article in the IEEE Spectrum.
July 6, 2009
Meet Me at GECCO 2009
As I previously mentioned, I will be giving a talk at the 2009 Genetic and Evolutionary Computation Conference (GECCO) in Montreal on July 10.
If you will be at the conference to give a presentation on work that you have done to further computer-automated inventing, please contact me directly so that I can attend your talk and meet with you in person. I will be blogging the conference live and would love to provide coverage of the latest advances in invention automation.
June 29, 2009
GA Gaming Coming to the App Store
Genetic algorithms (GA) have entered into the video game arena with Firemint's new highly anticipated Real Racing simulator, soon to be launched for the iPhone. Rather than using the traditional hardcoded method where drivers in the game are programmed to get better and better, Real Racing uses GAs to simulate more life-like opponents.
"What is great about genetic algorithms (GA) is that they produce AI that is much smarter, but also more human like," explains Firemint CEO Rob Murray. "What isn't so good (as we have discovered) is that just like good human players, they misbehave and find exploits."
Examples of these exploits include driving on the grass at high speeds and entering curves without braking and then bouncing off the racetrack walls. Firemint has had to address these issues, just as real race officials often have to reign in real race drivers. The fine tuning required for Real Racer's GA has led to a delay in its release, but there is the promise of a heightened gaming experience.
June 27, 2009
Your Desktop Supercomputer
In a recent blog post, Nick Jones forecasts a time in the not-too-distant future when home computers will have acquired the processing power and memory capacity of today's supercomputers. Jones ponders the question of what people will do with all that computing power. While some have suggested that the future of home computing lies in massive computer centers which home users will connect to, Jones doesn't think network technology will be advanced enough to support the resulting huge increase in data transmissions. Instead, he thinks today's PC will be beefed up to supercomputer levels.
Jones suggests that home supercomputers could make use of genetic algorithms (GA). He suggests that a variant of GA known as genetic programming (GP) could be used to evolve programs which solve problems. To put it simply, a home supercomputer would take a fitness function which determines what defines the best program to solve a problem and then use GP to 'breed' various solution programs until the best match was found.
Jones suggests that companies that have an interest in personal computers, including Intel and Microsoft, should start investing in the development of GA and GP tools for the mass market.
June 23, 2009
A New Evolutionary Computing Platform
A group of researchers at the Madrid Polytechnic University (UPM) are developing an evolutionary computing platform which will optimize the search for solutions to complex scientific and engineering problems. The researchers have devised a methodology known as MOS which intelligently combines different evolutionary algorithms and uses the best solution from each. The evolutionary models used by MOS include genetic algorithms, estimation distribution algorithms, and techniques of differential evolution.
The evolutionary computing platform will produce results which are applicable to many fields, including molecular chemistry, materials resistance, robotics and games theory.
June 13, 2009
Algorithms which Automate Creativity
In the Journal of Genetic Progamming and Evolvable Machines, a paper entitled Incorporating characteristics of human creativity into an evolutionary art algorithm examines computer-generated art and design software which uses an evolutionary approach. This software usually relies on human intervention to select the 'best' of two variants and determine the makeup of the next generation. The paper's authors, Steve DiPaola and Liane Gabora, discuss ways in which the software can incorporate this human intervention into its algorithms, automating one more step of human creativity.
June 11, 2009
AI and Future Enterprise
In Future Enterprise - the Intelligent Enterprise Revolution, futurist David Tow discusses the state of artificial intelligence in relation to e-commerce and global competitiveness. Tow lists the most promising AI trends as evolutionary or genetic algorithms, bayesian networks, fuzzy logic, swarm intelligence, neural networks, and intelligent agents.
Tow cites four major trends which are now emerging in relation to AI and the intelligent enterprise revolution:
1. AI is being used more frequently in e-commerce to achieve higher quality decision outcomes.
2. AI is moving up the decision chain to strategic and senior management levels.
3. AI techniques are being linked and used in more powerful combinations.
4. AI is beginning to leverage web intelligence from social networks, search services, and semantic applications.
See his article for more details and for his predictions on future trends. There is also an interesting analysis of Tow's ideas on the Genetic Argonaut.
May 9, 2009
Combating Common Diseases with Large-Scale Sequencing Technology
Uppsala University in Sweden, home to the UPPMAX Center for Advanced Computational Science, is expanding operations to provide biomedical researchers with large-scale sequencing technology. This technology can be used for studies on the impact of the genome on common disease. For example, the DNA modifications in a cancer cell can be catalogued by the new technology and used to help identify which gene mutations increase the risk of common diseases including cancer, diabetes, obesity and autoimmune-related diseases. UPPMAX has received funding to obtain three of the new technology sequencing machines.
May 3, 2009
Genetic Alogrithms on a Cellphone
Christian Perone has recorded a video of a genetic algorithm running on a cellphone. The algorithm solves the Traveling Salesman problem. His blog tracks his work in writing a complete genetic algorithm framework using Python. Perone promises to post the source code soon.
May 1, 2009
GECCO-2009 Car Racing Competition
The second contest of the GECCO-2009 Car Racing competition officially started on March 25. The competition is a software-simulated race between virtual cars. The second contest is designed to simulate the time before a race when mechanics and drivers optimize the car for performance. The goal of the contest is to build an evolutionary algorithm that can replace the team of humans and find the best car setup (e.g., gear ratio, wing area and angle, spring setup) on a given track.
The submission deadline for the contest is July 1, 2009. Results of the contest will be announced at the Genetic and Engineering Computation Conference (GECCO-2009) held July 8-12 in Montreal, Canada. This is the largest conference in the field of genetic and evolutionary computation.
Read an ealier post about last year's competition here.
April 23, 2009
Genetic Programming and Medical Applications
The blog for the Journal of Genetic Programming and Evolvable Machines (GPEMjournal) reports on the growing use of genetic and evolutionary programming in the area of medical applications. Since publishing a special GPEMjournal, "Medical Applications of Genetic and Evolutionary Computation" in December of 2007, the journal has continued to published related work. Some of the medical applications reported on include using genetic programming to aid in medical diagnoses. The journal encourages researchers to contact them with more information about similar applications.
April 17, 2009
Richard Feynman and Simulated Evolution
The Genetic Argonaut blog describes how author Daniel Hill spent some time with Richard Feynman working on a program which simulated evolution. Hill was later dismayed to discover that their findings had already been published by Motoo Kimura. Feynman on the other hand was elated by the realization that their "amateur" discoveries had been verified. Read more about it here.
April 15, 2009
Evoletronica: Survival of the Funkiest
The blog for the Journal of Genetic Programming and Evolvable Machines (GPEMjournal) reports on a new website which uses genetic programming and human fitness assessment to 'breed electronic music.' The Evolectronica website streams loops of audio which are voted on by site visitors. Loops which receive the most votes 'reproduce' and 'baby loops' are created. The website is also something of a social community, with members posting their comments and competing for the Hall of Fame. It takes a little work to get set up to listen to audio, but once you do you will be fascinated by the evolving sounds.
April 13, 2009
"Not Your Grandmother's Genetic Algorithm"
On the website for the Illinois Genetic Algorithms Laboratory (IlliGAL) at the University of Illinois at Urbana-Champaign, Professor David Goldberg has posted Not Your Grandmother's Genetic Algorithm, the slideshow he presented at HollandFest 09. Goldberg is director of the IlliGAL and a leader in the GA field. The slideshow follows the journey from simple GAs to the design of competent GAs which break the billion-variable optimization barrier.
April 9, 2009
The Power of the Simple Genetic Algorithm
In his Genetic Argonaut blog, Marcelo de Brito found himself asking the following question after examining a book on evolutionary computation: why, despite advances in evolutionary-based algorithms, is the most used algorithm the original Simple Genetic Algorithm (SGA) from the 1970s? De Brito attributes the success of the SGA to the heuristic knowledge its users have since embedded in it. Read a related post here.
April 7, 2009
Honoring a Genetic Algorithm Pioneer
The Genetic Argonaut blog describes a three-day event called HollandFest 09 which was held this February in Singapore to commemorate the contributions of Professor John Holland to the fields of evolutionary computation and genetic algorithms. Holland, a renowned professor in Psychology and Electrical Engineering & Computer Science at the University of Michigan, is the originator of Genetic Algorithms and one of the seminal architects of what is now known as Complexity Theory. This year marks both Holland's 80th birthday and the 200th anniversary of Charles Darwin's birth.
March 23, 2009
Charles Darwin and Robots
Many tributes have been paid to Charles Darwin this year in honor of the double anniversaries of his 200th birthday and 150 years since the publication of On the Origin of Species. On the website Robots.net, Darwin's influence on the field of robotics is examined. The development of bipedal walking and flapping wing mechanisms used evolutionary techniques, as did neural networks which allow robots to learn simple behaviors. See the article for more details on these and other innovations in robotics which are attributable to Darwin's theories.
March 17, 2009
The Legacy of Darwin
February 12 marked the 200th anniversary of Charles Darwin's birth. In an article in the Columbus Dispatch, several research scientists are profiled whose work carries on the tenets originally put forth by Darwin. One of them is John Holland, professor of psychology, electrical engineering, and computer science at the University of Michigan. Holland was among the first researchers to write computer programs that use genetic algorithms to mimic evolution. His current research is in the area of linguistics. According to Holland, "I'm working with linguists on the origin and evolution of language. Older linguists think language is wired in. The new group believes language is adaptive and very social."
See the Columbus Dispatch online for the complete article.
March 15, 2009
The Evolutionary Art of Theo Jansen
Theo Jansen is a Dutch artist and kinetic sculptor who creates animated works of art that resemble living organisms. Jansen's vision is to use inorganic materials in an attempt at "redoing the Creation." He works with light materials like plastic bottles, sheets and tubing; the animation is powered by wind. Jansen's works are a melding of art and engineering. Computer calculations which use genetic algorithms to simulate evolution are behind the designs of his sculptures. Since 1990, Jansen's 'animals' have developed through a series of evolved models. He's made the plans for his designs public and invites anyone to duplicate his creations.
Theo Jansen's sculptures really must be seen to be believed. Jansen and his work were recently featured in a European auto commercial, which you can see here. A longer documentary film is available here.
March 13, 2009
Darwin and Digital Technology
This year marks the 200th anniversary of the birth of Charles Darwin, prompting reflection on the profound impact of his work. Darwin's legacy is being re-examined in light of developments in the world of digital technology, especially computing and robotics. Genetic algorithms, which replicate the process of natural selection, are used for computer-based problem solving and design. Several popular video games, including Spore and Creatures, are modeled on biological reproduction and evolution. In the field of robotics, neural networks are being developed to control all aspects of robot behavior.
March 11, 2009
Darwin's Influence on New Technologies
The Houston Chronicle used the occasion of the 200th anniversary of Charles Darwin's birth to examine some new technologies whose development can be attributed to Darwin's theories. In the field of law enforcement, DNA identification techniques have had tremendous impact on forensic science and criminal justice. In the field of medicine, scientists have come to understand that evolution can cause bacteria and viruses to mutate over time, with antibiotics and vaccines becoming ineffective as a result. In computer science, genetic algorithms use the model of natural selection to evolve solutions in areas such as air traffic control and weather forecasting.
See the article for an example of how a company called Maxygen used genetic algorithms to design a new household detergent.
March 7, 2009
Evolved Transforms and Image Compression
Image compression is a key task performed by image processing software. The most widely used compression schemes, such as wavelet transforms, usually introduce a loss of information while reducing the number of bits required for image representation. A new approach which uses evolutionary computation (EC) circumvents the problem of data loss.
A team of computer scientists from the University of Alaska Anchorage and Wright-Patterson Air Force Base in Ohio are using EC's fitness-based selection and genetics-inspired operators to evolve solutions for image compression optimization. Working since 2004, Frank Moore, Brendan Babb, Michael Peterson, and Gary Lamont have found that EC can outperform wavelets for compression tasks. Ongoing research is underway on the optimization of satellite images. Future applications could include radio frequency signal compression and noise reduction in medical imaging.
February 19, 2009
CIG 2008 Car Racing Competition
The CIG 2008 Car Racing competition was a software-simulated race between virtual cars, organized by Swiss researcher Julian Togelius, and Daniele Loiacono and Pier Luca Lanzi of the Politecnico di Milano. Details of the race were presented at the IEEE Symposium on Computational Intelligence and Games held in December 2008 in Perth, Australia. The cars were powered by controllers based on a variety of architectures, including neural nets, genetic algorithms and evolution strategies.
The car race was enabled by TORCS, an open source race car simulator written in C++. TORCS provides multiple versions of cars, tracks, and controllers, and the ability to develop custom controllers. TORCS is supported by an active community of users and developers. The competition patch for TORCS was written by Daniele Loiacono.
February 17, 2009
The RoboTuna Project
MIT's RoboTuna is an engineering project which models the swimming dynamics of a bluefin tuna. Designing RoboTuna has been challenging due to the difficulty of analyzing and then emulating the complex movement of the fish at it swims through its liquid environment. A genetic algorithm is one of the tools used to search through data and determine optimal parameters to control movement of the robot.
RoboTuna is a long term project, originated in 1993 as a doctoral thesis. The overall goal of the project is to use a biological model to develop advanced propulsion systems for underwater vehicles. For more information on RoboTuna, including pictures and videos, see the MIT RoboTuna website.
February 13, 2009
Adrian Thompson is a scientist on the faculty at the University of Sussex who specializes in "Evolutionary Electronics", which is the use of genetic algorithms in the design of electronic system. Thompson calls this type design of evolutionary because it resembles natural selection, with "selection acting repeatedly upon heritable variation." He has researched the idea of self-designing circuits which could be used to build neural network chips.
February 5, 2009
"Survival of the Fittest" Marketing
A software program which uses a genetic algorithm to develop consumer product marketing? That's the concept behind IDDEA (Interactive Discovery and Design by Evolutionary Algorithm), an innovative system owned by a Massachusetts-based company called Affinnova. Developed in the 1990s by two M.I.T. engineers, the software has been used to help dozens of companies create marketing strategies, including Proctor & Gamble, Wal-Mart and Capital One.
Businessweek.com describes how Affinnova worked with office supply superstore Staples to create a paper product marketing strategy.
February 2, 2009
Students Use Genetic Algorithms for Airplane Engine Design
A team of high school students in Burlington, Vermont is experimenting with genetic algorithms to help create a fuel-efficient design for a two-engine jet airplane. The design is part of the Real World Design Challenge, which allows high school students to work on real-world engineering projects in a team environment.
The genetic algorithms are part of a sophisticated software package which was donated to the team. Genetic algorithms use test iterations to evolve a design to its optimal state. "We're going to experiment", says Mike Gaffney, a 17-year old member of the team. "If we get lucky, it works."
January 31, 2009
Recreating the Mona Lisa
Swedish programmer Roger Alsing has published an example of genetic programming which evolves a set of randomly placed polygons into an image of the Mona Lisa. Alsing's algorithm starts with the set of random polygons on a black background, then iteratively tests and adjusts them against a final image. After about a million iterations, the polygons are rearranged to resemble the final image. There is some controversy as to whether this can be called genetic programming, or represents a variation of known procedures such as the hillclimbing algorithm. In any case, the results are impressive.
January 29, 2009
Thinking, Self-Developing Robots
Brainstorm, heralded as the world's first "complete cognitive software system for robots", has been announced by the Institute of Robotics (iRobis) in Scandinavia. Brainstorm is capable of generating control programs for any robot on which it is installed. Built upon a methodology called "genetic programming" (GP) which enables robots to be turned into self-developing, adaptive, problem-solving machines, Brainstorm is the first commercially available system of its type. The next step for iRobis is working with early commercial adopters and researchers to develop prototypes which use Brainstorm.
December 23, 2005
History of Evolutionary Computation
Genetic Argonaut has posted the first posting in a series on the history of evolutionary computation, which says that the initial idea for evolutionary computation was inspired by a science fiction story called "Insel Der Krebse" (The Crab Island or The Island of the Crabs) by Anatolij Dnjeprow.
The article gives two examples that are particularly relevant to artificial inventing, dating back to the 1960s:
- Ingo Rechenberg and Hans-Paul Schwefel's use of a simple evolution strategy to find the most aerodynamic shape for six plane planks linked by five adjustable hinges; and
- Hans-Paul Schwefel's use of evolutionary computation to optimize a supersonic two-phase flashing nozzle.
Check out the posting for more details and photographs.
September 22, 2005
Evolutionary computation provides perspective on "intelligent design"
Lee Spector wrote a nice piece in the Boston Globe explaining in layperson's terms how evolutionary computation (EC) works, and pointing out how EC can be useful for enabling people to "appreciate the power of selection operating on random variation when it is stripped of its emotion-laden connections to human origins and is shown to be capable of designing complex solutions to difficult problems."
Of most relevance to this site, Prof. Spector describes how the quantum computing circuits that his software has evolved are not only difficult for humans in general to understand or design, "they are extremely difficult for me to understand or design, and I could never have produced the results on my own. I am not a designer equal to that task, but evolution is."
Evolving clearer fingerprints
The National Science Foundation (NSF) reports on the use of a genetic algorithm to evolve a computer program for compressing digital images of fingerprints. The resulting program consistently outperforms the current world-standard program for fingerprint image compression, WSQ, developed by the FBI and others in the 1990s.
Images showing the improvement of successive generations of the genetic algorithm can be found at the link above.
August 23, 2005
A few practical applications of genetic algorithms
IlliGAL Blogging has several recent postings on real-world applications of genetic algorithms:
July 28, 2005
Genetic algorithms optimize complex pipe design
Australian firm Optimatics reports that it has used genetic algorithms to help more than 80 major clients in Australia, the U.S., Canada, and Britain optimize the design of pipes for providing water through cities, towns, and new urban developments. Optimatics claims that its optimization techniques can produce solutions up to 20 percent less expensively than traditional engineering.
Evolutionary computation improves automobile design
NuTech Solutions has issued a press release describing how its ClearVu Engineering technology has been used to solve multidisciplinary optimization problems in car safety applications. Thomas Baeck gave an impressive presentation at GECCO this year describing NuTech's work with a German auto manufacturer to increase the speed and decrease the cost of design without comprising crash safety.
July 22, 2005
Overcoming the software bottleneck
Hardware has always improved more quickly than our ability to write software for it. Although you might think that this "software crisis," as evidenced by increasingly buggy, bloated, and insecure software, is a recent phenomenon, the term "software crisis" was used at least as early as 1972. I remember reading about it in Fred Brooks' classic The Mythical Man Month, first published in 1975.
Is this a job for genetic programming or some other automated programming technique? I don't know the answer, but when a technological "crisis" has lasted for 30+ years with no signs of abating, anything is worth a try.
July 12, 2005
Artificial inventions in science fiction
IlliGAL Blogging links to worldchanging's coverage of a science fiction novel in which the protagonist has "patented using genetic algorithms to patent everything they can permutate from an initial description of a problem domain – not just a better mousetrap, but the set of all possible better mousetraps. Roughly a third of his inventions are legal, a third are illegal, and the remainder are legal but will become illegal as soon as the legislatosaurus wakes up, smells the coffee, and panics." I don't know how prominently these inventions figure in the novel, but it looks like an interesting read, and it captures quite nicely an issue that the law needs to address soon.