第5期 谷文祥，等：求解流水线调度问题的万有引力搜索算法 .413· 用这种方式，所有物体的位置将被转化为一个新的 体，可以提高优化算法性能.采用如下方式生成： 调度方案，在表1中，使用一个简单的例子来阐述这 xg=(xm-xnta）Xr+xaia 个规则.从表1中，可以很显然地看出1.45是最大 式中：x=0,xm=4.0,r为(0,1)内产生的随机数 的值，所以维数为4对应的调度排序为1.稍小的是 3.4局部搜索算法 1.32,则维数为6对应的调度排序为2.用相同的方 IGSA算法虽然收敛速度比较快，但是它的收敛 法，可以得到它的调度方案为π=（3,4,5,1,6,2). 精度比较低.算法虽然具有比较强的全局搜索能力， 虽然这个方法比较简单，但是它能使得GSA能够求 但它的局部搜索能力较弱，为了提高解的质量，引入 解流水线调度问题. 了2种局部搜索的算子：插人和交换.这样可以有效 表1X的解表示 地避免搜索过程陷入局部极小值，也有利于全局空 Table 1 Solution representation of Agent X 间搜索和局部区域改良能力的平衡. 维数1234 6 交换算子：从1个调度方案挑选出2个不同作 x1.250.850.631.450.231.32 业，并且交换它们的位置 插入算子：从1个调度方案挑选出2个不同作 4516 2 业，将这2个作业之间的作业随着相同的方向移动 3.2边界变异 表1显示的调度方案为π=(3,4,5,1,6,2)，随 在GSA算法的实现过程中，当某个物体在搜索 机选出2个位置2和4，表2显示出执行交换算子所 过程中由于牛顿第二定律（运动定律）的作用使得 得结果，表3显示出执行插入算子所得结果. 物体运动出可行域时，通常的处理方法是使该位置 表2交换算子 处于边界上，即为如下的方法： Table 2 Swap f(x:>xma）then 维数 1 2 3 4 5 6 max x1.251.450.630.850.231.32 End T 3 1 5 If(x;<xmin)then 4 6 2 =Xmin 表3插入算子 End Table 3 Insert 经过这种处理后，所有的越界的物体都聚集在 维数 1 23 456 边界处.对于调度问题，这样的设置将导致排序不惟 号 1.250.631.450.850.231.32 一，当同时有2个物体都越界，这样将会有2个相同 3 5 1 4 6 2 的值，进行排序会产生问题.为了避免这种问题的发 生，将越界的物体作下面的改变，提出一种边界变异 在此基础上，提出一种新的局部搜索算法，可以 的方法： 有效地提高解的质量.算法的伪代码工作流程如下 f(x:>xmr）then 描述 x:=xax-c*rand(·）*xma Procedure local search (z) Begin End Let s,=x permutation of the global solution f(x:<xin）then for i=I to genmax 名：=xin+c*rand(·）*(-xmin) S=5 End f(s)=f(s) 其中：c=0.01,rand为[0,1]之间的一个随机 Find r and r2 randomly and rr if (rand<0.5) 数，从以上的过程可以看出，对越界的物体做了变异 s'=swap (s,r,r) //Swap 操作后，物体不再聚集在边界上，而是分布在离边界 else c×rand附近的可行空间内.通过这种操作，即使物 s'=insert (s,r,r2) //Insert end 体在不可行空间内，克服了使用最大排序规则时产 calculate f(s')//Calculate the makespan 生的排序不惟一问题，同时也增加了物种的多样性。 of the new permutaion 3.3IGSA算法的初始化 if(fs'）-f(s)<=0) 初始物体的位置是GSA搜索的起点.好的初始 S=x' f(s)=f(s') 群体有助于提高解的质量.一个好的初始种群可以 end //end if 保证一定的分布性，这样可以分布覆盖整个解空间. end //end for 从另一方面应包含部分较高质量的个体，以指导算 End 法能搜索到比较好的解.所以，一个高质量的初始群