知识卡片
离散粒子群以调整序列移动
旅行商问题(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 基 于 粒 子 群 算 法 的 优 化 问 题 · 查看原书依据
速度定义为迭代过程中粒子需要调整位置的集合,假设速度为V=[(a,a),(a,a),…,(an,an)],(a,a)则是被最优解选中的排列,其他则为需要调整的边的排列,借鉴2-opt调整策略改变粒子的位置顺序。
参考来源
- 位置:《智能算法导论》第 4 章“4.4.1 基于粒子群算法的旅行商问题”(`_epub-src/EPUB/xhtml/chapter4_0009.xhtml`,式(4-13)–(4-18)及 2-opt 例子)。
- 结论依据:正文明确以城市排列表示粒子位置,以路径调整集合表示速度,并用片段倒序示例解释离散移动;公式 SVG 显示离散运算符承接连续粒子群的更新结构。
- 原始内容:速度定义为迭代过程中粒子需要调整位置的集合