基于粒子群优化算法在NP难问题中的应用研究*

周廷慰

（蚌埠学院）

寻求最优化是人们在科学研究、工程技术和经济管理等领域中经常遇到的问题.优化问题研究的主要内容是在解决某个问题时，如何从众多的解决方案中选出最优化方案.它可以定义为：在一定的约束条件下，求得一组参数值，使得系统的某项性能指标达到最优及最大或最小［1］.传统的优化方法是借助与优化问题的不同性质，通常分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题等［2］.其中，商旅问题（Traveling Salesman Problem，TSP）是NP 困难问题中比较经典的问题之一，同时亦是一个典型的组合优化问题［3］.目前，求解TSP 问题的方法主要包括最近邻与搜索算法、粒子群算法、遗传算法、蚁群算法以及神经网络算法等［4－6］.其中，粒子群优化算法的研究大致集中在以下四个方向：PSO算法的改进、算法的参数设置、算法的收敛性以及工作机制与应用［7］.该文通过比较不同智能优化算法在NP 难问题中的应用研究，分析不同目标个数下最优旅游路径，拓展算法的应用特点，为智能优化算法的推广应用提供理论支撑.

1.1 PSO算法求解旅行商问题

粒子群优化算法（Particle Swarm Optimization，PSO）初始化为一群随机粒子（随机解），然后通过迭代找到最优解.在每一次的迭代中，粒子通过跟踪两个“极值”Pbest，Gbest来更新自己.在找到这两个最优值后，粒子通过公式（1）和（2）来更新自己的速度和位置［8］.

式中，i ＝1，2，…，N，N 是此群中粒子的总数.vi是粒子的速度，rand（）介于（0，1）之间的随机数，xi是粒子的当前位置，c1和c2是学习因子Vmax.算法流程图如图1（a）所示.

图1 求解TSP 算法流程图

基本步骤流程：

（1）初始化

随机生成城市的坐标，用点来画图，点的颜色为蓝色圆圈.通过每个城市的坐标，计算出任意两个城市的旅费，保存在二维数组Distance中.

（2）初始化粒子群

设定加速常数c1、c2，在定义空间R′随机产生n个粒子的初始位置（X1，X2，…，Xn）（其中每个元素Xi表示城市I的优先级，优先级越高，越排在前面）和初始速度（V1，V2，…Vn）形成初始种群Xt和Vt；
最大进化代数Tmax，将当前进化代数设为t ＝1.

（3）评价种群Xt，计算每个粒子的适应度值

粒子适应值的计算fitness ＝Distance［Y1］［Y2］＋Distance［Y2］［Y3］＋…＋Distance［Yn］［Y1］.（其中：Y ＝（Y1，Y2，Y3，…，Yn）表示将粒子坐标X ＝（X1，X2，…，Xn）通过优先级的比较转换为它所代表的城市路线Y ＝（Y1，Y2，Y3，…，Yn），则粒子适应值fitness 即是计算最小旅费的函数）.通过比较每个粒子的最好位置Pbest的适应度值与群体的最好位置Gbest的适应度值；
根据式（2）更新粒子的位移方向和步长，产生新种群Xt＋1直至达到最大迭代次数或最优位置，否则转步骤（3）.

协同粒子群优化算法（C－PSO）在PSO算法的基础上，引入了协同进化与策略与进化的思想，将个体与种群相互联系，用局部学习策略降低局部极值出现的概率［9］.如图1（b）所示，C－PSO算法在初始化、适应度值计算和信息素更新保留了PSO算法的模式，增加了种群中个体精英保留策略，根据个体适应度值大小保留精英，剩余部分进行进化操作；
将进化后的新个体与保留精英形成新的种群，从而达到最优个体与不同种群构成问题完整解的目的，实现种群信息的协同进化.

1.2 GA算法求解旅行商问题

遗传算法（Genetic Algarthm，GA）是模拟达尔文生物进化论的自然选择与遗传的计算模型，通过自然进化过程寻找城市间的最优距离［10］，如图1（c）所示.GA算法的具体步骤如下.

（1）初始化

初始化城市序列的坐标，设置种群规模k 与变异概率（一般取0.01）以及迭代步数等参数（n ＝1000）.

（2）适应度计算

用欧式距离计算城市序列中每个个体的适应度.

（3）交叉／变异与更新

通过轮盘赌策略根据适应度来选择个体作为交叉操作的父体，并确定是否对个体进行变异，如果需要进行变异，侧随机选择个体的两个城市进行交换.最终选择适应度最好的20 个个体直接保留到下一代.

（4）判断是否终止

根据设定迭代次数进行判断是否达到最大迭代次数，如果没有转到第2 步，反之则输出适应度最好的个体.

1.3 ACO算法求解旅行商问题

蚁群算法（Ant Cologn Optimization，ACO）是一种基于种群寻优的启发式搜索算法，通过个体间的信息传递与搜索完成最短路径的寻优过程［11］.其求解旅行问题的步骤如下.

（1）初始化

如图1（d）所示，首先进行各参数初始化，包括蚂蚁数量m，信息素因子α，启发函数因子β，信息会发因子ρ和最大迭代次数等.

（2）构建解空间

对数量为k（k ＝1，2，3，…，m）个蚂蚁进行初始位置随机化处理，计算各个蚂蚁转移至下一个待访问城市的概率，计算公式如式（3）：

式中，i和j为初始点与终点；
ηij（t）为启发函数；
τij（t）为时间t时刻，R为访问过的节点的集合.

（3）更新信息素

计算蚂蚁所经过的路程旅游费用，记录最优旅游费用，并更新各个城市的信息素.

（4）判断是否终止

判断抵达次数是否大于最大迭代次数，如果是小于则再次进行构建解空间，反之则输入最优解.

2.1 数据来源与参数设置

该文以美国地图为边界，采用随机数据来最大化模拟实际情况，即初始城市的坐标数据（x，y）为随机数.实验共设置了5、10、15、20、30 和100个随机城市坐标点，求解一条经过各城市且一次的旅行最低费用的路线.分别采用PSO 算法、C－PSO 算法、GA 算法和ACO 算法进行求解，运行100 次实验，比较四种算法的鲁棒性与实效性.实验工作平台：操作系统Windows 7，CPU为i7 4770，3.4GHz，RAM为8.0GB，Matlab R2016a.PSO和C－PSO算法中的惯性权重因子公共场所ω ＝0.7298，加速系数C1＝C2＝1.4962；
GA算法中的交叉概率和选择概率均为0.3，变异概率为0.01；
ACO算法中的，信息素因子α ＝2，启发函数因子β ＝1，信息素挥发因子ρ ＝0.2，最大迭代次数均为1000.

2.2 鲁棒性分析结果

如图2 所示，为不同问题规模下最短路径图.5个城市的最短路径为［4，1，5，2，3］；
10个城市的最短路径为［7，5，8，1，6，3，9，2，4，10］；
15个城市的最短路径为［7，4，13，10，11，12，5，3，15，6，2，8，1，9，14］；
20个城市的最短路径为［1，2，5，6，8，9，19，20，16，18，3，13，17，12，7，4，10，11，14，15］；
30个城市的最短路径为［9，10，11，25，29，22，19，24，15，8，17，2，27，26，14，28，7，1，3，4，5，6，12，13，16，18，20，21，23，30］；
100个城市的最短路径为［8，10，27，36，38，41，43，44，48，58，68，75，81，83，89，96，97，98，100，85，37，92，40，72，32，5，13，65，87，26，52，45，6，34，70，49，63，69，51，95，21，64，24，25，22，55，74，53，91，46，56，60，50，99，23，93，84，9，14，90，3，7，67，35，80，1，61，78，16，62，29，4，28，77，39，66，11，82，86，31，19，2，79，18，47，12，15，17，20，30，33，42，54，57，59，71，73，76，88，94］.利用回路排重算法统计四种算法在运行100 次后，在不同问题规模下最短路径出现比例，即准确率，结果见表1.

表1 不同问题规模下最短路径的准确率

图2 不同问题规模下最短路径

从表1可以看出，PSO算法的平均准确率为68.87%，PSO算法的平均准确率为69.84%，PSO算法的平均准确率为64.81%，PSO 算法的平均准确率为56.88%.随着城市个数的增大，各算法的准确率逐渐降低.其中，PSO 算法和C－PSO算法的准确率的变化较为平缓，说明算法的鲁棒性较好.而GA算法和ACO算法的准确率随城市个数变化较明显.当城市个数为100 时，ACO 算法的准确率仅有30.52%.此外，基本PSO算法存在误差，城市个数10个时路线基本不交叉，城市个数15个以上时路线出现交叉，其原因是PSO算法找不到最优时会陷入局部极值.而C－PSO算法将基本的粒子群算法和协同局部搜索相结合，可以抑制基本的粒子群算法过早陷入局部最优解，并能保持较高的收敛速度，同时对粒子迭代过程中的路径进行优化，提高算法的求解质量和效率.

2.3 运行速度分析结果

为了比较不同算法在TSP 问题求解过程中运行速度的情况，剖析问题规模大小与各算法运行时间的关系.通过测定同一问题规模下不同算法的运行时间（判断标准：算法开始运行到第一次收敛到最小值所需要的时间），分析在不同用时下的最佳算法.该文选择问题规模（城市个数）分别为5、10、15、20、30和100，最大迭代次数为1000，结果如图3所示.

图3 不同城市规模的运行时间

从图3可以看出，随着问题规模（城市个数）的增加四种算法的运行时间总体呈增大趋势.当城市个数小于15时，ACO算法的运行时间比GA算法的运行时间短；
当城市个数大于15 时，ACO算法的运行时间比GA 算法的运行时间长，而PSO算法在不同城市个数下的运行时间均是最短的.四种算法在测试中的总平均运行时间分别为1.166 s（PSO）、1.131 s（C－PSO）、2.717 s（GA）和1.516 s（ACO）.当城市个数为100时，PSO算法、GA算法和ACO算法的运行时间分别为4.367、4.107、5.625和12.746 s.综上所述，在问题规模小时，可以采用PSO算法和ACO算法；
在问题规模大时，可以采用C－PSO算法.

该文主要以求解NP 难问题中的典型－TSP问题为研究内容，对比了粒子群算法、协同粒子群算法、遗传算法和蚁群算法的鲁棒性与时效性.实验结果表明，通过多次迭代能够找到哈密尔顿回路及最优旅游路线，协同粒子群算法在解决规模较大的TSP 问题时，与其它算法相比具有更强的搜索能力和效率.随着城市个数的增大，各算法的准确率逐渐降低，运行时间延长.其中，PSO算法和C－PSO算法的准确率的变化较为平缓，说明算法的鲁棒性较好.而GA 算法和ACO算法的准确率随城市个数变化较明显.

推荐访问:粒子 算法 优化