知识卡片
热平衡更新须保持串行条件
模拟退火在每个温度 T 下要反复做“由当前路线产生新路线、按 Metropolis 准则决定是否接受”的尝试,直到该温度下达到热平衡,这一过程称为 Metropolis 过程;每个温度的尝试次数即马尔可夫链长 L。每次状态改变都建立在上一次得到的状态上,所以退火有内在串行性,只能部分并行。
书中方案并行化两处:
- 随机初始化时,并行计算任意两城市间的距离——这些距离互不依赖。
- 因 L 一般较大,并行处理每一固定温度下的循环。
但各循环体内的 Metropolis 过程每一步都依赖上一步的状态,仍须用 LOCK 与 UNLOCK 建立临界区(同一时刻只允许一个进程执行的代码段),使状态更新串行进行。原书未说明循环的具体划分与调度规则。
结构图:
flowchart TD
A[随机初始化] --> B[并行计算任意两城市间距离]
B --> C[每一固定温度 T 下的循环]
C --> D[循环可并行处理]
D --> E[各循环体内的Metropolis热平衡]
E --> F[用LOCK与UNLOCK建立临界区]
F --> G[串行执行状态更新]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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过程的串行执行。