（控制理论与控制工程专业论文）序优方法及并行仿真方法在离散事件动态系统中的应用.pdf

摘要 离散事件动态系统 d e d s 的分析 设计 及优化通常面临着三个方面的 困难 系统结构信息的缺乏 大的噪声与组合爆炸问题 以及 m o n t e c a r l o仿 真方法的低效率 这些都给 d e d s基于仿真方法的优化带来了巨大挑战 寻找 与传统方法完全不同的优化策率已成为目 前 d e d s优化设计的重要方向 其中 序优 o r d i n a l 如下几个问题 1 optim ization 是 一 个 较 具 有 吸 引 的 优 化 方 法 仓 文 此 讨 论 知子 我们在第一章阐述了随机优化问题当中的两个基本困难之后给出了序优 这一优化方法的基本思想 即我们的优化目 标为以较大的概率获得一个 或几 个 足够好的 以一定的标准 设计方案d而不是如以往那样寻求以 概率 1获 得最好的设计方案的性能指标 实际上这其中包括两个基本观点 1 性能指标 的 序以 指 数形 式收 敛 而 性能 指 标的 值 最快以 速 率1 f收 敛 2 得到 足 够 好 的 设 计 参 数 的 概 率 将 随 着 这 一 集 合 的 个 数 的 增 加 而 增 加 下 r 又 2 在 第 二 章 给 出 了 指 示 过 程 与 重 合 概 率 这 两 个 体 现 序 优 方 法 主 要 特 点 的 重 要概念 随后讨论了重合概率的单调性及遍历性 一般情形及更新过程的重合 概率的指数形式的收敛速率 系统性能指标的相关性对重合概率收敛速率的影 响 丫 3 在 第 三 章 我 们 首 先 假 定 了 一 种 最 坏 情 形 即 所 有 好 的 设 计 参 数 及 坏 的 设 计参数都分别为同一值 随后给出了有序的随机变量及不重合概率的概念 并 利用有序的随机变量这一概念 讨论了在最坏情形时优化目 标的弱化 性能指 标 的 优 劣 差 别 及 噪 声 对 不 重 合 概 率 的 影 响 17 1 4 一 般 来 说 我 们 总 是 假 设 系 统 的 性 能 指 标 的 估 计 误 差 为 独 立 同 分 布 的 而在d e d s 的仿真当中 我们要用到共同随机数及并行仿真技术 从而使独立同 分 布的假设不成立 因而我们不得不考虑噪声对序优方法的影响 直观上我们认 为 估计误差一般来说总是对序优方法有帮助的 因为如果我们设想所有的估 计误差为完全正相关的 即估计性能指标均向同一方向偏离且程度相同 那么 我们观察到的性能指标的序就与真实性能指标的序完全相同 如果所有的估计 误差为两两完全负相关 那么就有一半的性能指标相互之间为完全正相关 而 另一半我们则不加考虑 这样做并不影响许优方法的应用 在第四章我们就两 种 噪 声 模 型 进 行 讨 论 下 z r 5 在 第 五 章 我 们 首 先 给 出 离 散 动 态 系 统 的 广 义 半 马 尔 克 夫 过 程 的 定 义 并 据此构造性定义提出了一个精确但低效率的仿真方法 随后介绍了事件同步化 及时间同步化并行仿真算法 但它们主要是针对马尔克夫系统的 接着我们依 据二阶逼近的思想对标准时钟算法 s c 进行扩展得到所谓偏移指数分布逼近 算法及超指数分布逼近算法并分了这种方法的精确性 以便使 s c 算法能用于 非马尔克夫系统的仿真 最后 分 布 的 排 队 网 络 进 行 并 行 仿 真 们利用扩展的s o 算法对十个结点的具有非指数 从而证实了序优方法的有效性 关健词 序优 重合概率 关性 并行仿真 有 序 的 随 机 变 f 优 化目 标 的 弱 化 了 噪声的相 ab s t r a c t t h e p e r f o r m a n c e a n a l y s i s d e s i g n a n d o p t i m i z a t i o n o f d i s c r e t e e v e n t d y n a m i c s y s t e ms d e d s a r e c h a l l e n g e d b y t h r e e k e y p r o b l e m s l a c k o f a n a l y t i c a l s t r u c t u r e p r e s e n c e o f l a r g e u n c e r t a i n t i e s a n d e n o r m o u s l y l a r g e s e a r c h s p a c e a l l t h e s e d i ff i c u l ti e s r e s u l t i n l a r g e c o s t s a s s o c i a t e d w i t h o b t a i n i n g p r e c i s e e s t i m a t e s o f s y s t e m p e r f o r m a n c e u s i n g t i m e c o n s u m i n g s i m u l a t i o n s o n e o f t h e f e w a v e n u e s t h a t a p p e a r p o s s i b l e t o c i r c u m v e n t t h e s e l i m i t a t i o n s i s t o e ff e c t a s t r a t e g i c r e d i r e c t i o n o f t h e a t t a c k w h i c h i s v e r y d i ff e r e n t f r o m t h e tr a d it i o n a l o p t i m i z a t i o n m e t h o d w h i c h i s o r d i n a l o p t i m i z a t i o n t h e f o l l o w i n g p r o b l e ms a r e d i s c u s s e d i n t h i s p a p e r 1 a ft e r e x p o u n d i n g t w o d i ff i c u l t i e s o f s t o c h a s t i c o p t i m i z a t i o n w e e x p l a i n t h e b a s i c i d e a l o f o r d i n a l o p t i m i z a t i o n t h a t i n s t e a d o f e s t i m a t i n g t h e b e s t p e r f o r m a n c e f o r s u r e w e s e tt l e f o r a g o o d e n o u g h a lt e r n a t i v e w i t h h i g h p r o b a b i l i ty i n f a c t t h e t w o i s s u e s o f t h e s p i r i t a r e l o r d e r c o n v e r g e s e x p o n e n t i a l l y f as t w h i l e v a l u e c o n v e r g e s a t ra te l n j a n d 2 p r o b a b ility o f g e ttin g s o m e th in g g o o d e n o u g h in c r e a s e s e x p o n e n t i a l l y w i t h t h e s i z e o f t h e g o o d e n o u g h s e t 2 i n c h a p t e r t w o w e f o r m a l i z e t h e i n d e x d y n a m i c s a n d a l i g n m e n t p r o b a b i l i t y e x a m i n e t h e m o n o t o n i c i ty a n d e r g o d i c i t y p r o p e r t i e s o f t h e i n d e x d y n a m i c s p r o v i d e a l o o s e b o u n d o f t h e c o n v e r g e n c e r a t e i n f o r m a l a r g u m e n t s f o r e x p o n e n t i a l c o n v e r g e n c e r a t e a n d t h e i m p a c t o f t h e a s s o c i a t i o n e x a m in e r e g e n e r a t i v e p r o c e s s e s 3 we e x p l a i n t h e r o l e o f g o a l s o ft e n i n g i n t h e c o n v e r g e n c e o f a l i g n m e n t p r o b a b i l i t y e m p l o y e d i n o r d i n a l o p t i m i z a t i o n u s in g a n o r d e r s t a t i s t i c s f o r m u l a t i o n w e e x a m i n e t h e e x p o n e n t i a l d e c r e a s e o f m i s a l i g n m e n t p r o b a b i l i t y b o u n d s w h e n t w o o r m o r e d e s i g n s a r e c o m p a r e d t h e c o n c l u s i o n s t a t e s t h a t b y r e l a x i n g t h e g o o d e n o u g h s u b s e t a n d s e l e c t e d s u b s e t c r i t e r i a i t i s e x p o n e n t i a l l y e ff i c i e n t i n t e r m s o f m a t c h i n g g o o d d e s i g n s i n a s e l e c t e d g r o u p 4 g e n e r a l ly w e as s u m e t h a t t h e p e r f o r m a n c e e s t i m a t i o n e r r o r s a r e l i d i n a p p l i c a t i o n s s u c h a s p e r f o r m a n c e e s t i m a t i o n f o r d e d s v i a s i m u l a ti o n t h i s a s s u m p t i o n o f i n d e p e n d e n t e s t i m a t i o n e r r o r fr o m o n e d e s i g n t o n e x t m a y n o t h o l d d u e t o t h e u s e o f c o m m o n r a n d o m v a r i a b l e s a n d p a r a l l e l s i m u l a t i o n e t c q u e s t i o n t h e n n a t u r a l l y a r i s e s as t o t h e v a li d i ty o f t h e n o i s e i m m u n i ty p r o p e r t y o f o r d i n a l o p t i m i z a t i o n i n s u c h c as e s i n t u i t i v e l y w e e x p e c t t h a t c o r r e l a t i o n a m o n g t h e e s t i m a t i o n e r r o r s s e l d o m c a n h u r t a n d a c t u a l l y h e l p s m o s t o f t h e t i m e i n t h e e x tr e m e c a s e o f p o s i t i v e c o r r e l a t i o n i e a l l e s t i m a t i o n e r r o r s a r e t h e s a m e i t i s c l e a r t h e o b s e r v e d o r d e r o f p e r f o r m a n c e w i l l c o i n c i d e w i t h t h e a c t u a l o r d e r s i m i l a r l y i n t h e c as e o f e x tr e m e n e g a t i v e c o r r e l a t i o n b e t w e e n a d j a c e n t p e r f o r m a n c e s b y w h i c h w e m e a n t h a t o n l y h a l f o f t h e e s t i m a t i o n e r r o r s a r e p o s i t i v e l y c o r r e l a t e d t h e n t h e e ff e c t a t w o r s t i s t o r e m o v e h a l f o f t h e p e r f o r m a n c e s a m p l e s f o r m c o n s i d e r a t i o n a n d t h e r e m a i n i n g h a l f w i l l b e p o s i t i v e l y c o r r e l a t e d w h i c h a g a i n h e l p s we w i l l c o n f i r m t h e a b o v e c o n c l u s i o n i n t e r ms o f t wo e r r o r mo d e l s 5 i n c h a p t e r 5 w e p r e s e n t t h e g e n e r a l iz e d s e m i ma r k o v p r o c e s s fr a m e w o r k f o r d i s c r e t e e v e n t s i m u l a t i o n i n tr o d u c e t h e e v e n t a n d t i m e s y n c h r o n o u s m e t h o d s f o r p a r a l le l s i m u la t i o n o f ma r k o v i a n s y s t e m s p r o v i d e a n e f f i c i e n t a p p r o a c h t o g e n e r a l d i s t r i b u t i o n i n w h i c h s h i ft e d e x p o n e n t i a l a n d h y p e r e x p o n e n t i a l d i s t r i b u t i o n a r e u s e d a s s e c o n d o r d e r a p p r o x i m a t i o n s t o s i m u l a t e n o n e x p o n e n t i a l d i s t r i b u t i o n d e m o n s t r a t e t h e e ff i c i e n t c o m b i n e d i m p l e m e n t a t i o n o f t h e s t a n d c l o c k a n d o r d i n a l o p t i m i z a t i o n t e c h n i q u e s i n d e x t e r m s o r d i n a l o p t i m i z a t i o n a l i g n m e n t p r o b a b i l i t y o r d e r s t a t i s t ic s g o a l s o ft e n i n g c o r r e l a t e d e s t i m a t i o n p a r a l l e l s i m u l a t i o n 致谢 我首先要向导师涂奉生教授表达我最真挚的谢意和感激之情 感谢涂老师 将我带入了一个对我来说完全崭新而又吸引人的科学领域 使我体验到了这一 领域的壮观 尽管路途艰辛但令人愉快 感谢涂老师在我攻读硕士学位期间在 学业上的精心的指导 涂老师宽容大度的人品 渊博的知识 严谨正直的学术 风格以及对科学的责任感都将使我终生受益 感谢 c i ms实验室的全体老师及同学三年来在各个方面的帮助与关怀 感 谢他们在讨论班上给予的启发与提示 感谢宋庆硕 刘晓峰 李昭等同学在论文撰写及仿真程序编写期间给予的 大力支持 第一章 序言 第一章序言 一般来说 一个随机优化问题可以表述为如下形式 m ion j 0 e l 0 g l 这里0为搜索空间 0 为设计方案 j 为系统的真实性能指标 l为系统的采 样性能指标且它是0 及若 的函数 4 为系统固有的随机因素 由于对大多数问题 j 0 缺乏 封闭的 解 析解的 表达 式 因 而 常 用的 方 法为 通过 采样来得 到e l 沪 l 的 值 即 e l 0 二 责 客 l 0 三 j o l 2 其中古 代表 系 统的 第i 个 采样 轨 道 众 所周 知 2 式 所阐 述的 方 法的 精 确 度 不 会 超 过1 1 万 这样的 精确 度对 某 些问 题 来说已 经 足 够了 如卡 尔曼 滤 波问 题中 对状态变量的 估计 但对另 外一些问 题这样的 精确度是不能令人满意的 如d e d s 中利用mo n t e c a r l o方法进行性能指标的估计 如以这样的精确度进行估计 那么 对一个复杂的 d e d s的每一次采样即使使用最快的计算机仍需几秒钟甚至几分钟 的时间 而对不同的0 所进行的大量采样将消耗掉我们所无法负担的开销 而且对 精确度的要求稍有提高 将使计算量以几个数量级的形式进行增加 我们面临的另外一个困难是组合爆炸问题 这使得我们面对一个庞大的搜索空 间 任何优化方法都带有盲目 搜索的倾向 假设搜索空间0的大小为1 0 0 这对于 具有组合爆炸问题的优化问题来说并不大 我们均匀地采样 1 0 0 0 0个性能指标 j b 那么这 1 0 0 0 0个采样当中至少有 1 个设计参数属于搜索空间中最好的 5 0 个 5 0 0 个 5 0 0 0 个的概率为多少 通过计算得到 p r o b 1 0 0 0 0 个采样点中至少有 1 个属于最好的k 个设计方案 1 l 一 典l oo 又1 0 那么以上概率分别为 0 0 0 0 0 4 9 9 9 0 0 0 0 4 9 9 8 0 0 0 4 9 8 8 我们看到简单的随机 搜索对于组合爆炸问题不能得到好的结果 面对上面所述的优化问题的两个主要困难 首先想到的如何得到所研究的对象 的结构 因为一旦有了系统结构我们就可以 有针对性地在搜索空间中进行搜索而避 免过大的盲目 性 当然获得系统结构信息本身并不是一件容易的事 很多学者都在 长期从事这方面的工作 本文将介绍一种完全不同策略 序优方法 第一章 序言 所谓的 序优方法 概括地说即为 我们的 优化目 标为以 较大的 概率获得一个 或几个 足够好的 以一定的标准 设计方案 而不是如以 往那样以概率1 获得 最好的设计方案的性能指标 序优的第一个观点为 系统设计参数的优劣顺序在仿真当中的收敛速率是指数 形 式的 这 要比 性能 指 标的 收 敛 速率i 1 万快的 多 形 象 地说 也就 是 确定 两 个数a 与 b的大小要比确定a 一 b 的值为多少容易的多 同样在许多优化问题中常常需要 确定的是不同设计方案的优劣 而并 不要求获得系统的性能指标的 确切值 序优的 第二个观点为 获得足够好的设计方案的概率将随着好的设计方案的集合的个数的 增加而以 指数形式 增加 也 就是 说我们所 要求的 优 化目 标越宽 松 获得 满意结果的 几率就越大 因此序优的思想就可以用来解决以 往认为无法解决的优化问 题 本文 的以 后各章将就以上两个观点分别加以 论证 序优方法是有关学者通过观察d e d s 的仿真实验结果总结出的一种优化方法 显然高效的 仿真策略将有助于序优方法的 实现 近年来出 现了为数不少的有关离散 事件动态系统并行仿真的文献 其中两种主要的仿真方法为时间同步化方法与事拌 同步化方法 但主要是针对马尔克夫系统的 本文除对这两种方法进行介绍以外 还将介绍如何将这两种方法进行扩展以 便用于非马尔克夫系统的仿真 最后我们将 扩展的标准时钟算法用于仿真十个结点的排队网络以 证实序优方法的有效性 第二章离散事件动态系统的序比较的收敛速率 第二章 离散事件动态系统的序比 较的收敛速率 县 1引言 本章主要是针对序优方法在收敛速率上的有效性进行讨论 在这里我们首 先给出一个 重合概率 的概念 本章的内容主要是围绕着这一概念展开的 重 合概率是指我们在仿真过程当中 或利用不十分精确的数学模型 观察到的 或 计算得到的 s 个好的设计参数 或控 制策略 中 至少有k 个是 包含于s 个真 正 好的设计参数中的 概率 即 与9 的交集的 个数不小于k 的 概率 本章公分五节 第二节给出指示过程及重合概率的数学定义 第三节讨论 重合概率的单调性及遍历性 第四节主要讨论重合概率的收敛速率 第五节针 对更新过程 研究它的重合概率的收敛特性 肠 2 指示过程及贡合概率 我 们 考 虑 优 化问 题m a x j 0 0 e 二 0 0 二 0 为 设 计 参 数 集 合 j o 为 一 个离 散 事 件 动 态 系 统 的 性 能 指 标 不 失 一 般 性 我 们 假设 j 9 j 0 2 j o u 我们在这里用设计参数0 来代表一个离散事件动态系统 记l o c o t 为仿真 过 程当 中 在t 时 刻系统0 的 采样性能 指标 令j o t e l o co t 这里并 不 要 求l o a t 是 相 互 独 立的 为 简 单 起见 我 们 采 用勺来 代 替l o j co t o 我们假设 a l i ml o r o t l i m j o t 二j 0 a s b 0 e o 在仿真过程当中的任意时刻t 我们依据采样性能指标将系统进行排序 令 r e 为 排 在第l 个 位置 上的 系统 则l g co t l r co t 二 之 l g ro t a 我们在这里主要关心的是估计的排序结果与真实的排序结果相吻合的程度如 何 即 通过仿真得到的 个好的设计参数中 以 下将用t o p 一 来表示 至少有 k 个 包含于s 个真正 好的 设 计参 数 以 下 将用t o p 一 s 来表 示 这一点 可以 通过 下面的指示过程来刻画 1 s s k 1 is n g 1 k 1 0 否则 丁 在这里g 0 0 二 0 a s 2 二 在序优中 的 子集 s 称为选择子集 k 为重合程度 概率p i s k g称为足够好 1 称为重合概率 第二章 离散事件动态系统的序比 较的收敛速率 代i s g k 0 称为不重合概率 肠 3 指示过程的基本性质 3 1 单调性 性质3 1 指示过程i s g k 关于 和g 是非减的 关于k 和n是非增的 证明 1 i s g k i s g k 1 如果t o p s 中至少有k l 个属于 t o p g 即i s g k l 1 则t o p s中至少有k个属于t o p g 即 i s g k 二 1 2 i s g k i s l g k 如果i s g k 1 则t o p 一 s l 中至少有k 个 包 含于t o p 一 g 即i s 十 1 g k 1 3 i s g k i n s g k 让 我 们 分 两 种 情 况 进 行 讨 论 l 设o n 为 观 察 到 的g 个 好的 设 计 参 数 中 的 一 个 由 于o n 不 属 于t o p g 而当 确 定丫 s g k 时 o n 并 未 参 与 仿 真 因 而i n s g k i n s g k o 2 设8 n 不属于观察到的9个好的设计参数集合 显然 i s g k i n s g k 证毕 性质3 2 对于所有的s 1 9 及k 下式 a i s g k i s 一 1 g k 一 1 b i s g k i s g 一 1 k 一 1 c i s g k i s 一 i g 一 l k 成立 证明 如 果i s g k 1 则t o p 一 s 一 1 中 至 少有k 一 1 个包含 于t o p 一 8 即 i s l g k 1 1 并且t o p 中至少有k 1 属于t o p g 1 集合 即 i s g 1 k 1 e 叮 可以由 性质3 1 直接得到 证毕 前 面关于i 的 结果 对于p i 1 仍 然成立 即 如果 我们允 许一个宽 松的 设 计要 求 较小k 值及 较 大的g 值 那么p i s g k 1 就 可以 得到 增 加 当s g k 时 即当我们在仿真当中 只保留k 个最好的设计而我们的 设计目 标是找到k 个真正最好的设计时 重合概率达到最小值因而有下面性质存在 性 质3 3 p i s g k 0 p i k k k 0 3 2 速历性 性 质 3 4 在 假 设 a 下 当 t 3 时 p i s g k 1 l 第二章离散事 件动态系统的 序比 较的收敛速率 p i s g k 0 0 不重合概率可以写成如下形式 p i s g k 0 p u o t j o k 及 v 恤 t j o g s k l 以 概 率1 成 立 证明 在 这里我 们仅 考 虑u 佃 t v co t j b g 一 1 的 证明 类似 记三 为所有可能的采样轨道 的集合 记s l 为采样轨道 的集合 这里 为当 t 时 l 不收敛于j 0 的 采样轨道 显然对任意采样轨道 e e 一 n 1 有 u 一 分 j o 成 立 因 而 有 p u co t卜 j ok 尸卜 一 自 几 i 一 p 艺 q 成立 依假设a 对于所有i p s 2 卜0 因 而p u co t j o 1 证毕 性质 3 6在假设 a 成立的情况下 当 t 时 有e u c o t j b k 及 e v 佃 t j o g k l 成 立 性 质 3 7 在 假 设a 成 立 的 情 况 下 当t 00 时 c 4 0 j l 扭 0 t j 0 及e l 恤 u 0 t 1 归 以 概率1 成 立 4 f合概率的收徽特性 4 1 合概率收傲速率的下限 引理4 1 对于任意实数v 下式 p i s s k 全 p l j s v 十 全 p l j 成立 证明 依性质3 3 对于任意实数v 有 p i s s k 0 5 p i k k k 0 尸 pk m in l v 艺p l j v 艺p l j v j k l 成立 证毕 第二章离散事件动态系统的序比较的收敛速率 性质4 1 假设采样性能指标的方差存在 那么在假设 a 成立的情况下 存 在一个有限值t 对于所有t t 下式成立 p i s a k 0 a 2 艺v ar l 这里 j b k 一 j o k 1 4 证明 依假设 a 存在一个有限值t t j o 一 v 成立 当j 5 k 十 1 时 对于所有t t 当j k 时 j o j t j o j a 2 e x p a 0 成立 结合 3 得 p i s g k 一 0 o e x p 0 其中者 t 夕 m a x v a r o w t o e o 如果方差以 速率 1 t 收敛于 零 那么p 口 s g k 0 以 速率e x p 卜 o t 收 敛于 零 4 3 宜合概率指致收教速率的确定 引 理 4 2 对 于任意随 机 变量e e u a s 筑 e i 成 立 且u 0 那 么 存 在 t o 0 使 得 p e 0 t o 其 中 a x s u p f t l o g m a m a e e x p a e 证明 对 任意a 0 p e 0 e 1 e 0 从 幻 因 而有 p e 0 e x p 一 s u p t 一 l o g 从 a 第二章离散事件动态系统的序比较的收敛速率 成立 由 于e e u 及p 0 使得e e t 成立 证毕 我 们利用 2 式 即p i s g k 0 p u 恤 t 万 1 1 1 这 里万 s g k 为 类 似 于 5 式中 定 义 的h s g k 但 其中w 佃 t 为w 恤 t 所替 代 证明 略 见 3 6 a 4 5 有关大 偏差的的两个结论 考虑独立同分布随机变量序列 x d n 1 令 s y x m a e e x p 7 x a a l o g m a 以 及a x s u p a x 一 a a 这里m a 为一 种矩函 数 a 7 x 为a 幻的f e n c h e l l e g e n d r e 变换 引 理4 3 如果m 幻在a 0 的一个邻域 一 司 u r 0 内 存在 那么 p 邑 n x e x p n 从 p s l n x 0 d x e x 证明 略 见 3 6 0 引理4 4 对上述随机变量序列有下式成立 p x x 1 5 m a e x p a x b a 0 p x x m a e x p 瓜 b 1 0 m x 8 e e x p a y o 1 4 及 m a 0 二 e e x p y 0 存 在 那么当 考虑 7 式 形 式的 性能 指标时 有 存 在 使p i s g k 0 o e x p c t 成 立 证明 令y j o k j 归 j 1 2及 二 j s k 一 j 9 k i 2 考虑到 j 0 1 一 j 9 w 由引 理4 1 得 p i s g k 0 艺p 0 j 艺p 0 这里p b p l 8 t j 8 一 以 及p 6 k t p l 伏t j 仍 a 因此对于任意b e 若p 8 以及几 s 均以指数形式收敛于零 那么 p i s g k 0 也将以 指数形式收敛于零 下面我们仅就p z 0 进行论证 只 0 的 情 况完 全类似 为 简单 起见 我 们忽 略 符号0 e 首 先 有p z 一 p t x 0 有 p t k 一 卜 二 一 n k tr 一 s p k t q j p j 曰t n 0 l q j 成立 显 然 z 为 独 立 同 分 布 的 随 机 变 量 引 2 b y 且 对 于a e 一 1 2 b r r 2 b e e x p z 存 在 由 于e z l a e i l 0 由 k t 的 定 义 可 得 第二章离散事件动态系统的 序比 较的收敛速率 p k t t 门 2 1门 to 刘 p 噜y 刘 将引理 4 3用于上面不等式右边第二项 引理 4 3用于第一项 那么若 q e y j t l 2 则有 p k t 0 选择 q l t l 4 e y 习 那 么 可以 看出 p z 以 指 数 形 式 收 敛 于 零 证毕 定理 5 2 在定理 5 1的假设条件下 当采用 8 式形式的性能指标时 存 在c 0 使p i s g k 0 o e x p c t 成立 证明 略 见 3 6 0 第三章序优方法中优化目标的弱化 第三章 序优方法中优化目 标的弱化 肠 1引言 本章我们主要讨论序优方法中的 优化目 标的弱化问 题 g o a l s o f t e n i n g 序优的主要目的是提高仿真效率 在参数设计的初始阶段 我们可以利用序优 方法在一个大的搜索空间中以较大的概率很快找到相对较优的子空间 这使得 在初始阶段可以节省出大量的开销 然后再在较优的子空间中采用更有效的方 法继续搜索 传统的优化方法致力于寻找最优解 大部分算法为作到这一点使 得算法收敛速率变慢且开销极大 序优则采用一个不同的标准 即我们不坚持 找到一个绝对最好的解 而是希望以较大的概率得到一些足够好的设计参数 我们在这里再次给出重合概率的定义 记共有n个设计参数 g为足够好的参数子集 s为在仿真当中所选择的 参 数 子 集 令 g 一 g i 及 一 is i 则 重 合 概 率 定 义 如 下 p g s k p a g n s 1 传统的 优化方法考虑的情况为g s 1 因而重合概率将相当 小 我 们在这 里关心的主要是重合概率的指数收敛速率与9 及s 的大小之间的关系 关于重 合概率定义中n个设计参数我们作假设a 1 n个设计参数是在整个搜索空间中均匀采样得到 2 n个设计参数的估计误差为独立同分布的 第一个假设允许我们用n个设计参数来代表整个设计参数空间 第二个假 设我们将在以后进行说明 假设 a 使我们所讨论的问题的范围由整个搜索空 间变为n个设计参数 肠 2 问 的掀学描述 我 们记 佃0 z 二 b n 为n个设 计参 数 它 们的 真实 性能 指 标分别为 j i 1 j 2 j n 记按优劣排序后的性能指标为j a i u 2 p 2 一 u n 记l 肠 为 仿 真 过 程当 中 第 次 采 样 得 到 的 排 在 第i 位的 采 样 性 能 指 标 记 x n x 2 4 x n n 为 性 能 估 计 值 且 x n 卜写一 l j n 我 们 在仿真当中对所有设计参数将利用相同数量的采样性能指标得到相应的性能估 计值 第三章序优方法中优化目标的弱化 对于 每一个 设 计参数 l 1 l 2 二 l n 为 独立同 分 布的 随 机变量 序 列 那 么 对 任 意 1 e l t 一 k v a r l 一 a c n z n a 7 n n 为 估 计 误 差 从 而有x n u c n 这 里e 卜 n 0 一 般 认为 n 的 最 快 收 敛 速率 为o 1 而 这 样的 收 敛 速 率 是 不 能 令 人 满 意的 为便于分析 对于i 1 2 一 n 假设l n 为正态分布 其均值为刀 方差 为 考虑最坏情况 令 2 m a x 司 那么性能 估计值x n 二 j c e n 具 有 高 斯 分 布n u u 2 i n 9 3有序的随机变t与不 合概率 在 独立同 分 布噪 声的 假设条 件 下 足 够 好参 数子 集的 性能 指 标c u u 与其他参数性能指标的差别越大 则重合概率就越大 现在我们假设所有足够 好 参 数的 真实 性能 指 标 都 为 同 一 值 u 同 样 其 他 参数 的 真实 性 能 指 标都 为同 一 值1 i g 一这 是 最 坏 情 况 即 角十 一 户 g 产 g 一 月 n 刀 其 他任 何 情 况 都 会 更 有 利 于 增 大 重 合 概 率 不 失一 般性 令 刀 一 p x 以 及f i g i 一 p n 0 从 而由 仿 真 得 到的 足 够 好 性能 估 计 值 为x n 一n 0 6 2 的 1 1 2 b 其他 n g 个参数性能估计值为 x n 一n 0 6 2 i n f 1 从 3 1 有序的随机变f 考 虑 定 义 在r上 连 续 随 机 变 量y 其 概率 密 度 为 f y 记片 乓 狱n 为 由 随 机 变 量y 得 到 的m 个 独 立 采 样 其 值 分 别 为y i m y 2 m i y m m 将 创门 由 小 到 大进行排序得 y c m 5 y 2 5 y 相应的排序后的随机变量为 y r m y 2 m y m m 显 然y 之间具有相关性 y 的 边缘概率密度函 数 见 2 8 1 为 f m y c m if 一 一 一 f 一 一 f 一 2 州 1 厂lll 弓乙 3 2 不重合概率 为便于下 一 节进行讨论 这里我们介绍不重合概率的概念 即 q g s n 1 一p g s 1 n 1 一 p a ig n 5 l l n 也就是在仿真过程中所得到的选择子集中没有一个属于真正足够好的子集 的概率 我们现在来考察性能估计 一值的概率特性 由前面的分析及假设条件不难看 出 在最坏情况下 我们可以由一个具有正态分布的 概率密度为 第三章序优方法中优化目标的弱化 0 x 1 1 2 g 实际上g 个概率密度完全相同 的随机变量x n 一 n o q z n 来得到g 个性能估计值 同 样也可以由 一个具有正态分布的 概率 密 度 为o n x 一 一 的 随 机 变 量x n 一n o a z n 得 到 n g 性 能 估 计 值 另 外 记 x s 及叭 x n g a 分 别 为o n x g 与 0 x 一 的 分 布函 数 显 然 有两 个随 机 变 量 对 我 们尤 为 重 要 即由 随 机 变 量x g 得到 的 最 好 的 性 能 估 计 值x 及由 随 机 变 量x n 得 到 的 第 个 最 好的 性 能 估 计 值x s n g 由 这 两个随机变量就完全确定了最坏情况下的不重合概率 下面先给出一个引理 引理 3 1 不重合概率可以表示成如下形式 q g s n p x n g x i g 3 证明 在 任 何仿 真 过 程中 若要 事 件 x g x 一 发 生 则 必 有 下 列 等式 成立 x i n 一 二 x z n g x r n g x i g x a x x g g 因此 在这种情况下所选择的s 个最好的设计参数中将没有一个是属于足够 好 参 数 子 集g 的 既 g n s l 证毕 利用 2 式及引理 3 1 q a s 0 因而有引理中等式成立 不重合概率可以表示为下列形式 n p x n 一 x g 0 一 n 二 i l f d 一 一 1 1 一 d n y 一 g x o y z 一 1 1 一 d z g i o n z d z d y 4 令x 9 及x 一 的 均 值 分 别 为u c g 与巧 那 么 有 下 面 结 论 成 立 当 9 增 加 时 p 1 9 将向 左 移 而热 一 将向 右 移 当 增 加 时 p s 一 将向 右 移 县 4 优化目 标的弱化对不宜合概率收傲迫率的影晌 我们现在就前面所述最坏情况 针对 值的不同分三种情况进行讨论 当 o 时 即所有设计的真实性能指标都为同一个值时 q g s n l 一 一 p x 一 一 x i g o 95 n gg n c 沙 ys一 1 1 一 一 n g x 0 y z l il 一 z j o n z d i d y 通 过 替 换 o a y z 及 id 有 下 式 成 立 b 一 一 一 一 9一 du rnl s 一 第三章序优方法中优化目标的弱化 因而我们有如下结果 n 一s rlesesesesl 一 刀夕廿 nu q g s n l a 我们假设在一个箱子里 有g 个蓝球和n 一 g 个黑球 我们随机地选择s 个 其中 有h 个篮球的 概率为 p s 4 中 h 个 球 一 钊 i n g l s h 这 里g ig i s is i h 0 1 二 m in g s 不 重 合 概 率 g s n l4 0 即 为 当 0 时的情况 即一个篮球都未选中时的情况 当 二 0 时 这相当于没有作 球h 任何性能指标的估计 而是随机地从n个参数中选择 s个参数 这时 q g s n ia 0 是 不 依 赖 仿 真 时 间 的 即 无 论 仿 真 时 间 的 长 短 不 重 合 概 率 均 保 持不变 我们将这情况称为盲选 b l i n d p i c k i n g 定理4 1 盲选时的不重合概率的上限是一个由s 和8 规定的指数函数 证 明 对 于 任 一 有 1 一 x e x p x 成 立 因 而 一 n 一s 一 g o 我 们 有 z 一 m z 及 r o t 一 t n a s d t f t i 1 一 一 d t 从 而 有 g s n la 证毕 2 当 之 时 一 q s s n la o o 即我们掌握了用来区分9 个好的设计与其它不好的设计的 r 一 s 天 总 里 j令 一 v n 念 i n 一 i 1 山 一 入 二 二 功 2 lo g 2 tr 找 11 目 尤 正 久 一 广 pill t l t tf 1 m 如果对于所有的t 有 f f x x d a f f y d y 成 立 那 么 我 们 就 认 为 随 机 变 第三章序优方法中优化目 标的弱化 量x 随机小于随机变量y 即x y 如果仅不等式成立 那么我们说x 严格随 机小于y 记为x y 证明 设y i y i 了 y 为相 互独立的随 机变量 如果y y及y p y 助 一 琴 p yw i y 2 y z y p 沙 y 们来有 我自 证毕 对 于x g 我 们 现 在 来 寻找 一 个随 机 变 量x 使 它随 机地 大 于x o 选择具有以下概率密度的随机变量 即 f g x 一 p g 一 p expl p lx0 一 如 果 x z r 否则 因 而 我 们需 要寻找p x 0 决定p 和 1 一 d j x z x 我 们 选 择户 及z s 从 而 使 得龙 8 x 我 们 可以 利 用人 j g 8 我 们 现 在 来 确 定 z r 对 于 所 有 的 二 e x p f z