第3期 赵春晖，等：改进克隆选择算法的层叠滤波器的优化设计 ·255 11阈值分解 式中：N°=，N为观测窗长 假设X=(X,X2,X,X,,X)是一个长度 在实际应用过程中，C0,)等于理想输出为0 为的多值信号向量，其中X,∈Q,Q=0,M}, 时的二值矢量，在观测信号中出现的次数， 则信号的阈值分解如下： C(1等于理想输出为1时的二值矢量5在观测 1,X,≥t Xi=T(X)= 信号中出现的次数.P,(015)和P,(1/,)分别为输 0. else 入为输出为0和1的概率.因为P0/5,P1 则阈值分解信号可以表示为 )等于0或者1，所以可以将其一直接进行二进制 x={,,华x,…} 编码，便生成对应的布尔函数真值表，生成的布尔函 12正布尔函数的层叠性 数经过层叠性判断和约束后即生成为初始的正布尔 长度为N的矢量X和Y,若对于任意i∈{1,2， 函数，对其采用一定的优化算法进行优化，以式(3) :N},均满足条件X()≥Y(,则称X≥Y对于作为评价优化过程中正布尔函数的优劣，从而得到 矢量序列X,X2,…X若满足条件X1≥X2≥…≥ 最优正布尔函数定义的层叠滤波器对噪声图像进行 X,则称该矢量序列具有层叠性.一个有N输入的 层叠滤波处理 布尔函数F0,1}”→0,1}，任取2个包含N个分 量的二值向量X和Y,若X≥Y→fX)≥f(Y),则称 3克隆选择算法 布尔函数具有层叠性，或者称其为正布尔函数.根据 虽然目前对克隆选择算法的研究还处于起步阶 以上性质，可以得到层叠滤波器S,基于正布尔函数 段，相应的研究成果比较少，但是研究表明，利用克 F0,1}→10.1的定义： 隆选择算法的思想在解决组合优化问题时，能够较 好的保持群体多样性和避免陷入局部最优解6) S(x) =f(x) 克隆选择算法与其他智能算法如遗传算法、粒子 式中：x=TX)为输入信号的阈值分解向量 群算法等)之间有如下的区别： 2层叠滤波器的优化模型 1)它在记忆单元即群体较优个体基础上运行， 确保了快速收敛至全局最优解： 基于MAE准则进行优化时可以得到较好图 2它的亲和度的计算反映了系统的多样性，： 像细节保持能力，基于MSE准则进行优化时可以得 3)它的克隆选择算子实现了在候选解附近的 到较好抑制噪声能力.文中基于MAE准则进行层叠 局部搜索，进而实现全局搜索， 滤波器的最优化设计，以得到较好的边缘保持性，适 31基本的克隆选择算法 用于对图像细节要求较高的场合.最小平均绝对误 巴西人工免疫学研究专家Castro博士于1999 差准则MMAE)的表达式如下： 年在借鉴生物免疫系统的克隆选择原理的基础上提 MMAE(S)=m in E[D (n)-S,(R (n))1. 出了最早的克隆选择算法，其算法步骤如下： (1) 1)生成初始种群P,由记忆单元M和保留群体 式中：D(n)为期望信号，R(n)为输入信号向量， P,组成，即P=M+P: SR(n))为滤波器输出信号.由式(1)可得 2)根据亲和度选择n个个体组成群体(Pn: M MMAE(S)=min Ell d (n)-f(f (n))1 3)克隆这n个最好的个体，生成一个克隆临时 种群C,克隆规模和抗体抗原亲和度成正比： 2) 4)对克隆的临时种群进行变异，变异的概率和 式中：d(n)和向量”(n)分别为期望信号和输入 抗体抗原亲和度相对应，由此得到抗体群C: 信号向量的阈值分解信号 5)从C,中选取改进的个体组成记忆单元M,P 根据信号估计理论和贝叶斯判决理论，由式 中亲和度低的个体也被C,中其他个体取代， (2)进一步推导如下公式： 32改进的克隆选择算法 MAE(S)-IC(0.)(1/) 结合层叠滤波器理论，在基本克隆选择算法的 基础上，对算法进行了如下改进： C1,P0/)1, (3) 1)实现了记忆单元与保留群体同时进化.此操 P(1/)≤P1/)if≤ 4) 作既保证了算法的收敛性又保持了种群的多样性」 P(1/1)=0 or1Vj (5) 基本克隆选择算法中的3)~5)可称为单克隆算子、 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved htp://www.cnki.net1. 1 阈值分解 假设 X = (X1 , X2 , X3 , …, Xi , …, Xl )是一个长度 为 l的多值信号向量 ,其中 Xi ∈Q, Q = { 0, …, M }, 则信号的阈值分解如下 : x t i = T t (Xi ) = 1, Xi ≥ t; 0, e lse. 则阈值分解信号可以表示为 x t = { x t 1 , x t 2 , …, x t i , …, x t l } . 1. 2 正布尔函数的层叠性 长度为 N 的矢量 X和 Y,若对于任意 i∈{ 1, 2, …, N },均满足条件 X ( i) ≥Y ( i) ,则称 X≥Y. 对于 矢量序列 X1 , X2 , …, Xk 若满足条件 X1 ≥X2 ≥…≥ Xk ,则称该矢量序列具有层叠性. 一个有 N 输入的 布尔函数 f: { 0, 1} N →{ 0, 1},任取 2个包含 N 个分 量的二值向量 X和 Y,若 X≥Y] f (X) ≥f ( Y) ,则称 布尔函数具有层叠性 ,或者称其为正布尔函数. 根据 以上性质 ,可以得到层叠滤波器 Sf 基于正布尔函数 f: { 0, 1} N →{ 0, 1}的定义 : Sf (X) = ∑ M - 1 t =1 f ( x t ) . 式中 : x t = T t (X)为输入信号的阈值分解向量. 2 层叠滤波器的优化模型 基于 MAE准则 [ 5 ]进行优化时可以得到较好图 像细节保持能力 ,基于 MSE准则进行优化时可以得 到较好抑制噪声能力. 文中基于 MAE准则进行层叠 滤波器的最优化设计 ,以得到较好的边缘保持性 ,适 用于对图像细节要求较高的场合. 最小平均绝对误 差准则 (MMAE)的表达式如下 : MMAE (Sf ) = m in E[ | D ( n) - Sf (R ( n) ) | ]. (1) 式中 : D ( n )为期望信号 , R ( n )为输入信号向量 , Sf (R ( n) )为滤波器输出信号. 由式 (1)可得 MMAE(Sf ) = min ∑ M m = -M +1 E[| d m (n) - f ( r m (n) ) | ]. (2) 式中 : d m ( n)和向量 r m ( n)分别为期望信号和输入 信号向量的阈值分解信号. 根据信号估计理论和贝叶斯判决理论 , 由式 (2)进一步推导如下公式 : MAE (Sf ) =∑ N 3 j =1 [C (0, rj ) Pf (1 / rj ) + C (1, rj ) Pf (0 / rj ) ], (3) Pf (1 / ri ) ≤ Pf (1 / rj ) if ri ≤ rj , (4) Pf (1 / rj ) = 0 or 1Π .j (5) 式中 :N 3 = 2 N , N 为观测窗长. 在实际应用过程中 , C ( 0, rj )等于理想输出为 0 时的 二 值 矢 量 rj 在 观 测 信 号 中 出 现 的 次 数 , C (1, rj )等于理想输出为 1时的二值矢量 rj 在观测 信号中出现的次数. Pf ( 0 / rj )和 Pf ( 1 / rj )分别为输 入 rj为输出为 0和 1的概率. 因为 Pf ( 0 / rj ) , Pf ( 1 / rj )等于 0或者 1,所以可以将其一直接进行二进制 编码 ,便生成对应的布尔函数真值表 ,生成的布尔函 数经过层叠性判断和约束后即生成为初始的正布尔 函数 ,对其采用一定的优化算法进行优化 ,以式 ( 3) 作为评价优化过程中正布尔函数的优劣 ,从而得到 最优正布尔函数定义的层叠滤波器对噪声图像进行 层叠滤波处理. 3 克隆选择算法 虽然目前对克隆选择算法的研究还处于起步阶 段 ,相应的研究成果比较少 ,但是研究表明 ,利用克 隆选择算法的思想在解决组合优化问题时 ,能够较 好的保持群体多样性和避免陷入局部最优解 [ 628 ] . 克隆选择算法与其他智能算法 (如遗传算法、粒子 群算法等 )之间有如下的区别 : 1)它在记忆单元即群体较优个体基础上运行 , 确保了快速收敛至全局最优解; 2)它的亲和度的计算反映了系统的多样性; 3)它的克隆选择算子实现了在候选解附近的 局部搜索 ,进而实现全局搜索. 3. 1 基本的克隆选择算法 巴西人工免疫学研究专家 Castro博士于 1999 年在借鉴生物免疫系统的克隆选择原理的基础上提 出了最早的克隆选择算法 ,其算法步骤如下 : 1)生成初始种群 P,由记忆单元 M 和保留群体 Pr组成 ,即 P =M + Pr; 2)根据亲和度选择 n个个体组成群体 ( Pn ) ; 3)克隆这 n个最好的个体 ,生成一个克隆临时 种群 C,克隆规模和抗体 —抗原亲和度成正比; 4)对克隆的临时种群进行变异 ,变异的概率和 抗体 —抗原亲和度相对应 ,由此得到抗体群 C1 ; 5)从 C1 中选取改进的个体组成记忆单元 M , P 中亲和度低的个体也被 C1 中其他个体取代. 3. 2 改进的克隆选择算法 结合层叠滤波器理论 ,在基本克隆选择算法的 基础上 ,对算法进行了如下改进 : 1)实现了记忆单元与保留群体同时进化. 此操 作既保证了算法的收敛性又保持了种群的多样性. 基本克隆选择算法中的 3) ～5)可称为单克隆算子、 第 3期 赵春晖 ,等 :改进克隆选择算法的层叠滤波器的优化设计 ·255· © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net