Back to search

University of Southampton

Barrier trees for studying search landscapes

Abstract

dc:description.abstract

<p><span style='color:black'>This thesis </span><span >presents Barrier Trees and Barrier based models as tools to study small instances of problems exempla of the difficult problems faced by practitioners.</span></p> <p><span >Barrier Trees represent a cost landscape as a tree structure, with the leaves representing local minima and the internal nodes representing barriers between different parts of the landscape. They are a development of similar structures used in the study of protein folding, molecular clusters and potential energy surfaces amongst other fields. A novel definition of Barrier Trees is developed which has the advantage of defining a partitioning of the landscape, which can be used for further analysis and the animation of search heuristics working on the landscape. These techniques and various analyses using this partitioning are demonstrated.</span></p> <p><span >Barrier based models are model problems derived from small instances of real problems. They maintain the structure and connectivity between different local minima, and many other properties of the original problem, while massively reducing the state space. They provide a model Neighbourhood function that allows many different search algorithms to be implemented on the model problem, and they are particularly well suited to modelling search heuristics as Markov chains. These models are defined, and simple descent is used as an example of how the models can be used. The relationship between descent on the model problem and on the original problems is examined in detail. Variations on the basic model are explored.</span></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
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hallam, Jonathan

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

Hallam, Jonathan. Barrier trees for studying search landscapes. doctoral thesis, University of Southampton, 2006.