函数生成元（通用7篇）
函数生成元 篇1
通过我对陈显强老师著的《有限循环群的一个计数定理》文章分析, 我受到一些启发, 再结合目前的计算机专业的教材与常见的文章中很少提到有限循环群生成元的计数问题, 即使提到也只是给出有限循环群生成元的定性分析而没有确定数量上的计数公式。有时在解题时, 只需知道有限循环群生成元的个数而不需知道生成元是什么;如果能有一个确定的有限循环群生成元的计算公式, 这样可以提高解题效率。本文就是针对以上所提到的问题, 从欧拉函数的角度给出了有限循环群生成元个数的计算公式。
1 有限循环群与生成元
定义1:若一个群G的每一个元都是G的某一个固定元a的乘方, 我们就把G叫做循环群;我们也说, G是由元a所生成的, 并且用符号G= (a) 来表示, a叫做G的一个生成元。
循环群G= (a) 根据生成元a的阶可以分成两类:有限循环群和无限循环群。
设G= (a) 是循环群, 若a是n阶元, 则G={a0=e, a 1, a 2, L, an-1}, 那么G=n, 称G为有限循环群即n阶循环群。若a是无限阶元, 则G={a0=e, a±1, a±2, L}称G为无限循环群。
定理1:设G= (a) 是循环群。
(1) 若G是无限循环群, 则G只有两个生成元即a和a-1。
(2) 若G是n阶循环群即有限循环群, 则G含有ϕ (n) (即欧拉函数) 个生成元, 对于任何小于等于n且与n互素的正整数r, ar是G的生成元。
定理证明从略。
2 欧拉函数
定义2:不大于m而与m互素的数的个数, 叫做欧拉函数Euler, 记为ϕ (m) 。
易知, 若p为素数, 则ϕ (p) =p-1。
定理2:若正整数m的素数幂分解式为
证: (1) 不大于m的1p的倍数共有个:
故不大于而与互素的数共有
(2) 不大于m的2p的倍数共有个:
其中个数
也是1p的倍数。所以, 是p2的倍数而不是1p的倍数的数共有个。因而, 不大于m而与1p, p2互素的数共有个。
(3) 不大于m的3p的倍数共有个:
但在:
这些数内还有p1, p2的倍数, 由第Ⅱ步的结论知:不大于而与p1, p2都互素的数共有有这些数与p3相乘所得之积才是p3的倍数而同时不是p1或p2的倍数。所以, 不大于m而与p1, p2, p3都互素的数共有
(4) 这样继续作下去。因为n为有限数, 故得不大于m而与p1, p2, …, pn都互素的数共有
个。所以:
证毕。
推论:若
证明从略。
3 有限循环群生成元个数n的计数公式
由定理1中的 (2) 与定理2以及其推论可得, 有限循环群生成元个数n的计算公式:
下面给出一个利用此公式求解有限循环群生成元个数的例子:
例:设G是循环群且|G|=12, 则由于个生成元。
4 结语
本文从欧拉函数的定义以及与有限循环群生成元的关系入手, 详细阐述了有限循环群生成元的计算公式这个问题, 从而使读者对有限循环群生成元的公式有更深刻的理解与应用。
摘要：本文从有限循环群的定义出发, 结合有限循环群的定理;从欧拉函数的角度给出了有限循环群生成元的计算公式。
关键词：有限循环群,生成元,欧拉函数
参考文献
[1]陈显强.有限循环群的一个计数定理[J].中山大学学报论丛, 2002 (2) :22, 1.
[2]张禾瑞.近世代数基础[M].高等教育出版社, 2005.
[3]耿素云, 屈婉玲.离散数学[M].高等教育出版社.
[4]李复中.初等数论选讲[M].东北师范大学出版社.
[5]U.杜德利[著], 周仲良[译].基础数论[M].上海科学技术出版社.
概率生成函数的简单应用 篇2
1 匹配问题
匹配问题是关于把物体随机放入容器中这类问题中最简单的一种情形。现在我们将匹配问题一般化,这样更容易从本质上加深对问题的理解。
问题:给定一个随机事件的集合
其中Ai(1≤i≤n)都是随机事件。现在来求出在这n个事件中恰好有X个事件发生的概率。显然,X是随机变量,它能够取到的值为0,1,…,n。下面来计算X取到m的概率是多少,也就是说,在这n个事件中恰好有m个事件发生的概率是多少。
先从这n个事件中任取m个事件:
这m个事件同时发生可表示为Ai1∩Ai2∩…∩Aim,所以恰好有m个事件发生的概率记为
令S0=1。很容易得到
其中,二项式系数的均值为:用Nm表示元素个数为m的集合A的子集的个数与之对应的事件发生。
于是,有
其中,。由⑴式得
引入生成函数:
将⑵式代入,并对m求和,得
所以,GX(x)=GS(x-1)。由两侧xm的系数相等,得
这样我们就比较容易地得到了这个公式,当然,也可以用其他方法得到这个结论,但是论证过程可能相对复杂一些。
2 苍鹭捕鱼问题
小林老师应邻居的请求在他们度假不在家的时候帮助喂养在花园池塘里的金鱼。尽管小林老师每天都按要求去喂养金鱼,但是三星期来没有看到过一条金鱼。结果发现池塘里所有的金鱼都被一只苍鹭在邻居不在的时候偷偷吃掉了,而苍鹭吃鱼的时候一次也没被发现。
用N表示邻居不在时苍鹭访问池塘的次数,假设N服从参数为1-θ的几何分布,于是
每次苍鹭能捕到鱼的概率为p,假设任意两次捕鱼都是相互独立的,而且假设池塘里有无数多条鱼,且每条鱼被捕到的可能性都相同。现在我们来计算被苍鹭捕到的金鱼的总数T的分布。令
从而,
且X1,X2,…相互独立,所以有
而
令r=GX(s),得
将GX(s)=1-p+ps代入,即得
这是参数为的几何分布的生成函数,由生成函数的唯一性得T服从参数为的几何分布。
3 结论
概率生成函数作为一个工具,确实有着广泛的应用,它可以很好地起到一个桥梁的作用,连接离散与连续的关系。它是采用变换思想解决实际问题的一种具体方法,它将非负整数值随机变量的概率分布描述成一个幂级数或其和函数,即概率生成函数,然后利用概率生成函数的性质间接求解概率问题。从文中的实例可以看到概率生成函数在求解某些类型的问题时具有比较巧妙的作用,可以使我们在解决概率问题时陷入烦琐的计算当中。在教学过程中,可以通过类似问题的讲解来激发学生的学习兴趣和学习热情。
参考文献
[1]陈家鼎,郑忠国.概率与统计[M].北京:北京大学出版社,2007.
[2]李贤平.概率论基础[M].北京:高等教育出版社,1997.
函数生成元 篇3
变换域通信系统的基函数是整个通信系统的基础。它由电磁环境采样, 信道估计, 门限判决, 随机相位匹配几个步骤生成。生成的基函数是在变换域的, 要得到相应的时域形式需要经过相应的变换[1,2,3,4,5,6,7]。
变换域通信系统的基函数在信息传输过程中的作用, 与传统无线数字传输系统的载波有些类似。但是它与传统的载波又有很大的不同, 这种不同也体现出变换域通信系统相对于传统无线数字传输系统的优越性。首先, 基函数不是一个简单的由波形生成器产生的波形, 它是通过捕捉电磁环境的实时变化, 经过门限判决和随机相位匹配在变换域生成的波形。其次, 由于它特殊的生成过程, 使它能够避开干扰, 只存在于没有干扰或者干扰很小的域。正是由于这些特点, 使得基函数与传统传输系统的载波相比具有复杂性和时变性。这些特点不仅影响了物理层的调制技术, 对于数据链路层以及更高层的相关技术也同样有着深远影响。这些决定了变换域通信系统是不同于以往的无线数字传输系统的一个全新的数字传输系统。
构造一个好的基函数无疑是构造整个系统的关键。好的基函数不仅能够更好地规避干扰, 降低被敌方截获的概率, 同时它也是数据调制的基础。基函数在变换域通信系统的数据调制中扮演着传统通信系统中载波的角色, 它自身正交性的好坏, 直接影响到移位键控的性能。同样数据链路层的差错控制技术也是以基函数的特性为基础的。所以基函数的好坏直接影响到系统整体性能的发挥。
1 变换域通信系统概述
TDCS是一个宽带系统。TDCS的发射机和接收机分别由环境采样器、信道估计器 (谱估计、时频估计) 、随机相位发生器等模块构成。图1, 图2是TDCS基本工作原理图, 它是基于傅里叶变换 (FFT) 的变换域通信系统, 其他变换域通信系统的原理图基本一样, 只是将相应变换模块更换为其他的变换方法。下面将依照图1, 图2介绍基于FFT的变换域通信系统。
首先由发射机和接收机对环境进行采样, 并且估计出干扰在变换域中的位置。并根据这个估计产生一个基函数 (Basis Function) , 这个基函数的变换域形式中与干扰相同的频段的能量极低。假设接收机与发射机所处的电磁环境是一样的 (这个假设对短距离间的通信是成立的, 如编队飞行的飞机间的通信) , 因此, 发射机与接收机对电磁环境的估计应是一样的, 发射机与接收机产生的基函数也应该完全一样。然后发射机使用所生成的基函数对数据调制后发射[8]。既然接收机产生的基函数与发射机产生的基函数是一样的, 因此接收机可以使用自己产生的基函数相关解调。由基函数的产生过程可知基函数与通信信道中的所有干扰在变换域中是互不重叠的, 因此信号在传输过程中不会受到信道中的干扰影响。所以TDCS是一个干扰避免通信系统。
2 基函数的生成过程
2.1 电磁环境采样
变换域通信系统研究的出发点是解决在复杂电磁环境下的可靠通信问题。对电磁环境的采样, 可以看作是对某一电磁信号的采样, 它将构成基函数的基础。采样频率越高, 整个变换域通信系统的可选择带宽就越大。这对于系统来说当然是好事。但是采样频率越高, 对电子器件的要求就越高, 同样处理这些信息的时间也就越长。当时间长到跟不上电磁环境的变化速度时, 整个系统也就失去了意义。变换域通信系统是一个对器件要求很高的系统。也正是这一点制约了变换域通信系统向实际应用的发展。
模拟波形及其采样信号之间的联系由采样过程确定, 这个过程可以有几种方法实现, 最常用的是采样保持。此时, 一个转换和存储装置产生连续输入波形的一个采样序列。采样过程的输出称为脉冲幅度调制, 因为持续的输出间隔可以由一个幅度经输入波形样值获取的脉冲序列来描述。
根据奈奎斯特准则:
采样速率的快慢将决定整个通信系统的带宽。系统的最高频率低于采样速率的1/2。
2.2 干扰系数的引入
假设采样频率fs为1 000次/s, 那么系统的最高频率为500 Hz。对采样的结果进行谱估计, 将估计得到的功率谱密度A (w) 与一个选定的门限值相比较来确定整个工作频带中哪些部分己被干扰, 哪些部分没有受到干扰。在以往的文献中, 将高于门限的频带的谱值设为0, 低于门限的频带的谱值设为1, 这样就得到一个由0和1构成的谱向量A′ (w) , 它是一个理想的矩形谱[9]。
问题在于门限的选择, 并没有确定的标准。文献[4,10], 中对WDCS的性能进行分析时, 是根据经验而选定的固定门限值, 取为环境噪声功率的1.2倍。当小波子带的功率超过环境噪声功率的1.2倍时, 认为存在干扰, 整个子带被置为零。文献[4]中对基于傅里叶变换的TDCS使用自回归 (AR) 参数模型对信道进行功率谱估计时, 模型阶次分别取10阶和20阶, 门限取峰值最大值的40%, 也是固定值。
在TDCS中不存在干扰时, 构成基函数的每个子载波具有相同的能量, 不同的初相位。因此基函数的功率谱密度是平坦的, 是一个理想的离散矩形谱, 类似于带通型限带白噪声。平稳随机过程的自相关函数Rx (τ) 与信号的功率谱密度Sx (w) 是一对傅里叶变换对:
理想白噪声的自相关函数是一个脉冲函数。因此当限带白噪声的带宽W越宽时, 它就越接近理想的白噪声, 它的自相关函数也就越接近于脉冲函数。
这说明基函数的正交性与频谱的丰富性有关。越多的频谱被门限判定为存在干扰而删除, 基函数的可用的频谱就越单调, 基函数的正交性也就越差。无论采用哪种门限剔出方式, 都难免存在误判。也即所剔出的频带不一定是完全不可用的, 即使存在微弱的干扰, 也是有利用价值的, 特别是在干扰较强的情况下。
本文在这里引入干扰系数的概念, 对频带中各个频段受干扰的程度赋以权值。对确实不存在干扰的“干净”频段赋值为1, 对存在较强干扰的频段赋值为0, 而对受到较弱干扰的频段根据受干扰的程度赋值0～1不等。这样可以提高频谱的丰富性, 从而提高最终生成基函数的正交性。
2.3 随机相位匹配
经过门限剔除己经得到了基函数的频谱幅值, 可以根据需要生成相应的相位, 然后与谱的幅值去匹配。在这里使用伪随机相位发生器产生一个复随机相位向量ejφj, 该向量与之前产生的谱值向量A′ (w) 长度相同。首先由一个二进制伪随机码 (PN码) 发生器产生一个伪随机序列, 相位映射器根据这个伪随机序列计算得到随机相位并输出, 得到一个长度为N的相位向量ejφj[10,11,12,13,14]。
在相位匹配器中向量ejφj与谱值向量A′ (w) 点乘得到一个谱向量, 该谱按一定比例C放大以保证有一定发射功率得到基函数 (传输波形) 的频域形式B (w) , 即:
将得到的基函数频域形式B (w) 经过傅里叶反变换 (IFFT) 后得到基函数的时域形式b (t) , b (t) 的复数表示如下:
基函数实际上是多个子载波的叠加, 各个子载波的初相位φ必是在一个相位空间内随机分布的。采用随机相位是为了确保基函数在时域具有类似于噪声的波形, 从而使信号不容易被截获。它的自相关函数几乎是一个脉冲函数, 也就是说基函数与它的时移形式有较好的正交性。
2.4 仿真分析
仿真环境:Matlab 7.0;电磁环境:多音干扰, 高斯白噪声;信噪比:4 dB;干噪比:8 dB;谱估计方法:20阶AR模型;门限选取方式:功率谱密度高于干扰峰值 (dB) 60%以上的频段置0, 低于20%的置1, 在20%～60%之间按功率谱密度值归一化赋0～1。
仿真结果如图3～图5所示。
从图4 (a) 中可以看出常规门限剔除方法所得的频谱较窄, 而图4 (b) 中经过干扰系数平滑的功率谱, 频谱的利用率相对提高。从图5 (a) 和图5 (b) 的对比中可以看到引入干扰系数后得到的基函数自相关函数更加尖锐, 这种方法生成的基函数具有更好的正交性。
3 结 语
本文通过引入干扰系数, 针对强干扰环境下基函数的频谱相对单调, 基函数的正交性下降的问题, 提高了频谱的利用效率, 弥补了常规门限处理在频谱资源利用方面的不足。通过仿真验证了引入干扰系数的基函数生成方法所生成的基函数在强干扰环境下有更好的正交性。
三次样条插值函数的快速生成 篇4
1 三次样条函数插值问题
定义1 对于区间[a,b]上的一个分划△:a=x0<x1<…<xn=b,若函数s(x)满足条件
(1)s(x)在每个子区间[xi,xi+1](i=0,1,…,n-1)上是次数不超过m的多项式;
(2)s(x)在区间[a,b]上有m-1阶连续导数;则称s(x)是定义在[a,b]上对应于分划△的m次样条函数。x0,x1,…,xn称为样条结点,其中x1,x2,…,xn-1称为内结点,x0,xn称为边界结点。若当m=3,就得到最常用的三次样条函数。
定义2 设有区间[a,b]上的一个分划△:a=x0<x1<…<xn=b,函数f(x)在各结点处的值为yi=f(xi)(i=0,1,…,n-1),若s(x)满足:
(1)s(x)在每个子区间[xi,xi+1](i=0,1,…,n-1)上是不超过3次的多项式;
(2)s(x)在区间[a,b]上具有二阶连续导数;
(3)s(xi)=yi,i=0,1,…,n.则称s(x)为函数y=f(x)在[a,b]上的三次样条插值函数。
三次样条插值函数s(x)在每个小区间[xi,xi+1](i=0,1,…,n-1)上是不超过3次的多项式,含有4个待定系数,记为si(x)=aix3+bix2+cix+di(i=1,2,…,n),在整个插值区间上有4n个待定系数,即
按照三次样条插值定义,由条件(2)有
共有3n-3个条件,在加上条件(3)有n+1个条件,共有4n-2个条件。因此,要确定三次样条插值函数s(x),还要附加两个约束条件,这两个条件通常在区间[a,b]的端点给出,称为边界条件。从力学角度考虑,附加边界条件相当于在细梁的两端加上适当的约束,这是由意义的。
边界条件的类型很多,常见的边界条件有如下三类:
第一类:转角边界条件,即给定端点处一阶导数值:
第二类:弯矩边界条件,即给定端点处二阶导数值:
特别地,s″(x0+0)=0,s″(xn-0)=0称为自然边界条件。满足自然边界条件的样条函数叫做自然样条函数。它是通过所有数据点的插值函数类中曲率最小的惟一函数,是三次样条插值中最光滑的函数。
第三类:周期性边界条件,即当f(x)时以xn-x0为周期的周期函数时,自然要求s(x)也是以xn-x0为周期的周期函数。因此,周期边界条件为:
此时,y0=yn,这样确定的样条函数s(x)称为周期样条函数。
在附加了某类边界条件后,就得到了{ai,bi,ci,di}(i=1,2,…,n)为4n个未知数的4n个方程,从而惟一地确定了s(x)。
2 三次样条函数的快速生成
关于如何确定系数{ai,bi,ci,di},一般情况下并不直接去解线性代数方程组。下面我们介绍快速生成三次样条函数的方法———追赶法,它是解三次样条插值函数最常用的方法。
三次样条函数的实际计算,除周期情形外,都归结为求解系数矩阵为对角占优的三对角线方程组
其中aij=0,当i-j>1时,
我们利用矩阵的直接三角分解法来推导解三对角线性方程组(1)的计算公式。有系数阵A的特点,可以将A分解为两个三角阵的乘积
其中L为下三角矩阵,U为单位上三角矩阵。下面我们来说明这种分解是可能的。设
其中αi,βi,γi为待定系数,比较(2)两边即得
由α1=b1≠0,b1>c1>0,β1=c1/b1得0<β1<1。下面我们用归纳法证明
(即0<βi<1)从而由(3)可求出βi。
(4)对i=1是成立的,现设(4)对i-1成立,求证对i也成立。
由归纳法假设0<βi-1<1,又由(4)及A的假设条件有
也就是0<βi<1
由(3)得到αi=bi-αiβi-1(i=2,3,…,n);
这就是说,有A的假设条件,我们完全确定了{αi},{βi},{γi},实现了A的LU分解。
求解Ax=f等价于解两个三对角形方程组
(1)Ly=f,求y,(2)Ux=y,求x,
从而得到解三对角线方程组的追赶法公式:
1)计算{βi}的递推公式
我们将计算系数β1→β2→…→βn-1及y1→y2→…→yn的过程称为追的过程,将计算方程组的解xn→xn-1→…→x1的过程称为赶的过程。
在周期端点条件下,三次样条函数的实际计算,就归结为方程组的求解计算。在方程组(5)的系数矩阵中,除了三对角线上的非零元素外,它的右上角和左下角还各有一个非零元素a1和cn。因此方程组不能直接利用追赶法求解。于是先把xn看作参量,再由(5)中的前n-1个方程所组成的方程组
则方程组(6)的解计算就化为方程组
的求解计算。
利用追赶法计算出方程组(8)和(9)的解ui和vi(i=1,2,…,n-1)。另外由(7)有
将此二式代入方程组(5)的最后一个方程中得
解此方程得
这样就可以算出方程组(5)的解。
总结上述讨论有
定理 设有三对角线方程组Ax=f,其中A满足条件(a),(b),(c),则A为非奇异矩阵且由追赶法计算公式中{αi},{βi}满足:
追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果。这时由于A特别简单,而且计算量仅为5n-4次乘除法,而另外增加一个方程组Ax=f2仅需增加3n-2次乘除运算。易见追赶法的计算量是比较小的。
摘要：本文介绍了三次样条插值函数的基本概念和引入三次样条插值函数的必要性,以及如何利用追赶法快速生成三次样条插值函数。
关键词：三次样条插值函数,快速生成,追赶法
参考文献
[1]李庆扬,王能超,易大义.数值分析[M].4版.清华大学出版社.
[2]曹德欣,王海军.三次样条插值函数的数值稳定性[J].中国矿业大学学报,2001(2).
[3]牛旭,李小平.利用三次样条插值函数模拟机翼下曲线轮廓[J].科技风,2009(10).
[4]谢文龙.三次样条函数的构造方法[J].江南学院学报.
[5]王省富.样条函数及其应用[M].西安:西北工业大学出版社,1989.
函数生成元 篇5
广义最小生成树问题广泛应用于远程通信、能源分布、农业灌溉等领域。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边权的总和为最小,称为最小生成树问题(MST)。广义最小生成树问题(GMST)是最小生成树问题的推广,它是将这个无向图的顶点分为k个簇,在每个簇中找一个点作为这个簇的代表,共找到k个点,然后在这k个点组成的新的子图中,寻找它的最小生成树问题。GMST最先由Myung等[1]于1995年提出,并且证明它是NP-难的,而且给出了求解这个问题的分支定界法;Feremans等[2]对于GMST的8个整数规划模型进行了理论上的比较;Feremans等[3]提出了几类有效不等式以及分支切割法来解决GMST;Duin等[4]把GMST转化为斯坦纳树(Steiner Tree)问题,并利用一些专门的算法来解决。近年来,Pop等[5]提出了GMST的一种新的整数规划模型。
对于GMST,当规模比较大时,得到最优解比较困难,所以对于大规模GMST经常用元启发式算法进行解决。Feremans[6]首先提出用禁忌搜索算法来求解GMST;Pop[7]提出模拟退火算法来解决GMST;Hu等[8]提出了改进的变邻域搜索算法来解决GMST,并与其他的元启发式算法进行了比较;Golden等[9]提出了一种局部搜索算法和遗传算法来解GMST。最近,Wang等[10]提出了一种改进的禁忌搜索算法来解决GMST,并表示他的算法比文献[9]中的遗传算法有效。本文基于遗传算法和模拟退火算法的优点,提出了单亲遗传模拟退火算法,并且通过在2种邻域进行搜索改进禁忌搜索算法,并与文献[10]中给出的最优值比较,证明我们算法的有效性。
1 问题描述
考虑无向图G=(V,E),V={v1,v2,…,vn},将点集V中的顶点分为k个簇(即k个集合),分别为V1,V2,…,Vk(k≤n)。
E={{vi,vj}|vi∈Vp,vj∈Vq,p,q=1,…,k,且p≠q},为不同簇之间点的连接边集。C={cij},cij为边{vi,vj}的权。在每个簇中找一个点作为这个簇的代表,共找到k个点,然后在这k个点组成的新的子图中,寻找其最小生成树。最小生成树边权的和记为fm,则GMST就是要找满足fm最小的k个点。图1即为k=5,n=13的GMST。
2 算 法
针对广义最小生成树问题模型,本文设计了2种改进的元启发式算法:单亲遗传模拟退火算法和改进的禁忌搜索法。
2.1单亲遗传模拟退火算法
单亲遗传算法(partheno-genetic algorithm,PGA)是对传统遗传算法(GA)的一种改进算法,它取消了传统遗传算法的交叉算子,采取单亲繁殖方式。跟传统遗传算法相比,单亲遗传算法操作简单。而模拟退火(simulated annealing,SA)是一种强大的随机搜索算法,它不依赖于起始点,能在复杂的情况下产生高质量的解。己有研究证明,模拟退火算法在选择合适的退温函数后,能够以概率1收敛到最优解。所以综合了PGA和SA的优点,本文提出了单亲遗传模拟退火算法(PGASA),它的基本操作包括编码、初始种群的产生、个体的适应度评价、个体的选择、基因重组、模拟退火等。
2.1.1 初始种群的产生及编码
针对广义最小生成树问题的特点,本文用如下方式来构造个体,即S=[vi1,vi2,…,vik]。式中:vi1∈V1,vi2∈V2,…,vik∈Vk。初始种群中的个体随机产生,即S中的每一位vic都由Vc中的随机一个点产生,c=1,…,k,这样就能保证种群中的个体都是可行解。种群规模记为Ps。
2.1.2 评价个体适应度
本文直接以个体S的目标函数值作为它的适应度值,而个体S的目标函数值就是S中k个点组成的子图的最小生成树,通过Prim算法来求图的最小生成树。
2.1.3 自适应选择
在算法迭代的初始阶段:对于基因重组,考虑到重组操作会破坏优秀个体的结构,故不好的个体以较高的概率被选择进行重组操作,好的个体则以较低的概率进行重组操作;对于模拟退火,为了保证算法的全局收敛,每个个体都以较高的概率进行模拟退火操作。在算法迭代进行到一定阶段时:对于基因重组,考虑到算法会陷入局部最优,应该加大基因重组的作用,故不好的个体依旧以较高的概率进行重组,好的个体也以比较高的概率进行重组;对于模拟退火操作,为了提高算法效率,好的个体以较高的概率进行模拟退火操作,不好的个体则以较低的概率进行操作。于是本文设计了自适应选择法,针对个体的优劣情况,随着迭代的进行,根据一定的概率,自适应地选择个体进行操作,如下式:
式中:p1为接近于1的数;p2=exp((f-favg)/t)为关于t的递增函数,当然也与f的大小有关;p3=exp(t/(favg-f))为关于t的递减函数,本文t均指迭代数;f为个体的适应度;favg为当前种群中个体的平均适应度。这里对当前种群中的最优个体采取保存策略,即如果f=fmin,则该个体不进行重组,直接进行模拟退火;fmin为种群中个体的最小适应度。
2.1.4 基因重组
操作如下:从当前解S中随机选择2个点vi,vj从S中删除,再从vi,vj所在的簇Vi,Vj中随机选择2个不同的点加入S。
2.1.5 模拟退火
对基因重组后的个体S进行模拟退火操作如下:
1) 设定局部搜索步数。本文设定局部搜索步数与选择的簇有关,即局部搜索步数等于选择的簇中点的个数减1。
2) 邻域内局部搜索。在当前个体S的邻域中进行局部搜索,产生新个体S′。下面来解释如何进行局部搜索:对于S,随机选择一个点vl从S中删除,并将vl放入H中(H为加入过的点的集合),然后再从vl点所在的簇Vl中随机选择一个与H中不同的点加入S,这样就产生了一个新个体S′。
3) 判断新个体是否被接受。记Δf(S,S′)=f(S′)-f(S),如果Δf(S,S′)≤0,则令S=S′,否则产生一个(0,1)范围内的随机数r,如果exp(-Δf(S,S′)/T)>r,则令S=S′,T为当前的温度。这里为了实施最优保存策略,种群中的最优个体在进行局部搜索后,只有Δf(S,S′)≤0时,才令S=S′。
4) 初始温度的确定。如果初始温度设置过大,温度下降就会变慢,计算量也增加,影响算法效率。对于初始温度的选取,本文令T0=100。
5) 温度下降方式。T(t+1)=T0/(1+t)。
2.1.6 混合算法的操作步骤
综合以上各点,混合算法的操作步骤描述如下。
步骤1。初始化。采用实数编码,随机产生初始种群P,并评价个体的适应度,种群规模为Ps;计算初始温度T0,并令T=T0;令t=1。
步骤2。基因重组。对于种群P,利用式(1)选择算子①选出个体进行基因重组操作,生成新种群P′。
步骤3。模拟退火。对于种群P′,利用式(2)选择算子②选出个体进行模拟退火操作,生成新种群P″。对于要进行模拟退火操作的每一个个体,先令H=Ø,然后执行如下操作:
1) 对S进行局部搜索,随机选择S中的一个点vl,将其删除,并将vl加入H中。
2) 添加一个Vl中的不同点v′l,这样得到S′,然后再将v′l加入H中。如果Δf(S,S′)≤0,则令S=S′;否则产生一个(0,1)范围内的随机数r,如果满足exp(-Δf(S,S′)/T)>r,则令S=S′。
3) 如果H=Vl,跳到步骤4,否则返回步骤2继续局部搜索。
步骤4。种群更新。重新评价种群P″中个体的适应度,令P=P″。
步骤5。温度下降。令T=T0/(1+t),t=t+1。
步骤6。终止规则。产生一个(0,0.1)范围内的随机数rand,如果T<rand或连续迭代50次而最好解没有改进的时候,算法终止,输出当前种群中适应度最小的个体,即为近似最优解;否则返回步骤2继续迭代。
2.2改进的禁忌搜索算法
禁忌搜索(tabu search,TS)算法是局部邻域搜索算法的推广,该思想最早由Glover[11]提出,是一种全局逐步寻优算法。禁忌搜索算法是对人类智力过程的一种模拟,即人们对已搜索的地方不会立即去搜索,而去对其它地方进行搜索。所谓禁忌就是禁止重复前面的工作,它回避了局部邻域搜索陷入局部最优的主要不足,通过使用一个禁忌表来记录下已经达到过的局部最优点,在下一次搜索中,就利用禁忌表中的信息不再搜索或有选择地搜索这些点,以此来跳出局部最优,并通过特赦准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。
目前,禁忌搜索算法在组合优化、生产调度、机器学习等领域得到了广泛且成功的应用,近年来又在函数全局优化方面得到较多的研究。在本文改进的禁忌搜索算法中,通过在当前迭代点的2种邻域进行搜索来避免陷入局部最优。下面来详细描述本文的改进禁忌搜索算法
2.2.1 初始解的构造
从每一个簇中随机选一个点,共选择k个点构成初始解。即S=[vi1,vi2,…,vik],其中vi1∈V1,vi2∈V2,…,vik∈Vk。
2.2.2 评价函数
直接以每个解的目标函数值作为它的评价函数值。对于每个解,用Prim算法来求最小生成树,得到的值f(S)即为这个解的评价函数值。
2.2.3 邻域搜索
用到2个邻域结构,即N1(S)和N2(S)。N1(S)为从S中随机选择一个点vp从S中删除,并从vp所在的簇Vp中选择一个不同的点v′p加入S中,这样的v′p共有|Vp|-1个。N2(S)为从S随机选择2个点vp和vq从S中删除,并从vp和vq所在的簇Vp和Vq中选择2个点v′p和v′q加入S中,且v′p≠vp,v′q≠vq,这样的v′p和v′q的组合共有(|Vp|-1)×(|Vq|-1)个。
2.2.4 禁忌表
禁忌表是禁忌搜索算法的一个重要特征,它主要由禁忌对象和禁忌长度组成.禁忌的对象是那些引起解变化的因素,禁忌长度为禁忌对象的受禁时间,在算法中以迭代长度来表示.禁忌对象的选取:我们对当前解S每进行一次邻域搜索时,都要在1个簇或者2个簇中进行局部搜索。那么在进行完这次邻域搜索后,就将这1个簇或2个簇放入禁忌表中。对于N1(S)的情况,禁忌表记为T1,对于N2(S)的情况,禁忌表记为T2。禁忌长度的确定:对于在禁忌表中的簇,我们在一定的迭代次数内不对这些簇进行局部搜索,这个迭代次数就称为禁忌长度。对于禁忌表T1,它的禁忌长度记为L1;对于T2,它的禁忌长度记为L2。
如果禁忌对象达到禁忌长度,则取消对它的禁忌。禁忌长度的确定非常重要,如果过长,则会造成过早陷入局部最优,并且占用机器内存,但如果过短,则会造成搜索的循环。
2.2.5 特赦规则
在禁忌搜索算法的迭代过程中,会出现某一禁忌对象被解禁后当前最优值将下降的情况。在这样的情况下,为了达到全局最优,会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。本文算法的特赦规则为基于评价值的规则,即如果某个禁忌对象被解禁后,在该对象内进行局部搜索,能使得当前最小评价值降低,则将该禁忌对象从禁忌表中删除。
2.2.6 终止规则
本文给定一个最大迭代次数R,当算法达到最大迭代次数R或者连续迭代50次而最好解没有改进的时候,则算法终止。
2.2.7 算法步骤
步骤1。初始化。随机产生初始可行解S=[vi1,vi2,…,vik],并用Prim算法求其评价函数值,令t=1,T1=Ø,T2=Ø。
步骤2。N1(S)内局部搜索。从S中随机选择一个点vp。
1) 如果Vp∈T1,判断是否满足特赦规则,如果不满足,则跳到步骤3。
2) 否则将vp从S中删除,并从簇Vp中选择另外一个点v′p加入S中,得到新的解S′,求其评价函数值f(S′),判断如果f(S′)<f(S),则令S=S′;执行以上操作,直到满足Vp中的所有点均加入过S为止;令t=t+1,并将Vp加入禁忌表T1中;禁忌表长度为L1;如果禁忌对象达到禁忌长度,则取消对它的禁忌,将该禁忌对象从禁忌表中删除。
步骤3。从N1(S)跳到N2(S)。判断如果t>t1,则执行步骤4,否则跳到步骤6。
步骤4。N2(S)内局部搜索。从S随机选择2个点vp和vq从S中删除,并从vp和vq所在的簇Vp和Vq中选择2个点v′p和v′q加入S中,得到新的解S′,求其评价函数值f(S′),判断如果f(S′)<f(S),则令S=S′;执行以上操作,直到满足Vp×Vq中的所有两个点的组合均加入过S为止;令t=t+1,并将Vp,Vq加入禁忌表T2中;禁忌表长度为L2;如果禁忌对象达到禁忌长度,则取消对它的禁忌。
步骤5。从N2(S)跳到N1(S)。判断如果t>t2,则执行步骤6,否则跳到步骤4。
步骤6。终止规则。如果t>R或连续50次迭代当前最好解没有改进,则算法终止,输出当前最优解即为近似最优解;否则返回步骤2继续迭代。
3 数值实验
为了验证本文2种改进元启发式算法的有效性,将本文算法应用于新TSPLIB上的若干个实例,这些实例数据可以从http://neumann.hec.ca/chairedistributique/data/gmstp上下载。这些实例是通过对TSPLIB上的例子经过处理得到的,以便于适合本文的广义最小生成树问题。
下面介绍2种处理方法,这2种方法均由Fischetti等[12]于1997年提出。
1) 中心划分法(center clustering procedure)。
它先在n个点中找出互相之间尽可能远的k个点作为k个簇的中心点,然后在剩下的n-k个点中,把每一个点都被分配到离它最近的那个中心点,最后再就把n个点划分成了k个簇.这里k=round(n/5)。
2) 网格划分法(grid clustering procedure)。
这种方法一般适用于n个点的地理坐标(xi,yi),i=1,…,n都知道的情况,找出这n个点坐标中的xmin,ymin,xmax,ymax,那么由(xmin,ymin),(xmin,ymax),(xmax,ymin),(xmax,ymax)这4个点构成的矩形就可以把那n个点全包围起来.我们将这个矩形平均划分成g×g个网格,每个网格都满足高为(ymax-ymin)/g,宽为(xmax-xmin)/g,这里g为满足cluster(g)≥n/μ的最小整数,cluster(g)表示g×g个网格中的非空网格的个数.本文μ可取值为7,10,等等。
参数设置。单亲遗传模拟退火算法中:初始温度T0=100,种群规模Ps设为10,选择概率p1设为0.95。改进禁忌搜索算法中:中心划分法,禁忌表长度为L1=20,L2=30;网格划分法,禁忌表长度为L1=10,L2=15;迭代次数t1=80,t2=50,R=500。
表1为本文2种算法与Wang[10]中TS方法关于新TSPLIB上5个实例的数值实验结果。其中网格划分法为μ=10的情况第3列为最好值,最好值是指PGASA、TS、Wang[10]三者对同一个例子所得到的最好值(即3种方法求解同一实例所得函数值中的最小值)。由表1可见,PGASA每次都能得到最好值,TS算法的平均偏差是0.02%,Wang[10]的平均偏差是0.88%,显然本文的PGASA和TS比Wang[10]有效,且PGASA算法最有效。
4 结束语
本文提出了2种改进的元启发式算法来解决广义最小生成树问题,并且以新TSPLIB上的实例作为数据进行了数值实验,将本文提出的算法PGASA,TS与Wang[10]比较,实验结果表明本文提出的2种算法都比Wang[10]的有效,在解的质量方面,单亲遗传模拟退火算法表现要更好一些。
参考文献
[1]Myung Y S,Lee C H,Tcha D W.On the general-ized minimum spanning tree problem[J].Net-works,1995,26(4):231-241.
[2] Feremans C, Labbe M, Laporte G. A comparative analysis of several formulations for the generalized minimum spanning tree problem[J]. Networks, 2002,39(1):29-34.
[3]Feremans C,Labbe M,Laporte G.The generalizedminimum spanning tree problem:Polyhedral analy-sis and branch-and-cut algorithm[J].Networks,2004,43(2):71-86.
[4] Duin C W, Volgenant A, Voss S. Solving group Steiner problems as Steiner problems[J]. European Journal of Operational Research, 2004,154(1):323-329.
[5]Pop P C,Kern W,Still G.A new relaxation meth-od for the generalized minimum spanning tree prob-lem[J].European Journal of Operational Research,2006,170(3):900-908.
[6]Feremans C.Generalized spanning tree and exten-sions[D].Belgium:Universite′Libre de Bruxelles,2001.
[7] Pop P C. The generalized minimum spanning tree problem[D]. Netherlands: University of Twente, 2002.
[8]Hu B,Leitner M,Raidl G R.Computing general-ized minimum spanning trees with variable neigh-borhood search[C]∥Proceedings of the 18th Mini-Euro Conference on Variable Neighborhood Search,2005.
[9] Golden B L, Raghavan S, Stanojevic D. Heuristic search for the generalized minimum spanning tree problem[J]. Informs Journal on Computing, 2005(17):290-304.
[10]Wang Z,Che C H,Lim A.Tabu search for gener-alized minimum spanning tree problem[C]∥Ber-lin,Heidelberg,Yang Q,Webb G eds.PRICAI2006,LNAI,Vol.4099.Springer-Verlag,2006:918-922.
[11] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computers and Operations Reseach, 1986,13(5):533-549.
函数生成元 篇6
关键词：LISYS,MosCS,检测元,克隆算子
引言
当前的入侵检测系统要解决的关键问题是如何降低误检率和漏检率, 为此Forrest和Hofmeyr[2]将人工免疫技术引入到入侵检测中,并提出否定选择算法作为检测元生成算法。在此算法的基础上,J.Kim和P.J.Bentley根据免疫细胞克隆突变的原理提出动态克隆选择算法。本文在分析了上述两种算法的缺陷后,提出了基于单克隆算子的简单克隆选择算法,给出了该算法应用于LISYS系统的实验结果和分析。
1 检测元生成算法应用人工免疫技术的原理
1.1 免疫原理
在人体的免疫系统中,负责检测外来有害抗原的主要是被称为B-细胞和T-细胞的两种淋巴细胞。淋巴细胞通过两种方式产生:1.在胸腺或骨髓中随机产生[1];2.通过克隆选择产生。经过克隆选择产生的子B细胞含有与父代(Parent) B细胞不同的受体,因而具有不同的病原体亲和力。同时,子B细胞的部分受体与父代(Parent) B-细胞的受体具有一定的相似性,更易绑定与父代B-细胞所绑定的抗原相似的抗原,而由克隆选择过程的机制可知这些抗原正是当前大量存在于肌体的抗原。
1.2 已有算法分析
1.2.1 否定选择算法
Hofmeyr的LISYS系统采用否定选择算法来产生成熟检测元。该算法是从免疫细胞的胸腺或骨髓随机产生和耐受化过程中抽象而来。描述[2,3]如下:
a、定义一个自我模式集作为生成有效检测元的训练集;
b、产生候选检测元。通过一个随机过程来产生长度为49位的位串作为候选检测元;
c、产生有效检测元集合R,将产生的候选检测元与自我集中的模式进行匹配试验。若匹配,则丢弃该候选串,返回b;否则该候选检测元就是一个有效的检测元,进入R集合,返回b;
d、重复b,c直到产生一定数量的检测元为止。
算法的缺陷:
(1)算法是通过随机产生字符串的方法生成候选检测元集合,此时候选检测元集合的大小为整个字符串空间U=2L,大量候选检测元将在阴性选择过程中死亡,检测元成熟率较低。
(2)由随机产生字符串的方法生成候选检测元集合产生的成熟检测元的检测能力是分散的,不具有大量检测出模式相似而又在一定时期内大量频繁出现的异常行为的能力,从而导致检测效率低下。
1.2.2 动态克隆选择算法
J.Kim和P.J.Bentley认为对免疫细胞运用高突变率进行克隆是一个必要的机制,以调整当前免疫细胞达到更大的抗原绑定范围,因此,在否定选择算法的基础上提出了动态克隆选择算法。算法将被随机删除的记忆检测元存入基因库,通过对基因库中的记忆检测元进行克隆选择运算,生成新的候选检测元,再使之经历阴性选择,从而生成成熟检测元。该算法的描述[4,5]为:
If(未成熟检测元个数+成熟检测元个数<非记忆检测元集体的大小){
do{
if(被删除的记忆检测元个数>0&&突变率!=0) {
随机选择一个被删除的记忆检测元t;
对t进行突变,得到变体tt;
将tt加入到未成熟检测元群体中以受阴性选择;
} else
随机生成一个检测元并加入到未成熟检测元群体中以受阴性选择;
}while(未成熟检测元个数+成熟检测元个数<非记忆检测元集体的大小)
}
算法的缺陷:
a、算法无法保证产生最优的子代个体――候选(未成熟)检测元。由文献[6]可以得出结论:只有对具有最高亲和力的抗体群依据亲和力进行克隆操作产生大量的发生变异的子代抗体,才能确保能够在子抗体群中获得具有高亲和力的个体。该算法仅随机选择一个抗原(被删除的记忆检测元)进行突变。在基因库(被删除的检测元集)中随机选择的抗原不能保证具有最高亲和力,不能保证能够产生高亲和力的子代;同时,个体变异是随机的,父本仅产生一个子个体,该子个体具有高亲和力的几率很小。
b、产生的子代个体无法完全避免与现有的非未成熟检测元发生匹配。由于子代产生过程的随机性以及r-连续位匹配规则固有的特性可能导致随机产生的成熟检测元存在互相匹配的现象。
c、由于被删除的记忆检测元是由记忆检测元集随机选择删除的,因此被删除的记忆检测元的相对高亲和力性不确定,即不能保证基因库中基因的最优化。
2 单克隆算子的简单克隆选择算法
受动态克隆选择算法的启发,本文提出了基于单克隆算子的简单克隆选择算法(MosCS,monoclonal operator standard clonal selection algorithm)。
2.1 克隆算子(clonal operator)
本文参考生物学单、多克隆抗体对信息交换多样性特点的描述,定义仅采用变异的克隆算子为单克隆算子(monoclonal operator);交叉和变异都采用的是多克隆算子(polyclonal operator)。考虑到单克隆算子可以更多的保留父代的特征,本文采用单克隆算子。
2.1.1 基因库的进化
本文建立的基因库通过“Baldwin效应”来指导基因库进化,具体过程如下:
a、以记忆检测元集作为基因采集的对象,选择N个亲和力①最高的记忆检测元提取基因②加入基因库;
b、每当发生克隆选择操作时,转a.更新基因库。
①本文以记忆检测元绑定(匹配)异常模式(提取的二进制字串)的次数(绑定计数)作为抗体的亲和力(F)值,绑定次数越高,亲和力越高;被基因库选用的记忆检测元的绑定计数将会减半,以确保记忆检测元集的检测元有均等的候选机会。
②基因(gene)即记忆检测元用于绑定异常模式的二进制字串
设记忆检测元集为mSet={di|i =1,2, …,n ∧ n=mSet.size},,基因库为Genelib = { genei| i = 1,2,3…Genelib.MaxSize },基因库更新操作为T,则基因库的更新过程可表示为
T(Genelib)= { Gene(di)∈{Gene(d1),Gene(d2),…, Gene(dN)} | F(di)>F(dj),i≠j,i,j=1…N,i=1=1…mSet.size, ∧ dimSet };
其中genei= Gene(di)
LISYS系统的记忆检测元集是一个动态集合,当有新记忆检测元要加入集合而集合空间已满时,为了实现记忆检测器群体数目的动态平衡,必须采用一定的淘汰策略将原来的某记忆检测器淘汰,Hofmeyr和Kim等的策略是随机删除一个记忆检测器,该法简单易实现,但随机抽取的记忆检测器可能就是最近才插入的记忆检测器。本文采用“最久未使用”淘汰策略,即淘汰最久未被激活的记忆检测器,这个淘汰策略需要一个记录记忆检测器最近一次被激活的时间属性,在记忆检测器检测收集到的数据时,若出现真阳性,由该属性记录时间。这样可以保证记忆检测元集中的元素能够最大限度的保持对当前网络中抗原的绑定,从而使基因库能够提取到最适应当前网络的检测环境的基因。
2.2 克隆选择操作的基本过程
将基因库Genelib = { genei|i= 1,2,3…Genelib.MaxSize }简写为:G={G1,G2,…,Gn}
本文提出的基本操作如图1所示:
2.2.1 克隆操作TCc:定义
TCc(G(k)) = [ TCc(G1(k)) TCc( G2(k)) … TCc( Gn(k))]T
其中:TCc(Gi(k))=Ii×Gi(k), i=1,2,…n,Ii为qi维行相量,称基因Gi的qi克隆
qi=g(Nc,f(Gi(k)) )
一般取:
qi=Int[Nc×f(Gi(k))/undefinedf(Gi(k) )],i=1,2,…n,
Nc>n是与克隆规模有关的设定值; Int [﹒]为上取整函数,Int[x]表示大于x的最小整数。f(Gi(k) )为计算Gi(k)亲和力的函数。克隆后产生基因集合G′(k),
G′(k) = {G′1(k),G′2(k),G′3(k),…,G′n(k) }
其中:
G′i(k) = {Gi1(k),Gi2(k),…,Giqi-1(k) },Gij(k) = Gi(k),j= 1,2,…,qundefined
即从基因库中的基因Gi克隆出qi个新的基因Gi。
2.2.2 免疫基因操作TCg
单克隆算子的免疫基因操作只进行基因的变异操作。由Genelib通过克隆操作产生的基因是49位字串,本文确定的变异方法是对字串的前6字节任意选择M字节,在每一选中的字节中任选N位做异或操作。
设突变率为P,rand为突变随机数,则免疫基因操作可表示为:
undefined
当rand值在P的范围内则变异,反之不变异。产生的新基因集记为G"(k)。
2.2.3 克隆选择操作TCs
克隆选择操作定义:
∀i,j=1,2,…,n,∃Gs(k)={G”ij(k)|-match(Gi)∧ Gi∈G}
通过TCs操作,G"(k)中两种基因元素被清除:
a)G′(K),即未发生变异的基因。
b)G"(k)∈match(Gi),即与基因库基因互相绑定的基因。
2.3 MosCS算法描述
If(未成熟检测元个数+成熟检测元个数<非记忆检测元集体的大小) {
do{
if(记忆检测元个数>0&&变异率!=0){
if(Gs不为空){
随机选择一个Gi∈Gs,以Gi为基因创建候选检测元d;
将d加入到未成熟检测元群体中以受阴性选择;
}else{
更新基因库;
依据亲和度和设定的抗体克隆规模,进行克隆算子操作,获得集合Gs
随机选择一个Gi∈Gs,以Gi为基因创建候选检测元d;
将d加入到未成熟检测元群体中以受阴性选择;
}
}else
随机生成一个候选检测元并加入到未成熟检测元群体中以受阴性选择;
}while(未成熟检测元个数+成熟检测元个数<非记忆检测元集体的大小)
}
3 MosCS算法分析
1) 由于MosCS算法所采用的基因库从记忆检测元集选择亲和力最高的若干检测元作为基因采集对象,从而保证了基因库的基因最优化。
2) 在克隆选择过程中,通过清除与基因库基因高度匹配的子代基因可以使由子代基因生成的成熟检测元避免与已有的高亲和力检测元发生抗原绑定范围重合,提高检测覆盖率。
3) MosCS算法产生一个基因集Gs,较动态克隆选择算法只产生一个变异基因,有更高的生成更优待选检测元的几率。
4) 子代基因集Gs生成的候选检测元较随机方法产生的检测元通过阴性选择的概率更高。
5) 由子代基因集Gs生成的候选检测元较随机方法产生的检测元具有更高的特异性抗原受体,具有检测出模式相似而又在一定时期内大量频繁出现的异常行为的能力。
4 实验结果及分析
本文在202.113.76网段内使用82,83及99三台配置相同的实验机器作为检测节点,分别用5天时间做了MosCS与否定选择算法的对比实验,实验结果及分析如下。
4.1 通过阴性选择的难易度
对一定时间内用两种方法产生的检测元计算通过阴性选择的比率,设:
MosCS算法比率Pcs=通过阴性选择的检测元(MDcs)数量/产生的检测元(Dcs)总数
否定选择算法比率Pr=通过阴性选择的检测元(MDr)数量/产生的检测元(Dr)总数
参数:检测元数量上限=500,变异度=0.50,时间 120小时
参数:检测元数量上限=500,时间120小时
由表中数据可知Pcs>Pr,说明MosCS算法产生的检测元更容易通过阴性选择,其中可以发现作为基因提取对象的记忆检测元集对MosCS算法有一定的影响,集合越大,效果越好。
4.2 检测异常模式的效果
计算一定时间内两种方法产生的成熟检测元检测到异常模式数量的均值,设:
MosCS算法均值Vcs=成熟检测元检测到的NP(NPcs)总数/成熟检测元(cs)总数
随机算法均值Vr=成熟检测元检测到的NP(NPr)总数/成熟检测元(r)总数
参数:检测元数量上限=500,变异度=0.50,时间 Aug 25,2005—Aug 29,2005
参数:检测元数量上限=500,时间 Aug 25,2005—Aug 29,2005
由表中数据可知Vcs > Vr,说明MosCS算法产生的检测元绑定异常行为的效果更好。
5 结论
通过MosCS算法的分析和实验验证,MosCS相对现有的检测元生成算法在基因库的基因最优化方面有一定优势,MosCS产生的检测元更容易通过阴性选择,生成有效检测元的效率更高,同时可以显著提高检测覆盖率。
参考文献
[1]大众医药网.医学免疫学[EB/OL].http://www.windrug.com/book/book22.php.
[2]HOFMEYR S A,FORREST S.Architecture for an artificial immune system[J].Evolutionary Computation,2000,7(1):45-68.
[3]HOFMEYR,S.An Immunological Model of Distributed Detec-tion and Its Application to Computer Security[D],PhD The-sis,Dept of Computer Science,University of New Mexico,1999.
[4]KIM,J.,BENTLEY,P.J.Towards an Artificial Immune System for Network Intrusion Detection:An Investigation of Dynamic Clonal Selection[J],the Congress on Evolutionary Computation(CEC-2002),Honolulu,pp.1015-1020,May12-17,2002.
[5]KIM,J.,BENTLEY,P.J.A Model of Gene Library Evolu-tion in the Dynamic Clonal Selection[C].Proceedings of the First International Conference on Artificial Immune Systems(ICARIS)Canterbury.2002.175-182.
函数生成元 篇7
虽然早在20世纪初,就已有学者对核方法理论进行了探索[1]。但其被真正得到关注,还是在统计学习理论与支持向量机相关知识问世以后[2]。虽然核方法理论被提出的时间并不久,可是它在特征提取效率与分类泛化等方向所体现突出能力已被许多从事人工智能方向研究的学者所注意[3]。在核方法中核心是核函数的构造和选择。由于不同的核函数,其在分类等方面的性能也各有不同,因此研究者们常常将不同的核函数组合起来构造组合核函数,以期将不同的核函数的优点结合在一起,取得最佳的分类效果。但是,在这一过程之中组合核函数的组合参数的选择就至关重要,既不能使得其中某一个核函数被湮没,又必须可以达到较好的结果。在本文中,作者将RBF核函数与多项式核函数结合在一起,并选择了适当的组合参数,提出了既有侧重性又能够兼顾两种核函数特点的组合核函数。经试验验证,其综合性能较为优良。
1 基本概念
基于核函数的模式分析算法,是由核函数理论演化而来的。在未将核函数理论用于模式识别中前,模式识别只可在低维得到应用。若碰到需要高维数据分析或非线性运算,就必须使用神经网络或PCA等特征识别算法,它们在运行时需要消耗大量时间,这可以说是其主要缺点。当函数理论被提出后,其在解决非线性问题方面的优点很快就得到研究者们的注意:基于核函数的支持向量机算法(即核方法)在效率方面要优于神经网络算法[4]。
核方法的一个显著特征是其在对数据进行加工的过程中使用核投影。其在处理信号的过程中先将原始信号从信号域投影至特征域。之后在特征域中对数据执行相关的线性处理过程。因为这种非线性投影是十分复杂的,因此其处理非线性信号的能力极为突出[5]。
设有映射:
ψ:α→(ψ(α)) (1)
可得核函数:
H(α,γ)=〈ψ(α),ψ(γ)〉 (2)
其过程是这样的:①将信号用非线性方法从原空间投影至特征空间。②搜索恰当的途径对特征信号进行线性分析。
核方法其中心任务就是在信号、特征、分类三个域中进行非线性的数据变换。
设xm,xn是样本点,且xm,xn∈E,E为数据域,ψ是从数据域到特征域的投影函数,故可实现如下内积变换:
(xm,xn)→H(xm,xn)=ψ(xm)(xn) (3)
其中,变换函数ψ(.)常常是十分繁琐的,可在运算中遇到的核函数H(.,.)就要相对简单,核方法为研究人员注意的特点就是这个。将使用核函数进行信号处理的一类方法叫做核函数方法。其有以下特征[6]:
第一,其计算量和特征域的维数没有关系。使用它即可回避在变换后进行高维特征运算,从而使计算量大为下降,可有效地防止“组合爆炸”现象的发生。
第二,不须对ψ(.)具体形式与参数进行具体确定。
第三,核函数技术与确定的算法之间没有对应必须的依赖性和必然的相关性。这就使得核函数的研究与选择以及算法的开发都各自拥有了相当的灵活性。所以,核函数与算法的研发过程可以彼此分开。同时,核函数与算法也可以自由组成,进而构成不同的系统。
第四,任何满足Mercer条件的对称函数均能够被用来作为核函数。这就意味着能够使用的核函数是非常灵活的。
在日常研究工作中,以下核函数研究人员使用较多:
RBF核函数:undefined
Polynomial核函数:
K(x,x1)=(x·xi+1)d,d=1,2,…,m (5)
Sigmoid核函数:K(x,xi)=tanh(βxi+b) (6)
此外还有一些其他的核函数也是常见的。
为了使得实际应用时的运算量尽量减小,运算的复杂度尽量降低,且同时能够解决实际遇到的课题。研究者们常常在符合核函数运算规则的条件下,将不同的核函数有机的结合在一起。这样做就是为了对各种核函数的优点和缺点取长补短,取得在综合性能上最为平衡同时又实用的新型核函数。
2 支持向量机及其应用
2.1 支持向量机
在现今社会生活与工作当中,人们常常会接触到大量的数据。而在图像识别研究中,这一现象就更加明显。由于数据信号集十分庞大,使用人工对其进行分类几乎是不可能的,因此,当电子计算机问世以来,如何利用计算机对其进行自动化分类就成为了摆在研究者们面前的一个重大挑战。许多研究者都对这个领域进行了研究,提出了自己的成果。不过,这各种各样的不可胜数的分类法都是基于统计学而来的。
众所周知,在经典统计学中,其要求样本集规模是趋于无穷大的。可是在解决实际问题时,样本集的规模经常并非如此。这也就是许多方法在现实工作中效果不佳的原因所在。20世纪90年代中期,Vapnik等发明了一种新的方法—支持向量机。其在人工智能领域的优秀性能,为人工智能领域开辟出一片新天地[7]。
支持向量机是基于统计学习理论而来的。其基本原理是首先对目标区与背景区的边缘(界面)的具体特征进行训练,然后自行进行基于已训练知识的搜索,并以此定义在区别目标区与背景区方面性能突出的“向量”,利用这种“向量”来构造分类器。这样构造出的分类器,在分类性能上有着突出的优势,尤其是在逻辑推演能力和准确率方面更加引人注意。另外,SVM通过引入松弛变量来容纳错分状况这就有效地解决了线性不可分问题。
核函数是SVM的核心,不同核函数决定不同的SVM算法。通过对大量文献的总结,可以得知,构造核函数有两种常用方法:利用已知知识进行构造以及利用已有核函数组合进行构造。现在在对于核函数和SVM的参数的选择只能凭借已有知识、试验比较等方法来进行选择[8]。
2.2 支持向量机原理
有训练集{xi,yi}undefined,xi∈Rd为第i个元素,yi∈R为第i个输出值。SVM方法是构造一个最优分类函数:
f(x)=signundefined
其中,ai为符合值, b是一实常数。
对两类问题,设
undefined
则有
yi(ϕ(xi)+b)≥1 (i=1,…,n) (9)
这里,由ϕ将数据从原始域投影至特征域。对于错分情况,引进松弛变量ξi≥0 (i=1,…,n)。
因此有
yi(ϕ(xi)+b)≥1-ξi (i=1,…,n) (10)
其中,0≤ξi<1时,分类正确; ξi<1时,为错分向量。
核函数是支持向量机的核心,不同的核函数决定不同的支持向量机算法。这些算法各有不同、数量繁多,但总结起来大致有这样两类:基于已知常识和基于对已有核函数的组合。
在现在的SVM研究中,对挑选核函数和它的参数依旧没有固定规则。这一过程一般来讲,要根据经验、对比实验、遍历寻找、相互检测来确定最好选择。
3 核主元分析法
3.1 核主元分析法的基本概念
由主元分析(PCA)经过非线性推演可以得到核主元分析法(KPCA)。它的原理为:把原始信号从信号域经非线性变换从数据域投影至特征域中,再在特征域中采用PCA求得最好的投影方向,并从中取得非线性特征。KPCA方法从根本上来说,就是构造一个变换K,将原始域中数据向量An,从原始域向特征域中进行投影运算。这样做的主要目的就是提取原始域信号的特征。
设K是一个由原始域到特征域的非线性变换,An为原始信号向量,VC原始信号域,I为特征域,总信号规模为S,则有下式:
K:VC→I,An→K(An),n=1,2,…,S (11)
此式的含义为:构造一个非线性变换K将总规模为S的原始域VC变换到特征域I中,同时把原始信号向量An变换特征域中,成为其中的特征向量。
设在特征域I中有
undefined
那么其协方差矩阵为
undefined
且λZ=FZ (14)
在特征域I内,有任意非零特征值λ在相应的特征向量Z在K(A1),…,K(AS)构造的域中,故有系数kj(j=1,…,S)使
undefined
同样的
undefined
结合式(15)与式(16)
undefined
设存在S×S矩阵T,则
Tji=n(Aj·Ai)=(K(Ai)K(Aj)) (18)
由式(18)得
undefined
此处undefined由式(5)-(19)得
undefined
设矩阵T的特征值为λ1≤λ2≤…≤λS,则其特征向量是undefined令其中首个非零值是λf。
对undefined做标准化运算,并符合
(Kn·Kn)=1,n=f,…,S (21)
将式(15)代入式(21)中:
undefined
故undefined只要符合式即可有协方差矩阵undefined中归一且正交的特征向量集合。在I内计算Zn(n=f,…,S)上的投影。
设有输入信号A,那么其在I上的投影是
K(A);
位于特征向量Zn的映射是
undefined
从式(23)中,能够知道采用核函数法,可以免除在I中作内积运算的麻烦。
3.2 KPCA算法步骤
设有一个S维的数据集{an},n=1,…,S,在这个数据集中实现KPCA算法步骤如下:
①计算核矩阵N∈VS×S=[n(aj,ai)]
②对转换后的向量矩阵在向量空间中进行中心化:undefined,其中1s为
undefined
③求解undefined的特征值与特征向量。
④根据undefined对λn进行标准化,令输入待测样本是a,则位于特征域I内映射K(A)对特征向量Zn的投射是undefined。
3.3 一种可用于KPCA的组合核函数新方法
由于核方法的核心问题是核函数的选择,因为核函数的特征关乎核方法非线性运算性能的优劣。众所周知,核函数种类繁复,其特点各有千秋难以一一尽言。总的来说,可以以其推演能力将其划分为局部性核函数与全局性核函数[9]。
如图1所示,RBF核函数在局部性方面是极为突出的,它的内推性能由其参数决定。参数越大,其内推性能便越小。图2是参数p取0.1～0.5五个值的时候所得到的RBF函数曲线结果图,输入值是0.2。观察发现,其在输入值周边小范围内对数据点产生作用。
多项式核函数在外推性能方面十分突出。这种具有代表性的全面性核函数,其外推性能随函数阶数下降而升高。输入值为0.2,d取1～5五个值所得结果。观察其发现,在多项式核函数可以兼顾外野点。
由Mercer条件,可以得出这样一个结论:若干相异核函数它们线性的非负组合依然符合Mercer条件。因此可以构造这样一个组合核函数来满足这一条件。这个核函数有如下特点:由不同的核函数的内推与外推性能相异,它们的学习和推演性能也互不相同、各有千秋。为发挥它们各自的特点取长补短,采用加强组合在一起以使之同时兼具两者的特点,即得:
Kn=αKp+βKR (24)
为了使得所得的新函数同时拥有全面与局部两种特点,因此将α与β之和取为1。可是众所周知的是这两种特性是彼此不相容的。如果想要在同一核函数中兼顾这两种特性是不可能的。所以在设置α与β的具体取值范围和具体值要有所侧重。为使核函数侧重于全面性方面,就将α与β的取值范围定为α∈(0,0.1),β∈(0.9,1);为使核函数侧重于局部性方面,就将α与β的取值范围定为α∈(0.9,1),β∈(0,0.1)。但为防止全面特征与局部特征由于叠加而消失,在实验中取α=0.99,β=0.01以及α=0.01,β=0.99两组系数。这两种方法,前者侧重于全面性,后者侧重于局部性。
4 算法实验与结果分析
4.1 系统的构建与实验结果
本文理论推导与分析都是基于实践编程,实验所用计算机CPU为2.0GHz,内存为512MB,实验平台为Microsoft Windows XP,编程工具Visual C++6.0/MFC,编程语言为C++/C,在提出的系统中使用支持向量机来作为分类器。这一支持向量机(SVM) 系统是运用台湾林志仁先生研发的LibSVM软件包开发的。该软件包具有操作简易、使用方便、运行快速以及效果明显等特点,因此在相关研究领域被广为采用。经多次实验选择惩罚因子C=1000,σ2=10,效果最佳。设定好参数后可以经训练接口svm_train对输入向量进行训练,再对测试输入使用svm_predict进行加载。本文实验所采用的人脸库为ORL库,它含有400张256级灰度图像,分辨率为92×112。 其拍摄于40人,每人各有10张图片。这400幅图人脸正面或略微偏转图像,背景为相近的暗背景。但每个人的每张图片是其拍照时间、拍照光照、头部姿势(上抬、下俯、左转和右转)、人脸表情(闭眼、睁眼;有笑容、平静)和人脸遮挡(戴或不戴眼镜)各不相同,所以在姿势、光源条件、表情以及遮挡物方面各有变化。另外,每个人的10张图片中只含有上面变化中的一两种。
为使实验误差减到最小,在实验中对所有的训练集和检测集中图像,都进行相同的零均值、标准偏差以及直方图均衡化处理,以尽量在相同条件下进行实验测试。 在实验的过程中先应用小波变换算法来对原图像集进行处理抽取其中低频子图特征信息,并将其按行排成列向量,组成特征向量。然后,将图像特征向量输入支持向量机当中进行训练。
在对文中提出的系统进行实验中,步骤如下:
第一,将其中每人的10张图进行随机抽取5张,将它们组成训练集,剩余图像组成测试集。
第二,对训练集与测试集中每幅图像均进行同样的预处理,使实验误差减到最小。
第三,使用其中训练集对系统进行训练,求取训练时间。
第四,训练完成后,对测试集进行测试,取得每种系统对于相同条件下的检测样本的识别率与识别检测时间,从而比较各系统的性能。
实验结果如表1所示。
4.2 对实验结果的讨论
第一,因为不同的核函数其特性亦不一样,为了将它们的优点结合起来,选用RBF与多项式两种核函数结合在一起组成新的核函数,这样就可以兼顾全局性和部分性两个方面。在实验中,使用了上文所提到两种组合核方法。由表1可知,这种方法比系统①在识别率方面有较大的提高。但因为进行运算时须对两个核函数同时进行,使运算量有一定提高,因此其训练时间有所上升。
第二,在系统④改进小波变换+核主元分析(Cmbination Kernel Poly based)+SVM(gamma=1)与系统⑤改进小波变换+核主元分析(Cmbination Kernel RBF based)+SVM(gamma=1)中,同时使用小波改进算法与组合核方法来搭建系统。其中系统③小波变换+核主元分析(Cmbination Kernel)+SVM是对比实验,系统④是以多项式核函数为主构造的(α=0.99,β=0.01),系统⑤是以RBF核函数为主构造的(α=0.01,β=0.99)。经试验验证,其在识别率方面较系统①提高1%以上,但运算速度有所降低。
5 结束语
通过对支持向量机的有关知识,尤其是核主元分析法的相关知识进行了较为深入的探讨,提出了一种新的基于核主元分析法的组合核函数算法以用于分类识别。经对比实验验证,本文所述的小波改进算法与组合核函数相结合的算法是一种可有效提高人脸识别率,同时检测速度较为迅速的算法,其综合性能较为突出。
参考文献
[1]吕宁,刘少波,于晓洋.一种复合KPCA故障诊断模型[J].中北大学学报:自然科学版,2009,30(6):555-560.
[2]郭守团.基于支持向量机的组合核函数及模糊系统辩识研究[D].四川:西南交通大学,2010.
[3]丁子春.基于支持向量机的多领域自适应分类方法研究[D].湖北:武汉理工大学,2009.
[4]任东,于海业,王纪华.基于线性组合核函数支持向量机的病害图像识别研究[J].农机化研究,2007,9:41-43.
[5]蒋刚,肖建,郑水康,等.基于统计学习理论的海色遥感叶绿素浓度反演方法[J].中国海洋大学学报,2006,36(4):559-563.
[6]陆阳,王海燕,田娜.组合核函数支持向量机在水中目标识别中的应用[J].声学技术,2005,24(3):144-147.
[7]瞿娜娜.基于组合核函数支持向量机研究及应用[D].广东:华南理工大学,2011.
[8]袁见,李国辉,徐新文.一种基于组合核函数支持向量机的水下目标小波特征提取与识别方法[J].小型微型计算机系统,2007,28(10):1891-1897.