知识卡片

结构图卡 · 3767.b

热平衡更新须保持串行条件

理解等级:高级

模拟退火在每个温度 T 下要反复做“由当前路线产生新路线、按 Metropolis 准则决定是否接受”的尝试,直到该温度下达到热平衡,这一过程称为 Metropolis 过程;每个温度的尝试次数即马尔可夫链长 L。每次状态改变都建立在上一次得到的状态上,所以退火有内在串行性,只能部分并行。

书中方案并行化两处:

  1. 随机初始化时,并行计算任意两城市间的距离——这些距离互不依赖。
  2. 因 L 一般较大,并行处理每一固定温度下的循环。

但各循环体内的 Metropolis 过程每一步都依赖上一步的状态,仍须用 LOCK 与 UNLOCK 建立临界区(同一时刻只允许一个进程执行的代码段),使状态更新串行进行。原书未说明循环的具体划分与调度规则。

结构图:

flowchart TD
  A[随机初始化] --> B[并行计算任意两城市间距离]
  B --> C[每一固定温度 T 下的循环]
  C --> D[循环可并行处理]
  D --> E[各循环体内的Metropolis热平衡]
  E --> F[用LOCK与UNLOCK建立临界区]
  F --> G[串行执行状态更新]
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 1 . 5 . 3 基 于 模 拟 退 火 算 法 的 旅 行 商 问 题 · 查看原书依据

      该算法以两部分对SAA实现并行计算:第一部分是在随机初始化时,将计算任意两个城市间距离的过程并行处理;第二部分是在每一温度T,由于马尔可夫链长L值一般比较大,所以并行处理每一温度下的循环,但在每一循环体内,热平衡过程,即Metropolis过程必须串行执行,作者通过语句LOCK与UNLOCK建立临界区来实现Metropolis过程的串行执行。

    参考来源

    - 位置:《智能算法导论》第 120 项《11.5.3 基于模拟退火算法的旅行商问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0015.xhtml`) - 结论依据:原文将任意两城市距离计算并行化,并指出温度循环可并行,而每个循环体内的 Metropolis 热平衡因状态依赖必须串行并使用临界区保护。 - 原始内容:热平衡过程,即Metropolis过程必须串行执行,作者通过语句LOCK与UNLOCK建立临界区来实现Metropolis过程的串行执行。