摘要

说明遗传算法的原理和应用，描述遗传算法当前的研究现状，分析遗传算法当前的发展潜力和不足。针对未来研究生学习的需要，从相关专业的角度对其进行总结。

关键字：遗传算法；研究现状；发展

Absrtact

explaintheprincipleandapplicationofgeneticalgorithm,describethecurrentresearchstatusofgeneticalgorithm,andanalyzethecurrentdevelopmentpotentialandshortageofgeneticalgorithm.Accordingtotheneedsoffuturepostgraduatestudy,thispapersummarizesitfromtheperspectiveofrelevantmajors.

Keywords:geneticalgorithm;researchstatus;summary

引言

计算机专业的学习过程中，算法的学习不可或缺。算法，简而言之，就是解决问题的步骤。遗传算法是当前启发式算法的重要算法，对遗传算法的了解和掌握，对以后的研究生生活具有十分重要的意义。

1遗传算法

1.1遗传算法的基本原理

遗传算法起源于上世纪60年代中期，JohnHolland提出的位串编码技术。遗传算法（GeneticAlgorithm,GA），也成为进化算法，是年根据达尔文的自然选择和遗传学的生物进化抽象出来的一种启发式算法。其产生的最初目的是为了应对经典数学方法无法有效解决的大型复杂的最优化问题。简单描述思想：在一个随机的初始化集合中，根据个体的适应度大小选择个体，再通过遗传学的交叉和变异，产生一个比之前更优的集合，同时也相对更接近全局最优解。

1.2遗传算法的组成部分

遗传算法如下图1.1包含五个要素，分别是参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定。这里借鉴李岩的《遗传算法在优化问题中的应用综述》[1]，可以把遗传算法分为如下组成部分：

（1）参数编码。根据我们需要解决的实际问题，遗传算法通过编码的形式，把问题的可行解决方案转化为遗传算法的搜索空间。常用的编码方法有格雷码、二进制编码、浮点数编码、符号编码、多参数编码。遗传算法常用的编码形式是二进制编码。实际情况的应用中，格雷码的误差小于二进制编码。

（2）适应度函数的设定。适应度函数，是对群体集合内的个体与环境适应性之间的对应关系描述，所以它的设定，需要有效反应出个体之间和最优解之间的差距。

（3）遗传操作设定。基本的遗传操作包括:选择、交叉、变异。

A)选择。模拟“优胜劣汰”，适应度的高低直接影响到某一个体是否有机会遗传下一代的概率。常用的算法有：轮盘赌选择法，基于排名的适应度分配方法。

B)交叉。交叉操作是遗传算法的核心，直接关系到下一代的个体质量，决定了遗传算法的全局搜索能力。用数组的方法来描述：两个都是没有重复数的1到10的数的数组，把它们的某个同一位置的数互换，产生两个新的、依然没有重复数的1到10的数的数组。常用的算法是：实质重组，中间重组，离散重组，线性重组，二进制交叉，单点交叉，均匀交叉，多点交叉和减少代理交叉。

C)变异。两个个体之间发生等位基因的替换，从而形成新的个体。变异是辅助交叉产生新的个体的主要方法。这是遵循遗传规律的表现。主要的算法有：单点交叉，

均匀交叉，算术交叉，两点交叉和多点交叉。

（4）算法终止。算法的实现，需要不断的循环演化，而我们的目标是得到最优解，所以我们需要指定一个代数。当适应度函数的值不断收敛于这个代数时，终止进化。

1.1图

1.3遗传算法的应用

遗传算法在求解具体问题时，有并发性和全局性两个特点，不依赖于梯度信息或其他辅助知识，提供了一个通用的求解框架，具有很强的鲁棒性和应用性。遗传算法的主要研究领域是：遗传算法的理论与技术；用遗传算法进行优化；用遗传算法进行分类系统的机器学习。目前主要的应用领域如1.2图（该图来至冯智莉的《并行化遗传算法研究综述》[4]）有函数优化、生产调度问题、自动控制、机器学习、图像处理、人工生命、遗传编程，机器学习、数据挖掘等等。

1.2图

从1.2图，我们可以知道遗传算法还是数据挖掘领域和机器学习领域的研究重点。

2研究现状

遗传算法在编码表示、适应度函数、选择策略、控制参数和遗传算子等方面已经有大量的文献进行了综述，这里我侧重于这几年的综合方面。

[2]提出了基于遗传算法的动态聚类算法，同年文献[3]在参考文献[3]的基础上，展开了动态遗传算法在大数据上聚类分析中的应用。文献[5]提出了一些具有多极值和最优点的函数，让背包问题、布局优化和旅行商问题的求解空间大大上升。文献[6-7，9]在此基础上，在求解旅行商问题上成功地运用了遗传算法，文献[10]采用遗传算法优化航天航空控制系统，文献[11]同样采用遗传算法对模糊控制器进行了优化。

在机器人方面，也得到了广泛的应用。文献[12]在机器人移动路径上采用了遗传算法，通过遗传算法优化了图像处理过程中的误差。文献[13]在汉字识别上运用了遗传算法，同样文献[14-15]在图像恢复和图像边缘特征提取上运用了遗传算法。

在机器学习方面，遗传算法通过学习模糊控制规则，优化了模糊系统的功能。文献[16-17]通过遗传算法调整CNN的连接权，从而优化CNN，

数据挖掘方面，把数据挖掘问题转化成寻找最优解的问题，数据库就是搜索空间，遗传算法为此随机分配一组规则，终止条件是不断进化的规则可以全面覆盖数据库。文献[18-20]已经基于遗传算法的思想，开发出数据挖掘工具，并且在失事飞机的数据上展开了检验，结果很有效。

3发展潜力和不足

遗传算法，目前在很多优化问题上，都有成功的应用，但是也暴露出一些不足，比如：遗传算法侧重于全局搜索，局部搜索能力就比较差；在生物多样性的情况下，会出现一定的收敛误差等。这些不足就非常耗费时间。遗传算法是未来研究的重点算法，目前各国学者一直在致力于解决这些问题。

遗传算法，在寻找最优解的过程中，有一个重要特点：始终保持整个种群的进化。所以遗传算法不需要保持连续可微，在解决实际问题时，有很强的适应性。遗传算法，作为生物进化思想在工程计算中的一种体现，它的前途是光明可见的。

文献[2]中指出了遗传算法的发展方向，

（1）基于自身的不断优化，主要有两种方法，第一种对初始化种群的控制，避免因为物种多样性的不可控所产生的误差；第二种是控制遗传操作，尤其是控制交叉和变异的方法，使得变异的操作次数明显降低，从而提升效率。

（2）遗传算法与其他计算智能方法的相互渗透和结合。目前遗传算法和神经网络、模糊推理以及混沌理论等智能算法日益相互渗透、结合，取长补短，这使得遗传算法的实用性更强。

（3）并行处理的遗传算法。遗传算法具有并行性，改进并行遗传算法，主要有两个方面：一种是粗粒度并行遗传算法，另一种是细粒度并行遗传算法。分别从个体个体适应度评价的并行性、整个群体中各个个体的适应度评价的并行性、群体产生过程的并行性和基于群体分组的并行性这四个方面改进。

（4）遗传算法与人工生命的相互渗透。人工生命是通过人工的手段模拟和构造出的具有自然生命特有行为的人造系统。遗传算法的思想是研究人工生命现象的十分重要的理论基础。人工生命的发展必然会推动遗传算法的发展。

（5）遗传算法与进化规则及进化策略的结合。遗传算法、进化规则及进化策略是演化计算的三个主要分支，分别从不同的角度去模拟生物进化过程。目前这几种进化算法在实际操作中日益紧密，共同推动生物进化机制的发展。

4专业总结

遗传算法涉及的领域很广，虽然存在一些问题，但是随着世界各国对它不断改进，它的未来是光明的。

中南财经政法大学的电子信息专业，主要是信息系统工程、数据挖掘工程和大数据工程这3个专业培养方向。从长远上来看，学习算法是比不可少的。今年恰逢席卷全国的新型冠状病毒，党和国家在领导人民抗击疫情的同时，也积极号召相关单位采用大数据、人工智能和云计算等先进技术来分析疫情，治疗疾病。在年3月7日晚，清华大学李国栋教授就大数据视野下的新型冠状病毒分析展开讲座，通过大量的数据生动的描绘了整个疫情的发展过程。

随着各行各业不断推倒数据壁垒，在未来数据将会越来越多，这为大数据、数据挖掘的更加繁荣提供了可能。通过大数据和数据挖掘，人们不断发现新的生命规律，这为未来治疗疾病时，开始针对基因治疗提供可能。遗传算法是大数据和数据挖掘的重要算法思想，学习遗传算法，也将会大大方便未来研究生的科研实践之旅。

尾部附上一段通过遗传算法把正整数转化为二进制数据串的代码。

#includestdio.h

#includestdlib.h

#includetime.h

#defineamount10//每代个体数

#definelength5//个体长度

#definemaxtime//最多运行次数

intf(intx){

returnx;

}

intmain(){

srand(time(NULL));

intarr[amount][length],number[amount],temp[amount][length];

intcount=0,refer,maxfit=0,maxrecord,temp1,count2=0,count3,nowmaxfit=0,last;

for(inti=0;iamount;i++){

for(intj=0;j=length;j++){

temp[i][j]=0;

arr[i][j]=rand()%2;

if(arr[i][j]!=0arr[i][j]!=1)arr[i][j]=1;

}

}//初始化内存

while(count=maxtime){

count++;//执行一次

intsumfit=0;//总适应度

for(inti=0;iamount;i++)number[i]=0;

nowmaxfit=0;

for(intk=length-1;k=0;k--){

number[i]=number[i]*2+arr[i][k];

}

}//将二进制转换为十进制

number[i]=f(number[i]);

sumfit+=number[i];

//maxfit=maxfitnumber[i]?maxfit:number[i];

if(maxfitnumber[i]){

maxfit=number[i];

//maxrecord=i;

if(nowmaxfitnumber[i]){

nowmaxfit=number[i];

maxrecord=i;

}//计算对应适应度

refer=rand()%sumfit+1;

if(refersumfit

refer0)refer=sumfit;

for(intk=0;k=amount;k++){

if(refer0){

for(intj=0;jlength;j++){

temp[i][j]=arr[k-1][j];//temp[i]=arr[k-1]

}

break;

else{

refer-=number[k];

}//物竞天择

for(intj=0;jlength;j++)

arr[i][j]=temp[i][j];

//arr[i]=temp[i];

for(inti=0;iamount;i+=2){

refer=rand()%length;

if(refer=length

refer0)refer=length-1;

for(intk=refer+1;klength;k++){

temp1=arr[i][k];

arr[i][k]=arr[i+1][k];

arr[i+1][k]=temp1;

}//基因重组

if(nowmaxfit==maxfit){

count2++;

elsecount2=0;

if(count2=20){

printf(\n\n\nFinished,maxis%d,maxfit);

if(nowmaxfit==last){

count3++;

elsecount3=0;

last=nowmaxfit;

if(count3=10){

arr[rand()%amount][rand()%(length+1)]=rand()%2;

}//突变

printf(\n\nthisisthe%dtime,themaxfitis%d,nowmaxfit=%d\n,count,maxfit,nowmaxfit);

printf(Menbersare:\n);

for(intj=0;jlength;j++){

printf(%d,arr[i][j]);

//if(arr[i][j]!=0arr[i][j]!=1)arr[i][j]=1;

printf(\n);}

return0;

5参考文献

[1]李岩，袁弘宇，于佳乔，张更伟，刘克平.遗传算法在优化问题中的应用综述[A]DOI:10.-0/j.cnki.37-/t..12.

[2]戴晓晖,李敏强，寇纪淞.基于遗传算法的动态聚类算法[J].DOI:10./j.cnki.cn13-/tq..08.

[3]向丽，戴晓晖.动态遗传算法在大数据聚类分析中的应用[J]DOI:10./j.cnki.cnl3-/tq..08.

[4]冯智莉，易国洪，李普山，黎慧源，代瑜.并行化遗传算法研究综述[A]DOI:10./j.issn.一86x..11.

[5]孙如祥，黄春，邓国斌高维多峰优化的遗传算法设计[J].科技通报，,33(8):一,

[5]李和壁.遗传算法(GA)在旅行商问题(TSP)中的应用[J]科技创新与应用，5(10):48一49

[6]WangJ，Ersoy0K，HeM，etal.Multi}ffspringgenetic;al-gorithmanditsapplicationtothetravelingsalesmanproblem[J].AppliedSoftComputing,6，43(C):一

[7]LvH.AnovelQuantumGenetic;AlgorithminTSP[J].Ap-pliedMechanic、Materials，4，/:一

[8]赵宜鹏，孟磊，彭承靖.遗传算法原理与发展方向综述[J]0，05，05

[9]陈守家，付霞，周欣基于遗传禁忌算法结合解决排课问题[J]计算机应用，,27(7):一

[10]李素粉，朱云龙流水车间作业提前/拖期调度问题研究[J]计算机集成制造系统，,12(8):一

[11]饶运清，严治雄，张超勇，等一种混合遗传算法在车间作业调度中的应用研究[J]机械科学与技术，,25(5):一

[12]虞蕾，赵红，赵宗涛一种基于遗传算法的航迹优化方法[J]西北大学学报(自然科学版)，,36(2):一

[13]李辉，韩红，韩崇昭，等基于遗传算法的模糊逻辑控制器优化设计[J]西安交通大学学报，,36(4):一

[14]王科俊，徐晶，王磊，等基于可拓遗传算法的机器人路径规划[J]哈尔滨工业大学学报，,38(7):一

[15]林磊，王晓龙，刘家锋基于遗传算法的手写体汉字识别系统优化方法的研究[J]计算机研究与发展，2,38(6):一

[16]赵应丁，刘金刚基于遗传算法的指纹图像二值化算法研究[J]计算机工程，，32(7):一

[17]王建锋，吴庆标分层遗传算法实现图像边缘检测[J]计算机工程与应用，,42(14):95一96

[18]王静莲，刘弘，李少辉基于决策树的遗传算法在数据挖掘领域的应用[J]计算机工程与应用，,41(28):一

[19]张细政，邢立宁，伍栖基于遗传算法的数据挖掘方法及应用[J]哈尔滨工程大学学报，,24(Sl):一3RR.

[20]ChoenniS.Designandimplementationofagenetic;basedal-gorithmfordatamining[C]//VLDB，Proceedingsof,InternationalConferenceonVeryLargeDataBases，Septem-her10一14，，Cairo，Egypt.DBLP，:33一42