改进郭涛算法及其应用研究

《改进郭涛算法及其应用研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进郭涛算法及其应用研究摘要：郭涛算法可能是目前国际上求解TSP问题最快的演化算法之一。算法中提出了一种求解对称TSP问题的高效Inver-over算子，该算子兼有类似遗传算法中的杂交和变异特征，以一定的概率对粒子编码进行自适应序列倒置。文中对Inver-over算子进行改进，使粒子编码得到更加充分的序列倒置；并引入粒子群优化算法的思想以加快算法收敛速度，提高了郭涛算法求解效率。将改进后的郭涛算法应用到罩式退火车间钢卷自动优化组合堆垛，取得了良好的效果。关键词：郭涛算法；Inver-over算子；TSP问题；粒子群优化；组

2、合优化ResearchofModifiedGTAlgorithmandItsApplicationAbstract:TheevolutionalgorithmofGuoTao(GT)algorithmmayhavethehighestspeedofsolvingtheTSP(TravelingSalesmanProblem)atpresent.ThealgorithmincludesaneffectiveInver-overoperatorforsolvingthesymmetricalTSP.Thisoperatorha

3、sattributesofcrossoverandmutationingeneticalgorithm.Basedontheabovecharacteristics,theInver-overoperatorismodifiedtomakethesequenceinversionmoresufficiently.Inaddition,theruleofparticleswarmoptimizationalgorithmisapplied・TheefficiencyofGTalgorithmisimproved・And,th

4、emodifiedGTalgorithmisappliedtoautomaticcombinationstacksofsteelrollandachievesagoodresult.Keywords:GTalgorithm;inver-overoperator;travelingsalesmanproblem;particleswarmoptimization;combinationoptimization1996年，武汉人学郭涛闿士山提出了一•种基于序列倒置(Inver-over)算子的优化算法(简称郭涛算法)，可以理解

5、它为一种高效率的遗传算法。郭涛算法可能是目前国际上求解TSP问题最快的演化算法，该算法思路非常简单只有3个参数：群体规模、随机倒置概率和结束条件，算法中提出了一种求解对称TSP问题的話效Inver-over算了，本文称Z为序列倒置算了。郭涛算法比起其它只是单纯基于杂交算子的算法来说，在求解质量和速度上效果要好很多，主要在于它能够充分利用群体的信息。郭涛算法在求解TSP问题上取得了广泛关注，其对应的序列倒置算子被其他算法所应用于求解TSP问题和类似组合优化问题⑵，很多学者也对郭涛算法参数设置规律进行研究⑶，以及对序列倒置算子

6、进行改进⑷，同时也出现采用序列倒置算子的改进算法及应用I'",例如王玉亭等提出的基于序列倒置算子的离散和声退火算法⑸，危明等提出的基于精英策略的逆序算法⑹，XiaojunBi⑺等提出的基于序列倒置算子的改进蚁群算法。收稿日期:2012-5-22作者简介：安晶(1982-),女,讲师.E-mail:anjing991982@163.com对于小规模TSP问题，Inwover算子效來非常好，但是城市规模一口变人，该算子寻找全局最优的能力就人为下降⑷。这主要是由于该算法的交义算子是一种兼有杂交和变异特征的操作，这种对基因片段进行

7、逆转的操作在算法的前期很容易把有交义的边打开使其不相交，其儿何意义是：不允许边与边之间有交义的现象出现。正是因为这样的操作使算法在询期的收敛速度很快，到了算法的后期，儿乎所有的染色体所表示的解的路径都是没有交义的合法的环形路径了，再进行这种&口的基因片段的逆转操作容易陷入局部蚁优值，因此对现有序列倒置算子进行改进是有深刻意义的。序列倒置算子以一定的概率对染色体序列进行盲目倒置，没有充分利用到有用经验，限制了算法的进化速度。文中详细分析了己有序列倒置算子的特点，并对序列倒置算子进行改进，使粒子编码得到充分的序列倒置。粒子群优

8、化算法(particleswarmoptimization,简称PSO)最早是由Kennedy和Eberhart于1995年提出的跆】，该算法突出的优点是运算速度快和可调参数少。PSO充分利用了各粒子的局部最优和全局最优值，使得种群里优秀基因片段得到继承，可以明显加快收敛速度。木文在郭涛算法中引入粒子群