第1期 郭丽萍，等：改进的萤火虫算法求解阻塞流水线调度问题 ·35 力还和介质的吸收率有关9)，因此把个体在距离该 个体的最小完工时间.让2个种群中的个体按序号 个体为r的位置对其他个体的吸引力定义为 两两进行比较：种群1中的第1个个体和种群2中 B(r)=Boer2. 的第1个个体进行比较，选择其中最小完工时间较 式中：B,表示2个个体距离为0时，当前个体对另 小的个体，作为新种群的第1个个体；种群1中的第 外1个个体的吸引力，y为介质的吸收率。 2个个体和种群2中的第2个个体进行比较，选择 在该算法中，2个个体之间的距离r采用欧式 其中最小完工时间较小的一个，作为新种群的第2 距离.个体i向着比它更亮的个体j进行更新的公式 个个体；依此类推，新种群作为初始化种群.此外，由 定义为 于NEH(Nawaz-Enscore-Ham)[o启发式算法是目前 女=+Be(g-x)+a(R-2. (7) 求解流水线调度最有效的启发式方法之一，因此，在 初始化种群时还引入了NEH的思想.种群的第1个 式中：x:和分别表示个体i和个体j在整个种群 个体由NEH启发式方法生成，其他个体由双重初始 更新之前的位置，x表示个体i朝着比自己更亮的 化方式生成，从而使得算法有一个较好的初始化 个体j更新之后的位置，"代表个体i和个体j之间 环境 的距离，Be表示个体j对个体i的吸引力，a是 目前，人们已经发现很多昆虫存在莱维飞行 一个[0,1]内的随机数，R为一个随机数生成函数， (L6 yflights)a,且莱维飞行已经应用于优化领 生成[0,1]内的随机数 域，并取得了预期的良好效果.为了增强算法的全局 3 改进的萤火虫算法求解阻塞流水线 搜索性能，避免种群陷入局部最优，在萤火虫算法的 搜索过程中，如果当前个体找不到比自己更优的个 调度问题 体时，选择莱维飞行代替原算法中的随机飞行.此 虽然萤火虫算法在函数优化方面表现出了较好 外，对于那些种群中非最优的个体，对它们的飞行公 的计算性能，但是，它在求解阻塞流水线调度问题中 式进行改进：当它们发现比自己更亮的个体时，首先 仍然存在早熟现象，为了提高算法的寻优性能，本文 由系统产生一个随机数q,如果q小于0.5，则按照 对萤火虫算法进行了一些改进， 式(8)进行更新：否则，仍采用式(7)对个体的位置 萤火虫算法应用于求解阻塞流水线调度问题 进行更新 时，首先调到的问题就是如何将实数编码离散化.本 文提出一种最小排序方法，这种方法可以将个体的 对=对+Be(与-对)+a(R-2》.(8) 实数编码形式转化成离散的调度序列.该方法对初 式中：x仍然表示个体j在整个种群更新之前的位 始化后的实数序列从小到大进行排序，它们的排序 置，x表示的是第i个个体朝着前j-1个体中比自 序号构成一个离散序列，将这个序列作为该实数序 己亮的个体更新之后的新位置，x表示x朝着比自 列对应的离散调度序列.如表2所示，0.43是实数 己亮的个体j更新之后的位置，「代表个体i和个体 编码序列中最小的实数，从小到大排序后，它的序号应 j之间的距离，Be表示个体j对个体i的吸引力. 该为1；同理，0.91是实数序列中最大的，因此其序号为 可以看出，式(8)是实时更新的，式(7)仅仅依赖于 5.新生产的序列{4,2,5,1,3}作为实数序列{0.85， 整个种群移动之前的个体位置.这样的飞行更新方 0.56,0.91,0.43,0.76}对应的离散调度序列. 式能够增加飞行的随机性，有利于保持种群的多样 表2个体表示形式 性，增大种群搜索空间. Table 2 The presentation of an object 为了加速种群的收敛，本文还提出了一种α的 维数 X 更新方式，使得α随着迭代次数逐渐减小，更新公 1 0.85 4 式为 2 0.56 0 式中：o选用0.9，t为迭代次数. 0.91 对于一个调度序列而言，目前主要有3种产生 0.43 新序列的方法：插入、交换和逆序6.其中，插人方 J 0.76 法被证明为最适合产生一个新序列的方法.为了加 其次，在种群初始化时，本文设计了一种双重初 强萤火虫算法的局部搜索能力，本文引入了一个局 始化方法：分别生成2个种群，计算2个种群中每个 部搜索算法.局部搜索算法可以描述如下)：