知识卡片

结构图卡 · 3742.l

离散粒子群以调整序列移动

理解等级:高级

旅行商问题(TSP)要找一条遍历所有城市一次再回到起点的最短路线。路线是城市的排列,“位置 + 速度”这种连续加法用不上。离散粒子群(DPSO)重新定义了各个概念:

  • 位置:一个城市排列,如 X = (1, 2, 3, 4, 5, 6, 7, 8),表示从城市 1 出发依次经过各城再回到 1。
  • 适应度:整条回路的长度,越短越好。
  • 速度:一组有先后顺序的调整操作,借鉴 2-opt 改变城市顺序。

原书示例:对 X 施加调整 (1, 6),即找到城市 1 和城市 6 的位置,把 1 之后直到 6 的那一段倒序,使城市 6 紧接在城市 1 之后,得到 (1, 6, 5, 4, 3, 2, 7, 8)。

连续公式里的三种运算被换成离散运算:

  • 减号 → pbest Θ x:求出一串调整,使当前排列 x 变成 pbest 的排列。
  • 乘号 → r ⊗ 调整序列:按随机数决定这串调整中保留哪些。
  • 加号 → ⊕:按先后顺序依次执行调整。

每次调整后重新计算路线长度,并更新个体和群体最优。调整的执行顺序会影响结果;保留规则在原书中前后表述不一(一处写“按 r 的概率保留”,一处写“随机数大于 r 则保留”),实现前需自行确定。

结构图:

flowchart TD
  A[城市排列作为当前位置] --> B[由个体和群体最优生成调整序列]
  B --> C[按顺序执行路径调整]
  C --> D[计算完整路线长度]
  D --> E[更新个体与群体最优]
  E --> B
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 4 章“4.4.1 基于粒子群算法的旅行商问题”(`_epub-src/EPUB/xhtml/chapter4_0009.xhtml`,式(4-13)–(4-18)及 2-opt 例子)。 - 结论依据:正文明确以城市排列表示粒子位置,以路径调整集合表示速度,并用片段倒序示例解释离散移动;公式 SVG 显示离散运算符承接连续粒子群的更新结构。 - 原始内容:速度定义为迭代过程中粒子需要调整位置的集合