（计算数学专业论文）基于粒子群优化和差分进化的智能算法研究.pdf

摘要 粒子群优化算法和微分进化算法是近年来提出的两种简单而高效的进化算法，因为它们易丁： 理解和实现，以及受控参数少等优点，经提出就得到了广泛的研究和应用本文详细阐述了二 者的基本内容，基于粒子群优化算法和微分进化算法提出了几种新的优化算法，并重点研究了p s 0 和d e 算法在k - m e a n s 聚类优化问题中的应用主要研究内容如下： 1 对p s o 算法和d e 算法的原理进行了详细地阐述。分析了参数设置对算法优化效果的影响， 给出了算法流程 2 给出两种改进的粒子群算法一是带有自适应变异的簧子粒子群优化算法，根据群体适应 度方差和空间位置聚集度构造自适应变异算子，以增加种群的多样性，从而达到全局寻优；二是 提出了混沌量子粒子群算法，利用混沌初始化避免种群出现聚结现象，对全局极值添加混沌扰动 实现全局寻优，通过典型的函数测试表明，这两种改进算法既克服了标准粒子群优化算法易出现 早熟收敛的缺陷，又提高了算法的搜索速度和收敛精度，在很大程度上改善了标准粒子群算法的 性能 3 提出了一种带有自适应变异的混合差分进化算法，采用d e b e s t 1 和d e d r a n d 1 线性递减加权 组合变异方案引入开口向上抛物线缩放因子取值策略和指数递增交叉概率因子，以平衡局部搜 索和全局搜索能力，提高算法的全局寻优能力后期，根据适应度方差和空间位置聚集度进行自 适应变异增加种群的多样性实验结果表明新算法是一种收敛速度快、求解精度高、鲁棒性较强 的全局优化算法 4 针对k 均值算法易陷入局部寻优及对初始值敏感的缺点，结合p s 0 和d e 算法全局寻优能力强 的特性将k - m e a n s 算法的迭代过程由p s 0 和d e 算法来替代，协同进化，比较两种算法的最优值， 输出寻优结果较好的，利用不同的评判指标进行评判，并与基本k - m e a n s 算法、基于p s o 优化的k 均值聚类算法( k p s o ) 及基于d e 算法的k 均值聚类算法( k d e ) 进行比较，实验结果表明，融合p s o 和d e 的改进的k - m e a n s 算法，有很强的全局寻优能力，是一种可靠的聚类方法同时，也增强了 p s o 和d e 算法的应用性 关键词：粒子群优化，差分进化，量子粒子群优化，混沌，聚类分析 a b s t r a c t p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a n dd i f f e r e n t i a le v o l u t i o n ( d e ) a r et w oe f f e c t i v ea n ds i m p l e e v o l u t i o na l g o r i t h m sp r o p o s e dr e c e n t l y i ti se a s yt oc o m p r e h e n da n dr e a l i z et h ea l g o r i t h m sw i t hf e w c o n t r o l l i n gp a r a m e t e r sa n ds oo n t h e yh a v eb e e na p p l i e da n dr e s e a r c h e di nw i d ef i e l d s 1 1 心a p p l i c a t i o n o fp s oa n dd ea l g o r i t h m sa i m i n ga tk - m e a n sc l u s t e r i n gp r o b l e m sa r er e s e a r c h e de s p e c i a l l y t h em a i n c o n t e n t so ft h i sd i s e r t a t i o ni sa sf o l l o w s ： 1 t 1 1 ep r i n c i p l e so ft h ep s oa n dd ea l g o r i t h m sa r ei n t r e d u c e da tl e n g t h t h ee f f e c to fp a r a m e t e r s e l e c t i o na r ea n a l y z e d t h ep r o g r e s so ft h ea l g o r i t h m sa r ep r o v i d e d 2 t w oi m p r o v e da l g o r i t h m so fp s oa r ep r e s e n t e di nt h i sc h a p t e r o n ei sq u a n t u mp a r t i c l e8 w a r m o p t i m i z a t i o na l g o r i t h mw i t ha d a p t i v em u t a t i o n ( a m q p s o ) ，an e wa d a p t i v em u t a t i o no p e r a t o ri s c o n s t r u c t e da c c o r d i n gt ot h es w a r mf i t n e s sv a r i a n c ea n ds p a c ep o s i t i o na g g r e g a t i o nd e g r e ei no r d e rt o i n c r e a s ed i v e r s i t yo ft h es w a r ma n dr e a l i z eg l o b a lo p t i m i z a t i o n a n o t h e ri sc h a o sq u a n t u m - m h a v e d p a r t i c l e 洲a l mo p t i m i z a t i o na l g o r i t h m ( c q p s o ) 1 1 地b a s i ci d e ao fc q p s oa l g o r i t h mi st h a t i n i t i a l i z a t i o na d o p t e dt oe s c a p et h ep h e n o m e n o no fs w a r ma g g r e g a t i o na n dc h a o sp e r t u r b a t i o no ft h e b e s tp o s i t i o nb ei m p c m e n t e dt or e a l i z eg l o b a l o p t i m i z a t i o n i ti ss h o w nt h a tt h e s ei m p r o v e dp s o a l g o r i t h m sc a no v e r c o m et h ep h e n o m e n o no ft h ep r e m a t u r ec o n v e r g e n c e ，e i t h a n c ec o n v e r g e n c es p e e d a n dp r e c i s i o n ，a n di m p r o v ep e r f o r m a n c eo f p s ob yu s eo f w e l l - k n o w nb e n c h m a r kf u n c t i o n st e s t e d 3 d i f f e r e n t i a le v o l u t i o na l g o r i t h mw i t hd y n a m i cp a r a m e t e ra n da d a p t i v em u t a t i o n ( d p a m d e ) i s g i v e n mm i x e dm u t a t i o ns 劬l t e g ) ，o fd e b e s t 1a n dd e r a n d 1c o m b i n e db yl i n e s xd e c r e a s e dc o n v 强 c o m b i n a t i o ni st a k e n 1 1 h ep a r a b o l ao p e n i n gu p w a r d ss t r a t e g yi sa d o p t e ds oa st ob a l a n c et h el o c a la n d g l o b a ls e a r c h i n ga b i l i t y e x p o n e n ti n c r e a s e da 啪v e rp r o b a b i l i t yo p e r a t o ri st a k e ni no r d e rt oi m p r o v e t h ea b i l i t yo fg l o b a lo p t i m i z a t i o nb yd e a d a p t i v em u t a t i o no p e r a t o ri nl a t t e rp e r i o di sc o n s t r u c t e d a c c o r d i n gt ot h ef i m e s sv a r i a n c ea n ds p a c ec o n g r e g a t i o nd e g r e e8 0a st oi n c r e a s et h ed i v e r s i t yo f 8 w a r m 低e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mh a v ef a s tc o n v e r g e n c e ，h i 曲a c c u r a c ya n d m o r er o b u s t , m o r es u i t a b l et os o l v eh i g h - d i m e n s i o n a lc o m p l e xg l o b a lo p t i m i z a t i o np r o b l e m s 4 f o rt h ei i m i t a t i o no fk - m e a n sa l g o r i t h mw h i c hi se a s yt os i n kt ol o c a lm i n i m u ma n ds e n s i t i v et o t h ei n i t i a l i z a t i o nv a l u e s ，t h i sc h a p t e rs u b s t i t u t e st h ee v o l u t i o np r o c e s so fp s oa n dd ea l g o r i t h mw h i c h a r ce v o l v e di n d e p e n d e n t l yt of m dt h eb e s tv a l u ef o rk - m e a n sa l g o r i t h m v a r i o u sj u d g ec r i t e r i o n sa r c g i v e n 1 1 圮r e s u l t ss h o wt h a ti m p r o v e dk - m e a n sa l g o r i t h mh a v eas t r o n gg l o b a ls e a r c h i n gc a p a c i t ya n d r e l i a b l ep e 商o r m a n c ec o m p a r i n gt ok - m e a n s ，k p s oa n dk d e a l g o r i t h mb yt w oc l a s s i c a ld a t e st e s t e d a t t h es a m et i m e ，t h ea p p l i c a t i o no fp s oa n dd ea l g o r i t h ma s t r e n g t h e n e d k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n , d i f f e r e n t i a le v o l u t i o n ，q u a n t u m - b e h a v e dp a r t i c l es w a r m o p t i m i z a t i o n ，c h a o s ，c l u s t e ra n a l y s i s n 独创性声明 本入声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料与我一向工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意 学位敝作者躲铡1 铺 帆弘犀月2 日 学位论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 刭f 娥 锄妹 时间；歹辑多月日 时间；舞多月2 日 中夏人学顾卜论文第一帝绪论 1 1 课题的研究背景及意义 1 1 1 最优化问题及其分类 第一章绪论 最优化是一个重要的数学分支，是一门应用性强、内容丰富的学科例如，工程设计中怎样 选择没计参数，使得设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限的资源， 使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎样 的计划方案才能提高产值和利润在人类活动的各个领域中，诸如此类，不胜枚举这些问题在 某种程度上都可以称为最优化问题最优化的目的是对于给出的实际问题，从可行的方案中找出 最好或较好的解决方案，即要在尽可能节省人力、物力和时间的前提下，争取获得在可能范围内 的最佳效果 一般来说，最优化问题可以表示为： ln f m f ( x ) is t 岛( 曲0 ，f = l ，2 ，m ：( 功：o ，：l ，2 ，( 1 - 1 ) 【 工，x 其中工r “是决策变量，厂( 功是目标函数，x 为可行域，岛( 力，j i i ，( 曲为约束函数，( 功 为不等式约束，j i l ，( x ) 为等式约束 优化涉及的领域很广，问题的种类与性质繁多根据最优化问题中的变量、约束、目标、问 题性质、分成如下几种类型： ( 1 ) 无约束与约束优化问题 如果最优化问题中变量的取值范围不受限制，即在式( 1 1 ) 中有x = r ”j 也就是x 为自由变量， 则称为无约束优化问题求无约束优化问题的极值时，问题的最优解即为目标函数的极值但是 在实际问题中，变量的取值范围总是会受到限制的，对目标函数的优化研究总是在一定的约束条 件下进行的，即在式( 1 1 ) 中有x r “，称为约束优化问题约束条件可分为等式约束条件和不等 式约束条件等式约束条件上各点称为可行解，等式约束曲线表示可行解域满足不等式约束条 件的区域范围称为解的可行域，在该域内的解，称为可行解，而可行解的数目会有无限多个，其 中必有一个为最优解 ( 2 ) 线性和非线性优化问题 根据函数的性质，如果目标函数和所有的约束条件式均为线性，即它们是变量的线性函数， 则称为线性优化问题或线性规划问题如果目标函数或约束函数中至少有一个是非线性的，则称 为非线性优化问题或非线性规划问题线性优化问题可采用线性规划方法来解决非线性优化问 题通常采用非线性规划方法来解决非线性优化问题的求解方法大致可分为间接法( 解析法) 和 直接法( 数值解法) ( 3 ) 连续和离散优化问题 卜夏大学髟! l ：论文第一章绪论 皇曼量i i；iii 一一i ； 一i 一 一_ ；o 曼曼曼曼曼曼曼曼曼鼍曼曼量量曼鼍曼皇曼 根据变量的性质，若可行域内的点是有限的，则称为离散优化问题；若可行域内含有无穷多 个不可数的点，且可行域内的点可以连续变化，则称为连续优化问题对于离散优化问题，若变 量均为整数，则称其为整数规划问题；若部分变量为整数，而另一部分变量连续变化，则称其为 混合整数规划问题 ( 4 ) 光滑优化问题和非光滑优化问题 根据函数的可微性质，若目标函数及约束函数都是连续可微的，则称为光滑优化问题；若目标函 数及约束函数中至少一个是不连续可微的，则称为非光滑优化问题 ( 5 ) 单目标和多目标优化问题 根据目标函数的数量划分，若目标函数为单一目标函数时，则称单目标优化问题；若目标函 数由多个子目标函数组成时，则称为多目标优化问题 ( 6 ) 确定性和随机性优化问题 根据优化问题的性质，如目标函数和可行域都是确定的，则称为确定性优化问题如果目标 函数或约束函数具有随机性，也就是问题的表述形式随时间的变化而变化，具有不确定性，这样 的优化问题称为随机性优化问题在确定性优化问题中，每个变量的取值是确定的、可知的在 随机性优化问题中，某些变量的取值是不确定的，但可根据大量的实验统计，知道变量取某值服 从一定的概率分布规律解决随机性优化问题一般可采用卡尔曼滤波对于某些能表示成数学规 律模型的随机性优化问题，可以和确定性优问题一样采用规划方法求解 ( 7 ) 单变量函数与多变量函数优化问题 如果系统中需要寻优的变量仅有一个，则称为单变量函数的优化问题，如系统中需要寻优的 变量多于一个，则称为多变量函数的优化问题尽管在实际生产过程中往往需要寻优的变量是很 多的，即为多变量函数的优化问题，但对于许多多变量函数的优化问题，往往可归结为反复地求 解一系列单变量函数的最优值，因此，单变量函数的优化方法是求解优化问题的基本方法 除此之外，根据最优化问题的极值个数还可以分为单峰值最优化问题和多峰值最优问题：根 据最优化问题的时间因素还可以分为静态最优化问题和动态最优问题等 1 1 2 最优化方法分类 求解最优化问题的最优化方法有多种形式不同类型的最优化问题可以有不同的最优化方 法，同一类型的最优化问题也可有多种最优化方法某些最优化方法可适用于不同类型的最优化 问题，针对相同的最优化问题，不同的最优化方法具有不同的优化特性有些最优化方法可以快 速求解到局部最优解，有些优化方法具有很好的全局寻优特性一般来说，求解最优化问题的理 想情况是快速有效的得到全局最优解当然，由于对最优化问题的性质和最优化方法认识的不足， 这种情况只能在有限的条件下实现对于复杂函数最优化问题，一般很难找到收敛性好且全局最 优的最优化方法因此，求解最优化问题的方法大致分为以下两类： 1 确定性方法 最优化问题的数学求解方法一般可以分成解析法、直接法、数值计算法等几类 解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况求解方法是： 先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的 2 宁夏大学硕i ：论文第一章绪论 方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法 直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件此 时可采用直接搜索的方法经过若干次迭代搜索到最优点这种方法常常根据经验或通过试验得到 所需结果对于一维搜索( 单变量极值问题) ，主要用消去法或多项式插值法：对于多维搜索问题 ( 多变晕极值问题) 主要应用爬山法 数值计算法：这种方法也是一种直接法它以梯度法为基础，所以是一种解析与数值计算 相结合的方法 2 智能优化算法 承上所述，随着科学技术的发展，实际的优化问题也变得越来越复杂优化问题表现出了复 杂性、约束性、非线性、多极小、建模困难等特点，冈此常规的求解方法已很难适用，寻求一些 新的优化技术成为一个重要研究目标和引入注目的研究方向因此，近年来以模拟物质变化过程 或模拟生命体而设计的搜索方式为基础提出了各种优化算法，此类算法有人称之为智能算法，有 人称之为仿生算法、也有人称之为演化算法或进化算法，这类算法的本质都属于随机性算法此 类算法最大的优点就是不需要目标函数具有可导性，甚至不需要目标函数有明确的表达形式，只 要知道输入输出即可，所以这类算法适应了科技发展的要求，而且随着其在优化领域取得的成功， 日益引起了人们的关注。越来越多的人加入到此类算法的研究之中，并对之作出诸多改进，使其 更适合优化问题，所以对此类算法的研究将给求解优化问题带来新的活力 智能优化算法发展至今，提出了各种不同的智能优化算法，但主要的有以下几种，如人工神 经网络、遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群算法以及差分进化算法等 进化计算采用简单的编码技术来表示各种复杂的结构，并通过对一组编码进行简单的进化操 作和优胜劣汰的自然选择来指导学习和确定搜索的方向由于采用种群的方式组织搜索，这使得 进化计算可以同时搜索解空间的多个区域，而且用种群组织搜索的方式也使得进化计算特别适合 大规模并行操作在赋予进化计算自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择 和简单的进化操作使进化计算具有不受其搜索空间限制条件( 如可微、连续、单峰) 的约束及不 需要其它辅助信息( 如导数) 的特点 对于复杂优化问题的求解，进化计算具有实用性、通用性、灵活性强、效率高等特点，能在 更多的情况下求得有用的( 即近似的、次优的和在精度许可范围内的) 解与传统确定性方法相比， 群智能进化算法有如下特点： ( 1 ) 进化计算的处理对象可以是参数本身，也可以是经过某种映射形成的特定编码，编码形 式可以是矩阵、树、图、集合、串、序列、链和表等这个特点使进化计算有广泛的应用领域， 尤其是对多目标、大规模、高维数、非线性以及带有不可转化为约束条件的复杂优化问题，具有 更强的适应性 ( 2 ) 进化计算通过策略、参数、操作以及算子的调整，能够很快提高寻优求解的性能，更重 要的是进化计算能够通过自身的改良以及同其它方法的交义融合，在较短的时间内快速进化，这 一点体现了进化计算的灵活性 ( 3 ) 进化计算采用群体搜索策略，而传统方法多采用单点搜索策略，这种特点使进化计算具 有极好的全局性，减少陷入局部最优的风险；同时，也使进化计算本身易于大规模并行实现，可 充分发挥高性能计算机系统的作用 3 宁夏大学珂! l j 论文第一帝绪论 ( 4 ) 进化计算具有高效的特点，不是说在拥有同等计算资源时，求解优化问题肯定都比传统 方法快( 从整体上讲，在近年来多数工程应用中的效率确实高出传统算法，否则，进化计算的发 展速度也不会突飞猛进) ，更多的是指能够更充分挖掘计算机的潜力，比如容易实现并行寻优求 解( 通过占用更多的冗余计算资源来实现速度的提高) 等 ( 5 ) 进化计算基本不依赖搜索空间的知识及其它辅助信息，它采用适应度函数来评价个体， 并在此基础上驱动进化过程，而对适应度函数本身无特别严格要求而传统方法则要求函数有诸 如连续、可微或空间凸性等条件这使进化计算有更广泛的应用范围 ( 6 ) 进化计算用概率的变迁规则来控制搜索的方向，表面上看好像是在盲目搜索，实际上它 遵守某种随机概率，在概率意义上朝最优解方向靠近，因此，它不像通常采用确定性规则的传统 方法，需要构造合适的下降方向 因此，研究新型的优化算法以及分析它们的性能不仅有重要的理论意义，而且有广泛的应用 前景群智能优化算法是解决全局优化问题和聚类问题等的新的最有效的途径之一，得到了国内 外的广泛关注与研究，每年举行的各类计算机科学与技术、人工智能与信息处理、模式识别与控 制、运筹与管理方面的国际和国内会议都把智能计算及进化算法作为大会的专题进行交流讨论， 尤其值得一提的是粒子群优化和差分进化算法，对此二者的研究与应用越来越热，方兴未艾 1 2 课题的国内外研究现状 1 2 1p s o 的研究进展 粒子群优化算法i i j ( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s 0 ) 是由k e n n e d y 和e b e r h a r t 于 1 9 9 5 年提出的这种算法模拟鸟群飞行觅食的行为，通过个体之间的集体协作和竞争来实现全局 搜索，且实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了 其优越性目前p s o 已广泛应用于函数优化，神经网络训练，模糊系统控制以及其它遗传算法的 应用领域等和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，通过适应度来评价 解的品质但是它比遗传算法规则更为简单，它没有遗传算法的“交叉”( c r o s s o v e r ) 和“变 异”( m u t a t i o n ) 操作而是每个粒子根据自身的速度变化调整自己的位置一般来说，能应用g a 解决的问题基本上都可以用p s o 来处理，而且效率可能会更高 粒子群优化算法一经提出就吸引了学术界的广泛重视，目前已成为一个研究热点，然而p s o 算法容易陷入早熟，后期收敛速度慢，全局寻优效率偏低，对参数敏感等缺点围绕这些缺点， 学者们做了大量的改进工作，主要包含一下几方面： ( 1 ) 算法的理论怛- 7 分析文献【2 】和 3 】对p s o 算法的收敛性进行了研究，提出了p s o 收敛 因子模型，其基本手段是先将随机变量变为常量，然后用状态转移矩阵的方法研究一个粒子的运 动轨迹，从而可以得到使得单个粒子运动轨迹收敛的参数约束条件，初步证明采用收敛因子能够 确保算法的收敛文献【4 】对文献 2 】和【3 】中p s o 算法收敛性的证明提出了三点缺陷并提出了收敛 性的判定定理加以阐释由于p s o 算法是一种随机优化算法，因此证明它能收敛或不能收敛都是 有一定困难的，文献【5 7 】关于粒子群优化算法的研究进展中都尚无对其收敛性机理做进一步证明 分析，因此，目前尚无对p s o 算法作收敛性分析的显著成果 4 宁夏人学弼it 沦文第章绪论 ( 2 ) 算法的改进包括对算法参数的调整、变异算子的引入、与其它优化算法形成的混合算 法美国的s h i 和e b c r h a r t 生文献f 8 】中研究发现，p s o 算法中等式的第一部分为速度因子，由于具 有随机性，且其本身缺乏记忆能力，有扩大搜索空间，探索新的搜索区域的趋势引入惯性权重 来控制前面速度对当前速度的影响，消除对速度上限的需要因为它们的作用都是维护全局和局 部搜索能力的平衡当速度增加时，可通过减小惯性权重达剑平衡搜索较大的惯性权重可以加 强p s o 的全局搜索能力，而较小的能加强局部搜索能力，冈此提出了一种线性递减惯性权重策略， 极大地提高了算法的全局搜索能力文献 9 】中介绍了一种带收敛冈子的粒子群优化算法，与使用 惯性权重的粒子群优化算法相比，实验结果证明使用收敛冈子的粒子群优化算法有更快的收敛速 度文献【1 0 】提出模糊自适应惯性权值策略，文献i 1l 】提出动态惯性权值策略，文献 1 2 】提出随机 惯性权值策略，文献【1 3 】构造了开口向_ 卜- 的抛物线、开口向上抛物线和指数曲线三种惯性权值递 减策略，这些不同改进惯性权值策略一定程度上提高了算法的全局优化性能粒子群优化算法作 为一种新的随机搜索算法，存在着早熟收敛和收敛速度慢这两个难题，并且具有种群多样性随代 数增加下降过快，有可能收敛不到全局最优解等缺点为了避免早熟，一些研究者提出了通过控 制种群的多样性来提高算法性能的方法文献【1 4 】引入自适应变异算子策略，将目前找到的全局 极值进行自适应的变异跳出局部寻优，文献【1 5 】将个体极值位置中陷入早熟的粒子某维位置进行 变异以增加种群的多样性，文献【l6 】希望通过引入“变异”算子跳出局部极值点的吸引，提高算 法的全局搜索能力，从而得到较高的搜索成功率 在与其它算法的融合研究方面，文献【1 7 】提出一种混沌粒子群算法，根据混沌机制的特性将 其引入到p s o 算法中以增加种群的多样性，文献 1 8 】为了使粒子能够更好地达到全局收敛位置， 2 0 0 4 年j u ns u n 等人运用量子理论，并将量子进化算法引入到微粒群算法中，提出了量子粒子群算 法( q p s o ) 文献【1 9 】提出了将模拟退火引入并行粒子群算法，这种模拟退火并行粒子群算法，结 合了粒子群算法的快速寻优能力和模拟退火的概率突跳性，保持了群体的多样性，从而避免了种 群退化 ( 3 ) p s o 算法的应用研究与遗传算法和蚁群算法相比，p s o 有着算法简单，容易实现，并且 可调整参数少等特点，因此被广泛地应用于结构设计2 0 1 、电磁场、任务调度捌、约束优化 【2 3 ，2 4 1 、聚类分析2 5 - 3 0 1 等优化问题 尽管对p s o 的研究已取得了一些进展，但算法本身的工作原理、算法内部机理及其数学基础 仍未真正建立，算法中粒子的位置和及其速度的构造及参数的设计理论也不成熟、对参数分析尚 处于试验水平，缺乏实质性的认识与理论支持，算法实用性还需进一步提高，p s o 的研究热点主 要是： ( 1 ) 算法内部机理的数学基础研究p s o 算法在实际应用中被证明是有效的，但目前还没有 给出收敛性、收敛速度估计等方面的数学证明，已有的工作还远远不够 ( 2 ) 将各种先进理论引入到p s o 各种先进理论的引入，首先可以研究性能良好的新型粒子 群拓扑结构其次可以优化p s o 的参数及其选择，如何选择、优化和调整参数，使得算法既能避 免早熟义能比较快速地收敛，对t 程实践有着重要意义 ( 3 ) 与其它智能优化算法的融合将p s o 和其它优化算法进行融合，主要考虑如何将p s o 的优点和其它智能优化算法的优点相结合，取长补短，构造出有特色、有实用价值的混合算法； 5 宁夏人学硕l j 论文第一章绪论 量曼皇曼曼曼曼曼曼曼曼曼曼曼兽皇鲁曼曼i i _ 1 i iii i,n iii 量量曼曼量舅量量曼皇暑舅舅曼曼曼寰曼曼曼璺 ( 4 ) 算法应用与推广算法的有效性必须在应用中才能体现，广泛地开拓p s o 的应用领域， 也对深化研究p s o 算法非常有意义 1 2 2d e 的研究进展 差分进化算法【3 u 由s t o r n 等人于1 9 9 5 年提出的一种新兴的进化计算技术，一种随机的并行直 接搜索算法它最初的设想是用r 解决切比雪夫多项式问题，后来发现差分进化算法也是解决复 杂优化问题的有效技术d e 算法有三个主要操作也称为变异( m u t a t i o n ) 、交叉( c r o s s o v e r ) 和选择 ( s e l e c t i o n ) ，但是这些进化操作的实现和g a 等其它进化算法是完全不同的 差分进化算法是基于群体智能理论的优化算法，通过群体内个体间的合作与竞争产生下一代 群体进而指导优化搜索但相比于其它进化算法，d e 保留了基于种群的全局搜索策略，采用实 数编码，基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性同时， d e 特有的记忆能力使得其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局 收敛能力和鲁棒性，且不需要借助问题的特征信息，适用于求解一些利用常规的数学规划方法所 无法求解的复杂环境中的优化问题归纳起来，d e 算法具有如下优点： l 、算法通用，不依赖于问题信息，可对非线性不可微连续空间函数进行最小化； 2 、算法原理简单，容易实现且具有较强的稳健性和全局寻优能力； 3 、群体搜索，具有记忆个体最优解的能力； 4 、协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力： 5 、易于与其他算法混合，构造出具有更优性能的算法 s t o r e 和p r i c e 于19 9 5 年提出了差分进化算法( d i f f e r e n t i a le v o l u t i o n ，d e ) ，并进行了广泛研究 【3 2 川】在首届国际i e e e 演化算法大赛上表现超群，成为参赛算法中演化速度最快的随机性搜索 方法虽然差分进化算法有很多优点，但是它也存在一些无法克服的缺陷，例如：参数选取困难， 后期收敛慢，有时陷入局部最优解等，针对这些不足国内外学者作了大量的研究工作，现概括如 下： 针对参数选取困难问题，l i u 等利用模糊逻辑控制器来调整缩放因子和交叉因子，提出了模 糊自适应差分进化算法【捌；文献【3 6 】通过随机的缩放因子和混沌策略增加种群的多样性，平衡局 部和全局搜索能力；文献【3 7 】通过对全局极值进行随机变异和指数交叉概率因子策略，提高了解 的质量文献【3 8 】提出一种基于群体适应度方差自适应二次变异的差分进化算法，该算法在运行 过程中根据群体适应度方差早熟判断机制，增加一种新的变异算子对最优个体和部分其他个体同 时进行变异操作，以提高种群多样性，增强算法跳出局部最优解的能力；文献【3 9 】结合差分进化 算法d e b e s t 2 b i n 变异方式和d e r a n d l b i n 变异方式采用串行算法结构实现并行差分进化算法独 立进化、信息交换的思想为使初始化个体均匀分布在搜索空间，提高算法鲁棒性，提出了一种 基于平均熵的初始化策略；采用一种双群体伪并行差分进化算法；为了有效地平衡差分进化算法 的全局搜索和局部搜索能力，文献【4 0 】基于递增交叉概率因子的基本思想，在已有的自适应二次 变异差分进化算法的基础上，提出了开口向下抛物线、开口向上抛物线和指数曲线三种非线性的 交义概率因子递增策略，能够在不影响收敛精度的情况下较大幅度地提高差分进化算法的收敛速 度；文献【4 l 】对缩放因子取值策略进行了研究，并对对大多数连续优化问题来说，开口向上抛物 6 宁夏人学硕 ：论文第一章绪论 曼量量曼曼喜吕曼量皇曼舅笪鼍曼曼舅舅量鼍曼量曼曼笪曼曼曼曼皇鼍皇曼曼曼曼量暑曼量鲁葛邑量鼍鼍l _mmm m 量曼曼皇曼皇曼皇曼詈皇曼鼍曼皇舅量曼鼍曼曼曼 线策略优于指数策略、指数策略优于惯性策略、而惯性策略优于开口向下抛物线策略 与粒子群算法相比较，差分进化算法在应用方面的研究还相对较少，急需开拓，但我们也欣 慰的看到，关于d e 应用方面的文献也能陆续看到，粒子群优化应用的所有领域都开始有差分进 化算法的应用，如在多目标优化问题4 2 埘】、约束优化问题4 6 4 7 1 、聚类分析1 4 8 , 5 2 1 ，其它方面的应 用1 5 ) , 5 6 等 然而，尽管d e 获得了广泛研究，但相对于其他进化算法而言，其研究成果相对分散，缺乏 系统性和良好的理论基础因此，对d e 算法的研究具有重要的现实意义，目前主要在以下领域 还有待于进一步开展研究 一、理论研究成果相对分散缺乏系统性 d e 算法在应用中被证明是有效的，但并没有给出收敛性，收敛速度估计等方面的数学证 明有些文献对收敛性等做了一些研究，但与遗传算法相比在理论和数学基础上的研究还很不够 二、算法研究 由于实际问题的多样性和复杂性，尽管已出现了许多改进d e 算法，但仍不能满足需要，研 究新的改进d e 算法是必要而且迫切的应注重高效d e 算法的开发，提出合理的核心更新公式 以及有效的均衡全局搜索和局部改进的策略，构造出有特色有实用价值的混合算法考虑到问题 的特殊性，应注重高效混合d e 算法的设计，包括d e 算法与问题信息或规则，d e 算法与神经网 络，模糊逻辑，进化算法，模拟退火算法，禁忌搜索，生物智能以及混沌等方法或策略的结合目 前已有很多算法和其它经典，现代优化算法结合的成果应用，如何将其它优化算法和d e 算法的 优点相结合，是当前算法改进的一个热点方向 三、应用领域还需要进一步的拓展 目前d e 算法的应用研究大多集中在函数优化，组合优化，神经网络训练，机器人学等方面， 以后应该注重在离散，多目标，约束，不确定，动态等复杂优化问题上的研究和应用同时，d e 的应用领域也有待进一步拓宽，如在数据挖掘，自动控制，模式识别，生产调度等领域的研究就 化工及自动化领域而言，问题的多极小性，多约束性，离散连续变量共存，非线性，多目标，不 确定性等复杂性普遍存在，算法的有效性必须在应用中才能体现，因此，d e 算法还需要在更广 阔的领域展开应用研究，是一个很有前景的研究课题 1 3 本文的结构与主要内容 本文研究内容分布于以下各章节中： 第一章，绪论：介绍了本文的研究背景、意义及p s o 和d e 算法的国内外研究进展 第二章，粒子群优化和微分进化算法：详尽地阐述和分析了p s o 和d e 算法的基本内容，包 括算法流程、参数设置对算法的影响 第三章，粒子群优化算法的改进：本章提出了两种改进的粒子群优化算法首先，在2 0 0 4 年 s u nj u n 等人提出的量子粒子群算法( q p s o ) 基础上进一步完善，提出了一种带有自适应变异的量 子群优化算法( a m q p s o ) ，在迭代过程中，当适应度方差趋于零而且空间位置的聚集度j i l 越小 时粒子陷入局部收敛，算法将出现早熟收敛为了克服早熟收敛，引入变异算子、构造变异概率， 对每个个体极值进行自适应变异，实验表明新算法有效增强了算法的全局收敛能力其次，由于 7 宁夏人学硕i j 论文第一章绪论 q p s o 算法也易陷入早熟收敛，利用混沌的遍历性进行初始化提高个体的质量，迭代过程中当粒 子群体陷入早熟时，对最优位置添加混沌扰动变量，以跳出局部寻优，避免了由随机初始化产生 的聚结现象及数次混沌搜索耗费大量时间、甚至出现效果不佳等现象，与p s o 算法和q p s o 算法 相比，c q p s o 算法能够取得更好的优化结果 第四章，差分进化算法的改进g 采用d e b e s t 1 和d e r a n d l 线性递减加权组合变异方案引入 开口向上抛物线缩放因子取值策略和指数递增交叉概率因子，以平衡局部搜索和全局搜索能力， 提高算法的全局寻优能力搜索后期根据适应度方差和空间位置聚集度进行自适应变异增加种群 的多样性实验结果表明新算法是一种收敛速度快、求解精度高、鲁棒性较强的全局优化算法 第五章，融合p s o 和d e 的改进l c 汹值聚类算法：针对现有基本量：均值聚类算法中存在的缺陷， 本章提出了融合p s o 和d e 的改进l i 己均值聚类算法主要是将p s o ( d e ) 算法代替了k - m e , a m 算法 中的基于梯度下降的迭代过程，由两种算法同时进化，找出最好的寻有结果，使算法具有了很强 的全局搜索能力，避免了k - m e a n s 算法易陷入局部极小的缺陷，同时也降低了k - m e a n s 算法对初始 值的敏感度实现了分布呈任意形状的样本聚类 第六章，对所作课题进行结论性总结，同时指出目前存在的问题与未来可能的研究方向 8 宁夏人学硕l j 论文第：章柁了群优化f n 差分进化算法 第二章粒子群优化和差分进化算法概述 2 1 粒子群优化算法 2 1 1 算法原理 粒子群优化算法【1 1 ( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出 的一种优化算法p s o 算法的运行机理不是依靠个体的自然进化规律，而是对生物群体的社会行 为进行模拟在生物群体中存在着个体与个体，个体与群体间的相互作用、相互影响的行为，这 种行为体现的是一种存在于生物群体中的信息共享的机制p s o 算法就是对这种社会行为的模 拟，即利用信息共享机制，使得个体间可以相互借鉴经验，从而促进整个群体的发展 p s o 算法的发展十分迅速，研究者对其改进策略非常多，但其基本原理相差无几与其它进 化算法相类似，p s o 算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索，即先生 成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个解，并由目 标函数为之确定一个适应值( f i t n e s sv a l u e ) 每个粒子将在解空间中运动，并由一个速度决定其方 向和距离通常粒子将追随当前的最优粒子而动，并经逐代搜索最后得到最优解在每一代中，粒 子将跟踪两个极值，一为粒子本身迄今找到的最优解，二为全种群迄今找剑的最优解 通过数学描述为：假设搜索空间是d 维的，粒子群由个粒子组成，其中第f 个粒子的位置 用向量t = “。，玉：，) f = l 2 ，n 表示，第f 个粒子的速度用向量k = ( ，叶2 ，) ， i = 1 ，2 ，n 表示，第f 个粒子位置记为，( f ) = ( b ，b ：，p m ) ，i = 1 ，2 ，n ，整个粒子群迄 今为止搜索到的最好位置记为珞= ( b 。，以：，) 按追随当前最优粒子的原理，粒子玉将按照 ( 2 1 ) 、( 2 2 ) 式改变速度和位置： v i ( t + 1 ) = u o ) + c l ( p 概o ) 一薯o ”+ c 2 r 2 ( p , ( t ) 一( f ) ) ( 2 1 ) x i ( t + 1 ) = x i ( t ) + v i (