当前位置：首页 > news >正文

NICE Seminar(2023-07-16)|演化算法的理论研究到底有什么用？(南京大学钱超教授)

模式定理（Schema Theorem）

模式定理（Schema Theorem）是遗传算法（Genetic Algorithm, GA）的重要理论基础，由约翰·霍兰德（John Holland）在1975年提出。它描述了具有特定模式（schema）的基因片段在遗传算法中如何传播和保留的过程。以下是模式定理的详细介绍：

模式是一种模板，表示在某些位置上具有相似性的字符串子集。模式用“*”符号表示可以是任何值。例如：

模式定理的数学表达式如下：

模式定理揭示了以下几方面的内容：

假设在一个二进制遗传算法中，一个长度为10的个体有一个模式101*0*1*01，这个模式具有较高的适应度，并且定义长度较短。在这种情况下，根据模式定理，这个模式在下一代中会被更多地保留和传播，从而提高种群整体的适应度。

模式定理通过描述模式的保留和传播，解释了遗传算法如何通过选择、交叉和突变操作，在进化过程中逐步逼近最优解。

d m y 表示解的目标值

是由Wolpert和Macready在1997年提出的，它是计算复杂性理论中的一个重要概念，特别是在演化算法和机器学习领域。没有免费午餐定理指出，没有任何一种算法能够在所有可能的问题上普遍优于其他所有算法。

以下是定理的主要内容：

算法的普遍性能：NFL定理表明，如果我们考虑所有可能的问题（包括所有可能的输入和目标函数），那么所有算法的期望性能是相同的。换句话说，没有任何算法能够在所有问题上都表现得更好。
特定问题上的性能：尽管在所有可能的问题上的平均性能是相同的，但在特定问题上，一些算法可能会比其他算法表现得更好。

算法选择：NFL定理意味着在选择算法时，必须考虑特定问题的特性。没有一种算法是通用的，最好的算法取决于问题的性质。
偏差与适应性：NFL定理强调了算法设计中的偏差与适应性之间的权衡。一个算法可能在某些问题上表现良好，但这是因为它对这些特定类型的问题有适应性（或偏差）。

没有免费午餐定理是对算法设计和性能评估的一种哲学上的提醒，它强调了算法与问题之间的相互作用，以及在设计和选择算法时应考虑的问题特定性。

在优化问题中，目标空间和决策空间是两个核心概念，它们分别描述了优化问题的不同方面。

决策空间是指所有可能的决策变量值的集合。它定义了优化问题中可以探索的解的范围。决策空间中的每一个点都对应于问题的一个潜在解。

特性：
- 通常由一组变量 x_1, x_2, ..., x_nx1,x2,...,xn 定义，这些变量可以是连续的或离散的。
- 决策空间的维度等于决策变量的数量。
- 决策空间的边界可能由变量的物理限制或问题的约束条件决定。
例子：
- 在线性规划问题中，决策空间可能是所有线性不等式约束下的解集合。
- 在工程设计问题中，决策空间可能包括所有可能的设计参数值。

目标空间是指所有可能的目标函数值的集合。它是决策空间中每个点通过目标函数映射后形成的空间。在多目标优化问题中，目标空间通常是多维的，每个维度对应一个目标函数。

特性：
- 由目标函数 f(x)f(x) 的输出定义，其中 xx 是决策空间中的一个点。
- 目标空间可以是单维的（单一目标优化问题）或多维的（多目标优化问题）。
- 目标空间中的点通常表示优化问题的某种性能或质量指标。
例子：
- 在单目标优化问题中，目标空间可能是一维的，表示成本或收益的值。
- 在多目标优化问题中，目标空间是多维的，可能表示多个相互冲突的目标，如成本、质量、时间等。