The application of stochastic heuristic, like tabu search or simulated annealing, to address hard discrete optimization problems has been an important advance for efficiently obtaining good solutions in a reasonable amount of computing time. A challenge when applying such heuristics is assessing when a particular set of parameter values yields better performance compared to other such sets of parameter values. For example, it can be difficult to determine the optimal mix of memory types to incorporate into tabu search. This in turn prompts users to undertake a trial and error phase to determine the best combination of parameter settings for the problem under study. Moreover, for a given problem instance, one set of heuristic parameter settings may yield a better solution than another set of parameters, for a given initial solution. However, the performance of this heuristic on this instance for a single heuristic execution is not sufficient to assert that the first set of parameter settings will always produce superior results than the second set of parameters, for all initial solutions. This paper looks at three known statistical procedures (one of which is a basic statistical test procedure and two of which were developed for discrete event simulation (discrete) optimization) to assess and compare the computational performance of tabu search for MAX 3-SATISFIABILITY. The statistical procedures designed for application within the domain of discrete event simulation output analysis (a paired difference t-test and two multiple comparison procedures developed and studied by Nelson and others) are adapted for this new purpose. An empirical case study is reported by computationally studying MAX 3-SATISFIABILITY instances across 32 variations of tabu search.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Publisher Info
Article provided by Elsevier in its journal Omega.
Volume (Year): 37 (2009) Issue (Month): 3 (June) Pages: 522-534 Download reference. The following formats are available: HTML
(with abstract),
plain text
(with abstract),
BibTeX,
RIS (EndNote, RefMan, ProCite),
ReDIF