Research On Solving Combinatorial Optimization Problems Based On Grey Wolf Optimization Algorithm

Combinatorial optimization is an important NP-hard problem in computer science and operations research.With the rapid development of economy and the continuous progress of society,combinatorial optimization problems become more complex and difficult to solve,and the traditional algorithm is difficult to meet the needs of social production.In this context,scholars at home and abroad raise new ideas and methods for solving combinatorial optimization problems based on evolutionary algorithm,and achieved fruitful achievements.Evolutionary algorithm has become one of the most important methods for solving combinatorial optimization problems.Grey Wolf Optimization Algorithm(GWO)is an evolutionary algorithm proposed by Mirjalili to simulate the behavior of grey wolves in nature.It has the advantages of simple operation and few parameters,and has been applied in the fields of machine scheduling,inventory problems and distributed computing.Although GWO has achieved some success in solving optimization problems,it still has two shortcomings:Firstly,GWO's global search ability is unstable,and it is easy to fall into local optimal as other evolutionary algorithms;Secondly,GWO is proposed for optimization problems in continuous space and cannot be directly used for combinatorial optimization problems.In this paper,random search strategy and multiple exponential crossover strategy are introduced to improve the global optimization of the algorithm.Based on the the direct discretization method of modular n arithmetic and transfer function,raises two discrete grey wolf optimization algorithms DGWO1 and DGWO2 for solving combinatorial optimization problems on{0,1...,m₁}×{0,1...,m₂}×...×{0,1...,m_n}.They are used to solve the uncapacitated facility location problem(UFLP)and discounted knapsack problem(D{0-1}KP),and the effectiveness of the new algorithm is verified by comparing with the existing algorithms.At the same time,solving the community discovery problem based on DGWO1 not only confirms the practicality of the new algorithm,but also provides a new method for community division in complex networks.The main contents of this paper are as follows:1.Two discrete grey wolf optimization algorithms DGWO1 and DGWO2,which are suitable for solving discrete optimization problems,are proposed based on the modular 2arithmetic and transfer function respectively.Through solving UFLP examples,it is pointed out that DGWO1 and DGWO2 have better optimization ability,and it is further pointed out that solving UFLP based on DGWO1 is more efficient than existing best algorithms.2.Random learning strategy was introduced in DGWO1,and an improved discrete grey wolf optimization algorithm IDGWO1 was proposed to solve D{0-1}KP on{0,1,2,3}ⁿ.By comparing with DGWO2 and the best existing algorithms,it was pointed out that:IDGWO1 is not only more suitable for solving D{0-1}KP than DGWO2,but also better than the best existing algorithms.3.A new method using IDGWO1 to solve community discovery problem is proposed.Based on the simulation calculation of real network data set,the practicability and high efficiency of IDGWO1 in solving community discovery problem are verified.