← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3744.i

蚂蚁分工搜索前沿子问题

理解等级:中级

多目标社区检测要同时照顾若干互相牵制的目标(正文把最大化模块度密度改写成最小化 NRA 与 RC)。分解机制把它拆成一系列单目标子问题,每只蚂蚁负责其中一个子问题,它求出的解对应 Pareto 前沿上的一个点;许多蚂蚁一起,就用一组点去逼近整条前沿。这就是“蚂蚁分工搜前沿”。

实现时还要事先规定:蚂蚁与子问题如何对应、解怎样编码和构造、启发式信息矩阵与信息素矩阵如何定义和更新。本节只列出这些设计维度,没有给出可直接复现的完整更新公式。

示例(补充教学示例,非书中数据):两个目标 f1、f2 都要尽量小。把“更看重 f1”“两者各半”“更看重 f2”做成三个子问题,三只蚂蚁分别去搜,得到三个非占优点,连起来近似前沿。权重取法是演示,不是书中数据。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 5 . 4 基 于 蚁 群 算 法 的 社 区 检 测 · 查看原书依据

      可以将多目标算法和蚁群算法结合起来解决复杂网络的社区检测问题,采用分解机制可以将多目标问题转化为一系列单目标的子问题,每一只蚂蚁得到的解对应着Pareto前端特定的点。另外在算法设计过程中应考虑蚂蚁与子问题之间的关系、解的编码方式和构造、启发式信息矩阵的定义、信息素矩阵的定义和更新方式等问题。

    参考来源

    - 位置:《智能算法导论》第 5 章“5.4 基于蚁群算法的社区检测”(源文件:`_epub-src/EPUB/xhtml/chapter5_0008.xhtml`)。 - 结论依据:原文写明采用分解机制将多目标问题转化为一系列单目标子问题,每一只蚂蚁得到的解对应 Pareto 前端特定的点,并列出蚂蚁与子问题关系、编码构造、启发式矩阵和信息素矩阵等设计事项。三子问题示意为依据该框架补充的教学示例,非书中数据。 - 原始内容:采用分解机制可以将多目标问题转化为一系列单目标的子问题,每一只蚂蚁得到的解对应着Pareto前端特定的点。另外在算法设计过程中应考虑蚂蚁与子问题之间的关系、解的编码方式和构造、启发式信息矩阵的定义、信息素矩阵的定义和更新方式等问题。