Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Automatically detecting neighbourhood constraint interactions using comet

Andrew, A. (2008) Automatically detecting neighbourhood constraint interactions using comet. [Proceedings Paper]

[img]
Preview
PDF - Submitted Version
Download (71Kb) | Preview

    Abstract

    The major benet of using events as the basis for our detection system is the clean separation between the neighbourhoods and detector which we can achieve. The detector simply iterates over a set of Neighbourhood objects and checks each for interactions. The acceptance function for the neighbourhood is set to accept any tness. For purposes of detecting an interaction it does not matter whether a move reduces or increases the constraint violations; both indicate that a relationship exists. The simulation is performed in two stages. Starting from a randomly created initial solution a random move from the neighbourhood is chosen, often this will lead to a constraint change and prevent the need for further exploration. For some constraints the chance of randomly selecting a move which would violate it is fairly low and so a more rigourous search is required. If the initial move has not found any interaction then the detector explores every neighbouring state from the current position. If at any stage a change of the constraint violations is detected then the exploration is stopped.

    Item type: Proceedings Paper
    ID code: 36977
    Keywords: Comet, local search, neighbourhood constraint interactions , Electronic computers. Computer science
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 24 Jan 2012 09:29
    Last modified: 20 Jul 2013 21:35
    URI: http://strathprints.strath.ac.uk/id/eprint/36977

    Actions (login required)

    View Item

    Fulltext Downloads: