论文部分内容阅读
摘要：旅行商问题是典型的NP完全问题，而且在实际生产生活中应用广泛。求解旅行商问题的智能算法也有很多，但目前仍没有很好的算法求解组合优化问题。本文提出一种混合IDA星算法，先使用混合粒子群优化算法在有限迭代内求出一个较优解，再通过此解构造IDA星算法中的估值函数，求解旅行商问题。通过实验分析，此方法达到了较好的效果，为解决旅行商问题提供了一种新思路。
关键词：旅行商问题；混合粒子群优化算法；IDA星算法
旅行商问题（Traveling Salesman Problem，TSP）是一种典型的NP完全组合优化问题。TSP问题可以描述为：一个旅行商人要拜访N个城市，每个城市只能拜访一次，最后要回到出发的城市，求出路程为所有路径之中的最小的路径。TSP问题应用广泛，如焊接机器人焊点路径规划问题，水下清障机器人路径规划问题等都是TSP类问题。
TSP问题的主要求解方法有模拟退火算法、粒子群算法、启发式搜索法等。这些算法各有优劣，目前仍没有一个算法具有很好的综合性能。本文将用混合粒子群算法[2]求解结果构造IDA星算法中的估值函数来求解TSP问题。
1、粒子群算法
粒子群优化（Particle Swarm Optimization，PSO）算法[1]的主要思想是先初始化为一群随机粒子，通过不断迭代找到最优解。在每一次迭代中，粒子通过两个"极值"来更新自己。一个极值是粒子本身当前所找到的最优解，叫做个体极值pBest。另一个极值是群体目前找到的最优解，叫做群体极值gBest。
设D维粒子粒子i在t时刻的位置为Xi=（xi1，xi2，…，xiD），i=1，2，…，N，位置变化率为Vi=（vi1， vi2，…， viD），那么粒子i在t+1时刻的位置按如下公式进行更新：
其中c1，c2取值为正常数；r1，r2为[0，1]之间的随机数；w称惯性因子。
标准PSO是从解决连续优化问题发展起来的，对组合优化这样的离散型问题需要进行改进。目前已经有不少改进方法[3]，文献[2]讲述了一种混合粒子群算法，即将标准PSO算法中的速度更新公式（1式）中的w*vid（t）看做遗传算法中的变异操作，c1*r1*（pid（t）-xid（t））+ c2*r2*（pgd（t）-xid（t））看做当前个体分别与pBest和gBest个体的交叉操作。变异和交叉操作后，新的解可能比原来的解要坏，接受准则是采用类似模拟退火算法的思想，按概率进行取舍。本文所用PSO算法采用的交叉和变异策略分别为：区域交叉策略和随机两点间的子编码段倒序策略。
2、混合IDA星算法
2.1IDA星算法
IDA星算法是A*算法和迭代加深算法的结合，由Korf在1985年提出。其主要思路是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解。IDA星算法可以有效解决A星算法耗费空间多、计算时间长的问题。
2.2混合IDA星算法
IDA星算法中的初始上限值如果设置过大，搜索空间太大影响求解效率，但是设置太小又求解不出最优解。所以初始上限值的设置关系求解效率。本文中将先使用混合粒子群算法在有限条件（如有限代数或者有限时间）下求解出一个较优解S，以此构造估值函数中的h（n），再使用IDA星进行迭代求解。在IDA星中设置迭代代数，每一次迭代如果求解出更优的解则更新S为更优的结果，进行下一次迭代。这里称之为混合IDA星算法。
估值函数中h（n）的计算方法为：从S中从当前扩展节点开始依次循环查找所有的未扩展节点组成作为剩余节点的访问列表，计算此访问列表的代价作为估计值。
算法伪码如下：
初始解S= PSO（）；//使用离散PSO算法在1000代内的求解结果
3、仿真实验
实验中混合PSO算法和混合IDA星算法的求解时间相差不多，而从实验结果可知，混合IDA算法的求解结果比混合PSO算法迭代5000次的结果要好。
结语
本文提出了一个用混合IDA星求解旅行商问题的新思路。首先用混合粒子群算法求解出一个较优解，再通过此较优解构造IDA星算法的估值函数，求解旅行商问题。仿真实验的结果显示此方法参数设置简单，求解效果较好。鉴于PSO算法的研究还处于早期，未来还有更多工作需要进一步开展。
参考文献（References）：
[1]Eberhart R.C， Kennedy J. A new optimizer using particles swarm theory [A]. Proc Sixth
Int Symposium On Micro Machine and HumanScience[C]. Nagoya， 1995. 39-43.
[2]高尚，韩斌，吴小俊等.求解旅行商问题的混合粒子群优化算法[J].控制与决策，2004， 19（11）：1286-1289.
[3]李建勇.粒子群优化算法研究[D].杭州：浙江大学，2004.
关键词：旅行商问题；混合粒子群优化算法；IDA星算法
旅行商问题（Traveling Salesman Problem，TSP）是一种典型的NP完全组合优化问题。TSP问题可以描述为：一个旅行商人要拜访N个城市，每个城市只能拜访一次，最后要回到出发的城市，求出路程为所有路径之中的最小的路径。TSP问题应用广泛，如焊接机器人焊点路径规划问题，水下清障机器人路径规划问题等都是TSP类问题。
TSP问题的主要求解方法有模拟退火算法、粒子群算法、启发式搜索法等。这些算法各有优劣，目前仍没有一个算法具有很好的综合性能。本文将用混合粒子群算法[2]求解结果构造IDA星算法中的估值函数来求解TSP问题。
1、粒子群算法
粒子群优化（Particle Swarm Optimization，PSO）算法[1]的主要思想是先初始化为一群随机粒子，通过不断迭代找到最优解。在每一次迭代中，粒子通过两个"极值"来更新自己。一个极值是粒子本身当前所找到的最优解，叫做个体极值pBest。另一个极值是群体目前找到的最优解，叫做群体极值gBest。
设D维粒子粒子i在t时刻的位置为Xi=（xi1，xi2，…，xiD），i=1，2，…，N，位置变化率为Vi=（vi1， vi2，…， viD），那么粒子i在t+1时刻的位置按如下公式进行更新：
其中c1，c2取值为正常数；r1，r2为[0，1]之间的随机数；w称惯性因子。
标准PSO是从解决连续优化问题发展起来的，对组合优化这样的离散型问题需要进行改进。目前已经有不少改进方法[3]，文献[2]讲述了一种混合粒子群算法，即将标准PSO算法中的速度更新公式（1式）中的w*vid（t）看做遗传算法中的变异操作，c1*r1*（pid（t）-xid（t））+ c2*r2*（pgd（t）-xid（t））看做当前个体分别与pBest和gBest个体的交叉操作。变异和交叉操作后，新的解可能比原来的解要坏，接受准则是采用类似模拟退火算法的思想，按概率进行取舍。本文所用PSO算法采用的交叉和变异策略分别为：区域交叉策略和随机两点间的子编码段倒序策略。
2、混合IDA星算法
2.1IDA星算法
IDA星算法是A*算法和迭代加深算法的结合，由Korf在1985年提出。其主要思路是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解。IDA星算法可以有效解决A星算法耗费空间多、计算时间长的问题。
2.2混合IDA星算法
IDA星算法中的初始上限值如果设置过大，搜索空间太大影响求解效率，但是设置太小又求解不出最优解。所以初始上限值的设置关系求解效率。本文中将先使用混合粒子群算法在有限条件（如有限代数或者有限时间）下求解出一个较优解S，以此构造估值函数中的h（n），再使用IDA星进行迭代求解。在IDA星中设置迭代代数，每一次迭代如果求解出更优的解则更新S为更优的结果，进行下一次迭代。这里称之为混合IDA星算法。
估值函数中h（n）的计算方法为：从S中从当前扩展节点开始依次循环查找所有的未扩展节点组成作为剩余节点的访问列表，计算此访问列表的代价作为估计值。
算法伪码如下：
初始解S= PSO（）；//使用离散PSO算法在1000代内的求解结果
3、仿真实验
实验中混合PSO算法和混合IDA星算法的求解时间相差不多，而从实验结果可知，混合IDA算法的求解结果比混合PSO算法迭代5000次的结果要好。
结语
本文提出了一个用混合IDA星求解旅行商问题的新思路。首先用混合粒子群算法求解出一个较优解，再通过此较优解构造IDA星算法的估值函数，求解旅行商问题。仿真实验的结果显示此方法参数设置简单，求解效果较好。鉴于PSO算法的研究还处于早期，未来还有更多工作需要进一步开展。
参考文献（References）：
[1]Eberhart R.C， Kennedy J. A new optimizer using particles swarm theory [A]. Proc Sixth
Int Symposium On Micro Machine and HumanScience[C]. Nagoya， 1995. 39-43.
[2]高尚，韩斌，吴小俊等.求解旅行商问题的混合粒子群优化算法[J].控制与决策，2004， 19（11）：1286-1289.
[3]李建勇.粒子群优化算法研究[D].杭州：浙江大学，2004.