（系统工程专业论文）若干现代最优化技术的应用比较研究.pdf

声明尸州 本人郑重声明：此处所提交的硕士学位论文若干现代最优化技术的应用比较 研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作 和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：墨与篆一e t 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 作者签名：虚粒导师签名：基坐 日飙喇 日期：椰箩 华北电力大学硕士学位论文 摘要 最优化在实际应用中的作用越来越重要，而现代最优化算法作为优化手段和方 法在优化过程中是相当的重要的。相对传统的优化算法，现代优化算法的优点显而 易见。本文对遗传算法、鱼群算法、群体复合形算法、模拟退火算法和粒子群算法 五种算法进行详细论述，并用这五种算法对四个典型的函数和工程实例模型进行了 优化，优化结果用图形和表格来表示，总结和分析结果，通过结果来评价算法优劣。 然后取其中较优的算法进行改进和结合，同样对锅炉燃烧模型进行优化，并将结果 和单个算法优化的结果进行比较。论文在最后进行总结并提出展望。 关键词：最优化，算法，总结，比较 a b s t r a c t o p t i m i z a t i o nh a sb e e nm o r ea n dm o r ei m p o r t a n ti nt h ep r a c t i c a la p p l i c a t i o n a sa t o o lo fo p t i m i z a t i o n ，m o d e mo p t i m i z a t i o na l g o r i t h m sa r eb e i n gav e r yi m p o r t a n tp a r tf o r o p t i m i z a t i o n c o m p a r e dw i t ht r a d i t i o n a lo p t i m i z a t i o na l g o r i t h m s ，t h ea d v a n t a g e s o f m o d e mo p t i m i z a t i o na l g o r i t h m sa r eo b v i o u s t h i s p a p e rd i s c u s s e s f i v em o d e m o p t i m i z a t i o na l g o r i t h m si nd e t a i l t h ef i v ea l g o r i t h m sa r eg e n e t i ca l g o r i t h m ，a r t i f i c i a l f i s hs c h o o la l g o r i t h m ，m u l t i - c o m p l e xa l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h ma n d p a r t i c l es w a r n la l g o r i t h m s e c o n d l y , u s i n gt h ef i v ea l g o r i t h m s ，t h ea r t i c l eo p t i m i z e sf o r e t y p i c a lf u n c t i o n sa n ds o m em o d e l so fp r a c t i c a lp r o j e c t s t h er e s u l t so fo p t i m i z a t i o na r e l a i no u tb ys o m eg r a p h sa n dt a b u l a t i o n s a f t e rs u m m a r i z i n ga n da n a l y z i n gt h er e s u l t s ， t h et h e s i se x p a t i a t e sa n de s t i m a t e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ef i v e a l g o r i t h m s t h e n ，t h ea l g o r i t h m sw h i c h h a v eb e e na p p r o v e dm u c hb e t t e ra r ei m p r o v e do n a n dc o m b i n e dt oo p t i m i z et h em o d e l i n gc o m b u s t i o np r o c e s so fb o i l e r f o l l o w i n gt h a t ， t h eo p t i m i z i n gr e s u l t sa r ec o m p a r e dw i t ht h e s eo fs i n g l ea l g o r i t h m s a tl a s t ， s u m m a r i z a t i o na n de x p e c t a t i o no ft h ep a p e ra r es e tf o r t h l iy if a n g ( s y s t e me n g i n e e r i n g ) d i r e c t e db yp r o f h u a n gx i a n k e yw o r d s ：o p t i m i z a t i o n ，a l g o r i t h m ，s u m m a r i z e ，c o m p a r e 华北电力大学硕士学位论文 1 1 现代最优化技术 1 1 1 最优化的意义 第一章引言 最优化技术是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什 么样的方案最优以及怎样找出最优方案。这类问题普通存在。例如，工程设计中怎 样选择设计参数，使得设计方案既满足设计要求又能降低成本；资源分配中，怎样 分配有限资源使得分配方案既能满足各方面的基本要求又能获得好的经济效益；生 产计划安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题，怎样确 定各种成分的比例，才能提高质量，降低成本：城建规划中，怎样安排工厂、机关： 学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行 各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产， 发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存 自己，有利于战争的全局。在人类活动的各个领域中，诸如此类，不胜枚举。最优 化这一数学分支正是为这些问题的解决，提供理论基础和求解方法，它是一门应用 广泛、实用性强的学科。 随着现代科技的发展，各学科之间相互渗透，新的交叉学科不断形成，新的思 维方式、新的计算方法，特别是计算机科学与技术的迅速发展为优化技术的研究与 发展注入了活力，也为其提供了更广阔的研究空间。人们认识与改造世界的能力日 益扩大，对科学技术也提出了新的、更高的要求，其中对高效的优化技术和计算方 法的要求也日益迫切。同时，对于实际系统，例如工程领域，特别是人工智能与控 制领域，不断涌现出超大规模的非线性系统，在这些系统的研究中，经典优化方法 不能有效求解的优化问题必须采用智能技术。鉴于实际问题的复杂性、约束性、非 线性、不确定性、建模困难等特点以及传统优化方法局限性大的现状，寻求适合于 大规模并行且具有智能特征的最优化方法已成为很多学科研究的目标和内容，因 此，优化理论与算法的研究是一个具有理论意义和应用价值的重要课题。优化的根 本目的就是在原有的基础上改善，并力求在考虑范围内找到最佳的结果。 1 1 2 最优化问题 一般的最优化问题主要是指函数优化问题和组合优化问题。 以最小化函数为例，函数优化问题通常可描述为：令s 为灭“上的有界子集( 即变 量的定义域) ，厂：s 一尺为刀维实值函数，所谓函数厂在s 域上全局最小，即 4 华北电力大学硕士学位论文 v x s ：厂( ) f ( x ) 。对于有约束的问题可以利用设计专门算子使问题解始终保持 可行，或采用惩罚函数的方式将其转化为无约束问题，因此，函数优化研究中主要 以无约束问题为主。 仍以最小化问题为例，组合优化问题通常可以描述为：令q = “。岛) 为所有状 态构成的解空间，c ( 量) 为状态墨对应的目标函数值，目的是寻找最优解s ，使得 v s ，q ，c ( s + ) = r a i n c ( s 1 ) 。组合优化问题是函数优化问题中的一类特殊优化问题，求 解难度大，一般优化算法难以有效解决。 线性规划在最优化理论中起着独特的作用，在某种意义上，它也是连续的优化 问题。但是正像我们所指出的，本质上它也可视为组合问题，事实上它已是研究许 多严格的组合问题的基础。因此，我们将给出最优化问题的一般定义，使其包含线 性规划( 以及几乎所有最优化问题) 。 定义1 1 一个最优化问题的一个实例( 或例子) 是一对元素( ，c ) ，其中，只是 一个集合或可行点的定义域；c 是费用函数或映射 c ：f 专r ( 1 - 1 ) 问题是求一个厂f ，使得对一切y f 有 c ( 厂) c ( y ) ( 1 2 ) 这样一个点厂称为给定实例的整体( 或全局) 最优解，或者在不引起混淆的情况 下，简称为最优解。 定义1 2 一个最优化问题，就是它的一些实例的集合，。 我们非常谨慎地把一个问题和这个问题的实例做了区分。非形式地说，在一个 实例里，有输入数据，以及用于求解的足够信息。一个问题是实例的总体，通常这 些实例是用类似的方式产生的。 1 1 3 最优化理论的发展历史 最优化是个古老的课题。长期以来，人们对最优化问题进行探讨和研究。早在 1 7 世纪，英国的伟大科学家n o w t o n 发明微积分的时代，已经提出了极值问题。1 8 4 7 年法国数学家c a u c h y 研究了函数值沿什么方向下降最快的问题，提出最速下降法。 1 9 3 9 年苏联的一位数学家提出了解决下料问题和运输问题这两种线性规划问题的 求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但是，任 何科学的进步，都受到历史条件的限制，直至本世纪三十年代，最优化这个古老现 题并未形成独立的有系统的学科。 四十年代以来，由于生产和科学研究突飞猛进地发展，特别是电子计算机日益 广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。 因此最优化理论和算法迅速发展起来，形成一个新的学科。至今己出现线性规划、 华北电力大学硕士学位论文 整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。最 优化理论和算法在实际应用中正在发挥越来越大的作用。 在过去几十年中，优化的重要性不断提高，不论在科学实验还是在工程设计中， 都需要最优化计算，最优化决策。为了解决各种优化计算问题，人们提出了各种各 样的优化计算方法，如单纯形法、梯度法、动态规划法、分枝剪界法。这些优化算 法各有各的长处，各有各的适用范围，也有各自的限制。对于一些高度非线性的约 束优化问题或n p - h a r d 问题，上述方法往往难于奏效，特别当问题规模较大时， 在一个合理的计算时间内，上述算法无法获得一个用户满意的次优解。 1 2 优化算法 1 2 1 现代优化算法的应运而生 本文重点是介绍现代优化算法，现代优化算法是现代优化技术的一个重要分支， 也是优化的重要工具。标题中的若干现代最优化技术是指遗传算法，简称g a ；模 拟退火算法，简称s a ；蚁群算法，简称a a ；粒子群算法，简称p s o ；人工鱼群算 法，简称a f s a ；群体复合形算法五种算法。 在上面的文章也已经讲述过，在面对复杂的非线性的约束优化问题时，传统优 化算法无法获得一个用户满意的次优解。 随着社会的发展，在生产与管理实践中出现的复杂优化问题，经常遇到一些复 杂的系统优化问题，其输入参数受到随机因素的影响，导致输出不确定，系统的目 标函数也不能够用解析形式表达式表示出来。今年来，这种随机优化问题越来越受 到人们的重视，并提出了许多能够有效解决这类问题的启发式仿真优化方法。而传 统的方法在求解这些复杂的问题时，更是显得无能为力，其实，系统最优化的关键 是要有一个好的算法。而在本文中选择了现代优化算法中的遗传算法、模拟退火算 法、群体复合形算法、人工鱼群算法和粒子群算法这五种算法在优化这些复杂系统 时，在一般情况下，还是能得到较令人满意的次优解，它们的出现为解决这些复杂 系统的问题提供了新的途径。 1 2 2 算法分类 按优化机制与行为来分，目前工程中常用的优化算法主要可分为经典算法、构 造算法、迭代算法、演化算法和混合算法等。 经典算法。包括线形规划、动态规划、整数规划、和分枝定界等运筹学中的 传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在现实工程中往 往不适用。 6 华北电力大学硕士学位论文 构造算法。用构造的方法快速建立问题的解，通常算法的优化质量差，难以 满足工程需要，如调度问题中典型构造方法有j o h n s o n 法、p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、n e l l 法等。 迭代算法，或称邻域搜索算法。从问题的任一解出发，对其邻域的不断搜索 和当前解的替换进行迭代来实现优化。根据搜索行为，它又可分为在当前解的邻域 中贪婪搜索，只接受优于当前解的邻域搜索方法和利用一些指导整个解空间中优良 解的全局搜索方法，如s a ，g a 等。 演化算法。将优化过程转化为系统动态的演化过程，基于系统动态的演化来 实现优化，如神经网络和混沌搜索等。 混合算法。指上述各算法从结构或操作上相混合而产生的各类算法。 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局 部优化算法和全局优化算法。 本文所研究的五种优化算法，其实都是一种搜索过程或规则。它们是基于某种 思想和机制，通过一定的途径或规则得到满足用户要求的问题解的方法。属于迭代 算法。 1 2 3 现代新算法和传统算法的比较 像遗传算法、模拟退火算法、人工鱼群算法、粒子群算法和复合群体算法等现 代新型搜索算法相比单纯形法、梯度法、动态规划法、分枝剪界法等典型的老算法 有很多的优点，主要包括以下优点： 一般老算法都要求有目标函数，甚至要求满足目标函数连续光滑及可微等要 求，而新型的搜索算法对目标函数没有这样苛刻的要求，其对问题的依赖性较小， 甚至对有无目标函数都没有要求。 老算法由于算法自身原因，对搜索空间及系统复杂度都有很高的要求，对中 等规模和适度复杂性的问题都无能为力。而新型算法在这方面的要求放宽很多，能 解决很多很复杂的大系统，比如锅炉系统。 新型算法计算简单，容易编程和理解，而老算法的计算和编程过程都比较复 杂。 许多老算法往往只能得到局部最优而非全局最优，而新型算法基本上都是从 许多点开始并行操作，而非局限于一点，因而可以有效地防止搜索过程收敛于局部 最优解。 新型优化算法的优点将在以下章节中用具体优化过程来体现。 7 华北电力大学硕士学位论文 1 3 本论文的主要工作 本论文主要完成以下工作： 阐述最优化的意义和最优化问题，并简述算法的发展历史。按优化机制与行 为对优化算法进行分类，并将传统算法和现代优化算法进行比较。 对人工鱼群算法、群体复合形算法、模拟退火算法和粒子群算法四种算法的 具体操作过程进行详述，并对这四种算法可能的改进方向提出想法和进行简述。 研究遗传算法的基本原理和操作过程。列出算法的选择、交叉和变异的不同 方法：通过编码问题来印证算法采用不同选择、交叉和变异方法的组合，其优化结 果的不同；用遗传算法对两个典型约束函数举例说明遗传算法在优化问题上的可行 性和特点。 将这五个算法对四个典型的复杂函数进行优化。选取的函数都是有多个局部 最优解，在很大的程度上是考验优化算法的爬坡能力和优化速度的；将寻优结果用 图像和表格来显示，通过图像和表格对其结果进行分析和比较，并对比较的结果做 出总结。 用现代优化算法来寻优r b f 神经网络网络权值。提出优化算法在这方面应用 的步骤和思路。 用遗传算法、粒子群算法和人工鱼群算法对锅炉燃烧模型进行优化，以求得 到一组针对锅炉燃烧过程中的数据输入，优化目标是锅炉燃烧过程的热效率更高， 飞灰含炭量更低，优化结果用图像和表格来显示，并对结果进行分析和比较。 将遗传算法分别和粒子群算法与人工鱼群算法结合起来来优化锅炉燃烧系 统模型，并得到比较理想的优化结果。将两种方式的优化结果进行比较和总结，并 将这两个结果和上面的单个算法优化模型所得到的结果进行比较和分析。 以上的优化过程都用v c 来编制程序，通过程序的运行过程来分析算法优化对 象时的过程，从这个过程中也可以进一步理解和分析算法的寻优能力。 最后对论文做总结并提出不足和展望。 1 4 本章小结 最优化在本质上是一门交叉学科，它对多个学科产生了重大影响，并已成为不 同领域中很多工作不可或缺的工具。传统最优化方法已经十分完善且有多部优秀教 材出版，随着对最优化技术的深入研究和发展，一些已被证明在解决全局最优化问 题上行之有效的新方法又涌现了出来，例如神经网络、模拟退火、遗传算法、人工 鱼群算法和粒子群算法等。 本章首先介绍了最优化的意义和最优化问题。可以看出最优化的意义在于满足 8 华北电力大学硕士学位论文 整个社会发展的需要，我们的实际生活中无时无刻不在进行着最优化这一工作；文 章分别阐述了“一个最优化问题的实例 和“一个最优化问题”的定义，并对两者 进行了比较，最优化问题一般可以分为函数最优化问题和组合最优化问题，文章对 这两个问题进行了举例论述。 本章的第二部分内容主要讲述优化算法，对优化算法进行了分类，并对现代优 化算法和传统优化算法作了比较，由于实际问题的复杂化，传统算法的寻优结果和 过程难以满足人们的要求，现代优化算法的出现为解决这些复杂系统的优化问题提 供了新的途径。 9 华北电力大学硕士学位论文 第二章若干现代最优化算法综述 在上一章已经讲述，本论文标题中的若干现在优化技术具体是指遗传算法、人 工鱼群算法、模拟退火算法、群体复合形进化算法和粒子群算法五种算法，并用这 五种算法来优化典型函数和实际工程模型。在这一章要对后四种算法做一个概述， 由于遗传算法的相关内容较多，其选择、交叉和变异都有较多种方法，所以放在下 章来详细论述遗传算法。下面将分别介绍人工鱼群算法、模拟退火算法、群体复 合形进化算法、粒子群算法的具体操作过程，并对各算法提出可能的改进方向。 2 1 人工鱼群算法 2 1 1 人工鱼群算法的操作过程 人工鱼群算法是一种基于动物行为的寻求全局最优的新思路，是行为主义人工 智能的一个典型应用。算法利用了鱼的觅食、聚群和追尾行为，从构造单条鱼的简 单的底层行为做起，通过鱼群中各个体的局部寻优行为，最终在群体中使全局最优 值突现出来。该算法具有良好的克服局部极值、取得全局极值的能力，并且算法的 实现无需目标函数的梯度值等特性，故其对搜索空间具有一定的自适应能力。 ( 1 ) 算法原理 在一片水域中，鱼生存的数目最多的地方一般就是本水域中富含营养物质最多 的地方，依据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从 而实现全局寻优，这就是人工鱼群算法的基本思想。 人工鱼是真实鱼个体的虚拟实体，实体中封装了其自身的数据信息和一系列行 为，如图( 2 - 1 ) 所示。人工鱼所在的环境主要是问题的解空间和其它人工鱼的状态， 它在下一时刻的行为取决于目前自身的状态和目前环境的状态( 包括问题当前解决 的优劣和其它同伴的状态) ，并且它还通过自身活动来影响环境，进而影响其它同 伴的活动。 ， 谊 图( 2 1 )人工鱼虚拟实体 l o 华北电力大学硕士学位论文 以下是鱼类的几种典型行为： 鱼的觅食行为：一般情况下鱼在水中随机、自由地游动，当发现食物时，则会 向着食物逐渐增多的方向快速游去。 鱼的聚群行为：鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集 成群。鱼聚群时所遵守的规则有三条： 分隔规则：尽量避免与临近伙伴过于拥挤； 对准规则：尽量与临近伙伴的平均方向一致； 内聚规则：尽量朝临近伙伴的中心移动。 鱼的追尾行为：在鱼群的游动过程中，当其中一条或几条发现食物时，其临近 的伙伴会尾随其快速到达食物点。 人工鱼群算法就是利用这三种典型行为从构造单条鱼底层行为做起，通过鱼群 中各个体的局部寻优达到全局最优值在群体中突现出来的目的。该算法以水域中食 物浓度为目标函数，其中人工鱼个体的状态为欲寻优的变量。整个过程包括觅食、 聚群以及追尾三种行为。其中觅食行为是人工鱼根据当前自身的适应值( 食物浓度) 随机游动的行为，是一种个体极值寻优过程，属于自学习的过程；而聚群和追尾行 为则是人工鱼与周围环境交互过程。这两种过程是在保证不与伙伴过于拥挤，且与 临近伙伴的平均移动方向一致的情况下向群体极值( 中心) 移动。由此可见，人工 鱼群算法也是一类基于群集智能的优化方法。人工鱼整个寻优过程中同样充分地利 用自身信息和环境信息来调整自身的搜索方向，从而最终达到搜索食物浓度最高的 地方即全局极值。 ( 2 ) 算法结构及相关定义 人工鱼个体的状态可表示为向量x = ( 五，恐，吒) ，其中葺o = l ，撑) 为欲寻优的 控制变量；人工鱼当前所在位置的食物浓度表示为f c = f ( x ) ，其中f c 为目标函数 值；人工鱼个体之间的距离表示为4 。= 1 1 x , 一0 ，即向量( 鼍一) 的二范数；v i s u a l 表示人工鱼的感知距离；s t e p 表示人工鱼移动的步长的最大值；万表示拥挤度因子。 ( 3 ) 行为描述 觅食行为( a fp r e y ) 假定人工鱼当前状态为墨，在其可见域内( 即喀，v i s u a l ) 随机选择一个状态 x j ，当该状态的食物浓度大于当前状态时，则向该方向前进一步；反之，则重新随 机选择状态x ，判断是否满足前进条件；反复几次后，如果环境仍不满足前进条件， 则随机移动一步。用数学表达式表示为： 1 1 华北电力大学硕士学位论文 卜砘蝴彻锄c 脚，考高吗 。， 1 1 础= + r a n d o m ( s t e p ) 一 式中：k = l ，2 ，力；，靠和耐分别表示状态向量x ，置及人工鱼下一步状态 向量邑耐的第七个元素，r a n d o m ( s t e p ) 表示 o ，s t e p 间的随机数，f c , ，此，是状态 鼻，一对应的食物浓度。以下各式中的符号含义与此相同。 聚群行为( a f s w a r m ) 设人工鱼当前状态为五，其可见域内的伙伴数目为，z ，形成集合k j i ，且 弛= 一i l | 一一五忙“a l ( 2 - 2 ) 若：g r i 垂( 为空集) ，表明可见域内存在其它伙伴，即捍，1 ，则按式( 2 3 ) 探索伙伴中心位置彳。 = 睁协 3 ， 式中：k 表示中心位置状态向量以的第七个元素；颤表示第_ ，u = 1 ，2 ，刀厂) 个 伙伴t 的第七个元素。计算该中心位置的食物浓度值心，如果满足下式 f c j n f 6 f c i。(2-4) o 表明伙伴中心位置安全度较高，并且不太拥挤，则执行式( 2 5 ) ；否则人工鱼 执行觅食行为。 矗础= + 胁面似脚褊 ( 2 - 5 ) 若融= ，表明可见域内不存在其他伙伴，则执行觅食行为。 追尾行为( a ff o l l o w ) 设人工鱼当前状态为置，探索可见域内的所有伙伴中彤最大的伙伴x ，如 果满足下式 只8fc,(2-6) 表明伙伴x 懈的食物浓度高且其周围不太拥挤，则执行式( 2 - 7 ) ；否则执行觅 食行为。 1 2 华北电力大学硕士学位论文 础= + 黼历( & 印蹦i ( 2 - 7 ) 懈一以0 式中：j 一。表示状态向量墨眦的第k 个元素。 若人工鱼当前可见域内没有其他伙伴，也执行觅食行为。 公告板( a fb u l i e t i n ) 算法中设立一个公告板，同样定义为条人工鱼，用以记录最优人工鱼个体状 态及该人工鱼位置的食物浓度值。每条人工鱼在行动一次后，就将自身当前状态的 食物浓度与公告板进行比较，如果优于公告板，则用自身状态取代公告板状态。 ( 4 ) 行为选择 算法对人工鱼当前所处的环境进行评价，即模拟执行聚群、追尾行为，然后选择 行动后食物浓度值较大的动作来执行，缺省行为方式为觅食行为。 ( 5 ) 各个参数对收敛的影响分析 视野( v i s u a l ) 和步长( s t e p ) 当视野范围较小时，觅食行为和随机移动的行为表现的较为突出；当视野范围 较大时，追尾行为表现的较为突出。总体来看，视野越大越有利于全局收敛。 在使用固定步长条件下，步长越大越有利于前期收敛，但后期容易出现震荡现 象，不利于快速收敛。小步长虽然有利于局部收敛，但寻找全局最优较慢。 拥挤度因子( 万) 在极大值问题中，拥挤度因子0 s 万1 ，它越大，允许的拥挤程度越小，越有利 于全局收敛，但精度相对较差。 在极小值问题中，拥挤度因子万 l ，它越小，允许的拥挤程度越小，越有利于 全局收敛，但精度相对较差。 人工鱼个体的数目( ) a f s a 算法是一种群集智能的运用，人工鱼的数目越多，跳出局部极值的能力越 强，收敛速度也越快，但代价是每次迭代的计算量也要增加。 2 1 2 人工鱼群算法的改进方向 从人工鱼群算法的基本理论和具体操作过程可以总结出以下人工鱼群算法的 改进方向。 ( 1 ) 种群数的选择。种群数的大小选择对算法的寻优过程和结果都是非常重要 的。一般来说，种群数的选择过小会容易使得算法寻优到一个局部最优点；而若种 群数选择过大会使得寻优的过程所需要的时间过长。 ( 2 ) 人工鱼群算法的觅食、聚群和追尾三个行为在运算过程的安排。人工鱼群 算法的聚群和追尾行为促进了算法在寻优过程中的收敛性，而觅食行为的跨步行也 华北电力大学硕士学位论文 增进了样本的多样性。因此，在寻优的过程中，寻优初期，可能样本还是比较多样 化，所以在寻优初期，可以调整参数来增加聚群和追尾的操作比例，到寻优的后期， 样本比较趋向于统一化，可以增加觅食的操作比例，以增强样本的多样性，从而使 得寻优结果不至于陷入局部最优解。其实这是人工鱼群算法的三个运算行为的在寻 优过程中的自适应过程。 ( 3 ) 影响寻优过程收敛性参数的选择。视野( v i s u a l ) 、步长( s t e p ) 和拥挤度因子 ( 引这三个参数对人工鱼群算法的寻优过程和寻优速度起着举足轻重的作用。 视野( v i s u a l ) 是影响聚群行为的运行概率，若设置得大，则进入视野的人工 鱼个数会更多，则进行聚群行为的概率就会增加；若视野( v i s u a l ) 设置较小，则进 入视野的鱼个数会较少，则进行聚群行为的概率会降低。 步长( s t e p ) 是人工鱼群算法中最重要的参数，因为在觅食、聚群和追尾三个 行为中都需要步长( s t e p ) 来控制样本移动的跨度，一般在寻优前期，设定的步长会 比较大，这样会加快收敛速度；在寻优后期，设定的步长会比较小，这样可以避免 震荡过大，有利于收敛到全局或局部最优点。 拥挤度因子( 万) 是控制聚群和追尾行为是否运行的参数，在必要的时候可以 为聚群和追尾分别取拥挤度因子( 万) ；同样，为了促进人工鱼群算法在寻优过程的 收敛性，可以为聚群和追尾的拥挤度因子( 万) 以自适应的方式来取，根据寻优的目 的是取最大或最小，以确定拥挤度因子( 万) 逐渐增大或减少。 觅食行为的试探步数( ) 的确定。觅食行为若在试探步数范围内找到更好的 值，则朝这个值的方向前进，若在试探步数范围内找不到更好的值，则随机前进。 因此，觅食行为的试探步数的确定也是影响寻优过程的一个因素。 2 2 群体复合形算法 2 2 1 群体复合形算法的操作过程 本文中提出的群体复合形进化算法的基本思路是，从可行域中随机选取一初始 点集，把这些点分给若干个复合形，每个复合形包含若干个点，每个复合形个体分 别朝自己最优方向在可行域内搜索进化到收敛，即复合形的半径充分小，然后从收 敛的每个复合形中取出一个最优点，再从可行域中随机选取一点集替换其余的点。 将这两部分点掺混并重新分配，得到新的一代复合形群体。重复这一进化过程， 直至收敛到全局最优点。 群体复合形进化算法具有以下特点： 能求解一般的不等式约束非线性优化问题，包括区间约束非线性优化问题。 复合形个体进化采用了经典的求解凸不等式约束非线性规划的复合形法。因 1 4 华北电力大学硕士学位论文 此具有能充分利用目标函数值的信息、搜索效率较高等经典的复合形法所具有的优 点，比一般的基因算法具有较强的方向性和目标性，进化过程不会停滞，加快了收 敛速度。 复合形群体进化是从复合形个体进化收敛的每个复合形中仅取出一个最优 点，再从可行域中随机选取若干个点与之掺混杂交形成新一代复合形群体。这一途 径得到的新一代复合形群体既保留了复合形个体进化收敛求得的局部最优点的优 良性、淘汰了局部最优解的重复信息，又增加了较多的新的函数值信息。因此复合 形群体进化能很快收敛到全局最优解。 群体复合形进化算法的流程如下： 图( 2 - 2 ) 群体复合形进化算法的流程图 复合形个体进化的具体流程图如下： 华北电力大学硕士学位论文 图( 2 - 3 ) 复合形个体进化的流程图 算法的详细解释如下： 初始化。假定是拧维问题，选取参与进化的复合形的个数p ( p 1 ) 和每个复合 形所包含的顶点数目刀+ l k 2 n + l ，计算样本点数目s = p m 。 产生样本点。在可行域内随机产生s 个样本点葺，而。 ，分别计算每一点薯的 函数值z = 厂( 葺) ，i = 1 ，2 j 。 分为复合形群体。将样本点划分为p 个复合形4 ，4 ，, o0 9 a j , ，每个复合形含有m 个点。其中 a = ( 苟，k j ；_ k = 一小- 1 ) 。，片= 乃m 棚朋，y = l ，2 ，m ，k - 1 ，2 ，p ( 2 8 ) 复合形个体进化。按复合形个体进化算法分别进化每个复合形，直至每个复 合形收敛。 收敛性判断。如果复合形群体满足收敛条件则停止，否则进行步。 复合形群体进化。从收敛的每个复合形中分别取出一个最优点，记为 五，屯，x ，再从可行域中随机选取s - p + 点，将这两部分点掺混杂交形成新的点 集，回到第步。 1 6 华北电力大学硕士学位论文 个体复合形进化具体步骤： 计算复合形各顶点的目标函数值，确定 最差点： 五 厂( 五) = m a x f ( x j ) = 1 ，2 ，k 次差点：k厂( t ) = m a x f ( x i ) j = l ，2 ，kj , h 最好点： 五厂( 五) = m i n f ( x j )j = l ，2 ，k 计算除最差点以外各项点的型心鼍 五2 吉，磊。置( 2 - 9 ) 检查鼍是否在可行域内 j 、如果鼍d ，沿( t 一五) 的方向求反射点置， x r = xc + o c t xc x o0 2 - 1 0 检查z 的, - - f 行性。如果z 不在可行域内，将口值减半，重新反射，直至反射点x ， 满足约束条件为止。 玎、如果tgd ，则d 可能是一个非凸集。此时，以五和鼍为界，随机产生七 个新的顶点，构成新的复合形。重复步骤，的计算，直至点z 进入可行域为止。 计算z 上的目标函数值 如果厂( 墨) 厂( ) ，将反射系数口减半，重新计算反射点墨。 若厂( t ) 厂( 五) ，则t 为可行点，转向。否则继续将口减半，如此反复。如 果经过若干次减半，口值已经很小( 如口51 0 - 5 ) ，而厂( z ) 仍然大于厂( 五) ，可将最 差点五换为次差点t ，转入步骤，重新进行迭代计算，直到满足计算精度为止。 即当复合形已收缩到很小，满足 m 。轴a x l 。l x ，一鼍l l - 占 停止迭代。取复合形最小函数值顶点作为最优解。 2 2 2 群体复合形算法的改进方向 ( 2 - 1 1 ) 从群体复合形算法的基本理论和具体操作过程可以总结出以下群体复合形算 法的改进方向。 种群数的选择。和人工鱼群算法需要对种群数做出选择的原因是一样的。因 1 7 华北电力大学硕士学位论文 为种群数的大小会影响优化的速度和结果。 对复合群体的划分。复合群体实际上是把种群数划分为几个复合形个体，再 对每个复合形个体进行寻优，一次寻优完毕则再把这几个复合形个体的最优点记录 下来进行判断，若还不能满足终止条件，则重新分组，继续进行复合形个体寻优。 所以复合群体的分组数对整个寻优过程的影响也是很大的，因此，如何对复合群体 也是群体复合形算法的一个改进方向。 反射系数的初设值大小。若反射系数初设值比较大的时候，就表明在反射点 不满足约束的情况下，其能有更多的步数来寻找反射点。因此对反射系数的初设值 的适当选择对整个寻优过程也比较重要。 用次差点代替对差点的条件选择。在群体复合形算法中，如果反射系数折半 到一定的数据时，求得的反射点依旧还是不能满足约束条件，则就用次差点来代替 最差点。所以需要设置一个系数条件来结束求反射点的行为，那么这个系数的大小 设置会影响球反射点的步数，也就会影响整体寻优速度。 2 3 模拟退火算法 2 3 1 模拟退火算法的操作过程 ( 1 ) 模拟退火算法的基本概念 1 9 8 2 年，k i r k p a t c k 等将热力学中的退火思想引入组合优化领域，提出模拟退 火算法，它源于对固体退火过程的模拟，采用m e t r o p o l i s 接受准则，并用一组称为 冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。 在模拟退火算法中，设优化问题的一个解i 及其目标函数厂( f ) 分别与固体的一个 微观状态f 及其能量e 等价，设随着算法进程递减其值的控制参数t t $ 当固体退火过 程中温度的角色，则对于控制参数，的每一取值，算法持续进行“产生新解一一判 断一一接受舍弃的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程， 也就是执行了一次m e t r o p o l i s 算法。与m e t r o p o l i s 算法从某一初始状态出发，通过计 算系统的时间演化过程，求出系统最终达到的状态相似，模拟退火算法从某个初始 解出发，经过大量解的变换后，可以求得给定控制参数时组合优化问题的相对最优 解。然后减少控制参数f 的值，重复执行m e t r o p o l i s 算法，就可以在控制参数r 趋于 零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐 降温，才 能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也 必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。 模拟退火算法用m e t r o p o l i s 算法产生组合优化问题解的序列，并由与m e f ，o p o l i s 准则对应的转移概率p ，即 1 8 华北电力大学硕士学位论文 只c ，d = e x p 。垒堇；趔，；：劣三； 3 c 2 一2 ， 确定是否接受从当前解f 到新解的转移。 假定存在领域结构和产生器，再设厶表示m e t r o p o l i s 算法第k 次迭代时产生的变 换个数( 也称为m a r k o v 链长) ，气表示m e t r o p o l i s 算法第k 次迭代时控制参数f 的值 瓴= r ( q 一。) ) ，r ( f ) 表示控制参数更新函数，f ，表示终止温度。下面以最小化目标函 数为例，介绍模拟退火算法的具体操作步骤。 可随机产生一个初始解，以此作为当前最优点，并计算目标函数值。 设置初始温度、终止温度及控制参数更新函数：岛，f ，及r ( f ) 。 t k = 丁( 乓一，) 。设置厶，令循环计数器初值k 卜1 。 对当前最优点作一随机变动，产生一新解，计算新解的目标函数值，并计算 目标函数值的增量。 若 0 ，则接受该新解为当前最优点；若a 0 ，则以概率式( 2 - 1 2 ) 的方式接 受该新解为当前最优解。 若k 厶，则k 卜k + 1 ，转式。 若t 9 4 9 ，经验法则要求算法进程在合理 时间里搜索尽可能大的解空间范围，只有足够大的f 0 值才能满足这个要求， 控制参数终值t ， 控制参数的终值t ，通常由停止准则确定，合理地停止准则既要确保算法收敛于 某一近似解，又要使最终解具有一定的质量。 m a r k o v 链长厶 m a r k o v 链长度的选取原则是：在控制参数t 的更新函数已选定的前提下，厶应 选得在控制参数的每一取值上都能恢复准平衡。 不同的方法选取的m a r k o v 链长度就会不同，厶可以选取一个与控制参数气取值 无关的常数；也可以使得m a r k o v 链长度与该链遵循的目标函数值得波动情况相关， 得到的厶值将随算法进程动态变化。 m a r k o v 链长度的选取要据优化对象而适当选取，过大的链长只会导致c p u 时间 无谓地增加，无助于最终解质量的提高，因此，厶值只应选得“适当大 。 更新函数r ( f ) 为避免算法进程产生过长的m a r k o v 链，控制参数以的衰减量以小为宜，即“以 小为宜 是控制参数函数的选取原则。 一个常见的控制参数更新函数是 t k + l = a * t k k = o ，1 ，2 ，( 2 1 3 ) 式中：a 是一个接近1 的常数。 另外，n a h a r 等固定控制参数值的衰减步数k ，再通过实验确定f 。值， k = 0 ，l ，2 ，k 。s k i s c i m 等人把区间 0 ，t o 】划分为k 个小区间，把控制参数的更新函数 取为 t k ：1 k - _ k 气 后：0，1，2，k(2-14) a 上式也是一个常见的控制参数函数 2 3 2 模拟退火算法的改进方向 m e t r o p o l i s 准则的选择概率确定。m e t r o p o l i s 准则是对新样本和老样本的函数 值进行比较，然后定出接受新样本的概率值。所以可以根据优化对象来通过增加概 华北电力大学硕士学位论文 率系数来改变接受新样本的概率值。 控制参数初值气和控制参数终值t ，的选择。根据优化对象的不同，这两个参 数的选择也不同，控制参数初值名一般会取得很大，但具体大的程度要通过对函数 的分析才能给出：同样，控制参数终值t ，的选择的大小选择同样要在寻优过程中通 过对函数值的大小及函数之间的差值而定。 m a r k o v 链长厶的恰当选择。m a r k o v 链长厶可以通过自适应选择，在寻优初 期，m a r k o v 链长厶可以选择得更长，在寻优后期，m a r k o v 链长丘可以适当地选择 短些。 更新函数丁o ) 的确定。为避免m a r k o v 链长厶过长，更新函数t ( t ) 的衰减量要 “以小为宜。实际上，在寻优过程中，要将更新函数丁( f ) 的衰减量和m a r k o v 链长厶 调节到得到更好优化解的值。 2 4 粒子群算法 2 4 1 粒子群算法的操作过程 粒子群算法( p s o ) 算法初始化为一组随机粒子( 随机解) ，然后通过迭代寻找最 优解。粒子追随两个当前最优值来更新自己，一个是粒子迄今为止寻找到的最优值， 叫做个体极值，；另外一个是整个粒子群迄今为止寻找到的最优值，叫做全局极 值，粒子更新自己的公式如下： 巧- - w + q 吒一再) + 乞眨c 一再) ( 2 1 5 ) 其中：k 当前代的粒子移动速度； 随机数，范围0 1 ；c l ，c 2 ，学习因子， 当前代速度影响的权重，w 的确定： w2 w i m 一w r _ a “- - w n u n i t e ， i t e r w , ( 2 - 1 6 ) 巧一。前一代的粒子移动速度；，i ，呢， 一般取q = c 2 = 2 ；w ，上一代的速度对于 ( 2 - 1 7 ) 其中w 仃戳，分别为开始时和结束时的权重；i t e r 咄为最大，迭代次数，i t e r 为 当前迭代次数，一般取w 眦= 0 9 ，w m 2 0 4 。 在运动过程中，将对每个位置的适应度不断进行再评价。如果某个粒子的适应 度优于，则该粒子所处位置成为群最优粒子位置，这样将不断更新为群 最优位置；而且在粒子群的运动过程中，每个粒子的自身适应度也可能出现更优值， 此时将g 蛔，更新为该位置。粒子在向转移的同时也向靠拢。 2 1 华北电力大学硕士学位论文 2 4 2 粒子群算法的改进方向 种群数的选择。和前三种算法需要对种群数做出选择的原因是一样的。因为 种群数的大小会影响优化的速度和结果。 学习因子c t 和c 2 的适当选择，还有上一代的速度对于当前代速度影响的权重， w 的适当确定，这三个因素是影响每个样本更新速度参数。同样，这单个参数可以 在实际寻优的过程中采用自适应改变的办法。 为了增强样本的多样性，可以在粒子群算法中加入变异这一个步骤。 2 。5 本章小结 本章的第一部分主要