Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Stochastic Hillclimbing as a Baseline Method for Evaluating Genetic Algorithms

Martin Wattenberg and Ari Juels

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-834
September 1994

http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-834.pdf

We investigate the effectiveness of stochastic hillclimbing as a baseline for evaluating the performance of genetic algorithms (GAs) as combinatorial function optimizers. In particular, we address four problems to which GAs have been applied in the literature: the maximum cut problem, Koza's 11-multiplexer problem, MDAP (the Multiprocessor Document Allocation Problem), and the jobshop problem. We demonstrate that simple stochastic hillclimbing methods are able to achieve results comparable or superior to those obtained by the GAs designed to address these four problems. We further illustrate, in the case of the jobshop problem, how insights obtained in the formulation of a stochastic hillclimbing algorithm can lead to improvements in the encoding used by a GA.


BibTeX citation:

@techreport{Wattenberg:CSD-94-834,
    Author = {Wattenberg, Martin and Juels, Ari},
    Title = {Stochastic Hillclimbing as a Baseline Method for Evaluating Genetic Algorithms},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Sep},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5843.html},
    Number = {UCB/CSD-94-834},
    Abstract = {We investigate the effectiveness of stochastic hillclimbing as a baseline for evaluating the performance of genetic algorithms (GAs) as combinatorial function optimizers. In particular, we address four problems to which GAs have been applied in the literature: the maximum cut problem, Koza's 11-multiplexer problem, MDAP (the Multiprocessor Document Allocation Problem), and the jobshop problem. We demonstrate that simple stochastic hillclimbing methods are able to achieve results comparable or superior to those obtained by the GAs designed to address these four problems. We further illustrate, in the case of the jobshop problem, how insights obtained in the formulation of a stochastic hillclimbing algorithm can lead to improvements in the encoding used by a GA.}
}

EndNote citation:

%0 Report
%A Wattenberg, Martin
%A Juels, Ari
%T Stochastic Hillclimbing as a Baseline Method for Evaluating Genetic Algorithms
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-834
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5843.html
%F Wattenberg:CSD-94-834