TY - JOUR
T1 - Set algebra — based algebraic evolutionary algorithm for binary optimization problems
AU - He, Yichao
AU - Sun, Hailu
AU - Wang, Yuan
AU - Zhang, Xinlu
AU - Mirjalili, Seyedali
N1 - Funding Information:
We thank Editor-in-Chief and anonymous reviewers whose valuable comments and suggestions help us significantly improve this article. This article was supported by Natural Science Foundation of Hebei Province, China ( F2020403013 ), Funded by Science and Technology Project of Hebei Education Department ( ZD2021016 ), and National Pre-research Funds of Hebei GEO University in 2023 (Grant KY202307 ).
Publisher Copyright:
© 2023
PY - 2023/8
Y1 - 2023/8
N2 - In order to design algebraic evolutionary algorithms by set algebra, the intersection, union, complement, difference and symmetric difference operations of 0-1 vectors on {0,1}n are firstly defined based on set operations. Then, the isomorphism between algebraic system defined on {0,1}n and set algebra defined on power set P(Ω) of set Ω is proved. Therefrom a simple and fast implement method of set algebra is proposed. Third, symmetric difference operator and asymmetric mutation operator are successively proposed based on set algebra, they have global exploration and local exploitation capabilities respectively. On this basis, a novel algebraic evolutionary algorithm, named set algebra-based heuristic algorithm (SAHA), is proposed based on the operations of 0-1 vectors on {0,1}n for solving binary optimization problems. For verifying the performance of SAHA, it is used to solve 0-1 knapsack problem (0-1KP) and knapsack problem with single continuous variable (KPC), respectively. The comparison with the state-of-the-art algorithms of solving 0-1KP and KPC shows that SAHA can not only obtain excellent calculation results, but also is faster speed, it is most competitive for solving binary optimization problems.
AB - In order to design algebraic evolutionary algorithms by set algebra, the intersection, union, complement, difference and symmetric difference operations of 0-1 vectors on {0,1}n are firstly defined based on set operations. Then, the isomorphism between algebraic system defined on {0,1}n and set algebra defined on power set P(Ω) of set Ω is proved. Therefrom a simple and fast implement method of set algebra is proposed. Third, symmetric difference operator and asymmetric mutation operator are successively proposed based on set algebra, they have global exploration and local exploitation capabilities respectively. On this basis, a novel algebraic evolutionary algorithm, named set algebra-based heuristic algorithm (SAHA), is proposed based on the operations of 0-1 vectors on {0,1}n for solving binary optimization problems. For verifying the performance of SAHA, it is used to solve 0-1 knapsack problem (0-1KP) and knapsack problem with single continuous variable (KPC), respectively. The comparison with the state-of-the-art algorithms of solving 0-1KP and KPC shows that SAHA can not only obtain excellent calculation results, but also is faster speed, it is most competitive for solving binary optimization problems.
KW - 0-1 Knapsack problem
KW - Binary optimization problem
KW - Evolutionary algorithm
KW - Knapsack problem with single continuous variable
KW - Set algebra
UR - http://www.scopus.com/inward/record.url?scp=85160325292&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2023.110425
DO - 10.1016/j.asoc.2023.110425
M3 - Article
AN - SCOPUS:85160325292
SN - 1568-4946
VL - 143
JO - Applied Soft Computing
JF - Applied Soft Computing
M1 - 110425
ER -
