张国民

（浙江海洋学院 数理与信息学院，浙江 舟山 316000）

0 引言

遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。是由美国Michi遗传算法n大学的John Holland教授创建的，并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and artificial Systems》。它提出的基础是达尔文的进化论、魏慈曼的物种选择学说和孟德尔的群体遗传学说：其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。遗传算法以其具有并行搜索、简单通用、鲁棒性强等优点，受到国内外学者的关注。自1985年以来，国际上已召开了多次遗传算法学术会议和研讨会，并组织了国际遗传算法学会。

1 遗传算法的基本原理

在自然界中，由于同一个生物群体中各个体之间也存在差异，且对所处环境有的适应和生存能力也参差不齐，遵照进化论所提出的自然界生物进化的基本原则：适者生存、优胜劣汰，自然界将淘汰那些适应能力较差的个体。但是通过交配继承了父本优秀的染色体和遗传基因的，或者通过染色体核基因的重新组合产生的生物的生命力往往会更强，适应能力也更强。在自然界中，基因会发生突变，染色体核基因的重组是无法控制的，但这种无法控制的，小概率的变异，也可能产生新基因和生命力更强的新个体。在此基础上，遗传算法真实的模拟自然界生物进化机制进行对问题的最优化搜索。遗传算法是建立在自然选择和种群遗传学基础上的随机迭代和进化，具有广泛适用性的搜索方法，同时具有很强的全局优化搜索能力。对于某个给定的优化问题，目标函数为：

要求（X0，Y0，Z0）使得 H为极大值和极小值，以适应优化的需要。此外，Ω 是（X，Y，Z……）的定义域，H 为实数，f为解空间（X，Y，Z……）∈Ω到实数域H∈R的一种映射。遗传算法要根据目标函数H设定一个适应性函数f，用以判断某个样本的优劣程度。遗传算法的基本步骤如下：

（1）编码：定义问题的解空间到染色体编码空间的映射，一般是用二进制将解空间编码成由0和1组成的有限长度字符串。一般一个候选解（个体）用一串符号表示。

（2）初始化种群：在一定的限制条件下初始化种群，该种群的解空间的一个子空间。算法将从初始化种群开始模拟优胜劣汰的选择过程，最后选择出优秀的群体和个体。

（3）设计适应度函数：将种群中的每一个染色体解码成适于计算机适应度函数的形式，并计算其数值。设计适应度函数的主要方法是将问题的目标函数转换成合适的适应度函数。

（4）选择：根据适应度大小选择优秀个体繁殖下一代，适应度越高，则被选中的概率也越大。选择是遗传算法的关键，它体现了自然界中适者生存的思想。

（5）交叉：随机选择两个用于繁殖下一代的个体的相同位置，在选中的位置进行交换。

（6）变异：对某个串中的某一位进行取反操作。变异模拟了自然界中偶然基因突变现象。

从步骤四开始重复进行，知道满足某一性能指标或者规定的遗传代数。

步骤1、2和3是实际应用中关键，步骤4、5和6进行三种基本基因操作。对新生成一代群体进行重复评价、选择、交叉和变异，如此循环往复，使得群体中最优个体的适应度和群体的平均适应度不断提高，直到最优个体的适应度达到某个界限或者最优个体的适应度和平均适应度不能再提高。

图1 遗传算法的运行过程示意图

2 遗传算法的特点

遗传算法继承了进化计算的特征之外，也有其自身的特点：

（1）遗传算法不是直接作用在参数变量集上，而是在求解问题的决定因素和控制参数的编码(即染色体的0、1编码)上进行操作，从中找到适应值较高的子串。而且遗传算法不受约束条件的限制。

（2）遗传算法并不是从单个点出发执行算法，而是从一个点的群体开始，这样就可以提高算法的效率和程序的运行速率，也大大减少了陷入局部最优解的可能性。

（3）遗传算法利用了适应值的信息，适应值是根据不同问题设计所得，针对的是这个问题，从而减少了其他辅助信息的导入，即只需要对象函数和编码串。因此，遗传算法几乎可以处理任何问题。

（4）遗传算法利用概率转移规则，而不是确定性的规定。遗传算法采用的概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动。

（5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。

（6）遗传算法采用自然进化机制来表现现实复杂的现象，能够快速可靠地解决非常困难的问题。

（7）遗传算法具有固有的并行性，具有并行计算的能力。

（8）遗传算法具有可扩展性，易于同别的技术混合、结合使用。

3 遗传算法的应用

遗传算法是多学科结合与渗透的产物，已经发展成为一种自组织、自适应的综合技术。其提供了一种解决复杂系统优化问题的通用框架，但不是没用固定的方法，它不依赖于问题的具体领域，所以广泛应用于很多学科。

3.1 函数优化

函数优化是遗传算法的一个经典应用领域，也是对遗传算法进行性能评价的常用算例。很多学者构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何性质各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。

3.2 组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧扩大。有时在现有的的计机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，学者们已意识到应把主要精力放在寻求其满意解上，二不是一定要寻找精确的最优解，而遗传算法是寻求这种满意解的最佳工具之一。有实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形有划分问题等各种具有NP难度的问题上得到成功应用。

3.3 生产调度问题

在许多情况下所建立起来的数学模型难以精确求解，即使经过了一些简化之后可以进行求解，也会因为简化太多而使得求解结果与实际相差甚远。因此，目前在解决生产中的调度问题时还是主要依靠一些经验。1985年Davis首次将遗传算法引入到调度问题。从此在调度问题的解决过程中，遗传算法使得调度的总流程时间，平均流程时间等大大降低，提高了生产的效率。

3.4 图像处理

图像处理是计算机视觉中的一个重要的研究领域，其前景十分乐观。但在图像处理的扫描、特征提取、图像分割等过程中不可避免的会产生误差。而遗传算法则可以很好的解决这些问题。在图像分割的时候可以利用遗传算法来发现最优解从而帮助确定分割阈值；利用遗传算法在图像增强过程中寻找控制参数的最优解或者是近似最优解；利用遗传算法对图像进行特征提取再对所提取的特征进行优化，从而提高图像的识别率等。

3.5 自动化控制

随着现代技术和科学技术的不断发展，人工成本的不断提高，机器的自动化要求越来越高，工程师所要考虑的是选择合适的控制结构，然后对其参数进行一定的优化使得满足特定的实际性能要求。遗传算法具有鲁棒性和广泛适用性的全局优化方法，能更好的为其控制器降价，更好的控制机器人手臂，优化机器人手臂的运动轨迹。遗传算法的优化功能在越来越多的机器自动化领域得到关注。

4 遗传算法存在的问题

随着学科技术的迅速发展，遗传算法也应用到更多的领域。由于遗传算法来源于进化论和群体遗传学，缺乏严格的数学基础，收敛性证明比较困难，虽然可以利用马尔科夫链的性质证明在保留最优值情况下，遗传算法可以收敛到全局最优解，但是对其收敛速率估计是当前需要深入研究和讨论的问题。因为它能从理论上对遗传算法的任何修正形式提供评判标准，指明改进算法性能的正确方向。另外，利用马尔科夫链分析对遗传算法的具体应用和参数设计所提供的指导信息非常少。如何选择遗传算法的参数，才能得到最优结果，到目前还没有理论指导。以上这两个方面还需要需找更有效的分析手段和严格的数学证明。

5 结束语

遗传算法不是一种单纯的优化算法，而是一种以进化思想为基础的全新的一般方法论，是一种解决问题的方法。经过多年的研究和发展，遗传算法在越来越多的领域展现出它的优势，不论是基础理论研究、算法设计还是实际应用。应用研究是遗传算法的主要方向，开发遗传算法的商业软件、开拓更广泛的遗传算法应用领域是今后应用研究的主要任务。

［1］Holland J.H.Adaptation in Natural and Artificial Systems[M].Ann Arbor：University of Michigan Press,1975.

［2］边霞,米良.遗传算法理论及其应用研究进展[J].计算机应用研究,2010，27（7）.

［3］王东生.遗传算法及其应用[M].人民邮电出版社，1996.

［4］周国华.遗传算法及其在生产调度中的应用[J].西南交通大学学报：社会科学版，2000,1（2）.

［5］田莹,苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报,2007,12(3).

［6］马岚，张燕东.多目标遗传算法及其在自动控制系统设计中的应用[J].系统工程与电子技术，1997.