[摘 要]最短路径问题的存储结构通常是采用针对图论中的带权图的邻接矩阵。根据权的性质,这个问题的解可以是任何意义的最佳,如经济最省、时间最快、路程短、或者是其它意义上的“最优”。本文在最小成本计算、最佳地址选择等问题的基础上,同时进行了编程实践。
[关键词] 最短路径 遗传算法 编程 算法描述
一、遗传算法求解最短路径思路
遗传算法的基本思想是基于达尔文进化论和孟德尔的遗传变异理论的。遗传算法把问题的解表示成基因串,每一个基因串都是一个假设解。然后,把假设解置于问题空间(群体)中,以适应度函数(或日标函数)为依据,通过对个体施加遗传操作实现群体内个体结构重组的迭代处理过程,最后收敛到最适应环境的个体上,它就是问题的最优解。遗传算法主要考虑六个要素:一是染色体编码,由于遗传算法不能直接处理解空间的数据,因此必须通过编码将它们表示成遗传空间的基因型串结构数据。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基因是由二值符号集{0,1}组成;二是初始种群的生成,由于遗传算法的群体操作需要,所以进化开始前必须准备一个由若干初始解组成的初始群体;三是适应度评价,遗传算法在进化过程中一般不需要其它外部信息,仅用评价函数值来评估个体或解的优劣,并作为遗传操作的依据;四是遗传算子这个要素,基本遗传算法使用三种遗传算子:①选择运算: 比例选择。选择运算的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代繁殖后代子孙。判断个体优劣的准则是个体的适应度值。选择运算模拟了达尔文适者生存、优胜劣汰原则,个体适应度越高,被选择的机会也就越多;②交叉运算:单点交叉。交叉运算相当于生物进化过程中的有性繁殖的基因重组过程;③变异运算:基本位变异。变异运算模拟了生物进化过程中的基因突变方法,将某个基因座上的基因变异为其等位基因;选择运算不产生新的个体,交叉运算和变异运算都产生新的个体,因此,选择运算完成的是复制操作,而交叉运算和变异运算则完成繁殖操作。五是遗传终止条件,终止条件就是遗传进化结束的条件。基本遗传算法的终止条件可以是最大进化代数或最优解所需满足的精度;六是相关运行参数,基本遗传算法主要有群体规模、交叉概率PC、变异概率。
具体遗传算法的基本运算过程如下:设解空间为I,个体为Pi (1<=i<=m),选择算法为φ,,交叉算法为г,变异算法为ψ,替换算法为θ,终止条件判断函数为О,则算法可描述如下:
t=0;
initialize:P0={P0,1,p0,2,…,PO,M}∈I;
evaluate:PO:{E(P0,1),E(p0,2),…,E(P0,M)};
while O(T)do
select:Pt’=φ{Pt}
recombine:Pt’’=г{Pt’};
mutate:Ptm=ψ{Pt’’}
evaluate:Ptm:{E(Pt,1m),E(Pt,2m)…,E(Pt,1m)};
replace:Pt+1=θ{Ptm}:
t=t+l;
end while
在实现过程中,首先从整个种群中筛选出n个个体送到主结点上,然后再将整个种群被划分为k个相等的子群体P(i),1≤i≤k,分别分配到k个从结点上。
算法可描述如下:
输入:种群P;有输出:优化的种群P
Procedure ParallelGeneticO
Begin
Initialize(P);//初始化种群P
Divide();//首先选n个个体送到主结点上,然后将P分为k个大小相同的子种群送到k个从结点上
Generation=l;
ParallelBegin ;
Evaluation_G1();//评估第一代种群的适应度
FindllestGlo;//寻找第一代种群中的最优解,并保留下来.
While(Generation<=MaxGeneration)
Begin
If IsInServer Then//在主结点上
i=0;
While(i<=k)
SendDataToClient(i++);/*发送优良解到探测环*/
While(i<=k)
ReceiveDataFromClient(i++);/*从探测环接收优良解*/
Else/*在从结点上*/
SendDataTbServer0;/*发送优良解到主结点*/
SendDataToNextClient0;/*发送激励因子到后继从结点*/
ReceiveDataFromServer0;/*从主结点接收优良解*/
ReceiveData FromPreClient0;/*从前驱结点接收激励因子*/
EndIf
Replace0;/*用接收到的优良解和激励因子替换本代中最差解*/
ComputGenerationDiversity0;/*计算代间差异度,判断进化方向,即进化正在向什么方向发展*/
ComputeEvolutionScatter0;/*计算进化的离散度,预测进化方向,即进化应该向什么方向发展*/
Select_Step10;/*选择算子,第一步用迄今最优,替换本代最差,本代最优直接繁殖*/
Mutate0;/*变异算子,因为变异算子引入新基因,故先于交叉执行*/
Crossover0;/*交叉算子*/
EvaluateAll();/*评估本代适应度*/
Select_Step20;/*选择算子,第二步,父子竞争*/
FindBest();/*寻找本代中最优解,并保留下来*/
Generation++;/*进化代数*/
EndWhile;
ParallelEnd;
End;
算法中,语句对ParallelBegin和ParallelEnd表示其间的语句是并行执行的,具体的实现方案依赖于所采用的并行环境。
二、算法的实现
求最短路径问题,用图论术语描述如下:在G(V,A)中,V表示顶点集合,V=(v1,v2,…,vn)对G中的某一条边(vi,vj),相应地有一个数d(vi,vj),如果G中不存在边(vi,vj),则令d(vi,vj)=∞,如果把d(vi,vj)认为是边(vi,vj)的长度(也可以认为是边(vi,vj)的费用或权),则路径的长度定义为组成路的各条边的长度的总和。顶点vi,vj之间是否有边相连,由邻接矩阵来决定。邻接矩阵A:对一个具有V个顶点。A=aij是一个v×v阶方阵,其中aij=0表示vi和vj之间不相邻接(或i=j),aij为一个正数,表示顶点vi和vj邻接,同时该数表示边(vi,vj)的长度(或权)。当基因值为1时,表示相应的顶点被选入该条路径中,否则,当基因值为0时,表示相应的顶点不被选入该条路径中。已知各顶点(vi,vj)的边长度d(vi,vj),把vi1到vjn之间的一条通路vi1,vi2,…,vin的路径长度定义为适应函数:
n-1
f(i)=Σd(vir,vir+1)
i=1
对该优化问题,就是要寻找解使之最小。
选择作为交叉的双亲,是根据前代染色体的适应函数值所确定的,质量好的个体,即从起点到终点路径长度短的个体被选中的概率较大。将被选中的两个染色体进行交叉操作的过程是先产生一个随机数,确定交叉点,位于染色体的第几位基因上,然后在此位置进行部分基因交换。变异操作是将染色体中某位基因逆变,即由1变为0,或反之。变异的意义为在某条路径上去掉或增加某顶点。但这样做的结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失,迟缓了获得最优解的速度。为了使算法尽可能快地获得更好的解,改善遗传算法的收敛性,在变异操作时,增加了个体求优的自学习过程,即在某位基因变异后,计算新产生的染色体的适应函数值,若适应函数值更小,即获得的路径更短,则保留;否则,保持原来的解不变。如果有连续N/3次没有得到更好的解,则该过程结束,其中N表示从起点到终点的顶点数。
三、编程实践
根据上面的算法描述的具体步骤,可以用Delphi语言进行逐一翻译如下上:
S[Vs]:=1;P[Vs]:=0;λ[Vs]:=Vs;//Vs为出发点。
//对其他结点的初始化
for V:=1 to N do begin
if (V<>Vs) then begin
T[V]:=MAX_INT;
λ[V]:=MAX_INT;
S[V]:=0;
end;
end;
//考查Vs,Vk:=Vs;
for L:=1 To N-1 do begin
For m:=1 To N do //①
If S[m]= 0 || W[Vk,m] <>+∞ then
If T[Vm]>P[Vk]+W[Vk,Vm] Then begin
T[Vm]=P[Vk]+W[Vk,Vm];
λ(Vm)=Vk;
End;
//②
min:=MAX_INT;
For Vj:=1 To N do begin
If S[Vj] <> 1 and min>T[Vj] then begin
Min:=T[Vj];
Vk:=Vj;//下一次考查的点
End;
End;
//③
If min<>MAX_INT then begin
S[Vk]:=1;
P[Vk]:=T[Vk];
End;
end;
//Dijkstra算法到此结束.
最后用Delphi编写成算法软件,输入数值即可求解:
四、结论
通过上面的编程实践,初步找到了一种比较好的最短路径描述算法,即用遗传思想来描述算法,既简单清楚,又使后面的编程实现变得简单直观实用,再利用Delphi编程工具编成软件,使该算法在生产实际中的应用价值大大提高了。
参 考 文 献
[1] 运筹学教材编写组编.运筹学(修订版).清华大学出版社
[2] 林同曾编.运筹学.机械工业出版社
[3] 胡运权主编.运筹学基础及应用.哈尔滨工业大学出版社■