表型精英多维档案（MAP-Elites）

名称

MAP-Elites，表型精英多维档案（Multidimensional Archive of Phenotypic Elites）

分类

查看分类思维导图

MAP-Elites 是一种质量多样性算法，隶属于计算智能中的进化计算领域。它与新颖性搜索（Novelty Search）算法以及带局部竞争的新颖性搜索（Novelty Search with Local Competition, NSLC）算法密切相关。

• 人工智能
  • 计算智能
    • 进化计算
      • 进化算法
        • 质量多样性算法
          • MAP-Elites

策略

MAP-Elites 维护一个由精英解构成的网格，其中网格中的每个单元对应于预先定义的特征维度组合。算法首先随机生成一个初始解种群，并评估各个解的性能及其特征描述符。随后，根据每个解的特征取值，将其放置到网格中相应的单元内。如果该单元为空，或者新解的性能优于当前单元中的已有解，则用该新解替换原有占据者。

随后，算法反复从网格中选取一个单元，该选择可以是均匀随机的，也可以基于某种偏置选择策略。接着，对所选解施加遗传操作（如变异和/或交叉），生成一个新解。对新解进行评估后，再依据其特征描述符将其映射到网格中的相应单元；若该单元为空，或新解性能更优，则用新解替换已有解。

这一过程持续进行，直到达到预设的迭代次数，或者解集在多样性与质量上达到满意水平。最终结果是一个覆盖整个特征空间的精英解网格，从而提供一组兼具高性能与多样性的候选解。

小生境机制与多样性维持

MAP-Elites 通过在特征网格的每个单元中维护一个精英解来促进多样性。这种小生境机制确保算法能够探索并保留具有不同特征组合的解，从而避免整个种群收敛到单一最优解。

质量与性能优化

尽管 MAP-Elites 强调多样性，但它同样在每个特征网格单元内部优化解的质量。通过不断以性能更优的解替换原有解，算法能够持续提升各个小生境中精英解的质量。

过程

数据结构：

• 网格（grid）：一个多维网格，依据特征描述符存储精英解。
• 个体解（solution）：种群中的一个个体解，由其基因表示、性能指标和特征描述符组成。

参数：

• 迭代次数（num_iterations）：MAP-Elites 算法运行的迭代次数。
• 种群规模（population_size）：初始种群规模。
• 特征维度（feature_dimensions）：网格中特征维度的数量及其定义方式。
• 变异率（mutation_rate）：对解施加变异的概率。
• 交叉率（crossover_rate）：对一对解施加交叉的概率。

步骤：

1. 根据 feature_dimensions 初始化一个空的 grid。
2. 随机生成一个规模为 population_size 的初始解种群。
3. 评估种群中每个解的性能及其特征描述符。
4. 对于种群中的每个解：

• 根据其特征描述符确定其在 grid 中对应的单元。
• 若该单元为空，或者该解性能优于当前单元中的已有解，则将该解放入该单元。

5. 重复执行 num_iterations 次：

• 从 grid 中选择一个单元，选择方式可以是均匀随机，也可以采用偏置选择策略。
• 对所选解施加遗传操作（变异和/或交叉），生成一个新解。
• 评估新解的性能及其特征描述符。
• 根据新解的特征描述符确定其在 grid 中对应的单元。
• 若该单元为空，或者新解性能优于当前单元中的已有解，则将新解放入该单元。

6. 返回包含精英解的 grid。

注意事项

优点：

• 能够在整个特征空间中维持一组兼具高性能与多样性的解。
• 通过探索不同小生境，有助于发现新颖且非预期的解。
• 为分析特征与性能之间的关系提供了有效手段。

缺点：

• MAP-Elites 的效果高度依赖于特征维度的选择，而这通常需要领域知识支持。
• 随着特征维度数量增加，网格规模呈指数增长，从而带来较高的计算开销和存储需求。
• 在特征空间较为稀疏的区域中，算法可能较难发现高质量解。

启发式建议

特征维度选择

• 应选择与问题领域密切相关、能够刻画解关键属性的特征维度。
• 可考虑使用较少的特征维度（例如 2-5 个），以控制网格规模。
• 应确保各特征维度尽可能相互独立，并且能够提供有意义的多样性信息。

网格分辨率

• 应根据所需的划分粒度和可用计算资源来确定各特征维度的分辨率。
• 更高的网格分辨率能够捕捉解之间更细致的差异，但也会增加计算成本。
• 可考虑采用自适应或动态网格分辨率，使其在算法运行过程中发生变化。

遗传操作

• 应使用能够在保留解整体结构的同时引入有效变化的变异算子。
• 可采用交叉算子，使不同小生境中的解能够交换遗传信息。
• 应根据探索与开发之间的平衡需求，调整变异率和交叉率。

选择策略

• 可尝试不同的选择策略，例如均匀随机选择、基于单元质量的偏置选择，或基于好奇心驱动的选择。
• 也可考虑组合使用多种选择策略，以兼顾探索与开发。

初始化与重启

• 初始种群应具有较好的随机多样性，以促进对特征空间的广泛探索。
• 可周期性地对网格进行重置或部分随机化，以跳出局部最优并发现新的潜在优良区域。

性能评估

• 应定义能够准确表征解期望行为或质量的性能指标。
• 可考虑使用多个性能指标，从不同角度评估解，并进一步促进多样性。

并行化与分布式计算

• 可利用并行计算技术对多个网格单元同时进行评估与更新，以提高算法效率。
• 可探索分布式计算方法，将 MAP-Elites 扩展到更大规模问题或更高维特征空间中。