（通信与信息系统专业论文）智能计算及其在网络优化中的应用.pdf

山东大学硕士学位论文 中文摘要 优化命题的解决存在于许多领域，在国民经济的发展中也有着巨大的应用前 景。组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 所研究的问题涉及信息技术、经济管 理、工业工程、交通运输等诸多领域。由于其目标函数的非线性、约束性、多目 标、多模态性，甚至非连续或非解析性，难以用传统的基于严格机理模型的优化 方法求解。 与传统的优化方法相比，智能计算无集中控制、多代理机制、算法结构简单、 隐含并行性、易理解和易实现的优点，有效地促进了其在应用优化技术中的拓展， 在实现生产过程的优化、提高牛产效率与效益、节省资源等方面正逐步发挥重要 的作用。进化算法和群体智能等智能计算方法，通过“拟物”与“仿生”，形成 大规模并行且具有自组织、自适应、自学习等智能特征的计算系统，为解决某些 复杂问题提供了卓有成效的方法和途径。 本文针对智能计算中的进化算法和群体智能算法的理论、算法创新及其在网 络优化方面的典型应用进行了研究。在选题上，从智能计算的两类应用广泛且关 系密切的技术进化算法和群体智能算法入手，以进化算法中经典的遗传算法作 为研究基础，将新颖的人工鱼群算法、d n a 算法与进化算法的集成作为研究切入 点：在理论上，给出了各类算法的原理、结构、实现方法等系统的阐述和研究： 在应用上，把改进的算法应用于计算机网络的路由优化，和无线传感器网络的最 优覆盖等典型的网络优化j 题：在算法的创新上，在人工鱼群算法中融合了禁忌 搜索算法的禁忌表技术，并设计了一个参数。在d n a g a 算法中针对w s n 的最优 覆盖问题，解决了编译码的难点，在设计基因传递算子和变异算子时，融合了d n a 算法的某些技术特点；在实验仿真的效果上，两种改进的算法在全局寻优和邻域 搜索能力上得到了增强，取得了较好的收敛速度和寻优效率；在研究的方法上， 注重横向分析，给出了三种算法在具体实现过程中的参数特点，同时就进化算法 和群体智能算法特点进行了总结，并强调了算法的改进和发展方向。 本文首先从最优化问题和智能计算的概念、分类及其主要特点入手，对组合 优化问题、进化计算和群体智能计算、网络优化问题进行了介绍。然后，对进化 算法中最具代表性的经典算法一遗传算法的理论进行阐述和研究，并应用于计算 机网络的路由优化，给出实验仿真结果和分析。第三，系统阐述了人工鱼群算法 山东文学硕士学位论文 的原理、收敛性能、实现方法，提出改进的人工鱼群算法，应用于计算机网络的 路由优化，给出实验仿真结果、与遗传算法的对比分析和改进思路。第四，对d n a 的结构，d n a g a 算法的流程及实现进行了研究，针对传感器网络节点的分布优 化，设计d n a g a 算法，给出实验仿真结果、与遗传算法的对比分柝和改进思路。 论文的最后给出了三种算法在优化过程中的参数特点，总结了进化计算和群体智 能计算的特点，并系统概括了智能计算今后的发展方向。 关键词：遗传算法：人工鱼群算法：d n a g a 算法：路由优化：覆盖优化。 i i 山东大学硕士学位论文 a b s t r a c t o p t i m i z a t i o nc o n s i s t si nm a n yf i e l d sa n di ta l s oh a sh u g ea p p l i c a t i o nf u t u r ed u r i n g t h ec o u n t r ye c o n o m yd e v e l o p m e n t t h ei s s u e sc o m b i n a t i o n a lo p t i m i z a t i o ns t u d i e sr e l a t e t oag o o dm a n yf i e l d ss u c ha si n f o r m a t i o nt e c h n o l o g y , e c o n o m ym a n a g e m e n t , i n d u s t r y p r o j e c t a n dt r a f f i ct r a n s p o r t a t i o n ，s u c ha sn e t w o r ko p t i m i z a t i o n b e c a u s eo ft h e n o n - l i n e a r i t y , r e s t r i c tn a t u r e ，m u l t i - t a r g e t ，m u l t i m o d e ，e v e nn o nc o n t i n u u mo rn o np a r s e o f t h et a r g e tf u n c t i o n ，i ti sd i f f i c u l tt os o l v et h ec o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m sb y t r a d i t i o n a ln u m e r i c a lv a l u em e t h o dw h i c hh a v eb a s e do nt h es t r i c tm e c h a n i s mm o d e l c o m p a r e d w i t ht r a d i t i o n a l o p t i m i z a t i o nm e t h o d ，t h ea d v a n t a g e s s u c ha s n o n - c e n t r a l - c o n t r o l ，m u l t i - a g e n tm e c h a n i s m s ，s i m p l es t r u c t u r e ，i n n e rp a r a l l e la n de a s y t ob eu n d e r s t o o da n dr e a l i z e d e f f e c t i v e l yp r o m o t et h ed e v e l o p m e n to fi n t e l l i g e n c e c o m p u t i n gi no p t i m i z a t i o nt e c h n o l o g y i n t e l l i g e n c ec o m p u t i n gp l a ym o r ea n dm o r e i m p o r t a n tr o l e si no p t i m i z a t i o no fp r o d u c t i o np r o c e s s ，i m p r o v i n gt h ep r o d u c t i o n e f f i c i e n c ya n db e n e f i ta n ds a v i n gr e s o u r c e t h ei n t e l l i g e n c ec o m p u t i n gm e t h o d ss u c ha s e v o l u t i o nc o m p u t i n ga n ds w a r mi n t e l l i g e n c e ，b ym e a n so fi m i t a t i n gl i f e f o r ma n d b i o n i cs i m u l a t i o n ，a d a p tt ot h ec o m p u t i n gs y s t e mw h i c hh a v et h ei n t e l l i g e n c ec h a r a c t e r o fl a r g es c a l ep a r a l l e l ，a u t o o r g a n i z a t i o n ，a u t o a d a p t a t i o na n ds e l f - s t u d y , a n dc a no f f e r f r u i t f u lm e t h o da n da p p r o a c ht os o l v es o m ec o m p l e xp r o b l e m s t h em a i ni d e ao ft h i sp a p e ri st or e s e a r c ht h et h e o r yo fe v o l u t i o nc o m p u t i n ga n d s w a r mi n t e l l i g e n c e c o m p u t i n g ，t h ea l g o r i t h mi n n o v a t i o n a n di t s r e p r e s e n t a t i v e a p p l i c a t i o nt on e t w o r ko p t i m i z a t i o n i ns u b j e c ts e l e c t i o n ，i ts t a r t s w i t he v o l u t i o n c o m p u t i n ga n ds w a r mi n t e l l i g e n c ec o m p u t i n g i tm a k e st h eg e n e t i ca l g o r i t h m ( g a ) a s i t ss t u d yf o u n d a t i o n i tm a k e st h en o v e la r t i f i c i a lf i s hs w a r ma l g o r i t h mf a f s a ) a n d t h ec o m b i n a t i o no fd n aa l g o r i t h ma n de v o l u t i o na l g o r i t h ma si t sc u t i np o i n t i n t h e o r y , i tp r e s e n t ss y s t e m i ce x p a t i a t i o na n ds t u d ya b o u tt h ep r i n c i p l e ，s t r u c t u r ea n d i m p l e m e n tm e t h o d so f t h ea l g o r i t h m st o l da b o v e i na p p l i c a t i o n ，i ta p p l i e dt h ei m p r o v e d a l g o r i t h mt ot h et y p i c a ln e t w o r ko p t i m i z a t i o np r o b l e m ss u c ha sr o u t i n go p t i m i z a t i o no f t h ec o m p u t e rn e t w o r ka n dt h ec o v e r a g eo p t i m i z a t i o no fw s nw h i c hi st h eh o t s p o ta n d 1 1 1 山东大学硕士学位论文 d i f f i c u l t yo ft h ew s nr e s e a r c h i na l g o r i t h mi n n o v a t i o n ，i ts y n c r e t i z e st h et e c h n i q u eo f t a b o ot a b l eo ft a b o os e a r c ha l g o r i t h mi n t oa f s aa sw e l la sa d d sap a r a m e t e r i n d n a g a a l g o r i t h m ，i ts o l v e st h ed i f f i c u l t yo f c o d i n ga n da l s os y n c r e t i z e st h et e c h n i q u e o fd n a a l g o r i t h mi n t ot h ed e s i g no fg e n e - p a s s - o p e r a t o ra n dt h ea b e r r a n c eo p e r a t o r i n t h ee f f e c to fs i m u l a t i o n ，t h et w oi m p r o v e da l g o r i t h m sb u i l du pt h ea b i l i t yo fg l o b a l o p t i m i z a t i o n a n dn e i g h b o r h o o ds e a r c ha n dg e tb e t t e rc o n v e r g e n c e r a p i d i t y a n d o p t i m i z a t i o ne f f i c i e n c y i nr e s e a r c hm e t h o d ，i tp a y sa t t e n t i o nt o t h el a n d s c a p e o r i e n t a t i o na n a l y s i sa n ds u m m a r i z e st h ep a r a m e t e rc h a r a c t e r i s t i co f t h et h r e ea l g o r i t h m s a b o v ea n do ft h ee v o l u t i o nc o m p u t i n ga n ds w a r mi n t e l l i g e n c ec o m p u t i n g ，f u r t h e rm o r e ， i te m p h a s i z e st h ei m p r o v e m e n ta n dd e v e l o p m e n td i r e c t i o no f t h e a l g o r i t h m s 1 1 1 e p a p e rs t a r t s w i t ht h e c o n c e p t s y s t e ma n dm a i nc h a r a e t e r i s t i c o ft h e o p t i m i z a t i o np r o b l e m sa n di n t e l l i g e n c ec o m p u t i n g ，a n di n t r o d u c e st h ec o m b i n a t i o n a l o p t i m i z a t i o n ，t h ee v o l u t i o nc o m p u t i n g ，t h es w a r mi n t e l l i g e n c ec o m p u t i n ga n dt h e n e t w o r ko p t i m i z a t i o n t h e n ，t h eg ai ss t u d i e da n da p p l i e dt ot h er o u t i n g o p t i m i z a t i o n o f c o m p u t e rn e t w o r ko p t i m i z a t i o n t h es i m u l a t i o nr e s u l t sa n da n a l y s i sa r eg i v e n t h e t h i r d ，t h ep r i n c i p l e ，c o n v e r g e n c ec a p a b i l i t ya n di m p l e m e n tm e t h o do fa f s aa r e e x p a t i a t e d ，t h ei m p r o v e da l g o r i t h mi sp r e s e n t e d ，t h es i m u l a t i o nr e s u l t s ，a n a l y s i s c o m p a r e dw i t hg aa n di m p r o v e m e n tw a ya r eg i v e n t h ef o 而，t h es t r u c t u r e ，p r o c e s s a n di m p l e m e n to fd n a - g ai ss t u d i e d t h en e wa l g o r i t h mw a sd e s i g n e da c c o r d i n gt o t h ec o v e r a g eo p t i m i z a t i o no fw s n ，t h es i m u l a t i o nr e s u l t s ，a n a l y s i sc o m p a r e dw i t hg a a n di m p r o v e m e n tw a yi sg i v e n f i n a l l y , t h ep a p e rg i v e st h ep a r a m e t e rc h a r a c t e r i s t i co f t h et h r e ea l g o r i t h m sa b o v ea n dt h ec h a r a c t e r i s t i co ft h ee v o l u t i o nc o m p u t i n ga n d s w a r m i n t e l l i g e n c ec o m p u t i n g ，f u r t h e rm o r e ，t h ed e v e l o p m e n to f t h ea l g o r i t h m s k e yw o r d s ： g e n e t i ca l g o r i t h m ( g a ) - 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 ) ； d n a - g e n e t i ca l g o r i t h m ( d n a g a ) ；r o u t i n go p t i m i z a t i o n c o v e r a g eo p t i m i z a t i o n i v 山东大学硕士学位论文 a c o a f s a a i a l d n a g a e c e p e s g a g p s n p n p h a r d p s o t s p w s n 符号说明 a n tc o l o n yo p t i m i z a t i o n 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 r t i f i c i a li n t e l l i g e n c e a r t i f i c i a ll i f e d n a g e n e t i ca l g o r i t h m e v o l u t i o nc o m p u t e r e v o l u t i o n a r yp r o g r a m m i n g e o l u t i o n a r ys t r a t e g y g e n e t i ca l g o r i t h m g l o b a lp o s i t i o n i n gs y s t e m n o tp o l y n o m i a l n o tp o l y n o m i a l - h a r d p a r t i c l es w a r mo p t i m i z a t i o n t r a d i n gs a l e s m a np r o b l e m w i r e l e s ss e n s o rn e t w o r k 蚁群优化 人工鱼群算法 人工智能 人工生命 d n a 遗传算法 进化算法 进化规划 进化策略 遗传算法 全球定位系统 非多项式的 非多项式完全的 粒子群优化 旅行商问题 无线传感器网络 v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：粒日期：班 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复f p 件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 蝴：迩i 扎i i ：坦鹜期：牝 山东大学硕士学位论文 第一章绪论 1 1 课题研究的目的和意义 智能计算已成为一种新兴的优化技术，其无集中控制、多代理机制、算法结 构简单、隐含并行性、易理解和易实现的优点，有效地促进了其在应用优化技术 中的拓展，对实现生产过程的优化、提高生产效率与效益、节省资源具有重要的 作用。 鉴于实际工程问题的复杂性、约束性、非线性、多局部极小和建模用难等特 点，寻找各种适合于工程实践需求的新型智能优化方法，一直是智能计算的一个 重要研究方向。随着优化命题的复杂程度和规模的不断提高，使用单一的优化算 法很难得到满意的解。本文研究的目的之一是将成熟的算法进行良好的融合，优 势互补，寻找适合于工程实践需求的新型智能优化方法，通过具体的优化实践， 来探索进化算法和群体智能算法在优化问题上应用的特点。 遗传算法是进化算法的代表，d n a g a 算法和人工鱼群算法是近几年来发展 起来的智能计算方法，本文通过对这几种算法的研究，并将其应用于通信网络的 路由优化和传感器节点的分布优化问题，对在网络的管理过程中进行动态路由选 择，进行了新的探索，提供了新的方法；对以较小代价完成传感器网络节点的分 布优化，从而有效提高网络整体的感知能力，提供新的思路。 1 2 背景知识 1 2 1 最优化问题 人们在工程技术、科学研究和经济管理的诸多领域中有大量的问题需要在庞 大和复杂空间中寻找最优解或近似最优解。如结构设计要在满足强度要求等条件 下使所用材料的总重量最轻；资源分配要使各用户利用有限资源产生的总效益最 大；安排运输方案要在满足物资需求和装载条件下使运输总费用最低等等。人们 总希望采取种种措施，以便在有限的资源条件下或规定的约束条件下得到最满意 的效果，这是最优化问题。 最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对 象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。 山东大学硕士学位论文 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学方法的研究去寻找离散 事件的最优编排、分组、次序或筛选等，是运筹学中的一个经典且重要的分支， 所研究的问题涉及信息技术、经济管理、工业工程、交通运输等诸多领域。现实 生活中的大量优化问题是从有限状态中选取最好的，即组合最优化问题。由组合 最优化问题的定义可知，每一个组合最优化问题都可以通过枚举的方法求得最优 解，但枚举是以时间为代价的，有许多问题的枚举时间不能接受，即使求局部最 优解也是困难的。解决组合优化问题时，如果逐点搜索，其计算量将按照设计变 量的幂次增长，这种急剧增长，通常称之为“组合爆炸”。由于组合优化问题甘标 函数的非线性、约束性、多目标、多模态性，甚至非连续或非解析性，难以用传 统的数值方法求解。 所谓的n p h a r d 组合最优化问题，是一类难以求解的组合最优化问题，受人类 认识能力的限制，迄今为止，这些问题还没有一个能求得最优解的多项式时间算 法，目前人们只能假设这一类难解的组合最优化问题不存在求解最优解的多项式 时间算法。由于这些问题又有非常强的实际应用背景，人们尝试用一些并不一定 可以求解到最优解的算法，如启发式算法，来求解n p h a r d 的组合最优化问题。 人们生活的现代社会是一个由计算机信息网络、电话通信网络、运输服务网 络、能源和物流分派网络等各种网络组成的复杂网络系统。网络优化就是研究如 何有效地计划、管理和控制这个网络系统，使之发挥最大的社会效益和经济效益。 网络优化问题是与图和网络相关的最优化问题，多数网络优化问题是以网络上的 流和网络拓扑为研究对象。网络优化问题是一类特殊的组合优化问题。本文所研 究的计算机网络路由优化问题、传感器网络节点的覆盖优化问题，就是属于网络 优化问题中的n i p h a r d 组合最优化问题。 1 2 2 优化计算 研究最优( 或近优) 解及其求解方法的学科称为优化计算“。优化计算是一 种以数学为基础，用于求解各种工程问题优化解的应用技术。现代优化算法的主 要应用对象是优化问题中的难解问题，也就是优化理论中的n p h a r d 问题。 优化计算和方法可粗略地划分成三个重要阶段：即早期古典极值理论、近代 数值优化和智能计算。 早期古典极值理论的丰要特征是基于数学理论演绎和推理的微分法和变分 山东大学硕士学位论文 法，如著名的l a g r a n g i a n 数乘法、c a u c h y 最速下降法，到本世纪四十年代，苏联科 学家康托洛维奇在解决运输和生产计划问题时提出了线性规划问题求解的解乘数 法等。 扶四十年代以后，随着电子计算机的闯世和迅速发展，摹于计算机的近代数 值优化方法得到了长足发展，逐步占据了优化计算的主导地位。牛顿法、单纯形 法、共轭梯度、变尺度法和模式搜索法等一系列有代表性的数值计算方法相继涌 现并不断完善，使得优化理论形成为- - f j 独立和完整的学科分支。 传统的优化算法都是基于严格的数学模型的，当模型复杂的时候，如变量的 维数多、约束方程多、非线性强等，或模型不能用显式的方程来表达时，这些方 法往往不能进行有效求解。或者求解的时间过长，如上面提到的“组合爆炸”问 题；或者求解的效果差，如陷入局部极值、初始直接影响寻优的结果等。随着n p - h a r d 理论的建立和发展，传统的优化算法也难以有效处理包括n p h a r d 问题在内的难解 问题。 进入8 0 年代以来，生命科学与工程科学相互交叉、相瓦渗透和相瓦促进，优 化技术和理论中神经网络、进化计算和群体智能计算等新兴算法相继出现和不断 完善，形成了适应处理复杂问题并能够在非确定性、非精确环境中进行概率推理 和学习的现代优化方法一智能计算。 1 ，3 智能计算及其研究现状 1 3 1 智能计算的研究现状 智能计算1 4 1 ( i n t e l l i g e n tc o m p u t i n g ) ，也有人称之为软计算( s o f tc o m p u t i n g ) ， 是由模糊集理论的创始人，伯克利大学教授lz a d e h 提出来的。智能计算就是借助 自然界( 特别是生物界) 规律的启迪，并根据其原理，模仿设计求解问题的算法。 由于具有自学习，自组织、自适应等特性，在诸多领域得到了成功应用。智能计 算的主要技术包括进化计算、模糊集理论、神经网络、d n a 计算和群体智能计算 等。 智能计算正处于迅速发展阶段，引起了诸多领域专家学者的关注。成为跨学 科的研究热点。近年来，智能计算方法的应用研究呈互相融合的趋势，研究和实 践表明，它们之间的相瓦补充可增强彼此的能力，从而获得更有力的表示和解决 实际问题的能力。近十多年来，智能计算应用领域越来越广，从工业控制、模式 山东大学硕士学位论文 识别、知识自动获取、经济管理、生物医学到网络智能自动化等许多领域都取得 了激动人心的研究成果和应用。 智能计算技术将不断地从牛物智能中得到启示，探讨思想更先进、功能更强 大、能解决更复杂( 巨) 系统的整体智能行为的智能计算技术，使新型智能计算 系统逐步实现牛物智能的目标。探索新的算法、推进算法之间的融合及加强智能 计算在工程领域的实际应用将成为智能计算重要的发展方向。 本文着重就进化计算、群体智能计算和d n a 计算进行研究 】。 1 3 2 进化计算与群体智能计算 ( 1 ) 进化计算 进化计算( e v o l u t i o nc o m p u t i n g ，e c ) 是一种模拟牛物进化过程、机制求解问 题的自组织、自适应智能计算技术。它以生物界的“优胜劣态、适者牛存”作为 算法的进化规则，结合达尔文的自然选择与孟德尔的遗传变异理论，将生物进化 中的四个基本形式：繁殖、变异、竞争和选择引入到算法过程中，指导算法的迸 行，并在计算机上模拟牛命进化机制。进化计算是建立在模拟生物进化过程的摹 础上而产牛的一种随机搜索优化技术。 进化计算在2 0 世纪6 0 一7 0 年代并未受到普遍的重视，到y 8 0 年代，人们越来越 认识到传统优化方法的局限性，并且由于计算机速度的提高和并行计算机的普及， 也由于进化算法的不断发展及其在一些应用领域内取得的成功，进化计算表现出 了良好的应用前景。一些学者认为，进化计算将与混沌理论和分形几何一起成为 人们研究非线性现象和复杂系统的新的三大方法，并将与神经网络一起成为人们 研究认知过程的重要工具。 进化计算体现j 优胜劣汰和目然选择的优化思想，为许多难以用传统数学方 法和其他人工智能技术解决的科学和工程问题提供了全新的思路。当前进化计算 的研究内容十分广泛，如进化算法的设计与分析、进化计算的理论基础及其在各 个领域中的应用等。 进化计算具有三大分支，即遗传算法( g e n e t i c a l g o r i t h m 。g a ) ，进化规划和进 化策略。遗传算法和d n a g a 算法及其在优化问题上的应用是本文的研究重点之 一o ( 2 ) 群体智能计算 4 山东大学硕士学位论文 自然界存在着那些让人类叹为观止的生物群体智能现象，蜂巢之精美、蚁群 之有序、雁阵之和谐，这些群居生物所体现的社会性和分布式智能实现模式给了 人类很大的肩发。 群体智能( s w a r mi n t e l l i g e n c e ) 是受社会性昆虫的启发，通过对其行为的模拟 形成一系列用于解决传统复杂问题的新方法。群体中存在众多智能个体，它们通 过相瓦之间的简单合作表现出来的智能行为即称为群体智能。群体指的是一组相 互之间可以进行直接通讯或者间接通讯( 通过改变局部环境) 的主体，它们能够 合作进行分布式的问题求解。群体中简单个体是指具有简单能力( 如搬运、通信、 运动等) 的个体，这种能力可以用某一简单的功能函数来表示。简单合作足指个 体只能与其邻近的个体进行某种简单的协同动作，或通过改变环境间接的与其它 个体之间进行简单通信。 f 1 2 0 世纪9 0 年代以来，群体智能计算的研究引起了许多学者的极大兴趣，并 出现了蚁群优化( a n tc o l o n yo p t i m i z a t i o n ，a c 0 ) 算法、粒子群优化( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 算法等一些著名的群体智能优化算法。这些算法模式都是基 于种群寻优的启发式随机搜索算法，随着群体智能计算理论和应用研究的不断发 展，研究者们尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多 种研究表明，群集智能计算在离散求解空间和连续求解空间中均表现出良好的搜 索效果，并在组合优化问题中表现突出。 国内外群体智能的研究丰要体现在：群体行为的模拟、群体智能计算和分布 式问题解决装置研究等方面。其中群体智能计算是最为活跃的一个研究分支。 人工鱼群算法是近年来新兴起的一种群体智能计算方法。人工鱼群算法及其在 优化问题上的应用是本文的研究蕈点之- ：。 1 4 论文内容安排 本文的中心内容是研究进化算法和群体智能算法中的某些有代表性的算法一 遗传算法、人工鱼群算法和d n a g a 算法的原理、性能及其实现，对算法进行改 进，应用于解决网络优化等一系列组合优化问题的求解，并通过仿真结果分析算 法的性能。 第一章：绪论部分。介绍了课题研究的目的和意义，最优化问题、优化计算、 智能计算相关背景知识。 山东大学硕士学位论文 第二章：介绍了进化算法中的经典算法一遗传算法的基本概念、基本遗传算法、 遗传算法的构成要素、参数选择、及遗传算法的特点，并将其应用于计算机网络 的链路容量与流量分配，给出实验仿真结果，并进行分析。 第三章：介绍了新型的群体智能算法一人工鱼群算法，人工鱼的概念、鱼群行 为及描述、行为选择及最优值的获取、算法的寻优原理。对人工鱼群算法进行改 进，并将其应用于计算机网络的路由优化问题，给出实验仿真结果，并分析算法 的性能。 第四章：介绍了d n a 计算的相关知识，d n a g a 算法的结构，算法的实现。 通过与g a 算法的比对，分析d n a - g a 算法的特点。将改进的算法应用于传感器 网络节点的分布与优化问题，给出实验仿真结果，并分析算法的性能。 第五章：对遗传算法、d n a - g a 算法和人工鱼群算法，对进化算法和群体智 能算法的特点、应用进行对比分析和总结概括。 第六章：对本论文的内容作了总结并对将来的工作进行展望。 1 5 本章小结 本章围绕着智能计算及其相关的背景知识展开，主要阐明了课题研究的目的 和意义，最优化问题及其分类，优化计算的发展，智能计算及其研究现状，并分 别就进化计算和群体智能计算的发展进行了简要介绍。最后给出了论文的丰要结 构安排。 6 山东大学硕士学位论文 第二章遗传算法及其在路由优化中的应用 遗传算法7 1 是模拟牛物在自然环境中遗传和进化过程而形成的一种自适应全 局优化概率搜索算法。它最早是由美国密执安大学h o l l a n d 教授提出，起源于6 0 年 代对自然和人工自适应系统的研究。7 0 年代d ej o n g 基于遗传算法的思想在计算机 上进行了大量的纯数值函数优化的计算实验。在一系列研究工作基础上，8 0 年代 r h g o l d b e r g 进行归纳总结形成遗传算法的基本框架。 2 1 基本遗传算法 遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则 与群体内部染色体的随机信息交换机制相结合的搜索算法。它在搜索之前，先将 变量以某种形式进行编码( 编码后的变量称为染色体) ，不同的染色体构成一个 群体。对于群体中的染色体，将以某种方法评估出其适应值。新一代群体的产擘。 是按下面两个步骤完成的：首先，根据染色体的适应值选择被保留的染色体以及 相应的复制次数；其次，对被选择的染色体进行重组、变异，产牛新的染色体 遗传算法的基本流程如下： ( 1 ) 随机产生一组初始个体构成初始种群，并评价每一个体的适应度值 ( f i t n e s sv a l u e ) 。 ( 2 ) 判断算法收敛准则是否满足，是则输出搜索结果，否则执行以下步骤。 ( 3 ) 根据适应度值的大小以一定方式执行复制操作。 ( 4 ) 按交叉概率以执行交叉操作。 ( 5 ) 按变异概率以执行变异操作。 ( 6 ) 返回步骤( 2 ) 。 标准遗传算法的流程图描述，如图2 1 1 所示。 7 山东大学硕士学位论文 图2 1 ，1 标准遗传算法流程图 2 2 遗传算法的实现技术 从前面所述的遗传算法我们知道，染色体编码方法、个体适应度评价、遗传 算予、运行参数为实现遗传算法的几个关键方面，是必不可少的“。 2 2 1 编码方法 编码是指在遗传算法中，把个问题的可行解从其解空间转换到遗传算法所 能处理的搜索空间的转换方法。编码是应用遗传算法时要解决的首要问题，也是 设计遗传算法时的一个关键步骤。编码方法除了决定个体的染色体排列式之外， 它还决定个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方 3 山东大学硕士学位论文 法也影响到交叉算子、变异算子等遗传算子的运算方法，编码方法在很大程度上 决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。 对于一个具体的应用问题，如何设计一种完美的编码方案一直是遗传算法的 应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严 密又完整的指导理论及评价准则能够帮助我们设计编码方案。一般地，我们参考 d ej o n g 曾提出的两条操作性较强的实用编码原则“1 ： ( 1 ) 有意义积木块编码原则：应使用能易于产生与所求问题相关的且具有低 价、短定义长度模式的编码方案。 ( 2 ) 最小字符集编码原则：应使用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案。 需要说明的是，这两条编码原则仅仅是给出了设计编码方案时的一个指导性 大纲，它并不适合所有的问题。所以对于实际问题，仍必须对编码方法、交叉运 算方法、变异运算方法、解码方法等统一考虑，以寻求一种对问题的描述最为方 便、遗传运算率最高的编码方案。 由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方 法。总的来说，这些编码方法可以分为三大类：二进制编码方法、浮点数编码方 法、符号编码方法。 2 2 2 个体适应度函数 遗传算法中，采用适应度来度量群体中各个个体在优化计算中有可能达到或 接近于或有助于找到最优解的优良程度。适应度较高的个体以较高的概率遗传到 下一代；而适应度较低的个体遗传到下一代的概率就相对小一些。 遗传算法的一个特点是它仅便用所求阿题的目标函数值就廿j 得剑f 一步的有 关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个 体的适应度的一般过程是： ( 1 ) 对个体编码进行解码处理后，可得到个体的表现型。 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适 应度。 最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求日 9 山东大学硕士学位论文 标函数的全局最小值。对于这两类优化问题，可采用解空间中某一点的目标函数 值( x ) 到搜索空间对应个体的适应度函数值f ( x ) 的转换方法： 对于求最大值的问题，做如下转换： f c x ，= ，毒+ c 参；：妻；：；： 。2 2 ， 式中，c 。相当一个适当地相对较小的数。 对于求最小值的问题，做如下转换： 刖，= r 凡箩船耋乏 式中，c 。相当一个适当地相对较大的数。 遗传算法中，群体的进化过程就是以群体中个体的适应度为依据，通过一个 反复迭代过程，不断地寻求出适应度较大的个体。最终就可得到问题的最优解或 近似最优解。遗传算法搜索能力主要是由选择和杂交赋予的，变异算子则保证了 算法能搜索到问题解空间的每一点，从而使算法达到全局最优。 2 2 3 遗传算子 遗传算法中使用下述二种遗传算子： ( 1 ) 选择运算 选择运算是对群体中的个体进行优胜劣汰操作。遗传算法中的选择操作就是 用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体。选择操 作建立在对个体的适j 匝度避行评价的基础之上，适应厦较高的个体被遗传剑f 一 代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。其 主要目的是为了避免基因缺失、提高全局收敛性和计算效率。 选择运算使用的算予主要有：比例选择、最优保存策略、确定式采样选择、 无回放随机选择、排序选择等算子。用的较多的比例选择的思想是；各个个体被 选中的概率与其适应度大小成正比：最优保存策略则是考感到由于选择、交叉、 变异的遗传操作的随机性，它们有可能破坏当前群体中适应度最好的个体( 而这 恰恰是我们所需要保留的) ，为了避免这种破坏发生，采取当前群体中适应度最 1 0 山东大学硕士学位论文 好的个体不参与交叉和变异运算，替换本代群体中经过交叉和变异等遗传操作后 适应度最低的个体，从而直接保留到下一代的策略。 ( 2 ) 交叉运算 交叉运算是指对两个相瓦配对的染色体按某种方式相互交换其部分基因，从 而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它 在遗传算法中起着关键作用，是产生新个体的主要方法。 遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用 的配对策略是随机配对，即将群体中的m 个个体以随机的方式组成m 2 对配对个体 组，交叉操作是在这些配对个体组中的两个个体之间进行的。 最常用的交叉算子是单点交叉算子。单点交叉指是在个体编码串中只随机设 置一个交叉点，然后在该点相互交换两个配对个体的部分染色体，其特点是若邻 接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单 点交叉操作破坏这种个体性状和降低个体适应度的可能性较小。另外，人们根据 具体的问题，也使用双点交叉与多点交叉、均匀交叉、算术交叉等算子。 ( 3 ) 变异运算 变异运算是指将个体染色体编码串中的某些基因座上的基因值，用该摹因座 的其他等位基因来替换，从而形成一个新的个体。变异算予的主要作用是改善遗 传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。 最简单的变异算子是基本位变异算子，此外还有均匀变异、边界变异、非均 匀变异、高斯变异等算子。对于基本位变异操作，它对个体编码串中以变异概率p 。 随机指定的某一位或某几位基因座上的