Set algebra — based algebraic evolutionary algorithm for binary optimization problems

Yichao He, Hailu Sun, Yuan Wang, Xinlu Zhang, Seyedali Mirjalili

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number110425
JournalApplied Soft Computing
Volume143
DOIs
Publication statusPublished - Aug 2023

Keywords

  • 0-1 Knapsack problem
  • Binary optimization problem
  • Evolutionary algorithm
  • Knapsack problem with single continuous variable
  • Set algebra

Fingerprint

Dive into the research topics of 'Set algebra — based algebraic evolutionary algorithm for binary optimization problems'. Together they form a unique fingerprint.

Cite this