改进的引力搜索算法及应用

发布时间：2018-05-08 20:19

  本文选题：引力搜索算法 + 索引的非支配解　； 参考：《吉林大学》2016年博士论文

【摘要】：近年来,在信息处理、机器学习、机器视觉与模式识别、管理科学等诸多领域存在着许多待解决的NP类复杂最优化问题。通过传统优化方法解决这类问题已变得十分困难,所以现在学者们一般通过仿生途径来解决这类复杂的最优化问题。仿生类优化方法与传统优化方法相比可以更快地找到优化问题的最优解,所以这类方法具有更高的现实意义和应用价值。群智能优化算法作为一类新兴的仿生类方法,属于智能优化算法的一个分支。与传统优化方法相比其优点在于:第一,在求解问题时通常对与问题相关先验知识没有要求;第二,对问题本身的数学性质如可导性和连续性没有任何要求;第三,不需根据问题本身创建精确的数学模型,因而可以用于求解那些不易构建形式化模型的问题;第四,求解结果不依赖于对知识的表示方式,而是直接处理输入信息。群智能优化算法之所以优于传统优化方法的原因在于它是一种按照概率进行搜索的算法,具体而言是通过观察自然界和生物界规律,模仿仿生学原理,在优化过程中利用种群间个体的竞争机制寻找问题的最优解。如上所述,与其他方法相比群智能优化算法具有较强的鲁棒性、并行性、自适应性、随机性,并且可以有效地解决集中控制的复杂分布式问题和用传统优化方法很难解决或无法解决的问题。对仿生类群智能优化算法的探索和研究具有重要的应用价值。目前智能优化算法主要包括遗传算法、引力搜索算法、模拟退火算法、人工神经网络、免疫算法、DNA计算、粒子群优化算法、狼群优化算法、蚁群优化算法、细菌趋药性算法和萤火虫优化算法等。其中群智能优化算法属于模仿动物群体智能的算法。智能优化算法共分为两大类,即随机性搜索算法与确定性搜索算法。其中随机性搜索算法又可分为基于单解的智能优化算法和基于种群的优化算法,基于种群的智能优化算法与基于单解的智能优化算法相比,具有可以并行搜索的特点。因此,近年来基于种群的智能优化算法受到了众多学者的高度关注。群智能的研究方向主要分为以下三种:一是群智能行为模拟研究,通过模拟种群的行为获取新系统模型并对其进行实现;二是分布式装置研究,利用机器人等先进设备和群智能的分布式搜索特性,设计分布式装置系统并对其进行实现;三是群智能算法研究,即对群智能算法的设计、改进及其应用。其中,群智能算法的改进及其应用是群智能理论研究的重点。虽然群智能优化算法取得了不少具有应用价值研究成果,但仍存在以下一些问题:(1)群智能算法的理论基础比较薄弱,理论分析没有普遍意义,如收敛性分析等。(2)算法中的参数通常依据经验设置,没有理论依据。因此群智能算法对应用环境和具体问题的依赖性较大。(3)当利用群智能算法处理突发事件时,系统可能会出现不可预测的反应,从而导致应用风险增加。总之,群智能优化算法具有较强的鲁棒性,较广的适用范围且不依赖于函数,但也有一些缺陷,如易早熟、后期算法收敛速度慢、寻优结果不精确等。虽然国内外学者提出了各种各样的改进方法,但仍存在一些亟待解决的难题。针对上述问题,本文主要研究了引力搜索和粒子群等群智能算法的改进,并将图像分类、图像检索作为一个新的应用领域。本文的主要贡献和研究成果如下:(1)对群智能优化算法的研究现状进行了全面综述,并分析和讨论了该领域当前的发展趋势和所存在的困难。同时重点分析和讨论了引力搜索和粒子群等群智能优化方法的研究现状和存在的缺陷。这些内容的讨论和分析是开展下一步研究工作的基础;(2)针对现有引力搜索算法迭代速度较慢且容易陷入局部最优等问题,我们提出一种新的混合引力搜索优化模型,并应用于图像分类领域。在该模型中,集成量化粒子思想和GSA搜索方法,几乎在图像特征提取的同时,进行特征选择,大大的简化了整个分类框架的特征提取与优化速度。后续结合SVM分类器,进一步提高了图像分类精度。实验结果表明,我们所提出的混合引力搜索优化算法在场景数据库中,如Scene-8和RGB-NIR数据库,取得优于现有的群智能算法。(3)基于向心加速的粒子群优化算法(Centripetal Accelerated Particle Swarm Optimization,CAPSO)作为一种改进的PSO算法,在优化学习与收敛速度方面有较大提升。但是,其未对搜索过程陷入局部最优的逃离速度加以控制,使得浪费了许多无效的停留时间,针对此,我们在CAPSO优化过程中增加旋转角度和旋转半径两个参数,使得其在向心加速过程中探索的时间最少,进而使得陷入局部最优的逃离速度大大加快。此外,我们进一步将该CAPSO的改进方法,应用于图像检索领域的相关反馈中。实验结果表明,我们的改进方法在医学图像检索中获得优于其他的群智能方法检索精度。(4)现有大多数的特征选择方法是针对单一目标,然而在需要实际应用中存在基于多目标的特征选择问题。鉴于此,我们提出一种基于多目标引力搜索的特征选择方法。基于多目标的思想不是单一的优化问题,而是对所有优化结果的子集进行分组,以获得非劣解和非支配解。实验结果表明,我们所提出的方法在UCI系列数据库中获得优于其他多目标优化算法的性能。下面就几项具体的创新性工作进行详细介绍。(1)改进的引力搜索算法及在图像分类中的应用。本文主要研究的引力搜索算法是一种新型的启发式群智能优化算法,它是由伊朗克曼大学的Esmat Rashedi等人在2009年所提出。引力搜索算法的基本思想源于对物理学的万有引力进行模拟而产生的群智能优化算法,即将搜索的个体看成一组在空间运行的物体,个体间通过万有引力相互作用吸引,引力作用的大小与个体的质量成正比,与个体之间的距离成反比,因此万有引力会促使个体们朝着质量最大的个体移动,从而逐渐逼近求出优化问题的最优解。在引力搜索算法中,每个搜索粒子的质量有四种属性,即位置、惯性质量、主动引力质量以及被动引力质量。粒子的位置代表着问题的解,它们的作用力和质量取决于对象的适应度函数值,算法通过调整引力和惯性质量来运行。在算法迭代过程中,期望粒子被惯性质量大的粒子所吸引,在整个搜索空间中,惯性质量最大的粒子代表问题的最优解。引力搜索算法的流程一般分为如下几个步骤:(i)识别搜索空间;(ii)随机初始化搜索群体,即初始化所有粒子的位置和加速度,并设置迭代次数和算法中所采用的参数;(iii)为每一个搜索粒子计算适应度值;(iv)更新万有引力系数;(v)计算各个不同方向的力,并计算其合力;(vi)计算加速度和速度;(vii)更新粒子的位置;(viii)循环步骤3-7,直到满足最优化问题的终止条件。从上述的步骤流程不难发现,与其他基于种群的启发式搜索算法一样,引力搜索算法的迭代循环中同样具有三个基本环节来实现优化算法的搜索与学习能力,即粒子本身的调整,粒子之间的互相作用,粒子的选择与更新。在第一个环节,粒子通过调整完成自身性能的提升;在第二个环节,粒子依靠相互作用完成信息的相互传递;在第三个环节,粒子之间通过对比适应值完成更新与选择。这三个环节都是启发式的,不同的群智能算法依据不同的种群特性制定不同的运算机制,并通过多次迭代搜索找到全局最优解。然而,相比其他群智能算法,引力搜索算法具有如下独特的机理特点:(i)引力搜索算法是一种基于交互机制的算法,在最优解的迭代搜索过程中,粒子搜索解是由质量的大小来确定的,质量小的粒子趋向质量大的粒子;(ii)粒子受到的合力来自于周围其他粒子对它的作用,即粒子可感应周围的环境;(iii)根据万有引力定律,质量大的粒子其万有引力也大,并对应着较好的解,从而其他粒子会向着质量大的粒子方向运动;(iv)惯性质量在一定程度上阻止粒子的运动改变,使得质量大的粒子运动速度较为缓慢。这种特性一方面使粒子的搜索解空间受到一定限制,但另一方面也使局部搜索更为精细。这种惯性质量可理解为自适应学习因子;(v)引力搜索算法是非记忆式的启发式算法,即引力搜索算法的每次迭代循环都是独立的,不受之前的寻优结果的影响,某粒子的运动只决定于当前状态下该粒子所受的合力。而粒子群算法相反,它是记忆式的。粒子算算法中的每次迭代均受到先前最优解的影响,这也是粒子群较易陷入局部最优的一个原因;(vi)引力搜索算法在高维问题的优化问题中表现更为优异,这归因于搜索粒子运动的特性。粒子之间引力的大小受粒子之间距离的影响,于是粒子在运动中,搜索空间的各个维数之间是互相联系的。引力搜索算法基于粒子之间的引力交互作用来完成寻找最优解的过程,而万有引力不需要借助任何传播介质,处于搜索空间的粒子可获知全局环境的信息,这使得粒子具有很强的全局搜索能力。然而,像其他全局搜索算法一样,引力搜索算法也容易陷入局部最优。现阶段,国内外研究工作者对引力搜索算法的改进主要集中在加强该算法的局部搜索能力、提高种群的收敛速度和寻优精度等方面,如增加搜索粒子的记忆性、基于混沌搜索、为质量计算引入权重等方法。由于引力搜索算法在处理优化问题上的优异表现,它在越来越多的领域得到应用,如决策函数的估计、混沌系统中的参数识别问题、机器人路径规划问题、聚类算法等等。截止目前,应用引力搜索算法在图像分类、图像检索领域应用相对较少,而该领域的特征选择、参数优化、用户相关反馈等问题都可通过应用引力搜索算法来解决。本文在以下三个方面对引力搜索算法进行了改进,进行了应用:1、通过分析引力搜索算法自身的机理和在寻优过程中存在的缺陷,试图引入某种解决方法来改进引力搜索算法,以提高寻优速度和寻优精度;2、将其他优化算法的思想与引力搜索算法相结合,进一步改进引力搜索算法;3、将引力搜索算法应用于机器视觉领域,以解决图像分类、图像检索领域中特征选择、参数优化、相关反馈等具体问题。(2)改进的向心加速的粒子群优化算法及在图像检索相关反馈中的应用将引力搜索思想应用在粒子群优化算法中,提出了一种新的群智能算法,即向心加速粒子群优化算法。本文从改进引力搜索算法的思想出发,对向心加速粒子群优化算法进一步改进,并应用到图像检索相关反馈中。粒子群优化(Particle Swarm Optimization,PSO)算法是一种最重要的群智能技术之一。粒子群优化算法对问题解的搜索是通过模拟自然界中的生物群体的社会行为实现的,例如鸟群和鱼群,种群个体之间相互协作,利用个体信息和群体信息寻找食物。粒子群优化算法将种群中的个体抽象为没有体积和质量但具有速度和位置的粒子,同时每个粒子还具有一个评判粒子位置好坏的适应度值。粒子群优化算法以进化代表候选解的粒子群的方式求解问题。粒子的位置对应解空间的决策向量,表示粒子在决策空间中的位置;粒子的速度对应粒子在前一代进化中位置的改变,表示粒子在决策空间中移动的长度和方向;粒子的适应度值对应粒子的目标向量,表示粒子的优劣。每个粒子具有一个个体最优位置,该位置是其所经历的所有位置中具有最高适应度值的位置,同时每个种群具有一个全局最优位置,该位置是全部粒子的个体最优位置中适应度值最高的位置。种群中的粒子在进化过程中向粒子的个体最优位置和种群的全局最优位置移动,使粒子收敛到问题的最优解。粒子群优化算法作为一种新型的启发式搜索算法,能够在可接受的时间内寻找到最优解,却不能保证最优解的精确性,粒子群算法求得的最优解只是近似解。粒子群优化算法首先以随机生成种群中粒子的初始位置和速度,然后对每个粒子进行进化操作,在进化过程中种群粒子利用个体最优位置和全局最优位置在解空间上更新自己的位置和速度,更新后计算出新位置的适应度值,如果更新后的位置的适应度值优于个体最优的适应度值,则更新个体最优,同理,如果新更新的位置的适应度值优于全局最优,更新全局最优位置的信息。与其他优化算法相比,粒子群优化算法的优点主要体现在一下几个方面:概念易于理解,算法实现简单,对领域知识没有要求,仅涉及一些简单的初等数学知识;对待求解问题本身的结构,组织形式等要求不高,可以是黑盒问题;算法求解速度快,能够在可接受的时间内找到最优解;算法具有灵活的全局搜索能力和局部搜索能力,同时可以使二者保持平衡,收敛速度快。然而粒子群优化算法也有一些缺点:理论基础薄弱,在搜索前期收敛速度很快,但当粒子趋近极值点时对算法的局部搜索调整比较慢,最终导致算法求解精度不高,不能够确保算法收敛到局部最优点;粒子群优化算法作为启发式算法,不能保证最优解的精确性,粒子群算法求得的最优解只是近似解;算法的局部搜索能力有限;当利用粒子群优化算法求解多峰问题时,算法易陷入局部最优,无法保证算法求解的精度;在算法迭代过程中种群多样性损失过快,使算法早熟。CAPSO算法主要探讨了向心加速度以及它如何影响粒子在解空间中的搜索。因此问题的关键在于如何有效的调节粒子向心加速度的参数。这样能够使CAPSO在特征提取和特征选择方面的效率得到加强,从而进一步地提高分类精度。此算法的第一步是初始化一组随机解对搜索空间进行搜索。搜索的目标是经过几次迭代后能够找到满足目标函数的粒子[158]。由于一些被公认优化方法都不能很好地解决高维度的问题,所以CAPSO算法也不例外。正是出于到这样的考虑,所以在CAPSO的基础上引入了其他参数使得算法在面对高维搜索空间的寻优问题时能够在局部开采和全局搜索方面做的更好。为了改进CAPSO算法,我们有必要提一下下面的这些问题:i.快速地从局部最优中跳出ii.可调节参数的缺失iii.对随机性的监管iv.搜索停止v.不一致性问题vi.运行速度慢vii.过早收敛viii.二进制和实数的转换问题本文改进了向心加速的粒子群优化算法,在CAPSO优化过程中增加旋转角度和旋转半径两个参数,使得其在向心加速过程中探索的时间最少,进而使得陷入局部最优的逃离速度大大加快。将改进的CAPSO,应用于医学图像检索领域的相关反馈中。实验结果显示,该改进方法优于其他的群智能方法。(3)基于多目标优化引力搜索算法的特征选择虽然多目标优化问题是被认为是复杂的问题,但是它在科研中非常有用。多目标优化问题和单目标优化问题的区别在于多目标优化问题要达到多个目标,但是这多个目标彼此之间可能存在冲突。在优化的过程中多个相关的目标被同时优化从而确定一组帕累托非支配解集。与单目标优化问题的解不同,帕累托解集是利用支配的思想从解空间集合当中选取的一组解。帕累托最优解的选择主要基于帕累托前沿,它们是那些处于支配地位的解集。特征选择是在对数据进行降维处理时常用的方法。特征选择是指在某种特定的评估准则指导下,从初始的特征空间中选择出满足该准则的最佳特征子集,使得该子集可以提高算法的泛化能力,降低特征空间的维数,并能在处理未知样本时增强模型的预测能力。当前已经有一些基于群智能算法的特征选择研究工作,但是都是针对单一目标的优化。然而在需要实际应用中存在基于多目标的特征选择问题。本文提出一种基于多目标引力搜索的特征选择方法。通过对所有优化结果的子集进行分组,进行多目标优化,获得非劣解和非支配解。最后在UCI数据库中进行了测试,结果表明效果优于其他多目标优化算法。
[Abstract]:......
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18
，

本文编号：1862919