基于GraphEA的图进化优化及混合免疫算法研究

### 基于GraphEA的图进化优化及混合免疫算法研究 在当今的优化算法领域，各种算法不断涌现，以应对不同类型的复杂问题。本文将聚焦于GraphEA在文本提取和机器人控制器优化问题中的应用，以及混合免疫算法中局部搜索的不同应用方式对算法性能的影响。 #### GraphEA在不同问题中的应用 ##### 文本提取问题 在文本提取问题中，研究人员对比了GraphEA和CFGGP两种算法。对于每个问题和每种算法，都进行了20次独立运行，使用不同的随机种子。实验结果总结在表1中，以进化结束时最佳解决方案的适应度（中位数和标准差）来衡量。 | EA | ns = 2, nS = 5 | ns = 3, nS = 5 | ns = 4, nS = 10 | ns = 4, nS = 8 | | --- | --- | --- | --- | --- | | CFGGP | 0.160 ± 0.030 | 0.120 ± 0.050 | 0.092 ± 0.037 | 0.097 ± 0.044 | | GraphEA | 0.169 ± 0.027 | 0.093 ± 0.035 | 0.045 ± 0.015 | 0.043 ± 0.008 | 从表中的数据可以看出，除了最难的问题（ns = 2, nS = 5）外，GraphEA的表现优于CFGGP。基于图的表示方式非常适合学习确定性有限自动机（DFAs），而DFAs是提取器的自然选择，特别是当需要提取器具有紧凑、人类可读的表示时。因此，GraphEA似乎比CFGGP更有能力搜索解决方案空间，因为CFGGP在这种情况下使用的是不太直接的表示方式。 ##### 机器人控制器优化问题 软材料机器人为许多刚性机器人不适合的任务提供了有前景的解决方案。其中，基于体素的软机器人（VSRs）因其柔软性和模块化的特点，成为了研究的热点。然而，设计VSRs是一项复杂的任务，因为其许多组件之间的复杂相互作用难以建模。因此，通常使用优化方法来解决VSR的设计问题，特别是形状和控制器的优化。 在本文中，主要关注机器人控制器的优化问题。给定一个二维形状的VSR，每个体素配备零个或多个传感器，控制器是一个根据传感器读取的数值在每个时间步确定每个体素驱动值的规则。形式上，控制器是一个从Rm到Rn的函数，其中m是传感器读数的数量，n是体素的数量。机器人控制器优化问题的目标是学习一个控制器函数，使给定身体在完成给定任务时达到最佳效果。这里主要关注机器人的移动能力，适应度衡量标准是VSR在20秒模拟时间内移动的距离。 为了解决这个问题，使用GraphEA直接表示一个没有预定义拓扑的人工神经网络（ANN），类似于NEAT，实现了一种神经进化形式。所有表示参数（E、N、遗传算子和种群初始化）与CPPN - GraphEA相同，除了节点的可用基本函数（这里只使用tanh）和输出节点（y1, ..., yn）。 实验考虑了两种身体形状：一个由6×2个体素组成的“蠕虫”和一个由4×2的躯干和两个1×1的腿组成的“两足动物”。在这两种情况下，顶部行的体素配备了感应体素x和y旋转速度的传感器，底部行（对于两足动物来说是腿）的体素配备了触摸传感器，所有体素都配备了当前面积比传感器。 作为基线，使用了CMA - ES算法来优化固定拓扑的多层感知器（MLP）的权重。对于每个问题和每种算法，进行了20次独立运行，使用不同的随机种子。由于CMA - ES的种群大小取决于搜索空间的维度，因此在两种算法进行20000次适应度评估后停