遗传算法编程求解tsp问题

《遗传算法编程求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法编程求解TSP问题摘要本文利用基本遗传算法的思路寻找双峰或多峰函数的最大值，选择仍然采用轮盘选择方法；交叉算法采用一个启发式交叉算法，交叉位置随机，该算法以一定的概率生成一个比父代好的解，交叉概率取0.1；变异概率0.005。经多次运行，求得最优值。停止法则为循环最大遗传代数为止，另外如果30代解没有改进则停止。的编程环境为Matlab6.5。关键字遗传算法TSP遗传算法是一种通用性非常强，计算性能非常好的算法，解决TSP问题却存在很多问题，主要问题是解的可行性问题，在交叉，变异操作过程中，可能产生不可行的解，因此交叉和变异算子的设计是本程序的关键。

2、本程序中交叉算子采用一个启发式交叉算法，该算法以一定概率计算出一个比父代好的子代算法思路：设父代F1：10432978156F2：91352678410。随机确定交叉点，如4。查找F1中第四位为2。将F1向左旋转3位，使第四位在成为第一位，得到F1：29781561043。在F2中找到2所在位置，进行类似旋转，使2成为第一位，得到F2：26784109135。然后比较两个模式中第一位与第二位的距离：disance(2-9)，disance(2-6)，取比较小的如2-6所在父代F2不变，另外一个为，将F1进行旋转操作，使6在第2位，得到F2:：26104397

3、815。这样就形成了26*********的模式，如此往复，直到最后一位。另外将这个交叉算子的效率和普通单点交叉算子的效率进行了比较，发现该方法确实使得算法搜索能力增强。多次运行程序，得到一个相对好的解。以下是得到最优解的数据：代数最优值平均值--------------------------最优解---------------------------12625085719264810324145105928137410633855127110234895644165094711082953654095117510134892664165044711082

4、953674035056109817253484165134711082953694455061046589237110414509487110532961145349548716523910123854957110234895613440518579210368411442150048711062395154224994810175239616421512487110623951742150848711062395183765047610234891519421493487110623952042149148711062395214214904871106

5、239522421485487110623952338549171102348956242864814871952310625286462487195231062628641848719523106272864044871952310628286398487195231062928641348719523106302864014871952310631286418487195231063228644448719523106332864214871952310634286409487195231063528639848719523106362574164871

6、952610337286411487195231063828637548719523106392573924871952610340257380487195261034125737048719526103422573814871952610343257380487195261034424631548719253106452643004871953210646264298487195321064728629848719523106482642964871953210649264299487195321065026429648719532106512643244

7、871953210652264305487195321065326432248719532106542643314871953210655264310487195321065626429448719532106572643004871953210658264309487195321065926429748719532106602643164871953210661264336487195321066226433448719532106632643504871953210664264331487195321066526431548719532106662643

8、33487195321066724631848719