本站原创
摘要：本文采用遗传算法和模拟退火算法相结合的混合算法，求解路网拓扑图中的任意两点之间的最优路径，既能发挥遗传算法收敛速度快、模拟退火算法搜索范围广的优点，又能克服前者收敛容易早熟、后者收敛速度慢的不足。
关键词：遗传算法 模拟退火算法 最优路径 收敛速度
1.前言
随着经济和社会的发展，我国交通建设也迅猛发展，道路网络呈现出纵横交错的复杂结构，为公众出行提供最优路径成为交通发
本文针对基本遗传算法容易产生早熟现象，并且局部寻优能力较差的缺陷，将其与模拟退火算法相结合，形成混合遗传模拟退火算法，该混合算法大大改善了基本遗传算法的不足。
本文直接将路网节点编号进行实数编码，一条染色体代表一条路径，1个基因代表一个路网节点，染色体的基因值就是节点编号。以图2为例，设一条路径为：1→2→4→7→9，则初始染色体编码为：1 2 4 7 9 0。适应度函数设计为：ft=exp（J/t），其中：J为目标函数，t为SA中的温度值。
（2）选择运算
本文采用比例选择与精华模型相结合的选择策略，即：将每代种群的所有染色体按适应度值排序，将值最大的染色体复制一个直接进入下一代。下一代种群中剩下的染色体用选择法产生。
（3）交叉运算
检测设两条染色体为：P1：1 2 4 6 8 9 0 0 0 15；P2：1 3 5 6 7 9 0 0 0 13
将交叉点选在第三位，即将P1中4及以后的基因与P2中5及以后的基因互换，但由图2的路网拓扑图可知，节点2和节点5不能连通，所以P1和P2不进行交叉，重新选择一条染色体与P1交叉，重新判断两条染色体交叉点的连通性。
交叉后产生的新的染色体可能会出现重复基因的现象，本设计采用覆盖的方法消除重复基因。例如变异后的染色体为：1 2 3 5 3 8 9 0 0 13，消除重复基因后变为：1 2 3 5 8 9 0 0 0 13
（4）变异运算
采用倒置操作进行变异：如果当前随机值大于Pm，则根据染色体的节点基因数量，随机产生两个变异点mutatepoint（1）和mutatepoint（2），然后倒置该两个点的中间部分，产生新的个体。
例如当前染色体为：1 7 6 5 3 9 0 0 0 209，随机选择染色体的两个点“2”和“5”，则倒置该两个点的中间部分，即将“7653”变为“3567”，产生新的染色体为：1 3 5 6 7 9 0 0 0 13
得到的新的染色体的目标函数值为13，适应度值为0.0769，与原来的染色体对比，适应度值更加优异，所以保留新的染色体。
2.
1）初始化温度t=t0，路径长度为0；
2）j=k（k=1，…，N）时，相邻节点之间的距离为ff（k）=cc（k，k+1），从而得到整条路径长度为 ；
3）j=k时，任意选择两点进行位置互换，得到的新路径的相邻两个节点之间的距离为ff1（k），其整条路径的长度为 ；
4）令dd（i）=f（i）-f1（i），其中f为目标函数；
5）随机产生接受概率Pe=rand（1），计算exp（dd/t）的值，若exp（dd/t）> Pe，则接受f1（i）作为下一当前状态，否则仍然以f（i）作为下一当前状态；
6）令j=j+1，重复上面步骤2）～5）；
7）令i=i+1，重复上面步骤2）～6）；
8）T逐渐减少，且T>0，然后转第2）步。
三种算法搜索速度和搜索成功率的对比结果如表1。
由图3和表1可以看出，混合遗传算法不仅实现了最优路径的求解，而且实现了次优路径的求解。当节点数增多时，混合遗传算法的搜索成功率虽不及Dijkstra算法，但是却比单一的遗传算法要高很多，并且搜索速度非常快，这种优势在节点数量越多时表现得更加明显。
参考文献：
李建勋，文海玉.一类模拟退火算法与遗传算法混合优化策略[J].黑龙江工程学院学报（自然科学版），2010，24（2）
周明，孙海栋.遗传算法原理及应用[M].北京：国防工业出版社，1999
[3]金钟. MGASA算法求解物流中货物最佳运输路线[J].科学实践，2009，12（6）
[4]李擎，谢四江.一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较[J].北京科技大学学报，2006，28（11）
关键词：遗传算法 模拟退火算法 最优路径 收敛速度
1.前言
随着经济和社会的发展，我国交通建设也迅猛发展，道路网络呈现出纵横交错的复杂结构，为公众出行提供最优路径成为交通发
源于：论文参考文献www.udooo.com
展的重要目标，求解最优路径问题也成为研究热点。本文针对基本遗传算法容易产生早熟现象，并且局部寻优能力较差的缺陷，将其与模拟退火算法相结合，形成混合遗传模拟退火算法，该混合算法大大改善了基本遗传算法的不足。
2.混合遗传模拟退火算法求解最短路径
2.1.建立目标函数的数学模型
检测设图2代表某一城市的交通网络拓扑图，节点表示某个地点，则该问题的目标函数取从起点到终点途径路径的所有路段的长度总和的最小值。2.GA操作
（1）构造初始种群和适应度函数本文直接将路网节点编号进行实数编码，一条染色体代表一条路径，1个基因代表一个路网节点，染色体的基因值就是节点编号。以图2为例，设一条路径为：1→2→4→7→9，则初始染色体编码为：1 2 4 7 9 0。适应度函数设计为：ft=exp（J/t），其中：J为目标函数，t为SA中的温度值。
（2）选择运算
本文采用比例选择与精华模型相结合的选择策略，即：将每代种群的所有染色体按适应度值排序，将值最大的染色体复制一个直接进入下一代。下一代种群中剩下的染色体用选择法产生。
（3）交叉运算
检测设两条染色体为：P1：1 2 4 6 8 9 0 0 0 15；P2：1 3 5 6 7 9 0 0 0 13
将交叉点选在第三位，即将P1中4及以后的基因与P2中5及以后的基因互换，但由图2的路网拓扑图可知，节点2和节点5不能连通，所以P1和P2不进行交叉，重新选择一条染色体与P1交叉，重新判断两条染色体交叉点的连通性。
交叉后产生的新的染色体可能会出现重复基因的现象，本设计采用覆盖的方法消除重复基因。例如变异后的染色体为：1 2 3 5 3 8 9 0 0 13，消除重复基因后变为：1 2 3 5 8 9 0 0 0 13
（4）变异运算
采用倒置操作进行变异：如果当前随机值大于Pm，则根据染色体的节点基因数量，随机产生两个变异点mutatepoint（1）和mutatepoint（2），然后倒置该两个点的中间部分，产生新的个体。
例如当前染色体为：1 7 6 5 3 9 0 0 0 209，随机选择染色体的两个点“2”和“5”，则倒置该两个点的中间部分，即将“7653”变为“3567”，产生新的染色体为：1 3 5 6 7 9 0 0 0 13
得到的新的染色体的目标函数值为13，适应度值为0.0769，与原来的染色体对比，适应度值更加优异，所以保留新的染色体。
2.3.SA操作
SA的操作流程如下（退火速率设为t=t-0.1）
1）初始化温度t=t0，路径长度为0；2）j=k（k=1，…，N）时，相邻节点之间的距离为ff（k）=cc（k，k+1），从而得到整条路径长度为 ；
3）j=k时，任意选择两点进行位置互换，得到的新路径的相邻两个节点之间的距离为ff1（k），其整条路径的长度为 ；
4）令dd（i）=f（i）-f1（i），其中f为目标函数；
5）随机产生接受概率Pe=rand（1），计算exp（dd/t）的值，若exp（dd/t）> Pe，则接受f1（i）作为下一当前状态，否则仍然以f（i）作为下一当前状态；
6）令j=j+1，重复上面步骤2）～5）；
7）令i=i+1，重复上面步骤2）～6）；
8）T逐渐减少，且T>0，然后转第2）步。
2.4.仿真结果
本研究采用Matlab对算法流程进行编程实现，仿真结果如下：三种算法搜索速度和搜索成功率的对比结果如表1。
由图3和表1可以看出，混合遗传算法不仅实现了最优路径的求解，而且实现了次优路径的求解。当节点数增多时，混合遗传算法的搜索成功率虽不及Dijkstra算法，但是却比单一的遗传算法要高很多，并且搜索速度非常快，这种优势在节点数量越多时表现得更加明显。
3.结束语
本文采用的混合遗传模拟退火算法，既能发挥遗传算法收敛速度快、模拟退火算法搜索范围广的优点，又能克服前者收敛容易早熟、后者收敛速度慢的不足，经过仿真实验证明，在求解路网拓扑图中的任意两点之间的最优路径方面相对最为有效。参考文献：
李建勋，文海玉.一类模拟退火算法与遗传算法混合优化策略[J].黑龙江工程学院学报（自然科学版），2010，24（2）
周明，孙海栋.遗传算法原理及应用[M].北京：国防工业出版社，1999
[3]金钟. MGASA算法求解物流中货物最佳运输路线[J].科学实践，2009，12（6）
[4]李擎，谢四江.一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较[J].北京科技大学学报，2006，28（11）