粒子群算法实现.doc

《粒子群算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、西南科技大学计算机学院2015----2016学年第1学期硕士研究生课程《智能信息处理》考核报告题目：粒子群优化算法专业：计算机科学与技术学号：xxxxxxxxxxx姓名：xxxx2016年1月粒子群优化算法1.粒子群算法概述：粒子群算法是由Kennedy和Eberhart等于1995年提出的一种基于种群搜索的自适应进化计算技术[1]，算法最初受到鸟群觅食活动规律性的启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间的个体协作实现对问题最优解的搜索。Reynol

2、ds对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。在PSO模型中，每个鸟就是PSO中的粒子，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(FitnessValue)，每个粒子还有一个速度决定他们飞行的方向和距离。粒子根据自身和同伴的飞行经验动态进行调整，也就是说通过跟踪两个位置进行更新，一个是粒子自身找到的最优解

3、pbest,即个体最好位置；另一个是整个种群当前找到的最优解gbest,即全局最好位置。速度和粒子位置的更新公式如下：v[i]=w*v[i]+c1*rand()*(pbest[i]-present[i])+c2*rand()*(gbest-present[i])present[i]=present[i]+v[i]其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值

4、,present[i]代表第i个粒子的当前位置。对于第一个公式，第一部分为微粒先前行为的惯性，第二部分为“认知（cognition）”部分，表示微粒本身的思考；第三部分为“社会（social）”部分，表示微粒间的信息共享与相互合作。“认知”部分可以由Thorndike的效应法则（lawofeffect）所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被激励着去减小误差。“社会”部分可以由Bandura的替代强化（vicar

5、iousreinforcement）所解释。根据该理论的预期，当观察者观察到一个模型在加强某一行为时，将增加它实行该行为的几率，即微粒本身的认知将被其它微粒所模仿。这三个部分之间的相互平衡和制约决定了算法的主要性能。惯性因子w代表粒子上一次的速度对本次飞行速度的影响，它主要用于平衡粒子群的全局搜索能力和局部搜索能力。有研究表明，w对优化性能的影响很大，较大的w值有利于跳出局部极小点，而较小的w值有利于算法收敛[2]。2.粒子群算法的改进途径：目前，学者们对粒子群算法作了各式各样的改进，主要从算法离散化、

6、提高种群多样化、提高收敛速度三个方面进行。2.1算法离散化基于粒子群算法能有效地处理连续优化问题，但在实际工程中存在很多非连续优化类的问题，诸如组合优化问题等。因此，针对离散的优化问题，Kennedy和Eberhart[3]提出了二进制PSO算法，二进制PSO便于表示本身具有二进制特性的问题。一个典型的例子就是它可以用来表示神经网络的连接情况。例如，1可以代表网络上两个节点相连，而0代表网络上两个节点无连接。因而，一个二进制PSO可以用来优化神经网络结构。此外，H.Yoshida[4]还提出了混合编码的

7、粒子群算法，并用其求解电压控制问题。为了将粒子群算法应用于组合优化问题，Clerk[5]提出了有序编码的粒子群算法，并给出了以此种算法解决旅行商问题的具体模型，它的关键在于给出粒子位置和速度的类似定义。2.1提高种群多样化PSO算法作为一种新的随机搜索算法，仍存在着早熟收敛、收敛速度慢两个难题，并且还有诸如种群多样性随代数增加下降过快、有可能不收敛到全局最优解的缺点。为了解决早熟收敛的问题，一些研究者提出了通过控制种群多样性来提高算法性能的方法。一方面通过解决粒子间的冲突和聚集问题[5]、分析粒子和种群

8、最优位置的距离[6]、通过增加环境检测和响应等方法，提出了不同的策略以增加种群多样性，使算法不至于过早陷入局部极小；另一方面，通过引入遗传算法的“变异”操作来增强全局搜索性能也是一种十分有效的方式。Lovbjger[7]提出了一种改善种群多样性的途径一自组织临界点控制,算法对每个粒子增加了当前临界值属性,如果两个粒子间的距离小于预定闽值则增加彼此的临界值,当个体临界值超过系统全局极限值时,则需重新分配其在搜索空间中的位置,以达到控制种群多样