APP下载

基于信息素矩阵优化蚁群算法求解城市建模的旅行商问题

2025-08-03刘岱张亚鸣王凯崔海青

计算机应用研究 2025年6期
关键词:重置扰动局部

Travelling salesman of urban modeling based on pheromone matrix optimization ant colony algorithm

Liu Daia,Zhang Yamingʰ,Wang Kaib,Cui Haiqingh† (a.EngineegnCteFlfocftoutoatoltionUsitof 300000,China)

Abstract:This paper proposedanoptimizedantcolonyalgorithm toaddressthe traveling salesman problem(TSP)inurban modeling.Thealgorithmintegratedrandomaveragingofthepheromone matrix,adaptiveperturbation,anddynamicproportional resetingstrategies tooptimizethepath search intheprocessof acquiringurban modeling materials.Aftereachroundof path selection,thealgorithmgloballyupdatedthelocalpheromonebasedonthequalityof thepathsandacceleratedconvergence through2-optoptimization.Initialy,itappliedtherandomaveraging strategy.When theoptimalpathhadnotbeenupdated formultiple iterations,thepheromoneofrandom nodes wasaveraged toavoidlocaloptima.Whenmultipleatemptsattherandomaveraging strategyproveinefective,itintroducedtheadaptiveperturbationstrategy.Thisstrategyperturbedtheperomone matrix toselectpaths,therebyreducing theriskoflocal optima.This strategyperturbedthepheromonematrix toselect paths,reducingtheriskoflocaloptima.Whenthequalityof theoptimalpathdecreases byacertain proportion,itusedthe dynamicproportionalresetingstrategytoincreasethediferencebetweenhighandlowpheromonevaluesinthematrix,further accelerating convergence.Theresultsshowthatthealgorithm efectivelyimprovesglobal search capability,acelerates the convergence process,and provides a solution to the TSP in urban modeling.

Key words:antcolonyalgorithm;traveler’ssalesmanproblem;combinatorial optimization;2-optalgorithm;urban 3D modeling

0 引言

随着城市场景丰富和城市系统扩大,城市管理进人新阶段。城市模型在规划设计[1]、交通管理[2]和应急管理[3]等领域发挥重要作用,作为数字化城市的视觉表现。其通过模拟城市空间、结构和功能,为决策者提供关键信息和可视化参考。

现有高精度城市建模方法包括:基于多数据源的人工交互建模、基于影像和激光扫描点云的半自动建模,以及倾斜摄影建模[4]。这三种建模方法的共同特点是需对物体进行完整拍摄,覆盖所有最佳拍摄点并确保每个点至少拍摄一次,最终返回初始点,构成组合优化中的经典问题—旅行商问题(trave-ling salesmanproblem,TSP)[5]。其中,文献[6\~8]完成城市建模拍摄视点规划后,分别采用随机重启的2-opt算法、改进快速随机探索树算法和改进 A* 算法进行TSP路径规划。但是这些方法仍具有一定的局限性,未能深人开发优化路径规划的潜力。为此,提出新的方法进行补充开发,以提高城市建模中TSP的优化性能。

当前求解TSP的算法主要分为精确算法和近似算法。尽管精确算法能够提供最优解,但由于其计算量庞大[9,往往无法在实际问题中实现理想效率。因此,在大多数实际应用中,近似算法通常被优先选择,作为TSP的解决方案[10]。

近似算法中,蚁群算法(antcolonyoptimization,ACO)是一种受自然界蚂蚁觅食行为启发的元启发式近似算法,自20世纪90年代提出以来,因其良好的性能和灵活性被广泛应用于TSP的求解,进而被广泛应用于物流配送[11]、印刷电路板设计[12]和网络路由[13]等领域。蚁群算法通过模拟蚂蚁在路径上释放和追踪信息素(pheromone),逐步优化路径选择[14]。……

登录APP查看全文

猜你喜欢

重置扰动局部
白头发到底能不能拔
湖北省2025年下半年农作物病虫害发生趋势
煤矿局部通风机双停事故预防与智能运维
肛肠术后中药熏洗的作用及注意事项
基于多扰动策略的中文对抗样本生成方法
病人
信息互补的锐度感知最小化的标签噪声学习
系统重置中途出错的解决办法
重置人生 ①