求解TSP的量子遗传算法

《求解TSP的量子遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３０卷第５期计算机学报Ｖｏｌ．３０Ｎｏ．５２００７年５月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＭａｙ２００７求解犜犛犘的量子遗传算法王宇平１）１），２）李英华１）（西安电子科技大学计算机学院西安７１００７１）２）（大连理工大学数学系辽宁大连１１６０２４）摘要量子遗传算法（ＱＧＡ）在求解数值和组合优化问题时效率明显优于传统进化算法，但目前较多被用于求解组合优化的背包问题，为了充分发挥ＱＧＡ的优点，文中用其求解ＴＳＰ这一经典的ＮＰ难问题．首先，文中设计了一种利用几率幅值编码的新的编码方式，即利用几率幅值编码的量子个体与一组向量对应，而此向量又与一条可行路径一一对应．这样的编码方式不

2、仅缩小了种群规模，占用较少内存，所得的解均可行，而且有效地增强了种群的多样性；其次，在量子个体上实施量子杂交，这一操作有利于保留相对较好的基因段；最后，为了加快算法的收敛速度，引入两阶段局部搜索，第一阶段主要针对实例中排列稀疏处的城市进行优化，第二阶段在第一阶段的基础上着重对排列密集处的城市优化．据此，设计了解ＴＳＰ的一个新的高效的ＱＧＡ，并证明了其以概率１收敛到全局最优解；测定算法性能的数值实验数据表明，该算法在种群规模较小，迭代次数较少的情况下就可以收敛到已知最优解．关键词量子遗传算法；量子比特；ＴＳＰ；组合优化中图法分类号ＴＰ１８犃犖狅狏犲犾犙狌犪狀狋狌犿犌犲狀犲狋犻犮犃犾犵狅狉犻狋犺

3、犿犳狅狉犜犛犘１）１），２）ＷＡＮＧＹｕＰｉｎｇＬＩＹｉｎｇＨｕａ１）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犡犻犱犻犪狀犝狀犻狏犲狉狊犻狋狔，犡犻′犪狀７１００７１）２）（犇犲狆犪狉狋犿犲狀狋狅犳犃狆狆犾犻犲犱犕犪狋犺犲犿犪狋犻犮狊，犇犪犾犻犪狀犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔，犇犪犾犻犪狀，犔犻犪狅狀犻狀犵１１６０２４）犃犫狊狋狉犪犮狋Ｑｕａｎｔｕｍｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＱＧＡ）ｗａｓｐｒｏｖｅｄｔｏｂｅｂｅｔｔｅｒｔｈａｎｔｈｅｃｏｎｖｅｎｔｉｏｎａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｏｎｎｕｍｅｒｉｃａｌａｎｄｃｏｍｂ

4、ｉｎａｔｉｏｎａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ，ｂｕｔｉｔｉｓｕｓｕａｌｌｙｕｓｅｄｔｏｓｏｌｖｅｔｈｅｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓｏｆｔｈｅｃｏｍｂｉｎａｔｉｏｎａｌｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｔｉｓａｌｓｏｐｏｓｓｉｂｌｅｔｏｕｓｅｉｔｓｓｔｒｏｎｇａｂｉｌｉｔｙｏｆｅｘｐｌｏｉｔａｔｉｏｎａｎｄｅｘｐｌｏｒａｔｉｏｎｔｏｏｔｈｅｒｄｉｆｆｉｃｕｌｔｐｒｏｂｌｅｍｓ，ｆｏｒｅｘａｍｐｌｅ，ｔｈｅＴＳＰ，ａｃｌａｓｓｏｆＮＰｈａｒｄｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｆｉｒｓｔ，ａｎｅｗｅｎｃｏｄｉｎｇｓｃｈｅｍｅｗｉｔｈｐａｉｒｓｏｆａｍ

5、ｐｌｉｔｕｄｅｓｉｓｄｅｓｉｇｎｅｄ．Ａｑｕａｎｔｕｍｉｎｄｉｖｉｄｕａｌｉｓｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏａｖｅｃｔｏｒ，ａｎｄｔｈｅｖｅｃｔｏｒｉｓｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｔｈｅｕｎｉｑｕｅｖａｌｉｄｔｏｕｒ，ａｎｄｖｉｃｅｖｅｒｓａ．Ｔｈｅａｄｖａｎｔａｇｅｓｏｆｔｈｅｅｎｃｏｄｉｎｇｓｃｈｅｍｅａｒｅｔｈａｔｉｔａｌｗａｙｓｇｅｎｅｒａｔｅｓｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎ，ｕｓｅｓｌｅｓｓｐｏｐｕｌａｔｉｏｎｓｉｚｅａｎｄｓｔｏｒａｇｅ，ａｎｄｃａｎｅｆｆｅｃｔｉｖｅｌｙｅｎｈａｎｃｅｔｈｅｄｉｖｅｒｓｉｔｙｏｆｔｈｅｐｏｐｕｌａｔｉｏｎ．Ｓｅｃｏｎｄ，ｔｈｅｑｕａｎｔ

6、ｕｍｃｒｏｓｓｏｖｅｒｃａｎｍａｉｎｔａｉｎｔｈｅｒｅｌａｔｉｖｅｌｙｇｏｏｄｇｅｎｅｂｌｏｃｋｓ．Ｔｈｉｒｄ，ｔｈｅｔｗｏｐｈａｓｅｌｏｃａｌｓｅａｒｃｈｆｏｒｅｄｇｅｅｖｏｌｖｉｎｇｉｓｉｎｔｅｇｒａｔｅｄｉｎｔｏＱＧＡｔｏａｃｃｅｌｅｒａｔｅｉｔｓｃｏｎｖｅｒｇｅｎｔｓｐｅｅｄ．Ｔｈｅｆｉｒｓｔｐｈａｓｅｉｓｕｓｅｄｔｏｏｐｔｉｍｉｚｅｔｈｅｓｐａｒｓｅｌｙｌｏｃａｔｅｄｃｉｔｉｅｓ，ａｎｄｔｈｅｓｅｃｏｎｄｐｈａｓｅｉｓｕｓｅｄｔｏｏｐｔｉｍｉｚｅｄｅｎｓｅｌｙｌｏｃａｔｅｄｃｉｔｉｅｓ．Ｂａｓｅｄｏｎｔｈｅｓｅ，ａｎｏｖｅｌａｎｄｅｆｆｉｃｉｅｎｔＱＧＡｆｏｒＴＳＰｉｓｐｒｏｐｏ

7、ｓｅｄ，ａｎｄｉｔｓｃｏｎｖｅｒｇｅｎｃｅｔｏｇｌｏｂａｌｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｗｉｔｈｐｒｏｂａｂｉｌｉｔｙｏｎｅｉｓｐｒｏｖｅｄ．Ｔｈｅｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃａｎｆｉｎｄｔｈｅｇｌｏｂａｌｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｗｉｔｈｌｅｓｓｃｏｍｐｕｔａｔｉｏｎａｎｄｅｖｏｌｖｉｎｇｔｉｍｅ．犓犲狔狑狅狉犱狊ｑｕａｎｔｕｍｇｅｎ