（计算机应用技术专业论文）并行禁忌搜索算法及其在神经网络优化中的应用研究.pdf

济南大学硕士学位论文 摘要 禁忌搜索是一种亚启发式( m e t a - h e u r i s t i c ) 算法，简称t s ，由美国科罗拉多大学 系统科学家f r e dg l o v e r 教授于1 9 8 6 年首次提出。t s 与模拟退火算法、遗传算法、蚂蚁 算法、混沌等一样，都是通过模拟或揭示某些自然现象或智力过程而形成的一套算法， 以用于求解各种工程问题中的优化解。t s 以其灵活的存储结构和相应的禁忌准则来 避免迂回搜索，在优化算法中独树一帜，已成为计算智能领域的又一热点。 本文首先对禁忌搜索算法做了深入的研究，分析了算法的基本原理及其算法实现 的关键技术，并将算法与其他的优化算法做了比较，在此基础上，本文主要针对以下 两个方面的工作做了更进一步的研究： 一是在串行t s 算法的基础上实现了并行t s 算法，并将遗传算法中的交叉操作思 想引入到了并行t s 中，以提高算法的优化性能。在并行算法运行初期，每个进程执 行一个独立的t s ，并通过遗传算法的交叉操作在每个进程间进行当前最优解的交叉 操作，保证算法的分散搜索能力；运行后期，通过邻域分解策略把计算任务分配到各 个从进程，从而整体上提高算法的优化性能。以函数优化为实验，验证了该算法的可 性行和高效性。 二是将并行t s 算法应用于前馈神经网络中，提高神经网络的泛化能力。并行t s 算法用于神经网络优化主要包括两大方面：一是用于网络学习( 也称网络训练) ，即优 化网络各层之间的连接权值：二是优化网络的拓扑结构。本文研究的是神经网络连接 权值的优化，并构建了一个用并行t s 算法训练神经网络权值的神经网络优化模型，通 过其在入侵检测分类问题以及在汇率兑换预测问题上的应用测试，结果表明，基于并 行t s 的神经网络可以在一定程度上克服b p 算法和遗传算法训练神经网络时的不足，同 时还能得到比基于b p 和g a 的神经网络更好的泛化能力。 关键字：并行禁忌搜索算法，人工神经网络，遗传算法，入侵检测、汇率预测 并行禁忌搜索算法及其在神经弼络优化中的应用研究 a b s t r a c t t a b us e a r c h ( t s ) i sam e t a - h e u r i s t i ca l g o r i t h m , f i r s tp r o p o s e db yf r e dg l o v c ri n1 9 8 6 i ti sf o r m e das e to fa l g o r i t h m sb ys i m u l a t i n go rs h o w i n gs o m en a t u r a lp h e n o m e n o no r i n t e l l i g e n tp r o c e d u r ea ss i m u l a t e da n n e a l i n g ，g e n e t i ca l g o r i t h m ，a n tc o l o n ys y s t e ma n d c h a o s ，f o rt h eg o a lt oc o m p u t et h eo p t i m i z a t i o ns o l u t i o no fe n g i n e e r i n gp r o b l e m s t sh a s b e e nb e c o m i n gt h er e s e a r c hh o ti nc o m p u t a t i o n a li n t e l l i g e n c ef i e l d s ，b e c a u s eo fi t ss p e c i a l a n df l e x i b l em e m o r ym e c h a n i s ma n dr e s p e c t i v et a b uc r i t e r i at oa v o i dc i r c u i ts e a r c h i n g t h ed i s s e r t a t i o nf i r s t l yg i v e na ni n - d e p t ha n a l y s i sa b o u tt h et a b us e a r c h , a n a l y z e dt h e k e y s t o n eo ft h ea l g o r i t h ma n dt h ep i v o t a lt e c h n o l o g i e st oi m p l e m e n tt h ea l g o r i t h m , a n d c o m p a r e dw i t ho t h e re v o l u t i o na l g o r i t h m s o nt h eb a s i so f a b o v er e s e a r c h , t h ew o r ko f t h i s t h e s i si sm a i n l yp u te m p h a s i so nt h ef o l l o w i n g ： f i r s t , p a r a l l e lt sa l g o r i t h i nw a sc a r r i e do u tb a s e do nt h es e r i a lt s ，i nw h i c ht h e o p e r a t o ro fc r o s s i n go fg aw a su s e di nt h ep a r a l l e lt st oi m p r o v et h eo p t i m i z a t i o n p e r f o r m a n c eo f t h et a b us e a r c h a tt h ee a r l i e rs t a g eo f r a n n i n gt h ep a r a l l e la l g o r i t h m , e v e r y p r o c e s se x e c u t e di n d i v i d u a lt sa n de x e c u t e dt h eo p e r a t o ro fc r o s s i n gb e t w e e na i lb e s t r e s u l t so fa l lp r o c e s s e st oe 1 1 s l l r et h ea b i l i t yi ns e a r c h i n gd i s p e r s e d l yo ft h ea l g o r i t h m a t t h el a t e rs t a g e ，t h et a s k sw e r ea s s i g n e dt oe v e r yp r o c e s st h r o u g ht h en e i g h b o r d e c o m p o s i t i o np o l i c y t h e r e b y , t h ep e r f o r m a n c eo ft h ea l g o r i t h mw a si m p r o v e d i nt h e p a p e r , o p t 幽gt h ef u n c t i o n sv a l i d a t e dt h ef e a s i b i l i t ya n de f f i c i e n c yo ft h ep a r a l l e lt s a l g o r i t h m s e c o n d ，t h ep a r a l l e lt sw a su s e di nt h ef o r w a r dn e u r a ln e t w o r kt 0i m p r o v et h ea b i l i t y o fe x p r e s s i n ge x a c t l yc o m p l i c a t e do b j e c t so fn e u r a l p a r a l l e lt s 啪b eu s e dt oo p t i m i z e n e u r a ln e t w o r kt h x o u g h1 w ok i n d so f m e t h o d s ：o n ei sn e t w o r kl e a r n i n g , t h a ti su s i n gt st o o p t i m i z et h ec o n n e c t i o nw e i g h t so ft h en e u r a ln e t w o r k , t h eo t h e ri su s i n gt st oo p t i m i z e t h et o p o l o g yo ft h en e u r a ln e t w o r k t h ef i r s tm e t h o di st h em a i nr e s e a r c ho ft h e d i s s e r t a t i o n am o d e lo fn e u r a ln e t w o r kb a s e do np a r a l l e lt sw a sf o u n da n dw a st e s t e d t h r o u g hb e i n gu s e di nc l a s s i f i c a t i o no fi n t r u s i o nd e t e c t i o na n df o r e c a s t i n go fe x c h a n g e 济南大学硕士学位论文 r a t e s t h er e s u l t so ft h ee x p e r i m e n ti n d i c a t e dt h a tt h en e u r a ln e t w o r kb a s e do np a r a l l e lt s c o u l do v e r c o m et h es h o r t c o m i n g so ft h eo n e sb a s e do nb pa n dg a a tt h es a m et i m e ，i t c a no b t a i nb e t t e ra b i l i t yo f e x p r e s s i n ge x a c t l yc o m p l i c a t e do b j e c t s g e y w o r d ：p a r a l l e lt a b us e a r c ha l g o r i t h m , a r t i f i c i a ln e u r a ln e t w o r kg e n e t i ca l g o r i t h m , i n t r u s i o nd e t e c t i o n , e x c h a n g er a t e sf o r e c a s t i n g 1 1 1 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的 研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律责任由本人承担。 论文作者签名 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借鉴；本人授权济南大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名擞导师签名：卒塑逮日期：奎亟：堡：r l 济南大学硕士学位论文 第一章绪论 1 1 研究背景 优化技术是一门古老的技术，是一门以数学为基础的，用于求解各种工程问题优 化解的应用技术。自产生以来到现在，作为一个重要的科学分支，一直受到人们的广 泛重视，这是因为它在诸多工程领域得到了迅速的推广和应用，如系统控制、人工智 能、模式识别、生产调度、v l s i 技术、计算机工程等。实现生产过程的最优化，对 提高生产效率与效益、节省资源等具有重要的作用。在实际应用中，鉴于工程问题的 复杂性、约束性、非线性、多极小、建模困难等特点，传统的优化算法如线性规划、 动态规划、整数规划和分枝限界法等，己很难满足需要。因此，寻求一种适合大规模 并行且具有智能特征的算法已成为相关领域的一个主要研究目标和引人注目的研究 方向。 在众多的优化算法中，禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 以 其独特的搜索特点受到了国内外学者的广泛关注。t s 算法通过引入一个灵活的存储 结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状 态，进而保证多样化的有效探索以最终实现全局优化。迄今为止，t s 算法在组合优 化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又 在函数全局优化方面得到较多的研究，已经成为该领域的又一研究热点。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) ，亦称为神经网络 ( n e u r a ln e t w o r k s ，简称n n ) ，是近年来得到迅速发展的一个前沿课题。神经网络 由于其大规模并行处理、容错性、自组织和自适应能力和联想功能强等特点，已成为 解决很多问题的有力工具，对突破现有科学技术的瓶颈，更深入探索非线性等复杂现 象起到了重大作用，已广泛应用在许多工程领域。人工神经元是生物神经元特性及功 能的数学抽象，神经网络通常指由大量简单神经元而构成的一种计算结构，它在某种 程度上可以模拟生物神经系统的工作过程，从而具备解决实际问题的能力。 神经网络优化算法就是利用神经网络中神经元的协同并行计算能力来构造的优 化算法，它将实际问题的优化解与神经网络的稳定状态相对应，把对实际问题的优化 过程映射为神经网络系统的演化过程。 并行禁忌搜索算法及其在神经网络优化中的厦用研冤 随着科学技术的不断发展，问题搜索空间的不断扩大，面对越来越复杂的搜索空 间，传统的串行优化方法在优化效率和求解质量上都不能胜任要求。因为问题规模的 不断增大，导致单个c p u 上运行的优化算法通常需要很长的计算时间，甚至有时无法 得到满意的结果。随着高性能计算机和高性能网络设施的出现，并行处理技术得到日 益广泛的关注。而大多数优化算法由于其本身内在的并行性，所以特别适合大规模的 并行计算。 传统的神经网络模型是用著名的反向传播算法( b p 算法) 和遗传算法进行学习 的。由于b p 算法采用误差导数指导学习过程，本质上属于局部寻优算法，存在易陷 入局部最优、收敛速度慢、动态特性不够理想、学习精度与学习速度矛盾等不足。针 对这些问题，许多研究人员对传统8 p 算法进行多方面改进，取得了一定的进步，但 从本质上看，仍未脱离梯度法的局部寻优。而遗传算法存在的主要问题是对于大规模 的神经网络，搜索过程需要较长时间，另外其所使用的一些控制参数目前尚无理论上 的指导。 本文在现有成果的基础之上，对串行禁忌搜索算法、并行禁忌搜索算法进行了研 究，同时在并行禁忌搜索的基础上引入了交叉算子加以改进，并将改进后的算法应用 到神经网络优化问题中，对一些问题进行了实验，取得了满意的效果。 1 2 研究目的与主要内容 禁忌搜索算法是一种高效的全局优化算法，是对人类智力过程的一种模拟，近年 来已成功应用于各个领域。禁忌搜索算法的形式灵活多变，在函数优化问题中，不需 要目标函数的梯度向量，所有的参数都是用实数进行编码，使程序更直观、清晰，同 时也避免了编解码带来的延时：作为一种全局优化方法，t s 具有较强的爬山能力，能 根据其独有的记忆机制引导搜索程序跳出局部最优解，从而向全局最优靠近。研究表 明，禁忌搜索算法具有遗传算法相同的性能，在某些方面甚至超过遗传算法。 但是随着应用领域的拓展，问题规模的扩大，串行禁忌搜索并不能发挥效力，而 其并行算法的研究才刚起步不久，所以本课题将并行禁忌搜索算法的实现作为研究重 点，并把其应用于神经网络的优化中，在实际的应用领域上也具有很强的意义。 本课题研究的主要内容如下： l 、深入研究了串行禁忌搜索算法，给出了该算法的关键参数的设置方案，并描 2 济南大学硕士学位论文 述了算法的执行流程，对算法的发展及研究现状进行了介绍，并和其他现有算法进行 了比较。 2 、在串行禁忌搜索算法的基础上，提出了并行禁忌搜索算法。介绍了相关并行 环境，给出了并行禁忌搜索算法的分类，并深入研究了实现方案。在此基础上对并行 禁忌搜索算法作了改进，引入了遗传算法的交叉算子。通过函数优化的实例，证明的 该算法的可性行和高效性。 3 、采用并行禁忌搜索算法优化多层前馈神经网络，设计实现了基于并行禁忌搜 索算法的神经网络优化模型。 4 、针对模式分类问题和经济预测问题，用两个实例，即入侵检测数据和汇率兑 换数据对算法进行了测试，分析并行算法的时间复杂度及并行算法的加速比等。 并行禁忌搜索算法及其在神经网络优化中的应用研究 第二章串行禁忌搜索算法 2 1 引言 随着社会的不断进步，计算机科学与技术的迅速发展，现实世界中出现了大量难 以解决的优化问题。使用传统的优化技术无法满足实际工作的需求。在这种背影下， 研究人员在最近几十年提出了几种有效的智能优化算法以解决上述闯题，其中包括遗 传算法( g a ) 、模拟退火算法( s a ) 、禁忌搜索算法( t s ) 和蚁群优化算法( a c o ) 等。 其中禁忌搜索( t a b us e a r c h ，t s ) 的思想最早由g l o v e r 于1 9 8 6 年提出“”，它是 对局部领域搜索的一种扩展，是一种全局逐步寻优算法。作为一种亚启发式搜索算法， t s 已经在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大 的成功。在优化技术领域中具有重大的研究意义，本章主要介绍禁忌搜索的基本思想、 算法的关键技术、算法的发展和研究进展，并和其他算法进行了比较。 2 2 基本思想 禁忌搜索最重要的思想是标记已搜索到局部最优解的一些对象，并在进一步的迭 代搜索中尽量避开这些对象，从而保证对不同的有效搜索途径的探索。禁忌搜索涉及 到邻域( n e i g h b o r h o o d ) 、禁忌表( t a b ul i s t ) 、禁忌长度( t a b ul e n g t h ) 、候选解 ( c a n d i d a t e ) 、藐视准则( a s p i r a t i o nc r i t e r i o n ) 等概念。 简单串行禁忌搜索算法的基本思想是：给定一个当前解和一种邻域，然后在当前 解的邻域中确定若干候选解：若最佳候选解对应的目标值优于目前最好解，则忽视其 禁忌特性，用其替代当前解和目前最好解，并将相应的对象加入禁忌表，同时修改禁 忌表中各对象的任期；若不存在上述候选解，则在候选解中选择非禁忌的最佳状态为 新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌 表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。 简单串行禁忌搜索的算法步骤可描述如下： ( 1 )给定算法参数，随机产生初始解x ，置禁忌表为空。 ( 2 )判断算法终止条件是否满足? 若是，则结束算法并输出优化结果：否则， 继续以下步骤。 4 济南大学硕士学位论文 ( 3 )利用当前解x 的邻域函数产生其所有( 或若干) 邻域解，并从中确定若干 候选解。 ( 4 )对候选解判断藐视准则是否满足? 若成立，则用满足藐视准则的最佳状态 y 替代x 成为新的当前解，即x = y ，并用与y 对应的禁忌对象替换最早进入禁忌表的 禁忌对象，同时用y 替换目前最优解，然后转步骤6 ；否则，继续以下步骤。 ( 5 )判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的 最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象 元素。 ( 6 ) 转步骤( 2 ) 。 上述算法也可用如下流程框图描述，如图2 1 所示。 给定算法参数，随机产生初始解，置禁忌表为空 垂收敛准则叵= j 算法收敛准则满足= ，_ 二 、， nl 由当前解产生邻域解，确定候选解 藐视准则满足否? i 厂一ni 候选解禁忌属性判断 将非禁忌对象对应的最佳解作为 当前解，并用该对象替换最早进入 禁忌表的对象 结束搜索，输出优化结果 j 将满足藐视准则的解作 ! 一为当前解，其对应的对 l 象替换最早进入禁忌表 l 的对象，更新最优状态 图2 1 简章串行禁忌搜索算法的流程图 5 并行禁忌搜索算法及其在神经弼络优化中的应用研究 2 3 关键参数和操作 从对禁忌搜索算法的描述中我们可以看到，邻域函数、禁忌对象、禁忌表和藐视 准则，构成了禁忌搜索算法的关键。其中，邻域函数用于实现邻域搜索；禁忌表和禁 忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励， 它是对禁忌策略的一种放松。本节主要从实现技术上介绍禁忌搜索算法最基本的操作 和一些关键技术的设计原则和方法。 1 初始解 像大多数算法一样，禁忌搜索的初始解通常是随机产生的，但对一些特定问题， 也可以借助一些启发式方法产生初始解以保证一定的初始性能。 2 适配值函数 禁忌搜索的适配值函数用于对搜索状态的评价，进而结合禁忌准则和藐视准则来 选取新的当前状态。目标函数直接作为适配值函数是目前常用的方法；当然，若目标 函数的计算比较困难或耗时较多时，也可采用反映问题目标的某些特征值作为适配 值。至于选取何种特征值要视具体问题而定，但必须保证特征值的最佳性与目标函数 的最优性一致。 3 禁忌对象 禁忌对象就是被置入禁忌表中的那些变化元素，而禁忌的目的则是为了尽量避免 迂回搜索而多探索一些有效的搜索途径。归纳而言，禁忌对象的选取通常有如下三种 方法： 以状态本身或其变化作为禁忌对象。 以状态分量的变化作为禁忌对象。 以适配值或其变化作为禁忌对象。 第一种方法比后两种方法的禁忌范围要小，从而给予搜索范围要大，容易造成计 算时间的增加。但在禁忌长度和候选解集大小相同且较小的情况下，后两者也会因禁 忌范围过大而使搜索陷入局部极小。 4 禁忌长度和候选解 禁忌长度和候选解集的大小是影响t s 算法性能的两个关键参数。禁忌长度是指 禁忌对象在不考虑藐视准则情况下不允许被选取的最大次数；候选解集通常是当前状 6 济蔫大学硕士学位论文 态的邻域集的一个子集。 禁忌长度的选取与问题特性、研究者的经验有关，它决定了算法的计算复杂性。 禁忌长度的选取通常有如下几种方法： 禁忌长度固定为一个常量。 禁忌长度在一个给定的区间内，按照某种原则或公式动态变化。 给定一个禁忌长度的区间，该区间的大小可随搜索性能的变化而动态变化。 大量研究表明，禁忌长度的动态设置方式比静态方式具有更好的性能和鲁棒性。 候选解通常在当前状态的邻域中择优选取，选取过大造成较大的计算量，而选取 过小则容易造成早熟收敛。具体选取数据的多少可视问题特性和对算法的要求而定。 5 藐视准则 在禁忌搜索算法中，可能会出现候选解全部被禁忌，或者存在一个优于目前最好 状态的禁忌候选解，此时应该使某些状态解禁，以实现更高效的优化性能，这种规则 称为藐视准则或称特赦规则。藐视准则通常有如下几种方式： 基于适配值的准则。着某个禁忌候选解的适配值优于目前最优解，则解禁该候选 解为当前状态和新的最优解。 基于搜索方向的准则。若禁忌对象上次被禁时使得适配值有所改善，并且目前该 禁忌对象对应的候选解的适配值优于当前解，则对该对象解禁。 基于最小错误的准则。若候选解均被禁忌，且不存在优于目前最优解的候选解， 则对候选解中最佳的候选解进行解禁，以继续搜索。 基于影响力的准则。在搜索过程中不同对象的变化对适配值的影响有所不同，这 种影响力可作为一种属性与禁忌长度和适配值来共同构造藐视准则。 6 终止准则 常用的终止准则有如下几种： 给定最大迭代步数。 设定某个对象的最大禁忌频率。 设定适配值的偏离幅度。 以上介绍的内容为设计一个最基本禁忌搜索算法所必须的基本操作和常用设计 原则，根据不同问题作相应的修改可以构造出不同的禁忌搜索算法。 7 并行禁忌搜索算法及其在神经网络优化中的应用研究 2 4 发展及研究现状 禁忌搜索算法的提出最早是用于解决组合优化问题的。目前为止在组合优化领域 已经取得了很大的成功。如贺一等( 2 0 0 2 ) 研究了t s p 问题的禁忌搜索算法；自从 h u r i n kj 于1 9 9 4 年将禁忌搜索应用于j o b s h o p 问题后m 1 ，禁忌搜索算法在调度领 域获得了蓬勃的发展。而且调度问题至今仍是禁忌搜索算法应用最广泛而成功的一个 领域。譬如，童刚等( 2 0 0 1 ) 提出了一种改进的禁忌搜索算法，该算法利用了了h a s h 技 术和对j o b - s h o p 调度问题的解迸行编码实现了对j o b - s h o p 调度问题的解进行禁 忌，同时在算法中增加了回访功能，可对未访问到的先前产生的解的相邻解继续搜索 删；黄志等( 2 0 0 5 ) 描述了一种基于禁忌搜索技术的解决作业车间调度最短完工时阃 问题的算法叫。此外，禁忌搜索还被应用到图分区、o - 1 背包问题、时间表设计、电 力系统设计与调度，聚类问题、光学工程等领域，在此不再一一列举。迄今为止，t s 算法在组合优化、生产调度、机器学习、电路设计等领域取得了很大的成功。 然而在连续变量的函数优化问题上的贡献，t s 算法相对少于g a 、s a 等其他优化 算法。函数优化与组合优化的最大区别在于状态和邻域的表征。所以必须对简单禁忌 搜索算法作些改进以适应连续变量的函数优化这种情况。因此，鉴于t s 在组合优化 领域的迅速发展，有些学者尝试把它应用到连续优化问题的求解中，近年来这几成为 t s 的另一个发展趋势，到目前为止取得了一定的成果。h u ( 1 9 9 2 ) 是最早把禁忌搜索 算法用于连续优化问题的人之一，h u 在g l o v e r 所描述的t s 的基础上，又提出了一 个禁忌搜索与随机移动相结合的禁忌搜索算法哪! 。c v i j o v i c 和k l i n o w s h i ( 1 9 9 5 ) 在 h u 之后提出了一种新的想法，把连续空间离散化的思想，通过在其各轴向上划分， 把整个连续空间离散化成许多小的空问，称为细胞；并把各细胞看作是离散问题中的 一个可行点，运用离散问题中的t s 来求解嘲。之后p s i a r r y ，r c h e l o u a h 等在文 献”1 中提出了一个增强连续禁忌搜索算法，以使禁忌搜索适应函数优化这一情况。首 先将简单的组合t s 算法改造成一个适应连续情况的初步算法，称为连续型禁忌搜索 ( c t s ) 。后来又在些基础上，引入了集中性( i n t e n s i f i c a t i o n ) 搜索策略和多样性 ( d i v e r s i f i c a t i o n ) 搜索策略策略。前者用以扩大全局搜索范围，增大全局收敛概率； 后者用以增强在局部搜索的能力，以获得更优的解。在这之后，c h e l o u a h 和s i a r r y 在文献“”中又提出了一种禁忌搜索与n e l d e r m e a d 单纯算法相结合的全局优化算法， 利用禁忌搜索算法全局收敛的能力，结合n e l d e r - m e a d 单纯算法局部搜索性能，去改 8 济南大学硕士学位论文 善禁忌搜索算法全局搜索的性能。随后，又有文献删在c h e l o u a h 和s i a r r y 提出的 改进算法的基础上，又做出了新的改进。 从上述禁忌搜索算法的研究进展可以得出，现在人们对禁忌搜索算法的研究主要 包括下面几个方面： 1 、禁忌搜索算法的理论研究 主要包括算法的收敛性、以及为改善算法性能而进行的控制参数与搜索算子的选 择和算法操作研究等。 ( 1 ) 收敛性研究 算法的全局收敛性研究是算法理论研究的主要方面。迄今为止，禁忌搜索算法及 其相应的改进已在许多领域得到了成功的应用 6 ，7 ，8 ，9 ，1 0 。尽管许多文献通过仿真 研究来探讨参数和操作对算法性能的影响，但其理论研究还远远不完善，尤其是对收 敛性、收敛度、收敛速度的研究。g l o v e r 等对基于最近记忆和频率记忆的禁忌搜索 算法的有限收敛性进行了证明伽，并给出了其收敛边界。文献对禁忌搜索算法的收 敛性进行了研究，并对禁忌搜索算法运行的迭代次数与收敛性的关系进行了理论上的 说明。不过需要指出的是该文所证明的禁忌搜索算法的收敛并非是真正意义的禁忌搜 索算法，他借用了一个概率上的概念，就是小概率事件通常是不可能发生的，一个以 概率0 发生的事件和一个以极小概率6 发生的事件在实验设计时并无多大的区别，因 为在任一实验条件下都不可能达到理论上的完满状态，所以并不影响普遍意义下的收 敛性。王凌 5 以组合优化问题为例证明了若该类问题的解空间为有限状态集，且邻 域结构满足两个假设，即对称性和强连通性，则算法一定收敛。不过文献 5 中定理 的证明是在禁忌准则和藐视准则的抽象意义上进行的，并没有指出算法操作对性能的 具体作用，尤其没有涉及到算法效率。 ( 2 ) 算法参数的选择研究 算法参数是影响算法性能和效率的关键，如何确定最优参数使算法性能最佳本身 就是一个极其复杂的优化问题，由于参数空闯的庞大和各参数间的相关性，尚无确定 的最优参数的一般方法，目前在求解实际问题时主要凭经验选取算法参数。影响t s 性能的参数主要有禁忌表大小、邻域结构、藐视准则和禁忌准则的设置等。其中 g l o v e r 在文献“2 3 中对禁忌搜索算法的结构、参数的选择等方面进行了详细描述和讨 论。 9 并行票忌搜索算法及其在神经网络优化中的应用研究 ( 3 ) 算法操作的研究 算法操作是算法实施优化进程的关键参数，设计优良的操作对改善算法性能和提 高算法效率均有巨大作用。从搜索结构上考虑，邻域函数结构( 状态产生方式) 、状态 更新方式和收敛判据最重要。在t s 中研究得最多的是邻域结构和禁忌表结梅。如孙 元凯等( 2 0 0 1 ) 提出了一种变邻域结构的t s 算法嘲；l a rm 。h v a t t u m 等( 2 0 0 4 ) 提出了 自适应记忆的t s 算法来解决布尔优化问题汹1 ；j o z e f o w s k a 等( 2 0 0 2 h ”、p e r e z 等 ( 2 0 0 3 ) 脚1 研究了各种禁忌表结构的影响；s a l h i ( 2 0 0 2 ) 研究了禁忌表长度及藐视规则 的影响。 ( 4 ) 混合算法的研究 为提高优化性能和效率，对不同搜索策略的特点进行取长补短，近年来发展了一 些新颖的搜索机制和并行、混合搜索算法。研究表明新型的算法结构或混合算法对算 法性能和效率有较大的幅度的改善。就t s 而言，主要是与g a 和t s 的结合“”1 。一般 做法是以g a 为主，将t s 作为g a 中的一个操作算子，来改善g a 的早熟现象。也有 a c o 和t s 的结合删。 2 、应用研究概述 结合实际应用或理论问题对算法进行对比研究也是禁忌搜索算法研究中值得关 注的内容。由于禁忌搜索算法有很强的通用性，且无需问题的特殊信息，其应用领域 非常广泛。目前它在组合优化中的应用非常广泛，如调度问题、旅行商问题等经典问 题，此外，t s 还被应用到图分区、o - l 背包、时间表设计、电力系统设计、聚类问题 等等。目前正在往连续变量的函数优化嘲及神经网络矧的全局优化方面发展，现已取 得一定成效。禁忌搜索算法经过二十年的发展，已在很多领域得到成功应用，但其应 用领域远远不止这些，还有扩宽的趋势。 2 5 与其他算法的比较 禁忌搜索算法是继模拟退火算法和遗传算法之后出现的又一种十分有效的局部 搜索算法。它们和人工神经网络算法并称为四大现代启发式算法。 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是由美国m i c h i g a n 大学的j o h nh h o l l a n d 教授于1 9 7 5 年首次提出的。它是一种基于生物进化原理的全局优化算法， 它引进了生物学中的基因遗传和“自然选择，适者生存”的进化论思想，将优化问题 l o 济南大学硕士学位论文 的求解过程看成是可行解的进化过程。遗传算法的基本操作包括编码、产生初始群体、 适应值计算、选择、交叉、变异等操作。在遗传算法中，个可行解对应于一个染色 体串，多个可行解构成种群。首先对初始种群进行计算。然后根据评价函数排序，接 着执行选择、交叉、变异等基本操作，产生新的一代个体。重复以上进化过程，直至 满足终止准则。g a 最初是用于函数优化的，由于g a 具有天生的并行性，所以g a 能 够胜任任意函数优化问题，可以很快地找到搜索空间的最优区域。遗传算法发展到目 前已经成功地运用在诸多领域，但算法本身还是存在一些缺点，其中一个致命的不足 就是“早熟”。尽管g a 在搜索过程中可以存储相关的信息，但它也可能在搜索过程中 多次评估相似或相同的解，因为它们并没有任何机制来避免已经评估过的解，所以标 准g a 可能需要大量的评估次数才能找到最优解。因此对于这类需要较少评估次数的 问题，g a 并不适用。 模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) 的思想最早是由m e t r o p o l i s 等 于1 9 5 3 年提出的，1 9 8 3 年k i r k p a t r i c k 等将其用于组合优化。s a 算法是基于m e n t e c a r l o 迭代求解策略的一种随机寻优算法，其出发点是基于物理中同体物质的退火过 程与一般组合优化问题之间的相似性。由于标准的s a 算法是以迭代的方式搜索，所 以它更适合局部收敛。然而，由于它不能保留任何搜索的历史信息，同时又使用概率 地方法去选取下一个解，所以当解的质量没有改进时，相似的解可能被评估多次。此 外，s a 的收敛度依赖于初始解，如果初始解离最优解所在区域较远时，它需要很长 时间才可以找到最优值。总体来说，s a 的通用性很强，算法易于实现，但要想得到 高质量和高可靠性、初值鲁棒性好，计算时间短的效果，还需要大量的研究工作。 尽管g a ，s a 可以在组合优化和函数优化的领域中找到诸多应用，但t s 更适合非 线性连续优化问题，特别适合即时优化，因为t s 是基于邻域搜索，同时利用记忆的 历史信息可以很容易地跳出局部最优解，从而达到全局最优。因此许多研究人员都在 尝试改进各种不同的t s 以解决连续优化问题。 虽然禁忌搜索算法较之其他算法具有一定的优势，但任何算法都不是万能的，禁 忌搜索也有一个弱点，就是对初始解有较强的依赖性。为了解决这个问题，同时适应 大规模问题的求解，本文在第三章介绍了并行禁忌搜索算法，可以很好的解决串行禁 忌搜索算法对初始解的依赖性。 并行禁忌搜索算法及其在神经网络优化中的应用研究 第三章并行禁忌搜索算法及改进 上一章，我们详细介绍了串行禁忌搜索算法的基本思想和关键技术，并给出了算 法的流程图。近年来，禁忌搜索算法在许多领域得到了广泛而成功的应用。虽然禁忌 搜索引入了记忆功能，可以在搜索过程中接受劣解，具有较强的爬山能力，但也有明 显的不足：即对初始解有较强的依赖性，同时它迭代的搜索过程是串行的，仅是单一 状态的移动，而非并行搜索。这两点导致不能很好的发挥禁忌搜索的性能。不过随着 并行计算技术和并行计算机的发展，为满足求解大规模问题的需要，禁忌搜索算法的 并行实旌也得到了研究和发展。通过对串行禁忌搜索算法的并行化，我们可以解决串 行算法中的明显的不足之处。下面，首先介绍一下并行禁忌搜索算法的分类。 3 1 并行禁忌搜索的分类 随着禁忌搜索算法在许多领域地成功运用，越来越多的研究者开始关注如何在串 行禁忌搜索算法的基础上使用并行技术以满足大规模、实时性问题的需要。根据对算 法初始化、参数设置、通讯策略等环节实施不同的并行化方案，可以构造出不同类型 的并行禁忌搜索算法。目前比较认可的一种分类方法是由1 提出。它是基于以下三个 方面进行分类：用于搜索的进程数目、并行t s 间的通信策略及搜索空间的化分方法。 如图3 1 所示。 参数( 初值、禁忌表长度、候选解个数 等) 设置可相同或不同 图3 - 1 并行禁忌搜索算法的分类 1 基于空间分解的并行策略 ( 1 ) 搜索空间的分解策略。即通过搜索空间分解将原问题分解为若干子问题，各 济南大学硕士学位论文 子问题用不同的禁忌搜索算法进行求解，从而实现并行化。 ( 2 ) 邻域的分解策略。即每一代中用多种方法对邻域分解所得的各子集进行评 价，从而实现对最佳邻域解的搜索的并行化。 显然，这类基于空间分解的并行策略在实施时对同步的要求很高。 2 基于多禁忌搜索任务的并行策略 这类并行策略中包含多个禁忌搜索算法在运行，而各算法可以使用相同或不同的 算法参数( 如初值、禁忌表长度、候选解个数等) 。同时，各任务可以以不存在通讯 的独立方式运行，也可以以协作的方式运行。在多处理机情况下，鉴于各任务的数量 和定位相对并行机的负荷状态，如静态或动态，又可以将并行禁忌搜索分为非自适应 方式、半自适应方式和自适应方式。 3 2 并行禁忌搜索算法 本文介绍的并行禁忌搜索算法采用主从式( m a s t e r - s l a v e ) 编程模式和s p m d 编程 模式相结合的方法，采用基于多禁忌搜索任务的并行策略。在任务的分配阶段采用 m a s t e r - s l a v e 模式，根据求解问题的规模，主进程的主要工作是将求解问题分成若干 个子问题，申请和释放处理机，加载节点程序；执行f o 和处理用户界面；发送数据 给各个从进程，并收集各个从进程的计算结果。从进程的主要工作是所接受来自主进 程的输入信息；完成各自的局部计算，实施从进程间的通信；回送结果给主进程。各 个从进程的计算阶段采用s p m d 编程模式，各个从进程运行相同的代码段，但操作的 数据却不相同。主要完成串行禁忌搜索的任务并在后期根据并行策略的改变而计算任 务。 首先进行相应的数据结构的初始化，然后由主进程按并行机的空闲结点数启动相 应个数的从进程，并为每个从迸程发送初始信息，从进程根据接收到的相关信息开始 并行计算各自的任务。按多禁忌搜索任务的并行策略，每个从进程运行一个串行禁忌 搜索程序，多个从进程之间不进行通信，且从不同的初始点出发进行搜索，在达到算 法指定的迭代次数的时候，将每个从进程计算得到的当前最好解返回到主进程，主进 程通过比较各个从进程的最优解确定全局最优解，最后由主进程结束整个算法。迭代 的终止条件根据具体问题进行设定。 并行禁忌搜索算法及其在神经网络优化中的应用研究 图3 - 2 并行禁忌搜索算法基本流程图 具体的执行过程可描述如下； ( 1 ) 主进程初始化相关数据结构，并按启动的进程数随机产生相应于进程个数的 初始解。 ( 2 ) 主进程传递相关参数到各从进程。 ( 3 ) 从进程根据接收到的相关参数及初始解后，开始按串行禁忌搜索算法的步 骤执行搜索，直到满足给定的迭代次数。 ( 4 ) 各从进程把当前搜索到的最好解传送到主进程，整个算法结束，输出最终 1 4 济南大学硕士学位论文 结果。 图3 2 描述的是并行禁忌搜索算法的基本流程图。 3 3 并行禁忌搜索算法的改进 魉着禁忌搜索算法的提出及推广，其在组合优化、生产调度、机器学习、电路设 计和神经网络等领域取得了很大的成功，近年来在函数全局优化方面得到了较多的研 究，并有了很大的发展。但任何一种算法都不可能是万能的，都有其自身的不足之处。 禁忌搜索算法的不足主要表现在对初始解有较强的依赖性，好的初始解可使禁忌 搜索算法在解空间中搜索到好的解，而较差的初始解则会降低禁忌搜索算法的收敛速 度；另一个不足是禁忌搜索在搜索过程中只有一个初始解，在每代也只是从一个解移 动到另一个解，搜索范围较小。所以考虑和其他算法作结合来改善其不足，就成了一 个研究燕点。其中遗传算法就是一个比较适合混合的算法。将它们二者结合起来，互 相取长补短，构造更加高效的混合算法，就成了人们研究的一个新方向。 禁忌搜索算法的创始人g l o v e r y i 寸混合遗传算法与禁忌搜索算法的必要性和可行 性进行了理论上的分析和论述 2 ”，被公认为是混合遗传算法与禁忌搜索算法的理论 基础。基于这一理论基础，目前在这方面已经有了一定的研究并应用在了一定的领域， 如文献0 6 j 7 , 1 8 , 1 9 捌。在这类混合算法中，大多以g a 为主，将t s 作为g a 中的一个操作 算子，利用t s “爬山”能力强的优点，进行局部搜索，而g a 作全局搜索，取得了很 好的效果。 不过，上述研究内容基本上是基于串行算法的结合，本文提出的改进方法是以并 行禁忌搜索算法为主，将遗传算法中的交叉算子操作应用到并行禁忌搜索中，以处理 并行运行的多个基本禁忌搜索算法之间的信息交换，来提高整个算法的性能。 3 3 1 交叉算子 在遗传算法中，交叉算子因其全局搜索能力而作为主要算子。交叉是指对两个父 代个体的部分结构进行重组而生成新个体的操作。交叉算子的设计应与编码设计协调 进行，使之满足交叉算子的评估准则，即交叉算子需保证前一代中优秀个体的性状能 在下一代的新个体中尽可能得到遗传和继承。 遗传算法最常用的编码方法是二进制编码和浮点数编码。其中二进制编码的最简 并行禁忌搜索算法及其在神经网络优化中的应用研咒 单形式可操作如下：在个体串中随机设定一个交叉点，实行交叉时，对两个配对个体 在该点前后的部分结构进行互换，生成两个新个体。 下面给出一个单点交叉的例子： 个体a0 0 1 l | 1 1 0 0 0 0 0