智能优化算法_改

1、智能优化方法 1 目录 遗传算法概述遗传算法概述 遗传算法原理遗传算法原理 遗传算法应用遗传算法应用 1.遗传算法遗传算法 粒子群算法概述粒子群算法概述 粒子群算法原理粒子群算法原理 粒子群算法应用粒子群算法应用 2.粒子群算法粒子群算法 2 3 第一章 遗传算法遗传算法概述 1、遗传算法起源 遗传算法是由美国的J. Holland教授于1975年在他的专著自然 界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选 择和自然遗传机制的随机化搜索算法 。 2、遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基 因突变现象，在每次迭代中都保留一组候选解，并按某种指标

2、从解群 中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进 行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指 标为止。 4 第一章 遗传算法遗传算法原理 编码：GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排 成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排 成的串。 常用编码方式有： 二进制编码：1001（9）、110（6） 格雷码编码：000（0）、001（1）、011（2） 实数编码：1、2、3、4 符号编码：A、B、C、D 5 第一章 遗传算法遗传算法原理 适应度函数：遗传算法对一个个体（解）的好坏用适应度函数值来评 价，适应度函数值越大，解

3、的质量越好。适应度函数是遗传算法进化 过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解 问题本身的要求而定。 适应度函数的设计主要满足以下条件: 1)单值、连续、非负、最大化. 2)合理、一致性. 3)计算量小. 4)通用性. 6 第一章 遗传算法遗传算法原理 选择算子：个体被选中的概率与其适应度函数值成正比。 设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群 体的概率为： 轮盘赌选择 随机遍历抽样 截断选择 局部选择 锦标赛选择 n i iii FFP 1 / 7 第一章 遗传算法遗传算法原理 交叉运算：指对两个相互配对的染色体依据交叉概率 Pc 按某种方式 相

4、互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法 区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产 生新个体的主要方法。 例如：单点交叉中 交叉后： 00000|00000111111000101 11100|01110000000010000 交叉前： 00000|01110000000010000 11100|00000111111000101 8 第一章 遗传算法遗传算法原理 变异运算：是指依据变异概率 Pm 将个体编码串中的某些基因值用其 它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是 产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保 持

5、种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索 空间的全局搜索和局部搜索。 例如，SGA中变异算子采用基本位变异算子。 变异前：000001110000000010000 变异后：000001110001000010000 9 第一章 遗传算法遗传算法原理 运行参数： （1）M ： 种群规模 （2）T ： 遗传运算的终止进化代数 （3）Pc ： 交叉概率 （4）Pm ： 变异概率 10 第一章 遗传算法遗传算法原理 基本遗传算法（SGASGA）框图： 产生初始群体 是否满足停止准则 是 输出结果并结束 计算个体适应度值 比例选择运算 单点交叉运算 基本位变异运算 否 产生新一代群体

6、 执行M/2次 11 第一章 遗传算法遗传算法应用 应用准备： 操作系统：Windows 7 及以上 基本工具：Matlab 2012b及以上，Ga工具箱必须安装 12 第一章 遗传算法遗传算法应用 MatlabMatlab GAGA工具箱使用简介 x,fval= ga(fitnessfun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) 输出函数： X-最优解 fval-最优适应度 输入函数 fitnefun-适应度函数 nars-变量个数 输入参数 A,b -不等式约束Ax=b Aeq,beq-等式约束Aeq=beq lb,ub-变量的上下限 lb=xga

7、tool 打开ga工具箱，控制 界面如图 18 第二章 粒子群算法粒子群算法概述 粒子群算法简介： 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization）， 缩写为 PSO， 是近年来发展起来的一种新的进化算法(Evolutionary Algorithm - EA)。 PSO 算法属于进化算法的一种，它也是从随机解出发，通过迭代寻找 最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为 简单，没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其 容易实现、精度高

8、、收敛快等优点引起了学术界的重视，并且在解决实 际问题中展示了其优越性。 19 第二章 粒子群算法粒子群算法原理 算法原理简述： PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之 为粒子。所有的粒子都有一个由被优化的函数决定的适值，每个粒子还 有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优 粒子在解空间中搜索。 PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次 迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找 到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的 最优解，这个极值是全局极值。 20 第二章 粒子群算法粒子群算法原理

9、 21 第二章 粒子群算法粒子群算法原理 22 第二章 粒子群算法粒子群算法原理 23 第二章 粒子群算法粒子群算法原理 24 第二章 粒子群算法粒子群算法原理 开始 计算每个粒子的适应值 初始化每个粒子的速度和位置 开始求出每个粒子的个体最优 依据方程对粒子的位置进行进化 依据方程对粒子的速度进行进化 求出整个群体的全局最优值 是否满足结束条件 输出结果 是 否 25 第二章 粒子群算法粒子群算法应用 Matlab粒子群工具箱（PSOt）提供了非常先进的粒子群优化 算法 ，可指定惯性因子的起始值和中止值 ，可约定各维变量 的取值范围 、粒子在遇到边界时是否反弹等各种参数 。除此 以外 ，粒子

10、群工具箱既可以在用户约定的范围内自动随机生 成指定群体规模的初始粒子群 ，也可人工输入小于群体规模 的任意数目的初始粒子 ，具备非常强的灵活性 。 下载网址： http:/ 506-particle-swarm-optimization-toolbox 26 第二章 粒子群算法粒子群算法应用 PSOt具有非常强的灵活性，在实际计算中，用户只要根据需 求编写好目标函数，并设置好函数自变量的取值范围和每步 迭代允许的最大变化量，PSOt即可自动进行优化计算。 该工具箱的使用方法主要分为一下几个步骤： （1）在MATLAB的命令窗口中点击“File”，“Set Path”， 设置已下载好工具箱的路径

11、。 27 第二章 粒子群算法粒子群算法应用 PSOt具有非常强的灵活性，在实际计算中，用户只要根据需 求编写好目标函数，并设置好函数自变量的取值范围和每步 迭代允许的最大变化量，PSOt即可自动进行优化计算。 该工具箱的使用方法主要分为一下几个步骤： （1）在MATLAB的命令窗口中点击“File”，“Set Path”， 设置已下载好工具箱的路径。 （2）编写待优化的函数（test_func)，保存为同名m文件 28 第二章 粒子群算法粒子群算法应用 PSOt具有非常强的灵活性，在实际计算中，用户只要根据需 求编写好目标函数，并设置好函数自变量的取值范围和每步 迭代允许的最大变化量，PSOt

12、即可自动进行优化计算。 该工具箱的使用方法主要分为一下几个步骤： （1）在MATLAB的命令窗口中点击“File”，“Set Path”， 设置已下载好工具箱的路径。 （2）编写待优化的函数（test_func)，保存为同名m文件 （3）调用粒子群算法的核心模块：pso_Trelea_vectorized.m， 其调用格式为： pso_Trelea_vectorized(functname, D, mv, VarRange , minmax, PSOparams, plotfcn, PSOseedValue) 29 第二章 粒子群算法粒子群算法应用 pso_Trelea_vectorized(

13、functname, D, mv, VarRange, minmax, PSOparams, plotfcn, PSOseedValue) lFunctname：目标函数名 lD：待优化问题的维数； lmv：粒子飞行的最大速度； lVarRange：参数变化范围矩阵； lMinmax：寻优类型，取0代表求目标函数最小值，取1代表 求目 标函数最大值）； lPSOparams：参数矩阵，包括最大迭代次数、粒子群规模、 惯性因子、学习因子、终止迭代条件等； lPlotfcn：寻优过程中用于展示寻优过程的画图函数； lPSOseedValue：可允许用户输入任意多组初始粒子。 30 第二章 粒子群算

14、法粒子群算法应用 实际案例： 某公司经统计调查发现销售额与售后服务支出和广告投入有 关，设销售额增加为正向。固定负向投资有2.71289，不可 控因素为余弦下的服务支出和广告投入有关，可控因素是正 弦下的服务支出和广告投入平方和有关，其关系如下所示： 31 第二章 粒子群算法粒子群算法应用 （1）编写待优化函数（test_func)，保存为同名m文件 function z = test_func(in) nn=size(in); %输入的是矩阵 ，即算法中随机产生一组x和 y ，按x(nn, 1), y(nn, 1)排列 x=in(:,1); y=in(:,2); nx=nn(1); for i=1:nx temp=sin(sqrt(x(i)2+y(i)2)/sqrt(x(i)2+y(i)2)+e xp(cos(2*pi*x(i)+cos(2*pi*y(i)/2)-2.71289; z(i,:)=temp; 32 第二章 粒子群算法粒子群算法应用 （2）调）调用函用函数并运行数并运行 x_range=-2,2; y_range=-2,2; range=x_range; y_range; Max_V=0.2* (range(:,2) - range(:,1)