遗传算法的应用

徐文锋

遗传算法起源于上个世纪60年代，是一类模拟生物进化的智能优化算法，遗传算法是通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。算法从一组随机产生的初始群体开始搜索过程，以适应度函数为依据，采用基于适应值比例的选择策略在当前种群中选择个体，通过杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。目前，遗传算法已成为进化计算研究的一个重要分支。

一、遗传算法的原理

遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算法。在解决具体问题时先大致确定问题的潜在解的一个集合，这个集合就是算法的初始种群。种群由计算机生成（一般是随机生成）的一定数目的个体组成，个体就是潜在解的计算机编码，那么我们最后要求的解就由这些初始生成的个体进化而来。每个个体具有其自的特征（携带不同基因），我们根据这些个体的不同的特征来确定其存活到下一代的可能性高低，按照优胜劣汰的法则，我们由父代来产生子代，如此来繁衍。

当然在具体的进化过程中为了保持种群多样性防止过早收敛，还要在其中使个体以一定小概率发生变异。这样在最后满足收敛条件后的种群最优个体就是问题的近似最优解。遗传算法的实现过程主要包括编码、产生群体、计算适应度、复制、交换、变异等操作。

二、遗传算法的应用

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。所以，广泛应用于很多学科。下面是目前遗传算法的主要应用领域：

1、函数优化

工程上经常会遇到在多准则或多设计目标下设计和决策的问题，如果这些目标是相背的，需要找到满足这些目标的最佳设计方案。通常的做法是根据某有效函数将多目标合成单一目标来进行优化。

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

2、组合优化

组合优化是指在给定约束条件下，求解目标函数的最优值。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大。有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其最佳求解上，而遗传算法是寻求这种解的最佳工具之一。现如今，遗传算法已经在旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具问题中得到成功的应用。

3、生产调度问题

生产调度问题在很多情况下建立起来的数学模难以精确求解，即使经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差甚远。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效下具。在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

4、自动控制

许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求时，一般存在许多常规方法难以凑效的困难。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。都显出了遗传算法在这此领域中应用的可能性。

5、机器人学

机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。

6、图像处理

图像处理和模式识别是计算机视觉中的一个重要领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。目前遗传算法已经在图像校准、图像分割、几何形状识别、图像压缩、三维重建优化以及图像检索、模式识别（包括汉字识别）、图像恢复、图像边缘特征提取等方而得到了很好的应用。

7、人工生命

人工生命是用计算机、机械等人下媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的下具，人工生命的研究也必将促进遗传算法的进一步发展。基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力。

8、机器学习

学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。

9、数据挖掘

数据挖掘是从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。

除此之外，随着对遗传算法的进一步研究和发展，遗传算法将在更多的领域发挥其作用。现在遗传算法还分别在经济学、免疫系统、生态学、进化现象和学习现象、社会经济问题等方面都有所应用。

参考文献

1、钱志勤、腾弘飞，孙治国。人机交互的遗传算法机器在约束布局优化中的应用.计算机学报，2001

2、马玉明，贺爱玲，李爱民. 遗传算法的理论研究综述. 山东轻工业学院学报， 2004，18（3）：77～80

3、吉根林. 遗传算法研究综述. 计算机应用与软件， 2004，21（2）：69～73

4、马光文，王黎.遗传算法在水电站优化调度中的应用.水科学进展，1997，8

5、姚文俊. 遗传算法及其研究进展. 计算机与数字工程， 2004，32（4）：41～43

6、高艳霞，刘峰，王道洪. 改进型遗传算法及其应用研究. 上海大学学报， 2004（10）：249～253

7、马立肖，王江晴. 遗传算法在组合优化问题中的应用. 计算机工程与科学， 2005，27（7）：72～73、82