An investigation of the use of local search in NP-hard problems

D. Newth, M. Kirley, D. G. Green

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

4 Citations (Scopus)

Abstract

We combine local search algorithms with genetic algorithms. In this context local search can be thought of as learning over an individual's lifetime. We investigate two different ways of incorporating learning into the hybrid algorithm: Lamarckian evolution and the Baldwin effect. For each model we systematically vary the proportion of the population undergoing learning. We found that the quality of solution improves significantly at or above a critical level of learning.

Original languageEnglish
Title of host publicationIECON Proceedings (Industrial Electronics Conference)
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages2710-2715
Number of pages6
DOIs
Publication statusPublished - Oct 2000
Externally publishedYes

Cite this

Newth, D., Kirley, M., & Green, D. G. (2000). An investigation of the use of local search in NP-hard problems. In IECON Proceedings (Industrial Electronics Conference) (pp. 2710-2715). [972426] IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/IECON.2000.972426
Newth, D. ; Kirley, M. ; Green, D. G. / An investigation of the use of local search in NP-hard problems. IECON Proceedings (Industrial Electronics Conference). IEEE, Institute of Electrical and Electronics Engineers, 2000. pp. 2710-2715
@inproceedings{fa4578cd97ef4c889e2d1902bf3711d6,
title = "An investigation of the use of local search in NP-hard problems",
abstract = "We combine local search algorithms with genetic algorithms. In this context local search can be thought of as learning over an individual's lifetime. We investigate two different ways of incorporating learning into the hybrid algorithm: Lamarckian evolution and the Baldwin effect. For each model we systematically vary the proportion of the population undergoing learning. We found that the quality of solution improves significantly at or above a critical level of learning.",
author = "D. Newth and M. Kirley and Green, {D. G.}",
year = "2000",
month = "10",
doi = "10.1109/IECON.2000.972426",
language = "English",
pages = "2710--2715",
booktitle = "IECON Proceedings (Industrial Electronics Conference)",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
address = "United States of America",

}

Newth, D, Kirley, M & Green, DG 2000, An investigation of the use of local search in NP-hard problems. in IECON Proceedings (Industrial Electronics Conference)., 972426, IEEE, Institute of Electrical and Electronics Engineers, pp. 2710-2715. https://doi.org/10.1109/IECON.2000.972426

An investigation of the use of local search in NP-hard problems. / Newth, D.; Kirley, M.; Green, D. G.

IECON Proceedings (Industrial Electronics Conference). IEEE, Institute of Electrical and Electronics Engineers, 2000. p. 2710-2715 972426.

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

TY - GEN

T1 - An investigation of the use of local search in NP-hard problems

AU - Newth, D.

AU - Kirley, M.

AU - Green, D. G.

PY - 2000/10

Y1 - 2000/10

N2 - We combine local search algorithms with genetic algorithms. In this context local search can be thought of as learning over an individual's lifetime. We investigate two different ways of incorporating learning into the hybrid algorithm: Lamarckian evolution and the Baldwin effect. For each model we systematically vary the proportion of the population undergoing learning. We found that the quality of solution improves significantly at or above a critical level of learning.

AB - We combine local search algorithms with genetic algorithms. In this context local search can be thought of as learning over an individual's lifetime. We investigate two different ways of incorporating learning into the hybrid algorithm: Lamarckian evolution and the Baldwin effect. For each model we systematically vary the proportion of the population undergoing learning. We found that the quality of solution improves significantly at or above a critical level of learning.

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

U2 - 10.1109/IECON.2000.972426

DO - 10.1109/IECON.2000.972426

M3 - Conference Paper

AN - SCOPUS:84968745164

SP - 2710

EP - 2715

BT - IECON Proceedings (Industrial Electronics Conference)

PB - IEEE, Institute of Electrical and Electronics Engineers

ER -

Newth D, Kirley M, Green DG. An investigation of the use of local search in NP-hard problems. In IECON Proceedings (Industrial Electronics Conference). IEEE, Institute of Electrical and Electronics Engineers. 2000. p. 2710-2715. 972426 https://doi.org/10.1109/IECON.2000.972426