Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
ucin1006054556.pdf (2.81 MB)
ETD Abstract Container
Abstract Header
Why and How to Report Distributions of Optima in Experiments on Heuristic Algorithms
Author Info
Fitton, N V
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006054556
Abstract Details
Year and Degree
2001, MS, University of Cincinnati, Engineering : Computer Science.
Abstract
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.
Committee
Dr. Carla Purdy (Advisor)
Pages
63 p.
Keywords
design of experiments
;
experimental methodology
;
heuristic algorithms
;
probabilistic algorithms
;
optimization
;
sample size
;
statistics
;
VLSI circuit partitioning
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
ucin1006054556
Download Count:
575
Copyright Info
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.
Release 3.2.12