导 师: 张超英
学科专业: H1202
授予学位: 硕士
作 者: ;
机构地区: 广西师范大学
摘 要: 优化技术是一种以数学为基础,用于求解各种组合优化问题的应用技术。最优化问题是人们在工程技术、科学研究、和经济管理等诸多领域中经常碰到的问题,它是指在满足一定的约束条件下,寻找一组参数值,使目标函数达到最大或最小。最优化问题根据其目标函数、约束条件的性质以及优化变量的取值范围可以分为许多类型,例如:根据目标函数和约束条件是否均为线性表达式,把最优化问题划分为线性规划问题和非线性规划问题。针对不同的最优化问题,提出了许多不同的优化方法,如牛顿法、共轭梯度法、polar-ribiere法、拉格朗日乘子法等。这些优化算法能很好地找到问题的局部最优点,是成熟的局部优化算法。 但是随着人类生存空间的扩大以及认识与改造世界范围的拓展,人们发现由于问题的复杂性、约束性、非线性、建模困难等特点,解析性优化算法已不能满足人们的要求,需要寻找一种适合于大规模并行且具有智能特征的优化算法。 现代进化类方法如人工神经网络、遗传算法、禁忌搜索法、模拟退火法和蚁群算法等在解决大规模的问题时体现出强大的潜力,它们可以在合理的时间限制内逼近优化问题的较好可行解。其中,遗传算法和蚁群算法被称为智能优化算法,其基本思想是通过模拟自然界生物的行为来构造随机优化算法。 近十几年来,粒子群算法(particle swarm optimization,简称pso)越来越受到学者的关注。粒子群算法是美国社会心理学家james kennedy和电气工程师russell eberhart于1995年共同提出的,它是受到鸟群社会行为的启发并利用了生物学家frank heppner的生物群体模型而提出的。该算法用无质量无体积的粒子作为个体,并为每个粒子规定简单的社会行为规则,通过种群间个体协作来实现对问题最优解的搜索。由于算法收敛速度快,设置参数少,容易实现,能有效地解决复杂优化问题,在函数优化、神经网络训练、图像处理、模式识别以及一些工程领域都得到了广泛的应用。 不过,尽管粒子群算法的发展经历了十几年,但是无论在理论上还是在实践上都尚未成熟。粒子群算法也和其它全局优化算法一样,有易陷入局部极值点,进化后期收敛慢,精度较差等缺点。如何加快粒子群算法的收敛速度和提高算法的收敛精度,一直是大多数研究者关注的重点。加快收敛速度的措施主要有如何选择最优的算法参数,以及与其它优化算法结合来对粒子群算法的主要框架加以修正。在提高收敛精度,防止粒子早熟方面,主要有设法保持种群的多样性,或引入跳出局部最优点的机制等措施。现已有的改进粒子群算法有模糊自适应pso算法(fapso),杂交pso算法(hpso),离散二进制pso算法,协同pso算法,免疫粒子群优化算法等。 近年来,差分进化(differential evolution,de)算法以其独特的方便性和有效性得到人们的重视。差分进化算法(de)是由rainer storn和kenneth price为求解切比雪夫多项式而于1996年共同提出的一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法。de的原理简单,受控参数少,实施随机、并行、直接的全局搜索,易于理解和实现。 本文在粒子群算法和差分进化算法的基础上,对现有相关文献进行了研究和分析,通过引入一种新的信息交流机制,提出了一种基于改进后的粒子群算法再与差分进化算法进行混合的新型算法,有助于信息在两个不同种群中传递,从而达到改善算法性能的目的。研究中发现,并不是所有的pso改进后,再与de混合就能取得较好的性能,同时注意到,本文建立的基于不同选择策略的改进型pso,再与de混合,能取得较好的性能,原因在于这种改进的pso进化策略与de进化策略形成互补,混合后就能改善pso性能。 本文以函数优化为例,选取最近在核心学术期刊公开发表的算法为比较例子,用matlab编出源码,通过对sphere、rastrigrin、rosenbrock、quadric、girewank等几个学术界公认的经典测试函数进行测试,来说明本文提出的算法的优越性,具体如下: 1、通过对标准测试函数的测试,发现新型混合算法比单纯的粒子群或差分进化算法有更优越的性能,收敛精度更高,并且越高维时混合算法的优点表现得越明显。 2、通过对标准测试函数的测试,发现在quadric函数的情况下,差分进化算法的收敛性表现极差,但跟粒子群算法混合起来,收敛性就能取得比两种算法自身还优越的效果。 3、在高维的情况下,差分进化算法收敛性表现很差,一旦与粒子群算法混合,收敛性就有极大的进步,并有比两种算法自身还好的性能。 最后,把本文提出的新型混合算法应用到模糊聚类中,收敛精度有了提高,错分率取得预期的效果,说明本算法在具体应用的有效性。
关 键 词: 粒子群 差分进化混合算法 信息交流机制 性能 模糊聚类 收敛精度
分 类 号: [TP301.6]
领 域: [自动化与计算机技术] [自动化与计算机技术]