遗传算法基础
2021-05-20 13:59:19 0 举报AI智能生成
描述了遗传算法的历史背景、基本思想、算法流程、基本要素、数学基础、算法特点、应用场景。
作者其他创作
大纲/内容
遗传算法的产生
50、60年代 Holland提出遗传算法
60年代中期Holland的学生J.D.Bagley提出“遗传算法”一词
70年代Holland模式定理《Adaptation in Natural and Artificial System》发表
遗传算法的发展
计算智能computational intelligence
进化计算evolutionary computation
遗传算法(GA)
进化规划(EP)
计划策略(ES)
遗传程序设计(GP)
人工神经网络
模糊系统理论
遗传算法的生物学基础
达尔文的进化论
遗传
变异
生存斗争和适者生存
遗传学
基础
分离律
自由组合律
遗传性状是由基因决定
遗传学的基本结论
生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状
染色体是由基因及其有规律的排列所构成，遗传和进化过程发生在染色体上
生物的繁殖过程是由基因的复制过程来完成的
通过同源染色体间的交叉和变异会产生新的物种，使生物呈现新的性状
对环境适应性好的基因或染色体比适应性查的基因或染色体有更多的机会遗传到下一代
非达尔文式进化理论
分子进化中性理论
跳跃进化理论
间断平衡进化理论
现代综合进化论
选择--优胜劣汰
遗传--保持优良特性
变异--产生新特性
遗传算法的基本术语
编码：从问题域到遗传域的映射
解码：从遗传域到问题域的映射
适应度：种群的某个个体对生存环境的适应度
选择：以一定概率从种群中选择若干个体的操作。一般而言，选择就是基于适应度的优胜劣汰的过程
交叉：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染色体
遗传算法的基本思想
遗传算法的流程图
遗传算法基本要素与实现技术
编码与解码
二进制编码
二进制编码是一次算法中最常用、最原始的一种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作
二进制编码的串长度l取决于求解的精度δ
浮点编码
个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于器决策变量的个数
浮点编码使用的是决策变量的真实值
符号编码
个体基因值取自一个无数值含义，而只有代码含义的符号集。符号集可以是字母，也可以是数字序号
个体适应度评价
为正确计算个体的遗传概率，个体的适应度必须为正数或者为零，不能为负数
选择算子
适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小
选择方法
比例选择法(轮盘赌)
基本思想：各个个体被选中的概率与其适应度大小成正比
具体步骤：
1.计算各基因适应度值和选择噶率Pi
2.累计所有基因选择概率值，记录中间累加值S-mid和最后累加值sum=ΣPi
3.产生一个随机数N, 0<N<1
4.选择对应中间累加值S-mid的基因进入交换集
5.重复(3)和(4)，直到获取足够的基因
锦标赛选择法
基本思想：每次随机选取n个个体，比较之后选择其中适应度搞的个体作为下一代种群的父本
交叉算子
交叉算子：选择是对优秀个体的复制，不能产生新个体，交叉对相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作时产生新个体的主要方法
主要问题：
如何对染色体进行配对
随机配对：将选择出的种群中的M个个体以随机的方式进行M/2对配对个体组，交叉操作就是在这些配对个体组中的两个个体之间进行
如何确定交叉点的位置
如何进行部分基因交换
二进制编码染色体的交叉
单点交叉
多点交叉
均匀交叉
两个配对个体的染色体每个基因位以相同的交叉概率进行交互
具体步骤：
随机产生一个与个体编码串长度等长的屏蔽字W=ω1ω2...ωl
按下列规则交叉两个父本的基因
若ωi=0，则父代第i个基因相互交换
若ωi=1，则父代第i个基因不想和交换
例子
浮点编码染色体的交叉
线性交叉
交叉公式： 子个体=父个体1+F*(父个体2-父个体1) F为[0,1]间的均匀分布随机数
中间交叉
交叉公式： 子个体i=父个体1i+F*(父个体2i-父个体1i)
变异算子
变异算子：将个体染色体编码串中的某些基因位用编码字符集的其他字符替换
二进制编码染色体的变异
编码字符集为{0,1}，变异操作就是将变异点上的基因取反，变异点是按概率Pm在染色体基因位上指定的
具体步骤
随机产生一个与个体编码串长度等长的屏蔽字W=ω1ω1...ωl ωi为[0,1]间的随机数
按下列规则对基因进行变异
若ωi<=Pm，则父代基因第i位变异
若ωi>Pm，则父代基因第i位不便宜
浮点编码染色体的变异
遗传算法的数学基础模
模式定理
模式定义：种群中的个体即基因串中相同的结构
收敛性分析
遗传算法的步骤和意义
1.初始化
选择一个群体，即选择一个串货个体的集合bi, i=1,2,3,...n。
这个初始的群体也就是问题假设解的集合。一般取n=30~160.
问题的最优解将通过这些初始假设解进化而求出。
2.选择
根据适者生存原装选择下一代的个体。
在选择时，以适应度为选择原则。
适应度准则体现了适者生存，不适应者淘汰的自然法则。
对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
3.交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P，在选中的位置实行交换。
这个过程反映了随机信息交换，目的在于产生新的基因组合，也即产生新的个体。
交叉时，可实行单点交叉或多点交叉。
一般而言，交叉概率P，取值为0.25~0.75。
4.变异
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。
在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1.
变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01~0.2
例如有个体S=101011，对其的第1、4位的基因进行变异，则有S'=001111
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。
因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。
也就是说，变异增加了全局优化的特质。
5.全局最优收敛(Convergence to the global optimum)
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛，算法结束。
否则，用经过选择、交叉、变异所得到的新一代群体，并返回到第2步即选择操作处继续循环执行。
遗传算法的特点
从问题解的中集开始搜索，而不是从单个解开始。
这是遗传算法与传统优化算法的极大区别。
传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。
遗传算法从串集开始搜索，覆盖面大，利于全局择优。
求解时使用特定问题的信息极少，容易形成通用算法程序。
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。
遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
有极强的容错能力
遗传算法的初始串集本身就带有大量与最优解甚远的信息；
通过选择、交叉、变异操作能迅速排程与最优解相差极大的串；
这是一个强烈的滤波过程，并且是一个并行滤波机制。
故而，遗传算法有极强的容错能力。
选择、交叉和变异都是随机操作，而不是确定的精确规则。
这说明遗传算法是采用随机方法进行最优解搜索。
选择体现了向最优解迫近；
交叉体现了最优解的产生；
变异体现了全局最优间的覆盖。
具有隐含的并行性
遗传算法在神经网络中的应用
1.遗传算法在网络学习中的应用
1)学习 规则的优化：用遗传算法对神经网络学习规则实现自动化，从而提供学习效率。
2)网络权系数的优化：用遗传算法的全局优化及隐含并行性的特点提供权系数优化速度。
2.遗传算法在网络设计中的应用
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后此案已选择、交叉、变异操作得出最优结构。编码方式主要有下列3种：
1)直接编码法
这是把神经网络结构直接用二进制串标示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。
通过对“染色体”的优化就实现了对网络的优化。
2)参数化编码法
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。
一般对进化后的优化“染色体”进行分析，然后产生网格的结构。
3)繁殖衍生长法
这种方法步是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码如“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。
这种方法与自然界生物生长进化相一致。
3.遗传算法在网络分析中的应用
可用于分析神经网络
神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能
遗传算法可对神经网络进行功能分析、性质分析、状态分析
目前也还有各种不足
首先，在变量多、取值范围大或无给定范围时，收敛速度下降；
其次，可找到最优解附近，但无法精确确定最优解位置；
最后，遗传算法的参数选择尚未有定量方法
对遗传算法
还需要进一步研究其数学基础理论；
还需要在理论上证明它与其他优化技术的优劣及原因；
还需研究硬件化的遗传算法；
以及遗传算法的通用变成和形式等。
遗传算法案例分析
案例一：遗传算法在TSP上的应用及改进
计算的复杂性理论
广义地讲，一个算法的有效性可以用执行该算法所需要的各种计算资源的量来度量
最典型、最主要的两个资源就是所需的运行时间和内存空间
衡量一个算法的效果，最广泛采用的标准是在生产最终答案前它所花费的时间，并常称复杂性为时间复杂度
实际上，一般没有必要精确的计算出算法的时间复杂度，只需大致计算出相应的数量级(Order)
对应组合优化问题，我们关系的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解
计算复杂性理论就是用于研究算法有效性的问题难度的手段
几个重要的复杂性分类：
定义1.1：P问题和NP问题
凡是在多项式复杂程度内可以求出最优解的问题，称为P(Polynomial)问题
其他的则是NP(Non-polynomial)问题
在算法问题上，假如一个问题是P问题，我们通常认为它是“简单的”
对于一个NP问题，通常认为它是“复杂的”
NPC问题：有许多问题，被认为无法在多项式时间内被求解，而且已经证明他们可以在多项式的时间内相互转化，因此把他们称为NPC问题，即NP完全问题
定义1.2：NPC问题
假如有一个问题
可以经过多项式计算时间内的转化，变为求解一个已被证明的NPC问题
另外，存在一个已被证明的PNC问题，经过多项式计算时间的转化，可以变为求解改问题
那么，这个问题就成为PNC问题
由于NPC问题在现有的数学知识和计算机水平情况下找不到确定型的多项式时间算法，
因此，近年来，对NPC问题的研究逐渐向两个方向演化
一个是探求在多项式的计算时间内，求得具有上确界的解的算法
另一个是探索启发式的搜索方法
前一类方法更具理论意义；后一类方法显得更具实践价值
旅行商问题的应用
应用方案
印刷电路板的钻孔线路方案
连锁店的货物配送线路
数控机床的运作等问题
TSP概述
七十、八十年代是启发式算法的全盛时期
八十年代后期一直到九十年代
一些来自其他学科的新一代求解算法相继出现，在组合优化问题的求解中取得相当的成功
Hopfield和Tank提出用神经网络联想记忆技术求解TSP
1983年Kirkpatrick等首先提出了源于固体物理的模拟退火(Simulated Annealing)算法求解复杂的组合优化问题
1987年Grenfenstette等提出的源于生物学的遗传算法(Genetic Algorithm)求解TSP问题
以及最近(Marco Dorigo于1992年)问世的源于昆虫王国的蚂蚁算法(Ant Algorithm)
我国的许多学者研究中国城市的TPS问题，基本上都采用Hopfield神经网络求解
2000年，马良总结、归纳出1954年到1996年国内外近几十年求解TPS的算法
一类是精确算法
线性规划
动态规划
分枝定界发等
另一类是近似算法(启发式算法)
插入算法
R-OPT算法
神经网络算法
模拟退火算法
遗传算法
蚂蚁算法等
TSP的瓶颈问题、多目标问题
TSP数学描述
遗传算法简介
遗传算法的产生和发展
1967年，Bagley在他的论文中首次提出了遗传算法(genetic algorithm)这一术语，并讨论了遗传算法在自动博弈中的应用
1970年，Cavicchio把遗传算法应用于模式识别中
遗传算法尤其自身的特点
智能性
自组织
自适应
自学习
本质并行性
内在并行性
0 条评论
下一页
