遗传算法范文10篇

遗传算法范文篇1

遗传算法的思想由来已久。早在20世纪50年代，一些生物学家就着手于计算机模拟生物的遗传系统。1967年，美国芝加哥大学的Holland,J.H.教授在研究适应系统时，进一步涉及进化演算的思考，并于1968年提出模式理论。1975年，Holland教授的专著《自然界和人工系统的适应性》问世，全面地介绍了遗传算法，为遗传算法奠定了基础[228]。此后，遗传算法无论在理论研究方面，还是实际应用方面都有了长足发展。

伴随遗传算法的发展，其独特的优越性逐渐被体现出来，且各种理论、方法都得到了进一步发展和完善。但是，遗传算法的实际应用仍然存在着缺陷，具体表现在：

遗传算法在寻优过程中易出现“早熟”、设计变量增多时效率较低以及结构分析时间长，在线功能差。为此，在实际运用中尚需改进，寻找更优秀的算子和编码方法等。目前，改进的方法也各有优劣，有对遗传算法遗传算子进行改进的，也有将遗传算法与其他方法结合起来的。编码方法有二进制编码、多值编码、实值编码、区间值编码、Delta编码等多种编码方法。在执行策略方面有如下几种方法值得注意：遗传算法与模拟退火算法的结合、遗传算法与局部优化方法的结合、并行遗传算法、共存演化遗传算法、混乱遗传算法。

遗传算法的噪声适应性问题。遗传算法主要是针对无噪声的确定性环境设计的，在应用过程中，知识的不确定性、训练样本的错误、人为因素等都可导致问题求解环境包含一个或多个噪声。事实上，噪声是不可避免的，在实际工程测量中，测量得到的静态应变常常会伴有一定的噪声。遗传算法的进化过程是通过适应度大小来进行选择、变异、交*等遗传算子操作，从而对个体进行优胜劣汰。然而在噪声环境下，目标函数或适应度带有噪声，不能反映个体真正的适应度。显然，用有噪声的适应度去进化，其结果可能会被误导。在这种情况下，遗传算法的性能如何，怎样改进，还有待深入研究。

遗传算法范文篇2

关键词遗传算法；TSP；交叉算子

1引言

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点[1]。

基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。

2遗传算法程序设计改进比较

2.1基本遗传算法对TSP问题解的影响

本文研究的遗传算法及改进算法的实现是以C++语言为基础，在Windows2000的版本上运行，其实现程序是在MicrosoftVisualStadio6.0上编写及运行调试的。

1)遗传算法的执行代码

m_Tsp.Initpop()；//种群的初始化

for(inti=0；i<m_Tsp.ReturnPop()；i++)

m_Tsp.calculatefitness(i)；//计算各个个体的适应值

m_Tsp.statistics()；//统计最优个体

while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)

{

//将新种群更迭为旧种群，并进行遗传操作

m_Tsp.alternate()；//将新种群付给旧种群

m_Tsp.generation()；//对旧种群进行遗传操作，产生新种群

m_Tsp.m_gen++；

m_Tsp.statistics()；//对新产生的种群进行统计

}

2)简单的遗传算法与分支定界法对TSP问题求解结果的对比

遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。

2.2初始化时的启发信息对TSP问题解的影响

1)初始化启发信息

在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。

2)遗传算法与含有启发信息的遗传算法求解结果的对比

当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。

表220个城市的TSP问题求解结果数据

算法交叉操作

次数最优解

出现时间平均

最优解

简单遗传算法80244.479.4s1641.8

含初始化启发信息的GA79000.237.4s1398.9

从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。

2.3交叉算子对TSP问题解的影响

1)循环贪心交叉算子的核心代码

for(i=1；i<m_Chrom；i++)

{

flag=0；

city=m_newpop[first].chrom[i-1]；//确定当前城市

j=0；

while(flag==0&&j<4)

{

sign=adjcity[city][j]；//adjcity数组的数据为当前城市按顺序排列的邻接城市

flag=judge(first，i，sign)；//判断此邻接城市是否已经存在待形成的个体中

j++；

}

if(flag==0)//如果所有邻接城市皆在待扩展的个体中

{

while(flag==0)

{

sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//随机选择一城市

flag=judge(first，i，sign)；

}

}

if(flag==1)

m_newpop[first].chrom[i]=sign；

}

2)问题描述与结果比较

下面笔者用经典的测试遗传算法效率的OliverTSP问题来测试循环贪心交叉算子的解的精度和解效率。OliverTSP问题的30个城市位置坐标如表3所示[2]。

从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在多次试验中，贪心交叉算子找到的最优解与目前记载的最佳数据的误差率为2.7%。而部分匹配交叉算子找到的最优解与目前记载的最佳数据的误差率高达7%。从而可以得到交叉算子对于遗传算法

2.4并行遗传算法消息传递实现的核心代码

1)主程序代码

//接收各个从程序的最优个体

for(i=0；i<slave；i++)

{

MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

}

//计算接收各个从程序的最优个体的回路距离

for(i=0；i<slave；i++)

{

fitness[i]=0.0；

for(intj=0；j<chrom-1；j++)

fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；

fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；

}

//找到最优的个体并把它记录到文件里

for(i=0；i<slave；i++)

{

if(1/fitness[i]>min)

{

sign=i；

min=1/fitness[i]；

}

}

fwrite(&gen，sizeof(int)，1，out)；

for(i=0；i<chrom；i++)

fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；

fwrite(&fitness[sign]，sizeof(double)，1，out)；

//每九代向从程序发送一个最优个体

if(gen%9==0)

MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

2)从程序代码

//将上一代的最优个体传回主程序

MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；

//每九代接收一个最优个体并将其加入种群中替换掉最差个体

if(gen%9==0)

{

PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

Tsp.IndiAlternate(Rchrom2)；

}

//进行下一代的计算

Tsp.Aternate()；

Tsp.Generation()；

Tsp.Statistics()；

3)并行遗传算法的性能

笔者在MPI并行环境下，用C＋＋语言实现了一个解决TSP问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的MPI程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光TC1700机，测试的对象是OliverTSP问题的30个城市的TSP问题。

正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有达到目前所记录的最好解，但是它提高了算法的收敛性，并行遗传算法的收敛趋势如图2所示[4]。

图2遗传算法的收敛过程

3结束语

本文通过对基本遗传算法的不断改进，证明了添加启发信息、改进遗传算子和利用遗传算法固有的并行性都可以提高遗传算法的收敛性，其中对遗传算法交叉算子的改进可以大大提高遗传算法的寻优能力。

参考文献

[1]刘勇、康立山，陈毓屏著．非数值并行算法－遗传算法．北京：科学出版社1995.1

[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230

遗传算法范文篇3

论文摘要：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结束语

遗传算法范文篇4

关键词：虚拟现实；遗传算法；遗传编码；适应度函数；工业设计；产品造型设计

随着科技快速发展，消费者对产品造型和功效的要求越来越高，不仅注重产品的使用功能，更追求视觉感官上的享受。为了响应快速发展的市场需求，利用虚拟现实技术辅助设计师完成产品造型设计是十分必要的。在传统产品造型设计过程中，主要是从产品功能出发，以提高产品表象形式为目的对其进行设计，包含产品的形态设计、产品的色彩设计、产品造型的质感等设计方面[1]。设计师需要首先以用户的需求为设计方向，利用自身设计经验分析产品的原理及性能，并设计出对应产品的基本结构、功能和形态等造型设计元素，主要依靠设计师的个人能力。单纯由设计师完成，难以保证设计工作的效率，无法满足产品造型设计快速开发设计的要求。因此，利用遗传算法的高度并行、自适应性优势，对工业产品造型设计求解[2⁃3]。为了更好地结合用户需求偏好和设计师的经验，同时避免设计师的主观看法以及用户参与评估的过程较多，将虚拟现实和遗传算法相结合，通过交互式手段利用人工评估进行调整，以人工评估的方式替代遗传算法中的适应度值，得到结果最优解，既可以减少用户工作量，又可以提高产品造型设计结果的收敛速度。

1遗传算法在工业产品造型设计中的运用

遗传算法可以同时处理多个设计目标，在一个工业产品造型设计过程中得到多个满意的产品造型设计结果。遗传算法在工业产品造型设计中的运用是以进化论和遗传学说为基础，对产品造型中的每个个体设计要素进行编码，再通过选择、交叉、变异算子进行基因的排列组合，直到生成满意的新个体。在进化过程满足一定条件后，进入人工评估阶段进行方案调整，若输出结果不是最优的，再进入计算机运行自然阶段，形成一个循环，直至生成最优设计方案[4]。由于计算机可以同时进行多个目标的并行搜索，因此，能提高产品造型的设计效率。基于遗传算法的工业产品造型设计流程如图1所示。1.1设计产品造型基因编码。在遗传算法运行中，使用浮点编码方式将实际可行解变量转变为个体编码，能够在确定规模的种群中表示更多的模式[5]。在初始种群中，产品形态、颜色等都可以表示成具体的层次结构数据，每一个功能单元均对应一个结构特征参数，每一个染色体均包含一系列特征参数集合。将可行解从解空间转换到搜索空间中，通过这种层次结构将特征浮点参数编码进产品个体中。用层次化染色体结构表示产品造型元素，如图2所示。产品染色体的基因位为功能单元染色体，功能单元的染色体基因位是特征参数的染色体，功能特征参数由浮点值定义[6]。设定每一个产品造型设计元素的参数编码包括功能单元的名称、数量、形状特征、几何大小、产品颜色等。部分产品造型设计编码参数数据类型如表1所示。在将编码参数导入计算机辅助软件之前，设计师需要从市场及概念设计中提取需要数据，按照上述层次结构进行数据的编码。不同产品对应的特征参数均不相同，这种差异化会影响遗传算法获得有效解[7⁃9]。因此，将编码数据的浮点值强制映射在相同有效范围区间内，使得每个对应基因位均在[0，1]范围，解决参数在不同范围上的问题。1.2确定编码个体适应度。在非人工评估阶段，也就是自然阶段，由目标函数变换得到适应度函数，对个体进行适应值评价。适应度函数为：F(x)={Cmax-f(x),f(x)<Cmax0,f(x)≥Cmax（1）式中：F(x)为适应度函数；f(x)为目标函数；Cmax为一个预设的相对较大的正数，以保证大多数解为正。设定种群平均适应度值为FA。产品造型设计是一个多目标寻优的过程，实际过程中包含多种特征参数，对应产品不同状态。使用形态语义加权方法，根据设计元素在设计方案中的重要程度设定合适权重值，将用户语义与产品特征描述对应联系起来，反映设计个体在多方面的优劣程度[10⁃11]。对每一个设计元素进行调查，对调查结果取算术平均值，得到人工评估适应度值FE。随机生成N个个体字符串，其中，N个个体作为初始种群大小，初始进化代数为gen，最大非人工进化代数为GEN。1.3产品造型设计方案进化。产品造型设计方案的进化由三种遗传算子支撑。从初始种群开始迭代，获得最初种群平均适应度后，选择适应度较高的个体两两配对，再经过遗传运算中的交叉、变异运算再生，得到新个体放入新种群中，重复此过程，直至新种群生成，在每一代运算后生成的新种群将替代旧种群[10]。交叉运算是在交叉概率Pc控制下，随机选择上一代种群中的两个个体进行交叉，由两个个体中适应度值较高的个体提供更多基因。变异运算首先设定初始变异概率Pm，Pm∈[0,1]。产生下一代种群后，比较两代种群中最优个体的适应度值，新种群最优个体小于旧种群最优个体适应度值时，将初始变异概率Pm增加0.05，否则，减少0.05，但始终保持变异概率在初始变异概率值与1之间。为保证将适应度值最好的个体保留到下一代种群中，用当前种群中适应度值最高的个体直接替代经交叉和变异遗传操作后产生的适应度值最低个体[12⁃13]。同时，如果上一代种群中的最优个体的适应度值高于当前种群中最优个体的适应度值，即用上一代种群中的最优个体代替当前种群中的适应度值最低个体。当算法运行生成新的产品造型设计方案，同时满足人工参与条件后，解码进入虚拟现实环境下参与人工评估阶段。1.4虚拟现实环境下人工评估设计方案。虚拟现实环境下人工评估阶段，主要是借助虚拟现实技术，由计算机主机进行控制，通过四维形式将储存在知识库和数据库的算法内容展现在虚拟场景中[14]，输出最终设计结果方案、图纸或造型给客户。虚拟现实设计结果输出流程如图3所示。图3虚拟现实设计结果输出流程由人工评价是否生成了最优方案。设定设计产品评价目标为u=(u1,u2,⋯,un)，对应权重分别为qi，用矩阵表示为Q=(q1,q2,⋯,qn)，对产品各评价目标进行评分：（2）如果在人工评估阶段产生了用户满意的方案，那么停止算法运行，否则，转入自然阶段继续运行，并且剔除不符合设计要求的方案。至此完成虚拟现实环境下遗传算法在工业产品造型设计中的运用设计。

2仿真实验

设计模拟仿真实验，对比在虚拟现实环境下，利用遗传算法生成最优工业产品造型设计结果的收敛速度以及常规虚拟现实环境下生成设计结果的收敛速度。2.1实验准备及运行参数设定使用Matlab软件的GlobalOptimizationToolbox优化工具箱，将算法运行在原有建模系统[15]中。根据设计师的经验预先设定遗传算法中的运行参数值，其中，包括最大/最小种群数、传迭代数范围、交叉概率以及变异概率等参数。遗传算法类型选择最优保存策略及精英策略。遗传算法所需部分运行参数如表2所示。2.2实验结果以迭代次数为横轴，系统运行时间为纵轴，绘制算法收敛曲线如图4所示。2020年第43卷由图4可知，常规生成最优工业产品造型设计结果的收敛速度大约要经过700次迭代，而基于遗传算法的工业产品造型设计在迭代到290次时精确收敛到全局最优解。结果表明，在相同条件下基于遗传算法生成的工业产品造型设计结果的收敛速度更快，能更快速地收敛到全局最优解，提高了设计效率。

3结语

遗传算法范文篇5

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基于遗传算法的机械产品设计系统应用

遗传算法范文篇6

关键词：遗传算法全局寻优自动化组卷

1引言

计算机辅助考试系统的自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉及到一个全局寻优和收敛速度快慢的的问题，很多学者对其进行了研究。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。

PottsJC等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；HamiltonMA等结合遗传算法把其运用到神经网络中，并取得了良好的效果[4]；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的。

本文结合遗传算法的原理和思想，对考试自动出题组卷的问题进行了研究，找到了一种获得与考试试题控制指标符合的试题模型的解决方法。

2问题描述

自动组卷是考试系统自动化或半自动化操作的核心目标之一,而如何保证生成的试卷能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性,这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动组卷的关键。

以往的具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当题库中各状态类型平均出题量较低时，组卷往往以失败而告终。

回溯试探法这是将随机选取法产生的每一状态类型纪录下来，当搜索失败时释放上次纪录的状态类型，然后再依据一定的规律（正是这种规律破坏了选取试题的随机性）变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法接受的，因此它也不是一种很好的用来自动组卷的算法。

分析上述两种算法的优缺点，不难发现，在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷失败。回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法（GeneticAlgorithms）以其具有自适应全局寻优和智能搜索技术，并且收敛性好的特性能很好的满足自动考试组卷的要求。

3遗传算法描述

遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及Eldridge与Gould间断平衡理论为依据，同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想，模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作：selection，crossover，mutation……这样进行不断的所谓“生存选择”，最后收敛到一个最适应环境条件的个体上，得到问题的最优解。[6,7]

4遗传算法应用

一般来说，用户在自动组卷时会对试卷的质量提出多方面的要求，如总题量、平均难度、题型比例、章节比例、重点章节比例、知识点的交叉与综合等，自动组卷就应最大程度的满足用户的要求。因此，在组卷之前，我们首先为自动组卷过程建立控制指标相应状态空间D，

D=[]

D的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这些属性指标都进行编码表示成二进制形式，而每一列是题库中的某一指标的全部取值。在具体出题时，考方可能不会用到所有的指标，所以D包含的个体d_target可以表示为d_request和d_void，d_request表示考方要求的控制指标，d_void表示考方不要求的控制指标。即

d_target：：=<d_request>：<d_void>

<d_request>：：={0，1}m

<d_void>：：={0，1}n

试题库[STK]中的每一道试题在建库时都输入了相应的属性指标。试题模型的产生形式是：

if<data>then

<model>

<data>：：={0，1，#}m

#表示0和1之间的任意一位。

考试自动出题的遗传算法如下：

(1)根据考方的出题要求，规划状态空间库D中的数据，保留d_request部分，而不要d_void部分，对其剩余部分进行编码D[1]，D[2]，……D[i]。

(2)初始化试题库[STK]。随机从题库中抽出一组试题，并进行编号STK[1],STK[2]……STK[j],确定合适的交换概率Pc和变异概率Pm；并定义其适应值flexibility[k](k=1,2……j)

flexibility[k]<-0(k=1,2……j)

(3)从试题库[STK]中取出STK[m](0≤m≤j)与状态空间库[D]中的指标D[n](0≤n≤i)进行匹配。如果STK[m]与D[n]完全匹配，则

flexibility[k]<-flexibility[k]+1

如果不匹配，则有

flexibility[k]<-flexibility[k]+0

(4)进行淘汰选择，保留具有高适应度的试题。即把flexibility[k]为0的STK[m]去掉，这样就生成了一个新的试题模型STK[h]。

(5)重复过程2生成新的试题模型STK[p]。按一定的交换概率Pc从[STK]中随机选取模型STK[h]和STK[p]，交换彼此位串中对应的值，产生新的试题模型STK[h]、STK[p]，如

交换前STK[h]=110101

1

STK[p]=0011110

交换前STK[h]=1111011

STK[p]=1111110

(6)按一定的变异概率从题库[STK]中随机选出一试题模型STK[h]进行基因突变，产生一个新的试题模型。

(7)在完成以上选择、交叉、变异步骤后，产生一个考试试题模型，按照事先确定的误差精度对其进行收敛性的判别，当其适应度高时，试题组卷成功，转向步骤8，如果其适应度低，则转向步骤3继续执行。

(8)输出相应的考试试题，组卷结束。

以上用遗传算法抽题时，交换概率Pc和变异概率Pm的确定很重要。Pc

太小使选题工作进展缓慢，太大则会破坏适应值高的试题模型。通常规定其为0.4。同样，Pm太小就不能产生新的试题模型，太大又会产生过多的试题模型。它宜规定为0.1。

在自动选题时，选题的方式可采用父辈挑选和生存选择两种。父辈挑选就是采用不返回随机抽样，它使每个题目都有被选中的可能；生存选择采用允许父辈和子代进行竞争，并让其中的优良者进入下一轮竞争环境的二分之一择优选择。两种选择方式共同作用于选题保证了选题的顺利完成。在选题的过程中，哪一道题目被选中是一个非均匀随机事件，其概率依赖于上一次选题的过程。

5结束语

本文利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于自动组卷的好的算法，使自动组卷的成功率和速度都得到了明显的提高。要使自动出题的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。

参考文献

[1]J．H．Holland，Adaptationinnaturalandartificialsystems[M]，Annarbor:UniversityofMichigenpress,1975.

[2]HamiltonMA.JavaandtheShifttoNet-centricComputing.IEEEComputer,29(8),1996.

[3]袁富宇等，多目标相关分类的算法，浙江大学学报，33(3),1999

遗传算法范文篇7

关键词全局最优；混合算法；遗传算法；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．

遗传算法范文篇8

关键词:植保无人机;飞行控制系统;遗传算法;轨迹规划

随着无人机技术的不断发展，其在农业生产过程中应用范围也不断扩大。植保无人机在作业过程中具有较高的效率，能适应不同的应用环境，且可搭载不同的作业设备实现较高的灵活性［1］。无人机控制技术及人工智能程度逐渐提高，采用低功率、高效率的控制方式进行植保无人机飞行控制，已成为当前植保无人机发展的趋势［2－3］。在进行高效率智能控制过程中，为提高植保无人机的作业效率及作业质量，对无人机的飞行轨迹进行科学规划与控制，是植保无人机飞行控制系统的基础功能［4～5］。笔者针对植保无人机飞行作业过程中通过障碍区和非障碍区时的两种不同作业轨迹进行研究，提出一种基于遗传算法的植保无人机分析轨迹优化方法，以实现植保无人机飞行控制系统设计。

1无人机总体架构

植保无人机的主要架构包含飞行器、飞行控制系统及植保作业系统，如图1所示。在无人机上搭载飞行控制核心控制器，获取飞行器的飞行姿态及轨迹信息，并通过PWM指令信息进行姿态及轨迹的调整;同时，核心控制器输出控制指令，进行植保无人机作业系统控制［6－7］。

2无人机控制系统

植保无人机的飞行核心控制器包含飞行控制系统及地面控制系统。飞行控制器主要由飞行控制芯片组成，可在无人机飞行过程中读取传感器信号，并通过内置代码对传感器数据进行分析处理，解算出植保无人机飞行控制姿态角度［8］;同时，采用双闭环控制的方式完成飞行姿态角度的调整，将风速及其他噪音信号作为控制系统的干扰数据，从而达到消除扰动误差修正的目的，实现植保无人机飞行控制过程中的平衡稳定性［9］。植保无人机飞行过程稳定后，可接收地面控制指令，实现飞行过程的控制及植保作业过程的顺利进行。植保无人机飞行控制流程如图2所示。在植保无人机飞行过程中，传感器每隔2ms进行1次数据采集，实时进行无人机飞行姿态数据的更新;通过串口中断程序接收地面控制指令信号，并进行控制指令信号的处理，将接收到的地面期望控制指令进行解调，控制无人机按照期望飞行姿态进行飞行，保证植保无人机的自平衡稳定性，使其能够按照控制指令进行飞行［10］。图3所示为植保无人机控制系统工作流程图。根据植保无人机的飞行精度及作业要求，采用双闭环控制方式进行植保无人机控制程序的编制，将飞行姿态角度作为控制系统外环，将飞行角速度作为控制内环的双闭环控制系统［11］。在飞行控制过程中，每个自由度形成独立的闭环控制。其中，e(t)为角度偏差值;e(t－1)为上一时刻角度偏差值;Kp为角度环控制比例系数;Ki为角度环控制积分系数;Kd为角度控制微分系数;u(t)为角度环控制输出值。

3遗传算法与无人机飞行轨迹

植保无人机作业过程中，手动控制的操作方式无法适应无人机高效作业的需求，且容易造成无人机飞行过程路线偏离，导致无人机作业出现重复或者遗漏［12］。为提高无人机作业过程效率及作业准确性，采用遗传算法对无人机飞行过程中遇到障碍和无障碍两种条件下的飞行轨迹进行规划。在无障碍飞行过程中，以能源消耗最少为目标进行飞行轨迹规划;在有障碍物飞行过程中，以飞行轨迹长度最小为目标，同时减少飞行过程中转弯次数，提出一种基于遗传算法的植保无人机飞行轨迹规划算法。无障碍飞行轨迹优化过程中，首先将作业区域进行初始化，使作业区域划分为平面图，并寻找出作业区域边缘，随机生成不同的航向角个体。植保无人机飞行过程中，会遇到树木、电杆及建筑物等障碍，导致无人机无法按照无障碍情况进行飞行，此时需要采用一种避障轨迹规划的算法。随着障碍物数量的增多，植保无人机控制系统在进行避障轨迹计算时计算量加大，采用遗传算法进行轨迹优化，可有效进行避障轨迹的搜索。图4为避障轨迹优化算法流程图。

4仿真实验分析

为验证基于遗传算法设计的植保无人机飞行控制系统可靠性，设置两组实验进行验证。其中，一组为单障碍飞行，另一组为多障碍飞行。单障碍飞行过程中，在飞行区域设置1个障碍点，直径为8m，中心与飞行起点距离为60m，飞行区域宽度为40m、长度为120m，飞行速度分别为2、4、6m/s。飞行完成后，根据飞行坐标绘制植保无人机的轨迹，如图5所示。同理，多障碍飞行实验中，在飞行区域内设置两个不同障碍点，直径为8m，中心与飞行起点的距离分别为40m和80m，飞行区域宽度为40m、长度为120m，飞行速度分别为2、4、6m/s。飞行完成后，根据飞行坐标绘制植保无人机的轨迹，如图6所示。

5结论

遗传算法范文篇9

关键词：遗传算法全局寻优自动化组卷

1引言

计算机辅助考试系统的自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉及到一个全局寻优和收敛速度快慢的的问题，很多学者对其进行了研究。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。PottsJC等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；HamiltonMA等结合遗传算法把其运用到神经网络中，并取得了良好的效果[4]；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的。

本文结合遗传算法的原理和思想，对考试自动出题组卷的问题进行了研究，找到了一种获得与考试试题控制指标符合的试题模型的解决方法。

2问题描述

自动组卷是考试系统自动化或半自动化操作的核心目标之一,而如何保证生成的试卷能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性,这是实现中的一个难点。尤其在交互式环境下用户对于组卷速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动组卷的关键。

以往的具有自动组卷功能的考试系统大多采用随机选取法和回溯试探法。随机选取法根据状态空间的控制指标，由计算机随机的抽取一道试题放入试题库，此过程不断重复，直到组卷完毕，或已无法从题库中抽取满足控制指标的试题为止。该方法结构简单，对于单道题的抽取运行速度较快，但是对于整个组卷过程来说组卷成功率低，即使组卷成功，花费时间也令人难以忍受。尤其是当题库中各状态类型平均出题量较低时，组卷往往以失败而告终。

回溯试探法这是将随机选取法产生的每一状态类型纪录下来，当搜索失败时释放上次纪录的状态类型，然后再依据一定的规律（正是这种规律破坏了选取试题的随机性）变换一种新的状态类型进行试探，通过不断的回溯试探直到试卷生成完毕或退回出发点为止，这种有条件的深度优先算法，对于状态类型和出题量都较少的题库系统而言，组卷成功率较好，但是在实际到一个应用时发现这种算法对内存的占用量很大，程序结构相对比较复杂，而且选取试题缺乏随机性，组卷时间长，后两点是用户无法接受的，因此它也不是一种很好的用来自动组卷的算法。

分析上述两种算法的优缺点，不难发现，在限制条件状态空间的控制下，随机选取法有时能够抽取出一组令用户满意的试题。只不过由于它随机选取试题的范围太大，无法确定目前条件下哪些区域能够抽取合适的试题，反而可能在那些已经证明是无法抽取合适试题的区域内反复选题，进行大量的无效操作进入死循环，最终导致组卷失败。回溯试探法组卷成功率高，但它是以牺牲大量的时间为代价的，对于现今越来越流行的考生网上随机即时调题的考试过程来说，它已不符合要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法（GeneticAlgorithms）以其具有自适应全局寻优和智能搜索技术，并且收敛性好的特性能很好的满足自动考试组卷的要求。

3遗传算法描述

遗传算法是一种并行的、能够有效优化的算法，以Morgan的基因理论及Eldridge与Gould间断平衡理论为依据，同时融合了Mayr的边缘物种形成理论和Bertalanffv一般系统理论的一些思想，模拟达尔文的自然界遗传学：继承（基因遗传）、进化（基因突变）优胜劣汰（优的基因大量被遗传复制，劣的基因较少被遗传复制）。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。运用遗传算法求解问题首先需将所要求解的问题表示成二进制编码，然后根据环境进行基本的操作：selection，crossover，mutation……这样进行不断的所谓“生存选择”，最后收敛到一个最适应环境条件的个体上，得到问题的最优解。[6,7]

4遗传算法应用

一般来说，用户在自动组卷时会对试卷的质量提出多方面的要求，如总题量、平均难度、题型比例、章节比例、重点章节比例、知识点的交叉与综合等，自动组卷就应最大程度的满足用户的要求。因此，在组卷之前，我们首先为自动组卷过程建立控制指标相应状态空间D，

D=[]

D的每一行由某一试题的控制指标组成，如题号、题型、章节、难度等，并且这些属性指标都进行编码表示成二进制形式，而每一列是题库中的某一指标的全部取值。在具体出题时，考方可能不会用到所有的指标，所以D包含的个体d_target可以表示为d_request和d_void，d_request表示考方要求的控制指标，d_void表示考方不要求的控制指标。即

d_target：：=<d_request>：<d_void>

<d_request>：：={0，1}m

<d_void>：：={0，1}n

试题库[STK]中的每一道试题在建库时都输入了相应的属性指标。试题模型的产生形式是：

if<data>then

<model>

<data>：：={0，1，#}m

#表示0和1之间的任意一位。

考试自动出题的遗传算法如下：

(1)根据考方的出题要求，规划状态空间库D中的数据，保留d_request部分，而不要d_void部分，对其剩余部分进行编码D[1]，D[2]，……D[i]。

(2)初始化试题库[STK]。随机从题库中抽出一组试题，并进行编号STK[1],STK[2]……STK[j],确定合适的交换概率Pc和变异概率Pm；并定义其适应值flexibility[k](k=1,2……j)

flexibility[k]<-0(k=1,2……j)

(3)从试题库[STK]中取出STK[m](0≤m≤j)与状态空间库[D]中的指标D[n](0≤n≤i)进行匹配。如果STK[m]与D[n]完全匹配，则

flexibility[k]<-flexibility[k]+1

如果不匹配，则有

flexibility[k]<-flexibility[k]+0

(4)进行淘汰选择，保留具有高适应度的试题。即把flexibility[k]为0的STK[m]去掉，这样就生成了一个新的试题模型STK[h]。

(5)重复过程2生成新的试题模型STK[p]。按一定的交换概率Pc从[STK]中随机选取模型STK[h]和STK[p]，交换彼此位串中对应的值，产生新的试题模型STK[h]、STK[p]，如

交换前STK[h]=1101011

STK[p]=0011110

交换前STK[h]=1111011

STK[p]=1111110

(6)按一定的变异概率从题库[STK]中随机选出一试题模型STK[h]进行基因突变，产生一个新的试题模型。

(7)在完成以上选择、交叉、变异步骤后，产生一个考试试题模型，按照事先确定的误差精度对其进行收敛性的判别，当其适应度高时，试题组卷成功，转向步骤8，如果其适应度低，则转向步骤3继续执行。

(8)输出相应的考试试题，组卷结束。

以上用遗传算法抽题时，交换概率Pc和变异概率Pm的确定很重要。Pc

太小使选题工作进展缓慢，太大则会破坏适应值高的试题模型。通常规定其为0.4。同样，Pm太小就不能产生新的试题模型，太大又会产生过多的试题模型。它宜规定为0.1。

在自动选题时，选题的方式可采用父辈挑选和生存选择两种。父辈挑选就是采用不返回随机抽样，它使每个题目都有被选中的可能；生存选择采用允许父辈和子代进行竞争，并让其中的优良者进入下一轮竞争环境的二分之一择优选择。两种选择方式共同作用于选题保证了选题的顺利完成。在选题的过程中，哪一道题目被选中是一个非均匀随机事件，其概率依赖于上一次选题的过程。

5结束语

本文利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于自动组卷的好的算法，使自动组卷的成功率和速度都得到了明显的提高。要使自动出题的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。

参考文献

[1]J．H．Holland，Adaptationinnaturalandartificialsystems[M]，Annarbor:UniversityofMichigenpress,1975.

[2]HamiltonMA.JavaandtheShifttoNet-centricComputing.IEEEComputer,29(8),1996.

[3]袁富宇等，多目标相关分类的算法，浙江大学学报，33(3),1999

遗传算法范文篇10

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（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，但是搜索到全局最优的概率却远远高于标准遗传算法。