（电磁场与微波技术专业论文）多群体演化算法的研究与应用.pdf

1 1 南京邮电大学硕士研究生学位论文 摘要 ,fffff,u：l川jji|fffifjjliflldi删jj h y 1 7 5 5 0 6 1 。 自二十世纪六十年代以来，遗传算法( g a ) 、粒子群算法( p s o ) 和差分进化算法( d e ) 等 演化算法已成为解决各种优化问题的有力工具，但g a 、p s o 与d e 在实际应用中往往存 在如何避免全局搜索与兼顾计算速度方面的矛盾。而最近提出的团队进步算法( t p a ) 很 好的解决了这个矛盾。t p a 作为一种新型的演化算法，还需通过改进提高其性能，通过应 用于解决新问题以作验证。 本文对t p a 的学习的学习机制、样板生成方式进行了改进，并将改进后的算法以及 t p a 、p s o 、g a 应用于十个函数测试，通过测试结果分析了各种算法的全局寻优、收敛速 度以及其它性能。将改进后性能较好的算法与原t p a 应用于五个天线基准问题测试和天线 阵综合的优化中，并与相应文献进行比较，得出了解决这些天线问题时的算法性能比较的 结论。 最后，本文将原t p a 改为离散变量团队进步算法，将团队进步算法应用于解决离散变 量优化问题。首先在离散域确立了其运算机制；然后应用该算法成功的解决了旅行商问题， 最后通过与g a 算法进行比较说明了该算法在解决离散问题方面具有一定的优势。 有关算法改进成果表明t p a 的搜索机制值得进一步研究，并应用于不同的问题。 关键词：演化算法、全局寻优、团队进步算法、离散变量、天线、旅行商问题 ， 南京邮电大学硕上研究生学位论文 a b s t r a c t s i n c et h es i x t i e so fl a s tc e n t u r y , s o m ee v o l u t i o n a r ya l g o r i t h m ss u c ha sg e n e t i ca l g o r i t h m s ( g a ) ，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 dd i f f e r e n t i a l e v o l u t i o na l g o r i t h m ( d e ) a re e m p l o y e dt os o l v eav a r i e t yo fo p t i m i z a t i o np r o b l e m sa n dh a v eb e c o m ep o w e r f u lt o o l s h o w e v e r , t h e r ee x i s tt h ep r o b l e mo fc o n f l i c tb e t w e e nc o n v e r g e n c er a t ea n dt h eg l o b a ls e a r c h e si n a p p l i c a t i o n so ft h ec o n v e n t i o n a lg a ，p s oa n dd e t h et e a mp r o g r e s sa l g o r i t h m ( t p a ) p r o v i d e s ap o s s i b l es o l u t i o nf o rt h i sd i l e m m a f o rm o r ev e r i f i c a t i o n so ft h i sn e w e v o l u t i o n a r ya l g o r i t h m ，i t i sn e c e s s a r yt om a k ei m p r o v e m e n t sf o ri t sp e r f o r m a n c e sa n dt os o l v em o r ep r o b l e m sf o rt e s t s i nt h i st h e s i s ，t h el e a r n i n go p e r a t i o no ft h et p ai sm o d i f i e db yu s i n gr a n d o mn u m b e r so fb e t a d i s t r i b u t i o n sa n dt h eg e o m e t r i c a le p i t o m e s t h ep e r f o r m a n c e so ft h ei m p r o v e dt p ai sc o m p a r e d w i t ho r i g i n a lt p a ，p s o ，g au s i n g10b e n c h m a r kf u n c t i o n sf o rg l o b a lo p t i m i z a t i o ns u c c e s s e s ， c o n v e r g e n c er a t ea sw e l la so t h e rp e r f o r m a n c ep a r a m e t e r s i ti sa l s oa p p l i e dw i t ht h eo r i g i n a l t p af o rs o l v i n gf i v ea n t e n n a sb e n c h m a r k i n gp r o b l e m sa n dt h ep a t t e r ns y n t h e s i so fa n t e n n a a r r a y sf o rc o m p a r i s o n s t h ec o n c l u s i o n so f t h ep e r f o r m a n c e sa r eg i v e n t h ed i s c r e t ev e r s i o no ft h et p ai si m p l e m e n t e df o rd i s c r e t ev a r i a b l eo p t i m i z a t i o np r o b l e m s t h eo p e r a t i o n si nt p aa rec o n v e r t e di n t od i s c r e t ev a r i a b l ed o m a i n t h e n ，t h ei m p l e m e n t e d a l g o r i t h mi ss u c c e s s f u l l ya p p l i e dt os o l v et h et r a v e l i n gs a l e s m a np r o b l e m s t h er e s u l t ss h o wt h a t t h et p ai ss u p e r i o rt ot h eg af o rs o l v i n gd i s c r e t ev a r i a b l eo p t i m i z a t i o np r o b l e m s t h ea c h i e v e m e n t so ft h i ss t u d yr e v e a lt h a tt h em e c h a n i s mo ft p ai sw o r t h yo fm o r e r e s e a r c h e sa n da p p l i c a t i o n sf o rd i f f e r e n tp r o b l e m s k e y w o r d s ：e v o l u t i o n a r ya l g o r i t h m s ，g l o b a lo p t i m i z a t i o n ，t e a mp r o g r e s sa l g o r i t h m s ，d i s c r e t e v a r i a b l e s ，a n t e n n a , t r a v e l i n gs a l e m a np r o b l e m i i 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c t i i 目录。i i i 第一章绪论1 1 1 引言1 1 2 演化算法1 1 2 1 演化算法概述1 1 2 2 演化计算的主要特点及应用2 1 2 3 演化算法发展现状3 1 3 研究内容与创新4 1 3 1 本文的主要工作4 1 3 2 本文的创新点4 第二章常用演化算法6 2 1 遗传算法、粒子群算法及差分算法6 2 1 1 遗传算法6 2 1 2 粒子群算法7 2 1 3 差分进化算法8 2 2 遗传算法、粒子群算法及差分进化算法的异同9 2 2 1 三种演化算法的相同点9 2 2 2 三种演化算法的区别1o 2 3 小结l o 第三章团队进步算法及改进11 3 1 团队进步算法1 l 3 1 1 团队进步算法基本思想1 1 3 1 2 团队进步算法的运算过程1 1 3 1 2 1 新生成员1 l 3 1 2 2 学习行为1 2 3 1 2 3 探索行为1 2 3 1 3 团队进步算法的运算流程1 3 3 1 4 团队进步算法参数设置与特性1 4 3 2 团队进步算法的改进1 4 3 2 1 学习步长的改进1 4 3 2 2 样板的改进1 5 3 3 算法性能测试1 6 3 3 1 对比算法1 6 3 3 2 基准测试函数1 6 3 3 3 统计结果分析1 6 3 4 算法参数选择3 0 3 5 小结3l 第四章演化算法在阵列天线中的应用3 2 4 1 天线基准问题测试3 2 4 1 1 天线基准问题介绍3 2 4 2 天线阵方向图优化4 3 i i i 大学硕士研究生学位论文 目录 4 2 1 天线阵列的综合及解决方法4 3 4 2 2 天线阵列优化的目标函数及优化结果比较4 3 ，j 、结j 。4 5 团队进步算法在t s p 问题中的应用4 6 离散变量团队进步算法4 6 5 1 1 初始化新成员4 6 5 1 2 新成员产生4 6 5 1 3 小组样板选择4 7 5 1 4 候选成员生成4 7 5 1 4 1 学习行为4 8 5 1 4 2 探索行为4 9 5 1 5 更新规则4 9 5 1 6 算法流程5 0 旅行商问题5 0 5 2 1 旅行商问题概述5 0 5 2 2 求解旅行商问题的方法5 1 5 2 2 1 精确求解法5l 5 2 2 2 近似求解法。5l 离散变量团队进步算法应用于求解t s p 的试验结果及分析5 2 结论5 5 结束语5 6 总结5 6 展望5 6 攻读硕士学位期间撰写的论文5 7 致谢5 8 参考文献5 9 i v 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 引言 第一章绪论 随着社会的发展，科学技术已进入一个多学科相互交叉、渗透、影响的时代，生命科 学与工程科学的相互交叉、渗透和促进就是其中一个典型例子，也是近代科学技术发展的 显著特点之一。优化是人们在科学研究、工程技术、管理技术以及旅游规划等领域必然会 遇到的问题，很多n p 及n p 难问题都需要利用优化方法末进行解决【卜。】。例如结构设计要求 在满足强度要求等条件的情况下使用材料的总重量最轻、资源分配则要求使各用户利用有 限的资源产生最大的经济效益等典型的背包问题，安排运输方案要在满足物资需求和装载 的条件下使运输总费用最低的旅行商问题，都是典型的n p 问题。此外，智能天线的设计、 以及网络资源配置问题等等都需要用优化方法来解决。相信随着科学技术尤其是计算机技 术的迅速发展，以及数学理论与方法向各学科和各应用领域的渗透，在不久的将来，优化 理论和技术必将在社会的诸多领域发挥越来越大的作用。 二十世纪八十年代以来，人们逐渐意识到传统人工智能方法的局限性，而且随着计算 机运算速度的飞速提高及并行计算机的诞生、普及，演化算法对机器速度的要求已不再是 制约其发展的主要因素。特别是随着禁忌搜索算法、差分进化算法、蚁群算法、遗传算法、 粒子群算法等演化算法的兴起，以及以现代优化算法为主题的多个国际会议在世界各地的 定期召开，科学工作者对这些算法的模型、理论和应用技术等一系列问题进行了深入研究， 使演化算法成为解决优化问题的一种有效工具。 二十一世纪初，研究者又提出了一种新型的群体演化算法一团队进步算法 4 1 ，并将 其应用到函数优化、天线优化等方面【5 卅。本文在原有团队进步算法的基础上对其学习机制、 样板生成机制进行了改进，并将其应用到离散领域。 1 2 演化算法 1 2 1 演化算法概述 演化计算是一种基于生物自然选择和基因遗传学原理的计算模型，通过借用计算机等 先进工具，模拟自然界的演化过程来求解复杂问题。对于许多用传统算法难以解决或明显 无效的复杂问题，特别是优化问题，演化计算提供了一条有效途径7 期。 南京邮电大学硕士研冤生学位论文 第一章绪论 演化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 源于计算机科学与进化论的结合，始于2 0 世纪 5 0 年代末，但由于当时缺乏一种通用的编码方案，使得人们只能依赖变异而不是交配来产 生新的基因结构，故而收效甚微。到2 0 世纪6 0 年代中期，美m i c h i g a n 大学的j o h nh o l l a n d 提出了遗传算法，他的本意是在人工适应系统中设计一种基于自然演化原理的搜索机制。 1 9 7 5 年，他发表了一篇文章【l0 1 ，在其中，他描述了遗传算法的理论框架。大约在同一时间， f o e g l 和r e c h e n b e r g 及s c h w e f e l ，引入了另两种基于自然演化原理的算法，演化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和演化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 1 1 。2 0 世纪9 0 年代初， 在遗传算法的基础上又发展了一个分支：遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 【1 2 4 3 1 。 随后，蚁群算法、粒子群算法、差分进化算法等演化算法被相继提出并应用于解决各种优 化问题。虽然这几种算法在实现方面具有一些细微的差别，但它们具有一个共同特点，即 都是借助生物学的思想和原理来解决实际问题。 1 2 2 演化计算的主要特点及应用 演化算法作为解决优化问题的一种通用方法，目前比较常用的有粒子群演化算法、遗 传算法及差分进化算法，虽然模拟的生物种类及运算过程有一定的差异，但其都必须经过 演化计算过程。演化计算的基本特点主要有： ( 1 ) 多解性：演化算法计算的对象是一个群体或多群体，在每个演化计算阶段都存在 多个候选解，因此一次经常能找到多个解，这一特点适合于求解含有多个极值点的问题。 ( 2 ) 全局优化：传统优化算法是从单个初始值开始，通过逐步迭代的方法求解最优解 的，很容易陷入局部极值点。而演化算法从问题解的串集开始搜索，群体散布于整个搜索 区域，覆盖面广，利于全局择优，很容易找到全局最优解。 ( 3 ) 随机性：演化算法中的选择、交叉、变异操作都带有一定的随机性，而不是确定 的精确规则。它采用随机方法进行最优解搜索，选择体现了向最优解逼近的原则，交叉体 现了最优解的产生原则，变异体现了全局最优解的覆盖原则。 ( 4 ) 并行性：演化计算的性质决定了其本质的高度并行性，表现在两个方面。一是演化 计算的内在并行性，演化计算本身非常适合大规模并行；二是演化计算的内含并行性，由 于演化计算采用一个种群或多个种群的方式组织搜索，从而可以同时在所求解空间内的多 个区域进行搜索。 ( 5 ) 智能性：演化计算的智能性包含自组织、自适应、自学习。应用演化算法求解问 题时，在确定了编码方案、适应度函数后，算法将利用演化过程中获得的信息自行搜索。 2 南京邮电大学硕士研究生学位论文第覃绪论 演化计算提供了一种求解复杂优化问题的一般模型，它不依赖于问题的具体领域，不 要求目标函数有明确的解析表达式，对各种问题都具有较好的稳定性，因此已广泛应用于 各种领域。其主要应用领域有： ( 1 ) 函数优化和组合优化。函数优化是演化计算的经典应用领域，也是对演化计算进 行性能测评的常用算例，有确定性函数也有随机性函数，有单极值函数也有多极值函数， 等等。对于高度非线性、多目标的函数优化问题，用演化算法可以很方便地解决，演化计 算在函数优化中的应用成果甚多【1 , 1 4 - 1 5 】。组合优化问题的目标是从组合问题的可行解集中 求出最优解，往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。典型的组 合优化问题有旅行商问题、o 1 背包问题、装箱问题、图着色问题、生产调度问题等等。 这些问题描述简单且有很强的工程代表性，但随着问题规模的不断扩大，组合优化问题的 搜索空间急剧扩大，要想用枚举法求出精确解是很困难的甚至是不可能的。其主要原因是 求解这些问题的遍历运算过程需要极长的运行时问与极大的存储空间，以致根本不可能在 现有的计算机上实现。因此对于这类复杂问题，应把主要精力放在寻求近似解上，而演化 算法正是解决这种问题的工具之一。例如，遗传算法和粒子群算法已经在求解旅行问题、 背包问题、装箱问题和生产调度问题等方面得到了成功的运用【拍。8 1 ，本文也已成功的将团 队进步算法应用于解决旅行商问题。 ( 2 ) 自动控制。在自动控制领域有很多与优化相关的问题需要求解【l9 1 ，而且这些优化 问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式。演化计算在求 解这类问题方面已显示出其独特优点。 ( 3 ) 人工生命【2 0 2 1 1 。人工生命是用计算机、机械等人工媒体模拟或构造出具有自然生 物系统特有行为的人造系统。人工生命与演化算法具有密切的关系，基于演化计算的演化 模型是研究人工生命现象的重要基础，演化计算为人工生命提供了一种模型化方法，而人 工生命又将为演化计算提供更为丰富的发展源泉，这二者相辅相成，必将相互促进发展。 另外演化算法在演化机器人学、生物计算等方面也得到了广泛应用，就不一一列举了。 1 2 3 演化算法发展现状 在演化计算的研究中，可以看到主要有以下四类研究方向： ( 1 ) 演化计算的理论研究。演化计算的理论的研究成果相对较少，但近年来已同趋活 跃，有了一些收敛性的研究成果，收敛速度的研究还有待于科学家们的艰苦努力。 ( 2 ) 用演化算法作为工具解决实际工程问题，主要是进行优化，其关心的是优化性能 南京邮电大学硕七研冗生学位论文第一章绪论 是否能在传统方法上有所提高。当前大多数的研究多集中于演化算法的构造，相比于传统 的算法，这些算法能非常高效的解决这些问题 2 2 之3 1 。 ( 3 ) 演化软件，主要是自动程序设计，由计算机自己来编制程序，自动进行复杂系统 的建模【2 4 2 5 1 。 ( 4 ) 演化硬件的研究【2 6 1 。演化硬件是未来演化计算发展的重要趋势之一。所谓演化硬 件即指能像生物一样根据环境的变化改变自身结构以适应其生存环境的硬件。演化硬件是 演化算法和可编程逻辑器件的结合，演化计算为演化硬件提供了理论与方法学基础，而可 编程集成电路特别是新一代现场可编程门阵列( f p g a ) 为演化硬件提供了物质基础。演化硬 件的出现不过短短几年的时间，却在电路设计、控制和机器人、模式识别、容错系统和超 大规模集成电路的设计等领域都得到了一定的应用。 1 3 研究内容与创新 1 3 1 本文的主要工作 1 ) 总结差分演化算法、粒子群算法和遗传算法的机理与特性，并对三种算法性能进 行比较，得出三种算法的异同点。 2 ) 对团队进步算法进行介绍与改进，并将改进后的团队进步算法的性能进行试验测 试：首先把改进后的团队进步算法以及其它算法应用于十个极值函数测试中，通过分析运 算结果比较各种算法的特性；然后把团队进步算法及其改进较好的算法应用于天线基准测 试问题及天线阵综合的优化，并与相应文献进行比较，分析各算法在解决天线优化问题中 的性能。 3 ) 在离散领域重新定义团队进步算法的运算流程，并对旅行商问题进行介绍，最后 把团队进步算法及其对比算法( 基本遗传算法) 应用于解决典型的旅行商问题，通过试验 结果分析各算法在解决离散问题时的性能。 1 3 2 本文的创新点 1 ) 学习机制的改进。原团队进步算法的学习步长采用均匀随机数，对应几何意义为在 学习点到样板点为对顶点的超长方体内选择均匀分布的学习到达点，这可能导致学习的定 向性和集中度不够。为增强学习的定向性和学习达到点的集中度，本文将学习步长改进为 符合b e t a 分布的非均匀分布随机数。 4 南京邮电人学硕士研究生学位论文第一章绪论 2 ) 样板的改进。针对原团队进步算法的样板采用算术平均数生成，本文用最大、最小 方式确定群组的外接超长方体，并将外接超长方体的几何中心作为样板，称为几何样板。 通过对函数与基准天线优化的试验分析，通过分析寻优速度和寻优成功率来总结改进后团 队进步算法的特性。 3 ) 对算法参数进行离散化。通过分析团队进步算法和离散优化问题，本文对团队进步 算法的运算过程中相应参数进行了离散化，提出一种适应于解决离散问题的算法离散 。 变量团队进步算法，并给出了相应的算法运算流程，并将该算法应用于解决离散问题中的 旅行商问题。 5 的适应度值进行的，适应度越高，被选择的概率就越高，而适应度低的，被选择的概率则 低；然后被选择的个体进入交配过程，每两个个体通过交配产生两个新个体，代替原来的 老个体，其它个体则保持不变，交配父母的染色体相互交换，从而产生两个新的染色体， 第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里 的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意 位置。再下一步是通过突变产生新个体，新个体的染色体的随机突变，通常就是改变染色 体的一个字节。经过选择、交配和突变产生的新一代个体不同于初始的一代，并一代一代 向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应 度值低的个体则逐渐被淘汰掉。这样的过程不断的重复，每个个体被评价并计算出适应度 值，个体两两交配，然后突变，产生第三代；周而复始，直到终止条件满足为止【2 ”0 1 。 6 南京邮电大学硕士研究生学位论文第二章常用演化算法 遗传算法的算法流程包括选择、交叉、变异等环节，具体流程参阅文献2 8 。0 1 ， 其参数及参数设置为： 。 种群规模p ( p o p u l a t i o ns i z e ) ：即群体中所含个体的数量。当p 取值较小时，虽然能 提高遗传算法的运算速度，却会降低群体的多样性，导致遗传算法产生早熟现象，当p 取 值较大时，又会使遗传算法的寻优效率降低，因此p 一般根据所解决的具体问题进行具体 设置( 取值范围一般为2 0 2 0 0 ) 。 交叉概率p c ( p r o b a b i l i t yo f p e r f o r m i n gc r o s s o v e r ) ：p c 控制着交叉算子的使用频率。 交叉操作可以加快收敛，能够使所求解达到最有希望的最优解区域，因此p c 取值一般较 大，但p c 过高将导致算法早熟。因此建议p c 取值范围为0 4 - 0 9 较好。 变异概率p m ( p r o b a b i l i t yo f m u t a t i o n ) ：控制着变异算子的使用频率。 中止条件( t e r m i n a t i o nc r i t e r i a ) ：受进化次数、计算耗费资源、最优值条件、适应度 值以及人为干预的限制，因此一般根据具体问题的具体要求进行具体设定。 遗传算法的参数设置对算法的搜索效果及搜索效率具有一定影响，目前尚无选择它们 的合理方法，在遗传算法的实际应用中，往往需要经过多次试验后才能确定出这些参数合 理的取值范围或取值大小。 2 1 2 粒子群算法 粒子群( 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 ) 算法是19 9 5 年由e b e r h a r t 博士和k e n n e d y 惫 博士提出的一种新型演化算澍3 l 】，p s o 算法和g a 相似，它也是从随机解出发，通过迭代 寻求最优解，并通过适应度值来评价解的品质【3 2 3 3 】。但是它比遗传算法规则更为简单，它没 有遗传算法的交叉和变异操作。 p s o 算法从鸟类觅食行为模型中受到启示并用于解决优化问题 3 1 , 3 4 - 3 5 】。在p s o 算法中， 每个优化问题的解都被看作搜索空间中的一只鸟，我们称之为粒子，所有的粒子都有一个 由被优化的函数所决定的适应度值，每个粒子还有一个速度决定他们飞翔的方向和距离。 然后粒子群中的各个粒子追随当前最优粒子的解集区域进行搜索。p s o 算法首先初始化一 群随机粒子( 随机解) ；然后通过迭代找到其中的最优解，在每一次迭代中，粒子通过跟踪 两爪极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值p b e s t 。 另一个极值是整个种群目前找到的最优解，这个极值是全局极值g b e s t 。另外也可以不用 整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值 【3 1 1 。在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置： 7 学习因子c l 、c 2 ：c l 和c 2 通! l 常取2 ，一般c l 等t c 2 ，取值范围为叫。 最大速度v 眦：最大速度v 0 ，决定粒子在一个循环中最大的移动距离，通常设定 为粒子的范围宽度，例如对于问题f ( x ) = 砰+ + 求解，粒子可以直接编码为( 五，x 2 ，x 3 ) ，而 适应度函数就是f ( x ) 。( x j ，x 2 ，x 3 ) 【- 1 0 ，l o 】，那么的大小就是2 0 。 中止条件：与g a 相同，受很多条件限制，应根据实际情况进行分别对待。 惯性权重w ：w 使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力 探索新的区域，其取值范围为肌l 。 2 1 3 差分进化算法 差分进化( d i f f e r e n t i a le v o l u t i o n ，d e ) 算法是s t o r er 和p r i c ek 于19 9 5 年提出的一种随 8 南京邮电人学硕士研究生学位论文 第二章常用演化算法 机的并行直接搜索算、法【3 7 1 。差分进化算法是通过模拟自然界中生物种群的“优胜劣汰、适 者生存”的进化发展规律而形成的一种随机启发式搜索算法。由于其简单易用、稳健性好 以及强大的全局搜索能力，使得差分进化算法已在多个领域取得成功，譬如人工神经元网 络、化工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业、食品安 全、环境保护和运筹学等。 差分进化算法的基本运算思想是：从某一随机产生的初始群体开始，通过把种群中任 意两个个体的向量差加权后按一定的规则与第三个个体求和来产生新个体，然后将新个体 与当代种群中某个预先决定的个体相比较，如果新个体的适应度值优于与之相比较的个体 的适应度值，则在下一代中就用新个体取代旧个体，否则保留原个体，差分进化算法通过 不断地迭代运算对群体进行更新，从而达到保留优良个体、引导搜索过程向最优解逐渐逼 近的目的。其中差分进化算法的自参考种群繁殖方案通过把种群中两个成员之问的加权差 向量加到第三个成员上来产生新参数向量的操作称为“变异”，变异向量的参数与另外预 先确定的目标向量参数按一定规则混合来产生试验向量的操作过程称为“交叉”。基本差 分进化算法的种群初始化、变异、交叉的规则及算法流程参阅文献【3 7 。3 8 】。 在优化设计中，与传统的优化方法相比，差分进化算法具有以下特点：差分进化算法 从一个群体即多个点而不是从一个点开始搜索，这是它能以较大的概率找到整体最优解的 主要原因；差分进化算法的进化准则是基于适应性信息的，不用借助其它辅助信息，因而 大大扩展了其应用范围。 2 2 遗传算法、粒子群算法及差分进化算法的异同 2 2 1 三种演化算法的相同点 遗传算法、粒子群算法以及差分算法的基本思想都是通过模拟自然界中某种生物的进 化规则而提出来的，因此它们都具有着或多或少的联系。三种算法的相同点主要归纳如下： 都属于仿生算法。三种算法的基本思想都是根据自然界中生物“优胜劣汰的进 化规则提出的，因此都属于仿生算法。 都属于全局优化方法。三种算法对各种目标函数进行优化的目的都是为了尽量避 免陷入局部最优，找到全局最优。 令都属于种群随机初始化群体搜索算法。算法的初始化都是通过随机生成一组种群 来实现的。 令都使用适应度值来评价系统，而且都根据适应度值来进行一定的随机搜索。 9 区域，却不能很快进化至最优解。g a 、p s o 算法以及d e 算法较弱的局部搜索能力是造成 g a 和p s o 进化速度慢的一个重要原因。 2 3 小结 本章简单介绍了常用演化算法中的g a 、p s o 算法以及d e 算法的基本思想、算法运算 过程和算法参数设置。通过本章可知g a 、p s o 算法、d e 算法在解决优化问题时有很多相 似之处，且都具有各自的特点。 1 0 南京邮电大学硕十研究生学位论文第三章团队进步算法及改进 第三章团队进步算法及改进 本章主要介绍团队进步算法( t e a mp r o g r e s sa l g o r i t h m ，t p a ) 的基本思想和搜索机制 以及参数设置，并对团队进步算法的学习机制、样板生成方式进行了改进。最后将改进后 的算法、t p a 、g a 、p s o 算法应用于十个具有不同特性的函数进行测试，通过试验结果分 析各种算法在函数优化方面的性能，并得出结论。 3 1 团队进步算法 3 1 1 团队进步算法基本思想 在团队管理与经济体组织中，榜样的学习有助于引导团队的进步方向，社会的分工、 合作可提高生产效率。基于这一基本思想，2 0 0 8 年薄亚明教授提出了一种新颖的双群体搜 索算法一团队进步算法【4 】，该算法模拟了一个团队中两个小组的学习和探索过程，并设 计了其更新规则。该算法首先初始化一团队成员，并按照函数的适应度值的大小把该团队 成员分为精英组和普通组两组成员，精英组保证算法的收敛速度，普通组保证算法的全局 收敛效果，两组成员在新成员产生规则及学习、探索和成员更新规则作用下表现出了较快 的进步能力，能够通过较快的速度产生具有全局最优评价值的成员，故称为团队进步算法， 该算法与常用演化算法g a 和p s o 相比具有不同的寻优机制，且每次迭代最多实现一个成 员更新。 3 1 2 团队进步算法的运算过程 随机生成一组成员，假设该成员个数为n + m 个，然后由函数评价值最高的n 个成员 组成精英组 t 。，t ：，粕) ，其余的m 个成员组成普通组 。，讳：，x p m ) ，然后通过迭代 实现成员更新，最终找到问题的最优解。 3 1 2 1 新生成员 新成员记为t ，从精英组或普通组中产生4 矧，产生方法为： 算法及改进 选成员x 。 x ，= ( 1 一r ) x ，+ y e ， 生， ( 3 - 1 ) 方法 定。设学 习的目的 成公式分 ( 3 - 2 ) ( 3 - 3 ) 习成为候 ( 3 - 4 ) 出自精英组的新成员x ，沿x ，到e p 的反方向学习，所得候选成员x 。为 x 。= ( 1 + 厂) x ，一y e p ( 3 5 ) 其中y ( 0 ，1 ) 为平均分布随机数，来自精英组的候选成员存在越界的危险，因此对于越界 的分量，令其分量等于其边界值。 3 1 2 3 探索行为 假若新生成员选择探索，则新生成员的探索公式为( 3 6 ) ，其中为0 或1 的二值随机 数，珊对不同的屹( f = 1 ，2 ，z ) 分别生成，t e p 为探索次数的函数，其相应公式为( 3 7 ) ，其 中屯为当前累计探索次数，k 为算法的强制终止迭代次数，口卯为收缩指数，对精英组和 1 2 南京邮电大学硕士研究生学位论文第三章团队进步算法及改进 普通组可分别取不同的参数以和口p ，一般普通组的收缩指数口，要小一些，可取口， - - w a 。， w 为探索概率。 x 。= 【。，t ：，誓。】r f x 一+ 乞p ( b f x ，f ) ，当m i = 0 ( 3 6 ) x ，1x 一一乞，( x 一_ a f ) ，当砚：1 3 1 3 团队进步算法的运算流程 t e ，p = l - u 一r 叱” ( 3 7 ) 团队进步算法迭代一次只调用函数一次，最多更新一个成员，因此其算法复杂度为其 迭代次数。其求最小值情况算法流程如下( 若求最大值情况则只需将所有不等号反向) ： ( 1 ) 确定算法参数，包括精英组的成员数n 、普通组的成员数m 、学习概率，、探索强 度收缩指数吒、g t 。，允许的最大迭代次数k 。随机生成n + m 个团队成员，计算其评价值， 根据评价值排序将其分成含有n 个成员的精英组和含有m 个成员的普通组，确定成员的 最优评价值厂( x 删) 、两组术位评价值厂( x 。，) 和f ( x 。，) ，以及对应的成员x o p t 、x 和x 删， 用( 3 2 ) 、( 3 - 3 ) 两式计算样板e 。和e 。置迭代计数变量尼= 0 ，探索计数变量k e = 0 ，开始进 步过程； ( 2 ) 若f ( x o p t ) k ，则算法终止，否则执行下一步； ( 4 ) 产生一个值为0 或l 的二值随机数s 。如果s 为0 ，则选择从精英组中产生新生成 员，反之则选择从普通组中产生新生成员，公式采用( 3 1 ) ； ( 5 ) 产生平均随机数，( o ，1 ) 。如r l ，则执行下一步，否则转第( 7 ) 步； ( 6 ) 新成员通过学习行为更新成员个体，用( 3 4 ) 或( 3 5 ) 式计算x 。，然后计算其评价值 f ( x 。) ，转( 8 ) ； ( 7 ) 新成员通过探索行为更新成员个体。用( 3 6 ) 式计算x 。，然后计算其评价值f ( x 。) 。 执行下一步； ( 8 ) 如果f ( x 。) 厂( x 。，) ，则x 。进入精英组，丢弃x e 心，用( 3 2 ) 式更新e 。，并重新选 出厂( x 叫) 、( x ) ，更新x 叫和x ，转第( 2 ) 步，否则执行下一步； ( 9 ) 如果厂( x 一) 0 为指数参数、k 为迭代次数、t 为最大迭代次数。设其概率密度函数 1 4 南京邮电大学硕十研究生学位论文第三章团队进步算法及改进 为厶( x ) ，则其概率分布函数定义为： c o ( x ) = p a r 砷 ( 3 - 9 ) 将( 3 - 8 ) 带入( 3 9 ) 得： f o ( x ) = p o ( u 一r 石) = p o ( u ( x ) 1 1 一厂) ( 3 1 0 ) 由于“为 0 ，1 区i 、日j 的均匀分布随机数，由上式得： c o ( x ) = e o ( ux l l - t ) ) = 工加 ( 3 11 ) 对应的概率密度函数为： “功。南 卜”4 1 1 ( 3 1 2 ) 是概率密度分布随f 趋向x = 1 端的b e t a 分布，算法运算流程同基本团队进步算法。 3 2 2 样板的改进 针对原团队进步算法采用算术平均生成样板，本文提出一种采用几何平均生成样板的 方法，即利用最大、最小方式确定组的外接超立方体或长方体，并用该立方体或长方体的 几何中心作为小组样板，称为几何样板。其产生公式为： e 。= 毕 e p = 芋 ( 3 - 1 3 ) ( 3 - 1 4 ) 9 x ，一= 】【 t l 。，t 2 。，t ，b 】 劬2 鼍砀曲成2 一kj ， ( 3 一i 5 ) x p 眦2 x 【l 一，2 一，kj x ，幽2 x x p l 曲，2 曲，工】 其中e e 得自精英组，称为精英样板；e p 得自普通组，称为普通样板。以为个体成员的能力 因素数目。x e 一、x 。曲分别为精英组外接超几何体的边界点，x p 。、x p 面。普通组超几何 体的边界点。算法运算流程同基本团队进步算法算法。 函数：石：s c h w e f e l 函数；石：g r i e w a n g k e 函数；石：a c k l e y 函数；z o ：a c k l e y vs i n e 函数。其中除石为2 维函数外，其余测试函数的维数都可变，记为n 。石彳。为多极值函 数，十个测试函数的具体函数形式、变量范围以及极值点的性质参考相应文献【3 9 , 4 0 , 4 1 1 。 3 3 3 统计结果分析 所有测试函数寻优精度为1 0 一，即满足公式厂( ) 一f u - j 机制改进的t p a 和样板为几何样板的