中科携手共抗白癜风 http://www.txbyjgh.com/index.html
写了遗传算法的原理，这一篇写遗传算法解决旅行商问题的实战，而且使用python编写。近几年python越来越受欢迎，其中主要是简单易学和上手快，并且编代码的效率高，甚至有人喊出“人生苦短，我要用python”的口号，所以小编也来凑凑热闹。旅行商问题旅行商是一个组合优化问题，是一个经典的NP-hard问题，也就是不能在一个可接受的时间范围内得到最优解的问题。旅行商的问题来自一位商人，这位商人需要从一座城市出发，游历每一个城市最后回到出发的城市，商人希望整个游历路径最短。假如现在有A、B、C、D、F、E、G，七个城市并且两两城市之间的距离已知。如果从A出发，那么A-D-B-C-G-E-F-A就是一条游历的路径，并且可以得知其中的总距离，那么怎么样的路径组合才是最短的路径？每个路径的排列都计算一次路径，找到最短的路径，这样的时间复杂度为O(n!)，当n很大时，出现“知数爆炸”问题。骆驼商人实战结果图中一共16座城，城市的坐标为：x=[0,1,3.7,3,4,2.3,4,5.5,4,3,2,1,0,10,0,9.6]y=[0,8.0,0,4,0,1,3.6,3,7.3,4,9.6,4,8.6,6.1,2,1]在次迭代的时候取得较优解，优解的距离为41.4，将优解换算为城市的坐标点，得到完整的路线图。优解路线图1优解路线图2随着迭代次数增加，即不断的遗传进化，启发式的向最优解靠近，渐渐的距离减小，过程虽然曲折。由于初始的路线是随机生成的，每一次的计算结果都不一样，找到的最好的解也不一样，有时陷入局部最优解，有时甚至可以得到全局最优解。随着迭代次数增加，距离减小算法过程遗传算法是不断迭代的过程，其中只有达到了迭代的次数或者解的精度才可以跳出迭代，迭代的过程中总是不断的进行选择、交叉和变异。计算适应度函数就是不断维护fitness矩阵，其中第一列为适应度，第二列为选择概率，第三列为累计概率。计算适应度函数主要是为下面的选择函数准备好数据。计算适应度函数选择函数是通过轮盘赌的方式将遗传的下一代选择，并且选择的时候适应度强的个体被选中的概率按比例增大，数据主要来自fitness矩阵。选择函数交叉函数将两个个体的染色体相同位置的相同长度的基因互换，交叉之后会产生重复的表现型，代码中的处理方法是，将两段交叉的基因中重复的数字去掉，剩下的数字于未交叉的数字映射去重。交叉函数相对来说变异的处理十分简单，随机选择一个个体，互换两个位置上的数字就可以了。变异函数百家号上不能上传代码，有点难受呀，只能截图了。已经上传到Github,但是这里不能放链接。本文的版权归算法卡农所有，抄袭等侵权行为必究！喜欢我的话，加个

转载请注明:http://www.aideyishus.com/lkyy/7342.html