WORST-CASE INSTANCES AND LOWER BOUNDS VIA GENETIC ALGORITHMS

摘要

We explore a novel application of Genetic Algorithms, viz., as an empirical method in two sub-areas of the Analysis of Algorithms. First, Approximation Algorithms provide tractable solutions to NP-Complete problems while sacrificing solution quality. Second, Online Algorithms are designed for the case in which the problem instance does not arrive in its totality, as in Offline Algorithms, but arrives piece by piece, over the course of the computation. Generating worst-case instances for either algorithm type, for use both as test cases and in lower-bound proofs, is often non-trivial. We use GAs to find worst-case instances of several NP-Complete problems, including the Traveling Salesman Problem, and of Online problems, including versions of the Taxicab Problem. These worst-case instances give us lower bounds on the competitiveness of the approximation algorithms used. For example, they provide empirical results suggesting that the greedy algorithm, in the worst case, does better on planar graphs than on arbitrary graphs. In addition, they demonstrate that 6.93 is a lower bound on the competitiveness of the "hedging" algorithm for the Hard Planar Taxicab Problem. This experimental result has theoretical implications for the study of the problem, i.e., that further research to prove an upper bound of 7 may be warranted.