Stochastic Hillclimbing as a Baseline Mathod for Evaluating Genetic Algorithms

Ari Juels, Martin WattenbergNeurIPS 1995 · OpenReview

TL;DR

This paper argues that simple stochastic hillclimbing (SH) algorithms can serve as a surprisingly strong baseline for evaluating the performance of more complex genetic algorithms (GAs). The authors demonstrate that SH can achieve comparable or even superior results on challenging combinatorial optimization problems like the 11-multiplexer and jobshop scheduling, suggesting that GAs might not always offer a significant advantage and that insights from SH can inform better GA design.

What Problem Does This Paper Address?

Genetic algorithms (GAs) are widely promoted as powerful, general-purpose heuristics for solving complex combinatorial optimization problems, often requiring minimal problem-specific knowledge. However, the effectiveness of GAs compared to simpler, more direct optimization methods is not always rigorously established. This paper addresses this gap by proposing stochastic hillclimbing (SH) as a baseline for evaluating GA performance. The authors investigate whether GAs truly offer a significant advantage over SH on specific, well-studied problems where GAs have been applied, and explore how understanding SH can lead to improved GA designs.

Methods

The core of the paper is a comparative study of stochastic hillclimbing (SH) and genetic algorithms (GAs) on two distinct combinatorial optimization problems: Koza's 11-multiplexer problem and the jobshop scheduling problem.

  • Stochastic Hillclimbing (SH): The SH algorithm explores a discrete search space by iteratively moving to an adjacent state with a better fitness. The "neighborhood" and the method of choosing the next state are tailored to the specific problem's structure. For the 11-multiplexer, SH operates on S-expressions (tree-like structures representing programs) by randomly replacing nodes. For the jobshop problem, SH uses an ordering of markers to construct a schedule, with neighbors generated by moving a marker to a new position.
  • Genetic Algorithms (GAs): The paper references existing GA implementations for these problems, including Koza's Genetic Programming approach for the 11-multiplexer and Fang et al.'s GA for jobshop scheduling. These GAs employ standard evolutionary operators like crossover and mutation, adapted to the problem's representation.
  • Novel GA Formulation: For the jobshop problem, the authors also propose a new GA encoding that is inspired by their SH algorithm's representation, aiming to leverage insights gained from the simpler method.

The performance metric used is the fitness of the best solution found after a fixed number of function evaluations, a common practice in GA research.

Datasets

The paper evaluates the algorithms on two established benchmark problems:

  • Koza's 11-multiplexer problem: This is a boolean function synthesis problem where the goal is to generate a program (represented as an S-expression) that correctly maps 11 inputs to an output based on a specific logic. The problem has 2048 possible inputs.
  • Jobshop Scheduling Problem: This is an NP-complete problem involving scheduling a set of jobs, each with a sequence of tasks, on a set of machines to minimize the overall completion time (makespan). The paper uses standard benchmark instances: 6x6, 10x10, and 20x5 (jobs x machines).

Key Insights and Ideas

  • SH as a Powerful Baseline: The most striking insight is that simple stochastic hillclimbing algorithms can achieve performance comparable to, or even superior than, sophisticated GAs on these problems. This challenges the assumption that GAs are inherently superior for complex combinatorial optimization.
  • No Strict Local Minima for SH: For the 11-multiplexer problem, the SH algorithm's neighborhood structure is designed such that there are no strict local minima. This is a property of boolean formulas in general and contributes to SH's effectiveness.
  • Insights from SH Inform GA Design: The paper demonstrates that understanding the mechanics and representation of an SH algorithm can lead to improvements in GA design. Specifically, for the jobshop problem, a new GA encoding inspired by the SH algorithm's representation yielded better results.
  • Representation Matters: The success of both SH and the improved GA highlights the critical role of problem representation in optimization. The paper shows that carefully chosen representations, even for simpler algorithms, can be highly effective.

Key Results

  • 11-Multiplexer: The SH algorithm found correct programs significantly faster (in terms of function evaluations) than the GA reported by Koza. For example, after 40,000 function evaluations, SH achieved a 98% success rate, compared to the GA's 28%. At 80,000 evaluations, SH reached 100% success, while the GA was at 90%.
  • Jobshop Scheduling:
    • Standard Jobshop: The SH algorithm generally outperformed the GA from Fang et al. on the 10x10 and 20x5 instances, achieving better average makespans and often better "best known" solutions.
  • New GA: The newly formulated GA, inspired by the SH algorithm's encoding, further improved upon the existing GA and even matched or surpassed the SH algorithm on the 10x10 instance, demonstrating the value of SH-inspired design.

Limitations and Future Work

  • Limited Problem Scope: The study focuses on only two specific combinatorial problems. The authors acknowledge that the effectiveness of SH as a baseline might vary across different problem domains.
  • "Best Known" vs. Average Performance: While the paper presents "best known" results for comparison, the primary focus is on average performance after a fixed number of evaluations. The paper notes that for the jobshop problem, the GA results from Fang et al. do not clearly distinguish between average and "best" runs.
  • Future Work: The authors encourage designers of black-box algorithms to experiment with stochastic hillclimbing in the early stages of algorithm development to establish effective baselines and gain insights for GA design. They also suggest further exploration of SH's properties and its application to other combinatorial problems.

Summary updated

Abstract

We investigate the effectiveness of stochastic hillclimbing as a baseline for evaluating the performance of genetic algorithms (GAs) as combinato(cid:173) rial function optimizers. In particular, we address two problems to which GAs have been applied in the literature: Koza's ll-multiplexer problem and the jobshop problem. We demonstrate that simple stochastic hill(cid:173) climbing methods are able to achieve results comparable or superior to those obtained by the GAs designed to address these two problems. We further illustrate, in the case of the jobshop problem, how insights ob(cid:173) tained in the formulation of a stochastic hillclimbing algorithm can lead to improvements in the encoding used by a GA.
BibTeX
@inproceedings{juels1995stochastic,
  author = {Ari Juels and Martin Wattenberg},
  title = {{Stochastic Hillclimbing as a Baseline Mathod for Evaluating Genetic Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=SJ49qP-_ZH},
}
Figure