遗传算法论文范文
时间：2023-03-18 11:01:28
遗传算法论文范文第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结束语
该文在对TSP问题进行分析的基础上,通过对全局最优解和局部最优解中的边关系的分析发现,通过最小生成树的求解保存最有希望成为全局最优解的边,可以提高算法的效率,同时并不降低搜索的性能。在实验中发现,通过生成基因库快速提高种群质量,虽然可以快速收敛,但是TSP问题的求解质量并没有达到一个可以接受的程度,因此在群体演化阶段中又加入了2-Opt局部搜索算子和多重搜索策略,对不同类型的染色体以不同几率进行选择交叉操作。
遗传算法论文范文第2篇
假设所用的计算机传输介质两节点之间不多于一条直线的链接路，所用计算机网络就可以运用数学图G=（N,L）来进行描述。而且网络的节点不会出现任何的故障，网络链接介质的可靠和自身的长度没有关系，网络链接路与网络只有两种状态存在：正常工作和故障。而当所有的计算机网络用户都相互联通时，则可组成G图的一棵生成树，并且全部的结点都处于正常。那么无论在什么时刻，可能只有L种的子集（L）是正常状态，全部结点都是正常状态。因此，整个计算机网络的可靠度都可使用数学建模来进行运算。
2遗传算法在计算机网络可靠度优化计算中的应用研究
2.1遗传运算方法
在计算机网络中遗传运算主要是以变异和交叉这两种方式进行。交叉主要是通过在网络结点的范围（[1，N]）之间的随机数，以此作为基因交叉位置的设置且一次只可以操作一个结点。这样能够最大程度地确保网络的连通性，但也有可能出现错的连通结构，所以进行调整操作；变异则是先确定基因的变异和数目，然后再根据范围来选择新的基因段替换旧基因段生成后代。一般变异率都在0.001到0.01内，如是变异出现了错误的网络连通结构基因，就必须进行相应的调整。
2.2算法的调整与仿真实例
根据上面的遗传算法中的分析，可根据其假设，建立出一个计算机网络的通信系统，然后再运用遗传算法来进行仿真实验，假设次计算机有着6个网路信道系统的结点，通过对一个计算机算的网络信道可靠度优化计算的实验，而后经过多次的计算，构建起相应的数学模型。合理将遗传算法应用到计算机网络可靠度的优化实验中，使得其网络的稳定性与可靠性都得到有效地提升。而其中算法的调整是必须要先对每一个基因的表达式进行网络连通结构的判断。而后是观察gij，当gij=1时则进行原交叉变异操作，当gij=0时，则令gij=1，如果操作依然不能实现，就跳回到起始点进行重新判断，这样反复的进行循环。仿真实例。如下为网络可靠度优化实例，其分别是网络链路价值的成本和可靠度矩阵。这个时候的网络可靠度约束常数都是2，总结的点数是5，迭代的次数是100次。通过仿真求解得知，网络链路介质的总成本是40，确保网络可靠度的最大值是0.88。
遗传算法论文范文第3篇
1．1基因编码设计
编码就是将遗传算法中处理不了的空间参数转换成遗传空间的由基因组成的染色体或个体的过程．其中基因在一定意义上包含了它所代表的问题的解．基因的编码方式有很多，这也取决于要解决的问题本身．常见的编码方式有：二进制编码，基因用0或1表示，通常用于解决01背包问题，如基因A：00100011010（代表一个个体的染色体）；互换编码，主要用于解决排序问题，如调度问题和旅行商问题，用一串基因编码来表示遍历城市顺序，如234517986，表示在9个城市中先经过城市2，再经过城市3，依此类推；树形编码，用于遗传规划的演化编程或表示，其编码的方法就是树形结构中的一些函数，本文采用的是树形编码．
1．2交叉算子设计
交叉运算的含义是参照某种方式和交叉概率，将两组相互配对的个体互换部分基因，生成新个体的过程．交叉运算在遗传算法中起关键作用，是产生新个体的主要方法．交叉操作流程如图1所示．交叉操作首先判定要交叉的基因是否相同，如果相同进行子基因组的交叉，然后再判定交叉是否完成，没完成就继续，完成就退出；如果交叉的基因不相同，就要选择是否依据概率进行基因交换，选择交换就交换其所有的次级基因结构，然后再判定交叉是否完成，选择不交换就直接判定交叉是否完成．
1．3变异算子设计
变异操作从第i个子结构开始．依据变异概率进行第i个基因的变异，如果变异完成，就初始化其所有次级基因结构，如果变异没有完成，就进行子基因组的变异操作．重复操作上面的步骤，直至变异操作结束．
2遗传算法在机械产品设计中的应用
机械产品设计是在研究人机协同方案设计的工作机制上，建立产品的人机分析、人机约束模型和协同方案设计求解模型，确立人机协同系统的同步与异步交互、任务协同、数据共享、数据可视化、易用性等工作机制．
2．1基于遗传算法的数控车床设计
2．1．1数控车床总体设计任务分解
首先确定数控车床总体设计任务，然后根据多层次结构知识进化算法设计要求，将数控车床的总体设计任务分解。
2．1．2数控车床设计的基因编码表示
依据数控车床设计任务分解的结果，可以得出数控车床设计的基因编码图．数控车床设计任务按多层次结构划分为床身、滑台、刀架、尾台、冷却、控制器、电机．每个结构都包含多个选择方案．不同选择方案的有些结构含有子结构，并且这些子结构还可以进一步分解出多种选择方案．通过数控车床设计的基因编码，可看到数控车床设计任务每一层次的关系，包括各层次之间的约束关系．
2．2基于遗传算法的机械产品设计系统应用
本研究以数控车床整体方案设计为例，对系统进行了应用测试．首先在知识库中建立机械产品的基因编码库，然后通过开发的基于遗传算法的机械产品设计系统，从知识库中读取基因编码，再进行选择、交叉、变异操作，并通过指标评价函数的评价，生成最佳设计方案．
遗传算法论文范文第4篇
遗传算法就是一种以事物的自然属性和遗传属性为基础，通过计算机对生物进化规律进行模拟以寻优的一种算法，将寻优的范围与遗传空间相对应，把每一种可能的值通过二进制码进行编码，如同染色体一样，形成的字符串相当于基因，然后按预期的结果对每一组编码进行评价，选出最合适的一个值。算法一开始是提出一些问题的解，然后根据要求对这些解进行选择，重新拆解组合，去掉不合适的，留下最优值，由此形成的便是新值，如此往复，继承与改良，这便是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结语
随着GA算法的不断发展，由于其与其他技术易于融合，当然对于它的争议仍然是存在的，但就近年的研究，大量实例都证明了它是一种简单且实用性很强的算法，在工程领域中的应用也将更加广泛。
遗传算法论文范文第5篇
离心压缩机中的静止叶栅（包括叶片扩压器，回流器等）作为气流能量转换的主要元件，其中亦不可避免的存在有效能量的损失。以单机离心压缩机为例，目前我国设计和生产的机器，其整机效率的期望值为83左右，但研究表明叶轮的效率则可高达90以上。由此可见，静止件中的能量损失导致整级效率下降7之多。对压缩机来说，这是一个可观的能量损失比例。长期以来，人们在对离心压缩机中的主要部件－叶轮大量精力进行研究的同时，对其配套的静止叶栅的研究却极为有限。随着对节能型压缩机日益增高的性能需要，人们不得不把目光逐步投向>！设计出具有最小能量损失的高效离心压缩机静止叶栅，是摆在离心压缩机研究者人们面前的一个越来越紧迫的任务。
近年来得到快速发展的遗传算法，是一类模拟达尔文自然进化论的仿生随机优化方法。遗传算法着眼于从一组（种群）潜在解（个体）中寻找问题的最好解。通过在这一组当前潜在解之间进行一定的遗传操作，如选择，杂交和变异，便有望产生更好的解。这一过程反复进行，直至找到一个可以被接受的解。遗传算法较之其它搜索技术具有许多优越性。这些优越性包括：1）鲁棒性。遗传算法在计算上简单，搜索有效，且无须对搜索空间附加限制性假定。2）固有并行性。遗传算法通过一组解，而非单个解进行搜索，因此具有固有的并行性。3）全局性。遗传算法在搜索过程中使用随机操作，可以探测更广的搜索空间，因而最有希望获得全局最优解。
本学位论文将遗传算法引入离心压缩机静止叶栅的优化设计，首次对遗传算法在这一领域内应用进行了深入而系统的发展和研究。论文的工作及所获得的结果广泛而有明确工程应用价值。主要工作有：
1．基于叶栅优化问题的复杂性考虑，首次对现有标准遗传算法进行了改进，以更有效求解这些问题。提出了三个改进型遗传算法，即对偶适应性遗传算法，方向进化遗传算法和概率二值搜索遗传算法。在对偶适应性遗传算法中，提出了一个待优化目标函数的对偶函数，将该对偶函数巧妙的结合进标准遗传算法，从而使遗传算法可以自适应地进行变异运算，提高算法获得全局最优解的能力。在方向进化遗传算法中，提出一个新的遗传算子，方向进化算子。该算子以个体的祖父代和父代的进化趋势指导子代的个体变异，可以使新解以最大概率在最优区域产生。在概率二值搜索遗传算法中，提出对个体基因二值位在遗传进化中的表现进行统计记录，以此记录为指导产生若干新鲜解补入种群，以改良种群质量。三个新算法与标准遗传进行的数值实验和设计实例对比显示了新算法对遗传算法收敛性的改进是十分可观的（参见Fan,Xi,Wang,InverseProblemsinEngineering,20__）。
2．论文首次系统提出静止叶栅遗传算法设计理论和设计模型（参见Fan,JournalofPowerandEnergy,Proc.Itn.Mech.Engrs,1998）。在设计模型中，以改进型遗传算法为基础，探索了气动叶栅设计中遗传算子的选取及运算规律，提出了适合遗传算法操作的叶栅个体参数化技术和相应的基因编码方法。与此同时，在设计模型中，还尝试将遗传算法与人工神经网络进行结合，提出在遗传算法叶栅设计方法中加入一个前馈人工神经网络策略，用于完成对已知叶片形状的流动分析，从而减少算法中实际CFD分析程序计算个体适应值的时间，缩短遗传算法进化周期。另外，首次提出直接受用前馈人工神经网络在遗传算法的训练和演化下完成叶栅气动设计任务的方法。所提出的遗传算法设计模型均具有广泛的通用性，可以与任何层次的CFD流场分析程序结合。可以对气动叶栅进行任意命题下的自动设计，既可以对叶栅进行传统意义上的正命题设计和逆命题设计，也可以实现叶栅的混合命题设计。
3．传统的离心压缩机叶轮及其它气动元件均为单点设计，即按一个给定工况点设计。如此设计出的元件在设计工况点附近尚能较好工作，但当实际运行工况偏离设计工况时，元件的性能就会急剧恶化。论文将航空机翼中多点设计的思想首次引入离心压缩机叶栅的气动设计当中，欲通过以元件的两个或更多个希望的运行工况点作为给定设计点，设计出在各个设计点之间均能较好工作的折中（trade-off）最优化叶栅。论文首次提出气动叶栅多点设计问题的数学描述。对叶栅多点设计问题，提出三个有效获取问题Pareto解集的遗传算法方法求解策略，即全局适应值竞赛策略，双枝竞赛策略和Pareto占优竞赛策略。所提出的遗传算法多点设计方法得到扩压叶栅设计实例的实验验证（参见Fan,Xi,Wang,JournalofPowerandEnergy,Proc.Itn.Mech.Engrs,20__,Fan,Xi,Wang,ChineseJournalofMechanicalEngineering,20__）。
4．遗传算法在叶栅形状优化上的成功应用激励作者尝试用该方法进行叶栅流场的数值分析。论文研究和探讨了生物进行系统与守恒定律支配的非生物物理系统的相似性。基于这些相似性，提出了一个求解流场问题的初步的“遗传算法类”CFD方法。该方法以流场的解作为遗传进化个体，以候选解满足守流体守恒性（如质量守恒，能量守恒等）的误差作为其适应性的度量，通过遗传算法对流场进行求解。初步探讨了守恒性误差的求解方法所得结果令人鼓舞，它初步显示，遗传算法具有进行叶栅流场分析的巨大潜力。以此为起种类（参见Fan,Lu,Xu,EngineeringComputation,20__）。
关键词：遗传算法，优化，离心压缩机，叶栅，神经网络
StudyofEvolutionary-Computation-BasedMethodsAliedto
DesignofStationaryCircularCascadesinCentrifugalCompreors
ATRACT
Incentrifugalcompreors,stationarycascades,generallyincludingbladeddiffusersandreturningchael,arethekeypartsforgaseousenergytraformation.Itisinevitablethattheenergylooccursintheseparts.Forexample,theexpectedaerodynamicefficiencyofthesinglestagecompreorsthatarecurrentlyproducedinChinaisabout83.Butstudieshavedemotratedthattheimpellers’efficiencycanreachuptomorethan90.Thisimplie sthattheenergylointhestationarypartsreducesthemachines’totalefficiencymorethan7.Thisisacoiderableproportionoftheenergylotocompreors.However,foralongtimeperiod,researchershavemademostpartoftheireffortsonstudyinghowtoimprovethemostimportantparts,theimpellers,ofthecompreors,whilestudiestothestationarypartsareverylimited.Sincetherequirementsoftheimprovementontheperformancesoftheenergy-savingcompreorsarealwayscontinued,theresearchershavenochoicebuttoturntheirsighttothestationaryparts,expectingtofindnewenergy-savingpoibilitiessoastoincreasethetotalmachines’efficiencyfurther.Coequently,howtodesignthehighefficientstationarypartsthatcanhaveaminimumenergyloisanurgenttaskfacedbytheresearchersofcentrifugalcompreors.
Geneticalgorithms(GAs),rapidlydevelopedinrecentyears,areregardedasstochasticsearchtechniquesthatmimicnaturalselectionandDarwin’smainprinciple:survivalofthefittest.GAsaimtofinethebestsolutiotoaproblembygeneratingacollection(“population”)ofpotentialsolutio(“individual”).Bettersolutioarehopefullygeneratedthroughcertaingeneticoperatiosuchasselection,crooverandmutationfromthecurrentsetofpotentialsolutio.Theproceisrepeateduntilanacceptablesolutionisfound.GAsHavemanyadvantagesoverothersearchtechniques.Theseinclude:1)Robustne,GAsarecomputationallysimpleandpowerfulinthesearchforimprovementandhavenolimitationonthesearchace.2)Intriicparallelism,GAscarryoutsearchthroughpopulatioofpoints,notsinglepoint,whichmakesthemintriicallyparallel.3)Globalproperty,GAsuserandomoperationintheirevolutionproceesthatallowawiderexplorationofthesearchace,andhenceitislikelythattheexpectedGAsolutionmaybyglobaloptimum.
Thisdiertationaimsatintroductionofgeneticalgorithmsintothedesignofthestationary
cascadesofcentrifugalcompreors.Somegooddevelopmentsandsystematicstudiesarefirstcarriedoutinalicationofgeneticalgorithmstothisarea.Theresearchesandtherelatingresultsobtainedinthediertationarebroadandpracticalinengineeringaellatio.Themajorworksinclude:
1.Basedonthecoiderationofcomplexitiesfromtheoptimizationproblemsoftheaerodynamiccascades,theexitingstandardgeneticalgorithmisimprovedinordertouseittosolvethecascadeoptimizationproblemsmoreefficiently.Threemodifiedgeneticalgorithms,namely,dualfitnegeneticalgorithm,directionevolutionarygeneticalgorithmandprobabilitybinarysearchgeneticalgorithm,areproposed.Inthedualfitnegeneticalgorithm,adualfunctionoftheobjectivefunctionoptimizedispresented.Thedualfunctionisthenembeddedintothestandardgeneticinordertomakethemutationoperationbeingperformedadaptivelywithdifferentprobabilitiesandsoastomakethealgorithmhavinghighergloballysearchingability.Inthedirectionevolutionarygeneticalgorithm,anewgeneticoperator,directionevolutionaryoperator,isproposed,thisoperatordirectsmutationoperatioofachildindividualaccordingtotheevolutiontendencyofitsgrandparentandparentindividuals.Withthemutationoperation,theindividualcanbeyieldedinanoptimumregionwithahighprobability.Intheprobabilitybinarysearchgeneticalgorithm,thebehaviourofthebinarycomponentsateachallelelocatioofachromosomearestatisticallyrecordedandareusedtoproduceasetoffreshsolutiothatareaddedintoapopulation,sothattoimprovethequalityofthepopulation.Thenumericalsimulationandpracticaldesignexamplesshowthatthethreenovelgeneticalgorithmshavemuchbetterconvergenceabilitiesthanthestandardgeneticalgorithm(seeFan,Xi,Wang,InverseProblemsinEngineering,20__,).
2.Thegenetic-algorithm-baseddesignprinciplesandmodelsarefirstsystematicallyestablished(seeFan,JournalofPowerandEnergy,Proc.Itn.Mech.Engrs,1998).Inthegenetic-baseddesignmodels,basedontheimprovedgeneticalgorithms,thetuningandoperationpatt erofthegeneticoperatorsinadesignoftheaerodynamiccascadesareexplored.Someparameterizatioandtheircorreondingcodingmethodsforaerodynamiccascadesregardingtotheoperatioofgeneticalgorithmsarepresented.Inthemeanwhile,intheproposeddesignmodels,incorporatinggeneticalgorithmsandartificialneuralnetworksisattemptedtosolvecascadedesignproblems.Inthiscase,agenetic-algorithm-baseddesignmethodisembeddedwithafeedforwardartificialneuralnetworkthatisusedtocomputetheflowcharactersofgivebladeprofiles.Astheresult,thefitnecomputationaltimecanbereduced,andfurtherthealgorithm’sevolvingepochcanbeshortened.Moreover,thefeedforwardartificialneuralnetworksarefirstuseddirectlytocompleteacascadeaerodynamicdesigntask,withthegeneticalgorithmsbeingusedtotrainandevolvethenetwork.Allthegenetic-baseddesignmodelsestablishedpoewidegeneralities.TheycanincorporatewithanydegreeCFDsolvers.Theycanimplementautomaticdesigofanaerodynamiccascadeinanyrequireddesig,i.e.,aconventionaldirectdesignorinversedesign,andahybriddesign.
3.Conventionally,theimpellersandtheotheraerodynamicpartsofcentrifugalcompreorsareinsinglepointdesign,i.e.,aredesignedaccordingtoagivenoperationpoint.Theelementssodesignedcanratherwellworkundertheoperationconditionearthedesignpoint.Butwhiletheoperatingconditioarefaroffthedesignpointtheymayworkbadly.Thediertationfirstintroducestheideasof“multi-pointdesig”formaeronauticalairfoildesignintotheaerodynamicdesigofthecascadesofcentrifugalcompreors.Inotherwords,throughtakingtwoormoreoperatingpointsasthedesignpoints,itisexpectedthatanoptimalcascadedesigncanbeobtainedthatmakesagood“tradeoff”betweenthedesignpoints.Themathematicalformulatioofthemultipointdesignproblemforanaerodynamiccascadearefirststated.ThreeParetogeneticalgorithmstrategies,i.e.,globalfitnetournament,two-branchtournament,andParetodominatetournament,arethenproposedforeffectivelyobtaintheParetosetofthemultipointdesignproblemsofcascades.Thegenetic-algorithm-basedmultipointdesignmethoDSProposedaresuccefullyexaminedwithanexperimentofapracticaldiffusercascadedesign(seeFan,Xi,Wang,JournalofPowerandEnergy,Proc.Itn.Mech.Engrs,20__,Fan,Xi,Wang,ChineseJournalofMechanicalEngineering,20__).
遗传算法论文范文第6篇
【关键词】自动导航小车；路径规划；免疫遗传算法；疫苗
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.
作者简介
井治财（1968），男，诺伯特智能装备（汉中）有限公司，陕西省汉中市，邮编：723000。主要从事机床结构设计与误差检测。
遗传算法论文范文第7篇
关键词:量子遗传算法;多目标分配;最优化
中图分类号: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
[4]郭张龙,李为民,王刚.基于遗传算法的目标分配问题的研究[J].现代防御技术,2002,6:0172-0180
遗传算法论文范文第8篇
关键词：复杂建筑结构优化 协同理论 遗传算法
复杂建筑结构设计问题一般都是先将其分解为易于求解的子问题，且多学科的交叉存在于子问题中。不同学科的专家小组会参加复杂建筑结构的设计，他们之间还互不知晓，这就形成了优化过程中的四个特征：复合多目标，学科交叉，巨大数量的设计约束，大的设计变量空间。相对于复杂建筑耦合系统优化来说，协同优化方法是比较新的方法。作为一种新的优化方法，许多不足之处仍然存在。优化效率及效果是这一方法的关键课题。
1、建筑协同设计
1.1建筑协同设计的特点
建筑设计是一门集经济性、艺术性和实用性于一体的综合性的学科。建筑功能、造型、空间及工程预算等诸多问题在建筑设计中都要考虑，涉及多工种。多学科的协调和交叉。目前越来越激烈的市场竞争氛围，使得复杂建筑结构协同设计理论在学术界和设计单位受到越来越多的关注。建筑协同设计是一种新兴的网络环境下的建筑设计方式，设计人员及管理人员都能在不同地点同步的参与设计工作，提高了设计的效率和质量。建筑设计需要多学科合作及反复协作与修改，以满足客户需要的最优设计方案。一般工程设计的各种特性建筑设计中都有，但是复杂建筑结构要求高，总体设计难度非常大，从而建筑协同设计有以下几个明显的特点：综合与协调，反复迭代，创造性和科学性。
1.2建筑协同设计的冲突
在建筑协同设计过程中，各领域参数的确定是协同小组共同完成的，其中就有在一个领域内协同小组在一些数据指标上的分歧以及协同小组在不同领域对相关参数的范围的确定，从而发生协同设计的冲突。因此，可以分类管理存在建筑设计中的冲突，这样就可以从各个角度分析和处理建筑协同设计中存在的冲突。建筑设计冲突主要是设计目标冲突和设计结果冲突两种，根据建筑设计的特点，设计冲突在建筑协同设计中又分为以下几个方面：总体冲突，装配冲突，各领域之间冲突，经济性冲突。
2、协同遗传算法在建筑结构优化设计中的应用
2.1遗传算法简介
尽管传统结构优化方法中的解析法和直接法已经在实际工程中广泛应用，但对于如极点问题、非连续设计变量问题、目标函数的强非线性问题等特殊问题处理难度仍然很大。特别是功能函数的偏导数在许多传统算法中需要被计算，而这就要求工程函数的连续性特别良好，这就给计算带来了极大的麻烦。遗传算法作为一种新的算法，与以往方法截然不同，显示了强大的生命力，是复杂建筑结构优化设计的一个新思路。最初遗传算法是用来指导模拟人工自然系统和解释自然界的适应性的，后来这种方法对于复杂建筑结构优化设计的有效性在许多报告和论文中都论证了。但此法也存在许多问题，例如不利于工程应用、收敛速度慢等。目前研究的重点就是在总结以往方法的基础上提出加快收敛的改进方法。
对于单个计算点的优化追踪过程，遗传算法放弃了这个传统的优化方法，而是多个计算点同时控，一个生物群体被看成了操作的对象。遗传算法是改变线列集团的质量，通过遗传操作算子，有三种最基本的操作：交叉，再生产和突然变异。
2.2遗传算法的优化过程
遗传算法为求解复杂建筑结构优化问题提供了一种通用框架，它不仅仅只依赖于问题的种类和领域。对一个实际应用问题进行优化计算，遗传算法构造求解该问题一般可按下述步骤来进行。
第一步：确定各种约束条件及决策变量，即确定问题的解空间和个体的表现型X。
第二步：建立优化模型，确定是求目标函数的最小值或是求目标函数的最大值，即确定目标函数的类型及其量化方法或数学形式。
第三步：确定表示染色体编码的可行解方法，即确定出遗传算法的搜索空间及确定出个体的基因型X。
第四步：确定编码方法，即个体基因型X到个体表现型X的转换方法或对应关系的确定。
第五步：确定量化评价个体适应度的方法，即目标函数f（x）到个体适应度fit（x）的转换规则的确定。
第六步：设计遗传算子，即确定变异运算、选择运算、交叉运算等遗产算子的操作具体方法。
第七步：确定有关遗传算法的运行参数，即遗传算法的pc、pm等参数的确定。
研究遗传算法的优化过程一直被实际工程问题直接的推动，高效实用的遗传算法优化的研究和探讨具有广泛而深远的意义。
2.3遗传算法提高精度、加快收敛的策略
通常按照上述计算步骤进行遗传算法复杂建筑结构优化的收敛速度比较慢，跳跃的现象经常在计算过程中出现。为了更好的解决上述问题，下面介绍了三种修正方法。
第一种是引入突变算子，减小局部出现最优解的可能性。做法是按一个较小的概率取反池中经过交换算子操作过的个体的二进制串的每一个。如果更优个体产生，则使之保留，反之淘汰。一般突变概率很小，不宜超过0.005，根据实际情况来定。
第二种是可以保护最优的几个个体，使它们直接进入下一代而不受任何影响，直至更优的个体的出现；或者强制令最优的几个个体进行，其它个体进行正常过程的。这样局部退化现象就会有效的减少，收敛进程加快。
第三种是每个个体自己的代表值依据自己所处的环境来改变。具体做法是下一代所有个体代表值的平均值是目前最有个体的代表值，修正了每一个个体的代表值。
结语
遗传算法作为一种全新的复杂建筑结构优化设计的方法，如目标函数的强非线性问题、设计变量的非连续性问题、对多峰函数求解最优化的问题等传统优化方法存在的多种弊端都被它克服了，同时，遗传算法的结构优化方法及过程都比较简单，而且计算机的编程计算特别适用于传算法。并且三种遗传算法改进策略的联合使用明显使优化计算收敛速度加快，减少计算时间的同时，结果的准确性也很高。可以说对于处理复杂建筑结构优化问题，遗传算法及准确又可靠，非常值得深入研究。
参考文献：
[1]陶全心，李著景.结构优化设计方法.北京：清华大学出版社，1985.
[2]王科，王明强.基于协同设计的冲突检测与消解研究[J].华中科技大学学报（自然科学），2007，21（3）：32-35.
遗传算法论文范文第9篇
关键词：自动排课；遗传算法；求解与优化
中图分类号：TP301 文献标识码：A
排课问题在学校教学管理中十分重要，它是一个有约束的、多目标的组合优化问题，并且已经被证明为是一个NP完全问题。由于涉及信息较多且求解比较复杂资源的最优化配置不容易实现，因此使用计算机对排课信息进行管理，能够极大地提高学校教务管理的效率，也是各种体制学校管理科学化、现代化的重要条件。现在大多数的排课系统是以编程语言为实现语言，采用各种算法为实现手段，比如遗传算法、回溯算法、模拟退火算法等。作为对排课问题的探索，本文采用遗传算法的思想，提出一个课表方案的随机生成和优化算法，以期能够较大程度地反映实际排课情况和尽量达到多个目标最优。
1 排课问题分析
1.1 排课问题的因素
从手工排课的过程看出，排课问题需要考虑的条件很多，如周课时设置、课程信息、班级信息、教师信息、教室信息等等。从排课过程可能引起潜在冲突的角度，可以将排课问题涉及的因素考虑如下：
时间：在排课问题中涉及关于时间的概念有学年、学期、周、天、节。
课程：每个课程都有自己的编号、名称。每个课程都有指定的教师、教室等。某些课程由于上课班级较多难以协调或照顾教师要求等诸如此类原因，应该预先给定时间或教室。
教室：每个教室都有编号、门牌号和名称。每个教室在同一时间内只能接纳一门课程的授课，并且教室容量应该大于等于上课的人数。
班级：每个班级都有编号和名称。每个班级同一时间只能上一门课程。
教师：每个教师都有编号和姓名。每个教师同一时间只能上一门课程。
1.2 排课过程的约束条件
排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，以使教学正常进行。避免排课因素发生冲突是排课问题中要解决的核心问题。只有在满足全部约束条件和避免冲突的基础上，才能保证整个教学计划合理正常进行。而对教师、教室、学生及时间等资源进行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。
排课过程中常见的约束条件如表1所示：
1.3 排课问题的目标实现
排课问题是一个多目标的组合规划问题，要想制定出一个“合理、实用、有特色”的课表，必须保证所有的约束条件都不发生冲突。一套高质量的课表，在时间、教室资源、课程安排等很多方面都应该做到科学的安排，并且应该具有人性化的考虑。课表编排问题的难点在于：保证课表在时间及人员的分配上符合一切共性和个性要求，在此基础上，所有的课程都能够安排合适的时间和教室，使安排方案在各个目标上尽量达到全局最优。
遗传算法是1975年美国MIChiga大学的John.H.Holland教授及其学生们根据生物进化的模型提出的一种优化算法。作为一种随机的优化与搜索方法，遗传算法有两个主要特性：1智能性。即遗传算法在确定了编码方案、适应值函数及遗传算子以后，算法将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存概率，它是具有“潜在学习能力”的自适应搜索技术。2并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得遗传算法能以较少的计算获得较大的收益。正是由于遗传算法的这两个特性，使得遗传算法迅速被运用于求解组合优化的排课问题，且操作简单，可以更少地依赖于实际问题的情况，实现课表的优化。
2 遗传算法在课表编排中的应用
2.1 遗传算法的基本原理
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。一般的遗传算法都包含三个基本操作：复制、交叉、变异。
2.1.1 复制，是从一个旧种群中选择生命力强的个体字符串产生新种群的过程。复制操作过程中，目标函数是该字符串被复制或被淘汰的决定因素。遗传算法的每一代都是从复制开始的。
2.1.2 交叉，在由等待配对的字符串构成的匹配池中，将新复制产生字符串个体随机两两配对，然后随机地选择交叉点，对匹配的字符串进行交叉繁殖，产生一对新的字符串。
遗传算法的有效性主要来自复制和交叉操作，尤其是交叉在遗传算法中起着核心的作用。
2.1.3 变异，遗传算法中，变异就是某个字符串某一位的值偶然的随机的改变，即在某些特定位置上简单地把1变成0，或反之。变异操作可以起到恢复字符串字符位多样性的作用，并能适当地提高遗传算法的搜索效率。
2.2 遗传算法在课表编排中的设计
使用遗传算法编排课表，我们把课程和老师当作同一变量考虑，这样编排课表只需将教师编码排入周课表，在以后打印课表时，将教师编码改为课程名即可。于是我们设计以下步骤：对每一门任课教师进行编码；使用二维数组来构成初始群体；冲突的检验和消除；定义课表的适应度函数(x)(x∈{1,2,…,N}),其中x表示个体在群体中的位置。当函数值为0时，即找到了本次优化过程的最优值；复制操作：按照适配值计算选择率和期望的复制数；交叉操作：将种群中的个体配对产生的交叉点再分别交换；变异操作：将随机产生的同列的两个位置互换；再次进行冲突检测和消除，直至无冲突存在。
2.3 算法的实现
遗传算法结束后，可以得到综合效率函数值最好的个体。根据这个结果，即可生成相应的课程表。系统的流程分为以下几个主要的过程：（1）初始种群的产生：形成本学期教学信息二维表，对教师编码；产生染色体。（2）对各类冲突进行检测，如存在冲突则消除它。（3）计算适应度函数值、期望值及其复制数。（4）进行遗传操作。（5）可行课程表的产生。
这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。
结论
本文采用遗传算法来对课表编排问题进行求解，是求解这种难解的组合优化问题方法中较明智的选择，目的是在遗传算法基础上提出一个课表方案的随机生成和优化方案，能够较大程度地实现课表编排和多个目标的最优化。本文算法对我们这类院系较多、教师工作量大、学科变化较大、不确定性较多的学校能有所借鉴。
参考文献
[1]安勐.遗传算法在排课问题求解中的应用[J].铜仁学院学报，2009，11（2）：135-139.
[2]陈春明.遗传算法在自动排课系统中的应用研究(硕士学位论文)[D].苏州:苏州大学,2009.
遗传算法论文范文第10篇
【关键词】免疫遗传算法 粗糙集 属性约简
1 前言
对于一个粗糙集决策属性表，人们总是期望能找出所有约简或最小约简，然而一个信息表的属性约简并不是唯一的，得到信息表的包含最少条件属性的约简已被证明是NP 完全问题。由于免疫遗传算法在NP问题领域取得了比较好的效果，论文提出了一种基于免疫遗传算法的粗糙集属性约简算法，实验结果证明该算法是有效的，可快速收敛到全局最优解。
2 属性约简的免疫遗传算法设计
2.1 染色体编码
采用传统的二进制编码，即若决策表中有N个待约简的条件属性，算法产生一个长度为N的0-1二进制串，每一位代表一种对条件属性的取舍，1表示采用该位上的条件属性，0则表示不采用。
2.2 初始种群的产生
初始种群设置的好坏直接影响到最后的求解效果。任何一个信息表或决策表的相对核都包含在所有相对约简当中，即具有唯一性。因此考虑在产生初始种群的时候使每个染色体都含有相对属性核。
2.3 适应度函数的构造
适应度函数用来评价染色体的优劣，在对每一个染色体进行适应度评价前，先要对每个染色体进行一定的调整。调整是基于属性重要度相关的某种启发式信息，给出染色体的调整步骤：
（1）计算决策表S中条件属性集C关于决策属性集D的重要度γc（D）；
（2）设C'为当前染色体采用的条件属性集，计算条件属性集C'关于决策属性集D的重要度γc'（D）；
（3）比较γc（D）和γc'（D）的大小，若γc'（D）
（4）对任意属性ai（∈C-C'）（1=1，2，…，|C-C'|），计算每一个μD（ai），令j={j|μD（aj）=max（μD （ai））}，然后将染色体上第j位上的0置为1，并且C'=C'∪{aj}，转到步骤②；
（5）调整过程结束。当染色体经过如上调整以后，就可以应用适应度函数对该染色体进行评价，适应度函数的计算公式为：
F=|C|-|C'| （5.16）
则染色体中采用的条件属性个数越少，该染色体的适应度函数值就越高，个体就越优良。
2.4 抗体产生的促进和抑制
要使适应度高的抗体进行促进，浓度高的抗体进行抑制。
抗体相似性通过抗体编码的Manhattan距离来度量。抗体X={a1，a2，…an}与抗体Y={b1，b2，…bn}之间的相似度为：
d值越大，表示两者的相似程度越低，如果d=0，则表示两个抗体完全相同。故抗体X的浓度定义为：
其中，函数D（X）表示抗体X相似度小于λ的抗体数目，λ为一给定的阈值
2.5 基于收缩精度的逐级进化策略
可以用收缩精度作为算法的停止准则，即当收缩精度小于某个比较小的正数K时算法停止进化。假设优化目标为求目标函数F的最大值，在不同的进化时期适应度函数J采用不同的形式如下：
式中α、β、k1 和k1为正数，根据优化目标的需要取不同的值。其中α 和β是为了在算法的中后期拉大群体内个体之间的差距，α
3 实例分析
在某次战斗任务中，我方使用各种常规武器对敌方6处战场目标实施打击。参与毁伤效果评估计算的我方武器“投入”和“产出”数据离散化得出一个毁伤评估决策信息表。应用改进的遗传算法进行属性约简。图1所示为免疫遗传算法求解最优约简属性向量的迭代过程。改进后的基于收缩精度的遗传算法在进化15代以后即停止搜索，得出了近似最优解。
由图1可以看出在算法的进化过程中，迭代曲线每隔几代都会变化一次。并且在算法的中后期，曲线依然出现明显变化。一方面说明算法自始自终都实现了对解空间的有效搜索，另一方面与传统算法相比，没有出现过早收敛的现象。说明改进后免疫遗传算法的科学性和有效性。
参考文献
[1]曾子林，张宏军，张睿，邢英.变精度粗糙集的逻辑解释及其约简[J].计算机应用研究，2013（05）.
[2]肖大伟，王国胤，胡峰.一种基于粗糙集理论的快速并行属性约简算法[J].计算机科学，2009（03）.
作者单位
1.镇江船艇学院 江苏省镇江市 212003