旅行商问题（traveling salesman problem，TSP）是经典的NP-hard问题^[1]. TSP问题有较广泛的应用背景，如物流配送、交通运输、网络通信等；因此，高效解决TSP问题具有很高的应用价值. 许多学者一直致力于研究TSP问题，求解TSP问题的方法大致可以分为2类：精确算法（例如动态规划法^[2]、分支定界法等）以及智能算法^[3-6]（例如猫群算法、萤火虫算法、改进遗传算法、猴群算法等）. 这些智能算法在很大程度上缩小了解空间，能够在有限的时间内增大找到最优解的概率；这些算法有很多缺陷，例如较慢的收敛速度以及易陷入局部最优化. TSP问题虽然提出较早，但至今具有非常大的研究意义.

帝国竞争算法（imperialist competitive algorithm，ICA）是Atashpaz等^[7]提出的模拟人类社会演变过程的启发式算法. ICA的最大优点是收敛速度快，但存在早熟问题^[8]. 近年来，帝国竞争算法被应用到很多领域. 在光电领域中，Fathy等^[9]利用帝国竞争算法以优化光伏系统；Song等^[10]将帝国竞争算法应用到非相干波束合成领域；Mossad等^[11]结合该算法与遗传算法，运用到变压器参数估计领域；在车间调度领域，Zandieh等^[12]将帝国竞争算法用于求解维修状态下的柔性生产调度问题；Karimi等^[13]将帝国竞争算法用于求解具有运输时间约束的柔性车间调度问题. 在人工智能领域中，Sadhu等^[14]将帝国竞争算法用于求解机器人路径优化问题. 在TSP领域中，Hosseini等^[15]在研究ICA时，提出ICA可以用于求解TSP问题；Ardalan等^[16]将ICA用于求解TSP问题，得到较好的优化结果；为了进一步提高ICA的求解质量，张鑫龙等^[17]将自适应算子引入算法中，提高了求解质量，但该算法在求解过程中不能有效地搜索不同的解空间，易陷入局部最优化. 本文利用概率矩阵^[18]，组合成具有竞争优势的人造解，用以提高求解质量；引入反复搜索策略（repeated search strategy，RS）在不同的解空间进行有效的搜索，找出被遗漏的关键信息，避免局部最优化；利用贪婪准则，加快收敛速度及寻找区域最优解.

在组合优化问题中，旅行商问题为经典的最佳化问题. 该问题可以描述如下：假设有n个城市及1个推销员，推销员从其中某个城市出发，拜访各个城市一次，最后回到原来的出发地. 数学模型如下.

目标函数为

(1) $\min Z = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{d_{ij}}{x_{ij}}} } .$

约束条件为

(2) $\sum\limits_{j = 1}^n {{x_{ij}} = 1{\text{;}}\;\;i \in n} {\text{.}}$

(3) $\sum\limits_{i = 1}^n {{x_{ij}} = 1{\text{;}}\;\;j \in n} {\text{.}}$

(4) $\sum\limits_{i \in n} {\sum\limits_{j \in n} {{x_{ij}} \leqslant n - 1} } {\text{.}}$

$ {x_{ij}} = \left\{ {\begin{array}{*{20}{l}} 1{\text{，}}&{\text{若某推销员从城市}}i{\text{到城市}}j{\text{;}}\\ 0{\text{，}}&{\text{其他}}{\text{。}} \end{array}} \right. $

式中： ${d_{ij}}$为从城市i到城市j的距离.

Atashpaz等^[7]根据社会政治现象，提出帝国竞争算法. 该算法的主要步骤如下.

1）随机产生一些国家，根据适应度函数值的大小，选取一些适应度函数值大的国家作为殖民国家，其余国家作为殖民地；根据殖民国家的强弱瓜分殖民地，殖民国家与所属殖民地形成帝国.

2）各个殖民地向所属帝国移动（同化作用）.

3）角色互换，即若殖民地比所属殖民国家强盛，殖民地与所属殖民国家角色互换.

4）帝国竞争，即帝国之间相互竞争. 在帝国竞争过程中，弱小的帝国将被实力较强的帝国瓜分，经过不断的帝国竞争，在理想状态下，最终只会留存一个帝国，其他帝国中的殖民国家及殖民地都会成为该帝国的殖民地.

5）若只剩一个帝国时；停止运算；否则，返回2）.

1）为了提高收敛速度及增加初始解的多样性，利用贪婪准则及随机方式生成初始种群.

2）同化作用的目的是提高求解质量及增大殖民国家对殖民地的影响，本文采用概率矩阵模型用以记录并更新可行解.

3）通过同化及竞争，能够使得适应度函数值较小的帝国被适应度函数值较大的帝国瓜分. 在帝国同化过程中，若是能够保留一些高质量的可行解片段，则可以快速搜索到最佳解；本文引入区块来保留高质量的可行解片段，用以降低求解维度，从而提高搜索速度.

4）为了防止局部最优化，采用反复搜索策略，用以增加可行解多样性及提高求解质量.

具体流程如图1所示.

利用贪婪准则和随机方式产生 $N$个初始国家，为了区分殖民国家和殖民地，从 $N$个国家中选择适应度函数值较高的前 ${N_t}$个国家作为殖民国家，其余国家作为殖民地. 计算每个殖民国家的实力，每个殖民国家的实力与每个殖民国家的距离有关：

(5) ${S_E} = \frac{1}{{{\rm dis}_E}}{\text{.}}$

式中： ${{\rm dis}_E}$为遍历殖民国家E{E=1，2，···，N_t}所有城市的总距离， ${S_E}$为第E个殖民国家的实力.

为了确定每个殖民国家的殖民地数量，通过下式为每个殖民国家分配殖民地数量：

(6) ${w_E} = \frac{{{S_E}}}{{\sum\nolimits_{E = 1}^{{N_t}} {{S_E}} }}{\text{，}}$

(7) ${\rm NW}_E = {\rm round}\left\{ {{w_E} (N - {N_t})} \right\}{\text{.}}$

式中： ${w_E}$为第E个殖民国家在 ${N_t}$个殖民国家中的竞争力，NW_E为第E个殖民国家所分配的殖民地数量.

同化操作是帝国内部相互学习、竞争的过程. 对每个帝国内殖民国家及殖民地的城市编号，利用概率矩阵模型记录每个帝国的同化信息. 利用挖掘区块、区块竞争生成新的同化殖民地，用以完成帝国同化.

以每个帝国为单位，采用概率矩阵记载每个帝国中每个殖民国家及殖民地的城市配送顺序. 根据以下方式更新：

(8) $\left. \begin{array}{l} X_{ij}^k = \left\{ {\begin{array}{*{20}{c}} 1{\text{，}}&{\text{如果城市}}j{\text{紧邻城市}}i{\text{之后}}{\text{；}}\\ 0{\text{，}}&{\text{其他}}{\text{；}} \end{array}} \right.\\ i,j = 1,2,\cdots,n;\;\;k = 1,2,\cdots,m {\text{.}}\end{array} \right\}$

(9) $\left. \begin{array}{l} {C_{ij}}\left( t \right) = {C_{ij}}\left( {t - 1} \right) + \displaystyle\sum\limits_{k = 1}^m {X_{ij}^k}{\text{；}} \\ i,j = 1,2,\cdots,n, \;\;t = 1,2,\cdots,G, \;\;k = 1,2,\cdots,m{\text{.}} \end{array} \right\}$

式中：k为该帝国中殖民国家及殖民地的编号，m为该帝国中殖民国家及殖民地的总数， $C{}_{ij}$为j城市出现在i城市后的次数，t为当前的迭代数，G为总的迭代次数. 假设在该帝国中有1个殖民国家、4个殖民地，其中每个殖民国家及殖民地中各有5个城市，则将帝国中城市之间的先后关系记录到概率矩阵中，如图2所示.

各个帝国在同化过程中，通过同化作用产生高适应度函数值的可行解，从而使得帝国的实力变得更加强大. 在帝国同化的过程中，若能够保留有效的可行解片段，则可以帮助帝国更快得发展壮大. 本文通过构建区块来记录帝国在同化过程中不断出现的可行解片段信息，从而降低求解复杂度，如图3所示. 在母体中共有10个城市，产生的可行解共有10！种排列组合. 若利用构建区块将有效的可行解片段组合，产生的可行解组合降为6！种，则能够大幅度地降低求解复杂度. 本文从区块挖掘及区块竞争2个方面来构建区块.

随机产生符合最小长度的空白区块，设区块的最小长度为3，根据概率矩阵中的相关概率信息，进行区块挖掘. 首先，随机选择一个起始城市，根据最短距离选择下一个城市；然后根据概率，筛选最大概率作为该次所产生的区块，由于随着区块长度的增长，总概率逐渐降低，即错误率逐渐增大. 例如，一个由5个城市{城市1、城市2、城市3、城市4、城市5}组成的区块，概率分别为0.6、0.8、0.6、0.5、0.4，该区块的总概率为0.6×0.8×0.6×0.5×0.4=0.057 6；若该区块由3个城市{城市1，城市2，城市3}组成，则总概率为0.6×0.8×0.6=0.288，因而错误率随着区块长度的增加而增加. 为了保证区块质量，由阈值设置原则^[19]可知，阈值随着迭代次数的增加由0.24增到0.7. 将每代总概率符合阈值的区块保存至区块库中，其他区块按照该方式进行挖掘. 以长度为2的区块为例，具体如图4所示.

当该代挖掘的区块与区块库中的区块出现重复城市时，将该代区块与区块库中的区块进行竞争，并将具有较大竞争优势的区块保留下来，用以生成新的同化殖民地. 主要的竞争方式为与上一代的区块进行位置比较，若出现重复位置，则比较区块的概率并删除概率较小的区块.

新同化殖民地的生成有利于增加帝国的实力，采用组合人造解的方式，生成新的同化殖民地.

1）利用轮盘选择法（roulette wheel selection，RWS），随机产生人造解第一个位置上的城市序号.

2）将该城市序号与区块库中的区块比较，若有以该城市开头的区块，则将该区块复制到人造解中；否则，转3）.

3）以最短距离选择下一个城市，已经被选进人造解的城市不再参与选择.

4）返回2）.

以10个城市为例，如图5所示，此时有3条区块B¹、B²及B³，利用RWS选出City₃，与现有的区块进行对比. 此时有以City₃开头的区块，因此直接将B²的包含的City₁、City₇直接复制到人造解中，由City₇开始按照最短距离选择下一个城市，重复1）~4）直至完成人造解.

在同化过程中，适应度函数值较大的新同化殖民地成为新的殖民国家，原来的殖民国家沦为殖民地.

帝国革命能够在避免无效搜索的同时，增加可行解的多样性及提高可行解的质量. 利用贪婪准则及遗传算法中的插入搜寻算子操作，对同化后的每一条可行解进行变异操作，以提高收敛速度及可行解的多样性. 利用反复搜索策略进行全局性搜索，以增加全局搜寻最优解的机会.

从同化后的可行解中随机挑选2条作为母体；随机产生初始城市，从母体中挑选与该城市相连的城市；从被选中的城市中，选择与该城市最近的城市当作下一个城市，以此类推. 将新可行解的适应度函数值与母体比较，淘汰适应度函数值较小的可行解，具体如图6所示.

为了在加快收敛速度的同时增加可行解的多样性，对母体及运用贪婪算法变异后的可行解随机切成D个片段，选取最长的可行解片段及最短的可行解片段进行插入搜寻算子操作，对可行解片段重组，使得2个可行解片段形成1个可行解片段. 对该可行解片段根据合并概率重组，具体如图7所示.

陷入局部最优，是很多启发式算法面临的问题. 利用反复搜索策略进行全局性搜索，以增加可行解的多样性及提高求解质量. 反复搜索策略分为保留优势解集及改变搜索范围两部分.

设立K指标，令K=10，当母体中的最佳解没有更新时，累加K. 反之，若最佳解更新，则K指标归零重新累计，当K超过阈值时，保留母体的前80%的可行解，其余的20%以随机产生的方式填充，增加可行解的多样性及避免陷入局部最优化. 按照以上步骤更新至下一代，此时清空概率矩阵，改变原来的累计信息范围，搜索母体中不同区域的信息，用以增大全局搜索能力，具体如图8所示. 在迭代后期，若持续搜索母体中的不同区域，则可能会影响求解方向及收敛的质量. 当迭代数达到总迭代数的3%时，将概率矩阵回复到最初的探索范围，使得具有高竞争优势的可行解引领求解方向.

帝国通过竞争能够按照各个帝国的实力重新分配殖民地，帝国的实力包括该帝国殖民国家的实力及该帝国殖民地的实力2个部分. 2个部分对帝国的影响程度不同，因而引入权系数来构建各个帝国的权利函数，具体表示为

(10) ${{\rm TS}_E} = (1 - \xi ){S_E} + \xi \left({{\displaystyle\sum\limits_{k = 1}^{m - 1} {{S_{Ek}}} }} \right)/ \left({{m - 1}}\right){\text{.}}$

式中：TS_E为第E个帝国的实力；m−1为该帝国拥有的殖民地数量；ξ为殖民地对该帝国的影响系数，取0.1；S_Ek为该帝国的第k个殖民地的实力.

在帝国竞争过程中，即使最强的帝国也不一定能够占领最弱的殖民地，每个帝国占有最弱殖民地都有一定的概率，具体如下：

(11) ${\rm NCT}_E = {\rm TS}_E - \mathop {\rm min}\limits_{E \leqslant {\rm NS}} \left\{ {{\rm TC}_E} \right\}{\text{，}}$

(12) ${\rm TP}_E = \frac{{{\rm NCT}_E}}{{\displaystyle\sum\limits_{i = 1}^{\rm NS} {{\rm NCT}_E} }}{\text{.}}$

为了按照各个帝国的占有概率分配最弱帝国中的殖民地，构造如下实力向量：

(13) ${ P} = \left[ {{P_1},{P_2},{P_3},\cdots,{P_{\rm NS}}} \right]{\text{.}}$

建立维数与P向量相同的、由服从均匀分布的随机数r_E（E≤NS）组成的向量R：

(14) $ { R} = \left[ {{r_1},{r_2},{r_3},\cdots,{r_{\rm NS}}} \right]{\text{.}} $

式中：

(15) ${r_E} \sim U\left( {0,\frac{m}{N}} \right){\text{.}}$

为了表示各个帝国占有最弱殖民地的可能性，构建各个帝国可能占有率向量：

(16) ${ D} = { P} - { R} = \left[ {{P_1} - {r_1},{P_2} - {r_2},\cdots,{P_{\rm NS}} - {r_{\rm NS}}} \right]{\text{.}}$

向量D中的最大元素对应的帝国将会占有最弱的殖民国家.

每次迭代时，检查目前最弱帝国包含的殖民地数量，若该帝国没有殖民地，则该帝国灭亡. 随着迭代次数的增加，当只剩一个帝国且达到最大迭代次数时，算法终止.

为了验证混合帝国竞争算法的求解TSP的性能，利用混合帝国竞争算法对TSPLIB中的基准例题集进行测试，与文献[17]、[20]的算法进行比较. 利用Visual Studio2015中的C++，在操作系统为Windows8、处理器的主频为2.71 GHz的Intel（R）Core（TM）i5-6400处理器8 GB内存的电脑上进行仿真测试. 参数设计如下：仿真测试次数为20，初始种群的数量为100，最大的迭代次数为500. 当帝国的数量是国家总数的10%~20%时，ICA的求解质量较好，故帝国数量取15%. 将混合帝国竞争算法（HICA）与文献[20]的遗传算法（GA）进行比较. 由于在文献[17]中，ICA及GA在相同的运行平台下进行相关比较，并在最优值 $C{\rm{^*}}$、平均值 $\overline C $、偏差率 $\psi $及平均运行时间 $\overline t $等指标上，ICA优于GA. 为了保证算法之间对比的公平性，选用与文献[17]相近的计算机环境，并设置相同的参数，对HICA及ICA进行仿真测试. 以ICA为媒介，将HICA与文献[17]的对比算法即文献[20]的GA进行对比，具体的测试结果如表1所示. 表中，C_u为已知最优解.

选用TSPLIB标准案例库中的18个案例进行仿真测试，仿真测试结果如表1所示. 可以看出，在18个标准案中，HICA的平均偏差率为0.11，低于其他算法的平均偏差率；HICA的平均运行时间为25.16，低于其他算法的平均运行时间，这是因为在HICA中引入了区块，在算法迭代过程中，区块具有降维的作用，因而在一定程度上减少了运算时间；除了在第11、12个案例中HICA的最优解小于ICA，在第15个案例中HICA的平均解大于ICA,在第16个案例中HICA的运行时间高于ICA；除此之外，无论在最优解、平均解、偏差率还是运行时间上，HICA皆优于其他算法，表明该算法的整体求解性能优于其他算法.

为了进一步验证该算法的有效性，针对TSPLIB例题，将HICA与布谷鸟算法^[21]（DCS）、猴群算法^[5]（IMA）、离散水循环算法^[22]（DWCA）、离散共生生物搜索算法^[23]（DSOS）、拓展蚁群算法^[24]（ACE）进行比较. 由于文献[5]及文献[21~24]中的算法运行环境不一样，若在相同的初始种群数量及迭代次数下比较，则在比较平均运行时间时会出现一定误差. 该算法在不同规模的种群数量及迭代次数上与其他算法进行横向对比，以保证相对的公平性. 由于DCS^[21]及IMA^[5]、DSOS^[23]的初始种群数量为50、70、80，迭代次数为500；DWCA^[22]及ACE^[24]的初始种群数量均为100，迭代次数为300. 由于在相同的迭代次数下，初始种群数量越少，运行时间越短. 在相同的初始种群数量下，迭代次数越多，则运行时间越长. 设定该算法的初始种群数量为100，迭代次数为500，并与其他算法进行比较. 具体如表2所示.

从表2可以看出，在6个标准案例中，混合帝国竞争算法（HICA）除了在求解案例ch130标准案例时的平均解为6 142.1，其低于布谷鸟算法（DCS）算法的平均解；除此之外，无论是最优解还是偏差率，HICA均优于其他算法，表明该算法的整体求解性能优于其他算法. 尽管该算法的初始种群数量及迭代次数均多于其他对比算法，但由于该算法引入的区块具有降维作用，在一定程度上减少了该算法的运算时间. 混合帝国竞争算法求解部分标准案例的最优路线图如图9、10所示.

为了直观表达混合帝国竞争算法的收敛质量，以eil51及kroA200为研究对象，分别运用HICA与ICA进行求解，对所得的结果进行比较，如图11、12所示.图中，J为迭代次数，C为路径长度.

从图11、12可以看出，在迭代次数相同的情况下，HICA的收敛速度快于ICA算法，这是因为迭代过程中构建的区块具有降低算法维度的作用，HICA算法在一定程度上降低了问题复杂度和运算时间. 利用HICA得到的结果比ICA算法更优，误差更小.

本文提出求解旅行商问题的混合帝国竞争算法，将区块概念引入到帝国竞争算法中的同化阶段，加快了算法收敛的速度. 在帝国革命阶段运用突变策略及反复搜索策略，在保证种群多样性的同时，提高了算法的全局搜索能力. 通过对TSPLIB的仿真测试可以看出，混合竞争算法的求解质量及收敛速度都优于其他算法.

本文仅仅将混合帝国竞争算法用于求解旅行商问题，未用于求解流水车间调度问题、函数优化、含有时间窗的车辆配送问题. 未来可以从这几个方向进行研究.