RSA Laboratories

Topics in Black-Box Combinatorial Optimization

Ari Juels

Citation: Topics in Black-box Combinatorial Function Optimization, U.C. Berkeley Ph.D. Thesis Dissertation, 1996.

Abstract: This thesis explores the performance of a class of general optimization heuristics, known as black-box optimization algorithms, on a range of problems possessing a high degree of combinatorial structure. We first explore the performance of one of the most elementary of these algorithms, known as hillclimbing or randomized greedy, on the minimum bisection problem. We prove that a simple hillclimbing algorithm solves a range of problem instances drawn from Jerrum and Sorkin's $G_$ random graph model. We demonstrate an extremely broad range of effectiveness experimentally. We prove a weak lower bound on the number of local minima in the search space for the problem instances under investigation, and conduct an extensive experimental exploration of these local minima. Finally, we prove a result for hillclimbing on the maximum cut problem analogous to that for minimum bisection.

We then investigate the performance of hillclimbing relative to a class of global optimization algorithms known as genetic algorithms (GAs). We consider a range of published combinatorial optimization problems: these include the maximum cut and jobshop scheduling problems, a problem known as the multiprocessor document allocation problem, and a genetic programming task involving the discovery of an 11-multiplexer program. We show that simple hillclimbing algorithms can outperform GAs on problem instances for which the GAs were specifically designed in the literature. By modifying the structure of the search space for the jobshop problem, however, we are able to make a genetic algorithm more effective in turn than hillclimbing.

Finally, we propose an intuitively appealing, mathematical abstraction of the GAs known as the equilibrium genetic algorithm (EGA). The simplicity of this algorithm enables us to prove its ability to find the optimum of a simple, non-linear problem, which we call $MAX_$, in polynomial time. We also show experimentally that the EGA is competitive with a conventional GA on the jobshop scheduling problem.

Full Publication List