·36 智能系统学报 第8卷 1)选定调度序列π={，m2,…,n},i=0j=1. 4.1数据集 2)i=i+1,如果i>n,则i=i-n 本文采用著名的Taillard数据集作为测试实 3)把π赋给中间序列U,把序列U中的第i个 例，该数据集包含12个子集，每个子集包含10个测 作业π：从U中去除，将π：插入U中所有可以插入 试实例.为了检验算法的有效性，从这些子集中选取 的位置，选取其中最好的调度序列π. 了部分具有代表性的实例作为测试数据，所选实例 4)分别求解序列π和序列U的最小完工时 涵盖了从20个作业5台机器到200个作业10台机 间f(π)和f(U),如果f(π)<f(U),则U= 器不同难度的测试实例，具有很好的代表性.所选实 xj=0;否则j=j+1. 例的规模如表3所示.例如在T04实例中，20×5 5)如果j≤n,转步骤2)；否则，算法结束，m'=U. 表示20个作业在5台机器上运行. 在这个算法中，i和j用来控制循环次数，没有 实际意义，是作业的数目，也是解的维数 表3实例规模 这种局部搜索算法的好处在于：首先，局部搜索 Table 3 The size of instances 策略并没有直接对所选序列进行修改，而是应用于 实 例 规模 实例 规模 一个中间序列U,避免算法陷入局部最优；其次，在 Ta04 20×5 Ta54 50×20 每次搜索过程中，只有找到更好的解时，才对中间序 Tal4 20×10 Ta64 100×5 列进行更新，有利于算法逐步向更优的解靠近.因 Ta24 20×20 Ta74 100×10 此，局部搜索算法在一定程度上加强了萤火虫算法 Ta34 50×5 Ta84 100×20 的局部搜索能力， 改进后的萤火虫算法和原算法相比，初始化部 Ta44 50×10 Ta94 200×10 分使得算法有一个较好的搜索域，局部搜索算法又 进一步提高了算法的搜索性能.改进后的萤火虫算 4.2 实验结果及分析 法求解阻塞流水线调度问题的步骤如下： 实验中，种群大小为10，最大迭代次数tm为 1)初始化种群，包括迭代次数t=0、最大迭代 100,、B、Y的设置参考了萤火虫算法相关文献 次数t、随机参数、个体吸引力B,、介质吸收率 [9,13-14]中的参数设置，a6设置为0.9，B。设置为 Y、局部搜索概率p. 1.0,y设置为0.9，局部搜索概率p设置为0.2.对 2)按照式(1)~(5)计算每个个体的最小完工 于前6个实例，每个实例进行10次独立实验；对于 时间. 后4个实例，由于数据量较大，每个个体进行5次独 3)萤火虫算法 立实验.为了测试改进后的萤火虫算法在阻塞流水 ①更新； 线调度问题中的性能，还对同等条件下的未改进的 ②对当前个体，如果有比自己更亮的个体，则按 萤火虫算法和标准的粒子群算法进行了测试.表4 照改进后的更新方式，利用式(7)或(8)对当前个体 为未改进的萤火虫算法的测试结果，表5为标准粒 的位置进行更新；否则，采用莱维飞行对个体位置进 子群算法的测试结果，改进的萤火虫算法的测试结 行更新 果列于表6中.其中，在标准的粒子群算法中， 4)按照式(1)~(5)计算每个个体的最小完工 2个学习因子c1和c2取值为2，惯性权重w设置 时间. 为0.7 5)系统产生一个随机数，如果这个随机数小于 由表4、5可以看出，无论是最小值、最大值，还 局部搜索概率P,则对种群个体进行局部搜索，并更 是平均值，萤火虫算法的求解结果普遍优于标淮粒 新种群。 子群算法.对比表4和表6，可以发现，改进的萤火 6)t=t+1,如果t≥tmm或算法达到其他标准，则 虫算法在求解效果上要远远优于基本的萤火虫算 算法终止；否则，转步骤3) 法，而且求解结果更加稳定.综合表4~6，改进后的 4仿真实验 萤火虫算法的求解效果明显优于基本的萤火虫算法 和标准的粒子群算法.并且随着种群的增大，这种差 实验所用PC机的处理器为AMD Athlon64X2 距更加明显，充分体现了算法的有效性，而且新算法 3600+1.91GHz,内存为960MB,编程工具采用 的求解效果更加稳定. Matlab 7.0