（运筹学与控制论专业论文）智能优化算法在中值选址问题中的应用研究.pdf

大连理工大学硕士学位论文 摘要 选址问题是运筹学中的经典问题之一，在生产生活中有着广泛的应用。自选址问题 提出到现在，经历了1 0 0 多年的历史，获得了广泛的研究目前，关于选址问题的研究 主要集中在选址模型的扩展和求解算法的设计上。本文主要研究智能优化算法 ( i n t e l l i g e n t o p t i m i z a t i o n a l g o r i t h m s ) 在经典的p 一中值选址问题求解中的应用。 第一章介绍了设施选址问题的背景，包括设施选址问题的意义、发展过程、经典分 类以及现有成果，并阐述了本文的主要工作。 第二章给出了p 一中值选址问题的基本定义形式和广为使用的经典整数规划模型。 第三章重点介绍了智能优化算法中的禁忌搜索算法和遗传算法。详细介绍了两算法 的基本流程和关键参数及这些参数对整个算法性能的影响，并概括了两算法各自的特 点。 第四章集中研究了禁忌搜索算法及遗传算法在无容量约束p 一中值选址问题与有容 量约束p 一中值选址问题中的应用。分别选用两个著名的有效算法，在已有算法流程基 础上，针对算法存在的一些问题。研究如何进一步合理的提高原有算法往能。禁忌搜索 算法的研究以r o l l a n d 等人提出的有效禁忌搜索算法为基础，分别对算法的初始解、评 价函数、禁忌信息等参数做了改进尝试，并提出了一种以目标函数差值为评价函数的改 进禁忌搜索算法。通过理论分析和数值试验结果比较，验证了改进算法的可行性。基于 o s m a n 等人提出的有效遗传算法，根据“优胜劣汰，适者生存”的原理，提出了在交叉 操作中采用一种新的双亲选择机制，有效的改进了原有算法的效率。同时，给出了如何 设计求解有容量约束p 一中值选址问题的禁忌搜索算法与遗传算法的实例。 最后，总结全文，指出了目前中值问题研究中存在的一些问题及未来可行的研究方 向。 关键词：智能优化算法；p 一中值问题；禁忌搜索算法；遗传算法；现代启发式算法 大连理工大学硕士学位论文 i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m sf o rt h ep - m e d i a np r o b l e m a b s t r a c t l o c a t i o np r o b l e m sa r et y p i c a li no p e r a t i o n sr e s e a r c h i te x i s t se v e r y w h e r e i th a sb e e n s t u d i c d 晰d e l yf o ra l m o s to n eh u n d r e dy e a r ss i n c ei tw a sd e v e l o p e d p e o p l er e s e a r c hh o w t o i m p r o v et h el o c a t i o nm o d e l so rb o w t od e s i g nr i g h ta l g o r i t h m sf o rc o r r e s p o n d i n gm o d e l s 舷p a p e r s t u d i e sm a i n l ya b o u tt h ea p p l i c a t i o no fi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m sf o rt h e p - m e d i a np r o b l e m , w h i c h i so n eo f t h em o s tt y p i c a ll o c a t i o np r o b l e m s p a r to u ei n t r o d u c e st h eb a c k g r o u n do ff a c i l i t yl o c a t i o np r o b l e m s ，i n c l u d i n gt h e s i g n i f i c a n c e ，e v o l u t i v es t a g e s ，蛳c a lc l a s s i f i c a t i o n , a n dp r e s e n tr e s e a r c hs t a t u s ，f o l l o w e db y t h em a i nr e s e a r c ho f t h i sp a p e r p a r tt w om e n t i o n sb a s i cd e f i n i t i o na n dw i d e l yu s e di n t e g e rp r o 铲a m m i n gf o r m u l a t i o no f t h ep - m e d i a np r o b l e m s i np a r tt h r e e ，hd e s c r i b e si nd e t a i l0 1 1t h eb a s i cp t - o c c d b r e s ，c r i t i c a le l e m e n t sw i t hc r u c i a l i n f l u e n c eo nt h ep e f f o m m r x s ，a n dg e n e r a lc h a r a c t e r i s t i c so ft h et a b us e a r c ha l g o r i t h ma n d 掣舭a l g o r i t h mo f i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s i np a r tf o u r , i tc o n c e n t r a t e ss p e c i a l l yo nt h ea p p l i c a t i o no ft a b us e a r c ha l g o d t h r aa n d g e n c t i ca l g o r i t h mi ns o l v i n gt h ep - m e d i a np r o b l e m b a s e do ne x i s t e da l g o r i t h m s ，an e w m p r o v i n gt a b us e a r c ha l g o r i t h mf o r 璩a p a c i t a _ t c dp - m e d i a np r o b l e mi sp u tf o r w a r d , w h i c h u s e so b j e c t i v ef u n c t i o nd i f f e r e n c e 鹤e v a l u a t i o nf u n c t i o ni n s t e a do fo b j e c t i v ef u q g t i o ni n o r i g i n a lr o l l a n de f f i c i e n tt a b us e a r c ha l g o r i t h m i ta l s op r o p o s e s a l li m p r o v i n gg e n e t i c a l g o r i t h ma c c o r d i n gt ot h ee v o l u t i o n a lp r i n c i p l ef o rt m c a p a c i t a w dp - m e d i a np r o b l e m ，w h i c hi s b a s e do no s m a ne tc l s e f f i c i e n tg e n e t i ca l g o r i t h m t h e yd i f f e ri nt h es e l e c t i n go fp a r e n t so f c r o s s o v e ro p e r a t o r n u m e r i c a li n s t a n c 鼯s h o wt h a tb o t ht w oi m p r o v i n ga l g o r i t h m sp e r f o r m b e t t e rt h a no r i g i n a | a l g o r i t h m s i ta l s os h o w sh o wt od e s i g nt a b us e a r c ha l g o r i t h ma n dg e n e t i c a l g o r i t h mf o rt h ec a p a c i t a t e dp - m e d i a np r o b l e ma tt h ee n do f t h i ss e c t i o n t h ei a s tp a r tc o n c l u d e st h er e s e a r c ho ft h i sp a p e ra n dp r e s e n t st h ef u t u r er e s e a r c h0 1 1 p - m e d i a np r o b l e m s k e rw o r d s ：i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ；p - m e d i a np r o b l e m ：t a b u s e a r c ha l g o r i t h m ： g e n e t i ca l g o r i t h m ；m e t a - h e u r i s t i ca l g o r i t h m s - i i i - 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：二茎赴日期- 孕l 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交 学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：坌窒盏 导师签名盈毖丝 汗j 月- 妇 大连理工大学硕士学位论文 1 绪论 1 1 设施选址问题提出 选址问题在生产生活、物流、军事中都有着非常广泛的应用，涉及内容十分广泛。 从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住 区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，跨越经济、 政治、社会、管理、心理及工程地质等多门学科。选址的好坏直接影响到服务方式、服 务质量、服务效率、服务成本等。好的选址会给人民的生活带来便利，降低成本，扩大 利润和市场份额，提高服务效率和竞争力；差的选址往往会带来很大的不便和损失，甚 至是灾难。所以，选址问题的研究有着重大的意义。 设施选址问题是选址闯题中的一个重要研究领域，是运筹学的经典问题之一。通常， 设施选址是指与生产、商业流通及人类生活相关的、用地规模相对较小的场所、网点的 地址选择。1 9 0 9 年，w e b e r 研究了在平面上确定一个仓库的位置使得仓库与多个顾客之 间的总距离最小的问题( 称为w e b e r 问题) i n ，正式开始了选址理论的研究。在选址问题 发展的百年历史中，按时间可分为三个阶段：( 1 ) 零散研究阶段( 1 9 0 9 1 9 6 0 s ) 。该阶段 研究侧重于解决生产、生活中的各种实际问题，内容零散。经济学者在此阶段的早期有 突出贡献。最早的选址问题是w e b e r 问题，i s a r d 于1 9 5 6 年结合工业选址、土地使用和 相关问题对该闯题重新进行了研究。h o t e l l i n g 于1 9 2 9 年提出了一条直线上两个竞争供 应商的区位选择问题1 2 】，s m i t h i e s 与s t e v e n s 后来对这一问题进行了扩展。上世纪5 0 年 代和印年代，越来越多的研究者偏重予设施布置和设计问题，包括产品销售网点的分布 与设计、消防设施选址、垃圾处理厂选址、铁路货运编组站选址等。( 2 ) 系统研究阶段 ( 1 9 6 0 s 一1 9 8 0 s ) 。h a k i m i p l ：j ：1 9 6 4 年发表的关于网络多设施选址的论文是将设施选址问 题发展为一个系统、科学理论的里程碑。此后，选址问题被引入一个更宽广的领域，包 括生产中心选址、交通枢纽选址、变电站选址等等。研究方法也更集中于运筹学、拓扑 学，而经济学方法的应用越来越少。( 3 ) 不确定性闷题研究阶段( 2 0 世纪8 0 年代以后) 。 2 0 世纪8 0 年代后，随着市场变化加剧，实际生产生活中运输时间、需求量、需求空间分 布以及设施建造成本等因素不确定性加强，以往静态、确定性选址模型与方法已不能适 应选址研究的发展。随机选址问题已成为众多学者关注的焦点。l o u v e a u x l q 、w e a v e r l 5 i 等 学者在研究不确定中值问题时，均将运输时间与需求设为随机变量。b e r m a n 与o d o n i 、 b e r m a n 与l e b l a n c 分别研究了运输时间或运输成本为不确定系统变量的随机网络交通 问题伍一。 1 2 设施选址问题的经典分类 设施选址问题的分类方法很多，不同的评价标准会有不同的分类方式，如可以分为 1 智能优化算法在中值选址问题中的应用研究 单目标选址与多目标选址，受欢迎的设旅选址与不受欢迎的设施选址等 s - 1 0 j 。根据设旌 允许安置的空间或是决策变量的特征，可将设施选址问题分为连续选址、网络选址和离 散选址。 ( 1 ) 连续选址 又称为平面选址，它允许在可行的某一平面内连续选取位置值。平面上连续选址模 型主要有两大特征：一是决策变量是连续的，即可以将设施建在平面上的任何一点；二 是采用适当的度量方法度量距离，如比较常用的厶距离( 也称直角距离) 、厶距离( 也称 欧氏距离) 和匕模距离。韦伯提出的w e b e r 问题就是一个典型的连续选址问题。 ( 2 ) 离散选址 离散选址问题即候选设施点的区位是离散的，决策变量是在有限点集中取值。此类 闯题往往假定设旌点与需求点都位于网络节点上。其中，需求点的区位是确定的，需求 点有需求量，需求点与候选设施点之间有连线( 如交通线路、网线) 相连。最经典的无容 量约束的工厂选址问题( 1 ku n c a p a c i t a t e ap l a n tl o c a t i o np r o b l c r n ，u p l p ) ，也称作简单工 厂选址问题( t h es i m p l ep l a n tl o c a t i o np r o b l e m 。s p l p ) ，有容量约束的工厂选址模型( t h e c a p a c i t a t e dp l a n tl o c a t i o np r o b l e m ，c p l p ) 等都是离散选址问题。 ( 3 ) 网络选址 网络选址问题在物流设施规划、通讯系统设计等诸多邻域都有十分广阔的应用背 景。网络选址问题要求在某个网络上设置若干个服务中心，以达到特定的目的。例如， 城市中设置若干个1 1 9 消防站，以使到达最远的报警点的时间尽可能地短。又如物流配 送中心的选址，以便配送商品到所有超市的总的距离最短。网络选址允许在指定网络的 顶点与边上选址，而离散选址只允许在指定的一些离散点集上选址，两者主要用组合优 化方法研究。网络选址下的中值问题、覆盖问题、中心问题是网络选址的三个基础选址 问题。 1 3 中值选址问题研究现状 在1 9 世纪6 0 年代中期以前。选址理论的研究工作是在几个不相关的领域内展开的， 并没有形成统一的理论。1 9 6 4 年，h a k i m i 对选址问题进行了更加理论化的研究，考虑了 带有一股性的问题：在一个网络中选定一个或多个设施的位置，使得总距离或设施与点 之闯的最大距离最小。此后，选址问题提得到了广泛的研究，文献数目急剧增多。h a l e 在文献【1 1 中列出了截止到2 0 0 4 年3 月的3 4 0 0 多个关于选址问题理论研究的文献，文献 4 - 2 0 分别综述了选址研究取得的一些成果。 网络上的p 一中值问题可以分为绝对p 一中值问题( 设施可以安置在网络上的任何 地方) 和顶点p 一中值问题( 设施只能安置在网络的顶点上) 。h a k i m i 在提出网络上的p 一 中值问题时给出了一个著名的顶点最优性质：网络上的p 一中值问题至少有一个最优解 2 大连理工大学硕士学位论文 完全由网络的顶点构成【3 】。根据这种性质，可以把求解网络选址闯题在某种意义上归结 为求解离散选址问题，大大的缩小了解的搜索空间，且对网络上的p 一中值选址问题一 般不加区分。c o o p e r 2 1 1 研究了不仅在网络中选择设施区位，而且确定设施在网络中的服 务范围g o i d m a n 探讨了在树状网上如何选择一个设施点的中值问题 2 2 j ，具体方法为： 首先任选一个节点，计算该点的权重是否超过所有权重一半，如果是，则为中值点：否 则，该点权重被计算在相邻点上，直到找到中值点为止。z e l i n k a 田j 证明在无权重的树 中，树的中值与质心相同。k a r i v 和h a k i m i 则证明了在有权重的树中，中值与质心相同 刎。r e v e l l e 与s w a i n ( 1 9 7 0 年) 提出了p 一中值问题广为使用的整数规划模型【2 朋。 2 0 世纪7 0 年代末以前，绝大多数学者构建的中值问题模型都为静态、确定型，即客 户需求、运输时间、建设成本等变量均为确定值，这一假设与实际情况往往不符。动态 的和随机性的问题由于更符合现实特征，越来越引起人们的重视。文献【6 】综述了这方面 的研究成果。文献 2 6 1 首先指出了静态和确定性的选址模型的不足，并首次把动态规划 引入选址问题。从此，动态p 一中值问题 2 7 1 、随机p 一中值问题【嚣】得到了广泛关注和研 究。自从l a r s o n p 9 1 首次把排队论引入选址问题后，许多随机排队选址模型【3 0 f 3 1 1 相继建 立。模糊数学也被引入选址问题，出现了模糊中值问题和模糊中心问题。另外，还有条 件p 一中值问题、条件p 一中心问题、反p 一中值问题( 最大和目标函数) 等。根据这些 研究内容，可将中值选址问题的随机模型概括为以下三类： ( 1 ) 概率模型。 概率模型可分为需求随机模型与交通运输随机模型。c a r b o n e 在文献 3 2 】中研究了 需求不确定的公共设施选址问题。该文假设需求是多变量正态分布，利用非线性确定性 方程的多变量分析结果，构造了机会约束规划( c h a n c e - c o n s t r a i n e dp r o g r a m ) m i r c h a n d a n i p 3 】用马尔可夫随机过程对无能力约束的仓库区位进行研究，供给与需求及 运输时间都是随机变量。b e a n m 1 以m a n n e 的模型为基础，研究需求随机增长情况下的设 施生产能力扩张问题。此模型假设需求是非线性的布朗运动或是非马尔可夫生灭过程。 用确定性需求替代随机需求，将随机方程转化为确定性方程。l o u v e a u x 与p e e t e r s 【4 】研 究有能力约束的随机需求选址问题。m i r c h a n d a n i 与o d o n i p 副在h a k i m i 模型的基础上研 究具有离散概率交通线路的随机网络模型，不仅证实h a k i m i 在随机网络中也存在选址 最优解的命题为真，而且证明当运输时间的效用方程为凸时( c o n v e x ) ，在无方向的随机 网络上至少有一个最优集。c h u r c h 与w e a v e r l 5 1 用线性整数规划与拉格朗日松弛变量计算 o d o n i 等人构建的模型。b e r m a n 与o d o n i 3 6 1 扩展了m i r c h a n d a n i 和o d o n i 构建的模型。 ( 2 ) 情景模型。 情景模型是研究在一系列具有发生概率的情况下的设施可靠区位的选址问题。有些 文献假设所有情景发生的概率是相等的，而一些文献中的情景概率则通过计算得出。 k o u v e l i s 与y u 3 7 l 研究在树状网络上的一个设施点的区位问题，节点需求与线路长度随 3 智能优化算法在中值选蚍问题中的应用研究 露鬻线性交纯，溺辩馁设获有傍景穰率程等，嚣振函数是求最大邃穗健( r e g r e t ) 熬焱 小值。a v e r b a k h 与b e r m a n 弘 在上述研究基础上将网络树扩展为一般网络并提供了一个 多项妓算法。l a g u n a 3 9 1 利用情景模型研究基予时间的背包问题，模型分两阶段求解，第 一阶段为递推动态烧翅，第二盼羧薅最短路径求簿。 ( 3 ) 摊驮模型。 概率模型中的些参量引谶排队模型理论。l a r s o n 2 9 1 首先将排队论戍用在选址模型 中，奎娶研究紧急救助组织的率辆区位与服务范围，基于区内、区际阃呼救时间呈泊松 壤率分鑫、瓣务霹瓣羧麸指鼗分黍豹蔻据务绛，梅建了一令多驻务者捺酞篆统。b r a n d e a u 与c h i u 4 0 ! 研究单个设施的随机摊队区位问题，考虑排队与交通时间延迟情况下服务客 户的最短反应时间。 选缝闫题熬求麟方法大致霹分为定性和定爨两类。定蚀豹方法主要怒缝合层次分耩 法和搂糊综合法霹备方案进行指标洋侨，筏蹈袋优选缝：窥爱的常震方法爨f j 是松弛算法 和启发式算法以及两者的结合应用【4 l l 。由于p 一中值选址问题可以写成黢数线性规划的 形式，所以可以用线性规划技巧、整数规划按巧年日松弛方法来求解。此外，入们也提出 了一黧整发式求艇冀法。鬻矮鹣一些求解方法毯疆萋予簿耩豹多除羧濠、分棱定雾法、 对偶定界法等耻”。冀他的如近视算法( m y o p i ca l g o r i t h m ) 、交换启发式辫法、邻域搜索 算法等窟发式算法和l a g a a g i a n 松弛算法等【9 】。近视算法熙一种构造型冀法，有点类似 于贪婪雾法，它不鬻要初始解就霹以绘出一个较好豹辫( 拳努是最优解) 。交换算法秘 邻域援索算法都是敬迸墅算法，鞠对给定鹃裙始解迸行改遴，透常蘸者瓣改进效栗好予 后者。l a g r a n g i a n 松弛算法是通过松弛p 一中假问题中的约柬条件得到个松弛问题， 交替求解松弛问题与修正n a m a n g i 勰乘子，煮强l 求褥一个满足要求的解。以上算法中， 逶豢l a g r m g i 鲢松魏方法是最努鹣，不莰簿静震差毫，瑟纛戆给密最饶瓣黪主下葬，获 而能评价解的质量；但浪费的时间较多，而融得不到从卜中值到p 一中德闯题的解。缀 然前三种算法得不到好于b 盯a n 毓m 松弛方法的解，但在求解的过程中可以自动得到从 l 一孛毽潮p 一孛缓 蠢瑟戆簿。 诧外，动态规划启发式算法f 1 2 l 、启发式集中算法( h e u r i s t i cc o n c e n t r a t i o n ) 嘲l 、w 变邻域搜索算法m ，4 酆、分散搜索岛路径重联算法【撕】、禁忌搜索算法 4 7 1 、模拟退火算法【鹕】、 遗传算法m g , s o 、神绦嬲络算法蹬1 】等智能优化算法也被成功的应用于求解p 一中值选址翊 惩择酗硼。最近，春磷究逶：蓬将蔻耱癌发式方法溅会，褥蜀7 计算效栗 紫好的混合窟发 式算法1 5 4 1 。一些研究提出了一种半l g n m g i a n 松弛方法【5 5 1 ，利用它能够求得很多大规模 p 一中德问题的精确解；其他人尝试使用分枝寇价( b r a n c h - a n d - p r i c e ) 方法来求解p 一巾 蓬逮瑟骖”珏，该雾法综合瘸磊了爱藏秀、分较定赛饔其宅毖发式方法。 4 大连理工大学硕士学位论文 1 4 本文研究内容 本文研究了智能优化算法在设施选址问题中的应用，重点研究了禁忌搜索算法和遗 传算法在p 一中值选址问题中的应用。在已有算法基础上，针对算法存在的一些问题， 如算法的效率低下或是解的质量不是很理想，或者是算法对数据有严重的依赖性等，研 究如何进一步合理的提高现有算法性能，以获得性能更优或是效率更高的近似最优解， 并为设计新的算法提供参考。 在禁忌搜索算法求解无容量约束p 一中值选址问题的应用研究中，以r o l l a n d 等人 在文献【4 7 】中提出的有效禁忌搜索算法流程为基础。分别对算法的初始解，评价函数。 禁忌信息等关键参数傲了改进尝试。其中，在性能改进方面，重点研究了以基于目标函 数差值的评价函数来取代原有算法中基于目标函数的评价函数，从理论上证明了改进方 法的可行性，并引用公共测试数据集，与r o l l a n d 等人的有效禁忌搜索算法做了比较， 进一步验证了改进算法的优越性能。 在遗传算法求解无容量约束p 一中值选址问题的应用研究中，以o s m a n 等人在文献 【4 9 】中提出的有效遗传算法流程为基础，详细的介绍了该遗传算法的关键参数设置。基 于“优胜劣汰，适者生存”的原理，在遗传算法的初始解、评价函数、交叉算子的设计 等方面做了改进尝试，并提出了种改进算法。改进算法采用新的简单易行的双亲选择 机制和混合评价函数策略，有效的改进了原有算法的计算效率。引用公共测试数据，报 导了试验结果，并与原有算法作了性能比较。 另外，还研究了两算法在有容量约束p 一中值选址问题中的应用。设计了一种求解 有容量约束p 一中值选址问题的禁忌搜索算法，求解实际应用问题并报导了试验结果， 并探讨了c o f f e e 等人在文献 5 0 中提出的p 一中值选址问题分配方法存在的问题。 5 智能优化算法在中值选址问题中的应用研究 2p 一中值选址问题 p 一中值选址问题是一类选址一分配问题( 1 0 c a t i o n - a l l o c a t i o n ) ，是选定p 个设施的 位置，使全部或平均性能最优的问题。通常是使成本最小，如使总( 平均) 运输距离最 小，使总( 平均) 需求权距离最小，使总运输时间最少，或者使总运输费用最小等。距 离通常指需求点与最近设施之间的距离，需求权距离指需求点的需求量和需求点与最近 设施的距离的乘积。这种目标通常在企业问题中应用，所以又叫“经济效益性”目标。 ，一中值闯题可以简单的描述为：给定一个图或是网络g = ( 矿，d ，找到一个集合 量矿，使得该子集满足阮l - p ，且从顶点集 矿巧 到咋中最近的顶点的距离之和最 小。 2 1 p 一中值选址问题的基本定义形式 令g = ( 矿，e ) 是一个带权重的完全无向图，其中v 是顶点集，e 是弧集，每一对顶 点( f ，) 之间的弧具有最小权重吒( 最短距离) 。d = 呜l 。是顶点之间的最小距离矩阵， 是对称的，每个顶点酊矿) 具有权重w ；，带权重的距离矩阵= 嘭 令巧s 矿且k f = p ，d ( 畸，) 与攻畸，名) 分别为顶点到顶点子集巧与巧的最短 距离，h a k i m i 在文献【5 8 】中将p 一中值问题定义为：从g 中选取一个顶点子集巧满足， 对每个斥，都有： w f l ( v ，) 哗d “，匕) ( 2 1 ) 拉l i m l 称咋中的点为p 一中值顶点。 2 2 p 一中值选址问题的整数规划模型 r e v e i i e 与s w a i n 将p 一中值选址问题表示成如下的整数规划模型【2 5 】： 目标函数： m i n z = 岛如帕 ( 2 2 ) 一一o 7 ， l e nj ， 约束条件： 助= l ，v i e n ( 2 3 ) j e j 一= p ( 2 4 ) j e j 助s ，v i e n , v j e j ( 2 5 ) 6 大连理工大学硕士学位论文 o ，l ，石， o ，l ( 2 6 ) 式中： 一需求点的集合，n = l ，2 ，疗 ； ，一候选设施点集合，t 厂= l 2 ，肌 ； 珥一第i 个需求点的需求量： 以一第f 个需求点到第，个候选设施的单位运输成本； p 一所建中值点的总数： 均一0 ，1 变量。当需求点f 由中值点，服务时，- - - - - 1 ；否则，乃= 0 ； z ，一0 ，1 变量。当点_ ，当选为中值点时，z ，= 1 ；否则，j ，- - - - 0 。 通常，在p 一中值选址问题中，认为候选点集即为需求点集。公式( 2 2 ) 是矿中值 问题的目标函数；约束式( 2 3 ) 保证每个需求点有且仅由一个中值点服务；约束式( 2 4 ) 限制中值点的个数为p 个；约束式( 2 5 ) 表明每个需求点只能由中值点服务。 令b 为第，个候选设施的容量，当加入约束条件： q b j x j ，v j e j ( 2 7 ) 据 时，模型即为有容量约柬的p 一中值选址问题。有容量约束p 一中值问题与无容量约束 p 一中值相比：( 1 ) 有容量约束p 一中值问题的每个候选设旌的容量是有限的；( 2 ) 有 容量约束p 一中值闯题要求选择的p 个中值点的容量必须不小于需求点的需求总量。 2 3常用近似算法的设计思想 k a r i v 和h a k i m i 证明了一般网络上的p 一中值问题是n p _ 完全的i s 9 。当p 与孵都很 小时，采用枚举法就可以获得最优解( 行为网络的顶点数) 。一般网络上的卜中值问题 可以通过把距离矩阵的每一行求和，和最小的那一行对应的顶点即为所求的中值点。该 算法需要d ( 矿) 步运算求解距离矩阵，需o ( 舱2 ) 步运算找到该中值点旧。树网络上的l 一中值问题，可以采用更有效的方法，如华罗庚l 删和g o l d m a n z 2 各自提出的修剪树方法， 也称为需求叠加法，该算法的复杂度仅为d ( ，1 ) 哪7 j 。当p 2 时，p 一中值问题可以利用 近似算法近似求解。 已有近似算法的设计主要遵循以下三种思想： ( 1 ) 贪婪算法 首先求解1 一中值问题( 或任意指定一个顶点为中值点) ，求解目标函数；在此基础 上增加一个中值点，以使目标函数尽可能下降；继续增加中值点至p 个。 ( 2 ) 迭代法 首先指定p 个顶点为中值点，将所有的需求点均分配到最近的中值点上，从而形成 7 智能优化算法在中值选址问题中的应用研究 p 个顶点集。在每个集合内求解l 一中值问题，构成一组新的中值点，循环迭代，直至p 个顶点集均不再变化。 ( 3 ) 交换法 首先指定p 个顶点为中值点，求解目标函数，一次去掉其中一个中值点，从未入选 的顶点中选择一个顶点取代它，以使目标函数尽可能下降；循环往复至若干次或是中值 点不再变化。 8 大连理工大学硕士学位论文 3 智能优化算法 3 1引言 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传算法、进 化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或是揭示某些自然现象或 过程而得到发展。其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和 统计力学等方面，为解决复杂问题提供了新的思路和手段。在优化领域，由于这些算法 构造的直观性与自然机理，因而通常被称作智能优化算法( i n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s ) 或现代启发式算法( m e t a - h e u r i s t i ca l g o r i t h m s ) ”。 智能优化算法是借鉴和利用自然界中自然现象或生物体的各种原理和机理而开发 并具有自适应环境能力的计算方法。与传统数学规划方法相比，智能优化算法的优越性 主要体现在：( 1 ) 具有一般性且易于应用；( 2 ) 搜索最优解的速度快且易于获得满意的 结果。目前智能优化方法种类繁多，许多方法存在着不同程度的相似性，如噪声方法、 变邻域搜索等均属于邻域搜索算法，存在着与模拟退火算法所具有的许多相同特征【6 2 】。 常用的启发式算法包括禁忌搜索( t a b us e a r c h ，t s ) 、遗传算法( g e n e t i c a l g o r i t h m ， o a ) 、模拟退火算法、蚁群算法、人工神经网络等等。这些算法主要应用对象是优化问 题中的n p 一难问题，且在诸多领域得到了成功应用。本文主要研究禁忌搜索算法和遗传 算法在中值选址闯题中的应用。 3 2 禁忌搜索算法 禁忌搜索 6 3 , 6 4 , 6 5 1 ( t s ) 是由g l o v e r 于19 | 需年提出，并由其逐渐发展和完善的一种智 能型启发式算法，是局部邻域攫索算法的推广，是对人类智力过程的一种模拟。从广义 上讲，禁忌搜索是一种通过使用自适应的记忆结构来引导局部搜索的技术，是人工智能 在组合优化算法中的一个成功应用。禁忌搜索算法采用禁忌技术避免迂回搜索，并通过 特赦准则来赦免一些被禁忌的优良状态，保证多样化的有效搜索以最终实现全局优化。 目前，禁忌搜索算法在组合优化、生产调度、机器学习等领域得到了广泛且成功的 应用。以下主要介绍算法的基本流程、关键参数设计及算法的特点。 3 2 1 简单禁忌搜索算法流程 简单禁忌搜索的算法步骤描述如下【6 l , 6 3 1 ： ( 1 ) 给定算法参数，生成初始解x ，置禁忌表为空； ( 2 ) 判断算法是否满足终止条件。若是，则结束算法并输出结果；否则，执行以下步骤； ( 3 ) 利用当前解x 的邻域函数产生其所有( 或若干) 邻域解，并从中确定若干候选解； ( 4 ) 对候选解判断特赦准则( a s p i r a t i o n e r i t e d o n ) 是否满足。若成立，则用满足特赦准则 9 智能优化算法在中值选址问题中的应用研究 的最佳解y 替代x 成为当前新解，并用与y 对应的禁忌对象替换最早进入禁忌表的禁忌 对象，同时用y 替换当前最优状态( b e s t f a r ) ，转步( 6 ) ；否则，继续以下步骤； ( 5 ) 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳解为 新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。 ( 6 ) 转步( 2 ) 。 算法的流程框图如下： 图3 1 简单禁忌搜索算法的流程图 f i g 3 i f l o ws h to f s i m p l et a b us e a r c ha l g o r i t h m 3 2 2 算法关键参数与操作设计 一般而言，要设计一个禁忌搜索算法，需要确定算法的以下环节1 6 1 删： 初始解和适应值函数； 邻域结构和禁忌对象； l o 大连理工大学硕士学位论文 候选解选择； 禁忌表及其长度： 特赦准则； 集中搜索与分散搜索策略： 终止准则 ( 1 ) 初始解 禁忌搜索的初始解通常可以随机产生，但是也可以基于闯题信息借助一些启发式方 法生成。 ( 2 ) 适应值函数 适应值函数亦称评价函数。禁忌搜索的适应值函数用于对搜索状态的评价，进而结 合禁忌准则和特赦准则来选取新的最优解。通常以目标函数或是目标函数值的差值作为 适应值函数。当目标函数计算比较复杂时，可采用反映问题目标的某些特征值作为适应 值。选取何种特征值根据具体闯题两定，但必须保证特征值的最佳性与目标函数的最优 性一致。 ( 3 ) 禁忌对象 禁忌是在搜索过程中为了避免迂回搜索而采用的一种策略，禁忌对象是指被置入禁 忌表中的元素。禁忌对象可以是解、组成解的分量或是适应值等。 ( 4 ) 禁忌长度和候选解集 禁忌长度和候选集的大小是影响t s 算法性能的两个关键参数。所谓禁忌长度，即 禁忌对象在不考虑特赦准则情况下不允许被选取的最大次数。当达到最大次数后，禁忌 对象解禁。候选解集则通常是当前状态邻域解集的一个子集。在构造和设计算法时，一 方面要求计算量和存储量尽量少，这就要求禁忌长度和候选解集尽量小；但是，禁忌长 度过短将造成循环搜索，候选解集过小容易造成早熟收敛，陷入局部极小。 禁忌长度的选取与问题特性、研究者的经验相关，它影响算法计算复杂度。禁忌长 度可以动态选取或者静态选取。静态的选取方式是将禁忌长度固定为某个数或者是固定 为与问题规模相关的一个量，实现简单方便。动态的选取方式，可以根据搜索性能和问 题特性设定禁忌长度的变化区间【f 晌，。】，而禁忌长度则按某种原则或公式在区间内变 化。禁忌长度的区间也可以随搜索性能的变化而动态变化。此外，禁忌长度亦可在变化 区间中随机选取。 一般而言，当算法的性能动态下降较大时，说明算法当前搜索能力比较强，也可能 当前解附近极小解形成的“波谷”较深，从而可设置较大的禁忌长度来延续当前的搜索 行为，并避免陷入局部极小。研究表明，禁忌长度的动态设置方式比静态方式具有更好 的性能。 候选解通常在当前解的邻域中择优选取。候选解集过大会造成较大的计算量，过小 智能优化算法在中值选址问题中的应用研究 容易造成早熟收敛。通常确定性或随机性地在部分邻域解中选取候选集。候选集大小视 闯题性能和算法要求而定。 ( 5 ) 特赦准则 在禁忌搜索算法中，可能会出现候选解全部被禁忌，或者存在一个优于“b e s t8 0 缸”状态的禁忌候选解，此时可以通过特赦准则使某些状态解禁，以获得更高效的优化 性能。常用的典型特赦准则是基于适应值的准则，即当某个禁忌候选解的适应值优于 “b e s t f a r ”时，解禁该候选解。 ( 6 ) 集中与分散搜索策略 集中搜索( 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 ) 策略则用于拓宽搜索区域，尤其是未知区域，简单的处 理手段是对算法重新随机初始化，或是根据频率信息对一些已知对象进行惩罚。 ( 7 ) 禁忌频率 记忆禁忌频率( 或次数) 是对禁忌属性的一种补充，可放宽选择决策对象的范围。 实际求解时，可以根据问题和算法的需要，记忆某个状态的出现频率，也可以是某些对 换对象或适应值等出现的信息。 频率信息有助于加强禁忌搜索的能力和效率，并且有助于对禁忌搜索算法参数的控 制，或者可基于此对相应的对象实施惩罚。许多改进的禁忌搜索算法还根据频率等信息 在算法中增加集中搜索和多样性机制，以增强算法的搜索质量和效率。 ( 8 ) 终止准则 禁忌搜索算法常用的终止准则有： 给定最大迭代步数。此方法容易实现，但是难以保证优化质量。 设定某个对象的最大禁忌频率。若某个状态、适应值或对换等对象的禁忌频率超过 某一阙值，或是最佳适应值连续若干步保持不变，则停止算法。 设定适应值的误差。首先确定问题的下界，当算法中最佳适应值与下界的偏离值小 于误差时，终止算法。 3 2 3 禁忌搜索算法的主要特点 由于禁忌搜索算法具有灵活的记忆功能和特赦准则，并且在搜索过程中接受质量差 的解，因此具有较强的“爬山”能力。同时，新解是当前解的邻域中性能最优的解或是 优于“b e s t f a r ”的解，能增强获得更好全局最优解的概率。但是禁忌搜索对初始解的 依赖性较强。一个较好的初始解可使禁忌搜索在解空间中搜索到更好的解，而一个较差 的初始解则会降低搜索的收敛速度和搜索质量。为此，常使用其他启发式算法来获得一 个较好的初始解，来提高算法的性能。此外，禁忌搜索的迭代过程是串行的，仅是单一 状态的变化，非并行搜索。 大连理工大学硕士学位论文 3 3 遗传算法 二十世纪6 0 年代，h o l l a n d 首次提出遗传算法( g a ) 这一术语。1 9 7 5 年h o l l a n d 出版 了遗传算法历史上的经典著作自然和人工系统中的适应性，系统阐述了遗传算法的 基本理论和方法i 明。迸) k 8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是 应用研究都成了十分热门的课题，应用领域不断扩大。g a 是基于“适者生存”原理的一 种高度并行、随机和自适应的优化算法，它将问题的解表示成“染色体”，通过“染色 体”群的代代复制、交叉和变异等进化操作，最终求得问题的最优解或满意解。 目前遗传算法所涉及的主要邻域有自动控制、规划设计、组合优化、图像处理、信 号处理、人工生命等。 3 3 1标准遗传算法的基本流程 遗传算法是一类随机优化算法，它通过对染色体的评价和对染色体中基因的作用， 有效利用已有的信息来指导搜索改善优化质量的状态。遗传算法已有许多发展，但一般 来说，标准遗传算法的主要步骤可描述如下【6 1 闹； ( 1 ) 产生初始种群，评价每个个体的适应值： ( 2 ) 判断算法是否满足停止准则。着满足，则停止；否则。执行下一步： ( 3 ) 根据适应值大小确定复制操作； ( 4 ) 按概率以执行交叉操作； ( 5 ) 按概率执行变异操作； ( 6 ) 返回步( 2 ) 。 具体流程图描述如下： 智能优化算法在中值选址问题中的应用研究 图