遗传算法论文范文
时间：2023-04-08 21:49:39
导语：如何才能写好一篇遗传算法论文，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。
篇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
【关键词】自动导航小车；路径规划；免疫遗传算法；疫苗
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.
作者简介
篇3
关键词：遗传算法；肝脏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.
篇4
【关键词】多目标优化 进化算法 遗传算法 组合算法
中图分类号：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].
篇5
作者简介：陈 轩（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.
篇6
关键词全局最优；混合算法；遗传算法；Powell方法
1引言
不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。
近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。
本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。
2混合遗传算法
编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1)，式中为变量个数，、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：
min(1)
step1给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。
Step2随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。
fi’=a×fi’+b（fi³0）(2)
step3执行比例选择算子进行选择操作。
step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和，算术交叉产生的两个子代为和，是[0，1]上的随机数，1,。
step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异，，则变异结果为，其中，
(3)
(4)
返回区间[,]里的一个值，使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。是[,]之间的随机数，为最大代数，为决定非均匀度的系统参数。
step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作，则以作为初始点执行Powell方法得，若则把所得计算结果作为子代，否则，若取=；若取=，1。
step7计算个体适应值，并执行最优个体保存策略。
step8判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。
作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：
(1)变量赋初值，n个线性无关的n个方向,,…,，和允许误差ε>0，令k=1。
(2)令，从出发，依次沿方向,,…,作一维搜索，得到点,,…,求指标m，使得-=max{-}，令。若ε，则Powell方法计算结束，否则，执行(3)。
(3)求使得=min，令==，若，则Powell方法计算结束，得点；否则，执行(4)。
(4)若，令，否则令()，然后置，转(2)。
3算例
T[-500,500]
函数f(x)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。
采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。
Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数T=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。
采用本文混合法计算，取m=30，pc=0.85、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中PPowell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。
表1pPowell取不同值时混合法的计算结果
PPowell
0.0
0.02
0.05
0.1
0.2
0.3
求得最优解的次数
82
85
89
94
98
100
求得最优解的概率
0.82
0.85
0.89
0.94
0.98
1.00
平均计算时间/秒
0.14
0.20
0.31
0.47
0.68
0.87
4结束语
针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。
参考文献
[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．
[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．
[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44－48．
[4]戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．
[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．
[6]赵明旺．连续可微函数全局优化的混合遗传算法[J]．控制与决策，1997，12(5)：589－592．
[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．
[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．
篇7
关键字：频率分配 遗传算法 GECP 组合优化
1.
通信网频率分配问题的背景
无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1，S2，…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=min C（si）。因此FAP是一种组合优化问题。
具体设备频率分配方法虽然会随着设备的工作方式（单工、双工）、工作频段、天线类型、信号的调制解调方式的不同而有所区别，但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲，图的广义边着色问题是NPC问题[7]，也就是说无法在多项式时间内求得问题的最优解。例如对于存在n条边的无向图，使用c种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。
在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（Heufistic Algorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。
对于FAP问题国内外许多学者进行了深入的研究，提出许多解决问题的方法。文献[4]在对FAP进行理论分析的基础上给出了几种常用算法的框架，这些算法包括：最小-最后次序查找算法，贪心T着色算法、模拟退火算法（SA）、列表寻优算法（TS）、遗传算法（GA）、神经网络（NN）多面体算法等，并指出各种算法有各自的适用范围；文献[2]提出了利用启发式的蚂蚁算法，并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较；文献[1]比较了SA、TS、GA、VDS（variable –depth search）、BC等算法的性能。文献[7]利用GECP理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法；文献[9]则采用了BC方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决FAP问题。
2.
遗传算法在频率分配问题中的适用性
2．1 遗传算法的原理
遗传算法(Genetic Algorithms GA)是根据生物学上的染色体基因因子构成机制而产生的。1975年Holland教授首次提出了GA的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面。遗传算法是一种全局优化算法，其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决组合优化问题和复杂非线性问题[6]。
利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。
实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了模式定理。所谓模式，就是某些码位取相同值的编码的集合。模式定理说明在进化过程的各代码中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长[6]。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解[5]。
2．2 遗传算法的基本结构
在遗传算法中，将问题的求解的过程，看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索，一般采用遗传算子(或称遗传操作)诸如(Crossover)和变异(Mutation)等，以及模拟自然过程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。
遗传算法求解问题的基本步骤可以描述如下：
1. 首先生成一组初始的候选解群体(假设为N个候选解个体)，称为第0代；
2. 计算群体中各个候选解的适应值；
3. 如果有候选解满足算法终止条件， 算法终止，否则继续4；
4. 根据概率，将候选解群体中的个体随机两两配对，进行操作以生成新的候选解；
5. 根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；
6. 使用选择机制形成新一代候选解；转2。
GA算法具有下述特点： GA是对问题参数的编码组进行，而不是直接对参数本身；GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始；GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。
遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。
3.
遗传算法用于频率分配
3．1 算法的基本流程
采用遗传算法的FAP基本流程
3．2 遗传算子的选择
3．2．1 选择算子
选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在FAP中选择算子采用轮赌算法实现。
轮赌算法流程如下：
sum=0; i=0;
wheelpos=rand()*sumfitness;
for(sum
｛
i++;
if(i≥pop-size)
｛
sum=0; i=0
wheelpos=rand()*sumfitness;
｝
j=rand()*pop-size;
sum+=fitness［j］;
｝
return j;
3．2．2 交叉算子
交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。
其基本流程如下：
//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0
if(flip(pc))
crossover1(mother，father);
else if(flip(pc))
crossover2(mother，father);
else
copy(mother);
copy(father);
3．2．3 变异算子
变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。
其基本流程如下：
while(all frequentpoint)
{
if(flip(pm)) mutate(frequentpoint)；}
4.
工程上需要注意的问题
4．1 初始候选种群
由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的GECP得到以各个顶点为主顶点的可行解作为初始候选种群。
4．2 编码方案
编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。
4．3 适配值函数
适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：
fitness=1000 / Σ (pri×seperate(Freq))。
其中：
pri 是节点的加权值；
函数seperate(Freq)是节点中各条链路发频率同其它链路的收频率间隔的和；
参考文献
[1] Robert A.Murphey， Panos M. Pardalos etc， Frequency Assignment Problems， Handbook of combinatorial optimization， Kluwer Academic Publishers，1999
[2] Vittorio M.， Antonella C.， An ANTS Heuristic for the Frequency Assignment Problem， csr.unibo.it
[3] Joe Bater， Peter Jeavons， David Cohen， Are there optimal reuse distance constraints for FAPs with random Tx placement?， CSD-TR-98-01， CS Royal Holloway Uni. Of London，1998
[4] K.I Aardal， C.A.J. Hurkens， J.K. etc. Algorithms for Freequency Assignment Problems，CWI Quarterly，Vol9(1&2) ，1996
[5] 王凌： 《智能优化算法及其应用》清华大学出版社 2001
[6] 陈国良等：《遗传算法及其应用》人民邮电出版社 1996
[7] 孙俊柏：禁用频点、频段下野战通信网的频率分配 中国科学技术大学硕士学位论文 1998
篇8
[ 关键词 ] 异常客户 孤立点检测 k-medoids算法 遗传算法
国内大多数商业银行都已拥有自己的数据集中业务平台,数据集中以后,商业银行建立了庞大的数据仓库,实施了对经营信息、客户数据的有效存储,紧接着商业银行就迫切需要从这些海量的数据当中挖掘出高价值的信息资源,从而精确的把握商业竞争、客户动态等实时信息,以便实施具有针对性战略。面对数量庞大的银行客户,如何应对随之带来的风险,成为商业银行客户关系管理必须面对的一个问题。因此,本文将异常客户检测(Exceptional Client Distinguish,ECD)作为研究对象,利用数据挖掘的思想和方法,对异常客户的风险进行预警。
一、异常客户检测
客户关系管理即为吸引并保持有经济价值的客户,驱逐并消除缺乏经济价值的客户。识别异常客户,一方面可有效地驱逐和消除风险,另一方面可以避免将正常客户误判为异常客户,吸引并保持有经济价值潜力的客户。
目前,异常客户检测技术主要还是基于数据特征匹配的方法。目前存在两个缺点。首先,总结异常客户特征主要靠专家手工完成,耗费人力物力;其次,所需时间较长,错过最佳挽留时机,异常客户造成的危害就无法减少。
异常客户反映在数据上,就是异常数据。Hawkins给出了异常的本质性定义:异常是在数据集中与众不同的数据,使人怀疑这些数据并非随机偏差,而是产生于完全不同的机制;Knor和Ng给出了基于距离的异常定义:数据集S中的一个对象O,如果它满足下列性质:数据集S中至少有p*100%的对象与O的距离大于距离D,则对象O称为DB(p,D) - 异常 。
二、孤立点检测
发现异常数据,孤立点检测是个行之有效的方法。孤立点(outlier)是数据集中的小部分数据对象,这一小部分对
象和数据中的一般行为或数据模型有着明显的不同。孤立点挖掘分为两个子问题:在给定的数据集中定义什么数据可以认为是不一致的;找到一个有效的方法来挖掘孤立点。
孤立点在某种尺度下与其他点不同或不一致。孤立点可能是由于度量或执行错误导致的。许多数据挖掘算法试图使孤立点的影响最小化,或者排除它们。然而,一个人的噪声可能是另一个人的信号。这样的点通常包含了一些重要的隐藏信息。例如,在欺诈探测中,孤立点可能预示着欺诈行为。
目前孤立点挖掘算法主要有四种:统计学方法、基于距离、基于偏离和基于密度的方法。
基于统计的方法主要应用于科研计算,这主要是因为这种方法必须事先知道数据的分布特征,
从Knorr和Ng开始开始研究采用无需任何参数的方法,并提出使用数据点到其最近邻居的距离和的方法作为异常的量度标准。虽然距离是一种发现孤立点的有效的无参数方法,但需要耗费时间来计算距离。
A.Arning和P.Raghavan提出了基于偏离的孤立点探测的线性方法,但基于偏离的方法中的序列异常的概念并没有得到普遍的认同。这是因为序列异常在概念上仍然有一定的缺陷,遗漏了不少的异常数据。
基于密度的方法只关注对象周围临近的密度(最近邻居数)。关于它周围的邻居具有高密度邻居的数据点不是孤立点,具有低密度邻居的数据对象可能是孤立点。
上文中介绍了当前各种孤立点检测算法面临的种种缺陷,并对其进行了比较,发现基于距离的孤立点检测方法在许多方面都优于其他方法,在思路上也是正确的。基于距离的方法与基于统计的方法相比,不需要用户拥有任何领域知识。与“序列异常”相比,在概念上更加直观。
三、基于距离的k-medoids聚类算法与遗传算法
本文将基于距离的k-medoids聚类算法与遗传算法相结合,既可以很好地解决局部最优的问题,也可以很好地解决孤立点的问题,还可以加快遗传算法的收敛速度,节约时间成本。
k-medoids算法与k均值算法相似,但与k均值不同的是k-medoids算法不采用均值作为聚类中心,而是采用数据集中任意一个数据作为聚类中心,因此,可以很好地解决k均值对孤立点敏感的问题,极大地提高聚类的精度。但该方法同样受初始值影响很大,通常不能得到全局最优解。
遗传算法是一种建立在自然选择原理和自然遗传机制上的迭代式自适应概率性搜索方法,具有鲁棒性强、需要的领域知识少等优点,用于孤立点检测理论上是可行的。
本文提出的基于k-medoids算法和遗传算法结合的孤立点检测算法,继承了遗传算法的优点,在一定程度上克服了现有算法的弱点和不足。随机产生遗传算法的第一代并开始选择,然后在每代进化中,都用k-medoids算法对每个被选择的个体进行进一步的优化。也就是说,在每一代都要对所有被选中的个体计算以其为初始值的k-medoids算法的局部最优结果,并以这些局部最优结果替换掉原来的个体并继续进化,直到达到最大代数或者结果符合要求为止。
该算法的步骤将在以下部分详细介绍。
1.对个体进行编码和初始种群的生成
本文采用实数编码。染色体中实数的数量代表需要聚类的数量。初始种群采用随机函数生成,形成一个初始种群矩阵,其中每一行代表一个个体,每一行中的每个元素代表一个聚类中心。矩阵的行数代表种群中个体的数目,列数代表需要聚类的数目。
2.适应度函数的确定
本文采用均方差作为适应度函数,定义如下:
其中, E为所有数据对象与相应聚类中心的均方差之和,p为代表对象空间中的一个点,为聚类的中心对象,n为中点的个数。
3.选择算子的实现
遗传算法使用选择运算(或称复制运算)来实现对群体中的个体进行优胜劣汰操作。本文采用锦标赛选择法。
4.用k-medoids算法进行优化
用k-medoids算法对选择出来的个体进行优化,并用优化后的个体代替原来的个体。用k-medoids算法进行聚类一般只能得到局部最优解,但用其优化后的个体来代替原来的个体便可大大加速遗传算法的收敛速度,节约时间成本。
5.交叉算子的实现
交叉运算是产生新个体的主要方法。交叉率一般取值0.4 - 0.9。单点交叉中,交叉点的范围为[ 1, Nvar-1] ,Nvar为个体变量数目,以该交叉点为分界相互交换变量。
6.变异算子的实现
遗传算法中的变异运算是产生新个体的辅助方法,它是必不可少的一个运算步骤。变异率一般取值0. 001- 0. 1。
四、实验分析
本文的数据来自美国加州大学Irvine分校的机器学习库(the UCI Irvine Machine Learning Repository),选择德国信用数据集为研究对象,该数据集包含20个属性,本研究截取前100条数据,采用k均值算法、k-medoids算法和本文研究的新算法分别对数据集进行了聚类分析,实验结果见表1 (本结果只显示包含孤立点的类,其中的数字代表数据对象的序号)。
从表可以看出,在聚类时k均值算法无法把孤立点分离出来,而k-medoids算法和本文所研究的算法都可以把孤立点分离出来。从衡量聚类效果的重要指标均方差值的大小来看,在存在孤立点的时候, k-medoids算法比k均值算法要好,而新算法显然优于前面两个算法。
五、结论
本文比较了四种孤立点检测方法,通过分析发现基于距离的孤立点检测方法在许多方面都优于其他方法,在思路上也是正确的。基于距离的k-medoids算法可有效检测孤立点,但容易陷入局部最优。将k-medoids算法与遗传算法相结合,既可以很好地解决局部最优的问题,也可以很好地解决孤立点的问题,还可以加快遗传算法的收敛速度,节约时间成本。应用该算法可以有效地检测孤立点,即商业银行的异常客户,对风险进行有效地预警。
参考文献:
[1]Hawkins DM.Identification of Out1iers.Chapman and Hal1.London.1980
篇9
关键词：软件可靠性；神经网络；遗传算法
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)28-0181-03
Prediction of Software Reliability Based on Evolutionary Neural Network
ZHANG Gui-yong, SHEN Yuan-long, DING Xiao-guang, WANG Ling
(College of Optoelectronic Engineering,Nanjing University of Posts & Telecommunications,Nanjing 210003,China)
Abstract: It is more precise using neural network to predict software reliability than the model of NHPP. The structure of neural network designs by experienced experts. The author uses genetic algorithm to optimize the structure of neural network and solves this problem. The evolutionary neural network can effectively improve the ability of prediction in precision and accurate.
Key words: software reliability; neural network; genetic algorithm
1 软件可靠性
软件可靠性被定义为：“在一段时间内软件正常运行的概率”。软件可靠性模型对于软件可靠性的估测起着核心的作用。而对于软件质量保证有直接意义的模型，是那些它们的参数能够以软件故障发生的历史预测软件将来故障发生的行为，软件可靠性模型是这种思想的体现。
到目前为止，世界上大约已公开发表了一百多个软件可靠性模型，基本上被分为两类：参数型软件可靠性模型和数据驱动型软件可靠性增长模型。前者主要有Musa的执行时间模型、Goel-Okumoto模型、J-M模型、贝叶斯模型等等。这种模型的主要缺点是：预测的数据是在自己模型的假设前提下实现的，每个模型都有自己的假设前提，导致模型应用的局限性。后者主要指用神经网络去预测软件可靠性模型，这种模型没有前提、假设。输入的是历史错误数据，提高了预测的精度。Karunanithi.whitley&Malaiya在1992年的论文中已证明数据驱动型比参数型有着更好的预测精度。
2 BP神经网络
BP神经网络是采用BP算法的神经网络的统称。目前在人工神经网络实际应用中，绝大部分采用BP网络和它的变化形式，它是前向网络的核心部分。
2.1 BP网络的结构
BP神经网络有三层，分别为：输入层、隐藏层和输出层（见图1），其中隐藏层的层数理论上可以为任意值。
■
图1 BP网络模型结构 图2 三层BP网络模型
2.2 BP算法
BP神经网络参数传递有两个过程：一个为输出参数的顺传播，另一个为误差的逆传播。假设一个三层的BP神经网络（见图2）网络权值（Wij Tli）阈值为θ。则
1) 输出的顺传播
隐节点：■ 其中■
输出节点：■其中■
2) 误差的逆传播
误差：
■
输出节点权值修正值：
■
令δl=-(Tl-Ol)f'(netl) 则■
隐节点权值修正值：
■
令■ 则 ■
由于权值的修正正比于误差函数沿梯度下降，所以有：
Tli=ηδlY Wij=ηδi'Xj其中η为修正参数。
对阈值的修正过程同对权值的修正过程，推倒的结果为：
输出节点：θl(k+1)=θl(k)+ηδl
隐节点： θi(k+1)=θi(k)+η'δi'
2.3 传递函数
在BP神经网络中经常使用对数S形函数、正切函数和线性函数作为神经元的传递函数。
3 遗传算法
遗传算法(GA)是由美国科学家Holland提出来的，它的主要优点是简单、鲁棒性强、需要解决的问题越复杂，目标越不明确，优越性越大。它模拟自然界适者生存，优胜劣汰的进化原则，将问题的解表示成染色体(chromosome)，在计算机编程时，通常用二进制码串表示，每个码称为一个基因，每个染色体代表问题的一个解。一群染色体构成一个群体或种群，他是GA搜索的空间。在搜索过程中，用适应度函数(fitness function) 来评价每个染色体的优劣，其值越大（适应度越大），相应染色体代表的解越优。选择适应度大的染色体进行再生(reproduction)，通过交换(crossover) 、变异(mutation) 两种操作产生新的一代更适应环境的染色体群，这样一代一代地不断进化，最后收敛到一个最适应环境地个体上，求得问题的最优解。适应度函数的选择能有效的指导搜索空间沿着面向优化参数组合方向，逐步逼近最佳参数组合，而不会导致不收敛或陷入局部最优。
算法流程如下：
1) 编码所要解决的问题。
2) 随机生成N个个体，形成初始染色体群体。
3) 计算群体中每个个体的适应度值。
4) 计算群体的平均适应度，把每个染色体的适应度归一化。
5) 依据归一化后的染色体适应度值，赋给每个染色体一个生存概率，按这个概率选择n（n
6) 用新的染色体代替原来的2n个染色体，形成新的种群。
7) 若满足中止条件，则解码适应度最大的染色体得到问题的解，否则返回步骤2)继续进行。
4 用遗传算法去优化BP神经网络的结构
在用神经网络去预测软件可靠性的过程中，神经网络的结构往往是预先不能获得的。本文提出了用遗传算法优化神经网络结构的方法。论文假设神经网络有四个输入一个输出中间的隐层为待优化的部分。
4.1 个体的编码
我们用2进制编码方法对结构进行编码，每个隐层用4位二进制码来代表，则隐层的神经元的个数为0－15个，当个数为零时代表该层不存在，我们可以假设隐层有二层、三层或任意层，则个体的编码为8、12或更多个二进制码。
4.2 适应度函数
在遗传算法中使用适应度来度量群体中的个体在优化计算中能达到或接近于最优解的优良程度。本文采用的适应度函数为：
■
其中p为可靠性样本用于训练的数目，■i是神经网络的输出值，xi为样本值。
4.3 控制参数的选取
遗传算法中控制参数的选择非常关键，参数选取的不同对遗传算法的性能产生较大的影响。这些参数有群体规模N、交叉概率Pc、变异概率Pm等等。交叉概率太大使搜索走向随机化，交叉概率越小，搜索的速度就越慢，太小时则陷入停滞，一般Pc为0.4－0.99。变异概率越大，容易破坏好的模式，是遗传算法近似随机搜索，变异概率太小，对产生新个体和抑制早熟现象的能力就会较差，一般为0.001－0.1。群体规模的大小直接影响到遗传算法的收敛性或计算效率。规模过小容易收敛到局部最优解；规模过大，会造成计算速度降低。群体规模可以根据具体情况在10－200之间选择。
4.4 流程图(见图3)
4.5 泛化处理
在BP网络的训练中往往会出现这样的情况，当网络的训练误差很小的时候，一个新的输入会使网络的训练误差增大，这是因为网络记忆了已被训练的样本，而对新的输入没有良好的泛化能力。规则化调整方法是通过调整网络的性能函数，来增强网络的泛化能力。普通的BP神经网络都采用网络误差的均方根之和作为性能函数。如下式 ：
■
其中 ei ti ai分别表示第i个训练样本的训练误差、目标函数和网络输出。而调整后的网络函数如下：
msereg=γmse=(1-γ)msw
γ是性能参数 ■
使用该函数可以减少网络的有效权值和阈值，并且使网络的训练输出更加平滑，从而增强网络的泛化性能。
4.6 数据预处理
在我们开始试验之前，还得对原始数据进行如下处理：■，x为原始数据，=xmax-xmin。这样数据就被调整到0.1－0.9之间。在预测结束后用■将得到的数据调整到原始数据。
5 进化神经网络对软件可靠性预测实例
为了证明本文提出的方法优于直接用神经网络进行预测，这里我们找到了一组软件可靠性的数据，这组数据来源于一个中等项目软件测试过程（见表1）。
在进行仿真之前我们还得定义几个指标来代表预测的精度。
■其中■i为预测的数据，xi为实际的数据。
■其中■i为预测的数据，xi为实际的数据，n为待预测的数据量。
我们用前12组数据对神经网络进行训练，后四组作为待预测的数据，普通神经网络采用3－7－1的结构，优化的结果神经网络采用2－6－2－1的结构。预测结果的RE和AE比较（见表2）。
对数据的拟合度如图4所示 。
6 结论
篇10
关键词：排课；排课管理；遗传算法
中图分类号：G647 文献标志码：A 文章编号：1674-9324（2016）15-0011-02
一、国内外研究动态
（一）背景与意义
排课管理作为教育教学中的重要环节，其目的是为教师、学生安排合适的教学地点与时间。排课管理是教学管理中一项复杂的工作，只有合理安排好了课程时间与地点，才能保障教学工作的有序进行[1]。关于教学排课管理研究已经有近四十多年之久，在理论以及实际应用中都取得了丰硕的成果。然而，现有教学排课管理在面对复杂教学排课环境及大规模教学排课管理时存在的问题至今尚未完全解决，特别是随着各大高校学生的大力扩招，给教学排课管理带来了巨大的压力。在国内，目前教学排课管理采用系统自动排课与人工排课的方式[2]，系统首先进行自动排课，然后找出存在冲突的课程进行人工调整，并根据经验判断将课程安排到合理的位置。由于人工调整缺乏理论指导与数据模型，使教学排课管理具有一定的盲目性，因此需要利用计算机技术与合适的排课算法解决人工干预的问题，这对于推动教学的发展也起到了非常重要的作用[3]。排课管理通过将各个年级开设的课程汇总，然后根据学校全年教学计划任务和教学资源定制各个年级课程表，从而达到优化教学资源的目的，通过设计一个有效的智能排课系统，减轻教学管理工作者的劳动强度，提高教学工作效率，为规范教学管理工作流程提供技术支持，从而保障学校的正常教学秩序。排课管理是非常复杂而烦琐的管理过程，在学校规模大、约束（条件）复杂以及规律不断变化的环境下，目前许多排课软件与排课算法无法满足实际需求，为满足学校排课需求及师生对教学资源利用的要求，规避资源限制等约束条件，本研究对江苏信息学院排课管理进行了研究分析以满足学院实际排课需求。
（二）国内外研究现状和发展态势
排课问题是教育界非常关心的问题，对于排课问题研究主要集中在理论、启发式搜索技术应用求解、系统求解设计、遗传算法应用求解上。在国外，排课算法起源于20世纪50年代，1963年Gotlieb提出“排课算法数学模型”这一概念，标志着排课算法研究进入了科学的殿堂。自此以后，许多学者也参与到了排课算法研究中，早期的大多数求解都存在诸多问题，无法完全应用于实际生活中，如Ferland、吴金荣等人将排课问题化成整数规划来求解，但这种方法计算量巨大，只能应用到小数据量环境中，无法适用于实际应用中。而何永太和胡顺仁等人则采用图论中的染色问题进行排课研究，由于图论的染色问题本身也是NP完全问题，其计算比较复杂，也只能应用于特殊条件中，因此至今没有一个切实可行的算法。到了20世纪90年代，国外对于排课算法研究非常活跃，提出了一种新的课表编排方法，它以“人”为单位，利用格朗日松弛法及分支定界技术进行排课算法研究。而在我国，对于排课算法的研究却要始于20世纪80年代，从模拟手工排课到运用人工智能，逐步发展，取得了一定的成绩。随着人工智能的发展，开始在排课算法中引入了生物界进化思想和遗传算法，依靠其超强的并行搜索能力和在解决优化问题中表现出来的优势，已经被广泛使用。特别是生物进化思想和遗传思想的出现，出现了基于遗传算法来求解排课问题。本课题就是利用了基于遗传算法进行排课算法设计，并结合J2EE技术、Struts技术、MVC结构设计、SOA技术实现系统开发设计。
二、理论意义及实用价值
随着社会经济的发展，高校规模的扩大增加了教学管理的难度及造成了教学资源的相对紧张，但显然这些学校的师资、教学设备和其他教学资源都不能及时有效地进行补充，所以无法适应教学发展的需求，这其中排课问题就尤为突出。不仅在普通高校出现了以上问题，在高职院校也出现同样的问题。江苏信息职业技术学院经过六十多年的艰苦创业，现有全日制在籍学生共一万多人，学校形成了中高职衔接、职成教一体的办学体系。目前采用的是2004年引进学院的教务排课系统，经过十年的运营，技术已经落后，不能很好地满足日常教学工作的需要。本文也是基于这个原因，意在编写一套适用于江苏信息学院的自动排课系统。
三、目标、研究内容和研究方法
（一）工作目标与任务
结合江苏信息学院的现实，再造教务教学管理的管理流程，使它更加科学化、规范化。据此建立一套教学制管理制度，不但要适合江苏信息学院的现实，还要完成选课排课的信息化与自动化。最后设计一个排课系统，与现有运行的排课系统相比，该系统支持全学分制，这是它最明显的优点。它不仅能够减少各级教学管理人员的工作量，方便检索查询与管理，还能够形成先进的教学理念和管理制度。
（二）研究内容和研究方法
本文主要包括以下工作：重点分析、设计及研究排课管理系统。（1）对目前许多高校的教务管理流程进行重点分析，找出手工排课的主要问题和编制课表的基本原则，分析排课需求。组织学生评价教师及他们所授的课程，最优组合教师和课程，充分做好排课的相关准备工作；（2）从多方面分析系统需求，主要包括系统开发背景、可行性论证、主要业务流程分析、系统功能需求分析、数据模型分析等，确定江苏信息学院排课管理系统实现的必要性及可行性；（3）全面设计系统实现的各个功能模块，确定本排课系统的主要内容：其中包含系统管理、原始数据、教室管理、教学任务管理、排课管理、和课表管理等六大模块。同时，详细设计各个功能模块；（4）利用J2EE技术、Struts技术、MVC结构设计、SOA等技术进行具体的程序开发。同时，在后台数据库方面，选择SQL Server 2008作为管理系统；（5）关于算法研究方面，本排课系统完整讨论了排课问题的主要影响要素、约束条件、以及排课系统中遗传算法的设计及核心算法等问题。
四、关键技术问题
（一）创新之处
首先，对于排课问题的影响要素、主要约束条件、求解目标和难点，本系统进行了完整的讨论，提出了排课问题求解方法的总体框架和技术路线；其次，根据江苏信息学院的实际情况，从排课系统的需求分析开始，建立排课系统的数据模型及其体系结构。给出排课系统中遗传算法的设计，核心算法的实现方法和步骤；最后，说明本排课系统的总体设计方案、各模块的功能结构及相应的实现方法。
（二）拟解决的关键问题
影响排课的因素很多，总结起来分为以下两大类：一是参与教学活动的主体。主要是指教师、班级、课程，教学等主体对象因素，这些因素在每个学期都是可能变动的，是动态的。它们是需要给予分配资源的对象。而在排课过程中，这些主体对象必须在空间和时间上都保证独立，而不是冲突的。在排课过程中，最主要的问题就是解决这些主体对象因素在空间和时间上的冲突；二是教学资源对象因素。主要指被分配的资源，如教室、教学时间等因素，这些资源往往都是有限的。并且教学资源都是分种类的，如教室有大教室、小教室之分，类型有多媒体教室、普通教室、语音室、实验室之分。其他因素还包括教学计划的不同、教师个人的选择喜好等。
五、可行性论证
（一）目标可行性论证
通过校园网构建一个交流平台来连接教师、学生和教学管理部门，利用并结合J2EE技术、Struts技术、MVC结构设计、SOA技术实现B/S结构的数据信息管理目标。
（二）技术可行性论证
软件方面，本系统结合了物联网技术，采用目前最常用的J2EE技术与SQL相结合的模式进行开发，数据库服务器选用Microsoft的SQL Server 2008作为数据库，此数据库能够处理大量的数据，不仅能够保持数据的完整性，而且还能够提供多项高级管理功能。由此可见，系统的软件开发平台条件已经满足。在硬件方面，江苏信息学院计算机容量越来越大，可靠性越来越高，硬件平全能够满足系统开发和系统运行的需要。
（三）成本可行性论证
本系统只需花费少量的经费，广大教务管理人员就能从繁重的手工排课工作中解脱出来，他们可以把更多的精力投入到其他教学管理工作中，提高工作效率；同时也可以使广大师生通过校园网查询到相关的个人教学信息，此方式成本低，既方便又经济。
（四）社会可行性论证
目前，江苏信息学院校园网络已经覆盖了整个教学区和学生区，学院各个教学部门、行政部门和广大学生的上网需求都可以满足。尤其是本学院已经通过光纤接入的方式与Internet连接，能够很好地实现校内用户之间以及校内用户与校外用户之间的联系。
综上所述，面对江苏信息学院教务信息处理需求的日益增长，开发一个教务排课管理系统来应对这种需求，为学生和教学管理人员提供快捷方便的双向选择服务，提高排课管理工作的效率，是非常有必要的。
参考文献：
[1]刘真.基于URP的地方高校数字校园建设应用研究[D].山东大学硕士学位论文，2008.
