基于量子蚁群算法的旅行商问题求解及算法评估

量子蚁群算法是一种将量子理论与传统蚁群算法结合的高效生物进化算法,主要应用于故障诊断、路径规划、图像分割等问题的优化.基于传统蚁群算法的流程,介绍量子蚁群算法中的量子理论基础以及量子理论如何应用于蚁群算法.通过若干旅行商问题实例分析量子蚁群算法较传统蚁群算法的优势.针对目前研究多以离散指标来评估不同算法、难以直观显示不同算法综合差别的问题,提出一种综合评估算法搜索效率的方法,成功应用于量子蚁群算法和传统蚁群算法的对比,具有一定的实践意义.

基于量子蚁群算法的非常规储层叠前地震反演方法

在地球物理反演中,通常会设置个目标函数,通过求解目标函数的最小值进而得到问题的真解。(冉启全等,2006)从这个角度出发,反演问题也是个优化问题。在非常规储层中,地质条件复杂导致的地震信号杂乱和响应复杂多变等特征,使得常规基于蚁群算法的叠前地震反演方法存在寻优局部化和寻优效率低的问题。因此,将这种算法进步扩展到量子算法中得到量子蚁群算法(QACA)。

求解旅行商问题的改进型量子蚁群算法

针对传统量子蚁群算法在求解TSP时容易陷入局部最优以及收敛速度较慢,提出了一种求解旅行商问题的改进型量子蚁群算法(IQACA)。该算法设计了一种新信息素挥发因子的自适应动态更新策略,对信息素进行动态更新;并采用一种新的量子旋转门对量子概率幅值的收敛趋势进行改变。通过三个基本函数极值优化仿真与传统量子蚁群算法进行对比,证明算法性能较优。基于TSPLIB的仿真实验与其他几种算法进行比较,结果表明,算法具有较快的收敛速度,提高了解的全局性,有效避免了算法陷入局部最优。

量子蚁群算法求解多任务联盟问题

针对蚁群算法在求解多任务联盟问题(multi-task coalition problem,MTCP)时存在的求解精度不高、迭代次数多的不足,利用量子计算的并行性,提出了一种求解多任务联盟问题的量子蚁群算法.首先,利用量子叠加态给出了基于Agent的量子编码,使1个Agent能占据空间中的2个位置;其次,为使旋转角获得合适的大小和方向,提出了一种基于信息素的自适应修正旋转角调整策略;最后,通过对量子编码进行观测,给出了基于量子态的蚂蚁寻优策略.实验结果表明,与已有的算法相比,该算法不仅能获得更高质量的解,而且收敛速度也有显著的提高.

求解TSP的改进量子蚁群算法

将量子群进化算法(QEA)与蚁群系统(ACS)进行融合,提出一种新的量子蚁群算法(QACA)。该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素。该算法在全局寻优能力和种群多样性方面比蚁群算法有所改进,并结合TSP,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法是求解TSP的一种有效的算法。

基于自适应量子蚁群算法的石脑油裂解炉故障诊断

针对实际生产过程中缺乏故障数据,采用适合小样本问题的支持向量机对石脑油裂解炉进行故障诊断。为了消除高维数据及系统噪声对故障诊断的干扰,将量子编码引入蚁群算法,提出一种新的自适应量子蚁群算法进行故障特征选择以进一步提高诊断性能。数值仿真实验结果显示,提出的自适应量子蚁群算法具有更好的全局寻优性能;对石脑油裂解炉传感器故障的诊断结果表明自适应量子蚁群算法能快速、准确地搜索到关键故障特征,有效地提高了支持向量机故障诊断的正确率和鲁棒性。

一种改进的量子蚁群算法及其应用

将量子群进化算法(QEA)与蚁群系统(ACS)进行融合,提出一种新的量子蚁群算法(QACA)。该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素,从而在全局寻优能力和种群多样性方面比蚁群算法有所改进。结合旅行商问题(TSP),对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法具有较强的问题求解能力。

Job-Shop调度问题的量子蚁群算法求解

针对最小化最大完工时间的作业车间调度问题,提出了一种量子蚁群调度算法。该算法结合了量子计算中量子旋转门的量子信息和蚁群寻优的特点,通过作业车间调度问题的析取图表示,将原问题转换为求解析取图的关键路径,并利用量子蚁群算法进行求解。采用该算法对作业车间调度问题的基准数据进行测试,仿真结果表明了该算法的可行性和有效性。

求解旅行商问题的混合量子蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优和收敛速度慢的问题,提出一种新的求解旅行商问题的混合量子蚁群算法。该算法采用量子比特的概率幅对各路径上的信息素进行编码,采用量子旋转门及蚂蚁走过的路径对信息素进行更新,设计一种新的变换邻域准则。基于TSPLIB的仿真实验结果表明了该算法具有较快的收敛速度和求解精度。

用量子蚁群算法求解大规模旅行商问题

针对旅行商问题(TSP),提出了一种新的混合量子优化算法——量子蚁群算法.量子蚁群算法采用量子比特的概率幅表示蚂蚁的当前位置,采用量子旋转门更新蚂蚁的位置,选取国际通用的TSP实例库中多个实例进行测试.仿真实验表明,该算法具有很好的精确度和鲁棒性,可使搜索空间加倍,比传统的蚁群算法具有更好的种群多样性.

Steiner最小树问题的量子蚁群算法

Steiner最小树问题是组合优化中一个经典的NP难题,本文在蚁群算法的基础上结合量子计算提出一种求解欧氏Steiner最小树问题的量子蚁群算法.将量子比特、量子逻辑门以及Grover量子算法引入到蚁群算法中去,有效提高了算法的全局搜索能力,搜索速度也有显著的提高.一系列数据实例计算与比较表明,量子蚁群算法较蚁群算法在Steiner最小树问题的求解上具有更好的性能.

基于量子蚁群算法的图像分割

蚁群算法是一种新型的仿生进化算法,具有良好的鲁棒性、并行性及正反馈的特点,在许多领域得到了广泛应用,但蚁群算法存在收敛速度慢,容易陷入局部极值的缺点。基于此,提出将量子进化算法与蚁群算法相融合,算法将量子比特的两个概率幅看作是蚂蚁当前的位置信息,在蚂蚁数目相同时,可使搜索空间加倍,同时用量子非门来实现变异操作,避免算法陷入早熟。相比传统算法,在寻优过程中具有更好的种群多样性并有效克服了蚁群算法的早熟及停滞现象。并将此算法用于图像分割,实验结果表明,改进的量子蚁群算法有效解决了蚁群算法收敛速度慢和容易陷入局部极值的问题,而且在分割速度和精度上得到了较大提高。

量子蚁群算法在压力容器优化设计中的应用

建立压力容器的优化设计数学模型,利用一种新型的优化算法——量子蚁群算法对压力容器的主要参数进行优化设计。量子蚁群算法在蚁群算法的基础上引入量子理论,该方法能尽快搜索到较理想的下降方向,提高了算法的收敛速度。具体应用实例表明,基于量子蚁群算法的优化设计切实可行,显示量子蚁群算法在化工设备优化设计问题上的可用性。

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法.将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度.通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.

基于量子蚁群算法的网格任务调度研究

任务调度策略是网格计算的核心问题。在系统任务调度和资源分配中,提出一种基于量子蚁群算法的任务调度策略。算法将量子计算与蚁群算法相融合,通过对蚁群进行量子化编码并采用量子旋转门及非门操作,实现对任务自适应启发式的分配和优化。算法有效增强了种群的多样性、克服了遗传算法和蚁群算法的早熟收敛和退化现象。仿真实验中,分别与基于遗传算法和基于蚁群算法的任务调度策略相对比,结果表明算法有效缩短了任务调度的时间跨度,增强了网格系统的性能。

改进的量子蚁群算法求解带约束QoS组播路由

为了快速求解在带宽、延迟等约束下的最小代价组播路由树,并避免求解过程陷于局部最优,对量子蚁群算法进行了改进。改进算法采用量子旋转门对信息素进行更新,提出了一种动态调整旋转角的策略,并从理论上对其进行了证明。在求解服务质量组播路由时,将该策略融入蚁群算法中,提高了求解精确度。实验结果表明,该算法在服务质量组播路由优化中是高效的,性能优于蚁群算法和量子进化算法。

基于MapReduce的量子蚁群算法

量子蚁群算法是在蚁群算法的基础上结合量子计算而提出的,该算法具有较好的全局寻优能力和种群多样性。应用MapReduce的key/value编程模型,将量子蚁群算法并行化,提出了基于MapReduce的量子蚁群算法(MQACA),并将其部署到Hadoop云计算平台上运行。对0-1背包问题的测试结果证明,随着数据规模的扩大和并行程度的提高,MQACA具有良好的加速比和并行效率。

基于量子蚁群算法的医疗图像阈值分割算法

针对传统的医学图像分割方法存在分割线定位效果较差、分割耗时长、输出结果信噪比低的问题,提出基于量子蚁群算法的医疗图像阈值分割算法.首先,构建医疗图像的二值化特征采样模型,结合阈值检测方法对其进行信息增强和网格配对,建立最佳阈值区域生长模型;其次,在最大连通图区域中,根据背景像素强度定位边缘轮廓检测和邻域像素之间的位置,提取其中的病灶关联特征点;最后,利用量子蚁群算法进行多层特征分解,构建医疗图像阈值分割的多层特征分割模型,实现图像的阈值分割.实验结果表明,采用该算法进行医疗图像阈值分割过程的耗时较少,病变区域分割轮廓线定位的准确度较高,且输出结果的信噪比较高,有效提高了医疗图像分割的效果.

基于量子蚁群算法的带约束QoS多播路由

针对带约束服务质量多播路由在带宽、延迟等方面的需求,提出一种基于量子蚁群算法的多播路由优化方法。该方法结合量子计算和蚁群算法的特性,采用量子比特的概率幅表示蚂蚁当前位置信息,设计一种动态调整旋转角策略对蚂蚁信息素进行更新,使蚂蚁能够快速寻找到满足约束的可行路径,并避免陷入局部最优。仿真实验结果表明,该算法在寻优能力和收敛速度上表现较好。

量子蚁群算法现状综述

介绍了量子蚁群算法的发展、基本理论和方法。从量子编码、量子门改进、旋转角调整、加入新算子等几个角度论述了量子蚁群算法的改进方法,并总结了量子蚁群算法的应用领域。最后提出量子蚁群算法的发展方向。