新奇性算法，也称为新奇性搜索（Novelty Search），是一种非传统的优化和搜索方法，它与传统的目标驱动型算法形成鲜明对比。该算法的核心思想不在于直接追求某个预设的目标或优化某个特定的目标函数，而是鼓励探索未知和新颖的解决方案。它基于自然进化的原理，即新奇的行为或特性往往能开启通往更多新奇发现的路径，从而促进创新和多样性。
核心概念
- 新奇性作为驱动力：新奇性算法通过评估解决方案的新颖程度来指导搜索过程，而不是直接的性能或目标达成度。
- 探索未知：算法鼓励智能体或系统探索那些前所未有的行为或状态空间，即使这些行为在短期内不直接导向传统意义上的成功。
- 踏脚石概念：新奇性行为可以作为进一步发现的起点，类似于自然进化中创新的积累，新奇性可以是达到更复杂目标的间接路径。
- 应用领域：新奇性搜索在机器人学、人工智能、游戏AI、以及需要创新解决方案的任何领域都有应用，它能够帮助发现传统方法可能忽视的解决方案。
实践案例
- 迷宫实验：在迷宫实验中，新奇性探索算法的机器人通过尝试新路径，而非直接寻找出口，最终走出迷宫的次数多于目标驱动型算法，显示了其在探索未知方面的优势。
- 图片孵化器：一个科学实验通过“图片孵化器”网站，展示了新奇性算法如何通过不断繁育图像，生成前所未有的图像，如从基础形状进化到复杂图像，如汽车，这体现了新奇性如何促进创新生成。
思考与应用
新奇性算法挑战了我们对目标设定的传统理解，提倡在某些情况下，无目标的探索可能比直接追求目标更能促进创新和长期的成功。在教育、创新项目管理、以及人工智能的开放式探索中，这种方法鼓励人们接受不确定性，拥抱探索过程中的偶然性，从而可能发现更为广阔的可能性空间。
新奇性搜索在机器学习领域的应用广泛，它通过鼓励探索未知和新颖的解决方案，推动了多个方面的创新。以下是一些具体实例：
- 机器人学：
- 迷宫导航：机器人通过新奇性搜索，不直接寻找出口，而是探索新的路径，最终学会了高效穿越复杂环境。
- 双足机器人行走：新奇性搜索帮助双足机器人通过不断尝试新奇的步态，而非直接设定行走目标，学会了更自然、更稳定的行走方式。
- 自动编程与软件工程：
- 通过新奇性搜索，可以发现新的编程模式或算法，帮助优化代码结构，甚至自动修复错误。例如，Heather Goldsby使用新奇性搜索来发现计算机程序中的错误，这表明该方法能有效识别和改进代码的创新性部分。
- 材料科学与药物发现：
- 在材料设计中，新奇性搜索可以引导研究人员探索具有新奇性质的化合物，这些化合物可能具有前所未有的物理或化学特性，对于开发新材料至关重要。
- 在药物发现领域，算法可以探索化学空间，寻找具有新奇药理活性的分子，这在传统目标导向方法难以触及的领域尤为重要。
- 机器学习算法优化：
- 新奇性搜索可以用于优化神经网络架构或超参数，通过寻找新颖的配置而非直接最小化损失函数，可能发现更高效或更适应特定任务的模型结构。
- 游戏AI与创意生成：
- 在游戏AI中，新奇性搜索可以生成创新的策略和游戏行为，使AI角色的行为更加不可预测和有趣。
- 在艺术和创意领域，如生成艺术作品，新奇性搜索可以探索新的视觉或音乐表达，创造独特的艺术作品。
- 多智能体系统：
- 在多智能体系统中，新奇性搜索可以促进智能体之间的非直接竞争或合作，通过探索新的交互模式，提高整个系统的适应性和复杂任务的解决能力。
这些应用展示了新奇性搜索在促进创新、增加解决方案多样性以及在复杂、非线性问题上的潜力。通过鼓励探索未知，新奇性搜索为机器学习和人工智能领域带来了新的视角和方法。
通过新奇性搜索解决复杂问题，主要依赖于以下几个步骤和原则：
- 放弃直接目标：首先，不同于传统方法直接设定最终目标，新奇性搜索鼓励探索未知领域，不设定具体目标或优化指标，而是寻找行为或解决方案的新颖性。
- 定义新奇性标准：新奇性是相对于已知解决方案的差异度。需要建立一个机制来评估解决方案的新颖性，这通常基于与历史解的比较，如通过行为的统计特征或解决方案的结构差异来衡量。18
- 初始探索：启动搜索过程，生成一系列初始解决方案或行为模式，并记录这些行为的特征，作为新奇性评估的基准。
- 迭代与评估：
- 在每次迭代中，算法生成新的解决方案或策略。
- 评估这些新解的新奇性，保留那些与现有解相比具有显著差异的。
- 这些新奇解成为下一步探索的起点，即使它们当前可能不直接指向问题的解决方案。
- 累积知识：新奇性搜索过程中，虽然不直接追求解决方案，但通过不断积累的新奇解，可能会无意中发现解决问题的关键特征或中间步骤。
- 适应性与多样性：鼓励多样性，即使某些尝试看似无效，也可能为后续的创新提供灵感。在复杂问题中，多样性是克服局部最优的关键。
- 分析与整合：随着时间的推移，通过分析新奇解的模式，可能揭示出解决复杂问题的新途径。这需要人类的介入，理解这些新奇解背后的潜在价值，并可能手动或通过其他算法整合这些发现。
- 反馈循环：虽然新奇性搜索不直接设定目标，但可以设置反馈机制，确保探索的方向与问题的某些关键方面保持相关性，避免完全无目的的探索。
- 跨领域应用：新奇性搜索的原理可以应用于多个领域，如机器人控制、算法设计、创意生成等，通过跨领域的灵感，可能发现意想不到的解决方案。
通过上述步骤，新奇性搜索利用探索的广度而非直接的深度来解决复杂问题，这种方法特别适合于那些目标不明确或解决方案空间高度不确定的问题。它通过不断尝试和学习新奇事物，最终可能间接地达到或超越传统目标驱动方法的成果。
评估新奇性搜索中解决方案的新奇性，通常涉及以下几个关键步骤和考虑因素：
- 定义行为空间：首先，需要明确解决方案或行为的表示空间，这可以是解决方案的参数空间、行为轨迹、或是任何可以量化其特性的多维空间。
- 构建行为特征：为每个解决方案提取特征，这些特征应该能够描述解决方案的关键方面，比如在机器人学中，可以是步态的节奏、步幅长度等。特征的选择对新奇性的准确评估至关重要。
- 历史行为数据库：维护一个历史解的数据库，记录已评估过的解决方案的特征。这个数据库用于比较新解与历史解的新颖性。
- 新奇性度量：
- 距离度量：使用如欧氏距离或余弦相似度等，计算新解特征与历史解特征集的平均距离。距离越大，新奇性越高。
- 覆盖度：评估新解是否落在历史解的覆盖区域之外，如果新解在历史解的“行为地图”中开辟了新的区域，那么它就被认为是新奇的。
- 聚类分析：通过聚类算法识别行为模式，新解如果与任何现有聚类显著不同，则认为具有新奇性。
- 非目标性评估：新奇性评估不考虑解决方案的性能或目标达成度，仅基于其与历史解的差异性。
- 阈值设定：设定一个新奇性阈值，低于此阈值的解决方案被视为不新奇，不会被保留或进一步探索。
- 时间或代际窗口：有时，新奇性评估会考虑最近几代或一段时间内的解，以确保新奇性评估反映最近的探索进展。
- 人工或专家审查：在某些情况下，新奇性评估可能需要人工审查，特别是在解决方案的复杂性或领域专业知识要求较高的情况下。
- 动态调整：随着搜索的进行，新奇性的定义和评估标准可能需要调整，以反映当前探索的深度和广度。
通过上述方法，新奇性搜索能够系统地识别和保留那些在当前探索中具有独特性的解决方案，促进对未知领域的探索，即使这些新奇解在初期可能不直接带来性能上的提升。
在新奇性搜索（Novelty Search, NS）的实现基础中，保存新颖项信息的核心在于设计一个能够有效记录和管理探索过程中遇到的新颖解决方案的数据结构。以下是实现这一过程的关键步骤和组件：
- 定义 NoveltyItem 类：
- 属性：每个 NoveltyItem 应包含至少两个关键属性：个体的特征向量（代表解决方案的特性）和该个体的新颖性得分。特征向量用于后续的比较和新奇性评估，而新颖性得分则是基于与历史解的比较得出的。
- 方法：可能包括计算或更新新颖性得分的方法，以及用于存储和检索个体特征的接口。
- 新颖性列表（Novelty List）管理：
- 数据结构：使用列表、队列或更高级的数据结构（如平衡二叉搜索树、哈希表）来存储 NoveltyItem 对象。选择哪种数据结构取决于对查找效率、插入速度和内存使用的需求。
- 插入机制：每当评估一个新个体的新颖性时，将其作为 NoveltyItem 对象插入到列表中，并根据需要更新新颖性得分。
- 管理历史记录：为了保持数据结构的效率和实用性，可能需要定期或达到一定容量时移除最“不新奇”的个体，确保只保留最具代表性的或最近的解。
- 新颖性评估：
- 计算新奇性：对于每个新个体，计算其特征与新颖性列表中所有个体特征的相似度，可以使用距离度量（如欧氏距离）。
- 得分更新：基于相似度计算新颖性得分，得分越低表示越新奇。这一步可能需要一个全局或局部的阈值来决定一个个体是否足够新奇以被保留。
- 更新与维护：
- 定期更新：随着搜索的进行，新颖性列表需要定期更新，移除不再新奇的个体，保持列表的动态性和有效性。
- 多样性保持：确保列表中包含多样化的解决方案，避免过早收敛到特定的解决方案类型。
通过这样的实现，NS 能够有效地跟踪和利用探索过程中的新颖性信息，促进对未知解决方案空间的探索，而不是直接追求性能优化。这种方法鼓励算法探索新的行为或解决方案，从而在复杂和多变的问题中找到创新的路径。