基于人工蜂群算法的Van der PolDuffing振子的参数辨识

基于人工蜂群算法的Van der PolDuffing振子的参数辨识 基于人工蜂群算法的Van+der+PolDuffing振子的参数 辨识 分类号?? 学校代码垒 劣潭理歹大署 学 位 论 文 题 目 基王厶墨鳖登簋洼盟堡旦拯王鲍叁熬羞垫 英文趑目亘亟皇坠鱼鱼竺垒鱼塾. ????????????????????????一?一 指导教师 姓名?壹一职称一.割整撞学位谴? 申请学位级别 硕士 论文提交日期』. 论文答辩日期』.. 学位授予单位 盍垫墨墨盘堂学位授予日期 评阅 答辩委员会主席坌缝鲴 年 月四 椒舡大嚣等文?芋日月孑黼四四 独创性声明 本人声明,所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方 外,论文中不包含其他人已经发或撰写过的研究成果,也不包含为 获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 研究生签名:?匀孛年日期互型也一 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定,即: 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版, 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索,可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文,并向社会公众提供信息 服务。 保密的论文在解密后虞遵守此规定 研究生签名,:?租导师签名,舡日期一 注:此表经研究生及导师签名后,请装订在学位论文摘要前页。摘要 系统控制与同步是控制工程的重要组成部分,一直以来在工程应用的诸多领 域备受关注。作为系统控制与同步的前提,系统辨识有着十分重要的理论意义和 应用价值。自年以来,国际自动控制联合会曾多次召开过以系统 辨识和参数估计为主题的专题会议。到目前为止,系统辨识已取得了许多成果, 不仅在航空航天、工业生产中有着广泛应用,而且在经济管理、生物医学、气象 学、环境工程和社会系统等领域发挥着至关重要的作用。 作为一种新的群智能优化算法,算法在年才经提出,研究时间较 短。此算法主要用于多维度、多峰值的优化问题,其仿真结果可与算法和 算法相媲美。因其参数少、演化速度快、计算简单、易于实现等优点,算法 一经提出就在引起了研究人员的高度注意,但目前为止,该算法很少被用在系统 辨识的问题上。 本文旨在对算法做进一步的分析研究,在此基础上对算法加以改进, 建立恰当的数学优化模型,设计通用的求解系统辨识问题的,对一类非线性 振动系统“ .”振子的未知参数进行辨识。 第一章首先介绍了系统辨识的研究背景和意义。其次介绍了系统辨识的方法 以及系统辨识的国内外研究现状。最后给出了本文的研究内容、研究目的以及文 章的结构安排。 第二章首先概括地描述了智能优化算法的概念和意义,而后列举了目前常用 的一些智能优化算法。最后,通过详细介绍、、、四种算法的 优化原理、算法、研究现状、应用成果,着重说明了演化算法以及群智 能算 法。 第三章是对算法的详细论述。首先介绍了算法的产生与发展过程。 而后说明了该算法的优化原理。最后对此算法的全局收敛性进行了说明。 第四章提出了带有空间收缩机制的人工蜂群算法。为改善算法的 后期探索能力,每隔一定的演化次数,以当前最优解为中心定义新的搜索空 间, 在新空间中重新初始化种群。 第五章采用算法对振子的未知参数进行辨识。辨识过程分为 无噪和含噪两个阶段,基于对辨识结果的定量和定性分析,说明了改进后的 算法在解决此类问题中的可行性、有效性。 第六章总结全文所做工作,对将来的研究工作做出展望。 关键词:系统辨识,算法,空间收缩,振子 . . , , .. ., , ,?, , , . .., , ,.. . , ,, ,“ . ” , .. , . ,. , , . , ,,,. , ,., ., .. ,. , . . . ,. : . , . , . . : , , , 目录 摘要??.. 目录. 第章绪论 .本文的研究背景和意义??. . 国内外研究现状??. ..国外研究现状. ..国内研究现状. .本文的主要研究内容. .本文的研究目的??. .本文的组织结构??. 第章智能优化算法. 概丕一 .演化算法??. ..... 的概述... 的计算流程 .. 算法 ... 的概述... 的计算流程 ... 算法的发展与应用 .群智能算法?. .. 算法.. ... 算法的概述??一 ... 算法求解的模型?. ... 算法的发展及应用.. 算法... 算法的概述??... 算法的计算流程 ... 算法的发展.本章小结第章算法的概述.. . 算法的产生和发展..算法的产生? ..算法的发展? . 算法的优化原理??。 ..算法的数学模型..算法的流程图和伪代码.算法的收敛性哺.. 算法的链模型一 ...基本概念和数学定义 ... 算法的模型?.. .. 算法的收敛性分析... 随机优化算法的收敛性准则 ... 算法的全局收敛性.本章小结第章带有空间收缩机制的算法. .不完全演化算法.空间收缩机制 . 算法? .. 算法的思想? .. 算法的意义? .. 算法的流程图和伪代码..参数设定.本章小结第章算法在系统参数辨识中的 应用.. . 振子?.. . 振子辨识的数学模型.. . 仿真结果..单井振子??. ...心? ...?躲%? ...单井振子的次独立仿真结果..双井振子??. ...脓? ...?研%? ...双井振子的次独立仿真结果..双峰振子??. ...?驻%? ...双峰振子的次独立仿真结果..仿真结果分析 .本章小结第章总结与展望??. .全文总结.本文展望致谢. 参考文献?. 攻读硕士期间发表的论文.武汉理工大学硕士学位论文 第章绪论 .本文的研究背景和意义 系统控制与同步是控制工程的重要组成部分,一直以来在工程应用的诸多 领域备受关注。经过研究人员的多年努力,目前已提出了许多行之有效的系 统 控制与同步的方法,但这些方法一般是在假设系统参数已知的前提下进行的。 然而,在现实生活中,系统的参数通常是部分未知甚至是全部未知的。因此, 要想对系统加以控制和应用,必须先对其进行正确理解和精确建模,将其中未 知的参数辨识出来。由此可知,系统辨识有着十分重要的理论意义和应用价值。 自上年以来,国际自动控制联合会曾经多次召开过以系统辨 识和参数估计为主题的专题会议。目前为止,系统辨识已取得了诸多成果,不 仅在航空航天、工业生产中有着广泛应用,而且在经济管理、生物医学、气象 学、环境工程和社会系统等领域发挥着非常重要的作用【】。 根据对系统状况所知的多少,可将系统辨识问题分作两大类,即完全辨识 问题和不完全辨识问题。其中,完全辨识问题又称作“黑箱问题,这类系统的 辨识非常困难,目前尚无有效方法;不完全辨识问题又名“灰箱’’问题,即已 知系统的结构模型,但不确切了解模型的阶数和参数值。实际生活中,许多系 统辨识问题属于“灰箱”问题【】。 系统辨识是动力学研究的反问题。与已知操作参数的确定性系统的数值问 题相反,系统辨识则是通过恰当处理实验所得数据或者数值分析所得数据,建 立起近似地反映系统输入输出特性的数学模型,进而辨识出系统的未知参数 的, 属于典型的“灰箱问题”】。 系统辨识的主要内容【】: 选择模型。根据建模时的实际需要和对系统信息的了解,选择适当的 模型。 采集数据。选择恰当的试验信号,确定采样间隔和时间长度,记录系 统的输入输出数据。 参数估计。根据采集得到数据,选用某种辨识方法,对模型的参数进 行估计。 模型检验。对实验数据进行拟合,从而检验估计所得的数学模型和实武汉理工大学硕士学位论文 际系统是否相符。如果检验结果达标,则试验停止,所得估计值即为系统辨识 的结果;如果检验结果差太多,则调整模型,反复试验,直到检验结果合格为 止。 智能优化算法,或者说现代启发式算法,是一类全局优化能力强、具有通 用性、适合于并行计算的算法。算法本身具有严密的理论依据,不是单纯地凭 借经验,理论上能在可接受的时间范围内找到最优解或近似最优解。常用的智 能优化算法有演化算法和群智能算法两大类,目前,这两类算法在优化问题和 实际生活中均有着广泛应用。其中,群智能算法的研究起步相对较晚,具有较 好的开发潜能。 人工蜂群算法是一种新的群智能优化算法,该算法在年才经 提出,研究时间较短。此算法主要用于多维度、多峰值的目标函数的优化,其 仿真结果可与算法和算法相媲美【】。因其设置参数少、演化速度快、计 算简单、易于实现等优点,算法一经提出就在引起了研究人员的高度注意,但 目前为止,该算法很少被用于系统辨识的问题上。 算法旨在对算法做进一步的分析研究,在此基础上对算法加以改进, 建立恰当的数学优化模型,设计通用的求解优化问题的方法,对系统未知参数 进行辨识。上述研究一方面可以拓广智能优化算法的应用领域,另一方面也促 进了系统控制和同步的发展。 . 国内外研究现状 常用的系统辨识方法大体可分作经典算法和非经典算法两类。当然,根据 其他的划分标准,还可以分为时域、频域法,参数、非参数法,确定、非确定 法等。常用的经典系统辨识方法有:最小二乘法、极大似然法、梯度校正法, 时域中的阶跃响应法、脉冲响应法,频域中的频率响应法,相关分析法以及谱 分析法等。之后,为克服最小二乘法存在偏差的缺点,在此基础上,又提出了 其他辨识方法,如:广义的最小二乘法、增广的最小二乘法、辅助变量法以及 随机逼近法。 在过去的几十年里,经典的参数辨识方法已经讲究得比较透彻,而非经典 的辨识方法,如:人工神经网络算法,遗传算法,遗传规划,差分 演化算法,粒子群优化算法,人工蜂群算法等的研究 才刚刚起步,有待进一步的探索和发掘【】。根据无免费午餐理论【】,无论是经典武汉理工大学硕士学位论文 的参数辨识方法还是非经典的参数辨识方法,都有各自的优点和不足,因此最 终的算法选择取决于所研究的对象。但通常情况下,经典方法采用的多是点到 点的搜索策略,容易收敛到局部最优点,而非经典的参数辨识方法不受梯度的 限制,与初始点的选取无关,且对有噪声的系统表现出了较强的鲁棒性,在工 程应用中竞争力更强。鉴于此,本文将着重分析非经典算法在非线性系统辨识 中的研究状况。 ..国外研究现状 自上世纪年代以后,非经典算法在非线性系统参数辨识问题上的应用逐 步发展起来,直至目前已取得了丰硕的成果。.等利用多层神经网络对离 散时间的非线性系统模型的未知参数进行了辨识。和 采用辨识了两种感应电动机的未知参数【】。等将算法用于 函数链接型人工神经网络的辨识,该算法在辨识速度和精度上都超 过了算法【】。 等人采用改进的算法对混 沌系统??系统进行辨识,并与、标准算法的辨识结 果作对比,得出在辨识精度和计算时间上均优于其他两种算法【】。 和等人采用改进的算法辨识了一些数学模型中的未知参数【】。 和等采用不同的算法和算法对三类振子的未 知参数进行辨识,并对这两类算法的辨识结果给予了对比分析【】。和 采用几种演化算法包括,,对振子的未知参数进行辨识, 对比分析了辨识结果【】。 ..国内研究现状 国内学者在该领域的研究相对较晚,但近十年来的发展较为迅速。陆冠群、 吴俊莹提出了一种基于遗传算法的带有外部输出的非线性自回归系统辨识 算法 ?,用于连续时间的和离散时间的非线性系统的参数辨识【】。葛红 伟、梁艳春提出一种基于的网络学习算法,用于超声马达的参数辨 识【】。张艳、李少远采用算法对非线性系统模型做了辨识【】。边信 黔、牟春晖对神经网络进行改进,提出了一种带输出反馈的. 神经网络,用于个自由度的的辨识【】。付华将混沌免疫粒子群算法 与神经网络相结合,提出了一种耦合算法.州,并武汉理工大学硕士学位论文 将此算法用于非线性系统的参数辨识中【】。高飞采用算法辨识了三种含噪 声 的混沌系统的参数【】。 .本文的主要研究内容 本文主要以算法为基本工具,研究非线性动态系统的参数辨识问题。 具体内容如下: 对算法的分析与改进 以算法理论和数值实验两方面为基础,分析算法的优缺点,找出合理 的改进方向。和其他智能优化算法类似,算法的前期搜索能力较强,目标 函数值变化较快,及至后期,变化较慢。为改善算法的后期探索能力,每隔一 定的演化次数,以当前最优解为中心收缩空间,在新空间中重新初始化种群。 经测试函数进行验证,发现改进后的算法精度更高,稳健性更强。 采用改进后的算法对系统的未知参数进行辨识 建立恰当的数学模型,将系统的参数辨识问题转化为最小化问题,采用改 进的算法辨识出系统的未知参数。 .振子是一类 典型的非线性动力系统,在工程应用和物理学中常常见到,许多动态行为都 可 以以此为模型进行建模。因此,本文将以振子为例研究系统辨识问题。 .本文的研究目的 振子是高度非线性的,在取定某些参数或特殊条件时,系统还可以是 混沌的。所以,在采用非的方法进行系统辨识时,待辨识的参数所定 义的范围上对应的振子实际上是多个复杂非线性系统的集合。采用 算法做辨识,其实质是在上述诸多的系统中,找出最合理最真实的那一个。 .本文的组织结构 第一章绪论。本章简要地描述了系统参数辨识的研究背景、意义以及研究内 容; 对比分析了常用的系统辨识方法,详细列出了非线性系统参数辨识的 国内外研究现状;论述了本文的主要研究内容,研究目的;最后则交 代了本文的组织结构。 武汉理工大学硕士学位论文 第二章智能优化算法。本章概括说明了智能优化算法的概念和意义;详细描 述 了几种常用的智能优化算法,如遗传算法,算法,算法 以及算法的优化原理、算法流程、研究现状、主要应用。 第三章算法的系统论述。本章首先介绍了算法的产生与发展过程, 而后说明了算法的优化原理,最后对算法的全局收敛性进 行了说明。 第四章带有空间收缩机制的算法。本章针对基本算法后期收敛速度 慢,易陷入局部最优的弊端,引入了空间收缩机制,提出一种带有空 间收缩机制的算法??算法。 第五章算法在系统参数辨识中的应用。本章采用算法对 振子的未知参数进行辨识,辨识过程分为无噪和含噪两步。通过对辨 识结果的定量和定性分析,说明了算法在解决此类问题中的可行 性、有效性,推进了智能算法在系统参数辨识中的应用。 第六章总结和展望。本章先对全文所做的研究工作进行总结,之后对进一步 的 研究方向和研究内容做出展望。武汉理工大学硕士学位论文 第章智能优化算法 . 概述 作为科学技术的一个重要分支,优化技术是一门建立在数学基础上的、用 于求解各类工程问题优化解的应用技术。如今,随着计算机技术的迅速发展, 优化技术越来越受到人们的重视,广泛地渗透到工程应用的诸多领域中。考虑 到工程问题的复杂度、非线性、实际条件的约束性、具有多个局部极值以及建 模困难等特点,找寻适合大规模并行计算、具备智能性的算法已经成为相关学 科的主要研究目标和研究方向。 世纪后半页,通过模拟和揭示某些自然现象或自然过程,诞生了一批新 的优化算法。这些算法涉及到数学、物理、生物、人工智能以及统计学等多个 学科,为实际问题的解决提供了新的思想和方法。鉴于此类算法构造的直观性 以及对自然机理的借鉴和学习,通常称这些算法作智能优化算法或现代启发式 算法【】。 常用的智能优化算法有:人工神经网络算法、模拟退火法、禁忌搜索法、 演化算法、群智能算法等。下面将对两种经典的演化算法、算法以及两 类经典的群智能算法和算法进行介绍。 .演化算法 演化算法是建立在达尔文的自然演化以及孟德尔的遗传定律上的一 类随机优化方法。它们模仿自然演化的工作原理,赋予群体中的每个个体一 个 适应度值,并包含有随机元素。的研究可以追溯到世纪年代早期,那 时就产生了利用达尔文的演化原理自动解决问题的思想。到了年代,这个思 想催生了两种:演化规划、演化策略。大约十年后密歇根大学 的 提出了。 .. ... 的概述 是一种基于自然选择、群体遗传机制、通过模拟自然进化的思想,搜索武汉 理工大学硕士学位论文 最优解的算法【】。过去年,在复杂全局优化问题的应用方面,取得了成 功,并受到了广泛关注。的应用研究比理论研究更为丰富和成熟,已渗透到 多个学科领域,如:复杂的非线性最优化和组合优化,整数规划,工程应用, 以及计算机科学,生物学,社会科学,经济学等学科领域。在采用解决问题 时,问题的可行解要被编码成为一个个“染色体,也即个体。这些个体构成了 种群,种群中染色体的数目称为种群的大小或种群规模。 ... 的计算流程 随机生成若干个初始染色体。 借助评价函数评价每一个染色体的适应度。 遗传算子的操作,这里共有三个遗传算子:选择、交叉、变异。其具体 操作如下: 根据适应度从种群中选择较为优良的染色体,染色体适应度越高,其被 选中的可能性就越大。 对选择后的新种群执行交叉操作,把两个父代个体的结构替换重组,从 而得到新的个体。经过交叉,的搜索能力有所提高。交叉操作是按一定的交 叉概率选取父代个体的,交叉的位置也是随机选定的。交叉概率只的取值通 常 为.~.。 接下来是变异操作,以很小的变异概率 随机地改变个体的某些基因的 值。变异操作旨在增加种群个体的多样性,防止算法早熟收敛。需要注意的 是, 变异概率取值不宜太大,当 .时,就会退化成随机搜索,如此一来, 遗传算法的某些重要特性也就随之消失了。 经过上面的操作,我们会得到新的染色体种群。接下来,对新种群 重复中的选择、交叉、变异操作,直到算法满足终止条件时为止。最后, 将最优的染色体作为最优解输出。 .. 算法 ... 的概述 与类似,算法也属。为解决 提出的多项 式拟合问题,和在年提出了算法。此算法在处理非线 性、不可微、多峰值的目标函数的优化上颇有成效。武汉理工大学硕士学位 论文 ... 的计算流程 一面是算法的基本原理及算法的大体结构,这里给出的是/// 的版本【】。 给定优化问题厂,.??,其中五,,,杨,,分别表示 取值的下界和上界。下面是采用算法求解该问题的最优解的一般步骤: 种群初始化 随机生成胛个维向量誓薯,薯,,%,,,,。 变异 对由步骤得到的初始种群执行变异操作:。‘一‘。其中 ,,,?,,,互异,为满足这个条件,??;,?【,】是缩放 因子,它是一个实常数,用于控制差向量一:一一,的缩放幅度。 交叉 为增加解向量的多样性,算法引入了交叉算子,通过对当前解向量五和变异 向 量进行交叉,得到新的解向量吩。 ?,, ’ % . 圹协锟,鲫躲后?,,,。,。如果阳二, 其中?【,】是预先设定的交叉概率,可根据不同的问题需要自行设定;, 是第/个【,】之间的随机数;后?,,,是随机选定的下标,七的选取方法保 证了吩至少有一个分量来自。 选择 对交叉后得到的解向量和当前解向量五进行比较,择优选入下一代种群: ,一心如尉坼?厂薯 。 ?薯,其他 ... 算法的发展与应用 由于算法结构简单,易于实现,鲁棒性强,因此在之后的十几年中,无 论是算法模型方面还是应用方面,算法都得到了迅速发展。 对算法模型的改进可分为以下三个方面.?控制参数的改进,主要是针 对差向量比例因子和交叉概率的改进;?操作算子的改进,如对变异算子、交 叉算子的改进:?混合算法,将两种或多种算法的优点相结合,形成新的算 法是算法改进的又一常见做法。在过去十几年,已与其他几种全局优化武汉 理工大学硕士学位论文 算法如,蚁群系统,人工免疫系统,细菌觅食优化算法,模拟退火法成功 结合。此外,也有一些人将局部搜索技术加入了算法,以提升算法的搜索能 力。 算法的应用【】:在优化方面,算法及其改进形式主要被用于单目标 优化,多目标优化,约束优化,大规模优化,动态和不确定环境的优化,以及 多峰值优化等。另外也被用于神经网络的训练,数据挖掘,微列,工程设 计,系统辨识,图像处理,电力系统设计,化学工程与生物系统,调度问题等 实际问题中。 .群智能算法 群智能可简单定义为分散的自组织群体的集体行为,譬如鸟群、鱼群、蚁 群、蜂群等都是具有群智能的生物种群。群体中的智能行为源于种群中个体 问 的相互作用以及个体与环境间的相互作用形成的网络。群智能日渐成为计算 机、 工程、经济、生物信息以及其他许多学科的重要研究领域。 世界上的群体有很多,但不是每一种群体都具有群智能,白组织以及分工 是群智能的两个重要特征。年提出了群智能需具备的五个特征【】: 邻近:群体要具有执行简单的空间和时间运算的能力。 质量原则:群体要能对周围环境质量因素的变化做出反应。 反应多样性原则:群体不应该把要获取的资源限定于某个较小的范围内。 稳定性原则:群体应具有一定的稳定性,不用随着环境的每一次变化而变 化。 适应性原则:当有必要时,群体应能够改变自己的行为模式。 上世纪年代,两种重要的群智能算法??和算法被提出,这 两种算法被不同领域的研究人员研究和发展,由此解决了现实世界中的许多 难 题。下面将对这两种群智能算法给予详细说明。 .. 算法 ... 算法的概述 算法指的是一类算法,最早的算法叫做蚂蚁系统,是由 ,和在年提出的,其灵感来自蚂蚁觅食过程中发 武汉理工大学硕士学位论文 现路径的行为【,】。蚂蚁在运动时会释放一种信息素来指引自己的运动方向, 并 以此进行群体间的交流。由此,蚁群会呈现出信息正反馈现象:某一路径上途 经的蚂蚁越多,相应地此路径上的信息素的浓度就越大,进而后来选择这条 路 径的蚂蚁就越多。这样下去,最优路径上的信息素持续增多,其他路径上的信 息素则随着时间的变化而减少,最终,整个蚁群就找到了最优路径。 鉴于蚁群觅食行为与旅行商问题的相似性,最初被用于求解。 但算法中的人工蚂蚁与真实的蚂蚁略有不同:人工蚂蚁有“记忆”,能够记 住已访问过的地点,不会重复访问;人工蚂蚁可以得知两个地点间的距离, 并会择近访问下一地点。 ... 算法求解的模型 下面给出利用蚂蚁系统求解的模型??.模型:考虑一个具有 ,个城市的和一个有只蚂蚁的蚁群:,,表示城市和城市,之间的距离; 表示时刻时城市的蚂蚁数目,则?;%表示时刻城市与 城市/之间的路径上的信息素量,%设置为一个常数。为使蚂蚁不重复地访 问个城市,定义一个禁忌表用于记录蚂蚁访问过的城市。一次迭代结 束后清空禁忌表,蚂蚁重新选择路径,重新定义禁忌表。 在时刻,蚂蚁从城市到城市,的概率,,‘为: 勺口. ,如尉? ?气口%卢 ’’ ,其他 其中,%是城市到城市/的期望度,一般定义为/略;口,‖分别表示%和%的 重要度;,,,,一是没有被蚂蚁访问过的城市集合,当 全部个城市都添加到时,蚂蚁就完成了一次迭代,它的整条路径就是 问题的一个解。 待所有的蚂蚁完成一次迭代之后,信息素量就要更新,由于信息素会随着 时间的流逝而减少,故其更新公式为: 乃【/, ?乃??乃‘, 武汉理工大学硕士学位论文 奢侈蚂蚁旌过了路径“ ,其他 其中,?,】是路径上信息素的蒸发系数;?%是当前迭代过程中路径耖上信 息素的总增量;?%‘是蚂蚁尼在路径耖上释放的信息素量,取作/厶,厶是路 ... 算法的发展及应用 除上述.系统模型之外,根据?%‘的不同取法,还有. 和.两种系统模型,。前面一种模型利用的是全局信息,后面两种模型 利用的则是局部信息,这三类模型在求解不同的问题时各具优势。 为改善的性能,和提出了蚁群系统,相对于 ,提升了求解大规模的能力【】。为解决易陷入局部最优的问 题,等人提出了一种新的蚁群算法,最大一最小蚂蚁系统【】。 等人提出了基于排序的【】。对的改进形式进行 总结,提出了用于解决离散优化问题的通用算法??蚁群优化】。此 外,还与、、人工神经网络、人工免疫算法等其他优化算法融合在 一起,形成新的算法【】。 随着研究的深入,算法在应用方面也得到了极大的扩展,如今算 法不仅被用于求解,还被用于求解分配问题,图着色问题,调度问题,车辆 路径等优化问题,此外也有在数据挖掘,图像处理,系统辨识,电子电路设计, 无线路由等实际问题中的应用【】。 .. 算法 ... 算法的概述 算法产生于年,它是由美国的社会心理学家博士和电气 工程师博士共同提出的,是群智能的代表性算法之一【】。该算法通过 对一个简化的社会模型进行仿真模拟,立论于两种理论学说:一、人工生命, 特别是以鸟群、鱼群为代表的群集理论;二、演化计算。通过将鸟群、鱼群等 带有群智能的群体中的个体抽象为没有质量、没有体积的粒子,就得到了粒子 群的概念。算法的中心思想是通过群体中个体之间的相互合作、信息共享武汉理工大学硕士学位论文 来寻找最优解,其本质是一种并行的全局性随机搜索方法。 在算法中,每个粒子代表一个解,这些粒子在搜索空间中飞行,寻找 最佳位置。在每一次迭代中,粒子借助本身以及周围粒子的经验调整自身位置。 搜索空间中的粒子状态由两个因素决定:粒子的位置和粒子的速度,它们通过 下列公式更新: / 一尼置尼七 其中,’,,,表示第个粒子的速度;置葺’’,%表示第个 粒子的位置:表第个粒子历经的最佳位置局部最佳位置;表 示群体中所有粒子经历过的最佳位置全局最佳位置;和是『,间 的两个随机数;,是两个正数,称为加速系数;是粒子之前的速度, 用于记录之前的飞行方向;尼一置尼为认知部分,表示粒子当 前所在位置与自身最佳位置之间的差距;一墨尼是社会部分, 表示粒子当前所在位置与群体最佳位置之间的差距。此外,粒子的速度被一 个最大速度 ‰服徘悭糍三甍。 ... 算法的计算流程 初始化粒子群体包括粒子位置和速度,设置为粒子的当前位置, 取作群体极值所对应的粒子位置。 对每个粒子进行评估;将其当前适应值与的适应值做对比,如果当 前适应值更高,则用它替换;将其当前适应值与对应的适应值做对 比,如果当前适应值更高,则用它替换。 根据公式和更新粒子的速度和位置。 判断算法是否满足终止条件,如果满足,则终止算法;否则,转。 ... 算法的发展 虽然相对于传统的优化算法,算法在解决复杂的优化问题方面存在许 多优势,但算法也有两大缺点:一、算法性能依赖于被优化的问题。此依武汉 理工大学硕士学位论文 赖性主要表现在参数的设置上,不同的参数设置会引起巨大的性能差异。解 决 这个问题的一般方法就是采用自适应的参数。二、算法早熟,收敛到局部最 优。 在进行多峰值的函数优化时,常常会遇到这类问题。针对上述两个缺点,研究 人员对基本算法做了许多修改,所取得的成果如下: 加入对惯性权重和收缩因子 和】引入了一个新的参数,惯性权重,用于改进粒子速度, 把公式变作 ?尼?尼口聆船‘尼一墨一置尼。 和】引入了收缩因子用于控制算法的收敛性。的计算公 , 式如下:??毫『,.,加入收缩因子后,公式 一一、/ 变为:尼尼甜‘尼一置尼阳,。 其他方面的改进 如为增强算法的搜索能力、防止算法早熟、平衡算法的全局探索和局部开 发能力等所做的改进;与、以及等算法融合,提出新的算法【】。 算法的应用:自该算法提出后至今的十几年间,算法及其改进形 式在优化问题和实际应用方面均取得了成功。目前算法主己被用于无约束全 局 优化,约束全局优化,离散优化,多目标优化,车间调度,工程设计,电磁应 用,电源规划,医学图像处理,电力系统,数据挖据,聚类分析等领域【】。 .本章小结 本章从最优化算法谈起,简要叙述了最优化算法的概念、发展进程、智能优 化算法的衍生;而后列出了几种常见的智能优化算法,对其中常用的两类算法 ??和群智能算法给予了详细说明。针对的代表算法和,以及群 智能算法的代表算法和,分别从算法的优化进程入手,分析了算法的 优缺点,讨论了算法模型的改进途径,最后总结了算法的应用。武汉理工大学硕士学位论文 第章算法的概述 . 算法的产生和发展 ..算法的产生 如..中所述,群智能的两个重要特征是自组织和分工。作为一种群居式 昆虫,蜜蜂的许多行为如:舞蹈用于交流、觅食、交配、任务选择、巢址选 择、群体决策、导航等均带有上述两个特征,由此可以确定蜂群是具有群智能 的昆虫群体。 一个带有蜂群群体智能特性的最小觅食选择模型包含有三个要素:食物源, 被雇佣的觅食者和未被雇佣的觅食者;两种主要的行为模式:向食物源招募蜜 蜂和放弃食物源【】。 食物源:一个食物源的质量取决于多个因素,如:食物源与蜂巢的距 离,食物源的蜜量多少,蜂蜜的集中程度,采蜜的难易程度等。为方便起见, 现定义一个单一的量??“收益率”,来描述食物源质量的优劣。 被雇佣的觅食者:被雇佣的觅食者与之当前开采的食物源联系在一起, 这类蜜蜂从外界带回食物源的信息,如蜜源与蜂巢的距离、蜜源所在的方向, 蜜源的收益率等;而后以一定的概率将这些信息与蜂巢中的其他蜜蜂分享,蜜 源的收益率越大,该蜜源被分享的可能性也就越大。 未被雇佣的觅食者:未被雇佣的觅食者持续地搜寻待开发的食物源, 这类蜜蜂又可分作两小类:侦察蜂和跟随蜂。侦察蜂在没有预知任何信息的情 况下,随机地在蜂巢周围的环境中搜索新的食物源;跟随蜂则在蜂巢中等候被 雇佣的蜜蜂提供信息,然后根据所得信息寻找已被开采的食物源。 由于跟随蜂收到的食物源的信息并不唯一,因此,它会对这些食物源 做比较,选择收益率最大的那个进行觅食。所以,当食物源的收益率越大时, 被雇佣的觅食者越有可能向该食物源成功招募其他蜜蜂,从而有更多的蜜蜂开 采这个食物源。 开采食物源的蜜蜂越多时,食物源被开采的速度就越快,当此食物源 被开采殆尽时,被雇佣的觅食者就会选择放弃该食物源,转而成为侦察蜂,去 寻找新的食物源。 通过对上述蜂群觅食过程的仔细研究,等人模拟蜂群的觅食过程 武汉理工大学硕士学位论文 提出了一种新的群智能算法??算法,用于解决多维度多峰值的优化问题。 ..算法的发展 虽然算法的历史只有短短年.,但目前取得的成果颇为 可观:年建立了算法研究的专属网站://.../: 在年的 年 和中,算法都是重要的主题算法之一。 虽然算法没有和等算法的研究成熟,但是蜂群所具有的独特智 能对某些实际问题还是非常有效的。很遗憾的是,目前对算法的收敛性分 析的研究相对匮乏,控制参数的调整及理论研究不足,因此,需要对算法 做进一步的探索和研究。 目前算法的研究共可分为三类:算法的对比分析和改进;通过与其他 算法融合,提出新的混合模型;算法的应用。下面将从国外和国内两个方面对 该算法的研究现状进行说明。 国外方面 基于一些测试函数,等人将算法和,,,等 算法进行对比,分析相应的优缺点,为算法的改进奠定了基础【】。一些研究 人 员则从算法的控制参数和所用机制展开研究,对算法进行了改进,如: 以及等通过研究种群大小对优化结果的影响,提出了两种新的 人工蜜蜂更新位置的方法。】;和从初始化方面对算法进行了 改进】;等人对算法引入了新的变异步长的自适应机制等【】。 与其他算法进行融合、提出新的混合算法,是算法改进的又一重要途 径,如:与.单纯形法的融合,与的融合,与的融合 等。这些改进不仅为算法的深入发展打下了基础,也为其他算法的改 进提供了经验。除此之外,还有将混沌论引入算法,形成混沌蜂群算法, 以及高斯算法和算法等其他的改进形式。 除了算法模型的改进,算法在求解优化问题方面上也取得了成功。该 算法在单目标优化问题上的成功应用,启发了研究人员对其在其他优化问题 上 的推广,如:和将算法应用到了整数规划的问题上【】; 等对算法进行改进,提出了,专门用于二进制优化;和 提出了一种组合算法,用于问题的求解【】。虽然算法武汉理工大学硕士学位 论文 最初是用来解决无约束优化问题的,但很快就被推广到了有约束的问题上, 许 多研究人员采用改进后的算法求解有约束的优化问题】。 而在实际应用中,算法也被成功用于神经网络的训练,电气工程中的 优化问题,机械工程和土木工程的建模和优化,数据挖掘,图像处理,控制, 软件测试等诸多领域。 国内方面 对算法的研究相对较少,应用范围较窄,正逐渐形成热点。模型方面 主要有:沈阳自动化研究所的邹文平、朱云龙等人基于 拓扑结构, 提出了 邻域算法【】;太原理工曾建潮等人对侦察蜂的选择策 略进行了改进,提出了新的选择策略,如分裂选择,竞赛选择,排序选择策略 【】; 重庆大学罗钧等将混沌序列引入算法,利用混沌的遍历性使蜂群跳出局部 最优区域【】:河海大学的丁海军等人采用选择策略代替原来的轮盘赌 选择机制,以防止算法过早收敛【】。 应用方面如东南大学吴乐南小组使用混沌算法进行聚类分析;杨进等 在车辆路径问题上的应用、薛晗等在故障的容错中的应用、马良等在等约束 平 面选址中的应用、杨晨光基于方向概率和改进蜂群算法对地面防空武器组网 系 统优化布阵问题的研究、图像边缘检测、问题、机器人路径规划等;也有如 等在混沌及控制领域的应用【】。 . 算法的优化原理 ..算法的数学模型 , 一个基本的算法模型包含三种蜜蜂:被雇佣的蜜蜂 侦察蜂 ,跟随蜂 ;两种基本行为:向食物源招募蜜 蜂和放弃食物源。其中,食物源的位置代表优化问题中的可行解,食物源的蜂 蜜量代表解的适应度。每个食物源上只有一只被雇佣的蜜蜂,也就是说食物 源 的个数等于被雇佣的蜜蜂的个数。被雇佣的蜜蜂和跟随蜂在搜索空间中负责开 发工作,侦察蜂负责探索工作,三者协作以平衡算法的开发和探索机制。 一开始,算法随机生成 被雇佣的蜜蜂或者观察蜂的数目个维 个体食物源的位置五薯,,%,待,最作为初始种群, 。根据给定的适应度函数对这鼠个个体进行评估,记录适应度最大的个 武汉理工大学硕士学位论文 体的目标函数值及其相应的解‰盯。 在每次迭代过程中,蜂群,,执行下列搜索过程:通过比 较当前食物源当前解和周围新的食物源新解的蜂蜜的量适应度,被 雇佣的蜜蜂在记忆中保留较好的食物源位置,也即蜂蜜量较大的食物源的位置。 在所有的被雇佣的蜜蜂完成了此过程之后,它们就和跟随蜂分享食物源的位置 信息解以及蜂蜜量的信息适应度。之后,跟随蜂对被雇佣的蜜蜂所提供 的信息进行评估,以概率从中选出一个食物源,其中 易:粤 ?成 二一.,’’々 对于被选中的食物源,跟随蜂也要在当前食物源和周围新的食物源中择优选取, 选择方法同被雇佣的蜜蜂。 算法通过下式在原来的食物源周围产生新的候选食物源: ~而如‘【而一 其中 ,,鼠 :,/?,是随机选取的指标,办是区问【,】上的随机 数,用于控制。周围食物源的产生,表示蜜蜂通过视觉对两个食物源位置进行 比较。当式中参数%和%的差变小时,%上的摄动也随之变小,因此当 搜索接近最优解时步长就会自动减小了。实际上,此运算要分两方面看待:,,可 能会超出预先设定的边界值,这时就对它取边界值;当最优解是局部最优解而 非全局最优解时,此算法可能不收敛,而在局部最优解所在的区域中迂回。 每个候选食物源被生成后,人工蜜蜂就会对它进行评估。然后采用贪婪选 择机制在原来的食物源和候选的食物源中保留较好的一个。如果新生成的解的 适应度没有当前解的适应度大,也即可行解没有改进,就计数一次。 在算法中,如果一个可行解在预先设定的极限次数用于放弃的限制 值内都没有改进,那么它就被被雇佣的蜜蜂放弃,此被雇佣的蜜蜂转而成为 侦察蜂,被放弃的食物源由侦察蜂所发现的新食物源取代。假设被放弃的食物 源为五,,?,,则侦察蜂按照下式对其进行更新 嘞哆【,】’? 其中,“分别是薯的下界和上界,,】是【,】间的随机数。武汉理工大学硕士 学位论文 ..算法的流程图和伪代码 流程图: 图 算法的流程图 伪代码: 武汉理工大学硕士学位论文 设置参数;在解空间中随机生成 个解向量;初始化标志向量 ,用它来记录被雇佣的蜜蜂在同一蜜源处的次数; 评估解向量并记录适应度最大的解向量‰。。 每个被雇佣的蜜蜂按照公式寻找新的蜜源,计算新蜜源的适应 度,如果新蜜源的适应度优于原蜜源的适应度,则用新蜜源代替原来的蜜源, 并将设为,否则保留原来的蜜源,。 按照公式为跟随蜂计算每个蜜源被选择的概率,根据穰跟随 蜂按照轮盘赌的选择机制选择蜜源。对被选中的蜜源,跟随蜂按照对该蜜 源执行同样的操作。 判断的值是否大于预先设定的极限值,如果 ,则被雇佣的蜜蜂放弃蜜源,转而成为侦察蜂。 更新并记录目前得到的最优解‰时。 判断是否满足终止条件,若满足则输出当前最优解,算法停止;否 则,转到。 .算法的收敛性 链在随机算法收敛、拟概率收敛上有较强的应用性,目前已被成功 用于、、混沌蛙跳算法等的收敛性分析。算法中人工峰的运动 过程本质上是一个随机过程,故可以采用理论对算法进行收敛性 分析。具体做法:首先,建立算法的链模型,证明人工蜂群的状 态序列是有限齐次链;利用随机优化算法的收敛性准则分析算法的收敛 性【】。 .. 算法的链模型 ...基本概念和数学定义 定义 人工蜂状态和人工蜂状态空间 人工蜂状态由人工蜂运动时所在的食物源的位置构成,记作,?,为 可行解空间。 人工蜂的全部可能状态所组成的集合构成乐人工蜂的状态空间,记作武汉理 工大学硕士学位论文 。 定义 人工蜂群状态和人工蜂群状态空间 人工蜂群中全部的人工蜂的状态构成人工蜂群状态,记作五,,,., 其中,疋是第个人工蜂的状态。 人工蜂群的全部的可能的状态组成的集合构成人工蜂群的状态空间,记作 ,,,电墨?,??鼠 定义 状态等价 对于?, ,令妒,?,以为事件彳的示性函数,故伊, 表示人工蜂群状态中包含人工蜂状态的数目。 :?是两个人工蜂群状态, 若对坛?,有缈量,妒:,,则称。,:等价,记作。~:。 定义 状态等价类 通过等价关系“~’’在上诱导的人工蜂群状态等价类称为人工蜂群等价类, 记作/~。 人工蜂群等价类的性质: .同一等价类内任意人工蜂群状态之间是等价的,即,,,?,有墨~。 .内任意蜂群状态与 外的蜂群状态不等价,即,?厶仨,有 。 .对于任意的两个不同的等价类,它们之间是没有交集的。即厶?厶,有 厶厶囝。 ... 算法的模型 定义 状态转移 .人工蜂状态转移 对%,石,?,算法迭代中,人工蜂状态由薯一步转移到,,记作 巧‘誓。 .人工蜂群状态转移 武汉理工大学硕士学位论文 对墨,,?,算法迭代中,人工峰群状态由一步转移到,,记作 五量』。 人工峰群等价类间的转移 厶”:,,,,??,加是由等价关系“~,’在上诱导的两 个等价类,则厶一步转移到,记作互厶。 定理 状态转移概率 .人工蜂状态转移概率 人工蜂的状态由薯 的一步转移的状态转移概率为 :,由被雇佣的蜜蜂实现 ‰乃薯,由跟随蜂实现 五 。薯一,由侦察蜂实现 %互‘×。。薯,由被雇佣的蜜蜂和跟随峰共同实现 其忆酏:南?薯一妒“?”?是 【,其他 被雇佣的蜜蜂由状态薯到一步转移的状态转移概率 薯专,?;置三二苌:;; 触小南薯专妒州?”?且帅?, 【,其他 是跟随蜂由状态到的一步转移的状态转移概率; 。::』瓦三,?【‰,‰“】且状态‘的迭代次数疗是侦察蜂武汉理工大学硕 士学位论文 由状态玉到的一步转移的状态转移概率。 .人工蜂群状态转移概率 人工蜂群状态由墨到,的一步转移概率为 五墨:。:‰:‰。 .人工蜂群等价类问的转移 人工蜂群等价类由塑 的一步转移概率为 互厶::?? 五%:嘞。定理 算法中人工蜂群状态序列:是有限齐次砌链。 .. 算法的收敛性分析 ... 随机优化算法的收敛性准则 考虑问题:,?,其中厂工:”一尺,五,,‘?, ?“为搜索空间。 优化算法的迭代过程: 寻找‖?并令。 在样本空间尺”,,段中生成孝‘。 令“孝‘,选择段,令后,返回。 是“上的分布函数的相应概率测度,以‘? ,工,,‖。,曰是 彳的任意子集。是“专上的一个映射,应满足下面条件: 条件 ,善?厂,且若孝?,则厂,善?厂孝。 上述条件保证了随机优化算法的迭代值的适应度值厂是非递增的。优化 算法的全局收敛是说,该算法能以概率得到单调序列厂?:。.,收敛于厂 在爿上的下确界厂:工?么。但要注意的是厂可能存在一些病态情况, 如厂在彳上的下确界可能刚好在一个不连续的孤立点上取得,这时除非逐个 检验么上的每个点,否则就不可能找到最小值点。为了解决此问题,现在将搜 武汉理工大学硕士学位论文 索厂在彳上的本质下确界口来替代原来的下确界,其中 九? 上式意味着在搜索空间上存在非空子集,其元素的适应度可无限接近口。通 常彳表示彳的测度。 蝴题蝴优区瓤?枢僦高二认。 这儿,。如果随机优化算法找到了.肘的一个点,则认为算法找到 了可接受的全局最优解或近似最优解。 条件 对彳中任意的子集,有?一以曰。 条件说明,对于中任意满足条件的子集,其随机优化算法连 续无穷次搜索不到曰中的点的概率为。 机优化算法的全局收敛性定理:设厂是可测函数,么是”上的可测子 集,算法满足条件、,矗:。是算法生成的序列,则。.。‖?,。 这里??,村是算法在第七步生成的点‘落在足,肼中的概率。 ... 算法的全局收敛性 引理 算法能够满足条件。 证明:由于算法的迭代公式为吩:?:二;三二:嚣,所以算法每 次迭代都选择了群体最优位置,故满足条件。 定义人工蜂群最优状态集 设最优化问题彳,的最优解为,人工蜂群的最优状态集可以定义为 ‘工厂工厂‘,?。 由于时每个可行解都是最优解,这样的讨论没有意义,故以下的讨论武汉理 工大学硕士学位论文 定理 算法中,对于人工蜂群状态序列;,人工蜂群最优 状态集是状态空间上的一个闭集。 定理对于人工蜂群状态空间,使得 囝的非空闭集不存在。 定理】假设链有一非空闭集,且不存在另一个非空闭集使 得 ,则当/?时,溉‘,/‖时,,。./。 定理、、的证明过程见文献,由定理、、可得定理。 定理当蜂群迭代趋于无穷时,蜂群状态列一定会进入最优状态集。 引理 算法能够满足条件。 证明:由定理可知,算法连续无穷次搜索不到全局最优解的概率为,即 ?成立,故算法满足条件。 定理 算法是具有全局收敛性。 证明:由引理、可知,算法本身满足条件、条件,故由随即优 化算法全局收敛性定理可知,算法是一个全局收敛算法。 . 本章小结 本章旨在介绍一种受蜂群觅食过程启发的群智能优化算法??算法。 首先,通过分析自然界中的蜂群觅食模型引出了算法的提出过程;其次,介绍 了算法的发展过程、国内外研究现状,包括算法模型的改进情况以及算法 的应用领域;而后描述了算法优化过程的数学模型,并详细列出了算法的计 算 流程伪代码和流程图;最后给出了随机优化算法的全局收敛性准则,基于该 准则,对理论在算法的全局收敛性方面进行了说明。武汉理工大学硕士学位 论文 第章 带有空间收缩机制的算法 和其他的智能算法类似,算法初期的函数适应度改进较快,但随着迭 代次数的增加,种群的差异程度越来越小,个体集中在峰值附近,收敛速度减 慢,算法容易陷入局部最优。为避免在冗余空间中的过多搜索,提高算法的搜 索效率,同时避免算法陷入局部最优,现提出一种带有空间收缩机制的算 法。该算法建立在不完全演化、空间收缩的基础上,模拟数论序贯优 化的思想,利用算法进行寻优,在保持了种群多样性的前提下,充分利用 了局部最优解。 .不完全演化算法 大部分演化算法在运行的初始阶段时,个体的适应度变化较快,但经过若 干次迭代后,个体开始分布于函数的峰值附近,而后个体的适应度变化减慢, 从而导致算法收敛速度变慢。当种群中的个体分散在各个峰值附近时停止演化, 我们就称此算法为不完全演化算法。由于算法本身在没有找到最优解时便停了 下来,所以该算法可以在较短的时间内获取更多的较优点信息。重复进行此过 程,就可以获得足够多的较优点,从而为解空间的缩小和最优解的定位提供依 据【删。 .空间收缩机制 在解空间中使用上述不完全演化算法,可以快速获得更多的较优点的信息。 收缩空间时,算法采用当前迭代步骤中的精英个体决定下一代的搜索空间:保 留最优个体,其余个体全部灭亡,以此个体为中心,按照一定的收缩半径生成 新