一种改进的单纯形优化算法及其仿真研究.docx

一种改进的单纯形优化算法及其仿真研究罗文广( 广西工学院电子信息与控制工程系 ,广西 柳州 545006)摘要 :研究一种收缩系数和扩展系数适时适当变化的单纯形优化学习算法 。用 MATLAB 语言编制仿真程序 ,该程序简单 、通 用 。仿真结果表明 ,该算法与 N - M 法相比 ,有效地提高了寻优速度 。关键词 : 单纯形法 ;收缩系数 ;扩展系数 ;仿真程序中图分类号 :O224文献标识码 :An +11引言1947 年 Dantzig 提 出 单 纯 形 算 法 后 , 使 最 优 化 理 论 成 为 一门独立的学科 。1965 年 Nelder 和 Mead 提出了下降单纯形法 ( N - M 法 ) , 使 单 纯 形 法 变 得 有 效 、实 用 ; 1981 年 D. A.Walmsley 对 N - M 法进行了一些修改 。目前 ,单纯形法作为 一种能实现全局优化的算法 ,在线性规划 、神经网络等方面获得较广泛的应用 。本文研究在算法的寻优过程中使收缩系数和扩 展 系 数 适 时 适 当 地 变 化 , 以 提 高 寻 优 速 度 , 并 用MATLAB 编制相应的程序进行仿真研究 。 1ViVh =(5)ni = 1i hVR= Vh + ( Vh - V h )Vh 的反射点 :(6)hRERVh = Vh + ( V h - Vh )Vh 的扩展点 :(7)VC= Vh + Vh - Vh()( )Vh 的收缩点 :8h式中 、分别为反射系数 、扩展系数和收缩系数 , 且 =1 , 2 3 , 0. 5 0. 75 。 寻优过程的结束条件为 : 12单纯形优化算法基本原理 12 n +1 1 2n + 1 f ( Vi ) - f ( Vh ) 2 (9)N - M 法的基本原理是 : 在 n 维空间中 ,用 n + 1 个顶点构成一个多面体 ,即单纯形 ,然后根据一些简单的规则 ,不断 改变单纯形的顶点 ,使单纯形朝着目标函数 ( 准则函数) 最小的方向移动 ,最后找到函数最小值的近似解 。改变单纯形顶 点有三种方法 ,即反射 、扩展和收缩 。在以后的描述中作以下设定 :设准则函数 f : Rn R 在取最小值周围连续 , Vi Rn , ( i= 1 , 2 , , n + 1) , 为单纯形的 n + 1 个顶点 , 且i = 1式中 为给定常数 。3改进方法在应用单纯形优化算法时 , 初始顶点 、扩展系数和收缩系数取值不同 , 对算法的收敛速度有较大的影响 , 一般的做法是 :扩展系数和收缩系数分别固定取为 2 和 0. 5 ;而初始顶点取i - 1法如下 : V1 随机取 , 其他顶点按 V1 + s q , q , p , q , q Tf i = f ( Vi ) ( i = 1 , 2 , , n + 1)(1)ss(n + 1 + n - 1) , q =(n + 1 - 1)计算p =n 2n 2f h = f ( Vh )(2)f h = max f i ,or1 i n +1( s 为给定的单纯形边长) 。实际应用时 , 若收缩系数过大 , 一方面很容易使准则函数超出极小值区域 ; 另一方面 , 容易使 各顶点的准则函数值在某一个值附近振荡 , 用式 (9) 计算可 知寻优过程没有获得极小值时就结束 ; 若收缩过小 , 寻优速度慢 , 迭代次数过多 。扩展系数也存在同样的问题 。f l = min f i ,or1 i n +1f l = f ( Vl )(3)f p = max f i ,or1 i n +1i hf p = f ( Vp)(4)这里 , Vh 是准则函数最大时对应的顶点 ( 最坏点) , Vl 是准则函数最小时对应的顶点 ( 最好点) , Vp 是准则函数为次大值时 对应的顶点 , Vh 是 Vi ( i = 1 , 2 , , n + 1 , i h) (不包含 Vh ) 的重心 , 为一般而言 , 沿着 ( V - V 方向准则函数 f V 是下降的 ,h )( i )因而沿着 ( V - V 方向进行一维搜索 , 总会获得一个最佳的收缩系数 , 用公式可表为 :h )f V + ( V - Vh ) = min f V + 0 ( V - Vh ) ( 10)通过迭代 , 最终会获得一个最佳的收缩系数 0 。但是为了获得该系数而进行多次迭代 , 实际上也就使算法的寻优过 程减慢 。因此 , 对上述原理进行简化处理 , 即根据反射点准则基金项目 :本研究受广西自然科学基金资助 ( 桂科自 0066005)收稿日期 :2002 - 11 - 15 62函数的大小 , 采用 if t hen 的形式 , 选择适当的收缩系数 。具xshu) 。定义了两个函数参数 v 和 xshu 。其中 v 为顶点向量或矩阵 ,如果顶点是一维的 ,则 v 为行向量 ;如果顶点是 m 维 的 ,则 v 为 m ( n + 1) 矩阵 ,每个顶点是 m 维的列向量 。xshu为行向量 ,xshu (1) 为给定常数 , xshu ( 2) 为单纯形棱长缩边 系数 ,xshu (3) 为反射系数 ,xshu (4) 为扩展系数 ,xshu (5) 为收缩系数 。这里需要说明的是 ,本仿真程序编写成 N - M法和改进后的算法通用的程序 。当给 xshu (4) 和 xshu (5) 输入 值时为 N - M 法 ,否则为改进的算法 。体可以描述为 :如果 f ( VR ) f , 则需要进行收缩处理 ; 再与hp最大点准则函数 f h 进行比较 , 如果大得很多 , 则收缩可大些(即收缩系数取小些) ; 如果比较大 , 则收缩系数取得适中 ; 如 果大得不多 , 则收缩系数可取大些 。根据该思想 , 在具体编程实现时 , 根据需要可进行更细的区分和比较 , 有更多的收缩 系数可选 。进行扩展时 , 采用同样的思想选择扩展系数 。具体可以描述为 :如果 f ( VR ) f , 则需要进行扩展处理 ; 再进行细分2) 准则函数也定义为函数形式 。可输入不同的准则函h l比较 , 如果小得很多 , 则扩展可大些 ( 即扩展系数取大些) ; 如果不是很小 , 则扩展系数取得适中 ; 如果小得不多 , 则扩展系 数可取小些 。修改后的单纯形算法流程图如图 1 所示 。数进行仿真 。3) 各顶点的准则函数值用向量 f 保存 , 同时为了以后编 程方便 , 各顶点函数值按由小到大排列 , 即 f ( 1) 最小 , f ( n +1) 最大 。对准则函数值的排序只需简单地使用 MATLAB 提供的排序函数 sort 即可完成 。准则函数值用向量 f 重新排序 后 ,顶点矩阵 v 也需要重新排列 ,即 v ( : ,1) ( 即第一列) 为最 小值顶点 ,v ( : , n + 1) (即最后一列) 为最大值顶点 。用以下 简洁的编程实现 。ff = f ; %函数值暂存f = sort (f) ; %对各顶点函数值由小到大进行排列for i = 1 : n for j = 1 : nif f (i) = = ff (j) %搜索函数值排序前的位置vv ( : ,i) = v ( : ,j) ; %将顶点存入矩阵 vv 中与 f (i) 对应的 列中ff (j) = 1010101010 ; %取代原函数值 ,避免有相同函数值时的重复比较break %跳出内循环end end endv = vv ; %获得重新排列后顶点矩阵4) 收缩系数和扩展系数的适时适当变化 ,采用 if 语句即 可实现 。收缩系数变化的编程如下 :if fvr f ( n) %反射点函数值在次最大点和最大点函数 值之间vc = av + 0. 6 3 (v ( : , n) - av) ; %则 ,收缩系数取 0. 6 计 算收缩点elseif fvr 2 3 f ( n) %反射点函数值在最大点和两倍最大点函数值之间vc = av + 0. 5 3 (v ( : ,n) - av) ; %则 ,收缩系数取 0. 5elseif fvr 3 3 f ( n) %反射点函数值在两倍最大点和三倍 最大点函数值之间vc = av + 0. 4 3 (v ( : ,n) - av) ; %则 ,收缩系数取 0. 5elsevc = av + 0. 3 3 (v ( : ,n) - av) ; %反射点函数值大于三倍 最大点函数值 ,取 0. 3end 63图 1 改进的单纯形算法流程图4仿真程序和仿真结果4. 1 仿真程序仿真程序根据图 1 用 MATLAB 语言编写 。对程序 做 如 下说明 :1) 将程序编成函数形式 。定义为 :function y = simplex ( v ,4. 2 仿真结果取以下准则函数进行仿真研究 。组初始顶点 ( 即四种情况) , = 0. 0001 , 对改进算法和 N - M法进行仿真 , 仿真结果如表 1 所示 。进行 N - M法仿真时 ,固 定为 2. 0 ,则从 0. 1 0. 9 分别取不同的值 , 因篇幅所限 , 表1 只给出 0. 4 0. 7 的结果 。改进算法中 和分别按 1. 6 、2 、2. 6 和 0. 3 、0. 4 、0. 5 、0. 6 适时变化 。minf ( x) = 64 - 10 x1 - 4 x2 - 4 x3 + x2 + x2 + x2 + x x1 2 3 1 2(11)该函数的最小值为 8 , 最好点为 x = ( 8 , 6 , 2) T 。随机取四表 1 两种算法的仿真结果根据仿真结果 ,得以下结论 :1) 无论取何初始顶点 ,改进算法的寻优次数基本都比 N- M 法少 ,即改进算法的寻优速度较快 。该结果也说明改进 算法对初始顶点没有约束 。2) 采用 N - M 法 ,式 ( 9) 作为寻优的结束条件 ,在收缩系 数和扩展系数选取不合适时 ,容易造成各顶点的函数值十分接近 ,使式 (9) 成立 ,从而寻优过程在没有找到最好点的时候 结束 。改进算法则不会出现这种现象 ,说明改进算法更容易收敛和更有效 。度 ;同时 ,用 MATLAB 编制的仿真程序简单和通用 ,为研究算法及其应用提供一条捷径 。参考文献 :1杨华中 ,汪惠. 数值计算方法与 C 语言工程函数库 M . 北京 :科学出版社 ,1996 . 358359 .赵振宇 ,徐用懋. 模糊理论和神经网络的基础与应用M. 北京 :清华大学出版社 ,1996 . 108110 .2 作者简介 罗文广 ( 1967 - ) , 男 ( 汉 族) , 湖 南 衡 东 县 人 , 副 教 授 ,硕士 ,主要从事电子技术应用 、智能控制 、微机控 制技术的教学和研究工作 ,发表论文四十余篇 。5结束语综上所述 ,在单纯形优化算法的寻优过程中 ,使收缩系 数和扩展系数适时适当地变化 ,有效地提高了算法的寻优速Research on An Improved SimplexAlgorithm and its SimulationLUO Wen - guang(Dept . of Electronic and Control Engineering of Guangxi University of Technology , Liuzhou Gunagxi 545005 ,China)ABSTRACT :A kind of simplex algorithm that its constringency coefficient and expanding coefficient are been changing appropriately in theprocess of searching optimization values is developed. The simulation program is compiled with MATLAB , and is very simple and universal . The simulation results show that the improved algorithm has faster rate of searching optimization values comparing with N - M algorithm. KEYWO RDS :Simplex Algorithm ; Constringency Coefficient ; Expanding Coefficient ; Simulation Program(上接第 54 页)( School of Hydropower & Digitalization Engineering of HUST , Wuhan Hubei 430074 , China)ABSTRACT :The paper analyses the architecture of web computation based on component and its key techniques ,then discussing the applic