《运筹学最优化方法复习.docx》由会员分享，可在线阅读，更多相关《运筹学最优化方法复习.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 章 最优化问题的基本概念1.1 最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。1.2 最优化问题的数学模型1.最优化问题的一般形式 findx , x ,L, xmin( 1 , 2 ,L, n )f x xxs.t.1g ( x ,2x ,L,nx ) 0u = 1,2,L, pu 12nh ( x , x ,L, xv 12n) = 0v = 1,2,L, q2. 最优化问题的向量表达式 findXmin f ( X )s.t. G( X ) 0H ( X ) = 0式中： X = x , x12,L, x Tn
2、G( X ) = g ( X ), g12( X ),L, gp( X )TH ( X ) = h ( X ), h ( X ),L, h( X )T12p3. 优化模型的三要素设计变量、约束条件、目标函数称为优化设计的三要素！设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。1.3 优化问题的分类按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：1 按照模型中是否存在约束条件，分为约束优化和无约束优化问题2 按照目标函数和约束条件的性质分为线性优化和非线性优化问题3 按照目标函数个数分为单目标优化和多目标优化问题4 按照设计变量的性质不同分为连续变量优化和离
3、散变量优化问题第 2 章最优化问题的数学基础2.1 n 元函数的可微性与梯度一、可微与梯度的定义1. 可微的定义f ( X 0 + P) - f ( X 0 ) - LT P P设 f ( X ) 是定义在n 维空间 Rn 的子集 D 上的n 元实值函数，且X 0 D 。若存在n 维向量 L ，对于任意n 维向量 P ，都有lim= 0P 0则称 f ( X ) 在 X 0 处可微。2. 梯度设有函数 F ( X ) ， X = x , x12,L, xnT ，在其定义域内连续可导。我们把 F ( X ) 在定义域内某点 X 处的所有一阶偏导数构成的列向量，定义为 F ( X ) 在点 X 处
4、的梯度。记为： FFF TF ( X k ) = x1,L,xx2n梯度有 3 个性质：函数在某点的梯度方向为函数过该点的等值线的法线方向；函数值沿梯度方向增加最快，沿负梯度方向下降最快；梯度描述的只是函数某点邻域内的局部信息。2.2 极小点及其判别条件一、相关概念1. 极小点与最优解设 f ( X ) 是定义在 n 维空间 Rn 的子集 D 上的 n 元实值函数，若存在 X * D 及实数d 0 ，使得X N ( X * ,d ) D( X X * ) 都有 f ( X * ) f ( X ) ，则称 X * 为 f ( X ) 的局部极小点；若 f ( X * ) f ( X ) ，则称
5、X * 为 f ( X ) 的严格局部极小点。若X D ，都有 f ( X * ) f ( X ) ，则称 X * 为 f ( X ) 的全局极小点，若 f ( X * ) 0 都存在k0X k +1 - X * b X k - X *X k 为超线性收敛。 0 ，使当k k0时下式：3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点 x0和初始步长h ，由此可确定两点 x1= x 和 x02= x + h ，通过比较1这两点函数值 f (x ) 、 f (x12) 的大小，来决定第三点 x3的位置。比较这三点函数值是否呈“高低高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻
6、求下一点。进退法依据的基本公式：x = x10x = x + h21x = x + h32具体步骤为：任意选取初始点 x0和恰当的初始步长h ；令 x1= x ，取 x02= x + h ，计算 f (x ) 、 f (x ) ；112若 f ( x ) f ( x12) ，说明极小点在 x2右侧，应加大步长向前搜索。转；若 f ( x ) f ( x ) ，说明极小点在 x 左侧，应以 x 点为基准反向小步搜索。转；1211大步向前搜索：令h 2h ，取 x3= x + h ，计算 f (x ) ；23若 f (x2) f (x )12说明极小点在 x2点右侧，应加大步长向前搜索令h 2h
7、= 2 1 = 2 ，取 x3= x + h = 1 + 2 = 3则 f (x23) = 0Q f (x2) f (x )3说明极小点在 x3点右侧，应加大步长向前搜索舍弃原 x1= 0 的点，令 x1= 1x2= 3 ，则 f (x ) = 4f (x12) = 0令h 2h = 2 2 = 4 ，取 x3= x + h = 3 + 4 = 7则 f (x23) = 16 f (x2) = 0f (x ) 、 f (x12) 、 f (x3) 呈“高低高”排列x ,x13为单峰区间，即区间1，7即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：
8、对称取点的原则：即所插入的两点在区间内位置对称；插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；等比收缩的原则：即每一次区间消去后，单峰区间的收缩率l 保持不变。设初始区间为a，b，则插入点的计算公式为：x = a + 0.382(b - a)1x = a + 0.618(b - a)2黄金分割法的计算步骤如下：给定初始区间a，b和收敛精度e ；给出中间插值点并计算其函数值：x = a + 0.382(b - a)f (x )11；x = a + 0.618(b - a)f (x )22比较 f (x ) 、 f (x12) ，确定保留区间得到新的单峰区间a，b；1收敛性判别：
9、计算区间a，b长度并与e 比较，若b - a e ，输出 x* =否则转；在保留区间内继承一点、插入一点，转。(a + b)2例：使用黄金分割法求解优化问题： min f (x) = x 2 + 2x， - 3 x 5e = 0.2 。解： x1= a + 0.382(b - a) = -3 + 0.382 (5 + 3) = 0.056f (x ) = 0.1151 x = a + 0.618(b - a) = -3 + 0.618 (5 + 3) = 1.9442f (x2) = 7.667 f (x2) f (x )舍弃（1.944，5，保留-3，1.9441.944 - (-3) e
10、；1继承原 x 点，即 x12= 0.056f (x2) = 0.115插入 x1 f (x2= a + 0.382(b - a) = -3 + 0.382 (1.944 + 3) = -1.111f (x ) = -0.9871) f (x )舍弃（0.056，1.944，保留-3，0.0560.056 - (-3) e ；1继承原 x 点，即 x12= -1.111f (x2) = -0.987插入 x1 f (x2= a + 0.382(b - a) = -3 + 0.382 (0.056 + 3) = -1.832f (x ) = -0.3061) e ；1继承原 x2点，即 x1=
11、-1.111f (x ) = -0.9871插入 x2= -1.832 + 0.618 (0.056 + 1.832) = -0.665f (x2) = -0.888 f (x2) f (x )保留-1.832，-0.6651如此迭代，到第 8 次，保留区为-1.111,-0.940- 0.940 - (-1.111) = 0.171 e1 x* = (-1.111 + 0.940) = -1.02552f (x* ) = -0.9993.3 梯度法一、基本思想r对于迭代式 X k +1 = X k + a k S k ，当取搜索方向S k为求解无约束优化问题的梯度法。二、迭代步骤给定出发点
12、X k 和收敛精度e ；= -f ( X k ) 时构成的寻优算法，称计算 X k 点的梯度F ( X k ) ，并构造搜索方向S k = -F ( X k ) ；令 X k +1 = X k + a k S k ，通过一维搜索确定步长a k ，即：min F ( X k + a k S k )求得新点 X k +1收敛判断：若 F ( X k +1 ) e 成立，输出 X * = X k +1 、 F ( X * ) = F ( X k +1 ) ，寻优结束；否则令k k + 1转继续迭代，直到满足收敛精度要求。三、梯度法的特点梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一
13、轮搜索就可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。梯度法中相邻两轮搜索方向相互垂直。3.4 牛顿法牛顿法分为基本牛顿法和阻尼牛顿法两种。对于迭代式 X k +1 = X k + a k S k ，当取a kr 1 且搜索方向 S k= - 2 f ( X k )-1 f ( X k ) 时构成的寻优算法，称为求解无约束优化问题的基本牛顿法；r对于迭代式 X k +1 = X k + a k S k ，取搜索方向S k = - 2 f ( X k )-1 f ( X k ) ，a k 为从 X k出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优化
14、问题的阻尼牛顿法。r搜索方向S k = - 2 f ( X k )-1 f ( X k ) 称为牛顿方向。这里需要注意的是会求海塞阵的逆矩阵。3.5 变尺度法我们把具有 X k +1 = X k - a k Ak f ( X k ) 迭代模式的寻优算法称为变尺度法。其搜索方向表达式为： S k = - Ak f ( X k ) ，称为拟牛顿方向，其中Ak 称为变尺度矩阵。在迭代开始的时候， A0 = I ；随着迭代过程的继续， Ak - 2 f ( X k )-1 f ( X k ) 。因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。3.6 共轭梯度法一、共轭方向的概念设 H
15、为对称正定矩阵，若有两个n 维向量 S 和S12，满足S T H S12= 0 ，则称向量 S1与S 关于矩阵 H 共轭，共轭向量的方向称为共轭方向。2若有一组非零向量 S ， S12矩阵 H 共轭。， Sn满足 ST H Sij= 0 (i j) ，则称这组向量关于对于n 元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多 n 次即可得到极值点。二、共轭方向的形成对于函数 f ( X ) = f (x , x12, x ) =n1 X T HX + BT X + C2沿任意方向S 0 在设计空间上任意做两条平行线，分别与目标函数等值线切于点 X 1 、X 2 ，令S 1 = X 2 -
16、X 1 ，则 S 0 、S 1 关于矩阵 H 共轭。三、共轭梯度法对于迭代式 X k +1 = X k + a k S k ，取搜索方向S k +1 = -f ( X k +1 ) + b S kkf ( X k +1 ) 2f ( X k ) 2其中： S 0 = -f ( X 0 ) ， b=k共轭梯度法相邻两轮搜索方向是一对共轭方向。3.7 鲍威尔法基本迭代公式仍旧是： X k +1 = X k + a k S k基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上的一维搜索。对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。修正鲍威尔法与基本鲍威尔法类似，所不同
17、的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性。注意掌握鲍威尔条件的表达式和应用！ 每环搜索方向组的生成：1. 第一环的搜索方向组就是各坐标轴方向2. 下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是： 若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。下一环搜索起点的确定：下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件， 则以本环搜索终点为起点，沿新生成的方向作一维搜索
18、，得到的新点作为本轮的搜索终点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。这里需要注意的是反射点的计算： X k= 2 X k - X kn+2n0式中： X k是本环起点 X k 相对于本环终点 X k 沿新生成方向的反射点。n+20n例：对于无约束目标函数min f ( X ) = x 2 + 2x 2 - 4x- 2x x，利用修正Powell 法从11X 0 = 出发求最优解。 1211 21解：令 X 1 = X 0 = 1P1 = P 0 = (e , e )0 121 1 + aX
19、1 = X 1 + a0 = 1 10 3令 f ( X 1 ) = 0得：a = 2则： X 1 = 110 3 1 X 1 = X 1 + a = 211 1 + a 3 令 f ( X 1 ) = 0得：a = 0.5则： X 1 = 1.522 3 1 2 该环生成的新搜索方向为： S 1 = X 1 - X 1 = 1.5 - 1 = 0.520 对S 1进行有效性判别： 反射点 X 1 = 2 X 1 - X 1 = 2 3 - 1 = 51.512420 f = f ( X 1 ) = -3f102= f ( X 1 ) = -7.5f23= f ( X 1 ) = -74D =
20、 f ( X 1 ) - f ( X 1 ) = -3 - (-7) = 4 ， D = f ( X 1 ) - f ( X 1 ) = -7 - (-7.5) = 0.5101212故最大下降量Dm= D = 411故： f3 f 和( f11- 2 f2+ f )( f - f312- D )2 0 时 f ( X , r k ) = 12122x 2 + x 2 - 2x + 1当3 - x 0时1212令 f = 2x - 2 = 0x11f = 2x + 2r k (x - 3) = 0x2213r k得： x = 1x = x* = 1x* = lim x = 3f (x* ) =
21、 9121 + r k12k 2二、内点法构造惩罚函数：f ( X , r k ) = f ( X ) - r kpu=11g ( X )u或：f ( X , r k ) = f ( X ) - r kpu =1ln-gu( X )内点法只能处理不等式约束优化问题，不能处理等式约束优化问题。需要注意的是：惩罚因子 r k 随迭代次数的增加是递减的，当 r k 0 时得到的解就是原问题的最优解。例：用内点法求解约束优化问题min f ( X ) = x + x12s.t.x 2 - x 012- x 01解：构造惩罚函数f ( X , r k ) = x + x - r k lnx - x 2
22、- r k ln x12211f- 2x1令x = 1 - r k x121- x 21- r k = 0x1f1= 1 - r k = 0xx22- x 211 + 8r k - 1( 1 + 8r k - 1) 2得 x =， x =14216+ r k0当rk 0 时，得 x* = 0f ( x* ) = 0 三、混合法构造惩罚函数：f ( X , r k ) = f ( X ) - r k1pu =11g ( X )u+ r k2qv=1h ( X )2vp或：f ( X , r k ) = f ( X ) - r k 1ln-gu( X ) + r k q2h ( X )2v混合法的
23、特点是：对于不u等=1 式约束按照内点v=法1构造惩罚项，对于等式约束按照外点法构造惩罚项。混合法既可以处理不等式约束优化问题，也可以处理等式约束优化问题。例：用混合惩罚函数法求解约束优化问题min f ( X ) = x 2 - 3x12- x 22s.t. 1 - x 01x = 021解：构造惩罚函数f ( X , r k ) = x 2 - 3x - x 2 - r k ln1 - x -x 21222x + r k11r k2令f ( X , r k ) = 11 - x12x = 0- 3 - 2x2 +1 1 + 2r k得： x =， xr 2 k=31221 2( 1r k-
24、1)当rk 0 时，得 x* = 0f (x* ) = 1 第 5 章遗传算法本章要求重点掌握遗传算法的 5 个要素、遗传算法的寻优机制。一、遗传算法的 5 个要素1.编码将优化问题的解编码，用以模拟生物个体的基因组成； 2.初始种群生成将优化问题多个随机可行解汇成集合，用以模拟进化的生物种群； 3.个体适应度评估将优化问题目标函数加以变换，生成适应度函数来评价种群个体的适应度，用以模拟生物个体对环境的适应能力；4. 遗传操作包含选择、交叉、变异选择：一种使适应度函数值大的个体有更大的存活机会的机制，用以模拟环境对生物个体的自然选择；编码初始群体的生成结束是群体中个体适应度函数的评估收敛？否选
25、择交叉遗传操作变异基本遗传算法流程图交叉：不同个体间相互交换信息，用以模拟高级生物有性繁殖过程中的基因重组过程；变异：模拟生物在遗传过程中基因复制差错而产生新个体的现象。5. 控制参数的设定种群规模： M = 30 160 ；交叉概率： pc= 0.4 0.99变异概率： pm= 0.0001 0.1最大进化代数： T = 100 1000二、遗传算法的寻优机制寻优机制见右侧的基本遗传算法流程图。仔细看看遗传算法人工模拟进化的例题。作业练习：1. 确定下列函数的初始区间。 min f (x) = x3 - 6x取 x01= 2.2 ， h = 0.8答案：0.8，2 min f (x) =x
26、2 - x取 x40= 0.5 ， h = 0.3答案：0.8，2.6112. 用黄金分割法求解min f (x) = x3 - 6x ，取e = 0.3、初始搜索区间0.8，2。x* =(a + b) = (1.2584 + 1.5416) = 1.4f (x* ) = -4.256223. 用梯度法求解min f ( X ) = x 2 + 4x 2 ， X 0 = 4,4T （做两轮迭代）10.4723答案： X * = X 2 = 0.45312f ( X * ) = f ( X 2 ) = 1.04434. 用阻尼牛顿法求解min f ( X ) = x 2 - 2x x+ 1.5x
27、 2 + x- 2x， X 0 = 1,2T1/ 211 22121答案： X * = X 1 = f ( X * ) = f ( X 1 ) = -3 / 45. 用共轭梯度法求解min f ( X ) = x 2 + x 2 - x x- 10x- 4x， X 0 = 1,1 T8121 212答案： X * = 6f ( X * ) = -52 6. 用 Powell 法求解min f ( X ) = x 2 + x 2 - x x- 10x- 4x， X 0 = 1,1T （迭代 2 轮，计算1过程中小数点后面保留 3 位）7.998821 212答案： x* = 5.999 6f ( X * ) = f ( X 2 ) = -52 7. 用外点法求解： 2 min f (x) = x 2 + 2x 2 3 212答案： x* = ，f (x* ) =s.t. x + x12-1 01 33 8. 用混合罚函数法求解：min f (x) = x - x121 s.t. - ln x 0答案： x* = 0f (x* ) = 11x + x12- 1 = 0