Font Size: a A A

Monkey Algorithm And Its Application In Knapsack Problem

Posted on:2022-04-08Degree:MasterType:Thesis
Country:ChinaCandidate:L XuFull Text:PDF
GTID:2518306512975619Subject:Mathematics
Abstract/Summary:PDF Full Text Request
As a new method of optimization technology,swarm intelligent algorithm has the advantages of fast solving speed and not limited by the dimensionality and continuity of practical problems.Therefore,the research on swarm intelligence algorithm has been favored by many scholars at home and abroad.The monkey algorithm is a new swarm intelligent algorithm that imitates the monkey climbing process.The update process is easy to operate and is suitable for solving high-dimensional optimization problems.In order to further improve the optimization performance of the monkey algorithm,this thesis gives two ways to improve it,and apply them to solve the knapsack problem.1.Generalized opposition learning monkey algorithm based on Levy flight is proposed,and the proposed algorithm is used to solve the discount {0-1} knapsack problem.In order to improve the quality of the initial population,in the initialization phase of the basic monkey algorithm,the generalized opposition based learning is used to perform a generalized reverse transformation on the initial population,and the more adaptable individuals are selected from the initiall population and the reverse population to form a new population;In the climbing process,the fixed climbing step length of monkey algorithm is replaced with a non-linear decreasing climbing step length,so that the climbing step length of the monkey group shows a non-linear decreasing trend with the increase of the total number of iterations,so as to balance the algorithm to find the best when solving practical problems.The dual requirements of speed and solution accuracy;during the watch process,the Levy flight strategy is used to replace the watch process of the monkey algorithm,allowing individuals in the monkey to update collaboratively to expand the influence of outstanding monkeys in the population.In the numerical experiments,the proposed algorithm is used to optimize the benchmark test function and compared with the related comparison algorithm.The results show that the proposed algorithm has the highest solution accuracy.At the same time,the proposed algorithm and the comparison algorithm are used to solve the discount {0-1} knapsack problem.The results show that the proposed algorithm has higher solution accuracy and better robustness.2.Lagrange interpolation learning monkey algorithm is proposed,and the algorithm is used to solve the knapsack problem with a single continuous variable.In order to improve the convergence speed of the algorithm,the learning factor is introduced in the watch process of the basic monkey group algorithm,the field of view length is redefined,and the learning observation process is constructed;in the jump process,the best individual in the current population is used as the second point,The double point jump process is used to increase the diversity of the population;after the jump process,Lagrange interpolation is performed to further dig out potential solutions around the optimal solution,thereby improving the accuracy of the algorithm.Finally,the improved algorithm is used to perform numerical simulation experiments on the benchmark test function and the knapsack problem with a single continuous variable,and compared with the related comparison algorithms.The results show that the performance of the improved algorithm is the best,the solution effect is stable,and the goal of algorithm improvement is achieved.
Keywords/Search Tags:monkey algorithm, knapsack problem, Lévy flight strategy, Generalized opposition based learning, Lagrange interpolation strategy
PDF Full Text Request
Related items