遗传算法讲稿专家讲座

当代智能优化算法—

遗传算法遗传算法讲稿专家讲座第1页遗传算法(GeneticAlgorithms，简称GA)是一个模拟生物遗传和进化过程计算方法。进化学说三个方面：遗传：生物从其父代继承特征或性状生命现象，即种瓜得瓜，种豆得豆。遗传保持了物种稳定。变异：一母生九子，九子各不一样。变异选择和积累是生物多样性根源；适者生存：生物之间存在竞争，依据对环境适应能力，适者生存。遗传算法——概述遗传算法讲稿专家讲座第2页GA四个基本条件1.存在由多个生物个体組成种群2.生物个体之间存在着差异，或全体含有多样性3.生物能够自我繁殖4.不一样个体含有不一样环境生存能力，含有优良基因结构个体繁殖能力強，反之則弱遗传算法讲稿专家讲座第3页GA--特点遗传算法以决议变量编码作为运算对象，从而能够很方便地引入和应用遗传操作算子。传统优化算法往往直接利用决议变量实际值本身进行优化计算。遗传算法直接以目标函数值作为搜索信息，实现比较方便。传统优化算法往往不只需要目标函数值，还需要目标函数导数等其它信息。这么对许多目标函数无法求导或极难求导函数，实现困难。遗传算法讲稿专家讲座第4页GA--特点遗传算法同时进行解空间多点搜索。传统优化算法往往从解空间一个初始点开始搜索，这么轻易陷入局部极值点。遗传算法进行群体搜索，而且在搜索过程中引入遗传运算，使群体又能够不停进化。这些是遗传算法所特有一个隐含并行性。遗传算法使用概率搜索技术。遗传算法属于一个自适应概率搜索技术，其选择、交叉、变异等运算都是以一个概率方式来进行，从而增加了其搜索过程灵活性。遗传算法讲稿专家讲座第5页GA基础术语染色体（Chromosome）生物细胞中含有一个微小丝状化合物，是遗传物质主要载体，由多个遗传基因组成。基因（gene）也称遗传因子，DNA链中占有一定位置基本单位。生物基因数量依据物种不一样多少不一，从几个（病毒）到几万个（动物）。个体（individual）指带有染色体特征实体。种群（population）一定数量个体集合。遗传算法讲稿专家讲座第6页GA基础术语适应度（fitness）个体对环境适应程度进化（evolution）生物逐步适应其生存环境，使得其品质不停提升选择（selection）指决定以一定概率从种群中选择若干个体操作。普通而言，选择过程是一个基于适应度优胜劣汰过程复制（reproduction）细胞分裂时，遗传物质DNA经过复制转移到新细胞中，新细胞就继承了旧细胞基因遗传算法讲稿专家讲座第7页GA基础术语交叉（crossover）两个染色体某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新染色体变异（mutation）在细胞复制时，基因某个位发生某种突变，产生新染色体编码（coding）DNA中遗传信息按一定方式排列，也可看作从表现型到遗传型映射解码（decoding）从遗传型到表现型映射遗传算法讲稿专家讲座第8页GA三个基本算子复制／选择(Reproduction/Selection)

依据每一物种适应程度来决定其在下一代中应被复制或淘汰个数多少轮盘式选择竞争式选择遗传算法讲稿专家讲座第9页GA三个基本算子—交叉

交叉式一个提供个体间彼此交换信息机制，交叉过程主要是母代中较优良染色体作一些基因交换，预期产生更优良后代。普通常见交叉方式有：

（1）单点交叉(One-pointcrossover)

（2）双点交叉(Tail-tailcrossover)

（3）均匀交叉遗传算法讲稿专家讲座第10页GA三个基本算子—变异

经过突变方式，使得解能够跳脱单纯交叉产生区域，进而产生新染色体，变异过程主要以随机方式，将染色体基因位由0变成1或由1变成0，主要变异方式有：（1）等位基因突变(SimpleMutation)（2）均匀突变(UniformMutation)（3）非均匀突变(Non-UniformMutation)遗传算法讲稿专家讲座第11页GA基本流程遗传算法讲稿专家讲座第12页算例说明—编码求解问题maxf(x)=x2

[0,31]x取正整数第一步：编码采取二进制形式我们把变量x编码为5位长二进制无符号整数表示形式

00000031111117001111201100遗传算法讲稿专家讲座第13页算例说明—种群生成第二步初始种群生成因为遗传算法群体型操作需要，所认为遗传操作准备了一个由若干初始解组成初始群体。这里我们取群体大小为4，即群体由4个个体组成，每个个体经过随机初始化产生初始群体也称为进化初始代，即第一代（firstgeneration），初始化后，群体为

01101110000100010011遗传算法讲稿专家讲座第14页算例说明—适应度评价遗传算法用评价函数（适应度函数值）来评定个体（解）优劣，并作为以后遗传操作依据。这里我们依据f(x)=x2

在评价个体适应度值大小时，首先要解码，即把基因型个体变成表现型个体（即搜索空间解）这里就是二进制到十进制转换基因型01101110000100010011

表现型x

1324819f(x)=x2169

57664361

（适应值）遗传算法讲稿专家讲座第15页算例说明—选择选择概率

适应度总和1170，平均值293利用轮盘赌选择结果

1201计算结果为0.140.490.060.31遗传算法讲稿专家讲座第16页算例说明—选择初始族群适应值F(i)复制个数011101960.180.711110005760.522.072100012890.261.04100111490.040.180初始族群01110110001000100111选择后01110110001000111000遗传算法讲稿专家讲座第17页算例说明—交叉单点交叉为例两个染色体1011100111001100假设交叉点在位置41011|10011100|11001011110011001001遗传算法讲稿专家讲座第18页算例说明—交叉01110110001100010001选择后结果配对情况1和2配对3和4配对

01110

110001100010001交叉点选择第一对位置3，第二对位置1交叉前

01|110

1100|0

11|000

1000|1交叉后

01000110011111010000遗传算法讲稿专家讲座第19页算例说明—交叉交叉前配對交叉点交叉后xf(x)011102301000864110001311110309001100041110012562510001311000016256f=1845

平均适应度值f=461遗传算法讲稿专家讲座第20页算例说明—变异变异基因数决定基因总数×变异概率=(4×5)×0.1=2

有兩個基因將被突变随机选取染色体进行变异随机选取要变异染色体基因位变异目标在防止陷入局部最优解遗传算法讲稿专家讲座第21页算例说明—变异01000110011111010000假设变异基因发生在第一个染色体第3位和第四个染色体第二位上变异就是把二进制0变成1把1变成0变异前01000110011111010000变异后01100110011111010010遗传算法讲稿专家讲座第22页算例说明—变异变异池是否有变异变异点变异后ff(x)01000是3011001010011001否3111103090011110否1110012562510000是11001018324f=1949

平均适应度值f=487遗传算法讲稿专家讲座第23页算例说明—进化过程进化代数染色体xf(x)f平均值最正确值1011011100001000100111324819169576

6436111702921920110011001111101001012133018144169900324

1537384303101001100111110110102223302448452990057624896223041010111101111110001021

293124418419614224756231遗传算法讲稿专家讲座第24页算例说明—终止准则普通而言，遗传算法终止条件有以下几个：

（1）到达最大进化代数；

（2）所求解到达可接收范围；

（3）连续几代最正确解无改变或改变非常微小；

（4）到达最大运算时间。遗传算法讲稿专家讲座第25页遗传算法--参数配置种群数量视详细问题和解空间维数，问题越复杂，维数越高，种群数量要求越大，普通取遗传运算终止进化代数依据问题复杂程度，普通取为100~500交叉率普通选取范围在0.4~0.99之间变异率普通选取范围在0.001~0.1之间当代普通采取自适应改变交叉率和变异率遗传算法讲稿专家讲座第26页遗传算法—应用遗传算法提供了一个求解复杂系统优化问题通用框架，它不依赖于问题详细领域，对问题种类有很强鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法主要应用领域。遗传算法讲稿专家讲座第27页遗传算法—应用组合优化：遗传算法是寻求组合优化问题满意解最正确工具之一，实践证实，遗传算法对于组合优化问题中NP完全问题非常有效。遗传算法讲稿专家讲座第28页遗传算法—应用生产调度问题：生产调度问题在很多情况下所建立起来数学模型难以准确求解，即使经过一些简化之后能够进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为处理复杂调度问题有效工具。遗传算法讲稿专家讲座第29页遗传算法—应用自动控制：遗传算法已经在自动控制领域中得到了很好应用，比如基于遗传算法含糊控制器优化设计、基于遗传算法参数辨识、基于遗传算法含糊控制规则学习、利用遗传算法进行人工神经网络结构优化设计和权值学习等。遗传算法讲稿专家讲座第30页遗传算法—应用机器人学：机器人是一类复杂难以准确建模人工系统，而遗传算法起源就来自于对人工自适应系统研究，所以机器人学自然成为遗传算法一个主要应用领域。机器学习：基于遗传算法机器学习，在很多领域中都得到了应用。比如基于遗传算法机器学习可用来调整人工神经网络连接权，也能够用于人工神经网络网络结构优化设计。遗传算法讲稿专家讲座第31页遗传算法—应用图象处理：图像处理是计算机视觉中一个主要研究领域。在图像处