Bandit-based Random Mutation Hill-Climbing

Jialin LIU; Diego PÉREZ-LIÉBANA; Simon M. LUCAS

doi:10.1109/CEC.2017.7969564

Bandit-based Random Mutation Hill-Climbing

Jialin LIU, Diego PÉREZ-LIÉBANA, Simon M. LUCAS

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Referred Conference Paper › peer-review

7 Citations (Scopus)

Abstract

The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi-armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.

Original language	English
Title of host publication	2017 IEEE Congress on Evolutionary Computation, CEC 2017 : Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2145-2151
Number of pages	7
ISBN (Electronic)	9781509046010
DOIs	https://doi.org/10.1109/CEC.2017.7969564
Publication status	Published - 2017
Externally published	Yes
Event	2017 IEEE Congress on Evolutionary Computation, CEC 2017 - Donostia-San Sebastian, Spain Duration: 5 Jun 2017 → 8 Jun 2017

Conference

Conference	2017 IEEE Congress on Evolutionary Computation, CEC 2017
Country/Territory	Spain
City	Donostia-San Sebastian
Period	5/06/17 → 8/06/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

Bandit
OneMax
RMHC
Royal Road

Access to Document

10.1109/CEC.2017.7969564

Cite this

@inproceedings{e415beb7d3804904b41bea1ce40fcd07,

title = "Bandit-based Random Mutation Hill-Climbing",

abstract = "The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi-armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.",

keywords = "Bandit, OneMax, RMHC, Royal Road",

author = "Jialin LIU and Diego P{\'E}REZ-LI{\'E}BANA and LUCAS, {Simon M.}",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE Congress on Evolutionary Computation, CEC 2017 ; Conference date: 05-06-2017 Through 08-06-2017",

year = "2017",

doi = "10.1109/CEC.2017.7969564",

language = "English",

pages = "2145--2151",

booktitle = "2017 IEEE Congress on Evolutionary Computation, CEC 2017 : Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

LIU, J, PÉREZ-LIÉBANA, D & LUCAS, SM 2017, Bandit-based Random Mutation Hill-Climbing. in 2017 IEEE Congress on Evolutionary Computation, CEC 2017 : Proceedings., 7969564, Institute of Electrical and Electronics Engineers Inc., pp. 2145-2151, 2017 IEEE Congress on Evolutionary Computation, CEC 2017, Donostia-San Sebastian, Spain, 5/06/17. https://doi.org/10.1109/CEC.2017.7969564

Bandit-based Random Mutation Hill-Climbing. / LIU, Jialin; PÉREZ-LIÉBANA, Diego; LUCAS, Simon M.
2017 IEEE Congress on Evolutionary Computation, CEC 2017 : Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. p. 2145-2151 7969564.

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Referred Conference Paper › peer-review

TY - GEN

T1 - Bandit-based Random Mutation Hill-Climbing

AU - LIU, Jialin

AU - PÉREZ-LIÉBANA, Diego

AU - LUCAS, Simon M.

PY - 2017

Y1 - 2017

N2 - The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi-armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.

AB - The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi-armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.

KW - Bandit

KW - OneMax

KW - RMHC

KW - Royal Road

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

U2 - 10.1109/CEC.2017.7969564

DO - 10.1109/CEC.2017.7969564

M3 - Conference paper (refereed)

AN - SCOPUS:85027874344

SP - 2145

EP - 2151

BT - 2017 IEEE Congress on Evolutionary Computation, CEC 2017 : Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE Congress on Evolutionary Computation, CEC 2017

Y2 - 5 June 2017 through 8 June 2017

ER -

Bandit-based Random Mutation Hill-Climbing

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this