遗传算法论文篇1

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的组合，它并非盲目地完成计算，搜索数远小于问题解的数值。

遗传算法论文篇2

2基于遗传算法的模型优化

利用遗传算法进行模型优化，采用实数编码，染色体中每个编码位表示一个活动。假设设计活动总数为n，每个编码位的取值为1、2、…、n，每个整数只用一次。算法主要步骤如下：（1）初始化群体，群体中每一条染色体对应一个活动顺序设计方案，设置种群规模。（2）根据适应度函数计算群体中每个个体的适应度值。（3）采用赌法来选择下一代的个体，即个体被选中并遗传到下一代群体中的概率与个体的适应度大小成正比。（4）按交叉算子进行交叉操作，设置交叉概率。本文采用单点交叉法，例如两条父染色体分别为1234和5678，以第二个点作为分界点，交叉后得到的子染色体分别为1278和5634。（5）按变异算子进行变异操作，设置变异概率。文中变异方法为：若染色体长度为N，随机生成两个1～N之间的整数i和j，将个体i位和j位上的基因值相互对调。（6）如果不满足停止条件，转步骤（2），否则，输出种群中适应度值最优的染色体作为最优活动序列。

3算例

应用遗传算法进行优化时，种群大小设为140，最大遗传代数为200，交叉概率为0．9，变异概率为0．1，信息反馈系数wn＝0．4，交叉反馈系数wcn＝0．6。考虑返工量变化与不考虑返工量变化的优化结果对比如表3所示。从表3中可以看出，两种情况下，反馈点、交叉点和反馈距离的优化结果相同，但由于考虑返工量变化后每次返工时只做原工作量的一部分，因此在设计迭代时间和成本上得到进一步的减少。以活动9和活动8之间的返工时间计算为例，从图5和图7中可以看出，DSM中第三行第六列的数字表示活动8到活动9之间的返工次数为2次，返工活动执行的顺序依次为9、7、10、8。若不考虑返工量变化，则总返工时间t＝（19＋21＋20＋22）×2＝164；若考虑返工量变化，从图3中可以看出活动8到活动9的返工影响因子为0．6，则总返工时间t＝（19＋21＋20＋22）＋（19＋21＋20＋22）×0．6＝131．2；虽然两种情况下活动的顺序一样，但考虑返工量变化时的总返工时间较少。

遗传算法论文篇3

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

遗传算法论文篇4

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)14-20917-02

1 引言

近年来，遗传算法以其高效实用的特点迎来了兴盛发展的时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是在应用研究方面，众多的研究者在组合优化、模式分类、预测控制等领域都取得了丰硕的成果。对于大自然生物演化的行为准则，达尔文给出了“物竞天择，适者生存”的有力概括，这一学说也成为人们向大自然学习的一个依据。

2 国内外研究现状

遗传算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如raser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。它使用群体搜索技术，通过对目标群体实施选择、交叉、变异等一系列遗传操作，从而产生新一代的群体，并使群体进化包含或接近最优的状态。

自1985年以来，国际上已多次召开了遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的ICGA（International Conference on Genetic Algorithms）会议和FOGA(Workshop on Foundation of Genetic Algorithms)会议，为研究和应用遗传算法提供了国际交流的机会。

3 遗传算法的产生及发展

遗传算法(Genetic Algorithms,GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，20世纪60年纪末期到70年代初期，主要由美国著名学者密西根大学教授John.Holland其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。由于它采用种群（即一组表示）的方式组织搜索，这使得它可以同时搜索空间内的多个区域。而且用种群组织搜索的方式使得遗传算法特别适合大规模并行。在赋予遗传算法自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使遗传算法具有不受其搜索空间限制性条件（如可微、连续、单峰等）的约束及不需要其它辅助信息（如导数）的特点。这些崭新的特点使得演化算法不仅能获得较高的效率而且具有简单、易于操作和通用的特征，而这些特征正是遗传算法越来越受到人们青睐的主要原因之一。

4 遗传算法的基本原理

遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

遗传算法的实施过程包括编码、产生初始群体、计算适应度、复制、交换、突变、反复迭代、终止等操作。我们用Gen代表遗传（迭代）的代次，遗传算法从Gen=0开始。根据所研究问题的表达方式确定字符串长度L，接着随机产生M个初始群体。刚开始时，终止条件不会被满足，于是依次计算群体中各个个体的适应度。根据计算结果，依次进行复制、交换、突变等遗传操作。

遗传算法的思想简要给出如下：（1）初始化群体；（2）计算群体上每个个体的适应度值；（3）按由个体适应度值所决定的某个规则选择将进入下一代的个体；（4）按概率Pc进行交叉操作；（5）按概率Pc进行突变操作；（6）没有满足某种停止条件，则转第（2）步，否则进入（7）；（7）输出种群中适应度值最优的染色体作为问题的满意解或最优解。

5 遗传算法的缺点及改进

尽管遗传算法有许多优点，但目前存在的问题依然很多，如：（1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用；（2）遗传算法的早熟现象（即很快收敛到局部最优解而不是全局最优解）是迄今为止最难处理的关键问题；（3）快要接近最优解时在最优解附近左右摆动，收敛较慢。

因此，遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择遗传操作方式及相关参数，停止准则确定等。相应的，为改进简单遗传算法的实际计算性能，很多学者的改进工作分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。

6 总结

遗传算法是将生物学原理应用于计算机科学的仿生学理论成果。由于它具有极强的解决问题的能力，引起了众多学者的兴趣与参与，已成为学术界跨学科的热门专题之一。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多优化领域。据不完全统计，进化算法已经在16 个大领域、250 多个小领域中获得了应用。遗传算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，己引起了数学、物理学、化学、生物学、计算机科学、社会科学、经济科学及工程应用等领域专家的极大兴趣和广泛关注。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

参考文献：

[1] Holland J H(1975).Adaptation in natural and artificial systems. University of Michigan Press.

[2] 田延硕.遗传算法的研究与应用[D].电子科技大学硕士论文.

[3] 李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].科学出版社,2003.

遗传算法论文篇5

 

0引言

遗传算法是一种较新的全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。但由于算法复杂度的限制, 遗传算法虽然能以概率收敛到全局最优解，其局部搜索速度和精度并不能得到很好的保证。近几年来遗传算法作为优良的全局寻优方法日趋成熟,尤其是和其他寻优方法的结合,进一步提高了遗传算法的性能，其中借助于混沌改进遗传算法的性能,是近年来遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力,搜索精度,搜索速度等几方面得到较明显的改进。

1混沌的特征和虫口方程

混沌是存在于非线形系统中的一种较为普遍的现象。混沌并不是一片混乱，而是有着精致内在结构的一类现象。混沌运动具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。

描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：

2混沌遗传算法

GA较传统数学优化方法更易找到全局最优解，但对于一些问题也存在过早收敛、收敛速度较慢、难以找到较精确解的情况。因此，本文通过Logistic映射及相关混沌理论提出了一种运算性能较好的混沌遗传函数优化算法。混沌遗传算法(CGA)的主要步骤如下：

1.初始化:预先确定运行参数，包括：种群规模M，交叉概率pc，变异概率pm，最大迭代次数n。随机产生一个分布均匀的初始群体(包含n个初始解)，计算各个个体的适应度值；

2.采用比例选择算子对当前种群进行选择操作，实现强留劣汰；

3.对当前种群进行交叉运算。将种群内个体两两随机组合，对每个配对的组合，首先由系统随机生成一个(0,1)之间的数，由交叉概率决定是否交叉。论文参考。论文参考。若交叉，则采用映射生成的序列经简单映射后利用高斯函数来决定交叉位置，否则，看下一对组合。所有的交叉位置由一个混沌序列即可决定；

5.若终止条件满足，则算法中止，否则转向步骤(2)。

本文尝试在将改进后的遗传算法与混沌优化算法相结合，提出一种基于混沌理论的混合遗传算法，算法的流程如下页流程图所示：

图1 改进后的混沌遗传算法（ICGA）流程图

3仿真分析

本文选用一维和多维多峰值函数为例，见表1，用遗传算法（GA）、混沌遗传算法（CGA）和本文算法（ICGA）进行比较研究。

表1 测试函数

实验结果比较如下（以下图纵坐标表示最大适应值，横坐标表示演化代数）

图2 f2实验结果比较示意图图3 f3实验结果比较示意图

从图2、图3的比较结果看，本文中算法初始种群较好，进化开始就能找到高的最大值，加快搜索的速度，整个算法的寻优结果比遗传算法好。论文参考。考虑到算法中使用了随机操作，仅仅由一次实验得到的结果是不能够充分说明问题的，因此，再进行统计比较。本文中进行了20次统计实验。比较结果如表2

遗传算法论文篇6

0 引言

PID控制作为最早实用化的控制算法已有70多年历史，现在仍然是控制系统中应用最为普遍的一种控制规律。它所涉及的算法和控制结构简单，实际经验以及理论分析都表明，这种控制规律对许多工业过程进行控制时， 一般都能得到较为满意的控制效果。随着控制理论的发展，尤其是人工智能研究的日趋成熟，许多先进的算法理论逐渐被应用到传统的PID控制中，并取得了更为优越的控制效果。本文就以传统PID控制和遗传算法理论为基础，简述了基于遗传算法整定的PID控制基本理论和方法。

1 PID控制

通过将偏差的比例（Proportional）、积分（Integral）、微分（Derivative）进行线性组合构成控制量，对被控对象进行控制，这种控制方法叫做PID控制。在自动控制发展的历程中，常规PID控制得到了广泛的应用，整个控制系统由常规PID控制器和被控对象组成，根据系统给定值r（t）与实际输出值y（t）存在的控制偏差e（t）=r（t）-y（t）组成控制规律。PID控制器将偏差e（t）的比例-积分-微分通过线性组合构成控制量，对被控对象进行控制。其基本控制规律为

式中，Kp为比例增益，Ti为积分时间常数，Td为微分时间常数，u（t）为控制量，e（t）为偏差。

2 遗传算法基本操作

遗传算法，简称GA（Genetic Algorithms），是由美国Michigan大学的Holland教授于上世纪六十年代率先提出的一种高效并行全局最优搜索方法。遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，它将“优胜劣汰，适者生存”的生物进化理论引入优化参数形成的编码串联群体中，按所选择的适配值函数通过遗传中的复制、交叉和变异对种群个体进行筛选，并保留适配值高的种群个体，组成新的群体。新的群体既继承了上一代的种群信息，又包含有优于上一代的个体信息，这样周而复始，种群中个体的适应度不断提高，直到满足一定的特定条件而停止运算，从而得到最优解。

遗传算法的关键技术包含以下几个方面：

（1）遗传编码：遗传算法的编码方式主要有二进制编码、十进制编码、实数编码等。二进制编码是比较常见的编码方式，它将解空间编码成二进制串，然后对其进行遗传算法运算，二进制编码既符合计算机处理信息的原理，也方便了对染色体进行复制、交叉和变异等操作，但它通常都需要进行参数进制转换，需要对高维参数进行编码时很难平衡编码长度和变量精度之间的关系，算法的执行效率也是一大问题。实数编码将问题的解用一个实数来表示，解决了编码对算法精度和存储空间的影响，精度高，便于大空间搜索，适于高维复杂优化问题。

（2）适应度评估：遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会，个体适应度大的个体更容易被遗传到下一代，而用来衡量个体适应度大小的函数则被称为个体适应度函数。为正确分析遗传概率，通常要求所有个体的适应度必须为非负值，因此需要确定由目标函数到个体适应度值之间的转换规则。

（3）遗传算子：遗传算法的遗传算子主要包括选择算子、交叉算子和变异算子。选择算子是指从当前种群中根据“优胜劣汰、适者生存”的自然原理，选择适应度值高的个体以产生池的过程。选择的主要目的是避免有效基因的损失，提高全局收敛性和计算效率，通常使用的方法有适应度比例法、期望值法、排位次法等；交叉算子是指将两个父代个体的相关染色体的特定基因，加以重组排列出新个体的过程。交叉算子是遗传算法的核心，并决定遗传算法的收敛性和、，可提高算法执行过程中的优化效率，常用的交叉运算方式有单点交叉、多点交叉和均匀交叉运算等；变异算子是指以一定的概率模拟自然界生物进化中染色体上某等位基因发生的突变现象，从而改变遗传基因的过程。若只有选择和交叉，而缺乏变异，则有可能使进化过程在早期就陷入局部解而进入终止过程，造成算法的早熟收敛，变异操作一定程度上克服了这种情况，有利于在尽可能大的空间中获得质量较高的优化解。

（4）算法参数：遗传算法运行时有几个参数需要在种群初始化或者种群进化过程中进行合理的选择和控制，主要包括个体编码长度l、群体规模M（一般取20～100）、终止进化代数G（一般取100～500）、交叉概率Pc（一般取0.4～0.99）和变异概率Pm（一般取0.0001～0.1）。

3 基于遗传算法的PID控制

在传统的控制理论当中，PID控制的好坏主要取决于三个控制参数调节的好坏，而遗传算法的出现则提供了一种优化参数调节的可行方法。利用遗传算法对PID控制参数进行寻优并寻找合适的控制参数，使得设定的性能指标达到最优化，这就是基于遗传算法的PID控制的基本思想。

选取被控对象为二阶传递函数，采样时间为1ms，

采用10位二进制编码方式，样本群体规模为M=30，终止进化代数G=100，交叉概率为Pc=0.60，变异概率为Pm=0.001，进行Matlab仿真实验，其阶跃响应如图1所示。

4 结果讨论

由Matlab仿真实验结果可见，基于二进制编码遗传算法的PID控制阶跃响应过渡平稳，能快速达到控制要求，控制效果较为优良。根据遗传算法的特性，在实际应用中通过改变编码方式、交叉变异概率、样本数量及终止进化代数等参数都能显著影响到控制效果，这也为进一步提升遗传算法的优化方案指明了发展方向。

参考文献

[1] 刘金琨. 先进PID控制及Matlab 仿真[M]. 北京： 电子工业出版社，2011.

[2] 侯志强. 基于遗传算法的PID控制参数优化在炉温监控系统中的应用[D]. 长沙：中南大学，2012.

[3] 朱成娟. 遗传算法的改进及其若干应用[D]. 秦皇岛：燕山大学，2006.

遗传算法论文篇7

中图分类号：G431 文献标识码：A 文章编号：1009-914X（2014）27-0290-01

1 引言

利用计算机自动选题组卷，不仅节约了组卷工作者的工作时间，还能避免工作中出现的主观错误，增强考试的客观性、真实性以全面的反应实际的效果，有利于评价教学质量与教学水平。本文主要研究在已生成的题库情况下，根据试卷结构要求，利用MATLAB中遗传算法和0-1线性规划算法进行组卷，比较两种组卷方法的优劣。2采用的组卷算法

2.1 遗传算法

遗传算法[1]它是由美国密歇根州立大学的霍兰教授于1975年首先提出来的。它的求解过程是从若干可行解开始，即从任意初始种群出发，然后按照选择、交叉、变异及自然选择的规律和法则进行迭代，产生新解或称新个体，新个体加入原种群，继续参与遗传迭代，最后收敛到一个最适应环境的个体上，即为最优个体（最优结果）。利用遗传组卷算法能根据不同的组卷要求产生不同的试卷，而遗传算法具有自组织性和大规模并行计算能力[2]，非常适合解决此类问题。

2.2 0-1线性规划算法

有学者将线性规划引入测量领域，用于组卷[3]，下面给出一个0-1线性规划的简单模型：

模型中决策向量，i =1，2，...n，n是题库中的题数，为项目权重，为组卷约束条件，如测验量要固定为30，各章节、题型、难度等级等题量的分布情况。0-1整数规划的一般解法是通过单纯形法解出各个x的值，再用分枝确界法将x的值由[0，1]取为0或1。

3 GA和0-1线性规划用于组卷

3.1 试题属性指标体系

试题的属性指标是计算机进行抽题组卷的基础。根据已有研究，试题指标主要有题号、题型、难度、区分度、能力层次、分值等属性指标。

3.2 模拟题库

模拟一个题库，题数300个，题号1到300，题库参数表（表1）中列出题库样例，题库通过Matlab随机数函数生成。

表1 模拟试题库样例

4 总结和展望

本文主要工作如下：（1）本文通过查看大量有关自动组卷系统的文献，简要的介绍遗传算法，0-1线性规划算法；（2）简要的介绍了题库试题的属性指标及组卷要求等，分析了组卷的各项约束条件，如难度，内容，题型等；（3）将MATLAB遗传算法法和0-1线性规划应用到自动组卷问题中，并进行了模拟研究。结果表明：在模拟题库下，遗传算法和0-1线性规划组卷成功率相当，带随机性的遗传算法更方便得到多套平行试卷。

值得改进之处：（1）本文只是利用模拟题库参数，将MATLAB遗传算法法和0-1线性规划进行自动组卷，得出试卷试题编号。并没有开发和实现题库管理系统、题库与组卷算法整合等工作；（2）本文只是比较了两种组卷算法的表现，还有更多组卷算法，如最大优先指标Cheng， & Chang （2009） [7] ；（3）本文主要是基于经典测验理论指标进行组卷，基于项目反应理论指标进行组卷值得进一步研究，如李佳，丁树良，汪文义，吴锐（2009）[8]就采用最大优先指标在项目反应理论下进行组卷。

参考文献

[1] 席裕庚， 柴天佑， 恽为民. 遗传算法综述， 控制理论与应用， 1996，13： 697-708

[2] 全惠云， 范国闯， 赵霆雷. 基于遗传算法的试题库智能组卷系统研究， 武汉大学学报（自然科学版）， 1999， 45： 758-760.

遗传算法论文篇8

Threshold Citrusimage Segmentation Research and Analysis

WANG Jun, ZHOU Li-juan

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

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

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

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

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

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

1脐橙图像分割

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

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

2改进的遗传算法

2.1控制参数改进

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

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

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

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

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

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

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

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

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

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

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

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

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

遗传算法论文篇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）可行课程表的产生。

这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。

结论

本文采用遗传算法来对课表编排问题进行求解，是求解这种难解的组合优化问题方法中较明智的选择，目的是在遗传算法基础上提出一个课表方案的随机生成和优化方案，能够较大程度地实现课表编排和多个目标的最优化。本文算法对我们这类院系较多、教师工作量大、学科变化较大、不确定性较多的学校能有所借鉴。

参考文献

遗传算法论文篇10

引言

遗传算法GA（GeneticAlgorithms）模拟了达尔文的“适者生存，优胜劣汰”的自然进化论与孟德尔的遗传变异理论是由Michigan大学Holland教授1975年在他的专著AdaptationinNaturalandArtificial首次提出。其基本流程如图1。遗传算法（GA）与传统算法有很多不同之处，主要体现在GA适应性强，其使用的算子是随机的，如交叉、变异和繁殖等算子不受确定性规则的控制。但这种搜索也不是盲目的，而是向全局最优解方向前进。直接使用适值函数进行适值计算，而不需要求优化函数的导数，使一些不可求导的优化函数也可用GA优化；GA具有较强的鲁棒性，它能同时搜索解空间的多个点，从而使之收敛于全局最优解，而不至于陷入局部最优解；另外它还具有智能性和并行性，利用遗传算法的方法，可以解决那些结构尚无人能理解的复杂问题。它已广泛应用于函数优化、组合优化、模式识别和信号处理等领域，在处理复杂优化问题时遗传算法显示了巨大潜力，在实际工程应用中取得了巨大成功。由于上述特点，建立合理的模型，可以将GA用于设备的状态监测和故障诊断之中。本文把近年来的有关GA用于故障诊断的文献进行分析、归纳，总结出GA在故障诊断中的具体应用。

GA用于故障诊断从目前来看，有直接应用于故障诊断之中，主要用于提取特征向量，为诊断的后续处理作准备。有和其他的诊断方法相结合，研究得较多。

一、利用遗传算法提取、优化特征参数

机械故障诊断是一个典型的模式分类问题。在诊断实践中，由于诊断对象的复杂性，故障特征和故障类别的对应关系不甚明了，人们提出了大量的原始特征以进行故障识别。但由于特征向量之间存在一定的关联性，且特征向量对不同故障的敏感程度不同，这对设备诊断的效率和准确率有重要的影响。要对这些特征向量进行优化，使它们能够适应实际需要。

史东锋等对回转机械故障诊断中3类由同步振动引起的故障来分析，应用遗传算法，染色体采用二进制编码方式，以样本类内、类间的距离判据为适应值函数，进行特征选择，高效地剔除原始特征集的冗余特性，提高故障的识别精度。而用常规方法对得到的23个特征量进行分类，由于起高度的冗余性，很难取得理想的分类效果。

二、遗传算法与人工神经网络（ANN）的结合应用

人工神经网络以其强有力的学习和并行处理能力为故障诊断提供了全新的理论方法和实现手段。神经网络通过对经验样本的学习，将知识以权值和阈值的形式存储在网络中。网络的输入是被诊断对象的征兆即特征值，输出则表示发生故障的可能性。神经网络是以神经元为信息处理的基本单元，以神经元间的连接弧为信息通道，多个神经元联结而成的网络结构。神经网络以其独特的联想、记忆和学习功能在机械设备故障诊断领域受到广泛关注，其中研究较多的是BP神经网络及其改进算法。

三、遗传算法与模糊集理论的结合应用

模糊集理论是一种新的数据分析和处理方法，使用模糊集理论可以对决策表进行简化，去除冗余属性。故障模糊诊断的基本原理是利用模糊变换的原理、最大隶属度和阈值原则，根据各故障的原因与征兆之间不同程度的因果关系，在综合考虑所有征兆基础上来诊断旋转机械振动故障的可能原因。将模糊集理论应用到解决旋转机械故障诊断问题时，要计算旋转机械振动故障数据库中的频域征兆，使用模糊集理论对其进行约简，根据约简的结果生成规则。利用得到的规则对故障样例进行诊断。

四、遗传算法与小波理论的结合应用

遗传算法论文篇11

遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。同时，遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。

1.基本遗传算法

Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以每个基因产生的个体对环境具有某种适应性。基因突变和基因交叉可产生更适应于环境的后代。经过优胜劣汰的自然选择，适应性高的基因结构得以保存下来。

在基本遗传算法的运行过程中，控制参数的选择对搜索性能产生非常大的影响。因此对参数的合理选择与控制是十分重要的，以使 GA 呈现最佳搜索轨迹最终得到最优解。主要的控制参数包括染色体的长度L,种群规模M，交叉概率pc，变异概率pm。

作为一个优化算法，基本遗传算法也具有一些缺点，主要体现在以下几个方面。

首先，基本遗传算法是一类随机搜索型算法，而非确定性迭代过程描述。这种广种薄收的算法计算效率较低。

其次，对基本遗传算法的数值试验表明，算法经常出现过早收敛的现象。

第三，基本遗传算法的遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变化也使得一些好的优良个体的形态被过早破坏，降低了各代的平均适应值。

第四，Rudolph通过 Markov 链方法证明了基本遗传算法是不收敛到最优解的。

第五，基本遗传算法中常采用伪随机函数(rand)产生的“随机数”来生成初始种群和控制遗传算子的操作，这些“随机数”不具备真正的随机性和遍历性，很大程度上影响到最优解的出现。

基于这些局限性，本设计在下文中提出了一种改进的遗传算法，针对这些问题提出了几种有效的解决方案。

2.改进遗传算法的设计

2.1 遗传算法的收敛性的定义

Rudolph 给出了一种针对个体的收敛性定义：

设 Zt为 t 时刻种群 X(t)中所包含的个体的适应度值的最大值，f*为适应度值函数 f(x)在所有可能的个体所组成的集合中所取的最大值，若 Zt满足:

（2.1）

则称算法收敛到最优解。

2.2 精英保留策略

针对基本遗传算法不能收敛到全局最优解的问题，本设计提出，在进行选择前用保留最优解的策略，使算法最终能以100%的概率收敛到最优解。

精英保留策略是改进的遗传算法收敛性的保证。

2.3 引入混沌的遗传算子

⑴Logistic映射在交叉操作中的应用

用混沌序列来控制交叉点的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列。映射到染色体的基因位空间，并在相应的位置进行交叉操作。

⑵Logistic映射在变异操作中的应用

用混沌序列来控制变异位置的选择的思想为:设染色体有L位长，先产生一个混沌序列，然后把序列映射到染色体的基因位空间，并在相应的位置进行变异操作。

本设计中，采用Logistic映射产生混沌序列来控制遗传算子操作的策略称为混沌控制策略，它的优点在于在遗传进化的过程中充分利用了混沌所具有的随机性，尤其是混沌的遍历性，使交叉和变异操作具有内在的规律性，克服了简单遗传算法中伪随机所带来的缺点，充分发挥了遗传算法和混沌的各自优点。

2.4 自适应交叉和变异率算子

本设计中提出自适应交叉和变异率算子：当适应度低于平均适应度值时对它就采用较大的交叉率和变异率；如果适应度高于平均适应度值，对它就根据其适应度值取相对应的交叉率和变异率。当适应度值接近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率和变异率的值为零。为了保证每一代的优良个体不被破坏，采用精英选择策略，使它们直接复制到下一代中。

经过上述改进，pc和pm计算表达式如下：

（2.2）

（2.3）

上式中pc1，pc2，pm1，pm2的取值需要根据实际问题的规模，通过多数实验验证得到。

2.5 灾变算子设计

设计中引用了灾变的思想：在种群适应值保持在一个稳定值一段时间后，发生灾变，杀掉最优秀的个体，这样才可能产生更优秀的物种。

3.实验环境

实验测试的环境和工具:

⑴ 硬件环境:Intel Pentium® T4200@2.00GHz+ 2G RAM;

⑵ 操作系统:Mierosoft Windows xp Professional;

⑶ 编译环境: microsoft visual c++ 6.0;

⑷ 测试函数:

4.结论

⑴知道遗传算法的设计要从大体五个方面来设计：编码，初始种群的设定，适应度函数的设计，遗传操作的设计和控制参数的设定。在很好地设计一种遗传算法，且将其进行具体实际的应用，怎样去很好地选择、平衡这五个方面使算法得到更加理想的效果，这还需要继续进行试验研究，探讨。

⑵在进行遗传算法理论分析研究时，发现相关理论分析比较少。每一种设计的遗传算法都是将其进行具体的应用，所以算法的灵活性比较大，这样去寻求一种概括性的理论分析就存在一定的难度，且本设计提出的自适应遗传算法，从理论上分析研究其收敛到全局最优，仍然需要进一步的研究。

⑶关于遗传算法的定量分析和数学证明，仍需要进一步的研究。

参考文献:

[1]王小平，曹立明.遗传算法―理论应用与软件实现[M].西安：西安交通大学出版社，2002：21-22.

[2]张明辉，王尚锦.自适应遗传算法及其应用[J].机械工程学院学报，2002，20(1)：23-25.

[3]雷德明.多目标智能优化算法及其应用[M].北京：科学出版社，2009：67-78.

遗传算法论文篇12

1引言

随着城市轨道交通的发展,实时动态数据反映成为监控机车状态的重要组成部分,而遗传算法与模糊控制方法所具有很好的鲁棒性和形式上的简单明了使得它必然可以在城市轨道交通上得到巨大应用。遗传算法是一种自然进化系统的计算模型,也是一种通用的求解优化问题的适应性搜索方法,尤其是后者得到人们关注和普遍使用。而模糊控制则是近代控制理论中建立在模糊结合论基础上的一种基于语言规则与模糊推理的控制理论。

目前我国城市轨道交通建设正在蓬勃发展,伴随是城市轨道交通信息的大量增多与多信息融合,而在信息融合中经常会运用到遗传算法与模糊规则相结合的方法。

2信息融合结构方法

信息融合由于其应用上的复杂性和多样性,决定了信息融合的研究内容极其丰富,涉及的基础理论较多。多传感器信息融合根据信息表征的层次结构,其基本方法可分为3类:

数据层融合:在数据层融合中,每一个传感器观测物体并且组合来自传感器的原始数据.然后,进行特征识别过程.此过程一般是从原始数据中提取一个特征矢量来完成,并且根据此特征做出决策。

特征层融合:在特征层融合中,从观测数据中提取许多特征矢量后把它们连接成单个矢量,下一步进行识别.在该情况下,需要的通讯带宽减小,结果的精确性也相应减小,主要是因为在原始数据中生成特征矢量的同时,信息也在丢失。

决策层融合:在决策层融合中,每一个传感器依据本身的单源数据做出决策.这些决策被融合生成最后的决策,在上面阐述的3种结构中,精确性是最差的,但需要的带宽最小。

对于信息融合算法具体可以分为以下四类:估计方法、分类方法、推理方法和人工智能方法。

2.1估计方法

加权平均法是最简单、最直观融合多传感器低层数据的方法,该方法将由一组传感器提供的冗余信息进行加权平均,并将加权平均值作为信息融合值;利用最小二乘法原理可导出的数据平滑程序在许多情况下能够去除或减少测量过程中由于偶然因素带来的误差,使平滑后的数据一般会比原数据更有规律性;卡尔曼滤波用于实时融合动态的低层次冗余多传感器数据,该方法用测量模型的统计特性递推决定在统计意义下是最优的融合数据估计。

2.2分类方法

分类方法主要有参数模板法和聚类分析。无监督或自组织学习算法诸如学习向量量化法(learningvec-torquantization,lvq),k—均值聚类(k—meansclus-tering),kohonen特性图(kohonenfuturemap)也常用作多传感器数据的分类。k—均值聚类算法是最常用的无监督学习算法之一,而自适应k—均值方法的更新规则成了kohonen特性图的基础。此外自适应共振理论(art)、自适应共振理论映射(artmap)和模糊自适应共振理论网络(fuzzy—artnetwork)以自适应的方法进行传感器融合。它们能够自动调整权值并且能在环境变化和输入漂移的情况下保持稳定。

2.3推理方法

贝叶斯估计是融合静态环境中多传感器低层信息的一种常用方法.其信息描述为概率分布,适用于具有可加高斯噪声的不确定性;d—s是基于证据理论的一种推理算法,是贝叶斯方法的扩展。该算法解决了概率中的两个困难问题:一是能够对“未知”给出显式表示;二是当证据对一个假设部分支持时,该证据对假设否定的支持也能用明确的值表示出来。

2.4人工智能

人工智能方法对融合大量的传感器信息,用以非线性和不确定的场合颇有优势。可分为专家系统、神经网络和模糊逻辑。专家系统是一种基于人工智能的计算机信息系统。神经网络是一个具有高度非线性的超大规模连续时间自适应信息处理系统。模糊逻辑是多值逻辑,它允许将传感器信息融合过程中的不确定性直接表示在推理过程中。模糊集理论的基本思想是把普通集合中绝对隶属关系灵活化,使元素对集合的隶属度从原来只能取{0,1}中的值扩充到[0,1]区间中的任一数值,因此很适合于对传感器信息不确定性进行描述和处理。模糊集表达了一个不确定概念,应用模糊理论并结合其它手段与算法,如神经网络、遗传算法等,可以取得更好的融合结果。

3车速监控方法

3.1简介遗传算法

按照达尔文的进化论中的适者生存理论,计算科学学者提出了进化算法。进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索方法。

从整体上来讲,遗传算法是进化算法中产生最早、影响最大、应用也比较广泛的一个研究方向和领域,它不仅包含了进化算法的基本形式和全部优点,同时还具有若干独特性能,其优点主要有以下几个方面:

1)遗传算法的搜索过程是从一群初始点开始搜索,而不是从单一的初始点开始搜索,这种机制意味着搜索过程可以有效地跳过局部极值点。

2)遗传算法具有显著地隐式并行性(implicitpar-allelism),其进化算法虽然在每一代只对有限解个体进行操作,但处理的信息量为群体规模的高次方。

3)遗传算法形式上简单明了,便于和其他方法结合。

4)遗传算法具有很强的鲁棒性(robustness),即在存在噪声的情况下,对同一问题的遗传算法的多次求解中得到的结果是相似的。

3.2遗传算法对采集速度值融合

列车速度可由车轮上的传感器采集的转速求得,但是所测速度会有一定误差,这时我们可以以短时间内采集速度作为初始代群体开始应用遗传算法进行信息优化,其过程如下例:

取4个速度值(s/m):8,13,19,24。

取适应值函数f(x)=x3 (f(x)=x3与f(x)=x有相同的递加递减关系)。

以赌方式进行个体优胜劣汰的选择。

接着,我们按照遗传策略运用选择、交叉(变异概率pm很小,一般在0.005～0.01,设pm=0.01,则每代有4*5*0.01=0.2个变异,即认为在一代内不发生变异), 用以形成下一代群体;如表2:

由上表可见,随着一代的遗传操作,群体的平均适应度提高了,当前群体最佳个体也得到了改善。随着迭代次数的增加,群体将逐渐进化到该问题的最优解。

3.3模糊控制

首先设列车监控速度的模糊语言集合如下:

{快,稍快,适中,稍慢,慢}

设定其相应的语言变量,记作:

f(fast)=快

lf(littlefast)=稍快

e(equal)=适中

ls(littleslowly)=稍慢

s(slowly)=慢

其相应隶属度函数如下图2所示,其横坐标标示速度快慢,纵坐标为隶属度。为了计算简单,提高运算速度,采用了线性函数。

以d表示速度状态,u表示输出,p表示加速,lp稍加速,f表示保持目前状态,ln表示稍减速,n表示减速根据模糊关系制定相应模糊规则如表3:

4结束语

本文对日益发展的城市轨道交通提出了一种遗传算法与模糊逻辑相结合的监控方法,形式上简单明了,应用中可有效简捷地实现人的控制策略与经验,且模糊控制中不需被控对象的数学模型即可较好控制。

参考文献: