“Case Studies in Evolutionary Experimentation and Computation”, 2000-06-09 (; similar):
14 examples prove the potency of the evolution strategy. The exemplary compilation starts with the drag-minimization of a wing-like construction in a wind tunnel and ends with the creation of an extraordinary magic square on a computer.
Prerequisite for a successful evolutionary optimization is the validity of strong (or at least piecemeal strong) causality for the quality function. The problem solution fails without any inherent order of the quality function. Euler’s extension of Fermat’s last theorem cannot be disproved with an evolutionary algorithm, because the design of a piecemeal causal payoff function is not in sight.
[Keywords: evolutionary algorithms (GA, ES, EP), noisy fitness data, design out fear, optimization under noise, convergence improvement techniques, self-adaptation]
…Conclusion: Disciples of evolutionary algorithms could criticize that the above examples (except the Euler-problem) are too simple. I am frequently asked whether a problem solved with an evolutionary algorithm could not be solved faster with a deterministic method. The information science distinguishes between tractable and not tractable problems. A problem which can be solved with an evolutionary algorithm belongs to the class of tractable problems. And the more intensively we deal with such a problem, the more skillfully we can make the strategy. Herdy3 has shown that Rubik’s cube having 6×6 elements on each side can be arranged with the ES. Nobody can buy such a cube today. But if a 6×6-cube would be for sale, a strategist would surely design a method to arrange the cube much faster than the ES will do.
We look now to the world of hard problems (NP-hardness, NP-complete). There is no hope to solve the Hamiltonian path problem in polynomial expected time applying an evolutionary algorithm. No ‘deterministic’ strategy including the ES will do this. Certainly this is not a new statement. However, we may hope that an evolutionary algorithm, unable to solve the problem exactly, nevertheless finds a good solution. And we may further hope that this is done faster as if we work grimly to design the deterministic strategy which fits the special problem.