“Mom and dad jet engine can get together and have baby jet engines. You find the ones that work better, mate them, and just keep going.”
David Goldberg, professor of engineering at the University of Illinois
The theory of evolution represents one of the most significant breakthroughs in the history of science since its introduction by Charles Darwin in the 19th century. It is no surprise that it affected not just the development of biology but numerous other scientific and industrial fields such as engineering and computer science.
In fact, it has provided a source of inspiration for algorithm designers since the early emergence of computers. However, only recent advancements in computational resources, robotics and rapid prototyping (i.e. 3D printing) have established the so-called field of “Evolutionary Computation” as a relevant subfield of applied Artificial Intelligence. In this article, we briefly explain the fundamental workings of evolutionary algorithms and compare natural with artificial evolution. We highlight successful industrial and scientific applications and finally give an outlook on future developments.
Evolution states that organisms arise and develop through the natural selection of small, inherited variations that increase each individual’s ability to compete, survive and reproduce. This phenomenon is also referred to as survival of the fittest. The process of evolution can be described by three elementary components:
1.) Heredity: Traits can be passed from generation to generation.
2.) Variation: Traits vary among individuals with respect to their morphology, physiology and behavior. Variation is caused from random mutations in the genome.
3.) Selection: Different traits result in different rates of survival and reproduction
In both cases traits are controlled by some sort of genome. It contains all the necessary information that define the characteristics of an individual. The difference is that a biological genome consists of DNA pairs, whereas the software equivalent is simply a sequence of numbers.
For instance, we could describe a car by its structure, weight, velocity and so on and gather these properties in a numeric string. The mapping of the physical object to an “artificial genome” is an important step, because it enables us to apply the evolutionary operators heredity, variation and selection that we described earlier.
Let’s illustrate this with a well-known example from computer science: “The Travelling Salesman Problem”. A salesman has to visit a number of places in one tour and return to its origin by following the shortest possible route. Even though this sounds like a simple task, it is very hard to solve due to the enormous number of different trips. Traditional problem solvers cannot guarantee to come up with a solution in an acceptable time.
However, there are more efficient approaches, for example algorithms that make use of evolutionary techniques in order to “breed” solutions instead of computing them. We demonstrate their working with a simple step-by-step instruction:
First, we create an initial population of individuals where each individual represents a possible route between cities. You can view the permutation of cities as the individual’s “genes” and the route length as its fitness. In the next step, we can use this fitness value to select the best members of the initial population to be the “parents” of the next generation. During the mating process, the offspring is generated by combining and mutating the parent trades. In this example, we perform the mutation by randomly swapping two cities in a route with low probability.
The resulting population has a higher chance of containing good individuals because it combines the best characteristics of the previous generation. We can repeat this process until we finally end up with a population that contains very good solutions — perhaps even the best possible solution.
This is quite remarkable, as the underlying technology has no understanding of the problem itself. It requires no insights into the factors that determine the quality of a solution, a simple fitness measurement is enough.
It is no surprise that evolutionary computation has proven to be a powerful method for solving complex, poorly understood problems in countless real-world applications. In the following, we briefly present a few examples from the scientific and technical domain where the application of evolution has shown great advantages over traditional design and optimization methods.
NASA used an evolutionary approach to find an optimized antenna design for its Space Technology 5 mission. The traditional practice of solving this task manually is very time and labor intensive and requires expert knowledge. The evolutionary algorithm generated and tested thousands of different structures, among them many examples that engineers would normally not come up with. The resulting design turned out to be highly effective and was deployed to the final spacecraft in March 2006, making it the world’s first artificially-evolved object to fly in space. NASA thereby benefitted from reduced development costs and faster design cycles due to the algorithm’s ability to quickly respond to changing requirements.
This video illustrates the evolving of virtual creatures through an evolutionary algorithm that designs a controller for muscle movement. The creatures find different gaits based on target speed and gravity and even deal with external distractions as well as difficult terrains. While it is almost impossible to handcraft a controller that is able to produce the required movements, the evolutionary algorithm creates remarkable results after several hundreds of generations. It is an impressive demonstration of the adaptiveness to changing environments.
Natural evolution was discovered and described in the 19th century. About a hundred years later, with the invention of the computer, we observed the transition of evolutionary processes from wetware to software that enabled the development of powerful problem solvers. With the technological advancements of the 21st century such as rapid prototyping and material science, we may observe another transition: From software to decentralized, evolvable hardware, leading to the “Evolution of Things”. This would be a major breakthrough in the sense that hardware (i.e. in the form of autonomous robots) could create and develop itself and adapt to changing environments and requirements without a human in the loop. It would enable to build completely new products that replace the traditional design-and-ship approach by a design-ship-adapt circle where evolution plays a central role.
Think of robots that work in hazardous, changing environments. Instead of developing the final robot design, one can build a “basic” evolutionary robot, deploy it and let it fine-tune itself to the final job!
Our team at Unetiq builds applications using the latest advancements in AI — such as evolutionary algorithms — to automate design processes and to optimize products. Contact us now and learn more on how to use the power of evolution in your projects!
