·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卷