遗传算法课件1

1、1.遗传算法原理及应用，赵鹏，2，1。遗传算法起源于1975年由美国的J.Holland教授在其专著自然与人工系统的适应性中首次提出，是一种借鉴生物学中自然选择和自然遗传机制的随机搜索算法。1.基本原则；3.生物进化循环图；4.遗传算法中生物遗传概念的对应关系：5.遗传算法的主要特征：进化发生在解的编码中，在生物学术语中称为染色体。因为解是编码的，所以优化问题的所有性质都是通过编码来研究的。编码和解码是遗传算法的一个课题。自然选择法则决定了哪条染色体产生的后代多于平均水平。在遗传算法中，自适应函数是通过优化问题的目标人工构造的，这样好的染色体可以产生比一般的后代更多的后代。当染色体结合时，父母

2、基因的结合使孩子保持父母的特征。当染色体结合在一起时，随机变异会导致后代和父母之间的差异。遗传算法的主要处理步骤是首先对优化问题的解进行编码，称为染色体，组成编码的元素称为基因。编码的目的主要是优化问题解的表达，便于遗传算法的计算。二是自适应函数的构造和应用。适应函数基本上取决于优化问题的目标函数。在适应度函数被确定之后，自然选择规则确定哪些染色体适合存活，哪些染色体被由适应度函数值大小确定的概率分布消除。幸存的染色体形成一个群体，形成一个可以繁殖下一代的群体。第三是染色体的组合。父母的遗传组合是通过代码之间的交配产生下一代。新一代的产生是一个生殖过程，它产生了一个新的解决方案。最后，变异。基

3、因变异可能发生在新解的产生过程中，这改变了一些解的编码，使解更加遍历。基本遗传算法，简单遗传算法(简称SGA)，是戈德堡总结的最基本的遗传算法之一。它的遗传进化过程简单易懂，是其他遗传算法的雏形和基础。基本遗传算法的组成，(1)编码(生成初始种群)，(2)适应度函数，(3)遗传算子(选择、交叉、变异)，(4)运行参数，(8)函数优化实例，并求出下列一元函数的最大值：x-1，2，求解结果精确到小数点后6位。遗传算法通过某种编码机制将对象抽象成由特定符号按一定顺序排列的字符串。正如生物遗传的研究始于染色体一样，染色体是一串基因。SGA使用二进制字符串进行编码。代码9，SGA对于本例的代码，由于区间

4、长度为3，解的结果精确到小数点后6位，由自变量定义的区间可分为3106个相等的部分。由于221 3106 222，本例中二进制码的长度至少需要22位，本例中的编码过程实质上将区间-1，2中的相应实值转换为二进制字符串(b21b20b0)。10，几个术语，基因型：1000101110101000111，表型：0.637197，编码，解码，个体(染色体)，基因，11，初始群体SGA使用随机方法生成一组几个个体，这称为初始群体。初始种群中的个体数量称为种群规模。适应度函数遗传算法通过适应度函数值来评估个体(解)的质量。适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是自然选择

5、的唯一标准。它的设计应该与解决问题本身的要求相结合。12、选择算子，遗传算法利用选择操作实现种群中个体的适者生存：适应性强的个体很有可能被遗传到下一代种群中；体质差的人不太可能遗传给下一代。选择操作的任务就是这样选择SGA的选择算子采用轮盘赌选择方法。13，轮盘选择信号，轮盘选择方法，14，轮盘选择方法，轮盘选择也称为比例选择算子，其基本思想是每个个体被选择的概率与其适应度函数值成比例。假设种群规模为n，个体I的适应度为fi，选择个体I遗传给下一代种群的概率为：15，轮盘赌选择方法的实现步骤，(1)计算种群中所有个体的适应度函数值(需要解码)；(2)利用比例选择算子公式，计算每个个体被选择并遗

6、传给下一代群体的概率；(3)使用模拟赌博操作(即，生成0到1之间的随机数以匹配每个个体继承到下一代群体的概率)来确定每个个体是否继承到下一代群体。16，交叉操作符，即所谓的交叉操作，是指两对染色体按照交叉概率Pc以某种方式交换它们的一些基因，从而形成两个新的个体。交叉操作是遗传算法区别于其他进化算法的一个重要特征。它在遗传算法中起着关键作用，是产生新个体的主要方法。SGA的交叉算子采用单点交叉算子。17，单点交叉操作，交叉前：00000 | 011100000100011100 | 0000011111000101交叉后：00000 | 000001111000111100000。遗传算法中的

7、变异操作是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，保持了种群的多样性。交叉操作和变异操作相互配合，完成搜索空间的全局搜索和局部搜索。SGA的变异算子采用基本变异算子。19、基本变异操作符，基本变异操作符是指对一个或几个由个体编码串随机指定的基因进行的变异操作。对于基本遗传算法中以二进制编码符号串表示的个体，如果某个需要变异操作的基因座上的原始基因值为0，变异操作会将其改为1；相反，如果原始基因值为1，变异操作会将其更改为0。20，基本变异算子的执行过程，变异前：00000111000000010000，变异后：000001110000010000，变异点，21，运行参数，(1)M

8、:种群规模，(2)T:遗传操作的终止进化代数，(3)Pc:24，原始问题的分析可以转化为寻找点A的问题，该点A可以使Y取区间0，31中的最大值。那么，0，31中的点x是一个个体，函数值f(x)可以看作是x的适应度，区间0，31是一个(解)空间。因此，只要能给出个体X的适当染色体编码，这个问题就可以用遗传算法来解决。25，解决方案(1)设置群体大小，编码染色体，并生成初始群体。将人口规模设置为4；用5位二进制数编码染色体；选择下列个体形成初始群体13360 S1=13(01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。(2)适应度函数的定义和取值如下：f (x)=x2，26，(3，27)，首先计算人口中每个个体的适应度f(si):S1=13(01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。很容易发现，f(S1)=f(13)=132=