Standard

Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection. / Dang, Duc Cuong; Eremeev, Anton V.; Qin, Xiaoyu.

IFIP Advances in Information and Communication Technology. Springer Science and Business Media Deutschland GmbH, 2024. p. 217-232 (IFIP Advances in Information and Communication Technology; Vol. 703 IFIPAICT).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Harvard

Dang, DC, Eremeev, AV & Qin, X 2024, Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection. in IFIP Advances in Information and Communication Technology. IFIP Advances in Information and Communication Technology, vol. 703 IFIPAICT, Springer Science and Business Media Deutschland GmbH, pp. 217-232, 13th IFIP TC 12 International Conference on Intelligent Information Processing, Shenzhen, China, 03.05.2024. https://doi.org/10.1007/978-3-031-57808-3_16

APA

Dang, D. C., Eremeev, A. V., & Qin, X. (2024). Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection. In IFIP Advances in Information and Communication Technology (pp. 217-232). (IFIP Advances in Information and Communication Technology; Vol. 703 IFIPAICT). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-57808-3_16

Vancouver

Dang DC, Eremeev AV, Qin X. Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection. In IFIP Advances in Information and Communication Technology. Springer Science and Business Media Deutschland GmbH. 2024. p. 217-232. (IFIP Advances in Information and Communication Technology). doi: 10.1007/978-3-031-57808-3_16

Author

Dang, Duc Cuong ; Eremeev, Anton V. ; Qin, Xiaoyu. / Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection. IFIP Advances in Information and Communication Technology. Springer Science and Business Media Deutschland GmbH, 2024. pp. 217-232 (IFIP Advances in Information and Communication Technology).

BibTeX

@inbook{e46ea4a144bc43449d58950f74194f60,
title = "Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection",
abstract = "It has been proven that non-elitist evolutionary algorithms (EAs) with proper selection mechanisms, including the recently proposed power-law ranking selection, can efficiently escape local optima on a broad class of problems called SparseLocalOptα,ε, where elitist EAs fail. However, those theoretical upper bounds on the runtime are not tight as they require large populations and a tight balance between mutation rates and selection pressure to keep the algorithms operating near the so-called “error threshold”. This paper empirically clarifies the significance of these theoretical requirements and makes a series of performance comparisons between the non-elitist EA using power-law ranking selection and other EAs on various benchmark problems. Our experimental results show that non-elitist EAs optimise the Funnel problem with deceptive local optimum significantly faster with power-law ranking selection than with tournament selection. Furthermore, power-law selection outperforms UMDA and the (1+1) EA in our experiments on the NK-Landscape and Max k-Sat problems, but yields to the (μ,λ)-selection, tournament selection, and the self-adaptive MOSA-EA. On the unicost set cover problems, the EA with power-law selection shows competitive results.",
keywords = "Combinatorial optimization, Evolutionary computation, Experimental analysis, Local optima, Power-law ranking Selection",
author = "Dang, {Duc Cuong} and Eremeev, {Anton V.} and Xiaoyu Qin",
note = "The authors are grateful to Per Kristian Lehre for fruitful discussions of results presented in this paper and for his help with some of the experiments. A. Eremeev is supported by the Mathematical Center in Akademgorodok under the agreement 075-15-2022-282 with the Ministry of Science and Higher Education of RF.; 13th IFIP TC 12 International Conference on Intelligent Information Processing, IIP 2024 ; Conference date: 03-05-2024 Through 06-05-2024",
year = "2024",
doi = "10.1007/978-3-031-57808-3_16",
language = "English",
isbn = "9783031578076",
series = "IFIP Advances in Information and Communication Technology",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "217--232",
booktitle = "IFIP Advances in Information and Communication Technology",
address = "Germany",

}

RIS

TY - CHAP

T1 - Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking Selection

AU - Dang, Duc Cuong

AU - Eremeev, Anton V.

AU - Qin, Xiaoyu

N1 - Conference code: 13

PY - 2024

Y1 - 2024

N2 - It has been proven that non-elitist evolutionary algorithms (EAs) with proper selection mechanisms, including the recently proposed power-law ranking selection, can efficiently escape local optima on a broad class of problems called SparseLocalOptα,ε, where elitist EAs fail. However, those theoretical upper bounds on the runtime are not tight as they require large populations and a tight balance between mutation rates and selection pressure to keep the algorithms operating near the so-called “error threshold”. This paper empirically clarifies the significance of these theoretical requirements and makes a series of performance comparisons between the non-elitist EA using power-law ranking selection and other EAs on various benchmark problems. Our experimental results show that non-elitist EAs optimise the Funnel problem with deceptive local optimum significantly faster with power-law ranking selection than with tournament selection. Furthermore, power-law selection outperforms UMDA and the (1+1) EA in our experiments on the NK-Landscape and Max k-Sat problems, but yields to the (μ,λ)-selection, tournament selection, and the self-adaptive MOSA-EA. On the unicost set cover problems, the EA with power-law selection shows competitive results.

AB - It has been proven that non-elitist evolutionary algorithms (EAs) with proper selection mechanisms, including the recently proposed power-law ranking selection, can efficiently escape local optima on a broad class of problems called SparseLocalOptα,ε, where elitist EAs fail. However, those theoretical upper bounds on the runtime are not tight as they require large populations and a tight balance between mutation rates and selection pressure to keep the algorithms operating near the so-called “error threshold”. This paper empirically clarifies the significance of these theoretical requirements and makes a series of performance comparisons between the non-elitist EA using power-law ranking selection and other EAs on various benchmark problems. Our experimental results show that non-elitist EAs optimise the Funnel problem with deceptive local optimum significantly faster with power-law ranking selection than with tournament selection. Furthermore, power-law selection outperforms UMDA and the (1+1) EA in our experiments on the NK-Landscape and Max k-Sat problems, but yields to the (μ,λ)-selection, tournament selection, and the self-adaptive MOSA-EA. On the unicost set cover problems, the EA with power-law selection shows competitive results.

KW - Combinatorial optimization

KW - Evolutionary computation

KW - Experimental analysis

KW - Local optima

KW - Power-law ranking Selection

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85190712641&origin=inward&txGid=c43bc6570c8164244588fcd249ce4ae3

UR - https://www.mendeley.com/catalogue/c8c20e89-31d3-3837-ba2c-d69794b20a15/

U2 - 10.1007/978-3-031-57808-3_16

DO - 10.1007/978-3-031-57808-3_16

M3 - Chapter

SN - 9783031578076

T3 - IFIP Advances in Information and Communication Technology

SP - 217

EP - 232

BT - IFIP Advances in Information and Communication Technology

PB - Springer Science and Business Media Deutschland GmbH

T2 - 13th IFIP TC 12 International Conference on Intelligent Information Processing

Y2 - 3 May 2024 through 6 May 2024

ER -

ID: 60550817