Matlab与遗传算法.ppt

遗传算法理论 遗传算法的概要 问题的提出对于一个求函数最大的优化问题一般可以描述为下述数学规划模型式中 为决策变量 f x 为目标函数 式 1 2 1 3 为约束条件 U为基本空间 R是U的一个子集 称为可行集 总的来讲 求最优解或近似最优的方法主要有三种 枚举法 启发式算法和搜索算法 随着问题种类的不同和规模的扩大 上述方法都不理想 遗传算法却提供了这类问题一个有效方法 开创了一种新的全局优化搜索算法 遗传算法中 将N维决策向量用n个记号Xi i 1 2 n 所组成的符号串X来表示 把每个Xi看成一个遗传基因 它的所有可能取值称为等位基因 这样 X就可看做是由n个遗传基因所组成的一个染色体 遗传算法中 决策变量X组成了问题的解空间 对问题最优的搜索是通过染色体X的搜索过程来进行的 从而由所有染色体X就组成了问题的搜索空间 遗传算法的基本概念和术语 与生物界的进化过程相类比 遗传算法中有以下几个非常重要的概念和术语 种群 population 染色体带有特征的个体的集合称为种群 该集合内个体数称为群体的大小 有时个体的集合也称为个体群 适应度 fitness 度量某个物种对于生存环境的适应程度 对生存环境适应程度较高的物种将获得更多的繁殖机会 选择 selection 指决定以一定的概率从种群中选择若干个体的操作 一般而言 选择的过程是一种基于适应度的优胜劣汰的过程 交叉 crossover 将群体内的各个个体随机搭配成对 对每个个体以某个概率 交叉概率 交换它们之间的部分染色体 变异 mutation 对群体中的每个个体以某一概率 变异概率 改变某一个或某些基因座上的基因值为其它的等位基因 编码 coding DNA中遗传信息在一个长链上按一定的模式排列 也即进行了遗传编码 遗传编码可以看作从表现型到遗传子型的映射 解码 decoding 从遗传子型到表现型的映射 遗传算法的手工模拟计算示例 1 个体编码x1 x2取0 7之间的整数 可分别用3为无符号二进制整数来表示 将它们连接成一起所组成的6位无符号二进制整数就形成个体的基因型 表示一个可行解 如基因型X 101110所对应的表现型是X 5 6 个体表现型和基因型X之间可通过编码和解码程序相互转换 2 初始群体的产生规模取4 随机产生 3 适应度计算本例目标函数总取非负值 可求函数最大值为最优目标 以此计算个体的适应度 4 选择运算 选择方法 适应度比例法 转轮法 按各染色体适应度大小比例来决定其被选择数目的多少 某染色体被选的概率 Pc 5 交叉运算 方法 随机选择二个染色体 双亲染色体 随机指定一点或多点 进行交换 可得二个新的染色体 子辈染色体 新的子辈染色体 A 11010001B 01011110 6 变异运算 GA的流程 遗传算法的特点 遗传算法以决策变量的编码作为运算对象 传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算 而遗传算法是一决策变量的某种形式的编码为运算对象 遗传算法直接以目标函数值作为搜索信息 传统算法不仅需要利用目标函数值 而且往往还需要目标函数的到数值等其它辅助信息 因而遗传算法避开了求导的障碍 遗传算法同时使用多个搜索点的搜索信息 传统的优化算法往往从解空间中的一个初始点开始迭代搜索过程 遗传算法使用了概率搜索技术这优于传统算法的确定性搜索 因为从一个点到另一个点的确定性有可能使搜索永远达不到最优点 遗传算法的基本实现技术BY朱诗颖 1 编码方法2 适应度函数3 选择算子4 交叉算子5 变异算子6 遗传算法的运行参数 编码方法 在遗传算法中 把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码 编码是遗传算法在首要解决的问题 它会影响到交叉算子 变异算子等运算方法 决定了运算的效率 DeJong提出了两条操作性较强的实用编码原则 一 应使用能易于产生与所求问题相关的且低阶 短定义长度模式的编码方案 二 应使用能使问题得到自然表示或描述的具体有最少编码字符集的编码方案 目前主要的编码方法 1 二进制编码方法2 浮点数编码方法3 符号编码方法 二进制编码 遗传算法中最常用的一种编码方法 符号集是由二进制符号0和1所组成 符号串长度与问题所要求的解精度有关 取值范围是 假设用长度为二进制编码符号来表示 则能产生种不同的的编码 若使编码对应关系如下 格雷编码 格雷码的连续两个整数所对应的编码之间仅仅只有一个码位是不相同的 假设有一个二进制编码为B 其对应的格雷码为G 由二进制到格雷码的转换公式 遗传算法的局部搜索能力差 变异操作一个基因座的差异 对应的参数值却很大 格雷码则克服了这个弱点 例如 对于区间 0 1023 中的两个邻近的整数x1 175和x2 176 若使用长度为10位的二进制编码为 x1 0010101111 x2 0010110000而使用相同长度的格雷码 x1 0011111000 x2 0011101000 可见在进行变异操作后格雷码能保持稳定行 差异较小 相对提高了局部搜索能力 便于进行连续空间的局部搜索 其它常见的编码 浮点编码方法 个体的每个基因值用某一范围的一个浮点数表示 个体的编码长度等于其决策变量的个数 例如某个优化问题有5个变量Xi i 1 2 5 每个变量都有其对应上下限 则X 就是一个基因型 对应表现型X 5 80 6 90 3 50 3 80 5 00 注意每个字节的限制范围 符号编码方法 个体染色体编码串中的基因取自一个无数值含义 而只有代码含义的符号集 例如n个城市被访问顺序可构成一个旅行路线个体X 1 2 3 n 多参数级联编码方法 针对多个变量的个体进行编码 每个参数可采用任何一种 有不同的上下界和编码长度和精度 多参数交叉编码方法 先对各个参数分组编码 再将各个参数编码串中的最高位连接在一起 再取次高位的连接一起以此类推 适度函数 与自然界的优胜劣汰类似 在遗传算法里使用适应度来衡量群体中各个个体接近最优接的优良程度 度量适应度的函数称为适度函数 遗传算法中可以根据优化问题的类型 利用目标函数转化成适度函数 设目标函数为f x 适度函数为F x 最大值问题 最小值问题 适应度尺度转换 主要的三种变换方法 线性尺度变换 F aF ba b为系数条件一 变换后新适应度平均值要不改变条件二 变换后新的最大适应度要等于平均适应度指定的倍数乘幂尺度变换指数尺度变换 选择算子 选择操作建立在对个体适应度的评价基础之上最常用的选择算子是比例算子 一种回放式随机采样的方法 基本思想 各个个体被选中的概率与其适应度的大小成正比 设群体大小为M 个体i的适应度为Fi 则个体被选中的概率为Pi 用转轮方法进行选择 交叉算子 配对策略 随机配对 即将M个个体随机组成随机设置交叉点单点交叉双点交叉与多点交叉 均匀交叉算术交叉两个个体线性组合而产生两个新的个体 变异算子 基本位变异均匀变异 依次指定个体编码中的每个基因座为变异点 并以变异概率Pi从对应基因的取值范围中取一随机数来代替原有基因值 例如 遗传算法的运行参数 遗传算法中需要选择的运行参数主要有个体编码串长度L与精度有关群体大小M一般20 100交叉概率Pi一般取较大0 4 0 99变异概率Pm建议0 0001 0 1终止代数T100 1000代沟G每一代群体中被替换掉的个体在全部个体中的所占百分率例如G 1 0表示群体全部个体都是新产生的 MATLAB遗传算法工具箱 1 GAOT工具箱2 gatbx工具箱3 gads工具箱 Gaot主要函数列表 gatbx工具箱函数列表 Gads工具箱 基于图形用户界面基于 M文件编写的函数文件 适应度函数 变量个数 约束条件 图形选项 运行状态显示区 尺度变换 选择函数 繁殖选项 变异选项 交叉选项 算法停止条件 迁移参数 运算参数设定 混合函数选项 遗传算法搜索函数最小值 x fval exitFlag output population scores ga FUN GenomeLength Aineq Bineq Aeq Beq LB UB nonlcon options X 适应点值fval 适应度函数在x点处的函数值FUN 适应函数GenomeLength 个体基因长度Aineq Bineq Aeq Beq nonlcon 约束条件参数LB UB x的下界 上界 Options 算法参数结构体常 通过gaoptimset函数来设定 实例演示以Rastringrin函数为例演示matlab遗传算法工具箱的使用f 20 x 2 10 cos 2 pi x y 2 10 cos 2 pi y 5 12 x y 5 12 1 函数法直接在matlab命令行里输入rafitness 运行结果 x 1 0e 008 0 16630 0263fval 0 2 用GUI图形界面直接在Fitnessfuntion框里输入 rastriginsfcn 输入变量个数为2 设定繁殖代数为150代 在plot区里可以勾选希望看到的结果图像 设置完参数之后点击start按钮就可以运行了 GUI演示图 运行结果 遗传算法实例示范 作者 张健 函数优化实例 求函数f x 10 sin 5x 7 cos 4x 的最大值 其中x 0 10 将x的值用一个10位的二值形式表示为二值问题 一个10位的二值数提供的分辨率是每为 10 0 2 10 1 0 01 将变量域 0 10 离散化为二值域 0 1023 x 10 b 1023 其中b是 0 1023 中的一个二值数 1 编码initpop m函数的功能是实现群体的初始化 popsize表示群体的大小 chromlength表示染色体的长度 二值数的长度 长度大小取决于变量的二进制编码的长度 在本例中取10 位 遗传算法子程序Name initpop m 初始化functionpop initpop popsize chromlength pop round rand popsize chromlength rand随机产生每个单元为0或1 行数为popsize 列数为chromlength的矩阵 这样产生的初始种群 2 计算目标函数值2 1将二进制数转化为十进制数遗传算法子程序Name decodebinary m 产生 2 n2 n 1 1 的行向量 然后求和 将二进制转化为十进制 functionpop2 decodebinary pop px py size pop 求pop行和列数fori 1 pypop1 i 2 py i pop i endpop2 sum pop1 2 求pop1的每行之和2 2将二进制编码转化为十进制数 2 decodechrom m函数的功能是将染色体 或二进制编码 转换为十进制 参数spoint表示待解码的二进制串的起始位置 对于多个变量而言 如有两个变量 采用20位表示 每个变量10位 则第一个变量从1开始 另一个变量从11开始 本例为1 参数1ength表示所截取的长度 本例为10 遗传算法子程序Name decodechrom m 将二进制编码转换成十进制functionpop2 decodechrom pop spoint length pop1 pop spoint spoint length 1 pop2 decodebinary pop1 2 3计算目标函数值calobjvalue m函数的功能是实现目标函数的计算 其公式采用本文示例仿真 可根据不同优化问题予以修改 遗传算法子程序Name calobjvalue m 实现目标函数的计算function objvalue calobjvalue pop temp1 decodechrom pop 1 10 将pop每行转化成十进制 x temp1 10 1023 将二值域中的数转化为变量域的数objvalue 10 sin 5 x 7 cos 4 x 计算目标函数值3计算个体的适应值遗传算法子程序Name calfitvalue m 计算个体的适应值functionfitvalue calfitvalue objvalue globalCmin Cmin 0 px py size objvalue fori 1 pxifobjvalue i Cmin 0temp Cmin objvalue i else temp 0 0 endfitvalue i temp endfitvalue fitvalue 2 4选择复制 选择或复制操作是决定哪些个体可以进入下一代 程序中采用赌轮盘选择法选择 这种方法较易实现 根据方程pi fi fi fi fsum 选择步骤 1 在第t代 由 1 式计算fsum和pi 2 产生 0 1 的随机数rand 求s rand fsum 3 求 fi s中最小的k 则第k个个体被选中 4 进行N次2 3 操作 得到N个个体 成为第t t 1代种群 遗传算法子程序Name selection m 选择复制function newpop selection pop fitvalue totalfit sum fitvalue 求适应值之和fitvalue fitvalue totalfit 单个个体被选择的概率fitvalue cumsum fitvalue 如fitvalue 1234 则cumsum fitvalue 13610 px py size pop ms sort rand px 1 从小到大排列fitin 1 newin 1 whilenewin pxif ms newin fitvalue fitin newpop newin pop fitin newpop newin pop fitin newin newin 1 elsefitin fitin 1 endend5 交叉交叉 crossover 群体中的每个个体之间都以一定的概率pc交叉 即两个个体从各自字符串的某一位置 一般是随机确定 开始互相交换 这类似生物进化过程中的基因分裂与重组 例如 假设2个父代个体x1 x2为 x1 0100110 x2 1010001 这样2个子代个体就分别具有了2个父代个体的某些特征 利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体 事实上交又是遗传算法区别于其它传统优化方法的主要特点之一 遗传算法子程序Name crossover m 交叉function newpop crossover pop pc px py size pop newpop ones size pop fori 1 2 px 1if rand pc cpoint round rand py newpop i pop i 1 cpoint pop i 1 cpoint 1 py newpop i 1 pop i 1 1 cpoint pop i cpoint 1 py elsenewpop i pop i newpop i 1 pop i 1 endend2 6变异变异 mutation 基因的突变普遍存在于生物的进化过程中 变异是指父代中的每个个体的每一位都以概率pm翻转 即由 1 变为 0 或由 0 变为 1 遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间 因此可以在一定程度上求得全局最优解 遗传算法子程序Name mutation m 变异function newpop mutation pop pm px py size pop newpop ones size pop fori 1 pxif rand pm mpoint round rand py ifmpoint 0mpoint 1 endnewpop i pop i ifany newpop i mpoint 0newpop i mpoint 1 elsenewpop i mpoint 0 endelsenewpop i pop i endend7 求出群体中最大的适应值及其个体遗传算法子程序Name best m 求出群体中适应值最大的值function bestindividual bestfit best pop fitvalue px py size pop bestindividual pop 1 bestfit fitvalue 1 fori 2 pxiffitvalue i bestfitbestindividual pop i bestfit fitvalue i endend2 8主程序遗传算法主程序Name genmain05 mfunctiongenmain popsize n chromlength 10 字符串长度 个体长度 pc 0 6 交叉概率 pm 0 001 变异概率pop initpop popsize chromlength 随机产生初始群体fori 1 20 20为迭代次数 objvalue calobjvalue pop 计算目标函数fitvalue calfitvalue objvalue 计算群体中每个个体的适应度 newpop selection pop fitvalue 复制 newpop crossover pop pc 交叉 newpop mutation pop pc 变异 bestindividual bestfit best pop fitvalue 求出群体中适应值最大的个体及其适应值y i max bestfit n i i pop5 bestindividual x i decodechrom pop5 1 chromlength 10 1023 pop newpop endfplot 10 sin 5 x 7 cos 4 x 010 holdonplot x y r holdoff zindex max y 计算最大值及其位置x x index 计算最大值对应的x值y z 在MATLAB命令串口输入genmain 20 20