粒子群算法在组合优化问题上的研究与发展.pdf

《粒子群算法在组合优化问题上的研究与发展.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学术探讨基金项目粒子群算法在组合优化问题上的研究与发展陈永刚牛丹梅范庆辉(河南科技大学电子信息工程学院，河南洛阳471003)[摘要]粒子群优化算法是一种新兴的基于群智能搜索的优化技术。该算法简单、易实现、参数少，具有较强的全局优化能力，可有效应用于科学与工程实践中。介绍了算法的基本原理和算法在组合优化上一些改进方法的主要应用形式。最后，对粒子群算法作了一些深入分析并在此基础上对粒子群算法应用于组合优化问题做了一些总结。[关键词]粒子群算法；组合优化；智能优化算法个体极值，记为Pi。另一个极值是整个种群目前找到的最优1．引言解。这个极值是全局极值，记为Pg。组合

2、优化问题就是在给定的约束条件下，求出使目标设搜索空间为D维，总粒子数为n，第i个粒子表示为函数极小(或极大)的变量组合问题。典型的组合优化问题有Xi＝(xi1，xi2，…，xiD)；第i个粒子的历史最优位置记为Pi＝旅行商问题（TravelingSalesmanProblem－TSP）、加工调度(pi1，pi2，…，piD)；整个群体经历过的最好位置记为Pg＝(pg1，问题、0-1背包问题、装箱问题、聚类问题、指派问题等。它们pg2，…，pgD)；粒子速度记为Vi＝(vi1，vi2，…，viD)。则对于每一均属于NP难问题，它们具有共同的特点：假设问题的规模代，

3、每个粒子的位置根据如下方程变化。为n，问题空间可以归结为由n个自然数的全排列组成的离vid＝w*vid+c1*r1*(pid－xid)+c2*r2*(pgd－xid)(1)散集合。当问题规模较大时，没有合适的算法求精确解。求xid=xid+vid(2)解这类NP问题最好的算法是智能优化算法(如遗传算法、其中C1和C2是非负常数，称为学习因子。r1和r2是介模拟退火、蚁群优化等)。智能优化算法受物理现象或仿生学于[0，1]之间的随机数。w称为惯性因子，w较大适于对解空机理等的启发产生。该类算法一般采用概率或随机搜索策间进行大范围探查，w较小适于进行小范围开挖。每一

4、维粒略，能够在可行时间内以较大概率获得问题的最优解或近子的速度都会被限制在一个最大速度Vmax，如果某一维更新似最优解，从而保证算法在解的质量与计算费用之间获得后的速度超过用户设定的Vmax，那么这一维的速度就被设定较好的平衡。鉴于以上优点，该类算法已经成为NP问题最为Vmax，即vid∈[－Vmax，Vmax]。常用的求解方法之一。PSO算法基本步骤如下：粒子群优化(ParticleSwarmOptimization，PSO)算法最早Step1：随机初始化粒子种群，即初始化种群中所有粒子[1，2]是由Kennedy和Eberhart提出的，其基本原理是源于对鸟

5、的速度和位置(可行解)；群觅食行为的仿真，与蚁群算法类似，PSO算法是一种基于Step2：根据适应度函数对粒子种群进行评价；群智能的方法。PSO算法简单、易于实现，既适合科学研究，Step3：更新粒子的个体极值；又特别适合工程应用。因此，PSO算法一提出，便引起了学Step4：更新粒子的群体极值；者们的关注，并在短短几年内涌现出大量的研究成果。目前Step5：根据式(1)和(2)进行速度和位置的迭代；对PSO算法的研究主要集中在连续空间的PSO算法，即描Step6：重复Step2~Step5，直到满足算法停止迭代的条述粒子状态及其运动规律的量都是连续的。PSO算

6、法在连件。续空间优化领域取得的巨大成功，使许多学者试图用它去3．粒子群算法的一些认识和分析解决组合优化问题，并且已经取得了一些成果。粒子群算法的一些基本概念理解如下。本文的主要工作是介绍近几年PSO在组合优化问题上定义1粒子取得的研究成果。通过分析这些成果，总结PSO应用于组合相当于遗传算法中的染色体，原本代表捕食的鸟的当前优化问题常采用的方法，分析了PSO算法。为以后用PSO位置，对于优化问题则表示一个潜在的可能解。有时候根据求解组合优化问题提供了一些思路和可供参考的方法。采用优化策略、思想和问题等的不同，粒子代表一个不可行2．粒子群优化算法介绍解。所有粒子每

7、次进化不一定都要向好的方向进行。PSO初始化为一群随机粒子（随机解）。然后通过迭代定义2粒子的速度找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来从运动公式(2)可以看出：在函数优化等领域可以理解更新自己。第一个就是粒子本身所找到的最优解。这个叫做为表示同一个粒子t代和t+1代的距离。在组合优化领域主————————————————作者简介：陈永刚，男，河南修武人，硕士，助教，研究方向：智能优化算法。基金项目：河南省基础与前沿技术研究项目，项目编号：072300410210。—41—学术探讨基金项目要作用是调整粒子的某种组合和顺序关系，可以理解为表步骤1：

8、初始化粒子群，即给群体中