Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Why and How to Report Distributions of Optima in Experiments on Heuristic Algorithms

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Science.
The goal of this thesis is to make good science easier to do by promoting and facilitating the comparison of algorithms. Algorithms for solving difficult problems, and in particular heuristic algorithms for intractable problems, often do not lend themselves to standard methods of theoretical analysis: thus a researcher must make an empirical, statistical argument for or against an algorithm's quality. This thesis discusses the design and evaluation of experiments in this sometimes slippery area of study. We contend that a contribution to science requires more than the reporting of an algorithm's optimal results: researchers should choose sample sizes rationally; they should then report, at minimum, both the distribution of results overall and the distribution of a set of optimal values, which may involve further sampling to reach desired goals; they should account for sampling itself by including confidence intervals for their claims; and if they compare results of different algorithms, then their comparisons should be statistically sound and rigorous. We offer an experimental procedure with guidelines for each of these steps, and within the procedure, we offer a new method for sampling and comparing sets of optimal values, which we call k% optima. We also present a demonstration experiment in which we apply our procedure to report and compare the performance of three heuristic algorithms for VLSI circuit partitioning.
Dr. Carla Purdy (Advisor)
63 p.

Recommended Citations

Citations

  • Fitton, N. V. (2001). Why and How to Report Distributions of Optima in Experiments on Heuristic Algorithms [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006054556

    APA Style (7th edition)

  • Fitton, N. Why and How to Report Distributions of Optima in Experiments on Heuristic Algorithms. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006054556.

    MLA Style (8th edition)

  • Fitton, N. "Why and How to Report Distributions of Optima in Experiments on Heuristic Algorithms." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006054556

    Chicago Manual of Style (17th edition)