改进猴群算法求解有界背包问题

Improved Monkey Algorithm for Bounded Knapsack Problem

有界背包问题是经典的NP完全问题,确定性算法求解该问题时难度较大。本文在基本猴群算法的基础上,提出了一种改进猴群算法用于求解此问题。首先,对猴群算法的爬过程进行改进;然后,在望-跳过程后引入改进的合作过程,以加快算法的收敛速度;最后,在翻过程中引入改进的信息共享机制和扰动机制,让猴群之间进行信息交流,增加解的多样性,避免陷入局部最优,以便寻得更优解。为有效求解有界背包问题,先对猴群个体采用自然数编码,通过修复与优化法对不可行解进行处理,保证算法的求解效果。通过对三大规模有界背包问题实例进行仿真实验,结果表明,改进猴群算法能得到近似比接近1的近似解。

As a classic NP complete problem,the solution of bounded knapsack problem by deterministic algorithm is of relatively more difficulty.This paper proposes an improved monkey algorithm(IMA)on the basis of basic monkey algorithm(MA)to solve this problem.Firstly,the crawling process of monkey algorithm is improved;then,an improved cooperative process is introduced after the look-and-hop process to speed up the convergence rate of the algorithm;finally,an improved information sharing mechanism and disturbance mechanism are introduced in the turning process to avoid falling into a local optimum and obtain a better solution by allowing the monkey groups to communicate information and increasing the diversity of solutions.In order to effectively solve the bounded knapsack problem,monkey group individuals are firstly encoded with natural numbers,and then the infeasible solution is processed through repair and optimization method to ensure the solution effect of the algorithm.The results of simulation experiments on three large-scale bounded knapsack problems show that IMA is capable of obtaining an approximate solution with an approximate ratio close to 1.