·246· 智能系统学报 第13卷 ①变异操作，执行式(1)： 的。函数的详细说明详见文献[25]。 ②交叉操作，执行式(2)： 3.2实验设置 ③选择操作，执行式(3)，其中子种群在计算适 本实验采用Spark云模型，每个节点的配置如下： 应度值时，按照其位置信息替换掉bestInd中的部 64 bit corei?7CPU主频3.4GB,内存8GB,Ubuntul3.10 分解。 操作系统，安装使用Hadoop22.2.0和Spark1.2.0,编 10)利用collect动作算子将所有低维子种群按 程环境为ntel山IDEA14.l.2,使用Scala和Java语言。 协同机制合并成完整种群，并更新Pop; 为了验证SparkDECC的性能以及影响其性能 II)对Pop进行全局搜索并返回最优个体bestInd; 的各个因素，实验时SparkDECC中问题的维度 12)转到5)： D=1000,子问题的维度DimSub=100,问题规模 l3)循环结束，通过reduce返回最优值best。 NP=100,F=0.5,CR=0.9,每个子种群独立运行的代 在上述SparkDECC算法中，包含两个循环，即 数MaxGen=-100,合并轮数Cycles=50。为了验证 6)、10)。外循环6)控制问题的全局优化，内循环 SparkDECC算法的可扩展性，将问题的维度D扩展 10)控制子问题的局部优化。 到5000，其他参数保持不变。 上述算法的时间复杂度主要集中在10)，其主 3.3实验结果与分析 要功能是在Num个分区中同步并行优化M个低维 表1为SparkDECC与OXDE、CoDE、jDE、 子问题。一个低维子问题的时间复杂度为O(Mx PSO2刃算法的平均最优值和标准方差的结果对比。 NP),M个低维子问题在一个分区里按串行方式进 5种算法的参数设置一致，各算法独立运行25次。 化Gen代，运行Cycles轮的时间复杂度为O(MxNP× 采用了Wilcoxon秩和检验方法对4种算法的实验 Gen×Cycles)。在上述算法中，略去其他步的时间复 结果进行了统计分析，显著性水平为0.05，其中，“_” 杂度。因此，SparkDECC算法在每个分区的时间复 表示劣于，+”表示优于，“≈”表示相当于。 杂度为O(MxNPxGenxCycles)/Num。 表1中，SparkDECC与其他3种DE算法进行 3 数值实验与分析 对比，结果表明，SparkDECC在f、5、f6、fio~fi3共 7个函数能快速收敛到最优结果，实验数据优于其 3.1测试问题 他3种算法；SparkDECC算法在5、f和6等3个 为了测试SparkDECC算法求解大规模优化问 函数的收敛出现了停滞，实验结果弱于其他算法； 题的性能，本文选取了文献[25]中13个测试函数进 在不可分解函数上各算法的运行效果相当；方要 行实验。其中~为单模函数，f:为多模函数， 劣于DE,优于OXDE和CoDE;带噪声函数5的实 ∫和5为不可分解的函数，其他函数都是可分解 验结果劣于CoDE,优于jDE,与OXDE相当。 表1 SparkDECC、OXDE、CoDE、jDE、PSO算法的平均值、标准差和Vilcoxon秩的检验结果 Table 1 Comparison of SparkDE,OXDE,CoDE,jDE and PSO algorithms for solving the results OXDE (mean+std) CoDE (mean+std) jDE (mean+std) PSO(mean+std) SparkDECC (mean+std) 4.76×102±1.67×102-1.50x10±1.74×105-2.46x10±1.23×103-2.30x10±2.79x10- 5.85x10±1.62×101B 5.27x10'6.89x100-8.89x109.74×101-1.74×100±8.62x1010+ 7.16×10±3.30x10- 6.60x10±1.00×107 5 1.54x106±2.33×105+4.50x106.12×10*3+7.54×10±1.48×10+8.68×10t86.51×10”-5.31×10*7±7.20×106 f 2.59x10±1.84×100=2.67×10±1.95x10=5.04x104.58×10≈4.01x10±7.98x100- 9.76×10±2.22×10 2.28×10±7.08×103- 2.39×10±2.12×102=2.18×103±2.21×102≈9.23x102±1.29×102 1.62x10±1.62×102 7.86×105±8.86x102-5.26×106.26×101-1.06×10±2.98x105-2.30x10±1.29x105 1.60×10±4.73×10 5.68×10±7.25×10≈9.06×10±1.03x10+2.91×10±1.60x101-3.48x1013±3.87×102- 3.62×10±1.67×10 4.17×10±7.27x102+-1.89x10±5.14×105+-4.19×10±3.18×10+-1.34×10±4.51×103+ -6.11×10±1.18×103 4.94×102±5.32×10+ 4.59x10±2.10×102+2.98×10±4.03×10+2.33×10±1.35×105- 1.10x10“±3.93×10 io 6.49x10±2.79×10-2.25x10±1.82×10-5.12×10±7.06x10-2.15×10'±3.77×102- 4.55×10±8.16×109 5.02×10±1.19x10°-7.70x1032.29×102-8.91×10±7.39×10-5.75×102±4.15×101- 3.54×10“±1.03×1014 2 3.01×100±7.11x10-1-5.75×1024.85×102-1.32x10±2.20x106-6.99×10t2±7.75x10*1_ 7.46×10±2.58×103 1.94×10±3.40x102- 1.15x102±7.53×101- 1.14x10*7±8.17×106-7.87×102±8.78×10 8.79x10±3.04×103 + 8/3/2 7/42 7/4/2 12/1/0① 变异操作，执行式 (1)； ② 交叉操作，执行式 (2)； ③ 选择操作，执行式 (3)，其中子种群在计算适 应度值时，按照其位置信息替换掉 bestInd 中的部 分解。 10) 利用 collect 动作算子将所有低维子种群按 协同机制合并成完整种群，并更新 Pop； 11) 对 Pop 进行全局搜索并返回最优个体 bestInd； 12) 转到 5)； 13) 循环结束，通过 reduce 返回最优值 best。 在上述 SparkDECC 算法中，包含两个循环，即 6)、10)。外循环 6) 控制问题的全局优化，内循环 10) 控制子问题的局部优化。 上述算法的时间复杂度主要集中在 10)，其主 要功能是在 Num 个分区中同步并行优化 M 个低维 子问题。一个低维子问题的时间复杂度为 O(M× NP)，M 个低维子问题在一个分区里按串行方式进 化 Gen 代，运行 Cycles 轮的时间复杂度为 O(M×NP× Gen×Cycles)。在上述算法中，略去其他步的时间复 杂度。因此，SparkDECC 算法在每个分区的时间复 杂度为 O(M×NP×Gen×Cycles)/Num。 3 数值实验与分析 3.1 测试问题 为了测试 SparkDECC 算法求解大规模优化问 题的性能，本文选取了文献[25]中 13 个测试函数进 行实验。其中 f1~f8 为单模函数，f9~f13 为多模函数， f4 和 f5 为不可分解的函数，其他函数都是可分解 的。函数的详细说明详见文献[25]。 3.2 实验设置 本实验采用 Spark 云模型，每个节点的配置如下： 64 bit corei7 CPU，主频 3.4 GB，内存 8 GB，Ubuntu13.10 操作系统，安装使用 Hadoop2.2.0 和 Spark1.2.0，编 程环境为 IntellJ IDEA14.1.2，使用 Scala 和 Java 语言。 为了验证 SparkDECC 的性能以及影响其性能 的各个因素，实验时 SparkDECC 中问题的维度 D=1 000，子问题的维度 DimSub=100，问题规模 NP=100，F=0.5，CR=0.9，每个子种群独立运行的代 数 MaxGen=100，合并轮数 Cycles=50。为了验证 SparkDECC 算法的可扩展性，将问题的维度 D 扩展 到 5 000，其他参数保持不变。 3.3 实验结果与分析 表 1 为 SparkDECC 与 OXDE[26] 、CoDE、jDE、 PSO[27]算法的平均最优值和标准方差的结果对比。 5 种算法的参数设置一致，各算法独立运行 25 次。 采用了 Wilcoxon 秩和检验方法对 4 种算法的实验 结果进行了统计分析，显著性水平为 0.05，其中，“–” 表示劣于，“+”表示优于，“≈”表示相当于。 表 1 中，SparkDECC 与其他 3 种 DE 算法进行 对比，结果表明，SparkDECC 在 f1、f5、f6、f10~f13 共 7 个函数能快速收敛到最优结果，实验数据优于其 他 3 种算法；SparkDECC 算法在 f3、f8 和 f9 等 3 个 函数的收敛出现了停滞，实验结果弱于其他算法； 在不可分解函数 f4 上各算法的运行效果相当；f2 要 劣于 jDE，优于 OXDE 和 CoDE；带噪声函数 f7 的实 验结果劣于 CoDE，优于 jDE，与 OXDE 相当。 表 1 SparkDECC、OXDE、CoDE、jDE、PSO 算法的平均值、标准差和 Wilcoxon 秩的检验结果 Table 1 Comparison of SparkDE, OXDE, CoDE, jDE and PSO algorithms for solving the results F OXDE (mean±std) CoDE (mean±std) jDE (mean±std) PSO (mean±std) SparkDECC (mean±std) f1 4.76×10+2±1.67×10+2－ 1.50×10–5±1.74×10–5－ 2.46×10–6±1.23×10–5－ 2.30×10+6±2.79×10+4－ 5.85×10–13±1.62×10–13 f2 5.27×10+1±6.89×10+0－ 8.89×10–1±9.74×10–1－ 1.74×10–10±8.62×10–10 + 7.16×10+4±3.30×10+4－ 6.60×10–7±1.00×10–7 f3 1.54×10+6±2.33×10+5 + 4.50×10+4±6.12×10+3 + 7.54×10+4±1.48×10+4 + 8.68×10+8±6.51×10+7－ 5.31×10+7±7.20×10+6 f4 2.59×10+1±1.84×10+0 ≈ 2.67×10+1±1.95×10+0 ≈ 5.04×10+1±4.58×10+0 ≈ 4.01×10+2±7.98×10+0－ 9.76×10+1±2.22×10–1 f5 2.28×10+4±7.08×10+3－ 2.39×10+3±2.12×10+2 ≈ 2.18×10+3±2.21×10+2 ≈ 9.23×10+12±1.29×10+12－ 1.62×10+3±1.62×10+2 f6 7.86×10+3±8.86×10+2－ 5.26×10+1±6.26×10+1－ 1.06×10+4±2.98×10+3－ 2.30×10+6±1.29×10+5－ 1.60×10–1±4.73×10–1 f7 5.68×10+0±7.25×10–1 ≈ 9.06×10–1±1.03×10–1 + 2.91×10+1±1.60×10+1－ 3.48×10+13±3.87×10+12－ 3.62×10+0±1.67×10–1 f8 –4.17×10+5±7.27×10+2 + –1.89×10+5±5.14×10+3 + –4.19×10+5±3.18×10–1 + –1.34×10+5±4.51×10+3 + –6.11×10+4±1.18×10+3 f9 4.94×10+2±5.32×10+1 + 4.59×10+3±2.10×10+2 + 2.98×10+0±4.03×10+0 + 2.33×10+6±1.35×10+5－ 1.10×10+4±3.93×10+1 f10 6.49×10+0±2.79×10–1－ 2.25×10+0±1.82×10–1－ 5.12×10+0±7.06×10–1－ 2.15×10+1±3.77×10–2－ 4.55×10–8±8.16×10–9 f11 5.02×10+0±1.19×10+0－ 7.70×10–3±2.29×10–2－ 8.91×10–1±7.39×10–1－ 5.75×10+2±4.15×10+1－ 3.54×10–14±1.03×10–14 f12 3.01×10+0±7.11×10–11－ 5.75×10–2±4.85×10–2－ 1.32×10+6±2.20×10+6－ 6.99×10+12±7.75×10+11－ 7.46×10–4±2.58×10–3 f13 1.94×10+3±3.40×10+2－ 1.15×10+2±7.53×10+1－ 1.14×10+7±8.17×10+6－ 7.87×10+12±8.78×10+11－ 8.79×10–4±3.04×10–3 –/+/≈ 8/3/2 7/4/2 7/4/2 12/1/0 ·246· 智 能 系 统 学 报 第 13 卷