（系统工程专业论文）捕食搜索及其在组合优化问题中的应用.pdf

篓苎查兰丝! ：兰丝堡兰 垫矍 捕食搜索及其在组合优化问题中的应用 摘要 由于社会生产活动变得越来越复杂，很多复杂问题用传统的数学规划 ( m a t h e m a t i c a lp r o g r a m m i n g ) ( 包括整数规划，i n t e g e r p r o g r a m m i n g ：动态 规划，d y n a m i c p r o g r a m m i n g ；线性规划l i n e a r p r o g r a m m i n g 和非线性规 划n o n l i n e a rp r o g r a m m i n g ) 已很难按照实际生产的需要进行优化。所以， 为了能有效地对这些问题进行优化，迫切需要优化速度快且误差在实际生 产允许范围内的算法。在这种情况下，各种启发式算法( h e u r i s t i c s ) 和智 能优化算法( a i b a s e do p t i m i z a t i o n a l g o r i t h m so rm e t a h e u r i s t i c s ) 应运而生。 本文介绍的就是智能优化算法中的一种一一捕食搜索( p r e d a t o r ys e a r c h ， 简称p s ) 。 捕食搜索来源于对动物捕食策略的模拟。动物捕食时，在没有发现猎 物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎 物；一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物 或者有猎物的迹象的附近区域进行集中的区域搜索，以找到更多的猎物。 在搜寻一段时间没有找到猎物后，捕食动物将放弃这种集中的区域，而继 续在整个捕食空i 自j 寻找猎物。 模拟动物的这种捕食策略。a l e x a n d r el i n h a r e s 提出了捕食搜索( p s ) 算法。捕食搜索策略寻优时，先在整个搜索空间进行全局搜索，直到找到 一个较优解；然后在较优解附近的区域进行集中搜索，直到搜索很多次也 没有找到更优解，从而放弃局域搜索；然后再在整个搜索空间进行全局搜 索。如此循环，直到找到最优解( 或近似最优解) 为止。 本文的研究工作主要包括以下几个方面。 首先对捕食搜索的优化过程、研究现状和优化条件进行了研究。然后 指出了捕食搜索的原始算法一一用函数值限制的捕食搜索算法( r e s t r i c t e d b ys o l u t i o nc o s t ) 的不足之处，提出了新的捕食搜索算法一一用距离限制 的捕食搜索算法( r e s t r i c t e db ys o l u t i o n d i s t a n c e ) ，并与原始算法进行了分 1 1 型唆塑堂型鲨一 塑 墨 析和比较。结果显示，无论是运行时间还是解的质量，用解之间的距离限 制的捕食搜索算法都或者优于用函数值限制的捕食搜索算法或者与之相 当。 本文的另外一项工作就是算法应用工作。实现了这两种p s 算法在经 典的组合优化问题( 如旅行商问题，流水车间问题等) 中的应用，并通过 大量的实验确定了能使算法保持高效率并且适合同一类中不同的问题的通 用算法参数。 此外，本文还进行了繁重的算法比较研究。针对不同的问题应用，把 这两种算法分别与其他经典的算法( 如遗传算法、禁忌搜索、模拟退火和 邻域搜索等算法) 进行了比较。结果表明。这两种捕食搜索算法优于其它 算法。 关键词：优化算法。仿生计算，捕食搜索( p s ) ，组合优化 i i 东北人学硼“i ：学位论文 p r e d a t o r y s e a r c ha n di t sa p p l i c a t i o n i nc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s a b s t r ac t w i t ht h ei n c r e a s eo f c o m p l e x i t yo fs o c i e t ya n dp r o d u c t i o n ，i tb e c o m e sm o r e a n dm o r ed i f f i c u l tf o rc l a s s i c a lm a t h e m a t i c a lp r o g r a m m i n g ( i n c l u d i n gi n t e g e r p r o g r a m m i n g ，d y n a m i cp r o g r a m m i n g ，l i n e a rp r o g r a m m i n g a n dn o n l i n e a r p r o g r a m m i n g ) t oo p t i m i z el a r g e s c a l er e a l w o r l dp r o b l e m s i no r d e r t oe f f i c i e n t l y s o l v et h e s ec o m p l e xp r o b l e m s ，i ti s u r g e n tf o rt h ea l g o r i t h m sw h o s es e a r c h i n g s p e e d i sf a s ta n dw h o s es o l u t i o nq u a l i t yi sa b l et os a r i s f yt h en e e do f p r a c t i c e a s a r e s u l t ，a l l k i n d so fh e u r i s t i c sa n da i b a s e d o p t i m i z a t i o na l g o r i t h m s ( m e t a h e u “s t i c s ) c o m eo u t i nt h i sp a p e r ，t h ea u t h o rw i l li n t r o d u c eo n eo ft h e s e m e t a h e u r i s t i c s p r e d a t o r ys e a r c h ( p s ) t h ep si sm o t i v a t e db yt h ep r e d a t o r ys e a r c hs t r a t e g yo fa n i m a l s w h e nt h e y s e e kf o rf o o d s ，t h e ys e a r c hi nac e r t a i nd i r e c t i o na taf a s tp a c eu n t i lt h e yf i n dap r e yo rg o o d e v i d e n c eo fi t t h e n ，t h e yw i l ls l o wd o w na n di n t e n s i f yt h e i rs e a r c hi ni t sn e i g h b o r i n ga r e a i no r d e rt of i n dm o r ep r e y s a f t e rs o m et i m ew i t h o u ts u c c e s s ，t h e yg i v eu pt h ei n t e n s i f i e d a r e a r e s t r i c t e d s e a r c ha n dg oo nt os c a no t h e ra r e a s s i m u l a t i n gt h ep r e d a t o r ys e a r c hs t r a t e g y o fa n i m a l s ，a l e x a n d r el i n h a r e s i n t r o d u c e dan e we v o l u t i o n a r y c o m p u t i n ga p p r o a c h ，n a m e l yp r e d a t o r ys e a r c h ( p s ) w h e nt h i sa l g o r i t h ms e a r c h e sf o rt h eo p t i m u m ，i ta tf i r s ts e e k si nt h ew h o l e s o l u t i o ns p a c eu n t i lf i n d i n ga “g o o d ”s o l u t i o n t h e n ，i ti n t e n s i f i e st h es e a r c hi n t h ev i c i n i t yo f t h e “g o o d ”s o l u t i o n a f t e rs o m et i m ew i t h o u tf u r t h e ri m p r o v e m e n t ， i tg i v e su pt h ea r e a r e s t r i c t e ds e a r c ha n dt u r n st ot h eo r i g i n a le x t e n s i v es e a r c h t h er e s e a r c ho ft h i sp a p e ri sm a i n l yc o n c e r n e do nt h ef o l l o w i n g ： f i r s t ，a f t e rs t u d y i n gt h eo p t i m i z a t i o np r i n c i p l e ，t h er e s e a r c hs i t u a t i o na n dt h e a p p l i e dc o n d i t i o n so fp r e d a t o r ys e a r c h ( p s ) ，t h ea u t h o rp o i n t so u tt h ed e f e c t so f t h ei n i t i a la l g o r i t h mr e s t r i c t e db ys o l u t i o nc o s ta n dp r o p o s ean e wa l g o r i t h mo f 东北人学坝十学位论文a b s t r a c t p r e d a t o r ys e a r c h r e s t r i c t e d b ys o l u t i o nd i s t a n c e t h e n ，t h e t w oa l g o r i t h m so f p r e d a t o r ys e a r c ha r ea p p l i e di nt h ec 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 m s ( c o p s ) ， s u c ha st h e t r a v e l i n g s a l e s m a np r o b l e ma n d f l o w - s h o ps e q u e n c i n g t h e n u m e r i c a lr e s u l t ss h o w e dt h a tm ya l g o r i t h me i t h e ro u t p e r f o r mo ra tl e a s tm a t c h t h ei n i t i a l a l g o r i t h m w h e t h e r c o n s i d e r i n g t h e r u n n i n gt i m e o fa l g o r i t h m s o r f o c u s i n go n t h eq u a l i t yo fs o l u t i o n s a n o t h e rw o r ko ft h i sp a p e ri st oa p p l yt h et w oa l g o r i t h m st os o l v ec o m p l e x p r o b l e m s t h ea u t h o rr e a l i z e s t h ea p p l i c a t i o no ft h e s et w oa l g o r i t h m si nt h e 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 m s ( c o p s ) ，s u c ha st h et r a v e l i n gs a l e s m a n p r o b l e ma n df l o w s h o ps e q u e n c i n g ，a n ds e t su pas e r i a lo fp a r a m e t e r st h a ta r e a d a p t i v ef o rv a r i o u sp r o b l e m st h r o u g hn u m e r o u se x p e r i m e n t s i na d d i t i o n ，t h et w oa l g o r i t h m sa r ec o m p a r e dw i t ho t h e ra l g o r i t h m s ，s u c ha s g e n e t i ca l g o r i t h m s ( g a ) ，s i m u l a t e da n n e a l i n g ( s a ) a n dn e i g h b o u rs e a r c h a l g o r i t h m s ( n s a ) t h er e s u l t ss u g g e s t t h a tt h es o l u t i o nq u a l i t yo ft w oa l g o r i t h m s o fp si sb e t t e rt h a nt h a to ft h eo t h e r s k e yw o r d s ：o p t i m i z a t i o na p p r o a c h e s ，e v o l u t i o n a r yc o m p u t a t i o n ，p r e d a t o r y s e a r c h ( p s ) ，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 m s ( c o p s ) v 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论 文中取得的研究成果除加以标注和致谢的地方外，不包含其他 人已经发表或撰写过的研究成果，也不包括本人为获得其他学 位而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 本人签名：是j 裂 日期：2 d 争乒j 月j 譬曰 东北人学硕l j 学位论史 第一市绪论 第一章导言 本章在简要介绍了问题的来源、研究目的、选题背景及意义之后， 对本文研究的算法一一捕食搜索 1 ，2 ，3 ，4 ，5 ，6 进行了简单的介绍 对本文要解决的问题一一组合优化问题 7 进行了简单的探讨。最后 对本文的研究技术路线和主要工作进行了简要介绍。 1 1 问题的提出 1 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 np r o b l e m s ， c o p s ) 。本文以旅行商问题( 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 ) 和流水 车间的调度问题( f l o w s h o ps e q u e n c i n g ) 为例探讨捕食搜索算法在组合 优化问题中的应用。此外，本文还以组合优化问题为背景把这两种捕食 搜索算法与其他经典算法进行了分析和比较。 1 1 2 问题的背景、特点与意义 组合优化问题是一类广泛应用的运筹学问题，有很多实际优化问题 可以归为组合优化问题求解。例如旅行商问题可以应用于交通运输、航 班调度、晶体结构分析、电路板的制作和基因排序等领域；而机器上的 加工工序、交通中的运输调度、学校中的课程设置、医院中的病床或手 变苎查兰堡：i ! = 兰笙堡兰星二至堕堡 术配置和c p u 处理进程的方案等最终都可以通过简化为流水车间调度 问题来解决。 组合优化问题在各行各业的广泛应用引起了人们的浓厚兴趣，在运 筹学、应用数学、计算机科学、生产管理科学、人工智能以及工程科学 等领域，大量新的文献不断涌现，由此可见组合优化问题的重要性。 大多数组合优化问题描述起来都很简单，但解决起来却很麻烦。对 于这些组合优化问题，当问题规模很小时，可以利用穷举法先求出问题 的所有解，然后再从中选出最优解。但当规模稍微大时，用穷举法解决 起来很困难甚至不可能。这是由于所谓的“组合爆炸”，对于有n 个城市 的t s p 问题，可能的排列方式由胛! 种，对于由m 个机器胆个工件的流 水车问问题，则有( 疗! ) ”种不同的排列。即使对于每秒钟能处理一亿种 排列的计算机，要穷举2 0 个城市的t s p 问题也要几百年的时间。由于 穷举法的求解效率很低，所以人们开始研究如何只搜索一部分解便能找 到最优解的方法。分支定界( b r a n c ha n db o u n d ) 【8 】、动态规划( d y n a m i c p r o g r a m m i n g ) 【9 等经典的数学规划方法 7 ，1 0 ，1 1 ，1 2 就在这种背 景下诞生了。由于这些方法只检查一部分解，计算量比穷举法小很多， 所以在问题的规模不是很大时，这些方法都能在很短的时间内找到最优 解。但当问题的规模很大时，其计算的工作量也很大。在数学上已经证 明，几乎所有的经典组合优化问题( 如旅行商问题，和流水车间的调度 问题) 都是n p c 问题 13 ，1 4 ，不能用这些现有的优化方法在多项式 时问内找到最优解。于是，如果想要满足工程的实时性需要，即要在很 短时间内实现优化，就必须舍弃寻找最优解而转以寻找近似最优解为目 标。在这种思想的指导下，产生了大量启发式算法和智能优化算法 i 5 。 最初，人们运用构造的方法( 如旅行商问题中的n e a r e s tn e i g h b o r 、 g r e e d y 、c l a r k e w r i g h t 和c h r i s t o f i d e s 等算法 1 6 ：调度问题中的j o h n s o n 、 p a l m e r 、g u p t a 、d a u n e u b r i n g 、c d s 和n e h 等算法 1 7 ) 快速产生问 题的可行解。这种方法虽然很快，但应用面窄，优化质量差，难以满足 工程的需要。后来又产生了改进型算法( 或邻域搜索算法) 它从任一解 出发，通过对其邻域进行不断搜索和以一定的方法替换当前解来实现优 化。根据当前解的替换方法的不同，它又可分为局部搜索法和指导性搜 索法。局部搜索法是以局部优化策略在当前解的邻域中进行贪婪搜索， 东北人学琐i 学位论文第一章绪论 如果只接受优于当前状态的解作为下一当前解则为爬山法 ( h i l l c l i m b i n go r n e x t a s c e n t ) ；如果接受当前解邻域中最好的解为下一 当前解则为最速下降法( f a s td e s c e n t ) 。指导性搜索法利用一些指导规 则来指导在整个解空间进行优化搜索，以找到全局解的近似解。有很多 经典的现代智能优化算法都采用这种方法寻优，如以概率选择策略或其 他选择策略选择下一当前解的遗传算法( e v o l u t i o n a r ya l g o r i t h m s ，g a ) 18 ，以一定概率替换当前解的模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 1 9 和记忆搜索过的局部最优解以避免下次再陷入次此局优点的禁忌 搜索( t a b us e a r c h ，t s ) 2 0 ，2 1 等等。此外，还有一种基于系统动态 演化的方法，将优化工程转化为系统动态的演化过程。神经网络( n e u r a l n e t w o r k ，n n ) 2 2 和混沌搜索( c h a o t i cn e u r a ln e t w o r k ，c n n ) 2 3 等算法都属于此类方法。另外，还有一种来自人工智能( a r t i f i c i a l i n t e l l i g e n c e ，a i ) 的算法一一约束规划( c o n s t r a i n tp r o g r a m m i n g ，c p ) 2 4 ，这种算法与上面的算法不同的是，它并不以求得问题的最优解或 近似最优解为目标，而以求得问题的满意解为目标。 本文要讨论的捕食搜索属于智能优化算法中的改进型算法中的指导 性搜索算法。 1 4 本文的主要工作和技术研究路线 本文主要探讨了两种捕食搜索算法以及它们在组合优化问题中的应 用，主要工作如下： 1 1 对捕食搜索进行了简单的介绍，然后分别介绍了两种捕食搜索算法， 并指出捕食搜索的应用条件。 2 1 对组合优化问题进行了介绍，并对问题的复杂性进行了简单的探讨。 3 1 把两种捕食搜索算法分别应用于旅行商问题，并对两种算法进行了 比较和分析。 4 1 把两种捕食搜索算法分别应用于流水车间调度问题，并对两种算法 进行了比较；然后，还与其它算法( 遗传算法、模拟退火和邻域搜 索) 进行了比较。 本文的技术研究路线如下： 东北人学颂二l 学位论文 第章绪论 捕食搜索算法及其在组合优化问题中的应用 土 数学规划、启发式算法以及智能优化算法的分类和应用 上 捕食搜索及其原始算法( r e s t r i c t e db ys o l u t i o nc o s t ) 上 提出以解之间的距离作限制的捕食搜索算法 ( r e s t r i c t e db ys o l u t i o nd i s t a n c e ) f + 组合优化问题的背景与意义 组合优化问题的分类和研究现状 ii ll ，丫 把这两种算法应用于求解旅行商问题 图1 1 本文的技术研究路线 东北大学烦| - 学位论文 第二章捕食搜索o 组合优化 第二章捕食搜索与组合优化 2 2 捕食搜索简介 2 2 1 捕食搜索的提出 捕食搜索( p r e d a t o r ys e a r c h ，p s ) ，是继遗传算法，蚁群算法 2 5 ，2 6 和p s o 算法【2 7 】之后的另一种进化算法。它由a l e x a n d r el i n h a r e s 在1 9 9 9 年的“p r o c i e e e n t c o n f s y s t ”国际会议上提出来的。 同其它进化计算方法一样。它也是对自然进化规律的模仿的结果。 但是，与一些从自然界的性质得到灵感的算法( 如遗传算法、模拟退火 和神经元网络等) 不同，它属于对自然界行为的模仿的一类算法( 如禁 忌搜索、蚁群算法和p s o 等) 。特别地，捕食搜索来源于对动物捕食策 略的模拟。 动物学家 2 8 3 3 在研究动物的捕食行为时，发现尽管出于动物物 种的不同而造成的身体结构的干差万别，但它们的捕食行为却惊人的相 似。动物捕食时，在没有发现猎物和猎物的迹象时在整个捕食空间沿着 一定的方向以很快的速度寻找猎物；一旦发现猎物或者发现有猎物的迹 象。它们就放慢步伐，在发现猎物或者有猎物的迹象的附近区域进行集 中的区域搜索，以找到更多的猎物。在搜寻一段时间没有找到猎物后， 捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻找猎物。如 图2 1 所示，动物的这种捕食搜索策略可以概括为以下两个搜索： 搜索l ( 全局搜索) ：在整个搜索空间进行全面搜索，直到发现猎 物或者有猎物的迹象而转到搜索2 进行局域搜索： 搜索2 ( 局域搜索) ：在猎物或者有猎物的迹象的附近区域进行集 中搜索，宜到搜索很多次也没有找到猎物而放弃局域搜索，转到搜索l 进行全局搜索。 动物学家的进一步研究表明，动物的这种捕食策略的效率是很高的。 这是由于，除了简单和通用的特性，此策略很好地平衡了对整个猎物空 蓬北大学碗 学自楚仓文第二章捕食搜索，组含优化 间的探索( 在整个解空间进行全面搜索) 和对猎物聚集区域的开发( 在 发现猎物的附近区域进行集中搜索) 。全面的搜索可以发现猎物聚集的区 域为集中搜索提供搜索的区域，并能避免陷入猎物稀少的区域；集中的 搜索可以再猎物集中的区域仔细地搜索猎物，防止漏掉猎物。由于捕食 者大部分时间用在猎物聚集区，而猎物聚集区相对于整个搜索空问更容 易发现猎物，所以动物的这种捕食策略是很高效的。 圈2 i动物的捕食策略 f i g 2 i t h ep r e d a t o r ys t r a t e g y o fa n i l r l a l s 图2 2捕食搜索算法 f i g 2 2 t h e a g o r i t h mo f p r e d a t o r ys e a r c h 模拟动物的这种捕食策略，a l e x a n d r e l i n h a r e s 提出了种新的仿生 计算方法，即捕食搜索( p s ) 。如图2 2 所示，捕食搜索寻优时，先在整 个搜索空间进行全局搜索，直到找到一个较优解；然后在较优解附近的 区域进行集中搜索，直到搜索很多次也没有找到更优解，从而放弃局域 搜索：然后再在整个搜索空间进行全局搜索。如此循环，直到找到最优 解( 或近似最优解) 为止。 2 2 2 捕食搜索的基本思想 局域搜索和全局搜索，广度探索和深度开发，搜索速度和优化质量 是三对困扰着所有算法的三对矛盾。而捕食搜索非常巧妙地平衡了这三 东北大学颂j j 学垡论文 第二章捕食搜索与纽台优化 对矛盾。 捕食搜索在较差的区域进行全局搜索已找到较好的区域，然后在较 好的区域进行集中地局域搜索，以使解得到迅速她改善：捕食搜索的全 局搜索负责对解空间进行广度探索，捕食搜索的局域搜索负责对较好区 域进行深度开发；捕食搜索的局域搜索由于只集中在一个相对很小的区 域进行搜索，所以搜索速度很快，捕食搜索的全局搜索可以提高搜索的 质量，使搜索避免陷入局部最优点。 2 2 3 捕食搜索与其它算法的比较 穷举法要搜索整个解空间才能找到最优点，搜索没有方向性，所以 搜索效率很低：爬山法只搜索更好的解而能使解快速得到优化，但却很 容易陷入局部最优点而且它本身没有能力摆脱局部最优点：禁忌搜索利 用记忆达到过的局部最优点，使算法不陷入局部最优点而使解能够得到 进一步的改善：模拟退火利用概率转移策略，允许搜索过程向不好的方 向移动，从而使其能够摆脱局部最优点并向全局最优点迈进。 和爬山法把搜索限制在沿着使当前解得到改善的方向进行相类似的 是，捕食搜索利用把搜索空问限制在一个较好的区域进行搜索( 当限制 达到最小时，捕食算法也只能向更好解的方向移动，这时它就退化成了 爬山法) ；但和爬山法不同的是，爬山法的当前解只向更好的方向移动。 而捕食搜索可以向一个较大的区域移动( 这个区域中的点有可能比当前 解差，但肯定要比限刳值好) ，而且随着限制值的增大，捕食搜索可以向 更宽广的区域移动( 当限制值达到最大时，捕食搜索的搜索区域就变为 整个解空间) ，所以捕食搜索就有了跳出局部最优点的能力，这点和禁忌 搜索、模拟退火类似。但和这些算法不同的是，捕食算法可以利用局域 搜索使解很快得到改善，这也是捕食搜索优于其它算法的地方。 2 2 4 捕食搜索的研究现状 a l e x a n d r el i n h a r e s 在提出捕食搜索的时候，同时提出了一种实现捕 食搜索的算法，然后把它应用于旅行商问题( t s p ) 和超大规模集成电 墨些苎兰塑! ：兰垡堡兰 至三至塑童墼室望型垒些! 兰 路设计问题( v e r yl a r g es c a l ei n t e g r a t e dl a y o u t ，v l s il a y o u t ) ，并取得 了很好的结果 1 ，2 ，3 。 幽2 3以解的函数值限制的捕食搜索算法的流群幽 f i g 2 3t h ef l o wc h a r to ft h ea l g o r i t h mo fp r e d a t o r ys e a r c hr e s t r i c t e db ys o l “t i o “ c o s t 8 - 垄韭查兰堡兰：堂垡堡塞 丝三童塑堡墼墨! ! 塾垒垡些 该算法采用解的函数值来限制局域搜索的搜索空间，使算法只搜索 该局域搜索就能使解得到改善。它的限制条件是通过搜索最好解x + 的邻 域获得的。可以通过多次搜索z + 的邻域获得一组限制值，进行分解限制。 由于该算法的限制值是通过最好解x + 计算的，所以每当最好解得到改善 时，该算法的限制条件就要重新计算一次。该算法的具体流程如图2 3 所示。 2 2 5 捕食搜索的应用条件 无可否认，只有当猎物聚集时，捕食者采用这种策略效率才高。可 以想象，当猎物分布很扩散而且没有规律时，捕食者进行局域搜索只能 无功而归。同样，捕食搜索也只有在较好解聚集时才有效。特别当较好 解聚集于全局最优点时，捕食搜索的搜索效率很高。 a w 、d t1 4 t a l c ol f o n ln “l e tl o c a l l l l t l 1 m - i ( l ) t s t a n c t ；, t 0b e s ti ( k a ln i i f i i l l l i i o ( 剀24 ( a ) 表达的是1 0 0 个城市的旅行商问题的2 5 0 0 个局部虽优解平| i 它们的平 均最优解之间的距离与它们各自的函数值之间的关系；图2 ，4 ( b ) 表达的是这2 5 0 0 个局部最优解中的展蚶解和其余2 4 9 9 个点之间的距离与这2 4 9 9 个点的函数值之 间的关系。 f i g 24 ( a ) a n a l y s i s o f2 5 0 0r a n d o ml o c a lm i n i m af o ra1 0 0 c i t ye u c l i d 。8 “t s p i n s t a n c e t o urc o s ( ( v e r t i c a la x i s ) i sp l o t t e da g a i n s t ( a ) a v e r a g ed i s t a n c ef r o mt h e 一9 一 至韭查兰塑! ：兰垡笙苎； 兰三望塑童堡窒、! 型堂垡些 o t h e r2 4 9 9l o c a lm i n i m aa n d ( b ) d i s t a n c ef r o mt h el o c a lm i n i m u mw i t hl o w e s tc o s t a | l 2 5 0 0i o c a im j n i m aa r ed i s t i o c t a v ed i s l ；1 1 1 【nr ，1 1 1o ij 】p ii o t a lm i n i m a 1 ) i s t a l c et ob ( - s fk f , d m i n j i i ll 1 1 1 n 砖 幽2 ，5 ( a ) 表达的是g ( 15 0 ，0 s ) 的二分图问题钓2 5 0 0 个局部最优解和它们的平均 晟优解之间的距离与它们各自纳函数值之问的关系：国2 5 ( b ) 表达的是这2 5 0 0 个局部最优解中的是好解和其余2 4 9 9 个点之间的距离与这2 4 9 9 个点的函数值之 同的笑系。 f i g u r e2 5 ( a ) a n a l y s i so f2 5 0 0r a n d o ml o c a l l ym i n i m u mb i s e c t i o n sf o rg r a p hi n g ( 15 0 ，05 ) t h ed a t ar e p r e s e n t2 3 9 9d i s t i n c tl o c a lm i n i m a u c l a 的k e n n e t hd b o e s e a n d r e wb k a h n g ，和s u d h a k a rm u d d u 3 4 】利用贪婪算法( g r e e d yd e s c e n ta l g o r i t h m ) 求解了1 0 0 个城市 e u c l i d e a n 旅行商问题的2 5 0 0 个局部最优解和g ( 15 0 ，0 5 ) 的二分图问题 的2 5 0 0 个局部最优解，如图2 4 ( 旅行商问题) 和2 5 ( 二分图问题) 所示，并分别分析了这两个问题的2 5 0 0 个局部最优解之间的关系( 它们 的各自的巡游路线长度和它们之阅的距离的关系) ，得出结论：旅行商问 题和二分图问题的较好的局部最优解聚集于全局最优解。 东北人学坝l j 学位论文 第二章捕食搜索0 组合 兄化 幽2 6 流水车间问题的5 0 个局部擐优解和全局最优解之间的距离与它们的函数 值之间的关系 f i g 2 6a n a l y s i so f5 0r a n d o ml o c a l l ym i n i m u m s o l u t e i o na n dt h eg l o b a lm i n i m u m s o l u t i o n 此后，c o v e n t r y 大学的c r r e e v e s 【3 5 求解了2 0 5 f c 的流水车 间问题的5 0 个局部最优解，然后分析了它们的函数值与它们和已知的全 局最优解的距离之间的关系，如图2 6 所示，并得出了相同的结论。 由此，我们可以得出结论：捕食搜索是适合于求解旅行商问题 ( t r a v e l i n gs a l e m a np r o b l e m ，t s p ) ，二分图问题( g r a p hb i s e c t i o n ) 和 流水车间问题( f l o w s h o ps e q u e n c i n g ) 等组合优化问题的。 2 。3 组合优化问题简介 组合优化往往涉及排序、分类、筛选等问题，组合优化问题，它是 运筹学的一个重要分支。他的研究对象是离散变量，它的研究目标是从 一个无限集或者可数的无限集里寻找一个最优的对象，这个对象可能是 一个整数。一个集合，介排列，或者一个图。 组合优化问题通常可描述为：令口= s ，s 。，如) 为所有状态构成的 解空问，c ( s 。) 为状态s ，对应的目标函数值，要求寻找最优解s + ，使得v s i 1 1 东北 学碗4 l ：学位论文 第二章捕食搜索1 j 组台优化 口，c ( s + ) = m i n c ( s ，) 。 典型的组台优化问题有旅行商问题( t r a v e l i n g s 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 ) 、0 1 背包问题( k n a p s a c kp 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 ) 等。 2 3 1 问题的复杂性 出于有些优化算法所需的计算时问和存储空间难以承受，因此算法 可解的问题在实践中并不一定可解。如对称t s p 问题，可能路径为 ( 1 ) ! ，2 ，若以路径比较为基本操作则需( h 1 ) ! ，2 1 次基本操作。对于 每秒执行一百万次操作的计算机当月= 2 0 时就需1 9 2 9 年刁能找到最优 解。所以，我们必须对计算复杂性理论有所了解，才能有针对性地设计 算法。进而提高优化效率，这也是最优化的理论基础。 i 算法的复杂性 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对 时间和空间的需要量称为算法的时间复杂性和空间复杂性。问题的时间 复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂 性，问题的空间复杂性也可类似定义。按照算法复杂性理论研究问题求 解的难易程度，可把问题分为p 类、n p 类和n p 完全类。 算法或问题的复杂性一般表示为问题规模”( 如t s p 问题中的城市数) 的函数时间复杂性记为t ( n ) ，空间复杂性记为s ( n ) 。在算法分析和设 计中沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、 乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算 法的时自j 复杂性，算法执行期间占用的存储单元则定义为算法的空间复 杂性。在分析复杂性时，可以求出算法的复杂性函数p ( n ) ，也可用复杂 性函数主要项的阶0 ( p ( 疗) ) 来表示。若算法a 的时间复杂性为t 。( n ) - - - - 0 ( p ( n ) ) ，且p ( ，z ) 为n 的多项式函数，则称算法a 为多项式算法。时间复 杂性不属于多项式时间的算法统称为指数时间算法。 i i 问题的复杂性( p ，n p ，n p c 和n p - h a r d ) p 类问题指具有多项式时间求解算法的问题类。但迄今为止，许多 东北人学碗1 ：学位论义 第二章捕食搜索棚l 台优化 优化问题仍没有找到求得最优解的多项式时间算法，通常称这种比p 类 问题更广泛的问题为非多项式确定问题，即n p 问题。n p 的概念通常由 判定问题引入，下面介绍相应的若干概念。 定义1 1实例是问题的特殊表现，所谓实例就是确定了描述问题 特性的所有参数的问题，其中参数值称为数据，这些数据占有计算机的 空i 称为实例的输入长度。 定义1 2 若一个问题的每个实例只有“是”或“否”两种回答则 称陔问题为判定问题，并称肯定回答的实例为“是”实例否定回答的 实例为“否”实例或非“是”实例。 定义1 3 若存在一个多项式函数g ) 和一个验证算法h ，对一类判 定问题a 的任何一个“是”的判定实例，都存在一个字符串s 是，的“是” 回答，满足其输入长度d ( 国不超过g ( d ( d ) ，其中d ( d 为，的输入长度， 且验证算法验证s 为j 的“是”回答的计算时间不超过g ( 碳d ) ，则称判 定问题a 为非多项式确定问题，简称n p 。 由此可见判定问题是否属于n p 的关键是对“是”的判定实例是 否存在满足上述条件的一个字符串和算法，其中字符串在此可理解为问 题的一个解，而定义中没有强调字符串和算法是如何得到的。可见， p n p 。 归约和转换是描述问题特性的常用方法。如果能够将几类问题归结 为一个问题，则一旦解决了一个归结后的问题其他几类问题也就解决 了。 定义1 4 给定问题a 。和a ，称4 ，可多项式转换为a ：，若存在一 个多项式函数g ( z ) 和一个字符串，满足：( 1 ) 对a 。的任何一个实例，。，在 其输入长度的多项式时间g ( d ( 1 ，) ) 内构造a ：的一个实例：，使其长度不 超过g ( d ( 1 ；) ) ；( 2 ) 由此构造使得实例，和：的解一一对应，且d ，为，的 “是”回答的充要条件为d 。对应的解是，的一个“是”回答。 定义1 5给定判定问题a 和a ，称爿可多项式归约为a ，若存 在多项式函数g ( x ) 和g ：( x ) ，使得对a 的任何个实例，在多项式时 问内构造爿：的一个实例，其输入长度不超过g 。( 烈d ) ，并对a ：的任何一 个算法h ，都存在问题a 的一个算法日，使得h 调用：且计算时间 f 。( d ( d ) g2 ( h ，( g ( d ( ，) ) ) ) 。 东北人学坝1 1 学位论文 第二章捕食搜索与组台优化 由此可见，若问题a ，存在多项式时间算法，则问题a 一定存在多 项式时间算法。若问题a ，可多项式转换为问题a ，对a ，的一个算法 h ，可按如下步骤构造a ，的算法： t ) 对问题爿。的任何一个实例，先用多项式时间g 。( d ( 1 ) ) 构造问 题爿，的一个实例j ，； 2 ) 调用算法日：求解，：，此步计算时间为，。，( g ，( a u ，) ) ) 。 如此构造的算法对问题a i 的任何一个实例，。的计算时间不超过g ， ( d u 。)