第5期 谷文祥，等：求解流水线调度问题的万有引力搜索算法 ·415 M- 「1 需要遍历与之相对应的时间矩阵，其时间复杂度为 0(2md),由于需要计算所有物体的适应度，那么需 式中：M为随机矩阵，其每一行至少1个正数，更为 要消耗的时间为0(2mnd),在最坏情况下，在每一 N-1维行向量，显然M是一个可约随机矩阵，且 次迭代中每个物体都要更新它的当前位置和速度， M21、M2不是零矩阵，根据可约随机矩阵的性质有 质量和加速度的时间复杂度为O(6mnd2),当规模 M=(M,0,…,0),其中M>0.因为M°可以看 逐渐增大即m×n趋于无穷时，6mnd≥12nd≥2n, 作一个状态分布，所以M=1,于是M=(1,0,…, IGSA的时间复杂度为O(mnd2). 0),即算法收敛到c 5 仿真实验 所以，经过若干次迭代后，种群对应的调度状态 可以收敛到(c‘,c,…,c). 实验采用Carlier、Reeves、Trillard1所提 定理3IGSA算法的空间复杂度为O((6n+ 供的不同规模的数据集，为了检测算法的性能，在处 2m)×d),群体每次进化的最坏渐进时间复杂度为 理器为Pentium3.0GHz、内存为l.0GB的PC机上 O(mnd2),其中n为群体规模，d表示作业数量，m 进行测试，采用Matlab7.0编码.算法的参数设置 表示处理机个数。 为：种群为作业数n的2倍，最大迭代次数为1000， 证明在IGSA算法运行中，物体的当前位置、 局部搜索的迭代次数为5n(n-1).每个作业运行 当前速度、物体的质量、物体的加速度、物体之间的 20次.在Cariler、Reeves数据集中，使用本文提出的 距离以及物体所受的合力都要被存储，群体规模为 IGSA算法分别与几种构造启发式算法[]和元启发 n,那么它所消耗的存储空间为0(6nd),在求解物 式算法「51进行比较，实验结果如表4~7所示.表4、 体的适应度时还要存储调度问题的时间矩阵，所消 6是统计的最小完工时间，表5、7是最小完工时间 耗的存储空间为O(2md),所以IGSA算法的空间复 的百分比.实验结果表明IGSA是优于其他算法的. 杂度为0((6n+2m)×d).求解每个物体适应度时 表4IGSA算法在Cariler上与构造启发式算法比较 Table 4 Comparison of IGSA and construction heuristics on Carlier 问题规模 构造启发式算法 问题 最优解 IGSA算法 0 Palme Gupta CDS RA NEH Carl 7038 11 5 7472 7348 7202 7817 7038 7038 Car2 7166 13 4 7940 7534 7410 7509 7940 7166 Car3 7312 12 J 7725 7399 7399 7399 7503 7312 Car4 8003 14 o 8423 8423 8423 8357 8003 8003 Car5 7720 10 8520 8773 8627 8940 8190 7720 Car6 8505 8 9 9487 9441 9553 9514 9519 8505 Car7 6590 7 7 7639 7639 6819 6923 7668 6590 Car8 8366 8 8 90239224 89039062 9032 8366 表5IGSA算法在Cariler上与元启发式算法比较 Table 5 Comparison of IGSA and meta-heuristics on Cariler 问题规模 元启发式算法 问题 IGSA算法 m GA H_GA DPSO DPSO +LS SPSOA Carl 11 5 0.00 0.00 0.00 0.00 0.00 0.00 Car2 13 0.00 0.00 0.00 0.00 0.00 0.00 Car3 12 2.42 0.00 1.09 0.00 0.00 0.00 Car4 14 4 0.00 0.00 0.00 0.00 0.00 0.00 Car5 10 6 0.36 0.00 0.62 0.00 0.00 0.00 Car6 0 0.00 0.76 0.00 0.00 0.00 0.00 Car7 0.00 0.00 0.00 0.00 0.00 0.00 Car8 8 8 0.00 0.00 0.00 0.00 0.00 0.00