一种改进的免疫遗传算法求解0-1背包问题

杜彦华 靳宗信

（1.黄河科技学院 图书馆，河南 郑州 450063；2.黄河科技学院 信息工程学院，河南 郑州 450063）

在现代科技高速发展的过程中，随着交叉学科的发展，从生物体各个信息处理系统中抽取相应的人工模型已成为研究的热点。人工免疫模型正在为科学贡献力量，以其为基础的各种模型已经应用于科学的各个领域。

传统的遗传算法存在缺陷，例如在迭代后期容易出现退化现象，算法的收敛速度慢等。但传统遗传算法的改进算法较多，已被成功用于科学的不同领域。

生物作为计算问题的思想源泉，已经为科学工作者提供了许多解决问题的思路。生物免疫系统自身的许多机制，如适应性、记忆性和多样性等机制能被用来解决各种计算任务，在此基础上发展起来的计算方法已经成为一门学科，已经引起不同领域学者的关注。根据生物免疫系统与传统遗传算法结合而产生的免疫算法已经表现出良好的性能，本文将生物免疫系统产生多样性抗体的产生机制加入到传统的遗传算法中，提出了一种新型的免疫遗传算法。为了检测此算法的特性，使用经典的0-1背包问题进行检验，仿真实验结果表明此算法能够很快找到全局最优解，克服遗传算法的缺点，表现出较高的效率。

NIGA

在传统的遗传算法中加入生物体产生抗体的多样性机制，即加入免疫算子，不仅保留了原算法本身的优良特性，还可以抑制算法在迭代过程中出现的退化现象，提高算法的收敛速度。免疫算子对应于待求解问题的解的一些特征信息。NIGA的执行效率在很大程度上取决于免疫算子的选取。免疫算子的好坏，即生成抗体的优劣不会影响算法的收敛性，只会影响算法的收敛速度和免疫算子在整个算法中的作用。所以免疫算子的优劣直接影响了算法的好坏。本文改进了提取免疫算子的方法，并把这种方法加入到免疫遗产算法中去，得到了一种新型的免疫遗产算法（NIGA）。使用经典的NP难问题对其进行检验后，表明此算法能够很快找到当前最优解。

根据生物学的相关知识，生物染色体上的固定位置上的基因位可以决定生物的性状。也就是说，基因通过两个方面影响生物的性状，第一个是基因本身碱基的顺序，第二个是基因本身在染色体上的位置，由此可知，虽然两个基因的碱基顺序相同，但把它们放在染色体的不同位置，生物体就会表现出不同的性状。本文的免疫算子是一个基因串，其包含一个或多个基因位。为了使免疫算子发挥更大的作用，在产生免疫算子时对其位置信息也进行保存。免疫算子的结构如图1所示：

图1 免疫算子的结构图

在NIGA中，为了对免疫算子进行综合分析，需要建立一个算子库，算子库中用来存放全部迭代中的全部的优良免疫算子。免疫算子库由两个子库组成：H1和H2，其中子库H1中存放的算子的长度为2，H2中免疫算子的长度为Bl，Bl的长度可以通过计算得到。

免疫算子库H2中算子的长度可用下面的公式来计算：

其中：rand为随机数；α，β，γ分别取0.615，0.855和0.951，均为经验值。

根据操作的需要，在算法运行的过程中要始终保持免疫算子库中算子的数量不变。为了达到这个目的，当每次有新的算子加入算子库后，都要对库中所有的免疫算子按照适应度进行排序，保留适应度较大的算子。其中免疫算子库的大小可用下面的公式来计算：

上式中m表示算法中种群的数量，η表示调整系数。

子库H1的建立方法为：

（1）从抗体群中随机选取一个抗体，此抗体的所有基因位组成集合A，A={g1，g2，Λgn}；

（2）在集合A中随机选取一基因位g1，由基因g1与A-{g1}中的所有基因组成长度不同的基因段，并计算每个基因段的适应度；

（3）把计算后的基因段按照适应度进行从大到小排序，选取前k1个基因段组成子库H1；

子库H2的建立方法为：

（1）计算群体中所有抗体的适应度，并按照适应度按照从大到小的顺序排序；

（2）在集合A中随机选取一个基因位g1，在排序后的每个抗体中找到相应的基因g1，选取以g1开头，长度l为的基因段；

（3）把所有的基因段按照适应度排序，选取适应度最大的k2个基因段组成H2；

由于每个免疫算子本身包含了其在解中的位置信息，所以在注射疫苗时可以根据该信息所标注的位置进行注射，而不是采用随机注射的方式，从而使疫苗注射的位置更加合理。

更重要的是，在向抗体中加入算子时，除了要有效利用算子自身携带的位置信息以外，还要防止新算子的加入而导致已有算子的破坏。当这种情况发生时，以保留适应度高的算子为准。

基因中注射算子的算法如下：

（1）在免疫算子库中按轮盘赌的方法选取一个算子xi；

（2）在群体中也采用轮盘赌的方式选取一个抗体yj，根据xi所含的位置信息，在yj中找到加入算子的相应位置；

（3）找到抗体yj中xi与算子相冲突的部分，并将其删除；

（4）加入算子xi，得到yj；

（5）进行免疫检测，即计算yj的适应度，并与yj的适应度进行比较，取适应度较大着进入下一代；

此算法的流程图如图2所示。

图2 加入算子及检测过程流程图

综合上述，本文中NIGA的步骤如下：

（1）使用随机的方法产生初始种群Po；

（2）产生免疫算子库；

（3）计算种群的适应度；

（4）进行适应度判断，若种群中包含最佳个体，即找到最优解，则终止算法并输出结果，否则继续以下操作；

（5）对第k代种群Pk进行交叉和变异操作，得到种群Ak；

（6）向种群Ak中的每个个体注射疫苗后进行免疫选择，得到下一代种群Pk+1；

该算法的流程图如图3所示。

图3 改进的免疫遗传算法流程图

NIGA求解0-1背包问题

为了验证本文所提出的NIGA算法的全局寻优能力和有效性，现以0-1背包作为测试算例，并引用参考文献中的数据。从表1可以看出：NIGA比一般的遗传算法（IGA）更容易找到最优解。

表1 100次实验结果数据

结论

本文提出了一种新的免疫算子的提取方法，并用这种方法建立了免疫算子库，结合生物免疫系统的特性提出了一种新的免疫遗传算法（NIGA），把NIGA应用于0-1背包问题的求解中，仿真结果表明，NIGA能够抑制遗传算法在迭代过程中出现的退化现象，提高算法的收敛速度。