基于LabVIEW仿真的全局最短路径的遗传算法设计
为了改善这种情况，本文摒弃了双父代杂交而采用一种“群体精英父代杂交”的方法。因为杂交运算就是为了使优秀基因快速繁殖，扩大影响，所以不妨直接判定哪些基因是有较大概率优秀的。举例说明判断方法，选择所有f>favg的父代个体，这些个体明显都是优秀的，从这些优秀父代中提取出共有的或出现次数较多的基因，因为优秀父代中含有优秀基因的可能大，所以这些共有的基因就更可能是优秀基因。保留这些基因，在剩余的基因位上随机产生新的基因。最后从产生的这些新个体和ffavg的低适应度父代中选出适应度高的一部分作为子代，它们与开始的那些优秀父代一起合成新的子代。因为实际上并没有使用单点杂交的方法，所以不使用式(3)。
5．2 变异
按式(4)计算，如果一个父代个体要变异时，从其中随机取一条线段除去换上一条新的线段。为了提高变异操作提供新基因的效率，防止无方向性的变异产生大量冗余，新的线段要有一个端点不变。如图5所示，当除去线段12时，新产生的线段必须以节点3或6为端点，不算线段12，节点3、节点6分别还可以与其他M-2个节点产生共2M-4个子代个体，当然其中有很多新个体是不合法的，从合法的子代个体中选择适应度最高的遗传到下一代。这样，经过几代变异后，个体就会逐渐趋于所求目标。本文引用地址：http://www.eepw.com.cn/article/202494.htm
为了防止局部收敛，即使产生的予代个体适应度不如父代个体，也要淘汰父代个体。
5．3 精英保留
根据上述方法，在进化中很可能导致高适应度个体被意外的破坏，减缓进化速度甚至导致局部收敛。所以每次进化前取出当代个体中适应度最高的一个个体直接进入下一代，保证最优基因的安全。
6 仿真实验
选取一组数据(见表1)进行仿真实验，种群数量取50个，计算100代。
得到仿真结果如图6所示。
图6为分别截取了运行到不同代数时的结果。图6(a)表示所有点的位置及所有可能的连线，图6(b)～图6(d)中数字含义，括号内的数字表示运行代数，括号外是此时线段的总长度。图6(d)显示最终总长度为1087．77。
7 结论
综上所述，此方法可以有效地解决全局最短路径问题。相对于“旅行商问题”单一起点终点的“一笔画”情况和繁复的编码解码运算，本文的方法更具有广泛性。因为节省了一般的编码解码过程，所以运算更加快捷，结果更易识别。随着约束条件的改变，只需相应的修改目标函数即可，不会影响程序的其他功能。该方法可以适用多类工程设计，如Zigbee无线模块组网、城乡间道路和配电网设置、农田灌溉点之间的管道连接、多目标的运输问题等等。
评论