（概率论与数理统计专业论文）利用遗传算法寻找最优折扣因子序列.pdf

利用遗传算法寻找最优折扣因子序列 专业：概率论与数理统计 硕士生：蔡敬衡 导师：何远江教授 擒要：本文主要利用遗传算法寻找动态线性模型( d l m ) 的最优折扣 因子序列。在系统方差序列阵帜) 。为未知的情况下，一般会采取折 扣因子模型而在折扣因子模型中现今的方法都是在假设折扣因子 为单一常数的基础上进行研究的。本文会在单折扣因子模型的基础上 进行改进。令折扣因子为一序列 t ) 。，再利用遗传算法找出折扣因 子序列的局部最优解。在得到最优折扣因子序列看我们可以得出 4 ) 。的经验分布井对数据进行预测。另外我们还可以利用最优 折扣因子摩列对系统方l 阵进行估计。无论从糠涮的效果上还是估计 系统方差阵的效果看，遗传算法寻找到的折扣因子序列都要优于单折 扣因子。 关键词：动态线性模裂折扣因子遗传算法 f i n d i n gt h eb e s td i s c o u n t f a c t o rs e q u e n c e b yu s i n gg e n e t i cm g o r i t h m m a j o r ：p r o b a b i l i t ya n ds t a t i s t i c s n 龃i e ：c a i 弛g l l e n g s u p c r v i s o r ：p r 0 h ey 咖j i a n g a b s t r a c t ：t h i sp a p e ri sm a i n l ya b o u tt of i n dt h eb e s td i s c o u n tf a c t o r s e q u e n c ei nd y n a m i cl i n e a rm o d e l sb yu s i n gg e n c t i ca l g o r i t h m w h e n t h es y s t c mv a r i a n c em a t r i xs e q u e n c e 似) i su n k n o w n ，w eu s u a l l yu s e t h ed i s c o u n tf a c t o rm o d e l st oh a n d l ei t w h i l ei nt h em o s td i s c o u n tf a c t o r m o d e l s ，t h ee x i s t e n tm e t h o d sa hs u p p o s et h ed i s c o u n tf a c t o ra sc o n s t a n t t h i sp a p e fw i l lm o d i f ) ，t h ed i s c o 瑚tf a c t o rm o d e l s ，m a l 【i n gt h ed i s c o u m t o f sa sas e q u e n c e 点) 。n ，a n d l e nf i n dt h el o c a lb e s ts o l u t i o n so ft h e d i s c o u n tf a c t o rs e q u e i 脱a sw eg e tt | l eb e s td i s u n tf a c t o rs e q u e n c e ，w e c 锄g c t t h ee m p i f i c a ld j s t r i b u t i o no f 点l ，锄dt h e np r c d i c tt h ed a t ab y 略j n gi l w cc 柚a 1 e s l i 瑚t em ev a r i a n c em a r i x q 辩n c ea c c o r d i n gt o t h eb c s td i s c o u n tf a c t o rs e q l l e l i c c t h ed 妣o u n tk 姐s e q u c n c e f o u n db y g c 鹏t i ca l g o r i t h mi ss l 胖r i o ft ot h e s i n g i cd i s c o u n t f a c t o rb o t hi n p f e d i c t i o n 明dv a r i a n c c 脚t 血q n e s 妇培t 缅 1 ( e ) n 0 r d s ：d y m m i cu n e a rm o d e l s ， d i s c o u n tf a c t o r s ，g e t i c 他o r i t 咖 中山大学硕士学位论文第一章概述 第一章概述 动态线性模型( d t m ) 是在贝叶斯框架下对时间序列估计和预测的线性模型。 h a r r i s o n 和s t c v e 璐在1 9 7 6 年首先提出动态线性模型这个概念。在此后的三十年， 动态线性模型取得了很大的发展，并广泛应用到商业、工业、科学还有社会经济 学等多个领域。在众多应用中，正态多元动态线性模型的研究最为广泛，其最新 的应用是在t r i a n t 柚f y n o p o u l o s 和p i i 【o u l a s ( 2 0 0 2 ) 【1 3 】的计算机网络安全研究和 a i l g u s 等人( 2 0 0 3 ) 【1 i 闭的基因序列模型研究中。 记仁k 是一，维向量时问序列，正态多元动态线性模型的定义如下： 定义1 1 正态多元动态线性模型( n m d i m ) 由以下两个方程构成： 观察方程y - c q + u ki 三，一( o ，。) 系统方程 q q q 一。+ qql 彬一n ( o ，彤) 其中 ( 1 ) e 是n ，维设计矩阵( d 髂咖蚴妇) ： ( 2 ) 晓是”维状态向量( s t a t ev e c t o r ) ； ( 3 ) 是r r 维观察方差阵( o b s e n r a t j o n v a f i 柚c c i n a t 血) ； ( 4 ) q 是 x 万维系统矩阵( t 聊够血j o n 脚t 呶) ； ( 5 ) 形是耳x 维系统方差阵( t 棚础i o n v a r i a i 翳m a l 血) 。 该模型可以简记为 e ，g | ，= 。，彤) 。 记m ，儿y i 是观察向量t 我们称q 一 m ，y ：m ) 为f 时刻的信息集，显然有 d i - y | ，q 。) 。一般地，只，g | 是已知的，进一步，我们假设当给定q - 1 ，薯和 彬后，误差序列 哆) 。和 鸭 。是相互独立的。 在上述假设下，当e ，g ，邑和彬均为已知时，我们只需知道初始先验信 息( 吼id 0 ) 口j v ( 用。，c o ) ，其中j ，l o 和c o 为已知向量和矩阵，就可以利用贝叶斯方 法直接地得出每一时刻f 的一步预测及后验分布。h 町如n 和、s t ( 1 9 9 7 ) 【9 l 给 第l 页共弘页 中山大学硕士学位论文 利用遗传算法寻找最优折扣因子序列 出了下面定理： 定理1 1 在定义1 1 的模型及上述假设下，对每个f ，有 ( 1 ) f l 时刻的后验分布 一，id l 一，) 一( 。，c f 一，) 其中m 。和q 一。为已知； ( 2 ) f 时刻的先验分布 ( ql q 一。) ( q ，r ) 其中q g 啊- 1 ，县g f q ，g7 + 彬； ( 3 ) 一步预测 ( e i q 。) ( 正，q ) 其中z - 鼻7 n 。，q 一只r 只+ 墨； ( 4 ) f 时刻的后验分布 ( 只i q ) 一( 鸭，e ) 其中m 一口，+ 4 b ，q e 一4 q 4 ， 4 - r e q 1 ，岛一只一正。 但在实际应用中，墨和彬常常是未知的，这种情况下我们就要先对薯和彬 进行估计或得出其分布，再进一步求出一步预测和馥的后验分布。这就是动态线 性模型的参数估计问题。在众多动态线性模型的研究和应用中，参数估计一直是 研究的重点，其中对观察方差鼍估计的研究较为深入。w b 砒和h a r r i s o n ( 1 9 9 7 ) 【9 l 在z 。为常数矩阵= 且其初始先验分布为倒w h i s h a n 分布的假设基础上，利用 贝叶斯方法给出三的后验估计以及模型的更新方程。n 砒晦n o p o u b s 和m o n t a 媳 ( 2 3 ) f 1 4 】减弱了条件，只需知道三初始先验分布的自由度和期望就可以得出 模型的更新方程。除了贝叶斯方法外，d u f b i 和均p 姗( 2 0 0 1 ) 【6 j ，s h u 删a y 和s i o 旋r ( 2 0 0 0 ) 1 1 2 l 给出= 的极大似然估计；后者还和k i t a g a w a 和g e 腊c h ( 1 9 9 6 ) 【1 0 j 分别利用h i c 、m n r 矗p h s o n 和e m 算法给出观察方差的估计，但数值逼近的结 第2 甄共3 4 页 中山大学硕士学位论文 第一章概述 果并不理想。马尔科夫链蒙特卡罗( m c m c ) 方法也被广泛地应用到参数估计中。 c a r l i i l 等( 1 9 9 2 ) 【3 】，c a n e r 和l ( o l l n ( 1 9 9 4 ) f 4 】，f m h w m h s c h l l a t t e r ( 1 9 9 4 ) 【7 l ， 、耽s t 和h 蜘盎o n ( 1 9 9 r 7 ) 1 9 】，d o u c c t 等( 2 0 0 1 ) 【5 】都是利用m c m c 方法得到观 察方差的估计值。而g c w e k 和i z a h i ( 2 0 0 1 ) 嘲，l 眦( 2 0 0 1 ) 【1 1 】更是利用 该方法对非线性和非指数分布族下的动态模型的观察方差进行估计。 与观察方差相比，系统方差为未知时的研究并不多。在现有的文献中，只有 w b s t 和h a i r i s o n ( 1 9 9 7 ) f 9 l 利用折扣因子模型和富元斋( 2 0 0 1 ) 1 1 6 】利用广义指 数加权回归的方法对系统方差进行估计。其中折扣因子模型得到了广泛的应用。 折扣因子模型的思想是：在f 一1 时刻，q 一，的后验方差为矿( b 一。l 皿一。) c - 1 ， 因q - q 包。+ q ，所以q 的先验方差为y ( q l q 一，) 一q q 一。q + 彬，记第一项为只， 即卑一q g 一。q 一y ( g b 。i q 一。) ，于是r 一只+ 彬。我们把方差的逆看成估计的 “精度”，那么( q 。l q ，) 的“精度”为岛，( q i q 一。) 的“精度”为耳1 ，( g 缉一，l 皿一，) 的“精度”为只一。因为q 比q q 一，多了一个扰动项q ，因此( bld f 。) 的“精度” 会比( g | b 。i q 一。) 的“精度”要小，也就是说只4 “打了个折扣”后等于耳1 。即 耳1 - 6 只，其中6 ( o ，1 】称为折扣因子，从而r 。言置。由于r # + 彬，所以 有 彬- 半只 ( 1 1 ) 进一步，当给定6 和c o 后，通过模型的更新方程和( 1 一1 ) 就可以求出系统方差序 列 彤) 。折扣因子模型具有很多优点；应用方便，计算简单。折扣因子的选择 也相当简便由于6 ( 0 1 。我们可以利用穷举法去寻找最佳的折扣因子( 例如 取6 0 1 0 2 ，o 9 ，1 0 ，或更细致她6 - o 0 1 ，o 0 2 ，0 9 9 ，1 o o ) ，通过比较各个 折扣因子的预测误差来确定最佳折扣因子。在计算机被广泛应用的今天，最佳折 扣因子的寻找只是一个循环问题。 何谓“最佳”折扣因子? 我们可以通过预测的误差大小来作为折扣因子好坏 的标准。 第3 页麸3 4 页 中山大学硕士学位论文 利用遗传算法寻找最优折扣因子序列 定义1 2 由定理1 1 知( k l q 。) 一_ ( z ，q ) ，b 一只一工，称删d 为f 时刻的 平均绝对误差，m 舛为r 时刻的均方误差。 脚。驯，船。蔼露 可见 纠d 、艘e 越小，表示预测越好，即折扣因子越佳。 寻找最佳折扣因子的意义在于可以更好地预测y ，从定理1 - l 中可以知道 ( y + ，id i ) 一( 正+ ，l q ) ，通常我们会用五+ ，来作为y + 。的估计值，而由定理可知 工+ l ，q + 。与和q 有关，即与 l q ) 的分布有关。折扣因子的选择会直接影 响和g 的取值，而最优折扣因子表明在该折扣因子下对历史数据的预测最为 准确，因此也可作为对未来数据预测的折扣因子，而且一般相信预测效果比其他 折扣因予更好。 但单折扣因子模型仍存在不足之处：该折扣模型的折扣因子是一固定常数 6 ，即其“折扣”是恒定的，不会随时间变化而变化。一个更合理的假设是折扣 因子是一时间序列 点) 。，且每个6 ，都是独立同分布的，以反映“折扣”是随时 间变化丽变化的，并且有一定规律。在这种假设下，寻找最佳折扣因子就不再那 么简单了。假设f - 5 0 ，魂分别取o 1 ，o 2 ，o 9 ，1 0 ，那么用穷举法寻找将要进行 1 0 5 0 次运算。现在普用家用计算机每秒中大概可做1 0 9 次运算，那么将需要3 1 酽 年才可完成计算。可见，采用穷举法去寻找最佳折扣因子序列是不可能的。如何 在有限时间内寻找最佳因子序列成为主要问题。本文就是在假设折扣因子是一时 间序列 6 。) 。的基础上，利用遗传算法快速地找出局部最优折扣因予序列e 本文结构如下：第二章主要介绍遗传算法的起源、概念和算法步骤。第三章 介绍如何利用遗传算法寻找局部最优的折扣因子序列，并分析该算法的时间复杂 度。第四章是把遗传算法应用到实际和模拟数据中，并且把遗传算法找出的最优 折扣因子序列与单一折扣因子得出的估计误差进行比较；除此之外还会利用遗传 算法找出的最优折扣因子序列去估计系统方差的分布。第五章根据第四章的比较 结果中得出结论。 纂4 页共3 4 页 中山大学硕士学位论文 第二章遗传算法介绍 第二章遗传算法介绍m 3 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传 等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出 的一种全局优化算法。 遗传算法的概念最早是由b a g l e yj d 在1 9 6 7 年提出的；而开始遗传算法的 理论和方法的系统性研究是1 9 7 5 年，这一开创性工作是由m i c h i g 柚大学的 j h h o l k l d 所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法的简称g a ( g e n e t i ca l g o f j t h m ) ，在本质上是一种不依赖具体问题 的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业 优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研 究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智 能一样，都是对今后十年的计算技术有重大影响的关键技术”。 2 1 遗传算法的基本概念 遗传算法的基本思想是基于d a 唧i l l 进化论和m e n d e l 的遗传学说的。 达尔文( d a 刑i 1 1 ) 进化论最重要的是适者生存原来。它认为每一物种在发展 中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一 些异于父代的新交化。在环境变化时，只有那些能适应环境的个体特征方能保留 下来。 孟德尔( m c n d e l ) 遗传学说最重要的是基因遗传原理。它认为遗传以密码方 式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某 种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基 因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因 结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在 这个算法中要用各种进化和遗传的概念。这些概念如下： 1 串( s t 血g ) 它是个体( i n d i v i d u a l ) 的形式，在算法中一般为二进制串( 在某种情况 第5 页共弘页 中山大学顽士学位论文 利用遗传算法寻找量优折扣困子序列 下可以是数字串) ，并且对应于遗传学中的染色体( q u n o i n o s 锄e ) 。 2 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体的元素。 3 群体大小( p o p u 】a t i o ns 咖) 在群体中个体的数量称为群体的大小。 4 基因( g e n e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串 s = 1 0 1 1 ，则其中1 ，0 ，l ，1 这四个元素分别称为基因。 5 基因位置( g e n ep o s i t i o n ) 个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由 串的左向着计算，例如在串s 1 0 1 l 中，o 的基因位置是3 。基因位置对应于 遗传学中的地点( l o c u s ) 。 6 基因特征值( g e n ef e a t u r c ) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 5 ，1 0 1 1 中，基因位置2 中的1 ，它的基因特征值为2 ；基因位置4 中的1 ， 它的基因特征值为8 。 7 串结构空间 在串中，基因任意组台所构成的串的集合。基因操作是在结构空间中进 行的。串结构空间对应于遗传学中的基因型( g e t y p e ) 的集合。 8 参数空间s 一 这是串空间在物理系统中的映射，它对应于遗传学中的表现型 ( p h c t y p e ) 的集合。 9 非线性 它对应遗传学中的异位显性( e p i s t a s i s ) 。 1 0 适应度( f i i n c 鹦) 表示某一个体对于环境的适应程度。 遗传算法还有一些其他的概念，这些概念在介绍遗传算法的原理和执行过程 时，再进行说明。 第6 页共弘页 中山大学硕士学位论文 第二章遗传算法介绍 2 2 遗传算法的原理 遗传算法g a 把问题的解表示成“染色体”，在算法中也即是以二进制编码 的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后， 把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应 环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染 色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体” 上，它就是问题的最优解。 1 遗传算法的目的 典型的遗传算法c g a ( c a n o n i c a lg c n e t i c 舢g o r i t h m ) 通常用于解决下面 这一类的静态最优化问题： 考虑对于一群长度为l 的二进制编码趣，f - 1 ，2 ，n ：有 岛 o 册 ( 2 1 ) 给定目标函数，有，慨) ，并且 0 ， ) 求满足下式 m 缸 ，p 。) i6 j 0 册 ( 2 2 ) 的6 l 。 很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出 的原始解群中，不断进化产生新的解，最后收敛到一个特定的串扛处，即求 出最优解。 2 遗传算法的基本原理 长度为l 的斗个二进制串6 f ( f 一1 ，2 ，斗) 组成了遗传算法的初解群，也 称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进 化术语，对群体执行的操作有三种： ( 1 ) 选择( s c l c c i j o n ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖 第7 页共辩页 中山大学硕士学位论文利用遗传算法寻找量优折扣因子序列 下一代。故有时也称这一操作作为再生( r 叩r o d u c i i 0 咀) 。由于在选择用 于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的， 故而有时也称为非均匀再生( d 自睡r e n t i a lr e j 印d u c i j o n ) 。 ( 2 ) 交叉( c m s v e r ) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位 置的基因进行交换，从丽产生新的个体。 ( 3 ) 变异( m u t a t i o n ) 这是在选中的个体中，对个体的某些基因执行异向转化。在串趣中， 如果某位基因为1 ，产生变异时就是把它变成0 ；反亦反之。 遗传算法的原理可以简要给出如下： c h 0 0 s ea n 蛐 a lp o p u l a t i o n d e t e r m 白畦t h e 盘i 坞吕so fe 钏出证d i v i d u a i p c f f b 瑚s e l c c t i o n r 印e a t p e r f b 珊c r o s s o v e r p e r | d 瑚n m t a t i o n d e t e 彻抽en 忙6 t i 峙s so fc a c hi n d 却i d u a l p e r 如彻s e l e c t i o n u n t i ls o 雠s t o p p 如gc r i t 盯i o n 印p s 这里所指的某种结束准则一般是指个体的适应度达到给定的值；或者个 体的适应度的变化率为零。 2 3 遗传算法的步骤和意义 1 初始化 选择一个群体，即选择一个串或个体的集合岛，f l 2 ，h 。这个初始 的群体也就是问题假设解的集合。一般取疗- 3 0 6 0 。 通常以随机方法产生串或个体的集合包，f - 1 2 ， 。问题的最优解将 通过这些初始假设解进化而求出。 第b 页菇3 i 页 中山大学硕士学位论文 第二章遗传算法介绍 2 选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。 适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数，则，( 熟) 称为个体包的适应度。以 聪中岛卜掣 ( 2 3 ) 善， ) 为选中鱼为下一代个体的概率。 显然从( 2 3 ) 可知： ( 1 ) 适应度较高的个体，繁殖下一代的数目较多。 ( 2 ) 适应度较小的个体，繁殖下一代的数目较少，甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲， 就是选择出最优解和较接近的中间解。 3 交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按 交叉概率风在选中的位置实现交换。这个过程反映了随机信息交换；目的在 于产生新的基因组合，也即产生新的个体。 交叉时，可实行单点交叉或多点交叉。 例如个体 置- 1 0 0 1 0 1 & - o 1 0 1 l l 选择它们的左边3 位进行交叉操作，则有 s - 0 1 0 1 0 l 最- 1 0 0 1 1 1 一般而言，交叉概率p c 取值为0 2 5 o 7 5 。 4 变异 根据生物遗传中基因变异的原理，以变异概率p _ 对某些个体的某些位 第9 页共3 4 页 中山大学顼士学位论文利用遗传算法寻找量优折扣因子序列 执行变异。在变异时，对执行变异的串的对应位求反，即把1 变为o ，把o 变为1 。 变异概率以与生物变异极小的情况一致，所以，氏的取值较小，一般 取o 0 1 0 2 。 例如有个体 s _ 1 0 1 0 1 1 对其的第1 ，4 位置的基因进行变异，则有 s ；0 0 1 1 1 1 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无 法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的， 这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 5 全局最优收敛( c o n v e r g e c et ot h eg l o b a lo p t j l n u m ) 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适 应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、 交叉、变异所得到的新一代群体取代上一代群体，并返回到第2 步即选择操 作处继续循环执行。 图2 1 中表示了遗传算法的执行过程。 l 变为9 第l o 页菇3 页 淘汰4 ，5 提高1 。2 2 ，3 交叉 产生6 ，7 中山大学硬士学位论文第二章遗传算法介绍 2 4 遗传算法的特点 1 遗传算法从问题解的串集开始搜索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大差别。传统优化算法是从单个初始 值迭代求最优解的：容易误入局部最优解。遗传算法从串集开始搜索，覆盖 面大，利于全局择优。 2 遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问 题直接相关的信息。遗传算法只需适应值和串编码等同一信息，故几乎可以 处理任何问题。 3 。遗传算法有极强的容错能力。 遗传算法的初始串集本身就带有大量与最优解甚远的信息：通过选择、 交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过 程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 4 遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解 逼近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。 第l l 页头3 4 页 中山大学硕士论文第三章利用遗传算法寻找最优折扣园子序列 第三章利用遗传算法寻找最优折扣因子序列 3 1 算法描述 利用遗传算法，我们就可以快速地找出局部最优的折扣因子序列。我们首先 定义折扣因子序列 4 乙，其中嗔( 0 1 。在f 时刻，瞑的先验方差为 尽一矿( 包1 日。) g q 一。g + 彬一卑+ 彤。由于耳1 。4 暑，即墨一卑，所以 q 彬! 弓。这样就可以得出嘭的估计了。接下来的任务就是寻找最佳折扣因 子了。 下面给出寻找最佳折扣因子序列的步骤。 第一，生成初始群体。给定初始样本数量加舷e ( 如5 0 ) ，然后利用随机函 数生成加f t 娩譬个折扣因子序列( 每个因子序列为一个f 维的向量) 。 第二，计算初始群体中因子序列各自的脚g 。根据定理1 1 给出的更新方程 和( 1 1 ) 式计算每个折扣因子序列的m 艇。 第三，计算群体中各自被选中交配的概率。计算公式为 p 折扣因子序列被选中的概率 - 害掣菩辈鬻雾甏器i ：；辫 第四，选出一对折扣因子序列进入“交配池”。随机生成一个概率p o e 【o ，1 ， 再随机抽取一对折扣因子序列。若这对折扣因子序列被选中的概率均大于p o ， 则进入“交配池”；否则重新抽取一对折扣因子序列( 放还重取) ，直到取出合乎 要求的一对折扣因子序列为止。 第五，交配。对交配池内的两个折扣因子序列，对每一个位置f ( 1 f 蔓f ) 都生 成一个概率p i 0 ，1 ，若b 大于预先设定的交叉概率以，则进行交叉操作，从 而生成两个新的折扣因子序列。如交叉概率p c 一0 5 0 ，t 一5 0 第1 2 页共3 页 中山大学硕士学位论文 利用遗传算法寻找最优折扣因子序列 l123 45 0 a o 3 80 “o 7 20 0 20 9 6 折扣因子l 0 3 2o 5 40 6 80 9 70 7 2 折扣因子2 o 6 2o 9 80 3 40 5 90 4 5 新折扣因子1 0 3 20 9 8 o 3 4o 9 7 o 4 5 新折扣因子2 0 6 2o 5 40 6 8o 5 9 o 7 2 第六，变异。对新生成的折扣因子序列，每一个位置f ( 1 墨f 墨f ) 都随机生成一 个概率只f o ，1 】，若a 小于预先设定的变异概率以，则重新由随机函数生成一 个6 ；代替现有的点。 第七，计算新生成的两个折扣因子序列的鹏e 。通过第五步和第六步生成了 一对新的折扣因子序列，也是通过定理1 1 给出的更新方程和( 1 1 ) 式计算这对 折扣因子序列的肘龉。 第八，把这一对折扣因子序列加入到群体中，形成新的群体。 重复第三步至第八步，直到群体数日达到预定数目( s 钯e ) 为止。 第九，比较群体中各折扣因子序列的脚，得出最优折扣因子序列。 3 2 算法复杂度 本节会分析该算法的计算复杂度。按照一般计算算法复杂度的方法，是计算 算法中乘除运算、比较运算以及生成随机数几种运算的次数。 由定义1 1 的动态线性模型，下面按照3 1 节提到的算法步骤逐步计算遗传 算法的算法复杂度。 1 生成初始群体。初始群体的数目为砌i 【f 瓯裾，即有加靠勋个折扣因子序列， 每个折扣因予序列有f 个折扣因子，故需要做抽j f 瓯掰x f 次运算： 2 计算初始群体中豹脚e 。计算腻踞的运算次数比较复杂，对于单一一个 折扣因子序列，可以通过定理1 1 给出的更新方程得到。 对每个时刻f ，f 一1 ，2 ，t ( 1 ) q - g m 。，墨一q e 鹪+ 形。这里g ，c i 。均为万x 维矩阵，慨一。 第1 3 页共3 4 页 中山大学碗士论文 第三章莉月j _ 遗传算法寻找优祈扣茵子序列 为，l 维向量，故计算吩需要做一2 次乘法，霉- q c l 爿需要做孙3 次乘法，由 于研未知，所以要应用折扣因子模型置一d 卑，因此要多做h 2 次乘法a 故这 一步一共需要做2 ( 再3 + 一2 ) 次运算； ( 2 ) 五一曩7 q ，妨一互碍+ 墨。同样地，计算石需要做埘次乘法，q 需 要埘2 + r 2 丹次乘法。故这一步一共需要做m ( 1 + ，+ n 1 次乘法 ( 3 ) 4 ；r e q i l ，q - 咒一z ，啊- 嘎十4 弓，e 尽一4 q 4 。计算岔1 需 要做3 ，3 次乘除运算，而计算4 需要做聃2 + ，2 n 次乘法，需要m 次乘法，c f 同样需要州2 + r 次乘法故这一步一共需要做3 r 3 + m ( 1 + 2 ，+ 2 n ) 次运算； ( 4 ) 综合前3 步，对于某一个时刻i ，一共需要做 2 ( 玎3 + n 2 ) + 3 厂3 + m ( 2 + 3 ，+ 孙) 次运算。 由于f 遍历1 2 ，f ，故一共需要【2 ( 升3 + 月2 ) + 3 r 3 + m ( 2 + 3 ，+ 孙) 】f 次运算，另 外臃e 罗母需要做1 次运算。至此，计算单个折扣因子序列的 舰需要 f 箭。 做f 2 ( n 3 + 一2 ) + 知3 + m ( 2 + 3 ，+ 抽) 】f + f + 1 次运算，初始群体的数目为如淞妇 个折扣因子序列，故计算初始群体的m 蛆的运算次数为 【z 0 3 + 丹2 ) + 却3 + 埘( z + + 知) 】“- 1 如一 3 计算群体中各自被选中交配的概率。假设当前的群体数量为小，求每个折 扣医子的j l f 跖的倒数需要做m 次除法运算，计算概率也需要做m 次除法运算。 故一共需要做2 肼次运算。 4 选取一对折扣因子序列进入交配池。由于涉及随机性，故这一步的运算次 数不能确定，但按照经验，一般不会超过州2 次。 5 交配这一步需要做1 + f 次运算。 6 变异由于涉及是否生成新的随机数，故运算次数不能确定。但最坏情况不 会超过1 + 2 f 次运算。 第“页共3 页 中山大学硕士学位论文利用遗传算法寻找量优折扣因子序列 7 计算新生成的一对折扣因子序列的m 距。由第3 步可以知计算次数为 2 ( 席3 + 荐2 ) + 3 ，3 + 糟( ：+ 3 r + 知) 】x r + t + 1 ) 2 8 重复3 7 ，m 从棚博妇到_ s z 掰，故一共需要做 2 ( n 3 + 珂2 ) + 3 r 3 + m ( 2 + 卦+ 3 ，| ) 】x t + h - 1 x ( 醒一知f 疵e ) + ( 窜+ 2 ) 塑磐 + 了m 2 + 加 m g e 乏+ 2 9 最后比较总群体的m 诬得到最优折扣因子序列。这一步需要做s 妇一1 次 比较运算。 综合1 9 得，由遗传算法得到最优折扣因子序列的计算次数为 加i 心泌x t + 【2 ( 筇3 + n 2 ) + 3 ，3 + ，n ( 2 + + 孙) 】f + f + 1 】x 娩e 巾+ 2 ) 坠笋+ ( 。盖：小寸一- 假设加淞觇- 5 0 ，s z 醒一2 0 0 ，f - 5 0 ，厅- 1 0 ，一l ，则大概需要做3 x 1 0 7 次运算，也就 是说一般家用计算机可以用不到1 秒的时间就可以得到结果。 可见，遗传算法有着无可比拟的优势：较短时间内得到比较优的结果。 3 3 预测 在得到最优折扣因子序列后，我们就可以对未来的数据进行预测。假设从历 史数据已经得到( qi q ) 一( 鸭，c | ) 和 岛) 厶，对f 时刻以后的数据预测也可通过 定理1 1 得到。唯一的问题就在于在r 时刻以后的折扣因子应该如何选择。由于 假设6 是服从某种分布f ，而从 磊) | 。又可以得到6 的经验分布f ，因此在f 时 刻以后的折扣因子只需要从经验分布i 中抽取即可。 第1 5 页共3 4 页 中山大学硕士论文第四章算倒 第四章算例 这章首先会通过三个模型去评估由遗传算法得出的最佳折扣因子序列的 预测效果。第一个模型是h a t i 洳n 和w e s t ( 1 9 9 7 ) 【9 1 在第2 章提到的简单一元 动态线性模型，第二个模型是第1 0 章提到的季节模型。第三个模型是一二元动 态线性模型，数据是模拟生成的。最后再通过一个模型给出估计系统方差阵的方 法。 4 1 筒单一元动态线性模型 表4 1 ( 见附录a ) 给出1 9 7 5 年1 月到1 9 8 4 年7 月一共1 1 5 个月份美兀与 英镑的兑换变化率1 。我们把前1 1 0 个月的数据作为“历史数据”，通过这1 1 0 个 月的数据算出最优折扣因子序列，得出其经验分布以及鸭。和c l 。然后再对 x 1 l i x 。；进行预测。再把其预测的均方误差与旧方法进行比较。 通过经验得知，此兑换变化率满足以下动态线性模型。 x 一只+ 屹 v | i 矿一l ( o ，y ) q - 只。+ q鸭i 彤一1 ( o 彤) 给定初始先验信息( ld 0 ) d ( o ，1 ) ，由于y 未知，故给出y 的初始先验 y 一硒a “o 0 1 ) a 采用折扣因子模型，定义折扣因子序列 最) 。，令 彬学c | - l a 根据定理1 1 给出的更新方程，通过遗传算法，我们令初始群体数目为5 0 ， 然后开始迭代，直到群体数目为2 0 0 时停止迭代，在奔腾赛扬i i6 0 0 处理器， 2 5 6 m b 内存的硬件环境，w 蛔d o w s2 0 0 0p r o 慨s j 0 船l 操作系统下采用c + + 语言编 写程序，用时1 秒得到结果。通过前1 1 0 个月的历史数据得出最优折扣因子，再 对x l ，x 。，进行预测，得到预测的均方误差肘驰o 0 5 5 。与h a r r i n 和w e s t 1 数据来源：h a l m l s o nj 彻d w 硝t m ( 1 9 9 乃聊酷i a n f 。删略甜试功一，i c m 耐出，2 n d b d h i 锄 s p r m 雕啊l 唔n 钾k 曲_ p 咐2 6p 5 7 第1 6 页共3 4 页 中山大学硕士学位论文利用遗传算法寻找量优折扣因子序列 ( 1 9 9 7 ) 【4 】的单折扣因子模型相比，他们假定点一o 9 ，其预测均方误差 朋船- 0 0 0 0 “，本文所用方法的预测精度比它提高了 旦：唑坚= 竺：塑甄1 0 0 。1 4 1 。 o 0 0 0 6 4 4 2 季节模型 考虑一个复杂一点的例子。表4 2 及表4 3 ( 见附录a ) 给出了英国某公司在 1 9 7 6 年到1 9 8 1 年间的月销售数据和经济指标2 。 通过分析，销售数据满足定义1 1 的动态线性模型，其中 e 一( 1 五耳耳耳) ，置为f 时刻的经济指标，易一( 1o ) ， g _ 1 1 g 1 g - ，g l 一 压1 22 1 以 22 ，叫：孙q 3 1 22 13 22 由于未知，故设定( l d o ) _ 砌( ，警) ，其中。6 ，一。1 5 2 。根据经 验，我们直接给出f 一1 时刻的先验分布慨ld o ) 一( 4 ，墨) ，其中 吒。c 9 s ，加7 ，o 6 9 u j s 9 ，o 2 8 3 ，- o - 0 5 0 ，_ o 2 玎，0 j 4 4 卜r 。【 ， r ，- o 0 9 ，焉2 - 0 0 1 ，- 0 0 6 7 _ ，6a 我们采用折扣因子模型，定义三个折扣因 子序列6 n ，4 ：，屯，令 w - 【。一丸氏c 卜屯，r ：。，一屯，凡 继而可得到，c 1 等。 2 数据来源：地螂0 nj _ n d w e 汀m ( 1 9 9 7 ) & 嘶 阳r 睇4 ，嘲窖翻d 功腑埘砌出，2 n d 剧i t i 饥 s p r l “孵- d 唱h 州龇c 岫妇1 0 3 p 3 3 l 第1 7 页麸页 ! 坐查兰堡主丝苎曼苎壁! ! ! 丝 从而 彬一 f 只t1 卑- q q 一。q f # ： f ， 【j 等曩 导只z 訾吃 至此，我们就可以利用遗传算法去寻找最优折扣因子序列哦，6 。d 1 3 0 同4 1 类似，我们把前6 5 个数据作为历史数据，对比进行预测。系统环境与4 1 的设定一样，用时3 0 秒得到结果。其预测均方误差m 姬一o 4 1 7 0 9 1 。与h a i s o n 和w e s t ( 1 9 9 7 ) 【4 l 的单折扣因子模型相比，他们假定嘎o 9 ，6 2t o 9 8 ，6 3t 0 9 5 ， 其预测均方误差m 距一0 4 5 7 1 4 3 。我们的预测精度比它提高了 望：箜! ! 塑= 壁：兰! 翌! ! 1 0 0 。1 5 3 。 4 3 二元动态线性模型 本节主要考虑以下一个二元动态线性模型 y - b + uu i z 一2 ( o ，z ) q 一只一。+ 鸭q i 一2 ( o ，矽) 为了生成模拟数据，我们假定岛。( 习，z 。( ；习，矽。( ；：) 。在此假定下，我 们生成5 0 0 个模拟数据，y ，y ：，) ，。 得到模拟数据后，我们再假定在矽未知，初始先验为( 岛fd 口) 一( ，c 0 ) ， 其中- ( 1 ) ，c 0 _ ，的情况下，利用折扣因子模型对x 进行预测，同4 1 类似， 把前伽个数据作为“历史数据”，对l 进行预测。为了方便起见，我们 算蝠翼拄3 4 页 中山大学硕士学位论文 利用遗传算法寻找最优折扣因子序列 假设z 为已知。同样地，设定折扣因子序列 4 。，令彬一半c - l 。系统环境 与4 1 的设定一样，我们得到埘：踞。刍善石- 4 5 4 阱。 1 一 而采用单一折扣因子模型，利用穷举法，取d o 0 1 o 0 2 ，0 9 9 ，1 0 0 ，当 6 - o 0 8 时有展优预测，朋船，3 7 1 1 4 5a 由此可见，多折扣因子模型的预测精 度反而不及单折扣因子模型。究其原因，是因为在这组数据中彬为一恒定矩阵， 由h a r r 幻n 和w b s t ( 1 9 9 7 ) 【9 1 的定理5 5 知c 有极限，亦即当f 足够大的时候， 为一恒定值。当采用单折扣因子时，由( 1 1 ) 求出的彬也为定值，由此得出的预 测与模型更为吻合，而采用多折扣因子时，虽然e 为一恒定值，但由于折扣因 子每个时刻不同，因此由( 1 1 ) 求出的彬不为恒定值，与模型不吻合。因此采用 多折扣因子模型的预测精度反而会更低。 那么当彬不为恒定时，采用多折扣因子就可以得出不同的彬，与单折扣因 子相比，多折扣因子与实际模型更为吻合。为了验证这一点，我们对模型做稍微 的修改。同样是采用上述二元动态模型，但在生成模拟数据时，系统方差阵并不 是恒定矩阵，而是对于每一时刻f ，在以下三个矩阵中 暇一( 叫嵋。( 任意抽取一个作为该时刻的系统方差阵，从而得出5 0 0 个模拟数据_ ) ，。，y ：，y 。 同样地预测，我们得到托锈一6 7 4 8 7 1 。而采用单一折扣因子，当6 - 0 5 时有最 优预测凇e 一7 5 1 0 2 6 ，我们的预测精度比它提高了 三坠罂呈：；竺翌x 1 0 0 1 0 。可见，在系统方整阵为不恒定时，采用折扣因 7 5 1 0 2 6 子序列的预测效果要比单一折扣因子为优。 4 4 系统方差阵的估计 从定理1 1 以及( 1 一1 ) 式就可以得到系统方差阵的估计。我们仍然考虑一个简 第1 9 页共3 甄 中山大学硕士论文 第四章算倒 单的一元模型。 y 一缉+ v fe l y 一。( o ，y ) b 一只一。+ qq i 彬一m ( o ，彬) 我们令岛1 ，矿一1 ，彬一1 0 毛，其中t e x p ( 1 ) ，由此我们生成5 0 0 个模拟数 据y l ) ，m 。 得到数据后，我们再假定彬为未知，初始先验为( 吼ld o ) 一( 】，】) ，设定折 扣因子序列 瓯) 。，令彬半g 一。当找到最优折扣因子届，我们再利用( 1 1 ) 式求出系统方差序列 彬) 。，再由t 一哆乞求出t ，从而得出t 的经验分布。我 们利用k o l m o g o r o v s m i r n 0 v 检验，检验t 是否服从指数分布，由s p l u