计算机论文：面向仿真优化的粒子群算法计算模型

 　　物流系统的建模、基于仿真的优化和物联网应用；李文锋(1966-)，男，湖南人，博士，教授博导，研究方向为物流系统建模和物联网技术。Computation，EC）方法，其基本思想来源于对鸟群简化社会模型的研究及其捕食行为的模拟，它通过群体中粒子间的合作与竞争产生的群集智能指导优化搜索。PSO 吸取了人工生命（Artificial Life，AL）、鸟群觅食（Birds Flocking）、鱼群学习（Fish Schooling）和群理论（Swarm Theory）的思想，通过模拟鸟群和鱼群觅食过程中的迁徙和聚集行为，涌现出良好的搜索寻优能力。它一方面具有深刻的智能背景，另一方面又具备一组显示的数学计算模型，且参数少，操作和实现简单。故 PSO 算法一经提出，立刻引起了计算智能等领域学者们的广泛关注，被应用于众多的科学和工程领域中，并在连续和离散问题域中都取得了较好的性能表现。
　　但 PSO 算法也有其明显的缺陷和不足，一是早熟现象，二是求解精度不高。因此国内外学者通过对简单生物社会系统模型进行改良修正、将 PSO 与物理、数学和生物等其他学科进行交叉研究，或者与其他计算智能（ComputationalIntelligence，CI）方法相融合，来突破 PSO 自身的局限，提高算法总体性能。张顶学在 PSO 种群结构中引入小世界网络模型，使得算法具有动态的种群结构，从而保持了种群的多样性，提高了算法的有效性；高立群等将变异因子融入到 PSO 中，提出了一种带有变异策略的粒子群算法；徐星等把热力学中的扩散现象引入到 PSO 算法的改进当中，提出了基于扩散机制的双种群粒子群优化算法；刘志雄等对PSO 模型中随机数参数的设置问题展开了实验分析，并针对连续函数优化问题和作业车间调度问题的典型测试算例进行了讨论；张玮等研究了粒子在收敛域内的参数取值及对应的运动轨迹，进而应用离散系统分析理论，推导出模值和相角与标准 PSO 算法中的惯性权重和加速因子的关系，从而在理论上确定了 PSO 参数选择的原则。但上述文献都未提出一种系统研究和改良提高 PSO 的方法，于是本文利用基于仿真的优化（Simulation based optimization，SBO）方法来研究和改进 PSO，并重点探讨其搜索模式和参数选取问题，以期为智能算法和复杂系统的研究提供一个统一的体系框架，也为两者的相互借鉴和集成应用做出有益的尝试。
　　人工生命鸟群仿真模型与标准 PSO 算法1.1 群集智能与多智能体系统现代进化论所揭示的进化机制在本质上是一种鲁棒的搜索和优化过程，而进化计算就是一类模拟生物进化过程与机制来求解问题的自适应人工智能技术。群集智能则是一种全新的进化计算方法，它以生物社会系统为依托，利用模仿个体以及个体间相互交互的局部信息产生难以估量的群体涌现（Emergence）行为，从而求解那些难以建立有效的形式化模型而用传统优化方法又难以有效解决甚至无法解决的问题。
　　进化计算的典型代表遗传算法（Genetic Algorithm，GA）是 Holland 教授在复杂自适应系统（Complex AdaptiveSystem，CAS）建模的基础上提出的。显然，自然界中的鸟群就是一个复杂自适应系统，而实际上，复杂自适应系统中的每个个体就是一个智能体（Agent），具有目的性、主动性、适应性以及学习能力等。如果从多智能体系统（Multi-agent System，MAS）的角度出发，把群集智能中的个体看作一个具有局部感知、竞争协作和自学习能力的Agent，就可通过 Agent 与环境以及多 Agent 间的相互作用达到全局优化的目的。因此利用 MAS 对群集智能进行系统的研究和改良，既符合群集智能的原始起源，又能将竞争、协商、协作和博弈的思想、模式和机制更好的融入到智能优化算法中。
　　人工生命及鸟群仿真模型群集智能中的群体指的是一组相互之间可以进行直接通讯或者间接通讯（通过改变局部环境）的 Agent，它们能够合作进行分布式的问题求解，显然群集智能与人工生命有着极其密切的关系。人工生命是对具有自然生命现象和行为特征的人造系统的研究，其概念是美国国立洛斯.阿拉莫斯实验室 C.G.Langton 博士于 1987 年正式提出来的。自组织能 力 和 自 学 习 能 力 是 人 工 生 命 的 两 大 主 要 特 征 。C.G.Langton 认为人工生命模型区别于个体模型有四个方面：(1)人工生命模型由多个描述个体行为的简单程序组成；(2)不存在一个程序起主导作用；(3)每个程序描述个体在局部环境中的交互方式；(4)不存在确定种群整体行为的规则，任何高于个体级的群体行为都是涌现的。同时 C.G.Langton认为人工生命应采取自下而上的方法，从组成系统的自主个体开始，由个体的相互作用，逐步进化、发展，从而实现涌现的复杂行为。另一方面，Agent、智能和交互是基于 Agent 建模和仿真（Agent Based Modeling and Simulation，ABMS）思想中最基本也是最重要的内容。ABMS 是一种由底向上的建模方法，它把 Agent 作为系统的基本抽象单位，采用相关的 Agent技术，先建立组成系统的每个个体（individual）的 Agent模型，然后采用合适的 MAS 体系结构来组装这些个体Agent，最终建立整个系统模型。而这与人工生命的研究方法不谋而合，同时也为将 MAS 和 SI 的集成融合提供了思想方法的统一。
　　人工生命研究的主流之一是探索自然生物是如何以群体的形式生存，并在计算机中重构这种模型，其中较为着名的有 Reynolds 和 Heppner 对鸟群的模拟。Reynolds 通过计算机图形动画仿真了鸟群的复杂群体行为，其形象化地展示了群集涌现行为（源自于简单规则的相互作用）。他们对鸟群的模拟是通过模拟单个飞鸟的行为来实现的，每只飞鸟遵循下面 3 个简单的行为规则：避免碰撞（分离）；速度匹配（队列）；群体集中（聚集）。Heppner 使用了一个相近的鸟群模型，但是他添加了一只"雄鸡"作为一个对鸟群中所有个体的吸引子，主要目的是为了揭示那种使得很多鸟同时聚集的隐规则。上述的工作为 PSO 的诞生提供了直接的思想基础。
　　PSO 的创始人 Kennedy 和 Eberhart 认为其理论基础正是人工生命和进化计算。同时因为数学基础的有限，PSO 受到另外两种思想的影响：Heppner 所认为的鸟群之所以同步是由于鸟和鸟之间保持着最佳距离；Boyd 和 Recharson提出的个体学习和文化传递概念。综合以上四者，Kennedy和 Eberhart 提出 PSO 算法，粒子群中的每一个个体遵循简单的行为，即效法相邻个体的成功经验，而展现出来的累积行为就是搜索一个高维空间的最佳区域。依据前述的人工鸟群仿真模型，人们提出基本的粒子群优化算法。PSO 维持一个一定数量粒子的种群，其中每个粒子都代表了问题的一个潜在解。粒子在多维空间中飞行，它们位置的调整依赖于自身的经验以及周围邻居的经验。基本 PSO 有两个版本，分别是全局最优 PSO（GlobalVersion PSO，GPSO）和局部最优 PSO（Local Version PSO，LPSO），总体上来看，由于局部最优 PSO 具有更大的种群多样性，故相对不容易陷入局部极值，较全局最优 PSO 为优。但为了突出本文所提模型和方法的适用性和实用性，相关模型和仿真均以 GPSO 作为研究对象，以表明合适的算法参数和搜索模式选取能够充分提升 PSO 性能表现，且具有良好的敏捷性和鲁棒性。
　　一切学科都是建模和优化在某个特定领域中的应用。最优化技术从诞生至今，经历了数学规划、智能优化和基于仿真的优化三个发展阶段，其演变的原始推动力一是研究对象、问题模型、目标函数、约束条件和解的评估日益复杂，二是在面对求解问题复杂性的同时，还必须面对现实实践中的不确定性、动态性、强耦合性和开放性。目前所研究和应用的 SBO 是将系统建模仿真与智能搜索优化融为一体的方法。它的基本思想是用下层的仿真模型来模拟复杂系统的运行，并评估其性能；上层优化算法利用解的评价指标，引导算法内部解的搜索过程。仿真模型和优化算法在控制论思想的框架下相互协同工作，使得输出响应不断改进，非枚举地从可能值中找到最佳决策变量值，从而使得系统输出为最优解或满意解。
　　由 SBO 所发展的背景及其基本思想可知，其所主要应用领域和面向系统往往具有如下特点：系统内组成结构多样，关联耦合度高，系统整体无论是从体系结构还是运作机制上，都具有极高的复杂性，人们缺乏相关的必要知识，难以对其进行有效地形式化建模，即使建模也难以从数学上精确求解；系统与所处环境之间有频繁并发的物质、能量和信息交互，同时环境中又存在着大量的动态性、随机性和不确定性事件和活动；系统为了生存与发展，各组成部分间必须通过竞争和协作来完成各自的既定子目标，同时又不得不使得系统整体运作最优。