摘要
针对城市建模中的旅行商问题,提出了一种结合信息素矩阵的随机平均、自适应扰动及动态比例重置为主的优化蚁群算法,从而优化城市建模素材获取过程中的路径搜索。该算法在每轮路径选择后,依据路径优劣进行整体性的局部信息素更新并通过2-opt优化加速收敛。先采用随机平均策略,在最优路径多次未更新时均值化随机节点信息素,避免局部最优;当多次随机平均策略无效时,引入自适应扰动策略,通过扰动信息素矩阵选择路径,减少局部最优风险;当最优路径质量下降一定比例时,采用动态比例重置策略加大信息素矩阵中高低值元素差异,进一步加速收敛。结果表明,所提算法有效提升了全局搜索能力,加快了收敛过程,能有效解决城市建模中的旅行商问题。
This paper proposed an optimized ant colony algorithm to address the traveling salesman problem(TSP)in urban modeling.The algorithm integrated random averaging of the pheromone matrix,adaptive perturbation,and dynamic proportional resetting strategies to optimize the path search in the process of acquiring urban modeling materials.After each round of path selection,the algorithm globally updated the local pheromone based on the quality of the paths and accelerated convergence through 2-opt optimization.Initially,it applied the random averaging strategy.When the optimal path had not been updated for multiple iterations,the pheromone of random nodes was averaged to avoid local optima.When multiple attempts at the random averaging strategy prove ineffective,it introduced the adaptive perturbation strategy.This strategy perturbed the pheromone matrix to select paths,thereby reducing the risk of local optima.This strategy perturbed the pheromone matrix to select paths,reducing the risk of local optima.When the quality of the optimal path decreases by a certain proportion,it used the dynamic proportional resetting strategy to increase the difference between high and low pheromone values in the matrix,further accelerating convergence.The results show that the algorithm effectively improves global search capability,accelerates the convergence process,and provides a solution to the TSP in urban modeling.
作者
刘岱
张亚鸣
王凯
崔海青
Liu Dai;Zhang Yaming;Wang Kai;Cui Haiqing(Engineering Technology Training Center,Civil Aviation University of China,Tianjin 300000,China;Faculty of Electronic Information&Automation,Civil Aviation University of China,Tianjin 300000,China)
出处
《计算机应用研究》
北大核心
2025年第6期1719-1726,共8页
Application Research of Computers
基金
中央高校基本科研业务费资助项目(3122025079)。
关键词
蚁群算法
旅行商问题
组合优化
2-opt算法
城市三维建模
ant colony algorithm
traveler’s salesman problem
combinatorial optimization
2-opt algorithm
urban 3D modeling
