### 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 language | English |
---|---|

Pages (from-to) | 291-299 |

Number of pages | 9 |

Journal | Lecture Notes in Computer Science |

Volume | 2611 |

DOIs | |

Publication status | Published - 2003 |

### Fingerprint

### Cite this

}

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

Research output: Contribution to journal › Article › Research › peer-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 -