《一种基于动态群体结构的粒子群算法及其在啤酒分配游戏.pdf》由会员分享，可在线阅读，更多相关《一种基于动态群体结构的粒子群算法及其在啤酒分配游戏.pdf（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、中山大学硕士学位论文一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究姓名：刘红亮申请学位级别：硕士专业：计算机应用技术指导教师：任江涛20100602一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究摘要一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究计算机应用技术摘要粒子群优化算法作为一种新的智能优化算法，由于其收敛速度快、参数设置少，近年来受到众多学者的研究和重视。它常被用于解决大量非线性、不光滑和多峰值的复杂问题优化，现己广泛应用子许多科学和工程领域。大量的研究结果表明，粒子群算法在解决离散求解空间和连续求解空间问题时均表现出较好的全局搜索能力。但
2、是，在实际应用过程中人们也发现，对于标准的全局粒子群算法(使用星形拓扑结构的粒子群算法)，由于进化过程中种群多样性损失过快，粒子群算法易于陷入局部极值，引起算法过早收敛。而对于局部优化粒子群算法(使用环形拓扑结构的粒子群算法)，粒子群算法收敛速度较慢，需要对目标函数进行大量次数的评价。针对这个问题，本文提出了基于动态更新群体拓扑结构的新算法。种群拓扑结构是指整个种群所有粒子之间的连接方式。粒子群算法是一种随机性智能搜索算法，算法成功的关键在于能否有效地在早期全局开拓与晚期局部搜索解空间之间进行平衡。由于种群的拓扑结构决定了信息在整个种群问的流动速度，而信息流动的速度可以用来控制算法的探测和开发
3、能力。目前最普遍使用的拓扑结构是星形和环形。在星形拓扑结构下，每个粒子都与其他粒子相连接，因此信息流动最快，导致了粒子群算法收敛过快，出现“早熟”现象。而在环形拓扑结构下，每个粒子仅与相邻的两个粒子相连接，因此信息流通非常慢，最终导致使用该拓扑结构的粒子群算法收敛速度慢。因此，我们可以说星形和环形结构代表了信息流通速度的两个极端。但是我们不难发现环形结构满足了该算法早期对空间进行全局解空间探索的要求，而星形结构恰恰满足了该算法晚期对搜索空间进行局部开发的要求。因此如果能够动态地改变拓扑结构将是一个有效的平衡探测和开发的要求，基于这个想法，本文提出了动态增加每个粒子连接个数的方法来改变群体的拓扑
4、结构。本文还调查了增加的速度对算法的影响。通过对一系列经典优化函数进行测试，验证了本文提出算法的有效性。本文的另一个重要研究方面是把粒子群算法应用到供应链管理领域。本文V摘要一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究以啤酒分配游戏为例研究了该算法在供应链管理中的潜在应用。啤酒分配游戏是上世纪6 0 年代在M I T 开发的，代表了一类典型的供应链管理优化问题。这个游戏提供了一个复杂的模拟环境，并涉及了多维受限制的参数。传统上，啤酒分配游戏的研究都是基于一个简单的客户需求。本文设计了其它三种更为复杂的客户需求。另外，对每一种客户需求，我们还研究了两种不同的场景。在第一种场景下
5、，所有啤酒分配游戏的角色都使用相同的策略管理他们的库存。在第二种场景下，不同的角色允许使用不同的策略。从优化的角度来说，由于第二种场景设计更多的参数，因此也是一种更为复杂的优化问题。通过对一系列不同情景下的供应链问题进行优化，并对结果进行T 统计检验分析，我们发现本文提出的算法的性能整体上优于遗传算法。关键字：粒子群算法，动态群体拓扑结构，遗传算法，供应链管理，啤酒分配游戏，复杂客户需求一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究P a r t i c l eS w a r mO p t i m i s a t i o nv i aD y n a m i cP o p u l
6、 a t i o nT o p o l o g i e sa n dI t sA p p l i c a t i o ni nB e e rD i s t r i b u t i o nG a m eC o m p u t e rA p p l i e dT e c h n o l o g yA b s t r a c tP a r t i c l eS w a r mO p t i m i z a t i o n(P S O)a san e wi 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，h a sb e e na
7、 t t r a c t e dm a n ys c h o l a r sr e s e a r c ha n da t t e n t i o ni nr e c e n ty e a r s T h i si sm a i n l yd u et Oi t sf a s tc o n v e r g e n c er a t ea n d f e wp a r a m e t e rs e t t i n g I th a sb e e ne m p l o y e dt Os o l v eal a r g en u m b e ro fn o n-l i n e a r，n o n-
8、s m o o t ha n dm u l t i m o d e lf u n c t i o n s，a n da l s oh a sb e e na l r e a d yw i d e l yu s e di nm a n ys c i e n c ea n de n g i n e e r i n gd o m a i n s Al a r g en u m b e ro fs t u d i e ss h o wt h a tt h eP S Oa l g o r i t h m sh a v es h o w nab e t t e rg l o b a ls e a r c
9、hc a p a b i l i t yt os o l v ed i s c r e t ea n dc o n t i n u o u ss o l u t i o ns p a c ei s s u e s H o w e v e r,i nm a n yr e a la p p l i c a t i o n s，i ta l s of i n d s 吐l 矾f o rt h es t a n d a r dg l o b a lP S O(s t a rt o p o l o g yu s e d)，d u et oi t sr a p i dl o s so fs p e c i
10、 e sd i v e r s i t yi nt h ee v o l u t i o n a r yp r o c e s s，i tc o u l db ee a s i l yt r a p p e di n t ol o c a lm i n i m aa n dc a u s et h ep r e m a t u r ec o n v e r g e n c ep r o b l e m A sf o rt h el o c a lP S O(t h er i n gt o p o l o g yu s e d)，i tu s u a l l yn e e d sal a r g
11、 en u m b e ro fo b j e c t i v ef u n c t i o ne v a l u a t i o n sb e c a u s eo fi t ss l o wc o n v e r g e n c er a t e T oa d d r e s st h i si s s u e，t h i sp a p e rp r o p o s e san e wP S Oa l g o r i t h mv i aad y n a m i cn e i g h b o r h o o dt o p o l o g y T h en e i g h b o r h o
12、 o dt o p o l o g yr e f e r st ot h ew a yo fc o n n e c t i o n sb e t w e e np a r t i c l e si nt h ee n t i r ep o p u l a t i o n T h eP S Oi sa l li n t e l l i g e n tr a n d o ms e a r c ha l g o r i t h m，a n dt h ek e yt OS U C C E S Si st Oe f f e c t i v e l yb a l a n c eb e t w e e nt
13、 h ee x p l o r a t i o n so ft h es o l u t i o ns p a c ei nt h ee a r l ys t a g e sa n dt h ee x p l o i t a t i o n so ft h es o l u t i o ns p a c ei nt h el a t es t a g e s T h en e i g h b o r h o o dt o p o l o g yo ft h ep o p u l a t i o nd e t e r m i n e st h es p e e do fi n。f o r m a
14、 t i o nf l o wi nt h ee n t i r ep o p u l a t i o n，a n df u r t h e r r n o r e，t h es p e e do fi n f o r m a t i o nf l o wi nt h ee n t i r ep o p u l a t i o nc o u l db eu s e dt Oc o n t r o le x p l o r a t i o n sa n de x p l o i t a t i o n s T h em o s tc o m m o n l yu s e dt o p o l o
15、 g i e sa r et h es t a rt o p o l o g ya n dt h er i n gt o p o l o g y I nt h es t a rt o p o l o g y,e a c hp a r t i c l ei sc o n n e c t e dw i t ho t h e rp a r t i c l e s，S Ot h ef l o wo fi n f o r m a t i o ni se x t r e m e l yf a s t，w h i c hl e a d st or a p i dc o n v e r g e n c eo
16、ft h eP S O，a n ds u b s e q u e n t l yc a u s eap r e m a t u r ep h e n o m e n o n I nt h er i n gt o p o l o g y,e a c hp a n i c l ei so n l yc o n n e c t e dw i t ht w oa d j a c e n tp a r t i c l e s，S Ot h ef l o wo fi n f o r m a t i o ni sv e r ys l o w,w h i c he v e n t u a l l ya f-V
17、 一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究f e c t st h ec o n v e r g e n c es p e e do ft h eP S O T h e r e f o r e，w ec o u l ds a yt h a tt h es t a rt o p o l o g ya n dt h er i n gt o p o l o g yr e p r e s e n tt h et w oe x t r e m e so ft h ei n f o r m a t i o nf l o ws p e e d B u tw ec o u l da l
18、s of i n dt h a tt h er i n gt o p o l o g ym e e t st h er e q u i r e m e n t so ft h eg l o b a ls o l u t i o ns p a c ee x p l o r a t i o n si nt h ee a r l ys t a g e s，w h i l et h es t a rt o p o l o g yp e r f e c t l ym e e t st h er e q u i r e m e n t so ft u n i n gt h es e a r c hs p
19、a c ei nt h el a t es t a g e s S oi fw ec a nd y n a m i c a l l yc h a n g et h et o p o l o g i e s，i tw i l lp r o v i d ea ne f f e c t i v ew a yt ob a l a n c eb e t w e e ne x p l o r a t i o n sa n de x p l o i t a t i o n si nt h ew h o l es t a g e B a s e do nt h i si d e a，t h i sp a p
20、e rp r e s e n t sad y n a m i cn e i g h b o r h o o dt o p o l o g yt h r o u g hd y n a m i c a l l yi n c r e a s i n gt h en u m b e ro fc o n n e c t i o n sf o re a c hp a r t i c l ei nt h ep o p u l a t i o n T h i sp a p e ra l s oi n v e s t i g a t e st h ei m p a c to ft h ei n c r e a
21、s er a t eo fe a c hp a r t i c l e Sc o n n e c t i o n so nt h ep e r f o r m a n c eo ft h ea l g o r i t h m T h r o u g has e r i e so fc l a s s i co p t i m i z a t i o nf u n c t i o nt e s t s，t h i sp a p e rs h o w st h a te f f e c t i v e n e s st h ep r o-p o s e da l g o r i t h m A n
22、 o t h e ri m p o r t a n ta s p e c to ft h i sp a p e ri st os t u d yt h ea p p l i c a t i o no ft h eP S Oi ns u p p l yc h a i nm a n a g e m e n t I nt h i sp a p e r,t h eb e e rd i s t r i b u t i o ng a m ei su s e da sa ne x a m p l et oi n v e s t i g a t et h ep o t e n t i a la p p l i
23、 c a t i o n si nt h es u p p l yc h a i nm a n a g e m e n t T h i sw e l lk n o w ng a m ew a sd e v e l o p e da tM I Ti nt h e1 9 6 0 sa n dh a sm a n yp a r a l l e l sw i t hs u p p l yc h a i no p t i m i z a t i o np r o b l e m s T h i sg a m eo f f e r sac o m p l e xs i m u l a t i o ne n
24、 v i r o n m e n ti n v o l v i n gm u l t i d i m e n s i o n a lc o n s t r a i n e dp a r a m e t e r s T r a d i t i o n a l l y,t h er e s e a r c hr e l a t e dt ot h i sg a m ei sb a s e dO nas i m p l ec u s t o m e rd e m a n dp a a e r n T h i sp a p e rd e s i g n st h eo t h e rt h r e e
25、m o r ec o m p l e xc u s t o m e rd e m a n dp a R e r n s I na d d i t i o n，f o re a c hc u s t o m e rd e m a n dp a t t e r n，w ea l S Oe x a m i n et w od i f f e r e n ts c e n a r i O S I nt h ef i r s ts c e n a r i o，a l lt h eg a m ep l a y e r su s et h es a m es t r a t e g yt om a n a
26、g et h e i ri n v e n t o r y I nt h es e c o n ds c e n a r i o，t h ed i f f e r e n tr o l e sc a l lu s ed i f f e r e n ts t r a t e g i e s F r o mt h eo p t i m i z a t i o np o i n to fv i e w,a st h em u c hm o r ep a r a m e t e r sa r ei n v o l v e di nt h es e c o n ds c e n a r i o，t h
27、e r e f o r ei tr e p r e s e n t sam o r ec o m p l e xo p t i m i z a t i o np r o b l e m T h r o u g has e r i e so fo p t i m i z a t i o n su n d e rd i f f e r e n ts c e n a r i o s，a n dTs t a t i s t i c a lt e s t so ft h er e s u l t s，w ef o u n dt h a tt h ep e r f o r m a n c eo ft h
28、ep r o p o s e da l g o r i t h mi sb e t t e rt h a nt h eg e n e t i ca l g o r i t h m s K e yW o r d s：P a r t i c l eS w a r mO p t i m i z a t i o n，D y n a m i cN e i g h b o r h o o dT o p o l o g y,G e n e t i cA l g o r i t h m s，S u p p l yC h a i nM a n a g e m e n t,B e e rD i s t r i b
29、 u t i o nG a m e，C o m p l e xD e m a n dV m一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究原创性声明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：至-红花日期：二f o 年6 月弓E t一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究学位论文使用授权声明学位论文使用
30、授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。学位论文作者签名：主l jI 工毳日期：泸(o 年6，月岁日翩躲仁叫畚日期：列，年(月了日一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究第1 章绪论第1 章绪论1 1 论文选题背景本文研究的兴趣是优化问题。所谓优化问题是指在满足一定约束条件下，寻找一组参数值，使系统的某些指标达到
31、最大值或最小值。优化问题几乎存在于现实生活中的各个方面。无论在在科学技术研究中还是在工程技术应用中，或者是在经济、管理以及具体生活中，我们都会经常遇到各种各样的优化问题。这些问题或大或小，大到整个国家乃至全社会的资源优化配置，小到日常生活中工作的具体安排等。我们虽然可以利用传统的优化算法解决其中很多问题，但是对于其中一大类问题由于本身的复杂性(比如N P 难问题)，传统的优化算法是很难处理的。为了解决这些大量存在的复杂优化问题，人们受群体智能或自然界一些现象的启发，提出了许多仿生群体智能算法。其中比较著名的有蚁群算法(模仿蚂蚁群体在路径选择和信息传递方面的行为)和粒子群算法(模拟鱼群或鸟群的觅
32、食行为)。群体智能是一种基于生物群体行为规律的计算技术，主要受群居动物的一些发杂社会行为启发。例如蚂蚁、蜜蜂、鸟群、鱼群和兽群等群体个体之间能够互相协作，以群体的力量进行筑巢、觅食、御敌等 1】。在这些群体中，单个个体的智能并不高，但通过自发的组织起来之后，。却能表现出来惊入的智能，解决很多复杂问题，例如：发现新的食物源、在群体内部产生劳动分工、建筑庞大复杂精巧的巢穴、跨越几千公里迁徙到指定地区、在狭窄的空间内协调调度等。而且这些群体系统所拥有的鲁棒性和高超解决问题能力仅仅是依靠一套在个体间和个体与环境间简单的交互规则就可以产生。总之，这些群体可以很快能适应群体组织的变化和处理外界的挑战，在工
33、程和计算机科学有着很重要的价值。粒子群算法(P S O)是由K e n e d y 博士和E b e r h a r t 博士在1 9 9 5 年提出【2，3】。这项技术的基本概念源于对鸟群捕食行为的研究。设想这样一个场景：一群鸟在一个空旷的田野里寻找食物。假设在这个区域里只有一块食物，且所有的鸟儿都不知道食物在哪里，但是他们却能感知当前的位置离食物大概还有多远。那么如何有效地找到食物昵?最简单有效的就是搜寻目前离食物最近的鸟的周第1 章绪论一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的库用研究围区域。粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智
34、能指导优化搜索。粒子群算法由于具有易于描述和实现、参数少、鲁棒性强，且具备并行处理能力和全局搜索能力等方面的特点，而越来越受到人们的关注，成为了国内外学者一个研究热点。然而粒子群算法从提出到现在才经历1 5 年的时间，其研究目前还处于初级阶段，还有很多问题值得研究。1 2 国内外粒子群算法研究现状目前对粒子群算法的研究主要包括理论研究，性能改进和应用研究三个方面。下面从这三个方面对粒子群算法的研究现状进行综述。在算法的理论研究方面，目前粒子群算法还没有成熟的理论分析，只有一些学者对算法的收敛性进行了分析。这主要因为粒子群算法涉及随机性，增加了数学分析的难度。在假设粒子间无相互影响等条件下，C
35、l e r c 和K e n n e d y 形式化地证明了粒子群算法的收敛性，并得到了单个粒子运动轨迹收敛的参数约束条件 4】。后来B e r g h 和E n g e l b r e c h t 在此基础上对该算法的收敛性做了进一步的研究。他们主要分析了参数对粒子轨迹的影响。目前大部分国内外研究者都在研究如何进一步改进粒子群算法的性能。概括起来，目前提出的改进方法主要有改善参数，增加种群的多样性，提出新的拓扑结构，融合其他算法。与其他智能算法相似，粒子群算法对参数的选择也是相当的敏感。一些参数起着调节算法的全局探测能力与局部搜索平衡的作用。S h i 和E b e r h a r t 在原
36、始粒子群算法中了引入惯性权重参数【5】。这一参数主要用来控制粒子运动的速度，实验表明这一参数提高了该算法的性能。后来又有学者发现使用线性递减，非线性递减等方法来控制这个参数能够进一步改进算法的性能，这包括E b e r h a r t 和国内的李宁等【6，7】。通过增加群体多样性的方法来改进粒子群算法的性能也是比较常见的思想方法【8 。有关这方面的文献比较多，采用的技术也有很多种，比如引入变异算子、采用高斯变异、控制粒子间的距离、分层次等思想方法 9，1 0，1 1，1 2】。目的是增加多样性，提高全局搜索能力，进而能增强搜索最优点的能力。虽然这些研究工作已经给出了提高粒子群算法全局搜索能力的
37、方法，但是它们很难在提高搜索速度和保持种群多样性之间达到平衡。在粒子群提出算法的早期，群体的拓扑结构还没有引起学者的广泛注意。最早调查使用星形和环形两种拓扑结构是E b e r h a r t 等人【1 3】。后来，K e n n e d y 比较系统地研究了拓扑结构对粒子群算法性能的影响【1 4】。他主要调2一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究第1 章绪论查了四种不同的拓扑结构：星形，环形，车轮形辐射结构和无规则的网状结构。实验结果并没有发现在任何情况下都表现非常好的拓扑结构，但确定的一点是拓扑结构对粒子群算法的性能有很大的影响。近年来，K e n n e d y
38、和M e n d e s 又进一步调查了群体结构对粒子群算法的影响。他们在2 0 0 2 和2 0 0 6 年测试了一系列不同的拓扑结构，主要有星形结构和很多不同的局部连接结构，以及冯诺依曼拓扑结构【1 5，1 6 。同时国内的张丽平博士也比较了不同拓扑结构对不同测试函数的性能的影响 1 7 。他们的测试结果基本一致：没有一种拓扑结构能适合所有测试函数，相对来讲全局模型是一个较差的模型，容易早熟。虽然粒子群算法和演化算法之间思想原理有差别，但当其与进化算法相结合得到新的算法，往往能产生一些比较好的效果。比如L o v b j e r g 等人将遗传算法的一些算子引入粒子群算法，得到了不错的效果
39、【1 8】。国内也有很多学者提出了许多这方面的算法【1 9，2 0，2 1 。另外也有不少文献致力于改进粒子位置更新的方式和信息共享的方式 2 2，2 3】。除此之外，由于粒子群算法最初只能优化连续空间里的问题，最近有许多改进的方法使其能够优化离散的问题 2 4，2 5 1。在算法的应用研究方面，在粒子群算法刚刚提出的早期，其应用的方面还比较少：主要包括函数优化问题和约束优化问题【2，2 6 ，神经元网络的训练，人类的帕金森综合症等颤抖类疾病分析【2 7】。如今经过短短十几年的发展，其应用研究迅速增长。这主要是因为该算法简单、易于实现、设置参数少、无需梯度信息等特点，其在连续非线性优化问题和组
40、合优化问题中都表现出良好的效果。现在，现在粒子群算法已经应用于非线性规划，同步发电机辩识，车辆路径，约束布局优化，新产品组合投入，广告优化，多目标优化等问题【2 8，2 9，3 0】。不过值得一提的是，粒子群算法还未在供应链管理方面有广泛的应用。1 3 本文研究内容及其主要贡献本文的研究包括粒子群算法性能的改进及其应用两个方面。粒子群算法性能的改进方面，本文主要针对粒子群算法的早熟收敛问题，提出了基于动态更新群体拓扑结构的新算法。种群拓扑结构是指整个种群所有粒子之间的连接方式。粒子群算法是一种随机性智能搜索算法，算法成功的关键在于能否有效地在早期全局开拓与晚期局部搜索解空间之间进行平衡。由于种
41、群的拓扑结构决定了信息在整个种群问的流动方式，而信息流动方式可以控制算法的探测和开发能力。目前最普遍使用的拓扑结构是星形和环形。在星形3第1 章绪论一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究拓扑结构下，每个粒子都与其他粒子相连接，因此信息流动最快，导致了粒子群算法收敛过快，出现“早熟”现象。而在环形拓扑结构下，每个粒子仅与相邻的两个粒子相连接，因此信息流通非常慢，最终导致使用该拓扑结构的粒子群算法收敛速度慢。因此，我们可以说星形和环形结构代表了信息流通速度的两个极端。但是我们不难发现环形结构满足了该算法早期对空间进行全局解空间探索的要求，而星形结构恰恰满足了该算法晚期对搜索
42、空间进行局部开发的要求。因此如果能够动态地改变拓扑结构将是一个有效的平衡探测和开发的要求，基于这个想法，本文提出了动态增加每个粒子连接个数的方法来改变群体的拓扑结构。本文还调查了增加的速度对算法的影响。本文通过对一系列经典优化函数进行测试，验证了提出算法的有效性。本文的另一个重要研究内容是把粒子群算法应用到供应链管理领域。本文以啤酒分配游戏为例研究了该算法在供应链管理中的潜在应用。啤酒分配游戏是上世纪6 0 年代在M I T 开发的，代表了一类典型的供应链管理优化问题。这个游戏提供了一个复杂的模拟环境，并涉及了多维受限制的参数。传统上，啤酒分配游戏的研究都是基于一个简单的客户需求。本文设计了其
43、它三种更为复杂的客户需求。另外，对每一种客户需求，我们还研究了两种不同的场景。在第一种场景下，所有啤酒分配游戏的角色都使用相同的策略管理他们的库存。在第二种场景下，不同的角色允许使用不同的策略。从优化的角度来说，由于第二种场景设计更多的参数，因此也是一种更为复杂的优化问题。通过对一系列不同情景下的供应链问题进行优化，并对结果进行T 统计检验分析，我们发现本文提出的算法的性能整体上优于传统的粒子群算法和遗传算法。概括地说，本文的主要贡献主要有以下两个方面：1 本文提出了一种改善粒子群拓扑结构的方法，并通过相关分析和实验验证表明了该方法的有效性。2 本文以啤酒分配游戏为例研究了该算法在供应链管理中
44、的潜在应用。1 4 论文章节安排本文将按如下结构进行组织：第l 章介绍了本文的研究背景，总结了研究问题的研究现状，同时简要地概述了本文的主要研究内容和主要贡献。第2 章详细介绍标准粒子群算法，并对其进行详细分析。4一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究第1 章绪论第3 章提出动态更新拓扑结构的粒子群算法，并进行了实验分析。第4 章将提出的算法应用到供应链管理领域。第5 章将总结本文的工作，并展望在本文研究的基础上可以进行的下一步研究工作。5一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究第2 章粒子群算法第2 章粒子群算法2 1 粒子群算法产生背景自然界中
45、，鸟群或者鱼群中的个体运动看起来是离散的和随机的，但它们在整体运动中却表现出惊人的一致性，其整体运动形态却非常流畅且极富美感。这种似乎有意识的群体协同行为直是许多研究学者感兴趣的问题。其中生物学家C r a i gR e y n o l d s 在1 9 8 7 年设计了一个有非常大影响的鸟群飞行模拟模型【3 l】。在这个模型中，R e y n o l d s 假设每一个个体1 在飞行中遵循下面三个规则：1 避免与邻近个体碰撞。2。匹配与邻近个体的速度。3 飞向它所感受到的鸟群中心。仅仅利用这些简单的规则，就可以非常接近真实的模拟出鸟群飞行行为。另外在R e y n o l d s 的实验中还
46、显示遵循这些规则的飞行鸟群是相当耦合的群体，比如当在飞行中遇到障碍物时，他们会分开穿过障碍物然后又重新聚集在一起。R e y n o l d s 的这些规则已经广泛地用来模拟电影中的鸟群或牧群的聚集行为。后来另外两名研究学者H e p p n e r 和G r e n a n d e r 在此基础上也提出了另外一种模拟鸟群行为的方法【3 2】。这个模型增加了鸟群的栖息地这个条件，开始时每一只鸟都没有特定的飞行目标，但只使用上面的规则l 和2，当有一只鸟飞回栖息地时，它周围的鸟也会跟着飞回栖息地，这样到最后整个鸟群都会回到栖息地。受上述模拟乌群运动的影响，社会心理学博士J a m e sK e
47、n n e d y 和电子工程学博士R u s s e l lE b e r h a r t 在 1 9 9 5 年提出了粒子群算法【2，3】。他们最初的设想只是模拟简单的社会系统，研究和解释复杂的社会行为，但后来发现粒子群算法是一种很有效的优化工具。如今由于粒子群算法本身的简洁性和高效性，近些年来，它已经成为了进化计算领域的一个研究热点。1 在他的文章中，每个个体称之为“b o i d 7第2 章粒子群算法一种基于动态群体结构的粒子群算法及其在啤酒分配游戏中的应用研究2 2 最初的粒子群算法正如上面刚刚提到的，最早的粒子群算法是由J a m e sK e n n e d y 和R u s s
48、 e l lE b e r h a r t 在1 9 9 5 年开发的 2，3】。粒子群算法是基于鸟群或鱼群觅食的行为而设计的。在寻找食物过程中，鸟类通常与同伴进行信息沟通，然后调整自己飞行速度和方向，从而提高找到食物的概率。该算法模拟这一过程，把鸟群寻找食物的过程抽象为粒子群寻找最优解的过程。粒子群算法本质上与其他进化计算算法相似，也是基于群体的反复迭代算法。下面使用比较形式化的语言描述其最初的版本。粒子群中每一个粒子是没有质量和体积的，但可以在d 维空间里按一定的速度飞行。其中d 代表了需要优化问题的参数个数。飞行速度根据它自身的飞行经验以及同伴的飞行经验进行动态调整。每个粒子记录了一些飞
49、行经验信息，因此粒子都是有记忆的。这些信息包括当前的飞行位置，当前的飞行速度，自己曾经飞行过的最好位置和同伴曾经飞行过的最好位置。其中中粒子飞行位置的好坏(或称为粒子的适应度)是通过目标函数来衡量的。第i 个粒子的位置表示为甄=(戤1，z 仍，z t d)，飞行速度表示为饥=(仇1，V i 2，r i d)，曾经飞行过的最好位置表示为P i=(P i l，P i 2，P i d)以及同伴曾经飞行过的最好位置表示为g i=(g i l，9 1 2，g i r l)。在每一代，每个粒子先对自己的飞行速度进行调整，然后调整飞行的位置。其中速度是根据自己当前的速度，自己曾经飞行过的最好位置及同伴的最好
50、位置进行进行调整的，位置是根据更新过的速度进行调整。公式2 _ 1 和3-4 分别形式化了粒子i 的速度及位置是怎样调整的。加速常数参数c】和c 2 一般在f 0 7，2 1 之间取值，它们代表着将粒子i 向自己最好的位置及同伴的最好位置移动的的快慢；低的值允许粒子在最好的位置外徘徊，高的值则粒子很快的移向最好的位置。c 1 和c a 也经常被称为学习因子。r a n d()和R a n d()是两个在f 0，1 1 变化的随机函数。饥=仇+C 1 木r a n d()木慨一X i)+C 2 率R a n d()木(g i 一甄)(2 1)X i=翻+仇(心)这种最初的粒子群算法以及后来的绝大