（模式识别与智能系统专业论文）蚁群算法及其在tsp问题中的应用.pdf

一 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得j 量塞王些太堂或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被套阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：塑篁垡 导师签名： 垒蕉 日期： 至q q 旦：旦 摘要 摘要 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的 最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解， 属于n p 完全问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用 常规的方法求解。旅行商问题( t s p ) 就是一个经典的组合优化问题，属于n p 完全 问题。此类问题目前只能用启发式算法进行求解。 自从上世纪5 0 年代中期以来，人们不断地从生物进化的机理中得到启发， 提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退 火算法、进化规划等，并成功应用于解决实际问题。蚁群算法作为一种新的启发 式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成 功地解决许多n p - 完全组合优化问题。虽然，该研究方法目前处于研究的初级阶 段，但是一些研究成果己经显示出蚁群系统在求解复杂优化问题方面的优越性 本文在详细介绍蚁群算法原理的基础上，对蚁群算法在t s p 问题中的应用 进行分析和研究，对蚁群算法中参数口，p 的影响和作用做了分析和研究 ， 同时对最优的参数设置问题做了进一步分析和研究。最后提出了一种改进蚁群算 法模型，仿真实验表明：这种改进模型是行之有效的。 关键词：蚁群算法组和优化旅行商问题参数设置信息激素 北京t j i p 大学丁学硕十学位论文 a b s t r a c t c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mi sa ni m p o r t a n te m b r a n c h m e n to fo p e r a t i o n a lr e s e a r c h t h em a t h e m a t i c a lm e t h o d sc a nb eu s e dt os e a r c ho p t i m i z a t i o na r r a n g eg r o u p i n g ，s e q u e n c eo r r i d d i n go ft h ed i s c r e t ee v e n b t h e s ep r o b l e m sb e l o n gt o t h en o n - p o l y n o m i a l 。c o m p l e t e ( n p c ) q u e s t i o n s ，w h i c h c a n tb es o l v e di np o l y n o m i a lt i m e w i t ht h ee n l a r g e m e n to ft h es c a l eo fq u e s t i o n ， t h eq u e s t i o ns p a c em a k e st h ec h a r a c t e r i s t i co fe x p l o d i n gu p ，i su n l i k e l ys o l v e dw i t hg e n e r a l m e t h o d s a san p cp r o b l e m ，t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i sac l a s s i c a lc o m b i n a t o r i a l o p t i m i z a t i o nq u e s t i o n ，w h i c hn o wc a no n l yb es o l v e db ym e t a h e u r i s t i c st og e tt h ea p p r o x i m a t e s o l u t i o n s i n c em i d d l ep e r i o do f19 5 0 s ，p e o p l ea r eb e i n gi n s p i r e df r o mt h em e c h a n i s mo ft h e b i o l o g i c a le v o l u t i o nc o n s t a n t l y m a n yn e wm e t h o d sh a db e e na p p l i e dt o s o l v et h ec o m p l i c a t e d o p t i m i z a t i o np r o b l e m sa r ep r o p o s e d s u c h a sn e u r a ln e t w o r k ，g e n e t i ca l g o r i t h m ，s i m u l a t e d a n n e a l i n g ，a n de v o l u t i o nc o m p u t a t i o n t h e s en e wm e t h o d sh a d b e e ns u c c e s s f u l l ya p p l i e dt os o l v e t h ep r a c t i c ep r o b l e m a san e wh e u r i s t i ca l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h m w h o s em a i nc h a r a c t e r i s t i c sa r ep o s i t i v ef e e d b a c k ，d i s t r i b u t e dc o m p u t a t i o na n dc o n s t r u c t i v eg r e e d y h e u r i s t i cc a ns o l v em a n yn p - c o m p l e t ec o m b i n a t i o no p t i m i z a t i o np r o b l e m ss u c c e s s f u l l y a t p r e s e n t ，t h er e s e a r c hw o r ka b o u ta sa l r e a d ya r o u s et h ea t t e n t i o nf r o mm o r es c h o l a r sa n de x p e r t g r a d u a l l y t h o u g ht h i s r e s e a r c ha p p r o a c hl i e sa tp r i m a r ys t a g e ，b u ts o m er e s e a r c hr e s u l t sh a v e a l r e a d yd e m o n s t r a t e dt h es u p e r i o r i t yo f a s t h i sp a p e ri n t r o d u c e st h ep r i n c i p l e so f a c oi nd e t a i la n dd e s c r i b e so u rd e e pr e s e a r c hw o r k i nt h ea p p l i c a t i o no f t s pp r o b l e m s t h ei n f l u e n c ea n df u n c t i o no f t h ep a r a m e t e r ：a 、1 3 、pi na c o i sr e s e a r c h e di nt h i sp a p e r t h ee x p e r i m e n to f t h et s pf o r3 0c i t i e ss h o w su st h a tt h ec o n c l u s i o n s w eg e ta r ec o r r e c t a tt h es a m et i m e ，t h i sp a p e rt r i e st og i v et h eb e s tc o m b i n a t i o no ft h e p a r a m e t e r so fa c o i n s u r i n gg e t t i n gag o o ds o l u t i o na sap r e r e q u i s i t e ，t h es e a r c hs t r a t e g yi na c o i sa d j u s t e db ya u t h o rt oa c c e l e r a t et h ea l g o r i t h m e x p e r i m e n to f t h ee x a m p l es h o w st h a ti ti s e f f e c t i v ea n dv a l u b a l k e yw o r d s ： a n tc o l o n ya l g o r i t h mc o m b i n a t o r i a lo p t i m i z a t i o n t s p p h e r o m o n e 一 目录 目录 摘要l a b s t r a c t i i 第l 章绪论l 1 1 课题研究的背景。1 1 1 1 启发式优化算法l 1 1 2 旅行商问题( t s p ) 2 1 2 本文主要研究工作3 1 2 1 主要内容3 1 2 2 论文组织3 1 3 本章小结4 第2 章组合优化问题及其算法5 2 1 组合优化问题5 2 1 1 组合优化问题定义。5 2 1 2 算法复杂性3 2 1 6 2 1 3n p 完全问题【3 2 】8 2 2 几种随机优化算法l0 2 2 1 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 1 0 2 2 2 模拟退火算法( s a a ，s i m u l a t e da n n e a l i n ga l g o r i t h m ) 1 1 2 2 3 微粒群算法( p s o ，p a r t i c l es w a r mo p t i m i z a t i o n ) 1 2 2 2 4 蚁群优化算法( a c o ，a n tc o l o n yo p t i m i z a t i o n ) 1 2 2 3 本章小结1 3 第3 章蚁群算法研究14 3 1 基本蚁群算法机理分析14 3 1 1 蚁群算法生物学背景1 4 3 1 2 人工蚁群算法1 5 3 2 蚁群算法的实现。1 7 3 2 1 实现机理分析。1 7 3 2 2 基本蚁群算法实现步骤如下：1 9 3 3 基本蚁群算法的优缺点2 0 i 一 北京- r ：t k 大学丁学硕十学位论文 3 3 1 基本蚁群算法的优点2 0 3 3 2 基本蚁群算法的缺点2 1 3 4 蚁群算法的各种改进模型2 2 3 4 1 蚁群系统( a n tc o l o n ys y s t e m ) 2 2 3 4 2 最大。最小蚁群系统蚁群系统( m a x - m i na n ts y s t e m ，m m a s ) 2 3 3 4 3 基于蚁群算法的相遇算法2 4 3 4 4 多态蚁群算法( p o l y m o r p h i ca n tc o l o n ya l g o r i t h m ，p a c a ) 【2 0 1 2 5 3 5 本章小结2 8 第4 章蚁群算法参数分析2 9 4 i 参数对a c s 算法优化的影响2 9 4 1 1 参数0 【和b 的设定研究3 0 4 1 2 参数p 的设定研究3 2 4 1 3 印的设定研究3 3 4 2a c s 参数关系分析3 5 4 2 i 参数抗和口关系分析3 5 4 2 2 参数q d 和设置关系分析3 5 4 3 本章小结3 6 第5 章改进的a c s 算法3 7 5 1 参数设置方法改进3 8 5 2 局部改良策略3 9 5 3 改进算法的有效性研究4 0 5 4 本章小结4 2 结论4 3 参考文献4 5 攻读硕士学位期间发表的学术论文4 8 致谢4 9 附录：a c sm a t l a b 算法程序5 0 第l 章绪论 1b 1 课题研究的背景 第l 章绪论 随着计算机科学的飞速发展，许多科学研究领域和工程应用都产生了一些 组合优化问题，它们中很多都是n p 完全问题，对该类问题的研究具有十分重要 的理论意义和广泛的应用价值，其研究成果对科学研究的发展及国民经济的建设 都必将起到极大的推动作用。 目前对求解该类问题的研究主要有两个方向：传统的数学规划方法来得到 全局最优解，但这种算法的复杂性往往是不能接受的，因而难以适应大规模问题 实例的求解；近年来发展起来的各种启发式算法能够在多项式时间内找到比较好 的可以满足实际应用要求的解，但并不一定是全局最优解。考虑到，在大多数实 际的工程应用中，使用有限的时间得到较好的可以满足实际需求的解是至关重要 的，因此对组合优化问题的研究主要目前主要集中在一些启发式算法上。 1 1 1 启发式优化算法 些组合优化问题用传统的数学规划方法还没找到求最优解的多项式时间 算法，而这些组合优化问题又有非常强大的实际应用背景，人们不断尝试用一类 并不一定可以求到最优解的算法，在此称为启发式算法( h e u r i s t i ca l g o r i t h m ) ， 用来求解组合优化难题。启发式算法是相对于经典最优算法提出的，经典最优算 法包括线性规划，整数规划，动态规划和分支定界等数学规划方法，其算法计算 复杂性一般很大，只适用于小规模问题。启发式算法是一种技术，这种技术使得 在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优 性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。所以对于大规模 问题，启发式算法效果要好些。 2 0 世纪8 0 年代以来，相继出现了一些新颖的启发式优化算法，如模拟退火， 禁忌搜索，遗传算法，蚁群算法，神经网络等，其思想和内容涉及数学、物理学、 仿生科学、人工智能和统计力学等多个方面，为解决复杂问题提供了新的思路和 手段。在优化领域，由于这些算法构造的直观性与自然机理，因而被称为现代启 发式算法( m e t a h e u r is tica lg o rit h i n ) 。 本文着重研究的蚁群算法是2 0 世纪9 0 年代初出现的一种新型的启发式算 北京t 、i k 大学t 学硕十学付论文 法，研究显示这种新颖的启发式算法应用在一些复杂的组合优化问题上相对于其 它已有的算法具有自己独特的优势。它通过模拟自然界蚂蚁觅食的行为，进行信 息素传递和更新，找到蚁巢到食物源间的最短路径。虽然到目前为止人们对对蚁 群算法的研究时间并不长，但该算法己显示出极其强大的生命力和美好发展潜 力，该算法也是本文的研究重点。 以上的几种启发式优化算法在解决一些组合优化问题时显示出了前所未有 的优越性，近些年来，国内外的学者们对这一类算法兴趣渐浓，从而更加推动了 这一领域的进展，目前这一领域仍然是各国学者的研究热点，各种研究成果也不 断涌现。 应当指出，启发式优化算法尽管已经毫无争议地成为解决组合爆炸及n p 类 问题的锐利工具，但是在面对各种问题的特殊性和复杂性时，每一种算法存表现 出其自身的优势的同时，又都面临时间性能和优化性能的双重挑战，这些算法也 都存在着自身的种种缺点和不足之外。可喜的是，人们不断地对这些算法进行改 进，使得这一领域口益蓬勃发展，蒸蒸日上。 1 1 2 旅行商问题( t s p ) 术语“旅行商”( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 最早出现于1 9 3 2 年出 版的一本德文书旅行商应该如何做以及做什么才能获取酬金并在事业上取得成 功，该书的作者是一位老练的旅行商。t s p 由r a n d 公司于1 9 4 8 年引入，公司 的声誉使其成为一个知名且流行的问题。 旅行商问题( 以下简称t s p 问题) ，可以描述为：一名商人欲到n 个城市推销 商品，每两个城市j ，之间的距离为办亿爿，z 另，如何选择一条路径， 使得商人从一个城市出发，经过所有城市一次且仅一次后回到出发点，所行走的 总行程最短。 t s p 问题是属于典型的形式简单易于描述、但难于解决的组合优化问题。 长期以来，其作为算法研究与验证的平台一直被人们被广泛研究。实际上在t s p 问题上取得的理论或者实验成果，可以应用于其他的组合优化难题。许多求解其 它的组合优化问题的方法都源自于对t s p 问题的研究。因此t s p 问题从产生至今， 便吸引了众多的学者对其进行不断的研究，对t s p 问题的解决，也出现了许许多 多的不同的算法。 在长期的研究过程中，人们按照不同划分标准，对于t s p 问题作了不同的 分类。根据t s p 问题顶点之间不同方向上的距离是否相同，将t s p 问题分为 s t s p ( s y m m e t r i c t r a v e li n gs a l e s m a np r o b le m ) 对称旅行商问题和a t s p 第1 章绪论 ( a s y m m e t r i cr a v e l i n gs a l e s m a np r o b l e m ) ，非对称旅行商问题两大类；根据 t s p 问题顶点之间距离计算方法不同，将t s p 问题分为欧氏空间上的旅行商问题 非欧氏空间上的旅行商问题两大类：前者的每对顶点之间的距离可以用欧氏空间 上的距离函数计算，该类实例的表示方法有坐标和距离矩阵两种；而后者的每对 顶点之间距离不可以用欧氏空间上的距离函数计算，该类实例一般用距离矩阵来 表示。根据t s p 问题彼此连接的三条边的距离是否满足三角不等式关系，可以将 t s p 问题分为满足三角不等式的t s p 问题和不满足三角不等式的t s p 问题。本文 中研究的t s p 问题指的是欧氏空间的对称t s p 问题。 1 2 本文主要研究工作 1 2 i 主要内容 本文介绍了蚁群算法的基本机理，分析了其算法优点和不足之处，并以t s p 问题为例，对蚁群算法中参数a 、鼻、p 、q o 的影响和作用做了理论上的分析和 研究，并在此基础上提出了一种改进的算法模型，仿真实验表明，这种改进是行 之有效的。 1 2 2 论文组织 本文共分为五章： 第一章为绪论，着重阐述课题研究的背景和意义，国内外研究的现状。 第二章对组合优化问题进行阐述，以t s p 问题为例介绍了常见的解决算法 并分析了各个算法的特点。 第三章介绍了基本蚁群算法的机理，并分析了它的优点和不足之处。对各 种改进型的蚁群算法进行了研究，并分析的各自的特点。 第四章针对蚁群算法的不足，对参数a 、夕、p 、q d 等的设置做了定性的 分析，对其在t s p 问题中的作用作整体说明。然后通过以o l i v e r 3 0 等t s p 问题 为例，进行了仿真实验，验证了分析的正确性。 第五章提出了改进参数的设置方法，并在此基础上提出了改进算法模型， 并通过仿真实验并验证了其的有效性。 最后为结束语，为本文工作的总结，及对未来的展望。 北京t 业大学丁学硕十学位论文 1 3 本章小结 本章首先阐明了课题的研究背景、意义以及国内外的研究现状和概况，然后 介绍本文主要工作以及论文组织。 第2 章组合优化问题及其算法 第2 章组合优化问题及其算法 2 1 组合优化问题 “优化”是指在解决某一问题时，从所有可行方案中，通过分析、判断、比 较，从中找出一种最佳方案来。随着科学技术和现代化生产的飞速发展，客观世 界中的问题不断复杂化，而人们所求的优化程度却逐渐提高，使得优化问题在各 行各业中的地位越来越重要，优化问题几乎无处不在。目前，虽然传统的数学规 划理论成功地解决了一些优化问题，但当现代系统的规模增大，约束条件增多， 非线性严重时，传统的优化方法就显得无能为力了，因此迫切需要新的优化理论 和方法。 2 1 1 组合优化问题定义 “组合优化问题 ( c o m b i n a t o r i a lo p t i m i z a t i o n ) 又称离散优化问题，其目的 主要是寻找离散事件的最优编排、分组、次序或筛选等，组合优化问题广泛存在 于经济管理、交通运输、通信网络等领域，这类问题近年来越来越受到运筹学、 应用数学、计算机科学及管理科学等诸多学科的高度重视。虽然某些组和优化问 题有悠久的历史渊源，被费马( f e r m a t ) 、欧拉( e u l e r ) 等众多著名数学家研究过， 但作为运筹学的一个独立分支而发展壮大起来还是近几十年的事。它是一门新兴 的学科分支。 组合优化问题其实是个求极值问题，它由下述三部分组成： ( 1 ) 实例集合： ( 2 ) 对每一个实例l 有个有穷的可行解集合s 倒： ( 3 ) 目标函数万它对每一个实例，和每一个可行解，赋以一个有理数以0 j ，则 实例，的最优解为这样一个可行解0 + e s ( z ) ，它使得对于所有0e s ( z ) ，都有厂亿 o + ) f 亿。夕或者亿o ) f 亿o ) 。 典型的组合优化问题有t s p 问题、o 一1 背包问题( 0 - ik n a p s a c kp r o b l e m ) 、 加工调度问题( s c h e d u l i n gp r o b l e m ) 、装箱问题( b i n p a c k i n gp r o b l e m ) 、图着色 问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 以及最大团问 题( m a x i m u mc l i q u ep r o b l e m ) 和最大割问题( m a xc u tp r o b l e m ) 等。 组合优化问题都有一个显著的特点，就是问题的数学描述都非常简单，且在 北京t n p 大学t 学硕十学位论文 问题的规模较小时，算法并不复杂，但随着问题的规模变大，问题解空间会呈现 爆炸式增长，导到解决问题的算法复杂性会大大增加。 2 1 2 算法复杂性i ，2 】 一个算法的有效性可以用执行该算法所需要的各种计算资源的量来衡量，最 主要的两个资源就是所需的运行时间和存贮字间。算法或问题的复杂性一般是问 题规模n 的函数，时间复杂性记为t ( n ) ，空间复杂性记为s ( n ) 。 算法执行期间占用的存贮单元定义为算法的空间复杂性。但在算法分析和设 计中，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间需求 常常是决定某一算法在实际中是否真正有效的决定性因素。因此，在算法复杂性 研究中，衡量一个算法的效果，最广泛采用的标准是在产生最终结果前它所花费 的时间，并常称复杂性为时间复杂性。 时间复杂性并不是具体表示一个程序解决问题需要花多少时间，而是当问题 规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据 的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看 当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢 了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么 多的，我们就说这个程序很好，具有0 ( 1 ) 的时间复杂度，也称常数级复杂度： 数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 0 ( n ) ，比如找t 1 个数中的最大值；而像冒泡排序、插入排序等，数据扩大2 倍， 时间变慢4 倍的，属于0 ( n 2 ) 的复杂度。还有一些穷举类的算法，所需时间长 度成几何阶数上涨，这就是0 ( a n ) 的指数级复杂度，甚至0 ( n ! ) 的阶乘级复杂度。 不会存在0 ( 2 * n 2 ) 的复杂度，因为前面的那个“2 ”是系数，根本不会影响到整 个程序的时间增长。同样地，0 ( r l 3 + n 2 ) 的复杂度也就是0 ( n 1 3 ) 的复杂度。因 此，我们会说，一个0 ( 0 0 1 * n 3 ) 的程序的效率比0 ( 1 0 0 * n 2 ) 的效率低，尽管在 n 很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终0 ( n 3 ) 的复杂度将远远超过0 ( r l 2 ) 。我们也说，0 ( n 1 0 0 ) 的复杂度小于0 ( 1 0 1 n ) 的复 杂度。 容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何 都远远大于前者：一种是0 ( 1 ) ，0 ( 1 0 9 ( r 1 ) ) ，0 ( n a ) 等，我们把它叫做多项式级的 复杂度，因为它的规模1 2 出现在底数的位置；另一种是0 ( a r 1 ) 和0 ( n ! ) 型复杂度， 它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决个问题时， 我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时 第2 章绢合优化问题及其算法 间太多，往往会超时，除非是数据规模非常小。 在组合优化问题中，比较和搜索常被指定为基本操作。基本操作的执行次 数随问题规模的增长以一定的方式增长。在分析算法或问题的复杂性时，可以求 出算法的复杂性函数丁例是力的多项式函数，则称算法a 为多项式时间算法。 一般认为多项式时间算法是好的算法；反之，时间复杂性不能囿于多项式的算法 称为指数时间算法。求解组合优化问题的算法的时间复杂性对计算机的解题能力 ( 速度和规模) 有重大的影响。以旅行商问题为例，对此问题的直观的求解方法是 穷举法，我们来考察需要的计算时间。假设城市规模是n ，旅行商在起点时，可 以选择( n i ) 个城市进行访问，当他访问完这个城市后，他可以选择剩下的( n 一2 ) 个城市进行访问，依此类推，当他访问完第i 个城市后，他可以选择( n - i - i ) 个 城市进行访问，因此，需要进行向一! 的计算，每次计算，需要累加n 条访问 路线的费用总和，所以，总的计算时间是0 ( n ! ) 。用运算能力为每秒一百万次 浮点运算的计算机求解，在n = l o 时只需0 1 8 5 s 。而在n = 2 0 ，需用1 9 2 9 年才能找 到最优解。表2 1 比较了具有几种不同时间复杂度函数的算法在输入规模增加时 运算时间增长的情况，从表中可以看出，指数时间算法在输入规模增加时运算时 间急剧增，最终将达到天文数字的量级。 表2 - i 不同时间复杂度函数下算法性能的比较 ta _ b 2 1t h ec o m p a r eo fd i f f e r e n tt i m e c o m p l e x i t y r e l a t i v et od i f f e r e n tp r o b l e ms c a l e 时间 输入问题规模n 复杂度 1 02 03 04 05 01 0 0 玎1 0 纳秒2 0 纳秒3 0 纳秒4 0 纳秒5 0 纳秒1 0 0 纳秒 6 4 1 纳 n l o g n 1 0 纳秒2 6 纳秒 4 4 3 纳秒8 4 9 纳秒2 0 0 纳秒 秒 玎21 0 0 纳秒4 0 0 纳秒9 0 0 纳秒i 6 微秒2 5 微秒1 0 微秒 1 0 微秒1 0 毫秒1 1 秒1 8 3 分3 1 3 小时4 0 世纪 8 4 x 1 0 1 32 6 l o 猡9 6 1 0 凡3 0 1 0 ，刀 n13 6 毫秒 7 7 1 年 世纪世纪世纪世纪 北京t _ q k 大学丁学硕十学位论文 2 1 3n p 完全问题f 3 2 】 按照计算复杂性理论研究问题求解的难易性，可把问题分为p 类、n p 类和 n p 完全类。 p 类问题的概念：如果一个问题可以找到一个能在多项式的时间罩解决它的 算法，那么这个问题就属于p 类问题。 p 类问题的概念是好理解的，那么什么是n p 问题呢? 需要强调的是，n p 问 题不是非p 类问题。n p 问题是指没有找到多项式时间的算法，但可以找到在多 项式的时间里验证一个解的问题。在很多问题中，求解很困难，但验证一个解很 容易。如果验证一个解只需要多项式的时间复杂度，则这类问题就称为n p 问题。 当然有不是n p 问题的问题，即不能在多项式的时间里去验证它的一个解。 之所以要定义n p 问题，是因为通常只有n p 问题才可能找到多项式的算法。 我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项 式级的算法。 易知，所有的p 类问题都是n p 问题。也就是说，能多项式地解决一个问题， 必然能多项式地验证一个问题的解既然能求出解，验证任意给定的解也， i 需 要比较一下即可。但关键是，人们想知道，是否所有的n p 问题都是p 类问题。 我们可以再用集合的观点来说明。如果把所有p 类问题归为一个集合p 中，把所 有n p 问题划进另一个集合n p 中，那么，显然有p n p 。现在，所有对n p 问题 的研究都集中在一个问题上，即究竟是否有p = n p ? n p 问题一直都很引人注目但难以解决，目前为止，这是一个耗费了很多时 间和精力也没有解决的问题，好比物理学中的大统一和数学中的歌德巴赫猜想 等。但是，一个总的趋势、一个大方向是有的。学者们普遍认为，p = n p 不成立， 也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的n p 问 题。 学者们之所以如此坚信p n p 是有原因的，那就是在研究n p 问题的过程中找 出了一类非常特殊的n p 问题叫做n p - 完全问题，也即所谓的n p c 问题。c 是英 文单词“完全”的第一个字母。正是n p c 问题的存在，使人们相信p n p 。 为了说明n p c 问题，我们先引入一个概念归约( r e d u c i b i l i t y ) ，简单 地说，一个问题a 可以归约为问题b 的含义即是，可以用问题b 的解法解决问题 a ，或者说，问题a 可以“变成 问题b 。举了一个例子，比如说，现在有两个 问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以 归约为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。 我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照 这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序 上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变， 一元二次方程的二次项系数为o 。按照这个规则把前一个问题转换成后一个问题， 两个问题就等价了。 “问题a 可归约为问题b ”有一个重要的直观意义：b 的时间复杂度高于或 者等于a 的时间复杂度。也就是说，问题a 不比问题b 难。这很容易理解。既然 问题a 能用问题b 来解决，倘若b 的时间复杂度比a 的时间复杂度还低了，那a 的算法就可以改进为b 的算法，两者的时间复杂度还是相同。正如解一元二次方 程比解一元一次方程难，因为解决前者的方法可以用来解决后者。 很显然，归约具有一项重要的性质：归约具有传递性。如果问题a 可归约为 问题b ，问题b 可归约为问题c ，则问题a 一定可归约为问题c 。这个道理非常 简单，不再详述。 现在再来说下归约的标准概念就不难理解了：如果能找到这样个变化法 则，对任意一个程序a 的输入，都能按这个法则变换成程序b 的输入，使两程序 的输出相同，那么我们说，问题a 可归约为问题b 。 当然，我们所说的“可归约”是指的可“多项式地”归约( p o l y n o m i a l t i m e r e d u c i b l e ) ，即变换输入的方法是能在多项式的时间里完成的。归约的过程只有 用多项式的时间完成才有意义。扣 从归约的定义中我们看到，一个问题归约为另一个问题，时间复杂度会增 加，问题的应用范围也会增大。通过对某些问题的不断归约，就能够不断寻找 复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一 类问题的算法。结合前文所述的p 和n p 问题，再依据起归约的传递性，自然地， 就会推出，如果不断地归约上去，不断找到能解决若干小n p 问题的一个稍复杂 的大n p 问题，那么最后就能找到一个时间复杂度最高，并且能解决所有的n p 问题的这样一个超级n p 问题。也就是说，存在这样一个n p 问题，所有的n p 问 题都可以归约成它。换句话说，只要解决了这个问题，那么所有的n p 问题都解 决了。这种问题的存在曾一度令学者们难以置信，并且更加不可思议的是，这种 问题不只一个，它有很多个，它是一类问题。这一类问题就是我们所说的n p c 问 题，也就是n p - 完全问题。n p c 问题的出现使整个n p 问题的研究得到了飞跃式的 发展。我们有理由相信，n p c 问题是最复杂的问题。通常，如果想表达一个问题 不存在多项式的高效算法时，那么应该说它“属于n p c 问题”。 北京t 、i k 大学t 学硕十学佗论文 下面给出n p c 问题的定义，即同时满足下面两个条件的问题就是n p c 问题。 首先，它得是一个n p 问题；然后，所有的n p 问题都可以归约到它。证明一个问 题是n p c 问题也很简单。先证明它至少是一个n p 问题，再证明其中一个已知的 n p c 问题能归约到它，这样就可以说它是n p c 问题了。 既然所有的n p 问题都能归约成n p c 问题，那么只要任意一个n p c 问题找到 了一个多项式的算法，那么所有的n p 问题都能用这个算法解决了，n p 也就等于 p 了。因此，给n p c 找一个多项式算法会显得不可思议。这也是学者们之所以相 信“p ：n p ”的原因。我们可以就此直观地理解，n p c 问题目前没有多项式的有 效算法，j 能用指数级甚至阶乘级复杂度的搜索。 综上所述，关于我们给出以下结论： ( 1 ) 对于判定问题d ，存在一个多项式p ( t ) ，使得对其每一输入规模为n 的实例，可以在p ( n ) 的时间内求得最优解，此类问题称为p ( p o l y n o m i a l ) 问题。 ( 2 ) 若问题l n p ，所有n p 问题都可以经过多项式计算时间归约为l ，则l 称为n p 完全问题。 ( 3 ) 如果问题l ，是n p 完全问题，l ：n p ，且l ：可以多项式时间归约到l 。， 则l 。也是n p 完全问题。 ( 4 ) 如果某n p 完全问题有多项式时间算法，则n p 类中所有其他问题也有 多项式时间算法，因此n p 完全问题是n p 类中最难解问题。另一方面，如果一个 n p 完全问题没有多项式时间算法，则所有n p 完全问题也没有，因此所有n p 完 全问题是同等难度的。 ( 5 ) 假如一个问题是p 问题，我们通常认为它是“简单的”，而n p c 问题， 通常认为它是“复杂的”。n p c 问题是指可在多项式时间里检验的问题，至今尚 未找到多项式时间算法。在6 0 年代后期，人们认为大部分组合优化问题是属于 n p 类问题。 ( 6 ) 时至今日，人们相信，np 完全问题不太可能存在多项式计算时间内的 算法，因此，近年来，对n p 完全问题的研究逐渐向两个方向演化：一是寻求在多 项式时间内求得具有上确界解的算法：二是探索启发式的搜索算法，而启发式搜 索算法己经应用在许多实际问题上，并取得了令人满意的结果。 2 2 几种随机优化算法 2 2 1 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 遗传算法是美国m i c h i g a n 大学的j o h nh o l l a n d 教授等人于1 9 7 5 年提出的模 一1 0 一 第2 章绢合优化问题及其算法 拟自然界中生物遗传机制的随机搜索算法，它是基于染色体层而进行各种遗传优 化操作酬， g a 在本质上是一个群体迭代算法，它从一组随机的初始群体出发， 由目标函数( 适应度函数) 对其进行评价，根据“优胜劣汰”的竞争原则，通过选 择、交叉、变异等优化过程，产生性能更优的下一代群体，不断重复，直到获得 满意的结果。在遗传算法中变异算子主要起到维持群体的多样性、防止出现早熟 现象的作用。变异算子用新的基因值替换原有基因值，从而可以改变个体编码串 的结构，维持群体的多样性，这样就有利于防止出现早熟现象。 g a 的特点是：具有全局搜索能力，具有并行型，具有较强的顽健性，计算 过程简单，能很好地解决开发最优解和探寻搜索空间的矛盾，具有可扩展性。但 遗传算法也存在一些不足，例如局部搜索能力差，存在未成熟收敛和随机漫游等 现象，从而导致算法的收敛性能差，需要很长时间才能找到最优解1 5 ，6 1 。 g a 的基本步骤如下： 步骤l 确定群体规模( 整数) 及遗传操作的代数( 整数) 。随机产生一组初始解 i k ( k = 1 , 2 ，n ) 作为初始解群( p o p u l a t i o n ) ； 步骤2 计算解群中每个解的适应值f ( i k ) ( 适应值一般与其相应的目标函数有 关) ，求出其选择概率； 步骤3 按选择概率的大小随机地从解群中选出两个串作为父代，并以一定的 交叉率、变异率对其进行操作，产生新的个体，重复步骤3 ，直到得到n 个新的。 一 个体组成新解群； 步骤4 转步骤2 直到满足算法终止条件，结束操作。 2 2 2 模拟退火算法( s a a ，s i m u l a t e da n n e a l i n ga l g o r i t h m ) 模拟退火法是s k i r k p a t r i e k 等人于1 9 8 3 年提出的模拟高温物体退火过程的组 合优化方法1 7 - 9 1 。它是利用组合优化问题代价函数的极小化过程与固体物质冷却到 低能状态的过程的极大相似性，模拟高温物体退火过程，找出优化问题的全局最 优或近似全局最优解。近年来，有众多学者对其在增加算法并行性、提高搜索效 率、解决较大规模优化问题等方面进行了改进，推动了该算法的应用和发展，从 某种程度上改善了算法的性能。 s a a 的特点是：在搜索过程中能以一定的概率接受性能变差的解，算法具有 较强的全局搜索能力，从理论上说，具有全局渐进收敛性。虽然模拟退