旅行商问题(Traveling Salesman Problem, TSP)^[1,2]是组合优化中典型的NP难题, TSP有着很高的理论和实际价值, 在过去的几十年中成为智能计算、优化问题等重要算法思想的测试平台, 也被广泛应用于网络路由, 车辆调度, 机器人控制和计算机联网等领域. 其求解方法主要包括两个方向: 完全算法和近似算法^[3]. 前者能保证找到最优解, 但时间复杂度高, 难以满足大规模运算需求, 如分支定界法、分支剪支^[4,5]等. 后者只能找到近似解, 却能在多项式时间内结束, 如最近邻算法以及启发式算法. 如何将各种启发式算法有效结合起来, 成为广大学者关注和研究的热点.

2008年剑桥学者Yang^[6]提出萤火虫算法(Firefly Algorithm, FA), 该算法调整参数少, 收敛速度快, 是一种基于群体搜索的启发式算法. 与2005年印度学者Krishnanand和Ghose提出的萤火虫算法(Glowworn Swarm Optimization, GSO)不同的是: FA算法在位置迭代更新式中加入扰动项 $\alpha (rand - 1/2)$ , 避免算法陷入局部最优. 因此, 本文选择FA进行研究. 2010年Sayadi, Ramezanian 和Ghaffari-Nasab^[7]首次将离散萤火虫算法应用于组合优化中最小化流水调度问题, 实验结果表明该方法寻优精度优于蚁群优化算法, 反映出该算法应用于组合优化问题中的优越性, 至此, 离散萤火虫算法得到广泛关注, 在各个研究领域得到迅速的发展. Jati, Suyanto^[8]于2011年将离散萤火虫算法用于解决TSP问题, 所提出的两种方案都找到了问题的最优解. 然而, 文中只是单一的用萤火虫算法解决旅行商问题, 没有与其他算法相结合. Jati, Manurung, Suyanto ^[9]于2013年提出了基于边缘运动的方案解决TSP问题, 所提方案运算速度快, 保证萤火虫能更接近比它更亮的个体, 但是没能改善所求问题的适应度函数值. 文献[10]将萤火虫算法进行离散化, 提出一种确定性和随机性相结合的方法生成初始种群, 同时采取混合种群迭代更新策略. 仿真结果表明算法能够加速全局收敛, 然而所提算法的平均最优值较FA变化不明显. 因此, 有必要进一步改进萤火虫算法来提高算法的性能.

基于此, 本文在FA算法的基础上, 采用整数编码, 接着对FA算法位置更新部分引入对数递减的惯性权重, 并结合遗传算法中选择、交叉、变异、逆转操作, 来调整随着算法迭代次数增加导致种群多样性下降的缺陷, 提出一种改进的萤火虫算法, 用于求解TSP问题, 并采用标准TSPLIB数据库中的算例和多种群智能优化算法对比仿真验证所提算法的有效性.

1 旅行商问题

TSP是指给定n个城市的地点及每两城市间的距离, 某个旅行商以其中一个城市为起点出发, 访问给定的所有城市且仅访问一次, 再回到城市起点, 求最短路程的巡回方案. 其数学描述为^[11]:

$f({{x}}) = \sum\limits_{i = 1}^{n - 1} {d({x_i},{x_{i + 1}})} + d({x_1},{x_n})$

(1)

其中, $f(x)$ 表示路径长度, $d\left( {i,j} \right)$ 表示城市i到城市j的距离, $x = ({x_1},{x_2}, \cdots ,{x_n})$ 为一个访问的顺序, n表示城市个数, $1,\;2, \cdots ,n$ 表示城市的序号.

2 萤火虫算法 2.1 萤火虫算法

萤火虫算法的基本假设: 萤火虫是发光亮度跟当前的位置有关, 位置越好, 发光亮度越高. 此时它具有更大的吸引度, 从而能吸引其范围内亮度弱的其它萤火虫向其靠近, 而且它们之间的相对亮度与吸引度和距离成反比. 在算法的实现中, 利用问题的目标值来衡量萤火虫位置的好坏, 而用迭代式子模拟萤火虫的搜索飞行移动, 以此构造算法, 逐步向问题的最优解移动, 达到优化目的.

首先建立萤火虫i的绝对亮度 ${I_i}$ 和目标函数 $f(x)$ 之间的联系^[12], 通常以目标函数值代表绝对亮度, 即 ${I_i} = f(x)$ , $x = ({x_{i1}},{x_{i2}}, \cdots ,{x_{id}})$ . 若萤火虫i的绝对亮度大于萤火虫j的绝对亮度, 则萤火虫j被萤火虫i吸引而向i移动. 萤火虫i对萤火虫j的吸引力为 ${\beta _{ij}}$ , 即:

${\beta _{ij}} = {\beta _0}\exp ( - \gamma r_{ij}^2)$

(2)

其中, ${\beta _0}$ 为最大吸引力, $\gamma $ 为光吸收系数, 通常取 ${\beta _0} = 1$ , $\gamma \in \left[ {0.01,\;100} \right]$ ^[10]; ${r_{ij}}$ 为萤火虫i到萤火虫j的笛卡尔距离, 即:

${r_{ij}} = \left\| {{x_i} - {x_j}} \right\| = \sqrt {\sum\limits_{k = 1}^d {{{({x_{ik}} - {x_{jk}})}^2}} } $

(3)

其中, $d$ 为变量的维数; ${x_i}$ 、 ${x_j}$ 为萤火虫i和萤火虫j所处的空间位置.

由于萤火虫j被萤火虫i吸引而向i移动, 则萤火虫j的位置更新公式为:

${x_j}(t + 1) = {x_j}(t) + {\beta _{ij}}({x_i}(t) - {x_j}(t)) + \alpha {\varepsilon _j}$

(4)

其中, t为迭代次数; ${\beta _{ij}}$ 为萤火虫i对萤火虫j的吸引力; $\alpha $ 为常数, 一般可以取[0, 1]内的数; ${\varepsilon _j}$ 是由均匀分布得到的随机数向量.

2.2 萤火虫算法的改进(Improved Firefly Algorithm, IFA)

萤火虫算法中存在容易陷入局部最优, 求解精度不高等问题. 而萤火虫的位置迭代在萤火虫优化过程中占举足轻重的地位, 过大的步长会导致萤火虫移动过程中跳过全局最优值, 搜索精度下降; 过小的步长会增加它的局部寻优能力而无法得到全局最优值, 且影响算法的执行效率. 此外, 种群的多样性大大影响萤火虫寻优的速率和解的效果. 针对以上不足, 这里在算法的位置迭代和种群多样性方面作如下改进:

2.2.1 设计惯性权重 $\omega $ 来保证全局收敛性

下面是常见的惯性权重表示:

(1) Shi和Eberhart提出了惯性权重线性递减策略, 将 $\omega $ 的初始值从0.9随迭代次数增加线性递减为0.4, 调整公式为^[13]:

${\omega _k} = {\omega _{\max }} - \frac{{{\omega _{\max }} - {\omega _{\min }}}}{{ite{r_{\max }}}} \times iter$

(5)

其中, ${\omega _{\max }}$ 、 ${\omega _{\min }}$ 分别为 $\omega $ 的最大值和最小值; $iter$ 和 $ite{r_{\max }}$ 分别表示当前迭代次数和最大迭代次数; ${\omega _k}$ 表示当前迭代权重值.

(2) Baykasoğlu, Ozsoydan^[14]提出一种惯性权重正弦调整的粒子群算法, 该权值的调整使算法开始时, 粒子在附近做局部寻优, 在一定迭代次数后, 相互协作程度加大, 进行全局寻优, 最后让粒子进行局部寻优, 调整方案为:

${\omega _k} = {\omega _{\min }} + ({\omega _{\max }} - {\omega _{\min }})\sin (\pi t/ite{r_{\max }})$

(6)

(3) 文献[15]中提出一种惯性权重线性递减的粒子群算法:

${\omega _k} = {\omega _{\max }} - \alpha \times ({\omega _{\max }} - {\omega _{\min }}){\log _{ite{r_{\max }}}}k$

(7)

其中, $\alpha $ 为对数调整因子, 当 $0 < \alpha < 1$ 时称为压缩因子, 当 $\alpha > 1$ 时称膨胀因子. 图1是 $\alpha = 1$ , $ite{r_{\max }} = 200$ 的线性递减惯性权重、正弦调整惯性权重和对数调整权重策略与迭代次数的关系曲线.

式(5), 式(6), 式(7)引入萤火虫算法的位置更新公式变为 :

${x_j}(t + 1) = \omega (t)*{x_j}(t) + {\beta _{ij}}({x_i}(t) - {x_j}(t)) + \alpha {\varepsilon _j}$

(8)

萤火虫位置迭代过程中, 要求在前期有较高的全局搜索能力, 如果在最优解附近 $\omega $ 值能迅速减小进入局部搜索, 就可以加快收敛速度. 图1可以看出, 惯性权重对数递减策略可以满足要求. 经文献[15]仿真表明, 引入的权重策略增大了种群搜索范围, 使复杂问题的解能够迅速达到全局最优.

2.2.2 基于GA的改进萤火虫算法

为了保持种群多样性, 提高算法的全局搜索能力, 在萤火虫进行位置更新后, 引入遗传算法(Genetic Algorithm, GA)^[16]中的选择、交叉、变异和进化逆转, 对萤火虫个体执行选择、交叉、变异和进化逆转操作.

(1) 选择操作: 从群体中以一定概率选择适应度函数值大的个体, 进行交叉, 变异, 逆转产生新个体.

(2) 交叉操作: 在萤火虫吸引度, 位置, 亮度更新后, 确定交叉操作的父代并随机选取的两个位置进行交叉操作, 当交叉后的萤火虫适应度优于原来的萤火虫时, 萤火虫位置更新, 否则萤火虫位置不变. 交叉采用个体位置互换的方法如下:

$\begin{array}{l}{\text{　　　}}\;{\left[ {9\;\;5\;\;1\;|\;3\;\;7\;\;4\;\;2\;|\;0\;\;8\;\;6} \right]}\xrightarrow{{{\text{交叉}}}}\\{\text{　　　}}\;{\left[ {0\;\;5\;\;4\;|\;6\;\;3\;\;8\;\;7\;|\;2\;\;1\;\;9} \right]}\\{\text{新个体}}\;{\left[ {9\;\;5\;\;1\;|\;6\;\;3\;\;8\;\;7\;|\;0\;\;*\;\;*} \right]}\\{\text{　　　}}\;{\left[ {0\;\;5\;\;*\;|\;3\;\;7\;\;4\;\;2\;|\;*\;\;1\;\;9} \right]}\end{array}$

其中, 带*位置表示同一个体由于维数冲突不确定的数字, 此处采用部分映射进行消除冲突, 即用中间维数对应关系进行映射. 映射结果如下:

新个体 [9　5　1　6　3　8　7　0　4　2]

　　　 [0　5　8　3　7　4　2　6　1　9]

(3) 变异操作: 在萤火虫吸引度, 位置, 亮度更新后, 随机选取变异的2个位置, 进行位置互换, 当变异后萤火虫适应度优于原来的萤火虫时，萤火虫位置更新，否则萤火虫位置不变. 变异采取的个体变换方法如下:

若随机选择的个体位置为第4维和第7维, 变异后得到的个体为:

$\begin{array}{*{20}{c}}{\text{　　　　　}}\;{\left[ {9\;\;5\;\;1\;\;3\;\;7\;\;4\;\;2\;\;0\;\;8\;\;6} \right]}\xrightarrow{{{\text{变异}}}} \\{\text{新个体}}\;{\left[ {9\;\;5\;\;1\;\;2\;\;7\;\;4\;\;3\;\;\;0\;\;8\;\;6} \right]}\end{array} $

(4) 进化逆转操作. 为改善种群的多样性, 在选择、交叉和变异后引进逆转操作. 把进化逆转后适应度高的个体留下来, 适应度低的个体进化无效. 逆转采取的个体位置变换方法如下:

若随机选择的个体位置为第4维到第7维, 逆转后得到的个体为:

$\begin{array}{*{20}{c}}{\text{　　　　　}}\;{\left[ {9\;\;5\;\;1\;\;3\;\;7\;\;4\;\;2\;\;0\;\;8\;\;6} \right]}\xrightarrow{{{\text{逆转}}}} \\{\text{新个体}}\;{\left[ {9\;\;5\;\;1\;\;2\;\;4\;\;7\;\;3\;\;\;0\;\;8\;\;6} \right]}\end{array}$

3 改进的萤火虫算法求解旅行商问题

对包含n个城市的TSP问题, 这里采用整数编码表示萤火虫的位置^[9], 并且设置萤火虫的迭代步长为整数, 以确保有效解决TSP问题. 每个萤火虫的位置对应一条巡回路径, 以最短路为目标函数, 运用IFA对目标函数进行求解, 即以式(1)作为目标函数, 寻找 $f({{x}})$ 的最小值, 对应于路径的长度. 萤火虫的个体位置为一个n维矢量 $x = ({x_{i1}},{x_{i2}}, \cdots ,{x_{in}})$ , 其中 $i = 1,2, \cdots ,M$ 代表种群数目, n代表萤火虫的维数或所要访问的城市个数(min=1, max=n). ${x_{ij}}$ 为萤火虫 $i$ 的第 ${{j}}$ 维元素. 由于每个城市必须遍历且只能遍历一遍, 因此 $x$ 中任意两个元素互不相等. 具体步骤如下:

Step 1. 设定萤火虫群算法的参数值, 种群大小, 光强吸收系数, 迭代总次数nMax等参数.

Step 2. 对萤火虫初始位置进行整数编码, 即用randperm(n)给出种群中每只萤火虫初始位置.

Step 3. 计算萤火虫个体当前的目标函数值, 找出萤火虫当前的最优位置并记录对应的目标函数值.

Step 4. 利用式(7)更新权重, 计算惯性权值.

Step 5. 利用式(8)更新萤火虫位置, 计算位置更新后每个萤火虫的亮度 $f(x)$ .

Step 6. 如2.2进行选择, 交叉, 变异和逆转产生新个体.

Step 7. 进行终止条件判断, 达到预定的最大迭代次数nMax, 则停止计算, 输出最优位置和最优函数值就是TSP的最短路线和最短路径值; 否则重复执行Step 3–Step 6.

4 仿真实验

本文的实验平台是Windows7操作系统, 编程软件为Matlab R2013a. 针对TSPLIB库中的Burma14, Oliver30,ei151和st70四组Benchmark城市坐标数据, 分别用基本FA算法^[6,12], IFA算法, 猴群算法(Monkey Algorithm, MA)^[17], GA算法^[16]和蚁群算法(Ant Colony Optimization, ACO)^[18]做20次实验. 求得实验的最优值, 最差值, 平均值, 最优迭代次数以及偏差率. 表1所示为IFA算法与FA算法、MA算法、GA算法和ACO算法用算例Burma14, Oliver30, ei151 和st70的测试结果, 各算法的偏差率是根据公式(9)计算得到的数据.

${\text{偏差率}} = \frac{{{\text{计算最好结果}} - {\text{已知最优值}}}}{{{\text{已知最优值}}}} \times 100\% $

(9)

图2(a)–图5(a)分别表示各算法对这4组城市数据进行优化时各适应度值的变化趋势, 图2(b)–图5(b)分别表示IFA优化Burma14, Oliver30, ei151和st70问题的最优路径, 从起点至终点表示该算法优化的最短距离.

4.1 参数设置

各算法种群规模M=100, 城市数目n由具体测试数据决定, 总迭代次数 $nMax = 500$ , 其它参数依照相关文献的基本原则设置如下:

BFA和IFA算法的最大加权系数 $\omega_{\max} = 0.9$ , 最小加权系数 $\omega_{\min} = 0.4$ , 常数 $\alpha = 0.2$ , 吸引力 ${\beta _{\min }} = 0.2$ , 光照吸收率为 $\lambda = 1$ .

MA算法中爬步长 $\alpha = 1$ , 爬的迭代次数 $N{{c}} = 10$ , “好动策略”的执行次数 $Nn = 10$ , 视野长度 $b = 1$ , 望的迭代次数 $Nw = 5$ , 跳区间 $[c,d] = [ - 1,1]$ .

GA算法中交叉概率 $P{{c}} = 0.9$ , 变异概率 $P{{m}} = 0.05$ , 代沟 $GGAP = 0.9$ .

ACO中信息素重要程度参数 $\alpha = 1$ , 启发式因子 $\beta = 1$ , 信息挥发素系数 $\gamma = 0.95$ , 信息素增加强度系数 $Q = 100$ .

4.2 实验结果对比

在TSP问题中, 针对Burma14, 从表1可以看出, IFA算法100%能找到最优解, 算法精度高, 迭代次数少, 性能优化效果明显. MA,GA的偏差率都在2%内, 收敛速度较快, 但是迭代过程中波动较明显. ACO算法的偏差率较高, 所需迭代次数少. 从图2可以看出, IFA的收敛速度和收敛精度比其他4种优化算法更优; 针对Oliver30, 由表1可以看出, BFA和MA偏差率较大. GA所得的实验最优值小于已知最优值和TSPLIB路径长度, 故得出的偏差率为负值, 同时, 其最优值和最差值相差较大, 说明算法迭代最优值不稳定. ACO算法迭代次数少, 趋于最优值较平稳. 从图3(b)可以直观的看出巡回路径没有打结, 所去城市不重不漏, 以此可直观验证IFA算法的正确率; 针对ei151, 从表1可以看出, FA的偏差率最大, 随着城市规模的增大, FA的迭代次数和偏差率比较显著. MA, GA, ACO偏差率相对较大, 算法迭代稳定. IFA算法随城市规模的增大, 最优值和偏差率变化不太显著, 说明算法的改进效果较好. 从图4(a)可以看出在迭代进行时, IFA算法以相对较快的速度持续降低, 且快速搜索到了最优解; 针对St70, 由表1可以看出, BFA, MA, GA, ACO的偏差率都显著增加, GA迭代平稳, 收敛速度快. 随城市规模的增大, IFA的最优迭代次数和偏差率没有显著增加, 最优值, 最差值, 平均值相差较小, 可见IFA算法有较好的稳定性和鲁棒性. 从图5(a)可以看出, 当其他算法下降缓慢时, IFA算法以较快的速度, 较高的下降趋势, 有效的搜索到全局最优解.

5 结论

本文针对TSP问题的特点, 对FA算法的离散化和种群多样性进行了改进, 提出了一种改进的萤火虫算法, 并采用该算法解决TSP问题. 仿真结果表明改进的萤火虫算法能有效地解决TSP问题, 保证种群的多样性, 同时算法有较好的收敛速度优于MA, GA. 且IFA算法的最优解明显比GA, ACO更接近全局最优解, 所以说基于改进的萤火虫算法求解旅行商问题是有效的, 并且改进的算法的寻优能力, 稳定性更好, 收敛速度更快.