Improved Implementation Of Monkey Algorithm And Its Application In Solving Knapsack Problem

In recent years,swarm intelligence optimization algorithms(EAs),which are favored by the majority of researchers,have greatly improved the solution of complex optimization problems and have been used in various fields of research.Among them,Monkey Algorithm(MA)has relatively high performance in solving large-scale multimodal optimization problems,and has a broad application prospect.However,in the solution of some larger-scale discrete problems,MA still has some shortcomings.Therefore,further research on MA has important practical significance.Aiming at the solution performance of MA on large-scale discrete problems,this paper mainly studies two different types of large-scale knapsack problems: discount{0-1} knapsack problem(D{0-1}KP)and bounded knapsack problem(BKP).Since MA itself tends to fall into the local optimum when solving discrete problems,leading to shortcomings such as low accuracy and slow convergence speed,it is necessary to make certain improvements to MA.The main work is as follows:1.For D{0-1}KP,a hybrid monkey algorithm(MMA)is proposed.By fusing the greedy core acceleration operator with the MA,the backpack capacity is reduced,thereby reducing the calculation time,and the induction factor is introduced into the climbing process to avoid falling into the local optimal trend,and then the infeasible solution is repaired by a repair strategy.Finally,through the comparative analysis of simulation experiments,it is verified that the improved MA is effective for solving D{0-1}KP.2.BKP is a classic NP complete problem in combinatorial optimization problems.Based on MA,an improved monkey algorithm(IMA)is proposed to solve this problem.The natural number encoding method is mainly used to discretize the monkey group,then the climbing process is improved,and an improved cooperation process is introduced after the look-and-jump process to speed up the convergence of the algorithm.Finally,an improved information sharing mechanism and perturbation mechanism are introduced in the translation process to strengthen the information exchange between the monkey groups and avoid falling into a local optimum.Simulation experiments are used to verify three types of large-scale BKP examples,and the results show that the proposed improved method is effective3.In order to further reduce the adjustment of MA parameters,an improved monkey algorithm based on ring theory(RTIMA)is proposed for BKP.This algorithm improves stability while reducing parameter adjustments.RTIMA mainly proposes a ring theory operator based on the ring theory,that is,using the ring theory operator to improve the climbing process on the basis of IMA,so as to reduce the adjustment of parameters and reduce the time complexity of the algorithm.Finally,it is compared and analyzed with the calculation results of other algorithms to verify that the method is feasible.