CAJ | 학술논문

针对蚁群算法在求解大规模旅行商问题(Traveling Salesman Problems,TSP)中时间性能方面的不足,提出了一种快速的求解算法.首先,从TSP问题描述入手,给出了一种新的多粒度的问题描述模型;然后,基于该模型,设计了包括基于密度聚类的粒度划分、粗粒度的蚁群寻优、粒度间的连接、细粒度的蚁群寻优、粒度间可行解的合成以及循环分段优化6个阶段在内的求解算法.算法的复杂度分析及在中、大规模TSP问题上的实验表明:本算法的时间性能不仅比经典的蚁群算法有显著的提高,而且与近年来的一些同类算法相比也具有一定的优势,显示了快速求解大规模TSP问题的能力.
침대의군산법재구해대규모여행상문제(Traveling Salesman Problems,TSP)중시간성능방면적불족,제출료일충쾌속적구해산법.수선,종TSP문제묘술입수,급출료일충신적다립도적문제묘술모형;연후,기우해모형,설계료포괄기우밀도취류적립도화분、조립도적의군심우、립도간적련접、세립도적의군심우、립도간가행해적합성이급순배분단우화6개계단재내적구해산법.산법적복잡도분석급재중、대규모TSP문제상적실험표명:본산법적시간성능불부비경전적의군산법유현저적제고,이차여근년래적일사동류산법상비야구유일정적우세,현시료쾌속구해대규모TSP문제적능력.
Ant colony optimization (ACO) is a population-based metaheuristic technique to effectively solve combination optimization problems.However,it is still an active research topic how to improve the performance of ACO algorithms.Though there are many algorithms to effectively solve traveling salesman problems (TSPs),there is an application bottleneck that the ACO algorithm costs too much time in order to get an optimal solution.To improve the time performance of ACO in solving large scale TSPs,a fast algorithm is presented in this paper.Firstly,a novel multiple-grain representation model of TSPs is proposed.Based on the model,a new algorithm for TSPs is presented,which mainly contains six phases,i.e.a granularity partition algorithm based on density clustering,an ACO algorithm based on the coarse grain,a connection algorithm between two granularities,an ACO algorithm in the same granularity,a fusion algorithm among granularities,and a subsection optimization algorithm regardless of granularities.The analysis of computation complexity and the experimental results for large number of TSPs demonstrate that the proposed algorithm can greatly improve the speed of convergence in contrast to the classical ACO algorithm,and is highly competitive in time performance compared with some latest elitist ACO algorithms.