A swarm intelligence-based algorithm for the set-union knapsack problem


ÖZSOYDAN F. B., BAYKASOĞLU A.

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, vol.93, pp.560-569, 2019 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 93
  • Publication Date: 2019
  • Doi Number: 10.1016/j.future.2018.08.002
  • Journal Name: FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.560-569
  • Keywords: Genetic algorithm, Particle swarm optimization, Metaheuristic, Binary optimization, Knapsack problem, OPTIMIZATION ALGORITHM, DESIGN OPTIMIZATION, FRAMEWORK, CHAOS
  • Dokuz Eylül University Affiliated: Yes

Abstract

Swarm intelligence-based methods offer notable opportunities in problem solving. Although they do not guarantee optimality, such methods are shown to be promising particularly for non-convex and non-differentiable problem spaces. The present study proposes a simple yet effective binary swarm intelligence technique that is based on Genetic Algorithm and Particle Swarm Optimization. The performance of the introduced method is analysed on a recently caught on binary problem, namely, the Set-union Knapsack Problem that has a wide range of real-life applications including information security systems. It is put forth in the present contribution that the effectiveness of the proposed approach indeed stems from the easiness in implementation. It does not need transfer functions and further local search procedures in the mainstream, which usually add to the required CPU time. As secondarily, an optional mutation procedure that exponentially decreases the introduced diversity to the population is developed. Thus, while local optima traps are avoided at the earlier iterations, a more intensified search is encouraged towards the end. All available benchmarking problems are solved by the proposed approach. As shown by the experimental study and statistical tests, the proposed approach can achieve significant improvements over the published results. Moreover, it is demonstrated that the developed mutation procedure, which can easily be adopted in any metaheuristic algorithm, significantly contributes to the performance of the proposed algorithm. (C) 2018 Elsevier B.V. All rights reserved.