A Bayesian Restarting Approach to Algorithm Selection

Yaodong He; Shiu Yin Yuen; Yang Lou

doi:10.1007/978-3-319-68759-9_33

A Bayesian Restarting Approach to Algorithm Selection

^*Corresponding author for this work

Department of Electrical Engineering

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.

Original language	English
Title of host publication	Simulated Evolution and Learning
Editors	Yuhui Shi, Kay Chen Tan, Mengjie Zhang, Ke Tang, Xiaodong Li, Qingfu Zhang, Ying Tan, Martin Middendorf, Yaochu Jin
Publisher	Springer, Cham
Pages	397-408
ISBN (Electronic)	978-3-319-68759-9
ISBN (Print)	978-3-319-68758-2
DOIs	https://doi.org/10.1007/978-3-319-68759-9_33
Publication status	Published - Nov 2017
Event	11th International Conference on Simulated Evolution and Learning ( SEAL 2017) - Southern University of Science and Technology, Shenzhen, China Duration: 10 Nov 2017 → 13 Nov 2017 http://www.seal2017.com/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10593
ISSN (Print)	0302-9743

Conference

Conference	11th International Conference on Simulated Evolution and Learning ( SEAL 2017)
Place	China
City	Shenzhen
Period	10/11/17 → 13/11/17
Internet address	http://www.seal2017.com/

Research Keywords

Algorithm selection
Bayesian approach
Evolutionary algorithm
Monte Carlo method
Optimization problems

Access Output

10.1007/978-3-319-68759-9_33

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{59b5cbad23734850b7bb43ee2eebe339,

title = "A Bayesian Restarting Approach to Algorithm Selection",

abstract = "A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.",

keywords = "Algorithm selection, Bayesian approach, Evolutionary algorithm, Monte Carlo method, Optimization problems",

author = "Yaodong He and Yuen, {Shiu Yin} and Yang Lou",

year = "2017",

month = nov,

doi = "10.1007/978-3-319-68759-9_33",

language = "English",

isbn = "978-3-319-68758-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "397--408",

editor = "Shi, {Yuhui } and Tan, {Kay Chen} and Mengjie Zhang and Ke Tang and Li, {Xiaodong } and Zhang, {Qingfu } and Ying Tan and Middendorf, {Martin } and Yaochu Jin",

booktitle = "Simulated Evolution and Learning",

note = "11th International Conference on Simulated Evolution and Learning ( SEAL 2017) ; Conference date: 10-11-2017 Through 13-11-2017",

url = "http://www.seal2017.com/",

}

He, Y , Yuen, SY & Lou, Y 2017, A Bayesian Restarting Approach to Algorithm Selection. in Y Shi, KC Tan, M Zhang, K Tang, X Li, Q Zhang, Y Tan, M Middendorf & Y Jin (eds), Simulated Evolution and Learning. Lecture Notes in Computer Science, vol. 10593, Springer, Cham, pp. 397-408, 11th International Conference on Simulated Evolution and Learning ( SEAL 2017), Shenzhen, China, 10/11/17. https://doi.org/10.1007/978-3-319-68759-9_33

A Bayesian Restarting Approach to Algorithm Selection. / He, Yaodong ; Yuen, Shiu Yin ; Lou, Yang.
Simulated Evolution and Learning. ed. / Yuhui Shi; Kay Chen Tan; Mengjie Zhang; Ke Tang; Xiaodong Li; Qingfu Zhang; Ying Tan; Martin Middendorf; Yaochu Jin. Springer, Cham, 2017. p. 397-408 (Lecture Notes in Computer Science; Vol. 10593).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A Bayesian Restarting Approach to Algorithm Selection

AU - He, Yaodong

AU - Yuen, Shiu Yin

AU - Lou, Yang

PY - 2017/11

Y1 - 2017/11

N2 - A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.

AB - A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.

KW - Algorithm selection

KW - Bayesian approach

KW - Evolutionary algorithm

KW - Monte Carlo method

KW - Optimization problems

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85034219640&origin=recordpage

U2 - 10.1007/978-3-319-68759-9_33

DO - 10.1007/978-3-319-68759-9_33

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-319-68758-2

T3 - Lecture Notes in Computer Science

SP - 397

EP - 408

BT - Simulated Evolution and Learning

A2 - Shi, Yuhui

A2 - Tan, Kay Chen

A2 - Zhang, Mengjie

A2 - Tang, Ke

A2 - Li, Xiaodong

A2 - Zhang, Qingfu

A2 - Tan, Ying

A2 - Middendorf, Martin

A2 - Jin, Yaochu

PB - Springer, Cham

T2 - 11th International Conference on Simulated Evolution and Learning ( SEAL 2017)

Y2 - 10 November 2017 through 13 November 2017

ER -

A Bayesian Restarting Approach to Algorithm Selection

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this