（计算机应用技术专业论文）基于可拓学的多种群粒子群优化算法研究.pdf

摘要 基于可拓学的多种群粒子群优化算法研究 摘要 粒子群优化算法白提出到现在，得到了众多学者的广泛关注与研究， 它已被应用到越来越多的领域来解决各种优化问题。随着研究的深入及待 解决问题越来越复杂，粒子群优化算法的发展逐渐得到完善，各种改进措 施被相继提出，让粒子群算法的应用范围和性能得到进一步提高。粒子群 算法的改进，已不单局限在对算法本身的参数的修改上，它与其他优化算 法的结合也成为研究粒子群算法改进的一大重要方向。 可拓学是由中国学者自己发明创造的一门新学科，主要用于解决社会 生活中的矛盾问题。可拓学白提出到现在已有了自己的理论框架及应用研 究。近年来，可拓学与其他优化算法结合的研究也取得了进展，如可拓遗 传算法等，开辟了可拓学与智能优化算法结合的新思路。 本文将可拓学的思想加入到粒子群优化算法中，提出了一种基于可拓 学的多种群粒子群优化算法。与传统粒子群算法相比，它更具有生物特性， 更接近于鸟群觅食的真实规律。它让位于不同层次的粒子采取不同的进化 措施，并利用可拓变换的思想，让坏死粒子重新启用。通过测试函数，验 证了算法的效率。 关键词：可拓学，物元，可拓变换，粒子群，多种群，优化 a b s t r a c t t h es t u d yo fe x t e n i cs b a s e dm u l t ip a r t i c l e s w a r mo p t i m i z a t i o n a b s t r a c t p s o ( p a r t i c l es w a r mo p t i m i z a t i o n ) a l g o r i t h mh a sb e e nc o n c e r n e da n d , r e s e a r c h e dw i d e l yb ym a n ys c h o l a r ss i n c ei ti sp r o p o s e d ，w h i c hh a sb e e n a p p l i e dt os o l v ev a r i o u so p t i m a lp r o b l e m s i nm o r ea n dm o r ef i e l d s a l o n gw i t h t h ef u r t h e rr e s e a r c ha n dt h ei n c r e a s i n gc o m p l i c a t i o no ft h ea w a i t i n gs o l u t i o n s ， a l lk i n d so fi m p r o v e m e n tm e a s u r e sh a sb e e np r o p o s e ds u c c e s s i v e l yt op e r f e c t t h ep s oa l g o r i t h m ，w h i c hh a sm a d et h ea p p l i c a t i o ns c o p ea n dt h ep e r f o r m a n c e o fp s of u r t h e ri m p r o v e d t h em o d i f i e dp s oa l g o r i t h m sa r en o to n l yl i m i t e d t ot h ep a r a m e t e r sa m e n d m e n t ，w h o s ec o m b i n a t i o n sw i t ho t h e ro p t i m i z a t i o n a l g o r i t h m sh a v ec o n s t i t u t e da ni m p o r t a n tr e s e a r c hd i r e c t i o no ft h ep s o e x t e n i c si san e ws u b j e c te s t a b l i s h e do r i g i n a l l yb yc h i n e s es c h o l a r ， w h i c hi sm a i n l yu s e dt os o l v ec o n t r a d i c t i o np r o b l e m si ns o c i a ll i v e s e x t e n i c s h a si t so w nt h e o r e t i c a lf r a m e w o r ka n da p p l i c a t i o nr e s e a r c hs i n c ei ti sp r o p o s e d i nt h er e c e n t y e a r s ，t h es t u d yo n e x t e n i c sb i n d i n go t h e ro p t i m i z a t i o n a l g o r i t h m sh a sg o ts o m ea d v a n c e ，s u c ha st h ee x t e n s i o ng e n e t i ca l g o r i t h m ， w h i c ho p e nan e wt h i n k i n go nh o wt oc o m b i n ee x t e n i c sw i t hi n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s t h i sp a p e ri n t r o d u c e st h ee x t e n i c si n t op s o ，w h i c hp r o p o s e dam p s o 北京化t 人学顾十学位论文 a l g o r i t h mb a s e do ne x t e n i c s c o m p a r i n gw i t ht h et r a d i t i o n a lp s oa l g o r i t h m ，i t p o s s e s s e sm o r eb i o l o g i c a lc h a r a c t e r i s t i c sa n di sm u c hm o r ec l o s e dt ot h er e a l r u l e so fb i r d ss w a r m sf o r a g i n g i tm a k e st h ep a r t i c l e so nd i f f e r e n tl a y e r sa d a p t d if f e r e n te v o l u t i o nm e a s u r e s t h e nu s i n ge x t e n s i o nt r a n s f o r m a t i o nt om a k et h e b a dp a r t i c l ep u ti n t os e r v i c ea g a i n t h r o u g ht e s tf u n c t i o n ，a l g o r i t h me f f i c i e n c y h a sb e e nv a l i d a t e d k e yw o r d s ：e x t e n i c s ，m a t t e r - e l e m e n t ，e x t e n s i o nt r a n s f o r m a t i o n ，p s o ， m u l t is w a r m ，o p t i m i z a t i o n i v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：猛进：丛 日期：迎12 ：篁：至立 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的 规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京 化工大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学 位论文。 保密论文注释：本学位论文属于保密范围，在上一年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：弓丝照选 日期：鲨! ! ：皇：圣z 导师签名： 第一章绪论 1 1 课题背景及研究意义 第一章绪论 在生产生活中，科学研究、工程技术、社会科学和经济管理等多个领域罩，有一 种引起人们广泛关注并致力解决的问题，这就是优化问题。所谓优化就是在多种可行 方法中选出较优的问题的解的方法。对优化问题的研究，具有非常高的理论价值和应 用价值，至今也已形成了许多研究理论和方法。随着社会的进一步发展，需要解决的 问题规模和复杂性都越来越高，解决问题的困难也越来越大，因此，对优化算法的进 一步研究也越来越有必要。二次世界大战后，随着科学技术的迅猛发展，优化已经逐 渐成为一门新兴学科，并有广泛的科学应用，国防安全、交通运输、工程工业、经济 研究及生产管理等重要领域都要用到优化方法，它已引起政府机构、科研单位和生产 部门的高度重视。 对优化问题的解决，有很多专门的优化方法。近年来，对优化方法的研究热潮， 呈现一片上升的趋势，既有基于数学支持的精确算法，也有从生物智能中发展起来的 群智能优化方法，对优化方法的研究已具有越来越深刻的现实意义。 1 1 1 优化问题 在日常生活和工业生产的过程中，当遇到某个问题有多个解决方案可供选择的情 况时，如何根据问题自身所提出的某些性能的要求，从多个方案中选择一个可行方案， 使要求的性能指标达到最大或最小，这就是最优化问题。例如，在工业生产中怎样选 择参数，既能满足要求又能降低成本资源，怎样分配成本资源既可以满足各个方面的 要求，又能获得好的经济效益等。最优化问题已成为工程技术和经济管理领域中的一 种常见问题。 最优化的问题种类和性质繁多，按约束条件可分为无约束优化和约束优化两大 类。当决策变量的取值范围为整个实数空间时，称该问题为无约束优化；当决策变量 的取值受某一些约束条件的限制时，该类问题称为约束优化问题。 优化问题要优化的目标通常用一个函数表示，称为目标函数： ，、，、 ) = k ，z ：，吒j 式( 1 1 ) 对优化问题求解一般就是求目标函数的最大或最小值，但由于求最大值可以转换 为求负的最小值，因此，最大最小值问题并没有本质区别。 北京化工大学硕j 二学位论文 当决策变量可以取到实数空间的任意值时，即x r ”，求目标函数的最小值问题 称为无约束优化，记为： m i n f ( x ) 式( 1 2 ) x e r ” 当决策变量受某些条件的约束，比如决策变量必须在某一范围内或决策变量必须 满足某一等式要求时，求目标函数的最小值问题就称为约束优化，记为： f m i nf ( x ) g ) 0 x a 【j | l 似) = 0 x b 其中，a ，b 分别为不等式约束和等式约束中决策变量的取值范围。 优化问题根据不同的标准可以有多种分类方法，通常有如下几种： 1 按目标函数及约束函数性质分：线性规划、非线性规划、几何规划、整数规划、 二次规划问题等； 2 按计算复杂度分：p 问题、n p 问题、n p - h a r d 问题、n p c 问题等。 3 按包含变量确定性分：确定性规划问题、随机规划问题。 4 按目标函数与约束函数的可分离性分：不可分离问题、可分离问题。 在人们的生产生活中，可能遇到各种各样的需要优化的问题，这就需要根据待优化问 题的不同特性，用不同的优化方法进行求解。 1 1 2 求解方法 当目标函数为非线性时，不管其有没有约束条件，函数的求解都十分困难，特别 是对于目标函数在定义域内取得多个极值点时。求解这类非线性问题的优化方法，其 求解结果与初始值的选取有很大关系，一般的非线性优化方法只是求目标函数在定义 域内的近似极值点，而非真正的最小值点。总的来说，求最优解或近似最优解的方法 主要有两种：精确算法和启发式算法。 1 精确算法。精确算法可对解空间进行彻底搜索，得到精确全局最优解，如线性 规划、整数规划、动态规划等，但这类算法只能使用于有限的优化问题； 2 启发式算法。启发式算法又称为近似算法，它通过寻求一种能产生可行解的启 发式规则，来找到一个最优解或近似最优解。但不一定能保证找到解得可行性和最优 性，甚至不能证明所得解与最优解的近似程度。该方法的求解效率虽然较高，但对不 同的求解问题未必能找出其特有的启发式规则，不具有通用性。 2 0 世纪七八十年代以来，涌现出一些新的优化算法，如神经网络、混沌、遗传算 法、进化、模拟退火、禁忌搜索以及混合优化策略等，它们通过模拟自然现象的过程 规律而得到发展，在数学、物理、生物进化、人工智能、神经科学和统计力学等各方 2 第一章绪论 面都有涉及，提供了新的解决复杂问题的思路和手段。这些算法在优化领域掀起了研 究热潮，且已成功应用到工程实践中。这些算法通常也被称为后启发式算法。 后启发式算法主要包括进化算法、智能算法和群智能优化算法。 进化算法主要分为三类【l 】：遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 【2 1 、进化策略 ( e v o l u t i o ns t r a t e g i e s ，e s ) 【3 】和进化规划( e v o l u t i o np r o g r a m m i n g ，e p ) 1 4 】。第一类 方法【5 】现在已比较成熟，并被广泛应用，后两种算法也越来越广泛的应用在科研和实 际问题中。进化算法是一系列搜索技术，尽管它们有很多变化，但都是基于自然进化 过程的基本模型。与传统的基于微积分的方法和穷举法相比，进化计算具有高鲁棒性 和广泛适用性的特点，是一种全局优化方法，具有自组织、自适应、自学习的特性【6 1 。 智能算法比较著名的有模拟退火、禁忌搜索和人工神经网络等。 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 是k i r k p a t r i c k 于1 9 8 3 年提出的【7 1 。它是 一种基于m o n t ec a r l o 迭代求解策略的随机寻优算法，从一个较高的初始温度出发， 利用m e t r o p o l i s 抽样策略在解空问中随机搜索，随着温度的下降不断重复抽样过程， 最终找到问题的全局最优解。 禁忌搜索算法( t a b o os e a r c h ，t s ) 由g l o v e r 于1 9 8 6 年提出【8 ，9 】。该算法引入了一 个灵活的存储结构，通过相应的禁忌准则避免迂回搜索，并利用藐视准则，赦免被禁 忌的优良状态，保证多样化的有效探索，实现全局优化。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 是新近发展的一个新的人工智能 课题【lo 】。它利用神经元的协同并行能力来构造优化算法，将实际问题的优化解对应于 神经网络的稳定状态，把对实际问题的优化过程与神经网络的演化过程相对应。目前 神经网络技术已得到广泛应用，许多生产实践中都利用神经网络来调控参数，提高生 产率。 群智能优化算法( s w a r mi n t e l l i g e n c e ，s i ) 是一种新兴的演化计算，它已越来越 多的被研究者们关注。它和人工生命有非常特殊的联系，特别是进化策略和遗传算法。 群智能优化主要有两种算法：蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 【l l 】和粒子群 优化算法( 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 ) 1 2 , 1 3 】。蚁群算法模拟蚂蚁群落寻觅食 物的过程，它在许多离散问题上得到成功应用。粒子群优化算法是对鸟群觅食过程的 模拟，用粒子代替鸟，用粒子位置的迭代更新模拟每一次鸟群的变化，最终实现全局 搜索，达到最优解。此外，还有新近提出的人工鱼群算、法【1 4 , 1 5 也是一种群智能优化算 法。 近年来，在我国学者蔡文提出了可拓学之后，可拓优化的概念也渐渐地进入我们 的视线。本文将重点介绍粒子群优化算法和可拓理论，并提出一种二者的结合算法， 为优化算法的研究提供一条新的思路。 北京化t 人学硕十学位论文 1 2 粒子群算法研究现状 粒子群优化算 法( p s o ) f f e - - 种基于群智能方法的演化计算技术【1 6 】。系统先初始化 一群随机粒子，每个粒子代表问题的一个解，让粒子通过迭代更新，来达到最优值。 p s o 算法简单、易实现，且又包含深刻的智能背景，既适合于科学研究，又可以应用 于工程领域，所以算法一经提出，在演化计算领域立刻引起了学者的广泛关注，在短 时间内出现了多种改进措施，现在已成为一个研究热点。 p s o 算法由k e n n e d y 和e b e r h a r t 在1 9 9 5 年提出【1 2 , 1 3 】，受人工生命研究结果的启 发，p s o 算法概念的提出源于对鸟群捕食行为的研究。鸟群在觅食时，并不知道食物 的具体位置在哪，他们的位置也是随机分布的，但是它们之间可以互相交流，当有一 个鸟发现食物时，其他的鸟都会朝着离食物最近的鸟的方向飞行，通过改变自己的位 置来改变离食物的距离，并在每次飞行后都观察一下自身附近是否有比现有食物更好 的食物源，如果有则飞向新食物源，其他鸟也一样，重复这样的动作，直到找到最好 的食物。算法从这种模型中受到启发，并被应用于解决优化问题。每个优化问题的解 对应于搜索空间中的鸟，一个鸟就是一个粒子。每个粒子都有自己的位置和飞行速度， 速度决定他们的飞翔方向和距离，- 通过飞行来改变当前位置。粒子与优化问题的关系 由一个适应度函数决定，适应度函数值越优，说明粒子越适合于优化问题，通过适应 度函数，可以找出当前最优粒子。p s o 算法就是通过初始化这样一群随机粒子，让粒 子不断更新迭代找到最优解。在每一次迭代中，微粒通过两个“极值 来更新自己的 位置和速度。第一个是粒子本身所达到的最优值，称为个体极值；另一个是整个种群 目前达到的最优值，称为全局极值。 目前，对粒子群算法的研究大致分为：理论研究、改进研究和应用研究等。 1 理论研究 p s o 算法是根据自然界中鸟类觅食现象而设计的一种优化算法，它具有明显的生 物特性，但其数学基础相对比较薄弱，缺乏具体数学形式支持的理论分析。所以，能 从理论上对p s o 算法进行严格的数学证明就显得非常重要。 e n d e ro z c a n 和c h i l u k u r ik m o h a n 于1 9 9 9 年首次对p s o 作了理论分析的尝试【l7 】； m a u r i c ec l e r c 则在2 0 0 2 年对粒子的运动轨迹作了更深入的分析【1 8 】，微粒群算法【1 9 】 中在基于离散时间线性系统的基础上，理论的分析了p s o 算法的渐进收敛特性，并给 出了代数分析和解析分析模型。p s o 算法的拓扑结构和邻域结构的分析也取得了进 展，给出了粒子的成长轨迹和步长的数学分析，并给出加速度常数c 1 + c ，4 的数学 证明【2 0 1 。文献【2 1 1 采用系统动力学原理，分析了p s o 的收敛性和参数选择。文酬2 2 1 在 前人研究的基础上，也对粒子的运动轨迹和算法的收敛性进行了理论分析。 4 第一章绪论 2 改进研究 p s o 算法虽然简单易实现，但它也有本身的一些缺点，如收敛性能和计算效率较 差等问题，加之实际问题又非常复杂，因此各国学者对p s o 优化提出了很多改进措施。 惯性权重的概念首次由s h i ，e b e r h a r t 加入到p s o 算法中，并让其值从1 4 减小到 0 3 5 2 3 , 2 4 1 ，后来又进一步发展成为模糊自适应p s o 2 5 1 。 收缩因子由c l e r i c 提出【2 6 1 ，并给出计算公式。 带选择机制的p s o 优化由a n g e l i n e 提出【2 7 1 ，并指出其对于解决单峰函数的优化 问题具有明显效果，后来a n g e l i n e 又借鉴遗传算法的思想，提出了杂交p s o 2 8 1 。杂 交p s o 有比较快的收敛速度，其搜索精度也相对较高，特别是对于多峰函数，效果尤 为明显。a n g e l i n e 还指出当迭代次数增加时，p s o 算法不一定能进行精确搜索，因此 他又提出了带邻域的p s o 算法。 在空间邻域和环型拓扑结构的基础上，k e n n e d y 提出了具有社会模式的聚类分析 p s o 2 9 1 。 为解决组合优化问题，k e n n e d y 和e b e r h a r t 提出离散二进制的p s o 3 0 1 。 拉伸变化的概念提出之后，p a r s o p o u l o s 和p l a g i i a n a k o s 将其应用于极小化问题的 求解，形成了拉伸p s o 算法【3 1 】。 b e r g h 提出随机p s o ，多次启动p s o 算法【3 2 】。 b u t h a i n a h 等人提出多相p s o 算法，在算法中引入分群的思想和相的概念【3 3 1 。 雷开友提出通过团队协作寻找惯性权重曲线的p s o 算法、具有感觉特性的p s o 算法和基于长时记忆的p s o 混合算法等三种改进【3 4 】。 熊勇提出基于混沌搜索寻优的p s o 、p s o 和b f g s 的混合算法，以及基于旋转曲 面变换的p s o 2 0 1 。 还有其他一些对粒子群优化的改进，这里就不一一列举。 3 应用研究 在工业领域，c o s t a 等利用p s o 算法求解苯乙烯聚合反应的最优稳态操作条件f 3 5 】； o u r i q u e 等用p s o 估计化工动态模型中产生不同动态现象的参数区域，通过仿真结果 显示了p s o 能提高传统动态分叉分析的速度【3 6 】；k a n n a n 等将p s o 用于最低成本发电 扩张g e p 问题，有效的解决了带有强约束的组合优化问题【3 7 】；李崇浩等用p s o 求解 水库优化调度问题，比传统的动态规划算法节省了计算时间，取得了不错的效果【3 8 】。 汪新星等在求解水火电力系统的短期有功负荷最优分配问题时，利用引入“分群 和 “灾变 思想的p s o ，取得了很好的实效【3 9 1 。肖健梅等用p s o 求解物流配送车辆的 路径问题【柏1 。李辉应用p s o 求解水电站优化调度问题【4 1 1 ，赵辉应用p s o 优化电力系 统稳定器参数【4 2 1 。 北京化t 大学硕士学位论文 在通讯领域，p a r k 将p s o 应用于r f ( r a d i of r e q u e n c y ) 电路的设计【4 3 】；z h a n g 等利 用p s o 解决光通讯系统的p m d ( p o l a r i z a t i o nm o d ed i s p e r s i o n ) 补偿问题m j 。王雪提 出了基于并行p s o 的无线传感网络移动节点位置的优化策略【4 5 1 。 在经济管理领域，p a v l i d i s 应用p s o 求博弈论的n a s h 均衡觯4 6 】；n e n o r t a i t e 应用 p s o 和神经元网络技术，解决最大利益的股票交易决策问题【4 7 】。张连营在工程项目管 理中资源均衡问题上，建立基于p s o 的工程项目资源均衡模型【4 8 1 。 在图像处理中，y i n 利用离散p s o 解决多边形的近似问题，提高了多边形的近似 结剁4 9 】；p a r s o p o u l o s 在放射治疗模糊认知图的模型中，利用p s o 进行参数优化【5 0 】； c a o r s i 利用基于p s o 的微波图像法，确定电磁散射体的绝缘特性【5 1 】；w a c h o w i a k 利用 结合局部搜索的混合p s o 算法，对生物医学图像进行配准【5 2 1 。 在生物信息和医学领域，r a s m u s s e n 等在处理蛋白质序列比对的问题上，利用p s o 训练隐马尔可夫模型【5 3 】；x i a o 利用p s o 和自组织映射的混合聚类方法，解决基因聚 类问题阱】；s h e n 等利用离散p s o 对m l r ( m u l t i n o m i n a ll o g i s t i cr e g r e s s i o n ) 和p l s ( p a r t i a ll e a s ts q u a r e s ) 的模型进行参数选取，以及预测血管紧缩素的对抗性【5 5 1 。 粒子群算法从诞生到现在，引起了许多科研工作者的重视，并已被广泛应用到了 生产生活中的众多领域，本文在前人研究的基础上，将粒子群与最近新兴起的可拓学 结合在一起，开辟了粒子群与其他方法结合的新思路。 1 3 可拓学研究现状 现实世界中存在着许多的矛盾问题，例如在浅海上建桥，如何让拉着很重水泥板 的车在沙滩上前行；如何在人类手工不能细致到的地方进行工业生产；要选择一个优 秀的人胜任一项工作，没有合格的人选怎么办，诸如此类，社会生活中到处充满着矛 盾。那怎样解决矛盾问题呢，有没有可依靠的理论依据? 可拓学的研究重点就是解决 矛盾问题，它提出用形式化的方法解决矛盾问题的研究方向。 要解决矛盾问题，仅在数量关系上来处理是不行的。曹冲称象的关键就是把大象 转换成了与它等重的石头，这叫变换。新买的沙发横着竖着都拿不到屋罩，是因为沙 发的长度和宽度与门的长和宽矛盾了，如果把沙发侧着放，让沙发的高度和宽度对应 门的长与宽，这就把矛盾问题转换成了相容问题，这也需要变换。所以我们不能仅仅 在数量关系上解决问题，我们还要研究事物的特征，明白不同特征的量值，通过对事 物进行变换或变换矛盾问题来找出解决方案。事物与特征及特征量值之间的关系，就 对应于可拓学中物元的概念，把三者作为一个整体看待，就构成了可拓学中的一个细 胞。每一个事物都具有可以拓展的性质，这称为事物的可拓性，可拓性是可拓论里的 一个重要概念，它提供解决矛盾问题的依据。事物的可拓性在可拓学里用物元的可拓 6 第一章绪论 性表示。 可拓集合和不相容问题一文的发表，标志着可拓学的诞生。从可拓学概念的 提出到现在已近三十年，在这期间，一大批研究者们投入到了可拓学的建设之中。目 前，对可拓学进行的理论研究己取得一定进展，形成了以物元理论、可拓集合和可拓 变换为主要内容的可拓方法。它们已被应用到各个领域，形成一系列的可拓工程。可 拓学主要用于解决矛盾问题，它是用形式化模型来研究事物拓展的可能性和开拓创新 的规律与方法的科学。 近十几年来，一批有关可拓学的学术专著被相继出版，它们主要介绍可拓学的理 论成果和应用成果，如理论方面的有可拓工程方法，物元模型及其应用和从 物元分析到可拓学；应用方面的有可拓营销和可拓策划等。这些专著在我 国内地和台湾等多所大学中都能找到它们的读者。可拓工程方法和可拓营销 在台湾地区出版上市。自2 0 0 2 年起，可拓学丛书包括英文版专著已相继出版，有关 可拓学的论文也被相继发表在多家杂志上。在这些丛书和论文中，初步建立了可拓学 的理论体系框架。 可拓学与其他学科相结合，产生了多个领域中的可拓工程理论与方法。今年来， 可拓理论在人工智能领域、自动化领域，经济管理领域及机械设计等领域内都有广泛 应用。 2 0 0 4 年，科技部的科技成果管理办公室发布的可拓学研究成果指出：可拓学是一 项原始性的创新研究，在海内外同类研究中都处于领先和指导地位。以中国科学院 院士吴文俊和中国工程院院士李幼平为首的鉴定委员会在对可拓论及其应用研究 鉴定之后，指出在经历二十多年的研究之后，蔡文教授等人建立起了一门横跨哲学、 数学和工程学的新学科，可拓学是- - i - 由我国科学家自己建立，且具有深远价值的原 创性学科。中国科学院院士王梓坤先生曾说，可拓学是“前无古人，外无洋人 的创 造性成果。 1 4 本课题的研究内容 标准粒子群优化算法虽然简单实用，对有些问题也可以得到不错的结果，但它本 身也存在一些缺陷，如收敛速度慢和容易陷入局部最优值等。本文选用多种群粒子群 优化算法，并利用可拓学本身具有的选优功能，将可拓学与粒子群优化算法结合在一 起，把每一个粒子看作是一个物元，利用关联函数对物元的评价作用，把粒子分成不 同的层次，让位于不同层次的粒子采取不同的进化措施。让适应度值比较好的粒子， 取用较小的惯性权重，限制其位置变化幅度，防止其跳出极值周围，增加粒子的局部 搜索能力；对适应度值比较差的粒子，通过增大其惯性权重值，让粒子更新的速度和 位置范围加大，加快它向最优值的靠拢，增大全局搜索能力。本文还利用可拓变换的 7 北京化工人学硕- 学位论文 思想，对适应度值特别差的粒子采取变换，用适应度值优的粒子代替坏死粒子，加快 了粒子的收敛。 1 5 论文的组织结构 全文共分五章，具体安排如下： 第一章绪论 首先介绍课题的研究背景，给出优化的概念和方法，后介绍了从基本的优化算法 发展起来的群智能优化算法，及近年来新兴起的可拓学。尤其介绍了粒子群优化算法 和可拓学的国内外研究历史和现状，最后介绍了本课题的主要研究内容。 第二章粒子群优化算法 详细介绍粒子群的理论基础，包括基本原理、算法改进、参数设置等，以及粒子 群的应用及与其他算法的比较等。 第三章可拓理论 介绍可拓学的理论基础，包括物元理论和可拓集合等。 第四章基于可拓学的多种群粒子群优化算法 详细说明基于可拓学的多种群粒子群优化算法原理及程序流程，并通过对测试函 数的寻优与多种群粒子群算法进行比较，通过比较结果证明改进算法的有效性。 第五章结论与展望 对全文进行总结，并对未来的发展进行展望。 8 第二章粒子群优化算法 2 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 年提出的，它是一种群智能优化方法。粒子群优化算法通过模 拟鸟群觅食的行为，让个体之间相互协作使群体达到最优目的。同遗传算法( g e n e t i c a l g o r i t h m s ，g a ) 类似，它们都是基于群体叠代。系统由一群粒子组成，初始化为一 组随机解，粒子通过在追随群体最优粒子时进行协同搜索以达到最优。它没有交叉、 变异的操作，与达尔文“适者生存、优胜劣汰”的遗传算法不同。粒子群优化算法更 强调种群中个体粒子之问的协同与合作。粒子群优化算法从提出到现在，短短几年内， 已得到大力发展，各种理论研究及与其他优化技术的结合方法被相继提出，并已在很 多领域，进行了实际应用。目前，粒子群优化算法正逐渐成为一个新的研究热点。 2 2p $ o 算法 粒子群优化算法( p s o ) 是一种基于群体智能的随机优化技术。与其它进化算法相 比，它们的相同点是均初始化一组随机解，通过迭代达到最优解。不同的是进化计算 遵守适者生存的原则，而p s o 模拟社会行为，它将每个可能解表述为一个粒子，每个 粒子都有自己的位置和速度，以及一个由优化目标决定的适应度函数。所有粒子在搜 索空间中以各自的速度飞行，通过追随当前最优值来更新自己的位置，不断迭代达到 全局最优。 p s o 基本概念之一就是通过三条简单规则对粒子进行操作来模拟社会：飞离最近 的个体，以避免碰撞；飞向目标；飞向群体的中心。与其他优化算法相比，p s o 具有 以下优点： 1 具生物特性，容易理解； 2 需要调整的参数个数少； 3 实现简单，容易收敛； 4 个体故障不会影响整个问题的求解，系统具备高鲁棒性。 2 2 1 基本原理 自然界中动物的个体行为非常简单，但通过个体互相协作的群体行为却能完成非 常复杂的事情。通过研究鸟群觅食行为，研究者们对于鸟群表现出的一致性及协作性 很感兴趣，他们对每个个体的行为进行数学建模，通过在计算机上的模拟，再现鸟群 9 北京化t 大学硕士学位论文 觅食行为。在搜寻食物的过程中，鸟群中的个体成员能利用其它成员找到食物的信息， 这种对信息的利用在不确定食物具体位于什么地方时，显得至关重要，信息的分享机 制远远超过了竞争导致的不利。这一点是粒子群优化算法的基本原理。算法的主要思 想是把求解目标函数最优值的过程看成鸟群觅食行为，函数的每个可行解看作一只 鸟，称它为粒子，每个粒子都有一个评价它的函数，即离食物源的远近，粒子之间是 可以互相交流的，这样就可以知道谁离食物源更近。粒子通过利用自己的经验和其它 成员的经验来调整自己的状态。 粒子群优化算法和其他进化算法相似，都采用群体和进化的概念，根据粒子的适 应度值大小进行更新。不同的是，粒子群算法不像其他进化算法那样，对个体粒子使 用进化算子，它将每个个体看作是n 维空间中的一个的粒子，每个粒子在搜索空间都 有自己的位置，并且有一个由优化问题决定的适应度函数，来评价粒子离“食物源 的远近。粒子可以按照一定的速度飞行，通过跟踪两个极值来调整自身的飞行速度， 实现位置更新。这两个极值其中一个是粒子本身曾达到的最优值，就叫个体极值；另 一个是种群目前找到的最优值，叫全局极值。所有粒子通过不断迭代，找到问题的最 优解。 其具体的数学模型为： 假设问题的解是n 维的，则在n 维空问中，设有m 个粒子，每个粒子用向量 x f = g f l ，x 加，l ( f = 1 , 2 ，m ) 式( 2 1 ) 表示其位置坐标；用 k = “i ，2 ，y 加) ，( f = 1 , 2 ，m ) 式( 2 2 ) 表示其飞行速度，第i 个粒子曾达到的个体极值用只= 0 n ，p m ，p 加) 表示，种群目 前找到的全局极值用g = b 。，g ：，g 。) 表示，粒子通过以下公式更新其位置和速度： v o ( ，t + 1 ) 、= v o ( t ) + c , ，r a n d 、( ) g 驴o ) 一p 驴o ) ) + c ：朋刀d ( ) g o ) 一g ，o ”式( 2 3 ) o + 1 ) = o ) + y i f o + 1 ) 一v 叫 其中c 。，c ：为加速因子，r a n d ( ) 是o l 之间的随机函数。每次更新时，速度和位置都设 定一个上限和下限：( v m v m 。) 和似m i x m 戤) 。发生越界情况时，进行如下处理： v 加- ) = 篆z ( 叭t ) - v 。m a x 式( 2 4 ) ( f + 1 ) = 乏x 嘞j ( m t ) ： x k m a x 都- 5 ) 1 0 第二章粒了群优化算法 整个种群按照公式( 2 1 ) 进行迭代，当达到程序设定的最大迭代次数，或粒子 群找到的最优解满足预先设定的精度时，迭代终止。 y s h i 和e b e r h a r t 在原粒子群的基础上，又提出惯性权重w 的概念，让惯性权重 在进化过程中线性调整，以平衡全局和局部搜索能力，其具体形式如下： b o + 1 ) = 彩v 驴o ) + c 。r a 甩d ( ) b i ( t ) - p o ) ) + c 2 - r a 以d ( ) b o ) 一g ( f ” 斗，n z q + 1 j = x 驴【f j + 1 ，盯q + 1 ) 该公式后来被称为标准粒子群优化算法。当w = l 时，公式( 2 6 ) 实际就变成公式 ( 2 3 ) ，这也表明带惯性权重的粒子群优化算法，其实就是基本粒子群优化算法的扩展。 从公式( 2 3 ) 、( 2 6 ) 中可以看出，粒子主要通过三部分来更新当前的速度：前一时 刻的速度k ( f ) ；当前位置与自己最优位置的距离( x ，o ) 一只o ) ) ；当前位置与种群最优 位置之间的距离( x ，( f ) 一g ( 咖。 粒子位置更新趋势如图2 1 所示： 置o ) 图2 - 1 标准粒子群中粒子飞行趋势图 f i g 2 - 1p a r t i c l ef l y i n gt e n d e n c y i np s o 式( 2 3 ) 、( 2 6 ) 中的第一部分称为动量部分，表示粒子对自身前一时刻速度的继承， 它为粒子当前速度的获得提供了一个原始动量，让粒子跟据自身速度进行惯性运动； 第二部分称为个体认知，代表粒子自身的思考行为，通过对自身最优位置的记忆，让 粒子自动向个体最优位置飞翔；第三部分称为社会认知，表示种群间的信息共享，通 过社会学习行为，粒子飞向种群中的最优位置。第一部分对应多样化的特点，第二、 第三部分对应于搜索过程的集中化，这三部分之间的相互平衡决定了算法的主要性 能。 北京化t 大学硕上学位论文 2 2 2 参数设置 p s o 算法的参数主要有：种群的规模，粒子的维数，粒子坐标的变化范围，粒子飞 行的最大速度，惯性权重，加速因子，最小误差和最大迭代次数。 种群规模：通常情况下，将粒子个数设定为3 0 一5 0 个即可，但也根据问题的具体 情况而定，当优化目标为比较复杂的多峰值函数时，粒子数可以取1 0 0 5 0 0 不等。 粒子维数：由优化目标函数而定，函数解的长度即为粒子的维数。 坐标范围：对粒子的每一维，都可以根据具体问题设置不同的范围，但对多数函 数而言，设置一个统一的范围即可。 最大速度：速度的大小决定粒子位置改变的幅度，通常将位置变化的最大值设定 为最大速度值。 惯性权重：惯性权重w 对p s o 算法的收敛性有很大作用。通过调整惯性权重的大 小，可以控制以前速度对当前速度的影响，调节全局搜索能力和局部搜索能力。当惯 性权重较大时，当前速度受之前速度的影响较大，粒子发生较大位移，增加了粒子的 全局搜索能力，有利于粒子发现新的解；当惯性权重较小时，当前速度受之前速度的 影响较小，粒子的活动范围较小，有利于在当前空间里寻找极值解。通常惯性权重按 如下线性变化递减： 国：国。一( ) m _ a x 一- - ( ) m i n i t e ，式( 2 7 ) l t e r = a x 式中国。为最大惯性权重，缈m i n 为最小惯性权重，i t e r = 戤为最大迭代次数，i t e r 为当 前迭代次数。在开始迭代时，让w 取最大值，随着迭代次数的增大而线性减小，直到 取到最小惯性权重值，因为刚开始优化时，粒子都是随机生成，解空间比较大，需要 加强全局搜索能力；在优化后期，解空间缩小到较小的范围，应让算法具有较强的局 部搜索能力，以进行精细搜索，尽快找到最优值。实验表明，当w 的取值在 0 ，1 4 范围内变化时，可以取到较好的效果【5 剐。 加速因子：粒子自身的经验与群体经验在粒子速度变化中所起到的作用大小，用 加速因子表示。速度更新公式( 2 3 ) 、( 2 6 ) 中，除第一部分是继承上一次飞行速度的大 小之外，剩下两部分都称为学习部分。其中，第二部分是粒子本身的认知行为，它可 以知道当f j i 位置与自己曾达到的最优位置之间的距离，是粒子的动作变化中来源于自 己经验的部分；第三部分是粒子的社会行为，通过它粒子可以知道与种群中最优位置 的差距，是粒子速度改变中来源于社会学习的部分，这两部分经验的选取比重，就通 过加速因子调控。通常加速因子都取常数2 。 终止条件：算法通过达到最大迭代次数或误差要求而终止，而具体的最大迭代次 数和最小误差值都由具体问题决定。 1 2 第二章粒了群优化算法 2 2 3 算法步骤 标准p s o 算法步骤为： 1 初始化。初始化一个规模为m 的粒子群，每个粒子的维数设为n ，随机生成每 个粒子的初始位置和速度向量，把个体最优位置初始化为粒子的初始状态，把全局最 优位置初始化为第一个粒子的初始状态。 2 计算粒子适应度值。用适应度函数计算每个粒子的适应度值。 3 寻找个体最优。比较每个粒子的当f j i 适应值与其经历过的个体最优位置的适应 度值，如果当前位置的适应度值优于个体最优位置适应度值，则将当前的位置赋值给 个体最优位置。 4 寻找全局最优。比较当前种群中粒子的适应度值和全局最优位置适应度值，如 果当前种群中粒子的适应度值有比全局最有位置适应度值高的，将适应度值最优的粒 子赋值给全局最优。 5 更新粒子。找到个体最优和全局最优后，通过公式( 2 6 ) 更新粒子位置和速度， 完成一次迭代。 6 终止。如果满足终止条件：达到最大迭代次数或最小误差值，则停止迭代，此 时的最优位置即为问题的最优解；否则转到步骤2 。 p s o 算法流程图如下： 北京化_ t 人学硕i ：学位论文 2 2 4 算法分析 n y 一、 ( 输出最优解) 、， 图2 - 2 标准粒子群算法流程图 f i g 2 - 2d i a g r a mo fp s oa l g o r i t h m p s