遗传算法研究综述

摘 要：通过介绍遗传算法的基本概念和基本原理，说明了遗传算法应用领域，指出了遗传算法在应用中的几个关键问题，并介绍了遗传算法研究新动向及存在的问题。

关键词：遗传算法；编码机制；遗传算子；适应度函数

1 遗传算法的基本原理

遗传算法类似于自然进化，通过作用于染色体上基因寻找最好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对遗传算法所产生的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合成下一代新的种群，对这个新种群进行下一轮进化。

2 遗传算法的应用

遗传算法在应用中最关键的问题有如下3 个。

（1）串的编码方式。本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

（2）适应函数的确定。适应函数（fitness function）也称对象函数（object function），这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

（3）遗传算法自身参数设定。遗传算法自身参数有3 个，即群体大小n、交叉概率Pc 和变异概率Pm。群体大小n 太小时难以求出最优解， 太大则增长收敛时间。一般n=30-160。交叉概率Pc 太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01-0.2。

遗传算法的主要应用领域在于函数优化（非线性、多模型、多目标等），机器人学（移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化等），控制（瓦斯管道控制、防避导弹控制、机器人控制等），规划（生产规划、并行机任务分配等），设计（VLSI 布局、通信网络设计、喷气发动机设计等），组合优化（TSP 问题、背包问题、图分划问题等），图像处理（模式识别、特征提取、图像恢复等），信号处理（滤波器设计等），人工生命（生命的遗传进化等）。

3 遗传算法的研究新动向

3.1 基于遗传算法的机器学习

这一新的研究方向把遗传算法从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能崭新的機器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。遗传算法作为一种搜索算法从一开始就与机器学习有着密切联系。分类器系统CS-1 是GA 的创立Holland 教授等实现的第一个基于遗传算法的机器学习系统。分类器系统在很多领域都得到了应用。例如，分类器系统在学习式多机器人路径规划系统中得到了成功应用；Goldberg 研究了用分类器系统来学习控制一个煤气管道仿真系统；Wilson 研究了一种用于协调可移动式视频摄像机的感知运动的分类器系统等。

3.2 遗传算法与其他计算智能方法的相互渗透和结合

遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，以达到取长补短的作用。近年来在这方面已经取得了不少研究成果，并形成了“计算智能”的研究领域， 这对开拓21 世纪中新的智能计算技术具有重要意义。GA 的出现使神经网络的训练（包括连接权系数的优化、网络空间结构的优化和网络的学习规划优化）有了一个崭新的面貌，目标函数既不要求连续，也不要求可微，仅要求该问题可计算，而且搜索始终遍及整个解空间，因此容易得到全局最优解。

3.3 并行处理的遗传算法

并行处理的遗传算法的研究不仅是遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。GA 在操作上具有高度的并行性，许多研究人员都在探索在并行机上高效执行GA 的策略。研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并GA 的研究方面，一些并GA 模型已经被人们在具体的并行机上执行了；并行GA 可分为两类：一类是粗粒度并行GA，主要开发群体间的并行性；另一类是细粒GA，主要开发一个群体中的并行性。

3.4 遗传算法与人工生命的渗透

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

3.5 遗传算法与进化规则及进化策略的结合

遗传算法、进化规则及进化策略是演化计算的3 个主要分支，这3 种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性；另一方面，这3 种算法又是从不完全相同的角度出发来模拟生物进化过程，分别是依据不同的生物进化背景、不同的生物进化机制而开发出来的，所以三者之间也有一些差异。随着各种进化计算方法之间相互交流深入，以及对各种进化算法机理研究的进展，要严格地区分它们既不可能、也没有必要。在进化计算领域内更重要的工作是生物进化机制，构造性能更加优良、适应面更加广泛的进化算法。

参考文献

[1]张文修，梁怡.遗传算法的教学基础[M].西安：西安交通大学出版社，2000.

[2]余建坤，张文彬，陆玉昌.遗传算法及其应用[J].云南民族学院学报，2002（4）.

[3]蔡自兴，徐光.人工智能及应用[M].北京：清华大学出版社，2003.

[4]蒋腾旭.智能优化算法概述[J].电脑知识与技术，2007（8）.

[5]任庆生，叶中行.遗传算法中常用算子的分析[J].电子学报，2005（5）.

作者简介

温欢（1985-），江西南昌人，江西科技学院商学院教务处，本科，研究方向：应用数学