融合盈亏拿取策略的改进遗传算法求解TTP

打开文本图片集

关键词：旅行商问题；背包问题；旅行小偷问题；改进遗传算法；盈亏拿取策略中图分类号：TP301.6 文献标志码：A 文章编号：1001-3695（2025）08-021-2408-08doi：10.19734/j. issn.1001-3695.2024.12.0489

Improved genetic algorithm incorporating profit-loss picking strategy for solving TTP

Jiang Xiaojua，b，c，TanDailuna，b，c†，Feng Shiqianga，b，c （aSchoolofthaic&foatonCs&UesiKboatofOiAsie ofNonlinear Analysis & Applications，China WestNormal University，Nanchong Sichuan 637o09，China）

Abstract：TTPisanew typeofcombinatorialoptimizationproblem，which iscomposedof TSPandKP.Itsoptimizationmodelcovers theconstraintsofthetwokindsofproblemsandalsoinheritsthecomputationaldifiultyof thetwo kindsof problems.To solvetheTTP，thispaper proposedanimprovedgeneticalgorithm incorporating profit-losspicking strategy.Forthe listof itemsontheroadofanytraveler，itdefinedthevalueitemsandadoptedthe must-takestrategy，definedtheloss items fortheremaining itemsandeliminated them，introducedthedoublescorecalculation formulafortheeliminatedremaining items，andconductedcomprehensivesortingaccording tothemixed sorting strategy，andthenselected themintothebackpack inorder.Thewhole procesingproessconstitutedtheprofit-loss takingstrategyForthegeneticalgorithm，thispaper designedthestrategyofpopulation initializationbasedonnarestneighborsearchandtruncationexchange to improvethequalityoftheinitialpopulation.Itusedthestochasticuniversalsamplingselectionoperator，thepartialmatchingcrossoveroperator andthesecondarymutationoperatortostrengthensurvivalofthefitestandmaintainthediversityofthepopulation.Itadded reinsertionoperatorsto keep thepopulation stable.Thesimulationresultsshow thattheimprovedstrategycanobviously improvetheperformanceof thealgorithm，andtheresultof theexamplereachestheexpectation.Theimprovedalgorithmhas good optimization ability and stability.

Key words：traveling salesman problem（TSP）;knapsack problem（KP）；travel thief problem（TTP）;improved genetic algorithm；profit-loss picking strategy

0 引言

旅行小偷问题（TTP）是组合优化领域一个有趣且具有挑战性的问题。（剩余18677字）