智能优化算法_改

智能优化方法1目录•遗传算法概述•遗传算法原理•遗传算法应用1.遗传算法•粒子群算法概述•粒子群算法原理•粒子群算法应用2.粒子群算法23第一章遗传算法——遗传算法概述1、遗传算法起源遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。2、遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。4第一章遗传算法——遗传算法原理编码：GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。常用编码方式有：•二进制编码：1001（9）、110（6）···•格雷码编码：000（0）、001（1）、011（2）···•实数编码：1、2、3、4···•符号编码：A、B、C、D···5第一章遗传算法——遗传算法原理适应度函数：遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。适应度函数的设计主要满足以下条件:1)单值、连续、非负、最大化.2)合理、一致性.3)计算量小.4)通用性.6第一章遗传算法——遗传算法原理选择算子：个体被选中的概率与其适应度函数值成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：•轮盘赌选择•随机遍历抽样•截断选择•局部选择•锦标赛选择niiiiFFP1/7第一章遗传算法——遗传算法原理交叉运算：指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。例如：单点交叉中交叉后：00000|0000011111100010111100|01110000000010000交叉前：00000|0111000000001000011100|000001111110001018第一章遗传算法——遗传算法原理变异运算：是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。例如，SGA中变异算子采用基本位变异算子。变异前：000001110000000010000变异后：0000011100010000100009第一章遗传算法——遗传算法原理运行参数：（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率10第一章遗传算法——遗传算法原理基本遗传算法（SGA）框图：产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次11第一章遗传算法——遗传算法应用应用准备：操作系统：Windows7及以上基本工具：Matlab2012b及以上，Ga工具箱必须安装12第一章遗传算法——遗传算法应用MatlabGA工具箱使用简介[x,fval]=ga(fitnessfun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)输出函数：X---最优解fval----最优适应度输入函数fitnefun---适应度函数nars-----变量个数输入参数A,b------不等式约束Ax=bAeq,beq-----等式约束Aeq=beqlb,ub---------变量的上下限lb=x=ubnonlcon------------非线性函数约束option------传递给ga的参数，不写MATLAB自动取默认值，参考gaoptimset13第一章遗传算法——遗传算法应用实际案例：某公司对一项目进行投资，经过分析计算，以公司运营成本减少为正方向，该项目的运营成本与公司激励程度（下称激励系数，负向指标，取值范围0~1）和员工努力程度（下称努力系数，正向指标，取值范围0~13）有如下约定及关系：1.称努力系数与激励系数之乘积为协作系数，为负向指标2.按照当地法规，公司激励相对员工努力不得小于一定阈值，即：协作系数+激励系数-努力系数不得小于-1.5，即3.协作系数必须大于10，否则公司不可正常运营根据以上信息可以建模：130100*1005.1*.)1()(*100)(21212121212221xxxxxxxxtsxxxxfMin14第一章遗传算法——遗传算法应用解法：1.创建目标函数：15第一章遗传算法——遗传算法应用解法：2.创建约束函数：16第一章遗传算法——遗传算法应用解法：3.使用Ga工具包求解，对应的程序如下：17第一章遗传算法——遗传算法应用遗传算法工具箱gatool在控制窗口输入gatool打开ga工具箱，控制界面如图18第二章粒子群算法——粒子群算法概述粒子群算法简介：粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法(EvolutionaryAlgorithm-EA)。PSO算法属于进化算法的一种，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其容易实现、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。19第二章粒子群算法——粒子群算法原理算法原理简述：PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。20第二章粒子群算法——粒子群算法原理假设在一个10维的目标搜索空间中，有𝑁个粒子组成一个群落，其中第i个粒子表示为一个10维的向量𝑋𝑖=𝑥𝑖1,𝑥𝑖2,⋅⋅⋅,𝑥𝑖10,𝑖=1,2,⋅⋅⋅,𝑁第个i粒子的“飞行”速度也是一个10维的向量,记为𝑉𝑖=𝑣𝑖1,𝑣𝑖2,⋅⋅⋅,𝑣𝑖10,𝑖=1,2,⋅⋅⋅,𝑁第i个粒子迄今为止搜索到的最优位置称为个体极值，记为𝑃𝑏𝑒𝑠𝑡=𝑝𝑖1,𝑝𝑖2,⋅⋅⋅,𝑝𝑖10,𝑖=1,2,⋅⋅⋅,𝑁整个粒子群迄今为止搜索到的最优位置为全局极值，记为𝑔𝑏𝑒𝑠𝑡=𝑝𝑔1,𝑝𝑔2,⋅⋅⋅,𝑝𝑔10,𝑖=1,2,⋅⋅⋅,𝑁21第二章粒子群算法——粒子群算法原理在找到这两个最优值时，粒子根据如下的两个公式来更新自己的速度和位置：𝒗𝑖𝑑𝑘+1=𝒘×𝒗𝑖𝑑𝑘+𝑐1×𝑟1𝑗𝒑𝑖𝑑𝑘−𝒙𝑖𝑑𝑘+𝑐2×𝑟2𝑗𝒑𝑔𝑑𝑘−𝒙𝑖𝑑𝑘⋯⋯⋯1𝒙𝑖𝑑𝑘+1=𝒙𝑖𝑑𝑘+𝒗𝑖𝑑𝑘+1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2其中𝑖=1,2,⋯,𝑁;𝑗表示粒子的第𝑗维，𝑘表示迭代次数，𝑐1,𝑐2为了加速常数，一般在0~2之间取值。𝑐1主要是为了调节粒子自身的最好位置飞行的步长,𝑐2是为了调节粒子向全局最好的位置飞行的步长。𝑟1𝑗,𝑟2𝑗∈𝑢0,1为两个相互独立的随机函数。为了减少在进化过程中粒子离开搜索空间的可能性,𝒗𝑖𝑑通常限定在一定范围内，即𝒗𝑖𝑑∈𝒗𝑚𝑖𝑛,𝒗𝑚𝑎𝑥22第二章粒子群算法——粒子群算法原理其中：式（1）第一部分𝒘×𝒗𝑖𝑑𝑘为“惯性”部分，反映了粒子的运动“习惯”，表示粒子有维持自己先前速度的趋势；第二部分𝑐1×𝑟1𝑗𝒑𝑖𝑑𝑘−𝒙𝑖𝑑𝑘为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，表示粒子有向自身历史最佳位置靠近的趋势；第三部分𝑐2×𝑟2𝑗𝒑𝑔𝑑𝑘−𝒙𝑖𝑑𝑘为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，表示粒子有向群体或邻域历史最佳位置逼近的趋势。23第二章粒子群算法——粒子群算法原理①初始化粒子群，包括群体规模𝑁，每个粒子的位置𝑥𝑖和速度𝑣𝑖；②计算每个粒子的适应度值𝐹𝑖𝑡𝑖；③对每个粒子，用它的适应度值𝐹𝑖𝑡𝑖和个体极值𝑝𝑏𝑒𝑠𝑡(𝑖)比较，如果𝐹𝑖𝑡𝑖𝑝𝑏𝑒𝑠𝑡(𝑖)则用𝐹𝑖𝑡𝑖替换掉𝑝𝑏𝑒𝑠𝑡(𝑖)；④对每个粒子，用它的适应度值𝐹𝑖𝑡𝑖和全局极值𝑔𝑏𝑒𝑠𝑡(𝑖)比较，如果𝐹𝑖𝑡𝑖𝑔𝑏𝑒𝑠𝑡(𝑖)则用𝐹𝑖𝑡𝑖替换掉𝑔𝑏𝑒𝑠𝑡(𝑖)；⑤根据公式更新粒子的速度𝑣𝑖和位置𝑥𝑖；⑥如果满足结束条件(误差足够好或到达最大循环次数)执行步骤⑦，否则返回②；输出gbest。24第二章粒子群算法——粒子群算法原理开始计算每个粒子的适应值初始化每个粒子的速度和位置开始求出每个粒子的个体最优依据方程对粒子的位置进行进化依据方程对粒子的速度进行进化求出整个群体的全局最优值是否满足结束条件输出结果是否25第二章粒子群算法——粒子群算法应用Matlab粒子群工具箱（PSOt）提供了非常先进的粒子群优化算法，可指定惯性因子的起始值和中止值，可约定各维变量的取值范围、粒子在遇到边界时是否反弹等各种参数。除此以外，粒子群工具箱既可以在用户约定的范围内自动随机生成指定群体规模的初始粒子群，也可人工输入小于群体规模的任意数目的初始粒子，具备非常强的灵活性。下载网址：第二章粒子群算法——粒子群算法应用PSOt具有非常强的灵活性，在实际计算中，用户只要根据需求编写好目标函数，并设置好函数自变量的取值范围和每步迭代允许的最大变化量，PSOt即可自动进行优化计算。该工具箱的使用方法主要分为一下几个步骤：（1）在MATLAB的命令窗口中点击“File”，“SetPath”，设置已下载好工具箱的路径。27第二章粒子群算法——粒子群算法应用PSOt具有非常强的灵活性，在实际计算中，用户只要根据需求编写好目标函数，并设置好函数自变量的取值范围和每步迭代允许的最大变化量，PSOt即可自动进行优化计算。该工具箱的使用方法主要分为一下几个步骤：（1）在MATLAB的命令窗口中点击“File”，“SetPath”，设置已下载好工具箱的路径。（2）编写待优化的函数（test_func)，保存为同名m文件28第二章粒子群算法——粒子群算法应用PSOt具有非常强的灵活性，在实际计算中，用户只要根据需求编写好目标函数，并设置好函数自变量的取值范围和每步迭代允许的最大变化量，PSOt即可自动进行优化计算。该工具箱的使用方法主要分为一下几个步骤：（1）在MATLAB的命令窗口中点击“File”，“SetPath”，设置已下载好工具箱的路径。（2）编写待优化的函数（test_func)，保存为同名m文件（3）调用粒子群算法的核