一种用于函数优化的免疫算法

xiaoguiroger

人工免疫系统是基于生物免疫系统特性而发展的新兴智能系统。利用免疫系统的克隆选择机制，提出一种用于函数优化的改进免疫算法。其主要特点是采用克隆和自适应变异等操作，提高收敛速度和种群的多样性。仿真程序表明，该算法能以较快速度完成给定范围的搜索和全局优化任务。

　    在工程实际中，很多问题都可转化为函数优化问题，而对于高维、非凸、且有多个局部极值点的函数优化问题，传统的基于梯度的算法通常不能求得理想解。免疫系统作为一种分布式自学习系统，能自适应地维持群体多样性及具有自我调节功能，导致基于免疫机制的算法具有整体、局部搜索能力强的特点，使得这类算法在函数优化、组合优化、模式识别、数据挖掘及机器学习等方面得到了有效应用。

　    1 免疫算法原理

　    免疫算法的灵感来自生物获得性免疫的克隆选择原理。根据该原理，在生物免疫系统中，一旦病原体侵入肌体就被分解为抗原片段，B淋巴细胞能够为产生相应的抗体与抗原结合，同时活化、增殖和分化，产生浆细胞，通过中和、溶解和调理等作用，最终使抗原从体内清除。另有一些B细胞变成了长期存活的记忆细胞，它通过血液、淋巴和组织液循环，为下一次快速、高效的消除相同或者类似抗原引起的感染奠定了基础。

    　免疫算法采用高变异克隆的单性繁殖搜索方式，避免了遗传算法中的交叉操作引起的模式干扰，同时具有未被激发的细胞消亡及记忆细胞的产生等过程又保证了抗体的多样性。

　    2 算法描述

　    克隆选择算法模拟生物免疫系统的克隆选择原理，一般将待优化的目标函数及其约束条件视为抗原，其算法步骤如下：

　　 (1)初始化：随机产生N个二进制编码的抗体对应问题的可能解。

　　  (2)评价和选择1：将N个抗体分解成由m和r个抗体组成的两部分Am，Ar，分别表示进入记忆集的抗体和剩下的部分，其中进入记忆集的都是亲和度较高的抗体。

　　  (3)克隆：在亲和度最高的抗体中选择k个进行克隆，克隆的数量与其亲和度成正比。

　　  (4)变异：模拟生物克隆选择中的超变异过程，对克隆后的抗体执行变异操作，变异按某一变异概率以一定规模随机进行。

　　 (5)评价和选择2：重新计算变异后的抗体的亲和度，若克隆变异后的抗体中亲和度最高的抗体比父代抗体的亲和度还要高，就用该抗体替换原抗体，形成薪的记忆集。

　　 (6)消亡：模拟生物克隆选择中5％的B细胞自然消亡的过程，在Ar中选择d个亲和度最低的抗体重新初始化，以保证抗体的多样性。

　　(7)检查是否满足终止条件，若是，则终止，否则转到(2)，进入下一次迭代。

   　 通过分析不难发现，在CLONAL算法中，所有个体都是二进制编码，计算时需要将十进制数转化为二进制数，最后又必须将二进制数再转化为十进制数；而且对于多维函数的优化，二进制编码面临“维数灾”问题；其次，二进制的位数也限制了求解的精度，要求得高精度的解，势必大幅提高二进制编码的位数，也给计算带栗了麻烦；另外，在CLDNAL算法中，变异率是一个定值，抗体按这个变异率产生一定规模的随机变异，这样虽扩大了搜索空间，增加了抗体的多样性，同时也可能破坏亲和度高的抗体，打乱抗体的结构，降低收敛速度。文献提出一种改进免疫克隆多样性算法，采用实数编码，但它采用变异整个抗体群的方式进行变异，没有保持上代中亲和度高的抗体的优势。文献结合小生境技术，提出一种新的免疫算法，但该算法没有克隆操作，虽提高了收敛速度，但限制了搜索空间。

    　本文提出了一种改进的克隆选择算法，该算法采用实数编码，并引入自适应变异算子，根据抗体的亲和度调整变异步长。仿真实验说明该算法收敛速度快．运算简单、易于实现。

　　3 算法改进

　　在改进的函数优化免疫算法中，以实数编码的候选解作为抗体，将目标函数和约束条件视为抗原，将亲和度高的抗体按与其亲和度成正比进行克隆，并引入自适应变异算子，与亲和度成反比进行变异，使变异程度随着亲和度的提高逐步减小，促使抗体的稳定收敛；同时亲和度低的抗体按一定比例重新初始化，以保证多样性。算祛步骤如下：

    (1)随机初始化种群，种群大小为N，抗体采用实数编码；

　 (2)根据目标函数计算所有抗体的亲和度；

　 (3)若达到结束条件，算法终止；

　  (4)选出部分亲和度高的进入记忆Am，剩下的抗体记为Ar；

　 (5)在Am中选出亲和度最高的k个抗体进行克隆得到克隆抗体群Ab；

　 (6)根据抗体的亲和度计算每个抗体的变异率，并按该变异率进行变异，得到变异抗体群Ac；

　 (7)重新计算Ac中每个抗体的亲和度，在Ac中选出亲和度高的抗体，并用它们调整记忆集；

　 (8)在抗体的记忆集之外取得d个亲和度最低的抗体运用消亡算子予以抛弃，将其重新初始化，形成新的免疫网络；

　 (9)回到(2)。


　　3．1 克隆变异

　　算法中主要的免疫操作包括了克隆和变异。

    　克隆是拷贝抗体编码模式的过程，假设父代抗体为X=[x1，x2，……xn]T，则克隆后产生的子代抗体为X′=Ii×X，Ii是NCi维行向量。而NCi就决定了抗体克隆的数量，在这里NCi可由下式得到：


　　 β∈(0，1)是克隆常数，N是种群规模，将要克隆的抗体按亲和度排序，i是其序号。其结果是亲和度越高的抗体克隆的数量越多。

   　 变异的目的是使子代抗体的编码发生变化，以期得到优于父代的更好的解。由于算法中的抗体采用实数编码，因此原来的变异方法不再适用，而是采取了高斯变异的方式，并且变异并不作用到原始种群。

    　为了能在亲和度高的抗体周围集中搜索，同时又保证抗体的多样性，本文引入了一种自适应变异算子，即对每一个变异算子作用到的个体分量：

   　 其中N(0，1)是一个服从标准高斯分布的随机数；而Nmi则对应抗体的变异率，不失一般性，对求解最小值的问题：


    　显然，抗体的变异率是与其亲和度成反比的，亲和度越高变异率越小，抗体在每次迭代过程中根据亲和度自适应的调整变异步长，使得在亲和度高的抗体周围集中搜索以提高收敛速度，同时保持种群的多样性。ρ为变异常数，用来调整变异强度，与搜索的空间大小和种群规模相关。

　　3．2 调整免疫网络

　　 与遗传算法相比，免疫算法的一大特点就是其具有记忆性，从新的抗体群中选出优势个体，排除退化个体的过程就是重新生成免疫网络的过程。

   　 经过克隆和变异后，若存在新抗体ρ=min{f(xij)|j=1，2，……n}，使得f(p)