论文部分内容阅读
摘 要:本文提出了求解旅行商问题(TSP)的一个改进的单亲遗传算法。首先,定义了距离系数的概念,并据此设计了一种新的贪心基因段交换算子;同时结合一个模拟退火和2OPT局部搜索技术来改进该算子;然后,在此基础上提出了一个求解旅行商问题的一个新的单亲遗传算法。计算机仿真结果表明,该算法是有效的。
关键词:单亲遗传算法TSP贪心基因段交换算子
中图分类号:N1 文献标识码:A 文章编号:1674-098X(2011)07(a)-0231-01
旅行商问题(Traveling Salesman Problem,简记为TSP)是一个典型的,易于描述却难以处理的ＮＰ完全问题[1～2]。有效的解决TSP问题在可计算理论上有着重要的价值;同时TSP问题又是诸多领域内出现的多种复杂问题的集中概括和简化形式;因此快速、有效地解决TSP问题有着极高的实际应用价值。目前,TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准。
遗传算法是一种自适应全局优化概率搜索算法。该算法利用生物进化和遗传思想实现优化过程,能够有效地解决组合优化问题。但遗传算法在这类问题的应用上,都是在一定发生概率的条件下,随机地、没有指导地迭代搜索;因此它们在为群体中的个体提供了进化机会的同时,也无可避免地产生了退化的可能。在某些情况下, 这种退化现象还相当明显。由于不能确保群体的多样性,容易出现早熟现象。
针对序号编码GA的上述不足,单亲遗传算法(PGA)[3～4]采用序号编码,不使用交叉算子,而代之以隐含序号编码GA交叉算子功能的基因换位等遗传算子,简化了遗传操作。实验证明,单亲遗传算法(PGA)采用序号编码,仅在一条染色体上进行遗传操作,简化了遗传操作过程,提高了计算效率,一定程度上避免了早熟收敛。本文在单亲遗传算法的基础上设计的贪心基因段交换算子充分利用了连接城市之间距离的信息,结合局部搜索技术,大大地提高了收敛速度,减少了信息损失。
1 单亲遗传算法
通过对多个TSP问题解的特征研究,我们发现每一个可行解中都存在着一些的局部较优路径。而最优解是由多个局部较优路径组合而成的。简单的说,它们之间存在着相互冲突。最优解正是它们相互竞争又相互妥协的结果,也就是说,它们最大限度的依存产生了最优特性。因此,本文提出了贪心基因段交换算子,从父代个体中构造子代个体,但是尽量保留那些较好的基因片断。
1.1 新的贪心基因段交换算子
PGA的基因换位算子是指按一定的概率P交换一条染色体中的某两个(些)位置基因的过程。PGA的贪心基因段交换算子是指按一定的概率P把一条染色体中的某个(些)串中的基因在贪心思想的指导下重新首尾倒置连接的过程。被交换的子串及其长度是随机选取的。
1.2 局部搜索算子
在旅行商问题中比较有名的用于局部搜索的算法就是2OPT(二段优化)[5～6]。它是通过路径的每条边和反转子路径来实现较优解的搜索的。2OPT不仅仅是一个变异操作。使用2OPT的思想基于它既能够通过交换两边来进行变异,又能够作为局部搜索算法,从而一定程度上解决基本遗传算法的局部搜索能力差的缺陷。在本文中我们采取的是以模拟退火[5～6]控制降温的速度进行2OPT操作。
1.3 算法步骤
算法1
(1)TSP问题初始化,确定迭代代数、种群规模和设置退出条件。
(2)设置初始迭代次数,判断当前迭代次数是否小于设定的迭代次数。
(3)依次选取一个染色体进行如下操作:
1)对选择染色体采用贪心基因段交换算子进行操作
2)以模拟退火控制降温的速度对新构造的染色体的进行2OPT操作
3)返回3
4)是否达到设定的退出条件,没达到返回2
2 实验结果和讨论
本文选取文献http://www.iwr.uniheidelhergde/groups/vomopt/software/TSPL1B95的标准问题进行测试。本文中对这些问题连续进行了30次计算。计算机仿真结果见表1。
从表1可以看出本文算法在求解TSP问题上是有效的。在小规模TSP问题中本文算法在较小的种群规模和迭代次数就已经达到了问题的最优解,由于Att48问题的复杂性本文算法在100次迭代中获得了26次最优解。
3 结语
本文在分析TSP问题的基础上对传统的遗传算法和单亲遗传算法进行了比较,定义了好基因段和距离系数的概念,并据此设计了一种新的贪心基因段交换算子;同时结合一个模拟退火和2OPT局部搜索技术来改进该算子;然后,在此基础上提出了一个求解旅行商问题的一个新的单亲遗传算法。计算机仿真结果表明,该算法是有效的。但对于用遗传算法求解TSP,还存在许多问题有待于进一步地深入研究。比如如何更好的对大规模TSP问题进行求解。另外,本文算法也可以给其它优化问题的求解提供参考。
参考文献
[1] D Applexgate,RBixby,V Chvatal,et al.Implementing the Dantzig- Fulkerman-Johnson Algorithm for Large Traveling Salesman Problems[J].MathematicalProgramming,2003,97(122):91～153.
[2] SJung,BRMoon.To ward Minimal Restriction of Genetic Codingand Crossovers for the 2-D Eunclidean TSP[J].IEEE Transon Evolutionary Computation,2002,6(6):557～565.
[3] 李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究[J].湖南大学学报(自然科学版),1998,25(6):56～59.
[4] 陈俊红,黄丽华.基于配电网络规划的优化算法的研究[J].微计算机信息,2006,4(3):293～295.
[5] Gunter Dueck,Tobias Scheuer.Threshold Accepting:A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing[J].Journal of Computation Physics,1990,90(1):161～175.
关键词:单亲遗传算法TSP贪心基因段交换算子
中图分类号:N1 文献标识码:A 文章编号:1674-098X(2011)07(a)-0231-01
旅行商问题(Traveling Salesman Problem,简记为TSP)是一个典型的,易于描述却难以处理的ＮＰ完全问题[1～2]。有效的解决TSP问题在可计算理论上有着重要的价值;同时TSP问题又是诸多领域内出现的多种复杂问题的集中概括和简化形式;因此快速、有效地解决TSP问题有着极高的实际应用价值。目前,TSP问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准。
遗传算法是一种自适应全局优化概率搜索算法。该算法利用生物进化和遗传思想实现优化过程,能够有效地解决组合优化问题。但遗传算法在这类问题的应用上,都是在一定发生概率的条件下,随机地、没有指导地迭代搜索;因此它们在为群体中的个体提供了进化机会的同时,也无可避免地产生了退化的可能。在某些情况下, 这种退化现象还相当明显。由于不能确保群体的多样性,容易出现早熟现象。
针对序号编码GA的上述不足,单亲遗传算法(PGA)[3～4]采用序号编码,不使用交叉算子,而代之以隐含序号编码GA交叉算子功能的基因换位等遗传算子,简化了遗传操作。实验证明,单亲遗传算法(PGA)采用序号编码,仅在一条染色体上进行遗传操作,简化了遗传操作过程,提高了计算效率,一定程度上避免了早熟收敛。本文在单亲遗传算法的基础上设计的贪心基因段交换算子充分利用了连接城市之间距离的信息,结合局部搜索技术,大大地提高了收敛速度,减少了信息损失。
1 单亲遗传算法
通过对多个TSP问题解的特征研究,我们发现每一个可行解中都存在着一些的局部较优路径。而最优解是由多个局部较优路径组合而成的。简单的说,它们之间存在着相互冲突。最优解正是它们相互竞争又相互妥协的结果,也就是说,它们最大限度的依存产生了最优特性。因此,本文提出了贪心基因段交换算子,从父代个体中构造子代个体,但是尽量保留那些较好的基因片断。
1.1 新的贪心基因段交换算子
PGA的基因换位算子是指按一定的概率P交换一条染色体中的某两个(些)位置基因的过程。PGA的贪心基因段交换算子是指按一定的概率P把一条染色体中的某个(些)串中的基因在贪心思想的指导下重新首尾倒置连接的过程。被交换的子串及其长度是随机选取的。
1.2 局部搜索算子
在旅行商问题中比较有名的用于局部搜索的算法就是2OPT(二段优化)[5～6]。它是通过路径的每条边和反转子路径来实现较优解的搜索的。2OPT不仅仅是一个变异操作。使用2OPT的思想基于它既能够通过交换两边来进行变异,又能够作为局部搜索算法,从而一定程度上解决基本遗传算法的局部搜索能力差的缺陷。在本文中我们采取的是以模拟退火[5～6]控制降温的速度进行2OPT操作。
1.3 算法步骤
算法1
(1)TSP问题初始化,确定迭代代数、种群规模和设置退出条件。
(2)设置初始迭代次数,判断当前迭代次数是否小于设定的迭代次数。
(3)依次选取一个染色体进行如下操作:
1)对选择染色体采用贪心基因段交换算子进行操作
2)以模拟退火控制降温的速度对新构造的染色体的进行2OPT操作
3)返回3
4)是否达到设定的退出条件,没达到返回2
2 实验结果和讨论
本文选取文献http://www.iwr.uniheidelhergde/groups/vomopt/software/TSPL1B95的标准问题进行测试。本文中对这些问题连续进行了30次计算。计算机仿真结果见表1。
从表1可以看出本文算法在求解TSP问题上是有效的。在小规模TSP问题中本文算法在较小的种群规模和迭代次数就已经达到了问题的最优解,由于Att48问题的复杂性本文算法在100次迭代中获得了26次最优解。
3 结语
本文在分析TSP问题的基础上对传统的遗传算法和单亲遗传算法进行了比较,定义了好基因段和距离系数的概念,并据此设计了一种新的贪心基因段交换算子;同时结合一个模拟退火和2OPT局部搜索技术来改进该算子;然后,在此基础上提出了一个求解旅行商问题的一个新的单亲遗传算法。计算机仿真结果表明,该算法是有效的。但对于用遗传算法求解TSP,还存在许多问题有待于进一步地深入研究。比如如何更好的对大规模TSP问题进行求解。另外,本文算法也可以给其它优化问题的求解提供参考。
参考文献
[1] D Applexgate,RBixby,V Chvatal,et al.Implementing the Dantzig- Fulkerman-Johnson Algorithm for Large Traveling Salesman Problems[J].MathematicalProgramming,2003,97(122):91～153.
[2] SJung,BRMoon.To ward Minimal Restriction of Genetic Codingand Crossovers for the 2-D Eunclidean TSP[J].IEEE Transon Evolutionary Computation,2002,6(6):557～565.
[3] 李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究[J].湖南大学学报(自然科学版),1998,25(6):56～59.
[4] 陈俊红,黄丽华.基于配电网络规划的优化算法的研究[J].微计算机信息,2006,4(3):293～295.
[5] Gunter Dueck,Tobias Scheuer.Threshold Accepting:A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing[J].Journal of Computation Physics,1990,90(1):161～175.