求解0-1背包问题的改进树种优化算法

Improved Tree-Seed Optimization Algorithm for 0-1 Knapsack Problem

针对已有算法在求解0-1背包问题方面的不足,提出了一种改进的树种优化算法。基本树种优化算法中,算法容易早熟,难以搜索到全局最优解。改进算法中树木位置没有更新的迭代数超过某个阈值就会被重新初始化,树种会根据新的树木位置进行进一步搜索,提高了种群的多样性和算法的全局搜索能力。为了提高局部搜索能力,改进算法在计算适应度之前都引入贪婪策略来修复不可行解和对可行解局部优化。对4个测试案例进行仿真实验的数据表明,改进树种优化算法比其他4种算法具有更强的全局搜索能力,更高的稳定性和更快的收敛速度。

Aiming at the deficiency of existing algorithms in solving 0-1 knapsack problem,an improved tree-seed optimization algorithm is proposed.In the basic tree-seed optimization algorithm,the algorithm is easy to premature and difficult to find the global optimal solution.In the improved algorithm,if the iteration number of the tree position is not updated beyond a certain threshold,it will be reinitialized,and the tree-seed will further search according to the new tree position,which improves the diversity of the population and the global search ability of the algorithm.In order to improve the local search ability,greedy strategy is introduced to repair the infeasible solution and optimize the feasible solution before calculating the fitness.The simulation results of four test cases show that the improved tree-seed optimization algorithm has stronger global search ability,higher stability and faster convergence speed than the other four algorithms.