&>&改进粒子群优化算法..
改进粒子群优化算法..
上传大小：1.99MB
基于量子粒子群的改进投影寻踪聚类算法，多次仿真实验证明此算法有效、可行。并进一步运用该算法对生物信息学中的数据进行聚类分析，如乳腺癌细胞，Iyer基因表达谱数据，结果仍然比较理想。此后，将进一步深化聚类算法在生物学领域中的应用。
综合评分：4.3（3位用户评分）
下载个数：
{%username%}回复{%com_username%}{%time%}\
/*点击出现回复框*/
$(".respond_btn").on("click", function (e) {
$(this).parents(".rightLi").children(".respond_box").show();
e.stopPropagation();
$(".cancel_res").on("click", function (e) {
$(this).parents(".res_b").siblings(".res_area").val("");
$(this).parents(".respond_box").hide();
e.stopPropagation();
/*删除评论*/
$(".del_comment_c").on("click", function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_invalid/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parents(".conLi").remove();
alert(data.msg);
$(".res_btn").click(function (e) {
var parentWrap = $(this).parents(".respond_box"),
q = parentWrap.find(".form1").serializeArray(),
resStr = $.trim(parentWrap.find(".res_area_r").val());
console.log(q);
//var res_area_r = $.trim($(".res_area_r").val());
if (resStr == '') {
$(".res_text").css({color: "red"});
$.post("/index.php/comment/do_comment_reply/", q,
function (data) {
if (data.succ == 1) {
var $target,
evt = e || window.
$target = $(evt.target || evt.srcElement);
var $dd = $target.parents('dd');
var $wrapReply = $dd.find('.respond_box');
console.log($wrapReply);
//var mess = $(".res_area_r").val();
var mess = resS
var str = str.replace(/{%header%}/g, data.header)
.replace(/{%href%}/g, 'http://' + window.location.host + '/user/' + data.username)
.replace(/{%username%}/g, data.username)
.replace(/{%com_username%}/g, _username)
.replace(/{%time%}/g, data.time)
.replace(/{%id%}/g, data.id)
.replace(/{%mess%}/g, mess);
$dd.after(str);
$(".respond_box").hide();
$(".res_area_r").val("");
$(".res_area").val("");
$wrapReply.hide();
alert(data.msg);
}, "json");
/*删除回复*/
$(".rightLi").on("click",'.del_comment_r', function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_comment_del/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parent().parent().parent().parent().parent().remove();
$(e.target).parents('.res_list').remove()
alert(data.msg);
//填充回复
function KeyP(v) {
var parentWrap = $(v).parents(".respond_box");
parentWrap.find(".res_area_r").val($.trim(parentWrap.find(".res_area").val()));
评论共有2条
内容不错，不过没有代码...
内容符合标题，偏向于数学专业，无代码
审核通过送C币
广东工业大学考研真题及答案整理汇总
创建者：qq_
上百套精品PPT模板专题
创建者：fantasysxan
平面设计师/UI设计师 必读书单大集合，强烈推荐。
创建者：qq_
上传者其他资源上传者专辑
VIP会员动态
CSDN下载频道资源及相关规则调整公告V11.10
下载频道用户反馈专区
下载频道积分规则调整V1710.18
spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip
资源所需积分/C币
当前拥有积分
当前拥有C币
为了良好体验，不建议使用迅雷下载
改进粒子群优化算法..
会员到期时间：
剩余下载个数：
剩余C币：593
剩余积分：0
为了良好体验，不建议使用迅雷下载
积分不足！
资源所需积分/C币
当前拥有积分
您可以选择
程序员的必选
绿色安全资源
资源所需积分/C币
当前拥有积分
当前拥有C币
(仅够下载10个资源)
为了良好体验，不建议使用迅雷下载
资源所需积分/C币
当前拥有积分
当前拥有C币
为了良好体验，不建议使用迅雷下载
资源所需积分/C币
当前拥有积分
当前拥有C币
您的积分不足，将扣除 10 C币
为了良好体验，不建议使用迅雷下载
你当前的下载分为234。
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
改进粒子群优化算法..当前位置： >>
粒子群算法优化及其在图像检索中的应用研究
代号10701 TP301.6学 密号 级 公开分类号题（中、英文）目粒子群算法优化及其在图像检索中的应用研究 Research on Particle Swarm Optimization and its Application in Image Retrieval作者姓名 学科门类高璇 工学指 导 教 师 姓 名 、 职 称 姜建国 教授 学科、专业 计算机应用技术提交论文日期二○一三年三月
西安电子科技大学 学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：___________________日期：________________西安电子科技大学 关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件， 允许查阅和借阅论文； 学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 （保密的论文在解密后遵守此规定） 本学位论文属于公开，在 年解密后适用本授权书。 导师签名：________________ 日 期：________________本人签名：________________ 日 期：________________
摘要粒子群优化算法是一种基于群体智能的进化计算技术，是受到了鸟类规律性 集群活动的启发，进而在群体智能基础上建立的数学模型。粒子群优化算法在对 动物群体行为观察的基础上，利用了群体中个体间的信息共享，使整个群体在求 解空间中呈现从无序到有序的进化过程，进而得到问题的最优解。该算法的优势 在于简单、 容易实现并且没有过多参数需要调整。 目前已被广泛应用于函数优化， 组合优化，神经网络训练，模糊系统控制等领域。然而粒子群算法在理论与实践 上都不够成熟，在使用粒子群算法解决实际问题，尤其是复杂优化问题时，存在 早熟、收敛精度低和收敛速度慢等问题。因此，如何有效地改进粒子群算法以使 其能够更好地求解实际问题，成为了近年来该领域专家重点研究的问题。 针对粒子群算法存在的上述问题，本文提出了一种采用混沌搜索的自适应粒 子群优化算法。该算法采用了均匀设计的思想构造初始种群，使初始种群更均匀 地分布在搜索空间中，从而增加了初始种群的多样性，增强了算法的全局搜索能 力；在算法迭代过程中设计了自适应因子，并结合凹函数的特性改进了惯性权值 的更新策略， 使惯性权值的更新更符合种群进化的特征， 提高了算法的搜索效率； 在算法搜索过程中提出了采用混沌扰动的局部搜索策略，利用了混沌的不可预测 性，有效地避免了算法过早陷入局部最优解的现象，从而提高了收敛精度。实验 结果表明，本文提出的算法能够更快、更准确地收敛并有效地克服早熟现象。 随着计算机和网络技术的不断发展，数字图像等多媒体技术被广泛应用。如 何有效地组织、管理以及查找图像成为亟待解决的问题。图像检索技术在这样的 背景下被提出。鉴于粒子群算法的并行搜索及学习进化特性，本文提出了基于改 进的粒子群算法的图像检索方法。在基于内容的图像检索领域，采用单一的颜色 视觉特征往往不能明确地表达图像的内容，融合多种特征的图像检索技术成为了 研究的热点。本文设计了图像的不变矩向量作为图像的特征，兼顾了颜色及其空 间分布等信息。在图像特征提取时，对图像进行几何分割，计算各图像块的颜色 矩、图像边缘和信息熵等不变量构造图像的特征向量。并采用了本文改进的粒子 群算法进行检索。实验结果表明，本文提出的检索方法能够快速、准确地检索到 目标图像。 在后续的研究工作中，将继续研究粒子群的优化算法以及与其它算法的结合， 进一步加快收敛速度，提高求解精度，使其能够更好地适应实际工程应用中多峰 值、多目标问题。 关键词：粒子群优化算法 均匀设计 混沌变异 图像检索 特征向量
AbstractParticle Swarm Optimization (PSO) is an evolutionary computation technology based on the swarm intelligence. Inspired by birds' regular cluster activities, PSO is a mathematical model which is established on the basis of the swarm intelligence. Taking the advantage of the information’ sharing among the individuals within the population, Particle Swarm Optimization makes the evolution process of the population transform from disorder to order in the solution space, and then gets the optimal solution. The advantage of the algorithm is simple and easy to implement without too many parameters which need to be adjusted. Therefore, PSO has been widely used in function optimization, combinatorial optimization, neural network training, fuzzy systems control and other fields. However, PSO is immature enough both in theory and in practice. There is premature convergence, low convergence accuracy, slow convergence speed and other issues in the use of PSO to solve practical problems, especially the complex optimization problems. For this reason, the effective improvement of PSO algorithm to make it better adapt to actual problem has become the focus of the experts’ study in relative field in recent years. According to the problems mentioned above, an adaptive PSO algorithm using chaos searching is proposed in this paper. The concept of uniform design is used to construct the initial population of the algorithm, which makes the distribution of the particles more evenly, so as to improve the diversity of the initial population and enhance the global search ability of the algorithm. An adaptive factor is introduced in the evolution process of the algorithm and improves the update strategy of the inertia weight combined with the characteristics of the concave function. Thereby, not only the improved update strategy is more in accordance with the characteristics of the evolution, but also improves the search efficiency. Taking the advantage of the unpredictability of chaos, a local search strategy based on chaotic disturbance is proposed, which makes it possible to avoid the algorithm's falling into a local optimal solution effectively, thereby enhancing the accuracy of the convergence. The experimental results show that not only can the proposed algorithm convergence more effectively and accurately, but also overcome the premature convergence phenomenon. With the continuous development of the computer and network technology, digital image and other multimedia technologies have been widely used in all aspects of our daily life. So how to effectively organize, manage and retrieve image is the problem to be solved. Image retrieval is put forward in such a background. In view of thecharacteristics of parallel retrieval and evolutionary learning of the PSO algorithm, an image retrieval method based on improved PSO algorithm is proposed in this paper. In the field of content-based image retrieval, color features often fail to express the content of the image clearly. Image retrieval using the integration of a variety of features has become a hot research area. Taking both color and spatial distribution into consideration, a vector of invariant moment is designed as the characteristic of the image. Extracting image features within the geometric segmentation of the image, the feature vector is structured by calculating the color moment, edge and entropy for each image block. The experimental results show that the proposed retrieval method can get the target image rapidly and accurately. In the following research, a continuous study of the PSO algorithm as well as the combination of other algorithm would be done to make it converge much faster and improve the accuracy of the solution, so that it can be better adapted to engineering applications in multi-peak and multi-objective problems. Keywords: Particle Swarm Optimization Content-based Image Retrieval Uniform Design Feature Vector Chaotic Mutation目录第一章 绪论 ................................................................................................................ 1 1.1 研究背景..................................................................................................... 1 1.2 研究现状..................................................................................................... 3 1.2.1 粒子群算法研究现状........................................................................... 3 1.2.2 图像检索研究现状 .............................................................................. 5 1.3 本文工作..................................................................................................... 6 1.4 论文结构..................................................................................................... 7 第二章 粒子群优化算法概述 ..................................................................................... 9 2.1 群智能相关概念 ......................................................................................... 9 2.2 粒子群优化算法基本原理........................................................................ 10 2.3 粒子群算法的研究现状 ........................................................................... 13 2.3.1 混沌权值粒子群算法......................................................................... 13 2.3.2 双中心粒子群算法 ............................................................................ 14 2.3.3 基于距离度量的自适应粒子群算法.................................................. 16 2.4 粒子群算法的应用 ................................................................................... 17 2.4.1 函数优化 ............................................................................................ 17 2.4.2 神经网络训练 .................................................................................... 17 2.4.3 多目标优化 ........................................................................................ 17 2.5 经典测试函数 ........................................................................................... 18 2.6 本章小结................................................................................................... 21 第三章 粒子群算法的改进 ....................................................................................... 23 3.1 初始种群的构造 ....................................................................................... 23 3.1.1 均匀设计相关概念 ............................................................................ 23 3.1.2 基于均匀设计的种群初始化 ............................................................. 24 3.2 惯性权值更新策略的选择........................................................................ 26 3.2.1 惯性权值变化分析 ............................................................................ 26 3.2.2 基于凹函数特性及自适应因子的惯性权值更新策略....................... 27 3.3 基于混沌变异的局部搜索策略的设计 .................................................... 28 3.3.1 混沌的基本概念 ................................................................................ 28 3.3.2 基于混沌变异的局部搜索 ................................................................. 29 3.4 算法设计................................................................................................... 30 3.5 实验与结果分析 ....................................................................................... 313.6 本章小结 ................................................................................................... 34 第四章 基于内容的图像检索方法研究 .................................................................... 37 4.1 基于内容的图像检索 ............................................................................... 37 4.1.1 常用的图像特征 ................................................................................ 37 4.1.2 相似性度量标准 ................................................................................ 41 4.1.3 图像检索过程 .................................................................................... 42 4.2 改进的粒子群算法在图像检索中的应用 ................................................. 42 4.2.1 多特征不变矩向量的提取 ................................................................. 42 4.2.2 相似度的计算 .................................................................................... 47 4.2.3 基于粒子群优化算法的图像检索流程 .............................................. 48 4.3 实验与结果分析 ....................................................................................... 48 4.4 本章小结 ................................................................................................... 51 第五章 结束语 .......................................................................................................... 53 5.1 总结 .......................................................................................................... 53 5.2 展望 .......................................................................................................... 54 致谢 ............................................................................................................................ 57 参考文献 .................................................................................................................... 59 研究成果 .................................................................................................................... 63第一章 绪论1第一章 绪论基于从自然中获取智慧的理念，通过发现自然界所具有的独特规律，人们提 出了一系列仿生算法。这些算法具有自学习、自组织、自适应、鲁棒性强以及适 于并行处理等优点。它们属于计算智能，可以根据计算的过程和结果自发地调整 算法涉及到的各个参数，以达到求解问题最优结果的目的[1]。现实生活中的许多领 域都存在着传统人工智能技术难以有效解决、甚至无法解决的应用问题。因此， 计算智能的诞生和发展为摆脱传统人工智能所面临的困境提供了一种新的科学方 法和思路[2]。其中群智能作为一种新兴的演化计算技术，已在许多科研应用领域呈 现出了诱人的发展前景，如何有效地优化群智能算法使其适应日益复杂的各类工 程问题，引起了专家学者的广泛关注。1.1 研究背景优化技术是以数学为基础并广泛应用于求解各类工程问题最优解的一种应用 技术。其作为重要科学分支之一，备受专家学者的广泛关注，并迅速推广和应用 于各工程领域，如函数优化、系统控制、人工智能、模式识别、生产调度及计算 机工程等。由于实际工程问题具有复杂性、多峰值性、非线性以及难于建模等特 点，寻找一种适用于大规模数据且具有并行及智能特性的算法成为了相关领域专 家学者的重要研究目标及研究方向。自 20 世纪 80 年代以来，人们通过对生物系 统的行为和自然现象的研究和模拟，提取了其中所隐含的一般规律，为解决复杂 问题提供了新的思路和手段，并相继提出了一系列新颖的群智能优化算法，如人 工神经网络、遗传算法[3]、蚁群算法[4]、模拟退火算法[5]、粒子群算法[6]及其混合 优化策略等。这些算法以其独特的优点和运行机制，引起了国内外专家学者的广 泛关注，掀起了对该领域研究的热潮，并在工程实践中得到了成功应用。在优化 领域中，由于这些算法构造直观且隐含自然机理，因而被称作群智能优化算法， 或称现代启发式算法。 粒子群优化算法（Particle Swarm Optimization, PSO）是典型的群智能优化算 法，该算法是一种进化计算技术，于 1995 年由 Eberhart 博士和 Kennedy 博士提出[6]。 PSO 算法是受到鸟类集群规律性活动的启发， 进而利用群体智能建立的一个简化模型。鸟群飞行时经常排成某种队列，每只鸟在飞行时不断地变换飞行姿势和 飞行方向，以便同其它个体保持一定距离，每只鸟会根据自身经验与鸟群中其它 个体的信息，通过调整自身的速度及位置以达到最佳位置，而鸟群则根据个体的 表现使整体保持最优状态。鸟类具有记忆的能力，可以记下自己飞行过的最佳位 置，整个群体可利用这些记忆信息实现群体优化[7]。粒子群算法在对动物集群活动2粒子群算法优化及其在图像检索中的应用研究行为观察基础上，通过将鸟抽象为没有质量和体积的粒子，利用种群中各粒子间 的信息共享使整个群体在求解空间中呈现从无序到有序的演化过程，从而得到最 优解。PSO 算法以其收敛速度快、收敛精度高、容易实现等特点以及在解决实际 工程问题中表现出的优越性引起了各领域专家学者的广泛关注。 PSO 算法同遗传算法类似，是一种基于种群迭代的优化算法。但其不包含遗 传算法的交叉、变异等操作，而是粒子在求解空间中追随最优粒子进行搜索。尽 管对于如何将粒子群优化算法有效地应用到实际工程问题中的研究已取得了一定 的成果，但是大多数文献对粒子群优化算法在理论上的分析和研究目前仍处在初 级阶段，更多深入细致的工作还有待于进一步展开。 此外，随着多媒体技术的发展，图像作为一种重要的多媒体信息被广泛应用 于日常生活的各个领域，如何有效地管理图像数据库以及从中检索出所需图像成 为了亟待解决的问题。第一个以微电脑为基底开发的图像数据库检索系统，是由 80 年代麻省理工学院的 Banireddy Prasad 等所共同开发的。 大多传统图像检索的方式是利用增加元数据的方法，如字幕、关键词或图像 的说明等，如此便可以通过注解词完成检索。然而人工对图像进行注解耗时、费 力并且昂贵。从 20 世纪 90 年代初期开始，利用图像低层特征（如颜色、形状、 纹理）来检索图像的技术应运而生，这项技术被称为基于内容的图像检索技术 (Content-Based Image Retrieval, CBIR)。基于内容的图像检索是由 T.Kato 于 1992 年提出的[8]。他构建了一个基于颜色和形状的图像数据库，并提供了一定的检索功 能。基于内容的图像检索技术通过借助视觉信息进行从低层到高层的处理、理解 和分析，进而完成图像检索过程，能够在给定查询图像的前提下，依据图像内容 或特定的查询需求，在图像数据库中检索出满足检索条件的相应图像。 基于图像特征提取以实现图像检索的过程被广泛应用于科研领域，如统计学、 模式识别、信号处理和计算机视觉等，其在医学图像管理、多媒体数字图书馆、 商标与版权数据库管理、地理信息系统、罪犯调查等许多方面的成功应用展示了 其所具有的重要研究意义和巨大实用价值。虽然基于内容的检索技术的研究己经 取得了一定的进展，然而没有一种特征能够适用于任意类型图像的检索，并且存 在低层特征和上层理解之间的差异（即语义鸿沟） 。因此，如何充分地利用图像的 各种特征以及如何提高检索效率成为了国内外众多学者的主要研究课题及努力方 向。 基于内容的图像检索指的是查询条件本身就是一个图像，或者是对图像内容 的描述，其通过提取低层特征的方式建立索引，并通过计算、比较这些特征与查 询图像之间的距离以确定两幅图像的相似度[9]， 最终返回具有相同或相似内容的其 它图像。由不同低层特征共同构成的特征向量可以用来描述一幅图像，若对图像 库中的全部图像进行特征提取，便可得到一个特征向量空间。将目标图像对应的第一章 绪论3特征向量看作问题的“最优解” ，则检索图像的过程可看作利用粒子群算法在特征 向量空间迭代搜寻最优解的过程。1.2 研究现状1.2.1 粒子群算法研究现状 自粒子群优化算法提出以来，其以操作简单以及易于实现的特点，引起了国 内外许多领域专家学者的关注。他们结合各自研究领域的特点对粒子群算法进行 了不同的分析、实验和改进，取得了一定的研究成果，并将其成功应用于实际的 工程优化问题中。 最初的 PSO 算法主要用于解决单目标优化问题， 自 2001 年以来， 许多用于解决多目标问题的粒子群优化算法研究成果相继发表。针对粒子群算法 容易早熟收敛、 进化后期收敛速度慢和收敛精度低等缺陷， 出现了许多优化策略。 现阶段对 PSO 算法的研究主要集中在惯性权值的选择策略，种群多样性的增 加，算法的数学分析以及与其它智能算法的结合等方面。 1）惯性权值的选择策略。 在实际工程应用中，所要求解的问题对 PSO 算法的局部搜索能力和全局搜索 能力有着不同的需求。即使在同一问题的不同阶段，对搜索能力的需求也可能是 不同的。自 1995 年 Eberhart 和 Kennedy 提出 PSO 算法，Shi.Y 与 Eberhart 在分析 了算法的参数选择的基础上， 于 1998 年在原始的 PSO 算法基础上引入了惯性权值[10]。惯性权值的引入更好地平衡了 PSO 算法的全局搜索与局部搜索能力。惯性权值越大，则算法的全局搜索能力越强，局部搜索能力越弱；反之，则算法的全局 搜索能力越弱，局部搜索能力越强。由此，带有惯性权值的 PSO 算法被学者们引 用作为标准 PSO 算法，并且文中指出当惯性权值的取值在 0.9 到 1.2 之间时，算法 具有更好的性能。 尽管惯性权值的引入对 PSO 算法性能有了较大改善， 但是 Shi.Y 和 Eberhar 并未给出惯性权值确切的计算公式。因此， Shi.Y 与 Eberhar 又相继提出 了线性递减惯性权值(LDIW)[11]、 模糊惯性权值(FIW)[12]和随机惯性权值[13]的算法 优化策略。尽管这些文章中对惯性权值的计算提出了相对明确的计算方法，但是 这些计算方法并不符合种群进化的一般规律，仍然在一定程度上限制了种群的进 化速度。 2）种群多样性的增加 标准 PSO 算法从随机解出发，通过迭代寻找最优解。其种群的多样性随着迭 代次数的增加而不断下降，致使标准 PSO 算法全局搜索能力受限，从而容易陷入 局部最优解，出现早熟现象。针对 PSO 算法的这一问题，谢晓峰等通过按照一定 的概率对粒子的速度和位置分别引入了随机扰动[14]，该方法在一定程度上增强了4粒子群算法优化及其在图像检索中的应用研究种群的多样性，使得不可逆的进化能够向着更好的适应值进化，从而有效地改善 了算法的性能。但是算法中并没有明确给出进行随机扰动的概率计算公式，即粒 子变异的概率是人为设定的。这种设定或许在某一特定条件下有效，但是并不适 用于一般情况。而且过大的变异概率在增加种群多样性的同时也会导致整个种群 混乱，不仅不能提高算法的性能，反而会使得算法的收敛速度降低，并且在一定 程度上增大了算法收敛于局部最优解的可能性。 3）算法的数学分析 在算法的数学分析上，与遗传算法等相比，标准 PSO 算法缺乏严格的数学论 证基础。粒子群系统本身是非线性离散时间系统，当前的主要分析方式是将其简 化为确定的线性离散系统，通过对单一粒子在各维的运动规律进行分析，进而研 究粒子运动的内在特性以及整个群体的特性。由于标准 PSO 算法在迭代过程中会 出现早熟现象，Bergh 和 Engellbrecht 等人在对算法收敛性进行了一定分析的基础 上，提出了一种保证收敛的粒子群算法(GCPSO)[15]，文章分析指出当粒子位置达 到最优后，粒子的移动速度仅取决于粒子的初始速度，即粒子将会只沿着一个方 向飞行直至边界或者找到更优的解为止，然而这样的粒子是无法找到更优解的。 为了确保搜索到全局最优解的粒子能够继续进行搜寻，文章针对搜寻到最优解的 粒子提出了改进的速度和位置的更新公式。即根据算法迭代过程中全局最优解变 化（不变）的次数，对搜索到全局最优解的粒子的速度和位置进行变换，尽管改 进的算法比标准 PSO 算法有更好或类似的收敛结果，但是算法中没有对进行变换 时全局最优解连续变化（不变）次数应满足度的门限值提出明确的计算方法，该 门限值是人为设定的， 其准确性有待进一步研究， 并且该算法无法保证全局收敛。 4）与其它算法的结合 许多专家学者尝试着将其它优化技术同 PSO 算法相结合，利用各算法的优点 构成混合算法。 1999 年 Angeline 首次将遗传算法中的选择子思想引入到 PSO 算法 中，提出了混合 PSO 算法[16]。该算法的主要思想是在每次迭代中根据粒子的适应 度进行排序并选择，用适应度较好的粒子代替适应度较差的粒子，从而引导搜索 向着适应度较好的方向进行。选择机制的引入使得算法能够将有限的资源分配给 更有利的搜索空间。虽然该算法在一定程度上加快了搜索速度，提高了算法的搜 索能力。但是，Angeline 并未给出算法在迭代中粒子替代的一般公式。使用适应度 较好的一半粒子代替适应度较差的另一半粒子，虽然加速了算法的收敛，但是也 增加了算法陷入局部极值的可能性，影响了算法的收敛精度。高鹰与谢胜利等人 将模拟退火机制引入 PSO 算法中[17]，结合了杂交和带高斯变异特点的 PSO 算法， 首先采用随机方式生成初始种群，并采用粒子群算法得到新的粒子；其次对各个 粒子分别进行杂交和带高斯变异运算；最后对各粒子进行模拟退火，将最终的运第一章 绪论5算结果作为种群的下一代。该方法增强了算法避免陷入局部极值的能力，但是由 于模拟退火算法速度较慢，因此引入的模拟退火机制使得 PSO 算法的收敛速度急 剧降低且并未有效改善算法的收敛精度。 尽管 PSO 算法还缺乏完善的理论分析以及严格的数学论证，但是由于其设置 参数少，易于实现，目前已被广泛应用于函数优化，神经网络训练，组合优化， 模式识别，多目标优化和图像处理等工程领域。PSO 算法的成功应用也推动了对 其研究的不断进展，本文将从种群多样性的增加，惯性权值的更新策略以及局部 搜索策略的设计三个方面对算法进行改进。 1.2.2 图像检索研究现状 基于内容的图像检索的研究已发展近 20 年，互联网中传统的图像搜索引擎， 如 Google、Yahoo 以及 MSN 等所提供的相关图像搜索功能，其依赖于由图像的注 解所建立的索引以实现搜索功能。这种从文字进而到图片的传统搜索方式并不是 真正的基于内容的图像检索。以文字诠释图像的内容虽然简单易于理解，但是随 着图像数据库的爆炸式增长，用文字很难准确表达图像确切的含义且工作量巨大； 文字标注包含了较多的主观因素，对于同一幅图像不同的人有不同的理解，进而 给出不同的注解；文字是一种抽象性的描述，其很难涵盖一幅图像所包含的所有 信息，尤其是颜色、形状和纹理等图像的低层信息。 现阶段对图像低层特征的提取，主要集中在颜色、纹理以及形状等对视觉有 较大影响的因素。 图像的这些低层特征来源于其视觉特征， 无需人为干预和解释， 且能够自动提取。 1）颜色特征的提取 颜色是图像最为直观的特征，在对颜色特征的提取方法中，使用参考颜色表 的方式具有较高的检索效率，但是其依赖于事先定义的参考颜色表，该方法并不 适用于当今日益扩大的图像数据库。Kankanhalli 和 Mehtre 提出了基于聚类的颜色 匹配方法[18]。文章中提出了采用集聚分析的方法从图像中提取主色及属于该类主 色的像素数目作为图像的特征，这种特征提取方法降低了特征空间的维数以及相 似性计算的复杂度，加快了图像匹配的速度，但是只提取主色的方式并不能有效 地表示一幅图像， 即涵盖不同内容的图像可能拥有相同的主色， 如天空和大海等； 并且单一的颜色特征使图像失去了许多其它有效信息，如位置、空间分布和纹理 等。 该方法在图像的表示方面存在较大误差， 同时对最终的检索精度有较大影响。 2）形状特征的提取 形状是图像视觉特征之一，其概念简单明确，并且通过形状特征以区分物体6粒子群算法优化及其在图像检索中的应用研究较为直观，因此形状特征被广泛应用于 CBIR 中。形状特征是在图像边缘检测的 基础上进行提取的，因此边缘检测的效果将直接影响检索结果。赵宏中和张彦超 提出了基于 Canny 边缘检测算子的图像检索算法[19]。首先，通过高斯滤波器对图 像进行平滑处理；其次，使用改进的 8 邻域 Canny 算子采用基于梯度方向的边缘 点检测和链接方法提取图像的边缘；最后，采用具有旋转不变和转置不变特点的 傅里叶描述子表示图像的形状轮廓向量，并以曼哈顿距离作为相似性度量标准进 行检索。 尽管该算法能够较好地保留图像连续且清晰的边缘， 提高了检索的性能。 但是，该方法并不是一种较为通用的检索方法，对于含有丰富边缘信息的图像该 方法效率较高，然而对于边缘信息较少的图像该方法却并不适用；对于同样的图 像主体，在不同环境下拍摄的图像其边缘信息是不同的，这也较大地影响了检索 的精度；采用这种单一的边缘信息的提取方式，对于在不同的环境下拍摄的包含 不同主体的图像，仍会得到相似的边缘信息。 CBIR 是一种基于图像低层视觉特征的相似性检索。通过前人的经验可以看出， 任何采用单一图像低层特征的图像检索都在图像内容表达方面存在缺陷，且都存 在难以逾越的语义鸿沟。因此，如何有效地利用图像的低层特征，将多特征加以 融合来表示图像以及有效的相似性度量方法成为近年来该领域的专家学者研究的 核心问题。本文将融合图像的多种特征以构造特征向量，并结合粒子群优化算法 的并行搜索和学习进化特性进行检索。1.3 本文工作本文通过分析影响粒子群算法性能的因素，提出了采用混沌搜索的自适应粒 子群优化算法；通过分析图像低层特征，设计了不变矩向量表示图像特征，并提 出了采用改进的粒子群算法的图像检索方法。 本文的主要工作如下： 1、研究了 PSO 算法及影响算法性能的因素 PSO 算法模拟了鸟类的群体行为，优化问题的解被定义为搜索空间中的一个 粒子，各粒子通过自身速度以及由求解问题所抽象成的函数所决定的适应度来确 定其飞行的方向和距离。随后粒子根据自身经验，跟随整个种群的最优粒子在搜 索空间进行搜索。因此，初始种群的构造，速度的更新以及搜索策略的选择等因 素对算法的性能有较大的影响。 2、提出了一种改进的粒子群优化算法 为使 PSO 算法能够有效地适应实际复杂优化问题，并能够快速、准确地收敛 至全局最优解。本文对 PSO 算法做了如下改进： 1）构造了采用均匀设计思想的初始种群第一章 绪论7PSO 算法是一种从随机解出发的进化算法，其通过迭代寻找最优解。初始种 群的优劣对算法的性能有较大影响。针对标准 PSO 算法中初始种群分布不均匀的 问题，本文采用均匀设计的思想构造了初始种群，使初始种群能够更均匀地分布 在搜索空间，从而增加了种群的多样性。 2） 提出了基于凹函数和自适应因子的速度更新策略 为使算法能够更快、更准确地收敛到全局最优解，本文分析了种群动态搜索 的规律，研究了惯性权值对算法收敛速度的影响，提出了一种基于凹函数的惯性 权值策略。同时，在惯性权值的更新策略中引入自适应因子，使惯性权值的变化 更符合种群搜索的动态特征。 3） 设计了采用混沌扰动的局部搜索 标准 PSO 算法中并没有采用局部搜索策略，在算法迭代过程中存在易陷入局 部最优解从而早熟的现象。为使算法能够有效地跳出局部极值，向全局最优解进 化。本文利用了混沌运动的随机性和遍历性，设计了采用混沌扰动的局部搜索策 略，使 PSO 算法能够有效地避免陷入局部最优解的问题。 3、提出了基于改进粒子群算法的图像检索方法 传统的使用文字标注图像和采用单一图像低层特征的方法，不能很好地表示 图像所含有的内容。为了能够有效地利用图像的视觉信息表示图像。本文采用了 颜色矩、信息熵等不变量设计了图像的特征向量，使特征向量能够更有效地反映 图像信息；使用了特征向量对粒子进行编码，将目标图像定义为全局最优解；利 用了粒子的学习性和并行性，提出了基于改进粒子群算法的图像检索方法，使粒 子在搜索空间不断进化寻优，从而得到最终检索结果。1.4 论文结构本文共分为五章，各章的主要内容安排如下： 第一章介绍了粒子群优化算法及图像检索的研究背景、国内外研究现状以及 本文工作等内容。 第二章研究了标准粒子群优化算法的基本原理及算法流程，分析了不同 PSO 优化算法的优缺点，介绍了 PSO 算法在函数优化、神经网络训练以及多目标优化 等领域的应用，最后给出了用于测试 PSO 算法性能的经典测试函数。 第三章分析了影响算法性能的因素，提出了一种改进的粒子群优化算法，即 采用均匀设计思想构造了算法的初始种群；设计了迭代过程中的自适应因子，并 结合凹函数的特点改进了惯性权值更策略；利用混沌思想设计了局部搜索策略。 最后，描述了改进粒子群优化算法的流程并进行了仿真实验。 第四章研究了粒子优化群算法在图像检索中的应用。8粒子群算法优化及其在图像检索中的应用研究研究了基于内容的图像检索中常用的图像特征以及相似性度量标准等内容； 设计了图像的不变矩特征向量，并结合改进的粒子群算法提出了图像检索方法； 对图像检索方法进行了仿真实验。 第五章对本文工作进行总结并对本文后续工作进行展望。第二章 粒子群优化算法概述9第二章 粒子群优化算法概述近年来，随着科技的不断进步以及科研领域的不断扩展和深入，许多实际工 程应用问题向着复杂化、多维化和多峰值化的方向不断发展。粒子群算法以其参 数设置少、易于实现等优点，在多目标优化以及人工神经网络等领域取得了广泛 且成功的应用。因此，国内外许多专家学者对粒子群算法进行了深入地研究和探 索，并结合各科研领域特点对算法提出了各种改进方案。 本章将对群智能的相关概念进行介绍，研究粒子群优化算法的基本原理及算 法流程，并分析混沌权值粒子群算法、双中心粒子群算法以及基于距离度量的自 适应粒子群算法三种从不同角度对粒子群进行改进的算法及其优缺点，随后研究 粒子群算法在函数优化、神经网络训练以及多目标优化等工程领域的应用，最后 给出几个用于测试粒子群算法性能的经典测试函数。2.1 群智能相关概念群智能是一种来源于生物群体行为规律的计算技术。它是受社会昆虫和群居 脊椎动物，如蚂蚁、鸟群和鱼群等的启发，能够解决实际复杂分布式问题的方法。 群体是指一群相互间可以直接或者间接通信的个体，这些个体能够通过相互合作 求解分布式问题。群智能是无智能的个体间通过相互合作而表现出的群体智能行 为的特性[20]。生物系统在处理问题的能力上较分离的单个个体所组成的独立系统 有大幅提高。而且生物群体系统所表现出的鲁棒性和解决复杂问题的能力，仅仅 是依靠个体间以及个体与环境间的交互规则所产生的。群智能能够在没有集中控 制和全局模型的条件下，为寻找复杂分布式问题的解决方案提供了新的求解方向 和思路[21]。 生物群体能够解决发现新的食物源、 种群内部劳动分工、 建筑庞大复杂巢穴、 迁徙以及在有限空间内进行协调调度等复杂问题。种群中的个体可以快速适应群 体组织的变化并处理外界的挑战，生物种群以及个体的这些特点在工程优化和计 算机科学中有着非常重要的实用价值。 群智能优化算法是一种概率搜索算法。种群中相互合作的个体是离散分布的， 这使其能够适应在网络环境下的工作状态；由于算法没有中心的控制与数据，因 此系统具有较强的鲁棒性，即不会由于某个或某些个体的原因而影响整个问题的 求解；个体之间通过间接方式进行通信合作，使系统具有更好的可扩展性；由于 系统中个体的增加不会对通信开销带来较大的影响，并且系统中每个个体的功能 较为简单且执行时间较短，这使得整个系统容易实现。 除了已被人们所认知和发现的生物系统规律外，来自其它领域的求解模型被10粒子群算法优化及其在图像检索中的应用研究相继引入群智能领域，并不断地推动着群智能领域的发展。无论群智能技术如何 改进，自组织、并行性和个体对于局部信息的利用等特性是群智能计算技术永恒 的基本准则。正是这些来源于生物系统的特性使得群智能方法被广泛应用于解决 大多数优化问题以及能够转化为优化求解的问题。群智能优化的应用已涉及多目 标优化、人工神经网络、数据聚类、模式识别、机器人控制、决策支持以及仿真 和系统辩识等领域。 目前， 对群智能优化技术的研究主要集中在群智能理论基础， 群体行为分析、 设计和控制以及基于群智能的人工集群系统优化等方面，且仍处于萌芽阶段，存 在较多亟待解决的问题。首先，群智能优化算法是概率算法，缺乏对其可行性与 可靠性证明的数学理论基础；其次，各种群智能优化算法是针对某些特定问题所 提出的，仅适用于其所针对的问题，没有较为通用的算法结构；最后，在群智能 优化算法中，种群的行为是通过种群中个体间的信息交互等行为所体现的，即需 要建立两者之间的映射关系，但是由于两者之间的差别较大，因此如何设计群智 能优化算法中两者之间的映射和个体之间的信息交互成为群智能优化算法中较难 解决的问题。尽管群智能算法仍不完善，但是由于使用其解决实际工程问题时易 于实现，且仅涉及基本数学操作以及数据处理过程，对系统资源要求较低，因此 群智能优化算法在各领域得到了广泛的认可。现有群智能优化算法的成功应用证 明了群智能优化方法能够有效解决全局优化问题。其潜在的并行性、学习性和分 布式等特点，为处理实际工程优化问题的复杂数据提供了技术保证。无论是在理 论还是应用研究领域，群智能优化算法都展示了重要学术意义和现实价值。2.2 粒子群优化算法基本原理群体智能优化算法是模拟自然界生物群体行为构造的随机优化算法，对其的 研究始于 20 世纪 90 年代初。粒子群优化算法是一种典型的群体智能优化算法。 粒子群优化算法采用了“群体”和“进化”的概念，依据个体的适应度进行操作。 粒子群算法不像其它进化算法那样对个体使用进化算子，而是将每个个体看作空 间中的一个没有重量和体积的粒子，并在搜索空间中以一定的速度飞行。该飞行 速度根据个体以及群体的飞行经验进行动态调整[10]。 粒子群算法，又称微粒群算法，是由美国社会心理学家 James Kennedy 和电 气工程师 Russell Eberhart 于 1995 年所共同提出的一种进化计算技术[22]，其基本 思想来源于对简化社会模型的模拟，是对鸟类群体行为进行建模和仿真研究的结 果。在鸟群寻找栖息地时，最初每只鸟沿着随机方向飞行，直到有一只鸟找到栖 息地，当停留在栖息地比留在鸟群中有更大的适应值时，鸟将会离开群体而飞向 栖息地。当一只鸟离开群体飞向栖息地时，它将影响周围的鸟，引导着它们也向第二章 粒子群优化算法概述11着栖息地飞行。当所有的鸟发现栖息地有较大的适应值时，将全部向其飞行，直 到整个鸟群降落在此。自然界中各种生物体都具有一定的群体行为，人工生命的 主要研究邻域之一便是探索自然界的群体行为，从而构建群体模型解决类似的工 程应用问题。虽然群体中独立个体的行为规则非常简单，但是大量个体在一起时 所表现出的群体行为却非常复杂[23]。 James Kennedy 和 Russell Eberhart 通过研究， 将鸟类寻找栖息地的过程引入工程应用中寻求特定问题最优解的过程，得到了 PSO 算法这一新的求解最优解问题的模型。 在 PSO 算法中，种群是由在搜索空间中随机生成的粒子组成，初始种群的规 模由实际问题所确定，每个粒子都有一个随机生成的速度矢量，以决定其移动的 方向以及移动的步长，每个粒子性能的优劣由根据求解问题抽象出的适应度函数 所得到的适应度值所确定。 在 D 维搜索空间，由 N 个粒子构成的群体中，在第 t 次迭代时，粒子 i 的位置 表示为 xi (t ) ? ( xi1 (t ), xi 2 (t ),..., xiD (t )) ； 其速度为 vi (t ) ? (vi1 (t ), vi 2 (t ),..., viD (t )) ； 粒子 i 所 经历过的具有最佳适应值的位置记为 pi (t ) ? ( pi1 (t ), pi 2 (t ),..., piD (t )) ，称之为个体最 优解；在迭代过程中所有粒子所经历过的具有最佳适应值的位置索引用符号 g 表 示，记为 pg (t ) ? ( pg1 (t ), pg 2 (t ),..., p gD (t )) ，称之为全局最优解。 假设 f ( x ) 为所需求解工程问题抽象出的适应度函数。以最小化问题为例，适 应度函数值越小，粒子的适应度越好，即粒子的性能越好。粒子 i 所经历过的个体 最优解对应位置的确定方式为：? p (t ) pi (t ? 1) ? ? i ? xi (t ? 1)其全局最优解的计算公式为：f ( xi (t ? 1)) ? f ( pi (t )) f ( xi (t ? 1)) ? f ( pi (t ))(2-1)f ( pg (t )) ? min{ f ( p0 (t )), f ( p1 (t )),..., f ( p N (t ))}(2-2)其中， pg (t ) ? { p0 (t ), p1 (t ),..., p N (t )} ， N 为种群规模。 在第 t ? 1 次迭代时,粒子速度和位置的更新规则可以表示为：vi (t ? 1) ? vi (t ) ? c1r1 ( pi (t ) ? xi (t )) ? c2 r2 ( p g (t ) ? xi (t ))(2-3) (2-4)xi (t ? 1) ? xi (t ) ? vi (t ? 1)其中，i 表示第 i 个粒子，t 表示迭代次数，基本粒子群算法中 c1 和 c2 的取值为 2，r1 和 r2 为两个随机向量。 为了减少进化过程中粒子超出搜索区域的可能性， vi 通常限定在一定的范围 内，即 vij ? [vmin , vmax ], j ? 1, 2,..., D ， j 表示速度向量的第 j 维。12粒子群算法优化及其在图像检索中的应用研究基本粒子群算法的初始化过程为： (1)根据实际问题，确定群体规模 N 。 (2)在 [ xmin , xmax ] 区域内随机生成初始种群 xi , i ? 1, 2,..., N 。 (3)在 [vmin , vmax ] 区域内随机生成各粒子的初始飞行速度 vi , i ? 1, 2,..., N 。 (4)根据初始种群初始化各粒子的个体最优解 pi 和种群的全局最优解 pg 。 基本粒子群算法的步骤为： Step 1：随机初始化种群中各粒子的位置和速度。 Step 2：评价每个粒子的适应度，将当前各粒子的位置作为其个体最优解 pi ， 将所有粒子中适应值最好个体的位置作为全局最优解 pg 。 Step 3：判断算法是否满足结束条件，若满足则执行 Step8，否则执行 Step4。 Step 4：根据公式(2-3)和(2-4)更新粒子的速度和位置。 Step 5：计算各粒子适应值，将其适应值与个体最优解进行比较，并更新个体 最优解 pi ；将所有的 pi 和 pg 进行比较并更新 pg 。 Step 6：判断算法是否满足结束条件，若满足则执行 Step8，否则执行 Step7。 Step 7：迭代次数加 1，执行 Step4。 Step 8：输出结果算法结束。 基本 PSO 算法流程如图 2.1 所示。图 2.1 粒子群算法流程第二章 粒子群优化算法概述131998 年 Eberhart 提出了在基本粒子群算法的速度进化方程中引入惯性权重的 策略[10]，即：vi (t ? 1) ? wvi (t ) ? c1r1 ( pi (t ) ? xi (t )) ? c2 r2 ( p g (t ) ? xi (t ))(2-5)其中， w 称为惯性权重，基本粒子群算法可看作 w ? 1 时的特殊情况， c1 和 c2 是在 [0,1]范围内变化的随机值。此外，粒子的速度与位置分别受速度范围 [vmin , vmax ] 以 及位置范围 [ xmin , xmax ] 的约束。惯性权重的引入使得粒子能够保持一定的惯性，扩 展了其搜索空间并增强了算法的全局搜索能力，对算法的性能有一定的改善。目 前对粒子群算法的研究主要围绕着带有惯性权值的 PSO 算法进行，将带惯性权值 的粒子群算法称为标准粒子群算法。 由公式(2-5)可看出，粒子速度由三部分组成：第一部分为粒子先前行为的惯 性，其代表着粒子本身的记忆性；第二部分为“认知”部分，即粒子本身的思考， 其激励着各粒子向着适应度更好的方向进化；第三部分为“社会”部分，表示粒 子间的信息共享与相互作用，即粒子本身的思考被其它粒子所借鉴和模仿。在这 三部分因素的共同影响下， 粒子根据自身的思考、 记忆以及其它粒子共享的信息， 通过动态地调整自身速度，从而向着最优解飞行。PSO 算法利用了如下的心理学 假设：在寻求一致的认知过程中，个体始终记住自身的信念，并考虑其它个体的 信念。当其察觉其它个体的信念较好时，则借鉴其它个体的信念对自己进行适当 的调整[24]。2.3 粒子群算法的研究现状2.3.1 混沌权值粒子群算法 粒子群优化算法的优点之一便是所需设置的参数较少，惯性权值 w 是算法中 最为重要的参数， 它对算法的全局和局部搜索有着重要的影响。 在算法初期阶段， 希望算法有较强的全局搜索能力以扩展算法的求解空间，从而提高算法搜索到全 局最优解的可能，而在算法后期则应当以较快的速度进入局部搜索，提高算法的 收敛速度。Shi.Y 和 Eberhart 提出的线性递减惯性权值策略[11]是一种被广泛采用的 惯性权值调整策略，该方法能够在一定程度上调节算法的全局搜索和局部搜索的 能力。但对于复杂多维问题，在求解时所需迭代的次数往往较多，因此在每次迭 代时惯性权值的相对变化量很小，这在一定程度上减缓了算法的收敛速度。同时 简单的线性变换模式无法帮助在迭代后期陷入局部最优解的粒子跳出局部极值， 从而影响了算法的收敛精度。 基于以上启发，吴秋波等人提出了混沌惯性权值调整策略[25]。混沌是确定性 非线性系统内在的随机性，其具有遍历性、不确定性和随机性等特点。混沌惯性14粒子群算法优化及其在图像检索中的应用研究权值策略的基本思想是使用一组混沌变量，以类似载波的方式在惯性权值中引入 混沌变量，并将混沌的运动范围映射到整个可行的取值范围[25]，其效果如图 2.2 所示，其中惯性权值的取值范围为[0.4,0.9]。 惯性权值更新公式为： w(k ) ? wmin ? ( wmax ? wmin ) z (k ) (2-6)其中， wmin 为惯性权值的取值下限， wmax 为惯性权值的取值上限， k 为迭代的次数，z ( k ) 为随机值，其计算公式为： z ( k ? 1) ? ? z (k )(1 ? z (k ))(2-7)其中 u ? 0.4 ， z (1) ? 0.8 。图 2.2 混沌惯性权值该方法能够在一定程度上调整 PSO 算法的全局和局部搜索能力，并且混沌变 量的遍历性增加了种群的多样性。但是混沌是随机的、不可预测的，尽管该方法 能够在一定程度上改进算法的性能，但是其惯性权值的随机变化不符合种群进化 的一般特征。 在搜索的初期应保持较大的惯性权值， 以增强算法的全局搜索能力； 而搜索后期，应减小惯性权值，使算法进入局部搜索加快收敛。这种波动的惯性 权值更新策略在很大程度上减缓了算法的收敛速度。 2.3.2 双中心粒子群算法 自粒子群算法提出以来，尽管各领域的专家学者都从不同角度对粒子群算法 进行了不同的改进，但不同的改进方案却遵循着相同的基本原理，即通过迭代进 化，从而寻找最优解。在进化过程中，各粒子在个体最优解和全局最优解的影响 下，向着最优解飞行，最终粒子群会被吸引至全局最优解与个体最优解的邻近区 域。搜索结束后，所有粒子个体最优解的中心和整个群体的中心位于最优解或其 邻近区域，相比全局最优解，整个群体的中心和所有粒子个体最优解的中心或许第二章 粒子群优化算法概述15更接近于最优解[26]。 汤可宗等人分析了粒子群算法的基本原理和粒子的飞行的轨迹，并将广义中 心粒子和侠义中心粒子的概念引入算法，设计了一种新的全局极值更新方法并提 出了双中心粒子群优化算法[26]。 汤可宗等人注意到 PSO 速度更新公式是三部分矢量的合成，即粒子的更新可 看作粒子先沿着原速度 vi 方向飞行 wvi 距离，再沿着平行于矢量 pbesti (t ) ? xi (t ) 的 方向飞行 c1 ? r1 ? ( pbesti (t ) ? xi (t )) 距离，最后沿着平行于矢量 gbest ? xi (t ) 的方向飞 行 c2 ? r2 ? ( gbest ? xi (t )) 距离并达到粒子更新后的位置 xi (t ? 1) ，如图 2.3 所示。 pbesti (t ) 与 gbest 分别代表第 i 个粒子第 t 次迭代时的个体最优解与全局最优解。可 看出，每个粒子是以折线的方式从一个位置进化到另一个位置，这种进化方式使 每个粒子能够拥有更为广阔的搜索空间，从而更好地搜索最优解；其次，每个粒 子个体最优解的改善能够提高粒子收敛的速度。由此，汤可宗等人提出了新的个 体极值更新方式： f ( pbesti (t ? 1)) ? min( f ( A), f ( B ), f ( xi (t ? 1)), f ( pbesti (t ))) (2-8)随着迭代搜索的进行，全局最优解和各粒子个体最优解的中心不断向最优解 靠拢。在算法搜索的后期，各粒子个体最优解的中心或许比全局最优解更接近求 解问题的最优解。当该中心对应的适应值优于全局最优解时，用该中心替换当前 全局最优解，则各粒子将会在该中心的引导下更快地向着最优解进化，最终种群 中所有粒子都将收敛至该中心或其邻域内。 基于以上分析， 汤可宗等人引入了两个中心粒子： 广义中心粒子(General Center Particle, GCP)和狭义中心粒子(Special Center Particle, SCP)，并提出了全局极值的 更新方式，即：xGCP ? 1 n ?2 (? pbesti (t )) n ? 2 i ?1 1 n ?2 (? xi (t )) n ? 2 i ?1(2-9)xSCP ?(2-10) (2-11)f ( gbest ) ? min( f ( pbest1 ), f ( pbest2 ),..., f ( pbestn ), f ( xGCP ), f ( xSCP ))虽然该方法利用了粒子在进化过程中的移动特点对算法进行了优化，加快了 算法的收敛速度。但是在算法迭代的初期，粒子不应盲目地向其它粒子学习，而 该方法极易使粒子过快地向当前最优解飞行，从而削弱了粒子本身的思考，而这 种过快的进化往往会使得算法陷入局部最优并进一步恶化导致早熟。16粒子群算法优化及其在图像检索中的应用研究pbesti (t )xi (t ) vigbestxi (t ? 1)B A图 2.3 粒子移动过程2.3.3 基于距离度量的自适应粒子群算法 在 PSO 算法中，种群的特性是通过粒子的各种行为所体现的。多数粒子群优 化算法的改进策略未考虑粒子之间的位置关系及差异。李太勇等将粒子间的欧氏 距离引入算法，提出了一种基于距离度量的自适应粒子群优化算法[27]。定义粒子 i 和粒子 j 之间的距离为：ddist (i, j ) ??(xk ?1ik? x jk )2 ? ( f ( X i ) ? f ( X j ))2(2-12)其中， X i ? [ xi1 , xi 2 ,..., xid ] 表示第 i 个粒子， d 表示粒子维数， f 为适应度函数。定 义粒子间的平均距离为：N NMdist ? 2 ? ?? dist (i, j ) / N 2i ?1 j ?1(2-13)较大的惯性权值有利于算法扩展搜索空间进行全局搜索，较小的惯性权值有 利于算法对当前区域进行局部搜索，便于算法收敛。该算法根据粒子与全局最优 解之间的距离动态地调整惯性权值。即如果粒子与最优粒子间的距离大于粒子间 的平均距离，则给该粒子分配较大的惯性权值进行全局搜索；否则，给该粒子分 配较小的惯性权值进行局部搜索[27]。 该算法提出的惯性权值更新策略为：? ? wmax w?? ? ? wmin ? ( wmax ? wmin ) ? dist ( X , pg ) / Mdist dist ( X , pg ) ? Mdist 其它(2-14)尽管该方法考虑了粒子间的差异性，根据粒子与最优粒子间的距离自适应地 调整惯性权值的大小，使惯性权值的变化更符合种群进化的规律，提高了粒子群 算法的寻优能力。但是在粒子与当前最优解之间的距离较小时，该调整策略使算 法对于当前最优解进入局部搜索，这使得算法更容易陷入局部最优解，从而影响 了算法的收敛精度。第二章 粒子群优化算法概述172.4 粒子群算法的应用2.4.1 函数优化 在实际工程应用中，在对许多工程问题进行分析建模后，可将其抽象成函数 优化问题进行求解。目前求解函数优化问题已经有较为成熟的解决方法如遗传算 法。 遗传算法采用了遗传算子以及交叉变异等策略， 具有信息重组与集成等特点。 但是对于维数较高、局部极值较多的复杂函数，遗传算法的收敛速度和收敛精度 往往难以达到令人满意的效果，且遗传算子对算法的可行域较为敏感，对不同问 题需多次运行才能找出合适的交叉变异算子。通过研究表明，PSO 算法在解决多 数典型函数优化问题时，能够取得比遗传算法更好的结果[28]。 通过研究发现，PSO 算法同遗传算法类似，在解决实际工程优化问题时有两 个重要的步骤：编码目标问题的解以及选择恰当的适应度函数。使用 PSO 算法解 决函数优化问题不仅能够避免遗传算法的选择、交叉、变异等复杂操作，而且粒 子群算法中粒子间的信息共享比遗传算法中的信息共享更有效且易于实现，从而 能够简化上述两个步骤。 2.4.2 神经网络训练 人工神经网络是模仿人类大脑分析问题的过程所构建的数学模型，误差反向 传播算法(Back Propagation, BP)是使用最广泛的神经网络训练算法。目前许多领域 的专家学者开始研究使用演化计算技术来优化人工神经网络的各方面。使用演化 计算技术的优势在于其可以处理传统方法所无法解决的问题，例如不可导的节点 传递函数或没有梯度信息。 神经网络训练中使用 PSO 算法，主要涉及连接权重，网络的拓扑结构，传递 函数和网络学习算法等方面的内容。每个粒子包含了神经网络所需要的全部参数， 通过 PSO 算法的迭代优化选取更合适的参数组合，进而达到训练的效果。与使用 BP 算法进行神经网络训练相比，使用 PSO 算法的优势在于其不需要利用梯度信 息，即算法中可使用不可微的传递函数，并且可以克服 BP 算法容易陷入局部极值 的缺陷。大量实验证明，使用 PSO 算法的训练结果优于使用 BP 算法的结果，且 训练速度快。 2.4.3 多目标优化 一般情况下，多目标优化问题中的各子目标是互相冲突的，改善某个子目标 的性能可能降低其它子目标的性能，不可能使所有子目标同时达到最优值，只能 对其进行协调、折中选择，从而使各个子目标尽可能取最优解。同单目标优化问18粒子群算法优化及其在图像检索中的应用研究题的本质区别在于，多目标优化问题并非只有唯一解，而是拥有一组最优解集， 解集中的各个元素称为 Pareto 最优解或非劣最优解。 在解决多目标优化问题上，PSO 算法展现出了比传统优化方法更大的优势。 首先，PSO 算法是以分布在搜索空间的种群进行的迭代寻优，其并行搜索方式有 利于同时得到多目标意义下的多个非劣最优解；其次，PSO 算法对于处理多目标 问题具有较好的通用性，适合处理多种类型的目标函数和约束，并且容易与传统 的优化方法结合，从而改进自身的局限性，达到更高的效率。 将粒子群优化算法应用于多目标优化问题，关键在于如何确定各粒子个体最 优 pbest 及全局最优 gbest 。单目标优化问题的解决方法十分简单，各粒子个体最 优位置由该粒子历史最优位置确定，全局最优位置由该次迭代时种群中的最优位 置所确定。但是对于多目标的优化问题，由于不存在单个最优解，因此不能直接 得到 gbest 和 pbest 。对于群体最佳位置的选择，首先要使算法具有较高的收敛速 度，其次使得到的解在 Pareto 边界上具有一定的分散性。对于个体最佳位置的选 择，则要求通过所选的个体最优，能够以较少的比较次数达到非劣解的更新[29]。2.5 经典测试函数为了分析与检验粒子群优化算法的性能，目前该领域的专家学者一般采用以 下经典的测试函数。n(1)Sphere 函数： f ? x ? ? ? xi2i ?1Sphere 函数为单峰函数，其三维图像如图 2.4 所示。其在坐标原点处具有全局 最小值 0。图 2.4 Sphere 波形图100 xi ?1 ? xi2 (2)Rosenbrock 函数： f ? x ? ? ? ? ? ? i ?1n ?1?? ? ?1 ? x ? ? ? ?2 i2第二章 粒子群优化算法概述19Rosenbrock 函数是单峰函数，其全局最优解处于一个相对平滑的抛物线状山 谷中，由于函数为优化算法仅提供了少量的信息，使算法难以辨别搜索方向，搜 索到全局最优解的几率很小，特别是在维数较高的情况下，且在搜索过程中极容 易陷入局部极值。其三维波形如图 2.5 所示。图 2.5 Rosenbrock 函数波形图n xi2 ?x ? ? ? cos ? i ? ? 1 (3)Griewank 函数： f ? x ? ? ? i ?1 4000 i ?1 ? i? nGriewank 函数是典型的多峰值函数，其具有较为广泛的搜索空间。但存在大 量的局部极值对算法的收敛具有极大的影响，如图 2.6 所示。图 2.6 Griewank 函数波形图(4)Rastrigin 函数： f ? x ? ? 10n ? ? ? xi2 ? 10 cos ? 2? xi ? ?i ?1nRastrigin 函数也是一个具有大量局部极值的多峰函数， 这对其算法收敛也带来 了一定的影响。其波形如图 2.7 所示。20粒子群算法优化及其在图像检索中的应用研究图 2.7 Rastrigin 函数波形图1 5(5)Ackley 函数： f ? x ? ? ?20e?? i?1 xi2nn? i?1cos(2? xi ) ?enn? 20 ? eAckley 函数最优解在坐标原点处，在原点附近存在多个局部极值。其波形如 图 2.8 所示。图 2.8 Ackley 函数波形图sin 2 x 2 ? y 2 ? 0.5 (6)Schaffer F6 函数： f ( x ) ? 0.5 ? (1 ? 0.001? ( x 2 ? y 2 ))2Schaffer F6 函数是一个较为复杂的多峰值函数，其波形如图 2.9 所示。从图中 可看出，其存在大量局部极值，对全局最优解的搜索带来极大的影响。第二章 粒子群优化算法概述21图 2.9 Schaffer F6 函数波形图n n 2 i(7) Salomon 函数： f ( x ) ? 1 ? cos(2??xi ?1) ? 0.1(?xi ?12 i)Salomon 函数是复杂的多峰值函数，其波形如图 2.10 所示。从图中可以看出 其存在非常多的局部极值。图 2.10 Salomon 函数波形图2.6 本章小结本章研究了群智能算法的相关概念、应用领域及现存问题等内容；研究了标 准粒子群算法基本原理及求解流程；从三种不同的角度出发，分析了混沌权值粒 子群优化算法、双中心粒子群优化算法和基于距离度量的自适应粒子群优化算法 以及其优缺点；介绍了粒子群优化算法在函数优化、神经网络训练以及多目标优 化等工程领域的应用；最后，给出了用于测试粒子群算法性能的经典测试函数。 为后续章节的进一步研究工作奠定了基础。22粒子群算法优化及其在图像检索中的应用研究第三章 粒子群算法的改进23第三章 粒子群算法的改进PSO 算法是一种从随机解出发通过迭代寻找最优解的进化算法。初始种群的 优劣对算法的搜索能力有较大的影响，当初始种群中的粒子在搜索空间不均匀分 布时，会使得算法的搜索范围受到限制，降低其全局搜索能力；标准 PSO 算法的 惯性权值更新策略不符合种群进化的一般规律，这种更新策略会限制算法搜索的 步长， 在一定程度上降低了算法的收敛速度和收敛精度； 由于缺乏局部搜索策略， 若 PSO 算法在迭代的后期陷入局部最优解， 则很难跳出局部最优向全局最优进化。 由此可见，初始种群、算法参数以及搜索策略对算法的收敛速度和精度具有重要 的影响。本章将从初始种群的构造、惯性权值的选择以及局部搜索策略的设计三 个方面对粒子群算法进行改进，最终给出改进后的粒子群算法的流程并通过经典 的测试函数进行实验验证。3.1 初始种群的构造3.1.1 均匀设计相关概念 试验设计方法的基本思想是在试验范围内选取具有代表性的试验点。正交设 计依据正交性的准则选取试验点，所选取的试验点可以反映试验范围内各个因素 与试验指标间的关系。使用正交设计所设计的试验点具有均匀分布以及整齐可比 的特性。均匀分布使所选取的试验点具有普遍代表性；整齐可比使所得的试验数 据易于统计分析。 为了保证试验点具有整齐可比的特点， 则正交设计需至少进行 q 2 次试验，q 为每个因素的水平数。若需要减少试验的进行次数，则需省去试验点整 齐可比的特点。均匀设计便是一种只考虑试验点在试验范围内均匀分布的试验设 计方法。 均匀设计是继 60 年代华罗庚教授所倡导并普及的优选法和数理统计学者推广 的正交法设计方法之后，于 70 年代末应航天部第三研究院飞航导弹火控系统建立 数学模型、并研究其诸多影响因素的需要，由我国科学院应用数学所的方开泰教 授及王元教授所提出的一种只考虑试验点在试验范围内均匀散布的试验设计方法[30]。方开泰教授和王元教授首次提出了均匀设计的理论和方法，揭示了均匀设计与近代最优设计、古典因子设计、组合设计以及超饱和设计间内在的联系，并在 数学理论的基础上证明了均匀设计方法比传统设计方法具有更好的稳定性。 均匀设计采用了数论中一致分布理论的数学原理，该方法借鉴了近似分析中 数论方法的研究成果，将数论同多元统计结合，属于伪蒙特卡罗方法范畴[31]。设 试验区域为单位立方体 C s ? [0,1]s ，在立方体中选取 n 个试验点 x1 ,..., xs ，其与输出24粒子群算法优化及其在图像检索中的应用研究变量有一个确定性的关系：y ? f ( x1 ,..., xs ), x ? ( x1 ,..., xs ) ? C s(3-1)变量 y 在 C s 上的总体均值为：E ( y ) ? ? s f ( x1 ,..., xs ) dx1 ,..., dxsC(3-2)y 在这 n 个试验点上的均值为：y ( Dn ) ?1 n ? f ( xi ) n i ?1(3-3)其中， Dn ? {x1 ,..., xn } 代表这 n 个点的一个设计。 均匀设计中考虑了总体均值模型，设点集 Drandom 中的点 x1 ,..., xn 独立同分布， 遵从 C s 上的均匀分布，由数论方法中的 Koksma-Hlawka 不等式可知： E ( y ) ? y ( Dn ) ? V ( f ) D( Dn ) (3-4)其中， V ( f ) 是函数 f 在 C s 上的总变差，函数 f 平稳，则 V ( f ) 越小，函数 f 波动 越大，则 V ( f ) 越大； D ( Dn ) 为点集在 Dn 与 C s 上的偏差，偏差是度量点集均匀性 的一种测度， D ( Dn ) 越小即点在 C s 上分布越均匀[31]。设 n =8， s =2，则均匀设计 的步骤为： 1、 将试验区域各边界 8 等分，则共可以得到 64 个小正方形。 2、 在 64 个小正方形中选取具有代表性的 8 个，使得各行各列恰好只有一个 小正方形。对于每种取法，将试验放于小正方形的中心，并对所有试验设 计的偏差进行比较，使偏差达到最小的一个即为均匀设计。 均匀设计的主要思想是只考虑将试验点在试验范围内均匀分布，而不考虑试 验点是否整齐可比，这也是其选取试验点的基本出发点。它可保证试验点具有均 匀分布的统计特性，着重考虑试验点在试验范围内均匀散布，从而通过最少的试 验获得最多的信息。均匀设计适用于多因素多水平的试验以及系统模型未知的情 况。对于粒子群优化算法等群智能优化算法所需求的正是初始种群能够尽可能均 匀地分布在搜索空间，以增强算法的全局搜索能力。因此，使用均匀设计构造粒 子群优化算法的初始种群必定是可行且有效的。 3.1.2 基于均匀设计的种群初始化 PSO 算法是以种群为基础的迭代进化算法，初始种群的均匀性对算法的搜索 性能有重要的影响。标准 PSO 算法以随机的方式产生初始种群，这样的种群在搜 索空间分布不均匀，会导致算法的搜索范围受限，降低了算法的全局搜索能力。 因此，为使初始种群能够更均匀地分布在搜索空间，本文采用了均匀设计的方法第三章 粒子群算法的改进25构造初始种群，从而增加了初始种群的多样性，克服了传统随机初始化种群多样 性较低及种群分布不均匀的问题，扩展了算法的搜索空间且提高了算法的搜索效 率。 均匀设计利用了数论中的一致分布理论选取 n 个试验点， 使用数论方法所生成 的点集在积分范围内比其它方法所生成的点集分布更均匀，表现为该点集中各个 点离被积函数的各种值更为接近。当问题一定时，使用均匀设计的思想所构造的 初始种群是稳定不变的。 为验证采用均匀设计可生成均匀分布的初始种群。本文使用均匀设计的方式 与随机的方式分别在二维空间内生成包含 100 个点的点集， 其效果分别如图 3.1 所 示。(a)均匀设计生成 100 个点(b)随机方式生成 100 个点图 3.1 均匀设计方法与随机生成方法比较均匀设计与正交设计相似，是通过均匀设计表来完成试验设计。均匀设计表 是进行均匀设计的基础，可用 U n ( q s ) 表示，其中 U 表示均匀设计， n 为均匀设计 的行数（问题规模或试验次数） ， q 为各因素的水平数， s 为均匀表的列数。当水* * 平数 q 为偶数时， U n ( q s ) 的均匀性较差，方开泰等人建议用 U n ( q s ) 代替， U n 表是 * * s 由U n ?1 表去掉最后一行所获得的。一般情况下，同因素、同水平的均匀表 U n ( q ) 比U n ( q s ) 具有更好的均匀性。均匀设计表有很多构造方法，如好格子点法、拉丁方法、切割法、正交表扩 充法、折迭法以及 RBIBO 法等。好格子法是数论方法中最经典的方法，至今仍是 一种有效且可行的方法。 本文采用好格子法构造均匀设计表，初始种群构造具体方法为： 1) 给定初始种群的大小 n ，寻找比 n 小且与 n 互素的整数 ki , i ? 1,2,..., m 。由符 合条件的整数构成向量 k ? (k1 , k2 ,..., km ) ，其中 m 由欧拉函数 ? ( n) 确定。 2) 记 uij 为均匀设计表中第 i 行第 j 列的数据，定义第一行的元素 u1 j ? k j ，第 i26粒子群算法优化及其在图像检索中的应用研究行第 j 列数据的生成方式为：uij ? (i * k j ) mod n i ? 1, 2,..., k ? 1, 2,..., m(3-5)根据求解问题的维数 s ，选取其中均匀性较好的 s 列便构成了本文算法所需均 匀设计表。 3) 根据如下公式使用均匀设计表构造初始种群：xij ? xmin ?2uij ? 1 2n( xmax ? xmin )(3-6)其中， xmin 和 xmax 分别为粒子每一维取值的下限和上限。 根据以上的方法便可将均匀设计表中的 n 行映射为粒子群算法初始种群中的n 个粒子。3.2 惯性权值更新策略的选择3.2.1 惯性权值变化分析 PSO 算法的惯性权值在算法的迭代过程中起到了平衡其全局搜索与局部搜索 的作用。惯性权值的选择对算法的性能会产生较大的影响，权值较大时有利于算 法扩展搜索区域进行全局探索，反之则有利于算法收缩搜索范围更好地在局部区 域进行搜索。 基本 PSO 算法可以看作 w ? 1 的情况。然而，为了提高算法的搜索能力应当根 据不同搜索阶段的特点动态地调节惯性权值，从而使算法的全局搜索能力和局部 搜索能力达到最佳的平衡点。Shi 等提出了 LDIW 策略[11]，即在迭代的过程中惯性 权值以线性策略逐渐减小。该策略使算法在搜索初期具有较大惯性权值，能够较 好地进行全局搜索；在搜索的后期具有较小的权值，能够更好地进行局部搜索。 大量的实验结果表明，当惯性权值的取值在 0.8 和 1.2 之间时，算法具有较好的性 能。 在 PSO 算法搜索的初期可以通过加快惯性权值递减速度的方法使算法较快地 进入局部搜索阶段，从而获得更好的求解效率。然而线性递减策略在处理需要大 量迭代才可求解的问题时，惯性权值在每次迭代时的相对变化量很小，这种策略 反而减慢了算法的收敛速度。陈贵敏等通过线性递减权值策略和开口向下抛物线、 开口向上抛物线、指数曲线 3 种非线性递减策略的对比，得到了凹函数递减策略 优于线性策略，而线性策略优于凸函数策略的结论，即凹函数递减策略能更好地 提高粒子群算法的收敛速度[32]。 对于单值的、维数较小的问题而言，使算法尽快地进入局部搜索无疑是算法第三章 粒子群算法的改进27优化的最佳选择。然而，对于规模较大且维数较多的复杂、多峰值问题的粒子群， 过快地降低惯性权值虽然增强了算法的局部搜索能力，但在很大程度上限制了算 法的全局搜索能力，从而使算法陷入局部最优解，容易早熟，无法找到真正的全 局最优解。 3.2.2 基于凹函数特性及自适应因子的惯性权值更新策略 为了使算法能够较好地适应复杂问题，本文在粒子群惯性权值更新公式中设 计了自适应因子。定义：wa ? p g (t ) pg (t ? 1)(3-7)其中， pg (t ) 表示种群第 t 代的全局最优值， pg (t ? 1) 表示种群第 t ? 1 代的全局最优 值。即 wa 为当前代的全局最优解与上一代的全局最优解的比值。若 wa ? 1 ，则说 明粒子群的总体趋于收敛，且 wa 越小搜索步长应增大，以加强算法的全局搜索能 力；反之则应减小步长使算法进入局部搜索。若 wa ? 1 ，则说明此次迭代发散，且 wa 越大步长应越小，以加强算法的局部收缩能力。 与此同时，定义： wb ? pg (t ) pv (t ) (3-8)其中， pg (t ) 表示种群第 t 代的全局最优值， pv (t ) 表示第 t 代所有粒子适应度的平均 值。即 wb 为当前代的全局最优解与当前代所有粒子最优解平均值的比值。可见 wb ? 1 ，且 wb 值越大说明粒子的聚集性越强，即有可能陷入局部极值，则此时应 适当地增大 w 以增大搜索步长使算法跳出局部最优解。 本文结合了凹函数与自适应因子的特点，设计的惯性权值函数为：w ? wmax ? cos( 3t tmax? t ? w ? ) ? wmin ? sin( 3 ? ) ? exp(? a ) 2 tmax 2 wb(3-9)wmax 为惯性权值的最大值， wmin 为惯性权值的最小值， 其中， 此处定义 wmax ? 0.95 ， wmin ? 0.4 ； t 为当前迭代次数， tmax 为最大迭代次数。PSO 速度公式的第二部分和第三部分分别代表了粒子本身的思考和粒子间的 信息共享与相互作用。在标准 PSO 中这两部分的系数 c1 与 c2 是不变的。然而在算 法的不同阶段这两部分的重要性不是一成不变的。在算法的初期应当侧重于激励 每个粒子去减小误差，不能盲目地借鉴其它粒子的信息；而在算法的后期应当侧 重于迭代了多次以后的粒子间的信息共享。因此，在整个算法的过程中认知部分 的系数 c1 应当逐步减小，而社会部分的系数 c2 应逐步增大。动态地调整各部分的28粒子群算法优化及其在图像检索中的应用研究系数，使得算法更容易摆脱局部最优解，从而避免早熟现象。本文所设计的动态 系数调整公式如下：c1 ? ?( c1min ? c1max t 2 c1min ? c1max )?( ) ?( ) 2 tmax 2(3-10)c2 ? (c2min ? c2 max t 2 c2min ? c2max )?( ) ?( ) 2 tmax 2(3-11)参照文献[32]取 c1min ? 1.25 ， c1max ? 2.75 ， c2min ? 0.5 ， c2max ? 2.25 。3.3 基于混沌变异的局部搜索策略的设计3.3.1 混沌的基本概念 E.N.洛伦兹于 1972 年在美国科学发展学会第 139 次会议上发表了题为蝴蝶效 应的论文，他提出了一个看似荒谬的论断：在巴西一只蝴蝶翅膀的拍打能够在美 国的得克萨斯州引发一场龙卷风，并由此指出了天气是不可预测的。这一论断激 发了学者们对混沌学的研究热情。伴随着计算机等技术的飞速进步发展，混沌学 已成为一门影响深远、发展迅速的前沿学科。 尽管混沌现象己引起学术界的广泛关注，但至今混沌仍没有被公认的能够普 遍适用的数学定义。许多学者认为，精确定义混沌需要使用大量技术术语，而且 来自不同领域的学者都在积极研究混沌，他们对混沌的理解来自其研究领域的不 同角度。故不同领域的学者均在各自对混沌的理解基础上予以定义。1975 年 Li 和 York 首次给出了混沌的数学定义，称之为 Li-Yorke 定义。Li-Yorke 定义是目前流 传较为广泛的混沌数学定义之一，它给出了混沌在数学上的存在性。 Li-Yorke 定理：设 f ( x ) 是 [ a, b] 上的连续自映射，若 f ( x ) 有 3 周期点，则对于 任意正整数 n ， f ( x ) 有 n 周期点[33]。 Li-Yorke 混沌定义：闭区间 I 上的连续自映射 f ( x ) ，如果满足以下条件，则称 其具有混沌现象[34][35]： （1） f ( x ) 有任意周期的周期点。 （2）在闭区间 I 上存在不可数的非周期不变子集 S ，并满足： f ( S ) ? S ；且 对于任意 x ? S 和 f ( x ) 的任意周期点 y ，有 lim sup f n ( x ) ? f n ( y ) ? 0 ；对于任意n ??x, y ? S ， 当 x ? y 时 ， 有 lim sup f ( x ) ? f n ( y ) ? 0 ； 对 于 任 意 x, y ? S ， 有n n ??lim inf f ( x) ? f ( y ) ? 0 。n n n ??与通常研究的线性科学不同，混沌学研究的是一种非线性的科学，非线性科 学领域中，混沌指的是一种确定而不可预测的运动状态。其外在表现同随机运动第三章 粒子群算法的改进29十分相似，即都是不可预测的。但与随机运动的不同在于，混沌运动在动力学上 是确定的，其不可预测性主要来源于运动的不稳定性。或可理解为混沌系统对无 限小的初值变化和微扰具有很高的敏感性，无论多么小的扰动在存在较长时间后， 都将会引起系统偏离其原有演化方向，即混沌具有对初始条件的敏感依赖性[36]。 研究表明，混沌是非线性系统所固有的特点，是非线性系统中普遍存在的一种现 象。 混沌现象普遍存在于自然界中，即混沌并不是偶然事件，而是普遍地存在于 宇宙间各宏观或微观系统中，万事万物，莫不混沌。尽管在各研究领域对混沌的 理解是不同的，但其具有共同的特征： （1）有界性 混沌的有界性表现为，其运动轨迹始终限定在某一确定区域内，该区域称为混 沌吸引域。 无论混沌系统内部如何不稳定， 其运动轨迹始终不会超出混沌吸引域， 因此，混沌系统从整体上看是稳定且有界的[37]。 （2）内随机性 对于混沌系统施加确定性的输入，其产生的行为是随机的、不稳定的。而这 一过程不受任何外界随机因素的影响，因为随机性产生的根源在系统的内部，来 源于运动的不稳定性，故称之为内随机性。内随机性体现了混沌的不可预测性。 （3）遍历性 混沌运动始终限定在混沌吸引域内，其遍历性体现为在有限时间内其按照自 身的运动规律不重复地遍历混沌吸引域内的每一个状态点。 鉴于混沌的遍历性以及随机性，其可作为防止群智能优化算法陷入局部极值 的优化方法。即当算法进入局部搜索并认为已经搜索到全局最优解时，采用混沌 的方式对当前最优解在一定范围内进行扰动，从而进行局部搜索直至满足局部搜 索终止的条件。 3.3.2 基于混沌变异的局部搜索 PSO 算法是一种从随机解出发进行迭代寻优的算法，在算法迭代的初期，搜 索可能陷入搜索空间的某一区域内。随着迭代次数的增加，算法并不能跳出该区 域，而是一直在该区域内寻找最优解直至算法结束。尽管算法结束时收敛到的该 区域的局部最优解在理论上有可能是全局最优解。但是随着实际问题的复杂化、 多维化和多峰值化，该局部最优解往往并不是所求问题的全局最优解。克服过早 陷入局部极值而导致的早熟收敛，成为了粒子群优化算法等群智能优化算法所需 解决的一个重要问题。30粒子群算法优化及其在图像检索中的应用研究本文采用混沌的思想对可能陷入局部极值的搜索设计了扰动。 根据 Logistic 映 射：X n?1 ? u ? X n ? (1 ? X n )(3-12)产生混沌序列。 其中，X ? [0,1] ，u ? [0, 4] 。 由文献[40]知， 当 u ? (3.) 时， Logistic 映射处于混沌状态。 在连续迭代 K 代后， 若粒子群的全局最优解没有改变， 说明此时算法有陷入局部极值的趋势，则对搜索采用扰动，进行扰动的具体方式 为：b ? u ? b ? (1 ? b)(3-13) (3-14) (3-15) (3-16)k ? 1 ? exp((t ?1 m ) ? 1) tPc ? xmin ? b ? ( xmax ? xmin )x(t ) ? (1 ? k ) ? pg (t ) ? k ? Pc其中， b 为与粒子坐标维数相同的随机向量，其每一维的值在 0 到 1 之间， t 为当 前代数， m 确定了扰动影响的大小。即当连续迭代 K 代后，若粒子群全局最优解 没有改变，则对全局最优解对应粒子在一定范围内进行混沌扰动以得到一个新粒 子，若该粒子对应的解优于扰动前的最优解，则算法陷入局部极值，此时以新的 粒子替换之前最优解对应粒子，以新的最优解替换连续 K 代未变的最优解并进行 下一轮迭代。3.4 算法设计基于上述内容，本文所提出粒子群优化算法的主要步骤为： Step 1： 根据待优化函数确定种群规模 N ， 采用均匀设计思想构造初始种群 xi ， 随机初始化速度矢量 vi 。 Step 2：初始化各粒子的个体最优解 pi 及粒子群全局最优解 pg 。 Step 3： 判断算法是否满足结束条件， 若满足则执行 Step10， 否则执行 Step4。 Step 4：根据公式(3-9)，计算当前代的惯性权值 w 。 Step 5：根据公式(3-10)和公式(3-11)，计算当前 PSO 速度公式认知部分和社会 部分的系数 c1 、 c2 。 Step 6：根据公式(2-4)和公式(2-5)，更新所有粒子的位置和速度，计算粒子适 应度并更新 pi 和 pg 。 Step 7：判断算法是否满足进行混沌扰动的条件，若满足则执行 Step8，否则 执行 Step9。第三章 粒子群算法的改进31Step 8：根据公式(3-13)、公式(3-14)、公式(3-15)和公式(3-16)，计算混沌扰动 后的粒子位置，计算粒子适应度并更新 pi 和 pg ，执行 Step7。 Step 9：迭代次数加 1，执行 Step 3。 Step 10：输出结果，算法结束。3.5 实验与结果分析为了验证本文提出的算法能较好地克服早熟问题、提高算法收敛精度和算法 的收敛速度。 本文选取了 Rastrigin、 Griewank、 Rosenbrock、 Schaffer F6 以及 Salomon 等测试函数将本文算法同文献[32]、文献[38]以及文献[39]中的优化算法进行对比 试验。其中 Rosenbrock 为单峰函数，Rastrigin、Griewank、Schaffer F6 和 Salomon 为多峰函数。在实验中，粒子数设定为 30；最大迭代次数 tmax ? 1000 ；惯性权值最 大 值 为 wmax ? 0.95 ， 最 小 值 为 wmin ? 0.4 ； 加 速 因 子 的 设 置 为 ： c1max ? 2.75 ，c1min ? 1.25 ，c2max ? 2.25 ，c2min ? 0.5 。对加速因子无要求的算法，其加速因子值均设置为 2。为了便于观察，实验对适应度函数的结果取以 10 为底的对数，结果如 图 3.2 所示。(a)Rastrigin 函}