遗传算法的实现

1、生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究

2、中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。 321 遗传算法的基本概念 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的

3、个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下： 一、串(String) 它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。 二、群体(Population) 个体的集合称为群体，串是群体的元素 三、群体大小(Population Size) 在群体中个体的数量称为群体的大小。 四、基因(Gene) 基因是串中的元素，基因用于表示个体的

4、特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 五 、基因位置(Gene Position) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。 六、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 七、串结构空间SS 在串中，基因任意组合所构成的串的集合。基因操作是在结构空

5、间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 八、参数空间SP 这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 九、非线性 它对应遗传学中的异位显性(Epistasis) 十、适应度(Fitness) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。 322遗传算法的原理 遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，

6、从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 一、遗传算法的目的 典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题： 考虑对于一群长度为L的二进制编码bi，i1，2，n；有 bi0,1L (3-84) 给定目标函数f，有f(bi)，并且 0F(BI) 同时 f(bi)f(bi+1) 求满足下式 maxf(bi)|bi0,1L 的bi。 很明显，遗传算法是一种最优化方法，它通过进化和遗传机理

7、，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。 二、遗传算法的基本原理 长度为L的n个二进制串bi(i1，2，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种： 1选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。 2交叉(Cr

8、ossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。 3变异(Mutation) 这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。 遗传算法的原理可以简要给出如下： choose an intial population determine the fitness of each individual perform selection repeat perform crossover perform mutation determine the fitness o

9、f each individual perform selection until some stopping criterion applies 这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。三、遗传算法的步骤和意义 1初始化 选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。 通常以随机方法产生串或个体的集合bi,i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。 2选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应

10、者淘汰的自然法则。 给出目标函数f，则f(bi)称为个体bi的适应度。以 为选中bi为下一代个体的次数。 显然从式(386)可知： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。 3交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111

11、选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交 婊显譖。取值为0.250.75。 4变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，4位置的基因进行变异，则有 S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。

12、也就是说，变异增加了全局优化的特质。 5全局最优收敛(Convergence to the global optimum) 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。 图37中表示了遗传算法的执行过程。 图3-7 遗传算法原理 323遗传算法的应用 遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一

13、步研究开发。 一、遗传算法的特点 1遗传算法从问题解的中集开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。 2遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。 3遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波

14、过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 4遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。 5遗传算法具有隐含的并行性 遗传算法的基础理论是图式定理。它的有关内容如下： (1)图式(Schema)概念 一个基因串用符号集0，1，*表示，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。 (2)图式的阶和长度 图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，

15、并用(H)表示。对于图式H1x x0x x，有0(H)2，(H)4。 (3)Holland图式定理 低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。 遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。 二、遗传算法的应用关键 遗传算法在应用中最关键的问题有如下3个 1串的编码方式 这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。 2适应函数的确定 适应函数(fitness functio

16、n)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。 3遗传算法自身参数设定 遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。 群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm00102。 三、遗传算法在神经网络中的应用 遗传算法在神经网络中的应用主要反映在3个方面：

17、网络的学习，网络的结构设计，网络的分析。 1遗传算法在网络学习中的应用 在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用 (1)学习规则的优化 用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。 (2)网络权系数的优化 用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。 2遗传算法在网络设计中的应用 用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种： (1)直接编码法 这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色

18、体”的优化就实现了对网络的优化。 (2)参数化编码法 参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。 (3)繁衍生长法 这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。 3遗传算法在网络分析中的应用 遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析

19、，状态分析。 遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。 三、遗传算法的步骤和意义 1初始化 选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。

20、通常以随机方法产生串或个体的集合bi,i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。 2选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f，则f(bi)称为个体bi的适应度。以 为选中bi为下一代个体的次数。 显然从式(386)可知： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。 3交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相

21、同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交 婊显譖。取值为0.250.75。 4变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，

22、4位置的基因进行变异，则有 S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 5全局最优收敛(Convergence to the global optimum) 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。 图37中表示了遗传算法的执行过程。 图3-7 遗传算法原理

23、 323遗传算法的应用 遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。 一、遗传算法的特点 1遗传算法从问题解的中集开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。 2遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需

24、适应值和串编码等通用信息，故几乎可处理任何问题。 3遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 4遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。 5遗传算法具有隐含的并行性 遗传算法的基础理论是图式定理。它的有关内容如下： (1)图式(Schema)概念 一个基因串用符号集0，1，*表示

25、，则称为一个因式；其中*可以是0或1。例如：H=1xx 0 x x是一个图式。 (2)图式的阶和长度 图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用(H)表示。对于图式H1x x0x x，有0(H)2，(H)4。 (3)Holland图式定理 低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。 遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。 二、遗传算法的应用关键 遗传算法在应用中最关键的问题有如下3个 1

26、串的编码方式 这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。 2适应函数的确定 适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。 3遗传算法自身参数设定 遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。 群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜