（系统工程专业论文）连续禁忌搜索算法改进及应用研究.pdf

浙江大学硕士学位论文 摘 要 本文 对连续禁忌 搜索算法作出 改 进， 提出 了 两 种改 进的 算法i t s 和t s _ s q p , 并将改进的算法应用于系统辨识以及反馈神经网络的训练。 本文主要的研究成果 和创新点包括: i ) 对连续禁忌搜索算法进行改进， 提出了改进的算法i t s 。 在i t s 算法中， 既考虑到多样性搜索策略， 将当 前点的邻域空间用一组同心超矩形进行划分， 在 每个外围同心超矩形中随机选取一个点组成部分邻域; 又通过改进引入了 特赦规 则， 在中心超矩形内也随机选取一定数量的点， 与外围同心超矩形内选取的点共 同组成当前点的邻域。 通过对一些典型测试函数的仿真结果表明改进算法有助于 更快、更精确的搜索到全局最优点。 2 ) 针对禁忌搜索算法局部搜索的随 机性， 首次 提出了 一种与s q p 算法 结合 的 禁忌 搜索算法， t s _ s q p 。 利用禁忌 搜索 算法的 全局收敛 性， 结合s q p 局 部搜 索快速收敛的能力， 改善传统禁忌搜索算法的搜索能力， 使禁忌搜索算法可以 获 得精确的 最 优点。 在t s _ s q p 算法中， 首先产生当 前点的 邻域. 然后以 邻域内 的 每个点为初始点运行s q p 算法， 所有收敛点构成新的 邻域， 最后运用t s 规则更 新当 前点。 仿真结果表明， 与i t s 比 较， t s _ s q p 全局收敛的 速度更快， 获得的 最优点更精确。 3 ) 将改进禁忌搜索算法 ( i t s . t s _ s q p ) 应用于系统辨识，以改善传统的 辨识办法存在局部极小等缺点，并实现了对包括滞后在内的所有参数同时辨识。 通过对液位储罐模型、 离散、 连续以及高阶系统的仿真实验表明了算法的可行性 及有效性。 4 ) 将改 进的 禁忌 搜索 算法 ( i t s . t s s q p ) 应用于反 馈 神经网 络的 训 练。 其方法实质是将神经网络的训练问题转化为优化问题， 利用禁忌搜索算法的全局 寻优能力获得最优的 神经网络权值与阐 值。 仿真实验表明了该方法具有很好的 性 能，并且简单易实现。 关键词: 禁忌搜索;s q p ;系统辨识;反馈神经网 络 浙江大学硕士学位论文 ab s t r a c t t w o i m p r o v e dt a b u s e a r c h a l g o r it h m s , i t s a n d t s 多q p , a r e d e v e l o p e d f o r g l o b a l o p t i m i z a t i o n p r o b l e m s . t h e i r a p p l i c a t i o n s o n s y s t e m i d e n t i f i c a t io n a n d t r a i n i n g o f r e c u r r e n t n e u r a l n e t w o r k a r e a l s o s t u d i e d . t h e m a in r e s u l t s c a n b e s u mma r i z e d a s f o l l o ws : ( 1 ) a n i m p r o v e d c o n t i n u o u s t a b u s e a r c h a l g o r i t h m , i t s , i s d e v e l o p e d . i n t h e i t s , t h e n e i g h b o r s p a c e o f c u r r e n t s o l u t i o n i s p a r t i t i o n e d b y a s e t o f c o n c e n t r i c h y p e r r e c t a n g l e s . i n s i d e e a c h c o n c e n t r i c h y p e r r e c t a n g l e , o n e p o in t i s r a n d o m l y s e l e c t e d a s a n e i g h b o r o f t h e c u r r e n t s o l u t i o n . c o n s i d e r i n g t h e i n t e n s i f i c a t i o n s t r a t e g y a n i m p r o v e m e n t i s m a d e b y s e l e c t i n g a c e r te n n u m b e r o f p o i n t s a l s o i n s i d e t h e c e n t r a l h y p e r r e c t a n g l e f o l l o w i n g a n a s p i r a t i o n c r i t e r i o n . a l l s e l e c t e d p o i n t s g e n e r a t e t h e n e i g h b o r h o o d o f t h e c u r r e n t s o l u t i o n . n u m e r i c a l s i m u l a t i o n r e s u l t s p r o v e t h a t t h e e x t r a s e l e c t io n i n s i d e t h e c e n t r a l h y p e r r e c t a n g l e e n a b l e s t h e i t s t o o b t a i n m o r e p r e c i s e g l o b a l m i m i n u m w i t h l e s s t i m e c o s t ( 2 ) f u r th e r i m p r o v e m e n t o f t h e t a b u s e a r c h i s p r o p o s e d b y c o m b i n e w it h t h e s q p m e t h o d . a s a k i n d o f r a n d o m s e a r c h a l g o r i t h m , t h e p e r f o r m a n c e o f t s i s l i m i t e d . t h e s q p , g o o d a t f a s t c o n v e r g e n c e y i n l o c a l s e a r c h , i s i n t r o d u c e d t o p r o p o s e a n e w a l g o r i t h m , t s _ s q p . i n t s s q p , t h e s q p a l g o r i t h m s t a r ts fr o m e a c h p o in t i n t h e n e i g h b o r h o o d o f c u r r e n t s o l u t i o n a n d c o n v e r g e s a l o c a l m i m i n u m ; a l l t h e s e l o c a l m i n i m a c o n s i t i t u t e t h e n e w n e i g h b o r h o o d o f t h e c u r re n t s o l u t i o n ; t h e n t h e p r o g r a m c o n t i n u e s b y e x a c t i n g i t s . c o m p a r e d w i t h i t s , t h e s i m u l a t i o n r e s u lt s s h u w t h a t t s _ s q p c a n o b t a in m o r e p r e c i s e g l o b a l m i m in u m a n d c o s t s l e s s t i m e . ( 3 ) t h e i m p r o v e d t a b u s e a r c h a l g o r i t h m s i t s a n d t s s q p a r e a p p l i e d o n s y s t e m i d e n t i f i c a t i o n . t h e p r o b l e m s o f s y s t e m i d e n t i f i c a t i o n a r e t r a n s f o r m e d t o o p t i m i z a t i o n p r o b l e m s i n p a r a m e t e r s p a c e , a n d t h e n t h e i t s a n d t s _ s q p a l g o r it h m s a r e u s e d t o o b t a i n t h e g l o b a l o p t im a l e s t i m a t i o n o f t h e s y s t e m p a r a m e t e r s . t h e r e s u l t s o f s i m u l a t i o n s o n a t a n k m o d e l , a d i s c r e t e a n d a c o n t i n u o u s t w o - o r d e r s y s t e m , a n d a h i g h i v 浙江大学硕士学位论文 o r d e r s y s t e m ( 4 ) t h e d e m o n s t r a t e t h e f e a s i b i l it y a n d e ff e c t i v e n e s s o f i t s a n d t s _ s q p . i mp r o v e d t a b ua l g o r i t h m s , i t s a n d t s _ s q p , a r e a p p l i e d o n t h e t r a in i n g o f r e c u r r e n t n e u r a l n e t w o r k . t h e t r a i n i n g p r o b l e m i s c a s t a s o p t i m i z a t i o n p r o b l e m i n p a r a m e t e r s p a c e . t h e n u m e r i c a l s i m u la t i o n r e s u lt s s h o w t h a t t h e y a r e s i m p l e y e t e ff e c t i v e k e y w o r d s : t a b u s e a r c h ; s q p ; s y s t e m i d e n t i f i c a t i o n ; re c u r r e n t n e u r a l n e t w o r k v 浙江大学硕士学位论文 第1 章 绪论 ， . ，禁忌搜索算法 1 . 1 . 1背景 智能优化方法是伴随着计算机技术的高速发展和实际问题对优化方法的要 求而产生的。 实际问题要求优化方法对目 标函数、 约束函数的表达形式应更加宽 松， 这样优化方法才有更加广泛的应用领域， 传统优化方法的连续可导的要求有 点过于严格。 另外， 实际问题往往要求优化算法要有一定的智能性和模糊性， 这 对优化算法要求较高， 但在实际问题中这种不确定性是大量存在的。 实际问题的 这种要求是智能优化算法产生的前提。 计算机技术的高速发展， 计算能力的大幅 提高，内存容量的不断加大， 是智能优化算法产生的必要条件， 它为智能优化算 法的运算提供了可能性。 在这种背景下， 七、 八十年代提出了几个有效的智能优 化 算法， 其中 包 括遗 传 算 法( g e n e t ic a lg o r it h m , g a ) d 1 , 禁 忌 搜 索 算法( t a b u s e a r c h , t s ) 2 .3 和 模 拟 退 火 算 法( s im u l a t e d a n n e a l in g , s a ) 4 1 . 其中 禁忌搜索 ( t s )的思想最早由 g l o v e r 提出 2 ,3 1 ， 它是对局部邻域搜索的 一种扩展， 是一种全局迭代寻优算法， 是对人类智力过程的一种模拟。 禁忌( t a b u 或者 t a b o o ) 表示禁止的意思，来源于汤加语， 居住在汤加群岛的土著人用这个 词来表示神圣不可触犯的东西。 t s 通过引入一个灵活的存储结构和相应的禁忌 准则来避免迂回搜索， 并通过特赦规则来赦免一些被禁忌的优良 状态， 进而保证 多样化的有效搜索以 最终实现全局优化。 t s 也是人工智能的一种体现， 其最重 要的思想是标记对应己搜索到的局部最优解的一些对象， 并在进一步的迭代搜索 中尽量避开这些对象， 而不是绝对禁止循环， 从而保证对解空间中的不同区域进 行有效的搜索。 浙江大学硕士学位论文 1 . 1 . 2基本原理 在禁忌搜索算法中， 邻域( n e i g h b o r h o o d ) 、 禁忌表 ( t a b u l i s t ) 、 禁忌长度( t a b u l e n g t h ) 、 特赦规则( a s p i r a t i o n c r i t e ri o n ) 、终止规则 ( t e r m i n a t i o n c r it e r i o n ) 等基本 概念成为算法设计的关键。 下面介绍各概念在组合优化领域的基本定义。 以一个 5 城市的旅行商问题( t r a v e l i n g s a l e s m a n p r o b l e m , t s p ) 为例， 其距离数据如图 1 . 1 表示，对应的距离矩阵为: 1 0 1 5 6 l320 oocu n九x n介、曰 20l5 l39 0101562 一一 l d f 一- d 图 1 . 1 : t s p 距离数据图 假设其初始路径为 x o = ( a b c d e ) o 1 . 1 . 2 . 1 邻域 ( n e i g h b o r h o o d ) 光滑函数极值的数值求解中， 邻域是个非常重要的概念， 函数的下降或上升 都是在一点的邻域中寻求变化方向。 在距离空间中， 通常的邻域定义是以一点为 中心的一个圆。 在组合优化中， 距离的概念不再适用， 但是在一点附近即邻域搜 索另一个下点仍是组合优化数值求解的基本思想。 针对不同的组合优化问题，邻域的定义有各种不同的方法，常用的方法是 2 - o p t ， 并由 其推广出k - o p t 。 在上面所举的t s p 例子中， 对于 初始点x o ， 用2 - o p t 方 法产生的 邻域n ( x o ) 由 如下解构成: n ( x o ) = ( a c b d e ) , ( a d c b e ) , ( a e c d b ) , ( a b d c e ) , ( a b e d c ) , ( a b c e d ) ) ; 其目 标函 数值对应为 4 3 , 4 5 , 6 0 , 6 0 , 5 9 , 4 4 ) . 1 . 1 . 2 . 2禁忌表 ( t a b u l is t ) 为了避免重复工作，避免可能的局部内循环，以期跳出局部极小，t s将建 立禁忌表以 禁忌一定时期内 进行过的工作。 禁忌表有两个重要的指标是禁忌对象 浙江大学硕士学位论文 和禁忌长度。 a ) 禁忌对象 顾名思义， 禁忌对象是指禁忌表中被禁的那些元素。 根据解状态的不同变化 类型。 禁忌对象可有三类:简单解，向 量分量变化，目 标函数值。 1 )简单解 当解从一个解移动 ( m o v e )到另一个解，如上例中从 x o移动到 x 1 , x , 可 能是局部最优解，为了避开局部最优解， 禁忌x ， 这个解再度出现。禁忌的规则 是:当x 。 的 邻域中有比 它更优的 解时， 则选择最优的 解; 当x : 为n ( x j ) 的局部最 优时，不再选择x ) ，而选择除x , 外的最优解。 1 1 )向 量分量变化 解向量分量的变化以解向量的每一个分量为变化的最基本因素。以上面的 t s p问 题为例， 解向量的变化是两分量相互交换引起的。 考虑解从x o = ( a b c d e ) 变化到x , = ( a c b d e ) ，它的变化实际是由b和c的对换引 起， 但b和c的对换 可以引起更多解的变化，如: ( a b c e d ) 一 ( a c b e d ) , ( a b d c e ) 一 ( a c d b e ) , ( a e c d b ) 一 ( a e b d c ) , 等等，如果b和c交换被禁忌，这些情况的变化都将被禁忌。 1 1 d目 标函数值 在最优问题求解过程中，非常关心目 标函数值是否变小 ( 或变大) ，是否接 近最优目 标值。 如同等位线的道理一样， 把处在同一等位线的解视为相同。 若某 一目 标函数值被禁忌，那些有此目 标函数值的解都将被禁忌。 b ) 禁忌长度 禁忌长度是被禁忌对象不允许选取的迭代次数， 具体实现可以 给被禁对象z 一个数 ( 禁忌长度) t ，要求对象x 在t 步迭代内i 记忆， 每迭代一步， 该项指标做运算t a b u ( x ) = t - 1 ， 直到t a b u ( x ) = 0时解禁;也可 浙江大学硕士学位论文 建立一个长度为t 的禁忌表， 每步迭代时把新的被禁对象放到表头，表中原有元 素按顺序后移， 若禁忌表已满，则最后一个元素将被踢出禁忌表，即被解禁。 有 关禁忌长度 t 的选取，可以归纳为下面几种情况: ( 1 ) t 为常数，如t = 1 0 。 这种规则容易在算法中实现。 ( 2 ) t e t m in + 司。 此时t 是可以 变化的数， 它的 变化是依据被禁对象的目 标 函数值和邻域的结构。此时t m in r t m a x 是确定的。确定t m m , t- 的常用方 法 是 根 据问 题的 规 模t ， 限 定 变 化区 间a 万. 8 万 ( 0 a b ) 。 也 可以 用 邻 域 中 解 的 个 数。 确 定 变 化 区 间 a 石， a 而 。 当 给 定 了 变 化 区 间 ， 确 定 t 的大小主要依据实际问 题， 实验和设计者的经验。 如从直观可见，当函 数值下降较大时， 可能谷较深， 欲跳出局部最优， 希望被禁的长度较大。 ( 3 ) t m m ， t 。动态选取。 有的情况下， 用的变化能达到更好的解。 它的基本思 想同 ( 2 ) 类似。 禁忌长度的选取同实际问题， 实验和设计者的经验有精密的联系， 同时它决 定了计算的复杂性.过短会造成循环的出现，过长又造成计算时间较长。 1 . 1 . 2 . 3特赦规则 ( a s p i r a t i o n c r it e r ia ) 在t s 算法的迭代过程中，会出现候选集中的全部对象都被禁忌，或有一个 对象被禁，但若解禁则其目 标函数值将有非常大的下降情况。在这样的情况下， 为了 达到全局的 最优， 应该让一些 禁忌 对象重新 可选。 这种方法称为 特赦， 相 应的规则称为特赦规则。讨论求极小值问题，常用的特赦规则有: ( 1 ) 基于评价值的规则。 在算法迭代过程中， 记忆已出 现的最好解x b - r ， 当候 选集中出 现一个解x n . h ， 其评价值( 可能是目 标函数值) 满足c ( x n o w ) c( x b e , j) 时，即使x n ，被禁忌，当前点也可移动到x n o w ，即x n o w 被解禁。 ( 2 ) 基于最小 错误的 规则。当 候选集中 所有的 对象都被禁忌时， 而 ( 1 ) 的 规 则又无法使程序继续下去，为了得到更好的解，从候选集中的所有元素 中选一个评价值最小的状态解解禁。 ( 3 ) 基于影响力的规则。有些对象的变化对目 标函数值的影响很大，而有的 变化影响较小。应该关注影响力大的变化。从这个角度理解，如果一个 浙江大学硕士学位论文 影响力大的变化成为被禁对象，应该解禁它，这样才能得到问题的一个 更好的解。 1 . 1 . 2 .4终止规则 ( t e r mi n a t i o n c r it e r i o n ) t 5是一个启发式算法，不可能让禁忌长度充分大，只希望在可接受的时间 里给出一个满意的解。 于是很多直观， 易于操作的原则包含在终止规则中。 下面 给出常用的终止规则: ( 1 ) 确定步数终止。给定一个充分大的 数n ，总的 迭代次数不超过n步。即 使算法中包含其他的终止原则，算法的总迭代次数有保证。这种原则的 优点是易于操作和可控计算时间，但无法保证解的效果。 ( 2 ) 频率控制原则。当某一个解，目 标函数值或元素序列的频率超过一 个给 定的标准时，如果算法不做改进，只会造成频率的增加，此时的循环对 解的改进已无作用， 因此， 终止计算。 这一规则认为: 如果不改进算法， 解不会再改进。 ( 3 )目 标函数值变化控制原则。在禁忌搜索算法中，提倡记忆当前最优解， 如果在一个给定的步数内，目 标函数值没有改变，同 ( 2 )相同的观点， 如果算法没有其他改进，解不会改进。 此时，停止运算。 ( 4 )目 标函 数值偏离 程度原则。 对一些问 题可以 简单地计算出 它们的 下界( 目 标值为 极小) ， 记 一个问 题的 下界为z rb ，目 标函 数值为弃 刁 。 对给定的 充 分小的正数e r当.f (x ) - z b er f ，终止计算。 这表示目 前计算得到的 解与 最优解很接近。 1 . 1 . 2 . 5算法流程 总结以上各算法要素，可归纳出禁忌搜索算法一般步骤: 步骤 1 :随机生成一个初始点x o ， 计算出它的目 标函数值， 初始化当 前点 。 ， 最 优点x a e s i- x o . a x a e sr) a x o ) o 步骤2 :生成当前点x 的邻域，计算出 邻域内各点的目 标函数值， 步 骤3 : 选邻域内目 标函 数值最小的 点x o 浙江大学硕士学位论文 步骤4 : 判断特赦规则。 如果 特赦规则满足， 则新的当前点移到x ， 即x x , 同 时 更 新 最 优点x b s t= - x , f x a e sr) a x ) ， 转 到 步 骤6 ; 否 则 转 到 步 骤5 0 步骤5 : 判断点x . 是否被 禁忌。 如果点x 没被禁忌， 新的当 前点 移到x , 转到步骤6 ;否则x 从邻域中 删除， 转到步骤3 . 步骤6 : 更新禁忌表， 并判断终止规则。 若终止规则满足， 则终止计算， 否 则转到步骤2 . 1 . 1 .3研究进展 1 . 1 . 3 . ，理论与算法研究 ( 1 ) 收敛性研究 算法的全局收敛性研究是算法理论研究的重要方面。在这一点上，t s 远不 及 s a 和 g a 那 样 完 善， 但 也 取 得了 一 些 成 果。 如 f a ig le 等 5 1 得 到了 概率 型 t s 的 一 些 结 果 ;g lo v e r 等 6 得到了 基于 最 近记 忆 或 频 率记 忆的 t s 的 一些 结 果。 这主 要 是因 为t s 只是一个框架性的思想，没有确定的、具体的数学模型，难以进行准确的 数学分析。 此外， 算法的收敛速度估计和鲁棒性也应进行研究，目 前暂无这方面 的研究成果，今后需大力探讨。 ( 2 ) 算法参数的选择研究 算法参数是影响算法性能和效率的关键， 如何确定最优参数使算法性能最 佳， 本身就是一个极其复杂的优化问题。 由于参数空间的庞大和各参数之间的相 关性， 尚无确定最优参数的一般方法， 目 前在求解实际问 题时主要是凭经验选取 算法参数。影响t s 性能的参数主要有禁忌表大小、邻域结构和数量、特赦规则 和禁忌准则的 设 置等。 其中 g l o v e r 在文献 2 ,3 中 对 禁忌搜索算法的 结构、 参数的 选 择等方面进行了详细描述和讨论。 ( 3 ) 算法操作的 研究 算法操作是算法实施优化进程的关键步骤， 设计优良的操作对改善算法性能 和提高效率具有重大作用。 从搜索结构上考虑， 邻域函数结构、 状态更新方式和 收敛判据最重要，关键参数的控制可归入参数选择的研究内容。在t s 中研究得 最多的是邻域结构和禁忌表结构。如孙元凯等 8 提出了一种变邻域结构的 t s 算 浙江大学硕士学位论文 法 ;g lo v e r 等 8 1提出 了自 适 应 记 忆 的 t s 算 法 ; j d z e f o w s k a 等 t9 1 , p e r e z 等 10 1 研 究 了 各 种禁忌 表结 构的影响; s a lh i 1 1 1研究了 禁忌 表长度 及 特赦规则的 影响。 ( 4 ) 混合算法的研究 为提高优化性能和效率， 近年来， 将两种或几种启发式算法结合在一起， 互 相取长补 短， 己 形成一 种趋势。 就 t s 而言， 主 要是与 g a 和s a 的结 合1 2 - 1 5 1 。 也有 s a 和t s 的 结合 1 6 . 1 8 1 。 研究表明， 混合 算法对 算 法性能和效率 有较大幅度的 改善。 1 . 1 . 3 . 2应用研究 由于t s 具有很强的通用性， 且无需问 题的特殊信息，因此，其应用领域非 常广泛。目 前主要的应用领域有: ( 1 ) 生 产调 度。 这是 t s 应用最为 广泛， 也 最为 成 功的 领 域。 包括f lo w - s h o p 和 j o b - s h o p 等问 题的 求 解 19 -2 4 1 . ( 2 ) 组 合 优 化。 如 t s p 的 求 解2 5 ,2 6 1 , 0 - 1 背 包问 题的 求 解 2 2 1等; ( 3 ) 神 经网 络 设 计。 主 要是 将 t s 作为 前向 神 经网 络的 学习 算 法， 如 s e x t o n 等 t2 8 1 y a m a z a k i 等 2 9 1 . b a tt it i 等 3 0 1 . 1 . 2连续禁忌搜索算法 t s是为了解决组合优化问题而提出的，并且一经提出就得到广泛关注，许 多应用实例也表明了t s对解决组合优化问 题的优越性能。鉴于t s 在组合优化 领域的迅速发展， 有些学者尝试把它应用到连续优化问题的求解， 并取得一些成 果3 i -0 d 1 。 连续优化问 题和组合优化问 题的区别在于解空间的连续性， 因 此邻域的 定义以及禁忌的含义将有很大的不同。 针对解空间的连续性， 通常用圆或矩形来 定义一个点的邻域。 但这样定义出的邻域内 将有无穷多个可行点， 无法全部计算 各点的目 标函数值。 一般来说， 可以在圆或矩形内随机取一定数量的点， 组成当 前点的邻域。 同样， 在禁忌对象时， 因解空间的连续性， 禁忌一个点没有任何意 义。此时，应该禁忌点及它周围一定范围的区域 ( 圆或矩形) 。 据了 解， n . h u 3 1 是 最早把 禁 忌 搜 索 算法 用 于 连续 优化问 题的 人之 一， 但他 的算法思路跟g l o v e r 所提的t s思路有较大的不同。h u 提出了一个禁忌搜索与 浙江大学硕士学位论文 随机移动 ( r a n d m o v e ) 相结合的 禁忌搜索算法。随机移动的定义为:对于一个 给定的点x 和给定的半径h ， 邻域n ( x , h ) 定义为: n ( x , h ) 二 y : i x 一 y 1 h ) ( 1 . 1 ) 当 点y 是在n ( x ,h ) 随机产生时， 称为y 为邻 域n ( x , h ) 内 的 一个随 机移 动。 在 禁忌 搜索与随机移动相结合的算法中， h u 首先给出一个初始解和一组邻域半径h ; , 并且给定h = f h , , h2,， h , 。 如果目 标函 数的定义区间为 a , b ) ，则半径h ， 定 义为: 气= b 一 a ; ( 1 .2 ) h ,. i = 气 / 1 0 0 ; 1 = 1 , 2 , . - . , r 一 1 ;( 1 . 3 ) 禁 忌 表设 为t ， 被 禁元 素为半 径h ;。 如 果 满 足h ; s h一 t ， 则 称 邻 域n (x ,h ;) 为 可 行邻域( a c t i v e n e i g h b o r s ) 。 在算法的 每步迭代中， 在每个可行的 邻域n ( x , h ;) 内 产 生一个随机移动解， 计算其目 标函 数值。 如果某个点y 的目 标函 数值比当前点的 目 标函数值小，选v作为新的当前解， 并把对应的半径放到禁忌表 t中，如果 h - t 为空，则置t 为空;否则进行下一步迭代。 h u 的禁忌搜索与随机移动相结合的搜索算法步骤可归纳为: 第一步: 产生一个初始 解x ， 给定半 径 集h h = i h j , 扔， ， h , 。 初始化禁忌 表t 为空，设计算器k =o : 第 二步: 在每 个可 行 邻 域n (x ,h ;) ( 杠 e h一 t ) 内 ， 随 机 产生 一 个可 行 解; 第三步:比较各可行解与当前解的目 标函数值。如果存在某个点 y使得 1 ( y ) ( x ) ， 把 对应的 半径h 放到禁忌 表t 中， 并设k = 0 ， 转到 第四 步。 如果所 有的 可行 解都有.f ( y ) ? 1 ( x ) ， 并 且k比 某 一个给定的 值要大， 则算 法终止: 否 则设k =k +1 ，并转到第二步。 第四步: 设x = : y 。如果h - t 为空， 转到第五步;否则转到第三步。 第五步:如果终止规则满足，算法结束:否则更新禁忌表t 为空，转到第二步。 在h u 之 后 ，d . c v ij o v i e 和j . k lin o w s k i 提出 了 一 种 新的 想 法， 把 连 续 空 间 离 散 化以 得到 近 似最 优的 解 3 3 。 考 虑。 维空 间s ， 将s 在 其 各 轴向x x2 ， 二 ， x 浙江大学硕士学位论文 上分 别 划分 成p , p 2 , ， 二 ， p 。 份。 对不同 的 优 化问 题， 划 分参 数p 二 ( p i , p 2 , ， 二 ， p n ) 将 不一样。这样，空间s 被划分成一个个小的细胞 ( c e l l s ) ， 对每个细胞进行标注。 在每步迭代中，算法首先均匀的所有细胞中随机选出 n : 个，在每个选中的细胞 中随机选取n , 个点，这些点组成当前点的邻域。 这样当前点邻域内 将有n , * n , 个 点。算法将在这些所有点选出没被禁忌的目 标函数值最优的点作为新的当前点， 这个点并不需要是在当前点的附近邻域内。 两种情况下一个点将被禁忌: ( 1 ) 如 果点所在的区域被禁， 如所在的细胞在禁忌表中; ( 2 ) 如果点导致目 标函数值f 的退化超过一个给定的值。 禁忌表的长度固定为l , 被禁忌的对象为细胞，即每 一步迭代， 算法把访问过的细胞依次放到禁忌表中。 如果禁忌表已 满， 则把新的 细胞放到表头，表中最后一个 ( 最先放入)细胞踢出禁忌表。算法流程归纳为: 第一 步: 初 始 化参 数p = ( p , , p . . . . . p r ) , n . , n , ， 初 始 化 禁 忌 表t 为 空， 随 机 产 生一个初始点， 。 。 第二步: 根据参数 p ， 将解空间 s在在其各轴向xx 2 , . . ., x 。 上分别划分成 p , p 2 , , p份， 生成a p 2 * * p 。 个细胞， 对 每个细 胞进 行标注。 第三步:随机均匀的选出。 。 个细胞，在每个选出的细胞中随机产生n ,. 个点，组 成当前点的邻域，计算出个点的目 标函数值。 第四步: 选出邻域中没被禁忌的 最优点: ， 把对应的细胞c ( ) 放入禁忌表中。 第五步:判断终止规则，若满足则算法终止，否则转到第三步。 之 后p . s ia r r y , r . c h e l o u a h 等 在 文 献 3 5 ,3 7 ,4 0 中 提出 了 一 个 较 成 熟 的 连 续 优 化 问 题 禁忌 搜 索 算法， 并逐 步 对 算 法 进 行了 改 善。 首 先是s ia r r y 在文 献 3 5 提出了 一 个简单的连续优化问题的禁忌搜索算法。 在其算法中， 当前点的邻域空间是用一 系 列同 心 球冠 来 划分， 球冠c , ( s , h h ;_ , ) 的 定 义 如 下: c ; ( s , h ;, h ,_,) 一 s lh ,-, 4 i s - s 1i h i) ( 1 .4 ) 在 每 个 球 冠 c ; ( i = 1 ,2 ， 二 ， k ) 内 随 机 选 取 一 个 点 ， 这k 个 点 组 成 当 前 点 的 邻 域 。 其 中 为了 使当 前点有个明 显的 偏离， 中 心球体b ( s ,h o ) 内 是 禁止选点的。 在k 个邻域 中，最优的点， * 被选为新的当前点。 半径h , ( i = 1 ,2 , . . - , k )( 决定空间的划分方式) 定义方法可有: 浙江大学硕士学位论文 1 )几何划分:半径h ， 根据几何级数2 来计算: 气 - , = 气/ 2 一 ， ，i = 1 , 2 , . - . , k( 1 . 5 ) 其中半径h 。 是个独立变量。 二 / 办 万 、 卜 一 厂 一 ， 3 欠 币 口 吃丫 _斗 一 / ， 亚; r 二 5q二 / w 车一 厂 一 b ( s , 哈 b ( s , 执 ) b ( s , 悦 ) b ( s , 妈 ) b ( s , 吸 ) 图 1 . 2 :邻域空间划分示意图 2 )线性划分: 气 _ ，+ ， = 气* ( k 一 i + l ) l k ，i = 1 , 2 ， 二 、 k ( 1 .6 ) 3 )等容划分: 气 . , = ( h 一 衅l k ) v ，i = 0 ,1 , - - -, k ( 1 .7 ) 算 法在每步 迭代后， 把新当前点s * 的 周围 领域b ( s , e ) 放入禁忌表中， 其中 e = h o 。当 禁忌 表己 满时， 新的 元素 进入同 时 把最先放入禁忌表的 元素 踢出。 算 法流程图如图 1 . 3 所示。 图 1 .3 :连续禁忌搜索算法流程图 浙江大学硕士学位论文 随 后 ， c h e l o u a h 和s i a r r y 在 文 献 3 7 中 对 上 述 禁 忌 搜 索 算 法 进 行了 改 进， 引 入了 集中性 ( i n t e n s i f i c a t i o n )和多样性 ( d i v e r s i f ic a t i o n )策略。 在改进的禁忌搜索算法中，用一组同心超矩形代替同心球冠来划分邻域空 间，如图 1 .4 所示。 图 1 .4 :带多样性测量的邻域空间划分示意图 改进后的禁忌搜索算法主要有以下几个部分构成: 初始化、 多样搜索、 寻最 优区域、集中搜索，流程图如下: 初始化 多样搜索 寻最优区域 集中搜索 输出最优解 图 1 .5 :改进算法的简洁流程图 浙江大学硕士学位论文 在多样搜索部分，算法主要认为搜索出一些可能含有最优解的期望区域 ( p r o m i s i n g a r e a s ) 。 如同 改 进前的 算法 一样， 产生k 个没 被禁忌的点组 成当 前点 的邻域， 并选其中最优的点作为新的当前点。 禁忌表中保存的同样是当前点以及 一给定的半径，即禁忌一球域 ( t a b u b a l l ) 。 算法迭代的同时探测期望区域。如果 邻域内所有点的目标函数值比当前点都要大于一给定的局限， 则认为算法搜索到 一个期望区域。 这些期望区域的中心保存在一个表中，称为期望表 ( p r o m i s i n g l i s t ) 。 为了避免回到以 前走过的区域， 算法要检查新探测到的期望解 ( p r o m i s i n g s o l u t i o n )不在以访问过的期望区域 中心保存在期望表中)中。这个条件可以 保证新搜索方向远离以前访问过的区域。这部分算法流程为: 第一步:初始化个参数，产生一个初始点，作为当前点: 第二步: 用一组同心超矩形产生k 个没被禁忌的点， 组成当前点的邻域。 选其最 优点作为新的当前点; 第三步: 判断新当前点是否为新的期望解。 若当前点是新的期望解且不在以前访 问过的期望区域中，此新的期望解代表一个新的期望区域，将其放入期望表中。 如果期望表已 满， 则最差的期望区域被新的新闻区 域代替; 第四步:判断终止规则。 若终止规则满足， 则算法进行到下一部分;否则， 转到 第二步。 当 在一个给定的步数内 没有探测到新的期望区 域时， 算法将转到下一部分， 在期望表中保存的一组期望区域内探索最优期望区域。具体做法为: 第一步:计算期望表中个期望解的平均目 标函数值; 第二步:删除目 标函数值高于平均值的解; 第三步:把禁忌半径和构成邻域的超矩形半径减半。 第四步:对每个留下来的期望解，生成其的邻域，如果邻域内的最优解好于它， 则代替它。 第五步: 若期望表中期望解的个数大于一个， 则转到第一步; 否则进行下一部分; 算法期望表中此时只保留一个最佳期望解，此期望解定义一个新的搜索区 域， 其中心作为当前点。 禁忌表首先置空， 然后开始新的禁忌搜索: 产生邻域， 选最优点并把最优点放入禁忌表。 此时， 只有当最优点比当前点好时， 才会被替 换成为新的当前点。 当在一个给定的步数内目 标函数值没有改善时， 算法将把禁 浙江大学硕士学位论文 忌表重置， 并把禁忌半径和超矩形半径减半后继续搜索。 当连续一定次数减少这 两个半径后目 标函数值没有改善或迭代总步数达到一给定值时算法将终止。 可以看出，改进后的算法更复杂了，但算法性能也得到较大提高。之后， c h e lo u a h 和s i a r ry在文 献 la o l 中 又 提出了 一 种 禁 忌 搜索 与n e l d e r - m e a d 单 纯 算法 相结合的全局优化算法，利用禁忌搜索算法全局收敛的能力，结合n e l d e r - me a d 单纯算法局部搜索性能， 去改善禁忌搜索算法全局搜索的性能。 算法流程图如图 1 6 所示。 图 1 .6 :算法流程图 可以看出， 与前一个算法不同的是， 当 禁忌搜索算法探测到新的期望区域时 立即转用n e l d e r - m e a d 单纯算法在期望区 域内 进行搜索， 而不是再用禁忌搜索算 法去搜索。 浙江大学硕士学位论文 1 . 3论文结构 综上所述， t s在组合优化邻域迅速发展， 应用非常广泛，算法研究也很完 善。 但在连续优化邻域的研究并不多， 算法还不是很成熟， 算法性能有待进一步 提高。 本论文对连续禁忌搜索算法进行进一步研究， 改善了其性能， 并将其运用 到实际问题中。 本论文的结构安排如下: 论文第一章综述了t s的历史背景，介绍了t s的发展研究概况，及在连续 优化邻域的最新研究成果; 第二章提出了一种改进的t s 算法，并进行了数值仿 真试验; 在第三章， 将t s 与传统的 梯度算法s q p 算法相结合， 利用s q p 局部 快速搜索能力改善t s 算法: 第四章两种改进的t s 算法应用到系统辨识领域中， 取得了较好的效果。第五章研究了改进t s 算法在反馈神经网络训练中的应用。 最后一章对本文进行了总结。 浙江大学硕士学位论文 第2 章 改进的连续禁忌搜索算法 2 . ，引言 禁忌搜索算法最早提出是为了解决组合优化问题的， 算法一经提出就得到迅 速发展， 并在组合优化领域取得巨大成功， 同时也促进了其在连续优化问题领域 的 发展。 据了 解， h u 3 i 是 第一 个 把t s 运用 到连续优化邻域， 但他的 算 法思 路 跟 g l o v e r 的 初 始t s 有 较 大 的 不 同 ， 性 能 有 待 提 高。 c v ij o v i e 3 3 1提出 了 一 种 把 连 续 问 题离散化的思想， 通过在其各轴向上划分， 把整个连续空间离散化成许多小的 空间， 称为细胞 ( c e l l ) ; 标注各个细胞， 并把各细胞看作是离散问题中的一个可 行点， 运用离散问题中的t s 来求解。可以理解，当此算法处理维数很大的优化 问 题时 ， 很 难实 现合理的 空间 划 分。 s i a r r y 等 人 经 过一 系