第3卷第5期 智能系统学报 Vol 3 No 5 2008年10月 CAA I Transactions on Intelligent Systems 0ct2008 禁忌免疫网络算法及其在函数优化中的应用 赵云丰，尹怡欣'，付冬梅，王嘉2 (1北京科技大学信息工程学院，北京100083,2煤炭科学研究总院经济与信息研究所，北京100013) 摘要：基于人工免疫网络算法(aNet),借鉴禁忌搜索算法的机制，提出一种禁忌人工免疫网络算法(TS-aNe).在算法 中引入禁忌表，禁忌那些在网络迭代中亲和度不再增加的细胞，并通过特赦准则敖免一些被禁忌的优良状态，增加一个 记忆表，用于保存成熟的记忆细胞，改进了高斯变异方式，以保证多样化的有效搜索.通过对多个典型系统仿真分析该方 法的收敛性，并与克隆选择算法和aNt算法进行比较分析.结果表明，该算法在多模态搜索空间中具有更好的全局收敛 性、稳定性和寻找极值点能力，能够克服早熟现象，是一种有效的全局优化搜索方法. 关键词：人工免疫系统；人工免疫网络算法；禁忌搜索算法；优化 中图分类号：1P18文献标识码：A文章编号：1673-4785(2008)050393-08 Applica tion of a Tabu mmune network algorithm n function optin ia tions ZHAO Yun-feng,YN Yi-xin',FU Dongmei,WANG Jia (1.School of Ifomation Engineering,University of Science and Technology Beijing,Beijing 100083,China;2 Institute of Economy and Infomation,China Coal Research Institute,Beijing 100013,China) Abstract:A Tabu search artificial mmune algorithm (TS-aNet)was developed based on the aNet and Tabu search algorithms It introduces a taboo list of cells whose affinities are to no longer increase in netork iterations, and releases some excellent tabooed cells in line with amnesty criteria A memory table is added to store mature memory cells Moreover,exp ressions of Gaussian mutation for a diversity search in the process of global op tm iza- tion were mp oved Convergence analysis was perfomed with some typical systems and comparison was made with KLONALG and aNet algorithms The smulation results showed that the app roach presented has better global con- vergent ability and stability in multimodal search space,and can avoid prematurity effectively So it is a glbal op- tm ization algorithm with good feasibility and high efficiency Keywords:artificial mmune system;artificial immune ne tork algorithm;Tabu search algorithm;optm ization 人工免疫系统是一个动态进化系统，具有自然 抑制对应于优化解的促进和非优化解的删除.文献 寻优的特性，其算法和模型在调度山、计算智能2)、 [5结合遗传算法的免疫优化，较好地实现了函数 故障诊断)、优化学习、模式识别等领域中取得 优化问题；文献[6在遗传禁忌算法基础上，采用免 了很好的效果，免疫算法所具备的特性、强大而丰富 疫禁忌混合智能算法来求解配电网检修计划的优化 的信息处理能力，决定了其对优化问题的求解有着 模型，属于组合优化问题，虽然有遗传算法的影子， 巨大的潜力.从人工免疫观点看，函数优化问题等同但在解决电网检修规划问题中取得了较好的实用价 于抗体群体进化识别抗原.抗原对应求解的问题，抗值，文献[7利用免疫禁忌优化算法对流域生态环 体对应问题的解，优化问题的最优解亲和度对应解 境质量评价指数公式的参数进行优化，在生态环境 的评估.记忆细胞对应于保留的优化解，抗体促进和 评价中获得了较好的效果，其核心是禁忌搜索算法 的应用.正是由于某些算法和模型的研究还处于起 收稿日期：2008-07-12 基金项目：国家自然科学基金资助项目(60573016)；北京市教委重 步阶段，存在一些不足，如缺乏统一的免疫算法范 点学科共建资助项目(XK100080537). 通信作者：赵云丰.Emaik yunf zhao(@yahoo com cn 式、仿生机理借鉴不够深入、算法的收敛性和稳定性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 禁忌免疫网络算法及其在函数优化中的应用 赵云丰 1 , 尹怡欣 1 , 付冬梅 1 , 王 嘉 2 (1. 北京科技大学 信息工程学院 ,北京 100083; 2. 煤炭科学研究总院 经济与信息研究所 ,北京 100013) 摘 要 :基于人工免疫网络算法 ( aiNet) ,借鉴禁忌搜索算法的机制 ,提出一种禁忌人工免疫网络算法 ( TS2aiNet). 在算法 中引入禁忌表 ,禁忌那些在网络迭代中亲和度不再增加的细胞 ,并通过特赦准则赦免一些被禁忌的优良状态 ,增加一个 记忆表 ,用于保存成熟的记忆细胞 ,改进了高斯变异方式 ,以保证多样化的有效搜索. 通过对多个典型系统仿真分析该方 法的收敛性 ,并与克隆选择算法和 aiNet算法进行比较分析. 结果表明 ,该算法在多模态搜索空间中具有更好的全局收敛 性、稳定性和寻找极值点能力 ,能够克服早熟现象 ,是一种有效的全局优化搜索方法. 关键词 :人工免疫系统 ;人工免疫网络算法 ;禁忌搜索算法 ;优化 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0520393208 Application of a Tabu immune network algorithm in function optim izations ZHAO Yun2feng 1 , YIN Yi2xin 1 , FU Dong2mei 1 , WANG Jia 2 (1. School of Information Engineering, University of Science and TechnologyBeijing, Beijing 100083, China; 2. Institute of Economy and Information, China Coal Research Institute, Beijing 100013, China) Abstract:A Tabu search artificial immune algorithm ( TS2aiNet) was developed based on the aiNet and Tabu search algorithm s. It introduces a taboo list of cells whose affinities are to no longer increase in network iterations, and releases some excellent tabooed cells in line with amnesty criteria. A memory table is added to store mature memory cells. Moreover, exp ressions of Gaussian mutation for a diversity search in the p rocess of global op tim iza2 tion were imp roved. Convergence analysis was performed with some typ ical system s and comparison wasmade with KLONALG and aiNet algorithm s. The simulation results showed that the app roach p resented has better global con2 vergent ability and stability in multi2modal search space, and can avoid p rematurity effectively. So it is a global op2 tim ization algorithm with good feasibility and high efficiency. Keywords: artificial immune system; artificial immune network algorithm; Tabu search algorithm; op tim ization 收稿日期 : 2008207212. 基金项目 :国家自然科学基金资助项目 ( 60573016) ; 北京市教委重 点学科共建资助项目 (XK100080537). 通信作者 :赵云丰. E2mail: yunf_zhao@yahoo. com. cn. 人工免疫系统是一个动态进化系统 ,具有自然 寻优的特性 ,其算法和模型在调度 [ 1 ]、计算智能 [ 2 ]、 故障诊断 [ 3 ]、优化学习、模式识别 [ 4 ]等领域中取得 了很好的效果 ,免疫算法所具备的特性、强大而丰富 的信息处理能力 ,决定了其对优化问题的求解有着 巨大的潜力. 从人工免疫观点看 ,函数优化问题等同 于抗体群体进化识别抗原. 抗原对应求解的问题 ,抗 体对应问题的解 ,优化问题的最优解亲和度对应解 的评估. 记忆细胞对应于保留的优化解 ,抗体促进和 抑制对应于优化解的促进和非优化解的删除. 文献 [ 5 ]结合遗传算法的免疫优化 ,较好地实现了函数 优化问题 ;文献 [ 6 ]在遗传禁忌算法基础上 ,采用免 疫禁忌混合智能算法来求解配电网检修计划的优化 模型 ,属于组合优化问题 ,虽然有遗传算法的影子 , 但在解决电网检修规划问题中取得了较好的实用价 值 ;文献 [ 7 ]利用免疫禁忌优化算法对流域生态环 境质量评价指数公式的参数进行优化 ,在生态环境 评价中获得了较好的效果 ,其核心是禁忌搜索算法 的应用. 正是由于某些算法和模型的研究还处于起 步阶段 ,存在一些不足 ,如缺乏统一的免疫算法范 式、仿生机理借鉴不够深入、算法的收敛性和稳定性
·394· 智能系统学报 第3卷 有待进一步分析以及算法的执行效率有待提高等， 步寻优、高效启发式优化理论.已被应用于调度、工 从而为进一步的研究留下了很大的拓展空间 作流程排序、旅行商和路由选择等问题1，近年来 1人工免疫算法与禁忌搜索算法 在函数优化方面得到较大的发展，其中邻域函数、禁 忌表、候选解、特赦准则等概念构成了禁忌搜索的关 11人工免疫网络算法 键 人工免疫网络算法I)(artihicial mmune met 设有组合优化问题，TS算法解决优化问题的一 wok,aNe)是在人工免疫系统基础上发展起来的 般步骤为 一种智能算法，主要基于克隆选择、高频变异及免疫 m in C(x) 网络等免疫学原理实现.与Jeme和Famer的网络 (1) x∈X 一样，aNet模型忽略B细胞和抗体的区别，它是由 式中：X是x的约束空间，C(x)是目标函数，其算法 一些以一定连接强度联系起来的抗体群组成的网 流程如下： 络.网络中的抗体代表了抗原的内影像，抗体之间的 1)给定算法参数，随机产生初始解x,置禁忌表 连接表明了它们之间的相似程度.aNet将待分析的 H=Φ 数据看作抗原，将算法产生反映抗原特征的数据看 2 While循环条件) 作抗体，模拟免疫网络抗体抗原之间的相互刺激和 ①利用当前解x的邻域函数产生x的邻域 作用，按照一定的算法实现数据处理.aNet最初用 N(H,x),从中选出候选解CanN(x; 来解决数据聚类问题，Castro将聚类问题视为一 ②判断候选解CanN(x")是否满足藐视准 种多峰优化问题，提出了一种面向多峰值函数优化 则，若满足，最佳状态Y替代CanN(x")成为新的 的人工免疫网络，形成opt-aNet算法.该算法能有 效提取目标函数的绝大部分局部峰值，并具备群体 当前解，即Can_N(x)=Y并用与Y对应的禁忌 数量自动调节和实数编码等优良特性，具有强大的 对象替换最早进入禁忌表的禁忌对象，同时用Y替 计算和数据处理能力 换“best so far"状态，即xe=上否则，继续： 由于自然进化和生命现象的测不准性，进化 ③判断候选解CanN(x“)对应的各对象的禁 类算法不可避免地存在概率算法的缺陷，即未成熟 忌属性，选择候选解中非禁忌对象对应的最佳状态 收敛、种群多样性减少等退化现象.因而aNet在 为新的当前解，即x=x,用与之对应的禁忌对 处理多模态、多峰值、非凸函数优化问题时，仍存在 象替换最早进入禁忌表的对象 着如下困难：1)出现早熟现象，即在目标函数极值 3)输出结果，停止计算 点过多和过于密集的情况下，有可能使算法过早收 由于T$算法具有灵活的记忆功能和特敖准则， 敛而搜索不到全部的极值点.其细胞的克隆扩增基 在搜索过程中可以接受劣解，具有较强的爬山能力， 于高斯变异，这种变异方式往往使细胞的克隆体与 搜索时能够跳出局部最优解，转向解空间的其他区 上一代细胞克隆体有一定的冗余，搜索局部极值时， 域，从而增加获得更好全局解的概率，因而它是一种 收敛速度较慢，不能有效的找到多峰函数所有的局 局部搜索能力很强的全局迭代寻优算法，可以很好 部极值点，容易导致早熟现象.2)迂回搜索，aNet地改善aNet算法早熟的问题.其不足是，迭代搜索 算法在增加随机生成细胞时，未考虑当前网络存在 过程是串行的，仅是单一状态的移动，非并行搜索 的细胞，盲目的增加随机生成的细胞，没有指导的迭 从而制约了收敛速度.而aNet算法的种群操作，保 代搜索，往往导致迂回搜索，不但增加了计算量，而 留了算法多出发点的优势，弥补了禁忌搜索缺乏并 且使算法过早收敛而搜索不到全部的极值点 行性的弱点，因而二者具有很好的结合空间. 所以，为了克服aNet算法的不足，借鉴禁忌搜 2禁忌人工免疫网络算法 索算法的思想来进行改进 12禁忌搜索算法 21改进策略 禁忌搜索算法(Tabu search.,TS)是一种全局逐 结合aNet算法和TS算法各自的特点，提出了 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
有待进一步分析以及算法的执行效率有待提高等 , 从而为进一步的研究留下了很大的拓展空间. 1 人工免疫算法与禁忌搜索算法 1. 1 人工免疫网络算法 人工免疫网络算法 [ 8 ] ( artihicial immune met2 work, aiNet)是在人工免疫系统基础上发展起来的 一种智能算法 ,主要基于克隆选择、高频变异及免疫 网络等免疫学原理实现. 与 Jerne和 Farmer的网络 一样 , aiNet模型忽略 B 细胞和抗体的区别 ,它是由 一些以一定连接强度联系起来的抗体群组成的网 络. 网络中的抗体代表了抗原的内影像 ,抗体之间的 连接表明了它们之间的相似程度. aiNet将待分析的 数据看作抗原 ,将算法产生反映抗原特征的数据看 作抗体 ,模拟免疫网络抗体抗原之间的相互刺激和 作用 ,按照一定的算法实现数据处理. aiNet最初用 来解决数据聚类问题 , Castro [ 9 ]将聚类问题视为一 种多峰优化问题 ,提出了一种面向多峰值函数优化 的人工免疫网络 ,形成 op t2aiNet算法. 该算法能有 效提取目标函数的绝大部分局部峰值 ,并具备群体 数量自动调节和实数编码等优良特性 ,具有强大的 计算和数据处理能力. 由于自然进化和生命现象的“测不准 ”性 ,进化 类算法不可避免地存在概率算法的缺陷 ,即未成熟 收敛、种群多样性减少等“退化 ”现象. 因而 aiNet在 处理多模态、多峰值、非凸函数优化问题时 ,仍存在 着如下困难 : 1) 出现早熟现象 ,即在目标函数极值 点过多和过于密集的情况下 ,有可能使算法过早收 敛而搜索不到全部的极值点. 其细胞的克隆扩增基 于高斯变异 ,这种变异方式往往使细胞的克隆体与 上一代细胞克隆体有一定的冗余 ,搜索局部极值时 , 收敛速度较慢 ,不能有效的找到多峰函数所有的局 部极值点 ,容易导致早熟现象. 2) 迂回搜索 , aiNet 算法在增加随机生成细胞时 ,未考虑当前网络存在 的细胞 ,盲目的增加随机生成的细胞 ,没有指导的迭 代搜索 ,往往导致迂回搜索 ,不但增加了计算量 ,而 且使算法过早收敛而搜索不到全部的极值点. 所以 ,为了克服 aiNet算法的不足 ,借鉴禁忌搜 索算法的思想来进行改进. 1. 2 禁忌搜索算法 禁忌搜索算法 ( Tabu search, TS)是一种全局逐 步寻优、高效启发式优化理论. 已被应用于调度、工 作流程排序、旅行商和路由选择等问题 [ 10 ] ,近年来 在函数优化方面得到较大的发展 ,其中邻域函数、禁 忌表、候选解、特赦准则等概念构成了禁忌搜索的关 键. 设有组合优化问题 , TS算法解决优化问题的一 般步骤为 m in C ( x) , s. t. x ∈ X. (1) 式中 : X是 x的约束空间 , C ( x)是目标函数 ,其算法 流程如下 : 1)给定算法参数 ,随机产生初始解 x,置禁忌表 H =Φ; 2)W hile (循环条件 ) ①利用当前解 x now的邻域函数产生 x now的邻域 N (H, x now ) ,从中选出候选解 Can_N ( x now ) ; ②判断候选解 Can_N ( x now )是否满足藐视准 则 ,若满足 ,最佳状态 Y替代 Can_N ( x now )成为新的 当前解 ,即 Can_N ( x now ) = Y,并用与 Y对应的禁忌 对象替换最早进入禁忌表的禁忌对象 ,同时用 Y替 换“best so far”状态 ,即 x best = Y;否则 ,继续; ③判断候选解 Can_N ( x now )对应的各对象的禁 忌属性 ,选择候选解中非禁忌对象对应的最佳状态 为新的当前解 ,即 x now = x best ,用与之对应的禁忌对 象替换最早进入禁忌表的对象. 3)输出结果 ,停止计算. 由于 TS算法具有灵活的记忆功能和特赦准则 , 在搜索过程中可以接受劣解 ,具有较强的爬山能力 , 搜索时能够跳出局部最优解 ,转向解空间的其他区 域 ,从而增加获得更好全局解的概率 ,因而它是一种 局部搜索能力很强的全局迭代寻优算法 ,可以很好 地改善 aiNet算法早熟的问题. 其不足是 ,迭代搜索 过程是串行的 ,仅是单一状态的移动 ,非并行搜索 , 从而制约了收敛速度. 而 aiNet算法的种群操作 ,保 留了算法多出发点的优势 ,弥补了禁忌搜索缺乏并 行性的弱点 ,因而二者具有很好的结合空间. 2 禁忌人工免疫网络算法 2. 1 改进策略 结合 aiNet算法和 TS算法各自的特点 ,提出了 ·394· 智 能 系 统 学 报 第 3卷
第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·
·396· 智能系统学报 第3卷 中细胞变异时，细胞进化的方向.为加快寻求最优解 ⑤在每个网络细胞的克隆体C`和父代细胞中 的速度和精度，采用合理的进化方向显然很必要.进 选择亲和力最高的细胞组成新的网络C; 化方向表是一种串行结构的表，采用具有指示进化 ⑥判断C,中的每个细胞的亲和力是否增加并 方向作用的方向算子，依据父代、当代及子代个体在 计算细胞下一次的进化方向，将计算结果存入进化 结构中的位置的产生子代个体的进化方向，沿着亲 方向表： 和度上升的方向为目标进化方向.当网络中的细胞 ⑦判断网络中是否存在细胞的亲和力大小变化 是新生成时，细胞的方向初始值为Q.禁忌人工免疫 的次数己达到阈值σ，如果没有，返回到步骤①活 网络算法的流程见图1 则，继续： 随机生成初始网络C ⑧将已达到阈值o,的细胞加入禁忌表C,如 果网络中亲和力最高的细胞也达到了，该细胞被特 计算网络细胞的亲和度/ 赦，不加入禁忌表： ⑨将禁忌表C,中禁忌次数达到特赦阈值·。 克隆网络细胞N 的细胞移到记忆表Cw中， 细胞变异，并计算细胞的求和度 ⑩计算C,和CM中所有细胞的亲和力，抑制亲 和力小于抑制阈值·，的个体： 网络中总否有在 ①入一定数目细胞不在禁忌表中细胞形成 需禁忌的细？ 的邻域中)到网络中，使网络大小不变 将禁忌细胞加入禁忌表C, 3)输出C,和C中所有细胞和网络中最大亲 和力细胞， 将禁忌表中特放细胞转到记忆表CM 算法的迭代停止条件是禁忌表和记忆表中细胞 对禁忌表和记忆表进行抑制 的总数或者是达到最大迭代次数.在步骤①中，让禁 忌表和记忆表中的细胞互相作用，通过阴性选择对 满足停止条件？ 引入 新生成 亲和力小于抑制阈值的个体进行抑制，剩下的个体 Y 的到胞 则保留起来.经过抑制后，若禁忌表和记忆表中的细 输出结果 胞总数比上一代的总数多，表示找到新的极值点.假 如经过几次抑制过程，禁忌表和记忆表中的细胞总 图1禁忌人工免疫网路算法流程图 数不发生变化，表明找不到新的极值点，停止搜索， Fig I Flowchart of TS-aNet algprithm 则禁忌表和记忆表中剩下的细胞和网络中最大亲和 222TS-aNet算法的实现 力细胞就是问题的解口 TS-aNet算法实现的步骤如下所示 1)随机生成N个网络细胞，计算所有网络细胞 3仿真实验及分析 的亲和力￡形成初始网络Gw: 为了验证算法的性能，从局部收敛速度全局收 2 While满足迭代条件) 敛性、搜索极值点的能力3个方面进行定量分 ①将所有网络细胞的亲和力标准化： 析1 ②将网络细胞产生数目为N的克隆形成C,N。 31局部收敛速度分析 的大小与该细胞的亲和力成正比，计算公式为N。= 局部收敛速度指的是在搜索局部极值点时，找 round (f )+1: 到局部极值点的速度.采用以下2个函数进行优化 ③对产生的克隆C进行变异，如果变异后的个 并与CLONALG算法、opt-aNet来做比较 体不在可行域内，则不予保留； f(x,以=-sqt(x+y) 5) ④计算变异后形成的C`中的细胞亲和力； 人(x以=-(100(x.以2+(1.x2). 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
中细胞变异时 ,细胞进化的方向. 为加快寻求最优解 的速度和精度 ,采用合理的进化方向显然很必要. 进 化方向表是一种串行结构的表 ,采用具有指示进化 方向作用的方向算子 ,依据父代、当代及子代个体在 结构中的位置的产生子代个体的进化方向 ,沿着亲 和度上升的方向为目标进化方向. 当网络中的细胞 是新生成时 ,细胞的方向初始值为 0. 禁忌人工免疫 网络算法的流程见图 1. 图 1禁忌人工免疫网路算法流程图 Fig. 1 Flowchart of TS2aiNet algorithm 2. 2. 2 TS2aiNet算法的实现 TS2aiNet算法实现的步骤如下所示. 1)随机生成 N 个网络细胞 , 计算所有网络细胞 的亲和力 f, 形成初始网络 CN ; 2)W hile (满足迭代条件 ) ①将所有网络细胞的亲和力 f标准化; ②将网络细胞产生数目为 Nc 的克隆形成 C, Nc 的大小与该细胞的亲和力成正比 , 计算公式为 Nc = round ( f 3 i ×Nm ) + 1; ③对产生的克隆 C进行变异 , 如果变异后的个 体不在可行域内 , 则不予保留; ④计算变异后形成的 C 3 中的细胞亲和力; ⑤在每个网络细胞的克隆体 C 3 和父代细胞中 选择亲和力最高的细胞组成新的网络 CN ; ⑥判断 CN 中的每个细胞的亲和力是否增加并 计算细胞下一次的进化方向 ,将计算结果存入进化 方向表; ⑦判断网络中是否存在细胞的亲和力大小变化 的次数已达到阈值 σt ,如果没有 , 返回到步骤 ①否 则 , 继续; ⑧将已达到阈值 σt 的细胞加入禁忌表 CT , 如 果网络中亲和力最高的细胞也达到了 , 该细胞被特 赦 , 不加入禁忌表; ⑨将禁忌表 CT 中禁忌次数达到特赦阈值 σα 的细胞移到记忆表 CM 中; ⑩计算 CT 和 CM 中所有细胞的亲和力 , 抑制亲 和力小于抑制阈值 σs 的个体; λϖ引入一定数目细胞 (不在禁忌表中细胞形成 的邻域中 )到网络中 , 使网络大小不变. 3)输出 CT 和 CM 中所有细胞和网络中最大亲 和力细胞. 算法的迭代停止条件是禁忌表和记忆表中细胞 的总数或者是达到最大迭代次数. 在步骤 λυ中 ,让禁 忌表和记忆表中的细胞互相作用 ,通过阴性选择对 亲和力小于抑制阈值的个体进行抑制 ,剩下的个体 则保留起来. 经过抑制后 ,若禁忌表和记忆表中的细 胞总数比上一代的总数多 ,表示找到新的极值点. 假 如经过几次抑制过程 ,禁忌表和记忆表中的细胞总 数不发生变化 ,表明找不到新的极值点 ,停止搜索 , 则禁忌表和记忆表中剩下的细胞和网络中最大亲和 力细胞就是问题的解 [ 11 ] . 3 仿真实验及分析 为了验证算法的性能 ,从局部收敛速度、全局收 敛性、搜索极值点的能力 3 个方面进行定量分 析 [ 12 ] . 3. 1 局部收敛速度分析 局部收敛速度指的是在搜索局部极值点时 ,找 到局部极值点的速度. 采用以下 2个函数进行优化 , 并与 CLONALG算法、op t2aiNet来做比较. f1 ( x, y) = - sqrt( x 2 + y 2 ) , f2 ( x, y) = - (100 ( x 2 - y) 2 + (1 - x) 2 ) 1 (5) ·396· 智 能 系 统 学 报 第 3卷
第5期 赵云丰，等：禁忌免疫网络算法及其在函数优化中的应用 ·397 式中：是欧氏距离函数，极值点在原点；虽然是 点时不太稳定，有时可能会找不到局部极值点。 单峰值函数，只有一个极大值点1,1)，该点的函数 值为0，但该极大值点位于十分狭窄的脊谷中，函数 3 值此区域内取值变化极为缓慢，很难进行全局最大 0 化.对于无与￡2个函数，3个算法运算结果如图2 和图3 ----TS-aiNet -6 opt-aiNet ---·TS-aiNet -10 …CLONALG 8 opt-aiNet o…CLONALG 20 40 60 80 100 10 迭代次数 10 -5 0 5 (a)函数f最大亲和力 (a)函数f收敛过程 TS-aiNet 10 opt-aiNet …CLONALG 2 -15 0 20 40 60 80100 8 迭代次数 )函数f,最大亲和力 -6 TS-aiNet 图2最大亲和力变化过程图 -opt-aiNet -10 o…CLONALG Fig 2 Varying process of the max affinity -12 图2是3个算法对3个函数最大亲和力变化过 -10 -5 0 5 程，(a)、(b)分别是和变化过程.对函数无，从 函数∫，收敛过程 3个算法最大亲和力变化过程看出，TS-aNet算法迭 代11次就找到了极值点，CLONALG算法经过20次 图3函数收敛过程路径平面显示 迭代，而opt-aNet算法经过36次迭代；对于函数五， Fig 3 Convergent route of functions in plane TS-aNet算法迭代9次就找到了极值点(1,1)， 3.2收敛性比较分析 CLONALG算法经过100次迭代只收敛到原点(0， 为了验证算法在不同情况下的收敛性，选择一 0),没有找到(1,1)，而opt-aNet算法经过29次迭 些具有不同类型的测试函数 代找到了极值点(1,1).所以TS-aNet算法搜索局 1)阶梯函数的优化.阶梯函数是一种不连续函 部极值点时局部收敛速度要比其他2种算法快 数，其不连续性质往往使一些算法收敛困难.其表达 图3是对2个函数收敛过程路径的平面显示， 式如下 (a)、(b)分别对应f和收敛过程 5(x)=6n+ 之ntfk, 从3个算法对和方函数迭代收敛过程最大 亲和力点坐标的位置图中可以看出，TS-aNet前进 0≤x,≤10.1 6) 的距离是变化的，不是等距，而opt-aNeti前进的距 式中：x=,,xn,n为变量维数，有(x)取 离是接近等距离，因为在TS-aNet算法进行克隆变 最大值48对于阶梯函数，3种算法的最终收敛结果 异过程中，利用了进化方向.同时，可以发现 见表1比较可知，TS-aNet算法收敛速度更快，局部 CLONALG.算法前进的距离和方向是不规则的，因 搜索能力更强，在第26代就得到最优解；CLONALG 为CLONALG算法采用二进制编码，进行高频变异 算法需要42代，opt-aNet算法过早收敛，没有找到 时，变异的编码位置是随机的，所以在搜索局部极值 全局最优解 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
式中 : f1 是欧氏距离函数 ,极值点在原点; f2 虽然是 单峰值函数 ,只有一个极大值点 (1, 1) ,该点的函数 值为 0,但该极大值点位于十分狭窄的脊谷中 ,函数 值此区域内取值变化极为缓慢 ,很难进行全局最大 化. 对于 f1 与 f2 2个函数 , 3个算法运算结果如图 2 和图 3. 图 2最大亲和力变化过程图 Fig. 2 Varying p rocess of the max affinity 图 2是 3个算法对 3个函数最大亲和力变化过 程 , ( a)、( b)分别是 f1 和 f2 变化过程. 对函数 f1 ,从 3个算法最大亲和力变化过程看出 , TS2aiNet算法迭 代 11次就找到了极值点 , CLONALG算法经过 20次 迭代 ,而 op t2aiNet算法经过 36次迭代 ;对于函数 f2 , TS2aiNet算法迭代 9 次就找到了极值点 ( 1, 1 ) , CLONALG算法经过 100次迭代只收敛到原点 ( 0, 0) ,没有找到 (1, 1) ,而 op t2aiNet算法经过 29次迭 代找到了极值点 (1, 1). 所以 TS2aiNet算法搜索局 部极值点时局部收敛速度要比其他 2种算法快. 图 3是对 2个函数收敛过程路径的平面显示 , ( a)、( b) 分别对应 f1 和 f2 收敛过程. 从 3个算法对 f1 和 f2 函数迭代收敛过程最大 亲和力点坐标的位置图中可以看出 , TS2aiNet前进 的距离是变化的 ,不是等距 ,而 op t2aiNet前进的距 离是接近等距离 ,因为在 TS2aiNet算法进行克隆变 异过 程 中 , 利 用 了 进 化 方 向. 同 时 , 可 以 发 现 CLONALG算法前进的距离和方向是不规则的 ,因 为 CLONALG算法采用二进制编码 ,进行高频变异 时 ,变异的编码位置是随机的 ,所以在搜索局部极值 点时不太稳定 ,有时可能会找不到局部极值点. 图 3函数收敛过程路径平面显示 Fig. 3 Convergent route of functions in p lane 3. 2 收敛性比较分析 为了验证算法在不同情况下的收敛性 ,选择一 些具有不同类型的测试函数. 1)阶梯函数的优化. 阶梯函数是一种不连续函 数 ,其不连续性质往往使一些算法收敛困难. 其表达 式如下 : f3 ( x) = 6n + 6 n i =1 int( xi ) , 0 ≤ xi ≤ 1011. (6) 式中 : x = [ x1 , x2 , …, xn ], n为变量维数 , f3 ( x)取 最大值 48. 对于阶梯函数 , 3种算法的最终收敛结果 见表 1. 比较可知 , TS2aiNet算法收敛速度更快 ,局部 搜索能力更强 ,在第 26代就得到最优解 ; CLONALG 算法需要 42代 ; op t2aiNet算法过早收敛 ,没有找到 全局最优解. 第 5期 赵云丰 ,等 :禁忌免疫网络算法及其在函数优化中的应用 ·397·