各种优化算法求解函数优化问题.doc

1、各种优化算法求解函数优化问题.doc 各种优化算法求解函数优化问题 1. 遗传算法 的简单介绍及流程 1.1 遗传算法的基本原理 遗传算法( genetic algorithm ,简称 ga) 是近年来迅速发展起来的一种全新的随机搜索优化算法。与传统搜索算法不同,遗传算法从一组随机产生的初始解(称为群体)开始搜索。群体中的每个个体是问题的一个解,称为染色体。这些染色体在后续迭代中不断进化,称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体,称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代群体,再继续进化,这样经

2、过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解。遗传算法中使用适应度这个概念来度量群体中的各个个体在优化计算中有可能达到最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关。 1.2 遗传算法的流程 第一步：确定决策变量及各种约束条件，即确定出个体的表现型x和问题的解空间； 第二步：确定出目标函数的类型，即求目标函数的最大值还是最小值，以及其数学描述形式或量化方法，建立其优化模型； 第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x和遗传算法的搜索空间。 第四步：确定解码方法，即确定出个体的基因型x和个体的表现型x的对

3、应关系或转换方法； 第五步：确定个体时候适应度的量化评价方法，即确定出由目标函数f(x)值到个体适应度f(x)的转换规则； 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法； 第七步：确定出遗传算法的运行参数，即确定出遗传算法的m、t、pc、pm等参数。 1.3 遗传算法求解函数优化问题 中的参数分析 目前，函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用范例。对于函数优化中求解实数型变量的问题，一般采用动态编码和实数编码的方法来提高其搜索效率，所以是求解各类函数优化问题比较适合的算法。 1.3 .1 编码方案 在用遗传算法求解函数优化问题时

4、，把解空间中的数据点都映射到遗传中对应的基因型数据，采用二进制编码，在给定函数的变量上下界和编码精度内，求得单个变量的编码长度l ，然后随机生成一些固定长度为 l 的二进制数作为作为初始种群。 1.3.2 适应度函数 先用解码函数将二进制代码转换为解空间中的数据，把数据带入测试函数中，得到种群中每个个体的适应值，然后以种群中函数值取得最大值的个体的函数值与每个个体的函数值之差，再与最大函数值的n倍(假设种群粒子数为n)和种群中所有个体的函数值之和的比值，得到每个个体的适应度。如果求函数最小值问题，则适应度值越大其函数值越小。 1.3.3 选择算子 遗传算法最常用的选择策略就是正比选择策略，即每

5、个个体被选中进行遗传运算的概率为该个体的适应值和群体中所有个体适应值总和的比例。对于个体i，其适应度值为f i ，种群规模为np，则该个体的选择概率可以表示为 å=npiiiiffp1 得到选择概率后，采用旋轮法来实现选择操作，令 pp 0 =0 å=ijj ipp pp1 共转轮 np 次，每次转轮时，随机产生 ) 1 , 0 ( ukÎ x ，当 k ipp x £-1pp i ,则选择个体 i。适应度越高的个体的选择概率越大，越容易被选择参与交叉变异运算。 1.3.4 交叉 算子 在遗传算法中，最常用的交叉策略就是单点交叉和双切点交叉。在这个算法中

6、，先从种群中随机选择两个要进行交叉的个体，然后随机生成一个数据点，对两个父串中对应位的数值进行交换，得到两个字串。 1.3.5 变异算子 变异是在种群中按照变异概率p m 任选若干基因位改变其位值，对于0-1编码来说，就是反转位值。在这个算法中，先在父串中随机生成一个数，如果这个数对应的位值为0，则将它变为1；如果这个数上的位值为1，则将它变为0. 1.4 遗传算法求解函数优化问题流程 step 1：初始化选择、交叉、变异概率，设置初始代数和最大迭代次数，随机生成若干个初始个体构成初始种群； step 2：利用解码函数将初始种群的二进制编码转化为解空间中便于计算的数据，然后用测试函数以及适应度

7、函数求得每个个体的适应度。 step 3：采用轮盘赌选择种群中的个体进行遗传运算； step 4：对种群中的个体进行交叉，变异运算，产生下一代新的种群。 step 5：如果当前的迭代次数达到设置的最大迭代次数，则算法停止，进行step 6；若未达到最大迭代次数，则转入step 2. step 6：保存种群中每一代的选择函数值最小个体作为最优个体，并保存其对应的函数值。 1.5 测试函数运行结果 及算法参数对结果影响分析 1.5.1 各种函数测试结果 （1 1 ） quadric 函数 状种群动态 变化图( (- - 100,100) 第1代种群动态变化图 第50代种群动态变化图 第100代种群

8、动态变化图 第200代种群动态变化图 （ （2 ）tablet 函数测试种群变化图(-100,100) 第1代种群动态变化图 第50代种群动态变化图 第100代种群动态变化图 第200代种群动态变化图 （ （3 ）rosenbrock 测试函数的种群动态变化图 第1代种群动态变化图 第50代种群动态变化图 第100代种群动态变化图 第200代种群动态变化图 (4) griewank函数种群动态变化图 第1代种群动态变化图 第50代种群动态变化图 第100代种群动态变化图 第200代种群动态变化图 名称 最优值 最差值 目标平均值 tablet 2.2737e-009 0.2951 0.0015

9、 quadric 3.7719e-005 29.7138 1.7039 rosenbrock 1.7771e-007 3.8917 0.4625 griewank 0.0235 1.6926 0.0281 rastrigin 3.0273e-006 2.1965 0.0487 schaffers 2.0231e-010 1.0e-003* 0.9379 0.1470 从上面的实验结果中，我们可以发现遗传算法在求解函数优化问题时，对于大部分测试函数，搜索速度都比较快，能很快收敛到最优解上，获得的最优解也比较好，因此是一种比较有效的优化算法。 2. 粒子群算法求解函数优化问题 2.1 粒子群算法介

10、绍 粒子群算法是一种基于迭代的优化方法。进行优化时，粒子在一个 n 维空间中搜索，每个粒子的位置对应于问题的一个解，粒子通过不断调整自己的位置来搜索新解。每个粒子根据自己的飞行经验和其他粒子的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历的最好位置，就是粒子本身找到的最优解，称为个体极值（p best ）;整个种群所经历过的最好位置，就是整个群体目前找到的最优解，称为全局极值（g best ）。每个粒子都通过上述两个极值不断更新自己，从而产生新一代群体。 设粒子的群体规模为 n，粒子当前的位置表示为 ) , ,., , (2 1 knknk k kix x x x x = ， n n nk

11、nl n n u l x , 1 , , £ £ Î 和 un 分别表示第 n 维空间的上下边界；当前速度表示为kiknknk kiv v v v v ), ,., ,., (1= 被钳位在最大值 ) ,., ,., (max, max, 1 max, maxknknk kv v v v = 和最小值) ,. ,. (m i n, m i n, 1 m i n, m i nknknk kv v v v = 之间，粒子的速度和位置更新方程如式（1）和式（2）所示： ) ( ) (2 2 1 11 kikgkikikikix p r c x p r c v v - +

12、 - + =+ （1） 1 1 + + =kikikiv x x （2） 其中，kgkip p , 分别表示粒子第 k 次迭代的个体极值点位置和全局极值点位置。c1,c2 为常数，称为学习因子，用来调节向 pi 和 pg 方向飞行的最大步长；r1,r2 是（0，1）上均匀分布的随机数；式（1）中第一部分是粒子上一步的速度，表明粒子目前的状态；第二部分是粒子对本身的思考，是认知部分，粒子通过对本身位置的思考来调整自己下一步的速度和位置，这样可以是粒子有足够强的全局搜索能力，避免陷入局部最小；第三部分表示粒子通过与其他粒子之间进行信息交流来更新自己的下一步。 2.2 基本粒子群算法流程 （1）在初

13、始化范围内，对粒子群进行随机初始化，包括随机位置和速度。 （2）计算每个粒子的适应值。 （3）对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置 （4）对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最好位置。 （5）根据上面公式（1）和（2）更新粒子的速度和位置。 （6）若未达到终止条件，则进行步骤（2）。 一般将终止条件设定为一个足够好的适应值或达到一个预设的最大迭代次数。 2.3 粒子群算法求解函数优化问题的参数分析 2.3.1 编码方法 在用粒子

14、群求解函数优化问题时，采用实数编码来表示解空间内的粒子的位置，开始时随机初始化n个二维解空间内的数据点，这些数据点对应了每个粒子的位置。粒子的速度也是随机产生的，与粒子的位置的维数相同。 2.3.2 适应度函数 这里用测试函数作为目标函数来对算法进行评价，把每个粒子的位置带入测试函数，得到每个粒子的适应值，然后分别与粒子的个体极值以及种群中所有粒子的全局极值进行比较，如果比当前的个体极值好，就更新这个个体的个体极值的位置pbestpop以及对应的个体极值pbestfit，如果比上一代得到的全局极值好，则更新当代的全局极值的位置gbestpop以及对应的全局极值gbestfit。 2.4 标准粒

15、子群算法的几种改进方法 惯性权重法：惯性权重 w 是与前一次速度有关的一个比例因子，其速度更新方程为： ) ( ) ( *2 2 1 11 kikgkikikikix p r c x p r c v v - + - + =+w 用惯性权重来控制前面的速度对当前速度的影响，较大的 w 可以加强 pso 的全局搜索能力，而较小的 w 能加强局部搜索能力。基本的 pso 可以看作 w=1，因此在迭代后期缺少局部搜索能力。通常取 w 为0.8,1.2之间的数。 2.5 5 粒子群算法测试函数结果 2.5 .1 利用标准 pso 算法对测试函数结果 根据粒子群求解函数优化算法的流程，编写程序pso.m文

16、件，然后用函数来测试算法的好坏优劣。下表中列出了常用的几个测试函数： 对上表中几个测试函数用标准粒子群算法求最优值，设定群体规模为 50，最大速度vmax=0.5，迭代次数 n=200，学习因子 c1=c2=2，画出种群的动态变化图。 （1 1 ） quadric 函数状态变化图( (- - 100,100) 第1代种群变化图 第50代种群变化图 第100代种群变化图 第200代种群变化图 （2 2） ）rastrigin 的测试函数( (- - 5.12,5.12) 第49代种群动态变化图 第99代种群动态变化图 第200代种群动态变化图 （3 3 ） tablet 函数( (- - 100

17、,100) 第49代种群动态变化图 第99代种群动态变化图 第200代种群动态变化图 从以上三个函数的种群动态变化图可以看出，粒子在200代的时候已经将近收敛于一个点了。 （4 4 ）标准 pso 算法测试函数得到的结果 名称 最优值 最差值 目标平均值 tablet 6.9977e-010 0.0935 5.8828e-004 quadric 9.7719e-010 0.5134 0.0090 rosenbrock 1.1286e-008 2.0589e-007 0.0024 griewank 9.0223e-008 3.8537e-007 0.0051 rastrigin 2.0283e-

18、008 0.0874 0.0026 schaffers 5.6037e-009 8.4428e-006 8.8449e-007 2.4.2 用改进的粒子群算法测试函数运行结果 （1）用带惯性权重的粒子群来求解函数的最小值， w 的值是随机生成的(0,1)之间的数。下表就是测试结果： 名称 最优值 最差值 目标平均值 tablet 2.9455e-010 0.0266 6.6766e-004 quadric 1.5761e-009 1.2119 0.0117 rosenbrock 1.4386-012 0.02568 0.02641 griewank 1.9839e-009 4.2095e-00

19、4 3.4790e-004 rastrigin 3.0255e-006 0.5047 0.0044 schaffers 2.3281e-007 1.1189e-006 4.1312e-005 (2)用带收缩因子的改进粒子群算法测试函数，收缩因子 l 取(0,1)之间的随机数。测试结 果如下： 名称 最优值 最差值 目标平均值 tablet 1.0901e-005 2.3877 0.0192 quadric 1.2824e-006 1.7284e-005 9.2941e-004 rosenbrock 0.04891-004 0.0532-002 0.06364 griewank 1.5922e-

20、004 0.2197 0.0079 rastrigin 8.2416e-006 2.5299e-004 0.0106 schaffers 1.1029e-006 1.0096e-005 1.4717e-004 4. 模拟退火算法求解 函数优化 问题 4.1 模拟退火算法的基本原理和算法描述 1982 年，kirkpatrick 等将退火思想引入组合优化的领域，提出了一种求解大规模组合优化问题，特别是 np 完全组合优化问题的有效近似解的算法模拟退火算法（simulated annealing algorithm），简称为 sa。 模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳

21、特性在解空间中随机寻找目标函数的全局最优解，在局部优解处能概率性地跳出并最终趋于全局最优。 基于 metropolis 接受准则的优化过程，可避免搜索过程陷于局部极小，并最终趋于问题的全局最优解。 模拟退火算法包括四个要素： （1）系统状态(configuration)：即在某一个温度下，系统产生的初始解，并当作目前的现行解。 (2)搜寻法则(search rule)：在退火的过程中，由目前系统状态经由随机扰动而产生变化跳至另一种状态。一般而言，sa 较常用的有梯度搜寻法(gradient type) 和迭代改善法。 (3)成本函数(cost function)：用来衡量某一系统状态下之能量函

22、数。 (4)退火程序(annealing process)：退火程序中包含的参数有初始温度、降温机制、冷却率和终止温度。在退火的过程中，在温度高的時候，虽然是较差的目标值，但有可能被接受当成目前的目标值，但随着温度慢慢的降低，接受较差目标值的几率逐渐降低。 4.2 模 模 拟退火算法求解 函数优化 问题算法分析 4.2.1 解空间 模拟退火算法的解空间是随机生成若干个固定上下界的二维数据点，这里采用实数编 码，这些数据点在迭代的过程中会不断移动来寻找最优值。 4.2.2 目标函数 这里用测试函数作为目标函数来对算法进行评价，把每个粒子的位置带入测试函数，得到每个粒子的适应值，在退火的过程中不断

23、寻优，粒子不断更新自己的位置，通过适应值大小的比较来寻找最优值。 4.2.3 算法流程 第 1 步：初始化：初始温度 t，设定终止温度 t 0 和马尔科夫链长度 l，初始化每个粒子的位置。 第 2 步：用测试函数计算每个粒子的适应值。 第 3 步：对 k=1,l 做第 4 步至第 7 步； 第 4 步：对于初始的粒子位置和适应值进行随机扰动，产生新解 s。 第 5 步：计算增量 t d =c（s）-c(s),其中 c(s)为适应度函数。 第 6 步：若 t d 0 则接受 s作为新的当前解，否则以概率 exp(- t d /t)接受 s作为当前粒子新的位置。 第 7 步： 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接