Hybrid Discrete Grey Wolf Optimization Approach for solving Spectrum Assignment Problem in Elastic Optical Networks

技术摘要：用于弹性光网络频谱分配的混合离散灰狼优化算法

问题陈述
本文解决了弹性光网络（EON）中更广泛的路由与频谱分配（RSA）挑战中的频谱分配（SA）子问题。随着高带宽应用驱动流量增长，传统的固定网格波分复用（WDM）网络正变得难以为继。EON 通过使用更小粒度的灵活频谱分配提供了解决方案。然而，RSA 问题是一个 NP 难问题，特别是在大规模网络中，因为它需要同时满足三个关键约束：

1. 频谱连续性（Spectrum Continuity）： 在路径上的所有物理链路中，频率槽索引必须保持一致。
2. 频谱连通性（Spectrum Contiguity）： 分配的带宽必须形成由相邻频率槽组成的连续块，且不产生碎片。
3. 非重叠性（Non-overlapping）： 链路上的一个频率槽在同一时间只能为一个连接请求服务。

本研究的具体目标是最小化大规模光网络中频率槽（FSs）的总利用量，以提高网络容量和效率。

方法论
作者提出了一种将模拟退火（SA）集成到离散灰狼优化器（GWO）中的混合算法，称为 SA-GWO。

• 灰狼优化器（GWO）： 基础算法模仿了灰狼（Alpha、Beta、Delta 和 Omega）的社会等级制度和狩猎行为。选择它是由于其强大的全局探索能力。然而，作者指出，标准的 GWO 在处理大规模搜索空间时，可能会出现过早收敛和陷入局部最优的问题。
• 离散化适配： 由于 SA 问题涉及请求的离散排序而非连续变量，作者对 GWO 进行了适配。他们使用 汉明距离（Hamming distance） 取代了标准的基于向量的距离计算，以此来衡量解向量（即请求的排列）之间的差异性。
• 与模拟退火（SA）的杂化： 为了解决标准 GWO 的局限性，SA 被嵌入到 GWO 的位置更新机制中。
  • 算法不再仅仅根据 Alpha、Beta 和 Delta 领导者确定性地更新狼的位置，而是利用与汉明距离成比例的 交换变异（swap mutation） 为每只狼生成一个邻域解。
  • 接受新解的过程遵循 Metropolis 准则。如果新解更好，则接受；如果新解较差，则以概率 $P = e^{-\Delta E/T}$ 接受，其中 $\Delta E$ 是适应度差异，$T$ 是当前温度。
  • 这种概率性接受机制允许算法跳出局部最优，比单纯的 GWO 更有效地平衡探索（Exploration）与开发（Exploitation）。
• 评估： 解的评估基于所使用的最大频率槽数量，并遵循包括保护带（guardband）要求在内的距离频谱分配（DSA）模型约束。

核心贡献

1. 算法创新： 开发了一种专门针对 EON 中离散频谱分配问题的混合元启发式算法（SA-GWO）。
2. 机制集成： 将模拟退火创新性地集成到 GWO 的位置更新阶段，以优化搜索过程并防止过早收敛。
3. 离散化表述： 通过使用汉明距离和交换变异而非连续向量算术，实现了 GWO 在离散组合优化中的适配。

实验结果
所提出的 SA-GWO 算法通过以下方式进行了评估：

• 拓扑结构： 使用 Python 库（NetworkX 和 Matplotlib）生成的各种合成图，包括随机图和节点数在 14 到 25 之间的完全图。
• 对比： 结果将其与标准的两阶段算法（Two-Phase algorithm）、标准 GWO 算法以及由 CPLEX 12.9.0 求解器生成的最佳解（针对较小规模实例）进行了基准测试。

研究发现：

• 中小规模图（14–19 个节点）： SA-GWO 算法显著优于两阶段参考算法。在许多情况下，它产生的结果非常接近 CPLEX 找到的最优解。
• 大规模图（20–25 个节点）： 虽然 SA-GWO 未能达到 CPLEX 的最优结果（这对于 NP 难问题而言是预料之中的），但它表现出了优于标准 GWO 算法的显著优势，减少了所使用的最大频率槽数量。
• 可扩展性： 混合方法被证明在处理随图规模增长而增加的复杂性方面具有鲁棒性，而标准 GWO 与混合版本相比表现出更大的性能差距。

意义与主张
论文声称，所提出的 SA-GWO 方法通过优化频率槽分配，有效地提高了网络容量。其主要意义在于该算法能够更好地平衡全局探索与局部开发。通过引入模拟退火，该方法减轻了陷入局部最优的风险，而这是大规模 RSA 问题中的常见问题。

作者总结认为，与传统方法相比，该混合技术显著减少了频谱碎片化并最大化了资源利用率。他们将这项工作定位为解决复杂、大规模 RSA 问题的一步，在这些场景下精确方法（如 CPLEX）在计算上变得难以承受，因此该方法提供了一种高质量的启发式替代方案。

未来工作
作者简要概述了未来的研究方向，包括：

• 将算法扩展到 动态频谱分配 场景，以处理实时流量需求。
• 研究 多目标优化，以同时解决功耗和延迟问题。
• 探索 基于机器学习的启发式算法 的集成，以改进预测性频谱分配。