TY - GEN
T1 - On the Effects of Smoothing Rugged Landscape by Different Toy Problems
T2 - 13th IEEE Congress on Evolutionary Computation, CEC 2024
AU - Wang, Wei
AU - Shi, Jialong
AU - Sun, Jianyong
AU - Liefooghe, Arnaud
AU - Zhang, Qingfu
AU - Fan, Ye
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix Q1 (construct by ' +/-1'), a toy UBQP with matrix Q2 (construct by ' +/-i') and a toy UBQP with matrix Q3 (construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with Q1 (construct by ' +/-1') exhibits the flattest landscape among the three, while the toy UBQP with Q3 (construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with Q2 (construct by +/ i) emerges as the most effective, while Q3 (construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.
AB - The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix Q1 (construct by ' +/-1'), a toy UBQP with matrix Q2 (construct by ' +/-i') and a toy UBQP with matrix Q3 (construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with Q1 (construct by ' +/-1') exhibits the flattest landscape among the three, while the toy UBQP with Q3 (construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with Q2 (construct by +/ i) emerges as the most effective, while Q3 (construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.
KW - Homotopic convex (HC) transformation
KW - Landscape smoothing
KW - Unconstrained Binary Quadratic Programming (UBQP)
UR - https://www.scopus.com/pages/publications/85201732822
U2 - 10.1109/CEC60901.2024.10612165
DO - 10.1109/CEC60901.2024.10612165
M3 - 会议稿件
AN - SCOPUS:85201732822
T3 - 2024 IEEE Congress on Evolutionary Computation, CEC 2024 - Proceedings
BT - 2024 IEEE Congress on Evolutionary Computation, CEC 2024 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 30 June 2024 through 5 July 2024
ER -