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 -