Genetic Algorithms are widely used in industry to adapt high quality solutions to difficult non-convex optimization problems. Yet the means by which GAs generate better solutions over time is poorly understood. Despite the existence of many publications which purportedly explain how GAs “work”, no theory of adaptation for GAs has achieved widespread acceptance within the theoretical EC community.
In a sense, we know exactly what GAs ‘do’ (the algorithm after all is open for inspection). This is the same sense in which it can be said that we know what the set of assembly language instructions of a large executable application (e.g. Firefox), will ‘do’. In order to understand why the application exhibits some particular behavior, it is typically necessary to have a description of the behavior of the application in terms of concepts that are more abstract than those associated with assembly language. Similarly, in order to understand how genetic algorithms perform adaptation (i.e. to obtain a theory of adaptation for GAs) I believe that it will be necessary to express the behavior of a GA at a higher level of abstraction than the one at which the algorithm is specified. Chikofsky and Cross write that “reverse engineering is the process of analyzing a subject system to create representations of the system at a higher level of abstraction” [1]. Given this definition, another way of expressing the above is to say that in order to obtain a viable theory of adaptation for GAs it is necessary to reverse-engineer this class of algorithms.
Experimentation is very important to the reverse-engineering process. Information about the high-level description of some system can be gleaned by performing well-conceived experiments and by making inferences based on the results. Well-chosen experiments can also be used to resolve disputes between competing hypothetical high-level descriptions of the system.
It is also very useful to know the abstract constructs that may have been used at each level of abstraction involved in the the forward engineering of the system. In the software domain, reverse engineering is oftentimes an iterative process that produces descriptions of a system at higher and higher levels of abstraction. For instance when reverse engineering the bytecode of some Java application, a first step is to reverse engineer the application to the level of Java code. A subsequent step is to reverse engineer the application to the level of design patterns (e.g. factory, flyweight, façade etc.)
Genetic Algorithms however are not the end-products of human engineering, so unfortunately we have no apriori knowledge about what abstract concepts may be invoked in adaptation-relevant higher-level descriptions of their behavior. Adaptation focused mathematical analyses of genetic algorithms are based on the implicit assumption that concepts within mathematics will prove useful in an adaptation-relevant high-level description of GA behavior. This assumption is reasonable. Mathematics has proven to be an extremely useful framework within which to derive and express useful descriptions of natural systems. Yet, when it comes to the analysis of complex systems like GAs, mathematical approaches may be limited. It is not just that current mathematical techniques might not allow for the derivation of adaptation-relevant high-level mathematical descriptions of GA behavior, but that such descriptions might be best expressed algorithmically (i.e. programmatically) rather than mathematically (i.e. declaratively)
References:
[1] Chikofsky, E.J.; J.H. Cross II (January 1990). “Reverse Engineering and Design Recovery: A Taxonomy in IEEE Software“. IEEE Computer Society: 13–17
