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 -