求解FJSP的自适应免疫遗传算法

统 仿 真 学 报© V ol. 21 No. 12

2009年6月 Journal of System Simulation Jun., 2009

求解FJSP 的自适应免疫遗传算法

马 佳1, 2, 石 刚1, 高立群1, 李 丹1

(1.沈阳航空工业学院经济与管理学院, 沈阳 110134; 2.东北大学信息科学与工程学院, 沈阳 110004)

摘 要：借鉴生物免疫系统的免疫调节机理，提出一种求解柔性作业车间调度问题的自适应免疫遗传算法(AIGA)。该算法在保留基本遗传算法(SGA) 随机全局搜索能力的基础上，通过引入免疫算子和种群的自适应调节策略，保持了群体的抗体多样性。实验结果表明，该算法可有效改善基本遗传算法的未成熟收敛和局部搜索能力差的缺点，具有很好的全局收敛能力，能有效解决柔性作业车间调度问题。

关键词：柔性作业车间调度；免疫遗传算法；免疫算子；自适应策略；疫苗

中图分类号：O224 文献标识码：A 文章编号：1004-731X (2009) 12-3609-05

Adaptive Immune Genetic Algorithm for Flexible Job-shop Scheduling Problem

MA Jia 1,2, SHI Gang 1, GAO Li-qun 1, LI Dan 1

(1. School of Economic and Management, Shenyang Institute of Aeronautical Engineering, Shenyang 110134, China;

2. School of Information Science and Engineering, Northeastern University, Shenyang 110004, China)

Abstract: Based on the immune regulating mechanism of biological immune system, a kind of adaptive immune genetic algorithm (AIGA ) was introduced to deal with flexible job-shop scheduling problem . This algorithm not only preserves global research ability of simple genetic algorithm (SGA ), but also adopts the immune operator and adaptive regulation strategy to improve greatly the diversity of antibodies population . Experimental results show that the proposed AIGA can rise above efficiently such difficulties of SGA as precocious convergence and poor local search ability and provide well the global converging ability to enhance both global convergency and convergence rate, thus solving effectively the FJSP problem.

Key words: flexible job-shop scheduling problem; immune genetic algorithm; immune operator; adaptive strategy; vaccine

引 言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)是柔性生产管理及组合优化等领域的一个研究热点，也是理论研究中最为困难的优化问题之一，具有很强的理论意义和工程背景。然而，作业车间调度具有建模复杂、计算复杂和多约束等特点，属于组合优化问题，被证明是典型的NP-hard 问题，至今尚无很好的解决方法。近年来，很多学者将遗传算法应用于柔性作业车间调度问题中，取得了一定的研究成果[1]。但是尽管遗传算法在一定条件下具有全局收敛特性，但该算法的交叉、变异、选择等操作一般都是在概率意义下随机进行的，虽然保证了种群的群体进化性，但在一定程度上不可避免出现退化现象。在某些情况下，这种退化现象还相当明显。

免疫遗传算法(Immune Genetic Algorithm ，IGA)是近年来基于生物免疫机制提出的一种改进遗传算法，它是生命科学中免疫原理与基本遗传算法(Simple Genetic Algorithm, SGA)的结合[2]

。免疫算法是一种有效的全局寻优算法，它在

收稿日期: 2007-10-10 修回日期: 2007-12-28 基金项目: 国家自然科学基金 (60274009)

作者简介: 马佳(1979-), 女, 辽宁沈阳人, 博士生, 研究方向为智能优化, 生产调度; 高立群(1949-), 男, 辽宁沈阳人, 教授, 博导, 研究方向为智能优化, 经济控制论, 决策; 石刚(1978-), 男, 辽宁沈阳人, 博士生, 研究方向为智能优化, 模糊控制。

进化规划中加入了免疫操作，在一定程度上抑制了进化规划完全随机寻优过程中的退化和在进化后期可能产生的波动现象。因此，将免疫算子引入遗传算法中，可以提高算法的整体性能，并使其有选择、有目的的利用信息特征来抑制优化过程中的个体退化现象，提高了算法的全局收敛性。

本文提出了改进的免疫遗传算法，在增加免疫算子的同时，在算法中将自适应策略用于交叉和变异操作中，称为自适应免疫遗传算法(Adaptive Immunity Genetic Algorithm, AIGA)。将该算法应用于柔性作业车间调度的实例中，仿真结果表明该算法是有效可行的。

1 柔性作业车间调度问题描述

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)可描述为将n 个加工顺序不同的工件在m 台机器上加工完成。每个工件使用同一台机器可以多于一次，每道工序的加工过程不允许中断。机器的集合用U 来表示，每个工件J 包含n j 道工序，各工序之间的顺序不允许改变。O ij 表示工件J 的第i 道工序，它可以在有处理能力的任何一台机器上被加工。p i,j,k

表示工序O ij 用机器M k 来加工所需要的时间，可用集合,,{|1;1;1}i j k j T p j N i n k M =≤≤≤≤≤≤表示，N 为工件的数量，M 为机器的数量。例如表1即是一个实际的柔性工作车间调度加工时间表。

2009年6月 系 统 仿 真 学 报 Jun., 2009

表1 柔性作业车间调度加工时间表 M 1

M 2

M 3

M 4

O 1,1 1 3 4 1 O 1,2 3 8 2 1 J 1

O 1,3 3 5 4 7

O 2,1 4 1 1 4 O 2,2 2 3 9 3 J 2

O 2,3

9 1 2 2 O 3,1 8 6 3 5 J 3

O 3,2 4 5 8 1

在柔性作业车间调度问题中，应满足以下假设： 1) 所有的机器在时间t ＝0时都是可以使用的，每个工件都可以在t ＝0时开始加工。

2) 在给定的时间内，一台机器只能加工一道工序，直到加工完此工序后方可加工其它工序，这就是所谓的资源约束。

3) 对于每个工件的各道工序只能按照事先给定的顺序加工，这就是所谓的优先约束。

对于每一道工序O i,j ，我们用r i,j 来表示其最早开始加工时间，对不同的工序分别用下式进行计算：

,1,,0

i j i j i j r r γ−⎧=⎨+⎩12,1j j N i n j N ≤≤≤≤≤≤

式中：,,,min (),1,1i j k i j k j p i n j N γ=≤≤≤≤

对于FJSP 来说一般存在两个难题：第一个是如何为每道工序选择合适的机器；第二个是如何计算每道工序的开始加工时间t i,j 和结束加工时间tf i,j 。

本文所要研究的FJSP 的优化目标是，在满足上述优先约束和资源约束的条件下寻找最优调度方案，使全部工件的最大完工时间(Makespan)最短。

2 作业车间调度的自适应免疫遗传算法

2.1 算法基本思想

免疫遗传算法是一种新型的融合算法。它借鉴生物免疫系统的自适应识别和排除侵入人机体的抗原性异物的功能，将生物免疫系统的学习、记忆、多样性和模式识别的特点引入遗传算法[3]。免疫系统由抗原识别系统、记忆机制、抗体促进与抑制等部分组成，通过细胞可以产生大量抗体来抵御各种抗原，将这种机制加入遗传算法可以提高算法的全局搜索能力而不限于局部解；通过对抗体的促进和抑制可以自我控制产生一些必要的抗体，对应于免疫遗传算法，其可以有选择、有目的地利用待求问题中的一些特征信息或知识来抑制其进化过程中出现的退化现象，从而提高局部搜索能力；具有记忆机制，产生抗体的部分细胞会被保存下来作为记忆细胞，对于今后入侵的同类抗原，其相应的记忆细胞会迅速激发，产生大量抗体。利用这种抗原记忆识别机制，可以加快搜索速度，提高算法的总体搜索能力[4]

。

受免疫系统的启发，提出一种自适应免疫遗传算法，在保

留原有选择、交叉、变异等遗传算子的前提下，通过自适应交叉、变异操作，在遗传进化的不同阶段改变交叉点，保留遗传编码的优秀个体，促进最优解的产生[5]。算法流程如图1所示。

图1 自适应免疫遗传算法流程

2.2 作业车间调度的算法流程

2.2.1抗原识别

抗原识别是将优化设计的目标函数作为免疫遗传计算的一个抗原输入，对于柔性作业车间调度问题，优化设计的指标可以是基于加工完成时间的性能指标：如最大完成时间；基于交货期的性能指标：最大推迟完成时间；基于库存的性能指标：平均待加工工件数[6]。本文采用最大完成时间作为柔性作业车间调度的优化指标。 2.2.2 种群初始化

根据待求解问题的特征，产生初初始抗体群。合理的设计初始抗体群编码机制，对免疫遗传算法的质量和效益有很大的影响，在进行遗传编码时，必须考虑染色体的合法性、可行性、有效性以及对问题解空间表征的完整性。本文采用基于工序的表达法，即给所有同一零件的工序指定相同的符号，然后根据他们在给定染色体中出现的顺序加以解释。如3个工件，每个工件有三道工序，则染色体“122313132”中，第一个“1”表示第一个工件的第一道工序，第二个“1”表示第一个工件的第二道工序，依此类推[7]。 2.2.3 免疫选择

(1) 亲和度评价算子

亲和度表征免疫细胞与抗原的结合强度，与遗传算法中的适应度类似。亲和度评价算子通常是一个函数 aff (x )。函数的输入为一个抗体个体(可行解)，输出即为亲和度评价结果。亲和度的评价与具体问题相关，针对不同的优化问题，应该在理解问题实质的前提下，根据问题的特点定义亲和度评价函数[8]。本文的亲合度定义为最大完成时间。

2009年6月 马佳，

等：求解柔性作业车间调度问题的自适应免疫遗传算法 Jun., 2009 (2) 抗体浓度评价算子

抗体浓度den (x )表征抗体种群的多样性好坏，抗体浓度过高意味着种群中非常类似的个体大量存在，则寻优搜索会集中于可行解区间的一个区域，不利于全局优化。因此优化算法中应对浓度过高的个体进行抑制，保证个体的多样性。

抗体浓度通常定义为： 101()(,)N i i j j den ab aff ab ab N −==∑ (1) 其中N 为种群规模；ab i 为种群中的第 i 个抗体；

aff (ab i ,ab j )为抗体i 与抗体j 的亲和度。

,1(,)1(2)i j i j aff ab ab H =+ (2)

其中，H i,j (2)为抗体ab i 和ab j 组成的抗体群的平均信息熵，

定义为：

1,,,0

1(2)(2)L i j i j k k H H L −==

∑ (3) 其中L 为抗体编码长度，H i,j,k (N )为抗体ab i 和ab j 组成的抗体群第k 个基因座上信息熵，计算方法为：

1,,,,0

(2)log S i j k n k n k n H p p −==−∑ (4) 式中S 为离散编码中每一维可能取值的等位基因数目，如二进制编码算法中S ＝2；p n,k 为抗体ab i 和 ab j 组成的抗体群中第k 维为第n 个等位基因的概率[9]。

(3) 激励度计算算子

抗体激励度sim (x )是对抗体质量的最终评价结果，需要综合考虑抗体亲和度和抗体浓度，通常亲和度大、浓度低的抗体会得到较大的激励度[4]。抗体激励度的计算通常可以利用抗体亲和度和抗体浓度评价结果进行简单的数算得到，如：

()()()i a den ab i i sim ab aff ab e −=i i (5)

其中，sim (ab i )为抗体ab i 的激励度；a 、b 为计算参数。

(4) 免疫选择算子

免疫选择算子Ts 根据抗体的激励度确定选择哪些抗体

进入克隆选择操作。在抗体群中激励度高的抗体个体具有更

好的质量，更有可能被选中进行克隆选择操作，以在搜索空

间中更有价值的搜索区域展开局部搜索。免疫选择算子可以

描述为：

1, ()()0, ()i s i i sim ab T

T ab sim ab T ≥⎧=⎨<⎩

(6) 其中T 为激励度阈值。

2.2.4 克隆操作 克隆算子T c 将免疫选择算子选中的抗体个体进行复制。

克隆算子可以描述为：

()()c i i T ab clone ab = (7)

式中 clone (ab i

)为m i

个与ab i

相同的克隆构成的集合；m i

为抗体克隆数目。 2.2.5 自适应交叉和变异

(1) 种群平均信息熵

1

1()()L j k H N H N L −==∑ (8)

其中()j H N 为第j 个基因的信息熵：

,1,20()log i j

S p j i j n H N p −==−∑ (9)

其中,i j p 为第i 个符号出现在基因座上的概率，即：

,i j p =(在基因座j 上出现第i 个符号的总个数)/N 。 (2) 种群相似度

1

()1()A N H N =

＋ (10) ()A N 表征了整个种群总的相似程度，()(0,1)A N ∈。()

A N 越大，种群相似度越高，反之亦然。当()1A N =时，表示群

体中各个抗体是完全相同的。

(3) 自适应策略

交叉概率p c 和变异概率p m 是免疫遗传算法的两个重要的参数，无论过大还是过小，都会直接影响算法的收敛速度，对于不同的优化问题很难找到一个适应每个问题的最佳值。自适应策略能够使p c 、p m 随种群多样性自动改变[5]。当种群中个体适应度趋于一致或趋于局部最优时，使p c 、p m 增加，而当适应度比较分散时令p c 、p m 减少。p c 、p m 按下式进行自适应调整。

2(()1)A N c p e −= (11)

2(()1)0.1A N m p e −= (12)

2.2.6 疫苗抽取

免疫疫苗的抽取通常有两种：(1)视具体分析待求问题，

搜集特征信息，进而制作免疫疫苗；(2)自适应方法，即在群体进化过程中从其每代最佳的基因中抽取有效信息，从而制

作疫苗[8]。前者由于以下两个原因而受到：(1)对待问题

有时难以形成较为成熟的先验知识，无法从分析问题的过程

中抽取出合适的特征信息，因此得不到有效的免疫疫苗；(2)

提取疫苗的工作代价太大，超出了其在寻找全局最优解过程

中的比例，所以本文算法中采用自适应抽取疫苗方法。其过

程是：通过对最近K-1代保留下来的最优个体群和当前代的

最优个体群进行分析，抽取基因位的共同特点和有效信息作

为疫苗[9]。疫苗抽取的具体方法如下：

设每代保存种群中适应度最优的K b 个抗体，则最近

K (包含当前代)代共保留b K K ∗个抗体组成最优抗体群，每

个抗体的每个基因位有1

2

,,,s

k k k 共s 个符号可供选择，第

等位基因为i k 的概率为,1

1b

K K i j j j b p a K K ∗==

∗∑，其中，当 ()j g i k =时，1j a =，否则0j a =。()g i 为种群中第i 等位基因上的符号。将该等位基因上最大概率(记为,i p i =1,2,

2009年6月 系 统 仿 真 学 报 Jun., 2009

,L )的j k 作为该等位基因上的疫苗片断，从而最终提取出

疫苗12(,,,)L H h h h = 。 2.2.7 疫苗接种

从父代群体中选择要进行接种的抗体，根据轮盘赌方式选择出一个或多个基因片断通过置换基因码值产生新的免疫个体，形成更优种群[3]

。基因片段选择方式如下：由2.2.6

节可知，疫苗为12(,,,)L H h h h = ，令1

(1,2,,)i i L j

j p

q i L p ===∑

与i h 相对应，i p 含义同2.2.6节。根据轮判赌原理i q 值瓜分了整个论盘的盘面，他们决定了各个疫苗片段被选择的概率。

2.2.8克隆抑制算子

克隆抑制算子T r 对经过上述操作后的个体进行再选择，抑制亲和度低的抗体，保留亲和度高的抗体进入新的抗体种群。在克隆抑制的过程中，克隆算子操作的源抗体与克隆体经交叉、变异、接种疫苗作用后得到的临时抗体群共同形成一个集合X ti ，克隆抑制操作将保留此集合中亲和度最高的抗体，抑制其它抗体[10]。克隆抑制算子可以描述为：

()r ti i

T X ab ∗

= (13) 其中ab i 为集合X ti 中亲和度最高的抗体，aff (ab i )=max {aff

(ab k , ab k ∈X ti }。由于克隆、变异算子操作的源抗体是种群中的优质抗体，而克隆抑制算子操作的临时抗体集合中又包含了父代的源抗体，因此在人工免疫算法的算子操作中隐含了最优个体保留机制。 2.2.9种群刷新算子

种群刷新算子T d 对种群中激励度较低的抗体进行刷新，从抗体种群中删除这些抗体并以随机生成的新抗体替代，有利于保持抗体的多样性，探索新的可行解空间区域。种群刷

新算子可以描述为：

()d n n T X X ∗

= (14)

其中X n 为抗体种群中激励度较低的抗体组成的集合；X n *为随机生成的新抗体组成的集合，且集合X n *与

X n 具有相同的

规模。

3 仿真实例

由于实际生产过程要考虑的因素很多，调度问题也很复杂，所以在不同的生产系统中，Job-shop 问题也存在一定的差异。本文以某制造业加工车间为例，将生产数据做了简化处理，设计了一个由7类工件，6道工序，一共有11台机器完成加工任务的仿真实例。具体的工件、工序、机器以及加工工艺信息如下表2，表3，表4所示。在表2中，1表示机器可以完成的工序，0表示机器不能完成的工序。

本文采用遗传算法，免疫遗传算法和自适应免疫遗传算

法分别对该实例进行了仿真，各算法的参数如表5所示。

表2 工序－机器关系

工序车床M1车床M2镗床M3铣床M4铣床M5加工 中心 M6

加工 中心 M7 加工 中心 M8

磨床M9磨床M10刨床

M11

车11000 1 1 1 000铣00011 1 1 1 000刨000000 0 0 001磨000000 0 0 110钻00000 1 1 1 110镗

1

0 0 0 0

表3 工件工序信息

工序

工件 1 2 3 4 5 6

J1 车 铣 刨 镗 钻 磨 J2 铣 磨 镗 钻 车 刨 J3 镗 钻 车 刨 磨 铣 J4 磨 刨 钻 车 铣 镗 J5 刨 车 磨 铣 镗 钻 J6 车 镗 铣 磨 钻 刨 J7

钻

镗

磨

铣

刨

车

表4 工序加工时间

J1 J2 J3 J4 J5 J6 J7 M1 4 6 4 7 9 3 3 M2 3 5 3 8 8 5 2 M6 4 7 7 5 6 7 4 M7 5 8 6 6 7 8 5 车

M8 5 7 5 4 5 8 4

M4 3 5 8 4 3 9 4 M5 2 6 7 3 5 10

6

M6 5 9 4 5 7 8 7 M7 4 8 6 6 5 8 6 铣

M8 6 7 5 5 5 6 8

刨 M11 4 5 3 7 3 4 5 M9 7 3 6 8 4 8 6

磨

M10

6 5 4

7 4 6 4

M6 4 6 5 4 9 3 5 M7 6 4 4 6 7 4 6 钻 M8 5 7 6 5 8 3 5

镗 M3 5 3 3 6 4 6 7

表5 三种算法仿真参数

算法

种群数

交叉率变异率 疫苗接种率 克隆尺寸

进化代数

GA 200 0.750.1 无 无 200 IGA 200 0.750.1 0.2 无 200 AIGA

200 0.75

0.1 0.2

30

200

经过200代进化后，遗传算法求出的平均最优解为59.4，均方差为3.2312，计算时间是125s,平均收敛代数为140代左右；免疫遗传算法求出的平均最优解是55.8，均方差为

1.990，计算时间是137s,平均收敛代数为120代左右；自适应免疫遗传算法求出的平均最优解是53.3，

均方差为1.005，计算时间是140s,平均收敛代数为110代左右。三种算法进

2009年6月 马佳，

等：求解柔性作业车间调度问题的自适应免疫遗传算法 Jun., 2009 行十次仿真的结果如表6及图2所示。

表6 三种算法的多次仿真结果

1 2 3 4 5 10次解平均值61 55 61 58 59.4 6 7 8 9 10 均方差

GA

58 61 54 58

3.2311 1 2 3 4 5 10次解平均值57 55 57 53 56 55.8 6 7 8 9 10 均方差

IGA

60 55 55 57 53

1.990 1 2 3 4 5 10次解平均值55 54 52 52 54 53.3 6 7 8 9 10 均方差

AIGA

53 54 52 54 53 1.005

图2 三种算法的多次仿真结果稳定性分析

由表6及图2可见，通过多次仿真，AIGA 得到的目标适值普遍优于IGA 、SGA ；AIGA 得到解群的均方差低于

IGA 、SGA 。说明改进算法的有效性和稳定性相较前两种算法均有提高。在收敛性方面，由于AIGA 选取优良疫苗进行接种，并自适应地选择交叉和变异的概率，因此在收敛速度方面有所提高。另外，由于采用克隆选择思想，加大了局部搜索力度，执行了保优策略，有效降低了AIGA 在收敛过程中的振荡幅度，提高了其收敛质量，得到了更优解。本文仅就三种算法分别在10次仿真中获得最优解时的收敛曲线加以比较，如图3所示：

图3 三种算法的收敛过程比较

从上述的仿真结果可以看出,本文提出的自适应免疫遗传算法的性能的确优于遗传算法和一般免疫遗传算法。虽然自适应免疫遗传算法花费的时间稍多于前两者，这主要是由于这种混合算法比单一算法复杂，算子更多导致。但自适应免疫遗传算法不但保持了种群的多样性，加快了进化速度，而且在一定程度上避免了进化过程中出现过早收敛的现象，相对可以获得更优的解。

4 结论

本文在分析了遗传算法的原理和收敛性的基础上，提出了遗传算法的改进策略，引入免疫算子和自适应策略，构成自适应免疫遗传算法，并将其应用到了柔性作业车间调度问题上。其中免疫算子可以防止种群中个体再交叉、变异中出现的退化现象，自适应策略则保持种群的多样性和算法的收敛性。实验结果表明，自适应免疫遗传算法能快速、有效地解决柔性作业车间调度问题。

参考文献：

[1]

Holsapple W, Jacob V S, Pakath R, et al. A genetics -based hybrid scheduler for generating static schedules in flexible manufacturing contexts [J]. IEEE Transaction on Systems. Man and Cybernetics

(S0018-9472), 1993, 23(4): 953-972.

[2] Huang S. Enhancement of thermal unit commitment using

immune algorithms based optimization approaches [J]. Electrical Power and Energy System (S0142-0615), 1999, (21): 245-252. [3] Jiao Licheng, Wang Lei. A novel genetic algorithm based on

immunity [J]. IEEE Transactions on Systems, Man, and Cybernetics (S0018-9472), 2000, 30(5): 552-561.

[4] 肖人彬, 王磊. 人工免疫系统: 原理, 模型, 分析及展望[J]. 计算

机学报, 2002, 25(12): 1281-1293. [5]

M Srinivas, L M Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithms [J]. IEEE Transactions on Systems, Man and Cybernetics (S0018-9472), 1994, 24(4): 656-665. [6]

Kacem I, Hammadi S, Borne P. Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic [J]. Mathematics and Computers in Simulation (S0378-4754), 2002, 60(35): 245-276.

[7]

Najid N M, Stephane D P, Zaidat A. Modified simulated annealing method for flexible job shop scheduling problem [C]// Proceedin gs of the IEEE International Conference on Systems Man and Cybernetics, NJ, USA. USA: IEEE, 2002: -94.

[8] Dasgupta D. Artificial Immune Systems and Their Applications [M]. Berlin Heidelberg, Germany: Springer-Verlang, 1999.

[9]

Ho Nhu Binh, Tay Joc Cing. GENACE: An efficient cultural algorithm for solving the flexible job-shop problem [C]// Proceedings of the IEEE Congress on Evolutionary Computation, 2004. USA: IEEE, 2004: 1759-1766.

[10] Hunt J E. Cooke D E. Learning using an artificial immune system [J].

Journal of Network and Computer Application (S1084-8045), 1996, 19(4): 1-212.

BEST:

1-GA:55 2-IGA:533-AIGA:52

1:GA 2:lGA data3

1:GA 2:lGA 3:AlGA