Set algebra-based algebraic evolutionary algorithm for binary optimization problems

doi:10.1016/j.asoc.2023.110425

Set algebra-based algebraic evolutionary algorithm for binary optimization problems

2023-08-01

0

PRE

AI

DOI：10.1016/j.asoc.2023.110425

Original

Original request for help

Save

Abstract

En 中文

In order to design algebraic evolutionary algorithms by set algebra, the intersection, union, comple-ment, 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(S2) of set S2 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.& COPY; 2023 Elsevier B.V. All rights reserved.

Keywords:

Evolutionary algorithm

Set algebra

Binary optimization problem

0-1 Knapsack problem

Knapsack problem with single continuous variable

Set algebra-based algebraic evolutionary algorithm for binary optimization problems

Abstract

Journal

Organization