A template approach to producing incremental objective cost functions for local search meta-heuristics

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Meta-heuristic search techniques based on local search operators have proven to be very effective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to re-evaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using different local search operators.

Original languageEnglish
Pages (from-to)291-299
Number of pages9
JournalLecture Notes in Computer Science
Volume2611
DOIs
Publication statusPublished - 2003

Fingerprint

Metaheuristics
Cost functions
Local Search
Cost Function
Template
Objective function
Costs and Cost Analysis
Operator
Equate
Traveling salesman problem
Heuristic Search
Combinatorial optimization
Travelling salesman problems
Entire Function
Combinatorial Optimization Problem
System Modeling
Mathematical operators
Evaluate
Demonstrate
Local search (optimization)

Cite this

@article{4ec6cea0ea5a45e2a6572ee9e5937a09,
title = "A template approach to producing incremental objective cost functions for local search meta-heuristics",
abstract = "Meta-heuristic search techniques based on local search operators have proven to be very effective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to re-evaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using different local search operators.",
author = "Marcus Randall",
year = "2003",
doi = "10.1007/3-540-36605-9_27",
language = "English",
volume = "2611",
pages = "291--299",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

A template approach to producing incremental objective cost functions for local search meta-heuristics. / Randall, Marcus.

In: Lecture Notes in Computer Science, Vol. 2611, 2003, p. 291-299.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A template approach to producing incremental objective cost functions for local search meta-heuristics

AU - Randall, Marcus

PY - 2003

Y1 - 2003

N2 - Meta-heuristic search techniques based on local search operators have proven to be very effective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to re-evaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using different local search operators.

AB - Meta-heuristic search techniques based on local search operators have proven to be very effective at solving combinatorial optimisation problems. A characteristic of local search operators is that they usually only make a small change to the solution state when applied. As a result, it is often unnecessary to re-evaluate the entire objective function once a transition is made but to use an incremental cost function. For example in the travelling salesman problem, the position of two cities within a tour, may be interchanged. Using an incremental cost function, this equates to an O(1) operation as opposed to an O(n) operation (where n is the number of cities). In this paper, a new approach based on the use of templates is developed for the generic linked list modelling system [4]. It demonstrates that incremental objective cost functions can be automatically generated for given problems using different local search operators.

UR - http://www.scopus.com/inward/record.url?scp=35248840488&partnerID=8YFLogxK

U2 - 10.1007/3-540-36605-9_27

DO - 10.1007/3-540-36605-9_27

M3 - Article

VL - 2611

SP - 291

EP - 299

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -