摘要
TSP问题是典型的NP-hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法,利用遗传算法生成信息素的分布,克服了蚁群算法中搜索时间长的缺陷。此外,在蚁群算法寻优中,采用交叉和变异的策略,改善了TSP解的质量。仿真结果显示,改进的蚁群算法是有效的。
TSP is a classical NP-hard combinatorial optimization. There are some drawbacks such as long time searching and fall into local optimal solution. This paper presents an optimized algorithm for solving TSP. The proposed algorithm combines the ant colony algorithm and genetic algorithm. It uses GA to generate the distribution of pheromone.In addition, in the ant colony algorithm, the crossover and mutation strategies is used to improve the quality of TSP solution. The simulation result shows that the improved algorithm optimizes the TSP in time and performance.
出处
《自动化技术与应用》
2010年第7期1-3,共3页
Techniques of Automation and Applications
关键词
蚁群算法
遗传算法
TSP问题
ant colony algorithm
genetic algorithm
TSP optimization