The probabilistic heuristic in local (PHIL) search meta-strategy

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

48 Downloads (Pure)

Abstract

Local search, in either best or first admissible form, generally suffers from poor solution qualities as search cannot be continued beyond locally optimal points. Even multiple start local search strategies can suffer this problem. Meta-heuristic search algorithms, such as simulated annealing and tabu search, implement often computationally expensive optimisation strategies in which local search becomes a subordinate heuristic. To overcome this, a new form of local search is proposed. The Probabilistic Heuristic In Local (PHIL) search meta-strategy uses a recursive branching mechanism in order to overcome local optima. This strategy imposes only a small computational load over and above classical local search. A comparison between PHIL search and ant colony system on benchmark travelling salesman problem instances suggests that the new meta-strategy provides competitive performance. Extensions and improvements to the paradigm are also given.

Original languageEnglish
Title of host publicationInnovations in applied and artificial intelligence
Subtitle of host publicationIEA/AID 2005
EditorsM Ali, F Esposito
PublisherSpringer
Pages648-656
Number of pages9
ISBN (Print)3-540-26551-1
DOIs
Publication statusPublished - 2005
Event18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems - Bari, Italy
Duration: 22 Jun 200524 Jun 2005
Conference number: 18

Publication series

NameLECTURE NOTES IN ARTIFICIAL INTELLIGENCE
PublisherSPRINGER-VERLAG BERLIN
Volume3533
ISSN (Print)0302-9743

Conference

Conference18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems
Abbreviated title IEA/AIE
CountryItaly
CityBari
Period22/06/0524/06/05

Cite this

Randall, M. (2005). The probabilistic heuristic in local (PHIL) search meta-strategy. In M. Ali, & F. Esposito (Eds.), Innovations in applied and artificial intelligence : IEA/AID 2005 (pp. 648-656). (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE; Vol. 3533). Springer. https://doi.org/10.1007/11504894_90
Randall, M. / The probabilistic heuristic in local (PHIL) search meta-strategy. Innovations in applied and artificial intelligence : IEA/AID 2005. editor / M Ali ; F Esposito. Springer, 2005. pp. 648-656 (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE).
@inproceedings{ea22695e2edc4599a2b799ead89d133b,
title = "The probabilistic heuristic in local (PHIL) search meta-strategy",
abstract = "Local search, in either best or first admissible form, generally suffers from poor solution qualities as search cannot be continued beyond locally optimal points. Even multiple start local search strategies can suffer this problem. Meta-heuristic search algorithms, such as simulated annealing and tabu search, implement often computationally expensive optimisation strategies in which local search becomes a subordinate heuristic. To overcome this, a new form of local search is proposed. The Probabilistic Heuristic In Local (PHIL) search meta-strategy uses a recursive branching mechanism in order to overcome local optima. This strategy imposes only a small computational load over and above classical local search. A comparison between PHIL search and ant colony system on benchmark travelling salesman problem instances suggests that the new meta-strategy provides competitive performance. Extensions and improvements to the paradigm are also given.",
author = "M Randall",
year = "2005",
doi = "10.1007/11504894_90",
language = "English",
isbn = "3-540-26551-1",
series = "LECTURE NOTES IN ARTIFICIAL INTELLIGENCE",
publisher = "Springer",
pages = "648--656",
editor = "M Ali and F Esposito",
booktitle = "Innovations in applied and artificial intelligence",
address = "Germany",

}

Randall, M 2005, The probabilistic heuristic in local (PHIL) search meta-strategy. in M Ali & F Esposito (eds), Innovations in applied and artificial intelligence : IEA/AID 2005. LECTURE NOTES IN ARTIFICIAL INTELLIGENCE, vol. 3533, Springer, pp. 648-656, 18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Bari, Italy, 22/06/05. https://doi.org/10.1007/11504894_90

The probabilistic heuristic in local (PHIL) search meta-strategy. / Randall, M.

Innovations in applied and artificial intelligence : IEA/AID 2005. ed. / M Ali; F Esposito. Springer, 2005. p. 648-656 (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE; Vol. 3533).

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

TY - GEN

T1 - The probabilistic heuristic in local (PHIL) search meta-strategy

AU - Randall, M

PY - 2005

Y1 - 2005

N2 - Local search, in either best or first admissible form, generally suffers from poor solution qualities as search cannot be continued beyond locally optimal points. Even multiple start local search strategies can suffer this problem. Meta-heuristic search algorithms, such as simulated annealing and tabu search, implement often computationally expensive optimisation strategies in which local search becomes a subordinate heuristic. To overcome this, a new form of local search is proposed. The Probabilistic Heuristic In Local (PHIL) search meta-strategy uses a recursive branching mechanism in order to overcome local optima. This strategy imposes only a small computational load over and above classical local search. A comparison between PHIL search and ant colony system on benchmark travelling salesman problem instances suggests that the new meta-strategy provides competitive performance. Extensions and improvements to the paradigm are also given.

AB - Local search, in either best or first admissible form, generally suffers from poor solution qualities as search cannot be continued beyond locally optimal points. Even multiple start local search strategies can suffer this problem. Meta-heuristic search algorithms, such as simulated annealing and tabu search, implement often computationally expensive optimisation strategies in which local search becomes a subordinate heuristic. To overcome this, a new form of local search is proposed. The Probabilistic Heuristic In Local (PHIL) search meta-strategy uses a recursive branching mechanism in order to overcome local optima. This strategy imposes only a small computational load over and above classical local search. A comparison between PHIL search and ant colony system on benchmark travelling salesman problem instances suggests that the new meta-strategy provides competitive performance. Extensions and improvements to the paradigm are also given.

U2 - 10.1007/11504894_90

DO - 10.1007/11504894_90

M3 - Conference contribution

SN - 3-540-26551-1

T3 - LECTURE NOTES IN ARTIFICIAL INTELLIGENCE

SP - 648

EP - 656

BT - Innovations in applied and artificial intelligence

A2 - Ali, M

A2 - Esposito, F

PB - Springer

ER -

Randall M. The probabilistic heuristic in local (PHIL) search meta-strategy. In Ali M, Esposito F, editors, Innovations in applied and artificial intelligence : IEA/AID 2005. Springer. 2005. p. 648-656. (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). https://doi.org/10.1007/11504894_90