嵌套分割算法_一种新的并行随机优化算法

收稿日期: 2006202228; 修返日期: 2006205225 基金项目: 国家自然科学基金资助项目 ( 70371070 );上海市重点学科建设资助项目 ( T0502) 作者简介:张林刚 ( 19682 ),男,甘肃靖远人,博士研究生,主要研究方向为系统 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 、系统优化 ( forestgang@ 163. com);严广乐 ( 19572 ),男,广东 南海人,教授,博士,主要研究方向为系统工程、系统优化;路晓伟 ( 19762 ),男,山东淄博人,博士研究生,主要研究方向为系统优化、客户关系管理. 嵌套分割算法:一种新的并行随机优化算法* 张林刚 1, 严广乐 1, 路晓伟 2 ( 1.上海理工大学 管理学院, 上海 200093; 2.上海交通大学 管理学院, 上海 200030) 摘 要: 嵌套分割算法是一种新的系统优化计算方法,它可以应用于确定型和随机型、离散系统和连续系统的 优化问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。综述了嵌套分割算法的概念原理、方法步骤,介绍了算法的应用情况,并探讨了算法未来的研究方 向。 关键词: 嵌套分割算法; 系统优化; 算法综述 中图分类号: N945. 15 文献标志码: A 文章编号: 100123695( 2007) 0620079203 Nested PartitionsMethod: New Parallel Stochastic Optim ization A lgorithm ZHANG L in2gang1, YAN Guang2le1, LU X iao2wei2 ( 1.Manag emen tSch ool, Un iversity of Shanghai for Science& T echnology, Shangha i 200093, China; 2. Managemen tSch ool, Shangha iJ iao2 tong Un iversity, Shangha i 200030, Ch ina ) Ab stract: Nested Partitions (NP) method is a new system op tmi ization algorithm. It can be used in determ in istic and stochas2 tic optmi ization p roblems of discrete and continuous systems. Th is paper presented the concepts, princ iples, methods and pro2 cedures of nested partitionsmethod systematica lly. Furthermore, d iscussed app lications and further research expecta tions of the NP. Key words: nested partitionsmethod; system op tmi ization; algorithm overview 0 引言 实际的工程应用中有一类复杂的离散时间动态系统优化 问题。由于其状态变量和控制参数通常受随机因素影响,不能 得到具体的函数解析 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式,从而很难对实际系统进行优化分 析。为了解决这类问题,人们设计了很多求解方法 [ 1~ 3] , 但效 果都不理想 [ 4]。嵌套分割算法 (N ested PartitionsMe thod, NP 算法 )是由 L. Shi和 S. 7 lafsson提出的一种新的全局优化算 法 [ 5~ 7]。这种方法对于离散时间动态系统以及组合优化问题 具有很高的求解效率。它把全局搜索与局部寻优结合在一起, 具有开放性、并行性、全局性和易操作性等突出优点;能够解决 许多复杂系统的确定性和随机性优化问题,并且具有很高的计 算效率。NP算法具有广阔的应用前景 ,但国内外对这种方法 的研究才刚刚起步。尤其是国内只有路晓伟、蒋馥的少数几篇 研究论文 [ 8~ 10], 所以有必要对这种方法作出全面介绍, 以便进 行深入研究。 1 算法描述 1. 1 算法的概念原理 对于一个系统优化问题, 设系统变量的有限可行域为 ( , 目标是优化系统的目标函数 f: ( y R, 即 min HI ( f(H) 其中, | ( | < ] 。为便于 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 , 假设该问题有唯一的最优解 HoptI ( ,满足对所有的 HI ( \ {Hopt },有 f (Hopt ) < f (H)。在实践 中, 目标函数 f (H)经常是复杂系统性能指标的测度函数, 而且 没有解析式用以表达系统性能指标与变量之间的解析关系。 在这种情况下, 需要用仿真的方法, 用系统性能指标的仿真结 果Lt (H)来估计 f (H)。嵌套分割算法对目标函数的形式没有 任何限制。 定义 1 一个通过固定分割策略得到的区域称为该策略 下的可行域 (Va lid Region)。对于离散系统, 只含有一个单解 的细分区域称为单解域 ( Singleton Region) 。所有可行域的集 合表示为E 。单解域具有特别的意义,可以将单解域的集合表 示为E 0。 嵌套分割算法的实质是针对可行解的集合,而不是针对单 个可行点。在这点上它是与遗传算法、模拟退火等算法不同 的。嵌套分割算法是对可行域进行反复细分的过程。从整个 可行域 ( 开始,将整个可行域逐渐细分, 直到分为单解域或达 到精度要求为止。 定义 2 由原有限可行域到达一个可行域的分割层数称 为该可行域的深度 (Depth ), 表示为 d: E y N 0。原可行域的 深度为 0,即 d( ( ) = 0。单解域具有最大深度, 因此也被称为 最大深度域。 定义 3 如果一个可行域 RI E 是通过分割可行域 GI E 得来的, 则称 R为 G的子域 ( Subregion), G称为 R的母域 ( Su2 第 24卷第 6期 2007年 6月 计 算 机 应 用 研 究 ApplicationR esearch ofComputers Vo.l 24 No. 6 June 2007 perregion)。定义母域函数映射 s: E y E , 若 R I E \ ( 则 s(R ) = GI E , 当且仅当 R< G。为使定义完整起见, 定义 s( ( ) = ( 。 设定效果函数 I: E y R, 用来选择最有希望包含最优解的 区域 (最可能域 ), 因此称之为品质指标 ( Prom ising Index)。当 系统具有确定的目标函数时, 效果函数 (或品质指标函数 )通 常就是取目标函数。另外, 由于嵌套分割算法具有很大的开放 性, 可以根据需要设定品质指标函数的形式,唯一的要求就是 它要与单解域上的效果函数相一致。 假设经过第 k次重复分割, 得到了最可能域 R ( k) A ( ;然 后把该可行域分割成M R(k)个子域, 并将 R ( k)以外的整个区 域看成一个区域。在每次重复分割时, 都只是考虑M R(k) + 1 个不相交的可行域的子集 (初次分割除外 ), 在得到的每个区 域上利用抽样方法计算该区域的品质指标, 用以比较确定哪 个区域是最可能域。依此重复进行分割, 直到得到不再变化 的单解域为止。如果M R( k)以外的整个区域被认为是最可能 域, 则要回溯到包含当前最可能域的较大区域, 并将其作为 下一步继续分割的最可能域。由于所得到的分割区域是一 层一层嵌套的, 该优化方法被称为嵌套分割 ( Nested Pa rti2 tions)算法。 1. 2 算法的方法步骤 嵌套分割算法包括四个基本算子,即分割 ( Partition)、抽样 ( Samp ling)、选区 ( Selection)、回溯 (Backtrack)。其寻优过程也 是反复使用这四个算子的重复过程。 ( 1)分割 把最可能域 R ( k)分割成MR( k)个子域 R 1 ( k), R2 ( k), , , RM R( k) ( k), 并将 R ( k)以外的所有区域 ( \R ( k)合并为一个区 域。通过以上处理, 共得到 MR( k) + 1个分割区域。在初次分 割开始时, 把整个可行域 ( 看做最可能域, 即 R ( 0) = ( 。由于 其以外的区域为空集 ,在第一次分割时只考虑M ( 个子域。 由于可行域 ( 是有限的,当分割进行到一定时刻, 得到的 分割区域将是单解域, 此时M R(k) = 1, 得到两个区域 R ( k)和 ( \R ( k)。整个嵌套分割算法对最可能域进行的分割过程中, 分割策略应该保持固定。 ( 2)抽样 从每一个由分割算子得到的区域 Rj ( k)中随机选择 N j个 抽样点 H( j )1 , H( j )2 , , , H( j)N j , j= 1, 2, , , M R( k) + 1。由于嵌套分割 算法的开放性, 可以选择多种多样的随机抽样方法来改进算 法, 唯一的要求是每个区域中的每个点被选择的概率大于 0。 ( 3)计算索引值 ,选择最可能区域 假设已经选定了品质索引函数 I: E y R,对于每一个区域 Rj ( k), j= 1, 2, , , M R( k) + 1, 按照设定的抽样策略进行抽样, 并计算每个区域上的品质索引值的估计值。进行比较,求出具 有最小值的区域: jk =^ argm in I^ (Rj ( k) ), j= 1, 2, , , MR( k) + 1 若 jk [^ MR( k) , 即当前最可能域的某一子域具有最小适应 值, 则该子域就是下一步的最可能域;若 jk^ =MR( k) + 1,则下一 步的最可能域需要通过回溯算子来确定。 由于从不同区域中进行抽样,并计算每个区域的品质索引 值的步骤可以同时进行, 该算法在本质上具有并行计算的特 点, 可以很方便地使用并行计算方法来大大提高其计算效率。 (4)回溯 当 R ( k)之外的整个区域被认为是最可能域时 ,需要从当 前最可能域 R ( k)出发,按照事先确定好的回溯原则,回溯到一 个包含当前最可能域的较大区域,并将其作为下一步的最可能 域。回溯原则可以按照需要确定,如可以将当前最可能域的母 域 s(R ( k) )作为回溯对象。此时最可能域的选择可以表示为 R ( k+ 1 ) = R jk^ ( k) 当 jk^[ MR( k)时 s(R ( k ) ) 其他 当然也可以将整个有限可行域 ( 作为回溯对象,即 R ( k+ 1) = ( 。 由新的最可能域 R ( k+ 1)出发,继续进行上述分割、抽样、 选区和回溯四个算子,就得到了一个分割区域的序列。这样可 以一直进行到所有可行域中的点都与单解域相对应,可以将被 认为是最可能域的次数最多的单解域中的点看做是全局最优 解。 2 算法收敛的理论分析 在嵌套分割过程中,算法关心的区域从E 空间中的一个区 域转移到另一个区域。转移所依据的只是当前对各区域的抽 样信息。因此该算法的分割寻优过程就产生了一个以 E 作为 状态空间的马尔可夫链 {R ( k) } ] k= 1 。不难证明, 该马尔可夫链 具有唯一的平衡分布。 定理 1 当且仅当马尔可夫链 {R ( k) }]k= 1的一个状态 NI E 0,并且 N= {H* }时, N是该马尔可夫链的一个吸收态。其中 H* 是原优化问题的全局最优解。 设 N= R ( k) I E 0,且 N= {H* },有 f ( H* ) [ f (H), P HI ( 。 在马尔可夫链 {R ( k) } ] k= 1 中, 由 N状态开始, 下一步仍转移到 状态的转移概率为 PNN= P {I (^N)[ I^ ( ( \N) }= P {f (H* )[ I^ ( ( \N) }= 1 因此 N是一个吸收态。 如果马尔可夫链的起始状态不是最大深度域,它或者会转 移到当前最可能域的一个子域,或是回溯到一个更大的区域, 而转移到同一个状态的概率为 0。所以吸收态必定是最大深 度域。 对不包含全局最优解的的最大深度域 G= {H}I E 0, 存在 H* I ( \G,使得 f (H* ) [ f (H) ,则马尔可夫链从状态 G开始,转 移到 G以外的状态的转移概率为 PG( \G= P {I (^G) > I (^ ( \G) }= P {f(H) > I^ ( ( \G) \ P {H * 被从 ( \ G中随机选择 }> 0 因此 G不是一个吸收态, 而只是一个过渡态。由于全局最优 解所处的最大深度域是马尔可夫链 {R ( k) } ] k= 1 的吸收态, 当马 尔可夫链一经到达这种状态, 它就再也不会转移到其他状态。 马尔可夫链中存在很多过渡态, 所以要经过有限次的转移, 才 能由过渡态到达吸收态 [ 7]。 定理 2 用嵌套分割算法求解最优化问题 H* I arg m in HI ( #80# 计 算 机 应 用 研 究 2007年 f (H)时,它能够在有限步数内以概率 1收敛于全局最优解, 即 存在 K < ] , 使得 P {R ( k) = {H* } }= 1, P k\ K。 这就说明, 嵌套分割算法具有坚实的数学基础。用它来解 决一些复杂的优化问题一定能得到理想的最优解;而且上述理 论分析并没有限制嵌套分割算法的分割策略、抽样策略、品质 索引函数选择以及回溯策略。因此嵌套分割算法具有其他算 法无法比拟的开发性。 3 一个算例 有这样一个组合优化问题 :它的可行域为 G0 = ( = {1, 2, 3, 4, 5, 6, 7, 8}。利用嵌套分割算法求解,分割策略是:每次迭 代将当前最可能域分割成两等份 (图 1)。 图 1 嵌套分割算法示例图 第一次迭代。当前最可能域 G0被分割成两个子域, G1 = {1, 2, 3, 4}和 G2= {5, 6, 7, 8}, G0是它们的母域。分别在子域 G1和 G2中抽样,计算它们的品质索引值。假如对于给定优化 问题, G1的索引值比 G2的索引值来得好, 那么选择 G1作为下 一次迭代的最可能域。 第二次迭代。将当前最可能域 G1分割成两个子域, G3 = {1, 2}和 G4 = {3, 4}。这时分别在 G3、G4以及外围可行域 G2 中抽样, 计算它们的品质索引值。假如 G3的索引值最好,那么 G3是下一次迭代的最可能域。 第三次迭代。将 G3分割成两个子域, G5 = { 1}和 G6 = {2}。这时分别在 G5、G6以及外围可行域 G0 \ (G5 G G6 )中抽 样, 计算品质索引值。假如这时外围区域 G0 \ (G5G G6 )有较好 的品质索引值, 下一次迭代应该回溯到包含 G3的上级最可能 域。G1或 G0进行重新迭代计算,直到最终得到单解域。 4 算法应用及研究前景 嵌套分割算法是一种新型的优化算法,它在处理组合优化 问题时具有很高的计算效率。Shi等人将嵌套分割算法应用于 解决 TSP问题、供应链管理、产品设计以及机器分配等领域, 取得了显著效果 [ 11~ 13]。另外嵌套分割算法有比其他算法更广 泛的开放性, 能够方便地与其他算法结合在一起, 提高计算效 率。 Sh i等人将嵌套分割算法与遗传算法结合起来, 得到了比 遗传算法更好的结果 [ 6]。路晓伟、蒋馥将嵌套分割算法与模 拟退火算法相结合, 提高了算法的计算效率 [ 8, 9]。嵌套分割算 法还具有并行计算的特点,可以使用并行计算技术提高优化效 率。它经过拓展还可以应用于有限区域上的连续系统优化问 题 [ 10]。 嵌套分割算法为解决系统全局优化问题提供了新的选择, 具有广泛的应用前景 ,但对其研究才刚刚开始, 还有许多该算 法的未知领域值得进行深入的探索。¹ 算法的应用。虽然 NP 算法已经有了一些应用研究,但范围还很小, 深度还不够,有关 嵌套分割算法的更广泛深入的应用研究是一项很有意义的工 作。º 是 NP算法的改进研究。嵌套分割算法具有很强的全 局寻优能力, 结合一些具有优良局部寻优能力的算法, 可以对 算法进行有效改良。» 由于嵌套分割算法的分割算子和抽样 算子对算法的有效性起重要作用,所以分割策略和抽样策略的 研究也是一个有趣的研究方向。¼ 虽然嵌套分割算法建立在 一定的数学理论基础之上,但对理论的进一步完善是一项不会 终止的工作。 参考文献: [ 1] GONGW enbo, HO Yuch,i ZHA IW engang. Stochastic comparison algorithm for d iscrete op tim izat ion w ith est imat ion [ J]. S IAM Jou r2 na lon Op tmi iza t io n, 1999, 10 ( 2 ): 3842404. [ 2] YAN D, MUKAI H. Stochast ic d iscrete op tim izat ion [ J ]. S IAM Jou rna lC on tro la nd O p tmi iza t io n, 1992, 30( 3): 5942612. [ 3 ] NORK INGW I, ERMOL IEV Y M, RUSZCZYmSKY A. On opt imal allocation of ind iv isab les under uncertainty [ J ]. O pe ra t io n Re2 s ea rch, 1998, 46: 3812395. [ 4] 7LAFSSON S, SH I L. O rd inal comparison v ia th e Nested Partit ions method [ J]. D isc re te E ven tDynam ic Sys tem s: Theo ry a nd Ap2 p lica tio ns, 2002, 12 ( 2 ): 2112239. [ 5] 7LAFSSON S, SH I L. An in tegrated framework for d eterm in istic and s tochastic opt im ization: proc. of th e 1997W inter Simu lation Con fe2 rence[ C]. [ S. .l ]: [ s. n. ], 1997: 3582365. [ 6] SH I L, 7LAFSSON S, CHEN Q. A new hyb rid op tim izat ion algo2 rithm [ J]. C ompu te rs & Indus tria l E ng inee ring, 1999, 36 ( 2 ): 4092426. [ 7] SH I L, 7LAFSSON S. Nested part it ion smethod for global opt im iza2 tion[ J]. O pe ra tio ns Resea rch, 2000, 48 ( 3): 3902407. [ 8] 路晓伟,蒋馥.系统优化的嵌套分割算法及其改进 [ J ]. 上海交通 大学学报, 2004, 38 ( 3 ): 3942397. [ 9] 路晓伟,蒋馥.基于模拟退火的复合嵌套分割算法 [ J ]. 系统工程 与电子技术, 2004, 26 ( 1 ): 992102. [ 10 ] 路晓伟,蒋馥.连续系统优化的嵌套分割算法实现 [ J ]. 系统工程 理论与实践, 2004 ( 1): 1262129. [ 11 ] SH I L, 7 LAFSSON S, SUN N. New parallel random ized algorithms for th e traveling salesman prob lem [ J ]. Com pu te rs & Ope ra tio ns Resea rch, 1999, 26 ( 4 ): 3712394. [ 12 ] SH I L, CHEN C H, YBCESAN E. Simu ltaneous simu lat ion experi2 ments and nested p artit ion for d iscrete resou rce allocat ion in supp ly ch ainmanagemen t: p roc. of th e 1999W in ter Simu lat ion Conference [ C]. [ S. .l ]: [ s. n. ], 1999: 3952401. [ 13 ] SH I L, 7 LAFSSON S, CHEN Q. An op tim izat ion framework for product design [ J]. Managem en t S cien ce, 2001, 47 ( 12 ): 16812 1692. [ 14] 7 LAFSSON S, SH I L. Stopp ing criterion for a s imulation2b ased opt i2 mization method: proc. of the 1998 W inter Simulation Conference [ C]. [ S. .l ]: [ s. n. ], 1998: 7432750. #81#第 6期 张林刚等:嵌套分割算法:一种新的并行随机优化算法