从达尔文进化到群体计算与众包游戏

# 从达尔文进化到群体计算与众包游戏 ## 1. 经典计算与进化计算的对比 在技术和科技解决方案的制定中，使用不同的方法一直是一个持续的问题。长期以来，问题的解决主要依赖经典数学工具，如基于无穷小量、在函数空间应用变分法或数值方法等。这些方法能够为简单问题找到最优解，为复杂问题找到次优解。然而，计算和算法的难度不仅随问题的复杂性增加，还与函数自变量的优化类型有关。 在当前的工程问题中，常常会遇到这样的优化任务：函数的自变量定义在不同领域（实数、整数、逻辑、语言），并且自变量可能在允许区间的某些部分发生变化，同时，值还可能受到物理或经济可行性的各种限制，函数本身的范围也是如此。 经典优化方法对于某些超出一定难度或复杂度的任务并不适用。这并不意味着这些问题无法用经典方法解决，而是随着问题复杂度的增加，通常会从解析方法转向数值方法。 在过去几十年里，出现了一系列新颖的算法，即所谓的进化和群体算法。这些算法的名称源于其哲学层面的设计和发展理念。尽管它们部分忽略了“经典严谨”的数学，但具有许多特性，使其得到广泛应用。例如，从业者无需了解经典优化方法，只需对优化问题有深入了解，并能正确定义所谓的成本函数（或适应度），对其进行优化即可解决问题。此外，这些算法总是专注于寻找全局极值，而非像经典优化方法（尤其是数值方法）那样通常寻找局部极值。 不过，这些算法也存在缺点。由于它们基于随机过程，随机性和偶然性在寻找解决方案中起着重要作用，因此结果无法提前准确预测。而且，这类算法的数学证明相对困难，主要依赖于实践经验来证明其可行性和实用性。例如，基于遗传算法对波音飞机燃油消耗的优化，每年能为航空公司节省数亿美元。 同时，随着进化和群体技术以及理论信息学的发展，基于并行化的新计算机技术似乎与这些现代技术相辅相成。如果没有数学上的突破来解决目前原则上难以解决的问题，科学和技术计算的未来无疑在于数学运算的并行化。例如，对于复杂度为 N! 的问题（如旅行商问题），当 N = 59 时，组合数为 (1080)，超过了宇宙中估计的质子数（1079）。如果一个质子能够记录一种可能的组合以供后续评估，对于 N > 59 的问题，宇宙中的内存都不够，更不用说计算时间了。因此，如果没有新的数学方法或合法的数学捷径，并行化和使用现代启发式技术是唯一现实的方法。 ## 2. 进化计算在局部放电模式处理中的应用 ### 2.1 故障检测中的符号回归 局部放电（PD）模式可作为电机绝缘系统以及架空和电缆线路绝缘系统实际状态的指标。随着奥斯特拉瓦技术大学（VSB）设计的专利设备的使用，对中压架空线路进行故障检测的需求日益增加。 以往的实验基于对 PD 模式的基础知识来提取特征。而在不具备这些基础知识的情况下，能够推导出一组相关特征的方法，为解决该问题提供了新的思路。在这种情况下，当需要合成输入变量时，语法进化（GE）可被视为完成此任务的最优算法。 基于进化的合成方法被用于生成一组多项式，作为合成的信号特征。这些特征的值构成了训练分类算法的输入变量集。设计时需要定义它们的形式、目标函数和评估过程。在本次实验中，信号部分经过离散小波变换（DWT）的低通和高通滤波器，得到三个级别的系数（近似和细节）。每个系数序列都作为实验下一阶段的输入，由 GE 驱动合成非线性特征。 符号回归技术是一类能够从简单的用户定义构建块合成复杂解决方案的算法。这些构建块可以是数学运算、编程命令等，在本次实验中，结果是多项式。 该算法的实现基于 ECJ 工具包。定义的语法包含诸如 +、 -、 ×、 ÷、 sin(x)、 cos(x)、 ex 等运算符。为确保所有获得的多项式在数学上的正确性（避免除以零、对负数取对数等），需要对某些操作的行为进行修改。具体的修正协议如下表所示： | 操作 | 符号 | 保护措施 | | --- | --- | --- | | 加法 | + | 无 | | 减法 | - | 无 | | 乘法 | × | 无 | | 除法 | ÷ | 分母为零时输出零 | | 平方根 | √ | 在根号前应用绝对值运算符 | | 自然对数 | log | 参数为零时输出零；对负数参数应用绝对值运算符 | | 正弦 | sin | 无 | | 余弦 | cos | 无 | | 自然指数 | ex | 无 | | 最大值 | max | 无 | | 最小值 | min | 无 | | 求和 | ∑ | 无 | | 乘积 | ⫪ | 无 | 获得的多项式对信号系数进行计算，返回一个单浮点值，作为非线性特征。其相关性通过信息增益（IG）进行评估。IG 标准用于创建 C4.5 决策树，其中 IG 值最高的属性被用作分裂属性。在本次实验中，IG 被用作合成多项式特征的适应度函数。 IG 的计算公式如下： \[ Entropy(X) = - \sum_{i = 1}^{N} p(x_i) \log(p(x_i)) \] \[ Entropy(X, Y) = \sum_{x \in X, y \in Y} p(x, y) \log \frac{p(x, y)}{p(x)} \] \[ IG(X, Y) = Entropy(X) - Entropy(X, Y) \] 其中，$p(x)$ 表示 $x$ 取值为 $x_i$ 的概率，$p(x, y)$ 表示在 $y$ 取值为 $y_i$ 时，$x$ 取值为 $x_i$ 的条件概率。 选择 IG 值最高的前五个指标来构建分类模型的输入数据集，并使用人工神经网络（ANN）进行分类。以下是合成特征的示例： \[ i_1 = \sum_{n = 0}^{4} \sum_{n = 1}^{5} \sum_{n = 4}^{N - 1} \max(\sin(\sin(x_n)), \sin(\sin(x_n)), \cdots, \sin(\sin(x_n))) \] \[ i_3 = \sum_{n = 0}^{N} \min(x_1, x_2, \cdots, x_N) \log(\sin(x)) \] GE 的超参数调整如下表所示： | 参数 | 含义 | 值 | | --- | --- | --- | | 种群大小 | 种群中的候选数量 | 100 | | 基因组长度 | 每个候选的二进制向量大小 | 400 | | 代数 | 整个算法的迭代次数 |