多尺度量子谐振子算法在组合优化问题中的性能分析

王 鹏，黄 焱，安俊秀，李建平

（1. 西南民族大学计算机科学与技术学院 成都 610041；2. 中国科学院成都计算机应用研究所 成都 610041；3. 中国科学院大学 北京 石景山区 100049；4. 成都信息工程大学并行计算实验室 成都 610225；5. 电子科技大学计算机科学与工程学院 成都 611731）

多尺度量子谐振子算法在组合优化问题中的性能分析

王 鹏1，黄 焱2，3，安俊秀4，李建平5

（1. 西南民族大学计算机科学与技术学院 成都 610041；2. 中国科学院成都计算机应用研究所 成都 610041；3. 中国科学院大学 北京 石景山区 100049；4. 成都信息工程大学并行计算实验室 成都 610225；5. 电子科技大学计算机科学与工程学院 成都 611731）

多尺度量子谐振子算法（MQHOA）是一种基于一维量子谐振子波函数原理提出的新优化算法，该文在MQHOA框架下构建了旅行商问题（TSP）的求解流程和方法，研究了算法的物理意义和理论收敛过程。通过对12组TSP标准测试数据集的实验表明，根据算法物理模型要求的高斯邻域生成方法优于随机邻域生成方法，而且MQHOA算法对TSP问题的求解结果在获得最优解的概率和多次实验的平均最小距离两个指标上都要优于模拟退火算法，与其他算法对比也证明了该算法具有较好的性能。同时还研究了在规则城市数据集条件下算法的性能和收敛情况。这些结果证明MQHOA算法可以较好地被应用于组合优化问题。

组合优化； 多尺度量子谐振子算法； 优化算法； 旅行商问题

MQHOA［1］是受一维量子谐振子的波函数图像启发而设计的一种新的优化算法。文献［1］首次提出了MQHOA算法的完整实现方法，同时实验结果证明对于15种常用的优化测试函数都能在不改变算法参数的条件下以100%的概率获得精确的理论最优值，在求解高维函数优化问题时也表现出良好的性能，一些研究者也做了大量尝试将量子谐振子物理模型应用在算法设计上；文献［2］将量子谐振子势能场引入粒子群系统；文献［3］提出了一种量子谐振子蚁群算法；文献［4］研究了多尺度量子谐振子算法的物理模型；文献［5］研究了谐振子量子波函数的概率特性，但并未利用波函数的概率解释提出相应的算法模型；文献［6］对MQHOA算法的实现方法进行分析；文献［7］通过求解整数非线性规划问题对MQHOA算法的性能进行分析；文献［8］提出了一种基于划分的多尺度量子谐振子多峰优化算法；文献［9］将MQHOA算法用于求解聚类中心点问题，又对MQHOA算法进行优化改进，通过判断两次采样迭代后种群最优值的方差来判断系统是否达到稳定态，和均值替换法保持了种群的多样性，达到了良好的效果。

组合优化问题是很多科学、工程问题的抽象，这些问题本身看上去都非常简单，但求解这类问题却十分复杂。目前求解组合优化问题的方法很多都建立在模拟自然的基础上，有时也将这类算法称为自然算法［10］，如遗传算法［11］、模拟退火算法［12］、蚁群算法［13］，这些算法在理论和实践上取得了大量成果。MQHOA算法也是一类利用随机方法的不确定性算法，本文以典型的组合优化问题—TSP问题为例，研究并验证MQHOA算法应用于组合优化问题的方法，通过12组TSP标准测试数据集对算法性能进行实验，从方法和实验结果的角度均证实了MQHOA算法在组合优化问题领域的应用能力。

1 组合优化问题与算法量子理论模型

1.1 组合优化问题的定义

组合优化问题可以描述为：令Ω=｛s1，s2，，sn｝为所有状态构成的解空间，C(si)为状态 si对应的目标函数值，求解组合优化问题就是寻找最优解 s*，使得对于所有的si∈Ω，有C（s*）=min（C（si））。

1.2 MQHOA的物理模型介绍

一维谐振子的势能曲线为：

式中，K为简谐力强度的参数。一维谐振子的势能曲线表明目标函数在最优解附近近似是平滑的二次曲线。

将谐振子势能曲线代入相应的薛定鄂方程解出的能级和波函数概率密度分别为：

第n个能级的能量函数为：

波函数概率密度为：

谐振子的波函数从高能态向基态的变化是一个逐渐收敛的过程。从高能态多个高斯概率函数的叠加，逐步收敛到基态单一高斯分布的稳定状态

谐振子波函数图像描述了优化问题的逐步收敛过程，这一过程对应于波函数从高能态向低能态的变化过程。

2 MQHOA算法求解TSP问题的原理

TSP问题：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

2.1 多尺度量子谐振子算法的基本收敛过程

多尺度量子谐振子算法的基本工作原理包括两个过程：一个是同尺度上的量子波函数收敛过程，另一个是尺度本身的收敛过程。这两个过程一个是提取信息，另一个是收缩搜索区域，多次迭代后算法将收缩到最优解位置。尺度收敛过程较为简单，下面主要分析在同一个尺度上的量子收敛过程。

同一个尺度上量子谐振子算法的基本收敛过程可以描述如下：将每次迭代保留的k个较好的采样位置 ki作为k个局部收敛区域的中心位置，以所选的k个中心位置构造k个标准差为σ的高斯分布函数N(ki,σ2)，形成k个局部最优采样区域，每个区域分别按高斯分布N(ki,σ2)在定义域采样生成m个解；k个标准差为σ的高斯分布函数在迭代过程中逐渐聚集，向单一高斯分布收敛；迭代过程直到k个中心位置 ki之间的标准差σk小于σ时停止，类比量子收敛过程，这时可以认为k个高斯函数叠加形成的波函数收敛于高斯分布为N(ki,σ2)能量基态。量子谐振子波函数收敛的迭代过程就是多个标准差为σ的高斯采样函数叠加形成的波函数向基态的聚集收敛过程。

每次迭代中的k个标准差为σ的高斯分布函数的叠加称为量子谐振子算法的波函数，归一化的算法波函数定义为：

量子谐振子算法的波函数的概率分布是对目标函数定义域上进行采样的概率分布。 MQHOA算法收敛过程的详细数学物理描述见文献［1，4］。

2.2 MQHOA算法求解TSP问题的基本过程

在MQHOA算法框架下设计求解TSP问题的算法过程的关键是解空间中邻域的生成方法，本文采用两组不同的城市排列之间的对应位置城市标志的个数来作为函数的自变量，不同位置城市的个数越少认为这两组解相距越近，反之则越远。由于TSP问题的算法复杂度与城市个数是阶乘的关系，所以在面对TSP问题时将尺度变化因子λ设定为1.1（函数优化问题中一般将λ设定为2），算法在尺度降低到σ=1时停止。

根据多尺度量子谐振子模型，MQHOA算法处理TSP问题的基本工作流程的伪代码为：

1 BEGIN

2 Initialization：k、m、λ、σ

3 随机生成k×m 个城市排列序列

4 保留其中较优的k个城市序列

5 DO

6 DO

7 基于k个距离最优序列分别生成m个新的序列

8 计算其中k个较优序列的标准差σk

9 WHILE （σ＜σk）

10σ=σλ

11 WHILE （σ＞1）

12 输出当前k个较优序列中的最优序列

13 END

通常将σ的初始值设为城市总数N，算法在尺度变化时以一个固定的倍数减小，这一尺度变化方法近似于将TSP问题的算法复杂度降低为logN。在迭代中产生的k×m 个城市序列中选取k个较优城市排序中的最短距离序列，以此为基准计算σk，其他k-1个排序依据与基准序列之间的差距计算出方差值。如某一序列与基准序列之间有6个城市的位置不同则差距为6。第7步中新序列的生成方法为针对每个序列用标准差为σ的高斯分布分别生成m个整数Nm，分别在该序列中随机找到一个位置将该位置后面Nm个城市位置进行倒序，第7步将总共生成k×m 个城市排列序列。在算法的实际应用中k和m的值在设定后通常不用做太大的改变，m的值对应于每个区域的邻域采样个数。根据算法的物理模型新解的生成采用高斯函数，算法在运行过程中解空间中的搜索区域逐步聚集，当不满足σ＜σk时表明解已聚集在一个相对小的解空间范围了，这时算法缩小搜索尺度，执行σ =σλ操作，使搜索更加局部化，当σ等于1时表明k个序列中所有的序列都相同了，此时算法退出，在实际计算时这种条件较难满足，通常算法结束的情况都是σk迭代多次不再变化。k个序列相当于是k个搜索探针，根据所求解问题目标函数的引导信息逐步收敛，正如量子谐振子波函数所描述的一样。

3 实验结果及讨论

3.1 MQHOA算法求解TSP标准测试数据

3.1.1 标准实验测试数据集

本文选取了12组标准测试数据集对MQHOA算法和模拟退火算法分别进行实验。TSP问题的可行解是所有城市的全排列，随着城市个数的增加，其可能路径的总数与城市个数呈指数级的增长，城市个数较大时一般很难求解出其已知最短距离。

表1为本文的12组标准测试数据集，表中给出了各组数据集的已知最短距离。

表1 TSP问题标准测试数据集

3.1.2 两种新解生成方式的实验比较

本文求解TSP问题的算法也是采用高斯分布采样方式生成新解，可以保证当前尺度采样信息的完备性。为了验证此种采样方式在求解组合优化问题时的效果，本文将用高斯分布采样和随机分布采样生成新解的两种方式对12组标准测试数据分别进行10次重复实验，对TSP问题进行求解的实验结果统计如表2所示。

表2灰底部分为采用高斯分布采样方式生成新解的实验数据，随着城市个数的增长，平均迭代次数呈现出线性增长趋势，城市个数较小（21、30、48）时，MQHOA算法可以以100%的概率精确找到已知最短距离；随着城市个数的增长，找到已知最短距离的概率逐渐下降，当城市个数为100、127或更多时，MQHOA算法无法求得已知最短距离，只能找到相对较优距离。

表2白底部分为采用随机分布采样方式生成新解的实验数据，随着城市个数的增长，平均迭代次数与按高斯分布采样方式的平均迭代次数相近，算法可以在相近次数的迭代之后收敛，但收敛到已知最短距离的概率明显降低。当城市个数为21、30时，采用随机分布采样方式可以100%精确地找到已知最短距离，当城市个数大于48时，找到已知最短距离的概率就降至0，只能收敛求得较优距离。

表2 两种新解产生方式求解TSP问题的实验结果

本文在表2中统计了10次重复实验的平均距离，实验数据表明对于12组标准测试数据集用高斯分布求得的平均距离均小于用随机分布方式求得的平均距离。MQHOA算法用高斯分布采样生成新解方式求解TSP问题比用随机采样生成新解方式能更好的向最优解收敛，算法能以更大概率找到更优解。

因此，MQHOA算法采用高斯分布生成新解的方式能有效的求解组合优化问题，这同时也是算法物理模型涵义所要求的。

3.1.3 与模拟退火算法的比较实验

对同样的数据集用模拟退火算法进行实验，与MQHOA算法进行比较。实验测试数据集同样采用表1中的数据，实验结果如表3所示。

模拟退火算法实验参数设定如下：

步长L=10，初始温度T0=1 000。衰减系数D=1.000 5，停止温度2.0×10-6。

从表3的数据可以发现，当城市个数较小（21、30）时，采用模拟退火算法可以以100%的概率找到已知最短距离，当城市个数进一步增加时，获得已知最短距离的概率迅速下降为0，只能找到相对较短的距离，无法找到理论最短距离。对于同样的测试数据集，MQHOA算法在求解100个城市规模时依然能求得已知最短距离。MQHOA算法求解TSP问题所得的最短路径、获得已知最短距离的概率明显优于模拟退火算法。

表3 模拟退火算法求解TSP问题的实验结果

3.1.4 与其他文献报道算法结果的对比

根据文献［14］报道，本文也采用偏离最优路径比率来对比算法的性能，偏离最优路径比率的计算方法为：

表4 MQHOA算法与其他文献报道算法结果的对比

表4中的结果是采用MQHOA算法计算出的μ值与其他算法获得的μ值的对比，表4中其他算法的μ值数据来自于文献［15-17］。表中MQHOA算法的μ值数据是根据10次计算得到的值，总共对8个标准测试集进行了计算和对比，城市数目从51到152。从表中的结果来看对于大多数测试数据集MQHOA算法的μ值都要明显优于其他算法，其中只有st70数据集MQHOA算法的μ值要明显差些，对于pr152数据集MQHOA算法要优于KD、Budinich和ISOM算法。

3.2 MQHOA算法求解规则分布TSP问题

TSP标准测试集中的城市数据较为复杂、没有规律，为了对MQHOA算法进行分析，本节构造了一些有一定规律的规则分布的数据集研究算法。实验中参数k=3 000，m=200。

图1为利用MQHOA算法对不同的规则城市分布数据的TSP问题进行求解的结果。图1a为32个城市单一方形分布，迭代次数为15次，图1b为36个城市带有2个突出点的方形分布，迭代次数为21次，图1c为81个城市的9×9点阵分布，迭代次数为74次，图1d为80个城市的5个4×4点阵分布，迭代次数为91次，图1e为81个城市的随机分布，迭代次数为98次，图1f为225个城市的15×15 点阵分布，迭代次数为388次。从图中可以看出对80个城市以下的规则分布城市数据，MQHOA算法基本都能有效的找到最短路线。从图1f中可以看到大量的斜向路线，这表明算法此时收敛到的结果并不是理论最短路径，从实验中发现对于这类点阵数据算法从10×10 点阵开始就会出现找不到理论最优路径的问题。

图1 规则城市分布数据的实验结果

3.3 MQHOA算法收敛特性分析

对于表1中的标准测试数据集和图1c、图1f这类规则数据本文研究了算法收敛时的迭代次数与城市规模之间的关系如图2所示。

图2a为标准测试数据集的结果，图2b为点阵数据的结果，从图2中的结果来看迭代次数与城市规模总体呈的似的线性对应关系，标准测试数据集中的结果也基本与此结果相符，但随着城市规模的增长算法获得理论最优路径的概率会逐步下降。其他类型数据集的变化情况也类似，这证明算法在求解TSP问题时均具有良好的收敛性。

图2 算法迭代次数与城市数的关系

利用规则结构的城市分布数据可以使算法在数据内在结构一致的条件下进行对比，但由于TSP的内在结构目前还没有理论进行描述，这也是组合优化问题的困难之处。

4 结 束 语

本文提出了在MQHOA算法框架下的TSP问题求解方法，文中对比了高斯邻域生成方法和随机邻域生成方法，表明本文的所用高斯邻域生成方法要优于随机邻域生成方法。与其他算法的比较也表明算法的性能十分稳定，在偏离最优路径比率指标上也要优于已有的一些其他组合优化算法，同时MQHOA算法在获得理论最优解的概率和多次实验的平均距离两个指标上都要优于模拟退火算法。实验证明MQHOA算法也能有效地求解TSP这类组合优化问题，并具有良好的性能。

［1］ 王鹏， 黄焱， 任超， 等. 多尺度量子谐振子高维函数全局优化算法［J］. 电子学报， 2013， 41（12）： 2468-2473. WANG Peng， HUANG Yan， REN Chao， et al. Multi-scale quantum harmonic oscillator for high- dimensional function global optimization algorithm［J］. Acta Electronica Sinica，2013， 41（12）： 2468-2473.

［2］ 冯斌， 须文波. 基于粒子群算法的量子谐振子模型［J］. 计算机工程， 2006， 32（20）： 18-21. FENG Bin， XU Wen-bo. Quantum oscillator model of particle swarm system［J］. Computer Engineering， 2006，32（20）： 18-21.

［3］ 秦永波， 王鹏， 肖黎彬， 等. 量子谐振子蚁群算法［J］. 计算机应用， 2011， 31（增2）： 54-69. QIN Yong-bo， WANG Peng， XIAO Li-bin， et al. Ant colony optimization of quantum harmonic oscillators［J］. Journal of Computer Applications， 2011， 31（z2）： 54-69.

［4］ 王鹏， 黄焱. 多尺度量子谐振子优化算法物理模型［J］. 计算机科学与探索， 2015， 9（10）： 1271-1280. WANG Peng， HUANG Yan. Physical model of multi-scale quantum harmonic oscillator optimization algorithm［J］. Journal of Frontiers of Computer Science and Technology，2015， 9（10）： 1271-1280.

［5］ 王鹏. 云计算的关键技术与应用实例［M］. 北京： 人民邮电出版社， 2010. WANG Peng. Key technology and application of cloud computing［M］. Beijing： Posts & Telecom Press， 2010.

［6］ 刘峰， 王鹏， 黄焱， 等. 多尺度量子谐振子优化算法实现方法研究［J］. 成都信息工程学院学报， 2015（5）： 433-438. LIU Feng， WANG Peng， HUANG Yan， et al. Research on algorithm implementation of multi-scale quantum harmonic algorithm［J］. Journal of Chengdu University of Information Technology， 2015（5）： 433-438.

［7］ 袁亚男， 王鹏， 刘峰. 多尺度量子谐振子算法性能分析［J］.计算机应用， 2015， 35（6）： 1600-1604. YUAN Ya-nan， WANG Peng， LIU Feng. Performance analysis of multi-scale quantum harmonic oscillator algorithm［J］. Journal of Computer Application， 2015， 35（6）：1600-1604.

［8］ 陆志君， 安俊秀， 王鹏. 基于划分的多尺度量子谐振子算法多峰优化［J］. 自动化学报， 2016， 42（2）： 235-245. LU Zhi-jun， AN Jun-xiu， WANG Peng. Partition-based MQHOA for multimodal optimization［J］. Acta Automatica Sinica， 2016， 42（2）： 235-245.

［9］ 燕京京， 王鹏， 范家兵， 等. 基于量子谐振子模型的聚类中心选取算法［J］. 电子学报， 2016， 44（2）： 405-412. YAN Jing-jing， WANG Peng， FAN Jia-bing， et al. Clustering center selecting algorithm based on quantum harmonic oscillator model［J］. Chinese Journal of Electronics， 2016，44（2）： 405-412.

［10］ 吴启迪， 康琦， 汪镭， 等. 自然计算导论［M］. 上海： 上海科学技术出版社， 2011. WU Qi-di， KANG Qi， WANG Lei， et al. Natural computing introduction［M］. Shanghai： Shanghai Scientific and Technical Publishers， 2011.

［11］ HOLLAND J H. Genetic algorithms［J］. Scientific American， 1992， 266（4）： 44-50.

［12］ KIRKPATRICK S， GELATT C D， VECCHI M P. Optimization by simulated annealing［J］. Science， 1983，220（4598）： 671-680.

［13］ COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonies［C］//Proceedings of the 1st European Conference on Artificial Life. Paris： ［s.n.］， 1991：134-142.

［14］ 张军英， 周斌. 基于泛化竞争和局部渗透机制的自组织TSP问题求解方法［J］. 计算机学报， 2008， 31（2）： 220-227. ZHANG Jun-ying， ZHOU Bin. Self organizing map with generalized and localized parallel competitions for the TSP［J］. Chinese Journal of Computers， 2008， 31（2）：220-227.

［15］ ARAS N， ALTINEL I K， OOMMEN J. A Kohonen-like decomposition method for the euclidean traveling salesman problem-KNIES_decompose［J］. IEEE Transactions on Neural Networks， 2003， 14（4）： 869-890.

［16］ VIEIRA F C， NETO A D D， COSTA， et al. An efficient approach to the travelling salesman problem using self-organizing maps［J］. International Journal of Neural Systems， 2003， 13（2）： 59-66.

［17］ LEUNG K S， JIN H D. An expanding self-organizing neural network for the traveling salesman problem［J］. Neurocomputing， 2004， 62： 267-292.

编 辑 叶 芳

Performance Analysis of Multi-Scale Quantum Harmonic Oscillator Global Optimization Algorithm in Combinatorial Optimization Problems

WANG Peng1， HUANG Yan2，3， AN Jun-xiu4， and LI Jian-ping5
（1. School of Computer Science and Technology， Southwest University for Nationalities Chengdu 610041；2. Chengdu Institute of Computer Application， Chinese Academy of Sciences Chengdu 610041；3. University of Chinese Academy of Sciences Shijingshan Beijing 100049；4. Parallel Computing Lab， Chengdu University of Information Technology Chengdu 610225；5. School of Computer Science and Engineering， University of Electronic Science and Technology of China Chengdu 611731）

The multi-scale quantum harmonic oscillator algorithm （MQHOA） is a novel optimization algorithm based on the wave function of one-dimensional quantum harmonic oscillator. The process for solving traveling salesman problem （TSP） using MQHOA is proposed， and the physical meanings and theoretical convergence process of MQHOA are analyzed. The experiments for 12 groups of typical TSP data show that the neighborhoods generated on Gaussian distribution are better than those on random distribution. MQHOA for TSP is better than simulated annealing algorithm on the ratio of getting precise route and the average shortest distance. The comparison with other algorithms also proves the good performance of MQHOA. The performance about regular city data set has also been researched. The experiments results prove that MQHOA is an excellent algorithm to solve combinatorial optimization problems.

combinatorial optimization； multi-scale quantum harmonic oscillator algorithm； optimization algorithm； traveling； salesman problem

TP18

A

10.3969/j.issn.1001-0548.2016.02.027

2014 - 12 - 04；

2016 - 02 - 25

国家自然科学基金（60702075）；国家社会科学基金（12XSH019）；中国博士后科学基金（20090451420）；广东省科技厅高新技术产业化科技攻关项目（2011B010200007）；四川省青年科学基金（09ZQ026-068）

王鹏（1975 - ），男，教授，主要从事智能算法方面的研究.