计算机应用研究

作者：江晓菊,谭代伦,冯世强,

单位：西华师范大学a.数学与信息学院;b.最优化理论与应用四川省高校重点实验室;c.非线性及应用研究所,四川南充637009；

关键词：旅行商问题,背包问题,旅行小偷问题,改进遗传算法,盈亏拿取策略,

基金：国家自然科学基金资助项目(42204123)；四川省自然科学基金资助项目(2022NSFSC0558)；教育部产学合作协同育人项目(202102454008)；四川省教育厅重点教改项目(JG2021-959)；西华师范大学研究生教育改革研究项目(2022XM24)；；

旅行小偷问题（TTP）是由旅行商问题（TSP）和背包问题（KP）复合而成的一类新型组合优化问题，其优化模型涵盖了两类问题的约束条件，也继承了两类问题的计算难度。针对TTP，提出了一种融合盈亏拿取策略的改进遗传算法。对任意旅行商回路上的物品列表，定义了超值物品并采取必拿策略，对剩余物品定义了亏本物品并予以剔除，对剔除后的剩余物品引入了双评分计算公式，并按混合排序策略进行综合排序，再依序选入背包，整个处理过程构成盈亏拿取策略。对于遗传算法，设计近邻域搜索和截断交换的种群初始化策略以提升初始种群的质量；采用随机遍历抽样选择算子、部分匹配的交叉算子、二次变异算子以强化优胜劣汰和维护种群的多样性；增加重插入算子以保持种群稳定。仿真实验表明，改进策略明显提升了算法性能，对算例的求解结果达到预期，改进算法具有良好的寻优能力和稳定性。

来源：2025年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2025年第8期