遗传算法的原理及组成浅析

金天坤 高 扬

（大庆师范学院 数学科学学院，黑龙江 大庆 163712）

遗传算法(GA)是一种宏观意义下的仿生算法，它模拟的机制是一切生命智能的产生与进化过程。作为一种广为应用的、高效的随机搜索与优化方法，它对模型的表达式没有特定的要求，如目标函数用约束函数的连续性、可微性等函数解析性质的限制，还具有全局优化性、稳健性与可操作的简单性等优点。

1 遗传算法的主要步骤及

遗传算法操作的是一群编码化的可行解，称作种群p（t）。它通过种群的更新与迭代来搜索全局最优解。种群的迭代是通过选择、杂交和变异等具有生物意义的遗传算子来实现的。在算法中，进化过程是通过一代群体p（t）向下一代群体p（t+1）的演化完成的,每一代群体由若干个个体组成，每个个体称为一个染色体，而每个染色体是一系基因组成的基因串。每个染色体由于其中所含基因排列方式的不同而表现出不同的性能[1]。

算法在整个优化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全随机的搜索，它能有效的利用历史信息来推测下一代的期望性能有所提高的寻优点集,这样反复进行,最后收敛到一个最优解。

2 遗传算法的组成

遗传算法主要由几个部分组成:编码方式、适应度函数、遗传操作、算法终止条件。要利用遗传算法成功的解决优化问题,每个部分的设计都非常关键。

2.1 编码

编码原理遗传算法不是对所求问题的实际优化变量直接操作，而是对表示可行解的遗传编码（即个体)作遗传操作。因此遗传算法中在进行搜索之前需要把解空间的可行解转换为搜索空间的基因型结构，这些串结构数据的不同组合便构成了不同的点。编码问题实际上是问题空间到表示空间的映射问题。

一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作可以简单地实现和执行[2]。

通常的编码方法包括:①二进制编码方法；②格雷码编码方法；③浮点数编码方法。

符号编码方法:①多参数级联编码方法；②多参数交叉编码方法。

2.2 适应度函数的设计

从数学角度看,遗传算法实质上是一种溉率性捜索算法。但它也具有一定的智能特怔。遗传算法是在适应度函数的指导下进行搜索。而不是穷举式的全面搜索。适应度函数评估是选择操作的依据。各个体适应度函数值的大小决定了它们是继续繁衍还是消亡。相当于是自然界中各生物对环境的适应能力的大小。通常，适应度大的个体具有更适应环境的基因结构。再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。改变种群内部结构的操怍皆通过适应度加以控制。适应度函数的选取直接影响到遗传的收敛性及收敛速度。

2.2 遗传操作

基本遗传搡作包括:选择、交叉、变异。

1）选择。选择操作决定如何从当前种群中选取个体作为产生下一代种群的父代个体。不同的选择策略将导致不同的选择压力，即最佳个体选中的概率与平均中概率的比值。但也较容易出现过早收敛现象；较小的选择压力能使种群保持足够的多样性。从而增大算法收敛到全局最优的概率,但算法收敛速度一般较慢。

常用的选择方法有:

①基于比例的适应度分配(proportional fitness assignment)方法

在现代社会的新形势下，森林保护工作的重要性不言而喻。面对森林保护所带来的巨大利益，我们更应该坚定信心，努力做好森林保护工作，让森林发挥出巨大的作用。并且我们还要随时关注森林保护过程中存在的问题，并且要对这些问题提出相应的解决措施，还要注意让森林保护工作落到实处，真正的为我国的环境保护做出相应的贡献。

基干适应度比例的选择方法利用比例于各个体适应的概率决定其子孙的遗留可能性。包括繁殖池选择（breeding pool selection）、轮盘赌选择（roulette wheel selection）等方法。

②基于排名的适应度分配(rank-based fitness assignment)方法

基于排名的选择方法包括线性排名选择和非线性排名选择等方法，是将种群中的个体按目标值进行排序。适应度仅仅取决于个体在种群中的序位,而不是实际的目标值。

常用选择方法还包括局部选择、截断选择、锦标赛选择、稳态繁殖等。

2）交叉

在生物的自然进化过程中，两个同源染色体通过交叉而重组形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要坏节。模仿这个环节,在遗传算法中也使用交叉算子来产生新的个体。

常用的几种交叉算子有：

②二进制交叉；单点交叉；多点交叉；均匀交叉；洗牌交叉；缩小代理交叉。

3）变异

变异是遗传算法中保持生物多样性的一个重要途径。它以一定概率选择某一基因座,通过改变该基因座的基因值来获取新个体。

算法中的适应值函数要求是非负的，而一般优化问题的目标函数并不满足这个条件。常用的实现变异的适应度变换有以下三种[3]：

（1）线性尺度变换。假定J是原适应度度量。J′是变换后新的适应度置。 则线性尺度变换的变换公式是 J′（A)=aJ（A）+β，∀A∈H

这里α是缩放因子，β是平移参数，H为所有个体构成的个体空间。其变换效果取决于对参数α，β的选取。这两个参数的选取必须满足两个条件:第一、平均适应值等于原平均适应值Jmg；第二,新适应度度置的最大值是顷平均值的指定倍数,即Ji-mg=cJmg,其中C一般取为2。

（2）乘幕尺度变换。 变换公式为：J′=aJ（A）+β，∀A∈HL

即新的适应度是原适应度的某个指定乘幕。幕指数K与变换目的及所求解的问题有关。

（3）指数尺度变换換公式为：J′=aJ（A）+β，∀A∈HL

指数比例既可以让非常好的个体保持较多的复制机会，同时又限制了其复制数目以免它很快的控制整个群体。

3遗传算法的不足及改进

通过分析，可以看出在用遗传算法进行路径规划时，随机产生初始种群，为了避免陷人局部极值点，种群数量要达到 一定的规模。但种群规模大会导致搜索空间较大，删除冗余个体的能力较差，大大影响路径规划的速度。特别在环境较为复 杂的情形下，这种缺点就更加明显。

为了更好地发挥遗传算法的作用，众多学者从各方面对算法进行深人研究和讨论，目前的改进策略大致可以分为以下两方面[4]：

（1）改进遗传算法的各组成部分。如:设计新的编码方式、动态的、自适应的参数操作、新奇的遗传操作等，来进一步改 善算法的性能(如:收敛速度慢、早熟、易陷入局部最优解等)。

（2）由于遗传算法的操作简单，较容易与其他方法结合,实验研究表明这种改进相对是比较有效的。如:为克服早熟等缺陷，提出与禁搜索（Tabu search)结合，poths提出基于迁移和人工选择的遗传算法；为解决局部优的问题，遗传算法分别与模糊集（Fuzzy set)、与混沌（Chaos)结合、与单纯形、与爬出法、神经网络、正交设计、免疫等结合来不断优化算法。

在问题越来越复杂化的今天，遗传算法也应与时倶进，只有通过不同的方式来对算法的结构、参数、操作不断改进和 提高，才能设计高效的遗传算法，满足现代社会的需要。

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

［2］张晓绩，方浩，戴冠中.遗传算法的编码机制研究[J].信息与控制 ，1997，26（2)：134-139.

［3］周浦城，洪炳镇，杨敬辉.基于遗传算法的移动机器人路径规划方法[J].哈尔滨工业大学学报，2004，36(7)：880-883.

［4］林锉云，董家礼.多目标优化的方法与理论[M].吉林：吉林教育出版社，1992.