组合优化问题一直是科学研究领域中的一个重要问题。目前解决组合优化问题的方法可以分为两类。Non-Populationbased方法和Populationbased方法。本文主要讨论属于Populationbased方法的粒子群优化算法(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(BinaryParticleSwarmOptimization)算法。对于SAT问题，问题域是{0，1}n，那么粒子的位置只能是0，1串，而且粒子的速度向量也只能是0或者1，这些都是离散量，所以引入概率的概念，通过轮盘赌的方法来控制粒子的位置以及粒子的飞行速率。由于SAT问题是一种典型的多模式问题，也就是说一个SAT问题一般会有有多个解，正如前文所说，PSO算法并不适合解决多模式问题，所以为了使BPSO能够求解多模式问题，按下面的方式修改BPSO：当BPSO中某个粒子找到一个可满足的时候，把那个粒子从群中隔离，然后随机生成一个粒子替代原来的粒子，然后继续迭代。这个算法的难点在于它的参数选择尤其是轮盘赌中的概率值的选取。通过实验，可以看到该算法处理小规模的SAT问题非常有效，平均每次可以找到1.9个解，这是现有的求解SAT问题得算法所不能做到的。但是应用BPSO求解大规模SAT问题效果还不理想，还有待于进一步研究。 同时本文还讨论了如何使用PSO求解多目标规划问题。与传统的多目标规划算法相比，使用PSO算法不用进行复杂的求导运算，计算量小；而且也不需要按照某一标准组合多个目标，尽管这个标准很可能不满足实际需要；最重要的，使用PSO算法一次可以找到多个Pareto解，让用户自己选择适当的解。本文综述了目前几种比较著名的使用PSO解决多目标规划问题的算法，比如6.3中介绍使用交配池的MOPSO算法，6.4种介绍的动态邻域的MOPSO算法等。但是对于多维多目标规划问题，使用PSO求解还存在一定困难，本文也将它留作开放问题。 总的来说，本文的具体工作在于： 1.全面而具体的讨论了PSO算法的出现以及发展。 2.在PSO算法中引入了局部搜索，在达到足够迭代次数的情况下，一定程度上改善了算法的执行效果。 3.提出了一种BPSO算法，用来处理离散问题，尤其是SAT问题，该算法对于小规模问题十分有效。 4.本文具体的讨论了MOPSO算法，并对处理多维问题提出了一些建议。 本文还对以后的研究领域做了初步的展望，PSO处理离散问题，和处理多维的MO问题仍然有很大的研究潜力。