文件名称：粒子群优化算法及其在SAT问题matlab源码
文件大小：3KB
文件格式：M
更新时间：2016-01-20 06:51:24
粒子群 matlab 算法 优化
组合优化问题一直是科学研究领域中的一个重要问题。目前解决组合优化问题的方法可以分为两类。Non-Population based 方法和Population based 方法。本文主要讨论属于Population based 方法的粒子群优化算法(PSO).粒子群优化算法由Dr.Eberhart 和Dr.Kenney 于1995年提出,它是受到鸟群或者鱼群的社会行为的启发而形成的一种基于种群的随机优化技术。粒子群优化算法属于进化算法，具有进化计算的基本特征。例如这个系统也是最初被初始化成为随机解的集合，然后通过更新后代并用迭代的方式来实现搜索最优解。然而，不同于进化算法的是，粒子群优化算法中的每个粒子都是待求问题的一个可能解，它跟随最优粒子在问题空间中飞行。每个粒子记录它所找到的最好值以及相应的坐标，这个值记做Pbest, 同时每个粒子还记录该群内所有粒子所找到的最好值以及相应的坐标，记做Gbest.。在每一次的迭代中，需要改变每个粒子飞向Pbest,和飞向Gbest的速度，然后还要通过分别乘以为Pbest和Gbest而生成的两个不同的随机数来平衡这种改变。本文在综述了PSO算法及其发展过程的基础上，还提出了一种通过引入局部搜索来提高粒子本身搜索能力的方法。现有的对于PSO的改进，无论是动态邻域的PSO算法还是2.6节所介绍DPSO，都强调加强粒子之间的信息共享，或者说是加强群的搜索能力，但是，人们并没有对粒子本身的搜索能力给以足够的重视。如果能够提高粒子本身的搜索能力，使粒子能够发现一定范围的最优解，那么就可以改变粒子的飞行轨迹，从而尽快找到最优解。所以在每次迭代的过程中，让每个粒子以随机步长执行一次局部搜索，这里局部搜索采用最速下降法，并把局部搜索中找到的最好值记做Lbest，然后使粒子在Lbest,Pbest,Gbest的共同作用下更新。其中Lbest的作用放在更新公式的第一部分。实验证明，对于标准的优化函数，当迭代次数为1000时，效果与标准PSO相似，但是当迭代次数达到1500时，该算法解的精度高于标准PSO算法，具有一定的实用价值。因为PSO算法最初被提出用来解决连续域上的优化问题，所以他在离散问题上的应用仍然十分有限。本文中提出了一种处理离散问题的PSO算法，主要针对SAT问题提出了一种BPSO（Binary Particle Swarm Optimization）算法。对于SAT问题，问题域是{0，1}n ,那么粒子的位置只能是0，1串，而且粒子的速度向量也只能是0或者1，这些都是离散量，所以引入概率的概念，通过轮盘赌的方法来控制粒子的位置以及粒子的飞行速率。
由于SAT问题是一种典型的多模式问题，也就是说一个SAT问题一般会有有多个解，正如前文所说，PSO算法并不适合解决多模式问题，所以为了使BPSO能够求解多模式问题，按下面的方式修改BPSO：当BPSO中某个粒子找到一个可满足的时候，把那个粒子从群中隔离，然后随机生成一个粒子替代原来的粒子，然后继续迭代。
这个算法的难点在于它的参数选