基于改进探路者算法求解0-1背包问题  

The solution of 0-1 knapsack problem based on improved pathfinder algorithm

作　　者：张小萍[1] 谭欢 ZHANG Xiaoping;TAN Huan(College of Computer and Electronic Information,Guangxi University,Nanning 530004,China;China Mobile Group Guangxi Co.,Ltd.,Nanning 530022,China)

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004 [2]中国移动通信集团广西有限公司,广西南宁530022

出　　处：《邵阳学院学报（自然科学版）》2022年第1期1-7,共7页Journal of Shaoyang University：Natural Science Edition

基　　金：国家自然科学基金(61962005)。

摘　　要：为了有效地求解0-1背包问题,提出了改进探路者算法(IPFA)。首先,对种群个体进行二进制编码,把连续问题变为离散问题,然后,使用探路者算法进行寻优,并结合贪心修复与优化算法(greedy repair and optimization algorithm,GROA)修复不可行解和对解进行优化,通过变异策略来增加种群的多样性。仿真实验结果表明,提出算法比其他3个算法具有更好的全局寻优能力、更快的收敛速度和较强的稳定性。In order to effectively solve the 0-1 knapsack problem,an improved pathfinder algorithm is proposed.Firstly,the population individuals are binary coded to change the continuous problem into a discrete problem,and then the pathfinder algorithm is used for optimization,combined with greedy repair and optimization algorithm to repair,the infeasible solution and optimize the solution,so as to increase the diversity of the population through mutation strategy.Simulation results show that the proposed algorithm has better global optimization ability,faster convergence speed,and stronger stability than the other three algorithms.

关 键 词：0-1背包问题 探路者算法 贪心算子 变异策略 二进制编码 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]