IlliGAL Blogging

At IlliGAL, we use the term competence to refer to principled procedures that solve a large category of hard problems quickly, reliably, and accurately. By principled, we mean that there exists theory that gives us reason to believe that the procedure will work and scale well over the whole class, but we stop short of requiring a convergence proof (see my burning GAs and toaster convergence rant) and accept dimensional arguments bolstered by facetwise or other simplified models. The quick, reliable, and accurate part is quite similar to the usual requirements of PAC learning. We want polynomial time performance, that is probably approximately close to being accurate. For hard problems we look for boundedly difficult problems along dimensions of difficulty that challenge our procedure. This is a game theoretic argument. If we understand the dimensions of problem difficulty, and we can solve problems on some farout boundaries of those dimension in a sufficiently quick, reliable, and accurate fashion, we should be able to solve easier problems as fast or faster as those on the edge of our design envelope. The end result are procedures that scale nicely (subquadratically as problem size grows) whereby GA parameters can be set in a principled manner to give reliable and accurate solutions.