Title: A novel binary multi-swarms fruit fly optimisation algorithm for the 0-1 multidimensional knapsack problem

Authors: Xin Du; Jiawei Zhou; Youcong Ni; Wentao Liu; Ruliang Xiao; Xiuli Wu

Addresses: College of Computer and Cyber Security, Fujian Normal University, Fuzhou, China ' College of Computer and Cyber Security, Fujian Normal University, Fuzhou, China ' College of Computer and Cyber Security, Fujian Normal University, Fuzhou, China ' College of Computer and Cyber Security, Fujian Normal University, Fuzhou, China ' College of Computer and Cyber Security, Fujian Normal University, Fuzhou, China ' School of Mechanical Engineering, University of Science and Technology Beijing, Beijing, China

Abstract: To improve solution quality and accelerate convergence speed of traditional fruit fly optimisation algorithm in solving MKP, a novel binary multi-swarm fruit fly optimisation algorithm (bMFOA) is proposed. It comprises four novelties. Firstly, an item frequency tree (IFT) is constructed based on the idea of frequency pattern mining, and a new search strategy is proposed to obtain heuristic information. Secondly, two new heuristic operators of 'ADD' and 'DROP' are designed according to the obtained heuristic knowledge. Thirdly, a multi-swarm cooperation strategy is presented to strengthen the exploitation capability. To prevent algorithm falling into the local optimum prematurely, a swarm location escape strategy is put forward. To verify the efficiency of bMFOA, it is compared with some existing meta-heuristic methods by solving 58 MKPs from ORLIB. The experimental results show that the bMFOA performs better than existing meta-heuristic methods.

Keywords: fruit fly optimisation; multidimensional knapsack problem; binary optimisation.

DOI: 10.1504/IJBIC.2023.129982

International Journal of Bio-Inspired Computation, 2023 Vol.21 No.1, pp.1 - 10

Received: 31 Aug 2021
Accepted: 16 Dec 2021
Published online: 04 Apr 2023 *