范文一:基于随机_模糊理论的岩体力学参数优化
基于随机 - 模糊理论的岩体力学参数优化
韩磊舒继森舒应秋钱德雨 吕金星
()中国矿业大学
摘 要 岩石样本值既存在随机性 ,又存在模糊性 。用随机 - 模糊处理方法和传统方法对边坡工程中的岩石
力学参数进行分析 ,通过对比可知采用随机 - 模糊处理方法优于传统方法 。此外 ,对岩体力学参数取值臵信度进
行了探讨 ,讨论了岩体力学参数的概率分布形式 ,提出“臵信阈值 ”的概念 ,从而为随机 - 模糊方法在工程实践中的
应用奠定了基础 。
关键词 力学参数 随机 - 模糊法 臵信度 隶属函数
The O p t im iza t ion of Rock M echan ica l Pa ram e ter s Ba sed on Ran dom 2fuzzy Theory
H an L e i Shu J isen Q ian D eyu L u J inxing Shu Yingq iu
( )Ch ina U n iversity of M in ing Technology A b stra c t The va lue s of rock samp le a re random and fuzzy. Bo th of the random 2fuzzy app roach and the trad itiona l
m e thod we re app lied to ana lyze the m echan ica l p a ram e te rs of slop e enginee ring. A fte r comp a rison, it is conc luded tha t the
random 2fuzzy app roach is sup e rio r to the trad itiona l m e thod. A lso, the confidence degree and p robab ility d istribu tion fo rm of
m echan ica l p a ram e te rs we re d iscu ssed. Then, the confiden t th re sho ld concep t wa s p ropo sed so a s to p rovide a founda tion fo r
its app lica tion in enginee ring p rac tice.
Keyword s M echan ica l p a ram e te r, R andom 2Fuzzy M e thod, Confidence, M em be rsh ip func tion s
岩土体力学参数是进行岩土工程稳定性及力学试后凭个人经验确定的 。由于岩体空间分布的不确 分析的基础 。确定岩土力学参数的传统方法有点加 ,使得岩组的划分带有很大的模糊性 ,并由此带 定性
权平均法 、点群中心法和优定斜率法 。实践说明 ,这 来了岩体力学试验参数的模糊性 。显然 ,岩石样本 些方法的随意性较大 ,尤其是试验数据较少时 ,其随 力学参数的模糊性是一种比其随机性更重要的不确 意性显得更为突出 ,即使是基于随机统计思想的最 定性 。 下面举一个简单例子说明参数值对工程的小二乘法也只注意到了样本值的随机性而没有注意 影响
程度 。 到样本值的不确定性即模糊性 。随机性是指岩土样
有一散体干边坡 ,其粘结力 C = 0, 摩擦角为 <。 本取样测试过程中的一种客观的不确定性="" ,而模糊="">。>
α性是人们在判别岩土力学特性的整个过程中所反映 对于指定的边坡角 , 边坡的安全系数可定义为
α( )出来的一种主观不确定性 ,故试验样本是一随机模 1 F= tan< tan,="" s="">
安全系数的均值为 糊变量 ,为小子样 。本研究基于概率统计学和模糊 1数学 ,将岩土样本视为模糊随机样本 ,提出一种新的 ( )2 F = tan<, s="" tanα="" 随机="" -="" 模糊统计理论处理岩石样本值="" ,并且据随机="">,>
而安全系数的方差va r [ F] 正比于摩擦系数tan< s="" -="" 模糊理论从臵信度和可靠性="" 2个方面对岩体力学="">
va r [ tan< ]="" ,即的方差="" 参数的选取进行讨论="" ,提出参数臵信度分析模型和="" 2="" 1可靠性检验方法="" 。="" (="" )va="" r[="">< ]="" 1="" 3="" va="" r[="" f]="s" αtan="" 1="" 力学参数的随机-="" 模糊处理方法="" 111="" 岩石样本力学参数的不确定性="">
( ) 韩 磊 1984 —, 男 , 中 国 矿 业 大 学 矿 业 工 程 学 院 , 硕 士 研 究 生 , 岩石的力学参数指标应按工程地质岩组分别统 221008 江苏省徐州市中国矿业大学矿业文昌校区 。 计 。岩组的划分一般是依据现场调查及一些简单测
〃38〃
韩 磊等 :基于随机 - 模糊理论的岩体力学参数优化2010年第 5 期
n ( )( ) 如果将式 3 开平方 ,并除以式 2 ,则可得 2 ( ( ) ) -exp - x? wx x ii01 ? δδ= , i = 1tan< fs="" (="" )9="" x?="," n="" 2="" 即安全系数的变异系数等于摩擦系数的变异系数="" 。="" (="" (="" )="" )wexp-="" x-="" x?="" i="" 01="" i="1" 计算参数的离散程度对安全系数正确度的控制可见="" (="" )式="" 9="" 是岩土样本力学参数均值的计算公式="" 。该公="" 一斑="" 。="">
式为隐函数形式 ,需要迭代求解 。迭代求解可以通 由此可见 ,参数的不确定性对工程的影响程度 (过计算机编程来实现 本研究是通过 D e lp h i编程实 很大 。故如何处理这种带显著模糊性的数据就显得 ) 现的 。 非常重要 。 2 ( )δ= { x , x , , x } 中的。对于 U 2 模糊方差 1 2 n 1. 2 随机 - 模糊方法的计算过程 随机- 模糊变量作方差样本 ( ) 在概率空间 X , B , p中 , 对于 X 中的一个模糊 2 ) ( ( )x?1 ξ= x- 10 i i( ) μ集 A`, 如果它的隶属函数 x 是 Bo ra l可测的 ,则 A` ξξξξ取值为 R = {,, B`,} , 则 对 R 上的模糊子集 1 2 n i 称 A`是 X 中的一个模糊事件 。 的隶属函数为 模糊事件 A`的概率定义为 μ(ξ) (ξ) ( )= exp [ - D, S] 111 B i 2 i 1 2 ` μ) ( ) (( ) p A= x p x dx1` A` ( )ξ式 11 中 , D为 到 B 核心 S的马氏距离 ,形式如 X?2 i i 2
( 7 )式 ,只是权重取值为 当全集 X 是有限集时 ,则有
2 () μ( ) ( ) p = x p x , A` A`( )12 , w = w= i 2 ?x?X d - d 2m ax 2m in ( ) 式中 , p x 是 x的概率密度函数 。2 (ξ) ( 式中 , d, d 分别为 d =- Si = 1, 2, 2 i 2m ax 2m in 2 ( )1 模糊均值 x?。取论域 U = { X, , X} , 为 A`1 n ) n 中最大值 、最小值 。, ( xi = 1, 2, U 上的一个模糊子集 , 论域 U 中的元素 i 按照求均值的相似步骤组成目标函数 ( ) ) μ, n 对 A的隶属度为 x, 所求 A的核为`` A i `n
μ(ξ)( )= m ax1 13 J =( ( μ( ) ) ) ( )2 Ex = { Ex /x?= 1 } 1 4 B i `A A A ```? i = 1 ( )如果 4 式中的 x?能表示成 ( ) ( )= 0, 可得到样本差所服从的随机由 dJ/ dS 2 2 ( )( ) ( ) 5 Ex = f x= x? , A` i - 模糊统计公式 n 2 2 2( )则式 5 就是给定的岩土体某种力学参数所具有的 ( ) δ2 [ x - x?- ] - 2 i ( )exp〃 x - x? i ? 统计特征均值 。根据所论问题的性质 ,可使用如下 i = 1 d - d 2m ax 2m in 2 δ1 = n 2 2 2 的隶属函数 : ) δ ( - 2 [ x- x?- ] i exp ?( ) ( ) ( )Ex = exp [ - D x, x?], 6 A` i1 i i = 1d - d 2m ax 2m in 式中 , D 为关于 x模糊集合 A 的核点 Ei1 i A` (均值 )的 ( ) 14 马氏距离 ,其表达式可定义为 ( )式 14 是岩土样本力学参数模糊方差的计算公式 ,
2 同样该式也为隐函数形式 ,需要迭代求解 。 ) ( ( )7 D = x- x?w , i1i i
1. 3 模糊计算公式的合理性证明 式中 , w 为模糊度权重 , 其值可取为常数 , 即 w = i i
( ) ( )由公式 9 , 14 可以看出 ,岩土力学样本力学 con st = w。 按照使样本值整体上隶属于样本模糊01
参数的模糊均值实际上是基于岩土力学样本值的模 子集 A的 `
糊随机变量的模糊加权平均 。当不考虑岩土力学参 ( ) Ex 所具有的统计特程度最大的原则 , 可寻找到 A`
数的模糊特性时 ,模糊子集就蜕变为普通集合 ,则式 征 。为此 ,组成目标函数
n n ( ) ( )9 ,式 14 蜕变成随机统计公式 。令 D= D= 1 i 2 i 2 μ( ) ( ) = m ax1 J= x= exp- x x- x?w i i1 A` i ?? i = 1 i = 1 ) (= 0 , 其中 i = 1, 2,0 w, n ,则= w 0102
n ( ) 8 2 )( ( x? exp - - xwx i01i( ) n 当取 w为常数时 , 为取得极值 , 式 8 对 E求导应 01 A `? 1 i = 1 x? = = x? = x , ( ) ( ) 等于 0, 即 dJ/ dx = 0, 可以解得 in 1 ? n i = 12 ) )( ( x? - - wexpx i01 ? i = 1
( )15
〃39〃
? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
总第 407期金属矿山2010年第 5 期 n 2 2 2 n ( ) δ - 2 [ x- x?- ] 2 i - 1 ( )〃 x- x? exp i( )( λμ) λ24 = ln exp - 1 ?0 1i ? i = 1 - dd 2m ax 2m in2i = 1 δ = = n 2 2 2 ( )( )λ式 24 中的 可由式 25 求得 : )( δ - x? - ] i - 2 [ x iexp? n = 1 i - dd2m ax 2m in ( )( μ) ( λμ) 25 a - exp - = 01i ii n ? i = 1 21 2 δ ( ( )) 16 - x?1 = xi ? 则岩体力学参数分布即可得到 。 n i = 1
2. 2 岩体力学参数臵信度模型 在数 ( ) ( )式 15 ,式 16 就是随机变量的均值的计算公
( 理 统 计 中 , 若 子 样 取 值 Y = y, y,, 1 2 式 。可见 ,传统的随机处理方法是模糊随机处理方
法的一种特例 。由此可知 ,上述结论是正确的 ,应用 ) ( ) y, 其 概 率 分 布 函 数 为 F y , 分 布 密 度 函 数 为 n
( ) ( )式 9 ,式 14 计算考虑模糊特性的力学参数取值 f ( y ) , 则一般的表达式为
y i是合理的 。 ()( )( ) ( ) 26 p Y < y="F" y="f" ′zdz1="" i="" i="" i="" -="" 2="" 可靠性检验="">
图形表达见图 1。 2. 1 岩体力学参数分布模型
根据样本信息估计整体特性 ,若利用已获得的
样本值去估计最佳母体特性 ,确定出岩体力学参数 ,
需对其分布规律加以分析 。设岩体力学参数在模糊
) ( ( 子集 A` 中以 概率 p = p, p, , p取 值 x, x, 1 2 n 1 2
) , x,其隶属度为 n
μ( ) μx= , 则岩体力学参数的概A` i i
率分布问题可归结为最优化问 题 。
目标函数 图 1 一般分布模型 n 若给定臵信因子 β ,则分析数学模型为
p( Y < y)="β" ,="" (="" )27="" (="" )="m" ax1="" i="" i="" 17="" h="-" plnpi="" i?="" i="1" yi="" (="" )约束条件(="" )="" (="" )="" β="" 28="" p="" y="" y="f′zdz" =="" 1="" -="" 1i="" -="" n="">
Ω设力学参数母体为 , 由 n组试验确定的样本值为 X μ( )18 = a; pii? i = 1 ( ) μ( ) μ= x, x, , x, 其隶属度 x= , 它的随机 1 2 n n A i i
( )= x?; 19 pxi i( ) μ?模糊概率分布 p = p, p, , p, 是以 为自变量 1 2 n i i = 1 n 的函数 ,其分布密度函数为 ( )20 p= 1;i ? f′(μ) = - λexp [ - ( 1 +λ) - λμ] 1 ( 29 ) i = 1 i 1 0 1i
( )p= 1, p> 0, i = 1, 2, , n 21 1 i 为研究臵信问题 ,提出“臵信阈值 ”概念 . 对于样本
μ( ) ( ) ( ) ( ) μ( )x?x, p x? p x122 A` i A` j i j μ值 x, 其隶属度为 , 若 βi +? j = 1, 2, , n (μ) ( ) β( )F = f td t = 1 - ,30 β 式中 , n 为样本个数 ; ?x为随机模糊均值 ; a 为常数 , ?μβ 近似表达了概率分布与可能性分布的一致性 。由上 ( β)μ则 称为臵信阈值 , 确定了 1 个取值区间 ; 1 - β
述线性规划 , 求得岩体力学参数随机模糊概率分布 为臵信度 , 表示参数落在臵信阈值所定义的区间的 模型 。 可靠程度 。图形表达见图 2。
在解上 述 线 性 规 划 时 , 可 用 单 纯 形 法 逼 近 式 由此定义 ,在一定的臵信度 ( 1 - β) 下 , 可由式 ( ) ( ) ( ) 17 , 式 18 , 式 20 , 求得相应的解 p, 然后看是 i ( ) μ, 进而可检验所给参数的臵信度 。需30 确定出 β( ) ( ) 否适合式 21 , 式 22 , 若不符合则根据上次结果 ( β) 要说明的是 , 在经典统计理论中 1 - 称为臵信概 调整 a 值 , 再逼近 ,最终可求得其解如下 率 ,μ为单侧臵信下限。 β ( λ) λμ( )23 p= exp [ - 1 +- ], i 0 1i
〃40〃
? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
韩 磊等 :基于随机 - 模糊理论的岩体力学参数优化2010年第 5 期
首采区主要地层有第四系 、新生界第三系上新统 、中
生解白垩系 ,主要岩性为泥岩 、砂岩 、砾岩 。为获得
(岩石边 坡 稳 定 性 分 析 所 需 的 力 学 参 数 值 C 粘 聚
) () 力 和 < 内摩擦角="" ,="" 在首采区布臵="" 20="" 个补充勘探="">
孔取样 ,然后 ,采用 ZJ 型应变控制式直剪仪进行岩
石样本试件快速直剪试验 。首采区北帮部分试验结
果见表 1。
表 1 泥岩样本力学参数试验成果
图 2 置信度数学模型 1 2 3 4 5 6 样本号
2. 3 数据可靠性检验 岩体力学参数通常是通过室C / kPa 77. 35 200. 81 130. 97 99. 62 121. 89 104. 21 内或现场试验测试 )( < 21.="" 15="" 13.="" 37="" 22.="" 50="" 19.="" 01="" 11.="" 30="" 19.="" 98="" 取得的="" ,因而对测试数据的处理是参数取值的重要="" 样本号="" 7="" 8="" 9="" 10="" 11="" 12="" 环节="" 。对于一组测试数据="" ,="" 因物理方面="" ,="" 及取样原="" c="" kpa="" 51.="" 32="" 101.="" 55="" 102.="" 37="" 8.="" 62="" 91.="" 47="" 95.="" 13="" 则="" 、取样方法的原因而出现参差不齐现象="" ,甚至个别="" )(="">< 23.="" 15="" 20.="" 75="" 27.="" 61="" 14.="" 44="" 25.="" 52="" 16.="" 10="" 数据有较大的离散性="" ,从而缺乏代表性和真实性="" ,使="" 为计算岩石岩本的模糊特征值="" ,根据上述求解="" 得测试样本值里混入了异常值="" 。若这个异常值来自="" 方法编制了基于="" d="" e="" lp="" h="" i语言的模糊统计特="" 征值="" 计="" 其他母体的数据="" ,必定会影响到整个参数的确定="" ,若="" ()="" 算程序="" 图="" 3="" 。表="" 2="" 给出了泥岩采用常规随机统计="" 将这个受异常值影响的参数应="" 用于="" 工程="" 设="" 计与="" 计="" 方法和模糊统计方法的计算比较结果="" 。="" 算="" ,严重时会导致工程设计的重大失误="" 。若花费大="">
量的人力 、物力在室内或现场进行大量试验以获取
大子样 ,虽然这样做异常值对参数影响较小 ,不至于
造成明显的偏差 ,但在工程实践中常因工期 、经费等
原因而难以做到 。所以工程技术人员获取的数据常
常是小子样 ,必须用一定的数学方法对子样值加以
处理 , 以保证岩体力学参数的可靠性 、真实性 。为
此 ,依据岩体力学参数的随机模糊不确定性 ,利用臵 信
阈值的概念 ,提出了测试数据可靠性检验的方法 。
( ) 设样本值 X = x, x,为随机模糊变量 ,, x 1 2 n
μ( ) μ( ) 其隶属度为 x= , 其概率分布如式 23 所 图 3 程序编辑框 A i i
表 2 泥岩模糊统计结果 示 ,可靠性检验方法步骤如下 :
( 1 )计算出各测试数据的隶属度 μ。 统计特征值 模型特征值 i
( ) β( ) 2 给出臵信度 1 - , 利用式 30 计算出该力 项 目 标准 变异 标准 变异 均值 均值 方差 系数 方差 系数 μ学参数在此臵信度下的臵信阈值 。 β
( ) μμ3 剔除异常值 。分别把每个数据的 与 相 比C / kPa 98. 776 45. 665 2 0. 462 311 6 97. 838 28. 6 0. 292 3 β1 )( < μμ较="" ,="" 若="">< 则认为该测试数据是异常值="" ,予以="" 19.="" 573="" 4.="" 963="" 6="" 0.="" 253="" 590="" 4="" 21.="" 581="" 4.="" 12="" 0.="" 190="" 847="" β="" i="">
剔除 。经过这一过程 ,可对测试数据进行处理 ,从而 表 2表明 ,无论随机均值和模糊均值的大小关 得出具有一定臵信度的力学参数 。 系如何 ,模糊方差和模糊变异系数均比随机方差和 3 应用实例 随机统计得到的变异系数要小 ,且模糊标准差一般
胜利煤田地处内蒙古高原中东部大兴安岭西延 是随机标准差的 0. 5左右 。这说明采用模糊统计方 的北坡 ,属高原丘陵地形 。区域内地貌形态由构造 法计算得到的岩石力学参数更切合实际 ,更贴近材 剥蚀地形 、剥蚀堆积地形 、侵蚀堆积地形 、岩熔台地 料参数的真值 ,同时也表明 ,模糊统计处理方法优于 4 个地貌单元组成 。东二号露天矿区地处胜利煤田 传统的随机处理方法 。按照模糊统计方法计算得到 中东部的剥蚀堆积地形与低缓丘陵地形过渡地带 。 的参数值是最有可能取到的参数值 ,这一参数的获
〃41〃
? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
总第 407期金属矿山2010年第 5 期
表 3 模糊概率分布系数 得 ,减少了对经验知 识 的依 赖 , 当样 本数 据 量较 大
λλ a 项 目 01时 ,其结果的可信度更大 。 该区域泥岩力学参数试0. 855 2. 064 848 771 - 0. 698 5 内聚力 / kPa 验值见表 1 , 通过求解 摩擦角 / ( ?) 0. 909 998 4. 772 452 778 - 3. 978 2 ( ) ( )式 17 ,式 22 线性规划问题 ,可得该区泥岩力学 ( ) 计算 时 , 采用 式 9 的 均 值 公 式 计 算 x? , 用 式 ()参数 内聚力 、内摩擦角 随机模糊概率分布函数为 ( ) ( ) 18 , 25 式的定义计算其可能分布 , 计算结果 ( λ) λμp= exp [ - 1 +- ], i 0 1i 见表 4 ,表 5。 λλ式中 , ,值见表 3。 0 1
表 4 泥岩内聚力可能性分布与概率分布
1 2 3 4 5 6 7 8 9 10 11 12 样本号
C / kPa . 35 200. 81 130. 97 99. 62 121. 89 104. 21 51. 32 101. 55 102. 37 8. 62 91. 47 95. 13 77
μ i0. 924 . 135 254 0. 812 923 3 . 999 4 . 896 595 . 992 368 . 665 . 997 4 . 996 1 . 223 . 992 . 998 6 0000000000 p i0. 089 0. 051 284 0. 082 329 8 0. 093 8 0. 087 285 0. 093 324 0. 074 0. 093 7 0. 093 6 0. 055 0. 093 0. 093 7 模糊均值 C / kPa 97. 837 9
表 5 泥岩内摩擦角可能性与概率分布
1 2 3 4 5 6 7 8 9 10 11 12 样本号
)( . 15 13. 37 22. 50 19. 01 11. 30 19. 98 23. 15 20. 75 27. 61 14. 44 25. 52 16. 10 21<>
μ i0. 996 . 278 609 . 134 86 . 952 581 . 954 . 987 . 502 1 . 38 . 745 . 565 9 000000000. 984 115 1 0. 882 2 0 p i0. 137 67 0. 164 0. 009 428 0. 156 070 7 0. 104 1 0. 005 322 0. 139 0. 157 9 0. 0229 0. 014 0. 06 0. 029 6 )( 模糊均值 < 21.="" 580="" 9="">
从表中可直观地看出 ,该石英岩的可能性分布果表明 ,该法优于传统方法 。利用所给出的臵信度 与概率分布满足一致条件 。 模型对岩体力学参数的选取进行评价 ,可使工程应
( ) 根据式 29 ,可求得内聚力和内摩擦角的随机 用中的参数更合理 、更符合实际 。同时 ,对有限的测 - 模糊概率分布密度 : 试数据 ,运用所提出的可靠性检验方法 ,对异常数据 对于内聚力 C , 进行检验并排除 ,使测试数据更好地反映研究对象 ( 0. 7μ- 3. 1 )(μ)( ) f 31 = 0. 7 e , 的真实特性 ,避免出现参数取值偏差 。
对于内摩擦角 < ,="" (="" μ)4-="" 5.="" 8="" 参="" 考="" 文="" 献="" (μ)="" (="" )f="" 32="4" e="" 1="">
( β ) 6 若给定臵 信 度 1 - = 95 % , 则 臵 信 阈 值 如 表 [ 1 ] 祝玉学. 边坡可靠性分析 [M ]. 冶金工业出版社 , 1993. 黄志全. 边坡工程 - 非线性分析理论及应用 [ M ]. 郑州 : 黄河 所示 。 [ 2 ] 水利出版社 , 20051 μ置信阈值 表 6 β 张玉香. 基于随机 - 模糊处理理论的岩体力学参数研究 [ J ]. [ 3 ] μ 对 象 β ( ) 西北农林科技大学学报 :自然科学版 , 2007 , 35 12 , 231 2234.
刘 春. 边坡工程中岩石力学参数随机模糊选取研究 [ J ]. 岩 0. 671 2 内聚力 C / kPa [ 4 ] ( ) 土力学 , 2004 年 , 25 8 , 1327 21329. )( 内摩擦角 < 0.="" 281="" 9="" 马军平="" ,单仁亮="" ,韩友强="" ,等.="" 土体抗剪强度参数="" c="" 与="">< 的随机="">
( ) - 模糊分析 [ J ]. 岩石 力学与 工程 学报 , 2004 , 23 Z1 : 4343 2 利用此方法 ,可以评价每个测试数据的臵信度 。[ 5 ]
4346. μ以内摩擦角样本 4 为例 ,其隶属度 = 0. 882 2 ? i 徐卫 亚 , 蒋中 明 1 岩 土样 本 力 学 参 数 的 模 糊 统 计 特 征 研 究 μ, 则可认为它在臵信阈值所定义区间中取 19, 01 β( ) [ J ]. 岩土力学 , 2004 , 25 3 : 342 2346. [ 6 ] μ的臵信度为 95 % 。若取内摩擦角样本 5, 其隶属度 黄志全 , 李华 晔 , 姜 彤. 岩 体 力 学 参 数 取 值 的 臵 信 度 研 究 i
( ) [ J ]. 华北水利水电学院学报 , 1997 , 18 4 : 14 218. μ= 0. 134 86 ?,则认为它为异常值 ,予以剔除 ,对 β [ 7 ] 颜廷松 ,刘爱玉 ,邓奕航. 岩体力学参数的可靠性检验 [ J ]. 华 岩石力学参数取值时排除了该数据的影响 。 ( ) 北水利水电学院学报 , 2003 , 24 3 : 50 252. 4 结 论 [ 8 ]
岩石力学参数在岩土工程计算中起着重要作
用 。运用随机 - 模糊方法处理更符合实际 ,计算结 ()2010 203 202 收稿日期 〃42〃
? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
范文二:基于随机_模糊理论的岩体力学参数优化
( ) 文章编号 : 1000 - 1301 2009 02 - 0007 - 06
基于随机 Fou rie r谱的地震动合成研究
1 2艾晓秋 ,李 杰
( )1. 同济大学 上海防灾救灾研究所 ,上海 200092; 2. 同济大学 建筑工程系 ,上海 200092
摘 要 :本文基于与物理随机模型相对应的随机 Fou rie r谱 ,通过对地震动非平稳性及其所受影响机
制的分析 ,建立了非平稳地震动合成的新方法 。通过引入基本相位差谱 ,并将初始相角视为随机变
量 ,以相位差谱的分布特性 、随机地震动的统计特征以及对结构随机反应的影响为原则 ,利用计算机
程序生成相位差谱 ,提出了基于随机 Fou rie r谱的合成地震动方法 。同时 ,利用快速 FFT技术提高合
成精度 。根据本文提出的合成方法获得的地震动具有非平稳特性 ,将为后续研究工作提供合理的地
震动加速度时程 。
关键词 : 随机 Fou rie r谱 ;合成地震动 ;相位差谱 ;非平稳过程 ;随机变量
中图分类号 : P315; TU311. 3 文献标志码 : A
Syn thesis m ethod of non2sta tionary ground m otion ba sed on random Four ier spectra
1 2A I X iaoq iu, L I J ie
( 1. Shangha i In stitu te of D isa ste r P reven tion and R elief, Tongji U n ive rsity, Shangha i 200092 , Ch ina;
)2. D ep a rtm en t of B u ild ing Enginee ring, Tongji U n ive rsity, Shangha i 200092 , Ch ina
A b stra c t:B a sed on the random Fou rie r sp ec tra co rre spond ing to the p hysica l random ea rthquake mode l and con sid2 e ring the cha rac te r of se ism ic non2sta tiona rity and the influenc ing m echan ism , th is p ap e r p ropo se s a new app roach to syn the size the ea rthquake mo tion p re sen ting non2sta tiona rity. The ba sic p ha se angle d iffe rence sp ec trum is led in and the in itia l p ha se angle is rega rded a s a random va riab le. The d istribu tion cha rac te ristic s of the p ha se angle d iffe rence sp ec trum , the sta tistica l cha rac te ristic s of random ground mo tion and the effec ts on struc tu ra l stocha stic re spon se a re the judgm en t stra tegy. U tilizing the comp u ta tion p rocedu re to p roduce the p ha se angle d iffe rence sp ec2 tra, a syn the tic m e thod is p ropo sed on the ba sis of the random Fou rie r sp ec tra. Sim u ltaneou sly, the fa st FFT tech2 n ique is app lied to imp rove the syn the tic accu racy. The p ropo sed m e thod is cap ab le of ach ieving non2sta tiona ry ea rthquake mo tion, wh ich wou ld p rovide rea sonab le se ism ic acce le ra tion fo r succeed ing re sea rch wo rk. Key word s: random Fou rie r sp ec trum; syn the tic ea rthquake mo tion; p ha se2angle d iffe rence sp ec trum; non2sta tion2 a ry p roce ss; random va riab le s
引言
[ 1 ] ( ) 地震动加速度的人工合成一般由谱表现 Sp ec tra l R ep re sen ta tion 方法 实现 : 以工程场地的地震动功 率谱函数为基础 ,利用 Fou rie r变换的相关理论 ,通过有限 Fou rie r级数来模拟地震动时程 。若根据随机相角
收稿日期 : 2008 - 03 - 18; 修订日期 : 2008 - 06 - 21
( ) 基金项目 :国家自然科学基金委创新研究群体科学基金项目 50321803
( ) 作者简介 :艾晓秋 1977 - ,女 ,讲师 ,博士 ,主要从事灾害工程防御研究 1E2m a il: aixiaoq iu@m a il. tongji. edu. cn
均匀分布在 0,内的假定生成目标地震动时程 ,则利用谱表现方法生成的地震动加速度时程是一个平稳过
程 。而实际地震记录则表明 :地震动加速度时程是具有显著非平稳特性的时间过程 。在地震工程中 ,常将谱表现方法获得的平稳时间过程乘以确定的时间强度包络函数 ,来体现人工合成地震动的强度非平稳特性 。 [ 2 - 5 ] 显然 ,这样的处理方法仍然与实际地震动记录之间有很大差异 。有关研究成果表明 :地震动的非平稳性 与地震动相位差谱之间有着直接的关系 ,相位谱的分布规律不能完全确定地震动的非平稳性 。另一方面 ,由 于功率谱不具有相位信息 ,因此在实际合成地震动的过程中将存在并非唯一的相位谱或相位差谱 ,由此合成
的地震动时程虽然满足目标功率谱的要求 ,但并不具有唯一性 。
在文献 [ 6 ]中 ,作者从随机 Fou rie r谱函数的角度描述地震动 ,通过工程场地中地震动的传播过程建立物 理关系 ,建立了适用于各类工程场地的随机地震动模型 。本文研究目的在于 :基于随机 Fou rie r幅值谱 ,通过
相位差谱而非相位谱合成地震动以体现地震动的非平稳特性 ;同时 ,为解决相位差谱的不唯一性问题 ,提出基于随机 Fou rie r谱的非平稳地震动合成方法 。通过本文方法 ,将为后续的研究工作提供合理的地震动时 程 。
1 地震动合成的谱表现方法
[ 8 ] 利用谱表现方法 ,地震动随机过程可以表示为具有随机相角的三角级数的叠加 ,即
N - 1
(ωφ)( ) ( )x t= 6 A co s t + 1 j j j j = 1
( )ωφ其中 , x t为具有零均值的随机过程 ; N 为频率分量的总数 ; A 和 分别为第 j个频率分量的幅值和频率 ; j j j
( π) 为地震动时程的相位谱值 ,常被处理为在 0, 2内均匀分布的随机变量 。[ 1 ] Sh inozuka等人给出了 A 与功率谱之间的基本公式 ,即 , , j
( )ω)Δω(2 A , N - 1 4S , j = 0, 1, 2, jj
Δω (ω)ωΔω, N - 1;为频度间距 ,其中 , S 为功率谱密度函数对应于各个频率分量的离散值 ,= j , j = 0, 1, 2, j j
Δω Δω( )ω) ( =/N 。同时 ,式 2 应满足 A= 0, S = 0 = 0。u 0 0
( )若相位谱中的相角服从均匀分布 ,根据式 1 合成得到的时程将是一个平稳过程 。在既有研究中 ,通常 [ 8 ] 将这一结果乘以一个随时间变化的强度包络函数 :
( ) ( ) ( )( )a t= f t〃x t3
( )( )( ) 其中 , x t为按式 1 合成的具有零均值的平稳过程 ; f t为确定的时间强度包络函数 ,一般可简化地采用
分段函数 。通过上述处理 ,能在一定程度上体现地震动的强度非平稳特性 。
[ 9 ]O h sak i最早注意到相位谱的分布规律不能完全确定地震动的强度非平稳性 ,他研究了相位差谱对地
( )震动加速度时程的强度包络函数的影响 ,认为 : 1 对于绝大多数实际地震记录而言 ,相位分布是均匀的 ; ( )( ) 2 相位差的概率分布可以认为是正态的 ; 3 相位差随频数的概率分布与强度包络函数的形状之间存在着[ 3 - 5 ] 某种相似关系 。在 O ha sk i研究结果的基础上 ,多位学者研究了相位差谱对强度包络函数的调制作用 。 [ 3 ]例如 ,朱昱和冯启民 通过对大量的地震加速度记录的相位差谱进行分析 ,认为强震加速度时程的相位差 谱的分布符合对数正态分布 。根据该分布产生的随机相角合成的地震动不需要乘以强度包络函数 ,即可体 现出地震动的强度非平稳特性 。并认为 ,地震动加速度时程的相位特征对地震动的强度非平稳特性和频率
[ 4 ] 非平稳特性都有很大的影响 。金星和廖振鹏 进一步推导了幅值谱和相位差谱与强度包络函数之间的关
系 。
2 基于随机 Fourier谱的地震动合成
2. 1 基于物理的随机地震动模型
根据文献 [ 6 ] ,如果暂不考虑震级能量与地震动衰减的影响 ,而把研究重点放在具体工程场地的地震动 传播机制上 ,则可以建立地面地震动与基底输入傅氏谱 、场地固有卓越周期和场地等价阻尼比之间的理论物 理关系 ,相应的随机地震动 Fou rie r谱函数为 2ω ζωω2i 0 0( ω) ( ω)( )F X ,= 4 〃F S , 0 g 2 2ωω ζωω- 2i 0 0
9 第 2期艾晓秋等 :基于随机 Fou rie r谱的地震动合成研究
ωζ式中 , F 为输出 Fou rie r谱 , F为输入 Fou rie r谱 ,为场地基本频率 ;为场地等效阻尼比 ; S为输入地震动 0 0 g
ωζ幅值谱参数 。假定 、、S等基本随机变量为对数正态分布且互相独立 ,则利用随机建模准则 ,可给出适用 0 g
于不同工程场地随机地震动模型的基本物理变量概率分布参数 ,见表 1。
表 1 不同场地基本随机变量的分布参数
Tab le 1 D istribu tion p a ram e te rs of the ba sic random va riab le s fo r d iffe ren t site s
I II III IV
均值 变异系数 均值 变异系数 均值 变异系数 均值 变异系数
基底幅值 S 0. 22 0. 50 0. 25 0. 50 0. 29 0. 50 0. 35 0. 50 g
ω频率 18 0. 40 15 0. 40 12 0. 42 9 0. 42 0
0. 65 0. 30 0. 70 0. 30 0. 80 0. 35 0. 85 0. 35 ζ 阻尼比
2. 2 基本合成关系式
[ 10 ] Fou rie r系数与 Fou rie r积分的关系 , 基于前述随机 Fou rie r幅值谱合成地震动 ,可根据
1 ω)( )((ω) 5 F| dw A = ω ω =j j π2
ωΔω( )以及 d?,将式 1 在时域内转换为 , N Δω ) (ωφ)( )() ( ) ( 6 F w |〃co s t + x t= 2 〃6 ω ω =j j j j = 1 π2
(ω) ωζ式中 , F |为 Fou rie r幅值谱对应于各个频率分量的离散值 。在合成中 ,各随机变量 、、S取给定样 ω ω =0 g k
( )本值 。在实际的地震动合成中 ,直接利用式 6 的三角函数的叠加合成地震动的计算效率较低 ,通过快速
[ 11 ] ( ) Fou rie r变换 FFT技术 ,可在很大程度上提高合成计算的效率 。
在已有研究中 ,基于相位差谱的合成地震动首先确定服从某一分布的相位差谱 ,在以某频谱为目标谱的 后续拟合迭代过程中 ,仅通过调整控制频率点的幅值进行逼近 。也就是说 ,相位差谱虽然是由服从某分布的 随机变量组成 ,但是对于地震动合成过程而言 ,相位差谱却是一个确定性向量 。由此合成的地震动虽然满足 目标谱的要求 ,但显然 ,所使用的相位差谱并非唯一 ,即存在其他的服从同一分布的相位差谱 ,通过其合成的 地震动也将满足目标谱的要求 。
[ 11 ] 作者通过研究认为 :地震动的统计均值应具有趋近于零的性质 ; 若假定每一个地震动样本的相位差谱是完全相关的 ,即相位差谱对于每一个地震动样本都是相同的 , 则地震动统计特征中的均值将不具有零 均值的特性 。分析表明 ,即使重新获取一组相位差谱 ,仍然难以满足地震动统计零均值的条件 。也就是说 , 在初始相角不变的情况下 ,若对一组合成地震动中的每一个地震动样本均选用相同的相位差谱 ,所合成的地 震动是无法满足零均值特性的 。
基于随机 Fou rie r谱进行地震动合成 ,任意随机 Fou rie r幅值谱对应的相位差谱应该是随机的 ,也就是 说 ,任意地震动样本的相位差谱之间是相互独立的 ,即每一频率分量对应的相位差即为一个独立的随机变
量 ,这将导致随机变量数量的大量增加 。因此 ,对于随机 Fou rie r谱的地震动合成 ,为满足地震动的非平稳特
性和地震动统计特征值零均值特性 ,如何确定初始相角和相位差谱是需要解决的关键问题 。
2. 3 基于随机初始相角和基本相位差谱的地震动合成
本文的基本思路是 :将初始相角视为随机变量 ,通过 M a tlab程序函数产生随机数列引入基本相位差谱 。 本文提出的“基本相位差谱 ”意味着对应不同随机 Fou rie r幅值谱的相位差谱是相同的 ,即通过随机的初始相 角和确定的相位差谱描述地震动的强度非平稳特性 。 根
据已有研究结论 ,将基于以下述原则确定相位差谱 :
( ) 1 相位差谱的分布特性 。根据相关研究 :为体现地震动的强度非平稳特性 ,相位差谱需服从对数正态
分布 ,即基本相位差谱应该服从对数正态分布 。
( )2 随机地震动的统计特征 。随机地震动的统计特征具有以下两个特征 : 随机地震动样本集合的均值 应趋向于零 ,标准差受相位差谱的影响较小 。基本相位差谱的选取应使地震动符合上述特征 。
( ) 3 对结构随机反应的影响 。在结构的随机反应这个层面上 ,以单自由度线性体系的随机反应为例 ,其
样本集合统计特征同样应具有均值趋向于零 ,标准差受相位差谱的影响较小的特点 。基本相位差谱的选取
应使结构随机反应符合上述特征 。
2. 3. 1 随机初始相角的分布
分析表明 ,初始相角基本服正态随机分布 ,其关键参数是变异系数 ,本文假定初始相角服从均值为 0 ,标
δπδ准差为 〃的正态分布 。在相同基本相位差谱条件下 ,不同初始相角的变异性 条件下的地震动统计特征 曲线如图 1所示 。由图可知 ,初始相角的变异性对均值的影响是非常显著的 ,并且随着初始相角的变异性的
δ增大 ,均值曲线并不是逐渐趋向于零 ,均值峰值出现了先减小后增大的现象 :当 012 < 112时="" ,均值峰值随="">
δδδ的增大而迅速减小 ;当 112 < 210="" 时="" ,均值峰值随="" 的增大而增大="" 。由上述比较可知="" ,当="" 为="" 1.="" 2="" 时="" ,地震="">
δ动的统计特征最趋近于零均值 。对于标准差曲线 ,除了当 为 0. 2时略大 ,其余情况之间的差异很小 。根据
δ对比分析的结果 ,假定初始相角的变异系数 为 1. 2。
图 1 初始相角的变异性对地震动统计特征的影响
F ig. 1 Influence of the va riab ility of in itia l p ha se angle on the sta tistic cha rac te ristic s of ground mo tion s 2. 3. 2 基本相位差谱的生成
本文通过数学软件 M a tlab的应用程序随机产生基本相位差谱 : 通过程序产生服从正态分布的随机数
( )列 ,并利用随机发生器的种子 seed来固定生成的数列 ,变换得到服从对数正态分布的随机数列作为基本相
[ 3 ] μσ位差谱 。参考文献资料 ,假定基本相位差谱服从均 值为 2 ,标准差 为 0. 8的对数正态分布 ,则对应正 lnln
μσ 态分布的均值 和标准差 分别为
1 2 μ μ(σμ) = ln- ln 1 + /ln ln ln 2 ( )7
2 σ σμ= ln 1 + / ln ln
不同的随机发生器种子将产生不同的基本相位差谱 ,图 2 比较了不同的基本相位差谱对应的地震动统 计特征曲线 。由图可知 ,由不同种子产生的基本相位差谱得到的均值曲线的幅值与标准差相比 ,均值曲线基 本上可以视为趋近于零 ,标准差曲线的趋势也基本一致 。因而 ,根据 M a tlab 随机产生的基本相位差谱基本 上满足对地震动统计特征的要求 。
2. 3. 3 基本相位差谱与结构随机反应
11 第 2期艾晓秋等 :基于随机 Fou rie r谱的地震动合成研究
合成地震动的最终目的是为了对结构进行地震反应分析 ,因此考察相位差谱的差异对结构的随机反应 的影响尤为重要 。本文以单自由度结构为例 ,考察了 M a tlab随机发生器种子的选取对结构的随机反应的影 响 。
图 2 不同基本相位差谱的地震动统计特征曲线 图 3 不同基本相位差谱的单自由度
F ig. 2 Sta tistica l cha rac te ristic cu rve s of 体系随机反应的统计特征曲线
random ground mo tion s w ith d iffe ren t F ig. 3 Sta tistica l cha rac te ristic cu rve s of random
p ha se2angle d iffe rence sp ec tra ea rthquake re spon se w ith d iffe ren t p ha se2angle
d iffe rence sp ec tra
() 假定单自 由 度 的 结 构 参 数 为 注 : 均 为 国 际 单 位 制 : 质 量 M = 2. 0 e10; 刚 度 K = 5. 0 e11; 阻 尼 C =
ω ω ζ1. 0 e10。因此 ,圆频率 = K /M = 56 rad;阻尼比 = C / 2M= 0. 05。根据不同的随机发生器种子得到的相 应的基本相位差谱 ,图 3 所示为上述单自由度体系的加速度反应的统计特征曲线 ;图 4 所示为将地震动模型 的随机变量均取均值时生成的地震动作为确定性输入时 ,上述单自由度体系的加速度反应曲线 。从图 3 可 知 ,不同的基本相位差谱得到的随机反应统计特征包括均值和标准差均具有趋势一致 ,而形状有所差异的特 点 ,这与地震动的统计特征曲线的结果是一致的 。对比图 3和图 4可知 ,加速度反应的均值曲线的峰值远远 小于确定性输入时的峰值 ,因此可以认为加速度反应具有接近零均值的特征 。
图 4 不同基本相位差谱的单自由度体系加速度反应曲线
F ig. 4 R andom ea rthquake re spon se s w ith d iffe ren t p ha se2angle d iffe rence sp ec tra 2. 4 基于随机 Fou rie r谱的地震动合成实例 [ 6 ] 根据本文提出的确定相位谱的方法进行地震动合成 ,以 IV 类场地的随机地震动模型 为例 ,图 5 所示 为所生成的若干随机地震动样本 。由图可知 ,无需采用强度包络函数 ,由于相位差谱和初始相角的引入 ,根 据本文方法合成得到的地震动已具有较为显著的非平稳特性 。需要说明的是 ,本文提出的地震动合成技术 体现了地震动的强度非平稳特性 ,而根据作者建立的基于物理的随机地震动模型 ,则能够从另一侧面描述地 [ 11 ] 震动频率非平稳特性 。
图 5 随机地震动的合成结果
F ig. 5 R andom ground mo tion syn the sis re su lts
3 结语
本文针对基于物理的随机地震动模型 ,将初始相角视为随机变量 ,并引入基本相位差谱 ,以相位差谱的 分布特性 、随机地震动的统计特征以及对结构随机反应的影响为原则 ,通过对比分析 ,提出了基于随机 Fou2 rie r谱的合成地震动方法 。根据本文提出的合成方法获得的地震动具有较理想的非平稳特性 ,将为更为深
入的研究工作提供合理的地震动加速度时程 。
参考文献 :
( ) Sh inozuka M , D eoda tis G. Sim u la tion of staochastic p roce ss by sp ectra l rep re sen ta tion [ J ]. App lied M echan ic s R eview s, 1991 , 44 4 : 191 - 203. [ 1 ]
( ) O ha sk i Y. O n the sign ificance of p hase con ten t in ea rthquake ground mo tion s[ J ]. Ea rthquake Engineering and Struc tu ral D ynam ic s, 1979 , 17 4 : [ 2 ]
427 - 439. ( ) 朱 昱 ,冯启民. 地震加速度相位差谱分布的数字特征 [ J ]. 地震工程与工程振动 , 1993 , 13 2 : 30 - 37. [ 3 ]
( ) 金 星 ,廖振鹏. 地震动强度包线函数的理论研究 [ J ]. 地震学报 , 1994 , 16 4 : 519 - 525.[ 4 ]
( ) 赵凤新 ,胡聿贤. 地震动非平稳性与幅值谱和相位差谱的关系 [ J ]. 地震工程与工程振动 , 1994 , 14 2 : 1 - 6.[ 5 ]
( ) 李 杰 ,艾晓秋. 基于物理的随机地震动模型研究 [ J ] 1地震工程与工程振动 , 2006 , 30 5 : 21 - 26.[ 6 ]
胡聿贤. 地震工程学 [M ]. 2 版 ,北京 :地震出版社 , 2006.[ 7 ]
李 杰 ,李国强. 地震工程学导论 [M ]. 北京 :地震出版社 , 1992.[ 8 ]
大崎顺彦. 振动理论 [M ]. 谢礼立 ,等译. 北京 :地震出版社 , 1990.[ 9 ]
[ 10 ] 戴诗亮. 随机振动试验技术 [M ]. 北京 :清华大学出版社 , 1984.
[ 11 ] 艾晓秋. 基于随机地震动模型的地下管线地震反应及抗震可靠度研究 [ D ]. 上海 :同济大学 , 2005.
范文三:半方差约束下的模糊随机收益率贷款组合优化模型
半方差约束下的模糊随机收益率贷款组合
优化模型
第37卷第5期
2010年5月
计算机科学
ComputerScience
Vo1.37No.5
May2010
半方差约束下的模糊随机收益率贷款组合优化模型
潘东静
(德州学院计算机系德州253023)
摘要银行贷款的收益率在很多情况下具有模糊随机性.将贷款收益率刻画为模糊随机变量,
使用半方差作为风
险度量方式,建立半方差约束下的模糊随机收益率贷款组合优化模型,目的是在一定的半方
差约束和置信水平下,最
大化贷款组合的收益率不小于预置收益率的本原机会测度.应用集成模糊随机模拟,神经网
络,遗传算法的混合智能
算法进行求解,最后通过实例验证了模型和算法的可行性和有效性.
关键词本原机会测度,贷款组合,模糊随机变量,模糊随机模拟,混合智能算法
中图法分类号TP301文献标识码A
OptimizationModelofLoanPortfoliowithFuzzyRandomReturnRatesunderSemivarianceConstraint
PANDong-jing
(DepartmentofComputerScienceandTechnology,DezhouUniversity,Dezhou253023,China)
AbstractThereturnratesofloaninbankoftenhavefuzzyrandomcharacteristicinmanycases,thispaperdescribed
thereturnratesasfuzzyrandomvariables,usedsemivarianceastheriskmeasuremethod,constructedtheoptimization
modelofloanportfoliowithfuzzyrandomreturnratesundersemivarianceconstraints.Thepurposeofthemodelisto
maximizetheprimitivechancemeasurewhenthetotalreturnrateisnolessthanthepresetvalueatagivenconfidence
leve1undersemivarianceconstraints.Thehybridintelligentalgorithmwasemployedtosolvethemodel,thealgorithm
integratesfuzzyrandomsimulation,neuralnetworkandgeneticalgorithm.Atlast,numericalexamplesillustratethefea—
sibilityandeffectivenessofthemodelandthealgorithm.
KeywordsPrimitivechancemeasure,Loanportfolio,Fuzzyrandomvariable,Fuzzyrandomsimulation,Hybridintelli—
gentalgorithm
1引言
目前,国内外许多文献对商业银行贷款组合决策问题进
行研究.银行为分散风险,把贷款投放到不同的项目上,即贷
款组合,其本质上也是一种投资组合,最终目标是希望贷款收
益最大,风险最小.
自从Markowitz[1_对资产组合提出均值一方差模型后,很
多学者致力于资产组合的研究,Altman/2]提出的商业贷款组
合分析模型,是在贷款组合收益大于等于目标收益的约束下,
求解夏普指数的最大化;马志卫[3]通过蒙特卡洛模拟,以贷款
项目的财务内部收益率及其波动反映其收益和风险,建立组
合收益最大,组合风险最小的贷款组合多目标规划决策模型;
]等在组合风险小于目标值的情况下,追求组合收益最大
化,建立多阶段的均值方差组合优化模型;Sheedy等_5]在满
足目标收益率的约束下,建立了风险变化时的资产分配决策
模型;迟国泰等_6]建立了在VaR约束下以贷款组合风险最小
为目标的优化决策模型;宁玉富[73针对收益率为模糊变量的
情形,给出了贷款组合优化决策的机会准则模型;Xiaoxia
Huang[8]提出了模糊环境下的均值一半方差投资组合模型;马
惠民_9]针对贷款组合优化模型的求解问题,提出了求解该问
题的二进制粒子群算法.在以前的研究中,有把贷款收益率
刻画为随机变量或模糊变量的,实际上,贷款收益率经常受各
种模糊和随机因素的影响,因此贷款收益率具有模糊随机性.
本文将贷款收益率刻画为模糊随机变量,使用半方差作为风
险度量方式,建立半方差约束下的模糊随机收益率贷款组合
优化模型.
在风险度量中,方差作为一种风险度量方式已经被广泛
采用,方差描述了收益率偏离其均值的程度,在一定程度上测
量了金融资产价值的变化程度.然而,随着风险研究的发展,
人们清楚地认识到用方差/标准差方法来度量投资项目的风
险具有很大的弊端,主要表现在:(1)方差/标准差方法的假设
较为严格,它要求投资收益率必须服从正态分布,这与实际出
入较大,往往难以满足;(2)方差/标准差方法把样本值对于均
值(数学期望)的所有波动,不管是向上的偏差还是向下的偏
差,都计算为风险,这有违投资者对风险的真实心理感受.在
实际的项目投资中,投资者关注的是收益低于期望值的可能
性,而超出部分则是超额收益,通常不视为风险[1.因此,假
定资产收益率的分布具有正偏度,使用方差/标准差有可能高
估了风险的程度;假定资产收益率的分布具有负偏度,使用方
差/标准差就有可能低估了风险的程度.为了避免方差度量
到稿日期:2009—06—21返修日期:2009—08—30本文受山东省教育厅科研发展计划项目
(J08LJ54)资助.
潘东静(197O一),女,硕士,副教授,主要研究方向为不确定决策,智能算法
等,E-mail:pdj1970@163.corn.
?
29l?
的风险,有些学者提出了下侧风险度量方法,如半方差法,下
偏距等,半方差能较直观地反映贷款的风险程度,因此本文采
用半方差作为风险的度量.
本文第2节介绍模糊随机的相关概念;第3节介绍半方
差的概念和特性;第4节建立半方差约束下的模糊随机收益
率贷款组合优化模型;第5节给出混合智能算法的求解过程;
第6节用具体的实例阐明模型及算法的应用;最后对全文进
行简单总结.
定义5口]设为模糊随机变量,且期望值e有限,则称
臼一E[(一)]为的方差.
定义6设为模糊随机变量,且期望值e有限,则称S
[朗一E[[()一]]为的半方差.其中
()一f’苎10,右P
性质若为模糊随机变量,V[臼和s[臼分别是拿的方
差和半方差,则O?sE臼?Vr[鲴.
2预备知识4具有半方差约束的贷款组合模型
模糊随机变量是模糊随机现象的一种数[臼=f{车?r}dr--f{?r}drJUJ—一
为模糊变量的期望值.
定义2[“假设是一个从概率空间(Q,A,Pr)~lJ模糊变
量集合的函数,如果对于R上的任何B0re1集B,Pos{e()?
B}是的可测函数,则称为一个模糊随机变量.
例1(fl,A,Pr)为概率空间,如果n=(?1,(c,2,…,),
并且,,…,是模糊变量,那么函数
若(U一1
若?:
若:
是一个模糊随机变量.
例2:(1D,lD+1,ID+2),其中p~N(O,1),e为一个模义4[1lJ设e为定义在概率空间(Q,A,Pr)上的
模糊
随机变量,则称
ro.rO
E[臼一{{?QJ?()]?r)dr--{P厂f?QJU—..
I()]?r}dr
为e的期望值,为避免出现..一cx3的情形,要求上式右端中两
个积分至少有一个有限.
?
292?
设对种项目进行贷款,z=(,X2,…,)为决策向量,
Xi表示对第i种项目贷款的比例,=(6,,…,靠)为,2种贷
款的收益率组成的向量,8为模糊随机变量,风为预置的收
益率水平,在一定的半方差约束下,如果决策者想极大化贷款
组合的收益率不低于预置水平的机会,可建立如下的相关机
会规划模型.
maxCh{?五色>jR0}(口)
l一1
.t.
sEExz]?y(M1)
?z=1
i=】
?O
如果退化为一个随机向量,极大化机会Ch{?蕾?i一1
n
R.}(a)意味着极大化概率Pr{?五?岛},模型(M1)退化为i21
(M2).
maxPr{?丑8?Ro}
i=l
S.t.
sEEx,~t]?y(M2)
?嚣=1
=1
五?0
如果8退化为一个模糊向量,极大化机会Ch{?,?
i=1
n
Ro}(a)意味着极大化可信性Cr{?嚣&?扁},模型(M1)退化
i=1
为(M3).
inaxCr{?五?R0}
2萱1
s.t.
sE西蚵?),(M3)
?z=1
i=1
-z?O
5混合智能算法求解过程
本文使用集成了模糊随机模拟,神经元网络以及遗传算
法的混合智能算法[15q7]对(M1)进行求解,过程如下.
5.1模糊随机模拟
设8为模糊随机变量,z为决策变量3)置为aN的整数部分;
(4)返回序列{,,…,}中第个最大的元素.
计算S[?矗]的模糊随机过程描述如下:I=l
首先计算期望值E[?],步骤为:(1)置e一0;(2)根
据概率分布Pr,从样本空间Q随机抽取样本叫;(3)—+E
[?z(叫)],其中EE?五()]可以通过模糊模拟得到;(4)
重复步骤2至3共N次;(5)期望值P—P/N.
再根据s[臼一E[[(—e)一].],通过模糊随机模拟计算
s[?五].
5.2训练神经网络
因为8为模糊随机变量,模糊随机模拟Ch{?蕾?R.)l=l
(a)和半方差s[?]的工作量很大,当模糊随机模拟嵌人
遗传算法后,计算量会相当惊人,为减少计算量,训练神经网
络来近似Ch{?&?R0)(a)和半方差s[?zl&].神经网络
使用多层前向神经元网络,本文设立了一个隐层,采用反向传
播算法训练神经元网络,神经网络有个输入层神经元,2个
输出层神经元,2个输出层神经元分别逼近Ch{??R.)
l=l
(a)和半方差s[?五8].
5.3遗传算法
初始化过程:一个可行解X一(z,zz,…,z)可以通过一
个染色体一(,,…,)表示出来,,,…,为基因,
是[O,1]区间随机产生的数,X和V之问的关系为
五一跳/(++…+),一1,2,…,
从而可以保证?丑一1总能够成立.对于模型(M1),使l—l
用训练好的神经网络计算S[?五],如果s[?五&]?y,则
对应的染色体一(,,…,)是可行的,否则是不可行
的.
交叉变异过程:对染色体进行交叉变异操作,通过训练好
的神经网络检验染色体的可行性,计算可行染色体的目标值,
得到每个染色体的适应度,通过旋转赌轮,选择染色体,重复
此过程到满足终止条件,最后将最好的染色体作为最优解.
5.4混合智能算法
(1)确定遗传算法中的种群规模pop—size,交叉概率,
变异概率.
(2)通过模糊随机模拟为不确定函数产生输入输出数
据.
U1:C{?五8?R0)(口)
:z—S[?丑.]
(3)根据产生的输入输出数据训练一个神经元网络逼近
不确定函数.
(4)随机产生pop—size个可行的染色体,并利用训练好
的神经元网络检验染色体的可行性.
(5)通过交叉和变异更新染色体,并利用训练好的神经
元网络检验子代染色体的可行性..
(6)通过神经元网络计算所有染色体对应的目标函数
值.
(7)按照目标函数值计算每一个染色体的适应度.
(8)通过旋转赌轮选择染色体.
(9)重复步骤(5)到步骤(8)直到完成给定的循环次数.
(1O)给出最好的染色体作为最优解.
6算例分析
假设在模型(M4)中有5种贷款,其收益率如表1所列.
假设预置的收益率风一o.05,置信水平a一0.6,半方差
约束为0.005,则模型(M4)表示如下:
JrmaxC{?五已?O.05}(0.6)
sEE五已]40.005(M4)
Jl
?Xi—Il乏o
利用混合智能算法求解模型(M4),算法中参数的设置如
下:模糊随机模拟500次,2000个训练样本,神经网络有5个
输入神经元,8个隐层神经元,2个输出层神经元.遗传算法
迭代500代,种群规模pop_size=30,交叉概率Pc—O.3,变异
概率一0.2.
表15种贷款收益率
第i种贷款收益率
?l一(Ol--0.015,P1+O.06,p1+0.085,P1+0.085)
‘其中D1,N(0.01,0.02)
?2(p2一O.O1,P2+O.07,P2+0.07)’
,
其中p2,N(O.02,0.03)
屯(O3—0.Ol,p3+O.O5,p3+O.O8,p3+0.08)
其中,N(O.01,0.03)
(P4,0.O2,P4+O.O7,P4+O.O9,P4+O.09)
‘其中p4,N(O.03,0.03)
e5一(P5--0.012,P5+0.08,P5+O.08)
其中,N(O.01,0.04)
通过运行智能算法,得a水平下收益率大于等于Ro的最
大本原机会测度为0.501930,最佳分配方案为一
(0.2310,0.3008,0.1236,0.3401,0.0045).遗传过程如图1
所示.
图1混合智能算法的遗传过程
?
293?
,为观察半方差约束对决策的影响,在不同的半方差约束
下,通过运行智能算法,得到不同的最大本原机会测度和决策
方案,如表2所列.
表2不同半方差约束下的最大机会测度和决策方案
结束语本文使用半方差作为贷款组合中的风险度量方
式,讨论在模糊随机环境下的贷款组合优化模型,将贷款收益
率刻画为模糊随机变量,建立半方差约束下的模糊随机收益
率贷款组合优化模型,并应用混合智能算法进行求解,通过实
例验证了模型和算法的有效性.
[1]
[2]
[3]
[43
[5]
参考文献
MarkowitzH.Portfolioselection[J].JournalofFinance,1952,
7:71-93
AltmanEI.CorporateBondandCommercialLoanPortfolioA—
nalysis[R].NewYork:NewYorkUniversitySalomonCenter,
1997
马志卫,刘应宗.基于蒙特卡洛模拟的贷款组合优化决策方法
[J].管理科学,2006,19(3):66—70
LiD,NgWan-Lung.Optimaldynamicportfolioselection:Multi—
periodmean-variancerormulation[J].MathematicalFinance,
2000,10(3):387—406
TrevorSE,WoodRJ.Asset_all0cationdecisionswhenriskis
changing[J].JournalofFinancialResearch,1999,22(3):301—
3】5
誓,200210I-,优化决策模型[J].中国管理科学,,);7
[7]宁玉富,唐万生,严维真.商业银行贷款组合优化决策的机会准
则模型[J].计算机工程与应用,2008,44(21);235—237,244
[8]HuangXiaoxia.Mean—semivariancemodelsforfuzzyportfolio
selection[J].JournalofComputationalandAppliedMathema-
tics,2008(217):1-8
[9]马慧民,叶春明.粒子群算法在贷款组合优化决策中的应用[J].
计算机工程与应用,2006(14):219—221,224
[1o]陆源,朱邦毅.基于半方差的投资项目风险度量模型研究[J].数
量经济技术经济研究,2005(7):90—95
[11]LiuYK,LiuBFuzzyrandomvariables:Ascalarexpectedvalue
operator[J].FuzzyOptimizationandDecisionmaking,2003,2
(2):143-160
[12]KwakernaakH.Fuzzyrandomvariables:I.Definitionsandtheo-
rems[J].InformationSciences,1978,15:1-29
[13]KwakernaakH.Fuzzyrandomvariables-II.Algorithmandexa-
mplesforthediscretecase[J].InformationSciences,1979,17:
253,278
[14]LiuB,LiuY—K.Expectedvalueoffuzzyvariableandfuzzyex-
pectedvaluemodels[J].IEEETransactionsonFuzzySystems,
2002(10):445—450
[15]LiuBFuzzyrandomchance-constrainedprogramming口].IEEE
TransactionsonFuzzySystem,2001,9(5):713-720
[16]LiuBFuzzyrandomchance-constrainedprogramming口].IEEE
TransactionsonFuzzySystem,2001,9(5):721—726
[17]LiuB,ZhaoRQ,WangG.UncertainprogrammingwithAppli—
cation[M].TsinghuaUniversityPress,2003
[18]GaoJ,IJiuB.Newprimitivechancemeasuresoffuzzyrandome—
vent[J].InternationalJournalofFuzzySystem,2001,3(4):527—
531
[19]占德胜,唐加山.关于扰动广义cox保险风险模型的破产概率
[J].重庆邮电大学学报:自然科学版,2007,21(6):782-784
(上接第256页)
[11]StengerB,RameshV,ParagiosN,eta1.TopologyfreeHidden
MarkovmodelstApplicationtobackgroundmodeling[C]IEEE
InternationalConference0nComputerVision.2001
[123SunYRHierarchicaJObiect—BasedVisua1AttentionforMa—
chineVision[I)].2003
[13]WangY,JiQADynamicConditionalRandomFieldModelfor
ObjectSegmentationinImageSequences[C]{IIEEEComputer
SocietyConferenceonComputerVisionandPatternRecogni—
tion.2005
[14]WangY,LoeKF,wuJK.ADynamicConditionalRandom
FieldModelforForegroundandShadowSegmentation[J].IEEE
TransactionsonPatternAnalysisandMachineIntelligence,
2006,28(2):279—289
[15]YaserS,MubarakS.BayesianModelingofDynamicScenesfor
ObjectDetection[J].IEEETransactionsonPatternAnalysis
andMachineIntelligence,2005,27(11):1778—1792
[163YinP,CriminisiA,winnJ,eta1.Tree-basedClassifiersforBi—
layerVideoSegmentation[c]?Proc.IEEEComputerVision
andPatternRecognition(CVPR).2007
[17]ZhouY,XuW,TaoH,eta1.BackgroundSegmentationUsing
?
294?
Spatial-TemporalMulti—ResolutionMRFEC]lIEEEWorkshop
onMotionandVideoComputing.2005
[18]ZhaiY,ShahMVisualattentiondetectioninvideosequencesu—
singspatiotemporalcues[c]?ACMInternationalConferenceon
Muhimedia.2006:815—824
[19]陈睿,邓宇,向世明,等.结合强度和边界信息的非参数前景/背
景分割方法[J].计算机辅助设计与图形学学报,2005,17(6):
1278—1284
[20]邬正平,佳俊,陈纯.一种基于动态规划的视频分割方法[J].
计算机辅助设计与图形学学报,2002,14(8):743—746
[21]高丽,杨树元,李海强.,种有效的基于时空联合的视频对象自
动分割新算法口].中国图象图形学报,2005,9(10):1096—1104
[22]楮一平.基于条件随机场模型的视频目标分割算法研究[D].杭
州:浙江大学,2008
[23]吴思,林守勋,张勇东.基于动态背景构造的视频运动对象自动
分割[J].计算机学报,2005,8(28):1386—1392
[24]王林波,赵杰煜.基于贝叶斯学习的视频图像分割[J].中国图象
图形学报,2005,9:1073—1078
[25]赵明,李娜,陈纯.采用统计推断的自动视频对象分割[J].计算
机辅助设计与图形学学报,2003,15(3):318-323
范文四:随机优化技术研究
本科毕业设计论文 题 目 :随 机 优 化 技 术 研 究
专业名称:
学生姓名:
指导教师:
毕业时间:
毕业
任务书
一、题目
随机优化技术研究
二、指导思想和目的要求
1. 随机优化技术
优化是人类在生产和社会活动中所追求的目标, 也是人们在工程技术、 科学 研究等诸多领域中经常遇到的问题。 在人类的生产和社会活动中, 要办好一件事 (指规划、设计等),都期望能够得到最满意、最好的结果或效果。为了实现这 种期望,必须有好的预测和决策方法。
优化是以数学为基础, 用于求解各种工程问题优化解的一种应用技术。 作为 一个重要的科学分支, 最优化理论和方法一直受到人们的广泛重视, 它对多个学 科都产生了重大影响, 优化算法是一种搜索过程或规则, 它基于某种思想和机制, 通过一定的途径或规则来得到满足用户问题要求的优化解。
2. 蚁群优化算法
20世纪 50年代中期创立了仿生学, 人们从生物进化的机理中受到启发。 提出 了许多用以解决复杂优化问题的新方法,如进化规划、进化策略、遗传算法等, 这些算法成功地解决了一些实际问题。
20世纪 90年代意大利学者 M . Dorigo , V . Maniezzo , A . Colorni 等从生物 进化的机制中受到启发, 通过模拟自然界蚂蚁搜索路径的行为, 提出来一种新型 的模拟进化算法——蚁群算法, 是群智能理论研究领域的一种主要算法。 用该方 法求解 TSP 问题、分配问题、 job-shop 调度问题,取得了较好的试验结果.虽然 研究时间不长, 但是现在的研究显示出, 蚁群算法在求解复杂优化问题 (特别是 离散优化问题)方面有一定优势,表明它是一种有发展前景的算法。
3. 粒子群优化算法
Kennedy 在他的书中描述了粒子群算法思想的起源。
自 20 世纪 30 年代以来,社会心理学的发展揭示:我们都是鱼群或鸟群聚 集行为的遵循者。 在人们的不断交互过程中, 由于相互的影响和模仿, 他们总会
变得更相似, 结果就形成了规范和文明。 人类的自然行为和鱼群及鸟群并不类似, 而人类在高维认知空间中的思维轨迹却与之非常类似。 思维背后的社会现象远比 鱼群和鸟群聚集过程中的优美动作复杂的多:首先, 思维发生在信念空间, 其维 数远远高于 3;其次,当两种思想在认知空间会聚于同一点时,我们称其一致, 而不是发生冲突。
三、主要技术指标
本论文主要分析蚁群优化算法和粒子群优化算法技术研究的相关问题。 通过 工程实例,用 MATLAB 软件对优化方法进行分析和模拟演示,导出演示示意图。 算法的理论分析, 理论上的分析是一个算法解决实际问题的坚实基础。 因此, 本文对一类随机性算法的理论做了一些研究工作。 首先提出了一类解决连续优化 问题的基于记忆的禁忌算法,在相对较弱的条件,证明了此算法以概率为 l 收敛 到全局最优解。并且用类似手段证明了记忆模拟退火算法以概率为 1收敛到全局 最优解。
1)概述随机优化问题和机械优化设计的知识。
2)对蚁群优化算法和粒子群优化算法的相关内容做出简介。
3)掌握 MATLAB 分析软件,对蚁群优化算法和粒子群优化算法进行模拟。 四、进度和要求
第 1周:查阅资料,明确课题的目的及意义,完成开题报告。
第 2周:继续查阅具体的资料,学习优化设计的知识,并且翻译外文文献。 第 3-4周:学习蚁群优化和粒子群优化的基本的认识和文献资料。
第 5周:在前面学习的基础上,初步设计演示过程。
第 6-9周:学习 MATLAB 中的相关模块,做相关的练习,采集数据。 第 10-11周:在先前的学习的基础上参照教程建立简单的模型, 并进行分析。 第 12周:根据前期搜集的资料,开始着手论文的撰写。
第 13周 : 运用 MATLAB 对蚁群优化算法和粒子群优化算法编制程序。 第 14周:根据分析的结果,进一步完善论文。
第 15周:根据学校的要求对论文的格式进行修改。
第 16周:进行毕业论文的答辩工作。
五、主要参考书及参考资料
[1] 王凌.智能优化算法及其应用 [M].北京:清华大学出版社, 2001.
[2] 邢文训,谢金星.现代优化计算方法 [M].北京:清华大学出版社, 1999. [3] 俞国燕,郑时雄,刘桂雄,等.复杂工程问题全局优化算法研究川.华南理 工大学学报 (自然科学版 ) , 2000, 28(8):104. 110.
[4] Nriwan Ansari著.李军译.用于最优化的计算智能 [M].北京:清华大学出 版社, 1999.
[5] 钱晓龙,唐立新, 刘文新. 动态调度的研究方法综述 [J].控制与决策, 2001, 16(2):141-145.
[6] 何坚勇.运筹学基础 [M].北京:清华大学出版社, 2000.
[7] 谢云.模拟退火算法综述 [J]微计算机信息, 1 998, 1 4(5):66— 68.
[8] GloverF . TabuSearch :partI[Jl, ORSA Journal onComputing , 1989, 1:190 — 260.
[9] Glover F. Tabu Search:part II[J]. ORSAJournal on Computing, 1990, 2:4-32. [10] Kennedy J, Eberhart R C. Particle SWalTfl. optimization[C]. Proceedings of IEEE International Conference on Neural Networks, Piscataway,NJ , 1995, 4: 1942— 1948.
[11] Glover F’ Laguna M, R . Marti . ScaRer Search and Path Relinking:Advances and Applications[A]. Handbook of Metaheuristics[M]. F Glover and G Kochenberger (Eds. ) , Kluwer Academic Publishers, Boston , 2003.
[12] Glover F ScaRer Search and Path Relinking[A]. New Ideas in Optimization[M], D.Come , M 。 Dorigo and F. GloveL Eds. , McGraw Hill, 1999, 297— 3 16. [13] Laguna M, Armentano V Lessons from Applying and Experimenting with Scatter Search[M]. To appear in Adaptive Memory and Evolution :Tabu Search and Scatter Search, Cesar Rego and Bahrain Alidaee(Eds. ) .
[14] 张怀锋,宋顺林。基于遗传学的改进蚁群算法研究 [M].2011.
[15] 庄昌文,范明钰,李春辉,虞厥邦.基于协同工作方式的一种蚁群布线系 统 [J].半导体学报, 1999, 20(5):400-406.
[16] COELLO C A C,GUTIERREZ R L Z,GARCIA B M,et al.Automated Design of
Combinational Logic Circuits Using the Ant System [J].Engineering Optimization,2002,34(2):109-127
[17] 樊晓平,罗熊,易晟,张航.复杂环境下基于蚁群优化算法的机器人路径 规划 [J].控制与决策, 2004, 19(2):166-170.
[18] 陈真勇,何永勇,褚福磊等.基于遗传进化的最近邻聚类算法及其应用 [J]. 控制与决策, 2002(17), 4:469-472.
[19] Shi Y, Eberhart R. A modified particle swarm optimizer[A]. In :IEEE World Congress on Computational Intelligence[C]. Piscataway , NJ :IEEE Press, 1998: 69-73.
[20] Shi Y , Ebethart R C . Empirical study of Particle swarm optimization[A] . In :Proceedings of the 1999 Congress on Evolutionary Computation[C]. Piscataway , NJ :IEEE Service Center, 1999:1945-1950. [21] Shi Y , Eberhart R C . Fuzzy Adaptive Particle Swarm Optimization[A] . In :Proc. Congress on Evolutionary Computation2001[C]. Seoul , Korea :IEEE Service Center, 2001.
[22] Donald E.Knuth, 《计算机程序设计艺术》 第 3版第 2卷, 清华大学出版社 (影 印版 ) , 2002.
[23] 史道济(译) , (哈佛大学 &布朗大学) 《概率与计算》 ,随机算法与概率分 析,机械工业出版社, 2007.
[24] 刘汝佳,黄亮, 《算法艺术与信息学竞赛》 ,清华大学出版社, 2004. 学生 指导教师 系主任
范文五:随机算法及其优化
随机算法及其优化
王斌 摘要:
NP难解问题是计算机算法和理论界长期研究的课题。由于随机算法有简单和快速的优势,近十几年来,通过随机算法求解NP难解问题的研究取得了较大进展。报告对Las Vegas和Monte Carol两种类型的随机算法进行详细的描述和分析,并举例说明其应用方法。在以往的实验中,人们发现在求解 NP难解问题时,随机算法的性能往往很不稳定.为提高算法的性能和稳定性,需要对算法进行优化。报告介绍了基于重启和竞争的两种优化方法,给出策略构造方法及相关数学证明.同时,对两种优化方法的适用范围和优化效果做了讨论,提出两种优化方法混合使用的设想。
一、绪论
本章由确定性算法引出非确定算法(随机算法),介绍随机算法在求解NP难解问题方面的应用。
1.1确定性算法和非确定性算法
算法是计算机领域中的一个最基本也是最重要的概念之一,形象的来说,算法可以看作是用某种精确的计算机语言如C、 Pascal、汇编或是某种抽象的算法语言例如伪代码写成的计算机程序,它可以用于解决某一类具体问题。可将算法定义如下:
定义1-1. 算法是一步一步求解问题的通用程序。
通常算法被认为是确定的,即当输入相同时,不论何时执行该算法,其输出都将是完全相同的,人们熟知的图灵机便是在这样一种假设下构造的计算模型。
随机算法(非确定性算法)的出现打破了这一观念。随机算法即使是在输入完全相同时,其输出也会随着每次执行而不同。其基本思想可以追溯到在数值计算、统计物理和系统仿真中常用的Monte Carlo方法,该方法可用于获取具有随机分布的复杂系统的定性信息。1955年de Leeuw提出了概率图灵机的概念,在传统的图灵机中引入了不确定因素,为随机算法的设计与分析构造了一个最基本的计算模型,Rabin和Gill等人在这个领域进行了开创性的工作[5]。
最早的随机算法出现在数论领域当中,例如Berlekamp提出的多项式分解算法和
Solovay等人提出的素性判定算法等[5]。1976年,Rabin则在[10]中通过数论和计算几何领域中的实例指出了随机化方法己成为算法设计的基本工具之一。从那以后,随机算法的应用越来越广泛,并且人们不断提出新的随机算法设计与分析技术。
1.2 NP难解问题及随机算法的引入
NP完全性理论是为了确定不同问题的难度,检验各个问题在难易程度上的相互关系而建立的理论。P和NP是该理论中的两个基本概念,其定义如下:
定义1-2. P是所有可以在多项式时间内用确定图灵机求解的判定问题的集合。NP是所有可在多项式时间内用非确定图灵机求解的判定问题的集合。
这样,如果一个问题属于P,则可以认为它是易于求解的。如果一个问题属于NP但不属于P,则它不一定存在多项式时间的算法。P是否等于NP是在计算机科学领域中至今尚未解决的一个著名难题。
人们一般认为P不等于NP[2],也就是说,存在一些NP问题,它们无法在多项式时间内用确定图灵机求解。1971年,Stephen Cook在ACM计算理论年会(STOC)上发表的论文“The Complexity of Theorem-proving Procedures"奠定了NP完全性理论的基础。他在该文中证明了所有的NP问题都可以多项式时间归约为“可满足性问题”(SAT)。这样,只要解决了SAT问题,也就解决了所有的NP问题,因此可以认为SAT问题是NP问题中“最难”的问题。后来,人们又证明了还有许多的NP问题例如旅行商问题、图着色问题等和SAT问题一样,都具有这种“最难”的性质,人们将它们归结为一类,称为NP完全问题。
定义1-2. 如果SAT问题归约成问题L,则称问题L是NP难解的。如果L是NP难解的且LeNP,则称问题L是NP完全的[2]。
这样, 有些问题是NP难解的,但不是NP完全的。例如NP完全问题必须是判定问题,其对应的优化问题就可能是NP难解的。
NP完全问题的应用非常广泛,在[11]的附录中列出了12大类,300多个NP完全问题,它们来自图论、网络设计、排序调度和数学规划等众多领域。然而,直至目前,还无法找到这些问题的有效算法,另一方面,人们也开始研究它们的近似算法或以一定概率求解的随机算法。
在1.1节提到,概率图灵机是随机算法的计算模型,虽然己经证明,概率图灵机的计算能力并不高于传统的图灵机,但后来的研究发现,对有些问题,概率图灵机上的算法平均性能要高于常规的确定性算法。在1977年,J.Gill指出,任何一个非确定图灵机都可以由一个
概率图灵机模型以较小的错误概率模拟[12],而NP完全问题定义为可以在非确定图灵机上以多项式时间求解的问题,这样随机算法也就可能成为求解NP完全问题的一种可行的途径。
二、随机算法
本章对Las Vegas和Monte Carol两种类型的随机算法进行详细的描述和分析,并举例说明其应用方法。
2.1 随机数
随机数在随机算法设计中十分重要,在现实计算机上无法产生真正的随机数,因此在随机化算法中使用的随机数都是一定程度上随机的,即伪随机数。
2.1.1伪随机数的产生
可以使用线性同余法产生伪随机数。线性同余法产生的随机序列a1,a2,...,an,...满足
?a0=d ??an=(ban?1+c)modmn=1,2,...
式中,b≥0,c≥0,d≥m。d称为该随机序列的种子。m应取得充分大,一般取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。
2.2 Las Vegas 算法
所谓随机算法,就是在执行过程中要做出随机选择的算法。总能给出正确的解,且两次运行之间唯一的区别是运行时间不同的随机法叫做 Las Vegas算法[3]。
2.2.1 Las Vegas算法的基本思想
Las Vegas算法属于随机算法中的一种。它具有随机算法的特点,即允许算法在执行的过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此随机算法可在很大程度上降低算法的复杂度。拉斯维加斯算法不会得到不正确的解,一旦用该算法找到一个解,那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失效的概率任意小[1]。
2.2.2 Las Vegas算法的描述和分析
通常用一个bool型函数表示Las Vegas算法。当算法找到一个解时返回true,否则返回false。Las Vegas算法的典型调用形式为
bool success=LV(x,y);
其中x是输入参数;当success的值为true时,y返回问题的解。当success值为false时,算法未能找到问题的解。此时可对同一实例再次独立地调用相同的算法。
设p(x)是对输入x调用Las Vegas算法获得问题的解的概率。一个正确的Las Vegas算法应该对所有输入x均有p(x)>0。在更强意义下,要求存在一个常数δ>0,使得对问题的每
设s(x)和e(x)分别是算法对于具体实例x求解成功或失败所需的个实例x均有p(x)≥δ。
平均时间,考虑如下算法:
void Obstinate(InputType x, OutputType &y)
{//反复调用Las Vegas算法LV(x,y),直到找到问题的一个解y
bool success=false;
while(! success) success=LV(x,y);
}
由于p(x)>0,故只要有足够的时间,对任何实例x,上述算法Obstinate总能找到问题的解。设t(x)是算法找到具体实例x的解所需平均时间,则有
t(x)=p(x)s(x)+(1?p(x))(e(x)+t(x)) 解此方程得
t(x)=s(x)+1?p(x)e(x) p(x)
2.2.3 Las Vegas算法求解问题举例
整数因子分解设n>1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式:n=p11p22...pkk,式中,p1<><><><>
int split(int n){
int m= floor(sqrt(double(n)); mmm
for(int i=2;i<>
if(n%i==0) return i;
return 1;
}
在最坏情况下,算法Split(n)所需的计算时间为Ω(n)。当n较大时,上述算法无法在可接受的时间内完成因子分割任务。对于给定的正整数n,设其位数为m=?log10(1+n)?。由n=θ(10m/2)知,算法Split(n)是关于m的指数时间算法。
到目前为止,还没有找到解因子分割问题的多项式时间算法。算法Split(n)是对范围在1~x的所有整数进行试除从而得到1~x2的任一整数的因子分割。
Pollard提出一个求整数n的因子分割的Las Vegas算法,该算法效率比Split(n)算法有显著提高,可在相同工作量下得到1~x4范围内整数的因子分割。
Pollard算法在开始时选取0~(n?1)范围内的随机数x1,然后递归地由xi=(xi2?1?1)modn产生无穷序列x1,x2,...,xk,...。
对于i=2,k=0,1,...以及2<>
求整数n因子分割的Las Vegas算法Pollard(n)可描述如下,其中,gcd(a,b)是求2个整数最大公因数的欧几里得算法。
void Pollard(int n ){
RandomNumber rnd;
int i=1;
int x=rnd.Random(n);//随机整数
int y=x;
int k=2;
while(true){ i++;
x=(x*x-1)%n; //xi=(xi2?1?1)modn
int d=gcd(y-x,n); //求n的非平凡因子
if((d>1)&&(d
if(i==k){
y=x;
}
对算法进行分析可知,执行算法的while循环约
个因子p。由于n的最小因子p≤
素因子。 k*=2;} } p次后,Pollard算法会输出n的一n,故Pollard算法可在ο(n1/4)时间内找到n的一个
2.3 Monte Carlo算法
在实际应用中常会遇到一些问题,不论采用确定性算法或随机算法都无法保证每次都能得到正确的解。Monte Carol算法在一般情况下可以保证对问题的所以实例都以高概率给出正确解,但通常无法判定一个具体解是否正确。
许多比较有效的近似算法如遗传算法、模拟退火、蚁群系统和局部优化等均可归入Monte Carlo算法[4]。
2.3.1 Monte Carlo算法的基本思想
Monte Carlo算法的基本思想是当所要求解的问题是某种事件出现的概率,或者是某个随机变量的期望值时,它们可以通过某种“试验”的方法,得到这种事件出现的频率,或者这个随机变数的平均值,并用它们作为问题的解。
它是用一系列随机数来近似解决问题的一种方法,是通过寻找一个概率统计的相似体并用实验取样过程来获得该相似体的近似解的处理数学问题的一种手段。
2.3.2 Monte Carlo算法的描述和分析
设p是实数,且1/2<><1。如果一个monte carlo算法对于问题的任一实例得到正确解的概率不小于p,则称该monte="" carlo算法是p正确的,且称p-1/2是该算法的优势。如果对于同一实例,monte="" carlo算法不会给出两个不同的正确解答,则称该monte="">1。如果一个monte>
有些Monte Carlo算法除了具有描述问题实例的输入参数外,还具有描述错误解可接受概率的参数。这类算法的计算时间复杂性通常由问题的实例规模以及错误解可接受概率的函数来描述。
对于一致的p正确Monte Carlo算法,要提高获得正确解的概率,只要执行该算法若干次,并选择出现频次最高的解即可。
在一般情况下,设 ε和δ是两个正实数,且ε+δ<1 。设mc(x)是一致的(1/2+ε)正确的monte="" carol算法,且cε="-2/log(1-4ε2)。如果调用算法MC(x)至少?cεlog(1/δ)?" 次,并返回各次调用出现频次最高的解,就可以得到解同一问题的一个一致的(1-δ)正确的monte="" carol算法。不论算法mc(x)的优势ε="">0多小,都可以通过反复调用来放大算法的优势,最终得到的算法具有可接受的错误概率。
设 n>Cεlog(1/δ)是重复调用(1/2+ε)正确的算法MC(x)的次数,且p=(1/2+ε),q=1?p=(1/2?ε),m=?n/2?+1。经n次反复调用算法MC(x),找到问题
的一个正确解,则该正确解至少应该出现m次,其出现错误概率最多是
∑Pr{n次调用出现i次正确}
i=0m?1
?n?≤∑??piqn?i
i=0?i?
m?1n??n/2=(pq)∑??(q/p)n/2?i
i=0?i?m?1
?n?≤(pq)∑??i=0?i?
=(pq)n/22nn/2m?1(由于q/p<1,且n>1,且n>
=(4pq)n/2
=(1?4ε2)n/2
≤(1?4ε2)(Cε/2)log(1/δ)
=2?log(1/δ)
=δ(由于对任意x>0有x1/1ogx=2)
由此可知,重复n次调用算法MC(x)得到正确解的概率至少为1?δ。如果重复调用一个
Carol算法2m?1次,得到正确解的概率至少为1-δ,式中, 一致的(1/2+ε)正确的Monte
m?12i???11(1?4ε2)m
2??δ=?ε∑????4?ε?≤4εm i2?i=0???i(由于0<><>
在实际使用中,大多少Monte Carol算法经过重复调用后正确率提高很快。
设MC(x)是解某个判定问题的Monte Carol算法。当MC(x)返回true时解总是正确的,仅当它返回false时有可能产生错误的解。称这类Monte Carol算法为偏真算法。
当多次调用一个偏真Monte Carol算法时,只要有一次调用返回true,就可以断定相应的解为true。在这种情况下,只要重复调用偏真Monte Carol算法4次,就可将解的正确率从55%提高到95%,重复算法6次,可提高到99%。对偏真Monte Carol算法,可将p>1/2放松为p>0。
对于一般问题,设y0是所求问题的一个特殊的解,对于一个解所给问题的Monte Carol算法MC(x),如果存在问题实例的子集X,使得:
(1)当 x?X 时,MC(x)返回的解是正确的;
(2)当x∈X时,正确的解是y0,但MC(x)返回的解未必是y0。
称上述算法MC(x)是偏y0的算法。
设MC(x)是一致的p正确偏y0的Monte Carol算法。MC(x)返回的解为y0。则
(1)当y=y0时,MC(x)返回的解是正确的。事实上,当x∈X时,MC(x)返回的解总是正确的。当x∈X时,正确解是y0,故此时算法返回的解也是正确的。
(2)当 y≠y0时
在这种情形下,当x ?X 时,y是正确的。当x∈X时,y是错误的。由于算法是p正确的,产生这种错误的概率不超过1-p。
在一般情况下,如果重复k次调用MC(x),所返回的解依次为y1,y2,...,yk,则
1)存在i使yi=y0,此时y0为正确解;
2)存在i≠j,使得yi≠yj,此时必有x∈X,因此可知正确解为y0;
3)对所以i有yi=y,但y≠y0,此时正确解仍有可能是y0。
如果情形3)发生,则每次调用MC(x)均产生错误解y,但发生这种情况的概率不超过(1?p)k。可知,重复调用一致的、p正确、偏y0的Monte Carol算法k次,可得到一个(1?(1?p)k)正确的Monte Carol算法,且所得算法仍是一致的偏y0的Monte Carol算法。特别地,调用一个偏真Monte Carol算法k次可将其正确概率从p提高到(1?(1?p))。 k
2.3.3 Monte Carlo算法求解问题举例
素数测试
Wilson给出了一个判定素数的定理,对于给定的正整数n,判定n是一个素数的充要条件是(n?1)!≡?1(modn)该定理理论价值很高,但实际用于素性测试所需的计算量太大,无法实现对较大素数的测试。到目前为止尚未找到素数测试的有效的确定性算法或Las Vegas算法。首先容易想到下面的素数测试随机算法Prime。
bool Prime(unsigned int n){
RandomNumber rnd;
int m=floor(sqrt(double(n)));
}
算法Prime返回false时,说明找到n的一个非平凡因子,可确定n是合数。但对上述算法来说,即使n是一个合数,算法仍以高概率返回true。
费尔马小定理为素数判定提供了一个有力工具,定理表述如下: unsigned int a=rnd.Random(m-2)+2; return (n%a!=0);
如果p是一个素数,且0
利用费尔马小定理,对于给定的整数n,可以设计素数判定算法。通过计算d=2n?1modn来判定整数n的素性。当d≠1时,n肯定不是素数;当d=1时,n很可能是素数,但不能确定一定是素数,因为有些合数(Carmichael数)也满足d=2n?1modn。可利用二次探测定理对算法进行改进,避免将Carmichael数误判为素数。
二次探测定理 如果p是一个素数,且0<><>
利用二次探测定理,可以在利用费尔马小定理计算an?1modn的过程中增加对整数n的二次探测。发现违背二次探测条件即可断定n不是素数。
下面的算法power用于计算apmodn,并在计算过程中实施对n的二次探测。
void power(unsigned int a, unsigned int p,unsigned int n,unsigned int &result,bool &composite){
unsigned int x;
if(p==0) result=1;
else{
power(a,p/2,n,x,composite);//递归计算
result=(x*x)%m; //二次探测
if((result==1)&&(x!=1)&&(x!=n-1)) composite=true;
if((p%2)==1) //p是奇数 result=(result*a)%n;
}
}
在算法power的基础上,可设计素数测试的Monte Carol算法Prime如下:
bool Prime(unsigned int n){
RandomNumber rnd;
unsigned int a,result;
bool composite=flase;
a=rnd.Random(n-3)+2;
power(a,n-1,n,result,composite);
}
算法Prime返回false时,整数n一定是合数。而当算法Prime返回true时,整数n在高概率意义下是素数。但仍可能存在合数n,对于随机选取的基数a,算法返回true。当n充分大时,这样的基数a不超过(n?9)/4个,由此可知Prime算法是一个偏假3/4正确的Monte Carol算法。
上述算法的错误概率可通过多次重复调用而迅速降低。重复调用k次Prime算法的Monte Carol算法PrimeMC可描述如下:
bool PrimeMC(unsigned int n,unsigned int k){
RandomNumber rnd;
unsigned int a,result; if(composite || (result!=1)) return false; else return true;
bool composite=flase;
for(int i=1;i<>
a=rnd.Random(n-3)+2;
power(a,n-1,n,result,composite);
if(composite || (result!=1)) return false;
}
return true;
}
易知上述算法的错误概率不超过(1/4),实际使用效果会比估计好的多。 k
三、随机算法的优化
本章介绍了基于重启和竞争的两种优化方法,给出策略构造方法及相关数学证明.同时,对两种优化方法的适用范围和优化效果做了讨论。
3.1问题的提出
Las Vegas算法在运行结束时总能给出正确的解,但其求解时间随着每次执行而不同; Monte Carol算法则不保证可以求出正确的解,其性能可以使用当前求出近似解的质量来衡量,在任一时刻其求解质量可以看作为一个随机变量,且求解质量的分布随着时间变化[1]。在以往的实验中,人们发现在求解 NP难解问题时,随机算法的性能往往很不稳定,即使对于完全相同的输入实例,当随机数种子变化时,算法的性能也可能有数量级的差别,造成算法的平均性能下降。为提高算法的性能和稳定性,需要对算法进行优化。随机竞争策略和重启策略是针对随机算法的两种不同改进策略,理论和实验分析均表明这些策略对随机算法的性能具有良好的改进作用。
3.2 基于重启的优化方法
重启策略是对Las Vegas算法进行优化的一种常用的优化方法。
3.2.1重启的概念
重启的思想在日常生活中很常见。例如在Internet上浏览WWW页面时,经常会遇到某个页面很长时间都无法显示的情况,这时如果中断该页面的下载,并按下浏览器上的刷新按钮重新启动传输,往往就会很快的显示出该页面。这是由于Internet上的路由具有不确定性,当某条网络路径出现阻塞时,重启可以选取一条新的路径进行传输[9]。如果将页面的传输
看作一个随机算法,传输的时间是算法的运行时间,这也就是使用基于重启的方法对随机算法进行优化的基本思想,我们简称之为重启策略。
如图3-1所示,重启策略就是指若随机算法执行到某一给定时间(阈值)仍未结束,则停止算法的运行并以新的随机数种子重新启动算法的运行,循环执行此步骤直至算法终止,其
中每次执行的阈值可以是不同的。
图3-1
设计重启策略的关键,就是确定重启的次数和每次重启的时间。根据重启次数的不同,可以将重启策略分为有限次重启策略和无限次重启策略两类,但如果允许重启时间为无限大,则可以将有限次重启策略也看作为无限次重启策略,即将所有后续的重启时间都设为无限大。
重启策略通常用于对Las Vegas算法的优化。
文献[6]使用连续概率分布对算法性能分布建模,针对 Las Vegas算法提出了一种高效的重启策略构造方法。该文从平均性能和稳定性两个角度分析了该方法的效率,将理论与实验结合起来,兼顾效率和通用性,从而得到了更有应用意义的结论。本报告在3.2.2节对此策略构造方法做了详细阐述。
3.2.2 重启策略的构造
尽管从绝对意义上来说,算法的性能分布并不是一个连续分布,但是将它近似为连续分布并不会改变其本质特征,同时可以简化分析的过程。从这些问题出发,文献[6]对随机算法的性能使用连续概率分布建模分析了周期重启策略的平均运行时间和运行时间方差与周期选取的关系,指出将策略的周期设为算性能概率密度函数的极值点是一种高效的构造方法,并从平均性能和稳定性两个角度分析了该方法的效率,同时通过将策略应用于求解大规模 TSP问题验证了结论。
首先我们从性能分析的角度出发 ,在定义3.1-3.3分别给出了本文中使用的 Las Vegas算法运行时间、重启策略和周期重启策略的形式化定义。
ω定义 3.1. Las Vegas算法 A对某个固定输入实例ω的运行时间定义为PA,
ω其中ω∈Ω,Ω是算法A的输入实例空间.PA 是一个取值在正实数空间的随机
ωωω变量,其均值和方差分别记为E(PA)和V(PA)。我们称PA对应的概率分布为算
法的运行时间性能分布,简称为性能分布.
t1>0,定义 3.2. Las Vegas算法的重启策略定义为序列S={t1,t2,...,ti,...} ,
i∈Z+,表示算法依次独立执行时间ti,若满足结束条件则算法终止.
定义 3.3.若对重启策略S={t1,t2,...,ti,...},有?i>0,ti=t0,其中t0>0为一个常数,则称s为周期重启策略,记 t0为策略 s的周期,并记 Las Vegas算法
ωA在策略s下对输入实例ω的运行时间为 PA(t0)。
文献[6]指出在连续模型假设下,从平均性能的角度来看,Las Vegas算法的最优重启策略是一个周期重启策略,并给出了严格数学证明。而对于周期重启策略,只有一个参数需要确定,也就是重启的周期,周期的值可以为无限大,对应直接运行原算法的情况。引理
3.1给出了周期重启策略的平均运行时间和运行时间方差的表达式。
引理3.1.设有 Las Vegas算法 A和周期为t0的重启策略 S,算法A对输入
ω实例ω∈Ω的运行时间PA(t0)有概率密度函数f(t),则其平均运行时间为
ωE(PA(t0))=(M1(t0)+t0(1?M0(t0)))/M0(t0)。运行时间的方差为
其ωV(PA(t0))=(M2(t0)+t0(1?M0(t0))(2M1(t0)/M0(t0)+t0(2/M0(t0)?1)))/M0(t0)
中 Mk(t)=∫f(x)xkdx。 0t
由定义3.3,我们可以将直接执行原算法看作为周期为无穷大的周期重启策略,即有
ωωE(PA(?∞))=E(PA)
V(PA(+∞))=V(PA)
为了构造最优的周期重启策略,需要对原算法的性能分布进行研究。在文献[19]中,通过实验指出,对于任意一个固定的实例,算法的性能分布可以用对数正态分布 ωωf(t)=1e2t?(logt?μ)22σ来很好地拟合。这里参数μ,σ的值是与具体输入实例相关的,但为了简洁起见,我们仍使用μ,σ符号。
基于以上假设,通过引理3.1,可以得到周期重启策略的平均运行时间和运行时间方差与周期选取的关系,即随着周期的增加,周期重启策略平均运行时间和运行时间方差都是先减小然后增加,存在一个明显的极值点。这是由于周期太小,每次算法就得不到充分的运行,但周期太大,又相当于执行原算法.无法体现策略的改进作用,这样周期的选择就成为一个必须要考虑的问题。
令周期t0=eμ+kσ2,其中k是任意实数.记 Q为周期重启策略相对原算法平均运行时
间减小的倍数,Q的值越大代表重启策略的效率越高,若 Q的值小于 1 则表示重启策略对该算法是无效的。由引理3.1,有
ωE(PA)Q=E(PA(t0))
=(1+Erf(kσ/2)/(1+Erf((k?1)σ/2)+e(k?1/2)σ(1?Erf(kσ/2))) Erf(x)=?22
其中误差函数∫x
0edt?t2,误差补函数Erfc(x)=1?Erf(x)。Q的值与μ无
关,而只与σ有关。
下面定理3.1对提出的构造方法的效率进行了分析。
定理3.l 设有 Las Vegas算法 A和周期为t0的重启策略S,算法 A对输入
?1ωe实例ω∈Ω的运行时间PA(t0)有概率密度函数f(t)若f(t)=2t(logt?μ)22σ ,
t0=eμ?σ2ωω,则当σ>1.18时有E(PA(t0)) ωωV(PA(t0)) V(PA) 。 定理 3.1分析了我们提出的构造方法的效率,即将周期选取为原算法概率密度函数的极值点时,其效率只与σ有关。它也说明了算法性能分布的方差越大,重启策略的作用也越大,这在直观上是可以理解的,因为方差越大代表算法运行时间偏离均值的幅度越大,而使用重启策略可以使算法的性能变得“集中”。在实际应用中,测量μ,σ的值较为困难,然而针对具体问题估计算法运行时间密度函数的极值点是可行的,在文献[5]中针对旅行商 问题给出了一种估计极值点的方法。 3.2.3 求解NP问题的应用 TSP问题是一个经典的 NP难解问题,它要求找出经过N个城市恰好一次的最短周游路线.循环LK算法[5]则是一个典型的用于求解 TSP问题的高效算法,对于规模适度的问题实例可以在较短时间内求得最优解,但对于较大规模的实例往往会陷入局部最优,无法得到全局最优解。文献[6]将上节提出的重启策略构造方法应用于循环 LK算法进行了实验.验证了这样几个结论: (1)随着周期的变化,算法的平均运行时间和运行时间方差存在一个最优点,且达到最优点的位置非常接近。 (2)选取重启策略的周期为性能分布的极值点是一种高效的策略构造方法,且算法性能分布的方差越大,重启策略的效率也越高。 (3)使用对数正态分布模型对算法性能分布拟合得到的值决定了其被优化的难度。 3.3 基于竞争的优化方法 竞争策略是对Las Vegas算法进行优化的一种常用的优化方法,同时,该方法也可用于对Monte Carol算法的优化。 3.3.1 竞争的概念 竞争的思想来源于并行计算中对超线性加速的研究。在某些并行算法或程序中,可能会出现超线性加速现象,也就是加速倍数超过处理器数的现象。例如在某些并行搜索算法中,允许不同的处理器在不同的分枝方向上同时搜索,当某一处理器一旦迅速找到了解,它就向其余的处理器发出终止搜索的信号,这就会提前取消那些在串行算法中所作的无谓的搜索分枝,从而出现超线性加速现象;又如在绝大多数并行机中,每个处理器均有少量的高速缓存,当某一问题执行在大量的处理器上,而其大多数的数据均放在高速缓存中时,总的计算时间趋于减小,如果由于这种高速缓存效应所造成的计算时间下降补偿了由于通信等所造成的额外开销时间,则有可能造成超线性加速现象。 文献[8]专门研究了随机算法造成的超线性加速。文献[13]对 并行竞争策略的加速比进行了理论分析,指出在处理器数目较小时可以达到接近线性的加速比。文[14] 研 究了并行竞争策略在求解SAT问题中的应用,他们假设算法的性能分布为线性分布,指出此时应有线性的加速比,其实验结果显示使用10个处理器时加速比可以达到6~7。Hogg等人[15]分析了竞争策略在图着色问题中的应用,指出当算法性能分布为multi-model时,可以达到较高的 加速比。目前对于竞争策略的研究大都集中在其在并行计算中的应用,实际上,如果在并行机上能达到超线性的加速比,则将所有的程序在单机上按多进程运行也可以比直接执行要快。 随机竞争策略是用于改善Las Vegas算法性能的策略,其基本思想是对同一个问题实例,将算法的多个拷贝使用不同的随机数种子同时执行(从而各自的计算过程也不同),并采取竞争的方式,当其中一个拷贝计算结束时便结束整个计算的运行。目前的研究表明随机竞争策略对Monte Carlo算法的性能也具有良好的改进作用。 3.3.2 竞争的策略 如果要使用竞争策略,有两个问题需要进行研究[5]: 1) 何时能用竞争策略来改进随机算法的性能? 2) 如何选取竞争策略的参数使其性能达到最优? 我们将在下一小节基于对随机算法性能分布的分析,对竞争策略的效率开展研究。 竞争策略的效率分析 竞争策略只有一个参数,也就是拷贝的个数,我们需要分析拷贝个数对策略性能的影响。若共有k个拷贝,则运行时间为t时每个拷贝的实际运行时间为t/k,此时算法还未运行结束的概率为(1?∫t/k 0f(x)dx)k,其中f(t)为算法性能分布的概率密度函数,则使用竞争策 略以后的概率分布函数应为1-(1? 数为(1?∫t/k0f(x)dx)k,对其求导可得此时性能分布的概率密度函∫t/k 0f(x)dx)k?1f(t/k),通过计算,命题3-1给出了使用竞争策略后平均运行时间 的表达式。 命题3-1 设有Las Vegas算法A和竞争策略Sk,A对ω∈Ω有概率密度函数f(t),则策略的平均运行时间为E(Sk(A(ω)))=∫(1?∫0+∞t/k0f(x)dx)k?1f(t/k)tdt。 和分析重启策略一样,假设随机算法的性能分布符合对数正态分布模型。首先分析此时竞争策略的平均运行时间与拷贝数目的关系。将f(t)=1e2t ?x)?(logt?μ)22σ2代入命题3-1,可以得到:E(Sk(A(ω)))=k2eμ ∫+∞ ?∞((1?Erf(x))/2)k?1ex(dx。 设竞争策略相对原算法平均运行时间减小的数倍为P,可以计算出 eσ/2E(A(ω))P==E(Sk(A(ω)))k2+∞((1?Erf(x))/2)k?1ex(∫?∞22?x)dx 这样,P的值与μ无关,而只与σ和k有关,这里k是代表拷贝的数目。P的值越大代表竞争策略的性能越高,若P的值小于1则表示竞争策略对该算法是无效的。当σ较大时,k越大性能越高,但到达一定大小以后(20左右)增加k的值对性能的影响很小[5]。当σ比较小时,存在一个最优的k值,使竞争策略的性能最优,这个值在10到20之间。而当σ非常小时(小于1),使用竞争策略是无法改进算法性能的。文献[5]通过实验也验证在单机上直接使用竞争策略的算法性能不如使用重启策略的算法。 并行竞争策略及其分析 虽然竞争策略在单机上的性能不如重启策略,但是它有一个最大的优点,也就是其并行性非常好,各进程之间基本没有通信,可以直接在并行机或是工作站机群上实现,而重启策略是难以并行实现的。 定义3-4和命题3-2分别给出了并行竞争策略的形式化定义和加速比的公式。 定义3-4 Las Vegas算法的并行竞争策略定义为PSk,表示将算法在具有k个处理器的并行机上执行,每个处理器执行一个拷贝,若有一个处理器运行结束则策略终止。记Las Vegas算法A在并行策略PSk下对输入实例ω的性能变量为PSk(A(ω))。 命题3-2设有Las Vegas算法A和并行竞争策略PSk,A对ω∈Ω有概率密度函数f(t),则策略在并行机上的平均运行时间为 E(PSk(A(ω)))=∫k(1?∫f(x)dx)k?1f(t)tdt 00+∞t 加速比为Sp(PSk(A(ω)))=∫+∞ 0f(t)tdt/E(PSk(A(ω))) 并行效率为Eff(PSk(A(ω)))=Sp(PSk(A(ω)))/k。 ?1e假设算法的性能分布符合对数正态分布模型,将f(t)=2πσt(logt?μ)22σ代入命题3-2, 可以得到, 加速比Sp(PSk(A(ω)))=eσ +∞ ?∞2/2k?1x(?x)k∫((1?Erf(x))/2) k2, edx。 并行效率Eff(PSk(A(ω)))=eσ2/2 k?1x(?x)∫+∞ ?∞((1?Erf(x))/2)edx 加速比的值与μ无关,而只与σ和k有关,若加速比的值小于1则表示并行竞争策略 对该算法是无效的。 文献[5]指出对于性能方差大的算法,并行竞争策略往往可以达到超线性的加速比,大大减少平均运行时间,对于性能方差小的算法,也可以通过增加处理器数来减小算法的运行时间。 3.3.3 对Las Vegas算法的优化效果 根据3.3.2节的理论分析,我们可以得出如下结论:随机算法的性能分布可以和对数正态分布模型很好的拟合,竞争策略的性能取决于性能分布中的σ值,对于相同的拷贝数,σ值越大,性能越高,而当σ小于1时,竞争策略无法对算法进行优化。文献[5]通过对TSP问题的若干实例的Las Vegas算法实验验证表明,直接使用竞争策略对算法的优化效果不如重启策略。 3.2.2节的分析和相关实验表明,尽管在单机上竞争策略的性能不如重启策略,但是其并行性非常好。对于性能方差大的算法,往往可以达到超线性的加速比,大大减少平均运行时间,对于性能方差小的算法,也可以通过增加处理器数来减小算法的运行时间。 3.3.4 对Monte Carol算法的优化效果 由于 Monte Carlo算法并不保证总能求出问题的解,所以上述在 Las Vegas算法中使用的随机竞争策略应修正为将算法的多个拷贝同时执行,并不断输出当前各拷贝中最好的解。因为Monte Carlo算法求解质量的分布随时间而变化,故对它的性能分析要比Las Vegas算法更加复杂。文献[4]给出的理论分析和实验结果均显示该策略对Monte Carlo算法在许多情况下是一种有效的改进策略,可以提高原算法的性能和稳定性。 定义3-5. 最小化问题定义为Π(Ω,S,c),其中Ω是输入实例空间,S是可行解空间,c是目标函数,要求对实例ω∈Ω找到s*∈S使得c(s*,ω)=min(c(s,ω))。 s∈S 注:本文中假定c(s,ω)≥0。一般的最优化问题均可变换为这类最小化问题。在实际应用中,c(s,ω)应视为可行解s在实例ω中的质量。 定义3-6.求解最小化问题Π(Ω,S,c)的Monte Carlo算法定义为RA(Ω,F,m),其中Ω是输入实例空间;F是二元函数F(x,t)的空间,其中x,t≥0,且对给定的t0,F(x,t0)是一个概率分布函数;m是Ω到F的映射,将实例ω∈Ω映射为二元函数m(ω)(x,t)∈F,对给定的t0,记具有分布m(ω)(x,t0)的随机变量为m(ω)(t0)。 注:在实际应用中,m(ω)(t0)视为RA求解实例ω时在时刻t0的求解质量,其期望记为m(ω)(t),m(ω)(x,t0)则是在此时算法的求解质量小于x的概率。在不引起混淆的情况下,我们记F(x,t)=m(ω)(x,t)为算法RA对实例ω的质量分布函数。本文中假定所讨论的质量分 布函数均可导,并记f(x,t)=Fx′(x,t)为相应的质量密度函数。 定义3-7. 若有RA(Ω,F,m),则其随机竞争策略定义为RCSRAk(Ω,F,mk),其中m(kω)(t)=min(mj(ω)(t/k)),ω∈Ω,t≥0,对1≤j≤k,有mj(ω)(t)=m(ω)(t)。 1≤j≤k 注:对给定的k,相应的随机竞争策略可称为k-随机竞争策略,其中k称为拷贝的数目。 定义3-8. 若有RA(Ω,F,m)及其对应的随机竞争策略RCSRAk(Ωk,Fk,mk), 则随机竞争策略RCSRAk的效率定义为E(ω,t)=m(t)/mk(t),其中ω∈Ω,t≥0。(ω)(ω) 注:效率也就是在求解实例ω∈Ω时RA与RCSRAk在时刻t的平均求解质量之比.若效率的值大于1,则说明随机竞争策略是有效的。 定理3-2. 若有RA(Ω,F,m),RA对实例ω∈Ω的质量分布函数和质量密度函数分别为F(x,t)和f(x,t),x,t≥0,则RA对应的k-随机竞争策略算法c对同一实例ω的质量分布函数和质量密度函数分别为1?(1?F(x,t/k))k和k(1?F(x,t/k))k?1f(x,t/k)。 证明. 设RCSRAk对实例ω的质量分布函数为G(x,t),则G(x,t)是随机变量m(ω)(t)的分k布,由定义3可知,m(ω)(t)=min(mj(ω)(t/k)),ω∈Ω,t≥0,即有 1≤j≤kk 1?G(x,t)=(1?F(x,t/k))k, G(x,t)=1?(1?F(x,t/k)).k k?1对x求导可得相应的质量密度函数为k(1?F(x,t/k))f(x,t/k). 证毕. 定理3-3分析了当算法的质量分布服从对数正态分布时随机竞争策略对算法的性能和稳定性的影响。 定理3-3. 若有RA(Ω,F,m),RA对实例ω∈Ω的质量 密度函数为 ?(1f(x,t)=e2πσxlnx?μσ)2/2,其中u=lnz(t),x,t≥0,z(t)>0.则RA对k-随机竞争策 略算法RCSRAk(Ωk,Fk,mk)对同一实例ω的平均求解质量和求解质量的方差分别为∫(Erfc(0+∞lnx?u/2)kdx和 22∫+∞ 0+∞lnx?ulnx?ukx(Erfc()/2)dx?(∫(Erfc(/2)kdx)2。 02σ2σ 由定理3.3可以计算出随机竞争策略的平均求解质量,从而可求出其效率。文献[4]用图示的方法分析了在算法的质量分布为对数正态分布的情形下随机竞争策略的效率和方差,得出,随机竞争策略在如下两种情况下可以获得较好的效率和稳定性: 1)原算法求解质量的方差较大时,也就是稳定性较差时。 2)原算法的平均求解质量随时间下降比较慢时,也就是收敛性较差时。 同时,文献[4]在使用循环LK算法求解TSP问题中对该策略进行了实验分析,经过该策略改进后的算法性能和稳定性均有提高,平均求解质量可以达到原算法的两倍以上,显示出该策略具有很强的应用价值。 3.4 优化方法的讨论 随机竞争策略和重启策略是针对随机算法的两种不同改进策略,理论和实验分析均表 明这些策略对随机算法的性能具有良好的改进作用,不同策略之间也具有一定的联系。 3.4.1 两种优化方法的混合应用的尝试 文献[5]通过单机上TSP(旅行商)问题的实验,对两种优化方法混合使用做尝试,即在竞争策略的各拷贝之间都采用最佳的周期重启策略来执行循环LK算法。实验结果表明随着拷贝数目的增加,竞争策略的性能不断降低,无法对使用重启策略优化后的算法性能作出改进。出现这种情形的原因在于使用重启策略以后,算法性能的方差都变的很小,这时再使用竞争策略是无法得到更好的性能的。 但3.2.2节的分析和相关实验表明,尽管在单机上竞争策略的性能不如重启策略,但是其并行性非常好。对于性能方差大的算法,往往可以达到超线性的加速比,大大减少平均运行时间,对于性能方差小的算法,也可以通过增加处理器数来减小算法的运行时间。 目前尚没有对并行竞争策略和重启策略混合使用的实验报告和分析,这方面的尝试对算法性能的影响有待进一步讨论。 四、结束语 Las Vegas和Monte Carol两种类型的随机算法对于求解NP难解问题有较好的效果。但在以往的实验中已证实在求解 NP解问题时,随机算法的性能往往很不稳定。为提高算法的性能和稳定性,需要对算法进行优化。重启策略和随机竞争策略是两个通用的随机算法改进思路,而且其实现也并不复杂。通过上述报告的分析,我们可得出如下结论: 1)两种随机算法的性能分布可以和对数正态分布模型很好的拟合。 2)对于重启策略,周期性重启策略是最优的重启策略,选取重启策略的周期为性能分布的极值点是一种高效的策略构造方法,且算法性能分布的方差越大,重启策略的效率也越高。通过选取极值点构造重启策略具有较好的通用性,但极值点的计算比较困难。重启策略主要应用于Las Vegas算法的优化。 3)对于竞争策略,与重启策略相同,性能分布的方差越大,效率越高。策略的构造较重启策略更为简单,只需确定k,即运行拷贝的个数。竞争策略采取并行方式可获得超线性加速,会对随机算法起到更好的优化效果。竞争策略既可用于Las Vegas算法的优化,也可用于Monte Carol算法的优化,对两种算法的优化都可以得到较好的优化效果。 参考文献 [1] 王晓东.计算机算法设计与分析[M].电子工业出版社 2007. [2] 张立昂,王捍贫,黄雄.计算理论导引[M].机械工业出版社 2000. [3] 贺红,马绍汉.随机算法的一般性原理[J].计算机科学,Vol.29,No.1,2002,p90-92 [4] 谢幸,周智,陈国良,顾钧.随机竞争策略在Monte Carlo算法中的性能分析[J],计算机学 报,Vol.23,No.10,2000,p1015-1020 [5] 谢幸. NP难解问题随机算法的优化方法[D].中国科学技术大学计算机系,合肥.2001 [6] 陈国良,谢幸,徐云,顾钧.随机算法重启策略的构造及其在TSP中的应用[J],计算机学 报,Vol.25,No.5,2002,p514-519 [7] Mehrotra R. and Gehringer E.F.,Superlinear Speedup Through Randomized Algorithms[J], Proc. Of 1985 Intl. Conf. on Parallel Processing,1985,p291-300 [8] Huberman B.A., Lukose R.M. and Hogg T., An Economics Approach to Hard Computational Problems[J],Science,Vol.275,1997,p51-54 [9] Maurer S.M. and Huberman B.A.,Restart Strategies and Internet Congestion, Technical Report, Xerox Palo Alto Research Center,1999 [10] Rabin M.O., Probabilistic Algorithms,In: Algorthms and Complexity,Recent Results and New Directions,Traub J.F.Ed.,Academic Press,New York,1976,p21-39 [11] Garey M.R. And Johnson D.S., Computers and Intractability: A Guide to the Theory of NPCompleteness,W.H.Freeman,San Francisco,1979 [12] Gill J.T.III, Computational Complexity of Probabilistic Turing Machines, SIAM J. Comput.Vol.6 1977, p675-695 [13] Luby M. And Ertel W., Optimal Parallelization of Las Vegas Algorithms, Symp. On Theoretic Aspects of Computer Science,1994,p463-475 [14] 金人超,黄文奇,并行计算:提高SAT问题求解效率的有效方法,软件学报, Vol.11,No.3,2000,p398-400 [15] Hogg T. And Williams C., Expected Gains from Parallelizing Constraint Solving for Hard Problems, Proc. Of AAAI-94,1994,p331-336 转载请注明出处范文大全网 » 基于随机_模糊理论的岩体力学