第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·
·398· 智能系统学报 第3卷 50,0)=1,而其局部极大点为无穷多个.全局最 表13种算法对阶梯函数的收敛结果 优点周围有一个圈脊，因此算法很容易停滞在此局 Table 1 Convergent results of three a lgorithms for 部最优点.此函数形状相对于原点对称，且越接近原 step function 点最优点)，函数值变化越剧烈，在最优点附近形 3种算法对阶梯函数的收敛结果 最早发 成间隔很密、很陡的振荡峰.Schaffer函数能很好地 算法 迭代现最优 最优值 2 测试算法跳出局部极值点寻找全局最优点的能力. 次数值代数 对于Schaff能r函数，3种算法的收敛结果见表3.由 CLONALG 48 100168100032100599200 42 结果可知opt-aNet算法陷入了局部极值点，没有找 opt-aNet 47 9.42591004611003739111 TS-aNet4810041310011910069120026 到全局最优点(0.0001,0.0004)，TS-aNet算法在 第59代时发现了最大极值点，比其他2种算法找到 2)Rosenbrock函数的优化.Rosenbrock函数是 的最大极值点精确，且迭代次数最少 一种非凸、病态函数，常常用作优化算法的测试问 表33种算法对Schaffer函数的收敛结果 题.表达式如下： Table 3 Convergent results of three a lgor ithm s for (x)= ∑(100飞1-2+1-x2) Scha ffer 最早发 -30≤x,≤30 7) 收敛结果 迭代 算法 现最优 该函数在x,=1时达到极小值点，其解空间有 最优值 次数 值代数 非常多的狭窄的通道，导致很难获得全局最优值.为 CLONALG 0 958 0 00011 00004200 73 了使算法对Rosenbrock函数收敛，CLONALG算法 opt-aNet08199-00310-00033200 166 需要将迭代次数增加到4000代，比较表2的收敛 TS-aNet09636000010000420059 结果可以看出，在病态的Rosenbrock函数优化中， 以上测试结果表明，TS-aNet算法对具有不同 经过4000代的进化，CLONAL G算法能够收敛到 特点的优化问题具有良好的收敛能力，与其对照的 005934,opt-aNet算法无法收敛到最优解，而TS- 2种算法相比，受函数不连续、非凸性和病态等因素 aNet算法只经过了120代就收敛到最优解00424 的影响较小，具有良好的全局最优解搜索能力 所以TS-aNet算法明显优于另外2种算法」 3.3搜索极值点能力分析 表23种算法对Rosen brock函数的收敛结果 通常利用一些经典多峰函数测试算法搜索极值 Table 2 Convergent results of three a lgor ithm s for 点的能力，根据搜索的结果种群的分布情况评价算 Rosen brock 法性能.在此采用峰值比、搜索到的极值点的个数、 收敛结果 最早发 亲和度函数的计算次数等指标进行定量评价 算法 迭代现最优 最优值 次数值代数 8025-x),0≤x<25, a0NALG0059308235074510588240003989 64x-25),25≤x<50, opt-aNet-320890.2039-001970.045640004000 6475-x),50≤x<75, 1S-aNet004240.9804098040.9804120 115 28(x-75),75≤x<125. (9》 3)Schafferi函数的优化.Schaffer函数是一种只 28(175-x),125≤x<175, 有一个全局最优点，且在全局最优点附近存在无穷 32(x-175),175≤x<225, 个局部极值点将其包围的函数，其表达式如下： 32275-x),225≤x<275 5(x以=1-(+y2)25. 80(x-275),275≤x<30 sim250(x2+2)a1+1.0)1 (8 该函数在区间[0,30有5个非均匀分布的峰 该函数在可行域内只有一个全局极大值点 且2个等高的极值点在边界上，距离很远，搜索一旦 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
表 1 3种算法对阶梯函数的收敛结果 Table 1 Convergen t results of three a lgor ithm s for step function 算法 3种算法对阶梯函数的收敛结果 最优值 x1 x2 x3 迭代 次数 最早发 现最优 值代数 CLONALG 48 10. 016 8 10. 003 2 10. 059 9 200 42 op t2aiNet 47 9. 425 9 10. 046 1 10. 037 3 91 11 TS2aiNet 48 10. 041 3 10. 011 9 10. 069 1 200 26 2) Rosenbrock函数的优化. Rosenbrock函数是 一种非凸、病态函数 ,常常用作优化算法的测试问 题. 表达式如下 : f4 ( x) = 6 n i =1 (100 ( xi+1 - x 2 i ) 2 + (1 - xi ) 2 ) , - 30 ≤ xi ≤ 30. (7) 该函数在 xi = 1时达到极小值点 ,其解空间有 非常多的狭窄的通道 ,导致很难获得全局最优值. 为 了使算法对 Rosenbrock函数收敛 , CLONALG算法 需要将迭代次数增加到 4 000代 ,比较表 2的收敛 结果可以看出 ,在病态的 Rosenbrock函数优化中 , 经过 4 000代的进化 , CLONALG算法能够收敛到 0. 059 34, op t2aiNet算法无法收敛到最优解 ,而 TS2 aiNet算法只经过了 120代就收敛到最优解 0. 042 4. 所以 TS2aiNet算法明显优于另外 2种算法. 表 2 3种算法对 Rosenbrock函数的收敛结果 Table 2 Convergen t results of three a lgor ithm s for Rosenbrock 算法 收敛结果 最优值 x1 x2 x3 迭代 次数 最早发 现最优 值代数 CLONALG 0. 059 3 0. 823 5 0. 745 1 0. 588 2 4 000 3 989 op t2aiNet - 32. 089 0. 203 9 - 0. 019 7 0. 045 6 4 000 4 000 TS2aiNet 0. 042 4 0. 980 4 0. 980 4 0. 980 4 120 115 3) Schaffer函数的优化. Schaffer函数是一种只 有一个全局最优点 ,且在全局最优点附近存在无穷 个局部极值点将其包围的函数 ,其表达式如下 : f5 ( x, y) = 1 - ( x 2 + y 2 ) 0125 · õsin 2 (50 ( ( x 2 + y 2 ) 011 ) + 110) 」. (8) 该函数在可行域内只有一个全局极大值点 f5 (0, 0) = 1,而其局部极大点为无穷多个. 全局最 优点周围有一个圈脊 ,因此算法很容易停滞在此局 部最优点. 此函数形状相对于原点对称 ,且越接近原 点 (最优点 ) ,函数值变化越剧烈 ,在最优点附近形 成间隔很密、很陡的振荡峰. Schaffer函数能很好地 测试算法跳出局部极值点寻找全局最优点的能力. 对于 Schaffer函数 , 3种算法的收敛结果见表 3. 由 结果可知 op t2aiNet算法陷入了局部极值点 ,没有找 到全局最优点 (0. 000 1, 0. 000 4) , TS2aiNet算法在 第 59代时发现了最大极值点 ,比其他 2种算法找到 的最大极值点精确 ,且迭代次数最少. 表 3 3种算法对 Schaffer函数的收敛结果 Table 3 Convergen t results of three a lgor ithm s for Schaffer 算法 收敛结果 最优值 x1 x2 迭代 次数 最早发 现最优 值代数 CLONALG 0. 958 0 0. 001 1 0. 000 4 200 73 op t2aiNet 0. 819 9 - 0. 031 0 - 0. 003 3 200 166 TS2aiNet 0. 963 6 0. 000 1 0. 000 4 200 59 以上测试结果表明 , TS2aiNet算法对具有不同 特点的优化问题具有良好的收敛能力 ,与其对照的 2种算法相比 ,受函数不连续、非凸性和病态等因素 的影响较小 ,具有良好的全局最优解搜索能力. 3. 3 搜索极值点能力分析 通常利用一些经典多峰函数测试算法搜索极值 点的能力 ,根据搜索的结果种群的分布情况评价算 法性能. 在此采用峰值比、搜索到的极值点的个数、 亲和度函数的计算次数等指标进行定量评价. f6 ( x) = 80 (2. 5 - x) , 0≤x < 2. 5, 64 ( x - 2. 5) , 2. 5≤x < 5. 0, 64 (7. 5 - x) , 5. 0≤x < 7. 5, 28 ( x - 7. 5) , 7. 5≤x < 12. 5, 28 (17. 5 - x) , 12. 5≤x < 17. 5, 32 ( x - 17. 5) , 17. 5≤x < 22. 5, 32 (27. 5 - x) , 22. 5≤x < 27. 5, 80 ( x - 27. 5) , 27. 5≤x < 30. (9) 该函数在区间 [0, 30 ]有 5个非均匀分布的峰 , 且 2个等高的极值点在边界上 ,距离很远 ,搜索一旦 ·398· 智 能 系 统 学 报 第 3卷
第5期 赵云丰，等：禁忌免疫网络算法及其在函数优化中的应用 ·399· 陷入局部极大值所在的区域，一般难以转移到全局 六峰驼背函数，该函数共有6个局部极小点，其中 极值点所在的区域， (-00898.07126)和100898.-07126)为全 6(x,以=(4-21x+x3)x2+ 局最小点 xy+(.4+4y2) (10) 实验过程中每个算法运算50次，求其平均值， 式中：x∈[-3,3，y∈[-2,21函数被称为 求解结果见表4 表43种算法对函数6和6的收敛结果 Table 4 Convergent results of three algorithms for f andf 3种算法对函数6的收敛结果 亲和度 3种算法对函数万的收敛结果 亲和度 算法 搜索到的 函数的 搜索到的 函数的 搜索代数 峰值比 搜索代数 峰值比 极值点数目 计算次数 极值点数目 计算次数 CLONALG 200 4 07817 62240 200 2 03978 62240 optaNet 42 08192 59159 46 07181 63720 TS-aNet 33 0962515850 32 6 0841318408 峰值比反映算法找到的峰的质量，这一指标越 络算法可以很好地解决这种多模态、多参数的复杂 接近1，表明算法性能越好，由表3可以得知，TS-ar 寻优问题.人工免疫的分布式、并行和记忆性将会有 Net算法的峰值比较其他2个算法更接近于1；TS- 助于图像配准快速处理算法的生成， aNet算法搜索到的极值点个数也较多，反映了其良 算法的不足是对网络抑制阈值的设置还有些敏 好的全局搜索能力；亲和力函数的计算次数衡量算 感，仍然需要先验知识和实验来确定：进化代数也需 法的效率，TS-aNet算法的计算次数较少，表明其计 要人为干预，未能完全体现出免疫系统的自组织机 算复杂度相对较小 理，尚缺乏一定的自主性.如何进一步提高算法的性 由以上实验结果可知，TS-aNet算法以其出色 能及算法在红外与可见光图像配准中的应用，将是 的多样性和记忆功能，在系统稳定性、收敛速度、极 下一步的研究工作 值点搜索能力等方面表现出了更好的性能 参考文献： 4结束语 [1]SW IEC CCKA A,SEREDYNSKI F,ZOMA YA A Y et al 文章提出了禁忌人工免疫网络算法，该方法结 Multiprocessor scheduling and rescheduling with use of cel- 合了人工免疫网络算法与禁忌搜索算法二者的优 lular autmata and artificial mmune system support[J] 点，不仅包括抗体间促进和抑制的动态平衡，而且更 IEEE Transactions on Parallel and Distributed Systems, 好地反映了免疫系统的作用机制.仿真实验表明，与 2006,17(3)253262 其他算法相比，该算法能更好地保持解的多样性，很 [2 ]De CASTRO L N,TMM IS J.Artificial mmune systems as 好地避免了早熟问题，达到了全局寻优和快速收敛 a novel soft computing paradigm [J].Soft Computing Jour 的目的，显示出了更好的性能 nal2003,7(7):67-75. 此外，该算法具备搜索多个最优点的能力，其相 [3 GONZALEZ L,CANNADY J.A self-adaptive negative se- 关结果还适用于图像配准.图像配准是寻找图像之 lection approach for anomaly detection [C]//Proceedings of 间最佳转换参数的优化问题，由于其目标函数可能 the Congress on Evolutionary Computation Portland,USA, 表现为非连续、多峰值和带噪声等各种形式，传统的 2004:20-23 搜索技术求解会遇到许多困难，而禁忌人工免疫网 [4焦李成，杜海峰，刘芳，等.免疫优化计算、学习与识 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
陷入局部极大值所在的区域 ,一般难以转移到全局 极值点所在的区域. f7 ( x, y) = (4 - 2. 1x 2 + x 4 /3) x 2 + xy + ( - 4 + 4y 2 ) y 2 . (10) 式中 : x∈[ - 3, 3 ], y∈[ - 2, 2 ]. 函数 f7 被称为 六峰驼背函数 ,该函数共有 6个局部极小点 ,其中 ( - 0. 089 8, 0. 712 6)和 ( 0. 089 8, - 0. 712 6)为全 局最小点. 实验过程中每个算法运算 50次 ,求其平均值 , 求解结果见表 4. 表 4 3种算法对函数 f6 和 f7 的收敛结果 Table 4 Convergen t results of three a lgor ithm s for f6 and f7 算法 3种算法对函数 f6 的收敛结果 搜索代数 搜索到的 极值点数目 峰值比 亲和度 函数的 计算次数 3种算法对函数 f7 的收敛结果 搜索代数 搜索到的 极值点数目 峰值比 亲和度 函数的 计算次数 CLONALG 200 4 0. 781 7 62 240 200 2 0. 397 8 62 240 op t2aiNet 42 4 0. 819 2 59 159 46 4 0. 718 1 63 720 TS2aiNet 33 5 0. 962 5 15 850 32 6 0. 841 3 18 408 峰值比反映算法找到的峰的质量 ,这一指标越 接近 1,表明算法性能越好 ,由表 3可以得知 , TS2ai2 Net算法的峰值比较其他 2个算法更接近于 1; TS2 aiNet算法搜索到的极值点个数也较多 ,反映了其良 好的全局搜索能力 ;亲和力函数的计算次数衡量算 法的效率 , TS2aiNet算法的计算次数较少 ,表明其计 算复杂度相对较小. 由以上实验结果可知 , TS2aiNet算法以其出色 的多样性和记忆功能 ,在系统稳定性、收敛速度、极 值点搜索能力等方面表现出了更好的性能. 4 结束语 文章提出了禁忌人工免疫网络算法 ,该方法结 合了人工免疫网络算法与禁忌搜索算法二者的优 点 ,不仅包括抗体间促进和抑制的动态平衡 ,而且更 好地反映了免疫系统的作用机制. 仿真实验表明 ,与 其他算法相比 ,该算法能更好地保持解的多样性 ,很 好地避免了早熟问题 ,达到了全局寻优和快速收敛 的目的 ,显示出了更好的性能. 此外 ,该算法具备搜索多个最优点的能力 ,其相 关结果还适用于图像配准. 图像配准是寻找图像之 间最佳转换参数的优化问题 ,由于其目标函数可能 表现为非连续、多峰值和带噪声等各种形式 ,传统的 搜索技术求解会遇到许多困难 ,而禁忌人工免疫网 络算法可以很好地解决这种多模态、多参数的复杂 寻优问题. 人工免疫的分布式、并行和记忆性将会有 助于图像配准快速处理算法的生成. 算法的不足是对网络抑制阈值的设置还有些敏 感 ,仍然需要先验知识和实验来确定 ;进化代数也需 要人为干预 ,未能完全体现出免疫系统的自组织机 理 ,尚缺乏一定的自主性. 如何进一步提高算法的性 能及算法在红外与可见光图像配准中的应用 ,将是 下一步的研究工作. 参考文献 : [ 1 ] SW IECICKA A, SEREDYNSKI F, ZOMAYA A Y. et al. Multip rocessor scheduling and rescheduling with use of cel2 lular automata and artificial immune system support [ J ]. IEEE Transactions on Parallel and D istributed Systems, 2006, 17 (3) : 253 2262. [ 2 ]De CASTRO L N, TIMM IS J. A rtificial immune systems as a novel soft computing paradigm [J ]. Soft Computing Jour2 nal, 2003, 7 (7) : 67275. [ 3 ] GONZALEZ L, CANNADY J. A self2adap tive negative se2 lection app roach for anomaly detection [ C ] / /Proceedings of the Congress on Evolutionary Computation. Portland, USA, 2004: 20223. [ 4 ]焦李成 , 杜海峰 , 刘 芳 ,等. 免疫优化计算、学习与识 第 5期 赵云丰 ,等 :禁忌免疫网络算法及其在函数优化中的应用 ·399·
·400· 智能系统学报 第3卷 别[M]北京：科学出版社，2006：218-235 [10]TAN P H,RASMUSSEN L K Tabu search multi-user de- [5]ZHENGD L,L ANGR X,FU D M,et al Application of tection in CDMAEA C]//Radio Vetenskapoch Kommuni artificial mmune system and artificial mmune genetic alg- kation Stockhom,Sweden,2002:744-748 rithm opti ization [J]Joumal of University of Science [11 ]JU I YW,CHUNG Y K Artificial mmune system or so- and Technology Beijing.2003,3(25):284-287. ving constrained gbbal opti ization problem s[C]//The [6黄弦超，舒隽，张粒子，等，免疫禁忌混合智能优化算 First IEEE Symposium on ArtificialLife Honolulu:Hawaii, 法在配电网检修优化中的应用[J]中国电机工程学报， US4,2007:9299 2004,24(11):96-100 [12 ]SUN R X,QU L S Quantitative evaluation of opti ization HUANG Xianchao,SHU Jun,ZHANGLizi,et al Distribu- efficiency for genetic algorithms[J ]Acta Automatic Sini- tion maintenance scheduling using an intelligent optial ap- ca,2000,26(4):552-556 proach m ixed with mmune algorithm and tabu search[J] 作者简介： Joumal of Chinese Electrical Engineering Science,2004,24 赵云丰，男，1979年生，博士研究 (11):96-100 生，主要研究方向为人工智能、图像处 [7汪嘉杨，李祚泳，熊建秋，等.基于免疫禁忌优化算法的 理与模式识别」 生态环境评价指数公式及其应用[J]生态与农村环境 学报，2006,22(4)：25-29 WANG Jiayang,LI Zuoyong,XDNG Jiangiu,et al Expo- 尹怡欣，男，1957年生，教授，博士 nential fomula for evaluation of eco-envirommental quality 生导师，中国人工智能学会常务理事、 based on mmune taboo search[J].Joumal of Ecology and 中国自动化学会理事.主要研究方向为 Rural Envirorment,2006,22(4):25-29 复杂系统的建模与控制、人工生命、智 [8 ]De CASTRO L N,ZUBEN F J.aNet an artificial imune 能控制与智能管理 nework for data analysis [C]//Data m ining A Heuristic 付冬梅，女，1963年生，教授，博士 Approach Hershey,USA,2001:1-37 生导师，主要研究方向为红外图像技 [9 ]De CASTRO L N,TMM IS J.An artificial mmune nework 术、理论与实际应用、人工免疫智能算 for multiodal function optm ization [C]//Proc of IEEE 法及应用.作为主要参与人参加863、 Congress on Evolutionary Computation Honolulu:EEE 973、博士点基金等项目8项. Service Center,USA,2002:699-704. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
别 [M ]. 北京 : 科学出版社 , 2006: 2182235. [ 5 ] ZHENG D L, L IANG R X, FU D M, et al. App lication of artificial immune system and artificial immune genetic algo2 rithm to op tim ization [ J ]. Journal of University of Science and Technology Beijing, 2003, 3 (25) : 2842287. [ 6 ]黄弦超 , 舒 隽 , 张粒子 ,等. 免疫禁忌混合智能优化算 法在配电网检修优化中的应用 [J ]. 中国电机工程学报 , 2004, 24 (11) : 962100. HUANG Xianchao, SHU Jun, ZHANG L izi, et al. D istribu2 tion maintenance scheduling using an intelligent op timal ap2 p roach mixed with immune algorithm and tabu search [ J ]. Journal of Chinese Electrical Engineering Science, 2004, 24 (11) : 962100. [ 7 ]汪嘉杨 , 李祚泳 , 熊建秋 ,等. 基于免疫禁忌优化算法的 生态环境评价指数公式及其应用 [J ]. 生态与农村环境 学报 , 2006, 22 (4) : 25229. WANG Jiayang, L I Zuoyong, X IONG Jianqiu, et al. Expo2 nential formula for evaluation of eco2environmental quality based on immune taboo search [J ]. Journal of Ecology and Rural Environment, 2006, 22 (4) : 25229. [ 8 ]De CASTRO L N, ZUBEN F J. aiNet: an artificial immune network for data analysis [ C ] / /Data mining: A Heuristic App roach. Hershey, USA, 2001: 1237. [ 9 ]De CASTRO L N, TIMM IS J. An artificial immune network for multimodal function op timization [ C ] / /Proc of IEEE Congress on Evolutionary Computation. Honolulu: IEEE Service Center, USA, 2002: 6992704. [ 10 ] TAN P H, RASMUSSEN L K. Tabu search multi2user de2 tection in CDMAEA [ C ] / /Radio Vetenskapoch Kommuni2 kation. Stockholm, Sweden, 2002: 7442748. [ 11 ]JU I YW , CHUNG Y K. A rtificial immune system for sol2 ving constrained global op timization p roblem s[ C ] / /The First IEEE Symposium on A rtificialLife. Honolulu: Hawaii, USA, 2007: 92299. [ 12 ] SUN R X, QU L S. Quantitative evaluation of op tim ization efficiency for genetic algorithm s[ J ]. Acta Automatic Sini2 ca, 2000, 26 (4) : 5522556. 作者简介 : 赵云丰 ,男 , 1979 年生 ,博士研究 生 ,主要研究方向为人工智能、图像处 理与模式识别. 尹怡欣 ,男 , 1957年生 ,教授 ,博士 生导师 ,中国人工智能学会常务理事、 中国自动化学会理事. 主要研究方向为 复杂系统的建模与控制、人工生命、智 能控制与智能管理. 付冬梅 ,女 , 1963年生 ,教授 ,博士 生导师 ,主要研究方向为红外图像技 术、理论与实际应用、人工免疫智能算 法及应用. 作为主要参与人参加 863、 973、博士点基金等项目 8项. ·400· 智 能 系 统 学 报 第 3卷