最新遗传算法基本理论及实例.docx
《最新遗传算法基本理论及实例.docx》由会员分享，可在线阅读，更多相关《最新遗传算法基本理论及实例.docx（18页珍藏版）》请在冰点文库上搜索。
最新遗传算法基本理论及实例
遗传算法基本理论及实例
遗传算法基本理论与实例
一、遗产算法的由来
遗传算法（GeneticAlgorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。
20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。
很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。
JohnH.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。
遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。
按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。
生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。
各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。
具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。
，直至消亡。
达尔文把这一过程和现象叫做“自然选择，适者生存”。
按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。
不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。
经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。
遗传算法由美国的JohnH.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术。
二、遗传算法的国内外研究现状
遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生。
他们受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。
1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。
Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本理论——模式定理（SchemaTheorem）并于1957年出版了第一本系统论述遗传算法和人工自适应系统的专著《AdaptationinNaturalandArtificialSystems》。
20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。
1975年，DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。
1989年，Goldberg出版了《GeneticAlgorithminSearch，OptimizationandMachineLearning》一书，系统地总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理及其应用。
1991年，David出版了《HandbookofGeneticAlgorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。
1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程（GeneticProgramming，简称GP）的概念。
在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。
例如，Krishnakumar和Goldberg以及Bramlette和Gusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell（鲍威尔）的增音机设计所用的时间要少（功能评估）。
Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。
与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。
从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。
遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。
近些年来，国内外很多学者在遗传算法的编码表示、适应度函数、遗传算子、参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研究和改进。
还有很多学者将遗传算法和其他只能算法结合，进一步提高局部搜索能力。
在遗传算法的应用上也有很多改进。
由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点，使得遗传算法广泛地应用于计算机科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领域。
针对遗传算法的一些问题，还有一些问题需要进一步的探究，将大大促进遗传算法理论和应用的发展，遗传算法必将在智能计算领域中展现出更加光明的前景。
三、遗传算法的特点
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法。
它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数（评估函数）的梯度和较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖梯度信息，而是通过模拟自然进化进程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。
遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体。
遗传算法有以下优点：
（1）对可行解表示的广泛性。
遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码的基因个体，此编码操作使得遗传算法可以直接对结构对象进行操作。
所谓结构对象，泛指集合、序列、矩阵、树、链、表等各种一维或二维甚至多维结构形式的对象。
这一特点使得遗传算法具有广泛的应用领域。
比如通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化；通过对集合的操作，遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的；通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树；通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造顺序控制系统。
（2）群体搜索特性。
许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。
相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。
这一特点使遗传算法具有较好的全局搜索性能，也使得算法本身易于并行化。
（3）不需要辅助信息。
遗传算法仅用适应度函数来的数值来评估基因个体，并在此基础上尽心遗传操作。
更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。
对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。
由于限制条件的缩小，使得遗传算法的应用范围大大扩展。
（4）内在启发式随机搜索特性。
遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
概率不仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。
虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在的并行搜索机制。
（5）遗传算法在搜索过程中不容易陷入局部最优，即时在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。
（6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。
（7）遗传算法具有固有的并行性和并行计算的能力。
（8）遗传算法具有可扩展性，易于同别的技术混合使用。
遗传算法作为一种优化算法，也有它自身的局限性：
（1）编码不规范及编码存在表示的不准确性。
（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。
考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。
（3）遗传算法通常的效率比其他传统的优化方法低。
（4）遗传算法容易出现过早收敛。
（5）遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。
遗传算法的基本内容如下：
个体和种群。
个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。
种群（population）就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。
适应度与适应度函数。
适应度（fitness）就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。
适应度函数（fitnessfunction）就是问题中的全体个体与其适应度之间的一个对应关系。
它一般是一个实值函数。
该函数就是遗传算法中指导搜索的评价函数。
染色体与基因。
染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。
字符串中的字符也就称为基因（gene）。
例如个体上9，染色体的表示形式是1001，0和1是染色体上的基因。
遗传操作。
也称为遗传算子，就是关于染色体的运算。
遗传算法中有三种遗传操作：
选择-复制，交叉和变异。
四、遗传算法的流程
遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。
这样一代代的不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。
遗传算法所涉及的五大要素是：
参数编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。
流程如图1所示。
图1遗传算法基本流程
简单遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：
1）选择编码策略，把参数集合X和域转换为位串结构空间S。
2）定义适应度函数。
3）确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数。
4）随机初始化生成种群P。
5）计算群体中个体位串解码后的适应度值。
6）按照遗传策略，运用选择、交叉和变异算子作用与群体，形成下一代群体。
7）判断群体性能是否满足某一目标，或者已完成预定迭代次数，不满足则返回步骤6），或者修改遗传策略再返回步骤6）。
下面对基本步骤进行分解，进一步详细介绍流程中一些细节。
编码表示。
在许多问题求解中，编码是遗传算法中首要解决的问题，对算法的性能有很重要的影响。
Holland提出的二进制编码是遗传算法中最常用的一种编码方法，它采用最小字符编码原则，编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。
但二进制编码用于多维、高精度数值问题优化时，不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高，并且个体长度大、占用内存多。
针对二进制编码存在的不足，人们提出了多种改进方法，比较典型的有以下几种：
（1）格雷码编码。
为了克服二进制编码在连续函数离散化时存在的不足，人们提出了用格雷码进行编码的方法，它是二进制编码的变形。
格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。
假设有一个二进制编码为
，其对应的格雷码为
，则
（2）实数编码。
该方法适合于遗传算法中表示范围较大的数，使遗传算法更接近问题空间，避免了编码和解码的过程。
它便于较大空间的遗传搜索，提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算法与经典优化方法的混合作用，改善了遗传算法的计算复杂性，提高了运算效率。
（3）十进制编码。
该方法利用十进制编码控制参数，缓解了“组合爆炸”和遗传算法的早熟收敛问题。
（4）非数值编码。
染色体编码串中的基因值取一个仅有代码含义而无数值含义的符号集，这些符号可以是数字也可以是字符。
非数值编码的优点是在遗传算法中可以利用所求问题的专门知识及相关算法。
对于非数值编码，问题的解和染色体的编码要注意染色体的可行性、染色体的合法性和映射的惟一性。
适应度函数。
在遗传算法中，适应度是描述个体性能的主要指标，根据适应度的大小对个体进行优胜劣汰。
对于求解有约束的优化问题时，一般采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数；然后再将目标函数作适当处理，建立适合遗传算法的适应度函数。
将目标函数转换成适应度函数一般应遵循两个原则：
适应度必须非负；优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。
在使用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验或算法来确定相应的参数。
遗传算子。
在遗传算法中通过一系列算子来决定后代，算子对当前群体中选定的成员进行重组和变异。
（1）选择算子选择操作通过适应度选择优质个体而抛弃劣质个体，体现了“适者生存”的原理。
常见的选择操作主要有以下几种：
a）轮盘赌选择。
选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值而得到。
此方法是基于概率选择的，存在统计误差，因此可以结合最优保存策略以保证当前适应度最优的个体能够进化到下一代而不被遗传操作的随机性破坏，保证算法的收敛性。
b）排序选择。
对个体适应度取正值或负值以及个体适应度之间的数值差异程度无特殊要求，对群体中的所有个体按其适应度大小进行排序，根据排序来分配各个体被选中的概率。
c）最优个体保存。
父代群体中的最优个体直接进入子代群体中。
该方法可保证在遗传过程中所得到的个体不会被交叉和变异操作所破坏，它是遗传算法收敛性的一个重要保证条件；它也容易使得局部最优个体不易被淘汰，从而使算法的全局搜索能力变强。
d）随机联赛选择。
每次选取N个个体中适应度最高的个体遗传到下一代群体中。
具体操作如下：
从群体中随机选取N个个体进行适应度大小比较，将其中适应度最高的个体遗传到下一代群体中；将上述过程重复执行M（为群体大小）次，则可得到下一代群体。
（2）交叉算子交叉是指对两个相互交叉的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。
它是产生新个体的主要方法，决定了遗传算法的全局搜索能力，在遗传算法中起关键作用。
几种常用的适用于二进制编码或实数编码方式的交叉算子如下：
a）单点交叉。
在个体编码串中随机设置一个交叉点后在该点相互交换两个配对个体的部分基因。
b）两点交叉。
在相互配对的两个个体编码串中随机设置两个交叉点，并交换两个交叉点之间的部分基因。
c）均匀交叉。
两个相互配对个体的每一位基因都以相同的概率进行交换，从而形成两个新个体。
d）算术交叉。
由两个个体的线性组合而产生出新的个体。
（3）变异算子变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。
它是产生新个体的辅助方法，决定了遗传算法的局部搜索能力。
变异算子与交叉算子相互配合，可以共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法以良好的搜索性能完成最优化问题的寻优过程。
在遗传算法中使用变异算子主要有以下两个目的:
改善遗传算法的局部搜索能力；维持群体的多样性，防止出现早熟现象。
下面是几种常用的变异操作：
a）基本位变异。
对个体编码串以变异概率P随机指定某一位或某几位基因进行变异操作。
b）均匀变异（一致变异）。
分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。
均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加群体的多样性，使算法能够处理更多的模式。
c）二元变异。
需要两条染色体参与，通过二元变异操作后生成两条新个体中的各个基因分别取原染色体对应基因值的同或异或。
它改变了传统的变异方式，有效地克服了早熟收敛，提高了遗传算法的优化速度。
d）高斯变异。
在进行变异时用一个均值为L、方差为R2的正态分布的一个随机数来替换原有基因值。
其操作过程与均匀变异类似。
五、遗传算法实例
例：
利用遗传算法，求解区间[0，31]上的二次函数
的最大值。
分析：
原问题可转化为在区间［0，31］中搜索能使y取最小值的点x的问题。
那么，［0，31］中的点x就是个体，函数值f（x）恰好就可以作为x的适应度，区间［0，31］就是一个（解）空间。
这样，只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。
二次函数的图像如图2所示。
图2二次函数
的图像
（1）设定种群规模，编码染色体，产生初始种群。
将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群
：
=13（01101），
=24（11000）
=8（01000），
=19（10011）
（2）定义适应度函数。
取适应度函数：
f（x）=
。
（3）计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适应度最高的个体（即31（11111））出现为止。
首先计算种群S1中各个体的适应度
。
容易求得，
f（s1）=f（13）=132=169
f（s2）=f（24）=242=576
f（s3）=f（8）=82=64
f（s4）=f（19）=192=361
再计算种群
中各个体的选择概率。
选择概率的计算公式为
由此求得，P（s1）=P（13）=0.14
P（s2）=P（24）=0.49
P（s3）=P（8）=0.06
P（s4）=P（19）=0.31
用赌轮选择法可得图3，
图3赌轮选择法示意图
设从区间［0，1］中产生4个随机数如下：
r1=0.450126，r2=0.110347
r3=0.572496，r4=0.98503
表1第一代选中次数表
染色体
适应度
选择概率
积累概率
选中次数
s1=01101
169
0.14
0.14
1
s2=11000
576
0.49
0.63
2
s3=01000
64
0.06
0.69
0
s4=10011
361
0.31
1
1
于是，经复制得群体：
s1’=11000（24），s2’=01101（13）
s3’=11000（24），s4’=10011（19）
设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。
设s1’与s2’配对，s3’与s4’配对。
分别交换后两位基因，得新染色体：
s1’’=11001（25），s2’’=01100（12）
s3’’=11011（27），s4’’=10000（16）
设变异率pm=0.001。
这样，群体S1中共有5×4×0.001=0.02位基因可以变异。
0.02位显然不足1位，所以本轮遗传操作不做变异。
于是，得到第二代种群S2：
s1=11001（25），s2=01100（12）
s3=11011（27），s4=10000（16）
表2第二代选中次数表
染色体
适应度
选择概率
积累概率
估计的选中次数
s1=11001
625
0.36
0.36
1
s2=01100
144
0.08
0.44
0
s3=11011
729
0.41
0.85
2
s4=10000
256
0.15
1
1
假设这一轮选择-复制操作中，种群
中的4个染色体都被选中，则得到群体：
s1’=11001（25），s2’=01100（12）
s3’=11011（27），s4’=10000（16）
做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因，得
s1’’=11100（28），s2’’=01001（9）
s3’’=11000（24），s4’’=10011（19）
这一轮仍然不会发生变异。
于是，得第三代种群S3：
s1=11100（28），s2=01001（9）
s3=11000（24），s4=10011（19）
表3第三代选中次数
染色体
适应度
选择概率
积累概率
估计的选中次数
s1=11100
784
0.44
0.44
2
s2=01001
81
0.04
0.48
0
s3=11000
576
0.32
0.8
1
s4=10011
361
0.2
1
1
设这一轮的选择-复制结果为：
s1’=11100（28），s2’=11100（28）
s3’=11000（24），s4’=10011（19）
做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得
s1’’=11111（31），s2’’=11100（28）
s3’’=11000（24），s4’’=10000（16）
这一轮仍然不会发生变异。
于是，得第四代种群S4：
s1=11111（31），s2=11100（28）
s3=11000（24），s4=10000（16）
显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。
于是，遗传操作终止，将染色体“11111”作为最终结果输出。
然后，将染色体“11111”解码为表现型，即得所求的最优解：
31。
将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。
六、遗传算法编程
MATLAB程序需要解决的问题是利用遗传算法，求解区间[0，31]上的二次函数
的最大值。
使用的是matlabR2010A，在WIN7环境下运行。
鉴于此版本的软件不含有遗传算法工具箱，自行安装至路径“D:
\MATLAB\R2010a\toolbox\genetic\gatbx”，并在操作界面上添加路径。
程序见附录一，程序界面如图3所示。
图3程序图
运行结果如图4所示。
图4运行结果图
由图可知，经过10代之后，遗传算法找个了二次函数的最优值。
附录一：
运行程序
addpathD:
\MATLAB\R2010a\toolbox\genetic\gatbx
fplot（'variable.*variable',[0,31]）;
NIND=4;%种群个体数目
MAXGEN=10;%最大遗传代数
PRECI=5;%变量的二进制位数
GGAP=1;%代沟
trace=zeros（2,MAXGEN）;%寻优结果的初始值
FieldD=[5;0;31;1;0;1;1];%区域描述器
Chrom=crtbp（NIND,PRECI）;%初始种群
gen=0;%计数器
variable=bs2rv（Chrom,FieldD）;%计算初始种群的十进制转换
ObjV=variable.*variable;%计算目标函数值
whilegenFitnV=ranking（-ObjV）;%分配适应度函数值
SelCh=select（'sus',Chrom,FitnV,GGAP）;%选择
SelCh=recombin（'xovsp',SelCh,1）;%重组，100%
SelCh=mut（SelCh）;%变异
variable=bs2rv（SelCh,Fiel
升级会员 