A Discrete Whale Optimization Algorithm For Solving Combinatorial Optimization Problems

Combinatorial optimization problem is a classical and important branch of operational research,which is widely used in information technology,economic management,transportation,VLSI design,code design,image processing,electronic engineering,communication engineering,finance and municipal construction.With the development of science and technology,the new combinatorial optimization problems proposed in various fields are becoming more and more complex,which prompts people to constantly seek new solutions.The emergence of evolutionary algorithms provides a new and feasible method for solving these complex problems.The advantage of evolutionary algorithm is that it does not require the objective function to have some characteristics,such as continuity and derivability,and the algorithm itself has parallelism and very strong optimization ability..Whale optimization algorithm is a novel evolutionary algorithm proposed by Seyedali Mirjalili in 2016,which is very simple to implementation.However,this algorithm is designed to solve continuous optimization problems,so it can not be directly used to solve combinatorial optimization problems in discrete domain.At present,most scholars focus on the improvement of WOA,and the research on the discretization of this algorithm is relatively few.Therefore,this paper mainly studies how to design an efficient code conversion function to realize the discretization of WOA,and verify the effectiveness of the proposed method by using the classical knapsack problem instances.Finally,an improved discrete whale optimization algorithm is proposed and applied to the community detection problem,which provides a new method for solving the community detection problem of complex networks.The main contents of this paper are as follows:1.We first give a new V-shaped function by drawing lesson from the existing discretization methods,which transfer a real vector to an integer vector.Based on that,we propose a novel binary whale optimization algorithm,and compare it with other algorithms by using the 0-1 knapsack problem instances.2.Based on a new mapping function,a discrete whale optimization algorithm is proposed to solve the combinatorial optimization problem with space of{0,1,...,m₁}×{0,1,...,m₂}×...×{0,1,...,m_n}.3.We use the discrete whale optimization algorithm to solve discounted{0-1}knapsack problem and the bounded knapsack problem,and the search space of these two kinds of knapsack problems is{0,1,...,m}ⁿ and{0,1,...,m₁}×{0,1,...,m₂}×...×{0,1,...,m_n}.We compare the results with other algorithms.4.Finally,we propose an improved discrete whale optimization algorithm and applies it to community detection.This algorithm uses character encoding and takes modularity function as the target optimization function.We present a feasible method to solve community detection problem by using improved discrete whale optimization algorithm.