当前位置：搜档网 › 求解旅行商问题混合IDA星算法

求解旅行商问题混合IDA星算法

求解旅行商问题的混合IDA星算法

摘要：旅行商问题是典型的np完全问题，而且在实际生产生活中应用广泛。求解旅行商问题的智能算法也有很多，但目前仍没有很好的算法求解组合优化问题。本文提出一种混合ida星算法，先使用混合粒子群优化算法在有限迭代内求出一个较优解，再通过此解构造ida星算法中的估值函数，求解旅行商问题。通过实验分析，此方法达到了较好的效果，为解决旅行商问题提供了一种新思路。关键词：旅行商问题；混合粒子群优化算法；ida星算法

旅行商问题（traveling salesman problem，tsp）是一种典型的np完全组合优化问题。tsp问题可以描述为：一个旅行商人要拜访n个城市，每个城市只能拜访一次，最后要回到出发的城市，求出路程为所有路径之中的最小的路径。tsp问题应用广泛，如焊接机器人焊点路径规划问题，水下清障机器人路径规划问题等都是tsp类问题。

tsp问题的主要求解方法有模拟退火算法、粒子群算法、启发式搜索法等。这些算法各有优劣，目前仍没有一个算法具有很好的综合性能。本文将用混合粒子群算法[2]求解结果构造ida星算法中的估值函数来求解tsp问题。

1、粒子群算法

粒子群优化（particle swarm optimization，pso）算法[1]的主要思想是先初始化为一群随机粒子，通过不断迭代找到最优解。在每一次迭代中，粒子通过两个”极值”来更新自己。一个极值是

求解旅行商问题混合IDA星算法

相关文档

最新文档