遗传算法在优化问题中的应用综述

李岩 袁弘宇 于佳乔 张更伟 刘克平

摘 要：根据遗传算法的特点和优化过程中存在的问题，指出遗传算法存在缺陷。針对遗传算法在优化问题中的研究现状，从编码技术的改进、自适应算子的引入、操作算子的改进、混沌理论的加入、多种群方式的改进、免疫学原理的引入和小生镜技术的结合等方面做出了总结，最后研究并探讨遗传算法仍需要克服的困难与待解决的问题。

关键词：遗传算法；优化；研究现状；遗传算法的组成；遗传算法结构

DOI：10.16640/j.cnki.37-1222/t.2019.12.210

1 引言

遗传算法（GA）是一种基于生物界规律和自然遗传机制的并行搜索算法。1975年，J. Holland教授首次在书中提出“自然组合人工智能系统的适应性”。它是一种多参数，多组合同时优化方法，模拟自然进化过程中“自然选择，适者生存”的原则。其主要特征是群体间的搜索方法以及群体中个体信息的交换。GA非常适合解决传统搜索方法难以解决的非线性问题。遗传算法也经常用于生产线优化问题。文献[3]在生产线运行优化问题中运用GA，并通过与模拟退火算法得到的结果进行对比，得到遗传算法具有更好的效果。文献[4]使用免疫遗传算法研究线平衡问题。文献[5]主要采用遗传算法研究第一类生产线的平衡问题，解决了第一类生产线的负荷平衡问题。文献[6]对作业元素分配给工作站的顺序进行编码，并根据最大分配原则对其进行解码。实践证明，遗传算法可以有效地解决U形生产线的平衡问题。文献[7]的主要特点是受“鳗鱼效应”启发设计了周期性自适应杂交算子和变异算子。实验结果表明，改进算法可以有效地改善局部收敛和早熟现象。文献[8]提出了一种改进的遗传算法，并结合实例给出了第二类生产平衡问题的解决方案。缩放适应度方法，即保持最佳适应度的值与平均适应度的值的比率是恒定的通用采样策略，以及线性可变交叉和变异算子。文献[9]通过利用遗传算法对生产线排列来达到平衡生产线的目的。文献[10]提出一种针对“序列组合”编码方式的遗传算法，这种编码方式，设计了相应的遗传操作算子，提高搜索的效率和解的质量。

2 应用背景

与其他启发式算法相比，遗传算法具有以下特征：

（1）遗传算法从多个初始点而不是单个初始点开始搜索，因此可以有效地跳出局部极值；

（2）利用目标函数的评价信息而不是传统导数的目标函数，形式对目标函数没有要求，因而有良好的适应性和可规模化；

（3）具有良好的寻找全局最优解的能力，能够在非连续，多峰和嘈杂的环境中以较大的概率收敛到全局最优或满意的解；

（4）将每个过程划分作为决策变量，优化生产过程，解决最优作业调度问题；

（5）具有天生的并行性，即在对群体进行运算的同时，对多个结果进行信息搜索；它具有一定的概率，这增加了其搜索最优解决过程的灵活性。

生产线平衡问题也是一个典型的寻优过程，为此，人们在寻找新算法的同时，GA凭借着自身的优势而不失为一种好的算法。

3 遗传算法

3.1 遗传算法的基本原理

与旧的搜索算法不同，GA从种群的初始解决方案开始其搜索过程。群体中的每个个体被称为染色体。在迭代过程中染色体的不断更新称为遗传。GA主要通过交叉、变异、选择算子来实现。染色体的优点和缺点通常通过适应性来评估。根据适合度值的大小，从父母和后代中选择一定比例的个体作为后代的群体，然后继续迭代计算直到它收敛到全局最佳染色体。适应度是遗传算法用来评价种群在进化的过程中所能达到的最优值的一个概念。为了证明染色体的适应性，引入了测量每条染色体的功能函数，称为适应度函数。

3.2 遗传算法的组成

遗传算法的流程如图1所示。其主要组成部分包括：

（1）编码方式。遗传算法通常根据问题本身进行编码，并将问题的有效解决方案转化为遗传算法的搜索空间。工业中常用的编码方法包括实数编码，二进制编码，整数编码和数据结构编码。

（2）适应度函数。适应度函数，也称为目标函数，是对整个个体与其适应度之间的对应关系的描述。具有高适应性的个体中包含的高质量基因具有较高的传递给后代的概率，而具有低适应性的个体的遗传概率较低。

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

a）选择。选择操作基于个体适应度评估，选择群体中具有较高适应度的个体，并且消除具有较低适应度的个体。当然不同的选择操作也会带来不同的结果，有效的选择操作可以显著的提高搜索的效率和速度，减少无用的计算量。

常见的选择方法有：基于比例的适应度分配方法，期望值选择方法，基于排名的适应度分配方法，轮盘赌选择方法等。

b）交叉。在自然界生物进化过程中，两条染色体通过基因重组形成新的染色体，因此交叉操作是遗传算法的核心环节。交叉算子的设计需要根据具体的问题具体分析，编码操作和交叉操作互相辅助，交叉产生的新的个体必须满足染色体的编码规律。父代染色体的优良性状最大程度上的遗传给下一代染色体，在此期间也能能够产生一些较好的性状。

常见的交叉算子包括实质重组，中间重组，离散重组，线性重组，二进制交叉，单点交叉，均匀交叉，多点交叉和减少代理交叉。

c）变异。通过随机选择的方法改变染色体上的遗传基因。变异本身可以被视为随机算法，严格来说，是用于生成新个体的辅助算法。

几个与浮点数编码和二进制编码个体匹配的交叉运算：单点交叉，均匀交叉，算术交叉，两点交叉和多点交叉。

（4）算法终止条件。算法终止一般指适应度函数值的变化趋于稳定或者满足迭代终止的公式要求，也可以是迭代到指定代数后停止进化。

4 遗传算法的研究现状

（1）编码技术的改进。石飞等人[11]针对分区编码方法的不足，设计了一种改进的编码方式。该算法的编码方法基于组件的处理顺序和组件的组装关系。而且还设计了一种基于邻接矩阵的方法来修复不可行染色体，通过与分区编码的对比，最后证明了该算法的优越性。

杜轩等人[12]分析实际生产线组件分布问题的基础上，设计出矩阵编码的改进方式，并运用了两点交叉和改进的局部变异和自适应突变率方法用于变异操作。最后，通过工程实例解决了该问题，取得了良好的效果，提高了PCB装配线的效率，证明了算法的有效性。

林培光等人[13]将Grefenstette编码和2-opt优化算法结合到遗传算法中，并使用一定数量的城市坐标来解决路径搜索问题。提出的搜索空间路径方案实现了遗传算法能够快速收敛到最优解，保持强大的搜索能力，实现全局优化，防止陷入局部优化。

（2）操作算子的改进。朱佳栋等人[14]针对传统的遗传算法不能很好地解决现残存的问题，对其进行了优化。本文对变异个体和操作算子的设计进行了改进，并应用于多功能液压千斤顶的配置设计。改进的交互式算法可以在进化阶段将个体划分为不同的遗传单元，并为多用户协同配置设计具有相似偏好的用户。它可以更好地减少用户疲劳，并快速、轻松地获得用户需求。

李敬花等人[15]提出基于改进遗传算法的舾装件托盘拣选的智能化方法。通过建立以总延迟时间为优化目标的数学模型，设计了一种改进的遗传算法求解模型。使用基于托盘的单层整数编码方法，建议用每条染色体来表示不同的托盘排序。当种群陷入局部最优解，种群的多样性可以通过进化逆转操作和插入操作来实现，使种群能跳出局部最优解，并继续寻找全局最优解。

（3）自适应算子的引入。吴聪等人[16]提出了一种在进化的过程中，交叉概率自适应调整的交叉方法，变异概率自适应于调整的变异方法。进化代数和进化整个过程中没有改变个体的数量，从而提高了算法的局部搜索能力。引入自适应算子能有效抑制遗传算法的“早熟”，优化精度更高，使得到的优化结果更靠近全局最优。

刘帅等人[17]将自适应遗传算法应用到民航空中交通监视雷达部署方面的优化。该算法首先根据首要指标建立雷达部署的数学模型，如管制区域的覆盖范围和进近控制区域的双重覆盖。为了避免遗传算法的随机发散和局部收敛，采用可变交叉概率和变异概率。最后，实验结果表明，所需要的空域范围可以被自适应遗传算法快速收敛得到，并获得全局最优部署方案，提高雷达利用率并且增大空域覆盖率。

刘书明等人[18]针对解决水管网络的优化设计问题，选用了一种自适应遗传算法的应对方案。根据管段的流速和直径，可以自适应地调整遗传算法中下一代个体的直径选择，以提高演化效率。优化结果表明，与传统遗传算法相比，自适应遗传算法具有更高的收敛速度和优化效率。

（4）免疫学原理的引入。黄硕果等人[19]提出了一种解决模糊柔性作业车间调度的免疫遗传算法。算法中染色体采用实数编码，并采用自适应提取疫苗操作来进行浓度抑制，提出了新型的采用模拟退火的疫苗接种操作。这种算法可以有效地降低早熟及过早收敛的情况，并添加记忆库来弥补传统交叉变异的不灵活性。

赵韩等人[20]通过该算法自适应调整遗传过程中的遗传参数来提高算法的稳定性和效率。作者将改进的免疫遗传算法应用于作业车间调度问题，并验证了其有效性。

杨峰等人[21]将免疫学原理引入遗传算法，并提出一种新的编码方式来编码巡回路线，来实现抗体浓度群体的更新和多样性策略的保持，在物流路径规划的问题上实现了显著的改善。

（5）混沌理论的引进。张浩为等人[22]提出了将混沌理论与遗传算法相结合的优化算法。初始种群通過混沌理论进行优化，使用精英预留和混合排序选择策略，设计自适应交叉算子、自适应变异算子来提高改进算法的搜索性能。最后，验证了该算法的优化效果更好。

王华等人[23]把混沌理论的优点和遗传算法的优势相结合。运用该算法对已知模型进行仿真。相比之下，新算法比传统遗传算法具有更少的延迟，并且可以提高搜索结果的效率。

（6）多种群方式的改进算法。李锋等人[24]提出了一种有效解决装配线平衡问题的多种群遗传算法。采用多种群遗传算法对固定工位下装配线的优化目标进行求解，在子种群进化的阶段该算法保证了种群的多样性，优秀种群之间通过优秀个体的相互交流也保证了解的收敛速度，防止种群出现退化现象。提升了种群的多样性和遗传算法的全局搜索能力。

王军等人[25]提出了一种改进的双种群遗传算法。作者将顶点图像法、适应度函数、适应度函数增量法引入遗传算法，同时基于多种群的进化过程，将初始种群分为俩个种群，一个种群是全局种群，其主要目的是找到可能存在最优值的区域。另一个种群是局部种群，主要任务是仔细搜索全局种群划分的区域，找到最优解。

（7）小生境遗传算法。雷磊等人[26]找到了一种以实数编码为基础的小生境遗传算法。并将其用于雷达干扰资源的调度。小生境遗传算法将小生境技术引入遗传算法的原始结构，不影响遗传算法的原始特征。此外，保持了种群的多样性，并且改善了遗传算法处理多峰优化问题的能力。

李振等人[27]提出了一种采用适应函数共享的小生境技术结合遗传算法计算种群个体适应度。该算法在遗传算法的基础上借鉴了小生境技术，引入适应度共享函数作为评价标准，提高了整体的搜索效率避免陷入局部最优解，可以看出，小生境遗传算法优于传统的遗传算法。

5 遗传算法在寻优过程中存在的问题

通过不断的实验总结发现，遗传算法在迭代寻优的过程中容易出现以下需要解决的问题：

（1）遗传算法是以一个不断迭代来寻找最优值的过程，但该算法对新空间的搜索能力是有限的，处理规模也很小，特别是在优化的后期阶段，搜索效率很低，很容易收敛到局部最优解；

（2）选择算子，交叉算子和变异算子的实现也需要很多参数，如交叉率和变异率。而且，这些参数的选择严重影响了解的质量；

（3）遗传算法对初始种群有很强的依赖性，直接影响解的收敛性和优化结果的质量；

（4）根据一般情况，遗传算法迭代次数越多，算法的收敛性越好。然而，在增加遗传迭代次数的同时，算法的计算工作量增加，这消耗了大量的计算时间。

6 总结

遗传算法是近几年比较热的话题，相对于优化问题遗传算法凭借自身优势广泛应用于数据挖掘、自动控制，生产调度，自动控制，图像处理，组合优化等领域。但根据现在的研究和发展来看，遗传算法在优化的问题上还存在很多的不足，主要问题是遗传算法的编码不能完全表达优化问题的约束。还有很多方面需要改善，如适应度函数是影响种群的一个重要因素，对于子代种群以及初始种群间的关系以及如何合理的选择适应度函数都是需要进一步探讨的问题。

近年来，由于人工智能的快速发展，遗传算法有了更广阔的发展平台。与其他的智能优化算法相比，遗传算法虽然经历的发展较长，但仍然存在着以下几方面的问题需要进一步的研究：

（1）遗传算法在编码规则性和编码表示方面存在不准确性；

（2）单个遗传算法编码不能完全表达优化问题的约束。考虑约束的优化方法是找到不可行解决方案的阈值，以便更好地控制计算时间；

（3）遗传算法的一般效率低于其他传统优化方法，容易过早收敛；

（4）遗传算法对算法的准确性，可行性和计算复杂度没有有效的定量分析方法；

（5）将算法与神经网络，小生境技术和混沌理论等优化方法相结合，开发出一种新的混合优化算法，揭示了一种新的智能平台。

参考文献：

[1]HOLLAND J H. Adaptation in natural and artificial system. An Arbor， MI，USA ：The University of Michigan Press，1975.

[2]刘环宇，夏吉庆等.基于遗传算法对A公司生产线平衡的分析[J]. 物流技术，2014（17）：367-370.

（下转第180页）

（上接第243页）

[3]梁承姬，陈维斗，崔佳诚.自动化集装箱码头双轨道吊协调调度分析[J].计算机应用与软件，2018，35（09）：17-21.

[4]安鑫.免疫遗传算法在中药制药车间调度的研究[D].昆明理工大学，2011.

[5]范维博，周俊，许正良.应用遗传算法解决第一类装配平衡问题[J].计算机技术与发展，2010（02）：P194-196.

[6]宋华明，韩玉启.基于遗传算法的U型生产线平衡[J].系统工程学报，2002（10）：424-429.

[7]陈晓峰，肖田园.应用遗传算法解决装配线平衡问题[J]. 计算机工程与应用，2001（23）：81-83.

[8]张瑞军，陈定方，杨琴.用改进的遗传算法解决ALB问题[J]. 计算机工程与设计，2006，27（20）：3731-3736.

[9]王红军，赵建辉.基于遗传的装配线平衡系统研究[J].计算机工程与应用，2008，44（10）：195-197.

[10]吴尔飞.双边装配线平衡技术研究[D].上海：上海交通大学博士学位论文，2009.

[11]石飞，赵诗奎.基于工序约束链编码的遗传算法求解产品综合调度问题[J].中国机械工程，2017，28（20）：2483-2492.

[12]杜轩，李登桥，朱康.基于矩阵编码遗传算法的PCB生产线元件分配优化[J].三峡大学学报（自然科学版），2015，37（01）：89-93.

[13]公冶小燕，林培光，任威隆.基于Grefenstette 编码和2-opt 优化的遗传算法 [J/OL].山东大学学报（工学版）.

[14]朱佳栋，苏少辉，陈昌，刘桂英.面向产品配置设计的改进交互式遗传算法[J].中国机械工程，2018，29（20）：2474-2478.

[15]李敬花，曹旺，赵定刚，蒋岩，周青骅.基于改进遗传算法的托盘拣选延误时间优化[J].计算机集成制造系统.

[16]吴聪，陈侃松，姚静.基于改进自适应遗传算法的物流配送路径优化研究[J].计算机测量与控制，2018（02）.

[17]刘帅，秦姗姗.基于自适应遗传算法的空管雷达部署优化[J]. 通信技术，2018（04）.

[18]刘书明，李婷婷，王晓婷，吴雪.自适应遗传算法在给水管网优化中的应用[J]. 给水排水，2017（04）：107-110.

[19]黄硕果.基于免疫遗传算法的模糊柔性作业车间调度问题研究[D].重庆交通大学，2017.

[20]赵韩，高先圣，姜康.基于免疫遗传算法的多目标柔性作业车间调度研究[J].系统仿真学报，2008（22）：6163-6168.

[21]杨峰，柳林，唐贤瑛等.基于免疫遗传算法的物流配送车辆路径优化问题研究[J]. 计算机应用与软件，2007，24（05）：50-51.

[22]张浩为，谢军伟，张昭建.基于混合自适应遗传算法的相控阵雷达任务调度[J].兵工学报，2017，38（09）：1761-1770.

[23]王华，蔡延光.基于混沌遗传算法的干线交叉口信号控制优化研究[J].电子世界，2014（18）：362-363.

[24]李锋，邢静忠，刘伟.基于多种群遗传算法的装配线平衡问题研究[J].四川理工学院学报（自然科学版），2015，28（02）：30-36.

[25]王军.基于改进双种群遗传算法的AUV路径规划方法研究[J]. 自动化技术与应用，2010，29（06）：13-16.

[26]雷磊，周青松，张剑云.基于小生境遗传算法的干扰资源调度研究[J].现代防御技术，2014，42（01）.

[27]李振，胡庆东，张国英.基于小生境遗传算法的人工拣货路径优化研究[J].物流科技，2011（06）：85-88.

基金項目：吉林省科技发展计划项目（20180201105G X）

通讯作者：李岩（1978-），男，吉林人，博士在读，副教授，主要研究方向：智能机械与机器人控制。