c平台下的粒子群算法程序设计与优化分析【字数：11826】
摘 要作为一种新型仿生算法，粒子群算法一经面世就受到了国内外很多学者的关注。粒子群算法具有易理解、参数少、易实现、收敛速度快等特点，所以其应用领域非常广泛，例如神经网络训练、聚类分析及信息共享优化等领域。同时也因为其发现较晚，研究尚处于初期，其理论研究及工程应用需要不断充实。因此以粒子群算法为主要研究对象进而求解实际问题是很有意义的。本文首先对课题研究的目的和意义进行了介绍；并讨论国内外对粒子群算法研究、发展的趋势以及本课题研究的内容与方案；然后通过简要介绍基本粒子群算法的一些相关知识，引出了混合的粒子群算法以及近些年来学者们广泛关注的改进混合粒子群算法；提出一种新型的基于遗传算法特性的混合粒子群算法，在求解TSP问题中实验并对结果分析。最终得出这种新型的基于遗传算法特性的混合粒子群算法在求解TSPburma14问题具有较好的表现，且测试粒子群算法的迭代次数多少和种群规模大小影响着整体算法性能。
目 录
1.概述 1
1.1课题的目的和意义 1
1.2国内外对粒子群算法研究现状与发展趋势 1
1.3本课题所研究的主要内容 2
1.4小结 3
2.粒子群算法 4
2.1粒子群算法演化模型 4
2.2粒子群算法的数学描述 4
2.3标准粒子群算法的实现步骤 5
2.4粒子群算法的局限性 6
2.5小结 7
3.粒子群算法与遗传算法的比较 8
3.1遗传算法介绍 8
3.2粒子群算法与遗传算法（GA）的比较 9
3.3混合粒子群算法 10
4.基于遗传算法特性的混合粒子群算法 11
4.1主要思想 11
4.2主要流程 12
4.3C平台下的程序模块 12
5.粒子群算法求解旅行商（TSP）问题 16
5.1旅行商（TSP）问题 16
5.2混合粒子群算法求解burma14问题 16
5.3测试迭代次数对算法的影响 18
5.4测试种群规模对算法的影响 20
5.5实例：求解web服务优化组合的顺序路径问题 2 *好棒文|www.hbsrm.com +Q: #351916072#
2
5.5.1算法的步骤 22
5.5.2实验测试 23
6.结论 25
致 谢 26
参考文献 27
附 录 29
1.概述
1.1课题的目的和意义
随着人们对生态世界研究的深入，生物智能算法的研究在近几十年突飞猛进。人们花费数十年时间研究生物种群行为从而提出各种各样的智能算法和理论用来解决一些复杂的工程问题。如模拟达尔文生物进化论演化遗传算法（Genetic Algorithm，GA）、模拟天牛觅食过程演化天牛须搜索算法（Beetle Antennae Search Algorithm，BAS）、模拟种群觅食演化粒子群算法（Particle Swarm Optimization，PSO）等[1]。
20世纪90年代中期研究者Eberhart和Kennedy通过研究动物种群信息的交互性以及信息传递的高效性提出了粒子群算法，即以鸟群搜寻食物的群集行为和信息共享机制为模型。把鸟群体抽象成粒子群，个体视作一单位的粒子，个体速度和空间位置视作属性。
自粒子群算法模型提出以来，其研究取得了很大的进展。因其以动物个体之间信息的单向传递为基础，所以较为同类仿生算法而言具有收敛速度快、易实现、所需属性少等特点。不过又因其从种群群集行为的模型演化，所以受仿生算法本身的限制，目前没有严格的理论基础，不能从原理上解释其有效性及适用范围。虽提高了对特定范围的搜索精度，但容易陷入局部最优。为解决以上问题，国内外学者从各个方面对粒子群算法进行优化研究。本文主要研究混合的粒子群算法以解决该算法在组合优化方向的问题。
1.2国内外对粒子群算法研究现状与发展趋势
粒子群算法作为20世纪末的一种新型算法一经面世就受到学术界的重视。该算法作为仿生算法是以鸟类觅食活动的集群行为及信息共享机制为模型，把鸟抽象成粒子，给予其速度和位置属性，利用各独立粒子信息共享策略寻找个体极值与全局极值。粒子们通过集群行为在求解空间内跟随最优解粒子（极值粒子），并通过迭代找到近似最优解[2]。目前，针对粒子群算法优化的研究方向较多，经对资料的归纳整理可以分为以下几个方面：
1) 粒子群算法的原理研究。即证明粒子群算法对待优化问题的有效性、收敛性及时间对精度影响等问题。Van Den Bergh提出一种方法，以全局最优粒子加以一个新的公式束缚，其他粒子不变来保证粒子群算法的收敛。该算法能够保证局部最优，但在其他指标上不及标准粒子群算法。
2) 粒子群算法的算法结构研究。即通过改进粒子学习对象的选取、更新粒子迭代公式、更新或修改速度、限制位置等方法[3]。Al kazemi提出多阶段粒子群算法，在不同阶段对粒子施行不同的约束策略，粒子可以根据最优粒子选择两个方向移动。Leontitsis则在算法中引入排斥粒子的概念，在获取局部最优和全局最优粒子信息时，同时引用局部最差和全局最差概念，并将该种粒子引入最优位置，从而使粒子群更快进入收敛。
3) 粒子群算法的拓扑结构研究。通过设计拓扑结构来提高算法的性能，大多数方向是研究静态拓扑，也有少部分是关于动态拓扑[4]。其中Xu提出扩展PSO算法，这是一种统一的粒子群算法，它将个体最优粒子、全体最优粒子以及邻域中的局部最优粒子统一起来跟新粒子速度。
4) 粒子群算法的参数选择优化。粒子群因为参数少、易操作和易实现从众多仿生算法脱颖而出。其具体参数有：惯性权重ω、学习因子c1和c2、速度限制Vmax、位置限制Xmax、种群大小和初始种群。学界普遍认为惯性权重对粒子群算法性能有着重大的影响，对此的研究也是比较深入。另外，初始种群也影响着其算法性能。学界开始尝试以智能化初始种群，如Robinson提出以遗传算法优化之后的种群作为初始种群。
5）离散二进制粒子群算法。在调度或者路由的问题中，往往出现离散化或二值化的现象。而基本粒子群算法的公式不能应对离散问题，需要对速度定义和轨迹定义进行变化。Kennedy首先提出这个概念，利用二进制对粒子编码，通过函数限制粒子速度。其也可称其为概率的变化。Mohan在该基础上提出了多种二进制优化方法，如：量子方法、偏差向量方法以及混合方法。
6）多目标优化的粒子群算法。粒子群算法在的信息共享机制与其他仿生算法不同，粒子群算法的粒子信息属于单向共享而非双向共享[5]。所以传统的粒子群算法并不能同时寻到多个最优点。文献中通常使用两种方法:(1)轮盘模式，按照某种标准进行随机选择，从而维持种群的多样性;(2)标准模式:按照某种不涉及随机选择的方式来确定最优点。
关于粒子群算法优化还有很多研究方向，根据各个领域遇到的问题不同优化策略也各有侧重。作为一种智能计算的算法，其具有很大的潜力，算法能够用于多个领域并创造价值，在群智能算法中具有重要的地位，同时也能够在相关产业创造价值，发挥作用。
目 录
1.概述 1
1.1课题的目的和意义 1
1.2国内外对粒子群算法研究现状与发展趋势 1
1.3本课题所研究的主要内容 2
1.4小结 3
2.粒子群算法 4
2.1粒子群算法演化模型 4
2.2粒子群算法的数学描述 4
2.3标准粒子群算法的实现步骤 5
2.4粒子群算法的局限性 6
2.5小结 7
3.粒子群算法与遗传算法的比较 8
3.1遗传算法介绍 8
3.2粒子群算法与遗传算法（GA）的比较 9
3.3混合粒子群算法 10
4.基于遗传算法特性的混合粒子群算法 11
4.1主要思想 11
4.2主要流程 12
4.3C平台下的程序模块 12
5.粒子群算法求解旅行商（TSP）问题 16
5.1旅行商（TSP）问题 16
5.2混合粒子群算法求解burma14问题 16
5.3测试迭代次数对算法的影响 18
5.4测试种群规模对算法的影响 20
5.5实例：求解web服务优化组合的顺序路径问题 2 *好棒文|www.hbsrm.com +Q: #351916072#
2
5.5.1算法的步骤 22
5.5.2实验测试 23
6.结论 25
致 谢 26
参考文献 27
附 录 29
1.概述
1.1课题的目的和意义
随着人们对生态世界研究的深入，生物智能算法的研究在近几十年突飞猛进。人们花费数十年时间研究生物种群行为从而提出各种各样的智能算法和理论用来解决一些复杂的工程问题。如模拟达尔文生物进化论演化遗传算法（Genetic Algorithm，GA）、模拟天牛觅食过程演化天牛须搜索算法（Beetle Antennae Search Algorithm，BAS）、模拟种群觅食演化粒子群算法（Particle Swarm Optimization，PSO）等[1]。
20世纪90年代中期研究者Eberhart和Kennedy通过研究动物种群信息的交互性以及信息传递的高效性提出了粒子群算法，即以鸟群搜寻食物的群集行为和信息共享机制为模型。把鸟群体抽象成粒子群，个体视作一单位的粒子，个体速度和空间位置视作属性。
自粒子群算法模型提出以来，其研究取得了很大的进展。因其以动物个体之间信息的单向传递为基础，所以较为同类仿生算法而言具有收敛速度快、易实现、所需属性少等特点。不过又因其从种群群集行为的模型演化，所以受仿生算法本身的限制，目前没有严格的理论基础，不能从原理上解释其有效性及适用范围。虽提高了对特定范围的搜索精度，但容易陷入局部最优。为解决以上问题，国内外学者从各个方面对粒子群算法进行优化研究。本文主要研究混合的粒子群算法以解决该算法在组合优化方向的问题。
1.2国内外对粒子群算法研究现状与发展趋势
粒子群算法作为20世纪末的一种新型算法一经面世就受到学术界的重视。该算法作为仿生算法是以鸟类觅食活动的集群行为及信息共享机制为模型，把鸟抽象成粒子，给予其速度和位置属性，利用各独立粒子信息共享策略寻找个体极值与全局极值。粒子们通过集群行为在求解空间内跟随最优解粒子（极值粒子），并通过迭代找到近似最优解[2]。目前，针对粒子群算法优化的研究方向较多，经对资料的归纳整理可以分为以下几个方面：
1) 粒子群算法的原理研究。即证明粒子群算法对待优化问题的有效性、收敛性及时间对精度影响等问题。Van Den Bergh提出一种方法，以全局最优粒子加以一个新的公式束缚，其他粒子不变来保证粒子群算法的收敛。该算法能够保证局部最优，但在其他指标上不及标准粒子群算法。
2) 粒子群算法的算法结构研究。即通过改进粒子学习对象的选取、更新粒子迭代公式、更新或修改速度、限制位置等方法[3]。Al kazemi提出多阶段粒子群算法，在不同阶段对粒子施行不同的约束策略，粒子可以根据最优粒子选择两个方向移动。Leontitsis则在算法中引入排斥粒子的概念，在获取局部最优和全局最优粒子信息时，同时引用局部最差和全局最差概念，并将该种粒子引入最优位置，从而使粒子群更快进入收敛。
3) 粒子群算法的拓扑结构研究。通过设计拓扑结构来提高算法的性能，大多数方向是研究静态拓扑，也有少部分是关于动态拓扑[4]。其中Xu提出扩展PSO算法，这是一种统一的粒子群算法，它将个体最优粒子、全体最优粒子以及邻域中的局部最优粒子统一起来跟新粒子速度。
4) 粒子群算法的参数选择优化。粒子群因为参数少、易操作和易实现从众多仿生算法脱颖而出。其具体参数有：惯性权重ω、学习因子c1和c2、速度限制Vmax、位置限制Xmax、种群大小和初始种群。学界普遍认为惯性权重对粒子群算法性能有着重大的影响，对此的研究也是比较深入。另外，初始种群也影响着其算法性能。学界开始尝试以智能化初始种群，如Robinson提出以遗传算法优化之后的种群作为初始种群。
5）离散二进制粒子群算法。在调度或者路由的问题中，往往出现离散化或二值化的现象。而基本粒子群算法的公式不能应对离散问题，需要对速度定义和轨迹定义进行变化。Kennedy首先提出这个概念，利用二进制对粒子编码，通过函数限制粒子速度。其也可称其为概率的变化。Mohan在该基础上提出了多种二进制优化方法，如：量子方法、偏差向量方法以及混合方法。
6）多目标优化的粒子群算法。粒子群算法在的信息共享机制与其他仿生算法不同，粒子群算法的粒子信息属于单向共享而非双向共享[5]。所以传统的粒子群算法并不能同时寻到多个最优点。文献中通常使用两种方法:(1)轮盘模式，按照某种标准进行随机选择，从而维持种群的多样性;(2)标准模式:按照某种不涉及随机选择的方式来确定最优点。
关于粒子群算法优化还有很多研究方向，根据各个领域遇到的问题不同优化策略也各有侧重。作为一种智能计算的算法，其具有很大的潜力，算法能够用于多个领域并创造价值，在群智能算法中具有重要的地位，同时也能够在相关产业创造价值，发挥作用。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/dzxx/dzkxyjs/651.html
