（系统工程专业论文）蚂蚁算法在组合优化问题中的应用研究.pdf

中文摘要 组合优化问题是优化领域中的重要分支。组合优化问题有很强的工程背景， 例如任务分配问题和j o b - s h o p 问题。虽然求解组合优化问题的方法层出不穷， 但这些方法都有各自的缺点和局限性，目前还不能满足实际应用的需要。蚂蚁算 法作为一种新近出现的启发式算法，它具有正反馈、分布式计算和具有贪婪的启 发式等特点。蚂蚁算法已经成功地应用于求解货郎担问题t s p ( t r a v e l i n g s a l e s m a n p r o b l e m ) ，引起了广泛的关注。但是由于蚂蚁算法出现的时间很短，它的应用研 究还处于初步阶段，在许多组合优化问题上蚂蚁算法的研究还处于空白，例如任 务分配问题和j o b s h o p 问题。本文将蚂蚁算法应用于求解任务分配问题和 j o b s h o p 问题，并且针对求解过程中出现的问题，提出了改进的蚂蚁算法，并且 通过大量的仿真试验加以验证，取得了很好的结果。 在第一章中，主要介绍了最优化技术的基本理论和发展历史、启发式算法的 定义和设计方法以及本文的创新点。 在本文的第二章中，主要介绍了组合优化的概述和常用的求解方法。 在第三章中，主要介绍了蚂蚁算法，包括：蚂蚁算法的仿生原型、蚂蚁系统、 改进的蚂蚁算法以及目前国内外的研究现状。 在第四章中，将蚂蚊算法应用于求解任务分配问题。针对蚂蚊算法使用了局 部搜索法，易于陷入局部极小陷阱，因此作者对蚂蚁算法作了改进，在选择概率 中加入混沌函数扰动，使算法在一定程度上接受恶化解，以跳出局部极小的陷阱， 并通过仿真试验加以验证。 在第五章中，作者将蚂蚁算法应用于求解j o b s h o p 问题。针对采用传统信 息造成机床加工时间的大量浪费，作者提出了一种新的启发信息：最早允许开始 时间( e a p t ) ，可以使未加工的工序填入到机床上的空闲时间段内加工，缩短了 总的加工时间，同时在算法中加入了适量的随机信息，扩大了算法的解空间，避 免了陷入局部极小的陷阱，通过大量的仿真试验验证了新算法的有效性。在本文 的最后，作者还对算法的两个主要参数与仿真结果的关系作了研究。 论文的第六章总结了全文的工作，并对未来的研究工作提出了展望。 关键词： 蚂蚁算法、任务分配问题、j o b s h o p 问题、混沌函数扰动、 最早允许加工时间 a b s t r a c t c 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 sa r et h ek e yb r a n c ho ft h eo p t i m i z a t i o n p r o b l e m s c o m b i n a t i o no p t i m i z a t i np r o b l e m s h a v ea s 竹o n gb a c k g r o u n d o f e n g i n e e r i n g ，f o re x a m p l e ：a s s i g n m e n t p r o b l e ma n d j o b s h o pp r o b l e m a n ta l g o r i t h m i san e wa p p e a r i n gh e u r i s t i c 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 e f 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 dt h eu s eo f ac o n s t r u c t i v eg r e e d yh e u r i s t i c a n t a l g o r i t h mh a sa l r e a d ya p p l i e dt os o l v i n gt r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，w h i c h h a sa t t r a c t e dm u c ha t t e n t i o n r e c e n t l y b u t b e c a u s ea p p l i c a t i o nr e s e a r c ho fa n t a l g o r i t h ms t i l ls t a n d si nt h ep r e l i m i n a r yp h a s en o w , s o i nm a n yf i e l d so fc o m b i n a t i o n o p t i m i z a t i o n ，i t sa p p l i c a t i o n r e s e a r c hi sb l a n k i nt h i st h e s i s ，a n ta l g o r i t h mi sa p p l i e d t os o l v i n ga s s i g n m e n tp r o b l e ma n dj o b - s h o pp r o b l e m ，a n dp o i n t i n gt ot h ep r o b l e m s w h i c ha r e g e n e r a t e d i nt h ep r o c e s so fs o l v i n gt h ep r o b l e m s ，t w oi m p r o v e da n t a l g o r i t h m sa r cp u tf o r w a r d ，w h i c ha r cv a l i d a t e db ym a n ys i m u l a t i o n sa n dh a v eg o o d r e s u l t s i nt h ec h a p t e rl ，t h et h e s i si n t r o d u c e st h eb a c k g r o u n do ft h er e s e a r c l l ，a n dt h e d e s i g nm e t h o d so f h e u r i s t i ca p p r o a c h t h e n ，t h ef i n d i n g si nt h et h e s i sa r ep o i n t e do u t i nt h e c h a p t e r2 ，t h et h e s i si n t r o d u c e st h e o u t l i n eo fc o m b i n a t i o no p t i m i z a t i n p r o b l e m sa n dg e n e r a ls o l v i n ga p p r o a c h e s i nt h ec h a p t e r3 ，t h et h e s i si n t r o d u c e sa n ta l g o r i t h m ，i n c l u d i n g ：b i o n i cm o d e lo f a n ta l g n r i t h m ，a n t s y s t e m ，a n d d o m e s t i ca n df o r e i g ns t a t u so f r e s e a r c h i nt h e c h a p t e r4 a n ta l g o r i t h mi su s e d t os l o v ea s s i g n m e n tp r o b l e m b e c a u s eo f l o c a ls e a r c ha b i l i t yo ft r a d i t i o n a la n ta l g o r i t h mt h es o l u t i o ni se a s yt od r o pi n t ol o c a l t r a p ，s ow e a d d e dac h a o sf u n c t i o nd i s t u r bt ot h e p r o b a b i l i t yo fe h o i c e ，w h i c h c a n h e l p t h es o l u t i o ng a po u tl o c a lt r a p t h ee f f e c t i v e n e s so ft h ea l g o r i t h mi sd e m o n s t r a t e d b y s i m u l a t i o n s i nt h ec h a p t e r5 ，a n ta l g o r i t h mi su s e dt os l o v e j o b s h o pp r o b l e m b e c a u s eo f b a d s o l u t i o n sg o tb yu s i n gt r a d i t i o n a lh e u r i s t i ci n f o r m a t i o n ，w ea p p l i e dan e wh e u r i s t i c i n f o r m a t i o nn a m e de a r l i e s ta l l o w e d p o r o c e s s i n gt u n e ( e a p t ) t ot h ea l g o r i t h ma n d a d d e dar a n d o mi n f o r m a t i o nt ot h ea l g o r i t h mt oa v o i dd r o p i n gi n t ol o c a lt r a p n l c v a l i d i t yo f t h ea l g o r i t h mi sd e m o n s t r a t e db ym a n y s i m u l a t i o n s a tl a s to f t h e e h a p t e r ， t h er e l a t i o nb e t w e e nt h es i m u l a t i o nr e s u l t sa n dt h et w om a i np a r a m e t e r so ft h e a l g o r i t h m i sf u r t h e rs t u d i e d i nt h ec h a p t e r6 ，w es u m m a r i z et h i st h e s i sa n d p o h a t e do u tt h ep r o b l e m s ，w h i c h a r ew o r t h yo f f u r t h e rr e s e a r c hi nt h ef u t u r e k e yw o r d s ：a n t a l g o r i t h m ，a s s i g n m e n tp r o b l e m ，j o b s h o pp r o b l e m ，c h a o sf u n c t i o n d i s t u r b ，e a p t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨盗盘兰或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：辛切冬 签字日期：工哆年r 月j 口日 学位论文版权使用授权书 本学位论文作者完全了解墨洼盘鲎有关保留、使用学位论文的规定。 特授权鑫洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：初叁导师签名 参破 签字日期：z 哆年口月弓口日签字日期：叫年肛膨d 日 天津大学硕士学位论文 第一章绪论 一一- _ - - - _ - _ - _ - - - _ - - ，_ _ h 一 1 1 选题背景与研究意义 第一章绪论 在人们的生活和工作中，总会碰到各种各样的问题，而解决这些问题的方案 又有许多，其中有些方案较优，有些方案较差。人们总是希望得到最优的方案进 行实施，以达到满意的效果。这样随着知识和经验的积累，逐渐产生了一项技术 最优化技术。 解决最优化问题的技术称为最优化技术，这种技术可以概括为两个方面： f 1 1 建立数学模型：将实际的最优化问题用数学的语言描述出来。模型由一 组数学关系式，如方程、不等式、逻辑依赖关系式等组成。他们反映了 物理定律、市场约束、工艺关系的方面的内容； ( 2 ) 求出最优解：其内容包括对已建立的数学模型进行分析，选用适当的最 优化数学方法、编写计算程序、在计算机上运算和对运算的结果进行评 价，求出实际问题的最优解答。 建立数学模型是一项基础性的工作。要从实际问题中抽象出其正确的数学模 型，这又是一项复杂与困难的工作。对不同领域内的具体问题建立数学模型，需 要不同的专业知识。对于如何建立数学建模问题，已经有了许多理论，本文不再 做详细的阐述。本文主要针对的是，对实际问题已经建立好的数学模型，寻找解 决的最优方法。 历史上最早记载下来的最优化问题可以追溯到古希腊的欧几里得( e u c l i d 公 元前3 0 0 年左右) ，他指出：在周长相同的一切矩形中，正方形的面积最大。十 七、十八世纪微积分的建立给出了求解函数极值的一些准则，对最优化的研究提 供了某些理论基础，起到了很大的推动作用。然而在以后的两个世纪中，最优化 技术的进展是很缓慢的，起到很大的推动作用。然后在以后的两个多世纪中，最 优化技术的进展是缓慢的，主要考虑了有约束条件的最优化问题，发展了一套变 分方法。但是，用这些分析方法归结成的数学问题很难计算求解，从而不能真正 解决实际优化问题。一般称二十世纪五十年代以前用经典的微分法和变分法求解 最优化问题的技术为经典最优化技术。 近三、四十年来，尤其是六十年代以来，最优化技术进入了蓬勃发展的时期。 一方面是由于近代科学技术和生产力的迅速发展，提出了很多用经典最优化技术 天津大学硕士学位论文 第一章绪论 无法解决的最优化问题，为了解决这些经济、军事等问题，客观地推动了最优化 技术的研究与运用。另一方面，由于电子计算机的出现与发展，为最优化技术提 供了有效的手段，许多大型复杂的优化问题，过去仅能定性地、粗略地在理论范 畴内进行讨论，现在己经可以进行精确的定量分析了。 这些年，随着优化算法研究的进一步深入，特别是对于一些优化问题，如果 求解严格的最优解，不仅方法极其复杂，而且也是没有意义的，因为这类问题的 求解模型和约束条件本身就不太严格，而这时，启发式算法的发展恰好适应了优 化问题的求解要求，人工神经网络、模拟退火、遗传算法、禁忌搜索、进化规划 等现代启发技术在解决复杂优化问题中表现出巨大的潜力和作用。 蚂蚁算法作为一种新近出现的启发式算法，在许多领域中已经取得了成功的 应用。我们希望通过我们的研究工作可以扩大蚂蚁算法的研究范围，同时用在解 决问题的过程中得到的经验来丰富和完善蚂蚁算法的理论，也为解决组合优化问 题提供一秭新的途径。 1 2 启发式算法概述 在计算机科学、人工智能、智能工程、运筹学及其它一些工程学科中，我们 经常遇到启发式算法( h e u r i s t i c ) 这个词。 问题求解的第一步是将问题表达成易于求解的形式。利用状态空间来描述问 题是一种较通用的方法。 对大多数应用程序来说，问题求解是最基本的。问题主要有两种类型。第一 种类型的问题可以由一些确定的过程来求解，并且保证能成功，这个过程就称为 计算。通过计算来求解通常只适用于那些有计算过程的问题，但是现实世界的问 题很少是可以仅仅通过计算求解的。这样一些问题属于第二类；这些问题的求解 需通过搜索进行，这就是启发式算法解决的问题。 启发式算法对付的是这样一些问题：或者根本不存在解这种问题的确定算 法，或者虽有这种算法，但其复杂性之高足以使人望而却步。其中不少是属于所 谓n p 完备问题，例如货郎担问题。 任何一个问题求解系统的基本构成是由三个部分组成：一个数据库，一组运 算符和一个控制策略。数据库代表了所要解决的问题，每个运算符代表了解题的 一个步骤，它作用于数据库，改变数据库的状态。而控制策略则包含了解题的策 略，即在什么情况下运用哪个运算符去改变数据库的状态，以及怎样改变。在问 题求解的每一时刻，数据库都处于一定的状态，数据库所有可能状态的全体，称 为状态空间。 天津大学硕士学位论文 第一章绪论 任何问题的求解技术，包括状态空间技术，都包括两方面的内容表示和 搜索。对于同一个问题可以有许多不同的表示，其中某些表示要比另一些表示有 小得多的状态空间。如果被搜索的状态空间太大了，即使是原有效的搜索方法也 是不适用的。用尽可能经济的方法来表示问题是很重要的。 在讨论状态空间搜索时，经常要涉及两个基本问题；一是搜索的最优解；二 是搜索的复杂性。所谓搜索的最优解是指如何能尽快找到问题的最优解，所谓搜 索的复杂性是指搜索中究竟要进行多少步。与搜索复杂性有关的问题常被称之为 组合复杂性。因为在有些应用中，复杂性问题显得十分突出。例如，如果状态空 间中每一个结点都有6 个下一个状态，则当搜索向下进行到第h 步时，所产生的 可选择路径数目为b ”。由此可见，可选择的路径数目与路径本身长度成指数关 系，这就导致了常说的“组合爆炸”问题。 为了避免“组合爆炸”，必须恰当地利用与问题有关的某些特殊信息来控制 搜索过程，即用启发式搜索方法来搜索状态空间。 启发式算法是和问题求解及搜索相关的，也就是说，启发式算法是为了提高 搜索效率才提出的。1 9 8 4 年p e a dj 在其专著“h e u r i s t i c s ：i n t e l l i g e n ts e a r c hs t r a t e g i e s f o r c o m p u t e r p r o b l e ms o l v i n g ”中对启发式算法进行了详细的讨论。他认为：所谓 启发式算法是指一组指导算法搜索方向的、建议性质的规则集，通常按照这个规 则集，计算机可在解空间中寻找到一个较好解，但并不能保证每次都能找到较好 的解，更不能保证找到最优解。换句话说，所谓启发式算法就是那些从大量的实 验数据来看，算法的实际计算性能较好，但理论上证明这些算法在最坏情况下解 题性能并不好，或者理论上并不能证明这些算法具有优良的解题性能。 由于启发式算法的设计不依赖于纯数学中优化理论的突破与发展因此其研 究和应用在最近2 0 多年来获得了突飞猛进的发展。尤其是在复杂的组合优化问 题上，各种各样的启发式算法更是层出不穷，但正是由于启发式算法缺乏严格的 理论推导和数学证明，决定了它的设计具有很强的随意性及创造性。为了研究启 发式算法的设计规律z a n a k i s 等人挑选1 9 7 3 年到1 9 8 6 年1 3 年间发表在3 7 种 杂志上的4 4 2 篇关于启发式算法及应用的文章进行研究，这些文章涉及到1 4 4 个 应用领域，其中绝大部分为组合优化问题。 启发式算法的设计方法分为7 类，分别是1 】： ( 1 ) 构造法( c o n s t r u c t i o n ) 一个优化问题的解是由若干个构造元素组成的，构造性启发式算法通过一个 一个地增加解的构造元素来求得一个可行解。“贪婪法”在每一步都寻找最大的 改进其中包含了大量构造性的启发式算法。在大多数构造性启发式算法中，直 到算法结束才会找到可行解。例如对于货郎担问题来说，其解是由n 个城市间的 天津大学硕士学位论文 第一章绪论 距离组成，这些城市间的距离就是解的构造元素。货郎担问题的构造性算法之一 就是从某一城市开始，每次寻找与其距离最近且末走过的城市作为增加的构造元 素，如此循环，到结束时，一个较短的可行环游路线就得到了。构造性算法的循 环次数与问题解的构造元素个数成正比，而与解空间的大小无关。因此，其计算 速度通常很快。 ( 2 ) 改进法( i m p r o v e m e n t ) 。 该算法从一个可行解开始通过在其临域内的搜索如交换、合并结构元素等 来改进解的质量。一般来讲，在整个搜索过程中，解一直处于可行状态。例如， 货郎担问题的改进性算法之一就是从一条可行环游路线开始，每次迭代都删除k 个城市连线，然后再增加k 个不同的、能改进解的质量的连线。 将构造法和改进法组合起来使用是很常见的，首先利用构造法得到初始解， 然后利用改进法搜索邻域内的最优点。这种组合法在所列的文献中非常普遍。 ( 3 ) 数学规划法( m a t h e m a t i cp r o g r a m m i n g ) 该方法在问题的数学优化模型及其精确求解方法的基础上，修改求解方法以 其得到问题有效的启发式算法。 ( 4 ) 分解法( d e c o m p o s i t i o n ) 该法指求解一系列容易求解的小问题，一个问题的输出是下一个问题的输 人，然后将这些解归纳、合并成一个解。许多规j i l ( s c h e d u l e ) i n - 题的启发式算法 使用了分解法。 ( 5 ) 分割法( p a n i t l o n i n g ) 分割法将一个问题分割为几个子问题，然后独立地解决每个子问题。这些子 问题的解再合并成整个问题的解。例如，在求解货郎担问题时，将平面分割成几 个小区域，在每个小区域内求解旅行销售商问题，最后将所得的解合并成总的环 游路线。 ( 6 ) 解空间限制法( s o l u t i o ns p a c er e s t r i c t i o n ) 该法的思想是限制解的构造，以便问韪变得容易求解。在某种意义上，所有 的启发式算法都是限制法，然而在这里，是指明确地约束解空间的方法。典型的 限制法只允许算法在具有特殊性质的解中搜索。 ( 7 ) 松弛法( r e l a x a t i o n ) 这种方法与限制法相反，它是指为了得到容易处理的问题而扩展解空间。 虽然把启发式算法分成以上7 类，但在实际应用中很难明确划分使用的是某 一种方法。根据开发者的仓4 造性、经验及设计修改新的解题方法的技巧艺术， 可能将以上几种方法结合起来使用。 以上划分是基于运筹学观点的，对于求解该领域内的、难于用精确数学方法 天津大学硕士学位论文第一章绪论 求解的难题，具有很好的指导价值。 启发式算法比起比较标准的组合优化算法有明显的好处： ( 1 ) 启发式算法比较简单，因而常能由缺乏高级训练的实践者来实现； ( 2 ) 启发式算法不需要很多的计算时间，可以显著的节省开支； ( 3 ) 启发式算法是很灵活的，除去应用于定量化的问题，在一些不能定量表 示的问题上，启发式算法也有应用。 1 3 本文主要研究内容 本文主要研究内容是蚂蚁算法在组合优化问题中的应用。首先，蚂蚁算法作 为新近出现的一种启发式算法，它具有正反馈、分布式计算和具有建设性的贪婪 启发式等特点，它已经成功的应用于求解货郎担问题t s p ( t r a v e l i n gs a l e s m a n p r o b l e m ) ，引起了广泛关注。其次，组合优化问题具有很强的工程背景，如任务 分配问题( a s s i g n m e n t p r o b l e m ) 和j o b - s h o p 问题( 也称为车间调度问题) ，因此对组 合优化问题的研究有很高的实用价值。希望我们的研究既可以丰富蚂蚁算法的应 用研究，又可以为求解任务分配问题和j o b s h o p 问题提供更加可行、有效的算 法。 在第一章中，也就是本章中，我们首先提出了最优化技术的定义：因为蚂蚁 算法作为一种启发式算法，也就有启发式的明显特征和优点，然后我们介绍了启 发式算法的一些基本方面，包括：基本概念，设计方法，特点等；最后是本文的 主要内容和创新点。 在第二章中，主要介绍了组合优化问题的基本概念和求解组合优化问题的各 种方法，包括传统的局部搜索法、启发式算法( 模拟退火、遗传算法、紧急搜索 和人工神经网络) 和与蚂蚁算法密切相关的仿生算法( 人工免疫系统和粒子群算 法1 。 在第三章中，主要介绍了蚂蚁算法的基本概念。主要内容有：蚂蚁算法的仿 生原型，以货郎担问题t s p 为例介绍了蚂蚁算法的求解过程，蚂蚁算法的改进 算法和蚂蚁算法的应用研究及目前国内外研究现状。 在第四章和第五章中，主要介绍了将蚂蚁算法应用于求解任务分配问题和 j o b s h o p 问题，并且分别针对每个问题，对算法所出现的问题加以改进和提出了 新的思想。 在第六章中，也就是本文的最后章，对本文的研究工作做了总结，并且结 合实际的研究工作提出了展望，为进一步的研究提供了方向。 天津大学硕士学位论文第一章绪论 本文主要包括以下几个创新点： 首先：在用蚂蚁算法求解组合优化问题时，选择任务分配问题和j o b s h o p 问题，这就填补了国内外研究的空白，因为这两个问题尤其是j o b s h o p 问题属 于组合优化问题中最难的问题之一。在这两个问题上，蚂蚁算法的研究还属于空 白。 其次：求解任务问题时，我们引入了混沌函数扰动，避免算法陷入局部最小 的陷阱， 第三：在求解j o b s h o p 问题中，我们设计一种新的启发信息：最早允许加 工时间( e a p t ) ，并在算法中加入了适量的随机信息，使算法避免陷入局部最小的 陷阱取得了很好的效果。 天津大学硕士学位论文第二章组合优化问题的概述和常用解决方法 第二章组合优化问题的概述和常用解决方法 在这一章中，我们将对组合优化问题的基本理论和常用的解决方法作简单的 介绍。这些常用的解决方法与本文所研究的蚂蚁算法都有其各自的优点和缺点， 在许多共同的应用领域都可以互为补充、相辅相成，以弥补各自的不足。本章首 先介绍了组合优化的基本理论，然后介绍了求解组合优化问题的常用传统方法之 一的局部搜索算法，最后重点介绍并分析了几种启发式算法以及和近年来出现的 与蚂蚁算法密切相关的仿生算法。 2 1 引言 在人类几乎所有的社会活动中都有“寻优”的需求，将寻优的过程用数学模 型描述并求解，是2 0 世纪应用数学的重大进展之一。随着计算机科学的飞速发 展，针对离散变量的优化问题被逐渐重视，从而形成了有别于数学规划的另一类 重要模型，即组合优化( 离散优化) 。由于组合优化问题与大量的实际问题紧密 的结合，例如任务分配问题( a s s i g n m e n tp r o b l e m ) 是实际分配问题的抽象模型，车 间调度问题又称为j s p 问题( j o b s h o pp r o b l e m ) 直接研究车间生产的实际问题， 使得越来越多的人开始研究组合优化问题，提出许多新的方法和思路，使得组合 优化问题内容越来越丰富。组合优化问题的求解一直是近年来研究的热点领域之 2 2 组合优化问题的基本理论 2 2 1 最优化理论 最优化一般是指在某种状况下做出的决策或从几个候选者中选出最好的，这 种问题可以采用下面所叙述的数学模型1 2 1 ： “在给定的约束条件( c o n s t r a i n t ) 下，找出个决策变量( d e c i s i o nv a r i a b l e ) 的 值，使得被称为目标函数( o b j e c t i v ef u n c t i o n ) 的表达愿望尺度的函数达到最大值或 最小值。” 一般来说决策变量有多个，因此用n 维向量x = ( x t x o ) 7 来表示，可以把问 天津大学硕士学位论文 第二章组合优化问题的概述和常用解决方法 题写成下式： m i n ，( z )( 2 1 ) j s 其中：目标函数f ( x ) 是定义在包含s 的适当集合上的实值函数。可行域 s ( f e a s i b l er e g i o n ) 是该问题变量的可取值的集合。一般来说，可行域s 用于变 量工相关的等式及不等式表示，则最优化问题也可以表示为： m i n f ( x ) ( 2 2 a ) s t g 。( x ) 0 i = l f ( 2 - 2 b ) h ( x ) = 0j 1 m ( 2 2 c ) 其中：毋( x ) ，h j ( x ) 为约束函数。 满足约束条件互e s 的称为满足优化问题( 2 1 ) 的可行解( f e a s i b l es o l u t i o n ) ， 满足 f ( x ) ，( r ) ，( r s ) ( 2 - 3 ) 的可行解x s 称为问题( 2 。1 ) 的最优解( o p t i m a ls o l u t i o n ) 。另钋，在包含可行解 x + s 的适当邻域u ( x 。) 里，当 f ( x ) 厂( ) ，( x s n u ( x ) ) ( 2 - 4 ) 成立时，称x 为问题( 2 1 ) 的局部最优解( 1 0 c a l o p t i m a ls o l u t i o n ) 。有些问题的目标 函数和约束条件非常复杂，要找出在整个可行域中使目标函数达到最小的解非常 难，这时面临的目标就成为求出局部最优解。为区别式( 2 3 ) 的最优解与局部最优 解，称式( 2 - 3 ) 的最优解为全局最优解( g o b a lo p t i m a ls o l u t i o n ) 【2 1 ，记为x 8 。这里 所指的局部最优解是相对于全局最优解来说的，因为在涉及问题中，我们只是在 一个指定的局部区域内( 如u ( x ) ) 寻找局部最优解，而没有在整个可行解域 ( 如s ) 内寻找全局最优解，但同时在我们指定的区域内还有很多子区域，例如 u ( u c u ( x + ) ) ，每个子区域都有可能存在局部最优解( 如x ”) ，在很多情况下， x 与j 不一致，此时我们称x ”为局部最小陷阱。为了区别这些子区域上的局 部最优解x ，所以称在我们指定的区域内得到的局部最优解f 为最优解。 根据变量的类型，最优化问题( 2 1 ) 可以划分为两类：一类是变量取连续实数 的连续最优化问题( c o n t i n u o u so p t i m i z a t i o np r o b l e m ) ，另一类是变量取整数或类似 0 ，1 的离散数的离散最优化问题( d i s c r e t eo p t i m i z a t i o n p r o b l e m ) 。后者因为多用组 合性质来表示，也称为组合优化问题( c 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 ) 。本文将 研究重点放在组合优化问题。 组合优化问题有多种形式，把他们具体特征化的主要依据在其约束条件的结 构。一般来说，变量被限制取整数时的问题称为整数规划问题( i n t e g e r p r o g r a m m i n g p r o b l e m ) ，特别是当变量的值是0 或1 的时候称为0 - 1 规划问题( o 一1 p r o g r a m m i n gp r o b l e m ) ，背包问题就是o 一1 规划问题。另外，约束条件有关联图 天津大学硕士学位论文第二章组合优化问题的概述和常用解决方法 或网络给出的优化问题，例如：处理网络流的各种网络流问题( n e t w o r kf l o w p r o b l e m ) ，货郎担问题枷n gs a l e s m a n p r o b l e m ，t s p ) 等等。 2 2 2 组合优化问题 组合优化问题f 3 1 通常可描述为：令q = “，岛，晶) 为所有状态构成的解空 间，c ( s ) 为状态j 。对应的目标函数值，要求寻求最优解s ，使得v s ，q ， c ( s ) = 血n c ( 墨) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的 一个重要分支。 典型的组合优化问题有旅行商问题( 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 ) 、加工 调度问题( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b - s h o p ) 、o - 1 背包问题( k n a p s a c k p r o b l e m ) 、装箱问题( b i np 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 ) 等。这些问题其有很强的工程背景，数学描述虽然 简单，但最优化求解很困难，其主要原因是所谓的“组合爆炸”。例如，聚类问 题的可能划分方式有k “l k ! 个，j o b s h o p 的可能排列方式有( 行! ) ”个等等。因此求 解这些问题的关键在于寻求有效的优化算法，也正是问题的代表性和复杂性激起 人们对组合优化理论与算法的研究。 2 2 3 优化算法及其分类 所谓的优化算法口1 就是一种搜索过程或规则，它是基于某种思想和机制，通 过一定的途径或规则来满足用户要求的问题的解。 目前工程中常用的优化算法以优化机制与行为可分为：经典算法、构造型算 法、改进型算法、基于系统动态演化的算法与混合型算法。 ( 1 ) 经典算法包括线性规划、动态规划、整数规划和分支定界等运筹学中的 传统算法，其算法计算量一般很大，只适于求解小规模问题，在工程中 往往不实用。 ( 2 ) 构造型算法是用构造的方法快速建立问题的解，通常算法的优化质量 差，难以满足工程需要。例如，调度问题中的典型构造型方法有：j o h n s o n 法、p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、n e h 法等。 ( 3 ) 改进型算法，或称邻域搜索算法即从任意解出发，对其邻域的不断搜索 和对当前解的替换来实现优化。根据搜索行为，可分为局部搜索法和指 导性搜索法。 。 局部搜索法即以局部优化策略在当前解的邻域中贪婪搜索，如只接 受优于当前解的状态作为下一当前解的爬山法；接受当前解邻域中 天津大学硕士学位论文 第二章组合优化问题的概述和常用解决方法 的最好解作为下一当前解的最陡下降法等。 - 指导性搜索法即利用一些指导规则来指导整个解空间中优良解的探 索，如模拟退火( s a ) 、遗传算法( g a ) 、禁忌搜索( t s ) 、进化规划 ( e p , e v o l u t i o n a r yp r o g r a m m i n g ) 和进化搜索( e s ，e v o l u t i o n a r ys e a r c h ) 等。 ( 4 ) 基于系统动态演化的方法是将优化过程转化为系统动态的演化过程，基 于系统动态的演化来实现优化，如神经网络和混沌搜索等。 ( 5 ) 混合型算法值的就是将上述各算法从结构或操作上混合而产生的各类 算法。 2 3p 类问题，n p 类问题和n p c o m p l e t e 类问题 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和空 间的需求称为算法的时间复杂性和空间复杂性。问题的时间复杂性是指求解该问 题的所有算法中时间复杂性最小的算法的时间复杂性，问题的空间复杂性也有类 似的定义。按照计算复杂性理论研究问题的难易程度，可把问题分为p 类、n p 类和n p - c o m p l e t e 类 问题的复杂性一般表示为问题规模“如t s p 问题中的城市数) 的函数，时间 复杂性记为t ( n ) ，空间复杂性记为s ( n ) 。在算法分析和设计中，沿用实用性的复 杂性概念即把求解问题的关键操作，如加、减、乘、较等运算指定为基本操作， 算法执行基本操作的次数则定义为算法的时间复杂性，算法执行期间占用的存储 单元则定义为算法的空间复杂性。在分析复杂性时，可以求出算法的复杂性函数 p ( n ) ，也可以用复杂性函数主要项的阶o ( p ( n ) ) 来表示。若算法a 的时间复杂性 为l ( n ) = 0 ( j 口( 聍) ) ，且p ( n ) 为1 i 的多项式函数，则称算法a 为多项式算法。时间 复杂性不属于多项式时间算法统称为指数时间算法。 下面给出一些关于问题复杂性的定义和定理。 定义2 1 3 1 实例是问题的特殊表现，所谓的实例就是确定了描述问题特性的 所有参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实例的 输入长度。 定义2 2 【4 1 给定一个实例，即确定这个实例的目标函数c ( 丑) 和可行解集q 的一组数据，并给定一个常数工，是否存在一个可行解，使f ( x o ) ( ) 三? 判 定问题是用是或否来回答问题。 定义2 3 f qp 类问题指具有多项式时间求解算法的问题类。 天津大学硕士学位论文第二章组合优化问题的概述和常用解决方法 定义2 4 【3 t 若存在一个多项式函数g ( x ) 和个验证算法h 。对一类判定问题 a 的任何一个“是”实例i 都存在一个字符串s 是i 的“是”回答，满足其输入 长度d ( s ) 不超过g ( d ( i ) ) ，其中d ( i ) 为i 的输入长度，且验证算法验证s 为i 的“是” 回答的计算时间不超过甙d ( i ) ) ，则称判定问题a 为非多项式确定问题，简称n p 。 由此可见，判定问题是否属于n p 问题的关键是对“是”的判定实例是否存 在满足上述条件的一个字符串和算法，其中字符串在此可理解为问题的一个解， 而定义中没有强调字符串和算法是如何得到的。可见p c n p 。 定义2 5 h 1 如果4 和4 都是判定问题，而和屁是求解4 和4 的算法。如果 而是多项式算法，并且是多次以单位费用把屁作为子程序的算法，称4 在多项 式时间内归结为4 ，称以为4 到4 的多项式时间归结( p o l y n o m i a l t i m e r e d u c t i o n s ) i _ 已作4 4 。 定义2 6 f 3 1如果n p 类中所有的问题都可以多项式归约到n p 类某个问题 g r ，则称g l 是n p c o m p l e t e 问题。 定义2 7 p 1 如果某优化问题石的判定问题是n p c o m p l e t e 问题，则称问题石 是n p h a r d 问题。 由定义2 7 可知：n p c o m p l e t e c n p h a r d 。 定理2 1 1 3 1 如果问题丌n p ，那么存在个多项式p 使得石能用时间复杂 性为0 ( 2 “町) 的确定性算法求解，其中：n 表示实例的输入长度。 定理2 1 说明了n p 类问题属于可计算问题。 定理2 2 【3 1 如果确是n p c o m p l e t e 问题，n p ，且蜀可以多项式时间归 约到7 ，则毋是n p - c o m p l e t e 问题。 由以上定理及定义可知，如果某n p c o m p l e t e 问题有多项式时间算法，则 n p 类中所有的其他问题也有多项式时间算法，因此n p c o m p l e t e 问题是n p 类中 最难的问题。另一方面，如果个n p c o m p l e t e 问题没有多项式时间算法，则所 有的n p c o m p l e t e 问题也没有，因此所有n p c o m l e t e 问题具有同等难度1 5 1 。 n - p c o m p l e t e 问题具有重要的实际意义和工程背景，目前已有许多问题被_ 正 明为n p c o m p l e t e 问题，如背包问题( k n a p s a c k p r o b l e m ) 、任务分配问题( a s s i g n m e n t p r o b l e m ) 、j o b - s h o p 问题和f l o w - s h o p 问题、货自口担问题( t s p ) 等。 2 4 常用的传统方法 常用的求解组合优化问题的传统方法有很多种，在本节我们主要介绍与蚂蚁 算法紧密相关的局部搜索算法( l o c a ls e a r c h ) 嘲。 局部搜索算法是一种通用的近似算法，它是基于贪婪思想利用邻域函数进行 天津大学硕士学位论文第二章组合优化问题的概述和常用解决方法 搜索的，其基本法则可描述为：在邻近解中迭代，使目标函数逐步优化，直至不 能再优为止。局部搜索算法灵活、简便，能求解多种组合优化问题，并能给出较 好的近似解。 局部搜索算法的描述：从一个初始解i s 出发，然后运用一个产生器，持 续的在当前解i 的邻域s 中搜索比它更好的解，若能够找到比i 更优的解，就以 此为新的当前解，再对当前解继续算法；否则结束搜索过程，并以当前解作为最 终解。 下面给出伪p a s c a l 语言描述的求解最小化问题的局部搜索算法。 算法2 1 最小化问题的局部搜索算法l a p r o c e d u r el o c a i l s e a r c h ； b e g i n i n i t i a l i z e ( i o ) ； i ：= i 0 ： r e