遗传算法理论及技术研究综述

《遗传算法理论及技术研究综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法理论及技术研究综述周听凌兴宏（1.哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨150080；2.苏州大学计算机科学与技术学院，江苏苏州215006）摘要本文首先阐述了遗传算法的主要特点和基本原理，随后对遗传算法的理论与技术研究的主体,即编码机制、适应度评价以及选择、交叉、变异等遗传算子进行了探讨；比较分析了各种遗传操作方法的优缺点和适用场合；对遗传算法的理论和技术做了初步研究综述。关键词遗传算法；编码机制；遗传算子；适应度评价1引言遗传算法是模拟遗传选择和口然淘汰的生物进化过程的计算模型，由美国Michigan大

2、学的Holland教授于1969年提出，后经Dejong.Goldberg等人归纳总结，形成一种新的全局优化搜索算法⑴。所谓遗传算法來源于达尔文的进化论、魏茨曼的物种选择学说和孟徳尔的群体遗传学说。遗传算法足模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工解能技术2，,基木思想是模拟H然界遗传机制和生物进化论，引用了随机统计理论而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一•代一代地寻找问题的绘优解，直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代式算法,是一•种过程搜索最优解的算法,具有坚

3、实的生物学基础。遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维空间寻优问题。2遗传算法的基本原理及特点2.1遗传算法的基本原理遗传算法是一种基于口然选择和群体遗传机理的搜索算法，它模拟了自然选择和口然遗传过程中发生的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的毎个町能的解都被编码成一个“染色体”，即个体，若干个个体构成了群体（所冇可能解），通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，这些个体

4、经过交叉和变异算子进行再组合生成下-•代新的种群。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。因此，遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。⑶遗传算法的基本流程描述如图1所示。初始化群体“图1遗传算法基本流程2.2遗传算法的特点遗传算法利用了生物进化和遗传的思想，不同于枚举法、启发式算法、搜索算法等传统的优化方法，具有如下特点⑷：（1）自组织、自适应和智能性。遗传算法消除了算法设计中最大的障碍，即需要事先描述问题的全部特点，并说明针对问题的不同特点，算法

5、应采取的措施。直接处理的对象是参数编码集，而不是问题参数本身。它可用来解决复杂的非结构化问题，具有很強的鲁棒性。（2）搜索过程中使川的是基于目标函数值的评价信息，搜索过程既不受优化函数连续性的约束,也没有优化函数必须可导的要求。（3）易于并行化，可降低由于使用超强计算机硕件所带來的昂贵费用。（4）算法基本思想简单，运行方式和实现步骤规范,便于具体使用。3遗传算法的理论与技术研究遗传算法的研究主要包括三个领域®:遗传算法的理论与技术；用遗传算法进行优化；用遗传算法进行分类系统的机器学习。其中，遗传算法的理论与技术研究主要包括编

6、码、交叉运算、变界运算、选择运算以及适应度评价等问题。本文限于篇幅，仅就遗传算法的理论与技术研究进行探讨。3.1编码机制在许多问题求解屮，编码是遗传算法中首要解决的问题，对算法的性能冇很重要的影响。常见的编码方法冇如下儿种⑹：1）二进制编码由Holland®初提岀，遗传算法中最常川的一种编码方法。它采用最小字符编码原则，特点是编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。但二进制编码用于多维、高椿度数值问题优化时，不能很好地克服连续两数离散化时的映射谋差；不能直接反映问题的固冇结构，精

7、度不高，个体长度人、占用内存多。2)格宙码编码为了克服二进制编码在连续函数离散化时存在的不足，人们捉出了用格雷码进行编码的方法，它是二进制编码的变形。假设冇一个二进制编码为，其对应的格雷码为，则i=m-l,m-2,•••,2,1格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。3)编码该方法适介于遗传算法中表示范围较大的数，使遗传算法更接近问题空间，避免了编码和解码的过程。它便于较人空间的遗传搜索，提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算法与经典优化方法的混合作用，改善了遗传算法的计

8、算复杂性，提高了运算效率。4)十进制编码该方法利用十进制编码控制参数，缓解了“组合爆炸”和遗传算法的早熟收敛问题。5)符号编码染色休编码串中的基因值取一个仅冇代码含义而无数值含义的符号集，这些符号可以是数字也可以是字符。非数值编码的优点是在遗传算法中可以利用所求问题的专门知识及相关算法。对