宁夏大学硕士学位论文粒子群优化算法及其应用研究姓名：徐红芳申请学位级别：硕士专业：计算数学指导教师：高岳林2011-03
摘要 粒子群优化算法是近年来提出的一种简单而高效的进化算法，由于其算式简洁，受控参数少，易于编程实现，收敛速度快等优点，一经提出就得到了广泛的研究和应用.其利用群体的优势为寻找复杂问题的解决方案提供了新的思路，所以研究和掌握它的特性与规律，是一个具有理论和应用两个方面重要意义的课题.但是，作为一种比较新的和快速发展的智能算法，其在系统化和应用推广上都还存在一些急待解决的问题.本文详细阐述了粒子群优化算法的基本内容，在分析粒子群优化算法统一框架的基础上，对粒子群优化算法的改进方法做了一些研究工作，并在实验中进行了验证.本文的主要研究内容如下： 1.首先阐述了粒子群优化算法的研究背景及意义，并对粒子群优化算法的研究现状和应用进行了描述，其次对粒子群优化算法的原理进行了详细地阐述，分析了参数设置对算法优化效果的影响，给出了算法流程. 2.提出了一种调整惯性权重的粒子群优化算法.该算法对基本粒子群算法中的速度更新公式进行了改进，给出了粒子群算法中惯性权重的改进策略.通过对六个典型测试函数的实验表明，该算法提高了算法的搜索速度和计算精度，在很大程度上改善了标准粒子群算法的性能. 3.为了增强基本粒子群算法的全局搜索能力，从粒子群算法自身的搜索机理出发，提出一种带飞行时间的粒子群优化算法.该算法速度更新公式不仅考虑了粒子对本身的思考，还考虑了整个种群的平均信息，利用了更多的信息来调整自己的行为，其次采用动态自适应惯性权重使算法可根据粒子的适应度变化动态改变惯性权重，最后引入飞行时间，从而克服了由于传统粒子群算法固定粒子飞行时间而导致的粒子在进化后期搜索性能下降的问题.实验结果表明新算法是一种收敛速度快、求解精度高、鲁棒性较强的全局优化算法. 4.给出了求解混合整数规划问题的粒子群优化算法.该算法对粒子群的速度方程和位置方程进行改进，给出了违反搜索空间的处理策略，利用无约束双目标的方法求出问题的全局最优解，实验结果表明给出的算法是求解混合整数规划问题的有效算法. 关键词：粒子群优化，动态惯性权重，速度更新公式，飞行时间，混合整数规划 I
Abstract Particle swarm optimization (PSO) is effective and simple evolution algorithms proposed recently. It has been widely accepted and successfully applied in many areas, because it has simple expression, easy programing and fast convergence. With the advantages of colony it provides new means for the solution of complex problems. Therefore, how to study and master the characteristics and rule of PSO is a significant issue in both theoretical and applicated areas. However, as a new and developing research filed, PSO still has some problems on its systematization and application extending. The basic contents of PSO algorithms are represented, based on the analysis of algorithm’s framework, several improvement of PSO algorithms are researched. The main contributions of dissertation are as follows: 1. The background and significance of PSO’s research are represented, the research actuality and the application are described too,then the principle of the PSO algorithms are introduced at length, the effect of parameter selection are analyzed. 2. An improved algorithm of PSO with dynamical adjust inertia weight is presented. This algorithm is modified for velocity equation. Aiming to the problems such as the dynamic parameter, local convergence, and the surge phenomenon in anaphase of PSO, a modified strategie for the inertia weight are presented. The experiments on six typical problems show that this improved PSO algorithms can overcome the phenomenon of the premature convergence ，enhance convergence speed and enhance precision, and improve performance of PSO. 3. To improve the global search ability of the standard particle swarm optimization algorithm, considering PSO’s own search mechanism, this algorithm velocity modified equation not only take into account the particles on their own thinking, and also take into account the entire population of the average information , use of more information to adjust their behavior, the inertia weight is determined by the particle's fitness that makes the algorithm become dynamical and adaptive, introduce of flying time, overcome basic particle swarm optimization algorithm fixed particle flying time lead to particle searching ability decline in the later evolutionary. The experimental results show that the new algorithm has fast convergence, high accuracy and more robust, more suitable to solve global optimization problems. 4. An algorithm of PSO is given to solve the mixed-integer programming problem (MIP)，this algorithm gives impoved velocity equation and position equation, handing method of violateing search space, global optimization of PSO is derived through unconstraint bi-objective, Numerical experiments show that the proposed improved algorithm is effective to solve MIP. Key words：particle swarm optimization algorithm, dynamical inertia weight, velocity update equation, flying time, mixed-integer programming II
独 创 性 声 明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果.尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使用过的材料.与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意. 研究生签名： 时间： 年 月 日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文.同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容. (保密的学位论文在解密后应遵守此协议) 研究生签名： 时间： 年 月 日 导师签名： 时间： 年 月 日
宁夏大学硕士学位论文 第一章 绪论 第一章 绪论 课题的研究背景及意义 最优化理论与方法是一门应用性很强的学科，它广泛应用于工业、农业、交通、国防、金融、通讯等许多领域. 解决优化问题的算法通常分为确定性算法和随机性算法两种.确定性算法如：单纯形法、动[1,2]态规划法、牛顿法、共轭梯度法、分枝定界法等，这些确定性算法是按照函数变化机理进行寻优的，其搜索效率较高，但寻优结果与预先给出的初始值有关，以上这些算法通常对目标函数或约束条件有可导要求，在处理人们所面对的大规模、高维、非线性、不可微等特性的复杂且难以求解的问题时，非常容易陷入局部最优位置不能跳出进而不能得到问题的全局最优解.所以当前科研领域工作者研究的目标之一是构造非常有效的全局最优化算法来求解复杂的优化问题. 为了解决现实生活中存在的高维多峰值等特点的难以求解的优化问题，人们通过不断探索，[3]研究发明了许多智能优化算法.例如：以达尔文的进化论作为依据的遗传算法(Genetic Algorithm)，模拟了自然界中生物体的进化过程，通过相互之间优胜劣汰，最后获得全局最好的[4][5]结果；人工免疫系统(Artificial Immune Systems) ，此算法模拟了生物体免疫系统的多样性和认知功能；蚂蚁群优化(Ant Colony Optimization)算法，它是利用自然界中蚂蚁在寻找食物的路途[6]中，通过释放信息素来彼此互相传递信息，以此达到寻找食物的目的；粒子群优化算法(Particle Swarm Optimization)通过鸟群聚集而有效的寻找食物，为此每个粒子之间存有协作和信息的交换[7−9][10,11]；群落选址算法(Colony Location Algorithm)，此算法模拟了自然界植物群落的形成.以上智能算法都可在合理的时间内逼近复杂问题的最优解.这些智能算法的独特优点和机制，引起了国内外许多学者的高度重视并掀起了该领域的研究热潮，且在许多领域中得到了成功应用.在优化领域，由于这些算法构造的直观性与自然机理，因此被称作为智能优化算法. 智能进化算法是求解‘连续优化问题和组合优化问题等的新的最有效途径之一，受到研究者广泛关注，每年举行的各类计算机科学与技术、模式识别与控制、人工智能与信息处理、运筹与管理等方面的国际和国内会议都把智能进化算法作为大会的专题进行交流讨论，尤其值得一提的是粒子群优化算法的研究与应用越来越热，方兴未艾. 粒子群优化算法(Particle Swarm Optimization，简称PSO)是由Kennedy和 Eberhart于1995年提出，它是源于群智能和人类认知的学习过程而发展出的一种智能优化算法，该算法起源于对鸟[12,13]群寻找食物过程中的迁徙和群体聚集的模拟而产生的.它成功应用于求解函数的全局优化问题，后来又进行了有效的拓展.粒子群优化算法原理简单，易于编程实现，仅有少量的控制参数需要调整，且不需要待求解函数的梯度信息等，因而一经提出就成为智能优化领域的研究热点之一.短短十几年时间，粒子群优化算法就已经被广泛应用于许多领域，如函数全局优化、神经网络训练、模糊控制系统、电力系统优化等.总的来说，粒子群优化算法和其它进化算法一样，可[14]以解决几乎所有的复杂优化问题，其中最具有应用前景的领域包括复杂的全局优化，混合整[15][16][17]数规划问题、多目标优化问题、系统分析与设计、神经网络训练、模式识别、信号处理、[18]生物系统建模、决策和模拟、支持向量机等.目前，粒子群优化算法在模糊控制器的设计、车 1
宁夏大学硕士学位论文 第一章 绪论 间任务调度、实时机器人路径规划、图像分割、EEG信号模拟、语音识别、烧伤诊断以及探测移动目标等方面已经得到成功的应用，粒子群优化算法具有很多优点，主要体现在对整个种群进行群体搜索，能记忆个体最优解，算法的原理简单，易于理解编程实现，协同搜索，通过群体的全局最优信息和个体局部信息共同完成，易于与其它算法相互混合，能构造出具有更好优化性能的新算法，相对于蚂蚁群算法等其它智能优化算法，此算法能够较快收敛到全局最优位置. 课题的国内外研究现状 粒子群优化算法(简称PSO)是1995 年提出的，由于其原理简单易懂，以及前面给出的许多优点，因此使得很多研究学者对这种算法产生浓厚的兴趣且对这种算法进行研究，目前针对粒子群优化算法的研究已经取得了很大的进展，包括应用研究和理论研究，这些进展主要体现在以下几方面： (1) 针对粒子群优化算法容易陷入早熟收敛和为了提高粒子的收敛速度而进行的研究.文献[21]提出了一种简化的自适应粒子群优化算法，针对带有收缩因子的粒子群优化算法(CFPSO)容易陷入局部最优位置、进化后期的收敛速度慢和求解精度低等缺点，文中采用了自适应简化粒子群优化(AsCFPSO)方程与混沌搜索技术相结合的方法，提出了基于混沌搜索的自适应简化粒子群优化(CAsCFPSO)算法；文献[22]中美国的Shi和Eberhart研究发现，PSO算法中等式的第一部分为速度因子，由于此种算法具有随机性和扩大搜索空间的优点，因此研究学者们为了控制粒子以前飞行速度对当前飞行速度的影响，引入了惯性权重，它的作用是平衡算法的全局寻优能力和局部寻优能力，即平衡算法的收敛速度和收敛精度，表现为惯性权重的取值越大，则粒子群算法的全局寻优能力就越强，反之，惯性权重的取值越小，则粒子群算法的局部寻优能力就越强. 为了能找到更好的惯性权重的选取方法，使得粒子在局部和全局之间更好的搜索，许多研究学者进行了大量的研究，提出了惯性权重的不同选取策略：文献[24]提出了一种动态改变惯性权重的方法，文献[25]给出了一种非线性改变惯性权重的方法，文献[26]提出了一种基于混沌的动态改变惯性权重的方法，文献[27]根据粒子适应度值改变惯性权重的选取方法，以上提到的改变惯性权重的方法提高了粒子群优化算法的全局寻优能力. PSO作为一种新的随机优化算法，它的缺点也表现在容易陷入早熟收敛和全局收敛速度慢这两个方面，为了避免粒子群算法过早陷入早熟收敛的缺点，许多研究学者通过控制种群的多样性来提高算法性能，文献[28]针对基本PSO 算法存在易陷入局部最优位置的缺点，提出了一种新型的PSO 算法——混合变异粒子群优化算法.在每次迭代过程中，对满足变异条件的粒子，以多种变异函数方式进行变异，而这些变异函数分别被给予了一定概率，概率的划分取决于特定的优化问题.文献[29]针对粒子群优化算法容易早熟、收敛精度低等缺点，通过采用全变异策略、最大搜索速度自适应调整等策略给出了一种全变异粒子群优化算法.文献[30]提出了一种基于群能量恒定的粒子群优化算法，该算法根据粒子内能进行动态分群，对于具有比较好的适应度值的小群体采取引入最差粒子的速度公式更新方法，对于具有比较差的适应度值的小群体采取带有惩罚机制的速度公式更新方法，用其分担由于较优群体速度降低而产生的整群能量的损失，从而有效地克服了PSO 算法的早熟. (2) 为增强PSO全局搜索能力而进行的研究.文献[31]针对粒子群优化算法容易陷入局部最优解的问题，采用了协同处理的粒子群优化算法: 对于种群中适应度值差于平均适应度值的粒子， 2
宁夏大学硕士学位论文 第一章 绪论 采用动态Zaslavsk ii混沌映射公式调整粒子的惯性权重；对于种群中适应度值优于或等于平均适[32][33]应度值的粒子，采用动态非线性函数公式调整粒子的惯性权重. Higashi、NingLi、吕振肃[34]等人分别提出了自己的变异粒子群优化算法，其基本思路都是想通过引入变异算子以此来跳出局部最优值的吸引，提高算法的全局寻优能力，从而得到精度较高的计算结果. (3) 与其它算法的结合. Das等人将差分进化(DE)引入粒子群算法速度更新公式中从而提出了PSO-DE算法．高鹰等提出的基于模拟退火算法(SA)的粒子群优化算法是以基本粒子群算法的具体流程作为主要运算流程，把模拟退火机制引入粒子群算法，与粒子群算法的求解速度快、易于编程实现等优点与具有非常好的跳出局部最优解能力的模拟退火算法相结合，避免了粒子群优化算法容易陷入局部最优值点的缺陷，从而加快了粒子群算法在进化后期的收敛速度． 尽管对粒子群算法的研究已经取得了很大的进展，但对算法本身的工作原理、算法内部机理还没有真正建立，算法中参数的取值还不够恰当， PSO的研究热点主要体现在以下几方面： (1) 与其它智能优化算法的融合.将PSO和其它优化算法进行融合，主要考虑如何将粒子群算法的优点和其它智能优化算法的优点相结合，取长补短，构造出有实用价值的混合算法. (2) 将各种先进理论引入到PSO算法中.各种先进理论的引入，首先可以研究性能良好的新型粒子群拓扑结构.其次可以优化PSO的参数及其选择，使得粒子群优化算法既能避免早熟收敛又能比较快速地收敛到全局最优解，对工程实践有着重要意义. (3) 算法内部机理的数学基础研究.PSO算法在实际应用中被证明是有效的，但目前还没有给出收敛性、收敛速度估计等方面的数学证明，已有的工作还远远不够. 粒子群优化算法的应用 粒子群优化算法已得到广泛应用，在国内外的一些刊物上，已经出现了用粒子群优化算法解决整数规划、多目标优化、非线性规划、TSP问题等优化问题的文章.此外粒子群优化算法在神经网络训练、系统辨识等方面，也有着广泛的应用.本节简要介绍一些例子： (1) 组合优化 尽管有离散二进制版 PSO，但其并不能完全适用于各种不同类型的组合优化问题，因为离散二进制版 PSO中存在着很多问题，如约束条件怎样处理等.根据待求解问题的性质不同，有些研究学者通过自己重新定义算法迭代公式中的位置和速度更新公式来解决问题.目前，已经提出了很多求解整数规划、VRP、TSP等问题的新方法. (2) 神经网络的训练 PSO用于神经网络的训练中，主要包含三个方面：连接权重、学习算法和网络结构(网络拓扑结构以及传递函数).用PSO优化算法训练神经网络，一个粒子包含神经网络的所有受控参数，通过迭代来优化这些受控参数，从而达到训练的目的.与BP算法相比，使用粒子群优化训练神经网络的优点在于不利用待求解函数的梯度信息，可使用一些不可微的转换函数.大部分情况下粒子群优化训练神经网络训练结果优于 BP 算法，而且有非常快的训练速度. (3) 连续问题参数优化 作为一个优化方法，粒子群算法已广泛应用于许多连续问题的参数优化.例如，机器人路径规划、PID控制器参数优化、信号处理、模糊控制器的设计、VLSI 布图布线和电路优化设计、 3
宁夏大学硕士学位论文 第一章 绪论 约束布局优化、无功功率优化、数控加工参数优化等，并在以上问题中均取得了很好的效果. (4) 其他应用 除了以上领域外，PSO 在多目标优化、动态目标检测、数据挖掘、生物信号检测识别、聚类分析、游戏学习训练、系统辨识以及无人驾驶车辆的导航等方面也取得了显著的成果. 本文的结构与主要内容 本文研究内容分布于以下各章节中： 第一章，绪论：介绍了本文的研究背景、意义、PSO算法的国内外研究进展以及其应用. 第二章，粒子群优化算法概述：介绍了粒子群优化算法的基本原理、算法流程、参数设置对算法的影响，对基本粒子群优化算法的关键控制参数进行了分析，讨论了粒子群算法的改进策略，比较了粒子群优化算法与遗传算法等其它进化算法的异同. 第三章，动态调整惯性权重的粒子群优化算法：本章首先对标准粒子群优化算法中的速度更新公式进行了改进，从粒子群算法自身的搜索机理出发，目的是增强基本粒子群算法的全局搜索能力.给出了一种新的粒子群优化模型，其次对原有算法中的固定惯性权重进行改进，实验结果表明新算法具有更快的搜索速度和更高的计算精度. 第四章，带飞行时间的粒子群优化算法：该算法中的速度更新公式不仅考虑了粒子对本身的思考，还考虑了整个种群的平均信息，利用了更多的信息来调整自己的行为，同时使用了动态自适应惯性权重，该算法根据粒子群中各个粒子适应度值的变化动态调整惯性权重的取值，最后引入粒子的飞行时间，克服了由于基本粒子群算法固定粒子飞行时间从而导致的粒子在进化后期搜索性能下降的问题.通过一系列的数值实验表明新提出的带飞行时间的粒子群优化算法是一种收敛速度快、求解精度高、鲁棒性较强的全局优化算法. 第五章，给出了求解混合整数规划问题的粒子群优化算法：该算法对粒子群的速度方程和位置方程进行改进，给出了违反搜索空间的处理策略，利用无约束双目标的方法求出粒子群的全局最优解，实验结果表明给出的算法是求解混合整数规划问题的有效算法. 第六章，对所作课题进行了总结，同时给出了粒子群优化算法目前存在的问题与未来可能的研究方向. 4
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 第二章 粒子群优化算法概述 引言 粒子群优化算法具有收敛速度快、鲁棒性好等特点，能以较大概率找到问题的全局最优解，且计算效率比传统的计算方法高.该算法最大的优势在于概念简单易实现，且有着深刻的智能背景，目前已经在函数优化、模式识别、神经网络设计、分类、机器人技术、信号处理等应用领域取得了成功的应用.所以该算法自提出以来，引起了国际上相关领域众多学者的关注和研究. 本章首先对粒子群优化算法的基本原理和流程进行了介绍，然后对基本粒子群优化算法的关键控制参数进行了分析，讨论了以下几个方面的改进策略：调整惯性权重、引入收缩因子、融入选择策略、融入杂交策略等. 基本粒子群优化算法描述 算法原理 粒子群优化算法(PSO)是一种群体优化算法，它是受鸟群群体运动行为方式启发而提出的一种具有代表性的群体智能的方法.研究人员发现鸟群在觅食飞行过程中会改变方向、聚集、散开，其飞行行为通常表现为不可预测，然而其整体运动却能保持一致性，个体与个体之间的飞行也保持着最佳的距离.通过对类似生物群体的行为研究，发现生物群体中存在着一种社会信息共享机制，它为群体的进化提供了一种优势，这也是粒子群优化算法形成的基础. 该算法可描述为:假设在一个D维寻优空间中，粒子群由N个粒子组成，该粒子群可用下面的参数来表示: x=(x,x,L,x)表示种群中第i个粒子的位置；v=(v,v,L,v)表示种ii1i2iDii1i2iD群中第i个粒子的速度； p=(p,p,L,p)表示种群中第i个粒子迄今为止寻找到的最优位ii1i2iD置，也就是个体最优位置p；p=(p,p,L,p)表示整个粒子群迄今为止寻找到的全局最igg1g2gD优位置，也就是全局最优位置p. 那么每个粒子飞行的速度和位置的迭代公式如下: gv(t+1)=wv(t)+cr(p(t)−x(t))+cr(p(t)−x(t)), () idid11idid22gdidx t+=xt+vt+ () (1)()(1),ididid其中，1≤d≤D，1≤i≤N，w为惯性权重；c和c为学习因子，通常取(0,2]之间的常数， 12r、r为分布于(0,1)之间的随机数；公式由三部分组成，第一部分是(记忆项)粒子先前的速度，12说明了(上次速度的大小和方向)影响粒子目前的状态；第二部分是粒子的自我认知部分，是从当前位置指向该粒子自身最优位置的一个矢量，表示此粒子的飞行来源于自身经验，粒子通过对自身位置的思考来决定自己下一步的飞行速度和位置，这样可以使种群中的每个粒子有更好的全局寻优能力，避免陷入局部极小值；第三部分为(群体认知项)社会认知部分，是一个从当前位置指向种群最优位置的一个矢量，反映了种群中粒子间的相互合作和信息的共享，以上三部分共同决定了粒子的空间寻优能力.第一部分的作用是平衡全局寻优和局部寻优的能力，第二部分使粒子 5
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 有了很强的全局搜索能力，避免过早陷入局部极值点，第三部分体现了粒子之间的信息共享，在这三部分的共同作用下粒子才能有效的到达最好位置. 参数设置 粒子群算法中控制参数包括：最大速度V、加速常数c、c、惯性权重w. max12 (1) 最大速度v max一般来说，v的选择不应该超过粒子的搜索范围，如果v太大，粒子可能飞过最优解的maxmax位置；如果太小，粒子不能在局部好区间之外进行足够的探索，可能降低粒子的全局搜索能力. 数值实验结果表明，通常设v为每维变化范围的10%~20%. max (2) 学习因子 加速系数c,c代表将种群中每个粒子飞向个体最优位置p和全局最优位置p的加速权重. 12ig低的c、c值允许粒子在被拉回之前可以在目标区域外徘徊，而高的值则导致粒子突然地冲向或12越过目标域. (3) 惯性权重 惯性权重w是用来控制种群中粒子以前飞行速度对当前飞行速度的影响，粒子的局部搜索能力和全局搜索能力与惯性权重的选取有很大关系，其表现为惯性权重的取值越大，则有利于算法的全局搜索，惯性权重的取值越小，则对算法的局部搜索有力，合适的惯性权重值可以提高算法的求解效率.大量数值实验研究发现惯性权重的取值范围在[,]之间会有更好的求解结果，而且用线性递减的方法比用固定的惯性权重值的求得的结果要好，其原因是惯性权重的取值越小则有利于局部搜索，惯性权重的取值越大则有利于全局搜索.另外，文献[36]研究了惯性权重的取值和速度上限对粒子群优化算法性能的影响，得出的结论是惯性权重的取值接近1得到较好结果的前提条件是V比较小，通常来说，从线性递减到的惯性权重w的取值策略能得到max相对其它取值比较好的结果. 在整个求解过程中，最大速度v、学习因子c、c以及惯性权重w共同维持粒子对局部搜max12索和全局搜索性能的平衡. 算法流程 每个粒子的优劣程度根据已定义好的适应度函数来评价，这与被求解的问题有关，设待求解的优化问题为极小化问题，下面为PSO算法的算法流程： Step 1 初始化粒子群，包括群体规模N，搜索空间的维数D，每个粒子的位置和速度； xvididStep 2 ①计算种群中每个粒子的适应度值f(x(t)； id②求出到目前为止每个粒子i所找到的最优位置p； i③求出到目前为止当前种群所找到的全局最优位置p； gStep 3 根据公式()、()更新粒子的速度和位置； 由此形成第t+1代粒子群： x(t+1)=(x(t+1),x(t+1),L,x(t+1)； 12N 6
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 Step 4 对粒子群中的各个粒子，用它的当前适应度值和它本身的个体最优适应度值进行比较，如果当前适应度值较好，则用该粒子替换个体极值p； iStep 5 对粒子群中的各个粒子，用它的当前适应度值和全局最优适应度值比较，如果当前适应度值较好，则替换全局极值p； gStep 6 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则回到Step 2. 图2-1给出了PSO算法的具体流程： 开始 在整个搜索空间随机初始化粒子的速度和初始位置 计算每个粒子的适应度 更新粒子的p,p ig 根据公式()和()更新每个粒子的速度和位置 判断是否满足终止条件： 达到最大迭代次数或误差在 允许范围内否 是 结束 图2-1基本粒子群优化算法流程图 粒子群优化算法的改进策略 基本粒子群优化算法在解决复杂优化问题时遇到了很多困难，甚至有些优化问题用基本粒子群算法无法解决或效率非常低下，所以对基本粒子群算法的改进就显得尤为重要.粒子群优化算法的改进可谓层出不穷，这方面的研究非常庞杂，这些改进基于各种不同的选取策略和方法.这些不同的方法和策略，目的都是为了改善基本粒子群优化算法存在的缺点，这个缺点是PSO容易过早出现早熟收敛，陷入到局部最优值点中，最终使全局最优解不能求出，出现这种现象有以下 7
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 两个方面的原因，一是受到待求解的优化函数性质的影响，现实生活中有许多测试函数是高维、不可导、有多个极值点、形状非常复杂，然而粒子群优化算法不是从理论上证明此算法能收敛到所有类型函数的全局最优位置，所以针对高维、不可导、有多个极值点等特性的测试函数，不一定都能求得理论最优值；二是粒子群优化算法在运行过程中，由于算法中各个参数选取的不恰当等原因，造成算法在运行的过程中，粒子群中粒子的多样性减少，导致粒子群算法出现“早熟”现象，从而导致该粒子群算法不能收敛到全局最优位置，因此也就不能求出问题的全局最优解.以上这两个影响算法求解结果的原因通常密不可分的联系在一起，使人们很难说出究竟是二者之中哪一个因素在起作用，致使该算法不能收敛到理论的全局最优位置.针对第一个方面的缺点，许多学者试图在函数寻优的过程中，动态的改变函数的某些全局或局部的形态，使待求解的函数的图像逐渐变得简单从而有易于求解，同时又不改变待求解函数全局最优位置的性质.例如设计一个变换方法，随着函数优化过程的进行，使得待求解的函数由多峰函数变为单峰，从而克服以上缺点；针对第二个方面的问题一般可以采用如下方法来解决，通过对种群中粒子的多样性设置某些指标，例如粒子群的熵，随着进化过程的进行，如果这些指标大于某个预先给定的阈值，则对整个种群中的满足这个条件的某些粒子实施某种操作，比如按照给出的概率进行变异，从而改善整个种群的多样性，克服早熟现象.本节重点讨论以下几个方面粒子群优化算法的改进策略：调整惯性权重、引入收缩因子、融入选择策略等. 调整惯性权重 惯性权重w是用来控制粒子以前飞行速度对当前速度的影响，惯性权重可以平衡粒子群算法的局部搜索与全局搜索能力，惯性权重与模拟退火算法中的退火温度相似，惯性权重的取值越大，则粒子群算法的全局搜索能力就越强，从而算法的局部搜索能力就相对减弱，反之，惯性权重的取值越小，则粒子群算法的局部搜索能力就越强，而全局搜索能力就相对减弱.由于不同问题所具有的性质不同，致使对算法的全局搜索能力或局部搜索能力会有不同要求，因此调整惯性权重的大小可以使算法在全局寻优和局部寻优之间得到平衡，也就是说根据函数性质的不同进行自动调整惯性权重.文献[38]提出了一种自适应调整的线性递减权重选取策略，在进化过程中随迭代次数的增加，线性减少惯性权重的取值，用公式表示为： T−tmaxw(t)=(w−w)()+w () startendendTmax其中，T表示最大迭代次数，w表示进化初期的惯性权重，w表示进化到最大迭代次数maxstartend时的惯性权重，一般取w=，w=.这样设置惯性权重的值的好处是使得算法在迭代startend初期粒子的探索能力比较强，能不断搜索新的区域，之后粒子的开发能力逐渐增强，以使算法在可能是最优位置的周围进行更细致的寻优，但是寻优过程是一个非常复杂的非线性过程，采用惯性权重的取值线性递减的方法并不能正确地反映出粒子真实的寻优过程.因此，有的研究者提出了一种借助粒子适应度值来动态调整惯性权重的方法，通过求解的粒子适应度值确定惯性权重w的取值.数值实验结果表明，与线性减小惯性权重的粒子群优化算法相比，动态改变惯性权重的方法能求得更好的优化结果. 8
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 引入收缩因子 [39]收缩因子的概念是Clerc提出的，在种群的进化过程中每个粒子的速度更新公式为： v(t+1)=χ[v(t)+cr(p−x(t)+cr(p−x(t)] () idid11idid22gid其中，收缩因子 2 χ=，ϕ=c+c，ϕ>4 1222−ϕ−ϕ−4ϕ数值实验结果表明，使用了收缩因子的改进粒子群优化算法与使用惯性权重的粒子群优化算法相比，其优点在于前者有着更快的收敛速度.如果我们恰当地选取收缩因子的取值，那么带有收缩因子的改进粒子群优化算法可以被看作是基本粒子群优化算法的一个特例. 融入选择策略 PSO算法的寻优过程在很大程度上是与粒子群中当前个体最优位置p和全局最优位置p有ig关，它的寻优范围受个体最优位置p和全局最优位置p的限制.在智能优化算法中，此处的选择ig策略是用来选择比较优的寻优区域和淘汰比较差的寻优区域，以便更好地分配有限的资源.但是在基本的粒子群优化算法中，种群中每个粒子的最优值点的确定相当于隐含了选择机制，文献[40]给出的带有选择机制的新粒子群优化算法，数值实验结果表明新算法对一些测试函数能收敛到全局最优解.改进的新算法将种群中每个粒子当前位置的适应度值与种群中其它粒子的适应度值进行比较，记下适应度值最差的一个粒子.整个种群再依据这个记录排序，得分最高的粒子排在整个种群的前边，该新算法的具体流程如下： (1) 在种群中随机选择一个粒子，将该粒子的适应度值与种群中的其它粒子的适应度值分别进行比较，如果每次比较完之后该粒子的适应度值好于某个粒子的适应度值，就让该粒子得一分，对种群中的每一个粒子重复以上这一过程； (2) 根据上一步计算得出的每个粒子的分数大小对粒子群中的所有粒子由大到小排序； (3) 选择排在种群中前边的一半粒子，对这些粒子进行复制，取代种群中排在后边的一半粒子. 对给出的测试函数的数值实验结果表明，以上给出的新算法的优化性能好于基本粒子群优化算法的优化性能. 融入杂交策略 融入杂交策略的粒子群优化算法是Angeline提出的，种群中的每个粒子被预先给定一个比较小的杂交概率，通常情况下杂交概率是随机给出的.在算法的每次迭代过程中，依据杂交概率选择出指定数目的粒子放入一个储存池中，这些粒子随机地两两杂交，生成相同数目的下一代粒 9
宁夏大学硕士学位论文 第二章 粒子群优化算法概述 子，并用生成的下一代粒子替换上一代的粒子，以使种群中粒子的数目保持不变.通过以上的杂交操作，由上一代个粒子随机产生了两个新的位置，而粒子的数目没有改变.数值实验的测试结果表明，杂交操作的引入使具有单峰值的函数的收敛效率降低了，所以引入杂交操作的改进粒子群优化算法的收敛效率比基本的粒子群优化算法的更低，然而这种算法在求解具有多峰特征的函数时的收敛效率则更高，因此应用了杂交操作的粒子群优化算法比较适合求解具有多峰特征的函数.数值实验结果表明，引入进化计算改进的新粒子群优化算法的收敛速度相对于一些其它算法比较快，具有较高的求解精度，对一类非线性优化测试函数能够求得满意的结果. 与其它理论的结合 [41]Van den Bergh等人提出的协同粒子群优化算法，采用粒子局部学习的策略，因此与基本粒子群算法相比更容易避免过早出现早熟收敛，且能得到计算精度更好的求解结果. 孙俊等人从量子力学的视角提出了量子粒子群优化算法(QPSO) .QPSO算法具有控制参数少的优点，而且在寻优能力上好于基本粒子群优化算法.孔丽丹等人在量子粒子群优化算法的基础上给出了一种基于全局层次的自适应粒子群优化算法(AQPSO) .该算法使用了粒子群算法的迭代[42]公式，同时参考了ARPSO算法的基本思想，为种群定义了吸引和扩散状态. [43]高鹰等提出了混沌粒子群优化算法，实验结果表明该算法避免了粒子群优化算法容易陷入局部最优位置、算法迭代后期收敛速度慢、求解精度低等缺点. 本章小结 粒子群优化算法是近年来提出的一种简单而高效的进化算法，因为它易于理解和编程实现，以及受控参数少等优点，一经提出就得到了广泛的研究和应用.本章首先对粒子群优化算法的基本原理进行了介绍，然后对基本粒子群优化算法的关键控制参数进行了分析，给出了算法的设计步骤、算法的基本流程，其次由于粒子群优化算法与蚂蚁群算法一样存在控制参数选取困难、易陷入局部最优位置等不足之处，为解决这些缺点研究学者对粒子群算法进行了各种改进，重点给出了粒子群优化算法几个方面的改进策略：调整惯性权重、引入收缩因子、融入选择策略、融入杂交策略等. 10
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 第三章 动态调整惯性权重的粒子群优化算法 引言 由第二章可知粒子群优化算法是一种有效的寻找函数最优解的演化计算方法，它简便易行，收敛速度快.但算法也存在控制参数选取困难、易过早陷入局部最优位置等缺点，针对这些缺点，本章对基本PSO算法中粒子的迭代速度公式进行了改进，考虑了种群中更多粒子对整个种群寻优能力的影响.针对基本粒子群算法容易陷入局部最优位置的情况，本文采用动态非线性方程调整惯性权重和动态Tent混沌映射调整惯性权重，使算法避免陷入局部最优位置，加快向全局最优位置收敛，动态寻找全局最优值，提出了动态调整惯性权重的粒子群优化算法.通过对六个典型测试函数的实验，表明该方法具有较强的全局寻优能力，进一步提高了算法的求解精度. 改进的粒子群优化算法 速度方程的改进 基本的PSO算法的速度更新公式中只考虑了种群中的个体最优位置和全局最优位置，本文为了更多地考虑群体中其它粒子的位置对算法寻优性能的影响，提高PSO的全局搜索能力，将速度[44]公式() 更新为： v(t+1)=wv(t)+cr[ϕ(λp(t)+λp(t)+λx(t)−x(t)] () idid1id2gd3jdid x(t+1)=x(t)+v(t+1) () ididid1其中，λ,λ,λ∈[0,1]且λ+λ+λ=1，本文取λ=λ=λ=，即取p(t)，p(t)，x(t)123123123idgdjd3的重心位置；c为非负常数，本文取c=，r是[0,1]之间的随机数；ϕ为控制因子，这里取ϕ=，x(t)为随机产生的第j个粒子在第t代的第d维坐标（i≠j). jd由于速度公式()中的x(t)为除了第i个粒子外在群体中随机产生的一个粒子，因此，公jd式()更多地考虑了群体中其他粒子的位置对算法搜索性能的影响，从而能够进一步增强PSO算法的全局寻优能力. 动态惯性权重调整机制 为了保障算法收敛，逐步寻找全局最优位置，本文提出了两种动态调整惯性权重的方法： [45]第一种方法为：基于动态非线性方程调整惯性权重，其公式如下： u=u−(u−u)(t/T) () maxmaxminmaxuw=w−w−wtT () maxmaxminmax其中，u表示惯性权重w的调节因子，u表示调节因子的最小值，u表示调节因子的最minmax 11
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 大值；t表示当前迭代次数，T为最大迭代次数；w为惯性权重w的最小值，和w为惯性maxminmax权重w的最大值. 当调节因子u的取值是动态线性变化而不是通常给定的固定数值时，公式() 给出的惯性权重w的值是动态非线性递减的，且差异非常大.动态非线性形式的惯性权重，比一般固定形式的惯性权重w更容易避免陷入局部极值的缺陷，能够更好的维持全局搜索和局部搜索之间的平衡，能逐渐收敛到全局最优位置. 第二种方法为：动态Tent混沌映射调整惯性权重 混沌是自然界存在的一种非线性现象，是一种表面看去随机而实则非随机的运动.混沌不是简单无序的现象，其实是它不具有明显的周期性和对称性，是存在于非线性系统中的一种新的形式.目前对混沌尚无严格的定义，一般将由确定性方程得到的具有随机性的运动状态称为混沌.研[46]究发现Tent映射比常用的Logistic映射具有更好的遍历均匀性，表达式为： 1⎧2Y,0≤Y≤kk⎪⎪2Y= () ⎨k+11⎪2(1−Y),<Y≤1kk⎪⎩2Tent映射变量的变化区间为[0,1].混沌系统虽然貌似随机，但它毕竟是由确定方程导出的，因此具有特殊的运动规律，混沌运动的特征主要有： (1)稳定性（非周期性） 针对某些参数的取值，在大多数的初始条件下，混沌都将产生非周期性的运动过程，即混沌运动的轨迹具有不稳定性. (2)遍历性 混沌运动是一种自始至终局限于在有限区域且轨迹永不重复的运动.因此，随着运动时间的加长，混沌运动的轨迹肯定不停留在其中任何一种状态而是遍历搜索区间的每一点. (3)随机性 它始终局限在有限区域且轨迹永不重复. (4)对初值的敏感性 混沌现象随着时间的加长，任意邻近的各个初始条件将表现出不同的时间进化，也就是说具有对初始值的敏感性. (5)长期不可预测 由于混沌运动的初值限于某个精度，尽管对于初值的细小的差别也有可能对以后的时间进化产生非常大的影响，故而混沌系统的长期演化轨迹是不可预测的. 为了迫使具有适应度值较差的粒子跳出局部最优位置，我们引入了调节因子k来动态调整惯性权重的取值，调节因子k随着迭代次数的增大而动态减小，即线性递减，相应惯性权重w的值动态减小.动态Tent混沌映射数学表达式如下： k=k−(k−k)(t/T) () maxmaxminmaxw=k+(1−k)∗Y () k+1其中，k为惯性权重的调节因子k的最大值，k为惯性权重的调节因子k的最小值，t为当maxmin 12
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 前迭代次数，T为最大迭代次数. 惯性权重调整算法 对种群中具有不同适应度值的粒子，采用不同的惯性权重调整方法处理： if f≤f iavg根据公式()、()、()、()更新粒子的速度和位置， elseif f>f iavg根据公式()、()、()、()更新粒子的速度和位置. 其中，f表示每一代中第i个粒子的适应度值，f表示每次迭代过程中所有粒子的平均适应度iavg值，以最小化问题为例，全局最小值表示最优状态. 在算法每一次的运行过程中，从迭代初期每个粒子的适应度值比整个种群的平均适应度值差（即比平均值大），到后来每个粒子的适应度值优于整个种群的平均适应度值，或着粒子始终都在好的搜索区域进行搜索的情况时，为了避免种群中的粒子从当前较好的搜索区域进入不好的搜索区域，我们采用上文给出的动态非线性公式，通过调节因子u来改变每个粒子的惯性权重的取值，以此来保持种群中的粒子向全局最优位置处收敛.当种群中的粒子寻优速度较慢，在算法运行过程中从迭代初期每个粒子的适应度值比整个种群的平均适应度值好，到后来每个粒子的适应度值差于整个种群的平均适应度值，或着粒子始终都在较差搜索区域进行搜索的情况时，为了使种群中的粒子加快跳出局部最优位置，我们采用本文给出的Tent混沌映射来调整惯性权重的方法，在调节因子k的作用下，调整惯性权重的取值，以此避免粒子陷入早熟，加快寻找全局最优位置. 新算法的具体步骤 下面给出本文提出的改进粒子群优化算法的步骤： Step 1 设置初始化的参数：当前迭代次数t=1，种群的规模N，搜索空间的维数D，种群中粒子的位置和速度； Step 2 分别计算出粒子群中每个粒子的适应度值f和整个种群的平均适应度值f； iavgStep 3 分别计算出种群中每个粒子的个体极值p和全局最优位置p； igStep 4 对种群中各个粒子执行如下操作： if f≤f iavg根据公式()、()、()、()更新每个粒子的当前速度和位置， elseif f>f iavg根据公式()、()、()、()更新每个粒子的当前速度和位置. Step 5 计算新种群中每个粒子的适应度值，把种群中每个粒子的当前适应度值与它本身的最优适应度值进行比较，如果此粒子的当前适应度值优于它本身的最优适应度值，则令粒子的当前位置取代此粒子的个体极值p；再把种群中每个粒子的当前适应度值与种群的全i局最优适应度值进行比较，如果此粒子的适应度值优于全局最优适应度值，则令粒子的 13
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 当前位置取代整个种群的全局最优位置p； gStep 6 判断粒子适应度值是否满足停止条件(误差足够好或达到最大循环次数)，是则退出；否则，返回Step 3； Step 7 输出全局最优位置P和它的适应度值. 数值实验与分析 算法性能的比较通常是基于一些称为Benchmark的典型问题展开的.我们利用表3-1中的六个常用Benchmark函数求解最小值进行了测试，为了验证新算法的性能，这里选择2种有代表性的算法进行比较，将一种改变速度更新公式的粒子群优化算法简记NPSO，采用Logistic混沌映射调整惯性权重的粒子群算法简记为BLPSO与本文提出的新算法简记为BTPSO进行对比，这里的参数取值如下：种群规模N=20，动态非线性因子u=，u=；惯性权重maxminw=，w=；动态Tent混沌映射因子k=，k=，c=c=，维数maxminmaxmin12如表所示；经大量实验得出对于经典测试函数来说， NPSO中的c=. 每种算法独立运行100次，记录平均最优适应度值、最小适应度值和标准差，所得结果如表3-2~3-7所示： 表3-1 六个测试函数 函数 名称 特征 维数 范围 理论最优值Schwefel- DD f(x)=x+xx≤10Problem- 多峰30 0 1∑i∏iii=1i= 222sinx+x− x≤1Schafferf6 多峰 2 0 f(x)=+(1+×(x+x))12302 x≤100f(x)=xSphere 单峰30 0 i3∑ii=1D2f()=−20exp[− i=x≤32 Ackley 多峰30 0 iD−exp(cos(2∏x)/D)+20e∑ii=1D1Dx2i f(x)=x−cos()+1x≤600 Griewank ∑∏多峰30 0 i5ii=14000ii=1D2 x≤ f(x)=[x−10cos(2πx)+10]Rastrigrin 多峰 30 0 i6∑iii=1 14
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 表3-2 Branin函数实验结果对 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -008 80 最小最优值 -008 标准差 -008 平均最优值 -004 -010 100 最小最优值 -004 -011 标准差 -004 -010 f 1平均最优值 -004 -012 120 最小最优值 -005 -013 标准差 -005 -012 平均最优值 -005 -014 140 最小最优值 -006 -015 标准差 -006 -014 表3-3 Schafferf6函数实验结果对比 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -009 -016 50 最小最优值 -012 -014 0 标准差 -009 -015 平均最优值 -010 -018 60 最小最优值 -013 0 标准差 -010 -017 f 2平均最优值 -011 0 70 最小最优值 -01400标准差 -011 0 平均最优值 -014 0 90 最小最优值 -01700标准差 -014 0 15
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 表3-4 Sphere函数实验结果对比 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -010 60 最小最优值 -011标准差 -010 平均最优值 -01270 最小最优值 -004 -013 标准差 -012f 3平均最优值 -004 -014 80 最小最优值 -005 -015 标准差 -004 -014 平均最优值 -006 -018 100 最小最优值 -006 -019 标准差 -006 -018 表3-5 Ackley函数实验结果对比 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -005 50 最小最优值 -005标准差 -005 平均最优值 -00660 最小最优值 -006 标准差 -006f 4平均最优值 -007 70 最小最优值 -007标准差 -007 平均最优值 -00990 最小最优值 -004 -010 标准差 -009 16
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 表3-6 Griewank函数实验结果对比 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -007 50 最小最优值 -008标准差 -007 平均最优值 -00960 最小最优值 -011 标准差 -009f 5平均最优值 -005 0 100 最小最优值 -006 e-004 0 标准差 -005 0 平均最优值 -007 0 120 最小最优值 -008 0 标准差 -007 0 表3-7 Rastrigrin函数实验结果对比 函数 迭代次数 指标 NPSO BLPSO BTPSO 平均最优值 -008 50 最小最优值 -009标准差 -008 平均最优值 -01060 最小最优值 -011 标准差 -010f 6平均最优值 -004 -014 80 最小最优值 -005 0 标准差 -004 -014 平均最优值 -005 -017 90 最小最优值 -006 0 标准差 -005 -016 从函数最优值的角度来看，BTPSO算法所得平均最优值和最小最优值均好于NPSO、BLPSO 17
宁夏大学硕士学位论文 第三章 动态调整惯性权重的粒子群优化算法 所得平均最优值和最小最优值. 从标准差的角度来看，本章给出的新算法具有很好的稳定性，是一种可靠的全局优化算法．计算精度有明显提高，由此可见，BTPSO算法的全局寻优能力得到了提高. 本章小结 本章从PSO算法自身搜索机制出发，对基本PSO算法的速度更新公式进行改进，粒子速度更新公式中增加了一个除当前进行位置更新的粒子外随机产生的粒子，更多地考虑了群体中其他粒子的位置对算法搜索性能的影响，从而能够进一步增强PSO的全局搜索能力.采用动态非线性方程调整惯性权重和动态Tent混沌映射公式调整惯性权重，逐步摆脱局部最优，向全局最优处收敛，动态寻找全局最优值，提出了动态调整惯性权重粒子群优化算法.通过对六个经典测试函数的测试验证了BTPSO算法的性能，并与NPSO算法、BLPSO算法进行了比较，实验结果表明新提出的BTPSO算法既克服了标准粒子群优化算法易出现早熟收敛的缺陷，又提高了算法的搜索速度和计算精度，在很大程度上改善了标准粒子群优化算法的性能. 18
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 第四章 带飞行时间的粒子群优化算法 引言 与其它智能算法类似，PSO算法也存在早熟收敛和局部寻优能力差等缺点.目前解决这些问题的主要方法是增加种群的多样性以及和其它方法的融合等.而从PSO算法自身搜索机制的角度来考虑增强PSO算法性能的研究并不多，鉴于此，本文对基本PSO算法中粒子的速度更新公式进行了改进，首先引入了整个种群的平均信息，利用了更多的信息来调整粒子的行为，其次采用一种动态改变惯性权重的方法，根据各个粒子适应度值的变化动态改变惯性权重的取值，从而使新算法具有动态自适应性，最后引入了粒子的飞行时间，克服了基本粒子群算法中每个粒子飞行时间设为固定值为1进而导致的粒子群在优化后期寻优性能下降的问题.通过对八个典型的测试函数的试验，数值实验表明该方法是一种收敛速度快、求解精度高、鲁棒性较强的全局优化算法. 速度方程的改进及惯性权重的选取 速度方程的改进 基本粒子群算法的速度公式中只利用了个体最优位置和全局最优位置，考虑到种群中粒子间[46]的平均信息，把速度公式()更新为： v(t+1)=wv(t)+cr(p−x(t))+cr(p−x(t))+cr(p−x(t)) () idid11idid22gdid33avgid其中：p表示第t代所有粒子的个体最优位置的平均值；c为学习因子，决定整个种群对该粒avg3子(第i个粒子)的影响程度.因此，改进后的粒子群优化算法在第t代时，速度公式不仅考虑了粒子对本身信息的思考，同时还考虑了整个种群的平均信息，利用了更多的信息来调整自己的行为. 惯性权重的选取 大量数值实验结果表明，PSO算法无论是出现早熟收敛还是全局收敛，种群中的粒子都会出现“聚集”现象，所有粒子要么“聚集”在某一特定位置，要么“聚集”在某几个特定位置，这主要取决于问题本身的特性以及适应度函数的选择.粒子位置的一致等价于各个粒子的适应度值相同，因此，研究种群中所有粒子适应度值的整体变化就可以跟踪整个种群的状态，根据这种状[44]况，本文采用一种动态改变惯性权重的方法： a×(f(t)−f(t)iminw(t)= () N1f(t)−f(t)∑iminNi=1其中：f(t)表示在第t代时第i个粒子的适应度值，f(t)表示在第t代时所有粒子中最小的适imin 19
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 N1应度值(即全局最优适应度值)，f(t) 表示每次迭代中所有粒子的平均适应度值即f， a∑iavgNi=1为(0,1)之间的常数，本文通过实验取a=. 在算法运行过程中，如果粒子比较发散，它们之间的差异比较大，平均适应度值和群体最小适应度值之差比较大，故a×(f(t)−f(t)/(f−f(t)的值较小，因此惯性权重w较小，iminavgmin所以加强了粒子局部搜索能力.当粒子出现“聚集”现象时，算法陷入局部极值，这时种群的平均适应度值和群体最小适应度值之差比较小，故a×(f(t)−f(t)/(f−f(t)的值较大，iminavgmin因此惯性权重w较大，算法从局部极值区域中跳出来，扩大粒子搜索范围，以便找到全局最优解. 飞行时间的选取 在基本PSO算法中每个粒子通过跟踪个体极值和全局极值来更新自己的位置，该算法原理简单，易于编程实现.然而，迭代过程中基本PSO算法在搜索空间进行寻优时，有时出现种群中的粒子在全局最优值点的周围来回“振荡”，通过调整学习因子的取值和惯性权重的取值也不能完全避免这种现象的产生.数值实验研究发现：基本PSO算法中种群中的粒子在进行位置更新时，每次迭代过程中粒子的飞行时间都设为固定值为1，因此这是导致粒子产生“振荡”现象的一个原因.因为在算法的迭代初期，如果种群中的粒子的位置远离全局最优位置，此时应该让粒子的飞行时间长一些，这样有利于粒子飞到全局最优解的位置；如果当前粒子的位置在全局最优位置附近，这时应该让粒子的飞行时间短一些，以此来避免粒子因飞行时间过长而出现的粒子“飞过”全局最优解进而产生的“振荡”现象.然而我们知道基本粒子群优化算法中，在迭代的初期和后期都把飞行时间设置为固定值1，从而导致粒子在迭代后期寻优性能降低.带有速度和时间的位置公式如下： x(t+1)=wx(t)+v(t+1)∗T(s) () ididid上式中T(s)表示第i个粒子的飞行时间，在传统的粒子群算法中T(s)=1.在物理意义上来说，速度乘以时间才等于距离，即粒子当前位置等于先前位置加上它移动的距离. 粒子在进化过程中，其飞行时间应不断变化.很多实验结果表明，随迭代次数的增加而增长粒子的飞行时间并不能改善粒子群算法的搜索能力，这在现实中也不符合大多数情况下鸟群觅食行为机制.本文采用随迭代次数增加飞行时间非线性递减的公式： t T(s)=T[1+kcos()*π] () 0Tmax其中，T表示最短飞行时间，T=，k为比例系数，起调节作用，因为在很多情况下粒子不00需要进化T次就可收敛，这样T比t的最大值大得多，k在t和T之间起平衡作用，本文maxmaxmax取k=2. 从现实生活中鸟群寻找食物的行为来看，我们知道：种群在从一个位置飞向下一个位置时，并不是每次飞行都用相同的飞行时间.在实际中，鸟群在作位置移动时不仅改变飞行速度，而且他们的飞行时间也是各不相同的.所以，本文提出的带飞行时间的改进粒子群优化算法是符合自 20
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 然界生物进化机制的. 新算法的具体步骤 下面给出本文提出的新的粒子群优化算法的具体步骤： Step 1 随机初始化粒子群中粒子的位置x与速度v，设置最大迭代次数T，种群的规模N，iimax搜索空间的维数D； Step 2 计算每个粒子的适应度值f； iStep 3 将第i个粒子的位置p设置为该粒子当前的最好位置，p设置为初始群体中最佳粒子的ig位置； Step 4 对粒子群中的所有粒子，执行如下操作： 根据式()、() 、()、 ()更新每个粒子的速度与位置； Step 5 再次计算每个粒子的适应度值f；如果粒子的适应度值好于p的适应值，则更新p为当iii前粒子的个体最优位置；如果粒子适应值好于p的适应值，则更新p为当前粒子全局gg的位置； Step 6 判断粒子适应度值是否满足停止条件(通常为预设的运算精度或者迭代次数)，是则退出；否则返回Step 3继续搜索； Step 7 输出全局最优位置P和它的适应度值. 数值实验与分析 算法性能的比较通常是基于一些称为Benchmark的典型问题展开的.我们利用表4-1中的八个常用Benchmark函数逐一进行了测试，并与基本粒子群优化算法LWPSO(基本公式下固定惯性权重为1)和不带飞行时间的线性递减惯性权重粒子群优化算法AMPSO进行比较，本章提出的带飞行时间的粒子群优化算法简记为DPSO.三种算法随机连续运行50次，表4-1~表4-8是这三种算法在不同迭代次数下的具体最优适应度值的均值，这里的参数取值为：种群规模N=60，经大量试验得出对于上述测试函数，当PSO中的学习因子c=c=，c=1时PSO的优化性能最123好. 21
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 表4-1 八个测试函数 函数 名称 特征 维数 范围 理论最优值 D−1222 f(x)[100(x−x)+(x−1)]x≤30Rosenbrock 单峰30 0 1∑ii+1iii=1222sinx+x− x≤1hafferf6 多峰2 0 f(x)+ i2222(1+×(x+x))12302 x≤100f(x)=xSphere 单峰30 0 i3∑ii=1D2f()=−20exp[− i=1x≤32 Ackley 多峰30 0 iD−exp(cos(2∏x)/D)+20e∑ii=1D1Dx2i f(x)=x−cos()+1x≤600 Griewank ∑∏多峰30 0 i5ii=14000ii=1D2 x≤ f(x)=[x−10cos(2πx)+10]Rastrigrin 多峰30 0 i6∑iii=1Six-Hump- 246f(x)=4x−+x/3+7111 x≤5Griewank 多峰2 i24xx−4x+4x1222Camel Schwefel- DD f(x)=x+xx≤10Problem- 多峰30 0 8∑ii∏ii=1i= 表4-2 Rosenbrock 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 50 -005 -006 -015 100 -005 -010 -018 f 150 -006 -011 -023 1200 -06 -014 -030 250 -04 -017 -041 22
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 表4-3 Schafferf6 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 50 80 表4-4 Sphere 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 300 -008 -011 -014f 500 -013 -015 -017700 -016 -021 表4-5 Ackley 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 200 e-001 -005 -007f 600 -004 -012 -017900 -012 -020 表4-6 Griewank 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 200 -003 -003 400 f -0045500 -007 -008 600 -008 23
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 表4-7 Rastrigrin 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 600 800 -0011000 -002 表4-8 Six-Hump-Griewank Camel 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 100 200 f 300 7400 500 表4-9 函数实验结果对比 函数 迭代次数 LWPSO AMPSO DPSO 40 120 -004200 -002 -004 为了更直观的比较这三种算法，下面给出了表4-1中各函数在这三种算法中的寻优曲线图. -5x 值值优优最最均均平平 5010015020025050556065707580859095100迭代次数迭代次数 图4-1 图4-2 24
宁夏大学硕士学位论文 第四章 带飞行时间的粒子群优化算法 18 3 值值优优最8最均均平平 300350400450500550600650700200300400500600700800900迭代次数迭代次数 图4-3 图4-4 50 值值优优25最2最均均20平平 0 2002503003504004505005506006006507007508008509009501000迭代次数迭代次数 图4-5 图4-6 值值优0优最最均均平平 0 100150200250300350400450500100150200250300350400450500迭代次数迭代次数 图4-7 图4-8 从八个函数寻优曲线图明显可以看出，DPSO算法的收敛速度比另外两种算法的收敛速度快. 本章小结 本章提出了一种带飞行时间的粒子群优化算法(DPSO)，即对基本PSO算法中粒子的速度更新公式进行了改进，引入整个种群的平均信息，利用了更多的信息来调整粒子的行为，根据粒子的适应度的变化动态调整惯性权重，以平衡局部搜索和全局搜索能力，考虑到粒子群算法中粒子的飞行时间对优化性能的影响，提出了一种带飞行时间的粒子群优化算法，该方法很好的克服了基本粒子群优化算法中粒子飞行时间固定为1而导致的粒子在迭代后期寻优性能下降的问题.数值实验结果表明，新算法收敛速度均优于其它两种算法，并且其求解精度更高，鲁棒性更强. 25
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 第五章 求解混合整数规划问题的粒子群优化算法 引言 混合整数非线性规划问题(MINLP)的描述如下： 如果在优化问题的数学模型中，决策变量的取值除了连续变量以外还有整数或离散变量（即同时包含整数变量和连续变量)，且约束条件和目标函数部分或全部是含决策变量的非线性函数，则该类优化问题称为混合整数非线性规划，其一般数学表达式如下： ⎧minf(x,y)⎪(x,y)≤0,i=1,2,L,p⎪i⎪ h(x,y)=0,j=1,2,L,q ()⎨j⎪LUx≤x=(x,x,L,x)≤x12m⎪⎪y≤y=(y,y,L,y)≤y⎩12n其中：f(x,y)是带有实数变量和整数变量的目标函数，g(x,y)(i=1,2,L,p)为不等式约i束函数，h(x,y)(j=1,2,L,q)为等式约束函数，x表示一个m维的实数向量，y表示一个jLLUUn维的整数向量，x,y和x,y分别表示对应的决策变量的下界和上界.在用进化算法求解上述问题时，为方便起见，通常把等式约束转变成如下的不等式约束的形式： |h(x,y)|−δ≤0,j=1,2,L,q j这里，δ是一个很小的正数，δ=. MINLP问题广泛应用于机械、计算机、化工、管理、生物、经济、军事等领域.许多组合优化问题都可以视为MINLP问题， 如背包问题、选址问题、TSP问题、化工过程系统的综合最优问题、生产与存储计划问题和分配问题等.由于MINLP同时含有实数变量和整数离散变量，随着变量维数的增加，计算量会急剧增大，从而使这些算法存在很大的局限性.其目标函数和约束条件具有强烈的非线性，往往存在局部最优.求解MINLP问题并不是一件容易的事情，国内外许多学[47]者提出不同的求解方法，大致分为两类： 一是确定性方法，主要有Dantzig-Wolf分解法(GBD)、[48,49][50][51]分支定界法、割平面法（CP）、外逼近法(OA)等，这类方法主要针对特定的中小规[52]模MINLP问题有效.二是近年来广泛关注的随机性方法，主要有遗传算法(GA)，进化规划(EP) [53][54−56][57]，差分进化算法(DE) 和粒子群优化算法(PSO)等，这些方法一般都取得了满意的效果，但存在收敛性没有证明的问题. 求解混合整数规划问题的改进粒子群算法 要将处理连续优化问题的粒子群算法用于求解混合整数非线性规划问题，必须对PSO算法进行改进，根据PSO算法的特点，只要对其位置公式进行改进就可以将PSO算法用于求解混合整数 26
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 非线性规划问题.对于整数变量，本文中对位置矢量进行取整运算（采取四舍五入的方法）. 改进的粒子群优化算法 种群初始化策略 为了方便起见，粒子(x,y)代表第i个粒子(x,x,L,x,y,y,L,y)，x和y为种群ii1i2imi1i2inijij中每个粒子的实数变量和整数变量，并且都在其相应的约束范围内.初始化随机产生N个粒子(x,y)，并且尽量覆盖整个搜索区域，此处按照下面的形式产生初始种群： 00LLUULL (x,y)=(x,y)+ρ{(x,y)−(x,y)}, i=1,2,L,N () iiii其中，ρ是(0,1)之间的随机数. [58]对于每个粒子的整数变量y，利用下面的四舍五入规则进行取整，使其变成整数变量y： ijij(1) 如果y≥[y]+，那么y=[y]+1； () ijijijij(2) 如果y<[y]+，那么y=[y]. () ijijijij这里，[y]表示不超过y的最大整数，这样选取的初始粒子群，保证了粒子的随机性，避ijij免产生相同的整数. 速度方程的改进策略 在基本PSO算法的速度和位置的迭代公式()和()中，每个粒子的飞行轨迹由学习因子c，1c和两个随机数r、r控制，因此，适当地选择学习因子必将影响算法的性能.为了提高PSO算212[59]法的性能，本文对速度公式()进行改进，改进后的公式如下： v(t+1)=wv(t)+r(p−(x(t))+(2−r)(p−(x(t)) () ididididgdid其中：r称为随机调节因子，r取[0,2]之间均匀分布的随机数. 改进后的速度公式()减少了控制参数也就是学习因子c和c，通过以上方法改进后的速度12公式()避免了控制参数选取的困难，使得种群中的每个粒子在寻优范围内自适应地改变自我认知能力和社会认知能力，从而提高了粒子群优化算法的全局寻优能力. 惯性权重的取值较大则有利于提高算法的全局寻优能力，而惯性权重的取值较小则有利于提高算法的局部寻优能力.我们可以通过选取适当的惯性权重w的值，使得粒子群优化算法在每次迭代过程中自动维持该算法的全局寻优能力和局部寻优能力之间的平衡，下面给出了一种惯性权重的取值策略，表达公式如下： T−tmax w= () [(w−w)×()+w]×z maxminminn+1Tmax其中：w表示最大的惯性权重值， w表示最小的惯性权重值，t表示当前的迭代次数， Tmaxminmax表示最大迭代次数，z=4z(1−z)，z∈(0,1)，n=0,1,2,L. n+ 位置方程的改进策略 对于实数变量，我们用下面的公式来更新粒子的位置： 27
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 x () (t+1)=x(t)+v(t+1)+rand ()ididid对于整数变量，用四舍五入的方法进行取整，其位置更新公式为： y(t+1)=[y(t)+v(t+1)+rand () ()] 违反搜索空间的处理 在有边界约束的优化问题中，最重要的一点是确保产生的新粒子位于问题的可行域中，一个简单方法是将不符合边界约束的新粒子用边界来代替，另一种方法是用可行域中随机产生的向量来代替. U目前我们可以见到很多处理边界约束的方法，例如最常见的是将超出边界的分量用上界x jULLUULL(y)或下界x(y)来代替.本文用上一代的分量x(t)(y(t))和边界x(y)或x(y)的jjjijijjjjj平均值来替代超出边界的分量： 1⎧LL(x(t)+x) , if x(t+1)<xijjijj⎪⎪2x(t+1)= () ⎨ij1UU⎪(x(t)+x) , if x(t+1)>xijjijj⎪⎩2⎧1⎡⎤LL(y(t)+y) , if y(t+1)<yijjijj⎪⎢⎥2⎪⎢⎥y(t+1)= () ⎨ij1UU⎪(y(t)+y), if y(t+1)>yijjijj⎢⎥⎪2⎣⎦⎩UULLx、y，x、y分别表示变量的第j个分量的上、下界. . 约束条件的处理 在求解混合整数非线性规划问题时，约束条件的处理也是一个关键，这里我们定义每个粒子[60](x,y)的约束违反程度的函数为： pqG(x,y)max{0,g(x,y)}+max{0,|h(x,y)|−δ} () ∑∑iji=1j=1可见，G(x,y)是所有约束违反度函数的和，且G(x,y)≥0.当粒子(x,y)在可行域范围内时，G(x,y)=0，即G(x,y)=0的所有解组成了MINLP问题的可行域. 可行基规则 [15]在初始化的粒子群中，对于其中任意两个粒子，我们按照下面给出的三条规则来比较： （1）如果一个粒子为可行解，另一个粒子为不可行解，则可行解优于不可行解； （2）如果两个粒子都为可行解，则目标函数值较好的解为优； （3）如果两个粒子都为不可行解，则根据公式()定义的约束违反程度的函数值进行比较，约束违反程度的函数值较小的粒子优于约束违反程度函数值大的粒子． 动态约束处理方法 28
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 这里用定义的约束违反度函数G(x,y)来判断每个粒子是否在可行域里，我们采用下面给出的调整目标函数和约束函数的方法来优化目标函数f(x,y)和约束违反度函数G(x,y)，让粒子靠近可行域，即：如果一个粒子在可行域内，就用原来的目标函数f(x,y)来计算，否则，如果一个粒子跑到可行域外，那么就用这个粒子的约束违反度函数G(x,y)作为目标函数来计算．在这个优化过程中，如果一个粒子跑出可行域外，则将再一次优化约束违反度函数G(x,y)，所以每个粒子能动态调整各自的目标函数是f(x,y)还是G(x,y)，这样做的目的是让粒子进入可行域[61]内，成为可行解．因此用这种方法来动态调整目标函数和约束函数的算法可描述为： set G=G(X(t)),f=f(X(t)),G=G(p_bx),pbf=f(p_bx)iiiiibestiiIf G<G iibestThenp_bx=X(t),pbf=f,G=G,iiiibestiEnd If G=0andG=0iibest If f<=pbf ithenp_bx=X(t),pbf=fiiiEnd End其中，X(t)表示第t代第i个粒子(x,y)，G为个体最优位置的约束违反度函数值． iiibest以上是计算个体最优位置p_bx和个体最优值pbf．如果某一个粒子和个体最优位置的粒i子两者都是不可行粒子，且当前某个粒子优于个体最优位置，则该粒子记为个体最优位置，其目标函数值记为个体最优值，其约束违反度函数值记为个体最优位置的约束违反度函数值；如果任一个粒子和个体最优位置的粒子两者都是可行粒子，则目标函数值优的粒子记为个体最优位置，其目标函数值记为个体最优值． set G=G(g_bx),gbf=f(g_bx),G=G(X(t),f=f(X(t)gbestiiiiIf G<G igbestTheng_bx=X(t),gbf=f,G=GiigbestiEndIf G=0andG=0 igbest If f<=gbf itheng_bx=X(t),gbf=fiiEndEnd其中，G为全局最优粒子的约数违反度函数值． gbest以上是计算全局最优位置g_bx和全局最优值gbf．如果当前某一个粒子和全局最优位置的粒子两者都是不可行粒子，且当前某个粒子优于全局最优位置，则该粒子记为求解最优位置，其目标函数值记为全局最优值，其约束违反度函数值记为全局最优位置的约束违反度函数值；如果任一个粒子和个体最优位置的粒子两者都是可行粒子，则目标函数值优的粒子记为全局最优位 29
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 置，其目标函数值记为全局最优值． 新算法的具体步骤 由此，改进粒子群优化算法求解MINP问题的算法流程如下： Step 1 初始化设置：确定种群规模N和粒子维数D，最大迭代次数以及相关参数；随机初始化粒子速度，根据式()、() 、()初始化各个粒子的位置； Step 2 根据可行基规则计算出初始种群的每个粒子的个体最优位置p_bx、个体最优值pbf、i个体最优位置的约束违反度值G；全局最优位置g_bx、全局最优值gbf、全局最优ibest位置的约束违反度值G； gbestStep 3 对种群中的所有粒子，执行如下操作： 根据式()、()、()、()更新粒子群中每个粒子的当前速度与位置，如果某个粒子(x(t),y(t) 的某一维分量(x(t),y(t)(d=1,2,L,D)的取值不在寻优空间的范围iiidid内，则按公式()、()对该粒子的这一维分量进行重新赋值； Step 4 再次计算粒子群中每个粒子的适应度值f和约束违反度值G. ii根据上面给出的算法更新个体最优位置p_bx、个体最优值pbf、个体最优位置的约束i违反度值G和全局最优位置g_bx、全局最优值gbf、全局最优位置的约束违反度值ibestG； gbestStep 5 让t=t+1，若满足停止条件(通常为预设的精度或者迭代次数)，则搜索停止，并输出结 果，否则返回Step 3继续搜索； Step 6 输出全局最优位置gbx和它的全局最优适应度值gbf. 数值实验与分析 为验证本文提到的IPSO算法求解MINP问题的有效性，与文献[59]的结果进行比较.种群规模N=30，δ=，每个问题独立运行10次，记录10次所得到的最优值和成功率C%(10次运行中找到最优解的百分比)，目标函数的平均计算次数#F. 具体问题如下： (1) 问题1 min f(x,y)=2x+. −x−y≤0 x+y−≤0 0≤x≤ y∈{0,1}全局极小解是(,1)，全局极小值为2. (2) 问题2 30
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 min f(x,y)=−y+2x+. −2exp(−x)=012 −x+x+y≤012 ≤x≤ y∈{0,1}全局极小解是(,,1)，全局极小值为. (3)问题3 2min f(x,y)=−+5(x−)+. −exp(x−)−x≤012 x+≤− x−≤ ≤x≤ −≤x≤− y∈{0,1}全局极小解是(,−,1)，全局极小值为. (4)问题4 222222min f(x,y)=(y−1)+(y−1)+(y−1)−ln(y+1)+(x−1)+(x−2)+(x−3). y+y+y+x+x+x≤ y+x+x+x≤ y+x≤ y+x≤ y+x≤ y+x≤ y+x≤ y+x≤ y+x≤ x,x,x≥0123 y,y,y,y∈{0,1}1234全局极小解是(,,,1,0,0,1)，全局极小值为. (5) 问题5 31
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 2max f(x,y)=−−−+. a+ayx+ayx−axx−92≤012233124132 a+ayx+ayy+ax−110≤0562371281 a+axx+ayx+axx−25≤09101311111212 27≤x,x,x≤45123 y∈{78,L,102}1 y∈{33,L,45}2全局极大解是 (78,27,27)，全局极大值为. (6) 问题6 min f(x,y)=++5x+7x+. y+y−1=012 x−[1−exp(−)]=0614 x−[1−exp(−)]=0725 x+x−10=067 x+x−x=0123 xy+xy−10=06172 x−10y≤0 41 x−10y≤052 x−20y≤011 x−20y≤022 x≥0,y∈{0,1}全局极小解是 (,,0,1,0)，全局极小值为. 表5-1 本文算法的计算结果 目标函数的 问题 理论最优值 本文极小、大值成功率 C% 平均计算次数 #F 1 2 2 100 1293 2 100 1526 3 100 1397 4 100 4961 5 最大 100 2109 6 90 5260 32
宁夏大学硕士学位论文 第五章 求解混合整数规划问题的粒子群优化算法 表5-2 四种算法的结果比较 MIHDE HEA IPSO 问题 #F C% #F C% #F C% 1 13104 100 780 100 1293 100 2 28455 100 5250 100 1526 100 3 29166 100 1612 100 1397 100 4 12375 100 9008 80 4961 100 5 938 100 2580 100 2109 100 6 60950 100 8175 90 5260 90 由表5-1可以看出，本文提出的IPSO算法能以较大的概率找到所求问题的最优解，由表5-2可以看出，除问题1和问题5外，IPSO对适应度函数的平均计算次数明显少于其它算法，说明了新算法计算量小，收敛速度较快. 本章小结 本章给出了求解混合整数规划问题的粒子群优化算法，该算法对粒子群算法的速度方程和位置方程进行改进，给出了违反搜索空间的处理策略，利用无约束双目标的方法求出粒子群的全局最优解，它的主要思想是将约束违反度函数作为优化的第一个目标，将目标函数作为第二个目标进行优化.选取几个常见的测试函数对这种改进的粒子群优化算法进行了数值实验，实验结果表明给出的新算法是求解混合整数规划问题的有效算法. 33
宁夏大学硕士学位论文 第六章 研究工作总结与展望 第六章 研究工作总结与展望 研究工作总结 最优化是一门应用性强、内容丰富的学科，它是数学领域的一个重要分支.最优化方法是一个以数学为基础的科学，因此受到研究学者的极大重视，已经成功被迅速推广和应用于许多领域.随着高科技的不断发展，现实生活中的许多优化问题变得非常复杂难以求解.被求解的许多优化问题具有非线性、复杂性、多极小等特点，因此很难用常规的求解方法得到满意的解，因此探索一些新的求解优化问题的方法已成为一个主要研究目标和研究方向. 在求解复杂优化问题时进化算法给提供了新的思路和方法，近年来受到了人们极大的关注. 做为高效的智能进化算法之一的粒子群优化算法，已经在多个领域被广泛应用，但其在理论和应用推广方面还有待进一步研究，针对这些方面提出了改进的方法，以下对全文的研究工作给出简要的总结： (1) 首先对本文的课题来源、粒子群优化算法在国内外的研究现状和发展趋势作了详细介绍.详细阐述了粒子群优化算法的基本原理、算法的设计步骤、算法的基本流程和算法的控制参数设置及改进策略：调整惯性权重、引入收缩因子、融入选择策略、融入杂交策略，介绍了粒子群优化算法的一些应用. (2) 对随机优化中的PSO算法进行了改进.算法参数是影响算法性能和效率的关键，而粒子群优化算法中最重要的参数是惯性权重，它影响算法的全局搜索能力和局部搜索能力的平衡.针对线性递减惯性权重不能适应复杂的非线性优化搜索过程的问题，提出动态调整惯性权重的粒子群优化算法.通过一系列的数值试验表明，提出的动态调整惯性权重的粒子群优化算法求解精度高，其性能远远优于一般的粒子群优化算法. (3) 为了快速而高效的找到全局最优解，提出了一种带飞行时间的粒子群优化算法.改进的速度更新公式不仅考虑了粒子对本身的思考，同时还考虑了整个种群的平均信息，利用了更多的因素来调整自己的行为；动态自适应惯性权重使算法可根据粒子的适应度变化动态改变惯性权重，引入飞行时间，从而克服了由于基本粒子群优化算法固定粒子飞行时间而导致的粒子在进化后期搜索性能下降的问题，提高了算法的收敛速度和收敛精度. (4) 给出了求解混合整数非线性规划问题的粒子群优化算法，该算法对粒子群的速度方程和位置方程进行改进，利用无约束双目标的方法求出问题的全局最优解，选取几个常见的测试函数对这种改进的粒子群优化算法进行了数值实验，实验结果表明给出的算法是求解混合整数规划问题的有效算法. 关于未来研究的展望 目前虽然对粒子群优化算法PSO的研究和应用取得了许多的成果，但是该算法仍然还存在很多不足之处，主要表现为该算法的理论还不够完善，在应用上还有待更进一步的研究，需要解决的问题还很多： 34
宁夏大学硕士学位论文 第六章 研究工作总结与展望 (1) 解决复杂的优化问题如高维、不连续、多峰及随机环境下时，单一的进化算法有时不能求得问题的最优解，把其它进化算法的优点相融合的混合智能进化算法将是未来的研究热点. (2) 通过阅读大量书籍文献，发现粒子群优化算法在求解一些离散优化问题方面资料比较少，因此将粒子群优化算法用于图挖掘、计算生物信息学中的大量离散优化问题将是很有意义的研究. (3) PSO算法的改进.在实际应用中，并不是每一种算法都是适合求解所有优化问题的，每种算法都有局限性，需要不断的改进与总结.目前针对PSO算法的改进策略非常多，但改进算法通常只是针对测试函数的研究，在实际应用中往往会遇到一些困难，或根本无法实现.因此，对具体的问题，设计合适的改进算法更具有推广价值和意义. (4) 对粒子群优化算法的研究仅限于静态问题的优化，在实际的应用中很多优化问题是随时间动态变化并且是多目标的，因而将粒子群优化算法应用到动态领域或者多目标问题具有重要的现实意义. (5) PSO算法的应用研究.本文的研究仅限于混合整数规划问题的优化，局限性较大，因而将PSO算法应用到更复杂的领域具有重要的现实意义. 35
宁夏大学硕士论文 参考文献 参考文献 [1] 运筹学教材编写组.运筹学[M].北京：清华大学出版社，2000 [2] 薛嘉庆.最优化原理与方法[M].北京：冶金工业出版社，2001 [3] , , . Artifieial Intelligenee Through Simulated Evolution NewYork: Johniley, 1996 [4] 张丽萍，跃廷遗. 遗传算法的现状及发展动向[J]. 信息与控制，2001，30(6):531 - 536. [5] , , . The immune system, adaptation, and machine learning [J].1986, 22(2) :187-204 [6] , Maniezzo, . Theant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on System, 1996, 26(1):29- 41 [7] , . Particle swarm optimization[C]. IEEE International Conference on Neural Networks, Perth, Australia,1995, 1942-1948 [8] , . A new optimizer using particle swarm theory[J].1995, 39-43 [9] , The particle swarm: social adaption of knowledge[C]. 1997, 303-308 [10] Wang Dingwei. Colony location algorithm for combinatorial optimization[J]. Proe. IEEE, Co- nference on Systems, Man&Cybernetics[C]. Piscataway NJ:IEEE Service Center, 2004, 1903-1909 [11] Wang Dingwei. Colony location algorithm for assignment problem[J]. Journal of Control Theory and Application, 2004, 2(2):111-116 [12] Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization[C]. Proceedings of the Congress on Evolutionary Computation, Piscataway, NJ : IEEE Service Center , 1999. 1951～1957 [13] 杨维，李岐强. 粒子群优化算法综述[J]. 中国工程科学，2004，6(5): 87-93 [14] Qie He, Ling Wang. A hybrid particle swarm optimization with a feasibility-based rule for constra- ined optimization[J]. Applied Mathematics and Computation，2007, 186(2): 1407 - 1422 [15] , , . A mixed-coding scheme of evolutionary algorithms to solve mixe- d-integer nonlinear programming problems[J]. Computers and Mathematics with Applications, 2004, 47(8-9) : 1295-1307 [16] 张利彪，周春光，马铭等. 基于粒子群算法求解多目标优化问题[J].计算机研究与发展，2004，41(7):1286-1291 [17] 王俊年，申群太，周少武.基于种群小生境微粒群算法的前向神经网络设计[J].控制与决策，2005，20(9):981-985 [18] , , , etc. Particle swarm optimization for parameter determination and feature selection of support vector machines[J]. Expert Systems with Applications, 2008, 35 (4): 1817-1824 [19] . . Parricle swarm optimization: surfing the waves[C]. Proceedings of the IEEE 36
宁夏大学硕士论文 参考文献 Congress on Evolutionary Computation(CEC), Picataway, NJ, 1999, 1939-1944 [20] den Bergh. An Analysis of Particle Swarm Optimizers. [PHD Thesis]. University of Pretoria, Nov 2001 [21] Chunxia Fan, Youhong Wan. An Adaptive Simple Particle Swarm Optimization Algorithm[C]. 2008 Chinese Control and Decision Conference(CCDC2008) [22] , . A modified particle swarm optimizer. IEEE World Congress on Computation- al Intelligence, 1998, 69-73 [23] 高鹰，谢胜利.免疫粒子群优化算法[J].计算机工程与应用，2004，40(6):4-7. [24] , . Empirical study of particle swarm optimization[C]. International Conference on Evolutionary Computation, Washington, USA: IEEE, 1999, 1945-1950 [25] , . Fuzzy adaptive particle swarm optimization[C]. The IEEE Congress on Evolutionary Compution, San Francisco, USA: IEEE, 2001, 101-106 [26] , . Tracking and optimizing dynamic systems with particle swarms[C]. The IEEE Congress on Evolutionary Computation, Seoul Korea: IEEE, 2001 [27] 陈贵敏, 贾建援, 韩琪. 粒子群优化算法的惯性权值递减策略研究. 西安交通大学学报，2006，6(1):53-61 [28] 陈君波，叶庆卫，周宇， 曹小华. 一种新的混合变异粒子群算法[J].计算机工程与应用，2007，43(7) :59-61 [29] 陈建超，胡桂武. 全变异粒子群优化算法[J].计算机工程与应用，2009，45(32) :25-26 [30] 胡成玉，吴湘宁，王永骥. 基于种群熵的多粒子群协同优化[J].计算机应用研究，2008，25(12) : 3593-3595 [31] 刘怀亮，苏瑞娟，许若宁，高鹰.协同粒子群优化算法[J].计算机应用，2009，29(11) :3068-3073 [32] , . Particle swarm optimization with gaussian mutation[C]. The 2003 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 2003, 72-79 [33] Ning Li, Yuanqing Qin, Debao Sun, Tong Zou. Particle swarm optimization with mutation operator [C]. The Third International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE Press, 2004, 2251-2256 [34] 吕振肃，侯志荣.自适应变异的粒子群优化算法[J].电子学报，2004，32(3) :416-420 [35] Buthainh Al-Kazemi. Multi-phase particle swarm optimization[J]. Computer Engineering in the Graduate School of Syracuse University, USA, 2002 [36] Eberhart, X .Hu. Human tremor analysis using particle swarm optimization[C]. Proceedings of the IEEE Conference on Evolutionary Computation. Piscataway, NJ: IEEE Service Center, 1999: 1927 - 1930 [37] . Using selection to improve particle swarm optimization[C]. Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Anchorage, Alaska, USA, 1998,84-89 [38] . Shi, . A modified particle swarm optimizer[C]. Proceedings of the IEEE Congress on Evolutionary Computation (CEC) , Anchorage, Alaska, USA, 1998, 69-73 37
宁夏大学硕士论文 参考文献 [39] , . The particle swarm-explosion, stability, and convergence in a multidimension- al complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (1):58-73 [40] Suganthan P N. Particle swarm optimiser with neighbourhood operator[C]. Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Piscataway, NJ, 1999:1958-1962 [41] VAN DEN BERGH F, ENGELBRECHT A P. Training product unit networks using cooperative particle swarm optimization[C]. Proc of the third Genetic and Evolutionary Computatio Conferen- ce (GECCO), 2001:126-131 [42] 王瑾，张求明，黄波. 粒子群优化算法的分析与研究[J].计算机与现代化，2009，167(7) : 22-25 [43] 高鹰，谢胜利. 混沌粒子群优化算法[J].计算机科学，2004，31(8) :13-15 [44] 张小萍. 微粒群优化算法的改进及其应用：[硕士学位论文]. 宁夏：宁夏大学，2008 [45] 刘怀亮，苏瑞娟，许若宁，高鹰.一种新的改进粒子群优化算法[J].计算机工程与应用，2010，46(12) :38-41 [46] 秦玉灵，孔宪仁，罗文波. 混沌量子粒子群算法在模型修正中的应用[J].计算机工程与应用，2010，46（2）: 240-242 [47] 李会荣，李济民，高岳林. 带有种群平均信息和保持活性策略的粒子群优化算法[J].甘肃联合大学学报，2008，22(1): 82-86 [48] Yuelin Gao, Chengxian Xu, Jimin Li. Linear programming relax_PSO hybrid bound algorithm for a class of nonlinear programming problems[J]. Lecture Notes in Artificial Intelligence, LINA 4456: 29-35 [49] Yuelin Gao, Yanjun Wang, Xuewu Du. A two-level relaxed bound method for a nonlinear class of 0-1 knapsack problems[J]. Intelligent Information Management Systems and Technologies, 2005, 1(3): 461-470 [50] Yuelin Gao, Chengxian Xu, Yongjian Yang. An outcome-space finite algorithm for solving linear multiplicative programming[J]. Applied Mathematics and Computation, 2006, 179: 494-505 [51] , , , . An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms[J]. Computers and Chemical Engineering, 2008, 32:477-493 [52] , , . Li. Genetic algorithm for non-linear mixed integer programming problems and its applications[J]. Computers Ind. Engng, 1996, 30(4):905-917 [53] Fang Liu, Renhou Li. Solving mixed integer nonlinear programming problems by the evolutionary programming based on the prepotency of races[J]. Journal of System Simulation, 2003, 15(8) : 1076-1078 [54] , . Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4) : 341 -359. [55] Yungchien Lin, Fengsheng Wang, Kaoshing Huang. A Mixed-Coding Scheme of Evolutionary Algorithms to Solve Mixed-Integer Nonlinear Programming Problems[J]. Computers and Mathematics with Applications, 2004, 47:1295-1307 38
宁夏大学硕士论文 参考文献 [56] , , , Co-Evolutionary hybrid differential evolution for mixed-integer optimization problems [J]. Eng. Opt, 2001, 00:1-20 [57] Yijun He, Dezhao Chen. Hybrid particle swarm optimization algorithm for mixed-integer nonlinear programming[J]. Journal of Zhejiang University(Engineering Science), 2008, 42(5) [58] Kusum Deep, Krishna Pratap Singh, , C. Mohan. A real coded genetic algorithm for solving integer and mixed integer optimization problems[J]. Applied Mathematics and Computati- On, 2009，(212) : 505-518 [59] 李宏，焦永昌，张莉. 一种求解混合整数规划的混合进化算法[J].控制与决策，2008，23(10) :1098-1102 [60] 李会荣，高岳林.粒子群优化的速度非常改进与自适应变异策略[J].计算机工程与应用，2010，46（13）47-50 [61] Haiyan Lu, Weiqi Chen. Dynamic-objective particle swarm optimization for constrained optimization problems[J] .Combinatorial -419 39
宁夏大学硕士论文 致谢 致谢 感谢我的导师高岳林教授在硕士这三年来对我的辛勤培育.感谢高老师在论文期间给我的指导和帮助.高老师渊博的专业学术知识、严谨的治学态度、高度的敬业精神深深地影响着我，使我终身受益.从高老师身上，我不仅学到了专业理论知识，更学到了做人处事的道理，在此，我向高老师表示最诚挚的谢意.祝高老师身体健康，工作顺利. 感谢我的师兄弟和师姐妹们在这三年的学习中对我的关怀和帮助.同时，感谢所有在我学业和生活上给予我帮助的朋友和同学.感谢你们的援助之手.真心地祝福你们. 感谢我的家人，感谢你们对我的理解、支持与关爱！ 感谢在百忙之中评阅论文和参加答辩的各位专家、教授！谢谢！ 徐红芳 2011年5月 40
宁夏大学硕士论文 个人简介 个人简介 1 作者简历 徐红芳，女，汉族，1982年5月出生，2008年7月毕业于唐山师范学院，2008年9月至今在宁夏大学数学计算机学院攻读计算数学专业硕士研究生，研究方向为最优化理论方法及其应用. 2 在校期间参加的科研项目 1 宁夏自然科学基金项目“基于粒子群优化的混合智能算法研究(NZ0848)” 2 国家自然科学基金项目“融合粒子群优化和差分进化的混合智能算法研究(60962006)” 41
