Feasibility restoration for iterative meta-heuristics search algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)
34 Downloads (Pure)

Abstract

Many combinatorial optimisation problems have constraints that are difficult for meta-heuristic search algorithms to process. One approach is that of feasibility restoration. This technique allows the feasibility of the constraints of a problem to be broken and then brought back to a feasible state. The advantage of this is that the search can proceed over infeasible regions, thus potentially exploring difficult to reach parts of the state space. In this paper, a generic feasibility restoration scheme is proposed for use with the neighbourhood search algorithm simulated annealing. Some improved solutions to standard test problems are recorded.

Original languageEnglish
Title of host publicationDevelopments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings
EditorsTim Hendtlass, Moonis Ali
PublisherSpringer-Verlag London Ltd.
Pages168-178
Number of pages11
ISBN (Print)3540437819, 9783540437819
DOIs
Publication statusPublished - 1 Jan 2002
Event15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002 - Cairns, Australia
Duration: 17 Jun 200220 Jun 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2358
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002
CountryAustralia
CityCairns
Period17/06/0220/06/02

Fingerprint

Heuristic Search
Restoration
Metaheuristics
Heuristic algorithm
Search Algorithm
Combinatorial optimization
Simulated annealing
Neighborhood Search
Combinatorial Optimization Problem
Simulated Annealing
Test Problems
State Space

Cite this

Randall, M. (2002). Feasibility restoration for iterative meta-heuristics search algorithms. In T. Hendtlass, & M. Ali (Eds.), Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings (pp. 168-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2358). Springer-Verlag London Ltd.. https://doi.org/10.1007/3-540-48035-8_17
Randall, Marcus. / Feasibility restoration for iterative meta-heuristics search algorithms. Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings. editor / Tim Hendtlass ; Moonis Ali. Springer-Verlag London Ltd., 2002. pp. 168-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{8a052110612340c9966db25d60e7b28a,
title = "Feasibility restoration for iterative meta-heuristics search algorithms",
abstract = "Many combinatorial optimisation problems have constraints that are difficult for meta-heuristic search algorithms to process. One approach is that of feasibility restoration. This technique allows the feasibility of the constraints of a problem to be broken and then brought back to a feasible state. The advantage of this is that the search can proceed over infeasible regions, thus potentially exploring difficult to reach parts of the state space. In this paper, a generic feasibility restoration scheme is proposed for use with the neighbourhood search algorithm simulated annealing. Some improved solutions to standard test problems are recorded.",
author = "Marcus Randall",
year = "2002",
month = "1",
day = "1",
doi = "10.1007/3-540-48035-8_17",
language = "English",
isbn = "3540437819",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "168--178",
editor = "Tim Hendtlass and Moonis Ali",
booktitle = "Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings",
address = "Italy",

}

Randall, M 2002, Feasibility restoration for iterative meta-heuristics search algorithms. in T Hendtlass & M Ali (eds), Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2358, Springer-Verlag London Ltd., pp. 168-178, 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Cairns, Australia, 17/06/02. https://doi.org/10.1007/3-540-48035-8_17

Feasibility restoration for iterative meta-heuristics search algorithms. / Randall, Marcus.

Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings. ed. / Tim Hendtlass; Moonis Ali. Springer-Verlag London Ltd., 2002. p. 168-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2358).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Feasibility restoration for iterative meta-heuristics search algorithms

AU - Randall, Marcus

PY - 2002/1/1

Y1 - 2002/1/1

N2 - Many combinatorial optimisation problems have constraints that are difficult for meta-heuristic search algorithms to process. One approach is that of feasibility restoration. This technique allows the feasibility of the constraints of a problem to be broken and then brought back to a feasible state. The advantage of this is that the search can proceed over infeasible regions, thus potentially exploring difficult to reach parts of the state space. In this paper, a generic feasibility restoration scheme is proposed for use with the neighbourhood search algorithm simulated annealing. Some improved solutions to standard test problems are recorded.

AB - Many combinatorial optimisation problems have constraints that are difficult for meta-heuristic search algorithms to process. One approach is that of feasibility restoration. This technique allows the feasibility of the constraints of a problem to be broken and then brought back to a feasible state. The advantage of this is that the search can proceed over infeasible regions, thus potentially exploring difficult to reach parts of the state space. In this paper, a generic feasibility restoration scheme is proposed for use with the neighbourhood search algorithm simulated annealing. Some improved solutions to standard test problems are recorded.

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

U2 - 10.1007/3-540-48035-8_17

DO - 10.1007/3-540-48035-8_17

M3 - Conference contribution

SN - 3540437819

SN - 9783540437819

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 178

BT - Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings

A2 - Hendtlass, Tim

A2 - Ali, Moonis

PB - Springer-Verlag London Ltd.

ER -

Randall M. Feasibility restoration for iterative meta-heuristics search algorithms. In Hendtlass T, Ali M, editors, Developments in Applied Artificial Intelligence - 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE 2002, Proceedings. Springer-Verlag London Ltd. 2002. p. 168-178. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-48035-8_17