新颖性搜索算法（NS）
2026/3/21约 1545 字大约 5 分钟
新颖性搜索算法（NS）
名称
新颖性搜索（Novelty Search, NS）
分类
新颖性搜索是一种属于进化计算领域的搜索技术，而进化计算本身又隶属于计算智能与生物启发计算。它与其他进化算法（如遗传算法和神经进化）密切相关。:contentReference[oaicite:0]
- 计算智能
- 生物启发计算
- 进化计算
- 进化算法
- 遗传算法
- 神经进化
- 新颖性搜索
- 进化算法
- 进化计算
- 生物启发计算
策略
新颖性搜索是一种旨在发现新颖解而非直接优化预定义适应度函数的搜索策略。其基本思想是维护一个由既往行为构成的档案，并引导搜索朝向那些与档案中已有行为不同的行为区域推进。
行为表征
在新颖性搜索中，种群中的每个个体都通过其行为进行刻画。该行为通常表示为个体在具体问题域中表现方式的低维表示。这种行为表征用于比较不同个体，并据此判定其新颖性。
新颖性度量
个体的新颖性通过计算其在行为空间中与最近邻个体之间的行为距离来确定。该距离由新颖性度量函数给出，用以量化两个行为之间的差异程度。常见的新颖性度量包括欧几里得距离和汉明距离。
档案管理
新颖性搜索维护一个由搜索过程中所发现的新颖行为组成的档案。当一个新个体被评估时，其行为会与档案中的行为进行比较。若该个体的行为与已有行为具有足够大的差异，即表现出足够的新颖性，则将其加入档案。档案也可以设置为固定大小；在这种情况下，当新行为加入时，较不新颖的行为将被移除。
选择与繁殖
在新颖性搜索的每一代中，会根据个体的新颖性得分选择一部分个体用于繁殖。新颖性得分越高，即行为与档案中已有行为差异越大的个体，被选中的概率越高。随后，通过交叉和变异等遗传操作生成下一代个体。
过程
- 初始化种群
- 初始化空档案
- 当终止条件未满足时：
- 评估种群中的每个个体：
- 表征个体行为
- 计算新颖性得分：
- 计算其与档案中 个最近邻之间的距离
- 根据平均距离赋予新颖性得分
- 将具有足够新颖行为的个体加入档案
- 若档案大小超过最大容量：
- 从档案中移除新颖性最低的个体
- 根据新颖性得分选择父代
- 通过交叉与变异生成下一代
- 评估种群中的每个个体：
- 返回最终种群与档案
数据结构
- 种群（Population）：表示潜在解的一组个体集合
- 档案集（Archive）：搜索过程中发现的新颖行为集合
- 行为表征（Behavior representation）：个体行为的低维表征
- 新颖性度量（Novelty metric）：用于衡量两个行为差异程度的度量
参数
- 种群规模（Population size）：种群中的个体数量
- 档案规模（Archive size）：档案中可维护的最大行为数量
- 新颖性阈值（Novelty threshold）：个体被加入档案所需满足的最小新颖性得分
- 最近邻数量（Nearest neighbors，）：计算新颖性得分时考虑的最近邻数量
- 交叉率（Crossover rate）：繁殖过程中执行交叉操作的概率
- 变异率（Mutation rate）：繁殖过程中执行变异操作的概率
注意事项
优点
- 促进对搜索空间的探索
- 能够发现多样化且具有意外性的解
- 避免过早收敛到局部最优
- 适用于适应度函数具有欺骗性或难以明确定义的问题
缺点
- 计算代价较高，尤其是在行为空间较大时更为明显
- 对行为表征和新颖性度量的设计要求较高
- 不以全局最优为直接目标，因此若在搜索结束后再映射到适应度指标上，所得解未必具有全局最优适应度
启发式建议
行为表征
- 选择能够反映问题领域关键特征的行为表征方式
- 避免使用过于复杂或维度过高的行为表示
- 确保行为表征的计算评估开销可控
新颖性度量
- 选择与行为表征相匹配的新颖性度量方式
- 可考虑对各行为维度进行归一化，以确保它们对新颖性得分的贡献相对均衡
- 可尝试不同的距离度量方式（如欧几里得距离、曼哈顿距离、汉明距离），以确定最适合当前问题的方法
档案管理
- 根据可用计算资源和期望的多样性水平设定档案大小
- 调整新颖性阈值，以控制探索与开发之间的权衡
- 可考虑定期修剪档案，移除过时或信息价值较低的行为
种群与繁殖
- 根据问题复杂度和可用计算资源调整种群规模
- 设置合理的交叉率和变异率，以维持探索与开发的平衡
- 可尝试不同的父代选择策略（如锦标赛选择、按比例选择），以确定对当前问题最有效的方法
与其他技术的结合
- 可考虑将新颖性搜索与其他进化算法或优化技术结合使用
- 可将新颖性搜索作为更大优化框架中的多样性维持机制
- 可融入问题领域的先验知识或启发式规则，以引导搜索朝向行为空间中更有前景的区域