基于智能体的禁忌搜索 — 分布式多智能体元启发式优化
- 提出者
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- 年份
- 1989–1995
- 类型
- Hybrid metaheuristic — agent-based distributed tabu search
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
基于智能体的禁忌搜索(ABTS)将禁忌搜索元启发式方法嵌入多智能体框架中,其中自主智能体各自运行独立或协作的禁忌搜索线程,共享有希望的解以逃离局部最优,并比单线程实现更有效地集体探索大型组合或连续搜索空间。
方法背后的直觉
经典的禁忌搜索即使有其短期记忆机制,也可能陷入探索狭窄区域。通过部署多个自主智能体,每个智能体维护自己的禁忌列表和邻域,搜索会从不同的起始点扩散开来。智能体周期性地共享精英解(强化)并故意分散到未探索的区域(多样化)。这种协作而独立结构模仿了生物群行为——没有单个智能体拥有全局视图,但集体发现高质量解的速度远超任何单个搜索者。
历史学
禁忌搜索由Fred Glover在1986-1989年正式提出。分布式和并行变体出现在20世纪90年代初,研究人员试图利用多处理器架构。Verhoeven和Aarts(1995)对并行局部搜索进行了系统研究,包括协作禁忌策略。随着基于智能体的建模词汇进入运筹学领域,基于智能体的框架在21世纪初变得突出。
何时使用
在解决困难的组合或混合整数优化问题(调度、路由、网络设计、资源分配)时使用基于智能体的禁忌搜索,这些问题中的单线程禁忌搜索会停滞不前,并且有并行计算资源可用。当搜索景观有许多质量相似的局部最优解时,它尤其有效。当问题足够小可以被精确求解器(MILP、分支定界法)解决时,当单个评估在计算上是禁止的(使得许多并行评估不可行)时,或者当可复现性要求与非确定性、智能体交互动态冲突时,应避免使用它。
局限与注意事项
- 智能体之间的同步开销和通信成本可能会抵消紧耦合系统或慢速网络上的并行增益。
- 比单线程禁忌搜索有更多的超参数:智能体数量、通信拓扑、同步频率和多样化触发器都需要调整。
- 理论收敛保证弱于精确方法;解的质量很大程度上取决于调优和问题结构。
- 由于智能体交互引入了超出随机初始化的额外随机性,因此可复现性难以实现。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 与单线程禁忌搜索相比,并行探索显著减少了大型组合问题上的求解时间。
- 多智能体框架自然支持多样化,降低了过早收敛到差的局部最优解的风险。
- 灵活的架构允许异构智能体具有不同的邻域结构、禁忌租期策略,甚至混合元启发式方法。
- 协作解共享在智能体之间传递发现,加速了对高质量区域的强化。
- 与可用的计算核心很好地扩展,使其适用于现代多核和分布式计算环境。
应用
- 车辆路径和物流:协调每个优化子路径问题的多个智能体。
- 作业车间和柔性制造调度:智能体协同处理机器子集。
- 电信网络设计:分布式信道分配和拓扑优化。
- 供应链规划:多层库存和分销优化。
- 蛋白质结构预测:在构象空间上进行并行邻域搜索。
- 具有分布式部门级智能体的学术时间表和课程安排。
使用方式
使用方式
定义一个自主智能体种群。为每个智能体分配一个角色:一些专注于强化(在有希望区域周围进行深度局部搜索),另一些专注于多样化(逃逸到未探索区域)。每个智能体维护其禁止移动的禁忌列表、当前解以及为问题类型量身定制的邻域结构(例如,组合问题的交换、插入或2-opt移动)。
使用不同的起始解初始化智能体,这些解可以随机生成,也可以通过构造性启发式方法(例如,路由的最近邻法)进行种子。起始解的多样性至关重要——相同的起始会导致冗余的并行搜索。评估每个初始解的目标函数,并记录所有智能体中的全局最优解。
每个智能体执行自己的禁忌搜索循环:生成当前解的邻域,评估所有(或一部分)邻居解,选择最佳的非禁忌邻居作为下一步移动(渴望准则允许在候选解优于全局最优时覆盖禁忌列表),并通过添加具有固定或自适应范围内的租期的反向移动来更新禁忌列表。
智能体在定义的同步间隔或事件触发器处进行通信。常见策略包括将当前全局最优解广播给所有智能体(它们可以从中重新开始),将精英解注入一个智能体周期性咨询的共享池,或在拓扑结构(环形、全连接或随机)中的邻近智能体之间进行点对点解交换。多样性控制通过惩罚具有相同解的智能体来防止过早收敛。
当达到最大迭代预算、实际运行时间限制或停滞标准时终止(例如,全局最优解在给定迭代次数内没有改进)。选择所有智能体在所有迭代中找到的全局最优解作为最终输出。如果跟踪了多个目标,可以选择性地报告帕累托前沿。
常见陷阱
- 将所有智能体设置为相同的起始解会浪费并行能力——确保多样化的初始化。
- 过于频繁的通信会将智能体推入相同的解盆地,消除多样化优势,并有效地将搜索减少为一个线程。
- 在禁忌列表设计中忽略渴望准则,可能会导致智能体错过明显更好的解,尤其是在搜索早期阶段。
- 将ABTS应用于邻域评估成本极高且没有代理模型的问题,将导致运行时间过长。
常见问题
基于智能体的禁忌搜索与简单地运行多个禁忌搜索线程有何不同?
关键区别在于协作。在独立的并行运行中,线程从不共享信息。在ABTS中,智能体积极交换解,更新共享的精英池,或根据集体状态触发多样化——产生独立运行所没有的涌现搜索行为。
我应该使用多少个智能体?
一个常见的起点是每个可用CPU核心一个智能体。研究表明,对于大多数组合问题,超过8-16个智能体后收益递减,因为通信开销会增加。使用4、8和16个智能体的试点实验有助于确定给定问题的最佳点。
ABTS可以处理多目标问题吗?
可以。智能体可以维护帕累托前沿的局部近似,并通过共享存档交换非支配解。这有时被称为多目标基于智能体的禁忌搜索,与标准的单目标ABTS不同。
哪种通信拓扑最好?
全连接拓扑传播好解最快,但通信成本高。环形或小世界拓扑在信息扩散和自主性之间取得平衡。对于大多数实际问题,环形或随机稀疏拓扑作为默认值效果很好。
何时应优先选择遗传算法或粒子群优化而非ABTS?
当问题具有连续、平滑的景观或交叉/重组算子定义良好时,优先选择基于种群的方法(GA、PSO)。ABTS在离散、组合问题上表现出色,这些问题具有定义良好的邻域算子,并且禁忌记忆提供了强大的搜索优势。