内容发布更新时间 : 2024/5/5 5:48:30星期一 下面是文章的全部内容请认真阅读。

摘要：TSP是一个典型的NPC问题。本文首先介绍旅行商问题和粒子群优化算法的基本概念。然后构造一种基于交换子和交换序[1]概念的粒子群优化算法，通过控制学习因子c1和c2、最大速度Vmax，尝试求解旅行商问题。本文以中国31个省会城市为例，通过MATLAB编程实施对旅行商问题的求解,得到了一定优化程度的路径，是粒子群优化算法在TSP问题中运用的一次大胆尝试。

关键字：TSP问题；粒子群优化算法；MATLAB；中国31个城市TSP。

1

粒子群优化算法求解旅行商问题

1. 引言

1. 旅行商问题的概述

旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题，其描述非常简单，但最优化求解非常困难，若用穷举法搜索，对N个城市需要考虑N！种情况并两两对比，找出最优，其算法复杂性呈指数增长，即所谓“指数爆炸”。所以，寻求和研究TSP问题的有效启发式算法，是问题的关键。 2. 粒子群优化算法的概述

粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能 (Swarm intelligence, SI) 的一种。它可以被纳入多主体优化系统 (Multiagent Optimization System, MAOS). 粒子群优化算法是由Eberhart博士和Kennedy博士发明。

PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。

3. 粒子群优化算法求解旅行商问题

旅行商问题是一个典型的、易于描述却难于处理的组合优化问题,并且是一个NP完全难题,其可能的路径数目与城市数目n是成指数型增长的,对n个城市而言,可能的路径总(n-1)!。随着n的增加,路径数将按数率急剧增长,即所谓的“指数爆炸”,所以一般很难精确地求出其最优解,因而寻找出其有效的近似求解算法就具有重要的理论意义。而粒子群优化算法是解决复杂问题的有效方法,自然也能应用于解决旅行商问题。

PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有

2

的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

2. 粒子群算法的基本思想

1. 粒子群优化算法的基本原理

一个由m个粒子(Particle)组成的群体(Swarm)在D维搜索空间中以一定的速度飞行，每个粒子在搜索时，考虑到了自己搜索到的的历史最好点和群体内(或领域内)其它粒子的最好点，在此基础上进行位置(状态、也就是解)的变化。

第i个粒子的位置表示为：xi?(xi1,xi2,???,xiD)

第i个粒子的速度表示为：vi?(vi1,vi2,???,viD)，1?d?D

第i个粒子所经历的历史最好点表示为1?i?m：pi?(pi1,pi2,???,piD) 群体内(或领域内)所有粒子所经历过的最好的点表示为：

pg?(pg1,pg2,???,pgD)[2]

。

一般来说，粒子的位置和速度都是在连续的实数空间内进行取值，粒子的位置和速度根据如下方程进行变化

k?1kkkkkvid??vid?c1?(pid?xid)?c2?(pgd?xid)

k?1kkxid?xid?vid

其中，?为惯性权重。c1和c2称为学习因子(Learning Factor)或加速系数(Acceleration Coefficient)，一般为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，

从而向自己的历史最优点以及群体内或领域内的历史最优点靠近。c1和c2通常等于2。?，??U[0,1]，是在[0,1]区间内均匀分布的伪随机数。粒子的速度被限制在一个最大Vmax的范围内。

当把群体内所有粒子都作为领域成员时，得到粒子群优化算法的全局版本；当群体内部分成员组成领域时得到粒子群优化算法的局部版本。局部版本中，一般有两种方式组成领域，一种是索引号相邻的粒子组成领域，另一种是位置相邻的粒子组成领域。粒子群优化算法的领域定义策略又可以称为粒子群的领域拓扑结构。[1]

3