知识卡片
分簇与变邻域保持搜索能力
多次采样可能让 EDA 种群多样性下降并较早收敛。一种柔性车间调度方案先用 K-means 将种群分簇,再从各子簇选择优势群体更新概率模型,并配合变邻域搜索增强局部求解。
- K-means:把相似的个体归为同一簇,共分 K 簇;从每簇分别选优,模型就不会只由某一区域的个体决定。
- 变邻域搜索:轮流换用几种不同的“小改动”方式(邻域结构),在当前解附近寻找更优解,一种方式找不到改进就换下一种。分簇改变了更新模型所用的样本来源,局部搜索则针对候选附近继续改进;二者是不同环节,原文没有给出参数、消融或统一对照,不能把性能收益当成普遍保证。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 9 . 4 基 于 分 布 估 计 算 法 的 调 度 问 题 · 查看原书依据
张玺等[68]把聚类的思想引入分布估计算法中,考虑多次采样后种群的多样性会下降,容易出现早熟收敛的问题,因此对种群进行K-means聚类,从子簇中选择优势群体来更新概率模型,并利用变邻域搜索机制提高算法的局部求解能力。虽然分布估计算法在柔性作业车间调度方面的应用已经取得了不少研究成果,但是在面对大规模的复杂问题,准确地建立相应的概率模型仍是非常重要的。
参考来源
- 位置:《智能算法导论》第 9 章《9.4 基于分布估计算法的调度问题》(源文件:`_epub-src/EPUB/xhtml/chapter9_0007.xhtml`)
- 结论依据:原文以多次采样后多样性下降、早熟收敛为动机,列出 K-means 分簇、子簇优势群体更新概率模型和变邻域局部搜索。
- 原始内容:对种群进行 K -means聚类,从子簇中选择优势群体来更新概率模型,并利用变邻域搜索机制提高算法的局部求解能力。