量子扩展蚁群连续优化改进算法

马 颖，田维坚，樊养余

（1.西北工业大学 电子信息学院，陕西 西安710072；2.西安工业大学 电子信息工程学院，陕西 西安710032）

0 引 言

蚁群算法 （ant colony algorithm，ACA）在离散组合优化领域取得了巨大成功，是最有效的优化手段之一。其在连续空间的组合优化应用时，一般的做法是仍然采用离散算法模型，将连续问题离散化。在计算复杂度和求解精度要求不高时，这样的做法基本可以得到满意的优化结果，但是对一些特殊情况，如高维优化问题，则存在一定的求解困难。

真正将蚁群算法应用于连续函数求解的文献，目前仍不是太多。Socha等在充分研究蚁群算法结构和信息素概率选择机制后，提出了用于求解连续空间优化问题的蚁群算法 （ACOR）［1］，该算法引入高斯核函数表达复杂函数概率密度分布，定义了解存储器作为算法的信息素模型，将ACA 的离散概率选择连续化，从本质上将算法扩展到连续空间优化问题上。ACOR算法由于没有改变蚁群算法基于概率选择和信息素更新的本质，因而也被一些学者称为扩展蚁群算法［2］。文献 ［1］的测试结果表明，ACOR是目前最具竞争力的蚁群算法。虽然ACOR能够充分发挥蚁群算法的优势，但是也存在收敛速度过快而导致的求解精度不高、容易陷入局部最优和出现停滞现象等缺陷。

量子优化算法由于采用了量子比特作为信息的基本载体，因此具备了量子计算的许多特质，在信息容量、并行计算能力等诸多方面有着比经典计算无法比拟的优势。本文将ACOR核心思想引入量子领域，提出量子扩展蚁群连续优化改进算法 （improved quantum extended ant colony algorithm for continuous optimization，IQEACA），算法采用云模型对ACOR中关键的高斯核函数采样自适应机制进行改进，增强了全局搜索能力。

1 扩展蚁群算法简介

1.1 高斯核函数

高斯核函数Gi（x）是其各组成元素的高斯函数（x）的线性组合形成，即

式中：Gi（x）——第i个高斯核函数，每个高斯核函数由k个独立的高斯函数组成。高斯核函数包含3个参数，分别是权重ω、均值μi、标准差σi。

1.2 解存储器

ACOR用解存储器T 保存解的信息，间接达到信息素的保存与更新的目的。假定待优化问题的维度为n，解存储器中解的集合元素为k，则解存储器的结构如图1所示。

图1 ACOR 中解存储器的结构

图1中Sl表示这个n 维问题的第l 个解向量，表示这个解向量的第i个变量，f（Sl）表示该向量的函数值 （适应度值），ωl表示该向量对应的权值。图中可行解的排列顺序是根据其函数值从优到劣的顺序来排列的。例如在求解极小值问题时，可行解需按照f（S1）≤f（S2）≤…≤f（Sk）来排列；相应的，每个函数值对应权值的排列顺序为：ω1≥ω2≥…≥ωk。计算解向量Sl的权值ωl采用下式

式中：qk——标准差，q——算法的一个参数。当q 较小时，较优解的权值比较差解的权值大很多；而当q较大时，各可行解的权值差别较小，各可行解的权值分布较q 较小时均匀很多。q值对算法的影响类似于ACO 中调节信息素更新策略用以平衡迭代速度与搜索全局最优值。

1.3 ACOR 算法流程

算法的流程大致可分为以下几步：

（1）解存储器初始化：设蚁群有m 只蚂蚁，解存储器T 的长度为k，连续优化问题变量为n维。将解存储器T 随机初始化为k维解向量，每个解向量的长度为n，由这些解向量计算出对应的函数值，并根据式 （2）计算出相应的权值。

（2）对高斯核函数进行采样：在ACOR中，通过对核函数Gi的采样来形成新的可行解。对于每一个Gi，解存储器中第i维变量所有解变成了均值向量μi的元素

而对于任意一个组成核函数的高斯函数被选择采样的概率为

在实际操作中，通过将使用参数化正态随机数产生器（如Box－Muller）产生的随机数，等同于对高斯核函数的采样。与所选高斯函数采样最后一个相关参数σil由下式给定

其中，ξ＞0，算法的一个参数，对这n 维变量均相同；ξ的取值越大，算法的收敛速度越慢。

（3）信息素更新：对所有蚂蚁进行采样，得到m 个解向量与原解存储器T 中的解一起组成临时解向量，并将这个临时解向量按照函数值排序，取前k 个解向量对解存储器T 相关数据进行更新，确保了解存储器中始终为最优解，更好的引导蚂蚁进行搜索。

文献 ［1］虽然验证了算法的有效性，但同时并未给出局部优化策略，阻碍了算法性能的进一步提升［3］。

2 量子扩展蚁群改进算法

2.1 量子编码方案与解空间映射

在量子优化算法中，常见的量子位编码方案有量子位概率幅实数编码、量子位角度编码［4］、球面角度编码［5］、位置区域编码［6］等。就相对于优化算法所采用的全局和局部寻优策略对最终搜索结果的影响而言，采用何种量子位编码方案对最终优化结果的影响相对较小。因此，本文采用最简单的概率幅对蚂蚁的位置进行编码。其模型为：设蚁群共由m 只蚂蚁组成，则第i只蚂蚁的编码可表示为

其中，相位tij＝2π×rand，rand 是 （0，1）区间均匀分布的随机数。由于量子比特的两个概率幅都可视为蚂蚁的当前位置信息，因此，在蚁群规模不变的情况下，相当于蚂蚁的搜索空间得到加倍，增加了种群的多样性。

利用线性变换，将量子位概率幅由n 维单位空间映射到优化问题的解空间Ω。线性变换公式为

其中，aj≤Xj≤bj（j ＝1，2，…，n），是 优 化 问 题 的 解 空间Ω。

2.2 标准差的自适应改进

纵观整个ACOR算法，其最重要的过程是通过对高斯核函数进行采样构建新的可行解，而采样过程又是通过使用随机数产生器产生随机数来等同的。因此，随机数产生器所设置的参数，对可行解的产生起到决定性的作用。为了求得，ACOR算法的做法是：对第i个变量，计算当前解到解存储器中当前变量位置其它所有解的平均距离。通过研究式 （5）可知，虽然也是自适应于解的变化，然而更多的是体现出蚁群中蚂蚁的平均位置，这显然对整个迭代过程中最优个体的探索与种群优化的引导不利，达不到我们希望算法在初期的加快收敛和后期在极小领域的 “求精”搜索的效果。

我们已知使用云模型理论可以在随机性和模糊性两个方面有很好兼顾；近年来智能算法领域已经开始关注云模型，在智能控制、数据挖掘、入侵检测、系统评估等领域已被证明其有效性，在很多案例中取得了较传统自适应方法更优秀的表现［7－9］。本文使用云模型产生标准差，对其实行自适应控制。

首先，使用X 条件云模型，对解存储器T 中各可行解产生相对于最优可行解各变量的确定度值，如下所示：

为了简要说明该方法的有效性，对病态函数Rosenbrock的2维函数进行函数优化，并与ACOR算法进行优化结果的对比，如表1所示。设定蚁群数量m＝10，解存储器容量k＝10，最大迭代次数500，ACOR中ξ＝1，选取几个典型的q值，两算法独立运行50次，统计优化结果的最优值和平均最优值，见表1。

表1 Rosenbrock优化结果对比

从表中可知，本方法在q 取多种不同值情况下，得到的最佳优化值和平均优化值均明显优于ACOR原方法的优化结果；使用云模型自适应产生标准差，进而产生新可行解的方案是非常有效的。

2.3 q值的自适应改进

在ACOR中，q值的选取对结果优化的收敛速度和收敛精度会造成较大影响；具体到优化的每一次进程，q值的选取将直接决定核函数中高斯函数被选中采样的概率；而对于整个优化过程，q 值的改变又不会对作为ACOR核心的高斯采样过程造成任何本质的改变。因此，实现q 值在算法寻优过程中的自适应调整是有利于算法优化进程的。如果能够实现优化的初期q 值较小，这样最优可行解被采样的概率将会大一些，算法收敛速度就会很快；而达到一定搜索精度，产生优化停滞后，q值应相应调整的大一些，即可增加采样的多样性，利于优化过程跳出局部最优值。

对于q值自适应产生方法，可采用固定值、线性产生和非线性产生几种方法。固定值自适应法是选取一些典型值，根据进程需求，采用按比例分配、轮盘赌等方法，将典型值赋给q。

q值线性增大产生策略是使q 值随迭代次数t 的增加而线性增大，可采用下式取值

采用q值非线性增大产生策略，希望能够在迭代初期产生的q值较小，从而促使算法快速收敛；迭代进行到一定程度后，迅速增大q 的取值，增加采样多样性。因此，可以采用开口向上的抛物线模型，其方程形式如下

式 （9）～式 （10）中，q0是参数q的初始值。

仍然使用2 维Rosenbrock，函数对ACOR中这3 种q值产生方法进行优化结果进行对比，规定q0＝0.001，其它参数与上节仿真保持一致；固定值法以100次迭代为一个单位，由小到大的采用表1中q 的取值。优化过程采取两种方案，方案1中历次迭代过程中的q 值由本节中上述方法给出随着迭代次数变化而改变；方案2更遵从 “迭代初期q值要小利于快速收敛，迭代中后期q 值要大，利于保持可行解的多样性”这一思想，以方案1为基础，规定q0为初值，每当最优解一段时间 （如20 次迭代）不再优化时，再利用方案1的方法产生具体的q 值。两种方案分别记为ACOR（1）和ACOR（2）。3种方法优化的结果见表2。

表2 q值取值策略结果对比

从表中可以看出，ACOR（2）相比ACOR（1）具有明显的优势。在3种方法中使用线性方法自适应产生q 值，相比其它两种方法所得到的最优值和平均最优值更为理想。参照表1结果可知，使用线性ACOR（2）方案得到的最优解在多数情况下，优于标准ACOR算法中q 值采用单一固定值时函数的优化结果；但是q 值在迭代过程中的由小变大，同时也会减慢函数的收敛速度。

2.4 局部寻优策略

由于蚁群算法容易出现优化停滞现象，为了解决蚁群算法的搜索精度问题，众多学者一般采用将蚁群算法与进化算法相结合的办法。这样做的好处是显而易见的：进化算法本就在高精度搜索方面具有较大优势，且进化算法进行局部搜索的改进方案也较为成熟。而且，量子进化算法及其改进算法，相对于经典领域的进化算法，无论在收敛速度、还是在搜索精度方面具有更大的优势。

鉴于此，本文也采用与量子进化算法相结合的办法，加强函数局部寻优的能力。作者曾提出了一种基于云模型的量子自适应进化算法［8］，该算法相对于其它自适应量子进化改进算法具有较明显的优势，现简要介绍核心步骤。

当Ex ≥μ0i 时，式 （11）取 “－”号，否则取 “＋”号。分析云模型变异可知，在变异过程需要 “求精”操作时，变异能在最优适应度邻域以更小的搜索范围寻找更优解；在需要 “求泛”操作时，朝着最优适应度邻域拥有更大的搜索范围；同时，在某些情况下，相比于量子旋转门方案，能够对染色体个体产生更大的概率幅值变异，这对于加速收敛和跳出局部最优等有更大的意义。

其中，Fmax、Fmin、F′分别代表解存储器中适应度的最大、最小值及某可行解的适应度值，xij是蚂蚁的概率幅编码中某一位上具体的编码值。

（2）交叉操作：本文采用量子全干扰交叉算子对种群进行交叉操作，根据参考文献 ［10］结论，并经多种参数及测试函数的仿真结果对比，在本文算法中使用全干扰交叉算子在更多情况下可获得较单个个体或少量个体交叉更优的寻优结果。这种交叉操作方法模拟了量子的干涉特性，充分利用种群中染色体信息，有利于增加种群多样性，有效避免算法早熟收敛。

（3）变异处理：随机选择一定规模 （如0.1 m）的蚂蚁，然后随机选择其携带的若干个量子位，依变异概率对选中的量子位施加量子非门变换，使该量子位的两个概率幅互换。

2.5 算法步骤

（1）通过式 （6）和式 （7）产生初始化种群，完成解空间的线性映射，并评价种群中蚂蚁的适应度；

（2）构造解存储器T，并根据式 （2）和式 （10）计算各可行解的初始权重；

（3）按式 （4）选择高斯概率密度函数，使用云模型生成各可行解与最优解的相对确定度，通过式 （8）构建随机数发生器，完成对蚂蚁的采样，构造新可行解；

（4）执行局部寻优策略；

（5）对新可行解与解存储器T 中的原可行解进行比较、排序，完成解存储器T 的整合，更新信息素；

（6）对比最佳适应度，若T 中的最佳适应度值连续若干代保持不变，则按照式 （10）取得q 的即时值，重新分配T 中可行解的权重和被选概率；

（7）返回 （4）循环计算，直到达到收敛条件或最大迭代代数。

3 测试结果与分析

选取常用的5个典型测试函数检验算法的有效性，具体函数见表3。

表3 测试函数

将本文算法与标准扩展蚁群算法 （ACOR）［1］、基于量子旋转门局部寻优策略的改进量子扩展蚁群算法 （extended quantum ant colonyalgorithm，QACOR）［2］、基于量子旋转门局部寻优策略的连续量子蚁群算法（continuous quantum ant colony algorithm，CQACA）［11］两个优秀改进蚁群算法进行对比。

仿真环境为Matlab2012b，设定蚁群蚂蚁数量m＝10，解存储器容量k＝10，q0＝0.1，ACOR中ξ＝1，其它未说明参数设置与文献保持一致。分别计算变量为2维、10维和30维时函数的优化结果，各算法均独立运行50 次，统计结果的最优值、平均最优值见表4。

表4 函数优化结果对比

通过对表中数据的分析可知：对于引用的5个标准测试函数，本文算法无论是在最优值还是在平均最有值两个指标上都全面优于其它3种算法；算法的收敛速度快，尤其对解决连续空间高维优化问题相比其它算法优势较大；算法在所列几种参数的测试下均取得了较满意的结果，只在病态、有大量局部最优值的Rosenbrock函数的高维测试时，所得结果相对于本算法对于其它4个函数的优化结果的优势有所减小，但仍优于其它算法的优化值。以上结果充分说明采取本文算法提出的σil自适应产生机制和局部寻优策略是可靠、高效的。

选取数据维度为2，迭代次数为500这一参数，为4种算法设置共同的初始蚂蚁种群值，各算法再独立运行50次，取各算法全部优化结果的平均值，其收敛过程对比如图2所示。

从图2中可以看出，本文算法具有快速收敛的特性。

图2 4类算法的收敛过程对比

4 结束语

本文分析了ACOR算法高斯核函数采样标准差产生机制，提出了基于云模型的标准差自适应控制法替代原有产生机制，并简要论证了该方法相比于原办法更为有效；同时，自适应的控制了参数q 的取值，从而实现了采样概率的动态调整；在此基础上，给出了基于云模型变异的局部搜索策略。通过仿真验证了本文算法具有较强的搜索能力和效率，能够有效避免早熟，尤其适用于高维连续优化问题，相比于其它同类算法具有较明显优势。针对不同函数和优化问题，本文算法在参数的选取方面可进行相应的调整，其优化结果还会有提升的空间。

［1］Socha K，Dorigo M.Ant colony optimization for continuous domains［J］.European Journal of Operational Research，2008，185 （3）：1155－1173.

［2］LI Shiyong，BAI Jiyun.Extended quantum ant colony algorithm for continuous function optimization ［J］.Journal of Harbin Engineering University，2012，33 （1）：80－84 （in Chinese）.［李士勇，柏继云.连续函数寻优的改进量子扩展蚁群算法 ［J］.哈尔滨工程大学学报，2012，33 （1）：80－84.］

［3］HE Zongyao，WANG Xiang.Adaptive bee－ant colony optimization ［J］.Application Research of Computer，2012，29（1）：130－134 （in Chinese）.［何宗耀，王翔.蜂群－蚁群自适应 优 化 算 法 ［J］. 计 算 机 应 用 研 究，2012，29 （1）：130－134.］

［4］LI Panchi，SONG Kaoping，YANG Erlong.Phase encodedbased quantum ant optimization ［J］.Systems Engineering－Theory ＆Practice，2011，31 （8）：1565－1570 （in Chinese）.［李盼池，宋考平，杨二龙.基于相位编码的量子蚁群算法［J］.系统工程理论与实践，2011，31 （8）：1565－1570.］

［5］LI Panchi.Quantum genetic algorithm based on Bloch coordinates of qubits and its application ［J］.Control Theory ＆ Applications，2008，25 （6）：985－989 （in Chinese）. ［李盼池.基于量子位Bloch坐标的量子遗传算法及其应用 ［J］.控制理论与应用，2008，25 （6）：985－989.］

［6］HUANG Jingwen，QIN Chaoyong.Real coded quantum ant colony optimization algorithm for global numerical optimization［J］.Application Research of Computers，2009，26 （10）：3660－3662 （in Chinese）.［黄景文，覃朝勇.用于多维函数优化的实数编码量子蚁群算法 ［J］.计算机应用研究，2009，26（10）：3660－3662.］

［7］ZHANG Guangwei，HE Rui，LIU Yu，et al.An evolutionary algorithm based on cloud model［J］.Chinese Journal of Computers，2008，31 （7）：1082－1091 （in Chinese）.［张光卫，何锐，刘禹，等.基于云模型的进化算法 ［J］.计算机学报，2008，31 （7）：1082－1091.］

［8］MA Ying，TIAN Weijian，FAN Yangyu.Quantum adaptive immune clone algorithm based on cloud model［J］.Chinese Journal of Computational Physics，2013，30 （4）：627－632（in Chinese）.［马颖，田维坚，樊养余.基于云模型的自适应 量 子 免 疫 克 隆 算 法 ［J］.计 算 物 理，2013，30 （4）：627－632.］

［9］MA Ying，TIAN Weijian，FAN Yangyu.Adaptive quantumbehaved particle swarm optimization algorithm based on cloud model［J］.PR ＆AI，2013，26 （8）：787－793 （in Chinese）.［马颖，田维坚，樊养余.基于云模型的自适应量子粒子群算法 ［J］.模式识别与人工智能，2013，26 （8）：787－793.］

［10］LIU Fang，WANG Shuang，LIU Yingying，et al.A quantum－inspired evolutionary algorithm based on a modified quantum rotate gate for data clustering ［J］.Acta Electronica Sinica，2011，39 （9）：2008－2013 （in Chinese）. ［刘芳，王爽，柳莹莹，等.基于改进量子旋转门的量子进化数据聚类 ［J］.电子学报，2011，39 （9）：2008－2013.］

［11］LI Panchi，LI Shiyong.Quantum ant colony algorithm for continuous space optimization ［J］.Control Theory ＆ Applications，2008，25 （2）：237－240 （in Chinese）.［李盼池，李士勇.求解连续空间优化问题的量子蚁群算法 ［J］.控制理论与应用，2008，25 （2）：237－240.］