论文部分内容阅读
摘 要：平面选址问题是运筹学中的一个经典优化问题，是最重要的长期决策之一，在实际生活中有广泛的应用。用传统的最速下降法求解平面选址问题虽然设计简单，计算工作量小，但容易陷入局部最优，并且对不等式的处理比较困难；而粒子群算法具有易克服局部最优、收敛速度快、设置参数少和容易处理约束等优点，因此本文将粒子群算法与传统的最速下降算法融合，提出最速下降粒子群融合优化算法并将其运用于求解无约束的平面选址问题，实现算法全局优化和局部优化的平衡。最后通过具体实验与现有求解方法进行比较，验证了算法的可行性和有效性。
关键词：最优化计算；平面选址问题；最速下降法；粒子群；最速下降粒子群融合算法
1 引言
平面选址问题是运筹学中的一个经典优化问题。作为最重要的长期决策之一，平面选址的好坏直接影响着企业的生产成本、人民生活的便利度、产品的性价比等。因此，平面选址问题的研究有着重大现实意义。平面选址问题自提出以来，已经受到许多研究者的关注并提出了多种求解算法，这些方法为选址问题的求解提供了解决办法，但从实验结果来看这些方法的优化精度不高、求解效率较慢。而选址问题本身是一种较难的优化问题，探寻新的求解算法颇为重要。
粒子群优化算法PSO （Particle Swarm Optimization）作为一种经典的随机搜索优化算法，从多个初始点开始进行搜索的，较容易克服局部最优问题。此外，在PSO 中，可通过对粒子的移动区域和速度进行限制来满足优化问题中的各类约束。本文将粒子群算法与传统的最速下降算法进行融合，提出最速下降粒子群融合算法SDPSO（Steepest Descent Particle Swarm Optimization）并将其运用到求解平面选址问题中，取得了良好的效果。
2 平面选址问题数学模型
本文研究的是最常见的极小极大选址问题。其一般形式化描述为：在平面上给定n个位置点Pi（xi，yi），现要确定选址位置点P（x，y），使点P（x，y）到平面上n个点的距离之和最小。这类问题还没有通用的好方法。目前，求解平面选址问题的智能优化算法有模拟退火算法、蚁群算法、蜂群算法等。
3 最速下降法
最速下降法SDM（steepest descent method ）求解无约束优化问题minf（x）的基本思想是从当前点xk出发，取函数f（x）在点xk处的负梯度方向dk = - ▽ f（xk），即最速下降方向，得到点列{xk}满足条件f（x（k+1）） 作为无约束最优化中最经典的方法之一。最速下降法具有结构简单、计算量小、存储量小、对初始点没有特殊要求等优点，特别适合于低维空间的无约束最优化问题求解。
4 粒子群优化算法
粒子群优化算法是1995 年提出的一种基于群智能的随机优化算法。它把每个个体看作是一个D维搜索空间中的没有质量，没有体积的粒子，其中第i个粒子可以表示为Xi，所有这些粒子都有一个由目标函数确定的适应值， 每个粒子还有飞行方向和距离。每个粒子的速度也是一个D 维的向量， 记为vi。第i个粒子经过的最好的位置记为Pi，也称为pbest。整个群体搜索到的最优位置为pg。对每一次迭代粒子i（1≤i≤n）的第d维（1≤d≤D）更新自己的速度和位置，直到找到最优解。
5 最速下降粒子群融合算法求解平面选址问题
5.1 最速下降粒子群融合算法设计
为了克服粒子群优化算法的精度低， 后期收敛速度慢的缺点，本文将粒子群算法和最速下降法有机地结合起来， 构造出最速下降粒子群融合算法， 该算法继承了粒子群算法的全局收敛性与最速下降法的快速收敛性以及精度高等特点，提高了优化的速度和效果。
最速下降粒子群融合算法的基本思想是先通过粒子群算法初始化种群个体的位置及速度，计算每个个体的适应值并求出整个种群的最好点pg，再利用最速下降法对pg进行搜索得到pg′，然后继续用粒子群算法更新种群个体的速度和位置，产生下一代种群继续上述过程，直到达到最大迭代次数。
最速下降粒子群融合算法的基本流程如下：
Step 1 初始化种群， 设置各参数
Step 2 用粒子群算法更新种群，并求得每个粒子的历史最好点pbest以及整个种群的最好点pg
Step 3 以pg为初始点用最速下降法进行搜索，用得到的点代替pg
Step 4 根据粒子群算法來更新速度
Step 5 xid=xid+vid，返回Step 2，继续迭代，直到达到迭代次数
5.2 最速下降粒子群融合算法的性能
为了证明设计的最速下降粒子群融合算法的可行性，选取文献2中的一个算例，运用融合前的粒子群算法、最速下降法和融合后的最速下降粒子群融合算法分别求解，并将计算的结果进行比较。最后的结果数据为：最速下降法、粒子群算法求得的最优解分别为92.9855、92.9857，达到最优解的迭代次数分别为5次、60次。而SDPSO算法求得的最优解为92.9855，达到最优解的迭代次数为3次。
通过数据可以看出，改进后的SDPSO算法收敛的速度明显优于粒子群算法和最速下降法可以有效减少迭代次数提高优化效率，并且能找到比粒子群算法更优的目标值；而在求得同样最优解的情况下，改进后的算法达到最优解的迭代次数又少于最速下降法。因此证明本文对粒子群算法和最速下降法的融合可以有效减少迭代次数，优化求解结果。
6 实验分析
为了验证SDPSO算法的有效性，进行了实验对算法进行验证。实验在PC 机系列的Win8 环境下运行 Matlab R2013a 编程环境进行。实验平台如下： 计算机硬件资源，CPU 为 Core i5，内存为4GB。在实验中选取文献2中的算例进行求解，并将本文的计算结果和文献2、3、4中的模拟退火算法、蚁群优化算法和蜂群算法的求解性能进行比较。各算法求解的最好结果数据如表1所示。
从数据中发现，与传统的智能优化算法相比，本文提出的SDPSO算法，在求解平面选址问题上能发现更优的目标值，对求解无约束的平面选址问题的有效的。
7 结论
本文通过对粒子群算法的最速下降法的优缺点进行比较分析，设计出了最速下降粒子群融合算法SDPSO，并给出了采用SDPSO算法求解一般无约束平面选址问题的算法描述，再针对具体的实例进行了验算，计算结果表明利用本文提出的SDPSO算法求解无约束的平面选址问题是可行的。实际生活中存在许多与平面选址问题相关的优化问题，文中给出的方法为求解这类优化问题提供了一种新的方法，为数值优化提供了一种新的思路和手段。
参考文献：
[1] 袁亚湘， 孙文瑜.最优化理论与方法.科学出版社，1997.
[2] 马良.多目标平面选址问题的模拟退火算法. 系统工程理论与实践，1997，17（3）.
[3] 邱模杰， 马良.约束平面选址问题的蚂蚁算法. 上海理工大学学报，2000（22）.
[4] 樊小毛，马良.约束平面选址问题的蜂群优化算法.上海理工大学学报，2010（32）.
关键词：最优化计算；平面选址问题；最速下降法；粒子群；最速下降粒子群融合算法
1 引言
平面选址问题是运筹学中的一个经典优化问题。作为最重要的长期决策之一，平面选址的好坏直接影响着企业的生产成本、人民生活的便利度、产品的性价比等。因此，平面选址问题的研究有着重大现实意义。平面选址问题自提出以来，已经受到许多研究者的关注并提出了多种求解算法，这些方法为选址问题的求解提供了解决办法，但从实验结果来看这些方法的优化精度不高、求解效率较慢。而选址问题本身是一种较难的优化问题，探寻新的求解算法颇为重要。
粒子群优化算法PSO （Particle Swarm Optimization）作为一种经典的随机搜索优化算法，从多个初始点开始进行搜索的，较容易克服局部最优问题。此外，在PSO 中，可通过对粒子的移动区域和速度进行限制来满足优化问题中的各类约束。本文将粒子群算法与传统的最速下降算法进行融合，提出最速下降粒子群融合算法SDPSO（Steepest Descent Particle Swarm Optimization）并将其运用到求解平面选址问题中，取得了良好的效果。
2 平面选址问题数学模型
本文研究的是最常见的极小极大选址问题。其一般形式化描述为：在平面上给定n个位置点Pi（xi，yi），现要确定选址位置点P（x，y），使点P（x，y）到平面上n个点的距离之和最小。这类问题还没有通用的好方法。目前，求解平面选址问题的智能优化算法有模拟退火算法、蚁群算法、蜂群算法等。
3 最速下降法
最速下降法SDM（steepest descent method ）求解无约束优化问题minf（x）的基本思想是从当前点xk出发，取函数f（x）在点xk处的负梯度方向dk = - ▽ f（xk），即最速下降方向，得到点列{xk}满足条件f（x（k+1））
4 粒子群优化算法
粒子群优化算法是1995 年提出的一种基于群智能的随机优化算法。它把每个个体看作是一个D维搜索空间中的没有质量，没有体积的粒子，其中第i个粒子可以表示为Xi，所有这些粒子都有一个由目标函数确定的适应值， 每个粒子还有飞行方向和距离。每个粒子的速度也是一个D 维的向量， 记为vi。第i个粒子经过的最好的位置记为Pi，也称为pbest。整个群体搜索到的最优位置为pg。对每一次迭代粒子i（1≤i≤n）的第d维（1≤d≤D）更新自己的速度和位置，直到找到最优解。
5 最速下降粒子群融合算法求解平面选址问题
5.1 最速下降粒子群融合算法设计
为了克服粒子群优化算法的精度低， 后期收敛速度慢的缺点，本文将粒子群算法和最速下降法有机地结合起来， 构造出最速下降粒子群融合算法， 该算法继承了粒子群算法的全局收敛性与最速下降法的快速收敛性以及精度高等特点，提高了优化的速度和效果。
最速下降粒子群融合算法的基本思想是先通过粒子群算法初始化种群个体的位置及速度，计算每个个体的适应值并求出整个种群的最好点pg，再利用最速下降法对pg进行搜索得到pg′，然后继续用粒子群算法更新种群个体的速度和位置，产生下一代种群继续上述过程，直到达到最大迭代次数。
最速下降粒子群融合算法的基本流程如下：
Step 1 初始化种群， 设置各参数
Step 2 用粒子群算法更新种群，并求得每个粒子的历史最好点pbest以及整个种群的最好点pg
Step 3 以pg为初始点用最速下降法进行搜索，用得到的点代替pg
Step 4 根据粒子群算法來更新速度
Step 5 xid=xid+vid，返回Step 2，继续迭代，直到达到迭代次数
5.2 最速下降粒子群融合算法的性能
为了证明设计的最速下降粒子群融合算法的可行性，选取文献2中的一个算例，运用融合前的粒子群算法、最速下降法和融合后的最速下降粒子群融合算法分别求解，并将计算的结果进行比较。最后的结果数据为：最速下降法、粒子群算法求得的最优解分别为92.9855、92.9857，达到最优解的迭代次数分别为5次、60次。而SDPSO算法求得的最优解为92.9855，达到最优解的迭代次数为3次。
通过数据可以看出，改进后的SDPSO算法收敛的速度明显优于粒子群算法和最速下降法可以有效减少迭代次数提高优化效率，并且能找到比粒子群算法更优的目标值；而在求得同样最优解的情况下，改进后的算法达到最优解的迭代次数又少于最速下降法。因此证明本文对粒子群算法和最速下降法的融合可以有效减少迭代次数，优化求解结果。
6 实验分析
为了验证SDPSO算法的有效性，进行了实验对算法进行验证。实验在PC 机系列的Win8 环境下运行 Matlab R2013a 编程环境进行。实验平台如下： 计算机硬件资源，CPU 为 Core i5，内存为4GB。在实验中选取文献2中的算例进行求解，并将本文的计算结果和文献2、3、4中的模拟退火算法、蚁群优化算法和蜂群算法的求解性能进行比较。各算法求解的最好结果数据如表1所示。
从数据中发现，与传统的智能优化算法相比，本文提出的SDPSO算法，在求解平面选址问题上能发现更优的目标值，对求解无约束的平面选址问题的有效的。
7 结论
本文通过对粒子群算法的最速下降法的优缺点进行比较分析，设计出了最速下降粒子群融合算法SDPSO，并给出了采用SDPSO算法求解一般无约束平面选址问题的算法描述，再针对具体的实例进行了验算，计算结果表明利用本文提出的SDPSO算法求解无约束的平面选址问题是可行的。实际生活中存在许多与平面选址问题相关的优化问题，文中给出的方法为求解这类优化问题提供了一种新的方法，为数值优化提供了一种新的思路和手段。
参考文献：
[1] 袁亚湘， 孙文瑜.最优化理论与方法.科学出版社，1997.
[2] 马良.多目标平面选址问题的模拟退火算法. 系统工程理论与实践，1997，17（3）.
[3] 邱模杰， 马良.约束平面选址问题的蚂蚁算法. 上海理工大学学报，2000（22）.
[4] 樊小毛，马良.约束平面选址问题的蜂群优化算法.上海理工大学学报，2010（32）.