论文部分内容阅读
摘要 粒子群算法是通过对鸟群捕食行为进行的观察和研究而提出的一种群智能优化算法，通过群体中个体之间的协作和信息共享来寻找最优解。本文在介绍粒子群算法的基本原理基础上总结了目前主要的粒子群改进方法以及在调度中的应用，为未来的研究和企业调度工作提供了有力的依据。
关键词 调度 群智能 粒子群算法
中图分类号： TM622 文献标识码：A
一、引言
工业生产过程从20世纪80年代后逐渐朝着大型、连续、综合化的方向发展，从而形成了复杂的生产过程，同时也产生了各类急需解决的工程问题，从此，为了提高系统效率、降低生产成本、提高经济效益，各种不同的优化方法开始被提出。
近年来，由于市场竞争的加剧，众多企业都在加快新产品的上市，竭尽所能缩短产品的生产周期，这就要求生产制造企业提高生产效率，追求生产周期的最小化。生产调度，作为生产管理系统的核心内容和关键问题，其目标是资源的最合理配置，同时提高生产效率、降低生产成本，促成各项生产指标最优，从而提高企业的整体竞争力。调度在企业的生产和经营中扮演者如此关键的角色，因此，它已经成为企业在市场中生存的必要条件。
从20世纪初开始，调度开始在制造业中受到重视，各种有关调度的理论、算法、模型和系统相继被提出，对调度的实际工作起了很大的指导作用。调度算法早期主要采用动态规划和整数规划，但这种常规的算法在计算速度、收敛性和初值敏感性等各方面都不能满足复杂的大型计算。
二、群智能算法
群智能算法是人们从生物进化机理和一些物理现象中受到启发提出的许多用以解决复杂问题的新方法，近年来，随着人工智能和人工生命的发展，出现了一些新型的仿生算法，群智能算法主要有蚁群算法、蜂群算法和粒子群算法。各种不同的方法，各有其特长与局限，把不同的方法结合起来，构成一个优势互补、复合协同的综合集成应用系统已成为目前的主流方向。
三、粒子群算法
粒子群算法在1995年由美国的Kennedy和Eberhar提出，最初只是用于对简单的社会系统进行仿真研究和分析，但由于其概念简单、容易实现、搜索速度快、搜索范围大等优越性，在短短几年内获得了很大发展，广泛应用于多个科学和工程领域。
粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。算法源于对鸟群捕食行为的研究，当鸟群在随机搜寻食物时，若某一区域只有一块食物，则找到该食物的最便捷的方法就是搜寻目前离该食物最近的鸟的周围区域。通过对此现象的研究，将要优化问题的解比作空间中的一只鸟，称之为“粒子”，将系统初始化为一群无质量无体积的粒子群（随机解），通过迭代找到最优解。迭代规则根据粒子通过个体极值和全局极值两种经验来进行。
基本的粒子群算法如下：
式中，粒子i的位置为xi=(xi1, xi2,…，xiD)T，速度为vi=(vi1, vi2,…，viD)T。表示粒子i在第k次迭代中第d维的速度；c1，c2表示加速系数，也称学习因子，分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长，在实际应用中应选择合适的加速系数，以加快收敛速度且保证不陷入局部最优。rand1，rand2是rand1,rand2[0,1]之间的随机数；表示粒子i在第k次迭代中第d维的位置；是粒子i在第k次迭代中第d维的个体极值坐标；是群在第k次迭代中第d维的全局极值坐标。
从社会学分析，算法分为三部分，粒子初始速度、粒子自身思考的认知部分、粒子间相互共享和协作的社会部分，模拟了生物惯性的作用、个体认知能力和社会价值取向。这完全符合个体寻找最优办法的过程，既总结自己的经验，同时学习周围环境的优点，进行逐步改善。
四、粒子群算法应用
自从1995年提出粒子群算法以来，工程领域和优化领域就掀起了一股热潮，但由于其研究时间短暂，还没有形成完备的基础理论体系，还有很多未知领域需要探究探索。
粒子群算法最早应用于人工神经网络的训练，之后被推广至函数优化、约束优化、模糊系统控制、机器人路径规划、信号处理、模式识别、TSP、车间调度等工程领域。此外，粒子群算法在多目標优化、自动目标检测、生物信号识别、决策调度、系统辨识以及游戏训练等方面也取得了一定的成果。
五、结论
粒子群算法作为群智能算法的一个分支，具有群智能算法的共同特点，即：鲁棒性强，无集中控制，简单易行，扩展性好，自组织性强，具有潜在的并行性和分布式特点。同时，粒子群算法具有搜索速度快、搜索范围广的特点，优于传统的整数规划、动态规划模型，使之在众多科学和工程领域被研究和应用。但由于粒子群算法的提出建立在对社会模型仿真的基础上，在方法提出的初期并没有严格的数学理论基础，目前正在逐步建立。有关粒子群算法的改进方法也在不断地提出和验证，将粒子群算法与进化算法、神经网络以及其他一些优化技术相结合，以弥补粒子群算法本身的不足，建立特定的粒子群模型将是当前以及未来的研究重点，以更好地解决复杂的调度问题。
（作者：四川大学工商管理学院硕士研究生，研究方向：工业工程）
参考文献：
[1]唐海波，叶春明. 仿生群智能算法在生产调度中的应用综述. 工业工程，2010.6.
[2]边培莹，李德信，包宝军，路燕. 粒子群算法在生产物流调度中的应用研究. 计算机工程与应用，2010，46(17).
关键词 调度 群智能 粒子群算法
中图分类号： TM622 文献标识码：A
一、引言
工业生产过程从20世纪80年代后逐渐朝着大型、连续、综合化的方向发展，从而形成了复杂的生产过程，同时也产生了各类急需解决的工程问题，从此，为了提高系统效率、降低生产成本、提高经济效益，各种不同的优化方法开始被提出。
近年来，由于市场竞争的加剧，众多企业都在加快新产品的上市，竭尽所能缩短产品的生产周期，这就要求生产制造企业提高生产效率，追求生产周期的最小化。生产调度，作为生产管理系统的核心内容和关键问题，其目标是资源的最合理配置，同时提高生产效率、降低生产成本，促成各项生产指标最优，从而提高企业的整体竞争力。调度在企业的生产和经营中扮演者如此关键的角色，因此，它已经成为企业在市场中生存的必要条件。
从20世纪初开始，调度开始在制造业中受到重视，各种有关调度的理论、算法、模型和系统相继被提出，对调度的实际工作起了很大的指导作用。调度算法早期主要采用动态规划和整数规划，但这种常规的算法在计算速度、收敛性和初值敏感性等各方面都不能满足复杂的大型计算。
二、群智能算法
群智能算法是人们从生物进化机理和一些物理现象中受到启发提出的许多用以解决复杂问题的新方法，近年来，随着人工智能和人工生命的发展，出现了一些新型的仿生算法，群智能算法主要有蚁群算法、蜂群算法和粒子群算法。各种不同的方法，各有其特长与局限，把不同的方法结合起来，构成一个优势互补、复合协同的综合集成应用系统已成为目前的主流方向。
三、粒子群算法
粒子群算法在1995年由美国的Kennedy和Eberhar提出，最初只是用于对简单的社会系统进行仿真研究和分析，但由于其概念简单、容易实现、搜索速度快、搜索范围大等优越性，在短短几年内获得了很大发展，广泛应用于多个科学和工程领域。
粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。算法源于对鸟群捕食行为的研究，当鸟群在随机搜寻食物时，若某一区域只有一块食物，则找到该食物的最便捷的方法就是搜寻目前离该食物最近的鸟的周围区域。通过对此现象的研究，将要优化问题的解比作空间中的一只鸟，称之为“粒子”，将系统初始化为一群无质量无体积的粒子群（随机解），通过迭代找到最优解。迭代规则根据粒子通过个体极值和全局极值两种经验来进行。
基本的粒子群算法如下：
式中，粒子i的位置为xi=(xi1, xi2,…，xiD)T，速度为vi=(vi1, vi2,…，viD)T。表示粒子i在第k次迭代中第d维的速度；c1，c2表示加速系数，也称学习因子，分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长，在实际应用中应选择合适的加速系数，以加快收敛速度且保证不陷入局部最优。rand1，rand2是rand1,rand2[0,1]之间的随机数；表示粒子i在第k次迭代中第d维的位置；是粒子i在第k次迭代中第d维的个体极值坐标；是群在第k次迭代中第d维的全局极值坐标。
从社会学分析，算法分为三部分，粒子初始速度、粒子自身思考的认知部分、粒子间相互共享和协作的社会部分，模拟了生物惯性的作用、个体认知能力和社会价值取向。这完全符合个体寻找最优办法的过程，既总结自己的经验，同时学习周围环境的优点，进行逐步改善。
四、粒子群算法应用
自从1995年提出粒子群算法以来，工程领域和优化领域就掀起了一股热潮，但由于其研究时间短暂，还没有形成完备的基础理论体系，还有很多未知领域需要探究探索。
粒子群算法最早应用于人工神经网络的训练，之后被推广至函数优化、约束优化、模糊系统控制、机器人路径规划、信号处理、模式识别、TSP、车间调度等工程领域。此外，粒子群算法在多目標优化、自动目标检测、生物信号识别、决策调度、系统辨识以及游戏训练等方面也取得了一定的成果。
五、结论
粒子群算法作为群智能算法的一个分支，具有群智能算法的共同特点，即：鲁棒性强，无集中控制，简单易行，扩展性好，自组织性强，具有潜在的并行性和分布式特点。同时，粒子群算法具有搜索速度快、搜索范围广的特点，优于传统的整数规划、动态规划模型，使之在众多科学和工程领域被研究和应用。但由于粒子群算法的提出建立在对社会模型仿真的基础上，在方法提出的初期并没有严格的数学理论基础，目前正在逐步建立。有关粒子群算法的改进方法也在不断地提出和验证，将粒子群算法与进化算法、神经网络以及其他一些优化技术相结合，以弥补粒子群算法本身的不足，建立特定的粒子群模型将是当前以及未来的研究重点，以更好地解决复杂的调度问题。
（作者：四川大学工商管理学院硕士研究生，研究方向：工业工程）
参考文献：
[1]唐海波，叶春明. 仿生群智能算法在生产调度中的应用综述. 工业工程，2010.6.
[2]边培莹，李德信，包宝军，路燕. 粒子群算法在生产物流调度中的应用研究. 计算机工程与应用，2010，46(17).