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

【Abstract】 TTP is a new type of combinatorial optimization problem, which is composed of TSP and KP. Its optimization mo-del covers the constraints of the two kinds of problems and also inherits the computational difficulty of the two kinds of problems. To solve the TTP, this paper proposed an improved genetic algorithm incorporating profit-loss picking strategy. For the list of items on the road of any traveler, it defined the value items and adopted the must-take strategy, defined the loss items for the remaining items and eliminated them, introduced the double score calculation formula for the eliminated remaining items, and conducted comprehensive sorting according to the mixed sorting strategy, and then selected them into the backpack in order. The whole processing process constituted the profit-loss taking strategy. For the genetic algorithm, this paper designed the strategy of population initialization based on nearest neighbor search and truncation exchange to improve the quality of the initial population. It used the stochastic universal sampling selection operator, the partial matching crossover operator and the secondary mutation operator to strengthen survival of the fittest and maintain the diversity of the population. It added reinsertion operators to keep the population stable. The simulation results show that the improved strategy can obviously improve the performance of the algorithm, and the result of the example reaches the expectation. The improved algorithm has good optimization ability and stability.更多还原