时间：2023-02-04 21:30:32
论文摘要：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结束语
关键词:遗传算法,分类器,分类优化,集成学习
中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)33-9615-02
Discuss the Method of Classification with Genetic Algorithm
WANG Xin-Xin
(Software College, MinJiang University, FuZhou 350011, China)
Abstract: In the classifier system, applied genetic algorithm(GA) to optimized the classifier system which is use a single classify method or multiple classify methods. For the first classifier system, GA make the better precision; and for the other one, GA can make the classifier system to be more precise and apprehensive.
Key words: genetic algorithm(GA); classifier system; classify optimization; ensemble learning
分类问题是集成学习的基本研究问题,即对一个分类器输入一个实例的特征集,然后对这些特征进行判断,对这个样本进行归类并输出。在医疗诊断、语音识别、数据挖掘、人像识别等领域都有广泛的应用。
J.H.Holland于1975年出版了《Adaptation in Natural and Artificial Systems》[1],标志着遗传算法的正式产生。遗传算法是一种概率搜索算法,利用编码技术作用于被称为是染色体的二进制数串,其基本思想是模拟这些串组成的群体的进化过程。遗传算法通过有组织的然而是随机的信息交换来重新组合那些适应性好的串,在每一代中,利用上一代串结构中适应性好的位和串来生成一个新的串的群体。这是一类随机算法,但不是简单地随机走动,而是利用已有的信息来搜寻那些有希望改善质量的串,这个过程类似于自然进化。[2]
1 遗传算法的特点
与其他传统的优化算法相比,遗传算法在搜索的过程中采用群体搜索方式,有利于达到全局最优。依据个体相对优劣的适应度指标进行搜索,即使所定义的适应函数存在不连续、不规则或有噪声等情况,也可进行处理。通过在遗产算法中使用杂交算子,可将算法的注意力更多地集中到搜索空间中期望值高的那部分;同时,为了避免局部最优,在遗传算法中引入变异,这样既可在当前附近找到更好的解得同时保持群体多样性,有利于群体的继续优化。[2]
但是,由于进化的过程具有随机性,遗传算法搜索的结果具有一定的不稳定性,因此,与传统的优化算法相比,遗传算法的优化效率相对较低。[3]
2 基于遗传算法的分类优化方法
文献[4]中提出了一种基于遗传算法的分类优化方法。该方法针对两种分类器进行优化。一种分类器采用一种分类方法,使用遗传算法对分类结果进行优化。另一种是在分类器中使用几种不同的分类方法,使用遗传算法作为综合方法对分类结果进行综合优化。在一套训练集上使用一种方法,由此产生一个唯一的模型,不同的方法在同一套训练集上产生的模型也不一定相同。有些方法在某一类任务上的性能很好,但是在另外一类任务上的性能则较差,它们的预测结果有可能是错的,因此使用遗传算法可以将多种分类方法结合起来提高精度。
2.1 数据和算法集的定义
数据集合L={xn,yn},n=1,…,N},其中,xi是输入属性,yi是输出属性,N是例子数目。设有M个学习算法,分别用A1,A2,…,AM表示。A(R,S),其中A是算法,R是算法空间,S是算法搜索的空间。算法对数据集合进行学习,得到不同的学习结果,利用遗传算法对这些结果进行结合,得到一个综合结果。
2.2 基于遗传算法的组合方法框架
在L0层中,每个算法对输入的训练集数据进行训练,各自生成一套对分类问题的表示,利用规则产生器对将L0层中关于分类问题的表达转换为规则,然后作为L1层的输入。在L1层中使用遗传算法对规则集进行综合,生成最终分类器。这种方法综合各分类器的优点,其结果精度高于各单个分类器,用规则集表示其结果。
2.3 如何使用遗传算法对规则进行优化
1) 编码表示
GlodBerg在上个世纪80年代对遗传算法进行归纳,在文献[5]中总结了遗传算法的基本框架。根据该算法,一个个体代表问题的一组解,每一个个体含有表达全部解的一组规则集。规则由条件和结论组成:“if (x1,y1) and (x2,y2),…,and (xn,yn) then Cj”每一个规则用一个染色体表示。
2) 适应函数
适应函数由匹配值和不匹配值两个参数组成,当分类器能对规则进行正确识别并与结果匹配,则增加匹配值;若不能,则增加不匹配值;如果条件无法识别,则这两个参数都不变。
3) 选择策略
利用遗传算法来产生新的规则,采用限制策略,对于同类规则,可进行进化,而对于结论相同的规则,则只在其条件部分进行进化。对于结论相同的规则只在条件部分进行进化的目的是为了防止出现不收敛的情况。
4) 遗传算子
选择算子:选择算子从群体中选择优秀的个体,淘汰劣质的个体,将适应度高的候选解遗传到下一代。在选择的过程中以适应度为依据进行选择,独立于编码方式。
杂交算子:杂交是按照一定的概率将两个父代个体的部分结构加以交换重组,然后产生新的个体。在本文中,个体间同类规则的相同基因位进行交叉。
图2对遗传算法的交叉算子进行描述。
变异算子:变异算子使个体中某些基因发生突变,遗传算法中的变异运算通过位的取反操作实现。在本文中,通过对属性边界值进行突变实现。图3描述了变异算子。
5) 终止规则
遗传算法循环执行计算适应值,选择复制和应用杂交和变异算子几个步骤,直到找到满足条件的解。
3 优化结果讨论
3.1 对使用一种分类方法的分类器进行优化
文献[4]表明,遗传算法优化后的精度优于使用单个算法的精度。对于属性值十分接近的分类目标,使用单一属性生成的规则进行区分是很难实现的,而只有采用属性值的组合才能实现这类分类目标的区分。
3.2 对使用多种分类方法的分类器进行优化
在文献[4]中,使用遗传算法对基于C5.0和神经网络的规则集进行优化。优化后,得到两套规则集,基于C5.0的规则集边界值发生改变,新的规则在精度上比原来更高。而基于神经网络的规则集在形式上没有发生改变。对两种规则集进行比较,发现基于C5.0的规则集和基于神经网络的规则集均具有较高的精度,但是从理解性的方面考虑,基于C5.0的规则集既有较好的可理解度。
4 小结
该文讨论了一种基于遗传算法的分类器优化方法,在分类技术中结合遗传算法可以得到更好的分类效果,得到的分类结果更精确、易于理解。用分类技术处理原始数据集从而得到初步的规则集,而遗传算法通过优化规则条件的部分边界值提高了分类的精度。这种方法具有较好的鲁棒性和可延展性,当给定的边界值与其正确的位置相距很远,也可通过遗传算法对全局进行搜索得到解空间的最优解;如果在分类器中采用新的分类方法,可将分类的结果转化为规则集作为遗传算法输入,这些新的规则集与已有的规则集一起进行演化,从而得到更好的结果。
参考文献:
[1] Holland J H. Adaptation in Natural and Artificial Systems[M]. MIT Press,1992.
[2] 刘勇,康立山,陈毓屏.非数值并行算法遗传算法[M].2册.北京:科学出版社,1995.
[3] 孙瑞祥,屈梁生.进化计算的过去、现在与未来[C]//进化计算研究生论坛论文集.西安:西安交通大学,2001.
关键词：智能桁架；振动控制；模糊控制器；模糊规则；遗传算法
中图分类号：TU323.4文献标识码： A 文章编号：
引言：
近年来，大型智能桁架结构在航空航天领域得到越来越多的应用。其模型具有不确定性，模型结构和参数在很大范围内变化，基于精确模型的传统控制理论和现代控制理论都有局限性[1]。模糊控制不依赖于被控系统的精确数学模型，而是通过对系统动态特征的定性认识、直接推理、在线确定或变换控制策略，以达到对复杂的、非线性的、不确定性的被控系统的控制，这种方法容易实现，也更加易于保证其实时性。2005年，赵国伟等[2]将PID和LQG成功的应用于大型空间复杂智能桁架结构的振动主动控制上，2009年，张京军等[3]将模糊控制应用于智能悬臂梁的控制当中。本文基于对智能桁架结构模型的认识与分析，设计出相应的模糊控制器，并采用遗传算法对其控制规则进行优化，然后通过一实例仿真验证该方法的有效性。
1智能桁架结构有限元模型
设智能桁架结构中共有个压电主动杆，考虑压电主动杆的机电耦合特性，基于有限元法，建立智能桁架结构的运动方程: （1）
式中，、、分别为质量矩阵、阻尼矩阵和刚度矩阵、、分别为加速度矢量、速度矢量和位移矢量；是由主动杆的方向余弦组成的向量矩阵；为外部节点力矢量；是维主动杆产生的控制力向量。
为简化结构的仿真模型，对智能桁架结构的动力学模型做模态截断处理,则其独立模态空间的动力学方程及观测方程为：
（2）
（3）
式中，、、，，为第阶振动的固有频率，为第阶的模态阻尼比，为外界干扰力，为维模态控制力，其中为模态向量矩阵，为对角阵，为第个作动器单位压电作用下产生的控制力，为对角阵，为第个主动杆等效刚度，为模态坐标，为作动电压。
2.模糊控控制器的设计
目前振动控制中常用的模糊控制器多为双输入-单输出的结构形式。本文采用的也是这种结构模式，其输入输出变量分别为智能桁架的结构位移、速度和对其施加的控制反力。这三个变量都要从物理论域量化到整数论域上，然后再在整数论域上给出若干语言变量值，从而实现整个论域元素的模糊化过程。本文将位移和速度作为误差和误差变化率。设量化值、有统一论域，的论域为。为表达控制规则需先确定输入变量、输出变量的词集，为了简化设计过程，设计量化后的误差、误差变化、控制量的词集均为：负大（NB）、负中（NM）、负小（NS）、零（ZO）、正小（PS）、正中（PM）、正大（PB）。在模糊化时，输入变量选择三角形和梯形的隶属函数，输出变量选择三角形隶属函数。模糊控制规则直接影响到控制系统的性能，本文根据桁架的位移、速度和控制力之间的关系，总结出用语言值表示的二维控制规则表，见表1.
表1 二维模糊控制器控制规则表
模糊推理采用Mandain法，清晰化采用重心法。
3.遗传算法优化控制规则
利用遗传算法进行优化求解时，首先要对控制规则进行编码，然后选择合适的适应度函数，通过复制、交叉、变异等遗传操作，获取最佳种群，。该种群中最优个体为优化问题的解，即为最优模糊规则。
3.1 遗传编码
遗传算法中常见的编码方法有二进制编码和十进制编码。本文将采用十进制编码方法对模糊控制规则进行编码，用数字集{1,2,3,4,5,6,7}来依次表示模糊语言集{ NB，NM，NS，0，PS，PM，PB }，即对设计的控制规则进行数值化，按从左到右，从上至下的顺序把控制规则展开成一维形式，这样便形成了遗传算法所需要的个体。前面设计的控制器含有49条控制规则，即是含有49个待寻优参数，这样每个染色体就包含有49个遗传基因，每个染色体长度也就是49位。对其进行数字化处理后可以表示为染色体表2
表2 染色体表
3.2 适应度函数选择
要想利用遗传算法对控制规则进行优化，首先要解决种群个体的评估问题。本文研究的是智能桁架结构的模糊控制，其控制目标是在激励荷载作用下使得桁架结构的振幅达到最小、衰减随度达到最快。本文以模糊规则表的49个模糊语言集作为设计变量，以智能桁架结构的自由端最大挠度作为评价控制器性能指标的目标函数。其表达式为：
（4）
因为遗传算法要求个体适应度越大越优，故需将目标函数转化为最大值问题后作为目标函数，转换函数为：
（5）
3.3遗传操作
3.3.1 选择
选择算子是遗传算法中对群体中个体进行优胜劣汰的操作，本文采用适应度比例选择 ，设群体大小为，个体的适应度值为，则个体被选择的概率表示为：
（6）
3.3.2 交叉
交叉运算是两个配对染色体按照某种方式相互交换其部分遗传基因，从而产生两个新的个体。为了保证交叉运算后产生的新一代染色体个体的规则总数量不变，本文采用对位交叉算法。
3.3.3 变异
变异是指将个体染色体编码串中的某些基因位串上的基因值用该位串的其他等位基因来替换，从而产生新的个体。本文在进行变异操作时，是对个体染色体的49个基因，随机选择一位或多位基因值进行变异，随机变异所选用的基因用1-7之间的随机数值来代替
3.4遗传算法实现
首先，确定遗传算法的相关参数：本文的设计变量49个，取种群个数为15个，最大迭代次数取20次。然后，用遗传算法对控制规则进行优化，
4 实例仿真
本文所选桁架是由普通杆和由粘贴有压电片的主动杆构成，其结构尺寸为，共有83根杆件，普通杆是由铝合金材料构成，弹性模量为，密度，泊松比，杆件直径为。主动杆压电片采用压电陶瓷材料，传感器/作动器同位布置，布置在固定端端部，设该桁架结构的模态阻尼比为，顶端节点所受作用力，作用时间为0.01s。
将设计的模糊控制器和在遗传算法优化控制规则后设计的控制器分别作用于智能桁架结构，通过算法程序的运行可以得到
桁架架结构的仿真图：
仿真图中，红色线代表遗传算法优化模糊控制规则后的模糊控制器的控制效果，黄色线表示没有使用遗传算法的普通模糊控制器的控制效果。从仿真图中我们可以看出，遗传算法优化后的模糊控制器比普通模糊控制器有更好的控制效果，每阶的位移曲线最大位移都有明显的较小，智能桁架结构振动的衰减速度也有所加快。
5结论
本文对遗传算法做改进，然后作用在模糊控制器的控制规则优化上的方法是可行有效的，同时也说明了控制规则对于控制器的控制效果起着至关重要的作用。
参考文献
李东旭,陈卫东.大挠性航天桁架结构动力学及其主动控制研究进展[J]，力学进展，2009,38（2）：167-176
关键字：遗传算法；机器学习；人工生命；人工神经网络；神经网络拓扑结构
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)27-2040-03
The Application of Genetic Algorithm to the Artificial Intelligence
WANG Hui
(Xinjiang Petroleum Institute, Urumqi 830000, China)
Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.
Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology
1 遗传算法简介
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。遗传算法借鉴了生物科学中达尔文的物竞天择、适者生存的进化准则，1975年，Michigan大学Holland教授根据这一规律首次提出了遗传算法（genetic algorithm，简称GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定等数学问题，鲁棒性强、随机性、全局性以及适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
2 基本遗传算法
遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。
遗传算法是一种基于空间搜索的算法，它的求解可以看成是最优化过程。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题，你需要知道的仅仅是用什么样的方式对可行解进行编码，使得它能被遗传算法机制所利用。遗传算法并不能保证所得到的解是最优解，但可以将误差控制在容许的范围内。遗传算法具有以下特点：
1） 遗传算法是对参数集合的编码而非针对参数本身进行优化；
2） 遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3） 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4） 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
那么下面对基本遗传算法给出一个求解步骤：
1） 定义一个目标函数；
2） 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量x来编码，称为一条染色体，向量的分量代表基因，它对应可行解的某一决策变量；
3） 计算群体中每条染色体xi(i＝1，2，…，n)所对应的目标函数值，并以此计算适应值Fi，按Fi的大小来评价该可行解的好坏；
4） 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；
5） 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；
6） 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
3 遗传算法的发展动向
GA在应用方面的取得了较丰硕的成果，其主要应用领域在于函数优化，机器人学，设计，组合优化，信号处理，人工生命等，此外遗传算法还有几个引人注目的新动向。
3.1 基于GA的机器学习
这一新的研究方向把GA从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法，这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望，GA作为一种搜索算法从一开始就与机器学习有密切联系。分类器系统是第一个基于GA的机器学习系统。基于GA的概念学习是近几年机器学习领域的一个较为引人注目的研究方向。还有一些嵌入领域知识的基于GA的机器学习的研究。
3.2 并行处理的GA
并行处理的GA的研究不仅是GA本身的发展，而且对于新一代智能计算机体现结构的研究都是十分重要的，GA在操作上具有高度的并行性，许多研究人员都正在搜索在并行机上高效执行GA的策略。近几年也发表了不少这方面的论文，研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并行GA的研究方面，一些并行GA可以分为两类：一是粗粒度并行GA，它主要开发群体间的并行性，如Coboon分析了在并行计算机上解图划分问题的多群体GA的性能；另一类是细粒度并行GA，它主要开始一个群体中的并行性，如Kosak将群体中的每个个体映射到一个连接机的处理单元上，并指出了这种方法对网络图设计问题的有效性。
3.3 GA与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。人工生命与GA有密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
3.4 GA与进化规则及进化策略的结合
GA，进化规则及进化策略是进化计算的三个主要分支，这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性，但三种算法又是从不完全相同的角度出发来模拟生物的进化过程，分别是依据不同的生物进化背景，不同的生物进化机制而开发出来的，所以又有差异。但在进化计算领域内更重要的工作是生物的进化机制，构造性能更加优良且适应性更加广泛的进化算法。
4 基于遗传算法优化神经网络的应用研究
神经网络和遗传算法目标相近而方法各异。因此，将这两种方法相互结合，必能达到取长补短的作用。近年来,在这方面已经取得了不少研究成果，形成了以遗传算法与神经网络相结合的进化神经网络(ENN)。遗传算法在神经网络中的应用主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构两个部分。
4.1 遗传算法学习神经网络的权重
而最主要的是学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法 。目前广泛研究的前馈网络中采用的是Rumel hart等人推广的误差反向传播（BP）算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用遗传算法则可把神经网络的结构优化和权值学习合并起来一起求解，克服了BP算法的缺陷，是神经网络权值学习的有效方法。
遗传算法学习神经网络权值的算法步骤如下：
1） 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，进而构造出一个个码链（每个码链代表网络的一种权值分布），在网络结构和学习算法已定的前提下，该码链就对应一个权值和阈值取特定值的一个神经网络；
2） 对所产生的神经网络计算它的误差函数，从而确定其适应度函数值，误差与适应度成反比关系；
3） 选择若干适应度函数值最大的个体，直接遗传给下一代（精英保护策略）；
4） 利用交叉和变异等遗传操作算子对当前一代群体进行处理，产生下一代（新一代）群体；
5） 重复步骤2～4，使初始确定的一组权值分布得到不断的进化，直到训练目标得到满足或者迭代次数达到预设目标为止。
4.2 遗传算法学习神经网络的拓扑结构
神经网络结构包括网络的拓扑结构（连接方式）和接点转移函数两方面。利用遗传算法设计神经网络可根据某些性能评价准则如学习速度，泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构。利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案。
遗传算法学习神经网络结构的算法步骤如下:
1） 随机产生若干个不同结构的神经网络，对每个结构编码，每个码链对应一个网络结构，N个码链构成种群。
2） 利用多种不同的初始连接权值分别对每个网络进行训练。
3） 计算在每个对应码链下神经网络的误差函数，利用误差函数或其他策略（如网络的泛化能力或结构复杂度）确定每个个体的适应度函数。
4） 选择若干适应度函数值最大的个体构成父本。
5） 利用交叉，变异等遗传操作算子对当前一代群体进行处理，产生新一代群体。
6） 重复上述2）-5）步骤，直到群体中的某个个体（对应一个网络结构）能满足要求为止。
5 结束语
遗传算法作为一种新型的全局优化搜索算法，由于其直接对结构对象进行操作，不存在求导和函数连续性的限定，又具有鲁棒性强、随机性、全局性以及适于并行处理的优点，在人工神经网络的应用上展现了它的独特魅力与优势，但同时，它在理论和应用技术上也存在着许多不足和缺陷，比如相对鲜明的生物基础，其数学基础显得极为薄弱，尤其是缺乏深刻且具有普遍意义的理论分析。随着理论研究的深入，可以肯定，作为一种高效并行的全局搜索方法，遗传算法以其特有的算法特点使其在许多实际问题中的应用会越来越广；同时，广泛的数学方法和强大的计算机模拟工具的出现，必将使遗传算法的研究取得长足的进展。
参考文献：
[1] 蔡自兴. 人工智能及其应用[M]. 3版.北京：清华大学出版社，2003.
[2] 王风琴. 基于遗传算法的神经网络优化[J].燕山大学学报，2001，25（3）：234-239.
[3] 陈国良. 遗传算法及其应用[M].北京：人民邮电出版社，1999.
[4] 陈颖琪. 进化计算与神经网络的结合[J].红外与激光工程，1999，（4）：8-11，35.
[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.
[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE
[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE
[8] 杨旭东，张彤. 遗传算法应用于系统在线识别研究[J].哈尔滨工业大学学报， 2000，32（1）：102-104.
[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.
[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.
[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.
关键词:计算智能;人工神经网络;模糊系统;遗传算法;免疫算法
中图分类号:TP18 文献标识码:A文章编号:1009-3044(2010)09-2207-04
Overview of the Main Algorithm for Intelligent Computing
ZHOU Hong-mei
(Huaihua Technical School, Huaihua 418000, China)
Abstract: In order to resolve some problems that the traditional intelligent method can not breakthrough,and promote the process of intelligentizing machines, Computational Intelligence is presented.The development of Computational Intelligence has given rise to considerable concerns in the machine intelligence field.This paper summarizes several main Computational Intelligence algorithms'developing process,analyzes its'basic theories,and simply introduces its'characters and practical applications.At last,the paper looks ahead the direction of Computational Intelligence's advance.
Key words: computational intelligence; artificial neural network; fuzzy system; genetic algorithm; immune algorithm
众所周知,人们对于生活中遇到的各种复杂的情况可以不假思索的做出决策判断,然而这对于先进的电子计算机却相当的困难,这是由于电子计算机的体系结构所决定的。要想使电子计算机具有较强的形象思维能力,必须突破冯・诺依曼的体系结构,另辟蹊径。近年来,随着人工智能应用领域的不断扩展,传统的基于符号处理机制的人工智能方法碰到的问题越来越突出,特别是在知识表示、处理模式信息及解决组合爆炸等方面[5]。因此,寻求一种适合大规模并行且具有智能特征如自适应、自学习、自组织等的算法已经成为有关学科的一个研究目标。计算智能(CI,Computational Intelligence)在这种背景下应运而生。
早在1988年,计算智能这个概念是加拿大的一本刊物的名字。1992年,美国学者James C.Bezdek在论文《计算智能》中将智能分为生物智能(BI,Biological Intelligence)、人工智能(AI,Artificial Intelligence)和计算智能(CI,Computational Intelligence)三个层次,并讨论了人工智能与计算智能的区别[1]。CI的主要处理对象是应用人员提供的数据材料,包括数字、信号等,它并不依赖于知识;而AI则必须用知识进行处理各种数据信息。计算智能的目标是模仿人的智能,包括模拟人脑的结构和模仿人脑的逻辑思维。
目前主要的计算智能方法有人工神经网络(ANN,Artificial Neural Network)、模糊逻辑(FL,Fuzzy Logic)、进化算法(EA,Evolution Algorithm)、免疫算法(IA,Immune Algorithm)、人工内分泌系统(AES,Artificial Endocrine System)、模拟退火、禁忌搜索算法、粒子群算法、蚁群算法等。其中进化算法又包括遗传算法(GA, genetic algorithm)、进化规划(EP, evolution plan)、进化策略(ES, evolution strategy)。本文分别从算法的产生和发展、算法的基本原理、算法的特点及其应用和发展趋势等方面对几种具有代表性的计算智能算法进行了总结和分析,希望能让读者对计算智能的发展有一个大致的了解。
1 人工神经网络
1.1 人工神经网络的发展
人工神经网络(Artificial Neural Network,ANN)是脑科学、神经心理学和信息科学等多学科的交叉研究领域,是近年来高科技领域的一个研究热点。它的研究目标是通过研究人脑的组成机理和思维方式,进而通过模拟人脑的结构和工作模式使机器具有类似人类的智能。人工神经网络的发展已有60多年的历史。早在1943年,美国心理学家McCulloch和数学家Pitts联合提出了形式神经元的数学模型,即经典的M-P模型,从此开创了神经科学理论的新纪元。其后,Rosenblatt、Widrow和Hoff等学者又先后提出了感知器模型[1,3],使得人工神经网络技术得以蓬勃发展。20世纪六七十年代是人工神经网络发展的低谷期,直到1982年加州大学的物理学家Hopfield提出了Hopfield网络模型并用电路实现,人工神经网络的研究重新进入了兴盛时期。
1.2 人工神经元的工作过程
人工神经网络是由大量处理单元经广泛互连而组成的人工网络,用来模拟人脑神经系统的结构和功能。而这些处理单元称为人工神经元。人工神经元的形式化模型种类很多,最常见的有M-P模型、线性加权模型和阈值逻辑模型。下面通过M-P模型来简单的介绍人工神经元的工作过程。图1为M-P神经元模型图。
人工神经网络中的每一个神经元都可以接受一组来自该网络中其他神经元的输入信号,并且每个输入信号有一定的强度,用连接权值来表示,所有输入信号的加权和决定该神经元的激活状态。假设来自其他处理单元(神经元)i的输入信息为xi,它们与该处理单元的相互作用强度即连接权值为wi(i=0,1,...,n-1),处理单元的内部阈值为θ 。那么该处理单元的输入为:,输出为:。此式中f 称为激发函数或作用函数,它决定了神经元的输出。该输出为1或0取决于其输入和大于或小于内部阈值θ 。激发函数一般具有非线性特性。常用的非线性激发函数有阈值型、分段线性型、Sigmoid函数型(简称S型)和双曲正切型[3]。
1.3 人工神经网络的应用
人工神经网络能较好的模拟人的形象思维,对信息具有很好的隐藏性,还具有容错性强、鲁棒性强和自学习性强等特点,是一个大规模自组织、自适应且具有高度并行协同处理能力的非线性动力系统。人工神经网络理论的应用已经渗透到各个领域[2]。
信息处理领域:包括信号处理、模式识别和数据压缩等方面的应用。
自动化领域:包括系统辨识、神经控制器和智能检测等方面的应用。
工程领域:包括在汽车工程、军事工程、化学工程和水利工程等方面的应用。
经济领域:包括在微观经济领域的应用、在宏观经济领域的应用、在证券市场中的应用、在金融领域的应用和在社会经济发展评价和辅助决策中的应用。
医学领域:包括检测数据分析、生物活性研究和医学专家系统等应用。
2 模糊系统
2.1 模糊理论的发展
模糊概念在生活中普遍存在,如“高”,“大”等。这些模糊概念蕴含了许多不确定信息,人脑可以很容易的通过这些不完整不精确信息做出判断和决策。然而,对于精确的电子计算机而言,处理含糊不清的信息却是相当困难的。基于这个原因,美国控制论专家扎德(Zadeh.L.A)于1965年提出了模糊集合的概念,发表了开创性论文《模糊控制论(Fuzzy sets)》,为模糊系统的研究奠定了坚实的基础。1973年,扎德教授又提出了模糊逻辑(Fuzzy Logic)的理论,并积极倡导将模糊理论向人工智能方向发展。经过众多研究者的不断努力,模糊逻辑理论已经得到进一步发展,并在专家系统不确定推理模型的设计中显示了很强的生命力。另一方面,模糊理论在学术界也得到了普遍的认同和重视。1992年IEEE召开了第一届关于模糊系统的国际会议(FUZZ-IEEE),1993年IEEE创办了专刊IEEE Transaction on Fuzzy System。当前,模糊理论和应用正在向深度和广度进一步发展,发展的速度越来越快,涌现出了大量的研究成果,已经成为了世界各国高科技竞争的重要领域之一。
2.2 模糊系统的原理
模糊系统(Fuzzy System, FS)基于模糊数学理论,能够对事物进行模糊处理。模糊数学基础包括模糊集合、模糊逻辑、模糊规则、模糊推理和隶属度等。在模糊系统中,元素与模糊集合之间的关系是不确定的,即在传统集合论中元素与集合“非此即彼”的关系不适合模糊逻辑。元素与模糊集合的隶属关系是通过隶属度函数来度量的。当一个元素确定属于某个模糊集合,则这个元素对该模糊集合的隶属度为1;当这个元素确定不属于该模糊集合时,则此时的隶属度值为0;当无法确定该元素是否属于该模糊集合时,隶属度值为一个属于0到1之间的连续数值。在模糊系统中,知识是以模糊规则的形式存储的,如:IF E THEN H (CF, λ ),其中E表示模糊规则的条件,H表示模糊规则的结论,它们都是模糊的。CF表示这个规则的可信度,它既可以是一个确定值,也可以是模糊数或语言值,λ 是阈值,用于确定这条知识是否能被应用。模糊推理引擎运用这些模糊规则进行模糊逻辑推理,完成对不确定性问题的求解。图2是模糊系统的基本结构图。
2.3 模糊系统的应用
模糊系统能够很好处理人们生活中的模糊概念,清晰地表达知识,而且善于利用学科领域的知识,具有很强的推理能力。模糊系统主要应用在自动控制、模式识别和故障诊断等领域并且取得了令人振奋的成果,但是大多数模糊系统都是利用已有的专家知识,缺乏自学习能力,无法对自动提取模糊规则和生成隶属度函数。针对这一问题,可以通过与神经网络算法、遗传算法等自学习能力强的算法融合来解决[9,16]。目前,很多学者正在研究模糊神经网络和神经模糊系统,这是对传统算法研究和应用的创新。
3 遗传算法
3.1遗传算法的基本原理
遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国Michigan大学的Holland教授及其学生和同事共同发展起来的,是一种模拟生物界的自然进化规律而形成的一种基于全局的直接优化搜索算法,是一种进化算法。
遗传算法的基本思想源于达尔文(C.R.Darwin)的进化论和孟德尔(G.J.Mendel)的遗传学说。达尔文进化论的最基本原理是适者生存。在生物进化的过程中,只有那些能适应环境的一些个体特征才能得以保留。遗传学说的最基本原理是基因遗传原理,遗传以基因的形式包含在染色体中,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可以产生更适应于环境的后代。经过存优去劣的自然选择,适应性高的基因结构得以保存[3]。
遗传算法用“染色体”来表示问题的解。在执行遗传算法之前,首先给定一个“染色体”群,称为假设解。然后,把这些假设解置于问题的“环境”之中,通过适者生存原则,选择对环境适应度高的“染色体”进行复制,交换和突变等操作。如此逐代进化,最后算法收敛到一个适应度最高的“染色体”,此为问题的最优解。图3为遗传算法的基本流程图。
3.2 遗传算法的特点
遗传算法是一个不断寻找最优点的过程,它始终让整个群体保持进化状态。与传统优化方法比较,遗传算法主要有以下几个特点。
智能性:遗传算法具有自适应、自组织和自学习性等。在求解问题时,在确定编码方案、适应度函数和遗传算子之后,算法将根据自然选择的策略自组织进行搜索。
并行性:遗传算法的操作对象是一个可行解集合,而非单个可行解。它采用同时处理多个可行解,基于全局搜索优化[14]。这使得遗传算法减少了陷入局部最优解的可能性,同时体现了遗传算法良好的并行性。
不确定性:遗传算法的主要步骤都含有随机性,如交换操作、突变操作等,因此在算法的搜索方向具有很大的不确定性[4]。
通用性:遗传算法的处理对象不是参数本身,而是对参数集进行了编码的个体。这种编码操作,使得遗传算法可直接对结构对象进行操作[15];同时,该算法只需要适应度函数来评估个体,无需其他辅助信息。以此,它几乎可以处理任何问题。
作为一种搜索算法,遗传算法在各种问题求解和应用中展现出了它的特点和魅力,同时也暴露出了不足和缺陷。由于遗传算法的处理对象是编码的个体,因此编码方式很大程度上影响了算法的效率和结果;算法本身参数的设置无法定量表示;对于数量较大的群体,算法的收敛速度慢等。目前出现了很多基于上述问题的遗传算法的改进算法[10],如一种快速收敛的遗传算法,通过改变初始化群体的生成方式,较好地解决了算法收敛速率的问题。
3.3 遗传算法的应用
由于遗传算法具有的优点众多,因此其应用范围也极其广泛。遗传算法主要应用于神经网络、模式识别、组合优化、机器学习、图形处理等。下面介绍遗传算法作为一种机器学习技术在分类系统中的应用。
遗传算法在分类系统中主要是对分类系统中的分类器[3],即规则进行学习,用以产生更好的分类规则。其主要步骤如下:
1)根据分类器(规则)的适应度成正比的概率,选择复制出N个规则。
2)对选出的规则,利用遗传算法中的遗传操作(交叉、突变),重新生成N个新规则。
3)用产生的“后代”(新规则)取代分类器中适应度小的规则。
当一次遗传算法学习过程结束之后,如果得到群体中的规则和其父代完全相同,且各规则的适应度值已连续多次保持不变,则认为算法收敛,学习过程结束。
4 免疫算法
4.1 免疫算法的发展
1974年,诺贝尔奖得主,生物学家、医学家、免疫学家Jerne提出了免疫系统的第一个数学模型,为免疫算法的研究奠定了基础。之后Farmer,Perelson,Bersini,Varela等学者先后于1986年,1989年和1990年发表了相关论文,为免疫算法在实际工程中的应用做出了突出贡献,同时他们的研究工作为建立基于免疫理论的计算系统和智能系统开辟了道路。目前,免疫算法已经成为国际智能计算领域关注的热点和前沿课题。2002年,IEEE Transaction on Evolution Computation首次出专刊报到了有关人工免疫系统(Artificial Immune System)的研究进展。在国内,免疫优化算法的理论研究和应用具有鲜明的特色。中国科学技术大学王煦法教授在国内较早开展对免疫优化算法方面的研究,并把它应用到了人工生命和硬件领域。西安电子科技大学焦李成教授提出了比较完备的免疫克隆算法的理论基础以及一些改进算法,并较早地在国际上创造性地提出了免疫算法与遗传算法的结合――免疫遗传算法[6,13]。免疫算法正以朝气蓬勃的姿态发展。
4.2 免疫算法基本原理
免疫是生物体的特异性生理反应。生物免疫系统由具有免疫功能的器官、组织、细胞和免疫效应分子及其基因组成,通过分布在全身的各类淋巴细胞识别和清除侵入生物体的抗原性异物。当抗原入侵生物免疫系统时。首先与抗原亲和力高的抗体受刺激产生克隆和高频变异,生成新抗体种类,然后亲和力更高的抗体结合抗原后引起更强的反应,经过不断循环筛选出匹配抗体。人工免疫系统就是研究、借鉴和利用生物免疫系统的原理和机制发展起来的处理各种工程问题和信息计算问题的智能系统。免疫算法是基于免疫系统的学习算法,它具有良好的应答性和主动性,善于学习记忆,具有较强的模式分类能力。尤其在处理多模态问题时体现出了较高的智能性和鲁棒性。下面简单介绍一般免疫算法的原理。
首先,要对所求问题进行分析,找出待求解的目标函数,把它看成是生物免疫系统中的抗原,把问题的优化解看成是生物系统中的抗体,问题解的正确性或匹配性用抗体和抗原的亲和力来表示。亲和力指抗原和抗体的识别程度或者两个抗体之间的相似度,一般亲和力的公式为:,其中tk为抗体与抗原的结合强度,结合强度可以有各种距离公式求得,如欧几里得距离(ED,Euclidean distance),曼哈坦距离(MD,Manhattan distance)和明考斯基(MD,Minkowski distance)等。
免疫算法的流程如图4所示。免疫算法的步骤如下:
1)抗原的识别,免疫系统确定是否抗原入侵;
2)产生初始化抗体,同时激活记忆细胞,利用先前记忆的抗体消除先前出现过的抗原;
3)计算亲和力。计算所有抗体与入侵抗原的亲和力,选择亲和力最大的抗体,即它对入侵抗原的抵抗力最强,这是一个选择过程;
4)记忆细胞分化,把亲和力最大的抗体加给记忆细胞,以便抵御相同的抗原再次入侵;
5)抗体的促进和抑制;
6)抗体的产生,也就是问题优化解的产生。
4.3 免疫算法的应用进展
免疫系统是一种新型仿生智能算法,综合了分类器、神经网络和机器推理等学习系统的优点,是一种突现计算。免疫算法具有全局优化、鲁棒性强、并行性高和智能度高等特点[7],主要应用于计算机网络安全、智能控制和优化计算等领域[12]。此外,免疫算法在数据挖掘与分析、机器学习和异常与故障检测等方面取得了很大进展。尽管如此,目前对于免疫算法的研究只是处于起步阶段,理论研究和实际应用的深度还不够,而且免疫机理复杂,系统庞大,免疫学家对一些免疫现象也无法清楚的表述,而且免疫算法可以借鉴的成果也不多,所以免疫算法的研究存在着一定的困难。免疫算法和神经网络算法,进化算法一样都是模拟生物智能的算法,因此免疫算法的研究可以参照神经网络算法和进化算法的研究方法,借助其相关研究成果,这将是研究免疫算法的一个新方向。
5 结束语
目前关于计算智能的研究和应用处于蓬勃发展时期,其应用范围遍及各个科学领域。虽然计算智能是一门新兴的综合型学科,而且各种智能方法的发展历史也不是很长,但是其发展却是相当迅猛。当前除了对单一的算法进行研究和应用之外,很多学者开始对各种算法的融合进行研究,针对各个算法的特点,有目的的进行取长补短的算法综合。典型的融合方案有:人工神经网络与模糊逻辑、人工神经网络与免疫算法、人工神经网络与遗传算法、模糊逻辑与免疫算法、模糊逻辑与遗传算法和遗传算法与免疫算法[11]。融合之后的算法可以提高算法的性能,增强了算法的适应性,同时还克服了算法选择的盲目性。另外,还有学者提出了计算智能的新框架――生物网络结构,即神经内分泌免疫网络(NEIN, neuro-endocrine-immune networks)。它由人工神经网络(ANN)、人工内分泌系统(AES)和人工免疫系统(AIS)组成[8]。新框架的提出为人们研究其理论和应用技术提供了新平台。这些研究都为计算智能今后的发展指明了方向。
参考文献:
[1] 周春光,梁艳春.计算智能[M].长春:吉林大学出版社,2009:3-9.
[2] 韩力群.人工神经网络理论,设计与应用[M],北京:化学化工出版社,2007:16-18.
[3] 张仰森,黄改娟.人工智能教程[M].北京:高等教育出版社,2008:322-324.
[4] 王宏生,孟国艳.人工智能及其应用[M].北京:国防工业出版社,2009:139-141.
[5] 尹朝天.人工智能方法与应用[M].武汉:华中科技大学出版社,2007:169-175.
[6] 王磊,潘进,焦李成.免疫算法[J].电子学报,2000,28(7):74-78.
[7] 高家全,何桂霞,王雨顺.典型的人工免疫算法性能比较与分析[J].计算机工程与应用,2009,45(10):208-210.
[8] 丁永生.计算智能的新框架:生物网络结构[J].智能系统学报,2007,2(2):26-30.
[9] 罗熊,孙增圻.计算智能方法优化设计模糊控制系统:现状与展望[J].控制与决策,2007,22(9):961-966.
[10] 董聪,郭晓华.计算智能中若干热点问题的研究与进展[J].控制理论与应用,2000,17(5):691-698.
[11] 苏建元.智能计算主要算法的比较与融合[J].中国电子科学研究院学报,2007,2(1):52-56.
[12] 胡风新,郭红瑾,孙运芳.免疫算法理论及应用研究[J].计算机与数字工程,2009,37(7):46-49.
[13] 高彬彬,杨孔雨.免疫算法研究[J].计算机技术与发展,2009,19(7):249-252.
[14] 王煦法.遗传算法及其应用[J].小型微型计算机系统,1995,16(2):59-64.
【关键词】自动导航小车；路径规划；免疫遗传算法；疫苗
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.
作者简介
【文章摘要】
本文对货物配送企业的选址问题作了分析，对国内外相关问题的研究做了归纳，提出了一种基于遗传算法的货物配送企业的选址问题方案，阐述了方法的具体思想和实施方法。方案考虑了货物配送企业的选址问题过程中存在的各种参数。
【关键词】
课表；遗传算法；计算机
0 引言
货物配送企业的选址的问题最终归结为如何使得各种费用合成的总运营成本达到最小化的问题。为明确表达种费用以及在运算中使用费用值，可将各种费用转化为相应的决定参数的函数。运输费用的相关参数包括运输距离、运输方式和运输量。当然运输费用实际函数并非线性值，为了计算简便，方便判断，可简化为线性函数，这种替代只要处理得当，不影响结果的准确性。运营费用的参数包括劳动力、公用事业费用和其他开支等等。物流中心选址的固定费用则由土地使用、设备和建筑费用组成。重新选址费用由将设备移到新物流中心地址的费用、新物流中心初建费用和关闭旧址处的设施费用等参数来决定。当然还有其它一些相关参数。
多年来，选址问题的解决方法经过了不断的改进和发展，种类繁多，发展很快。特别是随着先进的计算工具的不断出现和应用，一些新的方案变得可行，这成了选址问题得以有效解决折基础。由于遗传算法的先进性和可行性，其在不同行业中应用越来越广，在企业选址问题上可以有效地应用，使问题可以有效收敛，最终解可以达到令人满意的效果，这对于改进易腐物流系统布局，提高易腐物流系统的科学决策水平具有极大的意义。
1 国内外研究现状
早期的选址问题中主要是基于运输成本的，该问题的早期理论的主要研究专家是土地经济学家和区域地理学家。1909年Weber最早提出选址问题，该问题的目标是找到一个使仓库与各处客户之间的总运输距离最短的仓库位置。1929年Holelling提出了另一个选址问题，研究一条直线上两个竞争供应商的选址。1964年，Hakimi的研究打破了以前研究的局限性，使问题更具一般性，形成了统一的理论，这一进步为后来的选址理论的进一步发展打下了坚实的基础，同时更具实用性，可以扩大实际应用。选址问题的研究有进一步深入的必要，因为选址问题和NP-完全问题经常有千丝万缕的联系，可以被更广更深的研究。
2 遗传算法的研究现状
遗传算法（Genetic Algorithm， GA）是一种全新的算法，近年来得以快速发展和广泛应用。它是基于生物体的进化的思想，主要来源于达尔文的进化论和Mendel的遗传学说。1975年Holland及其学生于密执安大学研究创建了遗传算法。由于优化效率和实用性，各国学者开始关注和研究遗传算法，对该算法进行了深入研究和改进。现在每年都有遗传算法的学术会议召开，影响范围越来越广。较为重要的会议包括国际遗传算法学会组织召开的ICGA（International Conference on Genetic Algorithms） 和FOGA（ Workshop on Foundation of GeneticAlgorithms）会议，这些会议成了相关研究人员获取信息和相互交流的平台。
进入90年代，遗传算法的发展速度得以大大提高，在理论研究和应用研究都取得了很多成果，现在遗传算法在各行各业的应用都成为可能，应用领域在不断扩大，遗传算法的效率也在不断提高。研究的过程中也出现了一些一些新的理论和方法。
国内的研究人员也对遗传算法进行了不断地研究，做了许多改进。为了解决局部收敛问题，2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略。2004年，赵宏立等提出了并行遗传算法（Building-block Coded Parallel GA，BCPGA），对简单遗传算法进行改进。2005年，江雷等使用弹性策略来维持群体的多样性，很好地解决了TSP问题。
3 遗传算法的编码
编码负责连接实际目标问题的遗传算法的染色串，在企业选址问题中也要依据不同的实际问题特点进行编码的确定。
对于一般性的企业选址问题，可以采用二进制编码形式。编码选择和确定会直接影响后面的遗传算子的选择，这一点设计交叉算子和变异算法时要重要考虑。
编码要具完备性、健全性、非冗余性。
4 重心法
重心法是用来求解物流企业选址问题的一个有效的方法，首先，要有相关的地图，图中包含物流企业的各个服务对象，图中相关比例要正确； 其次，构建坐标系，为个服务对象确定坐标，获得数据； 最后，建立重心模型，求解；
【参考文献】
[1]李敏强，寇纪淞，林丹，等.遗传算法的基本理论与应用[M].北京：科学出版社，2002年3月第一版.
[2]姜大立，杨西龙.易腐物品配送中心连续选址模型及其遗传算法.2003.2（2）：63-65.
[3]高竟成. 基于遗传算法的紧急物品配送中心选址问题的研究[J]，2009， 6：3-9.
[4]吴江，李太勇，姜，等 基于多样化进化策略的基因表达式编程算法[J].吉林大学学报：信息科学版，2010，28（4）：396-403
[5]李敬花.遗传蚁群融合算法求解多项目资源能力平衡问题[J].计算机集成制造系统， 2010，16（3）：643-649.
[6]陈皓，崔杜武，崔颖安，等族群进化算法[J].软件学报，2010， 21（5） ：978-990.
[7]慕彩红，焦李成，刘逸.求解约束优化问题 M-精英协同进化算法[J].西安电子科技大学学报：自然科学版，2010，37（5） ：852-861
关键词：机器人路径规划算法
一、本文就常见的几种常见的路径规划算法及应用进行简单的探讨如下：
（一）遗传算法概念
遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。基于随机早期人口，根据的原则，优胜劣汰，适者生存，世代演化产生更好的人口大概。在每一代，根据问题域的个体适应度大小来选择个人，然后选定的个人在自然遗传学，遗传算子组合交叉和变异，产生代表性的解集的人口 。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。人口最优个体解码后可作为近似最优解。
（二）遗传算法的特点
作为一种智能算法，遗传算法具有如下特点：①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面积很大，适合全局寻优。③遗传算法根据概率性的变换规则进行个体的优胜劣汰并推动种群的进化。④遗传算法具有隐含的并行性。⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。
（三）遗传算法的应用
遗传算法提供了一个整体框架地址复杂系统问题，它不依赖于俞特定领域的问题，问题的类型、 已是强的鲁棒性，所以广泛应用余许多科学： 功能优化遗传算法的经典应用，是遗传算法的性能评价的常见的例子，许多人建设的各种复杂的表格功能测试： 连续函数和离散函数，凸、 凹函数、 低维功能和高尺寸功能、 单式功能和更多峰值函数。一些非线性、 多模型、 多目标函数优化问题和其他优化方法很难解决，GA 你可以更好的结果。增加问题的规模，搜索空间的组合优化问题，将会迅速增加，有时的当前枚举方法和计算很难找到最佳的解决方案。实践证明，遗传算法、 组合优化问题的粒子非常有效。例如，已成功应用遗传算法解决旅行商问题、 背包问题、 装箱问题、 图形划分问题。此外，遗传算法的生产调度、 自动控制、 机器人技术、 图像处理和机器学习，人工生命，遗传编码，已获得广泛的应用。
二、蚁群算法及其应用
（一）蚁群算法概念
蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。
（二）蚁群算法的特点
①蚁群算法是一种自组织算法。在早期的算法，单一的人工蚂蚁障碍找到求解算法，久而久之，通过信息作用的激素，人工蚂蚁进化将找到一些解决办法更接近最优的解决方案，它是无序到有序的过程。
②蚁群算法的并行算法是一种基本的。每个蚁群搜索进程独立的对方，只能通过信息素通讯。因此，蚁群算法可以看作是一种分布式的多智能体系统，它在问题空间搜索算法开始是一个独立的解决方案，不仅提高了可靠性，这使得该算法具有强的全局搜索能力。
③蚁群算法是一种积极的反馈的算法。从蚂蚁觅食中不难看到蚂蚁已设法找到最短路径的信息的过程取决于直接上的最短路径的积累，以及信息素的积累是一个积极的反馈过程。这种正反馈的过程进行初步的差距有不断扩大，并导致系统的最优解的方向发展。
④蚁群算法具有较强的鲁棒性。比较与其他算法、 蚁群算法、 初始对齐要求不高，外务大臣蚁群算法用于路由和搜索过程的初步结果不需要手动调整。第二，设立简单、 便于应用的蚁群算法求解组合优化问题的蚁群算法参数的殖民地，数目。
（三）蚁群算法应用
蚁群算法应用包括：二次分配问题、车间任务调度问题、车辆路线问题、机构同构判定问题、学习模糊规则问题、旅行社新旅游线路与旅行产品的制作等领域。
三、神经网络算法
（一）神经网络的概念
人工神经网络也被称为神经网络连接模式，它是一种动物模型，神经网络的行为特征，分布式并行处理算法的数学模型。网络依赖于复杂的系统，通过调整内部之间的联系，大量节点，以实现节能的目的，信息处理。
特征的神经网络模型的人工神经网络的主要网络连接拓扑，神经元的特点，学习规则。目前，近40种神经网络模型，其中有一个BP网络，传感器网络，自组织映射，神经，波尔兹曼机，自适应共振理论。系统的稳定性与联想记忆功能密切相关。
神经网络的应用
人工神经网络的非线性自适应信息处理能力，克服了传统人工智能方法的直觉，作为模型，语音识别，非结构化信息处理方面的缺陷，使神经网络专家系统，模式识别，智能控制，组合优化，预测等领域得到成功应用。人工神经网络和其他传统方法相结合，将促进人工智能和信息处理技术的发展。近年来，人工神经网络模拟人类认知方式更深入的发展，模糊系统，遗传算法，进化机制相结合，形成智能计算，人工智能，已成为一个重要的方向，在实际的应用开发。信息几何学应用于人工神经网络的研究，人工神经网络理论开辟了一条新的途径。
关键词：墙土系统；损伤识别；改进多种群遗传算法；损伤程度；噪声
中图分类号：TU317
文献标志码：A
文章编号：1674-4764（2013）03-0001-06
Application of Improved Multi-population Genetic Algorithm to Damage
Identification of Soil-wall System
Liu Libiao， Zhang Yongxing， Chen Jiangong
（College of Civil Engineering； Key Laboratory of New Technology for Construction of Cities in Mountain Area，
Ministry of Education， Chongqing University， Chongqing 400045， P. R. China）
Abstract：
The method of damage identification in soil-wall system was studied； a new approach based on improved multi-population genetic algorithm （IMGA） was developed. First， the simplified dynamic-detection model of soil-wall system was established， meanwhile， the theoretical analysis of characteristic equations in soil-wall system was conducted when soil in damage status. The objective function based on characteristic equations was established. Then， the improvements of multi-population genetic algorithm， including the adoption of real-valued representation， adaptive cross operator and adaptive mutation operator， were conducted. Finally， the localization and quantification of the soil-wall system damage were performed by IMGA with and without the consideration of noise， respectively. The results indicate that damage location and damage extent can be detected efficiently， and anti-noise performance is better.
Key words：
soil-wall system； damage identification； improved multi-population genetic algorithm； damage extent； noise
结构系统损伤表现为结构动态特性的变化，将导致结构产生不同程度的安全隐患。土木工程设施（如高层住宅、大跨度桥梁、地铁和支挡结构等）在现实中具有非常重要的地位，及时对结构进行损伤检测可以减少很多安全事故的发生，准确识别出结构损伤位置和损伤程度是有必要的。在过去几十年里许多结构损伤识别方法不断地被提出，其中采用最优化方法识别结构损伤位置和程度被广泛应用。
遗传算法作为一种基于人工智能的优化算法，具有更强的全局搜索能力，在不同结构类型损伤诊断中的应用很广泛[1-14]。Chou等[1]采用遗传算法对一桁架桥进行损伤识别；Perera等[2]结合特征方程、MTMAC指标构造的目标函数和遗传算法对一简支梁结构进行损伤定位；Koh等[3]基于综合MDLAC指标的遗传算法对结构多处损伤位置和损伤程度进行识别；Meruane等[5]基于模态特性和实数编码的混合遗传算法对三维空间桁架结构进行损伤识别；Nobahari等[6]基于综合MDLAC指标和改进遗传算法分别对悬臂梁结构和桁架结构进行损伤识别；Liu等[7]采用频率改变率和MAC指标值构造多目标函数，基于遗传算法优化求解对简支梁结构进行损伤识别；袁颖等[8-9]提出了一种基于残余力向量法和改进遗传算法相结合的结构损伤识别方法，以节点的残余力向量构造用于遗传搜索优化的目标函数形式，利用改进的遗传算法进行了噪声条件下的结构损伤定位和定量研究；尹涛等[10]在传统遗传算法的变异算子里引入零变异率因子，使种群中时刻保持一定数量的零值元素，即相当于用结构的损伤只是发生在局部这个信息约束了传统的遗传算法，对框架结构进行损伤定位；陈存恩等[11]提出一种结合灵敏度修正的遗传算法对一个4层平面框架结构进行损伤诊断等。然而，现有遗传算法的大多数研究文献都是针对简单的梁结构、桁架结构、框架结构等。
刘礼标，等：改进多种群遗传算法在墙土系统损伤识别中的应用
针对板结构的墙土系统损伤识别研究相对较少，张永兴等[15]对墙土系统模态特性进行分析，仅研究了损伤对模态特性的影响，但并未对损伤识别方法进行研究。为此，本文提出一种改进的多种群遗传算法的墙土系统损伤识别方法，首先利用模态参数和物理参数关系，通过系统特征方程建立目标函数，再利用改进的多种群遗传算法搜索得到系统的损伤位置和损伤程度。主要研究墙后土体存在不同程度损伤时的识别方法，对于挡墙本身存在损伤时，按本文思路也可对损伤位置和损伤程度进行识别。
1基本模型
1.1墙土系统简化动测模型
本文旨在通过反映墙土系统模态特性的特征方程来识别墙土系统的损伤，建立了简化动测模型，为便于分析作以下基本假定：1）悬臂挡墙底板的刚度较大，忽略底板的影响，将立板底部视作固接；2）悬臂挡墙视为薄板单元，离散后计算挡墙结构的质量矩阵、刚度矩阵、阻尼矩阵；3）土体简化成附加刚度和附加阻尼来模拟，和挡墙附着在一起共同运动的墙后土体简化成附加质量集中在节点处；4）挡墙与土体之间完全接触，模型见图1。
文中主要基于墙土系统模态特性进行墙土系统损伤识别，一般情况下阻尼可以忽略不计，因此，图1中土体附加阻尼系数csi取0。
1.2墙土系统损伤动力特性模型
当墙后填土存在不同程度的损伤（如不密实、空洞等现象）时，假定损伤后土体附加刚度可以表示成无损伤状态下土体附加刚度乘以反映损伤程度βi的系数αi，此时简化模型中土体附加刚度可表示为：
假设土体发生损伤仅降低附加刚度，而不考虑附加质量降低，并且土体发生损伤后仍满足线性振动。若q对应无土体附加参数的自由度，r对应有附加土体参数自由度，则有：
2损伤识别的改进多种群遗传算法
简单遗传算法容易出现早熟和停滞现象，为了克服简单遗传算法的缺点，提高全局搜索能力，本文提出应用改进多种群遗传算法（IMGA）进行墙土系统损伤识别，主要对编码方案、交叉算子和变异算子进行改进。IMGA主要思想是每个子种群分别独立采用遗传算法进行复制、交叉、变异操作，子种群每进化若干代就进行子种群间的迁移。
2.1初始化种群
设计的初始种群长度为52，包含的变量分别为各测点对应的墙后土体附加刚度折减系数 （α1，α2，…， α52）。由于识别变量较多，为了提高算法性能，文中采用实数编码方式，同时每个实数个体均能反映1个测点的损伤程度等优点。按照每个变量的范围，随机产生初始种群并分割成M个子种群。
2.2适应值函数的确定及选择操作
墙土系统损伤识别主要目的是识别出各点的附加刚度损伤程度。由于式（8）中不含反映土体损伤程度系数，因此，损伤程度识别问题的关键是如何根据式（9）识别出附加刚度折减系数αi。因此，利用最小二乘法准则，式（9）可转化为求解如下非线性优化问题。
选择f（α）为算法的适应值函数，然后根据非线性排序独立计算各子种群中个体的适应度值。根据个体的适应度值按随机遍历抽样进行选择操作，从种群中选择优良个体。
2.3交叉、变异操作
简单遗传算法中交叉概率Pc和变异概率Pm是不变的，易造成较优个体破坏。因此，本文引入自适应交叉概率Pc和自适应变异概率Pm，其表达式分别如下：
2.4迁移操作
满足迁移条件时，将子种群中最适应的20%（迁移率为0.2）的个体被选择迁移，最邻近的子种群在他们之间交换个体。
2.5终止条件
循环执行2.2～2.4步的操作，直到目标函数 min f（α）达到满意值或达到最大迭代次数时，终止计算。这时输出的变量即为识别损伤位置和损伤程度。损伤识别的改进多种群遗传算法流程图见图2。
本文计算中改进的多种群遗传算法的主要参数：子种群数量M=5，子种群规模N=40，变量个数Nvar=52，交叉概率参数Pc1=0.9、Pc2=0.5，变异概率参数Pm1=0.4、Pm2=0.1，子种群迁移率rMIGR=0.2，遗传代数T=5 000。
3算例研究
研究算例基本参数：某悬臂挡墙弹性模量Ew=28 GPa，泊松比μw=0.2，密度ρw=2 450 kg/m3，阻尼比ξw=0.02；墙后填土弹性模量Es=288 MPa，泊松比μs=0.3，密度ρs=1 800 kg/m3，阻尼比ξs=0.05，粘聚力Cs=3.8 kPa，内摩擦角φs=31°。墙土系统整体有限元模型尺寸见图3，挡墙纵向长度方向取12 m，测点布置图见图4。
3.1研究方式
在有限元离散处理中，挡墙按图3测点布置图进行离散化，从左往右从下往上的单元编号用矩阵E表示，相应节点编号用矩阵N表示：
采用ANSYS对墙土系统无损状态下的整体模型进行瞬态分析得到测点加速度响应曲线，识别到系统频率和振型。为使问题简化，假定无损状态下基于模态参数的物理参数识别方法得到的土体附加参数是精确的，部分节点土体附加参数见表1。
假设墙后填土发生损伤时引起相邻节点处附加刚度损伤程度是已知的，计算出墙土系统模态参数，同时为了验证本文提出的墙土系统损伤识别方法的抗噪性能，按式（17）和（18）考虑随机噪声影响，然后将其作为式（10）的输入数据分析噪声对识别结果的影响。
由于对实际挡墙进行现场振动测量时受到多方面因素制约，不可能得到墙土系统所有的模态振型，〖JP3〗一般只能获得低阶的模态振型，因此，本文分析中仅采用前三阶模态振型φ1～φ3和前三阶模态频率ω1～ω3来识别墙后土体损伤位置和损伤程度。
对于土体附加刚度损伤程度识别准确性的评价用平均程度误差表示，即：
式中：N为待识别参数个数；βI，i为识别得到的附加刚度损伤程度值；βA，i为附加刚度实际损伤程度值；MMEE值越小意味着损伤识别结果越准确。
3.2损伤识别结果分析
分别对4种工况进行损伤识别，损伤识别结果分别见图5～8，图中x轴为挡墙高度方向，y轴为挡墙纵向长度方向。
由图5～8分析可知：在无噪声状态下，无论对单处损伤还是多处损伤、单一损伤程度还是多损伤程度，都能够精确的识别出土体损伤程度；对模态参数添加噪声后，本文方法识别的精度比无噪声状态下识别精度低，但仍然能够比较准确的识别出相应的损伤位置和损伤程度；根据不同工况的MMEE值，可以得到噪声对损伤识别有一定的影响，且随着损伤数量的增加MMEE值也增加，即损伤识别精度逐渐下降，因此，为了提高识别结果的精度，对现场测试数据处理时要注意消除噪声。
3.3算法性能的比较
为了便于比较改进多种群遗传算法和简单遗传算法计算性能的优越性，使IMGA和GA的初始种群保持一致，其他参数均相同。以工况2为例，同时不考虑测试噪声的影响。运行结果见图9。
由图9可知，改进多种群遗传算法收敛速度更快，在2 000代基本收敛到了近优解，迭代到5 000代时，MMEE值降低到了0.564%，得到了比较满意的结果；简单遗传算法在迭代到5 000代时，仍未收敛到较为理想的结果，因此，采用改进多种群遗传算法的寻优能力强于简单遗传算法。
4结论
本文基于墙土系统特征方程构造损伤识别的目标函数，结合改进的多种群遗传算法进行最优化计算来识别墙土系统的损伤，得到以下结论：
1） 文中改进的多种群遗传算法能有效的同时识别出墙土系统的损伤位置和损伤程度，弥补了现有的损伤识别方法中需要先识别出损伤位置，再进一步判定损伤程度的缺点。
2） 无论对单处损伤还是多处损伤、单一损伤程度还是多损伤程度，按本文识别方法都能较好的识别出墙土系统的损伤位置和损伤程度。
3） 为了验证本文识别方法的抗噪性能，对理论模态参数引入随机噪声的影响，采用改进的多种群遗传算法的损伤识别方法同样具有较好的识别效果，具有较强的抗噪声能力。
参考文献：
[1]Chou J H， Ghaboussi J. Genetic algorithm in structural damage detection [J]. Computers and Structures， 2001， 79： 1335-1353.
[2]Perera R， Torres R. Structural damage detection via modal data with genetic algorithms [J]. Journal of Structural Engineering， 2006， 132（9）： 1491-1501.
[3]Koh B H， Dyke S J. Structural health monitoring for flexible bridge structures using correlation and sensitivity of modal data [J]. Computers & Structures， 2007， 85： 117-130.
[4]He X， Kawatani M， Hayashikawa T， et al. A bridge damage detection approach using train-bridge interaction analysis and GA optimization [J]. Procedia Engineering， 2011， 14： 769-776.
[5]Meruane V， Heylen W. An hybrid real genetic algorithm to detect structural damage using modal properties [J]. Mechanical Systems and Signal Processing， 2011， 25： 1559-1573. [6]Nobahari M， Seyedpoor S M. Structural damage detection using an efficient correlation-based index and a modified genetic algorithm [J]. Mathematical and Computer Modeling， 2011， 53： 1798-1809.
[7]Liu H， Xin K G， Qi Q Q. Study of structural damage detection with multi-objective function genetic algorithms [J]. Procedia Engineering， 2011， 12： 80-86.
[8]袁颖，林皋，闫东明，等.基于残余力向量法和改进遗传算法的结构损伤识别研究[J].计算力学学报，2007，24（2）：224-230. Yuan Y， Lin G， Yan D M， et al. Study on structural damage identification based on residual force method and improved genetic algorithm [J]. Chinese Journal of Computational Mechanics， 2007， 24（2）： 224-230.
[9]袁颖，林皋，闫东明，等.基于改进遗传算法的桥梁结构损伤识别应用研究[J].应用力学学报，2007，24（2）：186-190. Yuan Y， Lin G， Yan D M， et al. Improved genetic algorithm for bridge damage detection [J]. Chinese Journal of Applied Mechanics， 2007， 24（2）： 186-190.
[10]尹涛，朱宏平，余岭.运用改进的遗传算法进行框架结构损伤检测[J].振动工程学报，2006，19（4）：525-531. Yin T， Zhu H P， Yu L. Application study of an improved genetic algorithm for frame structure damage detection [J]. Journal of Vibration Engineering， 2006， 19（4）： 525-531.
[11]陈存恩，李文雄.结合灵敏度修正的遗传算法的结构损伤诊断[J].地震工程与工程振动，2006，26（5）：172-176. Chen C E， Li W X. Structural damage diagnosis by genetic algorithm with sensitivity updating [J]. Earthquake Engineering and Engineering Vibration， 2006， 26（5）： 172-176.
[12]尹强，周丽.基于遗传优化最小二乘算法的结构损伤识别[J].振动与冲击，2010，29（8）：155-159.
Yin Q， Zhou L. Structural damage identification based on GA optim ized least square estimation [J]. Journal of Vibration and Shock， 2010， 29（8）： 155-159.
[13]李小平，郑世杰.基于遗传算法和拓扑优化的结构多孔洞损伤识别[J].振动与冲击，2011，30（7）：201-204.
Li X P， Zheng S J. Multi-hole damage detection in structures based on genetic algorithms and topology optimization [J].Journal of Vibration and Shock， 2011， 30（7）： 201-204.
[14]黄天立，楼梦麟，任伟新.基于CMDLAC指标和遗传算法的结构损伤定位研究[J].计算力学学报，2009，26（4）：529-534. Huang T L， Lou M L， Ren W X. Structural damage localization based on the CMDLAC and genetic algorithm [J]. Chinese Journal of Computational Mechanics， 2009， 26（4）： 529-534.
0 引 言
为减轻船舶驾驶人员在海上工作的负担和避免避碰过程中的操作失误，可利用现代化的科学手段和方法进行智能决策。大数据、互联网、人工智能等技术和理论的快速发展为船舶智能避碰决策的研究提供了强有力的技术和硬件支撑。船舶避碰路径规划是实现船舶智能避碰决策的关键技术之一，它经过大半个世纪的发展，从早期的经典数学理论逐渐过渡到基于人工智能和学科交叉的路径规划研究，取得了一定的研究成果。TAM等[1]将避碰路径规划的研究方法归纳为确定性算法和启发式算法：确定性算法是遵循一定的计算流程来确定最终方案的，主要包括专家系统[2-4]、模糊逻辑[5-8]、人工势场法[9-11]等;启发式算法是在一个搜索区域的子空间内寻找一个滿足设计要求的优化方案的，主要包括遗传算法[12-17]、蚁群算法[18-20]、粒子群优化算法[21-22]等。不同方法具有各自独特的优势，但都存在一定的缺陷。例如：专家系统的重点是建立避碰知识库和推理机制，可是存在知识获取困难，完备、简练的知识库难以形成，系统实时性较差，智能学习的能力不具备等问题[23];虽然模糊逻辑在船舶避碰领域的应用能在一定程度上实现对避碰这种非确定性问题的推理，但模糊推理的输出依赖于事先设定的参数，目前对模糊控制量的设定均使用经验参数，对环境因素考虑较少，环境自适应性有待提高[24];基于人工势场法对船舶进行避碰决策具有计算简洁、实时性强、便于数学描述等优点，但是存在局部极小值导致的陷阱区域、在碍航物前发生振荡、在邻近碍航物间不能发现路径等固有缺陷[25]。用确定性算法对船舶避碰路径进行规划的特点是计算量小、收敛速度快，但是往往基于其他变量确定的假设对某一变量进行确定，实际上船舶避碰路径规划是一个包含避碰规则、动态障碍避让、船舶操纵性能等多方面的决策优化问题。因此，很多专家学者转向基于启发式算法的船舶避碰路径规划研究，取得了一定的研究成果。然而启发式算法经常存在早熟收敛的问题，致使得到的决策方案不符合要求，因此采用不同的混合方式对各种技术进行优势互补以获得求解能力更强的路径规划模型成为一种新的趋势。
遗传算法具有对可行解编码的广泛性和易于与其他人工智能技术混合等特点，在船舶避碰路径规划领域受到广泛关注。本文基于遗传算法和非线性规划理论建立船舶避碰路径规划模型，解决遗传算法的早熟收敛问题，使混合后的算法在性能和效率方面都得到提高，为驾驶员的避碰决策提供科学依据和支撑。
1 会遇局面的定量划分
从运动路径可以看出，船舶的避让路径满足平滑度的要求。从两船距离变化曲线可以看出，船舶间距离满足船舶安全参数（船舶领域）的要求。在t2时刻，船舶的最近会遇距离（distance to closest point of approach， DCPA）接近船舶领域半径。船舶间距离变化曲线是一条光滑的曲线，表明船舶间的距离是均匀变化的，故避碰路径满足避碰过程中船舶安全性和路径长度的要求。因此，利用混合遗传算法可以得到有效的船舶避碰路径。
3.2 必要性分析
船舶避碰路徑规划是避碰决策中最关键的问题，需要综合考虑船舶安全性、路径平滑度和路径长度的影响。本文使用混合遗传算法不但提高了对避碰路径的搜索能力，而且极大地提高了避碰路径的质量。为证明混合遗传算法在避碰路径规划方面相对于标准遗传算法的优越性，分别利用两种算法对表3中的案例进行仿真，图7为这两种算法的适应度曲线。
由图7可知：混合遗传算法的适应度曲线在迭代25次后达到了相对稳定的状态，比标准遗传算法的适应度曲线达到相对稳定时的迭代次数大约少了10次;混合遗传算法的适应度曲线的斜率在迭代大约20次时有明显的跳跃，其最终的适应度值也明显更优。因此，在同等条件下，基于混合遗传算法的路径规划方法在收敛速度和求解结果上都优于基于标准遗传算法的路径规划方法。
4 结 论
本文首先对船舶会遇局面及避让责任进行判断，通过一维真值实数编码方式对避碰路径进行编码并根据转向避让方向和良好船艺对避碰路径进行初始化操作;再综合考虑船舶安全性、路径平滑度和路径长度对船舶避碰路径规划的影响，提出分类评价的方式，以此建立适应度函数模型;然后，基于遗传算法和非线性规划理论建立避碰路径规划模型，消除以往遗传算法在路径规划方面局部优化能力弱的缺陷;最后，通过船舶避碰仿真对混合遗传算法的有效性和必要性进行验证。
关键词： 遗传算法；网络分割算法；配电网优化；均衡负荷
中国分类号：TM344.1 文献标志码：A 文章编号：1671－7597（2012）0310089－02
0 引言
负荷均衡对于配电网意义重大，均衡用电，对于降低线损，节约电能具有重要的作用。同时也可以提高网络运行的可靠性。有关于配电网负荷均衡的问题。
1 配电网的拓扑模型及目标函数
由于配电网拓扑结构庞大，给全局优化带来困难，本文先将配电网分成若干子配电网，表示出这些子配电网之间的联接关系，然后再给出出每一个子配电网的分层模型，从而简化配电网的拓扑结构，而且降低负荷优化的复杂性。
1.1 分层拓扑模型
将子配电网的馈线当作图中的弧，把联络开关、分段开关、变电所母线当作图的顶点。分层拓扑模型是求某一基点对应的逐层顶点分布模型，该基点可以是源点、末梢点。本文取配电网的源点为基点，对源点分支进行逐层顶点分布。
定义配电网分层拓扑模型简化公式为：
（1）
其中 代表源点， 为与源点的间距， 分别表示各个顶点。公式表示与源点 的间距为 的所有节点处于以源点 为根的广义第 层。
对于图1所示的配电网的负荷分配图是一个具有3个广义层的配电网，以此类推就可以得到每一个子配电网的分层模型。分层拓扑模型表示出了各个子配电网的顶点分布次序，从而为下面计算各个子配电网的负荷和整个配电网的平均负荷做了铺垫。
1.2 算法的目标函数
配电网的负荷均衡指数和网损是判断配电网负荷的关键因素，所以本文给出目标函数如下：
式中： 表示负荷均衡指数和网络损耗目标函数的权重系数；
负荷的平衡可用负荷平衡指数（ ）表示为：
式中： -线路的条数目；
-线路上 的规范化的负荷；
-规范化的负荷 的平均值。
网损的计算公式 表示为：
式中： 为配电网支路数； 是第 支路的电阻； 为流过第 条支路的电流； 为开关的状态； 为0表示断开，1表示闭合。
此外目标函数的约束条件为：
1）网络必须保持辐射状结构；
2）除去开关外，网络的拓扑结构保持不变。
2 基于网络分割的遗传算法
由于配电网络比较庞大，难于进行全局优化，因此本节首先采用网络分割算法对配电网进行分割，然后将分割后的子网应用遗传算法进行负荷均衡化。针对遗传算法容易陷入局部最优，本文引入了自适应交叉和变异算子，以保证遗传算法的搜索效率，防止局部最优。
2.1 网络分割算法
源点负荷的计算对于一个配电网络来讲，应满足如下性质：父节点的负荷等于它的所有子节点的负荷之和再加上所有同父弧的负荷之和，即：
配电网的分割算法分割负荷时，必须分割与负荷的平均值最接近的点，即上界或下界的顶点。下界即为源点分支负荷中大于负荷平均值的最小值对应的负荷。上界则是源点分支负荷中小于负荷平均值的最大值对应的负荷。
配电网负荷均衡的网络分割算法的步骤：
1）首先利用分层拓扑模型求出各个节点分支的负荷，并计算出负荷平均值。如果线路区域的两个源点分支负荷都小于负荷的平均值，则分割负荷较大的一个节点分支。
2）其余的区域中至少都要有一个节点分支的负荷大于负荷平均值，那么此时可以求出负荷大于负荷平均值的节点分支下界及大于负荷平均值的节点分支上界，找出这些上、下界差距最大的两个节点分。
2.2 自适应遗传算法
本文将交叉和变异算子改进，这也是遗传算法区别于其他优化方法的主要标志。变异是避免“近亲繁殖”，实现多路径搜索，保持群体多样性，以避免局部收敛，恢复丢失的或者寻找尚未得到的优良信息的主要工具，它是通过较小的概率将密码串中的某位产生突变。传统遗传算法中交叉率 和变异率 取值是恒定的，在处理复杂的多变量优化问题时效率并不高，并且存在局部最优的可能性。为此采用自适应遗传算法，自适应
能够提供相对某个解的最佳 。该算法在保持群体多样性的同时，可保证遗传算法的收敛能力和优化能力。
在交叉方式上，把个体适应度大于群体平均适应度的个体对应于较低的交叉率，使该个体得以保护进入下一代；对于低于平均适应度的个体，相对于较高的交叉率，该个体则被淘汰。在自适应遗传算法中，交叉率按式（7）进行自适应调整：
式中： 为上一代群体交叉概率； 为下一代群体交叉概率；
为群体中的最大适应度的值； 为群体中的平均适应度的值； 为准备交叉的2个个体中较大的适应度的值。
类似于交叉操作，变异率 按式（8）进行自适应调整
式中： 为上一代群体变异概率； 为下一代群体变异概率。
3 算例分析
3.1 算法流程
本文基于配电网结构的特点，将遗传算法和网络分割算法综合应用来优化配电网络，具体的算法的流程如图2所示：
3.2 基于自适应遗传算法网络优化
下面利用遗传算法将分割后的网络进行优化，即对线路上的分段开关进行操作，以图3中北十变到北十九变线路为例，如图3所示，为分段开关，为联络开关。空心为合；实心为分。图中2座变电站，15个开关。利用监控中心采集到的负荷数据，通过遗传算法，求解最优分段开关操作方案，以实现负荷均衡。
遗传算法选取种群规模为50，基因长度单位为15位，染色体初始编码为111101110001000设定阈值为20，预设精度 为 ，权重系数
为0.5，优化结果见表1。
表1的计算结果表明，与优化前的网络相比网损相对优化前降低了43，负荷均衡指数BN也降到0.2以下，和优化前相比降低了0.1。
为和其他算法进行比较，同时采用模拟退火算法、免疫算法和传统遗传算法对本文算例进行计算，其结果如表2所示。免疫算法和模拟退火算法与本文算法相比较在操作次数上虽然少一次但负荷均衡指数相差较大分别为0.045和0.05，而传统的遗传算法负荷均衡指数与其他三种算法比较，差距较大、比本文算法高0.07。对比结果表明本文算法能够较好的实现配电网负荷均衡。
4 结论
本文以负荷均衡最优为配电网网络优化的目标，采用网络分割算法分割配电网络，用遗传算法优化分割后的网络，既平衡了负荷，又大大降低了网损，获得了较佳的效果。
参考文献：
[1]林景栋、曹长修、张帮礼，配电网负荷均衡的网络分割算法[J].继电器，2003，24（7）：5-10.
[2]刘扬、杨建军、魏立新等，基于混合遗传算法的配电网络重构优化[J].系统工程理论与实践，2004，11：122-127.
[3]徐赫、李欣、汪海、杨娜、洪镜雅，基于改进遗传算法的配电网网架规划[J].广东电力，2010，23（6）：6-9.
[4]陆铁坚、程柏，改进的模拟退火算法在网架结构优化中的应用[J].铁道科学与工程学报，2010，7（4）：1-4.
关键词：遗传算法；排课系统；Java
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）05-1032-04
排课是教学管理中十分重要、又相当复杂的管理工作，课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突并且要满足教师的要求和资源限制等约束条件。
为了利用计算机来解决这个实际问题，减轻工作人员的负担，自20世纪60年代起就有学者投入研究，研究者对于排课系统的解决方案大致分为以下几种：第一种是基于简单的经验法则解决教学规模不太大的问题[1]；第二类是建立排课模型，将排课问题归结为图的边染色问题[2]；第三种方式是先将固定时段的课程优先排入，然后依序填入其他课程[3，4]；第四种方法是采用模块化方式[5]；图形着色法[6]；搜索法[7]，总之这些方法适合处理小规模排课问题，当问题的约束条件增多时，问题变得相对复杂，求解过程会变得非常困难。
我国在排课方面的解决方案总结为两种：一是图着色模型[8]；而是数学模型[9，10]。
本文在讨论遗传算法的基础上，研究了遗传算法在排课系统中的应用和设计。
1 遗传算法
遗传算法最早于1968年由Holland教授提出，并建立了遗传算法原型，形成了遗传算法的理论基础。遗传算法是从生物进化论观点出发，用计算机模拟自然界演化的方式，对既定问题求最优解的方法，是基于自然选择和基因遗传、进化机制基础上的一种高度并行、自适应的优化算法[11]。遗传算法的操作步骤如图1所示。
图1 遗传算法流程图
2 排课系统的设计
2.1 总体设计
在充分调研教学排课管理业务后，经过分析，总结排课系统管理的信息和完成的功能有：
1） 基础信息管理
排课系统中所需要管理的基本信息有：教室信息、教师信息、课程信息、和班级信息；对这些信息管理的主要操作有、搜索、查看、添加、修改和删除。
2） 学期计划管理
学期计划管理模块主要依据学生的培养方案设置课程所在的学期、对应的专业（班级）、课程的名字以及课程所需的学时数；并为每一门课程指定相关的任何教师。
3）排课管理
排课管理有自动排课和手动课表调整两个方面的功能。自动排课是根据遗传算法的工作原理，对排课系统所管理的基本信息和学期计划进行杂交、编译操作后得到基本满足硬约束、软约束条件的课表；然后，在自动排课的基础上，将不满足条件的部分内容进行调整，最后生成教师课表、班级课表。
系统的总体功能模块图如图1所示。
图2 系统功能模块图
2.2 数据库设计
根据排课系统所涉及到的实体有：课程、教师、教室、班级、学期；这五个实体中教师和课程之间有授课关系；学期和课程之间有学期计划关系；班级与课程之间有班级课程关系；教室和课程之间有哪些课程在哪个教室上课的关系。关系E-R图如图3所示。
图3 排课系统中各实体及其关系E-R图
2.3 排课系统详细设计
1） 表示结构
在遗传算法排课系统中，一条染色体中应包含所有排课DNA分子，每个排课DNA分子又包含班级课程信息、老师信息、教室信息和时间信息，以及院系和学期信息。由于院系和学期在处理中是提前设定好的，在每次处理时都是一个给定的值，所以在染色体中可以不考虑他们。
2）初始种群
采用系统的随机数，生成初始种群。将排课任务表示为CyKwTx，在进行排课时，初始化种群中的个体就是用随机函数生成染色体中的RzMN的组合。
3） 约束条件
硬约束：
l每个指定时间段一个班级、一个教师、一个教室分别只能对应一门课程；
l要求教室的个数大于或等于指定时间段将要安排的课程数；
l安排教室时，要求教室容量必须大于或等于班级人数；
l教室类型与课程要求一致。
软约束：
l优先安排全校公共基础课；
l一周内课次多于2次以上的多课时课程，在时间安排上要求尽量隔天安排；
l较难课程应安排在上午第一节或下午第一节；
l体育课后尽量避免直接排课；
l同一门课程尽量安排在固定的教室。
4） 评价函数
评价函数是对种群中的每个染色体设定一个概率，使得高概率地选择某染色体，适应性值高的染色体被选择产生后代的机会更大。
评价函数的定义因各种问题而异，参数的个数也不一致。一般情况下，都是根据某种性的函数将各基因所获得的适应值进行统计，以求得整条染色体的适应值。
5）洗牌杂交
遗传算法中的杂交算法主要有：多点杂交、均匀杂交和洗牌杂交。本系统设计中使用的是洗牌杂交，即从每个父本中取它们一般的基因重组成新的个体。
6）变异操作
变异是随机改变一个染色体中某一基因的值，使得染色体出现新的基因特性，有时候将求解过程中趋于局限制时出现新的解决方法。变异的染色体个数根据变异率而定，如果变异率过高，将近似于随机数，难以达到最优解，如果变异率过小，将无法达到变异的效果。
基于遗传算法的排课流程图，如图4所示。
图4 基于遗传算法的排课流程图
3 实现与测试
自动排课系统按照学期进行，首先在学期课程计划中对教室、教室、课程、班级进行设置，在自动排课管理中选择“自动排课”，自动排课窗口如图5所示。
图5 自动排课窗口
自动排课功能并不一定能得到恰当的课表，这时可以手动对自动生成的课表进行调整。手工排课及课表调整窗口如图6所示。
4 结论
排课系统的求解的方法在实际中有许多解决方案。基于遗传算法的排课系统在实际效率上有很大的提高，这也是遗传算法在解决实际问题的一个简单应用。该文使用Java语言设计实现了基于遗传算法的排课系统，该系统实现了排课的自动化、智能化，使教务人员从繁杂的排课任务中解脱出来，而且对于推动教学的发展也起到非常重要的作用。
但是在非常复杂的应用中，使用遗传算法不一定能够得到最优解，即通过若干次迭代，算法不一定能收敛于某个最优解。这是可以提供不同的可行解供使用者进行选择，直到使用者得到一个解决方案为止。
参考文献：
[1] 周建新. 课表编排专家系统[J].计算机应用，2000，20（5）：76-78.
[2] Bondly J. A Graph Theory with Application[J].The Macnulan Press Ltd，1976：10-23.
[3] Selim S M. An Algorithms for Constructing a University Faculty Timetable[J].Compute Edue，1982（1）：323-332.
[4] Selim S M. An Algorithm for Producing Course and Lecture Timetable[J].Compute Edue，1983（2）：323-332.
[5] Dowsland W B，Lim puter Aided School Timetable – part2：the Micro-computer for School Timetabling[J].Compute Education，1982（1）：2-4.
[6] Dde Werra. Restricted Coloring Models for Timetabling[J]. Discrete Mathematics，1997（1）： 161-179.
[7] Hertz A.Finding a Feasible Course Schedule Using Tabu Search[J].Discrete Applied Mathematics，1992（3）：255-270.
[8] 胡顺仁，邓毅，王铮.基于高校排课系统中图论问题研究[J].计算机工程与应用，2002（4）：221-222.
[9] 孙建平，梅晓勇.关联规则在高校智能排课系统中的应用[J].计算机应用，2002，22（5）：37-38.
