遗传算法基础

遗传算法基础第一页，共四十四页，编辑于2023年，星期三遗传算法的产生

50，60年代Holland提出遗传算法

60年代中期Holland的学生J.D.Bagley提出“遗传算法”一词

70年代Holland模式定理《AdaptationinNaturalandArtificialSystems》发表Holland的学生DeJong将遗传算法用于最优化问题Grefenstette开发了第一个遗传算法软件第二页，共四十四页，编辑于2023年，星期三遗传算法的发展

EvolutionaryComputationcomputationalintelligence

第三页，共四十四页，编辑于2023年，星期三遗传算法的生物学基础

生物进化理论与遗传学

达尔文的进化论

达尔文（1858）的自然选择学说包括：1遗传2变异3生存斗争和适者生存遗传学1866孟德尔提出的分离律和自由组合律，奠定了现代遗传学的基础摩尔根进一步确立了染色体的遗传学说，认为遗传性状是由基因决定第四页，共四十四页，编辑于2023年，星期三遗传算法的生物学基础遗传学的基本结论生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状染色体是由基因及其由规律的排列所构成.遗传和进化过程发生在染色体上生物的繁殖过程是由基因的复制过程来完成的通过同源染色体间的交叉和变异会产生新的物种,使生物呈现新的性状对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代第五页，共四十四页，编辑于2023年，星期三遗传算法的生物学基础

生物进化理论与遗传学现代综合进化论

没有所谓生存斗争的问题，单是个体繁殖机会的差异也能造成后代基因库组成的改变，自然选择也能够进行生物的进化实际上是种群的进化每一代个体基因型的改变会影响种群基因库的组成种群基因库的进化就是种群的进化基因库+适者繁殖=群体进化第六页，共四十四页，编辑于2023年，星期三遗传算法的生物学基础

生物进化理论与遗传学非达尔文式进化理论1.分子进化中性理论2.跳跃进化理论3.间断平衡进化理论非渐变进化理论的核心基础仍然是自然选择第七页，共四十四页，编辑于2023年，星期三遗传算法的生物进化模型现代综合进化论选择优胜劣汰遗传保持优良特性变异产生新特性第八页，共四十四页，编辑于2023年，星期三遗传算法的基本术语编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射解码：从遗传域到问题域的映射。即将DNA序列解释成个体的性状适应度：种群的某个个体对生存环境的适应程度。适应度高的个体可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比较少，甚至逐渐灭绝选择：以一定概率从种群中选择若干个体的操作。一般而言，选择就是基于适应度的优胜劣汰的过程交叉：有性生殖生物在繁殖下一时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染色体第九页，共四十四页，编辑于2023年，星期三遗传算法的基本思想第十页，共四十四页，编辑于2023年，星期三遗传算法的流程图编码解码第十一页，共四十四页，编辑于2023年，星期三遗传算法基本要素与实现技术编码与解码问题域（解空间）优化变量遗传域（基因空间）优化变量的代码表示映射二进制编码浮点数编码符号编码第十二页，共四十四页，编辑于2023年，星期三编码与解码二进制编码二进制编码是遗传算法中最常用、最原始的一种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作。找到最优个体后再通过解码过程还原原始的数据形式进行适应度评价二进制编码的串长度取决于求解的精度编码公式解码公式第十三页，共四十四页，编辑于2023年，星期三编码与解码浮点编码个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于其决策变量的个数。浮点编码使用的是决策变量的真实值2.509.543.250.254.257.00X:某个优化问题含有6个变量，则它的一个基因表达为对应的表现型为x=[2.50,9.54,3.25,0.25,4.25,7.00]第十四页，共四十四页，编辑于2023年，星期三编码与解码符号编码个体基因值取自一个无数值含意，而只有代码含义的符号集。符号集可以是字母，也可以是数字序号。如血型A，B，AB，O可以分别用[a,b,c,d]表示，或者[a1,a2,a3,a4],也可表示为[1，2，3，4]第十五页，共四十四页，编辑于2023年，星期三遗传算法基本要素与实现技术最小与最大的转化个体适应度评价为正确计算个体的遗传概率，个体的适应度必须为正数或者为零，不能为负数而目标函数在寻优区间有一下三种状态：第十六页，共四十四页，编辑于2023年，星期三个体适应度评价F（x）＝f（x）＋CF（x）F（x）F（x）第十七页，共四十四页，编辑于2023年，星期三遗传算法基本要素与实现技术选择算子适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。选择方法比例选择法（轮盘赌）锦标赛选择法

第十八页，共四十四页，编辑于2023年，星期三比例选择法（轮盘赌）基本思想

各个个体被选中的概率与其适应度大小成正比。设群体大小为，个体的适应度大小为，则个体被选中的概率为第十九页，共四十四页，编辑于2023年，星期三比例选择法（轮盘赌）具体步骤

1）计算各基因适应度值和选择概率

2）累计所有基因选择概率值，记录中间累加值S-mid和最后累加值sum=∑3）产生一个随机数N，0〈N〈14）选择对应中间累加值S-mid的基因进入交换集

5）重复（3）和（4），直到获得足够的基因。第二十页，共四十四页，编辑于2023年，星期三比例选择法（轮盘赌）举例染色体的适应度和所占的比例第二十一页，共四十四页，编辑于2023年，星期三锦标赛选择法基本思想每次随机选取n个个体，比较之后选择其中适应度最高的个体做为下一代种群的父本第二十二页，共四十四页，编辑于2023年，星期三遗传算法基本要素与实现技术交叉算子选择是对优秀个体的复制，不能产生新个体，交叉对相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作是产生新个体的主要方法主要问题如何对染色体进行配对如果确定交叉点的位置如何进行部分基因交换第二十三页，共四十四页，编辑于2023年，星期三随机配对将选择出的种群中的M个个体以随即的方式组成M/2对配对个体组，交叉操作就是在这些配对个体组中的两个个体之间进行第二十四页，共四十四页，编辑于2023年，星期三二进制编码染色体的交叉单点交叉

基因位数为，交叉点k的范围为[1,-1],在该点为分界相互交换变量例如：子个体101110100101子个体210101011010第二十五页，共四十四页，编辑于2023年，星期三二进制编码染色体的交叉多点交叉多点交叉的破坏性可以促进解空间的搜索第二十六页，共四十四页，编辑于2023年，星期三二进制编码染色体的交叉均匀交叉

两个配对个体的染色体每个基因位以相同的交叉概率进行交换具体步骤随机产生一个与个体编码串长度等长的屏蔽字W＝按下列规则交叉两个父本的基因若=0，则父代第i个基因相互交换若=1，则父代第i个基因不相互交换第二十七页，共四十四页，编辑于2023年，星期三均匀交叉例如第二十八页，共四十四页，编辑于2023年，星期三浮点编码染色体的交叉线性交叉交叉公式子个体＝父个体1＋F×(父个体2-父个体1)F为[0,1]间的均匀分布随机数第二十九页，共四十四页，编辑于2023年，星期三浮点编码染色体的交叉中间交叉交叉公式子个体i＝父个体1i＋F×(父个体2i-父个体1i)第三十页，共四十四页，编辑于2023年，星期三遗传算法基本要素与实现技术变异算子将个体染色体编码串中的某些基因位编码字符集的其它字符替换二进制编码染色体的变异

编码字符集为{0,1},变异操作就是将变异点上的基因取反变异点是按概率Pm在染色体基因位上指定的第三十一页，共四十四页，编辑于2023年，星期三二进制编码染色体的变异具体步骤随机产生一个与个体编码串长度等长的屏蔽字W＝为[0,1]间的随机数按下列规则对基因进行变异若Pm，则父代基因第i位变异若>Pm，则父代基因第i位不变异第三十二页，共四十四页，编辑于2023年，星期三浮点编码染色体的变异浮点编码变异第三十三页，共四十四页，编辑于2023年，星期三遗传算法的数学基础

模式定理模式

定义：种群中的个体即基因串中相同的结构例如：(以二进制编码为例)假设编码基因串长度为5模式H＝11**0描述了在基因位1，2取值为“1”，在基因位5取值为“0”的所有个体的集合{11000，11010，11100，11110}第三十四页，共四十四页，编辑于2023年，星期三模式定理结论1定义在长度为的二进制编码基因串上的模式共有证明：在长为的基因串中任选定k位作为模式中的确定位，则这样的模式共有有二项式定理第三十五页，共四十四页，编辑于2023年，星期三模式定理模式阶

定义：在模式H中具有确定基因值的位置数目称为该模式的模式阶，记为例如：基因长度固定时，模式阶越高，能与该模式匹配的样本基因就越少第三十六页，共四十四页，编辑于2023年，星期三模式定理模式定义长度定义：模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，称为该模式的模式定义长度，记为例如：第三十七页，共四十四页，编辑于2023年，星期三模式定理引入模式的概念后，我们将遗传算法看作是对模式的一种运算。某一模式H的各个样本经过选择，交叉，变异运算后，得到一些新的样本和新的模式。符号说明假定在给定的时刻t，一个特定的模式H有m个代表串包含在种群中，记为m(H,t)。种群个体的适应度为，个体总数记为n，模式H的平均适应度记为，种群的平均适应度为第三十八页，共四十四页，编辑于2023年，星期三模式定理选择算子的作用若>1，m（H，t）增加若<1，m（H，t）减少在选择算子的作用下，对于平均适用度高于群体平均适应度的模式，其样本数将增长，对于平均适用度低于群体平均适应度的模式，其样本数将减少第三十九页，共四十四页，编辑于2023年，星期三模式定理交叉算子的作用（单点交叉）模式H1被破坏的几率大于模式H2一般地，模式H被破坏的几率小于，考虑到交叉操作是按照交叉概率Pc进行的，所以模式H的生存概率大于第四十页，共四十四页，编辑于2023年，星期三模式定理变异算子的作用此时若某一模式被破坏，则必然是模式描述形式中的确定位发生了改变，破坏发生概率为

当有则模式生存概率为第四十一页，共四十四页，编辑于2023年，星期三模式定理综合选择，交叉，变异操作下，种群中模式H的子代样本数目为结论二：模式定理遗传算法中，在选择，交叉和变异算子的作用下，具有低阶，短的定义长度，并且平均适应度高于群体平均适应度的模式将逐代增加第四十二页，共四十四页，编辑于2023年，星期三遗传算法的数学基础

收敛性分析遗传算法的收敛性定义定义一：种群状态空间所有可能的种群状态的集合称为种群状态空间，它的元素代表一个种群，这个种群的个体就用描述定义二：渐进收敛

若算法在t时刻的种群满足则成算法渐进收敛到经典的遗传算法不具