（通信与信息系统专业论文）群智能优化算法理论及在资源调度中的应用研究.pdf

山东大学硕士学位论文 中文摘要 最优化问题广泛存在于工程技术、科学研究和经济管理等诸多领域之中。目 前常用的求解最优化问题的优化算法可以分为：经典优化算法、贪婪算法和局部 搜索、智能优化算法、混合优化算法等。与经典优化算法相比，智能优化算法具 有很多优点，如操作简单、收敛速度快、全局收敛性好、鲁棒性强等。群智能优 化是智能优化的一个重要分支。社会性昆虫的个体行为和智能十分简单、有限， 但是通过相互合作形成的群体却能够完成复杂的任务。群智能优化就是通过模拟 社会性昆虫的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优。 人工鱼群算法是通过对鱼类群体行为的模拟而提出的一种群智能优化算法。 与其它群智能优化算法一样，人工鱼群算法具有很多优点，如对目标函数和参数 设置容忍性好、收敛速度快、并行性好等：但是作为一种新的群智能优化算法， 它也同时具有某些缺点，如算法后期收敛速度较慢、由于各种随机因素的存在收 敛精度不高等。为了提高人工鱼群算法的收敛性能，本文提出两种改进的人工鱼 群算法：基于混沌搜索和反馈策略的改进人工鱼群算法和量子人工鱼群算法。多 模函数优化问题和多目标函数优化问题是两类重要的最优化问题，本文将对基于 人工鱼群算法的多模函数优化问题和多目标函数优化问题进行研究。 资源调度问题是实际生活中经常遇到的一种最优化问题，其主要研究的是在 一定的约束条件下，如何合理地将有限的资源分配给指定的用户使其完成一批给 定的任务，获得某些性能指标的最优化。车间作业调度问题是一个非常著名的资 源调度问题模型，它也是一个非常复杂的n p h a r d 组合优化问题。认知无线电是为 解决无线电频谱资源匮乏而提出的，其中频谱分配是认知无线电的关键技术之一。 频谱分配就是研究在给定的限制条件下，如何将有限的频谱资源分配给一定数量 的认知用户，从而实现系统总效益的最大化同时保证所有用户的公平性，频谱分 配问题也是一种资源调度问题。本文将对基于人工鱼群算法的资源调度问题进行 研究，利用人工鱼群算法解决车间作业调度和认知无线电中的频谱分配这两个资 源调度问题。 分配 关键词：群智能；人工鱼群算法；函数优化；车间作业调度；认知无线电频谱 山东大学硕士学位论文 ab s t r a c t o p t i m i z a t i o np r o b l e m se x i s tw i d e l yi nm a n y f i e l d ss u c ha se n g i n e e r i n gt e c h n o l o g y , s c i e n t i f i cr e s e a r c h , e c o n o m i cm a n a g e m e n ta n d8 0o n - a tp r e s e n t , t h ec o m m o n o p t t m i z a t i o na l g o r i t h mf o rs o l v i n gt h eo p t i m i z a t i o np r o b l e m st a i l b ed i v i d e di n t o c l a s s i c a l o p t i m i z a t i o na l g o r i t h m , g r e e d ya l g o r i t h m a n dl o c a ls e a r c h a l g o r i t h m , 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 , h y b r i do p t i m i z a t i o na l g o r i t h ma n ds oo n c o m p a r e w i t hc l a s s i c a lo p 捌o na l g o r i t h m , 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 mh a sal o to f a d v a n t a g e s ，s u c h 嬲e a s i l yo p e r a t i n g , f a s tc o n v e r g e n c e ，g o o dg l o b a ls e a r c h i n ga b i l i t y , s t r o n gr o b u s t n e s sa n ds oo n s w a r mi n t e l l i g e n c eo p t i m i z a t i o ni sa ni m p o r t a n tb r a n c ho f i n t e l l i g e n c eo p t i m i z a t i o n i n d i v i d u a lb e h a v i o u ra n da b i l i t yo fs o c i a li m e e ta 他v e r y s i m p l ea n dl i m i t e db u tc o l o n yo f s o c i a li n s e c tc a na c h i e v ec o m p l e xt a s k si nc o o p e r a t i o n s w a r mi n t e l l i g e n c eo p t i m i z a t i o ni si m p i r e df r o mt h ec o l l e c t i v eb e h a v i o ro fs o c i a l i n s e t sa n di sr e a l i z e db yt h ec o m m u n i c a t i o na n dc o o p e r a t i o nb e t w e e ni n d i v i d u a l s a r t i f i c i a lf i s hs w a r ma l g o r i t h m ( a f s a ) i sak i n do fs w o _ r r f li n t e l l i g e n c e o p t i m i z a t i o na l g o r i t h mw h i c hi sp r o p o s e db y 砌t a l 吨t h eg r o u p b e h a v i o ro ff i s h a f s a h a sm a n ya d v a n t a g e s 鹤o t h e rs w a r mi n t e l l i g e n c eo p t i m i z a t i o na l g o r i t h ms u c ha sg o o d t o l e r a n c eo ft h eo b j e c t i v ef u n c t i o na n dp a r a m e t e r ss e t t i n g ，f a s tc o n v e r g e n c e ，g o o d p a r a l l e l i s ma n d8 0o n a sa n e w8 w r i ni n t e l l i g e n c eo p t i m i z a t i o na l g o r i t h m , a f s ah a s s o m es h o r t c o m i n g st o o ，s u c h 雒c o n v e r g e n c es l o wa tt h el a t e rs t a g eo ft h eo p f u n i z a f i o n p r o c e s s ，t h el o wa c c u r a c yb e c a u s eo ft h er a n d o mf a c t o ra n ds oo n i no r d e rt oi m p r o v i n g t h ep e r f o r m a n c eo fa f s a , w ep r o p o s e dt w ek i n d so fi m p r o v e da r t i f i c i a lf i s hs w a r m a l g o r i t h m0 a f s a ) i nt h i sp a p e r ：i m p r o v e da r t i f i c i a lf i s hs w a r ma l g o r i t h mb a s e do n c h a o t i cs e a r c ha n df e e d b a c ks t r a t e g ya n dq u a n t u ma r t i f i c i a lf i s hs w a r ma l g o r i t h m m u l t i - m o d a lf u n c t i o no p t i m i z a t i o np r o b l e m sa n dm u l t i - o b j e c t i v ef u n c t i o no i 疵i 删o n p r o b l e m sa r ct w oi m p o r t a n tk i n d so ff u n c t i o no p m n i z a t i o np r o b l e m s w ew i l lr e s e a r c h t h em u l t i - m o d a lo p 捌o na n dm u l t i - o b j e c t i v eo p t u n i z a t i o nb a s e do na f s ai nt h i s p a p e r r e s o u r c es c h e d u l i n gp r o b l e m si sac o m m o no p t i m i z a t i o np r o b l e m sw h i c hw eo f i t c l l m e e ti no u rr e a l l i f es i t u a f i o m i tm a i n l ys t u d yh o wt oa s s i g nf i n i t el e s o u r c e st ot a s k st o o p t i m i 犹s o m ep 砷o r m a n c ec r i t e r i o nu n d e rs o m ec o n s t r a i n tc o n d i t i o n s j o bs h o p s c h e d u l i n gp r o b l e m ( j s s p ) i sav e r yf a m o u sr c s o l l t o es c h e d u l i n gp r o b l e m sm o d e la n di t 2 山东大学硕士学位论文 i sa l s oac o m p l i c a t e dn p - h a r dc 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 s c o g n i t i v er a d i o ( c r ) i sp r o p o s e df o rs o l v i n gt h ep r o b l e mo ft h es c a r c i t yo ft h er a d i os p e c t r u ma n d s p e c t r u ma s s i g n m e n ti so n eo fk e yt e c h n o l o g yi nc r s p e c t r u ma s s i g n m e n tm a i n l y r e s e a r c h e sh o wt oa s s i g nf i n i t es p e c t r u mr e s o u r c e st oc e r t a i nc o g n i t i v eu 9 朗芯t o m a x i m i z es y s t e mt o t a lb e n e f i t sa n dg u a r a n t e et h ef a i r n e s so fa l lc o g n i t i v eu s e r sa tt h e s a i n et i m eu n d e rt h eg i v e nc o n s t r a i n tc o n d i t i o n s s p e c t r u ma s s i g n m e n ti sas o r to f i 吧s o l l r c es c h e d u l i n gp r o b l e m s w ew i l lr e s e a r c ht h er e s o u r c es c h e d u l i n gp r o b l e m sb a s e d a f s aa n ds o l v et h ej s s pa n ds p e c t r u ma s s i g n m e n tp r o b l e m su s i n ga f s ai nt h i sp a p e r k e yw o r d s ：s w a r mi n t e l l i g e n c e ；a r t i f i c i a l f i s hs w a r ma l g o r i t h m ；f u n c t i o n o p t i m i z a t i o n ；j o bs h o ps c h e d u l i n gp r o b l e m ；s p e c t r u ma l l o c a t i o ni nc o g n i t i v er a d i o 3 山东大学硕士学位论文 s 认 a f s a p s o a c a s a g a 蛏 c s q c q u b i t m o r c s m o p g d g a f s a j s s p t s c r p u s u s a 4 符号说明 s w a r mi n t e l l i g e n c ea l g o r i t h m a r t i f i c i a lf i s hs w a r ma l g o r i t h m p a r t i c l es w a r mo p t i m i z a t i o n a n tc o l o n ya l g o r i t h m s i m u l a t e da n n e a l i n g g e n e t i ca l g o r i t h m s a r t i f i c i a lf i s h c h a o t i cs e a r c h q u a n t u mc o m p u t i n g q u a n t u m b i t s m u l t i m o d a lo p t i m i z a t i o n r e s t r i c t e dc o m p e t i t i o ns e l e c t i o n m u l t i o b j e , c t i v eo p t i m i z a t i o np r o b l e m g e n e r a t i o n a ld i s t a n c e g l o b a la r t i f i c i a lf i s hs w a r ma l g o r i t h m j o bs h o ps c h e d u l i n gp r o b l e m t a b us e a r c h c o g n i t i v er a d i o p r i m a r yu s e r s e c o n d a r yu s e r s p e c t r u ma l l o c a t i o n 群智能算法 人工鱼群算法 粒子群算法 蚁群算法 模拟退火算法 遗传算法 人工鱼 混沌搜索 量子计算 量子比特 多模优化 限制竞争选择 多目标优化问题 世代距离 全局人工鱼群算法 车间作业调度问题 禁忌搜索 认知无线电 主用户 次用户 频谱分配 山东大学硕士学位论文 1 1 最优化问题 第一章群智能优化算法 最优化问题的主要研究内容是：对于一个给定的问题，如何从众多的解决策 略中寻找最优的解决策略从而获取最大的收益。最优化问题广泛的存在于工业、 农业、交通、能源和通信等众多的领域。迄今为止，最优化技术已成功应用于模 式识别、系统控制、生产调度等领域并获取了巨大的效益。 最优化问题可以定义为：在给定的约束条件下，求解目标函数的最大或者最 小值。其数学模型描述如下【1 】： m a x f ( x )( 1 1 1 ) s g o ) 0 j i i ( x ) = 0 工d 其r 扣f ( x ) 是目标函数，g ( x ) 和h ( x ) 分别是不等约束和等式约束，d 是自变量定义域。 最优化问题可分为两类：连续函数优化问题和组合优化问题。连续函数优化 的对象是一定区间内的连续变量，可以用一些b e n c h m a r k 典型问题测试连续函数 优化算法的性能。组合优化的对象则是解空间中的离散状态，典型的组合优化问 题包括：旅行商问题( 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 ) 、车间作业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s s p ) 、0 l 背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i n p a c k i n g p m b l e m ) 等。 解决最优化问题的方法就是优化算法，它是一种以数学为基础，用于求解各 类工程问题优化解的应用技术。目前工程中常用的优化算法主要有经典优化算法、 贪婪算法和局部搜索、智能优化算法和混合优化算法等。 经典算法包括最速下降法、共轭梯度法、牛顿法、单纯形法等，它是基于严 格的数学模型优化算法，当待优化问题比较复杂( 例如变量维数高、非线性强、约 束多) 时，其求解质量难以满足工程需要。贪婪算法和局部搜索算法的主要代表是 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 、禁忌搜索算法( t a b us e a r c h ，t s ) ，这两 种算法理论上可以收敛于最优值，但是收敛速度较慢。智能优化算法的典型代表 5 山东大学硕士学位论文 是粒子群算法( p 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 n tc o l o n ya l g o r i t h m ， a c a ) 、演化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 。智能优化算法具有收敛速度快、 收敛性能好、适用范围广等优点，尤其是当待求解的最优化问题比较复杂时，它 们的优势更加明显。 1 2 群智能优化算法概述 1 2 1 群智能优化算法简介 群智能( s w a r mi n t e l l i g e n c e ，s i ) 是通过对一些具有社会性行为的动物群体( 如鸟 群、鱼群、蚁群、蜂群) 进行研究、建模、仿真而建立起来的一个概念。这些群体 之中的单个个体能力有限、行为简单，但是当它们组成一个种群，协同工作时， 却能拥有不可思议的能力。1 9 9 9 年，b o n a b e a u 、d o r i g o 和t h e r a u l a z 在他们的著 作“s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt oa r t i f i c i a ls y s t e m s 1 2 】给出了群智能的一种 不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法 或分布式解决问题的策略均属于群智能。 群智能的一个重要研究方向就是群智能优化算法( s w a r mi n t e l l i g e n c e a l g o r i t h m , s 队) ，将搜索过程和优化过程模拟为社会性动物仿生个体的进化过程 或觅食过程，利用社会性动物组成的种群表现出来的强大的能力进行最优化问 题的求解。目前提出的群智能优化算法主要包括：粒子群算法、蚁群算法、 人工蜂群算法( a r t i f i c i a lb e ec o l o n ya l g o r i t h m ，a b c a ) 、细菌觅食算法 ( b a c t e r i a lf o r a g i n ga l g o r i t h m ，b f a ) 等 目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大 多数优化问题的新方法，更重要的是，群智能潜在的并行性和分布式特点为处理 大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研 究的角度分析，群智能理论及应用研究都具有重要的学术意义和现实价值。 1 2 2 粒子群算法 粒子群算法是由g e n n e d y 和e b e r h a r t 在1 9 9 5 年提出的一种基于群智能的计算方 法1 3 1 ，是一种群智能优化方法。鸟群觅食时，虽然鸟群不知道食物的具体位置，但 是通过所有飞鸟的合作和信息交互，鸟群能够很快聚集在食物附近。粒子群算法 6 山东大学硕士学位论文 就是通过模拟飞鸟的集群觅食行为，利用飞鸟之间的协作达到寻优的目的。 粒子群算法采用速度位移模型，每个解对应搜索空间中一只飞鸟的位置，这 些飞鸟称为粒子( p a r t i c l e ) 。粒子是一个没有质量和体积、仅仅有自己的位置和速度 的虚构的概念。每一个粒子都是一个潜在解，其位置对应一个由目标函数决定的 适应值( f i t n e s s v a l u e ) ，粒子还有一个速度决定它飞行的方向和距离。所有粒子 追随当前的最优粒子在解空间中进行搜索。 设搜索空间为d 维，总粒子数为刀。第f 个粒子位置表示为向量 f = ( ，艺) ；速度r = ( v ：i ，吒，吃) 。则在标准粒子群算法中，每个粒 子在搜索空间中的速度和位置根据如下公式确定： ，：+ l = 叫+ qx r a n d o ( p b e s t - x ；) + c 2x r a n d o x ( g b e s t - x ；) ( 1 2 1 ) l = 爿+ 1 j ； ( 1 2 2 ) 其中彩是惯性权重，c m 和乞是加速常数，r a n d o 用于产生【o ，1 】之间均匀分布的随机 数，p b e s t 和g b e s t 分别为t 时刻粒子的自身最好位置和全局最好位最。上述速度公 式第一部分为记忆部分，表示粒子对当前自身运动状态的信任，第二部分为认知 部分，表示粒子本身的思考，第三部分为社会部分，表示粒子间的相互合作与信 息共享。 粒子群算法仅需要设置惯性权重国和加速常数c l 、c 2 的大小，具有操作简单、 收敛速度快的优点，另外粒子群算法的鲁棒性较强，并且适用于并行处理；粒子 群算法的缺点是容易陷入局部极值，搜索精度不高。由于粒子群算法具有以上一 系列优缺点，很多学者对其进行了理论( 例如算法模型分析1 4 5 1 ) 、应用( 例如p i d 参数 控制【6 】、控制与决策【刀、多目标优化嗍、聚类分析9 】等) 方面的研究。 1 2 3 蚁群算法 蚁群算法是由意大利学者d o r i g o 和m a n i e z z o 等人受自然界中蚁群的觅食行为 启发而提出的一种群体智能算法1 1 0 1 。蚂蚁是一种社会性动物，单个蚂蚁的行为十 分简单，但是通过相互协作，蚁群却能表现出复杂的行为，完成复杂的任务。蚁 群觅食过程中，往往能找到一条蚁穴与食物之间的最短路径，甚至当环境发生变 化时，蚁群也能迅速找到新的最短路径。蚁群寻找最短路径的能力是通过一种称 7 山东大学硕士学位论文 为信息素的化学物质实现的，蚂蚁会在其经过的路径上释放信息素，而后面的蚂 蚁则会根据前面蚂蚁释放的信息素选择路径。最短路径上经过的蚂蚁最多，信息 素浓度最高，从而被后面的蚂蚁选择的概率也就越高。正是通过这种正反馈机制， 蚁群算法通过虚拟“蚂蚁”摸索不同路线，并留下随时间逐渐消失的虚拟 “信息素”，然后根据“信息素较浓的路线更近”的原则，就能找出最佳路线。 下面就以蚁群算法解决t s p 问题为例来介绍蚁群算法的实现方法。首先将m 只蚂蚁随机放到刀个城市中，每只蚂蚁通过一定的概率选择下一个尚未访问 过的城市直到走完所有城市。每只蚂蚁会在其经过的路径上释放信息素。在t 时刻，蚂蚁k 从城市i 转移到城市，的概率如下： 。i 童畿，反 露： 五h r ( f ) 】川叫删纠 ( 1 2 3 ) 【 。t h e r 霄；s e 其中a l l o w e d k 表示蚂蚁七下一步允许选择的城市的集合，( f ) 为城市f 与城市j 之 间路径上的信息素浓度，r # ( t ) 为启发因子，一般取城市f 与城市，距离的倒数，口 和分别为信息素和启发因子的相对重要程度。所有蚂蚁走完所有城市后，各城 市间的信息素浓度按下式更新： 勺( f + 刀) = ( 1 一p ) r ( t ) + a r c ( 1 2 4 ) 巧= c ( 1 2 5 ) 其中以0 户 1 ) 为路径上信息素的蒸发系数，为本次迭代过程中城市i 与城市 歹问路径上的信息素增量，f ：为第k 只蚂蚁本次迭代过程中在城市i 与城市j 问路 径上留下的信息素。上述过程循环执行直到满足循环终止条件。 蚁群算法通过信息素提供的正反馈机制进行寻优，具有鲁棒性强、并行 性好等优点，非常适合于组合优化问题的求解；但是也存在收敛速度慢、易 出现早熟收敛等缺点。针对其缺点，众多学者提出了很多改进蚁群算法，如 最大最小蚂蚁系统( m a x m i na s ，m m a s ) ! l l l 、最优解保留策略蚂蚁系统u o l 、 3 山东大学硕士学位论文 基j ：排序的蚂蚁系统1 1 2 j 等。i _ 前，蚁群算法止被j - 泛j 衄川j 各种组l 合优化问 题的求解之。 ，如4 ：图符色问题1 1 3 j 、1 ij i i j 作业调度问题1 1 4 l 、机器人路径规划 问题1 1 5 i 、路山算法设计i 6 1 等领域均取得了良好的效果，也彳丁学者尝试将蚁群 算法应用于连续问题的优化中。 1 3 人工鱼群算法 1 3 1 人工鱼群算法的基本思想 人：j ：鱼群算法( a n i 6 c a jf i s hs w a r ma l g o r i t h m ，a f s a ) 是由李晓磊1 1 7 1 于2 0 0 2 年 提出的一种基于群智能和人工智能的智能优化算法。在一片水域中，聚集鱼类最 多的地方往往就是这片水域中食物最为丰富的地方。模拟鱼类的这个特点构造人 i ：鱼( a r t i f i c a lf i s h ，a f ) ，每条人：f 鱼对应于一个优化解，人工鱼生存的虚拟水域 对应于优化问题的解空问，食物浓度对应于目标函数值，通过人工鱼群在虚拟水 域中的游动实现寻优，这就是人工鱼群算法的基本思想。 1 3 2 人工鱼 人工鱼是人工鱼群算法中的基本寻优t - ：体，它足对自然界中真实鱼类的模拟。每 条人i ：仉既包括自身的一些数据参数如移动步长、视野等，也包括一些行为如感知外 界变化、向某一个方向前进等。一个基本人：i ：值模型如图1 3 1 所示。人1 ：包可以通 过某种感官感知外界环境的变化，然后作出相应的反应；在人工鱼群算法中人_ 1 ：鱼通 过视觉感知外界环境变化；人工鱼生存的环境包括优化问题的解空问和其它人工鱼的 状态；而人i ：鱼作出的反应就是执行某种行为向某一个方向d 进一步。外界环境可以 影响人：1 ：鱼的活动，人工鱼也会通过自己的活动影响外界环境和其它人： 鱼。 i + 环嚏 ， 划 | 4 | 1 3 1 人l ：鱼模喇 9 山东大学硕士学位论文 1 3 3 人工鱼四种基本行为描述 假设优化问题解空间的维数为刀，人工鱼当前的位置是x = ( 五，五，鼍) ， 人工鱼移动的目标位置是五= ( 矸，霹) ，则人工鱼由当前位置向目标位置 前进一步的移动方式如下： f = 置+ v i s u a l * r a n d o ，i = l ，2 ，n ( 1 3 1 ) “+ 尚s t e p r a n d 0 ( 1 3 2 ) 其中h s u a l 是人工鱼的最大感知距离，s t e p 是人工鱼移动的最大距离。 人工鱼的四种基本行为包括：觅食行为a f、追尾行为、聚群p r e y a ff o l l o w 行为a fs w a r m 和随机移动行为a fm o v e 。其中觅食行为是人工鱼的基本行为， 它保证了算法的收敛性，聚群行为和追尾行为加速了算法的收敛速度，随机移动 行为则可以增强算法的全局收敛性。四种行为的具体的行为描述如下： 觅食行为：假设人工鱼当前位置是置，人工鱼在其视野范围内随机选择一个 新位置z ，如果艺优于z ，则人工鱼按照式( 1 3 1 ) 和( 1 3 2 ) 向新位置移动一步；否 则人工鱼重新选择新位置。如果人工鱼尝试t r y次后仍未找到一个比当前_number 位置优的新位置，则人工鱼执行随机移动行为。 追尾行为：假设人工鱼当前位置是五，探索其邻域内( 即吒 v i s u a l ) 的最优人 工鱼的位置一，如果优于i 并且 艿r ( 万拥挤度因子，为当前人工 鱼邻域内的伙伴数目) ，则人工鱼按照式( 1 3 1 ) 和( 1 3 2 ) 向位置x ，移动一步；否则 人工鱼执行觅食行为。 聚群行为：假设人工鱼当前位置是五，探索其邻域内( 即吒 v i s u a l ) 伙伴数目 刀厂及中心位置t ，如果艺优于z 并且艺刀厂 万z ，则人工鱼按照式( 1 3 1 ) 和( 1 3 2 ) 向位置置移动一步：否则人工鱼执行觅食行为。 随机移动行为：人工鱼在其视野范围内随机选取一个位置然后按照式( 1 3 1 ) 和( 1 3 2 ) 向选取的新位置移动一步。 i 0 山东大学硕士学位论文 1 3 4 人工鱼群算法的实现流程 为记录最优人工鱼的状态，在人工鱼群算法中引入公告板。人工鱼每次迭代 完成后都会比较自身的状态与公告板的状态，如果自身状态优于公告板状态，就 用自身状态更新公告板，因此公告板记录下了历史最优的状态，可以作为算法最 终的运行结果输出。 人工鱼群算法的实现流程如下： 1 ) 初始化设置，包括人工鱼群规模，人工鱼的初始位置，人工鱼步长s t e p ， 视野h s u a l ，重试次数砂n u m b e r ，拥挤度因子万等； 2 ) 计算每条人工鱼的适应度值，将最优人工鱼的状态记入公告板； 3 ) 对每条人工鱼进行行为评价，从四种基本行为( 觅食行为，聚群行为，追尾 行为，随机行为) 中选择一种最优的行为； 4 ) 执行选择的行为，更新人工鱼的位置信息； 5 ) 计算每条人工鱼的适应度值，更新公告板； 6 ) 如果满足循环结束的条件就输出结果，否则就跳转到3 ) 。 1 4 本章小结 本章我们首先介绍了最优化问题的基本概念和数学模型，并对常用的优化算 法进行了分类；然后阐述了群智能的概念，并且给出了两种常用的群智能优化算 法一粒子群算法和蚁群算法的详细介绍；最后介绍了人工鱼群算法的实现思想， 给出了人工鱼模型以及人工鱼的四种基本行为的详细描述，并且描述了人工鱼群 算法的具体实现流程。 山东大学硕士学位论文 2 1 引言 第二章改进人工鱼群算法 人工鱼群算法通过自下而上的设计方法，利用人工智能方法设计人工鱼，然 后基于群智能的思想，由人工鱼组成的群体在优化问题的解空间内进行寻优，最 终得到优化问题最优解。作为一种新的群智能优化算法，人工鱼群算法具有如下 的优点： 1 ) 宽容性好：人工鱼可以在优化问题的解空间内随机初始化，人工鱼的参数 如视野、步长、尝试次数等可以在较大的范围内取值，只需要给出优化问题的目 标函数值计算方法，对待优化问题无其它要求。 2 ) 实现简单：人工鱼在优化问题解空间随机初始化然后进行迭代搜索即可得 到优化解，容易实现； 3 ) 较好的全局收敛性：由于人工鱼具有随机移动行为，从而为算法提供了跳 出局部极值的可能性，使得算法具有较好的全局收敛性； 4 ) 收敛速度快：尽管算法中存在随机步长、随机移动行为等随机因素，但是 是由于觅食行为的存在，从总体上看，人工鱼是逐渐向最优值前进的，而追尾行 为和聚群行为更是加快了算法的收敛： 5 ) 并行性好：所有人工鱼在优化问题的解空间内并行搜索。 任何事物都具有两面性，人工鱼群算法虽然具有以上一系列优点，但同时也 存在一些缺点需要改进，例如： 1 ) 由于算法中存在随机步长、随机移动行为等随机因素，算法的寻优精度不 高，同时人工鱼的随机移动使得算法后期的收敛速度变慢。 2 ) 虽然人工鱼的随机移动行为在一定程度上可以保证算法的全局收敛性，但 是当优化问题局部极值很多并且局部极值与全局最优点相距较远时，人工鱼很难 跳出局部极值。 3 ) 随着人工鱼群规模的扩大，本算法的计算量急剧变大，需要更大的存储空间。 为了克服人工鱼群算法的缺点，很多学者提出了大量的改进思路，如加入生 存竞争机制的人工鱼群算法【l t i 、自适应策略人工鱼群算法【l q 、最优个体保留策略 山东大学硕士学位论文 人工鱼群算法【1 纠、加入全局信息人工鱼群算法【2 0 1 、模拟退火鱼群混合优化算法【2 l 】 等。接下来的两节将介绍两种改进的人工鱼群算法并对其寻优性能进行分析。 2 2 基于混沌搜索和反馈策略的改进人工鱼群算法 混沌运动貌似随机，却隐含着精致的内在结构，具有遍历性、随机性等特性， 能在一定范围内按其自身规律不重复地遍历所有状态，由于混沌运动的遍历性， 混沌可以作为一种局部搜索方法提高其它优化算法的全局搜索能力。人工鱼群算 法中已经搜索到的最优解也可以作为反馈信息用来指导人工鱼的移动，步长、视 野和行为选择等都可以根据反馈信息进行自适应的调整。为克服上节提到的人工 鱼群算法的缺点，本节提出一种基于混沌搜索和反馈策略的改进人工鱼群算法。 混沌搜索被引入人工鱼群算法来提高算法的全局收敛性，而公告板上记录的信息 被用来作为反馈信息指导人工鱼的移动从而提高人工鱼群算法的收敛精度和收敛 速度。 2 2 1 混沌搜索 混沌是自然界中一种较为普遍的现象，它看似混乱，却有着精致的内在结构。 混沌现象具有以下特征：( 1 ) 混沌现象的轨迹对初始值非常敏感。( 2 ) 确定性，混沌 轨迹通常是由确定的迭代公式产生的。( 3 ) 遍历性，混沌轨迹可以无重复的遍历一 定范围内的所有状态。 混沌现象与随机现象是非常相似的，但是实验结果表明混沌信号要明显比随 机信号好，尽管不能用明确的理论来证明【2 7 】；同样的道理，混沌搜索的效果也一 定比随机搜索的效果好。由于执行简单并且能够避免陷入局部极值，混沌搜索已 经成为一种新颖的局部搜索技术。 假设一个刀维优化问题，是其第j 维决策变量并且气鲥 乃 叫，则混 沌搜索的步骤可以具体描述如下： 1 ) 令七= 0 ，利用以下公式将第j f 维决策变量x r 映射为混沌变量饯严： a 卜兰主鱼( 2 2 1 ) 山东大学硕士学位论文 2 ) 利用混沌映射在“c x ，k ) 的基础上产生下一代混沌变量饯+ 1 ) ； 3 ) 利用以下公式将混沌变量“m 映射回为决策变量蜉卅) ： 矿= + ( 一) ( 2 2 2 ) 4 ) 评价新的决策变量石( i + 1 ) 的优劣； 5 ) 如果新的决策变量拶+ 1 优于工严，输出( 茸“n ，管+ 1 ，蜉+ 1 ) 作为混沌局 部搜索的结果，否则令k = k + l ，返回2 ) 。 其中第2 步中的混沌映射有很多种映射方法，这里我们选择的是l o g i s t i c 映射。 l o g i c 映射的迭代方程如下所示： z ( k - - 1 ) = z ( 七) ( 卜z ( 七) )( 2 2 3 ) 上式中是控制参数，当= 4 ，上式处于混沌状态，也就是说除( o ，0 2 5 ，0 5 ，o 7 5 ，1 ) 这几个点外，其它点都是通过迭代公式产生的，它们都处于o 和l 之间。因为混 沌现象的轨迹对初始值非常敏感，如果刀个决策变量的初始值不同，那么就可以 得到 i 个不同的混沌轨迹。 2 2 2 反馈策略 在人工鱼群算法中，为保存最优人工鱼的状态，引入了公告板的概念。每条 人工鱼执行完移动操作后就检验自身状态与公告板的状态，若自身状态优于公告 板状态，则用自身状态代替原公告板状态，这样公告板就可以记录下历史最优状 态。其实公告板记录的状态也可以反馈给人工鱼用来指导人工鱼下一步的移动。 基于这一思路，我们为人工鱼定义一个新的行为：反馈行为( a f _ t o g b e s t ) 。这一行 为可以具体描述为：人工鱼向公告板记录的最优状态游动，人工鱼将会以一定的 概率执行这个行为。 在人工鱼群算法中定义了人工鱼的四种基本行为：觅食行为、追尾行为、聚 群行为和随机行为。寻优过程中，人工鱼首先执行觅食行为、追尾行为和聚群行 为，如果这三种行为都不能找到比当前状态更优的状态，那么人工鱼就会执行随 机行为。随机行为使得人工鱼获得更多的随机移动的机会，从而能避免人工鱼在 优化的前期陷入局部极值，对人工鱼的全局寻优非常有利。但是到了优化的后期， 人工鱼聚集在全局最优值附近时，随机行为的执行则会降低算法的优化精度和优 山东大学硕士学位论文 化效率。 针对以上问题，我们对人工鱼群算法进行了改进。首先设置一个反馈概率厶， 然后对人工鱼的移动策略做出以下规定：人工鱼以概率厶执行随机行为，以概率 l 一厶执行我们上面新定义的反馈行为。优化过程开始时我们将厶设置为一个较 大的数值，随着优化过程的进行厶按式( 2 2 4 ) 所示线性减小。其中口为反馈概率 的衰减因子。 厶= 口厶 ( 2 2 4 ) 这样，在优化的前期，随机行为将会得到更多执行的机会，而在优化的后期，反 馈行为将会得到更多的执行机会。从而使得改进人工鱼群算法不仅能保证算法的 全局收敛性而且能保证收敛的精度和效率。 2 2 3 基于混沌搜索和反馈策略的改进人工鱼群算法 混沌由于具有遍历性特性，可以作为一种有效的防止优化算法陷入局部最优 的机制。将混沌搜索引入人工鱼群算法，应用人工鱼群算法执行全局搜索，而混沌 搜索则在人工鱼群算法搜索结果的基础上实行局部搜索。加入混沌搜索的人工鱼群 算法能够避免人工鱼长时间呆在一个局部最优值附近，从而提高人工鱼群算法的全 局收敛性和寻优效率。同时反馈策略也被引入人工鱼群算法提高算法的收敛精度和 收敛效率。基于混沌搜索和反馈策略的改进人工鱼群算法的具体步骤如下所示： s t e p l ：算法初始化，包括人工鱼的位置，种群规模彳巳乃脚，步v 黜t e p ，视野 v i s u a l ， 反馈概率厶，反馈概率的衰减因子口等； s t e p 2 ：计算所有人工鱼的适应度值，将最优的人工鱼记入公告板； s t e p 3 ：人工鱼模拟执行觅食行为、追尾行为和聚群行为然后对执行后的结果 进行评价，若执行后的状态优于当前状态，人工鱼向此优良状态的方向前进一步 然后转至u s t e p 5 ，否则执行s t e p 4 ； s t e p 4 ：产生一个随机数r a n d 0 ，r a n d o 厶，人工鱼执行随机行为，否则 执行反馈行为； s t e p 5 ：最优人工鱼执行混沌搜索； s t e p 6 ：更新公告板； 1 5 山东大学硕士学位论文 s t e p 7 ：更新反馈概率匕= 口厶； s t e p 8 ：如果满足算法终止条件，停止算法运行输出最后结果，否则返回s t e p 3 。 2 2 4 实验仿真与结果分析 为了测试改进的人工鱼群算法的性能，我们选择了两个标准测试函数进行仿 真实验。这两个测试函数如下所示，它们都是具有很多局部极值的复杂测试函数。 f i ：m i n i m i z e f ( x , y ) = 石l 曷i j 石i 二- 石2 于0 _ i 而+ 工2 + j ，2 ，- 2 。五y 2 。 f 2 ：m a x i m i z e f ( x ，y ) = 一x s i n ( i x l ) 一y s i i l ( i y l ) ，- 5 0 0 _ ) ，此 外它还能够处在既不是l o 也不是i l 的状态上，而是处于状态1 0 和1 1 的一个线性 组合即所谓中间状态之上，也就是处于状态1 0 和i l 的线性叠加态上。 i 缈 = 口1 0 + 1 1 ( 2 3 1 ) 这里口和是任意的复数，且满足归一化要求川2 + p 1 2 = 1 ，其中h 2 和蚓2 给出了 这个处于叠加态的量子比特表现为“0 和“1 一的概率。式( 2 3 1 ) 的量子叠加态也 可以表示为矩阵的形式。 1 9 = i 口， ( 2 3 2 )