Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization
TL;DR 精炼摘要
本文提出了一种新的量子启发式进化算法(QEA),该算法利用量子比特和叠加态的原理,在组合优化问题中取得显著效果。与传统遗传算法相比,QEA在小规模种群下表现出色,避免了早熟收敛,展示了量子计算在进化算法中的潜力。
摘要
This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit for probabilistic representation. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. Experiments on the knapsack problem demonstrate that QEA performs well, even with a small population, without premature convergence compared to conventional genetic algorithms.
思维导图
论文精读
中文精读
1. 论文基本信息
1.1. 标题
量子启发式进化算法及其在组合优化问题中的应用 (Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization)
1.2. 作者
Kuk-Hyun Han 和 Jong-Hwan Kim
1.3. 发表期刊/会议
IEEE Transactions on Evolutionary Computation。这是一个在进化计算领域享有盛誉和高影响力的顶级期刊,发表的论文通常代表了该领域的重要进展和高质量研究。
1.4. 发表年份
2002年
1.5. 摘要
本文提出了一种新颖的进化算法,称为量子启发式进化算法 (Quantum-Inspired Evolutionary Algorithm, QEA)。该算法基于量子计算的概念和原理,如量子比特 (quantum bit) 和叠加态 (superposition of states)。与传统进化算法类似,QEA 也通过个体表示、评估函数和种群动态来表征。然而,与二进制、数值或符号表示不同,QEA 使用 Q-比特 (Q-bit) 进行概率表示,并引入 Q-门 (Q-gate) 作为变异算子,以驱动个体趋向更优的解决方案。在背包问题 (knapsack problem) 上的实验结果表明,与传统遗传算法 (conventional genetic algorithms) 相比,即使在小规模种群下,QEA 也能表现出色,且没有出现早熟收敛 (premature convergence) 现象。
1.6. 原文链接
/files/papers/691e79048106199151d7ea11/paper.pdf (发布状态:已正式发表)
2. 整体概括
2.1. 研究背景与动机
进化算法 (Evolutionary Algorithms, EAs) 作为鲁棒的全局优化方法,在各种问题中显示出广泛适用性。EAs 的性能高度依赖于其组成部分,如个体表示、评估函数和种群动态(包括变异算子和选择机制)之间的平衡,以实现探索 (exploration) 和利用 (exploitation) 的良好权衡。然而,传统的 EAs,如遗传算法 (Genetic Algorithms, GAs)、进化规划 (Evolutionary Programming, EP) 和进化策略 (Evolution Strategies, ES),在某些情况下可能面临挑战,例如需要较大的种群规模才能有效探索搜索空间,或者容易陷入早熟收敛。
近年来,量子计算 (quantum computing) 领域的快速发展,特别是量子比特和叠加态等概念的提出,为解决经典计算中的难题提供了新的视角。一些研究开始探索将进化计算与量子计算相结合,例如使用自动编程技术生成新的量子算法,或将量子力学原理(如干涉、相干)引入进化算法中。
本文的动机正是基于这种背景,旨在通过借鉴量子计算的核心概念,设计一种新型的进化算法。具体来说,论文试图解决的问题是:如何在进化算法中引入一种更有效的信息表示和变异机制,从而在保持种群多样性的同时,加速收敛并避免早熟收敛,尤其是在种群规模较小的情况下,以适应实时应用的需求。
2.2. 核心贡献/主要发现
本文的核心贡献在于提出了一种新颖的量子启发式进化算法 (Quantum-Inspired Evolutionary Algorithm, QEA),其主要发现和特点包括:
- 提出 Q-比特 (Q-bit) 表示: QEA 使用
Q-bit作为信息的基本单位,其通过概率幅 来表示一个比特是 0 或 1 的概率,从而实现了对多个状态的线性叠加 (linear superposition of states) 的表示。这种概率表示方法极大地增强了种群多样性 (population diversity),使得一个Q-bit个体能够同时代表搜索空间中的多个二进制解。这与传统的二进制、数值或符号表示形成了鲜明对比。 - 引入 Q-门 (Q-gate) 作为变异算子: 论文设计了
Q-gate作为QEA的变异算子,特别是使用旋转门 (rotation gate)。Q-gate通过调整Q-bit的概率幅,逐步驱动个体向更优的解决方案收敛。这种机制允许QEA在搜索过程中动态地调整探索和利用的平衡。 - 平衡探索与利用 (Balance between Exploration and Exploitation): 实验结果表明,
QEA具有内在的机制来平衡搜索空间的探索和对已知优解的利用。初始阶段,Q-bit个体以等概率表示所有可能状态,实现全局搜索 (global search)。随着算法的进行,Q-gate逐渐引导Q-bit的概率幅趋向 0 或 1,从而转向局部搜索 (local search)。 - 在背包问题上的优越性能: 在经典的组合优化问题——背包问题 (knapsack problem) 上的实验验证了
QEA的有效性和适用性。- 高性能和快速收敛:
QEA相比传统遗传算法,在收敛速度和最终获得的利润方面表现显著更优。 - 避免早熟收敛:
QEA能够有效避免传统GA常见的早熟收敛问题,即使在迭代后期也能持续提升解的质量。 - 小种群规模下的有效性:
QEA即使在种群规模非常小(例如只有一个Q-bit个体)的情况下,也能取得良好的性能,这对于实时应用或计算资源受限的场景具有重要意义。
- 高性能和快速收敛:
3. 预备知识与相关工作
3.1. 基础概念
理解本文需要对进化算法和量子计算的基本概念有一定的了解。
-
进化算法 (Evolutionary Algorithms, EAs):
EAs是一类受生物进化过程启发的优化算法,通过模拟自然选择、遗传、变异等机制来搜索问题的最优解。EAs的核心组成部分包括:- 个体表示 (Representation of the individual): 如何将问题的解编码成算法可以操作的形式(如二进制串、数值向量)。
- 评估函数 (Evaluation function): 也称适应度函数 (fitness function),用于衡量个体解的质量。
- 种群动态 (Population dynamics): 包括种群大小 (population size)、变异算子 (variation operators,如交叉
crossover和变异mutation)、亲代选择 (parent selection)、繁殖与遗传 (reproduction and inheritance) 以及生存竞争方法 (survival competition method)。
- 常见的
EAs包括:- 遗传算法 (Genetic Algorithms, GAs): 由 Fraser、Bremermann 和 Holland 发展,通常使用二进制串表示个体,通过交叉和变异操作产生后代。
- 进化规划 (Evolutionary Programming, EP): 由 Fogel 发展,侧重于行为和突变。
- 进化策略 (Evolution Strategies, ES): 由 Rechenberg 和 Schwefel 发展,主要应用于连续优化问题,通过高斯突变和选择来搜索。
-
量子计算 (Quantum Computing) 概念:
- 量子比特 (Quantum bit 或 qubit): 是量子计算机中存储信息的最小单位。与经典比特 (classic bit) 只能是 0 或 1 不同,
qubit可以处于 0 态、1 态,或者两者的任意叠加态 (superposition of states)。- 一个
qubit的状态可以表示为: 其中, 和 是复数,称为概率幅 (probability amplitudes)。 表示qubit被测量为 '0' 态的概率, 表示qubit被测量为 '1' 态的概率。 - 归一化条件 (Normalization condition) 保证了总概率为 1:
- 一个
- 叠加态 (Superposition of states):
qubit同时处于 '0' 和 '1' 两种状态的可能性,直到被测量。一个由 个qubit组成的系统可以同时表示 种状态。 - 量子门 (Quantum gate): 用于改变
qubit状态的操作。它们是可逆的 (reversible) 酉算子 (unitary operator)。常见的量子门包括NOT gate、controlled NOT gate、rotation gate(旋转门) 和Hadamard gate(哈达玛门) 等。 - 测量/观察与坍缩 (Measurement/Observation and Collapse): 在观察
qubit状态时,其叠加态会“坍缩” (collapse) 到一个确定的经典态(0 或 1),并得到相应的测量结果。
- 量子比特 (Quantum bit 或 qubit): 是量子计算机中存储信息的最小单位。与经典比特 (classic bit) 只能是 0 或 1 不同,
-
组合优化问题 (Combinatorial Optimization Problem):
- 这类问题涉及从有限的离散对象集合中选择一个子集,以优化某个目标函数。通常这类问题的搜索空间巨大,难以通过穷举法解决。
- 背包问题 (Knapsack Problem): 一个经典的组合优化问题。给定一系列物品,每件物品都有其重量和价值。目标是在不超过背包总容量的前提下,选择物品使得总价值最大化。本文主要关注 0-1 背包问题,即每件物品只能选择放入或不放入。
3.2. 前人工作
- 经典进化算法的奠基:
- Fraser [1]、Bremermann [2] 和 Holland [3] 奠定了遗传算法 (GAs) 的基础。
- Fogel [4] 发展了进化规划 (EP)。
- Rechenberg [5] 和 Schwefel [6] 发展了进化策略 (ES)。
- 量子计算的早期发展:
- Benioff [7] 在 20 世纪 80 年代初提出了量子力学计算机的概念。
- Deutsch [8] 在 80 年代末形式化了量子力学计算机的描述。
- 著名量子算法:
- Shor 的量子因数分解算法 [9], [10] 和 Grover 的数据库搜索算法 [11], [12] 展示了量子计算机在特定问题上超越经典计算机的强大能力。
- 进化计算与量子计算的融合尝试:
- 自 90 年代末,研究开始将进化计算与量子计算相结合。主要分为两类:
- 利用自动编程生成新量子算法: 例如 Spector 等 [13] 使用遗传编程 (genetic programming) 寻找优于经典算法的量子
AND/OR算法。 - 经典计算机上的量子启发式进化计算: 旨在借鉴量子力学原理(如干涉、相干)来改进经典进化算法。Narayanan 和 Moore [14], [15] 在交叉算子中引入了干涉概念。
- 利用自动编程生成新量子算法: 例如 Spector 等 [13] 使用遗传编程 (genetic programming) 寻找优于经典算法的量子
- 自 90 年代末,研究开始将进化计算与量子计算相结合。主要分为两类:
- 作者自身工作: Han 和 Kim 之前的工作 [16], [17] 也探索了量子启发式遗传算法在组合优化问题中的应用。
3.3. 技术演进
领域技术演进可以概括为从经典的、确定性或基于概率分布的个体表示和变异操作,转向借鉴量子力学中“叠加”和“概率幅”思想的表示方法。最初的进化算法专注于模拟生物进化过程中的遗传和变异,通常使用二进制串或实数向量来直接编码解。这种直接编码方式在复杂搜索空间中可能导致种群多样性不足或收敛速度慢。量子计算的兴起为进化算法带来了新的灵感,特别是 qubit 的叠加态特性,可以提供一种更紧凑且多样性更强的解表示方式。本文的工作正处于这种演进的脉络中,通过引入 Q-bit 这种概率表示,旨在克服传统 EAs 在多样性和收敛性方面的局限。
3.4. 差异化分析
本文提出的 QEA 与先前将量子概念(如干涉)引入现有进化算子(如交叉)的方法有显著区别:
- 全新的个体表示:
QEA并没有尝试修改传统遗传算法的二进制串或实数表示,而是提出了一种全新的、基于量子比特概念的Q-bit概率表示。这个Q-bit可以同时以不同的概率幅表示 0 和 1,从而一个Q-bit个体能够概率性地表示搜索空间中的多个解决方案的叠加态。这从根本上增强了种群的多样性,而不是通过传统的变异和交叉操作来间接维护多样性。 - 新的变异算子: 针对
Q-bit这种特殊表示,本文引入了Q-gate(特别是旋转门)作为其变异算子。Q-gate直接作用于Q-bit的概率幅,以引导其向更优解的方向演化。这与传统GA中的位翻转变异或算术变异有本质不同,后者直接改变个体的值,而Q-gate改变的是个体状态的概率分布。 - 内在的探索与利用平衡:
QEA的Q-bit表示使其能够从初始阶段的均匀叠加(全局探索)逐渐演化到特定解的高概率状态(局部利用),这种探索与利用的平衡是算法的内在机制,而非通过调整多个超参数或复杂策略来外部控制。 - 非量子计算机运行: 尽管
QEA灵感来源于量子计算,但它是一种在经典计算机上运行的进化算法,并不需要实际的量子计算机硬件。这一点与一些旨在为量子计算机设计算法的研究方向不同。
4. 方法论
4.1. 方法原理
量子启发式进化算法 (QEA) 的核心思想是利用量子计算中的 qubit 和叠加态概念,为进化算法设计一种新的个体表示和变异机制。传统的进化算法通常用确定性的二进制串或实数向量来表示个体,每个个体都代表搜索空间中的一个特定解。当种群规模有限时,这容易导致种群多样性不足,从而陷入局部最优或早熟收敛。
QEA 引入 Q-bit 作为信息的基本单位,一个 Q-bit 并非确定地为 0 或 1,而是以一定的概率幅同时处于 0 和 1 的叠加态。因此,一个由多个 Q-bit 组成的 Q-bit 个体能够概率性地代表搜索空间中的 个(其中 是 Q-bit 的数量)二进制解决方案的叠加。这种表示方式极大地增加了种群的多样性,因为单个 Q-bit 个体就包含了关于多个可能解的信息。
为了驱动 Q-bit 个体向更好的解决方案演化,QEA 引入了 Q-gate 作为变异算子。Q-gate 作用于 Q-bit 的概率幅,通过旋转操作调整 0 和 1 状态的概率,从而引导 Q-bit 个体向已知最优解的方向收敛。算法通过周期性地“观察” Q-bit 个体来生成经典的二进制解,评估这些解的适应度,并根据适应度信息更新 Q-bit 的概率幅。这种机制使得 QEA 能够在初期进行广泛的全局探索,并在发现有希望的区域后逐渐将搜索重心转向局部利用,实现了探索与利用的动态平衡。
4.2. 核心方法详解
4.2.1. Q-比特表示 (Q-bit Representation)
-
定义 1:Q-比特 (Q-bit)
Q-bit是QEA中信息的最小单位,由一对复数 定义,表示为一个列向量: 其中,归一化条件 必须满足。 表示Q-bit被观察为 '0' 状态的概率,而 表示Q-bit被观察为 '1' 状态的概率。一个Q-bit可以是 '0' 态、'1' 态,或者两者的线性叠加态。 -
定义 2:Q-比特个体 (Q-bit individual) 一个由 个
Q-bit组成的Q-bit个体定义为一系列Q-bit的组合: 其中,对于每个Q-bit(从 1 到 ),都满足 。Q-bit表示的主要优势在于它能够表示状态的线性叠加。例如,一个三Q-bit系统,如果每个Q-bit都具有特定的概率幅,它可以同时包含 种二进制状态的信息。这意味着,与二进制表示需要八个独立的二进制串才能表示所有八种状态不同,一个Q-bit个体就能以概率的形式包含这些信息,从而提供了更好的种群多样性。
4.2.2. QEA 算法流程 (QEA Algorithm Procedure)
QEA 的整体结构如下图所示。
该图像是 QEA 的整体结构示意图。图中展示了最佳解的选择、局部迁移和全局迁移过程,以及个体的选择和观察机制。QEA 引入了 Q-gate 作为变异操作符,以更新状态并引导个体接近更优解。
图 1. QEA 的整体结构。
QEA 算法的详细步骤如下:
-
初始化 (Initialization):
- 步骤 i) 初始化
Q(t): 在初始世代 时,种群 中的所有Q-bit个体 的 和 值都被初始化为 。这意味着每个Q-bit都以 的概率处于 '0' 态和 '1' 态。 其中, 是由二进制字符串 表示的第 个状态, 根据 或 的概率选择 0 或 1。这种初始化确保了每个Q-bit个体最初以相同的概率表示所有可能的 种状态,相当于进行随机搜索。 - 步骤 ii) 通过观察
Q(t)的状态生成P(t): 对于种群 中的每个Q-bit个体 ,通过“观察”其Q-bit的状态来生成一个二进制解决方案 。具体方法是,对于每个Q-bit的每个位置 ,根据 和 的概率随机选择 0 或 1。需要注意的是,这并非量子计算机中物理上的坍缩,而是在经典计算机上模拟概率抽样过程。 - 步骤 iii) 评估
P(t): 计算种群 中每个二进制解决方案 的适应度值。 - 步骤 iv) 存储
P(t)中的最佳解决方案到B(t): 将 中表现最好的解决方案选出,并存储到 中。最初, 与 相同。
- 步骤 i) 初始化
-
迭代循环 (While Loop):
-
步骤 v) 通过观察
Q(t-1)的状态生成P(t): 在每个新的世代 ,重复步骤 ii),从上一个世代Q(t-1)的Q-bit个体中观察生成新的二进制解决方案种群P(t)。 -
步骤 vi) 评估
P(t): 重复步骤 iii),评估P(t)中每个二进制解决方案的适应度值。 -
步骤 vii) 使用 Q-门更新
Q(t): 这是QEA的核心变异操作。根据当前生成的二进制解决方案及其适应度,以及当前最佳解决方案,使用Q-gate来更新Q-bit个体Q(t-1)中的概率幅,从而生成新的Q(t)。- 定义 3:Q-门 (Q-gate)
Q-gate是QEA的变异算子,其操作后的Q-bit必须满足归一化条件 ,其中 和 是更新后的Q-bit值。 本文中使用的是旋转门 (rotation gate): 其中 是第 个Q-bit的旋转角度,其符号决定了Q-bit是趋向 '0' 态还是 '1' 态。 的具体值需根据应用问题设计。除了旋转门,NOT gate(非门)、controlled NOT gate(受控非门) 或Hadamard gate(哈达玛门) 也可作为Q-gate使用,它们各有特点:非门可以反转 0 和 1 的概率,用于跳出局部最优;受控非门适用于比特间有强依赖性的问题;哈达玛门适用于利用Q-bit相位信息的算法。
- 定义 3:Q-门 (Q-gate)
-
步骤 viii) 存储
B(t-1)和P(t)中的最佳解决方案到B(t): 从前一世代的最佳解决方案集合B(t-1)和当前世代的二进制解决方案种群P(t)中选择最佳的解决方案,存储到新的最佳解决方案集合B(t)中。 -
步骤 ix) 存储
B(t)中的最佳解决方案 : 从B(t)中选出整体最佳的解决方案 。如果它比当前存储的最佳解更优,则进行替换。 -
步骤 x) 迁移 (Migration): 如果满足迁移条件 (migration-condition),则执行迁移操作。
- 定义 4:迁移 (Migration)
QEA中的迁移定义为将B(t)中的最佳解 或整体最佳解 复制到B(t)的过程。- 全局迁移 (Global migration): 将所有
B(t)中的解决方案都替换为整体最佳解 。 - 局部迁移 (Local migration): 将
B(t)中部分解决方案替换为它们中间的最佳解。 迁移机制旨在引入额外的概率变异,以帮助算法跳出局部最优或加速收敛。
- 全局迁移 (Global migration): 将所有
- 定义 4:迁移 (Migration)
-
-
终止条件 (Termination Condition): 循环继续直到满足终止条件,例如达到最大世代数 (
MAX_GEN)。论文还提到,终止条件也可以基于最佳解决方案的概率Prob(b),例如当Prob(b)大于某个阈值 时停止。Prob(b)可通过Q-bit个体中所有对应比特概率的乘积计算。
4.2.3. 背包问题的 QEA (QEA for the Knapsack Problem)
本文将 QEA 应用于 0-1 背包问题,并加入了修复过程以处理容量约束。
-
背包问题描述: 目标是最大化利润 : 受限于背包容量 : 其中, 是一个二进制向量, 为 0 或 1, 是物品 的利润, 是物品 的重量。如果 ,则选择物品 。
-
QEA 流程(针对背包问题):
QEA针对背包问题的流程与通用QEA流程基本一致,但增加了repair(修复) 步骤。Procedure QEA for the Knapsack Problem begin t ← 0 initialize Q(t) make P(t) by observing the states of Q(t) repair P(t) // 新增修复步骤 evaluate P(t) store the best solutions among P(t) into B(t) while (t < MAX_GEN) do begin t ← t + 1 make P(t) by observing the states of Q(t-1) repair P(t) // 新增修复步骤 evaluate P(t) update Q(t) store the best solutions among B(t-1) and P(t) into B(t) store the best solution b among B(t) if (migration-period) then migrate b or b_j^t to B(t) globally or locally, respectively end end -
生成二进制解的 过程: 此过程用于从
Q-bit个体中生成二进制字符串。对于每个Q-bit个体 和其对应的二进制字符串 :Procedure Make Ψ(x) begin i ← 0 while (i < m) do begin i ← i + 1 if random[0, 1) < |β_i|^2 then // 如果随机数小于|β_i|^2,则设置为1 x_i ← 1 else // 否则设置为0 x_i ← 0 end end这里 表示第 个
Q-bit被观察为 '1' 态的概率。 -
修复二进制解的 过程: 当生成的二进制字符串 违反背包容量约束时(即 ),需要进行修复。
Procedure Repair Ψ(x) begin knapsack-overfilled ← false if (sum_{i=1}^{m} w_i x_i > C) then knapsack-overfilled ← true while (knapsack-overfilled) do // 移除物品直到容量满足 begin select an ith item from the knapsack // 从背包中选择一个物品 x_i ← 0 // 将其移除 if (sum_{i=1}^{m} w_i x_i <= C) then knapsack-overfilled ← false end while (not knapsack-overfilled) do // 尝试添加物品直到容量再次超过或无法再添加 begin select a jth item from the knapsack // 从未选择的物品中选择一个 x_j ← 1 // 尝试添加 if (sum_{i=1}^{m} w_i x_i > C) then // 如果添加后超载 knapsack-overfilled ← true end x_j ← 0 // 移除最后一个导致超载的物品 end注意: 原文中的 过程描述有些歧义,特别是第二个
while循环的select a jth item from the knapsack,结合上下文应理解为从未选择的物品中选择,且在发现超载后将其移除。这里为了清晰性稍作解释性调整,以符合修复策略的逻辑。 -
更新
Q-bit的Update (q)过程: 此过程使用旋转门 来更新Q-bit个体 中的 。其中, 是原始的概率幅, 是更新后的概率幅。
Q-bit旋转门的极坐标图如下所示:
该图像是图表,展示了 Q-bit 个体的旋转门的极坐标图。图中标记了 ( heta_i', eta_i') 和 ( heta_i, eta_i) 之间的角度变化 ,以及 Q-bit 在单位圆上的位置。图 2. Q-bit 个体旋转门的极坐标图。
旋转角度 的确定是关键,它通过一个查找表 (lookup table) (Table I) 来确定,该表基于当前二进制解 的适应度 与最佳解 的适应度 之间的比较,以及当前比特 和最佳比特 的值。
以下是原文 Table I 的内容,用于确定 :
xi bi f(x) ≥ f(b) ∆θi 0 0 false θ1 0 0 true θ2 0 1 false θ3 0 1 true θ4 1 0 false θ5 1 0 true θ6 1 1 false θ7 1 1 true θ8 表 1. 查找表,其中 是利润, 和 分别是最佳解 和二进制解 的第 个比特。在背包问题中,使用了 , , , , , , , 。
Update (q)过程的具体逻辑:Procedure Update (q) begin i ← 0 while (i < m) do begin i ← i + 1 determine Δθ_i with the lookup table // 根据查找表确定Δθ_i obtain (α_i', β_i') from the following: if (q_i is located in the first/third quadrant) then // 如果Q-bit位于第一或第三象限 [α_i' β_i']^T = U(Δθ_i) [α_i β_i]^T else // 如果Q-bit位于第二或第四象限 [α_i' β_i']^T = U(-Δθ_i) [α_i β_i]^T end q ← q' // 更新Q-bit个体 end这个过程中,
Q-bit的象限 (quadrant) 决定了旋转方向的符号。例如:- 如果 且 ,同时 (即 为
false):- 若
Q-bit在第一或第三象限(如 同号),则 使用 (正值),目的是增加 状态的概率(即增大 )。 - 若
Q-bit在第二或第四象限(如 异号),则 使用 (负值),同样目的是增加 状态的概率。
- 若
- 如果 且 ,同时 (即 为
false):- 若
Q-bit在第一或第三象限,则 使用 (负值),目的是增加 状态的概率(即增大 )。 - 若
Q-bit在第二或第四象限,则 使用 (正值),同样目的是增加 状态的概率。
- 若
- 对于那些 为
true的情况(即当前解不差于最佳解),或者 和 相同的情况,建议将 设为 0,以避免不必要的扰动。 - 的大小影响收敛速度,但过大可能导致发散或早熟收敛。建议范围为 到 。
- 如果 且 ,同时 (即 为
5. 实验设置
5.1. 数据集
实验使用了强相关 (strongly correlated) 的数据集来测试算法在背包问题上的性能。
- 物品重量 : 均匀随机分布在
[1, 10]之间。 - 物品利润 : 与重量相关,。
- 背包容量 : 设置为所有物品总重量的一半。
- 数据是未排序的。
- 问题规模: 考虑了三种不同规模的背包问题:100 个物品 (items)、250 个物品和 500 个物品。
5.2. 评估指标
论文主要通过以下指标来评估和比较算法性能:
-
最佳利润 (Best Profit): 在指定世代数(例如 1000 代)内找到的最佳解决方案的利润值。这是衡量算法优化能力的核心指标。
-
平均最佳利润 (Mean of Best Profits): 算法在多次运行(例如 30 次)后,每次运行得到的最佳利润的平均值。这提供了算法性能的统计稳定性。
-
平均种群平均利润 (Mean of Average Profits of Population): 在多次运行中,每个世代种群中所有个体利润的平均值的平均值。这个指标可以反映种群整体的演化趋势和多样性维护情况。
-
标准差 (Standard Deviation, ): 对最佳利润结果的标准差,反映了算法运行结果的稳定性或变异性。
-
单次运行耗时 (Elapsed Time per Run, t): 算法完成一次运行所需的时间,衡量算法的计算效率。
针对评估指标的标准化计算公式:
-
利润 : 概念定义:利润是根据选定物品的价值之和,用来衡量一个解决方案的优劣。在背包问题中,目标是最大化利润。 数学公式: 符号解释:
- :解决方案 的总利润。
- :物品的总数量。
- :第 个物品的利润。
- :二进制变量,如果第 个物品被选中则为 1,否则为 0。
-
标准差 : 概念定义:标准差衡量数据集的离散程度。在这里,它用于评估算法在多次运行中找到的最佳利润的稳定性。标准差越小,表明算法结果越稳定。 数学公式: 符号解释:
- :标准差。
- :运行次数(例如 30 次)。
- :第 次运行得到的结果(例如最佳利润)。
- :所有运行结果的平均值。
5.3. 对比基线
论文将 QEA 的性能与三种主要类型的传统遗传算法 (Conventional Genetic Algorithms, CGAs) 进行了比较:
-
基于惩罚函数 (Penalty Functions) 的 GA:
- 这类
GA将违反约束的解决方案进行惩罚,使其适应度降低。 - 利润函数 包含了惩罚项 :
- 考虑了两种惩罚函数:
- 对数惩罚 (Logarithmic Penalty)
Pen1: - 线性惩罚 (Linear Penalty)
Pen2: - 其中 是一个惩罚系数,通常取为 (物品利润重量比的最大值)。当 (超载) 时,惩罚项生效。
- 对数惩罚 (Logarithmic Penalty)
- 这类
-
基于修复方法 (Repair Methods) 的 GA:
- 这类
GA允许生成违反约束的解决方案,然后通过一个修复算法将其转换为可行解。 - 利润函数 基于修复后的向量 :
- 考虑了两种修复算法,主要区别在于选择移除物品的策略:
- 随机修复 (Random Repair)
Rep1: 随机选择一个物品从背包中移除,直到容量约束满足。 - 贪婪修复 (Greedy Repair)
Rep2: 将背包中的所有物品按其利润重量比降序排序,每次选择比率最低的物品移除,直到容量约束满足。
- 随机修复 (Random Repair)
- 在实验中,原始染色体以 5% 的概率被修复。
- 这类
-
基于解码器 (Decoders) 的 GA:
- 这类
GA使用一种间接编码方式,染色体本身不是直接的解决方案,而是通过一个解码过程生成解决方案。 Dec(随机解码):染色体是 个整数的向量,通过引用物品列表 来解码,物品在列表中的顺序对应输入文件中的随机顺序。- 注意: 这种方法在参数搜索阶段因“进化时间过长且性能不如其他
CGA”而被排除在主要比较之外。
- 这类
组合方法:
论文还测试了结合惩罚函数和修复方法的 CGA 变体,例如 (线性惩罚与随机修复) 和 (线性惩罚与贪婪修复)。最终在对比中, (P2R2) 被认为是表现最好的 CGA。
实验参数设置:
- QEA 参数:
- 种群大小:QEA1 (1 个个体), QEA2 (10 个个体), QEA3 (10 个个体)。
- 迁移机制:QEA2 使用每 1 代进行全局迁移;QEA3 使用每 100 代进行全局迁移,每 1 代进行局部迁移 (local migration)。
- 旋转角度 的参数:, ,其余 值()设为 0。这些值是通过对 的测试后选定的。
- CGA 参数:
- 种群大小:10 和 50。
- 通过对突变率 (mutation) (0.001, 0.01, 0.05, 0.1) 和两点交叉率 (two-point crossover) (0.001, 0.01, 0.05, 0.1, 0.3, 0.5) 的广泛测试 (24 种参数设置 6 种 CGA 2 种种群大小 = 288 组实验),最终选择突变率和交叉率都为 0.01 作为
CGA的参数。
- 运行次数和最大世代数: 所有实验均进行 30 次独立运行,最大世代数为 1000。
6. 实验结果与分析
6.1. 核心结果分析
6.1.1. 旋转角度参数的验证
论文首先通过实验验证了 QEA 中旋转角度 的参数设置。在第 III 节中,根据直觉将 设为正值, 设为负值,其余设为 0。为了验证这一设置,对一个 100 物品的背包问题,使用 QEA1 (单个 Q-bit 个体) 进行了 种 向量(每个 可以取 )的穷举实验。
以下是原文 Figure 6 的结果,展示了参数选择的逐步过程:
该图像是图表,展示了不同参数下量子启发演化算法的利润变化情况。图中包括六个子图,分别标记为(a)至(f),每个子图展示了在不同值(如和)下的利润波动。纵轴为利润,横轴为时间,显示了算法在不同条件下的表现及稳定性。
图 6. 和 的利润值。 和 分别是 和 。
实验结果表明:
- 当 为
true时(对应 ),这些角度参数对结果影响不大,可以设为任意值(例如 0)。 - 当 为
false时:- 将 和 设为 0 效果更好。
- 将 设为正值 (), 设为负值 () 效果更好。
- 最终,实验结果验证了直觉推理,即 可以设置为 ,其中 为正数, 为负数,
*可以是0, p, n中的任意一个。在后续实验中,具体选择了 和 。
6.1.2. QEA 与 CGA 性能对比
主要实验结果汇总在 Table II 中,比较了 QEA (QEA1, QEA2, QEA3) 和表现最佳的传统遗传算法 P2R2 (即 )。
以下是原文 Table II 的结果:
| CGAs | QEAs | ||||||
| P2R2(10) | P2R2(50) | QEA1(1) | QEA2(10) | QEA3(10) | |||
| 100 | b.m.W. | 597.6587.8577.6 | 602.2593.6582.6 | 597.7591.8582.5 | 612.7606.3597.7 | 612.7609.5607.6 | |
| σ | 5.227 | 4.958 | 4.840 | 3.308 | 2.404 | ||
| t | 0.154 | 0.786 | 0.021 | 0.199 | 0.203 | ||
| 250 | b.m.W. | 1455.01436.71415.2 | 1472.51452.41430.1 | 1480.2 | 1515.2 | 1525.21518.71515.2 | |
| 1464.5 | 1508.1 | ||||||
| 1445.1 | 1495.2 | ||||||
| σ | 11.377 | 10.324 | 9.554 | 5.427 | 0.357 | 0.055 | 0.558 |
| 500 | 2828.12807.22781.0 | 2899.72876.42836.2 | 3025.83008.02996.1 | ||||
| 14.142 | 12.832 | 8.039 | |||||
| 0.706 | 0.117 | 1.258 | |||||
表 2. 背包问题的实验结果:物品数量为 100, 250 和 500,最大世代数为 1000,运行次数为 30。括号中的值是种群大小。P2R2 表示由 实现的算法,b.m.W. 表示最佳 (best)、平均 (mean) 和最差 (worst) 利润。t (seconds/run) 和 分别表示每次运行的耗时和标准差。
主要观察:
- QEA 的卓越性能: 对于 250 和 500 物品的复杂问题,
QEA(特别是 QEA2 和 QEA3) 明显优于所有CGA变体 (包括表现最佳的P2R2)。QEA找到了更高的最佳利润,且平均利润也显著更高。 - 小种群优势:
QEA即使在非常小的种群规模下 (QEA1 仅 1 个个体,QEA2/QEA3 仅 10 个个体) 也能表现出色。相比之下, (50 个个体) 在 100 物品问题上性能与 QEA1 (1 个个体) 相近,但在更复杂问题上则被 QEA1 甚至 QEA2/QEA3 显著超越。这表明QEA的Q-bit表示能有效利用信息,减少对大种群的依赖。 - 计算效率:
QEA在多数情况下也表现出更高的计算效率,例如 QEA1 在所有问题规模下都比 和 运行时间更短。QEA2 和 QEA3 的运行时间与 相当,但取得了更好的结果。 - 稳定性:
QEA(特别是 QEA2 和 QEA3) 的标准差通常小于CGA,表明其结果更为稳定。
6.1.3. 收敛行为分析
以下是原文 Figure 5 的结果,比较了 QEA 和 CGA 在背包问题上的收敛曲线:
该图像是图表,展示了在背包问题中,通过简单计算获得的1024个案例的利润值。纵轴表示背包的利润值,横轴表示从十个项目中选择的1024个案例的编号。其中,第100个案例的最佳利润值被标记为O。
图 5. QEA 和 CGA 在背包问题上的比较。CGA 为 。
主要观察:
- QEA 更快的收敛速度:
QEA算法在收敛速度上明显快于CGA。在相同的世代数内,QEA能够达到更高的利润值。 - 避免早熟收敛: 传统
CGA的平均利润在早期阶段上升后很快趋于平稳,显示出早熟收敛的趋势。而QEA即使在 1000 代之后,其平均利润仍在持续增长,表明它能有效避免早熟收敛,继续探索并发现更好的解决方案。 - QEA1、QEA2、QEA3 的对比:
- QEA1 由于只有单个个体,其收敛速度相对 QEA2 和 QEA3 较慢。
- QEA3 初始收敛速度略慢于 QEA2,但在大约 500 代之后超越了 QEA2,并在最终利润上表现最佳。这归因于 QEA3 同时采用了全局迁移 (每 100 代) 和局部迁移 (每代),这有助于增加种群多样性,从而找到更好的全局最优解。
6.1.4. QEA 特性探究 (通过 10 物品背包问题)
为了深入了解 QEA 的内在工作机制,论文使用一个简单的 10 物品背包问题进行了分析。对于 10 个物品,共有 种可能的组合。
以下是原文 Figure 7 的结果,展示了 10 物品背包问题的利润分布:
该图像是图表,展示了在特定案例编号下的概率分布情况。左侧的图表对应于第一个实验,右侧对应第二个实验。两者均显示在某些案例上概率值显著高于其他案例,说明量子启发进化算法的有效性。
图 7. 通过简单计算得到的 10 物品背包问题中 1024 个案例的利润值。纵轴为背包的利润值,横轴为从十个物品中选择的 1024 个案例的编号。满足容量约束的最佳利润以 O 标记。
在这个问题中,满足容量约束的最佳利润为 62.192938,对应第 127 个方案。比此利润更高的方案都违反了容量约束。
以下是原文 Figure 8 的结果,展示了 QEA1 (单个 Q-bit 个体) 在不同世代下 1024 种解决方案的概率分布:
该图像是多个概率分布图,展示了不同案例编号下的概率变化,标记为(a)至(f)。这些图表显示了收敛趋势和波动性,表明量子启发的进化算法在解决组合优化问题时的性能表现。
图 8. Q-bit 个体在世代 10, 20, 30, 40, 50, 100, 200, 300 时 1024 种解决方案的概率。
分析总结:
- 初始随机搜索 (Generation 0): 如图 8(a) 所示(虽然图中未直接显示 Generation 0,但根据算法描述),所有 1024 种解决方案的概率都是均匀的 (1/1024 = 0.001),此时
QEA进行的是纯粹的随机搜索。 - 初期探索与利润分布相似 (Generation 10): 在第 10 代,1024 种解决方案的概率分布开始与图 7 所示的利润分布呈现相似的模式。这表明,即使只有一个
Q-bit个体,它也能够有效地感知并反映出搜索空间中不同解决方案的潜在价值。 - 转向局部搜索 (Generation 20-50): 随着世代的推进 (图 8(b)-(e),第 20 到 50 代),具有较高利润的解决方案的概率显著增加,形成明显的峰值。这表示算法开始将搜索重点从全局探索转向对有希望区域的局部利用。
- 集中收敛 (Generation 100-300): 在第 100 代和 200 代 (图 8(f)-(g)),虽然一些次优解的概率峰值有所下降,但最佳解决方案附近的概率峰值持续增强。到第 300 代 (图 8(h)),最佳解决方案的概率已超过 0.9,而其他解决方案的概率则趋近于 0。这表明
Q-bit个体已经高度收敛到最佳解决方案。 - 探索与利用的平衡: 这一系列结果清晰地展示了
QEA如何通过其内在的概率机制,从最初的全局探索自动平滑地过渡到局部利用。Q-bit表示能够有效地维护种群多样性,而Q-gate则负责引导这种多样性向最优解收敛,从而实现了探索与利用的良好平衡。
6.2. 数据呈现 (表格)
已在 6.1.2 节中完整转录了 Table II。
6.3. 消融实验/参数分析
论文通过对 参数的详细验证 (参见 6.1.1 节和 Figure 6),实际上进行了一种参数敏感性分析。虽然不是典型的“组件移除”式消融实验,但它展示了不同 Q-gate 旋转角度设置对算法性能的影响,从而验证了特定角度选择(例如 和 )的有效性。这种分析对于理解 Q-gate 如何引导搜索方向至关重要。
此外,对 QEA 种群大小 (QEA1, QEA2, QEA3) 和迁移策略的对比,也部分揭示了这些因素对算法性能和多样性维护的影响。例如,QEA3 (包含全局和局部迁移) 最终优于 QEA2 (仅全局迁移),表明在特定条件下,更精细的迁移策略有助于避免早熟收敛并达到更好的解。
7. 总结与思考
7.1. 结论总结
本文成功提出了一种新颖的量子启发式进化算法 (QEA),该算法借鉴了量子计算中的 Q-bit 和叠加态概念,并引入了 Q-gate 作为变异算子。QEA 的核心优势在于其独特的 Q-bit 概率表示,使得单个个体能够同时编码多个解决方案的叠加态,从而有效增强了种群多样性,并解决了传统进化算法易于早熟收敛的问题。通过 Q-gate 的旋转操作,QEA 能够动态地调整搜索方向,实现了全局探索与局部利用的良好平衡。在经典的 0-1 背包问题上的广泛实验表明,QEA 相比传统遗传算法,在收敛速度、最终解的质量以及避免早熟收敛方面均表现出显著优势,即使在种群规模非常小的情况下也能取得优异性能。对一个简单背包问题的详细分析进一步揭示了 QEA 从随机搜索到局部收敛的内在机制。
7.2. 局限性与未来工作
论文明确指出了 QEA 尽管受到了量子计算的启发,但它并非真正的量子算法,而是一种在经典计算机上运行的进化算法。这本身不是局限性,而是对其定位的澄清。
至于潜在的局限性和未来工作,论文中没有明确列出,但可以从其方法论中推断:
- 参数敏感性:
Q-gate中旋转角度 的确定,尤其是 和 的具体值,是通过实验调优得到的,并且具有一定的启发式成分。这些参数的设置可能具有问题依赖性,对于新的优化问题,可能需要重新进行大量的参数调整工作。这限制了其通用性和易用性。 - 约束处理的通用性: 论文为背包问题设计了一个特定的修复 (repair) 机制来处理容量约束。对于其他类型的组合优化问题,可能需要设计不同的约束处理策略,这增加了算法实现的复杂性。
- 理论分析的缺乏: 论文主要通过实验结果展示了
QEA的有效性。然而,关于QEA收敛性、收敛速度以及其在理论上为何能优于传统GA的更深入的数学分析和理论证明较少。缺乏这些理论基础可能会使得QEA的推广和改进缺乏指导。 - 复杂问题的可扩展性: 尽管在 500 物品的背包问题上表现出色,但对于物品数量更大、约束更复杂、目标函数更非线性的超大规模组合优化问题,
QEA的表现和可扩展性仍需进一步验证。 - 其他量子概念的集成:
QEA主要利用了Q-bit的叠加态和旋转门。未来可以探索如何更深入地集成其他量子力学概念,如纠缠 (entanglement)、量子隧道 (quantum tunneling) 等,以进一步提升算法性能。
7.3. 个人启发与批判
-
个人启发:
- 创新性的表示方法:
Q-bit这种概率性、叠加态的表示方法是QEA最具启发性的方面。它以一种优雅的方式解决了传统GA种群多样性不足的问题,使得算法在初期能够对搜索空间进行更广阔的探索,后期则能更聚焦于有潜力的区域。这种通过改变信息编码方式来提升算法性能的思路非常值得借鉴。 - 内在的探索与利用平衡:
QEA能够在算法运行过程中自动实现探索与利用的平衡,而无需复杂的自适应机制或多个超参数调整。这种“涌现”的特性是算法鲁棒性强、性能好的关键。 - 小种群的有效性:
QEA在小种群甚至单个个体下仍能取得良好性能,这对于实时系统、嵌入式设备或计算资源受限的场景具有巨大的应用潜力。 - 跨学科借鉴: 量子计算与进化计算的结合展示了跨学科研究的巨大潜力,通过从一个领域借鉴核心思想来解决另一个领域的难题。
- 创新性的表示方法:
-
批判:
- “量子启发”的界限: 尽管论文明确指出
QEA是“量子启发式”而非真正的量子算法,但对于初学者而言,这种表述有时可能带来混淆。算法的性能提升究竟是由于模拟了量子现象的“精髓”,还是仅仅是因为这种新的概率表示和更新机制恰好更适合这类问题,仍有探讨空间。 - 参数设置的经验性:
Q-gate旋转角度 的确定仍然是经验性的,需要通过大量实验进行调优。虽然论文进行了详细的验证,但这种依赖于经验的参数设置方式可能会阻碍算法在不同问题上的快速部署和性能保证。一个更自适应或理论驱动的 调整机制将是未来的重要研究方向。 - 修复机制的通用性: 对于背包问题,采用了特定的修复机制来处理约束。这种机制是否能直接推广到所有组合优化问题尚不确定。对于具有复杂或动态约束的问题,设计合适的修复策略可能成为
QEA应用的瓶颈。 - 与高级
GA的比较: 论文主要与几种基本CGA变体进行了比较。虽然P2R2是所测试CGA中表现最好的,但与当时或后续更先进的GA变体(例如具有更复杂选择、交叉或变异机制的GA,或者使用混合优化策略的GA)进行比较,可能会进一步揭示QEA的相对优势和局限。 - 局部最优问题: 尽管
QEA避免了“早熟收敛”,但它最终仍收敛到一个单一的最佳解。对于具有多个高质量局部最优解的问题,QEA是否能够探索并维持这些多个解,或者其在全局最优性上的保证,仍需进一步探讨。
- “量子启发”的界限: 尽管论文明确指出
相似论文推荐
基于向量语义检索推荐的相关论文。