求解带约束投资组合模型的量子粒子群算法*

何 光, 李高西

(重庆工商大学 数学与统计学院，重庆 400067)

0 引 言

Clerc[1]在分析粒子群优化(Particle Swarm Optimization,PSO)算法时提出粒子运动场中存在着吸引点，而粒子在迭代过程中会聚集到该点。随后Sun 等[2]在Clerc的研究基础上，从量子力学的角度提出了量子粒子群优化(Quantum-behaved Particle Swarm Optimization,QPSO)算法。由于粒子在量子空间中没有特定的轨道，具有更高的随机性，因而其智能性相比标准的PSO算法要高，收敛性能更好。尽管QPSO 算法在一定程度上提升了算法的性能，但是在实际计算时，粒子的搜索只是在可行解的空间进行，使得在算法迭代的后期依旧会出现群体的多样性缺失等现象，因此算法仍有很大的改进空间。

针对QPSO算法的不足，先后有学者提出了各种搜索策略和改进方法，以增加粒子的探索能力，避免算法陷入局部最优的困境。Mohadeseh等[3]提出了基于广义局部搜索的QPSO算法，以增强粒子脱离局部最优的能力。赵吉和程成[4]在演化搜索的基础上改善了QPSO算法，提升了算法的收敛速度。章国勇等[5]在算法中考虑了精英学习策略，增强了粒子的全局搜索能力。周頔等[6]提出了协同QPSO算法，避免了算法的早熟。张兰[7-8]分别融合了差分进化和黑洞搜索的优点，提出了改进的QPSO算法，拓展了粒子的空间探索范围。在算法的参数修正和丰富种群多样性方面，也有一些学者提出了不错的改良性结果[9-14]。在已有研究的基础上，准备从两个方面对QPSO算法进行改进：第一，在粒子的历史位置更新公式中，将粒子的历史最优和次优位置综合考虑，以扩大粒子的搜索范围，增加粒子的探索能力；第二，借助遗传算法的交叉操作，提高种群的多样性，避免算法进入早熟。然后，将改进后的QPSO算法应用到证券投资组合问题中。

1 改进的QPSO算法

标准的QPSO算法是在PSO算法的基础上进化而来，借助了PSO算法的粒子速度公式：

vi(t+1)=wvi(t)+c1r1(pi(t)-xi(t))+

c2r2(pg(t)-xi(t))

(1)

其中，xi(t)和vi(t)分别表示第i个粒子的位置以及速度，第i个粒子的个体极值以及全局极值分别为pi(t)和pg(t)。w表示惯性权重，c1和c2表示加速因子，r1和r2表示0到1之间均匀分布的随机数。在QPSO算法的更新公式中，没有粒子的速度公式，而采用蒙特卡罗法模拟粒子的运动状态，进行迭代。在迭代过程中，每个粒子会聚集到一个局部吸引点Pi(t)，从而式(1)将转化为吸引点的位置公式：

Pi(t+1)=φpi(t)+(1-φ)pg(t)

(2)

其中，φ=c1r1/(c1r1+c2r2)。粒子的位置更新公式如下：

xi(t+1)=Pi(t)±β|mi(t)-xi(t)|ln[ui(t)]-1

(3)

其中，β称为收缩-扩张系数，用来调节粒子的速度。mi(t)表示粒子历史最优位置的平均值，称为平均最好位置。ui(t)表示0～1之间均匀分布的随机数，当ui(t)大于0.5时，式(3)中取“+”，否则取“-”。

在更新粒子个体最优位置时，除了考虑它的历史最好位置外，还将粒子的历史次优位置也包括进去，这样能够增强粒子的搜索范围，避免陷入局部最优。另外，借鉴遗传算法的交叉操作，对粒子的历史最优和次优位置进行交叉处理，用新的位置作为粒子当前的最优位置，用于迭代后期增强种群的多样性，提高算法的收敛精度。

由于算法中选用了交叉操作，将改进的算法记为CR-QPSO。CR-QPSO算法中，粒子的历史最优位置和次优位置分别为p1i(t)和p2i(t)，经过交叉操作后得到的新位置仍记为pi(t)。收缩-扩张系数选择文献[13]的线性递减方法，如下：

其中，β1,β2为β的最小值和最大值，T为最大迭代次数。CR-QPSO算法的流程如下：

Step 1设定搜索维数D、种群规模N和最大迭代次数T，初始化种群中粒子的位置；

Step 2计算每个粒子的适应度，以适应度最优的粒子位置作为种群的全局最优位置pg(t)；

Step 3根据式(2)计算局部吸引点Pi(t)；

Step 4根据式(3)更新当前粒子的位置；

Step 5通过粒子适应度的比较，确定当前粒子的历史最优位置p1i(t)和次优位置p2i(t)，运用交叉操作，得到粒子的个体最优位置pi(t)；

Step 6当粒子适应度优于种群最优点的适应度时，则用当前粒子的位置更新pg(t)；

Step 7t=t+1，若满足迭代终止条件，输出最优解，否则，转入Step 2。

2 性能测试

在性能测试中，将CR-QPSO算法与标准的QPOS算法、DE-QPSO算法[7]和BH-QPSO算法[8]进行比较。基准测试函数的计算结果来源于文献[8]，其中f1为高维单模函数，f2-f5为高维多模函数，f6为低维多模函数。

在所有的QPSO算法中，加速因子分别取1.5和2，粒子总数为10个，搜索空间为20维，最大迭代次数为1 000次。在DE-QPSO算法中变异概率为0.5，交叉参数为0.9；在BH-QPSO算法中，黑洞理论阈值为0.8，黑洞半径为0.8；每个实例取50次结果的平均值和标准差。

在表1中，展示了4种算法在不同测试函数下的计算结果。在Sphere函数和Griewank函数的测试中，BH-QPSO算法和DE-QPSO算法取得了较好的寻优结果，相比而言CR-QPSO算法在最优解均值和解的稳定性方面则具有更好的表现，能够有效地跳出局部最优，探索到函数的全局最优点。对于Rosenbrock函数而言，BH-QPSO算法在函数均值方面取得了最佳的表现，然而稳定性不够理想；QPSO算法和DE-QPSO算法在求解过程中明显偏离了有效的寻优路径，寻优结果较差；CR-QPSO算法的综合效果较好，最优解的均值不如BH-QPSO算法，但是解的稳定性方面有更好的表现。就Rastrigin函数而言，4种算法都无一例外地陷入了局部最优的困境。其中BH-QPSO算法和DE-QPSO算法的改进效果不如原始的QPSO算法，寻优能力较弱；相比之下CR-QPSO算法具有较好的探索能力，经过变异操作之后的粒子能够比较有效地接近函数的全局最优点。在其余两个函数的测试中，CR-QPSO算法相比其他3种算法表现更突出，无论在函数的最优值还是鲁棒性上都取得了最理想的结果。

表1 4种算法的测试结果Table 1 Test results of four algorithms

总之，通过测试函数的检验结果，CR-QPSO算法在其中5个函数的测试中均表现出最佳的寻优能力，取得的最优解拥有更好的鲁棒性。

3 应用实例

经典的Markowitz均值-方差模型为一类多目标优化问题，其有效前沿即多目标优化问题的Pareto最优解。这里将多目标优化问题转换为单目标优化问题，并用改进的量子粒子群算法进行求解。在证券交易中，投资者和管理机构往往基于各种考虑会对证券的交易数量作出限制，于是这里讨论一类投资占比有上限的投资组合问题。具体模型如下：

(1)

其中，R为资产的收益矩阵，X为投资组合的权重向量，∑表示各种资产间的协方差矩阵，ei表示资产的预期收益率，设定所有股票的投资比不能超过总资金的50%。

数值实验中，从深圳证券交易所选取了A股市场中的20只股票，收集了这些股票从2017年9月18日到2018年9月20日共计250个交易日的收盘价格。每只股票以日收益率的历史平均值作为其预期收益率。在改进的量子粒子群优化算法CR-QPSO中，加速因子分别取1.5和2，粒子总数为40个，搜索空间为20维，最大迭代次数为1 500次，求解结果取50次实验的平均值。

表2给出了在不同预期收益率下的模型。式(1)的最优解，通过给定的ei(在最小与最大预期收益率之间均匀选取，由小到大逐渐增加)可以计算出相应风险最小的组合。从表2中数据可知，随着预期收益率的增大，投资组合的风险也在逐步变大。当收益率从0.081 2增加到0.193 9时，第1、第11、第17和第19这4只股票的投资占比逐渐减小；同时第4和第9这两只股票的比例分别从2.01%和5.66%增加到3.98%和19.87%。

表2 不同预期收益率下的最优投资组合Table 2 Optimal portfolios under different expected rate of return

进一步，为了说明改进算法求解模型(1)的有效性，接下来将CR-QPSO与PSO、QPSO和GA等算法从最差值、最好值、均值和方差等4个方面进行比较。在对比实验中，选取预期收益率为0.193 9，具体结果见表3。

表3 不同算法的优化结果比较Table 3 Comparison of optimization results of different algorithms

由表3可知:改进算法在4个指标下均取得了比其余3种算法更好的结果，表明CR-QPSO算法具有更强的寻优能力，获得的最优解更精确、更稳定。

4 结束语

为了提高量子粒子群算法(QPSO)的粒子探索能力和算法的计算精度，在原始的QPSO算法的基础上，对粒子的位置公式进行了改良处理。在改进算法中，一方面考虑了粒子的历史最优和次优位置的共同影响，用以拓展粒子的搜索范围；另一方面，采用了遗传算法中的交叉操作，用以增加粒子的多样性。通过与几种已有算法的对比，改进的量子粒子群算法(CR-QPSO)表现出更好的收敛性和鲁棒性。随后，将CR-QPSO算法应用于寻找Markowitz均值-方差模型的资产最优组合。借助证券市场中股票的历史数据，对一类具有投资数量限制的投资组合模型进行了求解，计算结果表明改进算法具有更好的性能。