（计算机软件与理论专业论文）分支定界算法的分布并行化研究.pdfVIP

摘要 摘要 分支定界算法是求解优化问题的重要方法。虽然它有很高的计算精度，但是， 高的计算时间复杂度，降低了它的实际应用价值。本文设计实现的一种专用于计 算分支定界算法的机群计算平台，能减少分支定界算法的计算时间复杂度，提高分 支定界算法的效率。 本论文在深入分析其它各种启发式算法和分布式并行计算的基础上，针对上 述平台，就如何减少分支定界算法的时间复杂度问题作了创新性和探索性研究。 主要内容为： 1 详细研究了分支定界算法，提出并实现了一种新的分布并行加速机制可以把 计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值，实时地广播 给所有其它并行的计算机，作为它们的新最佳本分值，来实现分支节点的快速并 行淘汰。 2 详细研究了几种主要的启发式算法，并使用启发式算法修改了分支定界算 法，在保证计算精度的前提下，提高了分支节点的淘汰效率。 3 详细研究了几种并行计算算法，并通过分布并行减小了组合优化问题的规 模。 4 本文选用旅行商( t s p ) 问题实例作为测试基准。计算表明，在保证求得最 优解的前提下，该平台能很好地提高分支定界算法的效率。 关键词：分支定界算法；分布平行计算；启发式算法；旅行商问题( t s p ) a b s t r a c t a b s t r a c t b r a n c ha n db o u n da l g o r i t h mi sa ni m p o r t a n tm e t h o dt ob eu s e dt oa c q u i r et h e s o l u t i o no fo p t i m a lp r o b l e m s b u ti tn e e d st o om u c ht i m ef o rg e t t i n gt h eo p t i m a l s o l u t i o n ，w h i c he x t r e m e l yl i m i t si t s r o l eo fp r a c t i c a la p p l i c a t i o n i nt h i st h e s i s ，t h e d e s i g na n dr e a l i z a t i o no fas p e c i a l c l u s t e ra r ep r e s e n t e df o rc a l c u l a t i n gb r a n c ha n d b o u n da l g o r i t h mt h a tc a nd e c r e a s et h ec a l c u l a t i n gt i m ea n de n h a n c et h ea l g o r i t h m i c e f f i c i e n c y b a s e so i la n a l y z i n gt h ed i s t r i b u t e dp a r a l l e lc o m p u t i n ga n do t h e rh e u r i s t i ca l g o r i t h m s ， t h et h e s i sf o c u s e so nh o wt od e c r e a s et h et i m ec o m p l e x i t yo fb r a n da n db o u n da l g o r i t h m i nt h es p e c i a lc l u s t e rm e n t i o n e da b o v e t h ec o n t e n t so ft h e s i sa r ea sf 0 1 l o w s ： 1 p r o p o s i n ga n e wa c c e l e r a t e dm e c h a n i s mf o rd i s t r i b u t e dp a r a l l e lc o m p u t i n g w h i c hc a nb r o a d c a s tt h ep r e s e n to p t i m a lv a l u et h a ti sc a l c u l a t e db ya n yc o m p u t e ri nt h e c l u s t e rt oo t h e r si m m e d i a t e l y 2 p r e s e n t i n ga m o d i f i e db r a n c ha n db o u n da l g o r i t h mb ya d d i n gt h eh e u r i s t i c a l g o r i t h mi nt h ed u s t e rw h i c hi n c r e a s i n gt h ee f f i c i e n c yo fe l i m i n a t i n gn o d e 3 t h ep r o b l e m ss c a l ei sd e c r e a s e dt h r o u g hu s i n gd i s t r i b u t e dp a r a l l e lc o m p u t i n g a l g o r i t h m 4 t h et s pa sb e n c h m a r ks h o w st h a tt h i sd u p e rp l a t f o r mc a ni n c r e a s et h eb r a n c h a n db o u n da l g o r i t h m se f f i c i e n c ya n dg e tt h eo p t i m a ls o l u t i o ns o o n k e yw o r d ：b r a n c ha n db o u n d ；d i s t r i b u t e dp a r a l l e l c o m p u t i n g ；h e u r i s t i c a l g o r i t h m ；t r a v e l i n gs a l e s m a np r o b l e m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 毒一j 哦 日期：2 0 0 # 年舌月2 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：珈0 6 年月2 日 第一章绪论 第一章绪论 在计算机学科中，存在多项式阶的时间复杂度的一类问题，称之为p 类问题； 而像梵塔问题、推销员旅行问题、( 命题表达式) 可满足问题等这类问题，人们目 前已设计的实现它们的算法其时间复杂度为指数阶的，至今没有找到多项式阶的 时间复杂度的算法或没有多项式阶的时间复杂度的算法，但可以在多项式时间内 验证一个解是否正确的的这一类问题，称之为n p 类问题。n p 是n o n d e t e r m i n i s t i c p o l y n o m i a l 的缩写，即非确定的多项式的意思。 1 。1 n p h a r d 问题 在n p 类问题中，库克( s c o o k ，1 9 7 1 ) 提出了一个“n p 完全性问题” ( n p c o m p l e t e ，简记为n p c 问题) ，是n p 问题的一个子类，它的意义是，如果n p c 问题可用多项式时间算法求解，则所有的n p 问题都可用多项式时间算法求解，采 用符号即：如果n p c = p ，则n p = p 。n p h a r d 问题是指这类难解的n p c 问题。 对于n p h a r d 问题，目前已设计的实现它们的算法其时间复杂度为指数阶的， 还没有找到或没有多项式阶的时间复杂度的算法，或者只找到时间复杂度为多项 式阶的近似算法。 1 2 求解n p h a r d 问题的方法 近年来，求解n p h a r d 问题的研究十分活跃。人们提出了许多用以解决复杂优 化问题的新方法，如模拟退火算法“、遗传算法”j 、蚁群算法“3 等新型启发式搜索 算法。这些新型启发式搜索算法能够在较短的时间内计算出n p h a r d 问题的“次 优解”，但由于受到算法自身的限制，它们通常只能求出问题的“次优解”，而 非“最优解”。因此这些新型启发式算法都是求解组合优化问题的近似算法。 12 1 模拟退火算法 1 2 1 1 模拟退火算法的概述 模拟退火( s i m u l a t e da n n e a li n g ，简称s a ) 算法是基于蒙特卡罗( m o n t ec a r l o ) l 电子科技大学硕士学位论文 迭代求解法的一种启发式随机搜索算法。算法思想最早在1 9 5 3 年由n m e t r o p o l i s 等人提出的，但是把它用于组合优化和v l s i 设计却是在1 9 8 3 年由s k i r k p a t r i c k 等人和v c e m y 分别提出来的。算法将组合优化问题和统计力学中的热平衡问题类 比，另辟了组合优化问题的新途径。其出发点是物理学中的退火过程，即在对固 体物质进行退火处理时，通常是先将它加温，使其粒子可自由运动，然后降温， 粒子逐渐形成低能态的晶体，若在凝结点附近温度下降得足够慢，则固体物质一 定会形成最低能量的基态。 退火的概念最初是人们为了研究组合优化问题而提出的，算法用于解决组合 优化问题则是基于物理中固体物质的退火过程与一般组合优化问题之间的相似 性。通过设定一个初始温度和一个初始状态，伴随温度的不断下降，结合概率突 跳特性在解空间中使用邻域函数进行随机搜索，最终得到全局最优解。模拟退火 算法是一种通用的优化算法，目前已在工程中得到了广泛的应用，诸如v l s i 、生 产调度、控制工程、机器学习、神经网络、图象处理等领域。 1 2 1 2 模拟退火算法的基本原理 模拟退火算法的基本思想是从一个给定解开始，从邻域中随机产生另一个解， 接受m e t r o p o i s 准则允许目标函数在有限范围内变坏，它由一个控制参数t 决定， 其作用类似于物理过程中的温度，对于控制参数的每一个取值，算法持续进行“产 生一判断一接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡 的过程。经过大量的解变换后，可以求得给定控制参数t 值时优化问题的相对最 优解。然后减小控制参数t 的值，重复执行上述迭代过程，当控制参数逐渐减少 并趋于0 时，系统亦越来越趋于平衡状态，最后的系统状态对应于优化问题的全 局最优解，该过程也称为冷却过程。由于固体退火必须缓慢降温，才能使得固体 在每一个温度下都达到热平衡，最终趋于平衡状态。因此，控制参数t 经缓慢衰 减，才能确保模拟退火算法最终优化问题的整体“最优解”。 模拟退火算法具体步骤如下“1 ： ( 1 ) 给定模型每一个参数变化范围，在这个范围内随机选择一个初始模型弛， 并计算相应的目标函数值e ( m 。) 。 ( 2 ) 对当前模型进行扰动产生一个新模型m ，计算相应的目标函数值e ( m ) ，得 到 e = e ( m ) 一e ( i i 】d )( 1 ) ( 3 ) 若e o ，则新模型m 按概率p = e x p ( 一e t ) 2 第一章绪论 进行接受，t 为温度。当模型被接受时，置j i l 。= r n ，e ( m 。) = e ( m ) 。 ( 4 ) 在温度t 下，重复一定次数的扰动和接收过程，即重复步骤( 2 ) 、( 3 ) 。 ( 5 ) 缓慢降低温度t 。 ( 6 ) 重复步骤( 2 ) 、( 5 ) ，直至收敛条件满足为止。 s a 算法实质上分两次循环，第一次循环是随机扰动产生新模型并计算目标函 数( 或称能量) 的变化；第二次是循环温度( t ) 的变化，决定新模型是否被接受。 由于算法初温设计在高温条件，这使得e 增大的模型可能被接受，因而能舍去局 部极小值，通过缓慢地降低温度，算法最终能收敛到全局最优点。 1 2 1 3 模拟退火算法的优点和缺点 从上述步骤可看出模拟退火算法依据m e t r o p o l is 准则接受新解，通过温度更 新函数的退温过程进行趋化式搜索并最终进入全局最优解集。模拟退火算法可以 用马尔柯夫链的遍历理论来给它以数学上的描述。在搜索最优解的过程中，模拟 退火算法除了可以接受优化解外，还用一个随机接受准则( m e t r o p o l i s 准则) 有限 度地接受恶化解( i l l c o n d i t i o n e d ) ，并且接受恶化解的概率慢慢趋向于零。即 算法不但往好的方向走也可向差的方向走，使得算法执行过程中即便落入局部最 优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。1 。这 是模拟退火算法的最大特点也是模拟退火算法的最大优点。 但是我们同时可以看出由于模拟退火算法的主要缺点是解的质量与求解时间 之间的矛盾。这是因为模拟退火算法对整个搜索空间的状况了解不多，不便于使 搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。为 此，许多学者提出了各种改进方法，如改进状态产生函数，改进固定的退温策略 和改进状态接受函数，将算法的寻优过程由串行转化为并行等。同时模拟退火算 法为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免 地增大时，缺乏可行的解决途径。 因此模拟退火算法的不足之处主要是：尽管理论上只要计算时间足够长，模 拟退火法就可以保证以概率1 0 收敛于全局最优点，但是在实际算法的实现过程 中，由于计算速度和时间的限制，在优化效果和计算时间之间存在矛盾。模拟退 火算法容易掉进局部最优的陷阱中，所以模拟退火算法不能保证计算结果为全局 最优解( 即最佳本分值) 。 电子科技大学硕士学位论文 1 2 2 遗传算法 1 2 2 1 遗传算法的概述 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟自然界生物进化机制的一种算法， 即遵循适者生存、优胜劣汰的法则，也就是寻优过程中有用的保留，无用的则去 除。在科学和生产实践中表现为，在所有可能的解决方法中找出最符合该问题所 要求的条件的解决方法，即找出一个最优解。这种算法是1 9 6 0 年由h o l l a n d 提出 来的，其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的软 件系统。它的特点是对参数进行编码运算，不需要有关体系的任何先验知识，沿 多种路线进行平行搜索，尽量不落入局部较优的陷阱，能在许多局部较优中找到 全局最优点，是一种全局最优化方法。近年来，遗传算法已被成功地应用于工业 设计、经济管理、交通运输等不同领域，解决了许多问题，例如：可靠性优化、 流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖 掘等方面。 1 2 2 2 遗传算法的基本原理 遗传算法。3 的基本思想是在自然界中，由于组成生物群体中各个体之间的差 异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适 者生存、优胜劣汰，将要淘汰那些最差个体，通过交配将父本优秀的染色体和基 因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它 们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强 的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化。 遗传算法是真实模拟自然界生物进化机制进行寻优的。在此算法中，被研究的体 系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体， 个体用多维向量或矩阵来描述。组成矩阵和向量的参数相应于生物种组成染色体 的基因，染色体用固定长度的二进制串表述，通过交配、突变等遗传操作，在参 数的一定范围内进行随机搜索，不断改善数据结构，构造出不同的向量。相当于 得到了被研究的不同的解，目标函数值较优的点被保留，目标函数值较差的点被 淘汰。因此遗传操作可以越过位垒，能跳出局部较优点，到达全局最优点。 遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解，这组解最初是 随机生成的。在每次迭代时又有一组新的解由模拟进化和继承的遗传操作生成， 每个解都有一目标函数给与评判，一次迭代成为一代。典型的算法步骤有”1 ： 4 第一章绪论 ( 1 ) 使用二进制编码对搜索空间进行编码。 ( 2 ) 随机产生包含n 个个体的初始群体。 ( 3 ) 适应度评判检测个体适应度( 个体适应度反映了个体好坏的情况) 。 ( 4 ) 用赌轮选择方法选出若干个体进行繁殖，个体可以重复。 ( 5 ) 随机配对，按一定概率( 交叉概率) 进行一点交叉操作，并生成两个子个 体。 ( 6 ) 按照一定概率( 变异概率) 变异二进制个体串中某个( 些) 位。 ( 7 ) 适应度评判检测个体适应度。 ( 8 ) 未满足迭代终止条件( 评判条件) 则循环( 4 ) ，( 5 ) ，( 6 ) ，( 7 ) ：满足迭代终 止条件则退出。 基本的遗传算法框图如图卜l 所示，其中变量g e n 是当前代数。它按不依赖 于问题本身的方式作用在特征串群体上，算法仅用到与搜索空间中检查过的点相 联系的适应值。不管求解问题本身，通过执行同样的、惊人简单的复制、杂交和 偶尔的变异操作来完成它的搜索。在实际应用中，遗传算法能够快速有效地搜索 复杂、高度非线性和多维空间，出人意外的是它并不知道问题本身的任何信息， 也不了解适应值度量。遗传算法成功的关键在于符号串表示和遗传操作的设计。 图卜1 遗传算法框架图 5 电子科技大学硕士学位论文 1 2 2 3 遗传算法的优点与缺点 遗传算法的优点是9 ： ( 1 ) 遗传算法不是直接处理问题的设计变量本身，而是设计变量的编码，提高 了算法的通用性； ( 2 ) 遗传算法的搜索过程是从一个初始群体开始，而不是从单个的个体开始 的，具有隐含并行搜索特性，从而大大减少了陷入局部最优的可能； ( 3 ) 遗传算法使用的遗传操作均是随机操作，同时它根据个体的适配信息进行 搜索，无需其他如导数信息等，因此具有广泛的适应性； ( 4 ) 遗传算法具有全局搜索能力，具有很强、很高的计算效率，善于解决如组 合优化这样的复杂问题； ( 5 ) 遗传算法通过适当的遗传操作使同代或前后代群体问相互作用，保持已经 搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。 遗传算法的缺点是：遗传算法本身构造所带来的局限性在组合优化问题求解 过程中表现得尤为突出。其中最为严重的是“过早收敛”问题。所谓“过早收敛” 是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷 入局部最优解，达不到“全局最优解”的现象。这就体现了遗传算法的局部搜索 能力较差，遗传算法比较费时。遗传算法的另一个缺点是“g a 欺骗”问题，即在 g a 的搜索过程中，有可能搜索到最优解然后又将其发散出去的现象。此外，遗传 算法有多种编码方案，如位串编码、实数编码、有序串编码等，但在解决组合优 化问题时如果不根据问题具体知识的特点来确定编码方案，容易产生“致死染色 体”。组合优化问题都有各种不同的约束条件，这就要求得到的可行解必须满足 某种条件，而用传统遗传算子如交叉、变异所得的个体可能不再是该问题的可行 解。 因此遗传算法局部搜索能力差，且不能保证计算结果为全局最优解( 即最佳本 分值) 。 1 2 3 蚁群算法 1 2 3 1 蚁群算法概述 蚁群算法是在2 0 世纪5 0 年代中期以来，人们从生物进化的机理中受到启发， 提出了许多用以解决复杂优化问题的新方法之一。蚁群算法( a n tc o l o n y a l g o r i t h m ) 有分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优 6 第一章绪论 解等优点。 蚁群算法是一种源于大自然生物世界的新型仿生类算法，是于2 0 世纪9 0 年 代初由意大利学者d o r i g o 和m a n i e z z o 等首先提出，在一系列复杂困难的系统优 化问题求解中取得了成效，显示出该算法在求解复杂优化问题特别是离散优化问 题方面的一些优越性。蚁群算法特别适合于在离散优化问题的解空间进行多点非 确定性搜索，已经先后被应用到t s p 问题、二次分配问题、工件调度问题、图着 色问题等多个经典组合优化问题，取得了很好的效果。 1 2 3 ，2 蚁群算法的基本原理 蚁群算法是模仿真实世界蚁群的行为而提出的。真实的蚂蚁在没有视觉的情 况下，能够找到从食物源到蚁巢的最短路径；同时，它们能适应环境的改变，当 原先最短的路径上出现障碍物时，能够再发现一条新的最短路径。其原理“”1 在 于：蚂蚁在所经过的路径上留下一种挥发性分泌物( p h e r o m o n e ，以下称为信息 素) ，信息素随着时间的推移会逐渐挥发消失。蚂蚁在运动过程中，不但能够在 它所经过的路径上留下该物质，还能够感知这种物质的存在及其强度，并以此来 指导自己的运动方向，倾向于朝着这种物质强度高的方向移动，即选择该路径的 概率与当时这条路径上该物质( 信息素) 的强度成正比。信息素强度越高的路径， 选择它的蚂蚁就越多，则在该路径上留下的信息素的强度就更大，而强度大的信 息素又吸引更多的蚂蚁，从而形成一种正反馈作用。通过这种正反馈，蚂蚁最终 可以发现最佳路径，导致大部分的蚂蚁都会走此路径。从而达到搜索食物的目的。 基本蚁群算法的原理，如图卜2 所示。 图卜2 中，设a 是蚁巢，f 是食物源。1 6 只蚂蚁从a 去往f ，同时1 6 只蚂蚁 从f 返回a 。假定：( a ) 时间t 是离散的；( b ) 在每1 个时间单位内，1 只蚂蚁运动 l 单位距离，运动后释放l 单位的信息素；( c ) t ：o 时，在任何路径上都没有信息 素：( d ) 蚂蚁在b 或d 点，以相同的概率选择下一路径。由此可得： t = l 时，有1 6 只蚂蚁在b ，1 6 只蚂蚁在d it = 2 时，有8 只蚂蚁在d ，8 只蚂 蚁在b ，1 6 只蚂蚁在e 。此时，每条路径上信息素浓度的分布为f 。- 1 6 ， f 。= 1 6 ， f 萨8 ，f 。= 8 ，f 萨1 6 ，f 矿1 6 ，且b c d 路径上的信息量是b e d 路径上的2 倍因 此，随着时间的推移，蚂蚁就会以越来越大的概率选择b c d 路径，直到最终选择 b c d 路径，实现寻优过程。 电子科技大学硕士学位论文 f i l d = 1 i d d = ! d = 0 5 e c 、 d = 卜 d ：0 5 b i d = 1 i a 图1 2 蚁群算法的基本原理 由上可知，蚁群算法中存在着几个重要的算法策略：选择策略。信息素浓 度越大的路径，被选择的概率越大；更新策略。路径上面的信息素浓度会随蚂 蚁的经过而增长，而且同时也随时间的推移逐渐减小：协同策略。蚂蚁之间实 际上是通过信息素浓度来达到间接的互相通讯、协同工作。这样的策略使得蚁群 算法在初始解的基础上经过一段时间后能够发现其中的最优解。 1 2 3 3 蚁群算法的优点与缺点 蚁群算法具有很强的发现较好解的能力，因为该算法不仅利用了正反馈原理 而且是一种本质并行的算法，不同个体之间不断进行信息交流和传递，从而能够 相互协作。蚁群算法可求解传统方法难以解决的非凸、非线性非连续的优化问题。 蚁群算法的主要优点是： 1 ) 正反馈性。通过不断强化最优解的信息素，加快算法的收敛速度。 2 ) 较强的鲁棒性。对基本蚁群算法模型稍加修改，便可以应用于其他问题。 3 ) 分布式计算。蚁群算法是一种基于种群的进化算法，具有本质并行性， 易于并行实现。 4 ) 易与其他方法结合。蚁群算法很容易与多种启发式算法结合，以改善算 法的性能。 蚁群算法的主要缺点是：首先，蚁群算法限于局部最优解。从算法解的性质 而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。 8 第一章绪论 其次，工作过程的中间停滞问题。和算法开始时收敛速度快一样，在算法工作过 程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近发 生停滞。较长的搜索时间。尽管和其他算法相比，蚁群算法在迭代次数和解的质 量上都有一定的优势，但对于目前解决问题的实际情况，还是需要较长的搜索时 间。虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一 问题，但是对于大规模复杂的问题，这还是一个很大的障碍。 因此蚁群算法容易限于局部最优解，不能保证计算结果为全局最优解( 即最佳 本分值) 。 1 24 混合算法简介 1 2 4 1 混合遗传算法与模拟退火算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 因其高度的并行处理能力、强鲁棒性和 全局搜索能力而被广泛地应用于诸多领域。理论上遗传算法依“概率l ”收敛于问 题的最优解，然而实践应用中，遗传算法会表现出早熟现象( 过早收敛) 、局部 寻优能力较差等不足。所以常规的遗传算法并不一定是针对某一问题的最佳求解 方法。 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 具有较强的局部寻优能力，并能使搜索 过程避免陷入局部最优解，但把握整个搜索过程的能力不够，不便于使搜索过程 进入最有希望的搜索区域，从而使得模拟退火的运算效率不高。 混合遗传模拟退火算法的基本思想是将遗传算法与模拟退火算法相结合而构 成的一种优化算法。与基本遗传算法的总体运行过程相类似，遗传模拟退火算法 也是从一组随机产生的初始解( 初始群体) 开始全局最优解的搜索过程，它先通过 选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的 各个个体进行模拟退火过程，以其结果作为下一代群体中的个体。这个运行过程 反复迭代地进行，直到满足某个终止条件为止。遗传模拟退火算法将遗传算法和 模拟退火算法的优点充分结合起来，提高了算法的效率”1 。 1 2 4 2 混合遗传算法与蚁群算法 遗传算法搜索使用目标函数启发，算法的求解速度快，但对系统中反馈信息 利用不够，求精确解效率低：而蚁群优化算法具有正反馈性、求精解效率高的特 点，但由于初期信息素匮乏，求解速度慢，因此将两者相结合，能够实现优势互 补。 9 电子科技大学硕士学位论文 遗传算法和蚁群算法结合的方式有很多种比如：将简单遗传算法( s i m p l e g e n e t i ca l g o r i t h m ，s g a ) 和最大最小蚂蚁( m a x m i na n ts y s t e m ) 算法相结合提 出了g a a a 算法。将简单遗传算法和改进的合作蚁群优化( c o o p e r a t i v ea n tc o l o n y o p t i m i z a t i o n ，c a c o ) 算法结合作为两层嵌套的循环，外层循环采用简单遗传算法 将任务分配给主体，内层循环采用c a c o 算法获取优化分配方案。将简单遗传算法 和蚂蚁网( a n t n e t ) 算法相结合，提出遗传蚂蚁路径算法( g e n e t i ca n tr o u t i n g a 1 9 0 r i t h m ，g a r a ) 等1 。 1 3 国内外发展趋势 1 31 模拟退火算法 模拟退火算法关键参数主要有状态产生函数、状态接受函数、初温、温度更 新函数等。改进算法主要就是调试、改进算法中某一部分函数，使其更接近自然 现象，现大致归纳为三个方面： ( 1 ) 改进状态产生函数 ( 2 ) 改进状态接受函数 ( 3 ) 改进温度更新函数 近年来，模拟退火算法同其它算法混合的主要模型和算法有： a 基于退火策略的混沌抻经网络络( a c n n ) 模型“” h n n 中引入混沌机制形成混沌动态，利用其遍历性在解空间中“随机”粗搜索， 再由退火策略控制混沌动态逐渐消失并产生逆分岔，一旦逆分岔过程结束便转入 h n n 极度优化。 b 混合遗传模拟退火m g a s a 算法”1 混合遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优 化算法。与基本遗传算法的总体运行过程相类似，遗传模拟退火算法也是从一组 随机产生的初始解( 初始群体) 开始全局最优解的搜索过程，它先通过选择、交叉、 变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的各个个体进行 模拟退火过程，以其结果作为下一代群体中的个体。这个运行过程反复迭代地进 行，直到满足某个终止条件为止。 i 0 第一章绪论 1 3 2 遗传算法 近年来，遗传算法已经在国际上许多领域得到了应用。1 9 8 5 年召开了第l 届 有关遗传算法的国际会议，第1 部关于这方面的专著在1 9 8 9 年问世。遗传算法是 一种有广泛应用前景的算法，但是它的研究和应用在国内尚处于起步阶段“。 a a g a 适应遗传算法 a g a 适应遗传算法的主要思想是交叉概率p c 和变异概率p m ，能够随适应度自 动改变。 b g a a a ( g e n e t i ca l g o r i t h m a n ta g o r j t h m ) 算法 g a m 算法结合了遗传算法和蚁群算法的优点，在时间效率上优于蚁群算法， 在求精解效率上优于遗传算法。它的思路是在算法的前过程采用遗传算法，充分 利用遗传算法的快速性、随机性和全局收敛性，产生有关问题的初始信息分布； 在算法的后过程采用蚁群算法，在有一定初始信息分布的情况下，充分利用蚁群 算法的并行性、正反馈性和求精解效率高等特点。 c a s g a ( a n ts y s t e mw i t hg e n e t i ca l g o r i t h m ) 算法 a s g a 算法也是将遗传算法和蚁群算法相结合，它通过控制参数的自适应调整 对原算法进行改进，使用了一系列用于解决问题的蚂蚁代理( a g e n t ) 。 1 3 3 蚁群算法 蚁群算法具有广阔的研究空间，己引起众多研究者的广泛兴趣和关注，通过 每2 年一届的a n t s 国际学术会议可见一斑。从1 9 9 8 年开始至今，在比利时的布 鲁塞尔己举行了3 届a n t s 国际学术会议。目前在理论方面，研究者们正在努力扩 展现有理论成果的范围，确定一个完整的理论框架，例如在确定算法的参数值、 证明算法的收敛性等方面进行研究；在实践方面，大多数研究着重于扩展蚁群算 法所能解决问题的范围，从而解决连续优化、动态优化等一些现实问题“。 针对蚁群算法的：收敛速度慢，计算时间长，易于过早地陷入局部最优，在 求解连续优化问题上相对较弱等缺点，目前已有了一些改进后的蚁群算法： a 连续优化问题的蚁群算法 该算法的思路为：( a ) 根据问题的性质估计最优解的范围，以及各个变量的取 值范围z 。s z ，s x 。( j = z 2 ，z ，n ) ；( b ) 在变量区域内打网格，每个空间的网格点 各对应一神状态，人工蚂蚁在各个空间网格点之间移动，根据各网格点的目标函 电子科技大学硕士学位论文 数值，留下不同的信息量，以此影响下一批人工蚂蚁的移动方向：( c ) 循环一段时 间后，目标函数值小的网格点信息量会比较大，根据信息量，找出信息量大的空 间网格点，缩小变量范围，在此点附近进行人工蚁群移动；( d ) 重复前述过程，直 到网格的间距小于预先给定的精度，算法终止。 b 具有变异特征的蚁群算法 该算法的思想是在基本蚁群算法中引入变异机制，采用逆转变异方式，变异 的次数是随机的，以此增大进化时所需的信息量。这种机制充分利用了2 一交换法 简洁高效的特点，从而克服了基本蚁群算法计算时间较长的缺陷。 c 自适应蚁群算法 该算法为了提高基本蚁群算法的全局搜索能力和搜索速度，对原算法做了如 下改进：首先保留最优解，其次自适应地改变信息量挥发系数p 的值，这样可以 避免p 过大时对全局搜索能力的影响，以及p 过小时对算法收敛速度的影响。 d m # 4 a s ( m a x m i na n ts y s t e m ) 算法 m m a s 算法的特点是只对最佳路径增加信息素浓度，从而能更好地利用历史信 息。另外，为了避免算法过早收敛于非全局最优解，将各路径的信息浓度限制在 r 。，r 。， ，超出这范围的值被强制设为r 。或r 。，这样就可以有效地避免某条 路径上的信息量远大于其余路径上的信息量。 1 4 本论文选题依据和研究内容 目前，有些大规模计算问题只能由“启发式”算法计算，而“启发式”算法 由于其自身的缺点，难以保证计算结果为全局最优解，且有些时候可能根本就计 算不出结果。 分支定界算法是求解最优化问题的一类重要方法，它在很多优化问题中得到 应用，例如整型规划、非凸函数的总极值问题、分段函数的极小问题、可行集复 杂问题的优化问题等。分支定界法以深度优先法作为分支决策的基础，在每一分 支节点上对所能达到的目标函数值的上界或下界进行估算，并将该估值与己知的 最佳本分值比较，通过提前退出或删除那些没有希望超过已知最佳本分值的决策 路径，可以提高分支决策效率。分支定界法的效率与精度，取决于变量的决策优先 次序与节点目标函数值的估计精度。 分支定界算法的优点是：能在保证精度的情况下减少问题的计算量，能够淘 1 2 第一章绪论 汰大量的没有希望超过已知最佳本分值的节点，最终得到问题的最优解，即最佳 的本分值。分支定界算法可将问题划分成相互独立的子问题，非常适合分布并行 计算。 分支定界算法的缺点是：在面对大规模问题的时候，减少的计算量还是不够 多，算法的效率与精度，取决于变量的决策优先次序和节点目标函数的估计精度。 本课题希望将分支定界算法和分布并行计算结合起来，使用一个分布并行的 计算平台，该平台能够提高分支定界算法的效率。利用分布并行减小问题规模， 并引入加速机制，使分布并行平台上的每台计算机均能在最短时间内得到任何一 台计算机计算出的当前全局最佳本分值，进一步减少分支定界算法的计算量。这 样，在提高分支定界算法效率的同时，不会落入局部最优陷阱，从而试图求出一 些旅行商( t s p ) 问题的最优解，或者求出比目前求解这些t s p 问题的“最优解” 更好的结果。 电子科技大学硕士学位论文 第二章并行计算 随着计算机技术、网络技术的迅速发展及其对科技、经济与生活影响的日益 深入，新的应用、新的需求也不断地涌现出来。人们对计算机系统的计算能力的 要求越来越大，制造了越来越快的c p u ，并发明了多机协同计算。按系统目标不同， 多机协同计算可分为分布式计算( d i s t r i b u t e dc o m p u t i r i g ) 和并行计算( p a r a l l e l c o m p u t i n g ) 。前者使地理上分散的系统协同工作，一般有多个用户同时与计算过 程交互，如银行业务系统、飞机定票系统和分布式工业控制系统；后者以获得高 性能( 如更短的计算时间) 和高可用性为主要目标，一般只有一个用户与计算过程 交互。目前，在某些并行计算系统中，也存在多用户交互，如美国a r g o n n e 实验 室的1 2 w a y 项目“。 2 。1 并行计算发展简介 并行和分布计算技术分别自2 0 世纪6 0 年代中期和2 0 世纪7 0 年代后期出现 以来，其并行处理方式经历了从阵列机( s i s d ) 、向量机及向量并行机、共享存储 的对称多处理器系统( s m p ) 、分布存储的大规模并行处理系统( m p p ) 到n u 舭( 非一致 访问的分布共享存储) 并行机系统和计算机集群系统( c l u s t e r ) 的演变过程。 在研制上述并行和分布计算系统的过程中，人们逐渐认识到，系统的规模可 伸缩性( s c a l a b i l i t y ) 和可编程性( p r o g r a m m a b i l i t y ) 已成为促使这两者进一步发 展的关键问题。规模可伸缩并行计算机系统，能以最低可能成本向用户提供最高 可能性能，因此，已成为并行计算技术发展的主流；如果计算机或工作站已连接 入局域网，计算机集群( 工作站集群n o w 集群c o w 等) 则能提供更为经济有效的高 性能计算能力，而事实上集群系统已成为分布计算技术发展的主流。 2 2 集群系统简介 计算机集群系统( c l u s t e ro fc o m p u t e r s ) 是由高性能网络或局域网物理地互 连的若于台计算机结点的集合。典型情况下，每个计算机结点是一台s m p 服务器、 一台工作站或是一台p c 计算机，结点可以是同构的，也可以是异构的。计算机数 1 4 第二章并行计算 目一般为几台至几十台，支持控制并行或数据并行的计算。每个结点上都有完整 的操作系统、网络和用户界面，都可作控制结点或运算结点，即结点之间是平等 的。集群系统最近几年的表现引人注目，由于具有出色的性价比、灵活性和良好 的并行处理能力，除了广泛作为研究课题外，在各个行业的应用发展也很快。 集群系统是利用高速通用网络将一组高性能工作站或高档p c 机，按某种结构 连接起来，并在并行程序设计以及可视化人机交互集成开发环境下，统一调度， 协调处理，实现高效并行处理的系统。从结构和结点的通信方式来看，它属于分 布存储系统，主要利用消息传递方式实现各主机之间的进程通信，由建立在一般 操作系统之上的并行编程环境并利用消息传递方式实现各主机之间的进程通信， 同时也屏蔽工作站及网络的异构性，对程序员和用户来说，集群系统是一个整体 的并行系统。机群系统中的主机和网络可以是同构的，也可以是异构的。r i s c 技 术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式成 为当前研究的热点。 2 ，3 网格计算简介 2 3 1 元计算简介 元计算“”概念是伴随着l a n ( 局域网) 向w a n ( 广域网) 、i n t e r n e t ( 国际互 联网) 的发展过程中提出来的。要回答什么是元计算，先要搞清楚什么是元系统、 元计算环境等概念。一般来讲，具有存在的主要任务和根本目标的任何形式的集 体均可算是一个元系统。广义上讲，元系统是一个异构系统，这个系统通过某种 网络将各个构件无缝的结合在一起，每个构件有自己的分工，完成一种特定的任 务。整个系统将所有构件协调起来完成一个总体目标，并对外表现为单一的整体， 且构件对外是不可见的。如果为了计算目的而组建的元系统，则称之为元计算环 境。在元计算环境中开展的程序设计和程序运行，则被称为元计算。如果将元计 算环境引入到广域网范围内，使得广域网上的空闲计算机资源集成和共享起来， 对那些亟需科学计算的用户提供统一界面的服务，而不必关心用户提交的任务是 如何划分的，在何种机器上运行，结果如何收集等，这就是元计算追求的目标。 2 3 2 网格计算简介 网格计算是在元计算的基础上发展起来的，是i n t e r n e t 应用的新发展，是在 电子科技大学硕士学位论文 巨型机与互联网技术的基础上推出的一项新变革，是完成超级计算任务的一种新 模式，又称为虚拟计算环境，或全球计算统一平台。网格试图实现互联网上所有 资源的全面连通和共享，包括计算资源、存储资源、通信资源、软件资源、信息 资源等。网格计算需要使用一套能够把一个应用程序划分成能在上千个计算机上 执行的软件和机制，感觉上如同个人使用一台超级计算机一样。从学术上讲，网 格是分布计算的一种形态。网格追求的目标来源于人们对“电力网”的类比理解， 人们希望从网格中获取“计算或服务”，就像家电用插头从电力网中获得“电能” 一样方便和普及。 2 3 3 一些著名的网格工程简介 2 3 3 1g l o b u s 工程 g l o b u s 是美国a r g o n n e 国家实验室的研发项目，全美有1 2 所大学和研究机构 参与了该工程。g l o b u s 对资源管理、安全、信息服务及数据管理等网格计算的关 键理论进行研究，开发了能在各种平台上运行的网格计算工具软件。g l o b u s 工程 的目标是阐明网格化应用的需求和开发必要的技术来满足这些需求。o l o b u s 系统 的主要部分是g l o b u s 元计算工具软件，提供了实现高层服务需使用的底层机制。 g l o b u s 最重要的成果是g l o b u st o o l k i t s ，它是开放代码，第1 版在1 9 9 9 年推出，目前可得到的版本是r e l e a s e2 2 。另外，基于o g s a 机制的下一代g l o b u s t o o l k i t s3 0 即将推出。g l o b u s 技术已在n a s a 网格( n a s ai p g ) 、欧洲数据网格 ( d a t ag r i d ) 、美国国家技术网格( n t g ) 等l o 多个网格工程中得到了广泛应用。 2 3 3 2l e g i o n 工程 l e g i o n 工程是基于对象的元系统软件。它最早在1 9 9 3 年，由v i r g i n i a 大学 的课题研究组提出并开发。l e g i o n 工程的目标是在一定的原则下构建高可用的、 有效的、可扩展的系统。l e g i o n 工程研究的关键问题是可扩展性、易编程性、容 错和安全等。它支持应用代码级的大规模并行计算，以及物理系统复杂性的管理。 l e g i o n 工程开发了一个丰富的对象模型来提供元计算服务，它提供了一个编程工 具集、一个人机交互的环境，以及一个应用程序请求元计算的执行环境。在一个 l e g i o n 应用程序里，分布的构件被看作对象。 2