遗传算法论文范文

前言：我们精心挑选了数篇优质遗传算法论文文章，供您阅读参考。期待这些文章能为您带来启发，助您在写作的道路上更上一层楼。

第1篇

论文摘要：TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

论文关键词：旅行商问题遗传算法基因库多重搜索策略

TSP(travelingsalesmanproblem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是NP难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于TSP在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。TSP的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。

遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。

用遗传算法求解TSP能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解TSP问题。该文根据文[7]中最小生成树MST(minimumcostspanningtree)的应用,由MST建立TSP的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。

1单亲演化过程

现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的TSP尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出TSP中最小生成树,并将各个MST中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。

1.1TSP编码表示

设n个城市编号为1,2,…,n,为一条可行路径,Pk=Vk1Vk2…Vkn为一条可行路径,它是1,2,…,n的一个随机排列,其含意是第k条路径起点城市是Vk1,最后一个城市是Vkn,则第k条环路的总长度可以表示为:

其中,d(Vki,Vkj)表示城市Vki与城市Vkj之间的距离。在算法中环路Pk的总长d(Pk)用来评价个体的好坏[9]。适应度函数取路径长度d(Pk)的倒数,f(Pk)=1/d(Pk)。

1.2构建TSP基因库

对n个编号为1,2,…,n的城市,根据它们的坐标计算各城市之间的欧氏距离d(i,j),i,j=1,2,…,n,得到一个n*n的方阵D={d(i,j)}。然后利用普里姆算法求得该TSP的一棵MST,并将这棵MST中的每一条边e(i,j)对应地存储在一个n*(n-1)的方阵M={e(i,j)},即该文的基因库。由于一个TSP可能有多棵MST,操作可以重复多次,这样生成的基因库中的基因就更多,增强了初始群体的全局性。具体算法如下:

VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){

Struct{

VertexTypeadjvex;

VRTypelowcost;

}closedge[MAX—VERTEX—NUM];

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j)

if(j!=k)closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;

for(i=0;i<G.vexnum;++i){

k=minimum(closedge);

printf(closedge[k].adjvex,G.vexs[k]);

closedge[k].lowcost=0;

for(j=0;j<G.vexnum;++j)

if(G.arcs[k][j].adj<closedge[j].lowcost)

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}

}

1.3单亲演化算法

单亲演化算法是利用遗传算法的优胜劣汰的遗传特性,在单个染色体内以基因重组的方式,使子代在满足TSP问题的限定条件下进行繁衍,然后保留适应度高的染色体种群,达到优化的目的。单亲演化算法的基因重组操作包括基因换位、基因段错位和基因段倒转三种操作来实现。基因换位操作是将亲代的染色体基因进行对换后,形成子代,其换位又分为单基因换位和基因段换位两种方式。基因段错位操作是随机确定基因段,也随机选定错位位置,整段错移。基因段倒转操作则是随机地确定倒转基因段的起止位置,倒转操作是对该段内基因按中垂线作镜面反射,若段内基因数为奇数时,则中位基因不变。单亲演化时可以是单个操作用于单个父代,也可以是几种操作同时采用。为了编程方便,文中采用基因段倒转操作。

2群体演化过程

在单亲演化算法求得的初始群体基础上,再利用多重搜索策略并行地进行群体演化,这样在保证算法的快速收敛的同时也注重了搜索空间的全局性。

2.1交叉算子

该文算子采用一种与顺序交叉OX(ordercrossover)法类似的交叉方法[11],即随机在串中选择一个区域,例如以下两个父串及区域选定为:

P1=(12|3456|789)P2=(98|7654|321)

将P2的区域加到P1的前面或后面,P1的区域加到P2的前面或后面,得

M1=(7654|123456789)

M2=(3456|987654321)

在M1中自区域后依次删除与区域相同的城市码,得到最终的两个子串:

S1=(765412389)S2=(345698721)

同时为了能更好地增强算子的全局搜索能力,对该算子作了如下的改进。子代个体的新边来自:随机生成和群体中其他个体,其选择比例由随机数p和阈值P来决定。如果随机数p小于阈值P,则子代个体的新边来自随机生成,否则就来自群体中的其他个体。

这种改进后的交叉算子在父串相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。实验结果也证实了这种改进算子对于种群的全局搜索能力有一定的提高,避免搜索陷入局部解。

2.2局部启发式算子

为了增强遗传算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。该算子通过比较两条边并交换路径以提升算法的局部搜索性能,示例见图2。

比较子路径ab+cd和ac+bd,如果ab+cd>ac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-Opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。

2.3选择机制和收敛准则

为了限制种群的规模[13],该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。

遗传算法求TSP问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续K1代不再出现更优的染色体;优化解的染色体占种群的个数达K2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。

2.4基于多重搜索策略的群体演化算法

由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。

3实验结果与分析

该文的GB—MGA算法由C#编程实现,所有的结果都是在P42.0G微机上完成,并进行通用的TSP库实验,选用了具有一定代表性的TSP实例,并把该算法和其他算法做了一个对比。为了减少计算量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图Kroa100的示例。

为了证明该文提出的GB—MGA算法的有效性,将该文算法与典型的遗传算法GA、单亲遗传算法PGA以及文[5]中杨辉提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都进行了一个对比。

实验结果证明,该文算法的求解质量要优于GA、PGA、MMGA算法,而求解速度方面则优于Ge—GA算法,特别是对于大规模城市的TSP问题求解效果尤其明显,具有快速收敛的特性。Ge—GA算法对于中等城市规模的TSP实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模TSP问题,那么时间上的代价就让人无法忍受。而该文的GB—MGA算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。

4结束语

第2篇

遗传算法就是一种以事物的自然属性和遗传属性为基础，通过计算机对生物进化规律进行模拟以寻优的一种算法，将寻优的范围与遗传空间相对应，把每一种可能的值通过二进制码进行编码，如同染色体一样，形成的字符串相当于基因，然后按预期的结果对每一组编码进行评价，选出最合适的一个值。算法一开始是提出一些问题的解，然后根据要求对这些解进行选择，重新拆解组合，去掉不合适的，留下最优值，由此形成的便是新值，如此往复，继承与改良，这便是GA算法。由以上我们可以看出GA算法并不是简单的重复，而是属于一种螺旋式的上升过程，是不断向更好的方向“进化”的，在淘汰与择优中趋于稳定。

2GA算法的数学基础和算子

2.1GA算法的数学基础

图式定理是GA算法的数学基础，图式定理是Holland提出的，它在一定程度上解释了GA算法强大的数据信息处理能力，由定理我们能看出，经过不断地复制和交叉变异，在第一代中包含的编码数量H可以用如下公式表示：m（H，t+1）≥m（H，t）（N（H）/FAV）[1-PC•（〥（H）/（L-1））-O（H）•Pm]（1）如以遗传学讲，其中m（H，t）和m（H，t+1）分别代表第t代和第t+1代种群数量，N代表图式H中染色体适应能力的平均水平，FAV代表种群中包含的染色体的适应力的平均水平，交叉比率用PC表示，变异比率用Pm表示，图式的长度用〥表示，OH是H的确定参数，即阶，染色体长度用L表示。

2.2GA算法的算子

GA遗传算法的基本算子有三个，分别是选择、交叉和变异。选择算子相当于生物界优胜劣汰，决定物种最终存活的自然选择，在生物群中选择一些适应力强的生物，将它们的染色体放入基因库，是染色体重新交叉组合完成变异的前提，选择算子的特点是只能在原有的基础上选择出优良的基因，而无法重新创造。交叉算子相当于自然界生物为完成繁衍生息和进化而进行的繁殖现象，染色体经由交叉，重新组合后形成新的染色体，即从双亲染色体里随机地分别选择一条再重新组合，是染色体的重新创造。变异算子是在选择和交叉算子完成重组的基础上使遗传算法能力的增强，以寻找GA值的最优解，如果在整个GA算法中少了变异操作，就只能在原有基础上来回寻找而没有新的突破。

3如何实现遗传算法

遗传算法归根结底是寻找一个最优的解或者工程中所讲的最好的解决方案，从函数来讲是求如下函数的最优解：F=f（x，y，z），x，y，z∈Ω，F∈R（2）其中x，y，z是自变量，每一组（x，y，z）就是一组解，优化目标的目的是寻找一组解使得：F=f（x0，y0，z0）=maxf（x，y，z）（3）首先，将公式（2）的各个参数通过二进制数编码形成字符串，再进行链接形成所谓的“基因链”，据已有的研究结果，可以知道字符串长度不同、码制不同都将对最终计算的结果的精度产生影响。其次，采用随机抽选的方式选择个体的初始值，之所以随机抽选是因为这样产生的结果更具有一般性，能代表寻常情况。最后，确定群体的规模，即确定基因选择的目标源，在这个目标源中寻找最佳值，规模的确定决定了GA算法结果的权威性和有效性，太小则不能提供足够的采样点，结果的多样性将会打折扣，太大则会增加计算量，拖长搜索时间，通畅将规模控制在40～200左右为宜，在对每个个体的优劣实施评价之后，设置一个适应度函数，然后分别确定交叉率和变异率，判断搜索何时停止，在本次讨论中，判断标准可以定为搜索所得的解是否达到了预期的最大值。

4GA在机械工程中的应用

GA算法的优点显而易见，它在机械工程中的应用是极为广泛的。在零件的切削中可以对零部件和切削工具予以优化，使得切削参数的设置达到总在工作以最低的成本，实现最高的效率，最终得到最高的收益的目的，在自动化控制的智能制造系统中可以为系统的静态动态的配合寻找到最佳契合点，以下对GA算法在机械公式和功能中的应用以具体实例加以阐述。

4.1优化人工神经网

ANN，即人工神经网，是一种用于建模和控制的，针对模型结构不稳定的线性系统而设计的结构，单次结构目前并不成熟，并没有确切的数据指导后来者准确的使用，处于摸索阶段。对于ANN，目前采用的训练方法是反向传播算法，大速度比较慢且结果具有一定的局限性，GA算法可谓使这一问题得见柳暗花明。在AN的行学习参数的优化工作中，仍用反向传播，但对一下因素进行编码操作，包括隐含层数、隐含层数的单元数、势态、网络连接方法、迭代数等，编码完成后，构成ANN基因链，把基因链的适应度函数定义为10-MSE-隐含单元数/10-训练跌代数/1000，MSE是训练好的网络对样本的方差。

4.2优化FLC矩阵的参数

模糊逻辑控制器，简称FLC，涉及到的概念有控制对象偏差和动作强度，表达了二者的模糊关系，现有一延时二阶系统的函数为GS=exp（-0.4s）/（0.3s+1），要求此系统的输出值尽量的跟踪输入值，采用FLC矩阵进行参数优化，取矩阵R=77×11，对此矩阵的77个元素以8bit的二进制码表示，基因链长616bit，经由GA算法优化的FLC控制下，输出值的效果明显地优于“比例-积分-微分”控制器的效果。

4.3实现机床挂最佳组合

机床挂轮组合的完美与否直接决定了生产线的效率，而这又是一个极为古老的问题，最佳组合最终实现的是挂轮组的传动比与要求的值误差达到最小，本文中，笔者通过GA算法，以求能找到一个有效的方案，适合度函数定义为：F=20-ABS（id）-（A/B）*（C/D）（A，B，C，D）∈Ω其中，A，B，C，D分别代表挂轮齿数，共计4个挂轮，ABS（）表示绝对值函数，Ω是挂轮约束条件，需要A+B＞C=d+m，C+D＞B+d+m，d，m分别代表齿轮模、安装轴径。笔者在文中采用cenitor算法，对每个齿轮用一个5位二进制码进行编码，代表挂轮表的32个挂轮，共4个挂轮故基因码长20位，个体数为100，经过验证后发现，如果id为整数，GA算法只需完成1000次杂交运算就可以选出多个误差为0的组合，它并非盲目地完成计算，搜索数远小于问题解的数值。

5结语

第3篇

假设所用的计算机传输介质两节点之间不多于一条直线的链接路，所用计算机网络就可以运用数学图G=（N,L）来进行描述。而且网络的节点不会出现任何的故障，网络链接介质的可靠和自身的长度没有关系，网络链接路与网络只有两种状态存在：正常工作和故障。而当所有的计算机网络用户都相互联通时，则可组成G图的一棵生成树，并且全部的结点都处于正常。那么无论在什么时刻，可能只有L种的子集（L）是正常状态，全部结点都是正常状态。因此，整个计算机网络的可靠度都可使用数学建模来进行运算。

2遗传算法在计算机网络可靠度优化计算中的应用研究

2.1遗传运算方法

在计算机网络中遗传运算主要是以变异和交叉这两种方式进行。交叉主要是通过在网络结点的范围（[1，N]）之间的随机数，以此作为基因交叉位置的设置且一次只可以操作一个结点。这样能够最大程度地确保网络的连通性，但也有可能出现错的连通结构，所以进行调整操作；变异则是先确定基因的变异和数目，然后再根据范围来选择新的基因段替换旧基因段生成后代。一般变异率都在0.001到0.01内，如是变异出现了错误的网络连通结构基因，就必须进行相应的调整。

2.2算法的调整与仿真实例

第4篇

【关键词】自动导航小车；路径规划；免疫遗传算法；疫苗

1、引言

目前，为使移动机器人规划出良好的去去路径，所用的方法很多，如栅格法[1]、势场法[2]、可视图法[3]等。但各种方法有其使用局限。人工智能的发展为AGV的路径规划提供了新思路，产生了诸如神经网络学习法、遗传算法等方法。这些算法在一定程度上解决了AGV的路径规划问题，但也有其缺陷。如神经网络学习法对于复杂环境难以数学建模，范化能力差；模糊法灵活性差。遗传算法在迭代过程中，个体在进化过程中不可避免地会产生退化。受生物免疫系统的启发，论文将免疫引入到遗传算法中，在保留遗传算法优点的情况下，利用待求问题的一些特征信息，采用免疫方法所具有的识别、记忆等功能来抑制遗传算法在进化中所出现的退化现象。本文所设计的基于免疫遗传算法的AGV路径规划方法利用AGV在移动过程中的特殊信息对所选路径进行优化，可较快地使AGV根据环境信息搜索一种满意的路径，提高了AGV路径规划的智能性。

2、环境信息建模

对AGV进行路径规划前，应解决对其环境信息的描述即环境建模问题。为此，作以下假设[3]：

（1）AGV在二维平面中运动，不考虑其高度方向的信息；（2）规划环境的边界及其内所有障碍物（妨碍AGV运动的所有物体）用凸多边形表示。（3）考虑到AGV的大小等，对环境边界进行缩小和对障碍物进行扩大时，其缩放量为AGV外形最大尺寸的一半。即AGV为“点机器人”。

至此，AGV的工作空间可描述为：工作平面和障碍物群{Oi|i=1，2…N}。具体到其个障碍物Oi，可描述为Oi={顶点1坐标（xi1， yi1），….. 顶点n坐标（xni， yni）}。为方便数据处理，对多边形顶点沿顺时针方向编号。起点为S，终点为E。工作平面可表示为矩形{（Xmin，Ymin），（Xmax，Ymax）}。

设在AGV的工作环境中有n个已知的障碍物Oi（i=1，2，...，n），对应的顶点数为Si，顶点坐标为（x（i，j），y（i，j））（j=1，2，…Si）。为描述AGV工作环境中的障碍物，采用Dm×m矩阵对环境信息进行描述，其中，m为障碍物顶点总数。定义d（i，j）为：

3、免疫遗传算法设计

3.1路径编码方式

采用免疫遗传算法求解最优问题的关键是对所求问题的解进行编码。编码的长度与搜索空间的大小及求解精度有直接关系，也影响算法的效率。对AGV进行路径规划时，传统的二进制或实数编码方式都不适用。本文设计了一种自适应变长度实数数组编码方式，即第p代Xp的第k条染色体Xkp的第j位基因Xkp（j）表示为Xkp（j）=|io，xk，yk|T，其中io为障碍物序号，（xk，yk|）为第io号障碍物的某顶点坐标。由于路径的起点为AGV的起始点，终点为其目标点，在路径规划时可省去以缩短染色体的长度。定义，AGV的可能运动路径由数条直线段组成，相邻两直线段的交点称为AGV的路径拐点。为使AGV不穿越障碍物运动，基于对工作规划空间建模时所作的假设，AGV可沿多边形障碍物的边界线移动，也可以障碍物的顶点为拐点在自由空间中移动。染色体即AGV的某行路径Xkp为Xkp={Xkp（1）， Xkp（2），…， Xkp（nkp）}，其中nkp为第p代中第k条染色体的长度，每代中各条染色体长度不同。

3.2适应度函数

在对AGV进行路径规划时，其优化目标为在所有可能的运动路径Xp={Xkp|k=1， 2，…，N}中找出一条最优或次优路径。设某个体Xkp的路径长度Dk为：

其中dj为Xk中各直线段轨迹长。因为AGV由一直线轨迹向另一直线轨迹过渡时运动速度的变化会影响其运行时间，因此，在对所选路径进行评价时，除考虑其总长度外，可要求路径中的拐点数尽可能的少或AGV的姿态角变化量尽要能的小。本论文的路径规划目标是路径短且拐点较少。定义适应度函数为：

式中，和为调整系数。这里取=0.8，=0.2。N为种群大小，Dj为种群中第j个体的路径长度，nj为第j个体路径拐点数。

3.3算法的实现

在进行路径规划时，首先判断AGV从起点向终点沿直线轨迹运动时是否穿越障碍物。若无障碍物，两点间的连线为AGV的最佳运动路径，无须进行路径规划。否则进行路径规划。

免疫遗传算法中，疫苗是根据待求问题的先验知识构造的最佳个体基因的估计，抗体是根据疫苗将某个体基因进行修正后所得到的新个体。论文所设计的基于免疫遗传算法的路径规划过程如下：

（1）根据问题从记忆抗体库中提取问题的抗体P得到初始种群 ，不足N个时在AGV起始点和目标点之间随机产生N-P条路径。个体的产生方法是：以包围AGV的起点、终点和所有在线障碍物的最小矩形为规划区域，在规划区域内的障碍物顶点个数为M，在线障碍物为m，则染色体的最大长度为M-m。以规划区域内的障碍物顶点为被选对象，沿一定的条件随机选取基因位上的基因组成一条染色体，同用样的方法产生其它染色体以组成群体。

（2）根据先验知识抽取疫苗H={h1， h2， …， hm}；

（3）计算第p代种群Ak所有个体的适应度，并进行终止进化判断。

（4）对当前群体Xp进行遗传算子操作得到子代群体Bp。进行交叉操作时，采用单点交叉。交叉操作时，两个个体若有相同的基因（而非等位基因）进行交叉操作。当相同基因位不止一个，随机选择其一进行交叉；当无相同基因位则不进行交叉。进行变异操作时，从个体中随机删除一基因位或随机选取一基因位插入一新基因位，或在个体中随机选取一基因位用另一随机产生的基因位交换。

（5）对子代Bp进行免疫操作，得到新代Xp+1；接种疫苗和免疫选择是免疫算法的主要操作，接种疫苗是为了提高个体的适应度，免疫选择是为了防止个体的退化。接种疫苗即从Bp中按比例K随机抽取Nk=KN个个体Bip（i=1，2，…，Nk），并按先验知识修改Bip（这时就变为抗体），使其以较大的概率具有更高的适应度。接种疫苗时，若Bip已经是最佳个体，则其以概率1转移为Bip。对路径规划，接种疫苗就是对所选个体进行判断：首先，相邻两点间能否使AGV无障碍的沿直线运动；其次，任意两点间能否使AGV无障碍的沿直线运动？条件满足，则删除中间点。免疫选择分两步完成：免疫检测和退火选择。免疫检测即对抗体进行检测，若出现适应度下降，此时由父代个体代替其参加竞选，退火选择即以概率P（Bip）在当前子代中进行选择：

其中，为适应度函数；Tk是单调递减趋于0的退火温度控制序列，Tk=ln（T0/k+1），T0=100，p是进化代数[3]。

（6）选择个体进入新的群体。更新抗体库，并转到第（3）步。

4、仿真实验

仿真是在Matlab6.1上进行的。AGV的工作环境大小为8×6m2，其内有6个形状各异、排列任意的障碍物（如图2所示），现欲使AGV从S点无碰撞地运动到E点且使其运动路径最短，建立如图4所示的可视图。其可视矩阵如左图：

论文采用所设计的路径规划方法和现有的遗传和免疫算法对AGV进行路径规划以寻找最佳路径。取遗传操作中的交叉概率Pc=0.8，变异概率Pm=0.2，免疫操作中的接种疫苗概率Pv=0.6，初始种群大小为N=20，抗体库M=5，遗传代数不超过K=200。图3为路径规划的最佳路径。进化过程中适应度变化和路径长度变化如图4所示。

由仿真结果知，采用免疫遗传算法进行路径规划时，退化现象基本不会发生，再能很快得到问题的最优解。其原因是，利用免疫遗传算法对AGV进行路径规划，一方面利用了遗传算法的优点，由于是对编码进行操作，对问题的依赖性小，且操作是并行进行，优化速度快；同时针对遗传算在进行交叉和变异操作时是以以概率方式随机地、缺泛指导性地进行导致问题进化时产生退化的现象，采用适当的指导，弥补了遗传算法的缺点。利用遗传免疫算法进行优化，在保证算法收敛的前提下，有效地提高计算速度。利用此法对AGV的路径进行规划，比其它的方法更有效。

5、结论

论文主要针对环境建模和路径搜索两大问题进行了研究。基于可视图环境建模方法优点，完成了对环境信息的建模。并结合遗传和免疫算法的优点设计了具有精英保留策略的基于免疫遗传算法的AGV路径规划方法。通过比较采用遗传算法、免疫算法和本论文所设计的免疫遗传算法对AGV进行路径规划结果和效率的比较，分析了所提出的基于免疫遗传算法的AGV路径规划方法的优点。仿真结果表明：

A.本论文采用改进的可视图法对环境信息进行建模，在改变障碍物位置、形状、大小和AGV的起点及终点的情况下，均可快速构建AGV的环境信息模型。

B.采用本论文所设计的基于免疫遗传算法的AGV路径规划方法对AGV进行路径规划，在速度方面优于传统的免疫算法和遗传算法，且系统退化现象基本得到消除。

参考文献

[1]吴锋，杨宜民.一种基于栅格模型的机器人路径规划算法[J].现代计算机（专业版），2012，4（3），7-9，13.

[2]沈凤梅，吴隆.基于改进人工势场法的移动机器人自主导航和避障研究[J].制造业自动化，2013，35 （12），28-30，39.

[3]李善寿，方潜生，肖本贤.全局路径规划中基于改进可视图法的环境建模[J].华东交通大学学报，2008，25（6），73-77.

作者简介

第5篇

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)12-2882-04

Threshold Citrusimage Segmentation Research and Analysis

WANG Jun, ZHOU Li-juan

(Collegeof Information Science and Technology, Hunan Agricultural University, Changsha 410128, China)

Abstract：Image segmentation is an important and primary problem in the field of computer vision. The thesis puts forward a full set of cit? rus image segmentation algorithm, which adopts improved genetic algorithm combining with improved threshold method. The thesis, through simulation experiment, brings forward threshold scope which is more stable, and makes the image segmentation edges more dedi? cated.

Key words: navel orange; threshold segmentation; classes distance; improved genetic algorithm

图像分割是计算机视觉领域的一个重要而且基本的问题。它在农产品无损检测方面得到了广泛的应用。图像分割算法好坏会直接影响检测系统的准确度。它是从图像处理到图像分析的一个关键步骤。对它的研究一直都是图像技术研究中的热点和焦点之一。但由于图像的特殊性，针对具体图像，针对具体问题，分割算法就不一样，至今还没有找到通用的分割理论，也没有找到对所有图像都适合的通用分割算法。

近几年来，基于遗传算法的图像分割方法得到了很多学者的研究。由于遗传算法在搜索方面具有很强的优势，而图像分割的实质是在众多的参量中去寻找一个最优参量，以此作为分隔的依据。于是如果在图像分割中引入遗传算法去求取最佳阈值，将会大大提高分割效率。

本论文重点对基于传统遗传算法的图像分割算法进行了比较系统的研究。针对传统遗传算法的不足，提出了一些改进措施，并且设计新的阈值确定方法——类类距离法，将两者结合共同运用到脐橙图像分割中，得到了比较好的效果。在最大程度上避免基本遗传算法收敛性差，容易早熟等问题。

1脐橙图像分割

对于脐橙出产大省湖南省，每年脐橙收获完后的分类，分等级进行销售是一项工作量庞大的任务。脐橙表面破损自动检测系统就是基于计算机视觉技术研发而成，其检测的精度较人工挑选有很大提高。该系统中脐橙图像分割算法好坏会直接影响系统检测脐橙表面是否破损的准确度。

通过特定装置获得比较清晰的彩色脐橙图像后，对于表面有破损的脐橙，要进行筛选清理。进行破损部分比对前，要对彩色脐橙图像先进行分割处理。把整幅图像分成脐橙和背景两部分，再提取脐橙部分的图像进行破损分析。这要求将脐橙的边缘和破损部分处理得非常清晰，最大可能的避免将破损区域误分割成图像背景。

2改进的遗传算法

2.1控制参数改进

在遗传算法中，直接影响到算法的收敛性的关键参数是：交叉概率与变异概率，它们的选取会影响到算法行为和性能。在适应度值变换的情况下将交叉概率与变异概率随之调整，以达到保证算法收敛性的目的。于是我们对交叉概率和变异概率按照如下公式进行自动调整：

图5本文提出的算法分割效果图

从表1，图2至图5可以得出以下结论：

1)脐橙图像利用遗传算法来分割，每次运行所得阈值都在变化，但变化的范围不是很大，只是在一定区域做细微波动。这种情况是正常的，也是完全可以接受的，其原因是由于遗传算法随机生产初始种群，这种随机性就带来了阈值的波动性。这也是遗传算法不稳定性的体现。但从表中数据看出采用本文所设计的改进的遗传算法，即交叉概率和变异概率随适应度自动调整，那么分割的图像所得到的阈值，其波动会限制在一个很小的范围以内（稳定在4个像素以内,阈值最大为60，最小为57），这样既保持了群体多样性，又保证了遗传算法的收敛性。同时其稳定性也明显地优于其他算法。

2)利用本文所设计的类类距离遗传算法进行图像分割可以极大减少阈值计算时间，平均运算时间比起其他几个常用方法都缩短了不少，平均仅在2.3s左右。在进化代数相同的条件下，本论文提出的图像分割算法较其他算法更有优势，收敛速度更快。

3)从图2至图5这几个图像分割结果图来看，本文所设计的分割方法中对脐橙图像中的破损部分，边缘轮廓等细节都有非常好的体现，可见结合遗传算法和类类距离法所设计出的图像分割新算法比其他常用算法有很大的优势。

本文通过改变的遗传控制参数结合类类距离法，把改进后的遗传算法应用到脐橙图像分割中去。仿真实验结果表明，此图像分割算法由于所设计的寻找最优阈值的方案比较合理，阈值的计算时间缩短了，使得最终图像分割所用时间明显减少了。同时此方法还做到了将阈值范围稳定在4个像素以内，大大提高了算法全局收敛的稳定性。而且从视觉角度来看，其分割效果更明显，图像边缘处理很细致、清晰。实验证明本论文设计的算法分割图像不仅快速准确，而且还能满足各种图像的实时处理、分析的需求。具有较高的通用性和实用性。

[1]姚敏.数字图像处理[M].北京:机械工业出版社,2006.

[2]孙艳歌,邵罕.基于改进遗传算法的最优阈值图像分割算法[J].信息系统工程,2010,10(6),26-27.

[3]童小念,刘娜.一种基于遗传算法的最优阈值图像分割算法[J].武汉理工大学学报：交通科学与工程版,2008,32(02),301-304.

[4]王强.图像分割中阈值的选取研究及算法实现[J].计算机与现代化.2006(10).54-56.

[5]左奇,史忠科.基于模糊理论的图像分割方法[J].西北工业大学学报,2003,(03):313-316.

[6]劳丽,吴效明,朱学峰.模糊集理论在图像分割中的应用综述[J].中国体视学与图像分析,2006,11(3):200-205.

[7]曹芳,吴迪.基于可见-近红外反射光谱技术的葡萄品种鉴别方法的研究[J].光学学报,2009,29(2),537-540.

第6篇

关键词:量子遗传算法;多目标分配;最优化

中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01

一、引言

遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]

目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。

量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。

本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。

二、量子遗传算法

在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。

一个 位的量子位染色体就是一个量子位串,其表示如下:

其中 。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个 位的量子染色体可以表达 个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。

为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:

(1)进化代数初始化: ;

(2)初始化种群 ,生成并评价 ;

(3)保存 中的最优解 ;

(4) ;

(5)由 生成 ;

(6)个体交叉、变异等操作,生成新的 (此步可省评价);

(7)评价 ,得到当前代的最优解 ;

(8)比较 与 得到量子概率门 ,保存最优解于 ;

(9)停机条件 当满足停机条件时,输出当前最优个体,算法结束,否则继续;

(10)以 更新 ,转到4)。

三、基于量子遗传算法的多目标分配应用

如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。

模型构建:设工厂有i个生产车间。 为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则 为在第i个车间生产该产品的总收益。由题意知为求解 最大问题。

仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:

此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。

四、结论

基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。

参考文献:

[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73

[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808

[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83

第7篇

关键词：遗传算法；肝脏CT图像；图像分割；阈值

中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)04-0864-02

Research on Liver CT Image Segmentation Based on Genetic Algorithm

KONG Xiao-rong1, SHI Yan-xin2, LIU Peng1

(1.Department of Computer Technology，Inner Mongolia Medical College, Huhhot 010059; 2.Department of Mathematics and Physics, Xi'an Technology University, Xi'an 710032, China)

Abstract: Genetic Algorithm (GA) is a global optimization and random search algorithm based on natural selection and genetic mechanism. It is suited to dealing with the tradition searching algorithms which cannot solve difficult and complicated problem. And it have great potentialities. First, this paper discusses fundamental principle and primary features of Genetic Algorithm. And it emphases on image segmentation based on GA. Then applying genetic algorithm to select theproper threshold, and it uses maximum entropy method to process liver CT images by segmentation methods. It obtains the results by segmentation experimentation and analyses the results.

Key words: genetic algorithm; liver CT images; image segmentation; threshold value

遗传算法(Genetic Algorithm, GA)的基本思想来源于Darwin的生物进化论和Mendel的群体遗传学，该算法最早是由美国Michigan大学的John Holland教授于20世纪70年代创建，之后，遗传算法的研究引起了国际组织及学者的关注。遗传算法通过模拟生物的遗传进化过程形成一种全局优化概率搜索算法，提供了一种求解复杂系统优化问题的通用框架，可以不依赖于问题的具体领域[1]。近年来，遗传算法已被广泛应用于函数优化、组合优化、生产调度、自动控制、人工智能、人工生命、机器学习、图像处理和模式识别等多个领域，具有巨大的发展潜力。本文主要介绍遗传算法在医学图像处理方面的应用。

1 遗传算法的基本原理

遗传算法是模拟生物进化和遗传机制发展起来的一种全局优化、随机、自适应搜索算法。它模拟了自然界遗传过程中的繁殖、和变异现象，依据适者生存、优胜劣汰的进化原则，利用遗传算子（即选择、交叉和变异）逐代产生优选个体（候选解），最终搜索到适合的个体。

遗传算法的运算对象是由N个个体所组成的集合，称为群体。遗传算法的运算过程是一个群体反复迭代的过程，这个群体不断地经过遗传和进化操作，每次按照优胜劣汰的进化原则将适应度较高的个体以更高的概率遗传到下一代，这样最终在群体中将会得到一个优良的个体，它将达到或接近于问题的最优解[2]。

遗传算法的求解步骤如下：

1）编码：定义搜索空间解的表示到遗传空间解的表示的映射，两个空间的解需一一对应且编码尽量简明。遗传算法把问题的解也称为个体或染色体，个体通常由字符串表示，字符串的每一位称为遗传因子，多个个体形成一个种群。

2）初始化种群 随机产生N个个体组成一个种群，此种群代表一些可能解的集合。GA 的任务是从这些群体出发，模拟进化过程进行优胜劣汰，最后得出优秀的种群和个体，满足优化的要求。

3）设计适应度函数：将种群中的每个个体解码成适合于计算机适应度函数的形式，并计算其适应度。

4）选择：按一定概率从当前群体中选出优良个体，作为双亲用于繁殖后代，一些优良的个体遗传到下一代群体中，适应度越高，则选择概率越大。进行选择的原则是适应性强的优良个体将有更多繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了适者生存原则。

5）交叉：交叉操作是遗传算法中最主要的遗传操作。对于选中的用于繁殖的每一对个体，随机选择两个用于繁殖下一代的个体的相同位置，在选中的位置实行交换。交叉体现了信息交换的思想。

6）变异：从群体中选择一个个体，对于选中的个体按一定的概率随机选择改变串结构数据中某个串的值，即对某个串中的基因按突变概率进行翻转。变异模拟了生物进化过程中的偶然基因突变现象，遗传算法中变异发生的概率很低。对产生的新一代群体进行重新评价、选择、杂交和变异。

7）终止准则：如此循环往复，使群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度满足某一性能指标或规定的遗传代数，迭代过程收敛，算法结束。

2 遗传算法在图像分割处理中的应用

在图像处理中，图像分割是图像三维重建的基础，常用的分割方法包括阈值法、边缘检测法和区域跟踪法，其中阈值法是最常用的方法[3]。图像阈值分割算法是利用图像中目标物体与背景灰度上的差异，根据图像灰度值的分布特性把图像分为不同灰度级的目标区域和背景区域，目前已有模糊集法、共生矩阵法、四元树法、最大类间方差法、最佳直方图熵法、最小误差阈值法等多种阈值分割方法。

遗传算法在图像分割中的作用是：帮助现存的图像分割算法在参数空间内搜索参数，或者在候选的分隔空间内搜索最优的分隔方案[3]。在参数空间内搜索参数主要是指利用遗传算法的全局搜索特性优化现有的阈值分割算法，用于帮助确定最佳分割阈值。

3 基于遗传算法的肝脏CT图像分割

本文基于遗传算法选取阈值，采用最大熵原则对肝脏CT图像进行分割。目的是将图像的灰度直方图分成两个或多个独立的类，使得各类熵的总量最大，根据信息论，这样选择的阈值能获得的信息量最大[4]。在图像的灰度直方图中设定一个灰度阈值，可以把图像分成背景和物体两类区域，这是一般的单阈值选择的情况，而设定N个阈值，可以把图像分成N+1类区域[4]。

最大熵分割方法步骤为：

用p0,p1,…,pn表示灰度级的概率分布，如果把阈值设置在灰度级s，将获得两个概率分布，一个包含1到s间的灰度级，另一个包含s+1到n间的灰度级，这两个分布如下：

其中，与每一个分布相关的熵为：

令: (4)

当该函数取最大值时即为图像的最佳分割，用此函数作为遗传算法中的适应度函数。通过遗传算法的设计步骤，取得最佳阈值，既而对人体肝脏中有病灶组织的CT图像进行分割，得到下面分割处理实验结果。

(a) 原图 (b) 分割结果(c)原图 (d) 分割结果

图1 对有病灶肝脏图像进行分割

通过实验结果可以看到，基于遗传算法采用最大熵原则，对人体肝脏CT图像进行分割，能够使选取的阈值获得的信息量比较大，从而原始图像和分割图像之间的信息量差异最小。因此分割后的图像效果明显，具有一定的优势[5]。

但由于医学图像的复杂性和人体的差异性，对人体同一器官不同状况的图像，无法找出一种最为适合的分割方法处理，必须根据具体情况具体分析，针对图像的特点来选取相应的分割算法，才能较好地解决问题。

参考文献：

[1] 田莹,苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报,2007,12(3):389-396.

[2] Hsieh puted Tomography Principle, Design, Artifacts and Recent Advances（中文翻译版）[M].北京:科学出版社,2006.

[3] 徐丹霞,郭圣文,吴效明,等. 肝脏CT图像分割技术研究进展[J].医疗卫生装备,2009,30(3):34-36.

第8篇

    论文摘要:随着计算机技术的飞速发展,智能计算方法的应用领域也越来越广泛。本文介绍了当前存在的一些智能计算方法,阐述了其工作原理和特点,同时对智能计算方法的发展进行了展望。

    The Analysis for Several Classic Algorism of Intellegence Computation

    YANG Ming-hui

    (Wuhan University of Technology, Wuhan 430074, China)

    Abstract: As the computer technology develops fast, the field for intelligence algorism become wider and wider.In this paper, I introduce some methods for intelligence, and analyze their Principles and characters, finally make a Forecast of the develop of integellence computation.

    Key words:Intelligence Computation; Artificial Neural Network Algorithm;Genetic algorithm;Annealing Algorithm

    1 引言

    智能算法也称作为“背影算法”,是人们从现实的生活中的各种现象总结出来的算法。它是从自然界得到启发,模仿它的原理而得到的算法,这样我们可以利用仿生原理进行设计我们的解决问题的路径,这就是智能计算的思想。这方面的内容很多,如人工神经网络技术、遗传算法、模拟退火算法等,下面分别对其进行分析。

    2 人工神经网络算法

    2.1 人工神经网络(ARTIFICIAL NEURAL NETWORK,简称ANN)

    人工神经网络是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年代初期,心理学家McCulloch、数学家Pitts就提出了人工神经网络的第一个数学模型,从此开创了神经科学理论的研究时代。其后,F Rosenblatt、Widrow和J. J .Hopfield等学者又先后提出了感知模型,使得人工神经网络技术得以蓬勃发展。

    2.2 人工神经网络的特点

    人工神经网络的知识存储容量很大。在神经网络中,知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息,而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。

    由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大,使得它具有很强的不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清,神经网络仍然能够联想思维存在于记忆中的事物的完整图像。只要输入的模式接近于训练样本,系统就能给出正确的推理结论。

    正是因为人工神经网络的结构特点和其信息存储的分布式特点,使得它相对于其它的判断识别系统,如:专家系统等,具有另一个显着的优点:健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是,当一个人的大脑因意外事故受轻微损伤之后,并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因,无论是网络的硬件实现还是软件实现中的某个或某些神经元失效,整个网络仍然能继续工作。

    人工神经网络是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限,标志着人们智能信息处理能力的一大飞跃。

    3 遗传算法

    3.1 特点

    遗传算法是解决搜索问题的一种通用算法,对于各种通用问题都可以使用。搜索算法的共同特征为:(1)首先组成一组候选解;(2)依据某些适应性条件测算这些候选解的适应度;(3)根据适应度保留某些候选解,放弃其他候选解;(4)对保留的候选解进行某些操作,生成新的候选解。在遗传算法中,上述几个特征以一种特殊的方式组合在一起:基于染色体群的并行搜索,带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。

    遗传算法还具有以下几方面的特点:

    (1)遗传算法从问题解的串集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。

    (2)许多传统搜索算法都是单点搜索算法,容易陷入局部的最优解。遗传算法同时处理群体中的多个个体,即对搜索空间中的多个进行评估,减少了陷入局部最优解的风险,同时算法本身易于实现并行化。

    (3)遗传算法基本上不用搜索空间的知识或其它辅助信息,而仅用适应度函数值来评估个体,在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

    3.2 运用领域

    前面描述是简单的遗传算法模型,可以在这一基本型上加以改进,使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域:(1)优化:遗传算法可用于各种优化问题。既包括数量优化问题,也包括组合优化问题;(2)程序设计:遗传算法可以用于某些特殊任务的计算机程序设计;(3)机器学习:遗传算法可用于许多机器学习的应用,包括分类问题和预测问题等。

    4 退火算法

    模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中ΔE为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f ,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt,每个t值时的迭代次数L和停止条件S。

    5 展望

    目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识,但智能计算将在21世纪蓬勃发展。不仅仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模仿,而是具有相同的特性。这两者的结合将开辟一个全新的领域,开辟很多新的研究方向。智能计算将探索智能的新概念,新理论,新方法和新技术,而这一切将在以后的发展中取得重大成就。

第9篇

[关键词] 配送 车辆路径问题 时间窗 遗传算法

随着经济全球化趋势的加强，科学技术尤其是信息技术的发展突飞猛进，产品营销范围日趋扩大，社会生产、物资流通、商品交易及其管理方式正在发生着深刻的变革，与此相适应，被普遍认为企业在降低物资消耗、提高劳动生产率以外的“第三利润源”的现代物流在世界范围内广泛兴起，目前正在成为全球经济发展的一个重要热点和新的经济增长点。随着传统批发、交通运输、仓储业向现代物流转化，尤其是配送方式的采用，对运输成本和时间的有效控制日渐成为城市配送车辆路径问题的一项重要目标。VRP一直以来都是车辆调度所重点研究的方向。而在城市内采取的配送方式恰恰具备了VRP问题的一般特征和优化调度条件。

一、VRP模型的条件及假设

VRP问题是指按要求用多个车辆从配送中心对顾客进行配给货物。各顾客点的位置和需求量为己知，各车辆的装载质量己知，力求寻找一个好的配送方案，使得总代价最小(车辆尽量少，行车总距离尽量短，总费用尽量低等)，由VRP的定义不难看出，必须满足以下条件及假设：

1.仅考虑位置已知的单一配送中心，所有的配送车辆以配送中心为起点，并最终回到配送中心。

2.每条配送路径上各需求点的需求量之和不超过车辆的装载质量，被配送货物是可混装的货物。

3.每条配送路径的长度不超过车辆一次允许行驶的最大距离，配送中心有足够的资源以供配送，并且有足够的运输能力。

4.各个客户需求和所在地均已知，每个需求点的需求由且仅由一辆车一次送货满足。

5.满足总时间约束与时间窗口。必须在时间区间[ei,lj]访问点i客户，并允许在i处等待，车辆服务的总时间不能超过物流中心的时间约束。

6.多个客户之间存在优先关系，必须在访问客户j之前访问客户i。

二、带时间窗VRP模型的建立

基于文献一文中的模型，并考虑配送系统是一个服务系统，所提供的服务必须能够让客户方便、满意。配送系统的运作成本必须和配送系统其他性能参数综合进行考评，单纯对成本进行评价是没有任何实际意义的。需要关注和努力的是：要在保证配送满足客户要求、提升客户满意度的同时，通过各种技术和管理手段，降低运作成本。因此，本文将建立改进的运输路径模型，在传统的车辆配送成本最小化目标的基础上，兼顾客户对配送时间的要求，使车辆等待和延误时间之和最小化。

（1）

（2）

式中K――车队规模，即总的车辆数目；

k――车辆数目(k=1,2,……,K)；

N――有待访问的总的客户的数目；

O――配送中心；

Q――每辆车辆的容量，这里假设所有车辆同质，容量均为Q;

i,j――顾客数(i=1,2,……,N；j=1,2,……,N)；

T――个很大的数字；

C――每辆车单位运距的运费；

t0――车辆从配送中心出发的时间；

e0――车辆可离开配送中心的最早时间；

ei――到达客户i处规定最早到达时间；

l0――车辆返回配送中心的最晚时间；

li――到达客户i处规定最晚到达时间；

dij――从客户i到客户j的距离；

pj――每个客户单位卸货量的卸载费用；

mi――客户i的货运需求量；

tki、tkj――第k辆车到达客户i、j处的时间；

tij――连接客户i和客户j的行驶时间；

si――客户i处的服务时间；

wi――在客户i的等待时间，wi≥0。

两个决策变量如下：

这个模型通用性很强，经过参数的不同设定，可以转换为其它组合优化问题的数学模型。

三、带时间窗VRP模型的遗传算法求解

在模型的处理上，根据本文提出的模型单位标量不统一的特殊性来选择权重系数变化法，将变化后的多目标函数经分析和试验得出各个子目标函数的数量级大小并确定权重，最后加权化为单目标函数用遗传算法求解。

1.惩罚函数的引入。在以往的对含有时间窗约束的车辆配送系统的研究中，所研究的成本大多仅包含行驶成本，但事实上，还包括其它成本(如装卸搬运成本)，将时间窗约束转化为惩罚函数而体现在模型中。

式中c1――车辆在任务点处等待单位时间的机会成本。

c2――车辆在要求时间之后到达单位时间所处以的惩罚值(c1和c2的大小，要根据实际情况来定)。

2.建立适度度函数。根据遗传算法中适应度函数的特点，需要将原目标函数式变化为：

(4)

(5)

式中A*，B* ――变化后的目标函数值，取值范围为[0，1)；

Amax,Bmax――分别是原始目标函数。

适应度函数因此变化为：f(A,B)=α×A*+β×B*(6)

经过分析和实验发现，A*，B*经过处理后，A*的数量级一般是10-2，B＊的数量级一般是10-1。

3.用遗传算法求解带时间窗VRP模型。本文取α＝0.8,β＝0.2，用遗传算法进行求解。在运用遗传算法求解后，验证了该算法易于理解，对问题的依赖性较小，对其求解的函数要求简单，实现起来简单高效，若参数选择的合理，收敛速度很快，但是遗传参数的控制对于算法的收敛速度影响很大，在参数选择方面有一定难度。虽然文中使用的是根据以往学者经验选定的参数，但计算表明最优解所在“代”数的稳定性不是很好，这也是以后需要进一步研究的地方。

四、结论

在传统的车辆配送成本最小化为目标的基础上，兼顾客户对配送时间的要求，建立了带时间窗的车辆路径优化多目标模型。在对模型的处理上，将两个量纲不统一的子目标函数除以各子目标函数的最大值后使其变成无量纲的函数，并通过权重系数变化法将各个子目标函数线性加权和作为多目标优化问题的适应度函数，使得多目标优化问题转化为单目标优化问题后再用遗传算法求解。

参考文献:

[1]王 惠:引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文,2006:1～13

[2]盛丽俊:带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文,2002:13～57

[3]牟燕妮:物流配送中路径优化的选择研究.沈阳工业大学硕士论文,2006:28～41

第10篇

【关键词】多目标优化 进化算法 遗传算法 组合算法

中图分类号：TP18

1引言

大多数多目标优化问题，每个目标函数之间可能是竞争的关系，优化某一个函数的同时，往往以牺牲另一个优化目标为代价，如果将多目标转化为单目标函数优化时，各优化目标加权值的分配带有很大的主观性，必然造成优化结果的单一性，没有考虑全局优化。而如果将多目标函数利用评价函数法转化为单目标函数求解，得到的仅仅是一个有效解，所以我们可以考虑直接采用多目标函数的优化方法对多目标进行优化[1-2]。

2多目标优化的发展现状

在多目标优化问题中，各分目标函数的最优解往往是互相独立的，很难同时实现最优。在分目标函数之间甚至还会出现完全对立的情况，即某一个分目标函数的最优解却是另一个分目标函数的劣解。求解多目标优化问题的关键，是要在决策空间中寻求一个最优解的集合，需要在各分目标函数的最优解之间进行协调和权衡，以使各分目标函数尽可能达到近似最优。多目标优化问题不存在唯一的全局最优解，而是要寻找一个最终解。得到最终解需要通过各种算法来实现，如进化算法、模拟退火算法、蚁群算法、粒子群算法和遗传算法等[3-4]。由于各种算法存在应用领域的差异和自身缺陷，人们也提出了一些改进算法和组合算法。

2.1进化算法

进化算法 （Evolutionary Algorithms，EA）是一种仿生优化算法，主要包括遗传算法、进化规划、遗传规划和进化策略等。根据达尔文的“优胜劣汰、适者生存”的进化原理及盂德尔等人的遗传变异理论，在优化过程中模拟自然界的生物进化过程与机制，求解优化与搜索问题。进化算法具有自组织、自适应、人工智能、高度的非线性、可并行性等优点[5]。

进化算法在求解多目标优化问题上优势在于：一是搜索的多向性和全局性，通过重组操作充分利用解之间的相似性，能够在一次运行中获取多个Pareto最优解，构成近似问题的Pareto最优解集；二是可以处理所有类型的目标函数和约束。三是采用基于种群的方式组织搜索、遗传操作和优胜劣汰的选择机制，不受其搜索空间条件的限制。

虽然基于Pareto最优解的多目标进化算法可以得到较好分布的最优解集，但如何保证算法具有良好的收敛性仍是一个热点问题。

2.2模拟退火算法

模拟退火（Simulated Annealing，SA）算法是根据物理中固体物质的退火过程与一般组合优化问题之间的相似性，基于Monte-Carlo迭代求解策略的一种随机寻优算法。SA在初始温度下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。SA具有以下优点：通用性强，对问题信息依赖较少，可有效避免陷入局部极小并最终趋于全局最优。因此在诸多工程和学术领域得到了研究与应用[6-7]。遗憾的是它在多目标优化领域的研究与应用尚少。

2.3蚁群算法

蚁群算法（Ant Colony Optimization， ACO）是一种用来在图中寻找优化路径的正反口的新型模拟进化算法。。蚁群算法具有并行性、分布性、正反馈性、自组织性、较强的鲁棒性和全局搜索能力等特点。目前运用这种方法已成功地解决了旅行商（TSP）问题、Job-shop调度问题、二次指派问题等组合优化问题。

由于蚁群算法需要的参数数目少，设置简单，在求解多目标优化问题时存在一些困难。首先，多目标函数优化问题是在连续空间中进行寻优，解空间以区域表示，蚂蚁在每一阶段可选的路径不再是有限的，蚂蚁在信息索的驻留和基于信息素的寻优上存在困难。文献[8]提出先使用遗传算法对解空间进行全局搜索，再运用蚁群算法对得到的结果进行局部优化；文献[9]修改了蚂蚁信息素的留存方式和行走规则，运用信息素交流和直接通讯两种方式来指导蚂蚁寻优；文献[10]将搜索空间划分为若干子域，根据信息量确定解所在的子域，在该子域内寻找解，也取得了满意的结果。

其次，蚂蚁算法需要较长的搜索时间、容易出现早熟停滞现象。文献[11]提出了具有免疫能力的蚂蚁算法和蚁群遗传算法，提高算法的寻优能力和寻优效率。

最后，多目标优化问题由于解的多样性，不仅要求所得的解能够收敛到Pareto前沿，而且要有效地保持群体的多样性。蚂蚁之间的这种信息素交流方式，会使所求得的解集中在解空间的某一区域内，不利于群体多样性的保持。

2.4粒子群算法

粒子群优化算法（Particle Swarm Optimization，PSO）是在1995年由美国社会心理学家Kennedy和电气工程师Eberhart共同提出的，源于对鸟群觅食过程中的迁徙和聚集的模拟。它收敛速度快、易于实现且仅有少量参数需要调整，目前已经被广泛应用于目标函数优化、动态环境优化、神经网络训练等许多领域。

由于直接用粒子群算法处理多目标优化问题，很容易收敛于非劣最优域的局部区域，以及如何保证算法的分布性等问题，Coello等人提出了基于Pareto的多目标粒子群算法（MOPS0），强调了粒子和种群之间作用的重要性[12]。

多目标粒子群优化算法作为一种新兴的多目标优化算法具有以下优点：（1）在编码方式上PSO算法比较简单，可以直接根据被优化问题进行实数编码；（2）对种群的初始化不敏感，可达到较快的收敛速度；（3）算法适用于绝大多数的多目标优化问题；（4）优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习和记忆的功能；（5）该算法在收敛性、解的分布性以及计算效率方面具有很大改善。

2.5遗传算法

遗传算法（Genetic Algorithm，GA）是进化算法的一种，是美国密执安大学的John Holland教授于七十年代中期首先提出来的，从生物进化的过程中得到灵感与启迪，模拟人自然“物竟天择，适者生存”的自然选择的法则创立的。

与其他优化算法相比，遗传算法求解多目标优化问题的主要优点：一是保证算法的收敛性，即在目标空间内，所求得的Pareto最优解集与实际Pareto尽可能的接近。二是多样性的维护，即希望找到的Pareto最优解集具有较好的分布特性（如均匀分布），且分布范围尽可能的宽阔。三是具有很好的鲁棒性，是一种高度并行、随机、自适应能力很强的智能搜索算法，因此特别适合于处理传统搜索算法解决不好的复杂非线性问题。四是新的遗传算法引入精英概念，使进化的每一代的Pareto最优解总是直接保留到下一代的群体中，提高了Pareto最优解的搜索效率。五是引入用户的偏好信息，以交互的方式表达偏好，使用决策者的偏好信息来指导算法的搜索过程和范围[13-14]。

3多目标优化研究的热点问题

多目标优化问题中，各个目标之间通过决策变量相互制约，对其中一个目标优化必须以其他目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。传统优化方法往往强调最优化，在解决因多种复杂因素难以建模，或根本不存在传统意义上的最优解或获得最优解的代价太大的优化问题时。由此，采用满意优化方法解决这类问题是较好的策略。满意优化本质上是一个多目标优化方法，它摒弃了传统的最优概念，它将优化问题的约束和目标融为一体，将性能指标要求的满意设计与参数优化融为一体，强调的是“满意”而不“最优”。所以，近年来，满意优化也逐渐成为各领域关心的问题。

4结束语

多目标优化问题是近年来人们越来越需要面对和解决的问题。除了以上单一优化算法外，很多学者已经在单一优化算法的基础上，结合多种优化算法解决了一些多目标优化问题，如NSGA-Ⅱ与MOPSP的结合算法[15]，模拟退火算法与遗传算法的结合算法[16]。然而，由于各种多目标优化算法的不同特点和缺陷，如何使这些优化算法能够更好地无缝对接，对解决多目标满意优化问题具有非常重要的意义。

参考文献

[1]玄光男，程润伟著.周根贵译.遗传算法与工程优化，清华大学出版社，2004.

[2] Liu Zhen Yu .Multi-objective optimization design analysis of primary surface recuperator for microturbines[J].Applied Thermal Engineering 28（2008）：601～610.

[3]肖晓伟等.多目标优化问题的研究概述.计算机应用研究，2011（03）

[4] Kalyanmoy Deb，Amrit Pratap，T Meyarivan.A fast and elitist multi-objective genetic 2002.6（2）：182～197.algorithm： NSGA-II [J].IEEE Transactions on Evolutionary Computation.

[5]杨海清.进化算法的改进及其应用研究.浙江工业大学硕士论文，2004.

[6]邓俊等.基于神经网络和模拟退火算法的配煤智能优化方法[J].冶金自动化，2007（3）.

[7]韩强.多目标应急设施选址问题的模拟退火算法[J].计算机工程与应用 ，2007（30）.

[8]陈峻等.蚁群算法求解连续空间优化问题的一种方法[J].软件学报 2002，13（12）.

[9]Dorigo M，Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Trans. Evolutionary Computation，1997，1（1）：53-56.

[10]张德勇，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策 2005，20（2）

[11]毛宁.具有免疫能力的蚂蚁算法研究（硕士学位论文） 河北工业大学.2006

[12]张慧敏.改进的粒子群计算智能算法及其多目标优化的应用研究（硕士学位论文）.

杭州大学.2005.

[13]李金娟.遗传算法及应用的研究[J].电脑与信息技术，2013（02）.

[14]洪朝飞等.面向机械设计的一种改进的遗传算法.太原科技大学学报，2013（02）.

[15]王金华等.基于NSGA-Ⅱ与MOPSP融合的一种多目标优化算法[J].

第11篇

关键词：公路路线；知识工程；遗传算法

中图分类号：X734 文献标识码：A 文章编号：

1引言

公路选线设计要根据项目需求并且综合考虑生态、环境、经济等各个方面，从大面积着手，由面到带、由带到线，逐步细化、逼近，确定线路空间位置、协调布设各种建筑物。选线设计过程受到地形、地质、水文、土地利用以及各种技术规范和需满足的运输要求约束，资料种类繁多，有数值的、字符的、图形的、图像的，而且还要考虑各种定性、定量、确定性和不确定的因素，另外主观需要和评价指标具有不可公度性和不一致性，使得设计决策过程异常复杂，难以建立涉及各种因素的统一决策数学模型。

虽然多种计算机辅助设计在选线设计中发挥了一定作用，基本实现了勘测设计一体化，但是还存在方案有限、决策周期长、评价指标单一、设计劳动强度大以对采用方案的科学性缺乏有效论证等问题。这些问题得从公路路线优化，引入人工智能的角度加以解决。

2 国内外研究现状

2.1国外研究现状

人工智能的普遍发展，引发了在铁路和公路领域应用的热潮，尤其是在智能交通系统和运输管理方面。但是人工智能在选线方面的应用却不多，近年来，其应用主要体现知识工程和把遗传算法引入平、纵断面优化中，以增加优化方法的实用性、易用性和准确性。

（1）知识工程的应用

1986 年苏格兰Strathclyde大学的Milne,P.H研究开发曲线半径选择和设计集成系统RODEOS，根据输入的现场地物约束和设计要求，利用规则知识选择、设计平面曲线或缓和曲线，并能协调处理平、竖曲线的重合问题。

1988年哥伦比亚大不列颠大学的学者和发表了题为《公路选线产生式系统》的文章，对不确定信息处理、空间数据的结构描述和常规评价与启发式原理的结合进行了探索。

1994年哥伦比亚大学的Khan,Sarosh I.等人在《Journal of Transportation Engineering》介绍了他们开发的集成数据库管理的公路维修专家系统4RSCOPE，该系统根据室内或现场数据来决定工程措施。

2004年西班牙Lawrence Mandow等联合西班牙工程公司开发的用于辅助公路初步设计的智能系统Sindi，已经在西班牙工程公司安装，用于辅助设计人员快速产生方案和进行方案评价。

（2）遗传算法的应用

线路优化技术能否成功的关键是：良好的搜索算法和总费用准确有效算法，遗传算法可以处理离散、连续或联合型目标函数或约束，其进化算子的遍历性使其能有效检索到全局最优解，且能通过与应用领域的启发规则杂交有效解决应用领域的具体问题，其基本原理是：首先自动生成连接起、终点的大量方案组成方案集合，然后对各方案进行费用和约束满足情况评价，从方案集合中选出较优的方案进行杂交以产生下一代方案集合，如此反复计算，直到评价指标没有较大改进为止。

1998年美国马里兰大学的Jyh-Chemg Jong在其博士论文中,在分析了现有优化方法的不足之处后，引入了遗传算法。

在2001年IEEE智能交通会议上，波兰格但斯克理工大学的WladyslawKoc提出了一种平面线形计算的新方法，他研究了用遗传算法计算考虑地形障碍时铁路反向曲线间非标准连接曲线的计算方法，这样设计出的线形不仅能合理处理地形障碍，而且有更好的动力特性，但距现场实用还有很长的距离。

2.2国内研究现状

1987年国家自然科学基金重大项目“工程建设中智能辅助决策系统”应用研究中的“公路路线设计方案生成专家系统”子课题开始了人工智能在公路选线中应用。该系统属工程设计型专家系统，系统针对公路选线设计的特点，将整个设计过程分成若干阶段，采用循环反复的控制流程，知识表示以框架和产生式规则为主，在约束控制下利用深度优先搜索策略成线路路径，然后利用评价模块对方案进行评价，在生成与判断之间合理地分配知识并对知识进行分块和分类处理。

1988年，北方交通大学主持研究“单线铁路技术改造方案决策专家系统”开始研究，用于模拟专家的思维过程进行单线铁路技术改造方案拟定，并对各可行方案进行综合评估、工程数量和造价计算。之后其在1992年进行铁路平面选线专家系统研究。1993～1996年采用黑板结构和产生式规则知识表示方法，用扩充与或图的深度优先搜索算法和不精确推理，以Turbo Prolog语言实现铁路中间站选址智能辅助决策系统；1994年，用Turbo Prolog和Turbo C语言实现，具有数据处理与分析、判别与评价、对策建议与决策支持的黄土地区铁路工程地质评价系统；基于专家系统的铁路工程造价估测系统；1994年，用Turbo Prolog语言编制、在COMPAQ386微机及兼容机上实现，采用谓词逻辑和产生式规则表示知识的铁路工程地质选线咨询系统；1998年，采用面向对象知识表示方法，运用包括模糊规则推理、约束满足推理、数据库的查询与数值计算等推理方法的国防交通铁路工程保障指挥决策专家系统。由于铁路选线本身的复杂性，以上的研究都尚未达到实用的目的。

3 研究现状分析

知识工程在线路领域应用的研究已经有了几十年的历史，从单独的曲线半径选择发展到了考虑多目标的初步设计智能助手，初始方案的生成以及综合性评价等离不开知识工程。但是公路选线设计考虑因素众多，虽然做了一些理论研究和方法探索，并尝试开发一些实用性系统，但是在实用性上远远没有达到“智能”要求，还要依赖设计人员。

遗传算法具有自适应，全局寻优，高度并行性等优点在数值处理方面发挥了很大作用，但是公路选线不仅仅需要数值处理，它还需要处理图形、图像，决策过程需要知识，经验的综合。遗传算法只有与GIS系统结合后才有效兼顾了地理、地质、水文等方面的信息以及选线知识，为选线交互设计提供了初始优化方案。从研究现状资料可以看出，遗传算法在平纵面的优化中得到应用，其与GIS系统结合的研究已经取得一定成效。目前遗传算法应用存在的难点是算法的设计和处理上如何更好地构造合适的适应度函数并有效地处理约束条件问题以及设计合适的遗传算子，从而得到更好的优化结果。

4 结语

本文对国内外知识工程，遗传算法等智能方面的研究进行分析发现：知识工程还远未取得实质性成果，在实际应用方面存在明显不足，应当随着计算机技术的不断发展进行进一步的研究；现今的优化算法虽然考虑了路线的多目标问题，但是在本质上还是单目标优化，人工智能的研究还有很大的空间。

参考文献：

[1]韩春华，易思蓉，吕希奎．人工智能在选线领域的研究现状分析[J]．计算机工程与应用．2005；29：229~232

[2]周宁，王富年．公路选线专家系统[C] ．1991年度论文集.北京:中国建筑工业出版社．1996；9(4) ：23~28

[3]Spring Sarosh I，Ritchie Stephen G，KampeKar．Integrated system to develop highway rehabilitation projects[J]．Journal of Transportation Engineering，1994；120(1)

第12篇

关键词：遗传算法；运筹学；应用

中图分类号：F27 文献标识码：A

收录日期：2011年10月28日

一、遗传算法简介

遗传算法（GAS）是由美国密执根大学的Holland等人创立的。与其他启发式方法顺序搜索解空间的工作方式不同，遗传算法采用解的种群作为工作单元，使用模仿生物进化的适者生存原则指导搜索并改进目标。种群由代表个体的定长字符串组成，每个个体表示解空间的一个点，每个解的质量，通过依赖于问题目标函数的适应值函数来进行评估。搜索过程通过进化来进行，每代中的个体以正比于它的适应值的概率遗传到下一代。它使用3个基本算子：选择、交叉和变异。选择是指个体以其适应值比例复制到池中；交叉是池中的两个个体进行，组合形成一个（或几个）新个体，复制和交叉将好的特性进行遗传；变异则是发生在少数字符串某基因位上的基因的突变，它使搜索过程能够有机会从搜索到的局部最优解逃出。

解决一个实际问题的遗传算法通常包括下列两个决策步骤：（1）将求解问题模型化为符合遗传算法的框架。可行解空间的定义，适应值函数的表现形式，解的字符串表达式方式；（2）遗传算法参数的设计。种群规模，复制、交叉、变异的概率选择，进化最大代数，终止准则设定等。

二、遗传算法的基本特点

（一）结构特点。遗传算法是以适应值提供的启发式信息进行搜索的，与其他启发式（模拟退火、爬山法、神经网络等）方法相比，在结构和工作过程方面的特点见表1。（表1）

（二）实验性能方面的特点

1、高效性。遗传算法具有大范围全局搜索的特点，与问题领域无关，前期工作量比较少。

2、健壮性。遗传算法的搜索是用种群作为基本单元，采用三个不同作用的基本算子进行搜索的，解的结果随时间增加而趋于稳定，不受初始解的影响，而且不因实例的不同而蜕变。

3、通用性和灵活性。遗传算法可用于多种优化搜索问题，解题程序可以通用，针对不同的实例，适当调整算子参数，就可以使算法执行获得最佳的解结果和占用CPU机时的关系。

三、遗传算法在解决经典运筹问题中的应用

（一）旅行商问题（TSP）。旅行商问题自诞生以来，颇受数学家推崇，今天的旅行商问题已远远超过其本身的含义，成为一种衡量算法优劣的标准。旅行商问题是采用非标准编码遗传算法求解最成功的一例，基因编码用推销员顺序经历的城市名表示，求最佳路线即是改变编码次序而求最低适应值的问题。对类似字符串使用标准交叉，产生的后代可能有重复或丢失的元素，因而成为非可行解。为克服这种困难，人们提出许多非标准的交叉和变异方法：交叉主要采用重排序方法――部分匹配重排序，顺序交叉和循环交叉等；变异主要采用位点、反转、对换、插入等方法，使旅行商问题得以有效地解决。值得一提的是，清华大学张雷博士提出的自适应多点交叉算子，能够保证多点交叉后路径的可行性，加快了搜索速度。

（二）作业调度问题。作业调度问题同样是自然变更次序的问题，可以用基于变更次序的遗传算法进行处理。（表2）

（三）背包问题。一维、二维和三维背包问题在商业和工业领域有着广泛的应用，基于遗传算法的求解方法很多。传统求解采用启发式规则，决定下一步该装哪一块和装在哪里，此时变更次序的编码与启发式安置策略是利用遗传算法解决这类问题的最为出色的方法，Lin使用一系列的惩罚项指导其搜索策略，测定单个个体的适应值。

Bortfeldt使用一个层次背包问题，个体用它们的层次代表，当两个亲代被选择交叉时，它们的层次混在一起，从中选择最好的作为子代的第一层，再从余下的组件中选择最好的作为第二层，以此类推，直至产生所有的层次。

陈国良等设计了一种“与/或”交叉方法，使子代继承双亲的同型基因，对杂型基因采用不同支配方式，这种策略为遗传算法的硬件实现创造了良好的条件。

（四）时刻表排定问题。Corne对Edinburgh大学7日内的28个时间期间安排40门课的考试问题作了处理，寻找一个可行的时间排定表，使每个学生参加的考试在时间上能够错开，时刻表用字符串代表，字符串每个位置代表一门课，该位置的值代表考试的时间，用均匀交叉和标准变异操作求解。

这类问题扩展到基于二维的矩阵代表的逼近问题，Colorini使用行代表教师列代表可用的小时数的矩阵，每个单元的值为教师在此时承担的任务，包括教室和其他一些资源配置，教师的任务是事先给定的，故行都是可行的，列代表的时间安排可能会发生冲突，将此冲突用惩罚函数表示在适应值函数中，而且采用修复算子在评价之前尽量将结论调整回可行区域内，该算法用Milan学校的实际数据进行了检验。

除此之外，遗传算法在运输问题、指派问题、分割问题及网络计划优化问题等方面都获得了非常成功的应用，这些问题被认为是NP类问题，其规模随变量的增加呈指数增长，遗传算法在这些问题的求解中，充分体现了其操作性能方面的优势。

四、应用和推广中存在的问题

在上述问题中，遗传算法求解展示了优良的性能，但遗传算法并未像其他启发式方法那样容易地被OR学者广泛接受而用于大量的实际问题中，究其原因，主要有以下几点：

（一）传播方式的障碍。遗传算法最初的工作是以密执根大学严谨的研究小组作为研究项目和学术讨论中心，当研究成员扩大时，这类讨论会演变为机构的学术会议（美国现有5个，欧洲有3个，我国目前还没有），许多研究者聚于此而远离问题导向，有关的会议论文公开出版数量很少，而且，由于历史原因，研究者常常将他们的研究结果选择在有关人工智能的杂志上发表，导致了应用遗传算法的信息很缓慢地扩散到其他不同技术应用领域的工作者中，这与模拟退火等其他启发式方法快速在运筹学会议及杂志上发表相反。由于缺乏交流导致了两方面的问题：一是许多关于遗传算法的论文不能与从其他方法得到的结论进行质量的比较，二是削弱了许多遗传算法多的潜在使用者用遗传算法与其他方法竞争的信心。

（二）术语的隔膜。初始跨入遗传算法领域的使用者常常感到起步非常艰难，遗传算法依赖于遗传学的术语也像模拟退火的术语来自于统计热力学一样。然而，温度、冷却等可能很快赋予新的意义，但遗传算法中的基因位、染色体、遗传型却难以很快被人理解和接受；另外，许多发表的研究偏重于用某些专门函数检验他们的新思路或新设想，这对于全面理解该技术固然是一件好事，但对于一个面对如此丰富复杂材料的初用者会发现，他将不知从何做起。即使一个非常愿意使用遗传算法的人，也要有足够的决心去克服上述障碍。

（三）方法的局限性。对于具有强约束的优化问题，采用惩罚函数逼近常常达不到预想的结果。Radcliffe评论说：“约束通常被认为是遗传算法面临的最大问题”因为惩罚因子选择不当时，会招致错误结论。目前，求解带约束优化问题的启发式遗传方法已经有了一些，但是，它们多数与问题领域相关，在这方面还缺少普遍适用的方法的系统研究。

（四）编码的困难。不是所有问题解空间中的点都能明显地用编码表示，作为OR研究者，常常从问题结构取得利益，用矩阵、树、网络或其他更适用的方法建立表达式；串表达中的建筑块假说建议适用较少的字符，导致人们对二进制编码的偏爱，但二进制编码具有一定的映射误差（实际计算时，我们是把问题作为整数规划），特别是它不能直接反映出所求问题本身结构特征，因此很难满足生成有意义的积木块编码原则；再者，二进制字符的长度随问题发生明显变化，当问题复杂时会因为编码太长而无法进行正常工作。

以上的种种阻力，在一定程度上减缓了遗传算法在运筹学实际问题中的推广和应用。

主要参考文献：

[1]陈国良等.遗传算法及其应用.北京：人民邮电出版社，1996.6.

第13篇

作者简介：陈 轩（1990―），男，湖北汉川人，硕士研究生，研究方向：智能控制与智能应用。

文章编号：1003-6199(2014)02-0089-04

摘 要：区域防空雷达网是防空作战空情预警的发展趋势，为了提高区域雷达网探测能力和抗综合电子干扰、抗隐身技术与隐身飞机的威胁，抗低空、超低空突防及抗反辐射导弹(ARM)的能力，研究雷达组网的问题，介绍免疫遗传算法的基本原理和特点，提出基于免疫遗传算法的雷达组网方法，通过计算机仿真实验证明方法的可行性。

关键词：免疫遗传算法；雷达组网；覆盖系数

中图分类号：TP39文献标识码：A

お

Approach to Radar Netting Based on Immune Genetic Algorithm

お

CHEN Xuank, HUANG Xinhan

(School of Automation, Huazhong University of Science and Technology, Wuhan,Hubei 430074,China)

Abstract:Regional airdefense radar netting is the tendency of air defense warfare in future, in order to improve the detective performance and the performance of anti synthesized electronic interference, anti stealth technique and stealth aircraft, anti low, ultra low altitude penetration and anti anti-radiation missiles(ARM), radar netting is studied. The principle and characteristics of immune genetic algorithm is introduced, and immune genetic algorithm is put forward in radar netting. The simulation experiment by computers indicates valid of this method.

Key words:immune genetic algorithm; radar network; coverage coefficient

1 引 言

随着新型空袭兵器和航天技术的不断发展，单台雷达无论在探测能力上，还是电子防御功能上都有较大的局限性，因此雷达组网技术在现代战争和人类对宇宙的探测中起着举足轻重的作用，该技术是通过将多功能、多类型、多频段的雷达进行组网，实现实时数据传输，资源共享，并在此基础上对数据实时处理，这已被证明是一种有效的方法［1］。雷达组网系统的关键问题是如何对多台雷达进行最佳组网以获得最优的防御能力。目前进行雷达组网的方法很多，常用的有效用函数法或专家法，它们是根据雷达覆盖防守区域面积、雷达部署任务、单台雷达探测距离、地形、衔接角、遮蔽角、起伏角等因素进行加权求和得到阵地的效用值，但是这些都不能很好地解决执行速度的问题。将免疫遗传算法应用于雷达组网，能较快地使布阵接近最优解，从而避免了采用穷举的方法带来执行速度慢的问题，并且克服了遗传算法未成熟收敛和局部搜索能力差的缺陷。

2 免疫遗传算法原理和设计

2.1 免疫遗传算法原理

生物免疫系统对抗原会自动产生相应的抗体来防御，这一过程被称为免疫应答。在此过程中，部分抗体作为记忆细胞保存下来，当同类抗原再次侵入时，记忆细胞被激活并产生大量抗体，使再次应答比初次应答更迅速，体现了免疫系统的记忆功能。同时，抗体与抗体之间也相互促进和抑制，以维持抗体的多样性及免疫平衡，这种平衡是依浓度机制完成的，即抗体的浓度越高，则越受抑制，反之亦然，体现了免疫系统的自我调节功能。抗体的浓度计算是系统保持种群多样性的基本手段之一［2］。

传统的遗传算法是一种具有“生成+检测”的迭代过程的搜索算法，而免疫遗传算法IGA (Immune Genetic Algorithm，IGA)则是一种借鉴生物免疫系统的自适应识别和排除侵入机体的抗原性异物的功能，将生物免疫系统的学习、记忆、多样性和识别特点引入的遗传算法。在解决实际问题时，目标函数和约束条件作为抗原输入，随后产生初始抗体群，计算抗原和抗体的亲和力用来描述可行解与最优解的逼近程度，并通过一系列遗传操作的计算，在保持抗体多样性的情况下，找出针对该抗原的抗体，即问题的解［3］。免疫遗传算法与传统的遗传算法相比，具有如下显著特点：

1）具有免疫记忆功能：可加快搜索速度，提高总体搜索能力，确保快速收敛于全局最优解；

2）具有抗体的多样性保持功能：可提高全局搜索能力，避免未成熟收敛；

3）具有自我调节功能：可提高局部搜索能力。

2.2 免疫遗传算法设计

免疫遗传算法在标准遗传算法的基础上增加了抗体浓度概率计算、抗体的促进与抑制等模块来提高解的多样性。该算法因为将免疫系统中抗体多样性维持机制引入了遗传算法，使得其性能比标准遗传算法更进了一步。在解决实际问题时，目标函数和约束条件作为抗原输入，随后产生初始抗体群，并通过一系列遗传操作及抗体亲和度的计算，在保持抗体多样性的情况下，找出针对该抗原的抗体，也就是问题的解［3］。免疫遗传算法的流程图如图1所示，其基本的步骤如下：

计算技术与自动化2014年6月

第33第2期陈 轩等:基于免疫遗传算法的雷达组网方法

1）算法初始化。输入抗原及设定参数：输入目标函数以及约束条件，作为抗原的输入；设定种群规模、选择概率、交叉概率、变异概率等参数。

2）初始抗体产生。在第一次迭代时，抗体通常在解空间中用随机的方法产生。

3）亲和度及浓度的计算。计算各抗体和抗原的亲和度以及各抗体的浓度。

4）终止条件判断。判断是否满足终止条件，如果满足终止条件，将与抗原亲和度最高的抗体加入细胞记忆数据库，然后终止；否则继续。

5）选择、交叉、变异操作。根据设置的选择概率、交叉概率和变异概率选择抗体，对抗体进行交叉和变异操作。

6）根据以上的操作更新群体以后转入步3)。

ネ1 免疫遗传算法流程图オ

3 采用免疫遗传算法的雷达组网

3.1 雷达组网问题描述

在采用免疫遗传算法进行雷达组网的方案中，雷达的覆盖系数为：

Е=［(∪Ni=1Si)∩Sarea］/Sarea(1)

式中Si为第i台雷达的探测范围，N为雷达总数，Sarea给定的责任区域。ρ∈［0，1］ 表示N台雷达所覆盖的有效责任区域占总责任区域的比重。maxρ为本次雷达组网的目标函数，也就是免疫遗传算法中的抗原，即

maxρ=max ［(∪Ni=1Si)∩Sarea］/Sarea (2)

3.2 抗体编码

雷达坐标是所求问题解的信息，为了缩小抗体空间，提高搜索效率，采用了对雷达组网比较直观的抗体编码方式，假设一共有5台雷达进行组网，则N种雷达布阵的方案可以表示为如下的结构：

X11Y11X12Y12X13Y13X14Y14X15Y15第1种雷达组网方案

X21Y21X22Y22X23Y23X24Y24X25Y25

第2种雷达组网方案

……

Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5

第n种雷达组网方案

其中，Xn1Yn1Xn2Yn2Xn3Yn3Xn4Yn4Xn5Yn5（n表示雷达组网的任意一种方案）分别是第1台、第2台、第3台、第4台和第5台雷达的横坐标和纵坐标。雷达布阵的每一种方案对应为免疫遗传算法中抗体种群中的每一个个体。

3.3 亲和力计算

亲和力是指发生免疫系统识别的抗体和抗原的结构越互补，结合越可能发生，而把彼此结合的强度称之为亲和力。抗原需要尽可能好的与入侵的抗体相结合。二者匹配程度越好，结合就越好，抗原和抗体亲和力就越大。对于雷达组网问题，抗原对应的是雷达组网的最大覆盖系数，由于雷达组网的总责任区域的面积是一定的，可以定义抗体Ab与抗原Ag的之间的亲和力为：

(Ab,Ag)=1Tb－Tg(3)

式中：Tb，Ta分别为抗体Ab，Ag对应的雷达网的覆盖系数，其中Tg也是所求的最大的雷达网覆盖系数。

定义抗体Ab1与抗体Ab2之间的亲和力为：

App(Ab1,Ab2)=1|Tb1－Tb2|(4)

式中：Tb1、Tb2分别为抗体Ab1与抗体Ab2对应的雷达网覆盖系数［4］。

3.4 算法选择、交叉、变异算子

免疫遗传算法能使抗体保持多样性并且最终能够收敛到最优解的主要操作，就是因为在算法中有选择、交叉和变异算子的存在，从而使整个抗体群沿着适应度较好的方向搜索。

1)选择算子

选择是根据适者生存原则选择下一代抗体，在基于免疫遗传算法的雷达组网中选择的是下一代的组网方案。采用如下的选择算子：

PS(xi)=αρ(xi)∑ni=1ρ(xi)+(1－α)1Ne－ciβ(5)

式中：ρ(xi)是以式(1)为适应度函数的雷达组网覆盖系数；ci是抗体xi的浓度，即群体中相似抗体所占的比重［5］，即

ci=和抗体i亲和度大于λ的抗体数N(6)

其中λ为相似常数，一般取为0.9~1；

α和β是常数调节因子； N是该种群内抗体的总数。

2)交叉

交叉是在选中的抗体中，对两个不同的个体按交叉概率Pc随机选中相同的位置进行基因交换(一般交叉概率取值为0.15~0.75)，从而产生新的抗体，也就是新的雷达组网方案。如果对于5台组网雷达，随机选择的是抗体1和抗体2进行交叉，抗体1和抗体2的编码如下：

抗体1：X11Y11X12Y12X13Y13X14Y14X15Y15

抗体2：X21Y21X22Y22X23Y23X24Y24X25Y25

按照交叉概率产生的交叉点为4，则交叉以后的抗体1和抗体2的编码分别是：

抗体1：X11Y11X12Y12X23Y23X24Y24X25Y25

抗体2：X21Y21X22Y22X13Y13X14Y14X15Y15

3)变异

变异是在选中的抗体中，对个体中的某些基因以一定的变异概率对某些抗体的某些位执行异向转化(一般变异概率的取值为0.01~0.2)。在变异的时候，对于交叉过程中产生的抗体方案，随机产生一个介于［-MAX/2, +MAX/2］的数字rand，其中MAX为横坐标和纵坐标可取的最大值。变异以后坐标值x’与原来值x之间的关系如下：

x，=x+rand(7)

变异以后如果x′＞MAX，则取x′=MAX；如果x，

单靠变异不能在求解中得到好处，但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样的时候，选择和交叉无法产生新的基因，这时只能靠变异产生新的基因，即变异增加了全局优化的特质。

3.5 基于浓度的种群更新

由式(5)可见，本文中的选择算子是采用基于抗体的雷达组网覆盖系数以及抗体浓度的选择概率Ps(xi)，从而有效地保证了抗体的多样性，避免了算法的早熟问题，能够获得更好的覆盖系数。

4 仿真实验

根据前面的算法流程，选取目标函数为N台雷达所覆盖的有效责任区域占总责任区域的比重。雷达的台数分别为3台，4台，5台，初始抗体的数量为N=50，即一共有50种方案。利用Иmatlab仿真的结果如图2所示。ネ贾芯匦慰虮硎镜氖亲橥雷达阵地的有效范围(长为200公里，宽为100公里)，雷达的类型一共有两种，即探测范围为50公里的雷达和探测范围为30公里的雷达。参照雷达组网的实际要求，在仿真的过程中，最多只提供2台性能优越的雷达，效能较差的雷达数量不限。

ィa）3台雷达的面积覆盖率

ィb）4台雷达的面积覆盖率

ィc）5台雷达的面积覆盖率

图2 matlab仿真结果

在图2中当雷达数量为3台时，组网雷达的面积覆盖率为87.84%（图2（a））；当为4台时，组网雷达的面积覆盖率为91.53%（图2（b））；当为5台时，组网雷达的覆盖率为94.27%（图2（c））。将仿真的结果与传统遗传算法的组网覆盖率对比［6］，如表1所示。

表1 雷达组网覆盖率对比

3台雷达

4台雷达

5台雷达

传统遗传算法覆盖率

81.5%

86.1%

88.2%

免疫遗传算法覆盖率

87.84%

91.53%

94.27%

由表1可以看出，基于免疫遗传算法雷达组网的覆盖率要高很多，将免疫遗传算法应用于雷达组网是一种有效的方法。

5 结 论

雷达组网能够有效地提高雷达系统的整体性能，更好的适应高科技电子战、信息战。将免疫遗传算法应用于雷达组网系统，能够有效地提高雷达网的面积覆盖率。免疫遗传算法与传统的遗传算法相比，能够克服传统遗传算法的未成熟收敛，提高全局搜索能力。

参考文献

［1］ 彭获由. 区域性雷达组网［J］. 电子科学技术评论, 1992(3) :1- 6

［2］ LUO WENJIAN, CAO XIANBIN,WANG XUFA. An Immune Genetic Algorithm Based on Immune Regulation［A］. Proceedings of the 2002 Congress on Evolutionary ComputationCEC2002. May 12-17, 2002. Honolulu, USA. Vol.2: 801-806.

［3］ 段玉波, 任伟建, 霍凤财, 等. 一种新的免疫遗传算法及其应用［J］, 2005, 20(10):1185-1188.

［4］ 谢刚, 武斌, 谢克明. 基于免疫遗传算法的TSP优化问题求解［J］. 太原理工大学学报, 2007, 38(3): 199-201.

第14篇

论文关键词：病毒进化遗传算法,局部最优解,反转录,转导

遗传算法(GeneticAlgorithm,GA)是一种基于自然选择、遗传变异等进化机制的全局搜索算法。从形式上说，GA也是一种迭代计算，计算过程模拟了生物体的进化机制，从一组解出发，采用类似自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代群体。

为进一步解决GA在解空间快速搜索与易陷入局部最优解之间的矛盾，受人类社会分工和协作的启发，提出了病毒进化遗传算法(VirusCo-EvolutionGeneticAlgorithm，VEGA)。VEGA在进化计算过程中产生两类种群:宿主种群和病毒种群。宿主种群对应问题的解空间,进行遗传操作,在上下代群体之间纵向传递遗传基因,实施解空间的全局搜索；同时病毒群体进行病毒感染操作,在同代个体之间横向传递,实施解空间的局部搜索。VEGA将宿主种群的全局进化和病毒种群的局部进化动态结合,从而病毒进化遗传算法有效解决了上述矛盾。

1VEGA的病毒、生物机制

1.1病毒机制

根据病毒进化理论,病毒是一种特有的生物,具有很强的感染能力,能够获得个体的染色体基因,并感染给另一个体,使得该个体的部分染色体基因发生相应的变化,从而改变遗传信息,又通过遗传传递给下一代,大大加速了生物体的进化换代。

病毒进化过程：首先病毒把基因反转录给邻近主种群中挑选出的个体，然后计算被感染个体的适应度，把病毒模式反转录给被选出的宿主个体，病毒不断感染直到满意为止，计算病毒i的生命力，如果生命力小于0，那么病毒个体从宿主个体中转导一个子链，否则从被传染的主个体中转导部分新子链。

1.2生物机制

生物进化过程：在自然界中生物的DNA结构是稳定的，很难被破坏，然而RNA的结构却不稳定，因此生物将基本继承DNA遗传信息。在VEGA中这种遗传被复制实现，另一方面，病毒又通过自我复制来适应它的宿主(如图1)。

图1：VEGA生物机理

Fig1:VEGABiologyMechanism

2VEGA算法模型

2.1病毒种群的感染操作

病毒对宿主个体的感染算子具有两种搜索操作：

（1）反转录：在宿主个体中随机选出与病毒等长的部分用病毒模式取代，形如病毒中某段为101，则宿主对应段被101取代（如图2），反转录操作突变出新的宿主个体。

（2）转导：借助病毒因子从一种个体转移到另一个体，其目的是产生新的病毒个体（如图3）。

图2：病毒反转录图3：病毒转导

Fig2:Virus’sReverseTranscriptionFig3：Virus’sTransduction

2.2VEGA算法实现过程

宿主种群和病毒种群分别表示待解决问题中的一组候选解和候选解个体上的一个子链，宿主遗传操作的纵向全局搜索和病毒感染操作的水平搜索协同进化共同构成了VEGA算法体系结构（如图4）。

图4：VEGA体系结构

Fig4:VEGASystemStruction

VEGA算法实现步骤：

Step1产生初始种群：生成宿主初始种群，再以一定概率产生病毒初始种群（取1/10~1/5）；

Step2实施遗传操作：以一定概率对宿主种群中的个体进行交叉操作，新个体取代父个体，再以较小的概率使群体中的少数个体发生变异，此时的遗传操作不受病毒影响；

Step3实施病毒操作：取病毒群体中对应主群体的病毒个体，以一定的概率感染主群体，包括反转录和转导两种搜索算子；

Step4计算宿主群体中每个个体感染前后的适应度，并计算病毒全体的感染力和生命力；

Step5选择优良宿主个体，组成同规模的新一代种群，再根据感染力和生命力选择新的病毒个体；

Step6判断终止条件，重复进行步骤2~步骤5，直至满足条件为止。

3TSP问题模拟仿真

3.1TSP问题描述

旅行商问题（TravelingSalesmanProblem,TSP）是著名的NP难题，在TSP问题中，已知N个城市两两间的距离，现有一名旅行者要遍访这N个城市，且每个城市只去一次，最后返回到源出发点，希望安排一条访问路线使得旅行的总路程长度最短。

3.2仿真实验

在这里我们比较了27个城市的VEGA和SGA的性能，VEGA算法的参数设置（见表1）。

表1：VEGA参数

Table1:VEGA’sParameters

交叉概率

变异 概率

宿主规模A

病毒规模A

宿主规模B

病毒规模B

生命衰减率

最大感染率

初始感染率

转导率

病毒浓度上限

0.8

0.001

36

3

64

6

0.9

0.1

0.05

第15篇

关键词：电网规划；地理信息系统（GIS）；遗传算法；现代启发式方法

0 引言

电网规划是电力系统规划的重要环节[1]，电网规划方案的优劣直接影响到电网的建设费用以及运行费用。传统的规划很难对地理实体进行数据采集，规划模型往往也忽略地表因素（障碍物等）的影响，所以精度较低，规划结果往往不具备实用性和可操作性，此外传统的规划很难实现可视化，缺乏直观性。结合GIS 平台，对电网规划问题进行优化，既可以方便的把地貌因素运用到电网规划中，又使规划结果直观可视，从而大大提高了结果的科学性和实用性。

1 基于GIS平台电网规划的特点

在电网规划中引入GIS系统有如下特点：

（1）电网规划要求大量详细的地理信息，如变电站位置、变压器位置等。借用GIS平台可以使规划区域的整个电网直观地显示在屏幕上，规划人员能够方便地确定待选变电站和待选线路路径。

（2）把GIS引入电网规划中，用户可以考虑许多实际的约束条件，如地理位置、街道等的互连关系、街区布局等等，而且由于空间数据模型的引入，这些约束条件对用户是透明的，可以直接从地图上获得，建模工作将得到简化。

（3）结合GIS的电网提供了从文-图和从图-文的双向查询，不但能通过系统开发的查询工具对任意点取图上目标进行所见即所得的查询，而且可以对电网图层空间的每一层设置其显示范围、是否可视等属性[2]～[4]。

2、基于GIS平台的电网规划方法

电网规划分为经典方法和现代启发式方法，传统的经典方法能够得到解析解，在理论上能使得规划结果相对最优，但对问题的规模、约束条件的数量、问题的组合度比较敏感，容易陷入“维数灾”而难以在合理时间内求得结果。近几年出现的基于生物学、人工智能的现代启发式算法具有直观、灵活、计算速度快、不受限于问题规模等特点，不仅遵循配网规划常用规则，而且便于规划人员应用过去的经验，在配网规划中能很快得到近似最优解。由于现代启发式方法优势明显，所以传统的经典方法已经很少使用。

2.1 Tabu 搜索算法

Tabu 搜索方法是一种亚启发式随机搜索算法，它从一个初始可行解X0（为n维向量）出发，选择一系列的特定搜索方向（移动）作为试探，从当前解的邻域N（X）中随机产生一系列试验解X1，X2，… XK选择其中最好的解X*作为当前解，即令Xcurrent=X*，重复迭代，直到满足一定的终止准则。

文献[5]运用Tabu 搜索算法，在GIS平台上对网架模型进行优化。目标函数是年费用最小，年费用为线路的新建投资年费用、维护年费用和运行、折旧年费用，约束条件包含配网辐射限制、负荷需求限制和线路潮流限制三个方面。该文以备选网络的生成树作为Tabu搜索的初始解，使得辐射性的约束自然满足，Tabu 搜索算法中采用“交换移动”进一步判断辐射性，Tabu表是先进先出的管理模式。Tabu 搜索结果可以在GIS界面中形象的观察到。

2.2 遗传算法（GA）

遗传算法是目前比较成熟的一种启发式算法，遗传算法类似于自然进化，通过作用与染色体上的基因寻找好的染色体来求解问题[6]。

文献[7]结合GA 和GIS 提出了一种新的电网规划模型，该模型目标函数中包含线路各种设备投资、维护、运行费用和用户停电损失费用。约束条件为输送功率、电流允许范围、最小电压降以及网络的辐射性。通过根节点融合法来保证网络的辐射性，并考虑到了中间节点和分支点，形成真正可行的网络接线方案，从而使该方法可以考虑各种复杂的网络结构，更适用于电网GIS规划。GA 算子过程采用Elitism 算法：每次构造子代种群时，都从父代种群中选择一定的最优个体直接作为子代个体，在随机选择时，适应度高的以一定比例选中，经试验证明变异率为0.02时遗传算法的性能较好。该文最后对一个算例进行投资总额分析，分析表明考虑可靠性价值可以节省资本，减少配网的投资金额。但该文仅解决了单条馈线优化规划，没有考虑线路之间的接线模式的影响。

2.3电源追踪算法

所谓电源追踪就是在选中杆塔或者杆塔上设备时， 搜索给该设备供电的变电站。

文献[8]将网络拓扑技术与电网GIS的开发相结合， 为电力企业的设备管理及辅助决策提供了图形化的管理工具， 提高了电力企业的工作效率。它提出电源追踪算法，该算法即使在网络拓扑关联属性字段的数据不全时， 也能快速、准确的定位电源点， 提高了电网电源追踪模块的实用性， 更好地满足了实际工程的应用需要。具体算法原理和过程如下：当拓扑信息数据不全时， 算法转为执行基于启发式搜索的拓扑分析追踪。它不需要借助拓扑关联属性字段的值， 而是通过地理信息系统软件提供的拓扑分析函数就可建立起整个电网络， 并通过这个网络进行搜索， 从而选择出设备到其供电电源的最优路径。

3 结论

1、每种算法都有自己的优点，但任何一种算法都有自己的不足。各种算法虽然在理论上能较好的满足规划要求，但还很难便捷的应用到实际中。

2、尽管基于GIS的电网规划方法的研究已取得很多成果，但至今还没有比较完善的电网规划软件能够方便地应用到实际规划工作中。因此，研究开发相对完善实用的电网规划软件和基于GIS的电网规划软件将是电网规划研究工作者们今后工作中的首要任务。

参考文献

[1]赵帅虎，吴健，陈丁剑.基于GIS 配电网自动化分布式协同建模技术的研究[J]. 微型电脑应用.Vol.27，No.1，2011.1：6

[2]王金凤.基于GIS的配电网优化规划研究.硕士学位论文[D].郑州大学，2002.4

[3] 张志波.基于GIS技术的县级配电网架优化规划软件[D].硕士学位论文.河北农业大学，2008.6

[4]张林峰.基于地理信息系统的智能城市电网规划.硕士学位论文[D].华北电力大学，2006.12

[5]杨丽徙，王金凤，陈根永.基于GIS 和Tabu 搜索的配电网优化规划[J].郑州大学学报（公学版）.VOL 23，No.3，2002.9：75-77

[6]刘娜.基于遗传算法的农村配电网检修计划方法的研究[D].沈阳农业大学，2005.10

[7]王春生，赵凯，彭建春.基于地理信息系统和遗传算法的配电网优化规划[J].电力系统自动化.2000.7.48-51

[7]赵强，杨柳.基于启发式搜索的配电网GIS拓扑分析[J]. 计算机应用与软件.Vol.25，No.9，2008.9：181-183

[8]陈珊. WebGIS中最短路径算法及其应用的研究[D]. 上海： 华东师范大学， 2005.