内容发布更新时间 : 2024/11/15 4:01:09星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

基于遗传算法的最短路径研究与编程实践

作者：刘雪龙

来源：《科学与财富》2010年第05期

[摘 要]最短路径问题的存储结构通常是采用针对图论中的带权图的邻接矩阵。根据权的性质,这个问题的解可以是任何意义的最佳,如经济最省、时间最快、路程短、或者是其它意义上的“最优”。本文在最小成本计算、最佳地址选择等问题的基础上,同时进行了编程实践。 [关键词] 最短路径 遗传算法 编程 算法描述

一、遗传算法求解最短路径思路

遗传算法的基本思想是基于达尔文进化论和孟德尔的遗传变异理论的。遗传算法把问题的解表示成基因串,每一个基因串都是一个假设解。然后,把假设解置于问题空间(群体)中,以适应度函数(或日标函数)为依据,通过对个体施加遗传操作实现群体内个体结构重组的迭代处理过程,最后收敛到最适应环境的个体上,它就是问题的最优解。遗传算法主要考虑六个要素:一是染色体编码,由于遗传算法不能直接处理解空间的数据,因此必须通过编码将它们表示成遗传空间的基因型串结构数据。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基因是由二值符号集{0,1}组成;二是初始种群的生成,由于遗传算法的群体操作需要,所以进化开始前必须准备一个由若干初始解组成的初始群体;三是适应度评价,遗传算法在进化过程中一般不需要其它外部信息,仅用评价函数值来评估个体或解的优劣,并作为遗传操作的依据;四是遗传算子这个要素,基本遗传算法使用三种遗传算子:①选择运算: 比例选择。选择运算的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代繁殖后代子孙。判断个体优劣的准则是个体的适应度值。选择运算模拟了达尔文适者生存、优胜劣汰原则,个体适应度越高,被选择的机会也就越多;②交叉运算:单点交叉。交叉运算相当于生物进化过程中的有性繁殖的基因重组过程;③变异运算:基本位变异。变异运算模拟了生物进化过程中的基因突变方法,将某个基因座上的基因变异为其等位基因;选择运算不产生新的个体,交叉运算和变异运算都产生新的个体,因此,选择运算完成的是复制操作,而交叉运算和变异运算则完成繁殖操作。五是遗传终止条件,终止条件就是遗传进化结束的条件。基本遗传算法的终止条件可以是最大进化代数或最优解所需满足的精度;六是相关运行参数,基本遗传算法主要有群体规模、交叉概率PC、变异概率。 具体遗传算法的基本运算过程如下:设解空间为I,个体为Pi (1 t=0;

initialize:P0={P0,1,p0,2,…,PO,M}∈I; evaluate:PO:{E(P0,1),E(p0,2),…,E(P0,M)};

龙源期刊网 http://www.qikan.com.cn

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 Begin

龙源期刊网 http://www.qikan.com.cn

If IsInServer Then//在主结点上 i=0; While(i

SendDataToClient(i++);/*发送优良解到探测环*/ While(i

ReceiveDataFromClient(i++);/*从探测环接收优良解*/ Else/*在从结点上*/

SendDataTbServer0;/*发送优良解到主结点*/

SendDataToNextClient0;/*发送激励因子到后继从结点*/ ReceiveDataFromServer0;/*从主结点接收优良解*/ ReceiveData FromPreClient0;/*从前驱结点接收激励因子*/ EndIf

Replace0;/*用接收到的优良解和激励因子替换本代中最差解*/

ComputGenerationDiversity0;/*计算代间差异度,判断进化方向,即进化正在向什么方向发展*/

ComputeEvolutionScatter0;/*计算进化的离散度,预测进化方向,即进化应该向什么方向发展*/

Select_Step10;/*选择算子,第一步用迄今最优,替换本代最差,本代最优直接繁殖*/ Mutate0;/*变异算子,因为变异算子引入新基因,故先于交叉执行*/ Crossover0;/*交叉算子*/ EvaluateAll();/*评估本代适应度*/

Select_Step20;/*选择算子,第二步,父子竞争*/ FindBest();/*寻找本代中最优解,并保留下来*/