多目标遗传算法python,Python编写遗传算法实战
多目标遗传算法python,Python编写遗传算法实战另一条路线。优解路线图1x = [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]在343次迭代的时候取得较优解,优解的距离为41.4,将优解换算为城市的坐标点,得到完整的路线图。
上一篇写了遗传算法的原理,这一篇写遗传算法解决旅行商问题的实战,而且使用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]
在343次迭代的时候取得较优解,优解的距离为41.4,将优解换算为城市的坐标点,得到完整的路线图。
优解路线图1
另一条路线。
优解路线图2
随着迭代次数增加,即不断的遗传进化,启发式的向最优解靠近,渐渐的距离减小,过程虽然曲折。由于初始的路线是随机生成的,每一次的计算结果都不一样,找到的最好的解也不一样,有时陷入局部最优解,有时甚至可以得到全局最优解。
随着迭代次数增加,距离减小
算法过程遗传算法是不断迭代的过程,其中只有达到了迭代的次数或者解的精度才可以跳出迭代,迭代的过程中总是不断的进行选择、交叉和变异。
计算适应度函数就是不断维护fitness矩阵,其中第一列为适应度,第二列为选择概率,第三列为累计概率。计算适应度函数主要是为下面的选择函数准备好数据。
计算适应度函数
选择函数是通过轮盘赌的方式将遗传的下一代选择,并且选择的时候适应度强的个体被选中的概率按比例增大,数据主要来自fitness矩阵。
选择函数
交叉函数将两个个体的染色体相同位置的相同长度的基因互换,交叉之后会产生重复的表现型,代码中的处理方法是,将两段交叉的基因中重复的数字去掉,剩下的数字于未交叉的数字映射去重。
交叉函数
相对来说变异的处理十分简单,随机选择一个个体,互换两个位置上的数字就可以了。
变异函数
已经上传到Github 但是这里不能放链接。
本文的版权归算法卡农所有,抄袭等侵权行为必究!
喜欢我的话,加个关注吧,有更加精彩的内容等着大家。