混合免疫范文

混合免疫范文（精选4篇）

混合免疫 第1篇

城市发展引发了交通量的日益增大, 为此需要对城市交通网络进行改善以适应变化。交通网络设计问题 (network transportation design problem, NTDP) 是1个最优投资决策问题:在一定的投资约束条件下, 考虑交通出行者行为选择情况的同时, 改善某些路段或在交通网络中添加新的路段等, 以使整个交通网络达到某种系统最优的策略[1]。

交通网络设计分为离散交通网络设计 (新建路段) 、连续交通网络设计 (扩建现有路段) 、混合交通网络设计 (既有新建路段又有扩建路段) 。国内外的学者对此进行了大量的研究, 对离散网络设计和连续交通网络设计研究较多[1,2,3,4,5], 而对混合交通网络设计研究较少。混合交通网络设计更符合实际, 但其求解困难, 一般较难用经典数值算法求解, 多采用启发式的智能算法求解, 如遗传算法 (genetic algorithm, GA) [6]等。

人工免疫算法受生物免疫系统启发, 通过抗体与抗原的结合, 采用选择、变异、克隆、免疫调节、免疫疫苗等操作, 逐渐实现抗体优化 [7,8,9,10,11,12], 广泛应用于各类工程问题的研究和解决。

笔者针对混合交通网络设计的求解问题, 结合免疫仿生机理, 在遗传算法中融入免疫策略, 利用遗传免疫算法对混合交通网络设计进行求解研究。

1 混合交通网络设计模型

城市混合交通网络设计问题可以用双层规划模型描述。

上层规划 (U1) 考虑网络系统总阻抗、路段新建费用、路段扩建费用, 以期最小化这3种费用之和:

$\begin{array}{l}\text{m}\text{i}\text{n}F{}_1(x)={\displaystyle \sum _{\alpha \in A{}_1}x}{}_{\alpha }t{}_{\alpha }(x{}_{\alpha })+{\displaystyle \sum _{\alpha \in A{}_2}(}x{}_{\alpha }t{}_{\alpha }(x{}_{\alpha }‚y{}_{\alpha })+\\ \delta g(y{}_{\alpha }))+{\displaystyle \sum _{\alpha \in A{}_3}(}x{}_{\alpha }t{}_{\alpha }(x{}_{\alpha }‚y^{\prime }{}_{\alpha })+\delta g^{\prime }(y^{\prime }{}_{\alpha }))(1)\\ \text{s}.\text{t}.0\le y{}_{\alpha }\le y{}_{\max }\forall \alpha \in A{}_2(2)\\ 0\le y^{\prime }{}_{\alpha }\le y^{\prime }{}_{\max }\forall \alpha \in A{}_3(3)\end{array}$

下层规划 (L1) 采用固定需求的用户平衡配流模型 (user equilibrium, UE) :

$\begin{array}{l}\text{m}\text{i}\text{n}F{}_2(x)={\displaystyle \sum _{\alpha \in A{}_1}{\displaystyle {\int }_0^{x{}_{\alpha }}t}}{}_{\alpha }(w)\text{d}w+\\ {\displaystyle \sum _{\alpha \in A{}_1}{\displaystyle {\int }_0^{x{}_{\alpha }}t}}{}_{\alpha }(w‚y{}_{\alpha })\text{d}w(4)\\ \text{s}.\text{t}.{\displaystyle \sum _{k\in {\rm K}}ƒ}{}_k^{rs}=q{}_{rs}\forall \alpha \in R‚s\in S(5)\\ x{}_{\alpha }={\displaystyle \sum _r{\displaystyle \sum _s{\displaystyle \sum _kƒ}}}{}_k^{rs}\mathit{\delta }{}_{\alpha ‚k}^{rs}\forall k\in A‚r\in R‚\\ s\in S‚k\in {\rm K}{}_{rs}(6)\\ ƒ{}_k^{rs}\ge 0\forall k\in {\rm K},r\in R,s\in S(7)\end{array}$

式中:A为网络中路段的集合;A1为不扩建的路段;A2为待扩建的路段;A3为计划新建的备选路段;R为起点的集合;S为终点的集合;r为起始节点;s为终到节点; ƒ${}_k^{rs}$为起点r与终点s在路径k上的流量; δ${}_{\alpha ‚k}^{rs}$为路径/路段关联矩阵;yα为扩建路段 α增加的实际通行能力; y′α为新建路段 α的实际通行能力;ymax、y′max分别表示yα、y′α的上限;g (yα) 为路段α 扩建的费用;g′ (y′α) 为新建路段 的费用;xα 为路段α 上的流量;tα (xα) 为现有不扩建路段α 的阻抗函数;tα (xα, yα) 为扩建路段 α的阻抗函数;tα (xα, y′α) 为新建路段的阻抗函数;δ 为时间费用转换系数。

式 (1) 为总费用最小化;约束式 (2) 、 (3) 分别为扩建路段能力和新建路段能力在可行范围之内;式 (4) 、约束式 (5) ～ (7) 为UE平衡配流模型。

2 遗传免疫算法

2.1传统遗传算法的局限性

1) 存在早熟现象。GA可能会出现过早收敛于某一局部最优解的情况。

2) 局部搜索能力较差, 往往与最优解失之交臂[9]。

3) 并没有很好的保留上代隐含的信息, 可能出现退化现象。

2.2免疫仿生机理

人工免疫算法基于生物系统中的免疫系统, 借鉴了免疫系统的功能、原理, 对抗体与抗原的亲合度进行计算, 实现对问题的优化求解。针对传统遗传算法存在的3点局限性, 引入免疫算法的免疫调节[9]、克隆选择[10,11]、免疫记忆[11,12]3种特性对遗传算法进行改进:

1) 免疫调节。利用抗体浓度对抗体与抗原的亲合度进行调节, 使亲合度较高且浓度较低的抗体得到促进并且以较大概率被选择进入下一代, 同时抑制亲合度较低且浓度较高的抗体, 从而在保留高亲合度个体的同时维持群体的多样性, 有利于防止算法过早收敛, 避免出现传统遗传算法中的早熟现象。

2) 免疫抗体的克隆选择。通过空间的扩张与压缩, 将局部搜索和全局搜索结合起来实现问题的求解。

3) 免疫记忆。引进免疫记忆单元, 保存上代的优化信息和全局的优化信息, 加速优化搜索过程, 避免出现传统遗传算法中的退化现象。

2.3遗传免疫算法设计

1) 抗体设计由于涉及到扩建路段的决策变量和新建路段的决策变量, 所以采用群体编码形式。

网络设计决策抗体β={b, d}。b={b1, b2, …bn…}为扩建路段决策抗体, 式中bn为扩建路段的决策变量; d={d1, d2, …dn, …}为新建路段决策抗体, 其中dn为新建路段的决策变量。在给定路网结构后, 抗体b和抗体d均为固定长度的编码。

抗体示意如图1所示, 将扩建决策分为7个等级, 分别用0～6的整数表示。0为不扩建路段, 1～6为扩建路段通行能力相应的增加等级;新建决策用0、1表示, 0为不新建相应路段;1为新建相应路段。种群规模为M的抗体种群空间表示为β (m) ={ β1, β2, …βm|m (s) }。式中m (s) ={m1, m2… ms}为记忆单元抗体空间。

2) 抗体浓度抑制设计。常用的抗体之间的亲合度计算方法有:R连续位方法、海明距离法、欧式距离法、信息熵度量法[9]。由于要利用抗体浓度计算抗体与抗原的亲合度, 所以运用信息熵度量法计算抗体与抗体的亲合度、抗体的浓度, 并根据这2个计算值重新计算抗体与抗原的亲合度。

3) 交叉设计。采用遗传算法中的2点交叉方式, 以扩建路段决策抗体交叉为例, 如图2所示。

4) 变异设计。为了增强局部搜索能力和全局搜索能力, 设计了2种变异算子:遗传变异算子和随机变异算子。遗传变异算子采取和遗传算法一样的操作, 增强了对算法空间的局部搜索能力;随机变异算子采用蒙特卡罗思想, 根据概率对每个路段决策进行随机变异, 增大算法对全局解空间的搜索能力。以扩建路段决策抗体为例, 如图3、4所示, 新建路段决策抗体的变异方式同扩建抗体。

5) 抗体克隆选择设计。对抗体进行克隆后, 进行变异操作。变异算子采取上面提到的遗传变异算子和随机变异算子, 以大概率进行遗传变异算子操作, 以小概率进行随机变异算子操作。然后进行选择操作。

6) 记忆单元设计。设置2种记忆抗体, 局部记忆抗体和全局记忆抗体。为了保存上代的最优信息, 局部记忆抗体记录上代抗体中的最优抗体;为了保存全局的最优信息, 全局记忆抗体保存进化中出现过的最优抗体。每次迭代计算中保存这2种记忆抗体, 并在下次迭代中将记忆抗体以一定比例加入到抗体种群中。

2.4计算步骤

本节给出求解混合交通网络设计的遗传免疫算法的具体计算步骤:

步骤1 初始化抗体种群。

步骤2 计算抗原与抗体的亲合度、记忆抗体。

步骤3 根据抗体与抗体的亲合度、抗体的浓度调整抗体与抗原的亲合度。

步骤4 根据轮盘赌的方式进行选择, 并进行交叉算子、变异算子操作。

步骤5 对抗体进行克隆选择操作。

步骤6 复制保存相应抗体到记忆单元。

步骤7 判断是否达到停止准则, 如果没有达到, 将记忆抗体复制到下一代抗体种群中, 返回步骤2;否则停止计算, 输出最优结果。

3 算例

3.1算例设计

图5为交通网络图, 其中路段1～12为现存路段, 路段13～20为备选新建路段。表1给出了相应的OD矩阵。表2、3分别给出了扩建路段和新建路段的信息。表1给出的OD矩阵以机动车为单位, 假设平均机动车载客为3人, 将表1中OD矩阵中的出行量乘以3便可得到以 (人·次) 为单位的OD矩阵。扩建路段费用g (ya) =da (y${}_a^2$) , da为费用系数 (如表2所列) 。时间费用转换系数 δ取0.1 min/元。

3.2计算结果

利用VC++进行程序开发, 编写了遗传免疫算法和标准遗传算法。遗传免疫算法设定:抗体种群大小30, 交叉概率0.6, 变异概率0.1, 克隆规模为4, 最大迭代次数200次;标准遗传算法设定:染色体种群大小30, 交叉概率0.6, 变异概率0.1, 最大迭代次数200次。同时给定这2种算法相同的初始解并进行求解, 图6表示2种算法每次迭代进行选择、变异等操作后的最优适应度和亲合度, 图7表示种群的平均亲合度和平均适应度, 表4表示两种算法的最优解。标准遗传算法求解中最优适应度为58 760 min, 小于收敛

时染色体平均适应度58 781 min, 出现退化现象。

3.3结果分析

从图6、图7可以看出:

1) 遗传免疫算法比标准遗传算法搜索到更优的解, 并且遗传免疫算法抗体的平均亲合度也收敛到最优抗体亲合度, 证明了算法的有效性。

2) 在标准遗传算法中, 最后种群收敛的平均适应度低于历史中出现的最优染色体适应度, 而在遗传免疫算法中, 抗体种群平均适应度与历史最优抗体适应度一致, 表明遗传免疫算法克服了标准遗传算法中的退化现象。

3) 虽然遗传免疫算法比标准遗传算法搜索更优, 并克服了早熟、退化等现象, 但进行克隆选择操作、记忆抗体操作需要更多的保存空间和更长的搜索时间, 降低了收敛速度, 增加了收敛所需时间。

3.4对离散网络设计和连续网络设计求解与比较

运用遗传免疫算法对离散网络设计和连续网络设计进行求解。对于离散网络设计求解, 将混合网络设计算法中扩建路段决策抗体d={d1, …dn, …} 全部设为0;对于连续网络设计求解, 将混合网络设计算法中新建路段决策抗体b={b1, b2, …bn, …} 全部设为0。计算结果:离散网络设计目标为63 324/min, 连续网络设计目标为56 713/min, 均大于混合网络设计的目标56 580/min。混合网络设计比离散网络设计和连续网络设计达到更优的目标值, 说明混合网络设计更符合实际, 更能达到优化整个交通网络的目的。

4 结论与展望

针对城市混合交通网络设计中的求解问题, 将免疫调节、克隆选择、免疫记忆3种仿生机理与标准遗传算法结合, 设计了遗传免疫算法。为了加大对解空间的搜索, 在变异操作中设计了遗传变异算子和随机变异算子, 通过算例验证了算法的有效性, 和标准遗传算法相比具有较好的求解效果。利用设计的遗传变异算法对离散网络设计与连续网络设计进行了求解分析比较, 表明混合网络设计能到达更优的解, 表明混合网络设计在优化交通网络方面具有优越性。

下一步的研究方向为:

1) 考虑与其他元启发式算法的结合, 引入更合理的策略, 以提高算法的收敛速度和解的质量。

2) 研究多种交通发式下的交通网络混合设计问题。

参考文献

[1]高自友, 张好智, 孙会君.城市交通网络设计问题中双层规划模型、方法及应用[J].交通运输系统工程与信息, 2004, 4 (1) :35-44

[2]LeBlanc L J.An algorithmfor discrete network de-sign problem[J].Transportation Science, 1975, 9:183-199

[3]Friesz T L, Shah S.An overview of nontraditionalformulations of static and dynamic equilibrium net-work design[J].Transportation Research Part B, 2001, 35 (1) :5-21

[4]蔡金, 高自友.求解城市交通连续平衡网络设计问题的混合算法[J].北方交通大学学报, 2002, 26 (2) :71-76

[5]赵彤, 高自友.城市交通网络设计问题中的双层规划模型[J].土木工程学报, 2003, 36 (1) :6-10

[6]聂伟, 邵春福, 杨励雅, 等.混合交通网络设计的双层模型及遗传算法求解[J].土木工程学报, 2007, 40 (8) :90-93

[7]Dai Y S, Li Y Y, Wei L, et al.Adaptive i mmune-ge-netic algorithmfor global opti mization to multivari-able function[J].Journal of Systems Engineeringand Electronics, 2007, 18 (3) :655-660

[8]Zhang Z H.Constrained multiobjective opti mizationi mmune algorithm:convergence and application[J].Computers&Mathematics with Applications, 2006, 52 (5) :791-808

[9]肖人彬, 曹鹏彬, 刘勇.工程免疫计算[M].北京:科学出版社, 2007

[10]刘若辰, 杜海峰, 焦李成.一种免疫单克隆策略算法[J].电子学报, 2004, 32 (10) :1 880-1 884

[11]肖人彬, 王磊.人工免疫系统:原理、模型、分析与展望[J].计算机学报, 2002, 25 (12) :1 281-1 293

混合免疫 第2篇

关键词：混合流水车间,调度,克隆选择,人工免疫系统

0 引 言

混合流水车间调度问题HFSP(Hybrid Flow-shop Scheduling Problem)是制造型企业生产车间中常见的调度模型,相当普遍地存在于化工、钢铁、制药等流程工业中。由于HFSP属于NP-hard问题,目前针对此问题的求解主要有数学规划法、启发式算法、遗传算法等,然而,当问题规模比较大时,这些方法都存在着一些不足[1]。

人工免疫系统AIS(Artificial immune system)是模仿免疫系统功能的一种智能计算方法,它具有噪声忍耐、无教师学习、自组织、记忆等进化学习机理,目前已被广泛应用于解决各种工程和科学问题中[2]。然而,与其它进化算法一样,一般免疫算法也存在容易陷入局部最优的平衡态以及进化后期停滞不前的缺陷。于是,受到生物免疫抗体克隆选择理论的启发,De Castro于2000年提出了免疫克隆选择算法ICSA(Immune clonal selection algorithm)。该算法的基本思想[3]是:通过对候选解进行克隆变异操作,产生一个候选解的领域解,通过扩大搜索范围加强局部搜索,并通过领域解和候选解的竞争(选择),促进算法的快速收敛全局搜索能力。另一方面,与其它算法(如遗传算法)不同,免疫算法不单纯以适应度作为个体的评价标准,而是用亲合度、相似度、浓度的概念衡量个体的特性,并基于此,动态调整变异概率,保持种群在进化过程中的多样性变化。鉴于CSA算法的这些特性,该算法在解决较复杂的模式识别、组合优化问题,表现出显著的能力[4,5,6,7,8]。

基于以上分析,针对HFSP问题的特点,本文首先给出了HFSP调度问题的数学模型;在此基础上,将免疫克隆选择算法应用于HFSP问题的求解;为提高算法的有效性,引入种群分组策略,根据种群优劣实施变异、交叉、死亡操作;最后通过仿真实例,验证了算法求解HFSP问题的可行性和有效性。

1 数学规划模型

如图1所示,HFSP调度问题[1]可描述为:需要加工n个同质工件,所有工件的加工路线都相同,都需要依次通过m道工序(车间),在工序j(j=1,2,…,m),有Mj台并行同质机器。需要解决的问题是确定并行机器的分配情况以及同一台机器上工件的加工顺序,使得调度指标最小。

1.1 基本假设及符号说明

为了保证HFSP调度问题数学规划模型的正确、有效,需要做一些必要的简化假设:

(1) 工件之间相互独立;

(2) 各阶段所有工件加工优先顺序相同;

(3) 工件在工序之间可以等待,并且暂时存储容量不受限制;

(4) 工件在每道工序的每台机器上的加工时间为固定值;

(5) 不考虑机器故障的情况。

相关参数说明:

n:待加工工件数;

m:加工工件需经历的工序数;

Mj:第j道工序的机器数量,j∈{1,2,…,m};

Njk:第j道工序的机器k上加工工件的数量,k∈{1,2,…,Mj};

Pijk:工件i在第j道工序的机器k上加工所用的时间, i∈{1,2,…,Njk};

Sijk:工件i在第j道工序的机器k上加工的开始时刻;

Cijk:工件i在第j道工序的机器k上加工的结束时刻;

hjk:第j道工序的机器k上加工的第h个工件,h∈{1,2,…,Njk};

Yijk:0-1变量,当工件i安排在第j道工序的机器k上加工时Yijk=1,否则Yijk=0。

1.2 约束条件

HFSP问题的相关约束主要有:

(1) 机器约束

${\displaystyle \sum _{k=1}^{{\rm M}{}_j}Y}{}_{ijk}=1$ (1)

∀i∈{1,2,…,Njk} ∀j∈{1,2,…,m}

${\displaystyle \sum _{k=1}^{{\rm M}{}_j}{\rm N}}{}_{jk}=n\forall j\in \{1,2,\cdots ,m\}$ (2)

式(1)表示每个工件的每道工序必须且只能选择该工序的一台机器来进行加工一次。式(2)表示分配到每道工序机器上的工件数之和为工件总数n。

(2) 时间约束

Cijk≤Si(j+1)r

∀i∈{1,2,…,n} ∀j∈{1,2,…,m-1} (3)

∀k∈{1,2,…,Mj} ∀r∈{1,2,…,Mj+1}

Cijk=Sijk+Pijk

∀i∈{1,2,…,Njk} ∀j∈{1,2,…,m} (4)

∀k∈{1,2,…,Mj}

Chjkjk≤S(h+1)jkjk

∀i∈{1,2,…,Njk} ∀j∈{1,2,…,m} (5)

∀k∈{1,2,…,Mj} ∀h∈{1,2,…,Njk}

式(3)表示对任意一个工件而言,只有它的前一道工序加工完成后才能开始下一个工序;式(4)表示一个工件的加工结束时刻为其加工开始时刻和加工用时之和;式(5)表示对于某台机器而言,下一个工件加工开始时刻必须大于或等于当前工件加工结束时刻。

1.3 目标函数

以最小化最大流程时间为调度指标,则目标函数为:

2 免疫克隆选择算法在HFSP调度问题中的实现

2.1 抗原识别、抗体编码与解码

在免疫算法中,抗原对应着待求解的问题,通常为目标函数f。

和其它智能算法一样,免疫算法也需对特定问题进行编码,HFSP中抗体的编码对应了最终的调度方案。本文采用文献[4]中的编码,详细的编码与解码方法参考文献[4],则抗体共有m个基因片段,每个基因片段长度为n,抗体编码长度L=n×m。

2.2 亲合度函数的构造

(1) 抗体与抗原的亲合度F:

用于表明抗体对抗原的识别程度。抗体v与抗原的亲合度定义为最大流程时间的倒数。即:

(2) 抗体间的亲和度(也称相似度)

S(0≤S≤1):用于表明两个抗体之间的相似程度。通常免疫算法采用信息熵或海明距离概念作为抗体间相似度的计算方法[4]。这种方法并不适用于本文所采用的编码机制,例如对于只有1道工序,n=3,m=2的情况:有如下抗体:v=[2.1,1.2,2.4],w=[2.1,1.4,2.5],按照海明距离的计算方法,这两个抗体是不相同的,然而实际调度中这两个抗体对应着相同的调度方案,即相似度为1。为了解决这一问题,本文采用分组匹配的计算方法,设抗体i,j基因座为l的编码为ail,ajl,则i,j的相似度Sij按下式定义:

$S{}_{ij}={\displaystyle \sum _{l=1}^{L}c}ount(fix(a{}_{il})\ne fix(a{}_{jl}))/L$ (8)

count(·)为统计个数函数,fix(·)为向下取整。

(3) 抗体的浓度D:反映了抗体群体的多样性,定义下式为抗体i的浓度:

$D{}_i=\exp (-{\displaystyle \sum _{j=1}^{L}S}{}_{ij}/L)$ (9)

显然,抗体间相似度越小,Di越小,抗体的浓度主要用来动态调整克隆的规模,防止近亲繁殖,保持抗体群的多样性。

2.3 初始种群的产生

Step1 设当前代数k=0,随机产生规模为N的抗体群B(0)={b1,b2,…,bN},设记忆库Mem大小为Nmem。

Step2 计算每个抗体和抗原的亲合度F(b1),F(b2),…,F(bN)},将抗体群B(k)按亲合度降序排列,前Nmem个抗体存入记忆库Mem中,为提高算法全局化能力,我们采用分组策略,按比例2:5:3划分抗体群B(k)为好、中、差三种群体。即:B(k)={Br(k),Bs(k),Bt(k)},其中r、s、t分别为三种群体中个体的数目。

2.4 更新抗体群

Step1 克隆操作

对Br(k)中的抗体bi(i=1,2,…,r),按规模qi进行复制,设:

$q{}_i=ceil\left({\rm N}{}_c\times \frac{\beta {}_i}{{\displaystyle \sum _{i=1}^r\beta }{}_i}\right)i=1,2,\cdots ,r$ (10)

$\beta {}_i=D{}_i\times \frac{F(b{}_j(k))}{{\displaystyle \sum _{j=1}^{r}F}(b{}_j(k))}i=1,2,\cdots ,r$ (11)

其中Nc为克隆规模,Nc>r,ceil(·)为向上取整,从上面两式可以看出,抗体bi的克隆规模依赖亲合度F(bi)和浓度Di是可以动态调整的。克隆后抗体群为B${}_r^c$(k)={Iq1b1,Iq2b2,…,Iqrbr} (Iqi为qi维单位矩阵)。

Step2 变异操作

对Br(k)中的抗体bi(i=1,2,…,r),按下式分配bi的变异概率[9,10,11]:

$p{}_i=[1+\exp (L\times F(b{}_i)/{\displaystyle \sum _{j=1}^{r}F}(b{}_i))]{}^{-1}$ (12)

可见,抗体的亲合度越大,变异概率越小,较好的抗体得以生存。对B${}_r^c$(k)中的每个子种群{Iqibi}以pi的概率实施变异,变异后,由B${}_r^c$(k)产生种群$\overline{B{}_r^c(k)}$。

Step3 交叉操作

对于Bs(k)中个体,以交叉概率Pc与记忆库Mem中的个体实施交叉,这里采取分段交叉的方式,对抗体的m个基因片段进行两点交叉,每个基因片段的交叉点随机生成,目的是通过中等个体与优良个体的杂来提高中等种群的整体亲合度,交叉后生成种群B${}_s^c$(k)。

Step4 选择

合并群体$\overline{B{}_r^c(k)}$和B${}_s^c$(k)组成群体Be(k),取Be(k)中的r+s个亲合度最高的个体组成群体Bu(k)。

随机生成规模为N群体,取其中亲合度最高的t个个体代替原来差的群体Bt(k),得到群体B′t(k)。最后合并Bu(k),B′t(k),新一代抗体群产生,即B(k+1)={Bu(k),B′t(k)}。

Step5 算法结束条件

算法采用最大迭代次数作为算法的结束条作件,当算法运行到指定代数时,取出记忆库Mem中亲合度最高个体即为问题的求解。否则,算法按Step2继续执行。

3 实例分析

假设加工工件数n=12个,每个工件加工工序m=3道,机器环境为3-2-4,工件在每个机器上的加工时间如表1所示。

对本文所述ICSA算法编制Matlab仿真程序。ICSA算法的相关参数:种群规模N=40,记忆库大小Nmem=15,克隆规模Nc=60;交叉概率Pc=0.8,进化代数为100。得到算法运行曲线如图2所示。

用本文ICSA优化实例得到最小makespan值为27s,收敛代数为32代,较优于文献[6]遗传算法求解的结果。从仿真结果不难得出:

(1) 由于ICSA算法的克隆变异算子,在局部最优解的周围产生邻域候选解,并通过局部最优解与邻域解的竞争,使抗体群得以朝着全局最优的方向进化。

(2) ICSA算法的记忆功能,保存了进化过程中的优良个体,并不断更新记忆库,最终将记忆库作为解的集合,更符合智能算法的生物特性。

(3) ICSA算法以亲合度、相似度和浓度作为抗体的评估方式,并自适应调整变异概率,删除较差个体,因此在种群保持抗体多样性的同时,也使种群进化趋于合理。

在本文的ICSA算法设计中,通过种群分组、精英变异策略,记忆库中优良个体与中等种群交叉操作,提高了算法的全局优化能力。

经过优化求解,ICSA求得的最终调度方案甘特图如图3所示。

4 结 语

本文针对HFSP的特点,研究了免疫克隆选择算法(ICSA)求解最小化最大流程时间为目标的HFSP调度问题,仿真结果表明该方法是一种有效的方法。具有其它优化算法(遗传算法、启发式算法等)不同的优良特性,如产生抗体的多样性能力、自我调节机制、记忆功能等,采用分组和多克隆操作(变异、交叉),提高了算法的全局搜索和快速收敛能力。如何针对不同问题的特点,引入疫苗提取与接种机制以及和其他算法结合,提高算法的有效性,是下一步研究的重点。

参考文献

[1]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003:30-45.

[2]Hart E,Nelson J.Producing robust schechules via an artificial immune system[C]//Proc of the ICEC'98Seoul IEEE Press,1998:464-469.

[3]葛红,毛宗源.免疫算法的改进[J].计算机工程与应用,2002,14:47-49.

[4]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007:60-89.

[5]王自强,冯博琴.车间流程的免疫调度算法[J].西安交通大学学报,2004,38(10):1031-1034.

[6]宋继伟,唐加福.基于DPSO的无等待混合流水车间调度方法[J].系统仿真学报,2010,22(10):2257-2261.

[7]韩忠华,史海波,刘昶.混合流水车间提前/拖期调度问题的DE优化解[J].计算机工程与应用,2009,45(32):9-13.

[8]Hu R,Wang L,Qian B,et al.Differential evolution method for stochas-tic flow shop scheduling with limited buffers[C]//2008IEEE Con-gress on Evolutionary Computation,Hong Kong,2008:1295-1301.

[9]Castro L.The clonal selection algorithm with engineering applications[C]//Workshop Proceedings of GECCO00,Workshop on Artificial Immune Systems and their Applications,Las Vegas,USA,2000.

[10]王金鹏,朱洪俊,周俊.最优子种群遗传算法求解柔性流水车间调度问题[J].计算机应用研究,2012,29(2):442-526.

混合免疫 第3篇

无线传感器网络 (Wireless Sensor Networks, 简称WSN) 不同于传统的网络, 它是由许多传感器节点自组网络形成的, 并广泛地应用在军事、环境、家居等各个领域。每个传感器节点都具有低成本、低功耗、多功能、体积小等优点。但同时也具有能量有限和节点不可再生等先天性缺点。这些节点通常被安放在无人监控或者人力难以到达的环境中, 完成信息采集, 数据传送等重要工作。因此, 在设计无线传感网络节点路径时, 需要有效地优化节点间路劲, 尽量减少由于路径过长造成的能量损耗。

1 人工免疫算法

1996年12月, 在日本首次举行的基于免疫性系统的国际专题讨论会上首次提出了“人工免疫系统” (AIS) 的概念。随后, 越来越多的学者投入到人工免疫系统的研究中。但由于人工免疫系统是对生物免疫系统的仿真, 而生物免疫系统本身的复杂性, 所以对人工免疫系统的描述并不多见。人工免疫算法 (AIA) 是基于人工免疫系统提出的一种仿生智能算法, 其仿生原型是生物体的免疫机制。算法具体步骤如下:①输入抗原:抗原即为人工免疫算法需要求解的问题;②产生初始抗体:按照一定的编码形式, 由系统随机产生针对抗原的初始解;③计算亲和力:计算抗体与抗原的亲和力, 亲和力表现了抗体对抗原的识别程度, 亲和力越高, 说明抗体对抗原的识别程度越好;④抗体的更新:将亲和力高的抗体加入种群;⑤抗体的促进和抑制:高亲和力的抗体受到促进, 低亲和力的抗体受到抑制;⑥种群的更新:对亲和力高的抗体按照免疫算子进行变异产生新的抗体, 并加入种群;⑦若满足终止条件则结束, 否则转③。

在AIA求解问题时, 需要确定抗体的编码、抗原的选择、亲和度表达式、排斥力表达式等问题。一般来说, 抗体的编码用一串字符串编码, 满足约束条件的最优解即认为是抗原, 亲和度计算公式和排斥力计算公式需根据待解决的问题实际定义, 亲和度公式是否合适直接影响了最优解求解速度和质量, 排斥力公式是否合适直接影响了抗体的多样性, 好的排斥力公式能有效地防止算法陷于局部最优解。AIA具有快速随机的全局搜索能力, 但不能有效地利用系统的正反馈信息, 往往会做大量的冗余迭代, 降低了求解效率。

2 蚁群算法

蚁群算法 (ACO) 是由意大利学者M.Dorigo, A.Colorni, V.Manizzo等在20世纪90年代初提出来的一类新的仿生智能算法。它是模拟蚂蚁在没有任何提示的情况下能找到通往食物的最短路径的行为产生的。蚂蚁会在走过的路径上释放一种叫做信息素的物质。当蚂蚁群体在食物和巢穴间还没有形成一条最短路径的时候, 会遇到很多岔路口, 当它们碰到一个还没有走过的路口的时候, 就随机选择一条路径, 并在经过该路径的同时, 释放信息素。信息素是可以挥发的物质, 路径越长该蚂蚁在该路径上残留信息素量越小。当后来的蚂蚁再次碰到这个路口的时候, 就会以更高的概率依据每条路径上的信息素残留量选择残留量高的路径, 这样便形成了一个正反馈机制, 最终使蚁群找出最优路径。

蚁群算法的基本步骤:

①参数初始化;②循环次数Nc←Nc+1;③蚂蚁的禁忌表索引号k=1;④蚂蚁数目k←k+1, 蚂蚁个体按照状态转移概率选择元素j并前进, j∈{C-tabuk};⑤修改禁忌表指针, 即选择好之后将蚂蚁移动到新的元素, 并把该元素移动到该蚂蚁个体的禁忌表中;⑥若集合C中元素未遍历完, 即k

ACO具有分布式并行全局搜索能力, 但由于初期信息素匮乏, 求解速度低。

本文提出的算法融合了人工免疫算法和蚁群算法的优点, 采用人工免疫算法产生初始种群, 即初始最优解集, 利用蚁群算法在初始解上产生信息素分布, 提高求解效率。经比较, 融合后的AIAC在寻优能力和求解效率上都优于人工免疫算法和蚁群算法。

3 人工免疫算法和蚁群算法的融合算法

3.1 AIAC算法实现中的若干问题

人工免疫-蚁群混合算法 (AIAC) 的思想是算法的前过程充分利用AIA的快速性和全局收敛性, 寻找较优的可行解, 产生信息素分布, 然后充分利用蚁群算法的正反馈性提高求解的效率。

用AIAC 算法优化WSN路径必须解决一下几个关键问题:

(1) 抗体的编码形式:随机将节点的编号排成一列字符串。例如, 由8个节点, 编号分别是1、2、3、4、5、6、7、8, 那么抗体的排列就可以是2、3、4、6、5、8、1、7, 即该抗体的编码形式就可以为 23 465 817。

(2) 抗原:预先设定的路径总长。

(3) 路径总长计算公式:如果两个节点的坐标分别为A (x1, y1) 、B (x2, y2) 。那么它们之间的距离就可以用公式undefined计算AB两点的距离。

(4) 亲和力计算公式:undefined是一个比较大的正常数, 选取T值是要考虑能保证公式结果为正值, t为抗体路径总长。

(5) 初始种群产生办法。初始种群由初始抗体进行预处理后的抗体组成, 初始抗体是按照轮盘赌的方式产生的。轮盘赌算法的基本思想是假设一个转动的轮盘, 轮盘最多只转一圈, 每次转动轮盘前, 把色子随机地放到轮盘外缘的某处, 即色子不随轮盘转动, 以一个随机数sel代表它所处的位置。轮盘转动后, 色子所指示的轮盘扇区号不断变化, 轮盘停止时色子所指示的轮盘上的扇区号, 即为本次轮盘赌所选中的个体号。

(6) 算法终止条件。抗体亲和度阈值a, a的值需要根据实际情况预先设定, a值的取值精确度直接关系到最优路径的精确度。

(7) 人工免疫算子:交叉、变异、克隆。

3.2 人工免疫算子

①交叉算子采用Davis提出的顺序交叉方法, 先进行常规的双点交叉, 再进行维持原有相对访问顺序的巡回路线修改;②变异算子有3种:字符串换位算子、字符串逆转算子、优质字符串保留。

3.3 算法的基本步骤

①确定抗体的编码方式;②根据实际问题输入抗原;③对初始抗体进行预处理形成初始种群;④分别对每个初始抗体计算亲和力;⑤判断是否满足结束条件, 若是则输出结果, 若否则进行下面过程;⑥对亲和力高的抗体按照变异数量公式进行变异, 得到新种群;⑦使用蚁群算法, 对新种群中的抗体产生初始信息素分布;⑧计算每只蚂蚁移动到下一节点的概率, 并根据选择概率移动每只蚂蚁到下一节点;⑨m只蚂蚁遍历n个节点后, 最优蚂蚁圈进行信息素增加;⑩所有路径信息素更新, 并进行递归迭代, 若满足终止条件, 则输出最优解更新种群, 并跳转到步骤④。算法流程见图1。

4 仿真结果

在Matlab中对拥有31个节点的WSN进行路径优化, 参数设置如下:

人工免疫算法部分参数初始化值:

N=31, NIND=100, MAXGEN=200, Pc=0.9, Pm=0.05, GGAP=0.9, Threshold=0.7。

蚁群算法部分参数初始化值:

m=50, alpha=1, beta=5, rho=0.1, Q=1。

经过10次迭代后产生如图2的结果。

从结果可以看出, AIAC能有效地优化节点间路径, 使节点间信息以最优路径传递。

5结论与分析

本文提出了用AIAC来解决WSN中路径优化的问题, 在蚂蚁算法处理路径优化问题效率较高的基础上, 人工免疫算法把最优路径长度作为抗原, 这就能保证所生成的抗体直接与问题相联系, 收敛方向能得到有效的控制, 不至于使得出的解偏离最优值。保留与抗原具有高亲和力的抗体, 能促进快速求解, 避免对劣质抗体做过多的操作, 降低了求解效率。算法中的人工免疫算子增强了抗体的多样性, 保证了算法不至于陷于局部最优解。本算法解决WSN路径优化问题可达到更高的效率, 仿真结果也证实了这一点。

参考文献

[1]莫宏伟, 左兴权.人工免疫系统[M].北京:科学出版社, 2009.

[2]莫宏伟, 基于免疫网络的数据挖掘原理与应用研究[D].哈尔滨:哈尔滨工程大学, 2005.

混合免疫 第4篇

关键词：病毒混合感染,ELISA,PCR,免疫抗体效价,关系分析

黑龙江省地处高寒地区,秋冬季节容易出现病毒性疫病的流行。虽然大中型猪场都会执行相应的免疫程序,但由于寒冷应激、饲养管理问题和猪群自身免疫力等各方面综合原因,猪群常常会出现病毒性疾病和细菌性疾病的感染,甚至是混合感染。笔者对黑龙江省某猪场425 头发病断奶仔猪进行了剖检及病原鉴定,对圆环病毒病( PCVD) 、猪瘟( SCF) 、猪繁殖与呼吸综合征( PRRS) 、伪狂犬病( PR) 进行了抗体检测,以期为该猪场的生产进行指导,从而有效地控制疾病的进一步流行。

1 材料与方法

1. 1 试剂及检测方法

TRIzol,Autolab Tech公司产品; DEPC,Sigma公司产品; DL - 2 000 DNA Marker,Tiangen公司产品;AMV反转录酶、RNase Inhibitor、r Taq DNA聚合酶、d NTPs等,均购自Clontech公司。

猪蓝耳病病毒( PRRSV X3 Ab) 抗体检测: 猪蓝耳病病毒的ELISA抗体检测试剂盒由美国IDEXX公司生产,检测方法按其试剂盒使用说明书进行操作。当S /P值≥0. 4 时为阳性; S /P值< 0. 4 时为阴性。

猪圆环病毒2 型( PCV - 2 Ab) 抗体检测: PCV -2 的ELISA抗体检测试剂盒由美国IDEXX公司生产,检测方法按其试剂盒使用说明书进行操作。当S / P值≥0. 25 时为阳性; 0. 16 < S / P值< 0. 25 时为可疑; S /P < 0. 16 时为阴性。

猪瘟病毒( CSFV Ab) 抗体检测: 猪瘟病毒抗体检测试剂盒由美国IDEXX公司生产,检测方法按其试剂盒使用说明书进行操作。被检样品抗体阻断率≥40% ,判定为阳性; 阻断率≤30% ,判定为阴性; 阻断率介于30% ~ 40% 之间,为可疑。

猪伪狂犬病病毒g B( PRV g B Ab) 抗体检测: 猪伪狂犬病病毒抗体检测试剂盒由美国IDEXX公司生产,检测方法按其试剂盒使用说明书进行操作。S /P比值< 0. 5 时,样品PRV抗体阳性; S /P比值>0. 7 时,样品PRV抗体阴性; S / P比值介于0. 5 ~0. 7 之间时则为可疑。

1. 2 对发病猪场的免疫、生产繁殖和既往病史情况进行调查

了解发病猪场以往使用疫苗的种类、是否有合理的猪群结构、环境等饲养管理是否合理、以往都发生过何种疾病以及应对措施等,综合考虑猪场猪群发病的原因。

1. 3 送检病猪病原学检测

猪场送检病死断奶仔猪( 35 日龄) 1 头,无菌采取病死猪肺门淋巴结、脾脏,液氮保存备用。各部位分别取部分病料加少量灭菌PBS液( 含青霉素100 IU / m L、链霉素 μg / m L) ,进行无菌研磨,取PB液按4 倍体积倍比稀释,分别在- 20 ℃ 和37 ℃ 反复冻融3 次,8 000 r/min( 4 ℃) 离心10 min,取上清液,- 20 ℃ 保存待检。

1. 4 引物合成

根据参考文献[1]中的方法常规合成PRRSV、CSFV、PCV - 2、PRV的RT - PCR引物。

1. 5 病毒总RNA提取

取-20 ℃保存的各病料上清液,按TRIzol LS Reagent试剂盒( Invitrogen公司产品) 使用说明书提取病毒总RNA,15 μL DEPC水溶解,-20 ℃保存待检。

1. 6 RT - PCR检测

取10 μL RNA,加1 μL下游引物、3. 5 μL d NTP、0. 5 μL RNase Inhibitor、1 μL LAMV、4 μL 5 × AMV Buffer,42 ℃ 水浴1. 5 h,得c DNA模板,之后进行PCR检测。PCR反应体系为: 10 × PCR Buffer 5 μL,d NTPs 4 μL,上、下游引物各1 μL,r Taq 0. 6 μL,c DNA 4 μL,用灭菌的dd H2O补齐至50 μL体系。反应参数: 95 ℃ 变性5 min; 94 ℃ 变性1 min,58 ℃ 退火40 s,72 ℃ 延伸50 s,共33 个循环; 最后72 ℃ 延伸10 min。反应结束后取7 μL PCR产物用1% 琼脂糖凝胶在120 V下电泳30 min,观察结果。

1. 7 发病猪场血清采集

对该猪场的种猪和不同日龄仔猪随机采集血样。耳静脉无菌采集猪全血2 m L,37 ℃ 放置1 h后4 ℃过夜,待全血凝固并析出血清后,4 000 r/min离心5 min,取上清液,- 20 ℃ 保存,待检。共采集待检血清425 份。

1. 8 抗体检测

参照CSFV、PRRSV、PRV、PCV - 2 抗体ELISA检测试剂盒使用说明书对血清样本进行检测。

2 结果

2. 1 猪场既往病史调查结果

猪场曾进行了常规的疫苗免疫,包括猪瘟兔化弱毒疫苗、口蹄疫疫苗、伪狂犬灭活苗、猪繁殖与呼吸综合征灭活苗,PCV - 2 灭活疫苗( LG株) 。猪场曾经出现过散发性的CSF、PRRS和PCVD,实验室检测鉴定确诊后,及时进行了相应的淘汰和净化。

2. 2 送检病猪临床症状及剖检变化

病猪精神萎靡、消瘦、贫血、被毛蓬乱,虚弱无法行走,眼睑水肿,皮肤苍白,体表淋巴结肿大,呼吸困难。

病理变化主要为全身淋巴结肿大、出血,其中颌下和腹股沟淋巴结病变特别明显; 胃底部黏膜出血,胃内有少量积食,肾脏表面有点状出血; 肺脏呈现明显的间质性肺炎,表面有出血; 脾脏肿大,有紫色的出血灶; 肝脏颜色发暗、萎缩,肾脏水肿。

2. 3 被检材料PCR扩增结果

常规合成PRRSV、CSFV、PCV - 2、PRV的引物,以病毒总RNA为模版,经RT - PCR扩增后,进行琼脂糖凝胶电泳,结果见图1。显示PRRSV、PCV - 2、PRV呈阳性,PCR产物符合预期产物的大小,CSFV病原检测呈阴性。

1.PRRSV PCR阳性;2.CSFV PCR阴性;3.PCV-2 PCR阳性;4.PRV PCR阳性;M.DL-2 000 Marker。

2. 4 猪场血清学检测结果

用ELISA方法对采集的425 份血清进行抗体检测,公猪、后备母猪、妊娠母猪、56 日龄仔猪平均抗体阳性率在70% 以上,100 日龄仔猪的PRV g B抗体水平低,21 日龄仔猪的CSFV抗体、PRRSV抗体、PCV - 2 抗体水平较低,见表1。

3 小结和讨论

本次剖检1 例35 日龄病死仔猪,根据临床症状、剖检病变观察和病原的PCR鉴定得出,该猪系PRV、PRRSV、PCV - 2 混合感染。该猪场已经发现5 头相似症状的断奶仔猪,因此对该猪场进行免疫效果监测、及时找出发病原因是非常必要的。因此,随机采集该猪场的公猪、妊娠母猪、后备母猪和不同日龄仔猪血清共计425 份进行血清抗体检测。结果显示公猪四种抗体平均阳性率达到80. 0% ,后备母猪四种抗体平均阳性率达到81. 7% ,妊娠母猪四种抗体平均阳性率达到79. 5% ,均高于国家标准,可见该猪场的公猪、后备母猪和妊娠母猪的总体免疫情况良好。仔猪采集了21 日龄、56 日龄、100 日龄三种日龄共计265 份血清,其中21 日龄仔猪CSFV抗体、PRRSV抗体和PCV - 2 抗体阳性率偏低,提示其为这些疾病的多发阶段; 56 日龄仔猪四种抗体合格率良好,100 日龄仔猪的CSFV抗体、PRRSV抗体和PCV - 2 抗体均在85% 以上,抗体水平较高,说明这个时期的猪群免疫力尚可。PRV抗体在仔猪21 日龄至100 日龄呈大幅下降趋势,母源抗体水平随着时间的推移逐渐下降,疫苗免疫抗体水平没有显著的提升,这跟免疫程序和疫苗间的相互影响及仔猪个体情况均有关系,过早地免疫会导致仔猪体内存在高水平的母源抗体而对免疫没有反应,因此应该调整免疫时间。

猪场出现的发病猪均在30 日龄左右,根据检测的抗体水平看,21 日龄的仔猪正是免疫保护力最低的时期,这个时期的母源抗体已经大幅下降,同时疫苗免疫的抗体水平还没上升,因此出现了通常所说的空档期,这对疾病的防控极其不利。

黑龙江省地处高寒地区,每到秋冬季节都是猪场发生疫情的主要阶段,因此及时地掌握免疫情况和发病情况避免疾病的扩散和流行,是规模化养猪场应该重视的。从抗体阳性率数值看,该猪场猪群抗体的整齐度好,个体差异不大。调查既往史发现,该猪场散发过PRV和PCV - 2,原因可能是疫苗保护率的差异,导致个别母猪免疫失败,或者是仔猪个体差异不产生抗体。PCV - 2 疫苗的应用在一定程度上有效控制了PCV - 2 感染,提高了猪的生长性能[2,3],但目前疫苗免疫并不能完全阻断病毒的传播,也不能清除体内已感染的病毒。PCV - 2 和PRRSV同属于免疫抑制病,断奶仔猪极易感染,并且特别容易继发PR以及CSF等,同时有的患病猪还会出现细菌感染和支原体感染。本次检测的病死猪同时感染了三种病毒,综合考虑可能由于PRRSV、PCV - 2 的感染造成该群猪免疫抑制,从而继发了伪PR。

综上,目前的首要任务是对猪场进行彻底净化和消毒,严格控制人员进出,同时将疑似病例进行实验室诊断,隔离饲养观察。重新制订免疫程序,猪场的免疫程序制订要根据情况灵活调整,切忌一刀切,一套程序应用多年,最终导致免疫的失败; 对猪群进行密切监测,一旦发现疫情,要及时处理,防止疫病的大规模流行给养殖户带来不必要的损失[4,5]。

参考文献

[1]岳丰雄.鉴别PCV-2、PPV、PRV、PRRSV、CSFV多重PCR诊断方法的建立及初步应用[D].乌鲁木齐:新疆农业大学,2008.

[2]彭志峰.河南省猪2型圆环病毒分子流行病学调查[D].郑州:河南农业大学,2009.

[3]韩庆安,许玉静,刘红,等.河北省猪繁殖与呼吸综合征病毒隐性感染情况的调查[J].中国兽医科学,2011,41(03):314-319.

[4]LI Y F,WANG X L,BO K T,et al.Emergence of a highly pathogenic porcine reproductive and respiratory syndrome virus in mid-east China[J].Vet J,2007,174(3):577-584.