第5期 赵云丰，等：禁忌免疫网络算法及其在函数优化中的应用 ·395 种禁忌人工免疫网络算法(Tabu search artificial a=(1/B)ep(-f) (3) mmune netork,TS-aNet) 式中：细胞C`是细胞C变异后产生的新细胞，N(0, 1)利用禁忌搜索算法改进人工免疫网络 1)是一个均值为0、标准差为1的Gauss随机变量 引入一个灵活的存储结构和相应的禁忌准则， B是控制指数函数衰减的变量，∫是标准化处理后 以避免迂回搜索，并通过特赦准则赦免一些被禁忌 的细胞亲和力值.该方法的缺点是： 的优良状态.在TS-aNet算法中，禁忌表用于记忆最 1)由式2)看出，这种变异方式往往会使细胞 近的一些迭代过程中亲和力没有增加的网络细胞， 的克隆体与父代细胞克隆体有一定重合： 并将这些细胞禁忌.随机生成细胞时，如果在禁忌表 2)从式3)看出，细胞的变异大小与细胞所对 的细胞形成的邻域中，将不被引入网络.当禁忌表中 应的解所在的位置无关，而只与网络中其他细胞的 的细胞禁忌次数超过一定的阈值时，将这些细胞特 亲和力有关，也就是说，在克隆选择过程中，评价的 赦.这样保证了对抗原空间的持续搜索能力和多样 尺度仅仅是个体的亲和力.在当该细胞的亲和力在 化的有效搜索，使得引入网络的随机生成的细胞有 网络中越排在前面时，变异的范围就越小，这不完全 更好的分布性，减少迂回搜索，能够搜索到更多的极合理.因为对于多峰值函数，峰值的函数值一般并不 值点，同时提高搜索全局最优点的速度，从而提高了 一定都能达到全局最大值，如果仅以亲和力作为评 TS-aNet算法的全局搜索能力，加快收敛速度 价指标，很容易使种群中相似亲和力的个体迅速增 2)在网络中增加免疫记忆 加，而函数值较小峰对应的个体，很难进入下一代. 免疫细胞经历骨髓模型，成熟并进入免疫循环 因此，函数值较小的峰值很容易被漏掉，导致算法多 成熟的免疫细胞具有固定的生命周期T,若在T时 样性差，容易出现未成熟收敛现象 间内积累了足够的亲和力，则成为记忆细胞.禁忌人 针对以上问题，利用迭代过程中细胞的变化来 工免疫网络算法模拟了这个机制，当网络中的细胞 估计下一代的大致位置，然后以这个位置为中心进 逐步成熟，并进入禁忌表，禁忌一段时间以后，该细 行搜索，不仅依靠记忆细胞，而且借助网络结构.改 胞将被释放，可以认为该细胞成了记忆细胞.为了保 进后 护记忆细胞，增加了一个记忆表.记忆细胞会不断的 C=C+ld|+aN0,1),d≠0 (4) 被更新，每次进行网络抑制时，如果网络中存在一个 式中：a=(R/B)ep(-f),d=C:-C.i,C,细胞 细胞，它在某个记忆细胞的邻域内，并且它的亲和力 在第次迭代取值，R是细胞变量的取值范围.当细 比该记忆细胞的大，该记忆细胞将被其替换.这样使 胞初次进入网络中，没有任何先验信息时，d=0,变 得记忆细胞逐渐趋近于局部极值，同时，通过更新替 异方式与高斯变异相似，只是增加了一个变量取值 换，避免记忆表增长的太大 范围.另外，当细胞趋近局部极值时，|d可能会越来 记忆细胞机制的引入，保存了搜索到的局部极 越小，这样会影响收敛速度，可以为其设定下限，如： 值，使得这些局部极值对应的细胞不再参与细胞网 T,=ange/100,其中range为[0,1的随机数 络的迭代，从而使网络保持原有的规模，而不是逐渐 通过改进，TS-aNet算法可以具有更好的极值 增大，大大减少计算量.另外，当算法结束时，记忆表 搜索能力、更快的收敛速度 中的记忆细胞和即将进入记忆表的细胞就是所有的 22TS-aNet算法的设计与实现 局部极值点，从中可以找到全局最优点.免疫记忆保 221TS-aNet算法的设计 存了各个局部最优解，这对于多峰值函数优化具有 禁忌人工免疫算法，增加了禁忌表、记忆表和进 重要意义 化方向表.禁忌表存储网络迭代过程中一些亲和力 3)重新定义变异方式 没有增加的次数达到阈值的细胞，记录细胞各变量 在经典aNet算法中，采用的高斯变异方法为 取值、亲和力和禁忌次数，记忆表存储记忆细胞，记 C=C+aN0,1), (2) 录细胞各变量取值和亲和力：进化方向表存储网络 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net一种禁忌人工免疫网络算法 ( Tabu search artificial immune network, TS2aiNet). 1)利用禁忌搜索算法改进人工免疫网络 引入一个灵活的存储结构和相应的禁忌准则 , 以避免迂回搜索 ,并通过特赦准则赦免一些被禁忌 的优良状态. 在 TS2aiNet算法中 ,禁忌表用于记忆最 近的一些迭代过程中亲和力没有增加的网络细胞 , 并将这些细胞禁忌. 随机生成细胞时 ,如果在禁忌表 的细胞形成的邻域中 ,将不被引入网络. 当禁忌表中 的细胞禁忌次数超过一定的阈值时 ,将这些细胞特 赦. 这样保证了对抗原空间的持续搜索能力和多样 化的有效搜索 ,使得引入网络的随机生成的细胞有 更好的分布性 ,减少迂回搜索 ,能够搜索到更多的极 值点 ,同时提高搜索全局最优点的速度 ,从而提高了 TS2aiNet算法的全局搜索能力 ,加快收敛速度. 2)在网络中增加免疫记忆 免疫细胞经历骨髓模型 ,成熟并进入免疫循环. 成熟的免疫细胞具有固定的生命周期 T,若在 T时 间内积累了足够的亲和力 ,则成为记忆细胞. 禁忌人 工免疫网络算法模拟了这个机制 ,当网络中的细胞 逐步成熟 ,并进入禁忌表 ,禁忌一段时间以后 ,该细 胞将被释放 ,可以认为该细胞成了记忆细胞. 为了保 护记忆细胞 ,增加了一个记忆表. 记忆细胞会不断的 被更新 ,每次进行网络抑制时 ,如果网络中存在一个 细胞 ,它在某个记忆细胞的邻域内 ,并且它的亲和力 比该记忆细胞的大 ,该记忆细胞将被其替换. 这样使 得记忆细胞逐渐趋近于局部极值 ,同时 ,通过更新替 换 ,避免记忆表增长的太大. 记忆细胞机制的引入 ,保存了搜索到的局部极 值 ,使得这些局部极值对应的细胞不再参与细胞网 络的迭代 ,从而使网络保持原有的规模 ,而不是逐渐 增大 ,大大减少计算量. 另外 ,当算法结束时 ,记忆表 中的记忆细胞和即将进入记忆表的细胞就是所有的 局部极值点 ,从中可以找到全局最优点. 免疫记忆保 存了各个局部最优解 ,这对于多峰值函数优化具有 重要意义. 3)重新定义变异方式 在经典 aiNet算法中 ,采用的高斯变异方法为 C 3 =C +αN (0, 1) , (2) α= (1 /β) exp ( - f 3 ). (3) 式中 :细胞 C 3 是细胞 C变异后产生的新细胞 , N ( 0, 1)是一个均值为 0、标准差为 1的 Gauss随机变量 , β是控制指数函数衰减的变量 , f 3 是标准化处理后 的细胞亲和力值. 该方法的缺点是 : 1)由式 (2)看出 ,这种变异方式往往会使细胞 的克隆体与父代细胞克隆体有一定重合; 2)从式 (3)看出 ,细胞的变异大小与细胞所对 应的解所在的位置无关 ,而只与网络中其他细胞的 亲和力有关 ,也就是说 ,在克隆选择过程中 ,评价的 尺度仅仅是个体的亲和力. 在当该细胞的亲和力在 网络中越排在前面时 ,变异的范围就越小 ,这不完全 合理. 因为对于多峰值函数 ,峰值的函数值一般并不 一定都能达到全局最大值 ,如果仅以亲和力作为评 价指标 ,很容易使种群中相似亲和力的个体迅速增 加 ,而函数值较小峰对应的个体 ,很难进入下一代. 因此 ,函数值较小的峰值很容易被漏掉 ,导致算法多 样性差 ,容易出现未成熟收敛现象. 针对以上问题 ,利用迭代过程中细胞的变化来 估计下一代的大致位置 ,然后以这个位置为中心进 行搜索 ,不仅依靠记忆细胞 ,而且借助网络结构. 改 进后 C 3 = C +| d | +αN (0, 1) , d ≠ 0. (4) 式中 :α= (R /β) exp ( - f 3 ) , d = Ci - Ci - 1 , Ci 细胞 在第 i次迭代取值 , R是细胞变量的取值范围. 当细 胞初次进入网络中 ,没有任何先验信息时 , d = 0,变 异方式与高斯变异相似 ,只是增加了一个变量取值 范围. 另外 ,当细胞趋近局部极值时 , | d |可能会越来 越小 ,这样会影响收敛速度 ,可以为其设定下限 ,如 : Td = range /100,其中 range为 [ 0, 1 ]的随机数. 通过改进 , TS2aiNet算法可以具有更好的极值 搜索能力、更快的收敛速度. 2. 2 TS2aiNet算法的设计与实现 2. 2. 1 TS2aiNet算法的设计 禁忌人工免疫算法 ,增加了禁忌表、记忆表和进 化方向表. 禁忌表存储网络迭代过程中一些亲和力 没有增加的次数达到阈值的细胞 ,记录细胞各变量 取值、亲和力和禁忌次数 ;记忆表存储记忆细胞 ,记 录细胞各变量取值和亲和力 ;进化方向表存储网络 第 5期 赵云丰 ,等 :禁忌免疫网络算法及其在函数优化中的应用 ·395·