各位，ae中有没有PS中分辨率与ppi（ppi）的概念
点击联系发帖人
时间：2018-03-22 16:05
为什么是72呢?72PPI的秘密解析
互联网 & 03-14 17:05:51 & 作者：佚名 &
为什么是72呢?很多朋友都不是很清楚，甚至也不知道为什么，所以下面小编为大家解析72PPI的秘密，来看看吧
在平时的设计中，我都会习惯性的在PS新建界面分辨率后面输入72。在某天ps更新后，我新建文档发现预设里的&移动应用程序设计&，不同大小的设备会显示不同的分辨率（PS CC 2015版本中已经都已经改为了72）。这引起了我的好奇，这个数字也不知道是谁告诉我的了，只是平时做pc端、手机端的设计时都会在分辨率里输入72。从来也没有去研究过这个72像素／英寸是从哪里来的，为什么是72呢？我设置...行吗？72有什么特殊呢？
PS中的单位
百分百：这个不需要解释
英寸、厘米、毫米：这些是我们生活当中常用的长度单位，是自然界中的绝对长度。
点、派卡：是打印中使用的长度单位，1英寸＝2.54厘米＝72点＝6派卡，这个换算公式告诉我们点、派卡也是绝对长度
像素：像素可以理解为&图像元素&即组成图像最小的元素，每个元素不是一个点或者一个方块，而是一个抽象的取样。我是这样理解的，像素就如同平面构成中点线面的点，这个点是一个抽象的概念，没有具体的大小，没有具体的形状，就如同一个点可以变成一个面，一个面可以变成一个点，相对整体而言这个点才有实际的意义。
分辨率的含义
分辨率Image resolution，中国大陆译为&分辨率&，香港、台湾分别译为&解像度&和&解析度&，泛指量测或显示系统对细节的分辨能力。（维基百科）
描述分辨率的单位
ppi－pixels per inch 像素分辨率&每英寸的长度内包含多少数量的像素。
dpi－dots per inch 设备分辨率 &每英寸的长度内包含多少数量的&点&。
分辨率的使用的三个误区
1、很多文章会把ppi和dpi混淆使用，从道理上讲是没有错的，因为我们也可以把像素理解成图像中的&点&。或是把设备中的&点&理解为像素，无论是手机还是电脑虽然分辨率都是以像素为单位的，但是它们都属于输出设备的范畴所以用dpi来表示更为合理，而图像的分辨率应该以ppi表示，这点大家理解就好。
2、PS中的分辨率72ppi和我们平时说的iphone5的分辨率326dpi的计算方法是不一样的。
PS中ppi只是计算图像长或宽中每英寸的像素数量，而我们说的手机或电脑的dpi是屏幕对角线每英寸的像素数量。
3、我们工作中经常说一幅图分辨率是72像素，正确的表述应当是600x1920像素，分辨率为72ppi，只是平时工作习惯简化描述而已。
为什么是72ppi呢？
（当图像的分辨率（长x宽像素）一样，不同大小ppi的图像是否会对我们的设计工作造成影响呢？）
例如我们设计一个手机界面，新建一个640x1136像素，分辨率为72ppi和一个640x1136像素，分辨率为7200ppi的图像。
在电脑上看到的效果和把两幅图输出到同一手机上看到的效果是一样的。这是因为屏幕上看到的图像都是由像素组成的，只要图像的像素数量没有改变，图像质量就不会改变，在同一屏幕上呈现的大小也就不会改变。但当我们把两幅图像打印出来时，分辨率7200ppi的图像面积不到10mm²，而72ppi图像面积大概有900cm²。这是因为打印出来的图像是由墨点组成的，而这些墨点的排列规则是由我们之前设置的图像分辨率ppi来决定的。
用生活中你的现象来打个比方
（这里我们要注意一点就是屏幕的物理像素点大小是不会改变的。）
就好比有一个盒子，里面放着正方形的糖块，这个盒子里面可以放640x1136块糖，每块糖1元，72块糖长度为1米。
还有另一个盒子里面也放着正方形的糖块，同样放着640x1136块糖，每块糖也是1元，但是7200块糖长1米。
所以我们购买他们的价钱是一样的，都是640x1136x1元。只要糖块的数量没有改变我们购买他们的价钱就是一样的，就像图像分辨率的ppi不论怎么改变，只要像素数量不发生变化，图像在同一屏幕上呈现的大小就不会改变。但是我们花同样的钱购买回来的糖大小却不一样了，就像同样像素数量的图像，ppi不一样打印的大小也不一样。
72ppi的由来
早期MAC开发了一种图形界面，当把ppi设置成72时1英寸＝2.54厘米＝72点＝72像素＝6派卡。这时就把只有相对单位长度的像素赋予了真实的物理长度，刚好1个点（打印设备）和屏幕上的1个像素对应。而且当时MAC的显示器大都是14英寸的，系统显示分辨率最高也就到800&600像素，72dpi。当图像分辨率的ppi和屏幕分辨率的dpi一致时，屏幕上的标尺就会和现实生活中的标尺一致，图像在电脑中显示的大小就和打印出来的尺寸是一样的了。
很久以前72ppi就已经成为了屏幕图像设计的标准，并且大家长期这样使用。所以对于屏幕图像的设计，分辨率ppi无论设置成多少都不会对我们的工作造成影响。但为了和大家保持一致我们还是要把分辨率设置成72ppi，这样还有一个好处就是在PS中无需设置字体的单位了，因为1pt＝1px。
大家感兴趣的内容
12345678910
最近更新的内容粒子群算法及其在图像分割中的应用_学霸学习网
粒子群算法及其在图像分割中的应用
分类号密级博 士 学 位 论 文题 目： 粒子群算法及其在图像分割中的应用 与研究 英文并列题目： The Study of the Particle Swarm Optimization and Its Application 研 专 导 究 生： 业： 师： in Image Segmentation 高 浩 轻工信息技术与工程 轻工过程模型化及控制 须 文 波研 究 方 向： 指导小组成员： 学位授予日期：答辩委员会主席： 袁景淇江 南 大 学地址：无锡市蠡湖大道 1800 号 二 OO 九年十二月
独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名： 日 期：关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名： 导师签名： 日 期：
摘要摘要粒子群优化算法源于鸟群和鱼群群体运动行为的研究， 是一种新的群体智能优化算 法，是演化计算领域中的一个新的分支。它的主要特点是原理简单、参数少、收敛速度 快，所需领域知识少。该算法的出现引起了学者们极大的关注，已在函数优化、神经网 络训练、组合优化、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。尽 管粒子群优化算法发展近十年，但无论是理论分析还是实践应用都尚未成熟，有大量的 问题值得研究。 本文从算法机理、算法改进和算法应用等方面对其进行了系统性的研究。此外，图 像分割是图像分析和模式识别的首要问题，也是图像处理的经典难题之一。本文将微粒 群算法和图像分割法相结合，提出了基于改进 PSO 算法的分割算法，在取得良好的分 割效果的同时，运用算法的并行搜索机制显著的提高了分割速度。论文具体内容如下： (1) 对粒子群算法及其理论基础（优化方法和进化计算）进行了详细的综述。 首先本文概述了优化方法的产生和发展，着重介绍了优化方法的基本思想、研究领域、 应用发展情况；阐述了进化计算的产生、定义以及研究内容，并介绍了几种典型的进化 计算方法，包括遗传算法、进化策略、微分进化等；最后介绍了粒子群优化算法，阐述 了粒子群优化算法的起源，介绍了粒子群优化算法的初始版本和标准版本，从理论研究 和应用研究的角度综述了粒子群优化研究的现状，总结了标准粒子群优化算法存在的问 题。同时本文使用了蒙特卡罗方法对粒子的行为进行了研究，结果显示 PSO 算法在迭 代后期具有搜索能力较弱的缺点，同时也给出了如何提高 PSO 算法收敛性的方法。此 外，九个标准测试函数用来测试 PSO 算法和其他几种流行的进化计算方法的性能，结 果验证了 PSO 有着其他进化算法无法比拟的快速收敛等特性。 (2) 尽管 PSO 算法比其他算法对复杂函数有着较强的寻优能力以及收敛速度快 等特点，但是它依然无法保证在搜索空间中找到全局最优点。因此在本文中引入了具有 着更强全局搜索能力的 QPSO 算法来进行研究改进。但是由于 QPSO 同 PSO 算法一样 的是， 它也把粒子作为一个整体来进行更新， 因此 QPSO 算法同样具有维数限制的缺点。 通过把一个具有复杂高维的粒子分解为多个一维的子个体进行优化，使用协作方法的 QPSO 算法能够很好的克服这一缺点。八个测试函数以及应用于图像分割领域的最大类 间方差法（OTSU 方法）在本文中用来测试改进以后的 QPSO 算法的成绩。仿真结果表 明，与其他算法比较来看，协作方法帮助 QPSO 算法获得更精确的解。它同样也克服了 OTSU 方法受维数束缚的缺陷。 (3) 在分析了粒子群全局收敛能力的基础之上，针对粒子群算法局部收敛和搜 索精度低的问题，提出了一种全局的基于 Gaussian 变异的粒子群算法(GGPSO）.该算法 结合了局部和全局变异因子使算法在全局和局部搜索能力中找到了一个很好的平衡，并 证明了它能以概率 1 收敛到全局最优解。典型函数优化的仿真结果表明，该算法不仅可 有效的避免标准 PSO 算法的早熟收敛，而且具有寻优能力强、搜索精度高、稳定性好等 优点。同时针对图像信息处理中的图象分割这一难点问题，以 Kapur 算法为优化目标，I 摘要验证了该算法克服了图象分割中寻优速度慢的缺点，与其他群体算法比较获得了更大的 适应度函数值。因此，该算法更适合于图像分割以及相关的函数优化问题。 (4) 在分析了粒子群收敛性的基础之上， 针对粒子群(PSO)算法后期搜索能力下 降的问题，提出了一种基于适度随机搜索策略的粒子群算法(IRPSO）.该方法在提高粒 子群算法收敛速度的前提下，有效的提高了粒子的全局搜索能力。另外，由于该方法只 有一个控制参数和迭代公式，因此更为简单易实现。典型函数优化的仿真结果表明，该 算法相对于比较算法来说获得了更好的性能。同时针对图像分割这一难点问题，以互信 息熵差为优化目标，验证了该算法在比较算法中获得了更好的分割效果。 论文最后对所做工作进行了总结，并提出了进一步研究的方向。关键词：进化算法，粒子群算法，图像分割，收敛速度，全局搜索能力，维数约束， 蒙特卡罗方法II AbstractAbstractParticle swarm optimization (PSO) is an evolutionary computation technique developed by Dr. Eberhart and Dr. Kennedy in 1995, inspired by social behavior of bird flocking or fish schooling. Recently, PSO algorithm has been gradually attracted more attention over another intelligent algorithm. PSO is simple in concept, few in parameters, and easy in implementation. It was proved to be an efficient method to solve optimization problems, and has successfully been applied in the area of function optimization, neural network training and fuzzy control systems, etc. However, both theory and application of PSO are still far from mature. The paper gives a comprehensive study on PSO from the aspect of algorithm mechanism, algorithm modification and its application. Furthermore, image segmentation is the first and foremost problem in image analyzing and mode recognition, and is also a typical stumbling block in image processing. In order to raise its speed, we combined the method of PSO and image segmentation algorithm on valves and therefore proposed several segmentation algorithms based on improved PSO. As we achieve an effective segmentation, we also raised the speed of the parallel searching system. The main content is as follows: (1) The paper surveys PSO algorithm and its basic theories (Optimization method and Evolutionary Computation, EC). First we summarize the generation and development of Optimization method in detail, and emphasize the basic idea, research field and applications. And then we expatiate the emergence, definition and research field, and some typical EC methods, e.g. Genetic Algorithm, Evolutionary Strategy, Differential Algorithm are introduced. At last we introduce PSO algorithm, including its original edition and standard edition, summarize its theoretical and applied research. Monte Carlo method is presented to investigate the ability of particles. The results reveal why the PSO has relative poor global searching ability in the last stage of iteration, it also gives the way how to improve the convergence rate of PSO. Furthermore, nine benchmark functions are used to test the performance of PSO and other popular EC algorithms. The results show that the merits of PSO in terms of the fast convergence rate. (2) In spite of PSO has comparable or even superior search performance for many hard optimization problems with faster and more stable convergence rates, but it can’t guarantee to find the global optima in the search space. So the Quantum-behaved PSO (QPSO) algorithm which has power global searching ability than PSO is introduced for improving in this paper. But for QPSO updating the position of particle as whole-item which likes PSO, it also has the problem of the curse of dimensionality. Hence two new hybrid QPSO algorithms with cooperative method (CQPSO and ICQPO) is proposed in this paper for solving this problem. The cooperative method is specifically employed to conquer the “curse of dimensionality”, by splitting a particle with composite high-dimensional into several one-dimensional sub-parts. Nine benchmark functions and Maximization of the measure of separability on the basis of between-class variance method (often called OTSU method), a popular thresholding technique, is employed to evaluate the performance of the proposed method. The experimentIII Abstractresults show that, compared with the exiting EC methods, the cooperative method helps the new PSO algorithm to get more effective and efficient results. It also conquers the curse of dimension of traditional OTSU method. (3) Based on analysis of the global searching ability of PSO, a new global Gaussian PSO (GGPSO) is proposed to overcome the problem of the premature and low precision of the standard PSO. In this algorithm, combining with global and local mutating method finds an excellent balance between global searching and local searching, which is also guaranteed to converge to the global optimization solution with probability one. Experiment simulations show that the proposed algorithm can not only avoid premature effectively but also has powerful optimizing ability, good stability and higher optimizing precision. For solving image segmentation which is the great importance in the field of image processing, we use Kapur function as the optimization object, and the experiments show that the GGPSO algorithm outperforms the compared algorithms especially in maximum the fitness value, so it can applied in image segmentation and optimization problems well. (4) Based on analysis of the convergence of particle swarm optimization (PSO), a new PSO based on improved Moderate Random Searching ability (IRPSO) is proposed to overcome the problem of bad searching ability in the last stage of the standard PSO. It helps the particles have more exploration ability and fast convergence rate. Furthermore, for the improved algorithm only having one parameter and iteration formula, it is simpler than PSO. Experiments show that the proposed algorithm performs much better than the other algorithms in terms of the quality of solution. For solving the problem in image segmentation, we use the difference of mutual information (DMI) as the optimization function, and the experiments show that the IRPSO algorithm gets the better performance of image segmentation among the compared algorithms. Finally, the work of this dissertation is summarized and the prospective of future research is discussed.Keywords: Evolutionary Computation, particle swarm algorithm, image segmentation, convergence rate, the global searching ability, the curse of dimension, Monte Carlo methodIV 目录目摘录要 ......................................................................................................................................... IAbstract .................................................................................................................................... III 第一章 绪 论 ............................................................................................................................ 1 1.1 课题背景 ...................................................................................................................... 1 1.1.1 最优化 ................................................................................................................. 1 1.1.2 最优化方法 ......................................................................................................... 1 1.1.3 基于进化计算求解最优化问题的方法 ............................................................. 3 1.2 课题的目标和意义 ...................................................................................................... 5 1.3 课题的主要研究工作和组织结构 .............................................................................. 6 第二章 优化算法介绍 .............................................................................................................. 9 2.1 优化研究基础 .............................................................................................................. 9 2.1.1 最优化问题 ........................................................................................................ 9 2.1.2 局部优化算法 .................................................................................................. 10 2.1.3 全局优化算法 .................................................................................................. 10 2.1.4 没有免费午餐定理 .......................................................................................... 11 2.2 进化计算 .................................................................................................................... 12 2.2.1 遗传算法 .......................................................................................................... 12 2.2.2 进化策略 .......................................................................................................... 13 2.2.3 进化规划 .......................................................................................................... 14 2.2.4 蚁群算法 .......................................................................................................... 14 2.2.5 微分进化 .......................................................................................................... 15 2.3 本章小结 .................................................................................................................... 16 第三章 粒子群算法分析 ........................................................................................................ 17 3.1 粒子群优化算法 ........................................................................................................ 17 3.1.1 算法原理 .......................................................................................................... 17 3.1.2 算法流程 .......................................................................................................... 18 3.1.3 社会认知行为分析 .......................................................................................... 18 3.1.4 全局模型与局部模型 ...................................................................................... 19 3.2 粒子群改进算法 ......................................................................................................... 19 3.2.1 与其他算法结合 .............................................................................................. 19 3.2.2 基于变异行为的 PSO 改进算法..................................................................... 20 3.2.3 针对粒子群迭代公式的改进 .......................................................................... 21 3.3 标准粒子群算法收敛性分析 .................................................................................... 22 3.3.1 以往 PSO 收敛性分析方法............................................................................. 22 3.3.2 基于蒙特卡罗模拟方法的 PSO 收敛性分析................................................. 23I 目录3.4 粒子群算法与其他进化算法比较及分析 ................................................................ 25 3.4.1 各种进化算法性能比较 .................................................................................. 25 3.4.5 比较结果分析 .................................................................................................. 29 3.5 PSO 算法应用............................................................................................................. 30 3.6 本章小结 .................................................................................................................... 31 第四章 基于协作方法的量子粒子群算法及其在图像分割的应用 .................................... 32 4.1 引言 ............................................................................................................................ 32 4.2 量子粒子群算法 ........................................................................................................ 32 4.3 基于协作方法的量子粒子群方法 ............................................................................ 33 4.3.1 协作方法 ........................................................................................................... 33 4.3.2 精英策略 .......................................................................................................... 35 4.3.3 仿真结果比较及其分析 .................................................................................. 36 4.4 基于 CQPSO 算法的图像分割应用 .......................................................................... 38 4.4.1 图像分割概述 .................................................................................................. 38 4.4.2 OTSU 分割算法 ............................................................................................... 39 4.4.3 计算步骤 .......................................................................................................... 39 4.5 基于 CQPSO 的最大类间方差图像分割 ................................................................. 40 4.5.1 算法描述 ........................................................................................................... 41 4.5.2 算法测试 .......................................................................................................... 41 4.6 本章小结 .................................................................................................................... 55 第五章 一种全局收敛的 PSO 算法及其在图像分割中的应用 ............................................ 58 5.1 引言 ............................................................................................................................ 58 5.2 基于 Gaussian 变异的 PSO 算法 ............................................................................... 58 5.2.1 引入 Gaussian 变异的粒子群算法 .................................................................. 58 5.2.2 GGPSO 算法 ..................................................................................................... 60 5.2.3 GGPSO 算法收敛性分析 ................................................................................. 61 5.3 比较实验及分析 ......................................................................................................... 63 5.3.1 试验设计 ........................................................................................................... 63 5.3.2 仿真结果及分析 ............................................................................................... 63 5.4 基于 GGPSO 方法的图像分割应用 .................................................................. 66 5.4.1 算法描述 ........................................................................................................... 67 5.4.2 算法测试 ........................................................................................................... 67 5.5 本章小结 ..................................................................................................................... 73 第六章一种基于随机搜索策略的粒子群算法 ...................................................................... 74 6.1 引言 ............................................................................................................................ 74 6.2 基于适度随机搜索策略的 PSO 算法........................................................................ 74 6.3 对比试验 ..................................................................................................................... 76II 目录6.3.1 试验设计 ........................................................................................................... 76 6.3.2 仿真结果比较分析 ........................................................................................... 76 6.4 IRPSO 算法针对图像分割问题的比较试验............................................................ 78 6.5 本章小结 ..................................................................................................................... 83 第七章 结束语 ........................................................................................................................ 85 致 谢 ...................................................................................................................................... 87 参考文献 .................................................................................................................................. 88 附录： 作者在攻读博士学位期间发表的论文 .................................................................... 96III
第一章 绪 论第一章 绪 论1.1 课题背景1.1.1 最优化 最优化已经成为了一个使用非常广泛的术语， 最优化的概念反映了人类实践活动中 十分普遍的现象。最优化是一个重要的数学分支，是一门应用性强、内容丰富的学科。 例如，工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能降低成本；资 源分配中，怎样分配有限的资源，使得分配方案既能满足各方面的基本要求，又能获得 好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润。在人类活 动的各个领域中， 诸如此类， 不胜枚举。 这些问题在某种程度上都可以称为最优化问题。 最优化的目的是对于给出的实际问题，从可行的解决方案中找出最好或较好的解决方案 来， 即要在尽可能节省人力、 物力和时间的前提下， 争取获得在可能范围内的最佳效果。 最优化问题可以追溯到十分古老的极值问题，早在 17 世纪，英国科学家 Newton 发明微积分的时代，就已提出极值问题，后来又出现了 Lagrange 乘数法。1847 年法国 数学家 Cauchy 研究了函数值沿什么方向下降最快的问题， 提出了最速下降法。 1939 年 前苏联数家Л .В . К а н т о р о в и ч 提出了解决下料问题和运输问题这两种线性 规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但 是，任何科学的进步都会受到历史条件的限制。直至 20 世纪 30 年代，最优化这个古 老的课题并未形成独立的系统学科。 20 世纪 40 年代以来，随着生产活动和科学研究地不断发展，特别是计算机技术 的高速发展和广泛使用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的 有力工具。因此各种优化理论研究发展迅速，新方法不断出现，实际应用日益广泛。而 且在计算机技术的推动下，一些超大规模的优化问题也得以实现，最终使得优化理论与 方法在经济规划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十 分活跃的学科[1]。 一般来说，最优化问题可以表示为：ì g (x ) ? 0, i 1,..., m ? i ? ? min f (x ) ，s.t . ? h j (x ) = 0, j = 1,..., l í ? ? x? X ? ? ?（1.1.1）其中， x ? R n 是决策变量， f (x ) 为目标函数，X 为可行域， gi (x ) 、h j (x ) 为约束函 数， gi (x ) 称为不等式约束， h j (x ) 称为等式约束。 1.1.2 最优化方法 为了达到最优化的目标所提出的各种求解最优化问题的方法称为最优化方法。 最优 化方法是一个以数学为基础的重要的科学分支，它一直受到人们的广泛重视，并在许多1 江南大学博士学位论文工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机 工程等。它对促进运筹学、管理科学、控制论和系统工程等新兴学科的发展起到了重要 的作用。 最优化方法在实践中的应用可以分为最优设计、最优计划、最优管理和最优控制等 四个方面[1]。最优设计: 在飞机、造船、机械、建筑等工程技术界都已广泛应用最优化 方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使 许多设计优化问题得到解决。电子线路的最优设计是另一个应用最优化方法的重要领 域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机 辅助搜索最佳配方、配比方向发展。一个新的发展动向是最优设计和计算机辅助设计相 结合。最优计划：在编制国民经济和部门经济的计划和农业、交通、能源、环境、生态 规划中，在编制企业发展规划和年度生产计划中应用最优化方法的过程称之为最优计 划。一个重要的发展趋势是帮助决策部门进行各种优化决策。最优管理：在企业日常生 产计划的制订、生产经营的管理和运行中，通过计算机管理系统和决策支持系统等辅助 工具的建立和使用，运用最优化方法进行经营管理的过程称为最优管理。在经济管理学 上就是在一定人力、物力和财力资源条件下，使经济效果（如产值、利润等）达到最大， 并使投入的人力和物力达到最小的科学方法。最优控制：主要用于对各种控制系统的优 化。例如，导弹系统、卫星系统、航天飞机系统、电力系统等高度复杂系统中运用最优 化方法。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制 创造了有利条件。 最优控制的对象也将从对机械、 电气、 化工等系统的控制转向对生态、 环境以至社会经济系统的控制。 求解最优化问题的最优化方法有多种形式。 不同类型的最优化问题可以有不同的最 优化方法，同一类型的最优化问题也可有多种最优化方法。某些最优化方法可适用于不 同类型的最优化问题， 针对相同的最优化问题， 不同的最优化方法具有不同的优化特性。 有些最优化方法可以快速求解到局部最优解，有些优化方法具有很好的全局寻优特性。 一般来说，求解最优化问题的理想情况是快速有效的得到全局最优解。当然，由于对最 优化问题的性质和最优化方法认识的不足，这种情况只能在有限的条件下实现。对于复 杂函数最优化问题,一般很难找到收敛性好且全局最优的最优化方法。 一般来说，求解最优化问题可以分为以下几个步骤： ⑴ 提出需要进行优化的问题； ⑵ 建立求解优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件； ⑶ 分析模型，选择合适的最优化方法； ⑷ 求解方程； ⑸ 最优解的验证和实施。 显然，在最优化问题的数学模型建立后，主要问题是如何通过不同的求解方法解决 寻优问题。最优化问题的数学求解方法一般可以分成解析法、直接法、数值计算法等几 类[2,3]：2 第一章 绪 论解析法：对于目标函数及约束条件有简单而明确的解析表达式的非线性优化问题， 通常可采用解析法来求解。解析法的求解方法是先按照函数极值的必要条件，用数学分 析的方法（求导或变分法）求出其解析解，然后按照充分条件或问题的实际物理意义间 接地确定最优解，因此也称间接法。这类方法主要用来解决动态优化问题。其中经典变 分法用来求解无约束动态优化问题；极大（极小）值原理和动态规划主要用于求解有约 束的动态优化问题。另外，经典微分法可用于求解静态优化问题。 直接法： 当目标函数较为复杂或者不能用变量显函数描述或无法用解析法求必要条 件时通常可采用直接法来解决。 直接法的基本思想是用直接搜索的方法经过一系列的迭 代以产生点的序列，使之逐步接近到最优点。这种方法常常是根据经验或通过试验得到 所需要的结果，直接法可以分为函数逼近法、区间消去法和爬山法。对于一维搜索(单 变量极值问题)，主要用消去法或多项式插值法，对于多维搜索问题(多变量极值问题) 主要用爬山法。 数值计算法：这种方法也是一种直接法，是以梯度法为基础的。它是一种解析与数 值计算相结合的方法。这类方法主要用于多变量的寻优问题。其中最速下降法、共轭梯 度法、牛顿法与拟牛顿法、变尺度法和牛顿-高斯最小二乘法等适用于多变量无约束的 优化问题。解决多变量约束的优化问题通常也采用以解析法为基础的数值解法，这类方 法很多，大致可分为以下三种类型：一是将有约束的优化问题转化为一系列无约束的优 化问题，然后采用无约束优化方法来求解，这种方法称为变换算法或序列无约束极小化 方法，如拉格朗日乘子法和惩罚函数法；二是采用一系列线性或二次规划问题的解来逼 近原非线性约束问题的解，这种方法称为线性近似化技术，如序列线性规划化、割平面 法和序列二次规划化；三是直接处理约束条件，研究在约束边界处如何搜索以获得使目 标函数值逐步改善的可行点列，最后趋近约束问题的极小值点，这种方法称为可行方向 法、梯度投影法和简约梯度法。 用数学方法求解优化问题的历史相对悠久，当前仍然在不断的发展过程中。这些传 统的方法大多是针对某些特定问题的，并且对搜索空间要求相对严格，有些方法还需要 使用被优化函数的各阶导数信息。但是，随着科学技术的发展，优化问题也变得更加复 杂。如工程优化所建立的数学函数,往往是带有多种约束条件的复杂函数,而且大部分是 不连续、 不可微的隐函数。 对于这些复杂函数来说,用常规的数学方法很难或根本无法处 理。有些问题甚至无法用函数关系来表达，对于这类问题，采用上述方法，不可能得到 圆满的结果。因此，需要进一步研究和探索新的优化思想和优化方法。 1.1.3 基于进化计算求解最优化问题的方法 承上所述，随着科学技术的发展，实际的优化问题也变得越来越复杂。优化问题表 现出了复杂性、约束性、非线性、多极小、建模困难等特点，因此常规的求解方法已很 难适用，寻求一些新的优化技术成为一个重要研究目标和引人注目的研究方向。 20 世纪 80 年代以来，进化计算作为一类通过模拟生物进化过程与机制来求解问 题的优化技术，为解决复杂优化问题提供了新的思路和方法，近年来受到了人们极大关 注。进化计算采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单3 江南大学博士学位论文的进化操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于采用种群的方式 组织搜索，这使得进化计算可以同时搜索解空间的多个区域，而且用种群组织搜索的方 式也使得进化计算特别适合大规模并行操作。在赋予进化计算自组织、自适应、自学习 等特征的同时， 优胜劣汰的自然选择和简单的进化操作使进化计算具有不受其搜索空间 限制条件（如可微、连续、单峰）的约束及不需要其它辅助信息（如导数）的特点。 基于进化计算求解优化问题的一般步骤为： ⑴ 随机给定一组初始解； ⑵ 评价当前这组解的性能； ⑶ 按照一定的方法选出性能优良的解作为进化操作对象； ⑷ 对选出的解进行进化操作（如交叉、变异等）得到新一代解； ⑸ 评价当前新一代解的性能，如果满足要求或进化过程达到一定代数，过程 结束，否则转到 ⑶。 对于复杂优化问题的求解，进化计算有实用性、通用性、灵活性强、效率高等特点， 能在更多的情况下求得有用的(即近似的、次优的和在精度许可范围内的)解。与传统数 学方法相比，基于进化计算方法有如下特点[4]： ⑴ 进化计算的处理对象可以是参数本身， 也可以是经过某种映射形成的特定编码， 编码形式可以是矩阵、树、图、集合、串、序列、链和表等。这个特点使进化计算有广 泛的应用领域，尤其是对多目标、大规模、高维数、非线性以及带有不可转化约束条件 的复杂优化问题，具有更强的适应性。 ⑵ 进化计算通过策略、参数、操作以及算子的调整，能够很快提高寻优求解的性 能，更重要的是进化计算能够通过自身的改良以及同其它方法的交叉融合，在较短的时 间内快速进化，这一点体现了进化计算的灵活性。 ⑶ 进化计算采用群体搜索策略，而传统方法多采用单点搜索策略，这种特点使进 化计算具有极好的全局性，减少陷入局部最优的风险；同时，也使进化计算本身易于大 规模并行实现，可充分发挥高性能计算机系统的作用。 ⑷ 进化计算具有高效的特点，不是说在拥有同等计算资源时，求解优化问题肯定 都比传统方法快(从整体上讲，在近年来多数工程应用中的效率确实高出传统算法，否 则，进化计算的发展速度也不会突飞猛进)，更多的是指能够更充分挖掘计算机的潜力， 比如容易实现并行寻优求解(通过占用更多的冗余计算资源来实现速度的提高)。 ⑸ 进化计算基本不依赖搜索空间的知识及其他辅助信息，它采用适应度函数来评 价个体，并在此基础上驱动进化过程，而对适应度函数本身无特别严格要求。而传统方 法则要求函数有诸如连续、 可微或空间凸性等条件。 这使进化计算有更广泛的应用范围。 ⑹ 进化计算用概率的变迁规则来控制搜索的方向，表面上看好像是在盲目搜索， 实际上它遵守某种随机概率，在概率意义上朝最优解方向靠近，因此，它不像通常采用 确定性规则的传统方法，需要构造合适的下降方向。 二十世纪七十年代以来，一些与经典优化方法不同的的进化计算方法相继被提出， 其中包括遗传算法[5,6]、蚁群算法[7]、粒子群算法[8,9]以及微分进化算法[10,11]。其中粒子群4 第一章 绪 论算法是近年来提出的一种简单而高效的进化算法。由于它容易理解、易于实现，所以发 展十分迅速，在很多领域得到了成功应用。由于图像分割是图像分析和模式识别的首要 问题，也是图像处理的经典难题之一，它是图像分析和模式识别系统的重要组成部分， 并决定图像的最终分析质量和模式识别的判别结果。因此本文针对基于 PSO 的图像分 割算法进行了研究，提出了多个新的解决这类优化问题的算法。1.2 课题的目标和意义粒子群优化算法有些与遗传算法相似，如它们都是基于群体的优化技术，有较强的 并行性无需梯度信息，只需利用目标的取值信息，具有很强的通用性。但是，粒子群算 法比遗传算法更简单、操作更方便。因而，粒子群算法从诞生起，就引起了国内外学者 的广泛关注，掀起了该方法的研究热潮，己经广泛应用于函数优化、神经网络训练、模 糊系统控制[12]等领域。近年来进化算法已成为分布式人工智能研究的一个重要领域，在 美国成立有专门的组织研究群体的仿真；由欧洲联盟资助的进化算法相关研究项目也于 2001 年在欧洲多个研究机构启动；在国内，国家自然科学基金“十五”期间学科交叉 类优先资助领域中，认知科学及其信息处理的研究内容就明确列出了群体智能的进化、 自适应与现场认知、相关项目以及复杂系统与复杂性。它的主要研究方向及内容是复杂 系统与复杂性的理论与方法研究； 物质层次复杂系统的研究； 生命层次复杂系统的研究： 社会层次复杂系统的研究。2001 年 3 月 8 日在北京召开的第六届全国人工智能联合会 议暨“863”计划智能计算机主题学术会议，戴汝为院士特邀报告的主要内容就是进化 算法的研究进展。到现在，国家自然科学基金委员会每年都有资助数项粒子群优化算法 相关理论和应用的研究。 国际上， 每年召开的顶级国际会议中以进化算法为主题的会议主要有美国计算机协 会（Association of Computing Machinery）每年举行的基因与进化计算国际会议（Genetic and Evolutionary Computation Conferences） ，IEEE 计算智能协会（IEEE Computational Intelligence Society） 每年举行一次的进化计算国际会议 （IEEE Conference on Evolutionary Computation）以及自 2003 年起每年举行一次群体智能会议（IEEE Swarm Intelligence Symposium） 。其中粒子群优化算法是这些会议的重要主题。 PSO 自 1995 年提出以来，由于其简单和明确的实际背景，以及前述的诸多优点， 使得很多研究者加入到对这种算法的研究中，目前粒子群优化算法的理论研究与应用研 究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不 同学科中得以实现。这些研究主要集中在如下几个方面： （1）粒子群优化算法的理论分析 具体来说，这个问题的研究分为三个方面：一是单个粒子的运动轨迹，现有的研究 发现，单个粒子不断的在各种正弦波上“跳跃” ，即其轨迹是各种正弦波的随机的叠加 组合，这里所用的主要工具是微分方程和差分方程[12]；二是收敛性问题，关于粒子群算 法的收敛性研究比较多的集中在一些简化条件下的结果，采用的主要工具是动态系统理 论。其它还有采用集合论的方法来研究此问题，得出的结论是[13]：在没有任何改进的情5 江南大学博士学位论文况下，原始的粒子群优化算法既不能收敛到全局极值点，也不能收敛到局部极值点，但 是这种证明是非构造性证明，对于理解算法的工作原理没有太大帮助。三是整个粒子系 统随时间的演化和分布，这方面的研究目前还少有人涉及。 （2）粒子群优化算法的改进 这方面的内容非常庞杂，从改进的策略来说，可以分为如下几种类型，一是从算法 本身的改进，例如对算法迭代式的改进[14]，或对算法参数的优化[15]优化函数的形状。以 上这些方法，从根本上说，主要是为了克服粒子群优化算法在优化多峰复杂函数时，会 出现早熟，粒子的多样性减低，以致于不能收敛到全局极值点的现象。 （3）粒子群优化算法的应用 粒子群优化算法的应用已经扩展到很多领域，从最初的复杂多峰非线性函数的优 化、多目标优化等传统问题，到电力系统的分析，动态系统的跟踪与优化、神经网络的 权值训练并将其用于复杂系统的建模，非线性系统的优化控制问题等等。算法研究的目 的如何将粒子群算法应用于更多领域，同时研究应用中存在的问题也非常值得关注。 但是，算法的发展历史尚短，在理论基础与应用推广上都还存在以下问题。 1. 算法理论研究不深入，无法彻底剖析算法行为。算法收敛模型的建立和收敛性 的分析是算法基础，目前收敛模型的建立和收敛性的分析都困难。 2. 关于算法早熟收敛的问题。算法应用于高维或超高维复杂问题优化时，往往会 遇到早熟收敛的问题，也就是种群在还没有找到全局最优点时已经聚集到一点 停滞不动。早熟收敛不能保证算法收敛到全局极小点，这是由于算法早期收敛 速度较快，但到寻优的后期，其结果改进则不甚理想，即缺乏有效的机制使算 法逃离极小点。因而，算法早熟收敛研究也是一个值得的研究问题。 3. 由于目前大部分改进的 PSO 算法都不同程度的增加了算法的时间或空间复杂 度，如何在提高算法性能的同时精简算法的迭代流程是广大学者研究的方向。 4. 关于算法的应用局限性问题。对任何一个算法，有自己的应用局限性，算法也 不例外。它如何克服自己的应用局限性，如何结合其它算法去解决实际问题， 也是大量学者研究的课题。 针对上述问题，本文展开了细致的研究，对不同问题提出了相应的改进。并将改进 的算法应用到图像分割领域。1.3 课题的主要研究工作和组织结构在本论文中，根据提出的问题，对算法进行了较为深入的研究。本文的主要研究内 容与创新点可归纳如下： 1 针对本课题组推出的 Quatum-behaved PSO(QPSO)存在的对于高维函数寻优困难 的缺点，提出了一种基于协作方法的 Cooperative QPSO(CQPSO)算法。该方法通过把优 化的解空间细化为每一个单维优化的目标，从而有效的解决了高维函数的优化问题；另 外，针对协作方法存在的时间复杂度高的问题引入了适应度比例方法，使参与协作方法 的粒子仅为选择后的粒子，有效的解决了时间消耗过大的缺点。6 第一章 绪 论2 由于有关粒子群性能的分析都是把粒子群迭代公式中的随机量作为常量在收敛性 分析中进行考察，并没有反映出随机变量对于粒子速度的影响。而这两项是影响 PSO 算法随机性的最重要两个参数， 因此有必要对它们的作用进行详细的测试进而考察粒子 群的运动轨迹。 由于传统的概率论等数学分析方法难以细致的考察随机量在迭代过程中 的变化， 因此本文引入蒙特卡罗模拟方法详细的对粒子进化轨迹进行了考察从而分析出 粒子群收敛速度快以及早熟收敛的原因，为进一步对标准 PSO 算法进行改进提供了方 向。 3 针对目前 PSO 算法早熟收敛的缺点目前国内外主要通过添加变异因子的方法来改 善粒子的全局以及局部搜索能力， 但如何协调变异粒子的全局以及局部搜索能力却一直 没有得到很好的解决。本文针对以往变异算法的缺陷，提出了一种基于高斯变异的 PSO 算法，该算法有效的结合了全局以及局部变异因子的优点，在收敛速度以及全局搜索能 力上得到了一种很好的平衡，使得改进以后的算法不仅在收敛速度上得到了很大的提 高，而且保证改进以后的算法具有全局收敛的特性。 4 由于目前大部分改进的算法都是在 PSO 算法上添加了一定的因子或者是对 PSO 算法的参数进行调节，而不是对 PSO 算法根本上的改进。本文提出了一种基于随机搜 索策略的 PSO 算法，该算法不仅在收敛速度上以及寻优精度上优于同类比较算法，而 且相对于 PSO 算法来说它只有一个迭代公式以及控制因子，因此更为简单高效，更适 合在多种领域进行应用推广。 5 针对目前热点的图像分割问题结合粒子群算法收敛速度快的优点，在有效改善粒 子群局部收敛的缺点的前提下，把改进以后的粒子群算法有效的引入了 OTSU 分割算 法、Kapur 分割算法以及互信息量分割算法。同比其他优化算法，改进的算法精度更高， 效率更好，稳定性更强。 具体地，本课题内容共分七个章节展开： 第一章介绍本课题的研究背景，并概述本课题的主要研究工作。 第二章对优化算法和进化算法进行了介绍。 第三章主要对 PSO 算法以往收敛性分析进行了总结，同时针对以往收敛性分析方 法的缺点提出了基于蒙特卡罗模拟方法的分析方法。同时在本章对于当前流行的多种进 化算法针对大量的测试函数进行了测试。 第四章针对 QPSO 算法中粒子寻优受到维数限制的缺点， 提出了一种基于协作方法 的 QPSO 算法。同时把该算法与图像分割中的大律法（OTSU）结合起来，有效的解决 了标准 OTSU 方法寻优效率低的缺点。 第五章在分析了以往基于变异因子的 PSO 算法的优缺点的基础上，提出了一种基 于高斯变异的全局收敛的 PSO 算法，同时对于该算法的收敛性进行了证明。另外结合 图像分割中的 Kapur 算法验证了该算法高效可行。 第六章提出了一种简化的 PSO 算法，该算法不仅在收敛速度以及寻优能力上优于 同类比较算法，而且只有一个迭代公式和控制参数。另外结合图像分割中的互信息量方 法验证了该算法简单高效。7 江南大学博士学位论文第七章对全文进行了总结，并对进一步研究做了展望。8 第二章 优化算法介绍第二章 优化算法介绍粒子群算法主要应用于优化问题，但它起源于社会认知科学，因此，本章首先阐述 与算法相关的优化概念和技术。其次，针对当前比较热点的几种优化算法进行了比较和 讨论。以上内容将为后面算法改进和研究提供了必不可少的基础。2.1 优化研究基础优化是科学研究、工程技术和经济管理等领域的重要研究工具。它所研究的问题是 讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数，使设计方案 既满足设计要求又能降低成本资源分配中，怎样分配有限资源，使分配方案既能满足各 方面的基本要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜 枚举。优化这一技术，正是为这些问题的解决，提供理论基础和求解方法，它是一门应 用广泛、实用性很强的科学。 2.1.1 最优化问题 最优化问题是一种在可接受时间限制内对一个优化目标寻找最小值的问题 （寻找最 大值问题可以通过数学方法转化为寻找最小值问题）[16]。它对于很多领域的研究问题都 至关重要，例如：物理、化学以及工程领域等。这些领域的科学研究者不得不考虑在工 业以及社会资源的优化分配问题。一些问题仅仅包含线性优化问题，其他的一些问题则 为比较难以解决的非线性优化问题。最优化问题根据其目标函数、约束函数的性质以及 优化变量的取值等可以分成许多类型，每一种类型的最优化问题根据其性质的不同都有 其特定的求解方法，在本文中主要考虑非约束非线性优化问题。不失一般性，最小化问 题可定义为： 定义 2.1 如果存在 x W(P )量。min{ f (x ) : x W WR n }, f :彤R nRl（2.1）其中 f (x ) 为目标函数，W为可行解空间，R n 为整个 n 维欧式空间，x 为 n 维优化变 当 f (x ) 为线性函数，上述最优化问题即为线性规划问题，其求解方法有成熟的单纯 形法和 Karmarc 方法。当 f (x ) 中为非线性函数时，上述问题即为非线性规划题。非线性 规划问题相当复杂， 其求解方法多种多样， 但到目前仍然没有一种适合所有问题的方法。 非线性规划问题包括无约束优化问题和约束优化问题，由于函数的非线性，使得问 题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线 性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约 束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。总的 说来，求最优解或近似最优解的方法主要有三种枚举法、启发式算法和搜索算法。9 江南大学博士学位论文（1）枚举法。枚举出可行解空间内的所有可行解，以求出精确最优解。对于连续 问题，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最 优解。另外，当枚举空间比较大时，该方法的求解效率比较低。 （2）启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近 似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特 有的启发式规则，这种启发式规则无通用性，不适合于其他问题。 （3）搜索算法。该算法在可行解空间的一个子空间内进行搜索操作，以找到问题 的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地 利用一些启发知识，就可近似解，同时解的质量和求解效率达到一种较好的平衡。 搜索算法可分为两大类平行搜索法 （simultaneous methods） 和序贯搜索法(sequential methods)作平行搜索时，需要计算目标函数值的自变量节点位置在事先一起选定。而作 序贯搜索法时则根据前一轮计算得到的目标函数值的情况用以确定下一轮计算目标函 数值的自变量节点位置，因此它带有迭代性。搜索算法又可分确定性搜索法和随机性搜 索法两种。确定性搜索算法在寻优过程中，一个搜索点到另一个搜索点转移有确定的转 移方法和转移关系，因而其过程可再现，其不足在于寻优结果与初值有关，初值选取不 当往往有可能使搜索永远达不到最优点。随机性算法在算法执行过程中加入随机性因为 真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数，需计 算算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，但它的准确率 略微降低。 2.1.2 局部优化算法 定义 2.2 如果存在 x * ? B ，使得对 & xf x * Ｎ f (x ),B 都有：( )xB(2.2)成立，其中 B 烫SR n 。则称 x * 为 f (x ) 在 B 内的局部极小点。 f (x ) 为局部极小值。常见的优化方法大多为局部优化方法，都是从一个给定的初始点开始，依据一定的 方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟的局部 优化方法很多，如 Newton-Raphson 法、共扼梯度法、Fletcher-Reeves 法、Polar-Ribiere 法等，还有专门为求解最小二乘问题而发展的 Leven-berg-Marquardt(LM)算法。所有这 些局部优化算法都是针对无约束优化问题而提出的，而且对于目标函数均有一定的解析 性质要求，如 Newton-Raphson 法要求目标函数连续可微，同时要求其一阶导数连续。 对于约束非线性优化问题， 除了根据一阶最优化必要条件直接将最优化问题转换为 非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性 规划法、可行方向法、拉格朗日乘子法等。最常用的方法是将约束问题通过罚函数法转 换为无约束优化问题，然后再采用无约束优化方法进行求解。 2.1.3 全局优化算法 定义如果存在 x * ? S ，使得对 & xS ，有：10 第二章 优化算法介绍f x * Ｎ f (x ),( )xS成立，其中 S 为由约束条件限定的搜索空间，则称 x * 为 f (x ) 在 S 内的全局极小点，f (x ) 为其全局极小值。 到目前为止，全局优化问题也已存在了许多算法，如填充函数法等，但比起局部优 化问题的众多成熟方法，其间还有很大差距。 另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标 函数不连续、约束域不连通、目标函数难以用解析函数表达或者难以精确估计（如仿真 优化问题）等问题时，解析确定性优化方法就难以适应。 为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨 对函数解析性质要求较低甚至不做要求的随机型优化方法。最早的随机型优化方法是基 于 Monte-Carlo 方法的思想，针对具体问题性质的特点，构造以概率 1 收敛于全局最小 点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法，是近十多年来人 们模拟自然界的一些自然现象而发展起来的一系列仿生型智能优化算法，如禁忌搜索算 法，模拟退火算法、进化类算法、群体智能算法等。 2.1.4 没有免费午餐定理 最优化理论的发展之功是 Wolpert 和 Macready 提出了没有免费的午餐定理， 简称(No Free Lunch Theorem, 简称 NFL)[17，18，19]。NFL 定理的简单表述为对于所有可能的问题， 任意给定两个算法 A、B，如果 A 在某些问题上表现比 B 好（差） ，那么在其他问题上 A 的表现就一定比 B 差（好） ，也就是说，任意两个算法 A、B 对所有问题的平均表现 度量是完全一样的。该定理暗指，没有其它任何算法能比搜索空间的线性列举或者纯随 机搜索算法更优。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚 不清楚。在计算机上实现的搜索算法都只能在有限的搜索空间实施，所以该定理对现存 的所有算法都可直接使用。 NFL 定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。 虽然定理 是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本质。当我们 所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法间所表现出的效 应，即若算法在某些函数上 A 的表现超过 B 算法，则在这类的其他适应值函数上，B 算法的表现就比 A 要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在 整个函数类上的平均表现度量是一样的。 有了上述讨论， 关于优化算法的研究目标就应该从寻找一个大的函数类上的优化算 法转变为: (1)以算法为导向，从算法到问题。对于一个小的特定的函数集，或者一个特定的实 际问题，给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一 个“指示性”的算法。 (2)以问题为导向，从问题到算法。对于一个小的特定的函数集，或者一个特定的实 际问题，可以设计专门适用的算法。11 江南大学博士学位论文实际上，大多数在进化算法方面的研究工作可以看作是属于这一范畴的，因为它们 主要是根据进化的原理设计的算法，或者将现有算法进行部分改进，以期对若干特定的 函数取得最好的优化效果，这也是本文研究的一个重要基础。2.2 进化计算近十年来， 遗传算法 （Genetic Algorithm, GA 算法） 进化策略 、 （Evolutionary Strategy, ES） 、微分进化（Differential Evolution, DE） 、进化规划（Evolutioary Programming, EP） 等进化类算法在理论和应用两方面发展迅速、效果显著，并逐渐走向了融合，形成了一 种新颖的模拟进化的计算理论，统称为进化计算（Evolutionary Computation, EC） 。进化 计算的具体实现与形式称为进化算法（Evolutionary Algorithm, EA） ，进化算法是一种受 生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具 有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。 2.2.1 遗传算法 遗传算法最早是由美国 Michgan 大学的 J. Holland 博士提出的，1975 年，他出版了 其开创性的著作”Adaptive in Natural and Artificial Systems” 诞生。 遗传算法的操作对象是一组二进制串，即种群(Population)。每一个二进制位串被称 为染色体(Chromosome)或个体(individual)，每个染色体或个体都对应于问题的一个解。 从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，并使用交叉 (Crossover)和变异(Mutation)来产生下一代种群，如此一代一代进化下去，直至满足期望 的终止条件。 遗传算法可以形式化描述为：[20]，标志着遗传算法的正式GA = P (0), N , I , S , g, p, f ,t())1N ，表示初始种群。其中， P (0) = a1 (0), a 2 (0),..., a N (0)(I = B l = {0,1}表示长度为 l 的二进制串全体，称为位串空间。N 表示种群含有的个体数目，即群体规模。 l 表示二进制串的长度。S : I N ? I N 表示选择策略。g 表示遗传算子，通常它包括选择算子，交叉算子和变异算子。 p 表示遗传算法的操作概率，包括复制概率 pr ，交叉概率 pc 。和变异概率 pm 。f : I ? R n 是适应值函数。t :IN ?{0,1} 是终止条件。有关遗传算法的研究已相当丰富，包括编码方案、遗传算子的设计以及操作概率的 自适应性控制策略等，各种各样的改进算法层出不穷，其应用范围几乎可以涉及优化问 题的所有领域，有关遗传算法方面的专著在国内外也出现了很多。12 第二章 优化算法介绍2.2.2 进化策略 进化策略（Evolutionary Strategy， ES）是由德工业大学的 I. Rechnberg 和 H. P. Schwefel[21]等在 20 世纪 60 年代初提出的。早期的演化策略，其种群中只包含单个个体 且只使用变异操作。具体在每一操作代中，变异后的个体与其父代个体进行比较，从中 择优选取作为新一代个体，这就是所谓的策略。它所使用的变异算子主要是基于正态分 布的变异操作。 由于 (1 + 1) 策略难以收敛到最优解，且搜索效率相对较低。其改进的方法就是增加 种群内个体的数量。此时种群内含 u 个体，随机抽取一个个体进行变异，然后取代群体 中最差的个体。为了进一步提高搜索效率，后来又提出了 (u + l ) 进化策略和 (u , l ) 进化 策略。(u + l ) 进化策略是根据种群内的 u 个个体采用变异和重组产生 l 个个体，然后将 这 u + l 个个体进行比较选择 u 个最优者； (u , l ) 进化策略则是在新产生的 l (? u ) 个个 而 体中比较 u 最优者。 进化策略与遗体算法相比， 其主要不同之处在于遗传算法是将原问题的解空间映射 到位串空间上，然后再进行遗传操作，它强调的是个体基因结构的变化对其适应度的影 响，而进化策略则是直接在解空间上进行遗传操作，它强调的是父代到子代行为的自适 应性和多样性。 (u + l ) [22]的算法描述如下： 1.初始化：在解空间 W中均匀分布随机选取 u 个点 x 1 (0), x 2 (0),..., x u (0) 。这样得到 初始种群 X (0) = x 1 (0), x 2 (0),..., x u (0) ，置 k := 0 2.产生中间种群：执行 l 步（ l ? u ） 。 2.1 置 i := 1 。 2.2 以等概率从 X (k ) 中选取两个个体 x i 1 (k ) ， x i 2 (k ) 。^{}2.3 以杂交算子作用于 x i 1 (k ) ， x i 2 (k ) 以产生中间个体 x u + i (k ) ，其中杂交算子 为中间杂交，即：^x u + i (k ) = x i 1 (k ) + x i 2 (k ) / 2^()2.4变异：令x u + i (k ) = x u + i (k )/ 2，其中D x ~ N (0, s ) = N (0, s 1 ), N (0, s 2 ),..., N (0, s n ) ， N (0, s i ) 表示均值为 0，方差为 s i2 的正态分布，且 D x 的 n 个分量 D x 1, D x 2,..., D x n 之间相互独立。 2.5 若 x u + i (k ) W ，转 2.6；否则转 2.4. 2.6 若 i = l ，转步骤 3；否则置 i:=i+1,转 2.2.()T13 江南大学博士学位论文3.选择：从 x 1 (k ), x 2 (k ),..., x u + l (k ) 中选取 u 个函数值最小的个体组成新一代种群X (k + 1) = x 1 (k + 1), x 2 (k + 1),..., x u (k + 1) 。{}{}4. 终止检验：检验当前种群 X (k + 1) 是否产生满意解或已达到预设的进化时限， 若满足则停止；否则置 k := k + 1 ，转步骤 2. 2.2.3 进化规划 进化规划（Evolutionary Programming， EP）方法最初是由美国科学家 Lawrence J. Fogel 等人在 20 世纪 60 年代提出的[23, 别很小。 进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化 策略的变异相类似，也是对父代个体采用基于正态分布的操作进行变异，生成相同数量 的子代个体，即 u 个父代个体总共产生 u 子代个体。EP 采用一种随机一竞争选择方法， 从父代和子代的并集中选择出 u 个体构成下一代群体。其选择过程如下：对于由父代个 体和子代个体组成的大小为 2u 临时群体中的每一个个体， 从其他 2u - 1 个个体中随机等 概率地选取出个个体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较 的个体的适应值，则称该个体获得一次胜利。从 2u 个个体中随机等概率地选取出 q 个个 体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较的个体的适应值， 则称该个体获得一次胜利。 2u 个个体中选择出获胜次数最多的 u 个个体作为下一代群 从 体。 2.2.4 蚁群算法 蚁群算法[26, 27](AntC olonyA lgorithm ,ACA)是一种最新发展的模拟真实世界蚂蚁觅 食行为的仿生优化算法。1991 年，意大利学者 Dorigo M 在巴黎召开的第一届欧洲人工 生命会议(European Conference on Artificial Life. ECAL)最早提出了蚁群算法的基本思想; 1992 年，DorigoM 又在其博士论文中进一步阐述了蚁群算法的核心思想。 根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索的模型， 蚁群算法对搜索空间的“了解”是从观察蚁群觅食活动从中启发而建立的机制，主要包 括三个方面。 （1）蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会被选择，由此在蚁 群算法中建立 tabu(禁忌)列表来进行模拟 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信息 素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成 为蚂蚁之间进行通讯的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜 索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越 来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路 径的信息素强度，而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移1424, 25]。它在求解连续参数优化问题时与 ES 的区 第二章 优化算法介绍而蒸发。因此，模拟这种现象从而利用群体智能建立的路径选择机制，使蚁群算法的搜 索向最优解推进. 下面就以求解 n 个城市的 TSP 问题为例，介绍基本蚁群算法的实现步骤: 先作如下假设，令有 m 只蚂蚁， d ij (i,j=1,2 二 n)表示城市 i 和 j 之间的距离， t ij 表 示 t 时刻在 ij 连线上残留的信息量。 (1 ) 参数初始化。令时间 t=0 和循环次数 Nc=O， 设置最大循环次数 Ncmax， 将 m 个蚂蚁置于 n 个城市上， 令有向图上每条边 (i , j ) 的初始化信息量 t ij (t ) = const ，其 中 const 表示常数， 且初始时刻 D t ij (0) = 0 ，其中 D t kij (t ) 表示第 k 只蚂蚁在本次循环中 留在路径(i,j)上的信息量。 (2 ) 循环次数 Nc ? Nc (4 ) 蚂蚁数目 k ? ka1.(3 ) 蚂蚁的禁忌表索引号 k=1.1(5 ) 蚂 蚁个体根据状态转移概率公式计算的概率选择城市 j 并前进.pij (t ) = 轾 (t ) * 轾h b tj D 犏 ij 犏 臌 臌 a 轾 (t ) * 轾h tl D 犏 lj l? m 犏 臌 臌j? t (t + 1) = (1 - r ) * t (t ) + D t (t ) 式中, D h (t ) 为启发函数，表示在j jbijt 时刻从城市 i 到城市 j 的概率，表达式为D hij = h j - hi ，其中 hi 为对应的适应度函数值。如果城市 j 在 t 时刻被进过了则D t j (t ) = t j (0) = 1 ，否则为 0. a 表示信息启发因子，其值越大，该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强； b 为期望启发因子，表示能见度的相对 重要性，其值越大，越接近于贪心规则。 （6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到 该个体的禁忌表中。 （7）若集合 C 中城市未遍历完，即 k&m，则跳转到第(4)步，否则转第(8)步。 （8）若 满 足 结束条件，即循环次数 NC&=NCmax，则循环结束并输出程序计算 结果。 2.2.5 微分进化 1995 年，Storn 和 Price 提出了一种新的进化算法：微分进化 [28,29]（DifferentialEvolution，DE） ，和其它的进化算法相比，DE 算法容易理解、易于实现、有很强的空 间搜索能力。 作为一种新颖的搜索算法， DE 算法首先在搜索空间内随机产生初始群体， 然后通过将群体中两个成员间的差向量增加到第三个成员的方法来生成新的个体。如果 新个体的适应度值更好，那么新产生的个体将代替原个体。15 江南大学博士学位论文DE 算 法有 三个 主要 操作也 称为 变异 （ Mutation ） 交叉 （ Crossover ）和 选择 、 （Selection） ，但是这些进化操作的实现和 GA 等其它进化算法是完全不同的。设群体 规 模 为 NP ， 向量的维度为 D ，那么群体中的目标向量可以用x i = 轾1, x i 2 ,..., x iD (i = 1,..., NP ) 表示。对于任意一个目标向量 x i 而言，按下面公式 xi 犏 臌vi = x r 1 + F * (x r 2 - x r 3 ), i = 1,..., NP其中 x r 1 ， x r 2 ， x r 3 是群体中随机选择的三个个体，并且 r1 构r2r3i 。F 是一个介于[0，2]间的实型常量因子，用于控制差向量的影响，一般称为放缩因子。显然差向 量越小，扰动也就越小，这意味着如果群体靠近优化值，扰动会自动减小。 DE 算法的交叉操作的目的是通过变异向量 v i 和目标向量 x i 的结合以提高变异向量ui 的多样性。算法通过下面公式生成新的向量 u i = 轾1, u i 2 ,..., u iD : 犏 臌 ì v if randb ? CR OR j randr ? ji ? j = 1 , . .D , . u ji = í ? x ji if randb & CR OR j randr ? ? ?这里，randb 是[0,1]间的随机数；CR 是范围在[0,1]间的常数，称为交叉常量，CR 的值越大，发生交叉的可能性越大，CR=0 表示没有交叉；randr 是在[1,D]随机选择的整 数，它保证 u i 至少要从 v i 中获得一个元素，否则就不会有新的向量生成，群体也就不会 发生变化。 DE 算法中的选择操作，是一种“贪婪”选择模式，当且仅当新的向量个体 u i 的适 应度值比目标向量个体 x i 的更好时，u i 才会被保留到下一代群体中。否则，目标向量个 体 x i 仍然保留在群体中，再一次作为下一代的父向量。2.3 本章小结在本章中，首先对最优化方法进行了详细的描述，在这些基础知识的指导下，研究 PSO 算法就会有规律可寻。另外对于当前大量的进化算法进行了详细的描述，这对研究 PSO 算法提供了借鉴与参考的资源。16 第三章 粒子群算法分析第三章 粒子群算法分析粒子群算法的发展十分迅速，研究者对其改进也非常多，但其基本原理相差无几。 本章首先阐述原始算法的原理；其次对算法发展概况进行了综述；然后对目前最常用的 惯性权值粒子群算法进行了收敛性分析。最后对几种常用的进化算法进行了性能比较分 析。3.1 粒子群优化算法3.1.1 算法原理 如第一章所述，粒子群算法兼有进化计算和群智能的特点。起初 kennedy 等只是设 想模拟鸟群觅食的过程，但后来发现 PSO 算法是一种很好的优化工具。与其他进化算 法相类似，该算法模拟鸟群集体飞行觅食的行为，通过鸟之间的集体协作与竞争使群体 达到目的。在算法系统中，每个备选解被称为一个“粒子” ，多个粒子共存、合作寻优 近似鸟群寻找食物。算法先生成初始种群，即在可行解空间中随机初始化一群粒子，每 个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值（fitness value） 。 每个粒子将在解空间运动，并由一个速度决定其方向和距离。通常粒子将追随当前的最 优粒子而动，并经逐代搜索最后得到最优解。在每一次迭代过程中，粒子将跟踪两个极 值，一为粒子本身迄今找到的最优解 pbest ，另一为全种群迄今找到的最优解 gbest 。 数 学 模 型 描 述 为彤R n：考虑全局优化问题(P )min{ f (x ) : x W WR n }, f :R l ，则问题 (p ) 的多个可行解一个集合称为一个种群(swarm).种群中的每个元素（可行解）称为一个粒子(particle)。微粒的个数称为 种群规模(size)。用 n 维向量 X i = (x i1, x i2,....,x i n) W 来表示第 i 个粒子的位置，用TV i = (vi1, vi2,....,vi n) W 来表示第 i 个微粒的速度。微粒在搜索空间飞行过程中，它自身经历的最佳位置为 Ppi = (ppi 1, ppi 2, ...., ppin ) ， 所有微粒经历过的最佳位置用索引号 g 来表 示，即 Pg 。因此，微粒在每一代中的速度和计算函数的评价函数的位置可通过如下两个 公式进行变化：vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t ) + c 2rand 2 * pgd - x id (t )TT()()(3.1) (3.2)x id (t + 1) = x id (t ) + vid (t + 1)其中： i = 1, 2,...,m ； d = 1, 2,..., n ； rand1 和 rand2 是服从U (0, 1) 分布的随机数； 学习因子 c 1 和 c 2 为非负常数，c1 = c2 = 2 ；vid = [- v max , v max ]，v max 是由用户设定的速度 上限。 算法迭代过程描述为：Initialize population: random X i17 江南大学博士学位论文repeat: for each particle i ? [1, S ] if f X i & f Pi( )( )Pi = X iend if f Pi & f Pg( )( )Pg = Piend update the position and velocity of particle using equation (3.1), (3.2) end until termination criterion is satisfiedPSO 算法的研究主要分为两个方面：算法性能的提高，收敛性的分析。在接下来的 部分主要对这两个方面进行分析。其中第二节主要对改进的算法进行分析，第三节主要 介绍收敛性的分析。 3.1.2 算法流程 基本粒子群算法的流程如下 （1）依照初始化过程，对粒子群的随机位置和速度进行初始设定。 （2）计算每个粒子的适应值。 （3）对于每个粒子将其适应值与所经历过的最好位置 pbest i 的适应值进行比较，若 较好，则将其作为当前的最好位置。 （4）对于每个粒子将其适应值与全局所经历的最好位置 gbest 的适应值进行比较， 若最好，则将其作为当前的全局最好位置。 （5）根据方程（3.1）和方程（3.2）对粒子的速度和位置进行进化。 （6）如未达到结束条件通常为足够好的适应值或达到一个预设最大代数，则返回 步骤（2） 。 3.1.3 社会认知行为分析 在式（3.1）所描述的速度进化方程中，其第一部分为粒子先前的速度；其第二部分 为“认知”部分，因为它仅考虑了粒子自身的经验，表示粒子本身的思考。如果基本粒 子群算法的速度进化方程仅包含认知部分，即vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t )()则其性能变差。主要原因是不同的粒子间缺乏信息交流，即没有社会信息共享，粒 子间没有交互，使得一个规模为的群体等价于运行了单个粒子，因而得到最优解的概率 非常小，收敛速度大大降低。 式（3.1）的第三部分为“社会”部分，表示粒子间的社会信息共享。若速度进化方 程中仅包含社会部分，即vid (t + 1) = vid (t ) + c2rand 2 * pgd - x id (t )()18 第三章 粒子群算法分析则粒子没有认识能力，也就是社会的模型。这样，粒子在相互作用下，有能力到达 探索空间，虽然它的收敛速度比基本粒子群算法更快，但对于复杂问题，由于粒子群的 快速聚集性造成了无法对整体搜索空间进行较好的搜索，因此容易陷入局部最优点。 3.1.4 全局模型与局部模型 以上算法描述中，粒子跟踪两个极值，自身极值和种群全局极值，称为全局版本算 法，如图 3.1（a） 。另一种为局部版本算法，指粒子除了追随自身极值外，不跟踪全局 极值，而是追随拓扑近邻粒子当中的局部极值，如图 3.1(b)。在该版本中，每个粒子需 记录自己和它邻居的最优值， 而不需要记录整个群体的最优值， 对于局部版本， （3.1） 式 更改为：vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t ) + c2rand 2 * pid - x id (t )()()（3.3）其中 pid 为局部最优点。 比较全局和局部版本两种算法，可注意到，它们收敛速度和跳出局部最优的能力有 所差异。由于全局拓扑结构中的所有粒子都进行信息共享，粒子向当前最优解收敛的趋 势非常显著，因而全局模型通常收敛到最优点的速度较局部结构快，但更易陷入局部最 优，表现为整个种群一致收敛到当前第一个较好的解。局部拓扑结构模型则允许粒子与 其邻居比较当前搜索到的最优位置，从而相互之间施加影响，即便其值比种群最好值要 差，该影响可以使较差个体进化为较好的个体。局部版比全局版收敛慢，但不容易陷入 局部最优。（a）gbest 模型 （b）lbest 模型 图 3-1 两种拓扑结构 Fig.3-1 Two Structure of Tepology3.2 粒子群改进算法近年来，对于粒子群算法的改进算法有很多种，主要从改善粒子群算法的性能这个 方面着手。改善粒子群算法性能的方法主要有： （1）与其他算法进行结合； （2）基于变 异行为的 PSO 改进算法； （3）改进 PSO 迭代公式。 3.2.1 与其他算法结合 虽然粒子群算法相对于其他进化算法来说具有算法简单、收敛速度快的优点，但由 于粒子群算法对于复杂函数求解过程中仍然存在易于陷入局部最小点的缺点，很多学者 考虑把其他具有全局搜索能力的进化算法与 PSO 算法结合起来以获得更好的性能。19 江南大学博士学位论文遗传算法相对于粒子群算法来说，由于具有着变异因子和交叉因子的影响，具有着 比粒子群算法更为优异的全局搜索能力。文献[31，33,33]把遗传算法和 PSO 的优点很好的结合在一起，实验结果表明改进以后的算法相对于遗传算法来说收敛速度更为快速，相 对于 PSO 算法来说具有了更好的全局搜索能力。最近几年由于微分进化算法的大量推 广，很多学者也把 DE 和 PSO 算法进行结合改进[34,35, 36]。R. Xu 等[34]利用改进以后的DEPSO 算法对神经网络进行训练。主要方法是先用 PSO 算法对粒子进行训练，在下一 次的迭代过程中使用 DE 算法对粒子群进行进化。如此往复从而可以提高粒子群的多样 性以达到改善全局搜索能力。 3.2.2 基于变异行为的 PSO 改进算法 这类算法主要是借鉴遗传算法中的变异因子来改善粒子群算法的全局搜索能力。 但 和遗传算法不同的是，变异系数不仅仅局限于均匀分布函数[37,38]。比较常用的是高斯变 异[39,40]，柯西变异[41-43]，小波变异[44]等。 赫然[37]等针对粒子群算法的后期速度下降的弱点， 提出了一种基于自适应逃逸策略 的改进算法。当粒子速度下降到某个设定的阈值时，该粒子速度值将随机的在整个速度 空间内按均匀分布函数得到一个较大的速度值，从而使得粒子群在任意时刻都具备跳离 局部最小点的可能性，该算法相对于标准 PSO 算法来说全局搜索能力大大改善。 Kennedy[40]提出了一种基于高斯函数的粒子群算法， 它不同于传统的 PSO 算法研究中的 轨迹方法，即通过速度的调控产生下一代粒子的位置，取而代之的是高斯分布的方法。 H. Hu[41]等提出了一种基于 Cauchy 变异的粒子群算法。 该算法利用个体最优解未更新的 次数为触发点， 借以协助粒子跳出局部最优点。 H. Ling[44]等利用震荡系数对小波母函 S. 数的变化区间的影响提出了一种基于小波函数的粒子群改进算法。该算法在运行初期允 许随机选择的粒子在较大区间内进行小波变异，而在粒子进化后期给予粒子以较小的变 化区间，由于较好的平衡了全局和局部搜索，该算法在以上几种变异方法中取得了较好 的成绩。 比较这些变异策略来看， 一个共同点就是给予被变异的粒子以较大的速度值从而可 以跳出当前局部最小点；另外变异函数的选取对于实际结果也有一定的影响。以原点为 中心的 Gaussian 和 Cauchy 分布的概率密度函数分别为f (v ) = 骣 v2 ÷ ÷ exp ?? ? 2s ÷, - ? ? 桫 ÷ 2ps 1 v&f (v ) =1 a * 2 ,- ? p a + v2v&其中为了覆盖整个速度空间，Gaussian 和 Cauchy 分布的参数分别设置为 s = 0.16 ，a = 0.32 。为了覆盖整个速度空间 Morlet 小波母函数可表示为y (x ) = e - x2/2cos (5x )- 2.5 x ＃2.520 第三章 粒子群算法分析图 3-2 小波，柯西，高斯函数比较图 Fig. 3-2 The comparision of Wavelet, Cauchy and Gaussian从图 3.2 的结果可以看出，高斯函数在同等状态下可以获得较大的变异数值，而小 波函数则获得了较小的变异数值，而且在同等状态下还可以产生负值。根据仿真表明小 波函数在局部变异中获得了较好的成绩，而对于那些需要对 PSO 算法位置最大值进行 限制的函数中获得了其他两种算法无法获得的好成绩。因此，我们可以得出结论，三种 变异函数应该根据具体变异策略而选取。 3.2.3 针对粒子群迭代公式的改进 在这一类型的改进方法中，应用比较广泛的有带惯性权重的粒子群算法、带收缩因 子的粒子群算法。 为了更好的协调全局搜索能力和收敛能力，shi[45]等人引入了惯性权重 w ，则（3.1） 式变为：vid (t + 1) = wvid (t ) + c1rand1 * p pid - x id (t ) + c2rand 2 * pgd - x id (t )()()（3.4）由（3.2）（3.4）式组成的迭代算法通常被认定标准的 PSO 算法。 、 显见，惯性权重 w 描述了粒子上一代速度对当前代速度的影响。控制其取值大小可 调节算法的全局与局部寻优能力。w 值较大，全局寻优能力强，局部寻优能力弱，反之， 则局部寻优能力增强，而全局寻优能力减弱。基本 PSO 算法可以看作 w = 1 ，因此在迭 代后期缺少局部搜索能力。实验结果表明，在[0.8, 1.2]之间时，算法有更快的收敛速度。 文献[45]中试验了将设置为从 0.9 到的 0.4 线性下降， 使得算法在开始时探索较大的区域， 较快地定位最优解的大致位置，随着逐渐减小，粒子速度减慢，开始精细的局部搜索。 该方法加快了收敛速度，提高了算法的性能。当待解问题很复杂时，该法使得算法在迭 代后期全局搜索能力不足，导致不能找到要求的最优解，这可以用自适应改变惯性权重 来克服。 Clerc[46,47]建议采用收缩因子的方法，通过正确选择控制参数 c 1 ，c 2 和 w 来保证算法 收敛。其速度更新方程为：vid (t + 1) = c vid (t ) + c1rand1 * ppid - x id (t ) + c2rand2 * pgd - x id (t )(()}
互联网 & 03-14 17:05:51 & 作者：佚名 &
为什么是72呢?很多朋友都不是很清楚，甚至也不知道为什么，所以下面小编为大家解析72PPI的秘密，来看看吧
在平时的设计中，我都会习惯性的在PS新建界面分辨率后面输入72。在某天ps更新后，我新建文档发现预设里的&移动应用程序设计&，不同大小的设备会显示不同的分辨率（PS CC 2015版本中已经都已经改为了72）。这引起了我的好奇，这个数字也不知道是谁告诉我的了，只是平时做pc端、手机端的设计时都会在分辨率里输入72。从来也没有去研究过这个72像素／英寸是从哪里来的，为什么是72呢？我设置...行吗？72有什么特殊呢？
PS中的单位
百分百：这个不需要解释
英寸、厘米、毫米：这些是我们生活当中常用的长度单位，是自然界中的绝对长度。
点、派卡：是打印中使用的长度单位，1英寸＝2.54厘米＝72点＝6派卡，这个换算公式告诉我们点、派卡也是绝对长度
像素：像素可以理解为&图像元素&即组成图像最小的元素，每个元素不是一个点或者一个方块，而是一个抽象的取样。我是这样理解的，像素就如同平面构成中点线面的点，这个点是一个抽象的概念，没有具体的大小，没有具体的形状，就如同一个点可以变成一个面，一个面可以变成一个点，相对整体而言这个点才有实际的意义。
分辨率的含义
分辨率Image resolution，中国大陆译为&分辨率&，香港、台湾分别译为&解像度&和&解析度&，泛指量测或显示系统对细节的分辨能力。（维基百科）
描述分辨率的单位
ppi－pixels per inch 像素分辨率&每英寸的长度内包含多少数量的像素。
dpi－dots per inch 设备分辨率 &每英寸的长度内包含多少数量的&点&。
分辨率的使用的三个误区
1、很多文章会把ppi和dpi混淆使用，从道理上讲是没有错的，因为我们也可以把像素理解成图像中的&点&。或是把设备中的&点&理解为像素，无论是手机还是电脑虽然分辨率都是以像素为单位的，但是它们都属于输出设备的范畴所以用dpi来表示更为合理，而图像的分辨率应该以ppi表示，这点大家理解就好。
2、PS中的分辨率72ppi和我们平时说的iphone5的分辨率326dpi的计算方法是不一样的。
PS中ppi只是计算图像长或宽中每英寸的像素数量，而我们说的手机或电脑的dpi是屏幕对角线每英寸的像素数量。
3、我们工作中经常说一幅图分辨率是72像素，正确的表述应当是600x1920像素，分辨率为72ppi，只是平时工作习惯简化描述而已。
为什么是72ppi呢？
（当图像的分辨率（长x宽像素）一样，不同大小ppi的图像是否会对我们的设计工作造成影响呢？）
例如我们设计一个手机界面，新建一个640x1136像素，分辨率为72ppi和一个640x1136像素，分辨率为7200ppi的图像。
在电脑上看到的效果和把两幅图输出到同一手机上看到的效果是一样的。这是因为屏幕上看到的图像都是由像素组成的，只要图像的像素数量没有改变，图像质量就不会改变，在同一屏幕上呈现的大小也就不会改变。但当我们把两幅图像打印出来时，分辨率7200ppi的图像面积不到10mm²，而72ppi图像面积大概有900cm²。这是因为打印出来的图像是由墨点组成的，而这些墨点的排列规则是由我们之前设置的图像分辨率ppi来决定的。
用生活中你的现象来打个比方
（这里我们要注意一点就是屏幕的物理像素点大小是不会改变的。）
就好比有一个盒子，里面放着正方形的糖块，这个盒子里面可以放640x1136块糖，每块糖1元，72块糖长度为1米。
还有另一个盒子里面也放着正方形的糖块，同样放着640x1136块糖，每块糖也是1元，但是7200块糖长1米。
所以我们购买他们的价钱是一样的，都是640x1136x1元。只要糖块的数量没有改变我们购买他们的价钱就是一样的，就像图像分辨率的ppi不论怎么改变，只要像素数量不发生变化，图像在同一屏幕上呈现的大小就不会改变。但是我们花同样的钱购买回来的糖大小却不一样了，就像同样像素数量的图像，ppi不一样打印的大小也不一样。
72ppi的由来
早期MAC开发了一种图形界面，当把ppi设置成72时1英寸＝2.54厘米＝72点＝72像素＝6派卡。这时就把只有相对单位长度的像素赋予了真实的物理长度，刚好1个点（打印设备）和屏幕上的1个像素对应。而且当时MAC的显示器大都是14英寸的，系统显示分辨率最高也就到800&600像素，72dpi。当图像分辨率的ppi和屏幕分辨率的dpi一致时，屏幕上的标尺就会和现实生活中的标尺一致，图像在电脑中显示的大小就和打印出来的尺寸是一样的了。
很久以前72ppi就已经成为了屏幕图像设计的标准，并且大家长期这样使用。所以对于屏幕图像的设计，分辨率ppi无论设置成多少都不会对我们的工作造成影响。但为了和大家保持一致我们还是要把分辨率设置成72ppi，这样还有一个好处就是在PS中无需设置字体的单位了，因为1pt＝1px。
大家感兴趣的内容
12345678910
最近更新的内容粒子群算法及其在图像分割中的应用_学霸学习网
粒子群算法及其在图像分割中的应用
分类号密级博 士 学 位 论 文题 目： 粒子群算法及其在图像分割中的应用 与研究 英文并列题目： The Study of the Particle Swarm Optimization and Its Application 研 专 导 究 生： 业： 师： in Image Segmentation 高 浩 轻工信息技术与工程 轻工过程模型化及控制 须 文 波研 究 方 向： 指导小组成员： 学位授予日期：答辩委员会主席： 袁景淇江 南 大 学地址：无锡市蠡湖大道 1800 号 二 OO 九年十二月
独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名： 日 期：关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名： 导师签名： 日 期：
摘要摘要粒子群优化算法源于鸟群和鱼群群体运动行为的研究， 是一种新的群体智能优化算 法，是演化计算领域中的一个新的分支。它的主要特点是原理简单、参数少、收敛速度 快，所需领域知识少。该算法的出现引起了学者们极大的关注，已在函数优化、神经网 络训练、组合优化、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。尽 管粒子群优化算法发展近十年，但无论是理论分析还是实践应用都尚未成熟，有大量的 问题值得研究。 本文从算法机理、算法改进和算法应用等方面对其进行了系统性的研究。此外，图 像分割是图像分析和模式识别的首要问题，也是图像处理的经典难题之一。本文将微粒 群算法和图像分割法相结合，提出了基于改进 PSO 算法的分割算法，在取得良好的分 割效果的同时，运用算法的并行搜索机制显著的提高了分割速度。论文具体内容如下： (1) 对粒子群算法及其理论基础（优化方法和进化计算）进行了详细的综述。 首先本文概述了优化方法的产生和发展，着重介绍了优化方法的基本思想、研究领域、 应用发展情况；阐述了进化计算的产生、定义以及研究内容，并介绍了几种典型的进化 计算方法，包括遗传算法、进化策略、微分进化等；最后介绍了粒子群优化算法，阐述 了粒子群优化算法的起源，介绍了粒子群优化算法的初始版本和标准版本，从理论研究 和应用研究的角度综述了粒子群优化研究的现状，总结了标准粒子群优化算法存在的问 题。同时本文使用了蒙特卡罗方法对粒子的行为进行了研究，结果显示 PSO 算法在迭 代后期具有搜索能力较弱的缺点，同时也给出了如何提高 PSO 算法收敛性的方法。此 外，九个标准测试函数用来测试 PSO 算法和其他几种流行的进化计算方法的性能，结 果验证了 PSO 有着其他进化算法无法比拟的快速收敛等特性。 (2) 尽管 PSO 算法比其他算法对复杂函数有着较强的寻优能力以及收敛速度快 等特点，但是它依然无法保证在搜索空间中找到全局最优点。因此在本文中引入了具有 着更强全局搜索能力的 QPSO 算法来进行研究改进。但是由于 QPSO 同 PSO 算法一样 的是， 它也把粒子作为一个整体来进行更新， 因此 QPSO 算法同样具有维数限制的缺点。 通过把一个具有复杂高维的粒子分解为多个一维的子个体进行优化，使用协作方法的 QPSO 算法能够很好的克服这一缺点。八个测试函数以及应用于图像分割领域的最大类 间方差法（OTSU 方法）在本文中用来测试改进以后的 QPSO 算法的成绩。仿真结果表 明，与其他算法比较来看，协作方法帮助 QPSO 算法获得更精确的解。它同样也克服了 OTSU 方法受维数束缚的缺陷。 (3) 在分析了粒子群全局收敛能力的基础之上，针对粒子群算法局部收敛和搜 索精度低的问题，提出了一种全局的基于 Gaussian 变异的粒子群算法(GGPSO）.该算法 结合了局部和全局变异因子使算法在全局和局部搜索能力中找到了一个很好的平衡，并 证明了它能以概率 1 收敛到全局最优解。典型函数优化的仿真结果表明，该算法不仅可 有效的避免标准 PSO 算法的早熟收敛，而且具有寻优能力强、搜索精度高、稳定性好等 优点。同时针对图像信息处理中的图象分割这一难点问题，以 Kapur 算法为优化目标，I 摘要验证了该算法克服了图象分割中寻优速度慢的缺点，与其他群体算法比较获得了更大的 适应度函数值。因此，该算法更适合于图像分割以及相关的函数优化问题。 (4) 在分析了粒子群收敛性的基础之上， 针对粒子群(PSO)算法后期搜索能力下 降的问题，提出了一种基于适度随机搜索策略的粒子群算法(IRPSO）.该方法在提高粒 子群算法收敛速度的前提下，有效的提高了粒子的全局搜索能力。另外，由于该方法只 有一个控制参数和迭代公式，因此更为简单易实现。典型函数优化的仿真结果表明，该 算法相对于比较算法来说获得了更好的性能。同时针对图像分割这一难点问题，以互信 息熵差为优化目标，验证了该算法在比较算法中获得了更好的分割效果。 论文最后对所做工作进行了总结，并提出了进一步研究的方向。关键词：进化算法，粒子群算法，图像分割，收敛速度，全局搜索能力，维数约束， 蒙特卡罗方法II AbstractAbstractParticle swarm optimization (PSO) is an evolutionary computation technique developed by Dr. Eberhart and Dr. Kennedy in 1995, inspired by social behavior of bird flocking or fish schooling. Recently, PSO algorithm has been gradually attracted more attention over another intelligent algorithm. PSO is simple in concept, few in parameters, and easy in implementation. It was proved to be an efficient method to solve optimization problems, and has successfully been applied in the area of function optimization, neural network training and fuzzy control systems, etc. However, both theory and application of PSO are still far from mature. The paper gives a comprehensive study on PSO from the aspect of algorithm mechanism, algorithm modification and its application. Furthermore, image segmentation is the first and foremost problem in image analyzing and mode recognition, and is also a typical stumbling block in image processing. In order to raise its speed, we combined the method of PSO and image segmentation algorithm on valves and therefore proposed several segmentation algorithms based on improved PSO. As we achieve an effective segmentation, we also raised the speed of the parallel searching system. The main content is as follows: (1) The paper surveys PSO algorithm and its basic theories (Optimization method and Evolutionary Computation, EC). First we summarize the generation and development of Optimization method in detail, and emphasize the basic idea, research field and applications. And then we expatiate the emergence, definition and research field, and some typical EC methods, e.g. Genetic Algorithm, Evolutionary Strategy, Differential Algorithm are introduced. At last we introduce PSO algorithm, including its original edition and standard edition, summarize its theoretical and applied research. Monte Carlo method is presented to investigate the ability of particles. The results reveal why the PSO has relative poor global searching ability in the last stage of iteration, it also gives the way how to improve the convergence rate of PSO. Furthermore, nine benchmark functions are used to test the performance of PSO and other popular EC algorithms. The results show that the merits of PSO in terms of the fast convergence rate. (2) In spite of PSO has comparable or even superior search performance for many hard optimization problems with faster and more stable convergence rates, but it can’t guarantee to find the global optima in the search space. So the Quantum-behaved PSO (QPSO) algorithm which has power global searching ability than PSO is introduced for improving in this paper. But for QPSO updating the position of particle as whole-item which likes PSO, it also has the problem of the curse of dimensionality. Hence two new hybrid QPSO algorithms with cooperative method (CQPSO and ICQPO) is proposed in this paper for solving this problem. The cooperative method is specifically employed to conquer the “curse of dimensionality”, by splitting a particle with composite high-dimensional into several one-dimensional sub-parts. Nine benchmark functions and Maximization of the measure of separability on the basis of between-class variance method (often called OTSU method), a popular thresholding technique, is employed to evaluate the performance of the proposed method. The experimentIII Abstractresults show that, compared with the exiting EC methods, the cooperative method helps the new PSO algorithm to get more effective and efficient results. It also conquers the curse of dimension of traditional OTSU method. (3) Based on analysis of the global searching ability of PSO, a new global Gaussian PSO (GGPSO) is proposed to overcome the problem of the premature and low precision of the standard PSO. In this algorithm, combining with global and local mutating method finds an excellent balance between global searching and local searching, which is also guaranteed to converge to the global optimization solution with probability one. Experiment simulations show that the proposed algorithm can not only avoid premature effectively but also has powerful optimizing ability, good stability and higher optimizing precision. For solving image segmentation which is the great importance in the field of image processing, we use Kapur function as the optimization object, and the experiments show that the GGPSO algorithm outperforms the compared algorithms especially in maximum the fitness value, so it can applied in image segmentation and optimization problems well. (4) Based on analysis of the convergence of particle swarm optimization (PSO), a new PSO based on improved Moderate Random Searching ability (IRPSO) is proposed to overcome the problem of bad searching ability in the last stage of the standard PSO. It helps the particles have more exploration ability and fast convergence rate. Furthermore, for the improved algorithm only having one parameter and iteration formula, it is simpler than PSO. Experiments show that the proposed algorithm performs much better than the other algorithms in terms of the quality of solution. For solving the problem in image segmentation, we use the difference of mutual information (DMI) as the optimization function, and the experiments show that the IRPSO algorithm gets the better performance of image segmentation among the compared algorithms. Finally, the work of this dissertation is summarized and the prospective of future research is discussed.Keywords: Evolutionary Computation, particle swarm algorithm, image segmentation, convergence rate, the global searching ability, the curse of dimension, Monte Carlo methodIV 目录目摘录要 ......................................................................................................................................... IAbstract .................................................................................................................................... III 第一章 绪 论 ............................................................................................................................ 1 1.1 课题背景 ...................................................................................................................... 1 1.1.1 最优化 ................................................................................................................. 1 1.1.2 最优化方法 ......................................................................................................... 1 1.1.3 基于进化计算求解最优化问题的方法 ............................................................. 3 1.2 课题的目标和意义 ...................................................................................................... 5 1.3 课题的主要研究工作和组织结构 .............................................................................. 6 第二章 优化算法介绍 .............................................................................................................. 9 2.1 优化研究基础 .............................................................................................................. 9 2.1.1 最优化问题 ........................................................................................................ 9 2.1.2 局部优化算法 .................................................................................................. 10 2.1.3 全局优化算法 .................................................................................................. 10 2.1.4 没有免费午餐定理 .......................................................................................... 11 2.2 进化计算 .................................................................................................................... 12 2.2.1 遗传算法 .......................................................................................................... 12 2.2.2 进化策略 .......................................................................................................... 13 2.2.3 进化规划 .......................................................................................................... 14 2.2.4 蚁群算法 .......................................................................................................... 14 2.2.5 微分进化 .......................................................................................................... 15 2.3 本章小结 .................................................................................................................... 16 第三章 粒子群算法分析 ........................................................................................................ 17 3.1 粒子群优化算法 ........................................................................................................ 17 3.1.1 算法原理 .......................................................................................................... 17 3.1.2 算法流程 .......................................................................................................... 18 3.1.3 社会认知行为分析 .......................................................................................... 18 3.1.4 全局模型与局部模型 ...................................................................................... 19 3.2 粒子群改进算法 ......................................................................................................... 19 3.2.1 与其他算法结合 .............................................................................................. 19 3.2.2 基于变异行为的 PSO 改进算法..................................................................... 20 3.2.3 针对粒子群迭代公式的改进 .......................................................................... 21 3.3 标准粒子群算法收敛性分析 .................................................................................... 22 3.3.1 以往 PSO 收敛性分析方法............................................................................. 22 3.3.2 基于蒙特卡罗模拟方法的 PSO 收敛性分析................................................. 23I 目录3.4 粒子群算法与其他进化算法比较及分析 ................................................................ 25 3.4.1 各种进化算法性能比较 .................................................................................. 25 3.4.5 比较结果分析 .................................................................................................. 29 3.5 PSO 算法应用............................................................................................................. 30 3.6 本章小结 .................................................................................................................... 31 第四章 基于协作方法的量子粒子群算法及其在图像分割的应用 .................................... 32 4.1 引言 ............................................................................................................................ 32 4.2 量子粒子群算法 ........................................................................................................ 32 4.3 基于协作方法的量子粒子群方法 ............................................................................ 33 4.3.1 协作方法 ........................................................................................................... 33 4.3.2 精英策略 .......................................................................................................... 35 4.3.3 仿真结果比较及其分析 .................................................................................. 36 4.4 基于 CQPSO 算法的图像分割应用 .......................................................................... 38 4.4.1 图像分割概述 .................................................................................................. 38 4.4.2 OTSU 分割算法 ............................................................................................... 39 4.4.3 计算步骤 .......................................................................................................... 39 4.5 基于 CQPSO 的最大类间方差图像分割 ................................................................. 40 4.5.1 算法描述 ........................................................................................................... 41 4.5.2 算法测试 .......................................................................................................... 41 4.6 本章小结 .................................................................................................................... 55 第五章 一种全局收敛的 PSO 算法及其在图像分割中的应用 ............................................ 58 5.1 引言 ............................................................................................................................ 58 5.2 基于 Gaussian 变异的 PSO 算法 ............................................................................... 58 5.2.1 引入 Gaussian 变异的粒子群算法 .................................................................. 58 5.2.2 GGPSO 算法 ..................................................................................................... 60 5.2.3 GGPSO 算法收敛性分析 ................................................................................. 61 5.3 比较实验及分析 ......................................................................................................... 63 5.3.1 试验设计 ........................................................................................................... 63 5.3.2 仿真结果及分析 ............................................................................................... 63 5.4 基于 GGPSO 方法的图像分割应用 .................................................................. 66 5.4.1 算法描述 ........................................................................................................... 67 5.4.2 算法测试 ........................................................................................................... 67 5.5 本章小结 ..................................................................................................................... 73 第六章一种基于随机搜索策略的粒子群算法 ...................................................................... 74 6.1 引言 ............................................................................................................................ 74 6.2 基于适度随机搜索策略的 PSO 算法........................................................................ 74 6.3 对比试验 ..................................................................................................................... 76II 目录6.3.1 试验设计 ........................................................................................................... 76 6.3.2 仿真结果比较分析 ........................................................................................... 76 6.4 IRPSO 算法针对图像分割问题的比较试验............................................................ 78 6.5 本章小结 ..................................................................................................................... 83 第七章 结束语 ........................................................................................................................ 85 致 谢 ...................................................................................................................................... 87 参考文献 .................................................................................................................................. 88 附录： 作者在攻读博士学位期间发表的论文 .................................................................... 96III
第一章 绪 论第一章 绪 论1.1 课题背景1.1.1 最优化 最优化已经成为了一个使用非常广泛的术语， 最优化的概念反映了人类实践活动中 十分普遍的现象。最优化是一个重要的数学分支，是一门应用性强、内容丰富的学科。 例如，工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能降低成本；资 源分配中，怎样分配有限的资源，使得分配方案既能满足各方面的基本要求，又能获得 好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润。在人类活 动的各个领域中， 诸如此类， 不胜枚举。 这些问题在某种程度上都可以称为最优化问题。 最优化的目的是对于给出的实际问题，从可行的解决方案中找出最好或较好的解决方案 来， 即要在尽可能节省人力、 物力和时间的前提下， 争取获得在可能范围内的最佳效果。 最优化问题可以追溯到十分古老的极值问题，早在 17 世纪，英国科学家 Newton 发明微积分的时代，就已提出极值问题，后来又出现了 Lagrange 乘数法。1847 年法国 数学家 Cauchy 研究了函数值沿什么方向下降最快的问题， 提出了最速下降法。 1939 年 前苏联数家Л .В . К а н т о р о в и ч 提出了解决下料问题和运输问题这两种线性 规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但 是，任何科学的进步都会受到历史条件的限制。直至 20 世纪 30 年代，最优化这个古 老的课题并未形成独立的系统学科。 20 世纪 40 年代以来，随着生产活动和科学研究地不断发展，特别是计算机技术 的高速发展和广泛使用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的 有力工具。因此各种优化理论研究发展迅速，新方法不断出现，实际应用日益广泛。而 且在计算机技术的推动下，一些超大规模的优化问题也得以实现，最终使得优化理论与 方法在经济规划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十 分活跃的学科[1]。 一般来说，最优化问题可以表示为：ì g (x ) ? 0, i 1,..., m ? i ? ? min f (x ) ，s.t . ? h j (x ) = 0, j = 1,..., l í ? ? x? X ? ? ?（1.1.1）其中， x ? R n 是决策变量， f (x ) 为目标函数，X 为可行域， gi (x ) 、h j (x ) 为约束函 数， gi (x ) 称为不等式约束， h j (x ) 称为等式约束。 1.1.2 最优化方法 为了达到最优化的目标所提出的各种求解最优化问题的方法称为最优化方法。 最优 化方法是一个以数学为基础的重要的科学分支，它一直受到人们的广泛重视，并在许多1 江南大学博士学位论文工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机 工程等。它对促进运筹学、管理科学、控制论和系统工程等新兴学科的发展起到了重要 的作用。 最优化方法在实践中的应用可以分为最优设计、最优计划、最优管理和最优控制等 四个方面[1]。最优设计: 在飞机、造船、机械、建筑等工程技术界都已广泛应用最优化 方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使 许多设计优化问题得到解决。电子线路的最优设计是另一个应用最优化方法的重要领 域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机 辅助搜索最佳配方、配比方向发展。一个新的发展动向是最优设计和计算机辅助设计相 结合。最优计划：在编制国民经济和部门经济的计划和农业、交通、能源、环境、生态 规划中，在编制企业发展规划和年度生产计划中应用最优化方法的过程称之为最优计 划。一个重要的发展趋势是帮助决策部门进行各种优化决策。最优管理：在企业日常生 产计划的制订、生产经营的管理和运行中，通过计算机管理系统和决策支持系统等辅助 工具的建立和使用，运用最优化方法进行经营管理的过程称为最优管理。在经济管理学 上就是在一定人力、物力和财力资源条件下，使经济效果（如产值、利润等）达到最大， 并使投入的人力和物力达到最小的科学方法。最优控制：主要用于对各种控制系统的优 化。例如，导弹系统、卫星系统、航天飞机系统、电力系统等高度复杂系统中运用最优 化方法。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制 创造了有利条件。 最优控制的对象也将从对机械、 电气、 化工等系统的控制转向对生态、 环境以至社会经济系统的控制。 求解最优化问题的最优化方法有多种形式。 不同类型的最优化问题可以有不同的最 优化方法，同一类型的最优化问题也可有多种最优化方法。某些最优化方法可适用于不 同类型的最优化问题， 针对相同的最优化问题， 不同的最优化方法具有不同的优化特性。 有些最优化方法可以快速求解到局部最优解，有些优化方法具有很好的全局寻优特性。 一般来说，求解最优化问题的理想情况是快速有效的得到全局最优解。当然，由于对最 优化问题的性质和最优化方法认识的不足，这种情况只能在有限的条件下实现。对于复 杂函数最优化问题,一般很难找到收敛性好且全局最优的最优化方法。 一般来说，求解最优化问题可以分为以下几个步骤： ⑴ 提出需要进行优化的问题； ⑵ 建立求解优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件； ⑶ 分析模型，选择合适的最优化方法； ⑷ 求解方程； ⑸ 最优解的验证和实施。 显然，在最优化问题的数学模型建立后，主要问题是如何通过不同的求解方法解决 寻优问题。最优化问题的数学求解方法一般可以分成解析法、直接法、数值计算法等几 类[2,3]：2 第一章 绪 论解析法：对于目标函数及约束条件有简单而明确的解析表达式的非线性优化问题， 通常可采用解析法来求解。解析法的求解方法是先按照函数极值的必要条件，用数学分 析的方法（求导或变分法）求出其解析解，然后按照充分条件或问题的实际物理意义间 接地确定最优解，因此也称间接法。这类方法主要用来解决动态优化问题。其中经典变 分法用来求解无约束动态优化问题；极大（极小）值原理和动态规划主要用于求解有约 束的动态优化问题。另外，经典微分法可用于求解静态优化问题。 直接法： 当目标函数较为复杂或者不能用变量显函数描述或无法用解析法求必要条 件时通常可采用直接法来解决。 直接法的基本思想是用直接搜索的方法经过一系列的迭 代以产生点的序列，使之逐步接近到最优点。这种方法常常是根据经验或通过试验得到 所需要的结果，直接法可以分为函数逼近法、区间消去法和爬山法。对于一维搜索(单 变量极值问题)，主要用消去法或多项式插值法，对于多维搜索问题(多变量极值问题) 主要用爬山法。 数值计算法：这种方法也是一种直接法，是以梯度法为基础的。它是一种解析与数 值计算相结合的方法。这类方法主要用于多变量的寻优问题。其中最速下降法、共轭梯 度法、牛顿法与拟牛顿法、变尺度法和牛顿-高斯最小二乘法等适用于多变量无约束的 优化问题。解决多变量约束的优化问题通常也采用以解析法为基础的数值解法，这类方 法很多，大致可分为以下三种类型：一是将有约束的优化问题转化为一系列无约束的优 化问题，然后采用无约束优化方法来求解，这种方法称为变换算法或序列无约束极小化 方法，如拉格朗日乘子法和惩罚函数法；二是采用一系列线性或二次规划问题的解来逼 近原非线性约束问题的解，这种方法称为线性近似化技术，如序列线性规划化、割平面 法和序列二次规划化；三是直接处理约束条件，研究在约束边界处如何搜索以获得使目 标函数值逐步改善的可行点列，最后趋近约束问题的极小值点，这种方法称为可行方向 法、梯度投影法和简约梯度法。 用数学方法求解优化问题的历史相对悠久，当前仍然在不断的发展过程中。这些传 统的方法大多是针对某些特定问题的，并且对搜索空间要求相对严格，有些方法还需要 使用被优化函数的各阶导数信息。但是，随着科学技术的发展，优化问题也变得更加复 杂。如工程优化所建立的数学函数,往往是带有多种约束条件的复杂函数,而且大部分是 不连续、 不可微的隐函数。 对于这些复杂函数来说,用常规的数学方法很难或根本无法处 理。有些问题甚至无法用函数关系来表达，对于这类问题，采用上述方法，不可能得到 圆满的结果。因此，需要进一步研究和探索新的优化思想和优化方法。 1.1.3 基于进化计算求解最优化问题的方法 承上所述，随着科学技术的发展，实际的优化问题也变得越来越复杂。优化问题表 现出了复杂性、约束性、非线性、多极小、建模困难等特点，因此常规的求解方法已很 难适用，寻求一些新的优化技术成为一个重要研究目标和引人注目的研究方向。 20 世纪 80 年代以来，进化计算作为一类通过模拟生物进化过程与机制来求解问 题的优化技术，为解决复杂优化问题提供了新的思路和方法，近年来受到了人们极大关 注。进化计算采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单3 江南大学博士学位论文的进化操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于采用种群的方式 组织搜索，这使得进化计算可以同时搜索解空间的多个区域，而且用种群组织搜索的方 式也使得进化计算特别适合大规模并行操作。在赋予进化计算自组织、自适应、自学习 等特征的同时， 优胜劣汰的自然选择和简单的进化操作使进化计算具有不受其搜索空间 限制条件（如可微、连续、单峰）的约束及不需要其它辅助信息（如导数）的特点。 基于进化计算求解优化问题的一般步骤为： ⑴ 随机给定一组初始解； ⑵ 评价当前这组解的性能； ⑶ 按照一定的方法选出性能优良的解作为进化操作对象； ⑷ 对选出的解进行进化操作（如交叉、变异等）得到新一代解； ⑸ 评价当前新一代解的性能，如果满足要求或进化过程达到一定代数，过程 结束，否则转到 ⑶。 对于复杂优化问题的求解，进化计算有实用性、通用性、灵活性强、效率高等特点， 能在更多的情况下求得有用的(即近似的、次优的和在精度许可范围内的)解。与传统数 学方法相比，基于进化计算方法有如下特点[4]： ⑴ 进化计算的处理对象可以是参数本身， 也可以是经过某种映射形成的特定编码， 编码形式可以是矩阵、树、图、集合、串、序列、链和表等。这个特点使进化计算有广 泛的应用领域，尤其是对多目标、大规模、高维数、非线性以及带有不可转化约束条件 的复杂优化问题，具有更强的适应性。 ⑵ 进化计算通过策略、参数、操作以及算子的调整，能够很快提高寻优求解的性 能，更重要的是进化计算能够通过自身的改良以及同其它方法的交叉融合，在较短的时 间内快速进化，这一点体现了进化计算的灵活性。 ⑶ 进化计算采用群体搜索策略，而传统方法多采用单点搜索策略，这种特点使进 化计算具有极好的全局性，减少陷入局部最优的风险；同时，也使进化计算本身易于大 规模并行实现，可充分发挥高性能计算机系统的作用。 ⑷ 进化计算具有高效的特点，不是说在拥有同等计算资源时，求解优化问题肯定 都比传统方法快(从整体上讲，在近年来多数工程应用中的效率确实高出传统算法，否 则，进化计算的发展速度也不会突飞猛进)，更多的是指能够更充分挖掘计算机的潜力， 比如容易实现并行寻优求解(通过占用更多的冗余计算资源来实现速度的提高)。 ⑸ 进化计算基本不依赖搜索空间的知识及其他辅助信息，它采用适应度函数来评 价个体，并在此基础上驱动进化过程，而对适应度函数本身无特别严格要求。而传统方 法则要求函数有诸如连续、 可微或空间凸性等条件。 这使进化计算有更广泛的应用范围。 ⑹ 进化计算用概率的变迁规则来控制搜索的方向，表面上看好像是在盲目搜索， 实际上它遵守某种随机概率，在概率意义上朝最优解方向靠近，因此，它不像通常采用 确定性规则的传统方法，需要构造合适的下降方向。 二十世纪七十年代以来，一些与经典优化方法不同的的进化计算方法相继被提出， 其中包括遗传算法[5,6]、蚁群算法[7]、粒子群算法[8,9]以及微分进化算法[10,11]。其中粒子群4 第一章 绪 论算法是近年来提出的一种简单而高效的进化算法。由于它容易理解、易于实现，所以发 展十分迅速，在很多领域得到了成功应用。由于图像分割是图像分析和模式识别的首要 问题，也是图像处理的经典难题之一，它是图像分析和模式识别系统的重要组成部分， 并决定图像的最终分析质量和模式识别的判别结果。因此本文针对基于 PSO 的图像分 割算法进行了研究，提出了多个新的解决这类优化问题的算法。1.2 课题的目标和意义粒子群优化算法有些与遗传算法相似，如它们都是基于群体的优化技术，有较强的 并行性无需梯度信息，只需利用目标的取值信息，具有很强的通用性。但是，粒子群算 法比遗传算法更简单、操作更方便。因而，粒子群算法从诞生起，就引起了国内外学者 的广泛关注，掀起了该方法的研究热潮，己经广泛应用于函数优化、神经网络训练、模 糊系统控制[12]等领域。近年来进化算法已成为分布式人工智能研究的一个重要领域，在 美国成立有专门的组织研究群体的仿真；由欧洲联盟资助的进化算法相关研究项目也于 2001 年在欧洲多个研究机构启动；在国内，国家自然科学基金“十五”期间学科交叉 类优先资助领域中，认知科学及其信息处理的研究内容就明确列出了群体智能的进化、 自适应与现场认知、相关项目以及复杂系统与复杂性。它的主要研究方向及内容是复杂 系统与复杂性的理论与方法研究； 物质层次复杂系统的研究； 生命层次复杂系统的研究： 社会层次复杂系统的研究。2001 年 3 月 8 日在北京召开的第六届全国人工智能联合会 议暨“863”计划智能计算机主题学术会议，戴汝为院士特邀报告的主要内容就是进化 算法的研究进展。到现在，国家自然科学基金委员会每年都有资助数项粒子群优化算法 相关理论和应用的研究。 国际上， 每年召开的顶级国际会议中以进化算法为主题的会议主要有美国计算机协 会（Association of Computing Machinery）每年举行的基因与进化计算国际会议（Genetic and Evolutionary Computation Conferences） ，IEEE 计算智能协会（IEEE Computational Intelligence Society） 每年举行一次的进化计算国际会议 （IEEE Conference on Evolutionary Computation）以及自 2003 年起每年举行一次群体智能会议（IEEE Swarm Intelligence Symposium） 。其中粒子群优化算法是这些会议的重要主题。 PSO 自 1995 年提出以来，由于其简单和明确的实际背景，以及前述的诸多优点， 使得很多研究者加入到对这种算法的研究中，目前粒子群优化算法的理论研究与应用研 究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不 同学科中得以实现。这些研究主要集中在如下几个方面： （1）粒子群优化算法的理论分析 具体来说，这个问题的研究分为三个方面：一是单个粒子的运动轨迹，现有的研究 发现，单个粒子不断的在各种正弦波上“跳跃” ，即其轨迹是各种正弦波的随机的叠加 组合，这里所用的主要工具是微分方程和差分方程[12]；二是收敛性问题，关于粒子群算 法的收敛性研究比较多的集中在一些简化条件下的结果，采用的主要工具是动态系统理 论。其它还有采用集合论的方法来研究此问题，得出的结论是[13]：在没有任何改进的情5 江南大学博士学位论文况下，原始的粒子群优化算法既不能收敛到全局极值点，也不能收敛到局部极值点，但 是这种证明是非构造性证明，对于理解算法的工作原理没有太大帮助。三是整个粒子系 统随时间的演化和分布，这方面的研究目前还少有人涉及。 （2）粒子群优化算法的改进 这方面的内容非常庞杂，从改进的策略来说，可以分为如下几种类型，一是从算法 本身的改进，例如对算法迭代式的改进[14]，或对算法参数的优化[15]优化函数的形状。以 上这些方法，从根本上说，主要是为了克服粒子群优化算法在优化多峰复杂函数时，会 出现早熟，粒子的多样性减低，以致于不能收敛到全局极值点的现象。 （3）粒子群优化算法的应用 粒子群优化算法的应用已经扩展到很多领域，从最初的复杂多峰非线性函数的优 化、多目标优化等传统问题，到电力系统的分析，动态系统的跟踪与优化、神经网络的 权值训练并将其用于复杂系统的建模，非线性系统的优化控制问题等等。算法研究的目 的如何将粒子群算法应用于更多领域，同时研究应用中存在的问题也非常值得关注。 但是，算法的发展历史尚短，在理论基础与应用推广上都还存在以下问题。 1. 算法理论研究不深入，无法彻底剖析算法行为。算法收敛模型的建立和收敛性 的分析是算法基础，目前收敛模型的建立和收敛性的分析都困难。 2. 关于算法早熟收敛的问题。算法应用于高维或超高维复杂问题优化时，往往会 遇到早熟收敛的问题，也就是种群在还没有找到全局最优点时已经聚集到一点 停滞不动。早熟收敛不能保证算法收敛到全局极小点，这是由于算法早期收敛 速度较快，但到寻优的后期，其结果改进则不甚理想，即缺乏有效的机制使算 法逃离极小点。因而，算法早熟收敛研究也是一个值得的研究问题。 3. 由于目前大部分改进的 PSO 算法都不同程度的增加了算法的时间或空间复杂 度，如何在提高算法性能的同时精简算法的迭代流程是广大学者研究的方向。 4. 关于算法的应用局限性问题。对任何一个算法，有自己的应用局限性，算法也 不例外。它如何克服自己的应用局限性，如何结合其它算法去解决实际问题， 也是大量学者研究的课题。 针对上述问题，本文展开了细致的研究，对不同问题提出了相应的改进。并将改进 的算法应用到图像分割领域。1.3 课题的主要研究工作和组织结构在本论文中，根据提出的问题，对算法进行了较为深入的研究。本文的主要研究内 容与创新点可归纳如下： 1 针对本课题组推出的 Quatum-behaved PSO(QPSO)存在的对于高维函数寻优困难 的缺点，提出了一种基于协作方法的 Cooperative QPSO(CQPSO)算法。该方法通过把优 化的解空间细化为每一个单维优化的目标，从而有效的解决了高维函数的优化问题；另 外，针对协作方法存在的时间复杂度高的问题引入了适应度比例方法，使参与协作方法 的粒子仅为选择后的粒子，有效的解决了时间消耗过大的缺点。6 第一章 绪 论2 由于有关粒子群性能的分析都是把粒子群迭代公式中的随机量作为常量在收敛性 分析中进行考察，并没有反映出随机变量对于粒子速度的影响。而这两项是影响 PSO 算法随机性的最重要两个参数， 因此有必要对它们的作用进行详细的测试进而考察粒子 群的运动轨迹。 由于传统的概率论等数学分析方法难以细致的考察随机量在迭代过程中 的变化， 因此本文引入蒙特卡罗模拟方法详细的对粒子进化轨迹进行了考察从而分析出 粒子群收敛速度快以及早熟收敛的原因，为进一步对标准 PSO 算法进行改进提供了方 向。 3 针对目前 PSO 算法早熟收敛的缺点目前国内外主要通过添加变异因子的方法来改 善粒子的全局以及局部搜索能力， 但如何协调变异粒子的全局以及局部搜索能力却一直 没有得到很好的解决。本文针对以往变异算法的缺陷，提出了一种基于高斯变异的 PSO 算法，该算法有效的结合了全局以及局部变异因子的优点，在收敛速度以及全局搜索能 力上得到了一种很好的平衡，使得改进以后的算法不仅在收敛速度上得到了很大的提 高，而且保证改进以后的算法具有全局收敛的特性。 4 由于目前大部分改进的算法都是在 PSO 算法上添加了一定的因子或者是对 PSO 算法的参数进行调节，而不是对 PSO 算法根本上的改进。本文提出了一种基于随机搜 索策略的 PSO 算法，该算法不仅在收敛速度上以及寻优精度上优于同类比较算法，而 且相对于 PSO 算法来说它只有一个迭代公式以及控制因子，因此更为简单高效，更适 合在多种领域进行应用推广。 5 针对目前热点的图像分割问题结合粒子群算法收敛速度快的优点，在有效改善粒 子群局部收敛的缺点的前提下，把改进以后的粒子群算法有效的引入了 OTSU 分割算 法、Kapur 分割算法以及互信息量分割算法。同比其他优化算法，改进的算法精度更高， 效率更好，稳定性更强。 具体地，本课题内容共分七个章节展开： 第一章介绍本课题的研究背景，并概述本课题的主要研究工作。 第二章对优化算法和进化算法进行了介绍。 第三章主要对 PSO 算法以往收敛性分析进行了总结，同时针对以往收敛性分析方 法的缺点提出了基于蒙特卡罗模拟方法的分析方法。同时在本章对于当前流行的多种进 化算法针对大量的测试函数进行了测试。 第四章针对 QPSO 算法中粒子寻优受到维数限制的缺点， 提出了一种基于协作方法 的 QPSO 算法。同时把该算法与图像分割中的大律法（OTSU）结合起来，有效的解决 了标准 OTSU 方法寻优效率低的缺点。 第五章在分析了以往基于变异因子的 PSO 算法的优缺点的基础上，提出了一种基 于高斯变异的全局收敛的 PSO 算法，同时对于该算法的收敛性进行了证明。另外结合 图像分割中的 Kapur 算法验证了该算法高效可行。 第六章提出了一种简化的 PSO 算法，该算法不仅在收敛速度以及寻优能力上优于 同类比较算法，而且只有一个迭代公式和控制参数。另外结合图像分割中的互信息量方 法验证了该算法简单高效。7 江南大学博士学位论文第七章对全文进行了总结，并对进一步研究做了展望。8 第二章 优化算法介绍第二章 优化算法介绍粒子群算法主要应用于优化问题，但它起源于社会认知科学，因此，本章首先阐述 与算法相关的优化概念和技术。其次，针对当前比较热点的几种优化算法进行了比较和 讨论。以上内容将为后面算法改进和研究提供了必不可少的基础。2.1 优化研究基础优化是科学研究、工程技术和经济管理等领域的重要研究工具。它所研究的问题是 讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数，使设计方案 既满足设计要求又能降低成本资源分配中，怎样分配有限资源，使分配方案既能满足各 方面的基本要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜 枚举。优化这一技术，正是为这些问题的解决，提供理论基础和求解方法，它是一门应 用广泛、实用性很强的科学。 2.1.1 最优化问题 最优化问题是一种在可接受时间限制内对一个优化目标寻找最小值的问题 （寻找最 大值问题可以通过数学方法转化为寻找最小值问题）[16]。它对于很多领域的研究问题都 至关重要，例如：物理、化学以及工程领域等。这些领域的科学研究者不得不考虑在工 业以及社会资源的优化分配问题。一些问题仅仅包含线性优化问题，其他的一些问题则 为比较难以解决的非线性优化问题。最优化问题根据其目标函数、约束函数的性质以及 优化变量的取值等可以分成许多类型，每一种类型的最优化问题根据其性质的不同都有 其特定的求解方法，在本文中主要考虑非约束非线性优化问题。不失一般性，最小化问 题可定义为： 定义 2.1 如果存在 x W(P )量。min{ f (x ) : x W WR n }, f :彤R nRl（2.1）其中 f (x ) 为目标函数，W为可行解空间，R n 为整个 n 维欧式空间，x 为 n 维优化变 当 f (x ) 为线性函数，上述最优化问题即为线性规划问题，其求解方法有成熟的单纯 形法和 Karmarc 方法。当 f (x ) 中为非线性函数时，上述问题即为非线性规划题。非线性 规划问题相当复杂， 其求解方法多种多样， 但到目前仍然没有一种适合所有问题的方法。 非线性规划问题包括无约束优化问题和约束优化问题，由于函数的非线性，使得问 题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线 性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约 束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。总的 说来，求最优解或近似最优解的方法主要有三种枚举法、启发式算法和搜索算法。9 江南大学博士学位论文（1）枚举法。枚举出可行解空间内的所有可行解，以求出精确最优解。对于连续 问题，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最 优解。另外，当枚举空间比较大时，该方法的求解效率比较低。 （2）启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近 似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特 有的启发式规则，这种启发式规则无通用性，不适合于其他问题。 （3）搜索算法。该算法在可行解空间的一个子空间内进行搜索操作，以找到问题 的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地 利用一些启发知识，就可近似解，同时解的质量和求解效率达到一种较好的平衡。 搜索算法可分为两大类平行搜索法 （simultaneous methods） 和序贯搜索法(sequential methods)作平行搜索时，需要计算目标函数值的自变量节点位置在事先一起选定。而作 序贯搜索法时则根据前一轮计算得到的目标函数值的情况用以确定下一轮计算目标函 数值的自变量节点位置，因此它带有迭代性。搜索算法又可分确定性搜索法和随机性搜 索法两种。确定性搜索算法在寻优过程中，一个搜索点到另一个搜索点转移有确定的转 移方法和转移关系，因而其过程可再现，其不足在于寻优结果与初值有关，初值选取不 当往往有可能使搜索永远达不到最优点。随机性算法在算法执行过程中加入随机性因为 真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数，需计 算算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，但它的准确率 略微降低。 2.1.2 局部优化算法 定义 2.2 如果存在 x * ? B ，使得对 & xf x * Ｎ f (x ),B 都有：( )xB(2.2)成立，其中 B 烫SR n 。则称 x * 为 f (x ) 在 B 内的局部极小点。 f (x ) 为局部极小值。常见的优化方法大多为局部优化方法，都是从一个给定的初始点开始，依据一定的 方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟的局部 优化方法很多，如 Newton-Raphson 法、共扼梯度法、Fletcher-Reeves 法、Polar-Ribiere 法等，还有专门为求解最小二乘问题而发展的 Leven-berg-Marquardt(LM)算法。所有这 些局部优化算法都是针对无约束优化问题而提出的，而且对于目标函数均有一定的解析 性质要求，如 Newton-Raphson 法要求目标函数连续可微，同时要求其一阶导数连续。 对于约束非线性优化问题， 除了根据一阶最优化必要条件直接将最优化问题转换为 非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性 规划法、可行方向法、拉格朗日乘子法等。最常用的方法是将约束问题通过罚函数法转 换为无约束优化问题，然后再采用无约束优化方法进行求解。 2.1.3 全局优化算法 定义如果存在 x * ? S ，使得对 & xS ，有：10 第二章 优化算法介绍f x * Ｎ f (x ),( )xS成立，其中 S 为由约束条件限定的搜索空间，则称 x * 为 f (x ) 在 S 内的全局极小点，f (x ) 为其全局极小值。 到目前为止，全局优化问题也已存在了许多算法，如填充函数法等，但比起局部优 化问题的众多成熟方法，其间还有很大差距。 另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标 函数不连续、约束域不连通、目标函数难以用解析函数表达或者难以精确估计（如仿真 优化问题）等问题时，解析确定性优化方法就难以适应。 为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨 对函数解析性质要求较低甚至不做要求的随机型优化方法。最早的随机型优化方法是基 于 Monte-Carlo 方法的思想，针对具体问题性质的特点，构造以概率 1 收敛于全局最小 点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法，是近十多年来人 们模拟自然界的一些自然现象而发展起来的一系列仿生型智能优化算法，如禁忌搜索算 法，模拟退火算法、进化类算法、群体智能算法等。 2.1.4 没有免费午餐定理 最优化理论的发展之功是 Wolpert 和 Macready 提出了没有免费的午餐定理， 简称(No Free Lunch Theorem, 简称 NFL)[17，18，19]。NFL 定理的简单表述为对于所有可能的问题， 任意给定两个算法 A、B，如果 A 在某些问题上表现比 B 好（差） ，那么在其他问题上 A 的表现就一定比 B 差（好） ，也就是说，任意两个算法 A、B 对所有问题的平均表现 度量是完全一样的。该定理暗指，没有其它任何算法能比搜索空间的线性列举或者纯随 机搜索算法更优。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚 不清楚。在计算机上实现的搜索算法都只能在有限的搜索空间实施，所以该定理对现存 的所有算法都可直接使用。 NFL 定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。 虽然定理 是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本质。当我们 所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法间所表现出的效 应，即若算法在某些函数上 A 的表现超过 B 算法，则在这类的其他适应值函数上，B 算法的表现就比 A 要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在 整个函数类上的平均表现度量是一样的。 有了上述讨论， 关于优化算法的研究目标就应该从寻找一个大的函数类上的优化算 法转变为: (1)以算法为导向，从算法到问题。对于一个小的特定的函数集，或者一个特定的实 际问题，给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一 个“指示性”的算法。 (2)以问题为导向，从问题到算法。对于一个小的特定的函数集，或者一个特定的实 际问题，可以设计专门适用的算法。11 江南大学博士学位论文实际上，大多数在进化算法方面的研究工作可以看作是属于这一范畴的，因为它们 主要是根据进化的原理设计的算法，或者将现有算法进行部分改进，以期对若干特定的 函数取得最好的优化效果，这也是本文研究的一个重要基础。2.2 进化计算近十年来， 遗传算法 （Genetic Algorithm, GA 算法） 进化策略 、 （Evolutionary Strategy, ES） 、微分进化（Differential Evolution, DE） 、进化规划（Evolutioary Programming, EP） 等进化类算法在理论和应用两方面发展迅速、效果显著，并逐渐走向了融合，形成了一 种新颖的模拟进化的计算理论，统称为进化计算（Evolutionary Computation, EC） 。进化 计算的具体实现与形式称为进化算法（Evolutionary Algorithm, EA） ，进化算法是一种受 生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具 有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。 2.2.1 遗传算法 遗传算法最早是由美国 Michgan 大学的 J. Holland 博士提出的，1975 年，他出版了 其开创性的著作”Adaptive in Natural and Artificial Systems” 诞生。 遗传算法的操作对象是一组二进制串，即种群(Population)。每一个二进制位串被称 为染色体(Chromosome)或个体(individual)，每个染色体或个体都对应于问题的一个解。 从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，并使用交叉 (Crossover)和变异(Mutation)来产生下一代种群，如此一代一代进化下去，直至满足期望 的终止条件。 遗传算法可以形式化描述为：[20]，标志着遗传算法的正式GA = P (0), N , I , S , g, p, f ,t())1N ，表示初始种群。其中， P (0) = a1 (0), a 2 (0),..., a N (0)(I = B l = {0,1}表示长度为 l 的二进制串全体，称为位串空间。N 表示种群含有的个体数目，即群体规模。 l 表示二进制串的长度。S : I N ? I N 表示选择策略。g 表示遗传算子，通常它包括选择算子，交叉算子和变异算子。 p 表示遗传算法的操作概率，包括复制概率 pr ，交叉概率 pc 。和变异概率 pm 。f : I ? R n 是适应值函数。t :IN ?{0,1} 是终止条件。有关遗传算法的研究已相当丰富，包括编码方案、遗传算子的设计以及操作概率的 自适应性控制策略等，各种各样的改进算法层出不穷，其应用范围几乎可以涉及优化问 题的所有领域，有关遗传算法方面的专著在国内外也出现了很多。12 第二章 优化算法介绍2.2.2 进化策略 进化策略（Evolutionary Strategy， ES）是由德工业大学的 I. Rechnberg 和 H. P. Schwefel[21]等在 20 世纪 60 年代初提出的。早期的演化策略，其种群中只包含单个个体 且只使用变异操作。具体在每一操作代中，变异后的个体与其父代个体进行比较，从中 择优选取作为新一代个体，这就是所谓的策略。它所使用的变异算子主要是基于正态分 布的变异操作。 由于 (1 + 1) 策略难以收敛到最优解，且搜索效率相对较低。其改进的方法就是增加 种群内个体的数量。此时种群内含 u 个体，随机抽取一个个体进行变异，然后取代群体 中最差的个体。为了进一步提高搜索效率，后来又提出了 (u + l ) 进化策略和 (u , l ) 进化 策略。(u + l ) 进化策略是根据种群内的 u 个个体采用变异和重组产生 l 个个体，然后将 这 u + l 个个体进行比较选择 u 个最优者； (u , l ) 进化策略则是在新产生的 l (? u ) 个个 而 体中比较 u 最优者。 进化策略与遗体算法相比， 其主要不同之处在于遗传算法是将原问题的解空间映射 到位串空间上，然后再进行遗传操作，它强调的是个体基因结构的变化对其适应度的影 响，而进化策略则是直接在解空间上进行遗传操作，它强调的是父代到子代行为的自适 应性和多样性。 (u + l ) [22]的算法描述如下： 1.初始化：在解空间 W中均匀分布随机选取 u 个点 x 1 (0), x 2 (0),..., x u (0) 。这样得到 初始种群 X (0) = x 1 (0), x 2 (0),..., x u (0) ，置 k := 0 2.产生中间种群：执行 l 步（ l ? u ） 。 2.1 置 i := 1 。 2.2 以等概率从 X (k ) 中选取两个个体 x i 1 (k ) ， x i 2 (k ) 。^{}2.3 以杂交算子作用于 x i 1 (k ) ， x i 2 (k ) 以产生中间个体 x u + i (k ) ，其中杂交算子 为中间杂交，即：^x u + i (k ) = x i 1 (k ) + x i 2 (k ) / 2^()2.4变异：令x u + i (k ) = x u + i (k )/ 2，其中D x ~ N (0, s ) = N (0, s 1 ), N (0, s 2 ),..., N (0, s n ) ， N (0, s i ) 表示均值为 0，方差为 s i2 的正态分布，且 D x 的 n 个分量 D x 1, D x 2,..., D x n 之间相互独立。 2.5 若 x u + i (k ) W ，转 2.6；否则转 2.4. 2.6 若 i = l ，转步骤 3；否则置 i:=i+1,转 2.2.()T13 江南大学博士学位论文3.选择：从 x 1 (k ), x 2 (k ),..., x u + l (k ) 中选取 u 个函数值最小的个体组成新一代种群X (k + 1) = x 1 (k + 1), x 2 (k + 1),..., x u (k + 1) 。{}{}4. 终止检验：检验当前种群 X (k + 1) 是否产生满意解或已达到预设的进化时限， 若满足则停止；否则置 k := k + 1 ，转步骤 2. 2.2.3 进化规划 进化规划（Evolutionary Programming， EP）方法最初是由美国科学家 Lawrence J. Fogel 等人在 20 世纪 60 年代提出的[23, 别很小。 进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化 策略的变异相类似，也是对父代个体采用基于正态分布的操作进行变异，生成相同数量 的子代个体，即 u 个父代个体总共产生 u 子代个体。EP 采用一种随机一竞争选择方法， 从父代和子代的并集中选择出 u 个体构成下一代群体。其选择过程如下：对于由父代个 体和子代个体组成的大小为 2u 临时群体中的每一个个体， 从其他 2u - 1 个个体中随机等 概率地选取出个个体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较 的个体的适应值，则称该个体获得一次胜利。从 2u 个个体中随机等概率地选取出 q 个个 体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较的个体的适应值， 则称该个体获得一次胜利。 2u 个个体中选择出获胜次数最多的 u 个个体作为下一代群 从 体。 2.2.4 蚁群算法 蚁群算法[26, 27](AntC olonyA lgorithm ,ACA)是一种最新发展的模拟真实世界蚂蚁觅 食行为的仿生优化算法。1991 年，意大利学者 Dorigo M 在巴黎召开的第一届欧洲人工 生命会议(European Conference on Artificial Life. ECAL)最早提出了蚁群算法的基本思想; 1992 年，DorigoM 又在其博士论文中进一步阐述了蚁群算法的核心思想。 根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索的模型， 蚁群算法对搜索空间的“了解”是从观察蚁群觅食活动从中启发而建立的机制，主要包 括三个方面。 （1）蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会被选择，由此在蚁 群算法中建立 tabu(禁忌)列表来进行模拟 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信息 素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成 为蚂蚁之间进行通讯的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜 索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越 来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路 径的信息素强度，而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移1424, 25]。它在求解连续参数优化问题时与 ES 的区 第二章 优化算法介绍而蒸发。因此，模拟这种现象从而利用群体智能建立的路径选择机制，使蚁群算法的搜 索向最优解推进. 下面就以求解 n 个城市的 TSP 问题为例，介绍基本蚁群算法的实现步骤: 先作如下假设，令有 m 只蚂蚁， d ij (i,j=1,2 二 n)表示城市 i 和 j 之间的距离， t ij 表 示 t 时刻在 ij 连线上残留的信息量。 (1 ) 参数初始化。令时间 t=0 和循环次数 Nc=O， 设置最大循环次数 Ncmax， 将 m 个蚂蚁置于 n 个城市上， 令有向图上每条边 (i , j ) 的初始化信息量 t ij (t ) = const ，其 中 const 表示常数， 且初始时刻 D t ij (0) = 0 ，其中 D t kij (t ) 表示第 k 只蚂蚁在本次循环中 留在路径(i,j)上的信息量。 (2 ) 循环次数 Nc ? Nc (4 ) 蚂蚁数目 k ? ka1.(3 ) 蚂蚁的禁忌表索引号 k=1.1(5 ) 蚂 蚁个体根据状态转移概率公式计算的概率选择城市 j 并前进.pij (t ) = 轾 (t ) * 轾h b tj D 犏 ij 犏 臌 臌 a 轾 (t ) * 轾h tl D 犏 lj l? m 犏 臌 臌j? t (t + 1) = (1 - r ) * t (t ) + D t (t ) 式中, D h (t ) 为启发函数，表示在j jbijt 时刻从城市 i 到城市 j 的概率，表达式为D hij = h j - hi ，其中 hi 为对应的适应度函数值。如果城市 j 在 t 时刻被进过了则D t j (t ) = t j (0) = 1 ，否则为 0. a 表示信息启发因子，其值越大，该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强； b 为期望启发因子，表示能见度的相对 重要性，其值越大，越接近于贪心规则。 （6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到 该个体的禁忌表中。 （7）若集合 C 中城市未遍历完，即 k&m，则跳转到第(4)步，否则转第(8)步。 （8）若 满 足 结束条件，即循环次数 NC&=NCmax，则循环结束并输出程序计算 结果。 2.2.5 微分进化 1995 年，Storn 和 Price 提出了一种新的进化算法：微分进化 [28,29]（DifferentialEvolution，DE） ，和其它的进化算法相比，DE 算法容易理解、易于实现、有很强的空 间搜索能力。 作为一种新颖的搜索算法， DE 算法首先在搜索空间内随机产生初始群体， 然后通过将群体中两个成员间的差向量增加到第三个成员的方法来生成新的个体。如果 新个体的适应度值更好，那么新产生的个体将代替原个体。15 江南大学博士学位论文DE 算 法有 三个 主要 操作也 称为 变异 （ Mutation ） 交叉 （ Crossover ）和 选择 、 （Selection） ，但是这些进化操作的实现和 GA 等其它进化算法是完全不同的。设群体 规 模 为 NP ， 向量的维度为 D ，那么群体中的目标向量可以用x i = 轾1, x i 2 ,..., x iD (i = 1,..., NP ) 表示。对于任意一个目标向量 x i 而言，按下面公式 xi 犏 臌vi = x r 1 + F * (x r 2 - x r 3 ), i = 1,..., NP其中 x r 1 ， x r 2 ， x r 3 是群体中随机选择的三个个体，并且 r1 构r2r3i 。F 是一个介于[0，2]间的实型常量因子，用于控制差向量的影响，一般称为放缩因子。显然差向 量越小，扰动也就越小，这意味着如果群体靠近优化值，扰动会自动减小。 DE 算法的交叉操作的目的是通过变异向量 v i 和目标向量 x i 的结合以提高变异向量ui 的多样性。算法通过下面公式生成新的向量 u i = 轾1, u i 2 ,..., u iD : 犏 臌 ì v if randb ? CR OR j randr ? ji ? j = 1 , . .D , . u ji = í ? x ji if randb & CR OR j randr ? ? ?这里，randb 是[0,1]间的随机数；CR 是范围在[0,1]间的常数，称为交叉常量，CR 的值越大，发生交叉的可能性越大，CR=0 表示没有交叉；randr 是在[1,D]随机选择的整 数，它保证 u i 至少要从 v i 中获得一个元素，否则就不会有新的向量生成，群体也就不会 发生变化。 DE 算法中的选择操作，是一种“贪婪”选择模式，当且仅当新的向量个体 u i 的适 应度值比目标向量个体 x i 的更好时，u i 才会被保留到下一代群体中。否则，目标向量个 体 x i 仍然保留在群体中，再一次作为下一代的父向量。2.3 本章小结在本章中，首先对最优化方法进行了详细的描述，在这些基础知识的指导下，研究 PSO 算法就会有规律可寻。另外对于当前大量的进化算法进行了详细的描述，这对研究 PSO 算法提供了借鉴与参考的资源。16 第三章 粒子群算法分析第三章 粒子群算法分析粒子群算法的发展十分迅速，研究者对其改进也非常多，但其基本原理相差无几。 本章首先阐述原始算法的原理；其次对算法发展概况进行了综述；然后对目前最常用的 惯性权值粒子群算法进行了收敛性分析。最后对几种常用的进化算法进行了性能比较分 析。3.1 粒子群优化算法3.1.1 算法原理 如第一章所述，粒子群算法兼有进化计算和群智能的特点。起初 kennedy 等只是设 想模拟鸟群觅食的过程，但后来发现 PSO 算法是一种很好的优化工具。与其他进化算 法相类似，该算法模拟鸟群集体飞行觅食的行为，通过鸟之间的集体协作与竞争使群体 达到目的。在算法系统中，每个备选解被称为一个“粒子” ，多个粒子共存、合作寻优 近似鸟群寻找食物。算法先生成初始种群，即在可行解空间中随机初始化一群粒子，每 个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值（fitness value） 。 每个粒子将在解空间运动，并由一个速度决定其方向和距离。通常粒子将追随当前的最 优粒子而动，并经逐代搜索最后得到最优解。在每一次迭代过程中，粒子将跟踪两个极 值，一为粒子本身迄今找到的最优解 pbest ，另一为全种群迄今找到的最优解 gbest 。 数 学 模 型 描 述 为彤R n：考虑全局优化问题(P )min{ f (x ) : x W WR n }, f :R l ，则问题 (p ) 的多个可行解一个集合称为一个种群(swarm).种群中的每个元素（可行解）称为一个粒子(particle)。微粒的个数称为 种群规模(size)。用 n 维向量 X i = (x i1, x i2,....,x i n) W 来表示第 i 个粒子的位置，用TV i = (vi1, vi2,....,vi n) W 来表示第 i 个微粒的速度。微粒在搜索空间飞行过程中，它自身经历的最佳位置为 Ppi = (ppi 1, ppi 2, ...., ppin ) ， 所有微粒经历过的最佳位置用索引号 g 来表 示，即 Pg 。因此，微粒在每一代中的速度和计算函数的评价函数的位置可通过如下两个 公式进行变化：vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t ) + c 2rand 2 * pgd - x id (t )TT()()(3.1) (3.2)x id (t + 1) = x id (t ) + vid (t + 1)其中： i = 1, 2,...,m ； d = 1, 2,..., n ； rand1 和 rand2 是服从U (0, 1) 分布的随机数； 学习因子 c 1 和 c 2 为非负常数，c1 = c2 = 2 ；vid = [- v max , v max ]，v max 是由用户设定的速度 上限。 算法迭代过程描述为：Initialize population: random X i17 江南大学博士学位论文repeat: for each particle i ? [1, S ] if f X i & f Pi( )( )Pi = X iend if f Pi & f Pg( )( )Pg = Piend update the position and velocity of particle using equation (3.1), (3.2) end until termination criterion is satisfiedPSO 算法的研究主要分为两个方面：算法性能的提高，收敛性的分析。在接下来的 部分主要对这两个方面进行分析。其中第二节主要对改进的算法进行分析，第三节主要 介绍收敛性的分析。 3.1.2 算法流程 基本粒子群算法的流程如下 （1）依照初始化过程，对粒子群的随机位置和速度进行初始设定。 （2）计算每个粒子的适应值。 （3）对于每个粒子将其适应值与所经历过的最好位置 pbest i 的适应值进行比较，若 较好，则将其作为当前的最好位置。 （4）对于每个粒子将其适应值与全局所经历的最好位置 gbest 的适应值进行比较， 若最好，则将其作为当前的全局最好位置。 （5）根据方程（3.1）和方程（3.2）对粒子的速度和位置进行进化。 （6）如未达到结束条件通常为足够好的适应值或达到一个预设最大代数，则返回 步骤（2） 。 3.1.3 社会认知行为分析 在式（3.1）所描述的速度进化方程中，其第一部分为粒子先前的速度；其第二部分 为“认知”部分，因为它仅考虑了粒子自身的经验，表示粒子本身的思考。如果基本粒 子群算法的速度进化方程仅包含认知部分，即vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t )()则其性能变差。主要原因是不同的粒子间缺乏信息交流，即没有社会信息共享，粒 子间没有交互，使得一个规模为的群体等价于运行了单个粒子，因而得到最优解的概率 非常小，收敛速度大大降低。 式（3.1）的第三部分为“社会”部分，表示粒子间的社会信息共享。若速度进化方 程中仅包含社会部分，即vid (t + 1) = vid (t ) + c2rand 2 * pgd - x id (t )()18 第三章 粒子群算法分析则粒子没有认识能力，也就是社会的模型。这样，粒子在相互作用下，有能力到达 探索空间，虽然它的收敛速度比基本粒子群算法更快，但对于复杂问题，由于粒子群的 快速聚集性造成了无法对整体搜索空间进行较好的搜索，因此容易陷入局部最优点。 3.1.4 全局模型与局部模型 以上算法描述中，粒子跟踪两个极值，自身极值和种群全局极值，称为全局版本算 法，如图 3.1（a） 。另一种为局部版本算法，指粒子除了追随自身极值外，不跟踪全局 极值，而是追随拓扑近邻粒子当中的局部极值，如图 3.1(b)。在该版本中，每个粒子需 记录自己和它邻居的最优值， 而不需要记录整个群体的最优值， 对于局部版本， （3.1） 式 更改为：vid (t + 1) = vid (t ) + c1rand1 * p pid - x id (t ) + c2rand 2 * pid - x id (t )()()（3.3）其中 pid 为局部最优点。 比较全局和局部版本两种算法，可注意到，它们收敛速度和跳出局部最优的能力有 所差异。由于全局拓扑结构中的所有粒子都进行信息共享，粒子向当前最优解收敛的趋 势非常显著，因而全局模型通常收敛到最优点的速度较局部结构快，但更易陷入局部最 优，表现为整个种群一致收敛到当前第一个较好的解。局部拓扑结构模型则允许粒子与 其邻居比较当前搜索到的最优位置，从而相互之间施加影响，即便其值比种群最好值要 差，该影响可以使较差个体进化为较好的个体。局部版比全局版收敛慢，但不容易陷入 局部最优。（a）gbest 模型 （b）lbest 模型 图 3-1 两种拓扑结构 Fig.3-1 Two Structure of Tepology3.2 粒子群改进算法近年来，对于粒子群算法的改进算法有很多种，主要从改善粒子群算法的性能这个 方面着手。改善粒子群算法性能的方法主要有： （1）与其他算法进行结合； （2）基于变 异行为的 PSO 改进算法； （3）改进 PSO 迭代公式。 3.2.1 与其他算法结合 虽然粒子群算法相对于其他进化算法来说具有算法简单、收敛速度快的优点，但由 于粒子群算法对于复杂函数求解过程中仍然存在易于陷入局部最小点的缺点，很多学者 考虑把其他具有全局搜索能力的进化算法与 PSO 算法结合起来以获得更好的性能。19 江南大学博士学位论文遗传算法相对于粒子群算法来说，由于具有着变异因子和交叉因子的影响，具有着 比粒子群算法更为优异的全局搜索能力。文献[31，33,33]把遗传算法和 PSO 的优点很好的结合在一起，实验结果表明改进以后的算法相对于遗传算法来说收敛速度更为快速，相 对于 PSO 算法来说具有了更好的全局搜索能力。最近几年由于微分进化算法的大量推 广，很多学者也把 DE 和 PSO 算法进行结合改进[34,35, 36]。R. Xu 等[34]利用改进以后的DEPSO 算法对神经网络进行训练。主要方法是先用 PSO 算法对粒子进行训练，在下一 次的迭代过程中使用 DE 算法对粒子群进行进化。如此往复从而可以提高粒子群的多样 性以达到改善全局搜索能力。 3.2.2 基于变异行为的 PSO 改进算法 这类算法主要是借鉴遗传算法中的变异因子来改善粒子群算法的全局搜索能力。 但 和遗传算法不同的是，变异系数不仅仅局限于均匀分布函数[37,38]。比较常用的是高斯变 异[39,40]，柯西变异[41-43]，小波变异[44]等。 赫然[37]等针对粒子群算法的后期速度下降的弱点， 提出了一种基于自适应逃逸策略 的改进算法。当粒子速度下降到某个设定的阈值时，该粒子速度值将随机的在整个速度 空间内按均匀分布函数得到一个较大的速度值，从而使得粒子群在任意时刻都具备跳离 局部最小点的可能性，该算法相对于标准 PSO 算法来说全局搜索能力大大改善。 Kennedy[40]提出了一种基于高斯函数的粒子群算法， 它不同于传统的 PSO 算法研究中的 轨迹方法，即通过速度的调控产生下一代粒子的位置，取而代之的是高斯分布的方法。 H. Hu[41]等提出了一种基于 Cauchy 变异的粒子群算法。 该算法利用个体最优解未更新的 次数为触发点， 借以协助粒子跳出局部最优点。 H. Ling[44]等利用震荡系数对小波母函 S. 数的变化区间的影响提出了一种基于小波函数的粒子群改进算法。该算法在运行初期允 许随机选择的粒子在较大区间内进行小波变异，而在粒子进化后期给予粒子以较小的变 化区间，由于较好的平衡了全局和局部搜索，该算法在以上几种变异方法中取得了较好 的成绩。 比较这些变异策略来看， 一个共同点就是给予被变异的粒子以较大的速度值从而可 以跳出当前局部最小点；另外变异函数的选取对于实际结果也有一定的影响。以原点为 中心的 Gaussian 和 Cauchy 分布的概率密度函数分别为f (v ) = 骣 v2 ÷ ÷ exp ?? ? 2s ÷, - ? ? 桫 ÷ 2ps 1 v&f (v ) =1 a * 2 ,- ? p a + v2v&其中为了覆盖整个速度空间，Gaussian 和 Cauchy 分布的参数分别设置为 s = 0.16 ，a = 0.32 。为了覆盖整个速度空间 Morlet 小波母函数可表示为y (x ) = e - x2/2cos (5x )- 2.5 x ＃2.520 第三章 粒子群算法分析图 3-2 小波，柯西，高斯函数比较图 Fig. 3-2 The comparision of Wavelet, Cauchy and Gaussian从图 3.2 的结果可以看出，高斯函数在同等状态下可以获得较大的变异数值，而小 波函数则获得了较小的变异数值，而且在同等状态下还可以产生负值。根据仿真表明小 波函数在局部变异中获得了较好的成绩，而对于那些需要对 PSO 算法位置最大值进行 限制的函数中获得了其他两种算法无法获得的好成绩。因此，我们可以得出结论，三种 变异函数应该根据具体变异策略而选取。 3.2.3 针对粒子群迭代公式的改进 在这一类型的改进方法中，应用比较广泛的有带惯性权重的粒子群算法、带收缩因 子的粒子群算法。 为了更好的协调全局搜索能力和收敛能力，shi[45]等人引入了惯性权重 w ，则（3.1） 式变为：vid (t + 1) = wvid (t ) + c1rand1 * p pid - x id (t ) + c2rand 2 * pgd - x id (t )()()（3.4）由（3.2）（3.4）式组成的迭代算法通常被认定标准的 PSO 算法。 、 显见，惯性权重 w 描述了粒子上一代速度对当前代速度的影响。控制其取值大小可 调节算法的全局与局部寻优能力。w 值较大，全局寻优能力强，局部寻优能力弱，反之， 则局部寻优能力增强，而全局寻优能力减弱。基本 PSO 算法可以看作 w = 1 ，因此在迭 代后期缺少局部搜索能力。实验结果表明，在[0.8, 1.2]之间时，算法有更快的收敛速度。 文献[45]中试验了将设置为从 0.9 到的 0.4 线性下降， 使得算法在开始时探索较大的区域， 较快地定位最优解的大致位置，随着逐渐减小，粒子速度减慢，开始精细的局部搜索。 该方法加快了收敛速度，提高了算法的性能。当待解问题很复杂时，该法使得算法在迭 代后期全局搜索能力不足，导致不能找到要求的最优解，这可以用自适应改变惯性权重 来克服。 Clerc[46,47]建议采用收缩因子的方法，通过正确选择控制参数 c 1 ，c 2 和 w 来保证算法 收敛。其速度更新方程为：vid (t + 1) = c vid (t ) + c1rand1 * ppid - x id (t ) + c2rand2 * pgd - x id (t )(()}
我要回帖
更多关于 167ppi是多少分辨率 的文章
更多推荐
- ·手机用什手机怎么拦截陌生号码号码不会第一声响铃？设置拦截了别人也不知道的 方法有没有？或者打过来直接自动挂断
- ·求邓紫棋最新明星同款鞋图片子
- ·请问下这个SILsil安全等级认证软件在风险评估中的重要性是什么？
- ·淘宝手机版企业店铺宝贝详情图片大小尺寸要多大？
- ·电子商务下的配送中心的概念有哪几种方式?
- ·怎样在微信读书邀请好友找到之前阅读的好友
- ·灌篮高手日语版在线百度云，有的话百度云加个好友！
- ·共享时代怎么赚钱平台能赚钱吗
- ·宝骏510自动挡配置配置都有哪些
- ·苹果平板小米平板3 ipadmini42刷系统忘了ID怎么办
- ·Ios 贴吧是不能直播斗鱼手游直播了是吗
- ·win7光盘win7安装映像文件件该如何安装呢？
- ·谁有韩剧 the theking2hearts下载 的百度云中字资源？谢谢
- ·程序中序遍历的非递归算法遍历
- ·各位大佬 这将游戏手柄映射为键盘用手柄和键盘玩 哪个更
- ·台式机网卡坏了怎么办坏了深圳景田电脑维修推荐哪家好
- ·求《牯岭街少年杀人事件4k》百度云资源 中文字幕
- ·urbox盒子下载怎么推广让别人下载?
- ·骁龙625玩游戏60aie好吗，x21玩游戏怎么样
- ·各位，ae中有没有PS中分辨率与ppi（ppi）的概念
- ·新浪微博热搜 知乎的"知乎邵工"这个人是谁呀,怎么在微博热搜 知乎上这么火红呢?
- ·知道多久可以现在成为者恢复记忆忆 还能不能恢复成
- ·求凉生我们可不可以忧伤不忧伤全集百度云
- ·轻度hpv是什么意思怎么回事
- ·微信支付和支付宝区别和微信为什么要接入网联
- ·锐龙 内存支持的频率1600x，请教大神，为什么内存频率拉高，cp
- ·国内有哪些pwa应用大全
- ·凯翼x3怎么安装软件能安装车顶帐篷吗
- ·QQ查询,怎么查询QQ谈判记录内容怎么写如何查询QQ内容
- ·求 四个字母圈资源百度云的百度云资源！谢谢！
- ·求电影资源、百度云盘、《梅丽莎百度云盘》中文字幕
- ·爱因你而在慕晴何而为,终身可网,
- ·可以用第一人称写作文任务驱动型作文吗？
- ·派出所录指纹采血拍照查房要手机号Q号还拍照是什么意思，这资
- ·哪个配置有哈曼卡顿音响音响
