[D] Should We Be Concerned About The Failure Of Evolutionary Algorithms, And Its Implications?
A number of possible explanations for [why we can’t evolve complex software] could be considered. We tried to be as comprehensive as possible in this section, but it is possible that we have not considered some plausible explanations:
Incompetent programmers—It is theoretically possible, but is highly unlikely, that out of thousands of scientists working on evolutionary computation, all failed to correctly implement the Darwinian algorithm.
Nonrepresentative algorithms—Some have suggested that EAs do not accurately capture the theory of evolution, but of course that would imply that the theory itself is not specified in sufficient detail to make falsifiable predictions. If, however, such more detailed specifications are available to GP believers, it is up to them to implement them as computer simulations for testing purposes, but no successful examples of such work are known and the known ones have not been successful in evolving software.
Inadequate fitness functions—Fitness function for a complex software product is difficult to outline and specify and may be as complex (or even more complex) as the software we want to evolve as it has to consider all the possible use cases and pass all unit tests. This may be the Achilles heel of GP, but it is also an objection to feasibility of programming in general and GP in particular, as both have to convert software specification into the source code. If human programmers and biological evolution succeed with such constraints, so should Darwinian simulations.
The Halting problem—Turing proved that it is impossible to determine whether an arbitrary program halts, but this is also a problem for human programmers and could be easily addressed by placing time limits on considered solutions.
Program correctness—If we require evolved software to be provably correct, this would present a problem as GP does not verify produced designs but only tests them against specific unit tests. Likewise, we cannot rely on automated software verification as it is still an unsolved problem in the general case. This is not really a problem as most of the human-written software is never proven to be correct and only a small portion of software engineering process relies of formal specification and Test Driven Development.
Inappropriate solutions—Literature on EA is full of examples of surprising creativity of Darwinian algorithm resulting in solutions which match the letter of design specifications but not the spirit. This is similar to human-produced software and numerous examples of ways in which such software fails the goals of the initial design.
Insufficient complexity of the environment (not enough data, poor fitness functions)—It is possible that the simulated environment is not complex enough to generate high complexity outputs in evolutionary simulations. This does not seem correct as Internet presents a highly complex landscape in which many self-modifying computer viruses roam. Likewise, virtual world such as Second Life and many others present close approximations to the real world and are certainly more complex than early Earth was: A skeptic might insist that an abstract environment would be inadequate for the evolution . . ., believing instead that the virtual environment would need to closely resemble the actual biological environment in which our ancestors evolved. Creating a physically realistic virtual world would require a far greater investment of computational resources than the simulation of a simple toy world or abstract problem domain (whereas evolution had access to a physically realistic real world “for free”). In the limiting case, if complete microphysical accuracy were insisted upon, the computational requirements would balloon to utterly infeasible proportions. Requiring more realistic environmental conditions may result in an increase in necessary computational resources, a problem addressed in the next bullet.
Insufficient resources (compute, memory)—From the history of computer science, we know of many situations (speech recognition, NN training), where we had a correct algorithm but insufficient computational resources to run it to success. It is possible that we simply do not have hardware powerful enough to emulate evolution. We will address this possibility in section “Computational Complexity of Biological Evolution and Available Compute.”
Software design is not amenable to evolutionary methods—Space of software designs may be discrete with no continuous path via incremental fitness to the desired solutions. This is possible, but this implies that original goals of GP are unattainable and misguided. In addition, because a clear mapping exists between solutions to problems and animals as solutions to environmental problems, this would also imply that current explanation for the origin of the species is incorrect.
Darwinian algorithm is incomplete or wrong—Finally, we have to consider the possibility that the inspiration behind evolutionary computation, the Darwinian algorithm itself is wrong or at least partially incomplete. If that was true, computer simulations of such algorithm would fail to produce results comparable with observations we see in nature and a search for an alternative algorithm would need to take place. This would be an extraordinary claim and would require that we discard all the other possible explanations from this list.
We challenge EA community to prove us wrong by producing an experiment, which evolves nontrivial software from scratch and without human help. That would be the only way in which our findings could be shown to be incorrect. Perhaps, reframing the problem in terms of maximizing negentropy of digital organisms, as suggested by Schrödinger, Michaelian, and Ulanowicz and Hannon, with respect to negative energy being a fundamental property of all life-forms may produce better results.
On a positive side, the fact that it seems impossible to evolve complex software implies that we are unlikely to be able to evolve highly sophisticated artificially intelligent agents, which may present significant risk to our safety and security. Just imagine what would have happened, if the very first time we ran a simulation of evolution on a computer, it produced a superintelligent agent. Yampolskiy has shown that programming as a problem is AI-complete; if GP can solve programming that would imply that GP = AGI (artificial general intelligence), but we see no experimental evidence for such claim. In fact, it is more likely that once we have AGI, it could be used to create an intelligent fitness function for GP and so evolve software. Genetic programming will not be the cause of AI, but a product of it. However, neuroevolution methods for optimizing deep learning architectures and parameters remain a strong possibility for creation of AGI.