Back to search

University of Southampton

Parameter optimisation for search heuristics via a barrier tree Markov model

Abstract

dc:description.abstract

<p>The quality of solution provided by a search heuristic on a particular problem is by no means an absolute value. Most heuristics are controlled by a set of parameters, upon which the performance is heavily dependent. We construct Markov models for search heuristics on specific problem instances, and model the relationship between the quality of search and the choice of parameters.</p> <p>For any problem instance of nontrivial size, the state space for this model is large enough so as to make computation infeasible. Our solution is to use a reduced-state model of the search space, by amalgamating many similar points. We use a model based on a level-accessible barrier tree, grouping regions of the search space according to the reachability of minima.</p> <p>Optimal annealing and mutation schedules are produced, minimising either “where-you-are” or “best-so-far” cost, over binary perception, spin-glass and Max-SAT problems. The predictions of the model are found to be consistently over-optimistic; we discuss reasons for this and suggest some possible refinements to the model.</p> <p>A population-based variant of simulated annealing is briefly examined, where annealing temperature is adjusted according to performance. We later optimise the average first-passage time for several special-case heuristics, comparing the minimal times across a range of problems.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Benfold, William

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Benfold, William. Parameter optimisation for search heuristics via a barrier tree Markov model. doctoral thesis, University of Southampton, 2007.