（控制理论与控制工程专业论文）微粒群优化算法的改进与应用.pdf

摘要 如今，随着计算机科学与技术的迅速发展，人类生存空间的扩大以及认识与改造 世界范围的拓宽，人们对科学技术提出了新的和更高的要求，其中高效的优化技术和 智能计算的要求日益迫切。微粒群优化算法是一种新兴的智能优化算法，其概念简单， 实现容易，自从k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出以来，在短短几年之内便获得了 很大的发展，并在一些领域获得了成功应用。微粒群优化算法具有较强的全局搜索能 力，但同时也有易陷入局部极值的缺点。本文主要研究了微粒群优化算法的改进与应 用，并进行了仿真研究。主要研究内容如下： 模拟退火算法具有较强的局部搜索能力，并能避免陷入局部最优解，但它的全局 搜索能力不强。本文将微粒群优化算法和模拟退火算法结合，提出一种基于模拟退火 的微粒群优化算法。该算法能克服微粒群优化算法容易陷入局部极值的缺点，且不断 缩小优化变量的搜索空f 副，有较高的搜索效率。应用该算法对测试函数进行优化计算， 得到了满意的效果。 对旅行商问题、车辆路径问题、物流配送中心选址问题这三种受约束的、离散的 组合优化问题，本文采用微粒群优化算法分别进行了应用研究。 对微粒群优化算法的速度位置算式进行了改进，提出一种改进的微粒群优化算 法，该算法符合组合优化问题的特点，在求解旅行商问题上有较高的搜索效率。将此 改进微粒群优化算法分别应用于1 4 个点的t s p 问题以及中国旅行商问题中，都在较 短时间内获得了目前已知的最好解。 设计了求解车辆路径闽题的一种新的实数编码方案，将车辆路径问题转化成准连 续优化问题，并采用罚函数法处理约束条件。应用该微粒群优化算法求解了多个车辆 路径问题的算例，并与遗传算法和双种群遗传算法进行了比较。计算结果表明，该算 法可以更膏效地求得车辆路径问题的优化解，是解决车辆路径问题的有效方法。 构造了微粒表达方法，提出了物流配送中心选址问题的一种混合微粒群优化算 法。通过整数规范化，微粒群能在整数空间内对问题进行优化求解。该算法能克服基 本微粒群优化算法精度较低，易发散的缺点，有较高的搜索效率。实验仿真证明了该 算法的有效性。 关键词微粒群优化算法，函数优化，旅行商问题，车辆路径问题，配送中心选址 l i a b s t r a c t n o w a d a y sw i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e rs c i e n c ea n dt e c h n o l o g y ， p e o p l e sl i v i n gs p a c eh a sb e e ne n l a r g e d a n dt h ef i e l di nw h i c hp e o p l er e c o g n i z e a n dc h a n g et h ew o r l dh a sb e e nb r o a d e n t h ed e m a n df o rs c i e n c ea n dt e c h n o l o g y i si ni n c r e a s e t h e r e f o r eh i g h p e r f o r m a n c eo p t i m i z i n gt e c h n o l o g ya n di n t e l l i g e n c e o p t i m i z a t i o ni s i nu r g e n tn e e d p a r t i c l es w a r mo p t i m i z a t i o na l g o m h mi sak i n do f r i s i n gi n t e l l i g e n c eo p t i m i z e r i t sc o n c e p ti ss i m p l ea n di ti se a s yt ob ei m p l e m e n t e d a f t e rb e i n gp r e s e n t e db yk e n n e d ya n de b e r h ar ti n19 9 5 ，i th a sa c h i e v e dg r e a t d e v e l o p m e n ti ns e v e r a ly e a r sa n dh a sb e e ns u c c e s s f u l l ya p p l i e dt os o m ef i e l d s p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mh a sas t r o n ga b i l i t yt oa c h i e v et h em o s t o p t i m i s t i cr e s u l t m e a n w h i l ei th a sad i s a d v a n t a g es of a ra si t sl o c a lm l n i m u mj s c o n c e r n e d ，i nt h i sd i s s e r t a t i o n ，i m p r o v e m e n ta n da p p l i c a t i o no fp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h ma r em a i n l yd i s c u s s e d t h em a j o ri n n o v a t i o n si nt h i sa r t i c l e a r ea sf o i l o w s ： s i m u l a t e d a n n e a l i n ga l g o r i t h m h a sa s t r o n ga b i l i t y t oa c h i e v et h el o c a l o p t i m i s t i cr e s u l t a n di tc a na v o i dl o c a lm i n i m u m b u to nt h eo t h e rh a n di t sa b i l i t yt o a c h i e v et h eg l o b a l o p t i m i s t i c r e s u l ti s q u i t ew e a k ah y b r i dp a r t i c l es w a r m o p t i m i z a t i o ni sp r o p o s e d t h i sm e t h o di n t e g r a t e st h ep a r t i c l es w a r mo p t i m i z a t i o n w i t ht h es i m u l a t e da n n e a l i n g i tc a nn a r r o wt h ef i e l do fs e a r c ha n ds p e e du pt h e r a t eo fc o n v e r g e n c ec o n t i n u a l l yi nt h eo p t i m i z i n gp r o c e s s i th a sh i g h e rs e a r c h i n g e f f i c i e n c y i tc a na l s oe s c a p ef r o mt h el o c a lm i n i m u m s i ti sa p p l i e dt os e v e r a lt e s t f u n c t i o n so p t i m i z a t i o np r o b l e ma n dt h es i m u l a t i o ns h o w st h a tt h i sa l g o r i t h mi sm u c h b e t t e r 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 ) ，v e h i c l er o u t i n gp r o b l e m ( v r p ) ，a n dt h e l o c a t i o no fd i s t r i b u t i o nc e n t e rw h i c ha r ec o n s t r a i n e da n dd i s c r e t ep r o b l e m sa r e d i s c u s s e di nt h ep a p e ru s i n gp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m i i l am o d i f i e dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mi sp r o p o s e da f t e rm o d i f y i n g t h ev e l o c i t ya n dp o s i t i o ne x p r e s s i o n so ft h ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m t h i sa l g o r i t h ma g r e e sw i t ht h ec h a r a c t e ro ft 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 oi th a sh i g h e re f f i c i e n c yo fs e a r c h t h i sa l g o r i t h mi sp r a c t i c e dt oat r a v e l i n g s a l e s m a np r o b l e mw i t h14 n o d e sa n dc h i n e s et r a v e l i n gs a l e s m a np r o b l e m ，a n di t o b t a i n sl h eb e s tr e s u l t si nt h ew o r l d am e t h o db a s e do np s ow a sr e s e a r c h e dt os o l v et h ed i s c r e t ev r p t h ev r p w a sc h a n g e di n t oaq u a s i c o n t i n u o u sp r o b l e mb yd e s i g n i n gan e wr e a lc o d i n g c o n s t r a i n e dt e r m si nv r pw e r ep r o c e s s e db yt h ep e n a l t yf u n c t i o n t h i sp r o p o s e d a l g o r i t h mw a sa p p l i e dt oi l l u s t r a t i n gi t sh i g h e rs e a r c h i n ge f f i c i e n c yi nc o m p a r i s o n w i t hs t a n d ar dg e n e t i ca l g o r i t h m d o u b l ep o p u l a t i o n sg e n e t i ca l g o r i t h mf o rv r p s i m u l a t i o nr e s u l t so fs e v e r a lv r pe x a m p l e sd e m o n s t r a t e dt h ee f f e c t i v e n e s so ft h i s a l g o r i t h m f u r t h e r m o r e ，ak i n do fc o d i n gi sc o n s t r u c t e df o rl o c a t i o no fd i s t r i b u t i o nc e n t e r a n dt h e nah y b r i dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mi sp r o p o s e d t h ep a r t i c l e s w a r me v o l v e si nt h ei n t e g e rs p a c ea f t e rb e i n gi n t e g e rs t a n d a r d i z e d t h i sa l g o r i t h m c a ns o l v et h ep r o b l e mo fl o wp r e c i s i o na n dd i v e r g e n c eo fb a s i cp ar t i c l es w a r m o p t i m i z a t i o na l g o r i t h m ，s o i th a sh i g h e re f f i c i e n c yo fs e a r c h i ti sc o m p a r e dw i t h b a s i cp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h ma n dg e n e t i ca l g o r i t h m r e s u l t sp r o v e t h a tt h i sa l g o r i t h mi se f f e c t i v e l ij u n j u n ( c o n t r o lt h e o r ya n dc o n t m le n g i n e e r i n g ) d i r e c t e d b yw a n gx i h u a i x i a oj i a n m e i k e y w o r d sp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，f u n c t i o no p t i m i z a t i o n ，t r a v e l i n g s a l e s m a np r o b l e m ，v e h i c l er o u t i n gp r o b l e m 1 0 c a t i o no fd i s t r i b u t i o nc e n t e r 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果二论文 中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已经发表或 撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作 了明确的声明并表示了谢意。 作者签名：垄互篁 日期 论文使用授权声明 协671 泞 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布论文的全 部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。保密的论 文在解密后遵守此规定。 作者签名：互砸 导师签名：日期妒f - - ! 第一章绪论 最优化问题是在有限种或无限种可行方案( 决策) 中挑选最优的方案( 决策) 。 随着高新技术、计算机及信息技术的飞速发展，最优化在工农业、国防、交通、金融、 能源、通信等众多领域的应用越来越广泛，问题的规模越来越大、复杂性越来越高。 追求最优目标是人类的理想，最优化理论和方法是一门新兴的应用数学分支，是 第二世界大战后迅速发展的一个新学科，它就是从众多可能方案中选择最佳者，以达 到最优目标uj 。最优化是一门应用相当广泛的学科，它讨论决策问题的最佳选择之特 性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现。因 为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域， 它已受到政府部门、科研机构和产业部分的高度重视1 2 j 。 1 1 最优化问题 1 1 1 最优化问题分类【3 】 优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化问题可 分为无约束优化问题与约束优化问题两大类。其中决策变量x 的解空间若为r ”，则 该问题为无约束最优化问题；决策变量z 的解空间受到一些约束函数的限制，则该问 题被称为约束优化问题。 按对象是连续状态还是离散状态，最优化问题也可分为函数优化问题和组合优化 问题两大类，其中函数优化问题的对象是一定区域内的连续变量，而组合优化问题的 对象是解空间中的离散状态。 1 无约束最优化与约束优化 最优化问题的一般形式为 m i n m ) f 1 - 1 1 s t x x 、 其中x r ”是决策变量，( z ) 为目标函数，x c r ”为约束集或可行域。特别地，如 果约束集= r ”，则最优化问题( ) 称为无约束最优化问题： m i n f ( x ) ( 1 - 2 ) j 约束最优化问题通常写为 r a i nf ( x ) j r c 。( z ) = 0 ，i e ，( 1 3 ) c 。( x ) 0 ，i i ， 这里e 和，分别是等式约束的指标集和不等式约束的指标集，c i ( x ) 是约束函数。 当目标函数和约束函数均为线性函数时，问题称为线性规划。当目标函数和约束 函数中至少有一个是变量x 的非线性函数时，问题称为非线性规划。此外，根据决策 变量、目标函数和要求的不同，最优化还分成了整数规划、动态规划、网络规划、非 光滑规划、随机规划、几何规划、多目标规划等若干分支。 2 函数优化与组合优化 函数优化问题通常可描述为：令s 为r ”上的有界子集( 即变量的定义域) ， 厂：s r 为n 维实值函数，所谓函数厂在s 域上全局最小化就是寻求z m m s 使得在 s 域上全局最小，即b 彳s ：f ( x m m ) f i x ) 。鉴于许多工程问题存在约束条件，受 约束函数的函数优化问题也一直是优化领域关注的主要对象。 组合优化问题通常可描述为：令q = s 1s ：，s 。) 为所有状态构成的解空间， c ( s ) 为状态s 。对应的目标函数值，要求寻找最优解s ，使得v s 。q ， c ( s t ) = m i n c ( s ，) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个 重要分支。 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a n p 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 kp r o b l e m ) 、装 箱f 咂( 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 g p r o b l e m ) 等。 1 1 2 局部极小和全局最小 极小点的类型有局部极小点和全局最小点两种州。 定义1 1 如果存在j 0 ，使得对所有满足x r ”和1 i x - - x * g ) ，则称x 为厂( x ) 的严格全局最小点。 1 1 3 计算复杂性与n p 完全问题 1 计算复杂性的基本概念 由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问题在 实践中并不一定可解。按照复杂性理论研究问题求解的难易程度，可把问题分为p 类、n p 类和n p 完全类。 2p ，n p ，n p c 和n p 、h a r d p 类问题指具有多项式时间求解算法的问题类。但迄今为止，许多优化问题仍没 有找到求得最优解的多项式时间算法，通常称这种比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 lp r o b l e m ) 。 定义1 3 若存在一个多项式函数g ( x ) 和一个验证算法h ，对一类判定问题a 的 任何一个“是”的判定实例，都存在一个字符串s 是，的“是”回答，满足其输入长 度d ( ，) 不超过g 【d ( 功，其中d f f ) 为，的输入长度，且验证算法验证s 为，的“是” 回答的计算时间不超过g ( d ( 助，则称判定问题a 为非多项式确定问题，简称n p 。 司。见，尸亡 7 p 。 进一步，我们给出n p - c ( n p c o m p l e t e , n p 完全阃题) 和n p - h a r d ( n p 难问题) 的概念。 定义14 称判定问题a n p c ，若a n p 且n p 中的任何一个问题可多项式 归约为问题a 。称问题a 为n p h a r d ，只要上述第二个条件成立。 由止e 可见， 驴一c n p h a r d 。 n p c 问题具有重要的实际意义和工程背景，目前已有许多问题被证明为n p c ， 如背包问题、装箱问题、j o b s h o p 和f l o w s h o p 问颢、集合霜羔问颢、t r p 阍颢笺 t 2 最优化方法 最优化理论与方法是一门应用性很强的年轻学科。它研究某些数学上定义的问题 的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。 虽然最优化可以追溯到十分古老的极值问题，然而它成为一门独立的学科是在 本世纪4 0 年代末，是在1 9 4 7 年d a n t z i g 提出求解般线性规划问题的单纯形法之后。 现在，解线性规划、非线性规划以及随机规趔j 、非光滑规划、多目标规划、几何规划、 整数规划等各种最优化问题的理论的研究发展迅速，新方法不断出现，实际应用日益 广泛。在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产管理、 交通运输等方面得到了广泛应用，成为一门十分活跃的学科口1 。 1 2 2 经典精确算法 1 无约束最优化方法 无约束最优化方法有最速下降法、牛顿法及其改进和拟牛顿法。这些方法各有特 色，适应面也不尽相同，但它们都是求解无约束优化问题的最基本、最重要的算法。 无约束优化问题的许多其他求解方法乃至一些约束优化闳题的求解法都是以它们为 基础发展起来的。 2 ，大规模无约束最优化方法 2 l 大规模无约束最优化方法有共轭梯度法、稀疏拟牛顿法、有限内存拟牛顿法和无 记忆拟牛顿法。共轭梯度法具有不需要存储迭代矩阵，并且具有较快的收敛速度和二 次终止性的优点。 s c h u b e r t ( 1 9 7 0 ) 首先把拟牛顿校正推广到不对称稀疏矩阵上，提出了解非线性方 程组的稀疏拟牛顿法。p o w e i l ( 1 9 7 6 ) ， r o i n t ( t 9 7 7 ) ，s h a r m o ( 1 9 8 0 ) 先后推导了稀疏拟牛 顿校正公式。s t e i h a u g ( 1 9 8 4 ) 给出了一个采用预处理策略的稀疏拟牛顿法，并给出了 收敛性证明【4 1 。 迄今为止，拟牛顿法中的b f g s 方法是求解无约束优化问题的最有效方法。有限 内存拟牛顿法就是对它进行了改进，减小其存储量，使之能适用于求解大规模无约束 最优化问题。无记忆拟牛顿法( 尉继英，1 9 9 0 ) 在计算过程中不必存贮矩阵，具有存 贮量小，收敛速度快的特点。因而，特别适用于求解大规模无约束最优化问题。 3 非线性最小二乘方法 在大量的实际最优化问题中，目标函数f ( x ) 取若干非线性函数平方和的形式而 成为熟知的非线性最d - - 乘问题 r a i n f ( x ) = 去 1 ( z ) 2 = 挑( 州， 山拉1 其中r ( x ) = ( 伍) ，( x ) ) 。称为在点x 的残向量。作为一个最优化问题，它可以用在 前几种最优化方法求解。有高斯一牛顿法、对高斯牛顿矩阵的拟牛顿修正、混合算法 和分解拟牛顿方法。 4 线性约束最优化方法 线性约束优化问题求解要比无约束优化问题复杂。以下是几种早期求解线性约束 优化问题的方法。 确定可行下降方向的两种早期典型算法有：投影梯度法、简约梯度法( w o l f e ， 1 9 6 3 ) 。 约束零空间表示的两个比较有效的算法为零空间方法、值空间方法。 有效集方法处理余数的方式类似于投影梯度法。但它是通过求解一等式约束子问 题来寻找搜索方向。因此，有效集方法在某种意义上可看作是对投影梯度法思想的推 广。 二次规划是是线性约束优化问题在目标函数f ( x ) 为x 的二次函数时的特例。由于 其问题的特殊性，一方面对前述方法的简化与改进，使得算法更有效；另一方面，还 有一些新型求解算法，如内点算法等。 5 非线性约束最优化方法【2 1 非线性约束最优化问题是最一般形式的非线性规划问题。一些常用的、可靠性与 有效性相对好的算法有罚函数方法、乘子法、广义简约梯度法和s q p 方法等。 传统的罚函数方法就是通过给原来的目标函数加上项出约束函数所构成的惩 罚项来生成新的目标函数，以便将约束优化问题转化为无约束优化问题的求解。有外 点罚函数法、s u m t 内点罚函数法，混合罚函数法精确罚函数法。实际中最常用的两 个重要内点罚函数法分为分( 倒) 数罚函数和对数罚函数法。 可以从几个不同的角度来导出乘子类算法，但其主要目的是一致的，即克服罚函 数的病态性质，以便数值求解，并同时尽量使所构造的辅助函数具有较好的光滑性质。 乘子法有具体估计非线性约束问题拉格朗日乘子的一、二阶方法，s q v 类算法。 广义简约梯度法是简约梯度法在非线性约束时的推广。其实，确定可行下降方向 法、约束零空间表示法的处理线性约束的方法均可推广到一般非线性约束问题。可将 这类方法分为两种：广义消去法和序列线性规划方法。 与无约束情形一样，s q p 方法也是在牛顿法的基础上发展起来的，与有关算法相 比具有许多显著的优点。s q p 方法有这几种：h a r t 方法，w i - i p 算法，投影海森阵校 正方法，序列最小二乘方法，信赖域s q p 算法，可行s q p 算法，强次可行s q p 算法。 1 2 3 智能优化算法( i n t e | ij g e n to p t i m iz a t i o na i g o r i t h m s ) 2 0 世纪8 0 年代以来，一些新颖的优化算法如人工神经网络、混沌、遗传算法、 进化、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或揭示某些自然现象或过 程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和 统计力学等方面，为解决复杂问题提供了新的思路和手段。这些算法独特的优点和机 制掀起了优化领域的研究热潮，且在诸多领域得到了成功应用。这些算法通常被称为 智能优化算法，或称为现代启发式算法( m e t a h e u r i s t i c a l g o r i t h m s ) 。 根据使用情况的不同，本文在这里将智能优化算法分为进化计算、其他智能优化 算法、群智能优化算法。 1 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 进化算法是一系列搜索技术，包括遗传算法、进化编程、进化策略、遗传编程等。 尽管进化算法有很多变化，但它们都是基于自然进化过程的基本计算模型。同传统的 基于微积分的方法和穷举法等优化算法相比，进化计算是一种成熟的具有高鲁棒性和 广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性【5 】。 ( 1 ) 进化计算的分类嘲 仿生进化研究主要有三类；遗传算法( o e n e t i ca l g o r i t h m s ，g a s 或o a ) 【7 】、进化策 略( e v o l u t i o ns t r a t e g i e s ，e s s 或e s ) 【8 】和进化规划( e v o i u t i o np r o g r a m m i n g ，e p ) 9 1 。第一 类方法 1 比较成熟，现已广泛应用，进化策略和进化规划在科研和实际问题中的应用 也越来越广泛。遗传算法的主要基因操作是选种、交配和突变，面在进化规则、进化 策略中，进化机制源于选种和突变。就适应度的角度来说遗传算法用于选择优秀的父 代( 优秀的父代产生优秀的子代) ，而进化规则和进化策略则用于选择子代( 优秀的 子代才能存在) 。 ( 2 ) 进化计算的起源与发展 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是基于生物进化理论的原理发展起来的一种广 为应用的、高效的随机搜索与优化的方法。它是在7 0 年代初期由美国密执根( m i c h i g a n ) 大学的霍兰( h o l l a n d ) 教授发展起来的。1 9 7 5 年霍兰教授发表了第一本比较系统论述 遗传算法的专著自然系统与人工系统中的适应性( ( ( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s ) ) ) 。遗传算法与进化策略、进化规划共同构成了进化算法的主要框 架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人 知的算法。 进化规划 进化规划是由美国人lj f o g e l 于2 0 世纪6 0 年代提出来的。他提出采用有限字 符集上的符号序列表示模拟的环境，采用有限状态机表示智能系统。这种方法与遗传 算法有许多共同之处，但不像遗传算法那样注重父代与子代的遗传细节，而是把侧重 点放在父代与子代表现行为的联系上1 1 2 1 。 进化策略 进化策略是在欧洲独立于遗传算法和进化规划而发展起来的。1 9 6 3 年德国大学 的两名学生i ，r e c h e n b e r g 和h rs c h w e f e l ，在利用流体工程研究所的风洞作实验室 时r e c h e n b e r 提出了按自然突变和自然选择的生物进化思想的进化策略思想。 近年来，国际上掀起了进化计算的研究和热潮，各种新的研究结果和应用实例不 断涌现，将来有一天可能会出现一门内容包括进化计算但比进化计算更为广泛的科 学，这科学可能被称为“自然计算( n c ，n a t u r a lc o m p u t a t i o n ) ” 6 】。 2 其他智能优化算法【3 1 其他智能优化算法较为著名的有模拟退火，禁忌搜索，神经网络优化算法等。 1 9 8 3 年k i r k p a t r i c k 1 3 1 提出了模拟退火算法( s i m n l a t e d a r u l e a i i n g ，s a ) 。归纳而言， s a 算法是基于m o n t ec a r l o 迭代求解策略的一种随机寻优算法，s a 由某一较高初温 开始，利用具有概率突跳特性的m e t r o p o l i s 抽样策略在解空间中进行随机搜索，伴随 温度的不断下降重复抽样过程，最终得到问题的全局最优解。 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h 简称t s ) i t 4 【1 5 】的思想最早由g l o v e r ( 1 9 8 6 ) 提出。t s 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并 通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现 全局优化。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 1 6 】是近年来得到迅速发展的一个 前沿课题。神经网络优化算法就是利用神经网络中神经元的协同并行能力来构造的优 化算法，它将实际问题的优化解与神经网络的稳定状态相对应，把对实际问题的优化 过程映射为神经网络系统的演化过程。相应的有h o p f i e l d 反馈神经网络优化算法、混 沌序列优化和混沌神经网络算法等。 另外，算法混合的思想已发展成为提高算法优化性能的一个重要且有效的途径， 其出发点就是各种单一算法相互取长补短，产生更好的优化效率。 3 群智能优化算法 目前群智i g ( s w a r mi n t e l l i g e n c e ，s i ) 作为一种新兴的演化计算技术已成为越来越 多研究者的关注焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的 联系。群智能是指“无智能的主体通过合作表现出智能行为的特性”。群智能在没有 集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础 旧。 目前，群智能理论研究领域有两种主要的算法：蚁群算法( a n tc o l o n yo p t i m i z a t i o n ， a c o ) t8 1 和微粒群优化算f 去( p a r t i c l es w a r l t lo p t i m i z a t i o n ，p s o ) 0 9 2 0 1 。前者是对蚂蚁群 落食物采集过程的模拟，已成功应用于许多离散优化问题微粒群算法也是起源于对 简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化 工具。近年国内提出的人工鱼群算法口1 1 【2 2 1 是一种基于模拟鱼群觅食、聚群和追尾行 为的随机搜索优化算法，也是一种群智能优化算法。 群智能依靠的是概率搜索算法，虽然概率搜索算法通常要采用较多评价函数，但 其优点还是显著的2 0 ：( 1 ) 无集中控制约束，不会因个别个体的故障影响整个问题的求 解，确保了系统具备更强的鲁棒性：( 2 ) 以非直接的信息交流方式确保了系统的扩展 性；( 3 ) 并行分布式算法模型，可充分利用多处理器；( 4 ) 对问题定义的连续性无特殊 要求；( 5 1 算法实现简单。 己完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多 数全局优化问题的新方法。无论是从理论研究还是应用研究的角度分析，群智能理论 及应用研究都是具有重要学术意义和现实价值的【2 3 1 。 本文主要研究微粒群优化算法的改进和应用，因此在这里将微粒群优化算法特别 作为一节。 1 3 微粒群优化算法 微粒群优化( p a r t i c l es w a r mo p t i m i z e r , p s o ) 算法是一种基于群智能( s w a r m i n t e l l i g e n c e ) 方法的演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术口”。p s o 算法同遗传算法类 似，是一种基于群体( p o p u l a t i o n ) 的优化工具。系统初始化为一组随机解，通过迭代搜 寻最优值。但是并没有遗传算法用的交y ( c r o s s o v e r ) 以及变异( m u t a t i o n ) 操作，而是微 粒( 潜在的解) 在解空间追随最优的微粒进行搜索。与遗传算法比较，p s o 算法的优 势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应 用。因此，p s o 算法一提出，立刻引起了演化计算等领域的学者们的广泛关注，并在 短短的几年时间里出现大量的研究成果，形成了个研究热点。 p s o 算法最早是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的。受到人工生命( a r t i f i c i a l l i f e ) 的研究结果启发，p s o 算法的基本概念源于对鸟群捕食行为的研究。设想这样一 个场景：群鸟在随机搜寻食物。在这个区域里只有一块食物。所有的鸟都不知道食 物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什 么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。p s o 算法从这种模型 中得到启示并用于解决优化问题。p s o 算法中，每个优化问题的潜在解都是搜索空间 中的一只鸟，称之为“微粒”。所有的微粒都有一个由被优化的函数决定的适应值 伍t n e s sv a l u e ) ，每个微粒还有一个速度决定他们飞翔的方向和距离。然后微粒们就追 随当前的最优微粒在解空间中搜索。p s o 算法初始化为一群随机微粒( 随机解) 。然 后通过迭代找到最优解。在每一次迭代中，微粒通过跟踪两个“极值”来更新自己。 第一个就是微粒本身所找到的最优解。这个解称为个体极值。另一个极值是整个种群 目前找到的最优解。这个极值是全局极值。另外也可以不用整个种群而只是用其中一 部分作为微粒的邻居，那么在所有邻居中的极值就是局部极值。 由于认识到p s o 算法在函数优化等领域所蕴含的广阔的应用前景，在e b e r h a r t 和k e n n e d y 之后很多学者都进行了这方面的研究。目前，己提出了多种p s o 改进算 法，并且p s o 算法已广泛应用于函数优化口鄂，神经网络训练伫。1 ，预测控n t 2 6 】，模糊 系统控制以及其他的应用领域。 1 4 本文的研究内容与结构安排 本文在上海市高校科技发展基金项目“分布式协同建模技术和分布式仿真研究” ( 0 3 i k 0 9 ) 的支持下，主要研究了微粒群优化算法在函数优化问题、旅行商问题、车 辆路径问题、物流配送中心选址问题上的改进和应用。通过与其他算法结合。根据组 合优化问题调整改进编码方式、算子，对微粒群优化算法进行了应用研究。全文内容 安排如下： 第章简单介绍了最优化问题，最优化理论与方法及其分类，微粒群优化算法： 第二章介绍了微粒群优化算法的原理、发展、应用情况； 第三章将微粒群优化算法与模拟退火算法相结合，提出了一种基于模拟退火的微 粒群优化算法，并应用于函数优化问题； 第四章是微粒群优化算法在旅行商问题上的应用研究。对微粒群优化算法的速度 位嚣算式进行了改进，提出一种改进的微粒群优化算法； 第五章针对车辆路径问题这种离散的组合优化问题，设计了一种新的实数编码方 案，将车辆路径问题转化成准连续优化问题，提出了一种求解车辆路径问题的改进微 粒群优化算法； 第六章为微粒群优化算法在物流配送中心选址问题上的应用研究。在第三章提出 的基于模拟退火的微粒群优化算法的基础上，构造了配送中心选址问题的一种微粒表 达方法，提出了一种配送中心选址的混合微粒群优化算法； 第七章总结了全文，并指出今后的研究方向。 第二章微粒群优化算法 大自然始终是开启人类智慧的老师。“师法自然”，入类受到社会系统、物理系统、 生物系统等运行机制启发，建立和发展起一个个研究工具和手段来解决和攻克研究过 程中遇到的困难。典型的有遗传算法、人工神经网络、进化规划、蚁群优化算法等。 这些算法已经被广泛应用于工程，有许多很成功的实例。而在计算智能( c o m p u t a t i o n a l ， i n t e l l i g e n c e ，c i ) 领域中，有两种基于群体智能 2 7 】【2 ”的算法：蚁群优化算法和微粒群优 化算法。前者是对蚂蚁群落搜索食物行为的模拟，已经成功运用在很多组合优化问题 上；后者就是本章将要介绍的微粒群优化算法。 微粒群优化算法是一种进化计算技术，是进化计算领域中台勺一个新的分支，其源 于鸟群和鱼群群体运动行为的研究。与基于达尔文“适者生存，优胜劣汰”进化思想 的遗传算法不同的是，微粒群优化算法是通过个体之间的协作来寻找最优解的。文献 f 2 0 引用了生物社会学家e 0 w i l s o n 关于生物群体的一段话，“至少在理论上，一个 生物群体中的一员可以从这个群体中所有其他成员以往在寻找食物过程中积累的经 验和发现中获得好处。只要食物源不可预知地分布于不同地方，这种协作带来的优势 可能变成决定性的，超过群体中个体之间对食物竞争所带来的劣势”【2 9 1 。这段话的意 思是说生物群体中信息共享会产生进化优势，这也正是微粒群优化算法的基本思想。 p s o 算法概念简单，容易实现，其代码只有短短的几行，和其他优化算法相比， 这也是它的优点之一。短短几年里，p s o 算法已经获得了很大的发展，并已经在一些 领域得到应用。两三年前，国内对p s o 算法的研究还刚刚开始引起人们的注意：而 现在已出现不少相关的文献，正逐渐成为一个研究热点， 2 2p s o 的算法原理 自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种群体 行n ( s w a r mb e h a v i o r ) 在计算机中建模，实际上就是在计算机中用简单的几条规则来 建立个体的运动模型但这个群体的行为可能很复杂。例如，r e y