IlliGAL Blogging

In a recent post I discussed the term competence in connection with GAs. The term is used to refer to well-designed GAs that solve a large class of hard problems quickly, reliably, and accurately. The bottom of line of designing competent GAs to solve problems in the class of problems Herb Simon called nearly decomposable is that you end up with solvers that might be as good as subquadratic, that is, they give good solutions in times that grow no more quickly than a quadratic function of the number of decision variables (in a relaxed PAC sense).

Polynomial time is usually good news and cause for celebration, but if you are solving big ole problems, the square of a large number is darn huge (yes, Virginia, these are technical terms I'm using here). The square of a thousand is a million, which means that you might have to go off and run 1000s of function evaluations in large problems, which may be impractical if your eval is an expensive simulation, computation, or data-crunching task.

Thus, we see a problem with stopping at seeking GAs that are merely competent. Yes, competence takes us from solutions that are worst-case exponential to polynomial (from intractable to tractable), but to go from tractable to practical requires that we pay attention to enhancing the efficiency of effective (competent) GAs.

At IlliGAL we do this with a four-part decomposition of the efficiency problem:

1. Parallelization
2. Time continuation
3. Evaluation relaxation
4. Hybridization

Erick Cantu-Paz's work was our first principled foray into the issue of parallelization. My paper on time continuation set the stage for Ravi Srivastava's thesis and Kumara Sastry's work with me on BB-mutation. Kumara's MS thesis and Laura Albert's thesis set the stage for our current thinking in evaluation relaxation. Work with Siegfried Voessner in 1999 laid down a barebone's framework for thinking about global-local hybrids and was followed up by Abhishek Sinha's MS thesis. Many of these items are cited in the references of The Design of Innovation (Google searchable version here).