免疫记忆克隆选择算法

2024-07-17

免疫记忆克隆选择算法（精选5篇）

免疫记忆克隆选择算法篇1

0 引言

电力系统无功优化是指从优化运行的角度调整系统中各种无功控制设备的参数,在满足节点正常功率平衡及各种安全指标的约束下,使目标函数最小化的过程[1]。它对保障电压稳定、降低系统有功损耗具有重大意义,是实现系统安全和经济运行的重要手段之一。

从本质上讲,无功优化是一个多变量、多约束的混合非线性规划问题,含有大量的连续变量和离散变量[2]。目前求解无功优化的方法很多,可分为传统数学方法和现代启发式算法。传统数学方法有:简化梯度法[3]、内点法[4]、非线性规划法[5]等,这类方法有一定的优越性,但计算较为复杂,不方便处理离散变量,且易陷入局部最优解。随着计算机运行速度的提高和人工智能的发展,越来越多的现代启发式算法在无功优化中得到了应用,如遗传算法[6]、免疫算法[2,7]、蚁群算法[8]、搜索禁忌算法[9]、粒子群算法[10]、模拟退火算法[11]等,且都取得了一定的成果。

本文结合克隆选择算法搜索速度快,寻优能力强的优势,以及免疫记忆学说保持抗体均匀性和多样性出色的特点,提出了一种免疫记忆克隆选择算法(Immune Memory Colonial Selection Algorithm,IMCSA),并将其应用于求解电力系统无功优化问题。该算法同时具备全局均匀搜索能力和局部精确寻优能力,搜索速度快,寻优能力强,所得解集有良好的均匀性和多样性,可以有效抑制寻优过程中出现的退化现象。此外,目前多目标无功优化的目标函数绝大部分采用加权叠加比较的评价方法。本文采用归一化处理后的目标函数值与理想点欧氏距离的大小来评价解的优劣性,有效降低了决策结果对权重选取的依赖性。

1 多目标无功优化数学模型

1.1 目标函数

综合考虑系统运行的经济性和安全性,本文选取系统有功网损最小、节点电压平均偏移量最小以及静态电压稳定裕度(Voltage Stability Margin,VSM)最大作为目标函数。

(1)系统有功网损

式中:i,j为支路k两端节点编号;Ui、Uj、δi、δj分别为节点i,j电压的幅值和相角;Gk(i,j)为支路k的电导;NL为网络支路总数。

(2)电压平均偏移量

式中:Vb为节点b的实际电压值;Vbideal为节点b的期望电压值;δVb为节点b允许的最大电压偏移量;n为网络节点总数。其中函数

(3)静态电压稳定裕度

文献[12]提出以收敛潮流雅可比矩阵的最小奇异值作为度量系统静态电压稳定裕度的指标,并通过计算分析验证了该方法的有效性。本文将静态电压稳定裕度最大作为目标函数之一,即

式中:Jacobi表示收敛潮流雅可比矩阵;eig(Jacobi)表示雅可比矩阵的所有特征值;min|eig(Jacobi)|表示将雅可比矩阵所有特征值取模后其中的最小值。

因此无功优化的目标函数为

1.2 约束条件

等式约束条件为潮流方程,即

不等式约束可分为控制变量约束和状态变量约束,其中控制变量约束为

状态变量约束为

式中:Ug为发电机端电压;Qc为无功补偿电容器容量;T为可调变压器的变比;Qg为发电机注入无功;V为各节点的运行电压;Ugkmin(Ugkmax)、Qcjmin(Qcjmax)、Timin(Timax)、Qgkmin(Qgkmax)、Vimin(Vimax)分别表示以上变量所对应的最小(最大)值。

2 多目标函数评价

多目标无功优化的目标函数之间存在相互矛盾性,因此很难找到一个解,可以使各目标函数同时达到最优,如何评价这些解的优劣性是该问题求解的难点之一。目前绝大部分算法采用加权叠加比较的评价方法。针对该方法不能很好地反应各目标函数优劣性的缺点,本文将各个解所对应的目标函数值,经归一化处理后映射成多维解空间中不同的坐标点,而后利用这些坐标点与理想点欧氏距离的大小来评价解的优劣性,有效降低了决策结果对权重选取的依赖性。具体操作如下。

多目标函数min(F)=min(f1,f2,f3,…,fn)存在一组可行解x1,x2,…,xl,则每个解对应的多目标函数可表达为

(1)将目标函数值构建为目标函数矩阵

(2)对目标函数矩阵进行归一化处理

其中

(3)求取目标函数理想点。所谓理想点即归一化矩阵中f1',f2',…,fn'对应的最小值,则该点的坐标为(min(f1'),min(f2'),…,min(fn'))。

(4)评价各个解的优劣性。本文采用各目标函数值与理想点欧氏距离的大小来评价解的优劣性,第i个解与理想点的欧氏距离可用式(13)计算。Ψi越小表明该解越优。

3 免疫记忆克隆选择算法

3.1 自适应克隆

本文采用了自适应克隆操作,抗体克隆规模依据拥挤距离[13]来自适应地调整,也就是拥挤距离越大者,克隆规模就越大,被搜索的机会越多,从而实现了种群的扩张,也更好地保证所得最优解的均匀性。其具体操作如下。

将抗体群A(it)={V1,V2,V3,…,Vm}中抗体Vi=[xi1,xi2,xi3,…,xin]以比例qi进行克隆,其中

式中:Nc为与克隆后的规模有关的设定值,本文中取Nc=200;idis为拥挤距离;round[]表示取整为最近的整数。

则克隆后的抗体群将变为

3.2 交叉重组

为进一步增强种群多样性,提高算法收敛速度,本文引入了交叉重组算子,实现了抗体间的协作,促进了不同抗体间信息的交流。其具体操作如下:

若将抗体群A(it)={V1,V2,V3,…,Vm}中的抗体Vi=[xi1,xi2,xi3,…,xin]和Vj=[xj1,xj2,xj3,…,xjn]进行交叉重组,xik,xjk(i≠j;k=1,2,…,n)分别是抗体Vi,Vj的第k个决策变量,交叉重组后的取值为

式中

r和u均是(0,1)之间高斯分布的随机数;ηc是交叉指数参数,本文中取ηc=15。

3.3 非一致性变异

本文引入了可以将变异范围和进化代数相联系的非一致性变异算子[14]。使得演化初期算子在较大的范围进行全局均匀搜索,加快寻优速度;而随着演化的推进,变异范围越来越小,实现精确的局部寻优。其操作如下:

若抗体V=[x1,x2,…,xk-1,xk,…,xn]是一个变异父解,分量xk被选定进行变异,若xk为抗体V的实数编码部分,则变异后的xk变为

若xk为抗体V的整数编码部分,则变异后的抗体V的xk变为

式中:it为当前代数;gmax为最大进化代数;r为[0,1]上的一个随机数;buk表示所选分量xk取值的上界;bdk表示所选分量xk取值的下界;rnd(2)表示随机进行模2运算;round[]表示取整为最近的整数。

3.4 抗体群更新

依据本算法的选择策略,当进化达到一定代数时,非支配抗体个数可能会有很多,这样会导致运算速度变慢。为了避免该情况发生,本算法采用抗体群更新操作。若克隆选择出的非支配抗体超过了一定数目Nn,则可将Pareto-前端上较为密集的地方所对应的抗体删除,从而在保证算法运算速度的前提下,很好地保证了所得解分布的均匀性[15]。其操作如下。

(1)给出当前抗体群规模Nnon(it),期望保留的抗体数Nn,目标函数的维数m,初始化i=1,j=1。

(2)依据第i个目标函数值大小将抗体群升序排列,将最小和最大函数值所对应的抗体分配无穷大的适应度值,即ci1=NN,cim=NN,并计算其他抗体的适应度值:

其中:(F(A(it)))(j+1,i)表示抗体aj+1(it)的第i个目标函数值;it表示进化代数。

(3)若i=m,转步骤(4);否则,令i=i+1,返回步骤(2)。

(4)若j=Nnon(it),转步骤(5);否则,令j=j+1,i=1,返回步骤(2)。

(5)计算第j(j=1,2,…,Nnon(it))个抗体的适应度值:f(cj)=c1j+c2j+…+cmj即为该抗体的适应度函数。

(6)若Nnon(it)=Nn,则停止;否则,转步骤(7)。

(7)删除适应度函数最小的一个抗体;令Nnon(it)=Nnon(it)-1,i=1,j=1,返回步骤(2)。

3.5 记忆单元

记忆单元是由特定抗体组成的抗体群。本文将当前代所保留的精英个体(即下一代寻优的初始解)作为记忆单元保存,并于下一代抗体变异完成后,将疫苗植入种群。从而保证了种群多样性,并且可以有效防止寻优过程中出现的退化现象。

4 基于免疫记忆克隆选择算法的无功优化

4.1 抗体的编码和解码

本文取发电机端电压Ugi,无功补偿装置的投切档位qci,变压器分接头的可调档位ti为控制变量,即抗体。其中,发电机端电压可以为额定范围内的任意实数,而无功补偿装置的投切档位和变压器分接头的可调档位都是按整数变化的。为与实际运行情况相符,采用了整、实数混合编码方案。则抗体可表示为

式(21)所表示的发电机端电压、无功补偿电容器容量及变压器实际变比所对应的解码方式为

式中:△qci和△ti分别表示无功补偿器的单步长容量和变压器分接头的步进量;Ugi的初始值由式(23)生成。

Qci和Ti的初始值由式(24)生成。

式中:rand为介于0和1之间的随机数;round[]表示取整为最近整数。

4.2 算法流程

免疫记忆克隆选择算法应用于多目标无功优化的流程如图1所示。

5 算例分析

本文选用IEEE-14和IEEE-118节点测试系统进行多目标无功优化计算来验证所提出算法的可行性和有效性。用Matlab语言编制了免疫记忆克隆选择算法和系统潮流计算程序。算法中抗体群初始规模为50,最大迭代次数为100。

5.1 IEEE-14节点系统算例

该系统包含5台发电机、3台可调变压器、1个无功补偿点。各发电机端调压范围为0.95~1.05。各可调变压器上下档位数为±16,步进量为0.625%,其变比范围为0.9~1.1。无功补偿点(节点9)的无功补偿上限为0.5,分段步长为0.1。以该节点系统为例,将本文算法独立运行30次,其优化结果如表1所示。

将所得最优解平均值与其他算法应用于IEEE-14节点系统的结果进行了比较,如表2所示。

5.2 IEEE-118节点系统算例

该系统包含54台发电机、8台可调变压器、14个无功补偿点,其中各节点的无功补偿上限和补偿量参见文献[16],以该节点系统为例,将本文算法独立运行30次,其优化结果如表3所示。

将所得最优解平均值与其他算法应用于IEEE-118节点系统的结果进行了比较,如表4所示。

5.3 分析与比较

本文提出的算法有良好的稳定性,在多目标无功优化问题中应用效果明显,较免疫算法[2]、混沌免疫算法[17]、自适应遗传算法[15]可更好地找出全局最优解,进而有效降低了有功网损,提高了系统电压稳定指标,满足了实际工程需求。

6 结论

结合免疫记忆学说和克隆选择原理,本文提出了一种解决多目标无功优化问题的免疫记忆克隆选择算法。该算法同时具备全局均匀搜索能力和局部精确寻优能力,搜索速度快,寻优能力强,所得解集有良好的均匀性和多样性,可以有效抑制寻优过程中出现的退化现象。选用目标函数值与理想点的欧氏距离替代了现有绝大多数算法中各目标函数值加权叠加的评价方法,降低了决策结果对权重选取的依赖性。以IEEE-14和IEEE-118节点测试系统为例进行仿真计算,验证了该算法的正确性与可行性。

免疫记忆克隆选择算法篇2

随着互联网的高速发展, 网络上的信息也成指数增长, 为了从海量的Web信息中获取用户所需要的信息, 人们主要是借助于搜索引擎。CNNIC[1]2013年7月发布的报告称:中国网民中使用搜索引擎的比例为79.6%, 使用搜索引擎的用户规模达47 038万人。在各类网络应用中, 搜索引擎的使用在各类网络应用中稳居第二。而85%的搜索引擎使用者只会查看返回结果的第1页的内容, 也就是排名前10的查询结果[2,3]。而在检索结果中靠前的网站能得到更大的访问量, 增加网站的知名度, 增加广告等收入等。

因此, 有些网站就会采用不正当的手段来提高网页在搜索引擎中的排名, 这种以欺骗搜索引擎来获得较高排名的方法, 被称为搜索引擎作弊或网页作弊[4], 这样的网页被称为作弊网页或垃圾网页。垃圾网页不仅严重降低了搜索结果的质量, 使用户对搜索引擎提供商失去信任, 也使得人们花费更多的时间去寻找到有用的信息。同时也会浪费掉搜索引擎提供者大量的计算资源与存储资源, 对搜索引擎公司的物力与财力都是巨大的损失。

网页作弊技术分为两大类[4], 分别是提高评分技术和隐藏技术。提高评分的作弊技术可分为内容作弊和链接作弊, 隐藏作弊分为掩盖作弊和重定向作弊。随着互联网的发展, 网页作弊技术也越来越先进, 给垃圾网页的检测带来更大的难度。本文研究提出的使用基于克隆选择分类算法CSCA (Clonal Selection Classification Algorithm) [5]的垃圾网页检测技术, 利用人工免疫系统的识别、学习、记忆、自适应等特点, 在数据集WEBS-PAM-UK2006[6]的实验结果表明该技术能有效地检测垃圾网页。

1 相关工作

早在2002年Henzinger等人就指出, 网页作弊是搜索引擎面临的主要挑战之一[7], 为此, 国内外学者对垃圾网页的检测作出了大量的研究。Fetterly等[8]认为能通过一些统计特性来检测Web Spam。研究发现Spam页面的URL的点号、短划线、数字及长度等具有正常页面相比不寻常的值, 同时, Spam页面的内容也会经常变化。另外, 通过网页的入链及出链数目可以发现大量的作弊网页。垃圾网页检测可以看作是一个分类问题, 将一个网页分为正常或者垃圾页面。Abernethy等[9]利用内容和链接特征并运用SVM算法能有效地检测垃圾网页。Prieto等[10,11]提出基于C4.5分类器的Web spam检测系统SAAD (Spam Analyzer and Detector) 。Arauio等[12]提出了一种结合链接特征与语言模型的检测垃圾网页的分类器, 取得了不错的检测效果。

以上这些检测方法大多使用传统的分类器, 而要提高垃圾网页的检测效果, 通常是通过改进现有分类器或寻找新的适用于垃圾网页检测分类器。近年来, 人们从生物系统获取灵感, 越来越多的新方法被用于机器学习, 而这些方法在垃圾网页检测的应用中并获得不错的检测效果。Taweesiriwate等[13]提出了基于链接的蚁群优化学习算法用来检测spam host, 并能在spam和normal的识别上获得很高的精准率。Goh等[14]将网页的链接特征和内容特征输入多层感知神经网络, 利用其灵活的结构和非线性变换等特点能有效地检测垃圾网页。Zitar等[15]将遗传算法结合到人工免疫系统中进行垃圾邮件检测能获得比商用反垃圾软件更好的效果。Mahmoud等[16]用基于人工免疫系统的克隆选择来进行SMS spam的检测, 该方法能有效地区分正常短信与垃圾短信。诸多研究表明基于人工免疫的分类方法有着很好的分类特性, 在垃圾邮件的检测中, 用垃圾邮件和正常邮件训练分类器获得能识别邮件类别的检测器, 而垃圾网页与垃圾邮件有着许多类似的特征, 如热门词比例、单词平均长度等, 在本文中利用这种新兴的机器学习方法, 将人工免疫系统应用于垃圾网页的检测中, 实验表明这是一种有效的垃圾网页检测方法。

2 基于免疫克隆选择的垃圾网页检测算法

2.1 免疫克隆选择原理

人工免疫系统是基于生物免疫系统, 用来抵抗身体遭受的外部入侵的病原体, 如细菌、病毒等[17]。入侵的病原体就被称为抗原, 引起免疫系统产生的免疫细胞就称为抗体。抗体通过与抗原的特异性结合来消灭抗原。抗原与抗体之间的匹配程度被称为亲和度, 如果亲和度高, 那么抗原就将位于抗体的识别区内[18]。如果抗体能有效识别抗原, 那么它将成为记忆细胞, 在系统再次遭受同一类抗原入侵时, 系统就能通过记忆细胞快速作出二次免疫应答。

克隆选择的基本原理是能有效识别抗原的抗体才能进行克隆增殖, 即与抗原具有越高的亲合力的细胞能产生越多的后代。克隆选择算法就是通过候选解集的变异, 并由亲和度进行解集的筛选。克隆选择算法是全局优化搜索的算法, 同时具有全局搜索和局部搜索的功能, 有较好的记忆功能和收敛特性, 通过构造记忆细胞产生局部最优解, 最终形成全局最优解群体。

2.2 特征选择

特征选择主要是过滤掉一些不相关的或者冗余的特征, 以获取最有区分度的特征来提高检测系统的性能, 如果使用的特征较少就能减少算法的计算量, 节省资源。有许多经典的特征选择算法包括χ2 (Chi-squared) [19], SVM, IG (Information Gain) [20]等。文献[20, 21]比较了各类特征选择方法在文本分类中的效果, 证明了χ2和IG是比较有效的特征选择方法, 在本文中我们对比了基于χ2的特征选择方法和基于IG的特征选择方法在本检测方法中的效果。

基于χ2的特征选择方法是利用χ2统计原理, 通过计算特征的χ2值来选择特征。χ2值的计算方法如下:

其中, n是网页样本的类别数, m是特征值的区间数。Aij是第i个区间, 第j类别的样本数。Eij=Ri×Cj/N是Aij的期望值, 其中的Ri是第i个区间的样本总数, Cj是第j类别的样本总数, N是总的样本数。

当每个特征的χ2值被计算出来后, 将特征按χ2值由高到底排序, χ2值越高的特征越具有区分度。

基于信息增益的特征选择方法是通过计算特征对类别的信息增益, 反映的是特征出现前后的信息熵之差, 特征t的信息增益计算如下:

式中H (C) 为整个分类系统的熵, 表示为:

其中n为网页类别的数目, P (Ci) 为该类别网页所占比例。条件熵H (C|t) 表示为:

其中m为特征t的取值的数目, P (Ci|t=tj) 表示特征t取值为tj是属于类别Ci的概率。

同样地, 每个特征对类别的区分度由信息增益值决定, 特征选择时按信息增益值由高到低进行选择。

2.3 基于克隆选择分类算法的垃圾网页检测

克隆选择算法是一种基于免疫系统中克隆选择理论设计的免疫算法, 基于克隆选择原理的克隆选择分类算法CSCA最早由Jason Brownlee[5]提出, 是一种有效的机器学习方法。本文提出的垃圾网页检测方法基于克隆选择分类算法, 基于免疫克隆选择的垃圾网页检测方法的总体结构如图1所示。

免疫系统概念与检测算法的对应关系如表1所示。

算法的最终目的是生成能检测垃圾网页的记忆细胞集。算法中所有的抗体、抗原和记忆细胞都由向量表示, 定义如下:

其中, vij (j=1, 2, …, r) 是特征值, C是类标。对于网页, C表示的是垃圾网页或正常网页;对于抗体, C表示的是抗体能识别的网页类型。

算法详细步骤如下:

(1) 初始化

将所有网页样本作为抗原, 添加到抗原集AG中。从抗原集中随机选择S个抗原添加到抗体池AB中, 作为初始抗体池。

(2) 进行G次迭代

(1) 计算抗体池AB中每个抗体的适应度值fitnessi, 适应度值反映了分类器最大化准确率的优化问题, 就将分类问题表示为函数优化问题。计算方法如下:

其中, correcti表示第i个抗体识别正确的抗原数, 即识别出的抗原与抗体类别相同。incorrecti表示第i个抗体识别错误的抗原数, 即识别出的抗原与抗体类别不相同。对每个抗原找到与其最匹配的抗体, 就表明这个抗体识别到了该抗原。抗原与抗体的匹配程度由亲和力affinity度量, 亲和力affinity是由欧几里得距离进行度量的, 反映的是抗体对抗原的识别程度。计算方法如下:

其中, ag.vi表示抗原ag的第i个特征值, ab.vi表示抗体ab的第i个特征值。

然后将所有的抗体加入到候选集AB*中, 再按以下规则进行精简:

i.将候选集AB*中错分数incorrect为0的抗体从AB*中剔除。

ii.若抗体的正确分类数correct为0且错分数incorrect大于0, 则将他们的类标改为它们所识别的最多的抗原的类标。然后计算它们的适应度值。

iii.若抗体的适应度值低于阈值ε则将该抗体从候选集AB*以及抗体集AB中剔除。

(2) 对候选集AB*中的抗体再进行克隆和变异, 抗体的克隆个数为num Clonesi, 克隆的规模由抗体的适应度决定, 若抗体适应度值高, 克隆数目就大, 反之就小。克隆数目由下式计算:

其中, fitnessi为抗体的适应度值, n为AB*中总的抗体数目, α为克隆比例因子。

抗体的每个属性能变化的范围由它的适应度值来决定。每个属性的变异范围rangei由公式得出:

其中, ri为该属性的属性值范围。

(3) 新产生的克隆体添加到抗体集AB中, 同时随机选择n个抗原添加到AB中以保持抗体集的多样性。

(3) 记忆细胞的生成

再次计算抗体集AB中所有抗体的适应度值, 若抗体的适应度值低于阈值ε则将该抗体从抗体集中剔除。剩余的抗体添加到记忆细胞集MC中。

(4) 分类

对未知样本采用K-Nearest Neighbors分类算法进行判别, 即该样本的类别由记忆细胞集MC中与它最匹配的K个记忆细胞投票决定。

3 实验结果分析

3.1 数据集及评价指标

本实验采用WEBSPAM-UK2006数据集, 这些数据由米兰大学Web算法实验室于2006年5月收集, 并作为首届Web Spam Challenge使用的数据集。这是一个基于host页面的公共数据集, 所有的这些网页均是随机爬取自.uk域名, 包括spam页面和non-spam页面。其中spam页面有1978个而non-spam页面有6511个, 这是一个不平衡的数据集。数据集包含直接特征、内容特征和链接特征, 共139个。基于内容的特征包括网页标题长度、网页中含有的词数、平均单词长度、可见文本所占的比例等;基于链接的特征包括网页的入链数、出链数、PageRank值、TrustRank值等;直接特征包括host的page数、host name的字母数。

实验采用十倍交叉验证的方法, 将数据集分成十分, 每次用其中一份做测试, 其余九份用作训练。分类结果的评价方法采用召回率 (Recall) 、精准率 (Precision) 和F-Measure值来衡量。其中, 召回率是指实际为垃圾网页中预测正确的网页的比例, 精准率是指预测为垃圾网页中的实际为垃圾网页的比例, 而F-Measure值是取的召回率和精准率的一个平均, 它的计算方法为:

3.2 检测结果分析

为了比较两种不同特征选择方法对本检测算法的性能影响, 我们在数据集上作了测试, 由于数据集的不平衡性, 我们通过随机选择的方法从6511个non-spam样本中选择出1978的样本与全部spam样本组成平衡数据集。本实验中设置参数为G=8, S=100, α=1.0, ε=1.0, k=1。表2为测试结果。

从表2可以看出, 在特征数目为10至30个时, χ2方法在分类器上获得比IG方法更高的精准率, 但召回率略低;在特征数为10、20、40、60等数目较少时, χ2方法在分类器上获得更好的F-Measure值, IG方法仅在特征数为30、50、70、80、130时F-Measure值略高;χ2方法在特征数为60个时, 获得最好F-Measure值87.9%, 而IG方法需在特征数为80个时, 获得最好F-Measure值88.0%, 整体上说, 这两种特征选择方法在本检测算法中获取着相似的效果。

为了测试本算法的性能, 我们还与经典的分类算法Na6ve Bayes进行对比。同时, 实验数据采用在对比特征选择方法实验中平衡后的数据集。本检测实验中设置参数为G=8, S=100, α=1.0, ε=1.0, k=1。同时, 实验中的特征是按χ2值从高到低进行选取的。图2至图4为两种检测算法在不同的特征数下的实验统计结果。

从图2可以看出两种方法的召回率都随着特征数的增加都趋于减少, 但本检测方法的召回率要明显高于Na6ve Bayes。从图3可以看出在精准率上, 两种方法都随着特征数的增加都趋于平缓, 本方法要比Na6ve Bayes稍低一点。原因在于免疫克隆选择算法的动态检测机制, 使得被漏检的垃圾网页数目减少。抗体的适应度阈值的设定, 它体现了抗体的进化程度即问题的解的优化方向。其次, 训练时的迭代次数也会影响系统的动态性, 如果迭代次数过少会造成特征的遗漏, 而过多会产生冗余, 都会影响判断的准确度。

从图4可以看出, 本方法的F-Measure要明显高于Na6ve Bayes, 而且比较平缓稳定。本检测方法在特征数为40至60时, 可获得较高的召回率、精准率和F-Measure值, 能以较少的特征获得比较好的检测效果, 同时F-Measure最高可达87.8%, 而Na6ve Bayes最高仅能达到86.2%, 说明本方法用于检测垃圾网页优于Na6ve Bayes算法。

4 结语

本文利用新兴的机器学习方法, 提出了一种基于免疫克隆选择的垃圾网页检测方法, 通过在WEBSPAM-UK2006上的实验表明, 本研究方法能有效地进行垃圾网页的检测。今后的研究将从以下方面继续研究:对算法进行改进或寻求新的算法使之能适用于不平衡数据集的处理。利用遗传算法等改进现有的免疫克隆选择算法以提高检测效果。

摘要：垃圾网页是指一些网页通过不正当的手段来误导搜索引擎, 使网页获得高于其应有的排名, 从而获得更多的访问量。它不仅降低了网页的质量, 同时也导致了严重的Web信息安全问题。传统的垃圾网页检测通常使用经典的机器学习方法包括贝叶斯算法、SVM、C4.5等, 这些算法对垃圾网页的检测有一定的效果。在前人的研究基础上提出一种基于免疫克隆选择的垃圾网页检测方法。利用人工免疫系统的自学习及自适应能力来检测利用新作弊技术的垃圾网页, 并与广泛用于垃圾网页检测的贝叶斯算法对比。实验表明该方法能有效、可靠地检测出垃圾网页。

免疫记忆克隆选择算法篇3

启发式随机搜索在解决单目标的优化计算中取得了优异的成果, 这种方法不依赖于问题的连续性和可导性, 可以解决非线性、多峰函数的寻优计算, 且计算的难度也要远远小于传统方法。然而, 在工程实际中, 往往很难仅凭借单项指标来衡量某项决策的好坏, 因此即需引入多项指标来更为全面地评价相应决策。但是若使用多个性能泛函来评价一个事物时, 多个性能指标往往相互制约、且相互矛盾, 也就是一方的收益多会导致另一方的利益受损。我国以崔逊学、郑金华为代表的多目标进化算法学者, 于2006年先后发表了相关理论研究成果, 算法的进化方式则是依靠交叉和变异的有性生殖。随着免疫学的进步, 脊椎动物的免疫机理正逐步引入到进化计算的思想中, 本文即借鉴免疫机理, 模仿脊椎动物的免疫应答过程来实现多性能泛函的寻优计算。

1 多目标优化算法

1.1 多目标优化问题描述

多目标优化问题 (MOP) 可用如下数学表达式描述:

给定决策向量X= (x1, x2, …, xn) ∈Ω, 且满足下列约束:

设有r个优化目标, 但这r个优化目标却相互矛盾, 一方的增益会导致另一方的利益受损, 则该优化目标可以表示为:

寻求X*= (x1*, x2*, …, xn*) 使得F (X*) 最优, 且满足式 (1) 的两个约束条件。

1.2 生物免疫

免疫是复杂生物的一种生理机能, 生物通过这种机能来保护自己不受外来物 (细菌、病毒、致敏源) 或本身有害细胞 (肿瘤细胞) 的侵袭。1920年之后, 免疫学的理论研究进入到了免疫化学的研究阶段, 在这之后生物免疫系统诞生了两个重要学说。其中, 一个是1960年Burnet和Medawar的克隆选择学说, 这一学说解释了当抗原进入生物体后, 生物体如何对其进行识别, 并产生免疫应答和免疫记忆的过程;另一个则是Jerne提出的免疫网络学说[1]。这两种学说清晰阐明了免疫过程作用机理, 具体如图1所示。

图1即为免疫应答过程的简化流程示意图。当抗原被识别后, 效应T细胞和浆细胞进行克隆, 产生抗体并杀死抗原, 同时抗原数量又能反作用于抗体, 并且限制抗体的数量[1]。而在免疫应答过程中, 将会产生免疫B细胞, 这样就能在抗原再次刺激时快速发起杀死抗原的效应, 这一过程则称为免疫记忆。该过程也为算法提供了借鉴意义, 即对于一个多目标问题, 每一代进化均应保留一定数量的精英个体。

1.3 多目标人工免疫

人工免疫系统 (Artificial Immune Systems, AIS) 是一种模仿生物体免疫系统的智能方法, 这一过程主要包括免疫应答和免疫记忆[2]。AIS的研究最初起始于上世纪80年代, 并伴随着人们对生物免疫系统的深入研究而获得了稳步发展。近年来, 越来越多的学者团体投身免疫计算的研究, 所取得的异体检测与识别、未知异体学习与记忆、异体消除和系统修复等理论成果均已应用到了智能网络、故障诊断以及智能机器人等一众领域, 并获得了很好的效果。然而, 针对多目标优化的免疫算法和单目标情况却有着较大的区别, 这也是多目标优化算法的发展滞后于单目标优化算法的原因之一。我国针对多目标免疫算法的研究起步于2005年, 直至2010年焦李成、尚荣华等人发表了我国第一部拥有实际理论研究成果的多目标免疫算法著作。其算法的核心思想是对传统免疫算法理念的一个挪用或参照。区别于单目标免疫优化算法, 多目标免疫优化算法模仿的免疫过程及相关概念如下分别列示如下:

定义1抗体。同一抗原的表面有多个抗原表位, 每一个表位就相当于一个性能泛函, 只有多个表位被识别并产生免疫应答时才会产生抗体。因此, 抗体在多目标算法中就是根据每个性能泛函所产生的Pareto最优解。

定义2克隆。克隆是生物的无性增殖过程, 在算法中克隆是对抗体基因片段的简单复制, 在基因长度确定的情况下, 不允许基因位的横向扩展复制。

定义3变异。基因突变公认为是生物种群的进化方式之一, 由于抗体的克隆增殖过程不存在基因交叉, 因此, 高频变异是算法进化的主要动力。

定义4抗体—抗原亲和力。抗原和抗体是一种非共价的结合, 不形成共价键, 因此需要四种分子间的引力 (静电引力、范德华力、氢键结合力、疏水作用力) 来使其结合。在多目标优化中, 不同的结合力度对应着不同的支配等级, 所有非支配集合中的个体均认为是具备最强的结合力。

定义5选择与修剪。抗体不仅能够识别抗原, 还能相互识别, 这就使得抗体不会永远增殖, 算法通过计算抗体的聚集度来选择聚集度小的抗体并修剪抗体规模以保持种群良好的分布性。

2 算法的Matlab实现

染色体或基因片段的表达通常以矩阵的方式来描述, Matlab对矩阵计算具有较大优势, 而且以矩阵方式表述染色体更是降低了代码的复杂度。除此之外, Matlab自带的Simulink可以将仿真和优化计算相结合, 为工程实际问题的高效解决提供了更加便捷的方式。因此, 本文采用Matlab来实现免疫克隆选择多目标优化算法的编程, 算法步骤为:

Step1:根据抗原产生初始抗体群的基因片段, 为与其他进化算法的表述一致, 将这一基因片段当作是一条染色体;

Step2:根据免疫记忆原理, 对初始的抗体群进行小规模的克隆 (本文所用复制比为5) ;

Step3:高频变异 (本文采用0.9) 是本算法中种群的进化动力, 各个抗体的每一基因位均采用按概率变异的方式;

Step4:构造non-dominated set, 通过逐一比较的方式, 可将抗体划分为支配个体和非支配个体, 再将受支配的个体从进化种群中删除;

Step5:计算拥挤距离, 并判断种群规模是否超过预设值。若种群规模过大, 则删除聚集度大的个体, 以保持种群良好的分布特性;

Step6:克隆优异抗体;

Step7:判断是否达到预设的进化代数, 是则输出Parto最优解, 并绘制解的分布图, 否则跳转Step3。

算法的流程图如图2所示。根据算法流程图可以得到算法的主函数程序, 其主要内容如算法1所示。

算法1

2.1 变异算子

由于在二进制编码中存在着“Hamming”悬崖, 故本算法采用实数编码方式, 且实数编码方式省却了二进制数到十进制数的转换计算, 如此即能有效降低算法的时间复杂度。针对实数编码的变异方式有多种, 而每种变异方式对算法的局部搜索能力和全局搜索能力都会发生一定的影响, 尤其是进化过程中不存在交叉算子的情况下, 影响将更加突出。本文选取了常用的高斯变异方式, 其实现代码如算法2所示。算法中, chrom为抗体的基因片段, pm为变异概率 (本文取0.9) , bound则指明了每一基因位个体的变异取值范围。

设xk为变异点, 其取值范围是[xkmin, xkmax], 那么新的基因x'k为:

算法2

2.2 non-dominated set构造

非支配集的构造采用逐一比较的方式, 非支配集的构造即需遵循如下的定义6。

定义6:设X和X*是多目标优化问题候选解集中的任意两个非等值个体, 假定X*是非支配的 (Pareto-占优) , 则需要满足如下条件:

(1) 对于所有的子目标, X*不比X差, 即fk (X*) ≤fk (X) , (k=1, 2, …, r)

(2) 至少存在一个子目标, 使得X*比X好, 即q∈{1, 2, …, r}至少有一个子目标使fq (X*)

其中, r为子目标的数量, 此时可用“”表示两者的关系, 即。

算法设计时, 对受支配的个体, 将其赋值为Inf, 然后查找出种群中目标值为Inf个体, 删除对应的解和抗体, 具体实现如算法3所示。其中给出了部分代码, 输入的objv为候选解集, selch为对应的抗体 (变异后) , 相应的输出则为非支配集及其对应的解。

算法3

2.3 选择与种群修剪

随着迭代次数的增加, 非支配集中抗体数量会不断增殖, 为了保持种群良好的分布性, 避免局部抗体过于密集, 就需要对种群进行修剪, 选择出聚集度小的个体, 将其作为优秀抗体, 送入到下一代的进化过程中。本文在算法设计时, 首先对目标值进行排序, 然后分别计算每个目标值的拥挤距离, 对于两端的个体, 将其值取为Inf, 即无条件保留边界个体进入下一代。稍后, 按照原有抗体对应的目标值顺序将目标值相加并排序, 最后, 即按照种群的预设规模, 删除聚集度高的个体。拥挤距离的计算如公式 (4) 所示。

式中, aj-1, i表示第j-1位个体在第i个目标值的拥挤距离, sortdata为目标值矩阵, 分母中加上0.1是为了避免分母在特殊情况下为0状况的发生。

3 算法测试

为了验证仅依靠高频变异作为进化动力的免疫克隆选择多目标优化算法在解决多目标优化问题上的有效性, 本文选取了一个普通二维目标函数、一个经典kur测试函数以及三维目标测试函数MOP5和MOP7, 测试函数如下所示:

(1) test1测试函数

(2) kur测试函数

(3) MOP5测试函数

(4) MOP7测试函数

函数的测试结果如图3所示。

图3中, (a) 和 (b) 分别为二维目标函数的测试结果, 计算时设置最大进化次数Maxgen=100, 抗体规模nonex=80, 优异抗体克隆比例为20。 (c) 和 (d) 则为三维目标函数的测试结果, 计算时设置最大进化次数Maxgen=100, 抗体规模nonex=100, 优异抗体克隆比例为20。由计算结果可知, 解集分布均匀, 经典测试函数与标准结果相比较, 解集分布范围广阔且分布区域正确。

4 结束语

本文介绍了一种用于多目标优化的免疫克隆选择算法, 该算法通过模仿生物的免疫应答过程来实现多个目标函数的寻优计算。算法中, 抗体群的进化仅依靠变异算子来实现, 对优异抗体进行大比例的克隆, 且按概率进行免疫记忆, 保留精英抗体。通过算法的测试, 与文献[3]中所提供分布图的比较结果表明, 本文在Matlab环境下设计的算法计算效率高、Pareto解集分布广泛且均匀。本文算法可应用于经济中的多目标决策、最优控制器设计、路径优化、工程中的多目标优计算等诸多领域, 为解决实际问题提供了有效、可靠的计算方法。

参考文献

[1]焦李成, 尚荣华, 马文萍, 等.多目标优化免疫算法、理论和应用[M].北京:科学出版社, 2010.

[2]雷德明, 严新平.多目标智能优化算法及其应用[M].北京:科学出版社, 2009.

[3]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.

[4]JIAO L C, GONG M G, SHANG R H, et al.Clonal selection with immune dominance and anergy based multi-objective optimization[C]//Proceedings of 3rdInternational Conference on Evolutionary Multi-criterion Optimization.Berlin:Springer, 2005:474-489.

[5]SCHAFFER J D.Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of 1stInternational Conference on Genetic Algorithms and Their Applications.Hillsdale:Lawrence Erlbaum Associates, Inc., 1985:93-100.

[6]DEB K, PRATAB A, AGARWAL S, et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6 (2) :182-197.

[7]COELLO C A, CRUZ C N.An approach to solve multiobjective optimization problems based on an artificial immune system[C]//Proceedings of 1stInternational Conference on Artificial Immune Systems, Canterbury, 2002:212-221.

[8]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006.

免疫记忆克隆选择算法篇4

聚类分析[2,3]是多元统计分析的一种，也是非监督模式识别的一个重要分支，它把一个没有类别标记的样本集按某种准则划分成若干个问题子集，使相似的样本尽可能归为一类，而不相似的样本尽量划分到不同的类中。聚类分析的研究过程中，出现了一批经典的聚类算法，如k-means聚类算法、FCM聚类算法等。随着聚类算法对相关数据进行聚类时，聚类中心在迭代的过程中很容易陷入局部极值点，而无法发现该类型数据集的正确聚类，因此，对聚类算法可靠性，稳定性方面亟待加强。人工免疫系统[4]是借助高等脊椎动物免疫机理及医学免疫学原理建立和发展一种新颖、有效的现代计算智能方法，并已成功的应用于解决工程实际中的复杂问题。如组合优化问题，数值优化，智能控制等。

本文提出了一种免疫克隆选择聚类算法的TSP问题求解，本文针对大规模TSP问题，利用K均值动态聚类法对TSP进行邻域分区，免疫克隆选择算法对群内细分的TSP进行精确优化，后根据K重心邻域连接方法进行全局连接以快速得到大规模TSP问题满意解。实验结果表明文中提出的算法是有效的，可行的。

1 免疫聚类克隆选择算法

1.1 K-means算法的数学思想

K_means算法[5]的核心思想如下：算法把n个向量xj(1,2…,n)分为c个组Gi(i=1,2,…,c)，并求每组的聚类中心，使得非相似性(或距离)指标的价值函数(或目标函数)达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时，价值函数可定义为：

这里是组i内的价值函数。这样Ji的值依赖于Gi的几何特性和ci的位置。

一般来说，可用一个通用距离函数d(xk,ci)代替组I中的向量xk，则相应的总价值函数可表示为：

为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为(1)式。划分过的组一般用一个c×n的二维隶属矩阵U来定义。如果第j个数据点xj属于组i，则U中的元素uij为1;否则，该元素取0。一旦确定聚类中心ci，可导出如下使式(1)最小uij:

重申一点，如果ci是xj的最近的聚类中心，那么xj属于组i。由于一个给定数据只能属于一个组，所以隶属矩阵U具有如下性质：

且

另一方面，如果固定uij则使(1)式最小的最佳聚类中心就是组I中所有向量的均值：

这里|Gi|是Gi的规模或。

1.2 K-means算法步骤

1)从n个数据对象任意选择k个对象作为初始聚类中心;

2)循环(3)到(4)直到每个聚类不再发生变化为止

3)根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

4)重新计算每个(有变化)聚类的均值(中心对象)。

1.3 免疫克隆选择算法

1958年，Burnet等人最先提出了克隆选择学说，其核心思想为：抗体是天然产物，以受体的形式存在于细胞表面，抗原可与之选择性地反应。抗原与相应抗体受体相互刺激可导致细胞克隆性增殖。该群体具有相同的抗体特异性，其中某些细胞克隆分化为抗体生成细胞，另一些形成免疫记忆细胞以参加以后的再次免疫应答。在此过程中，主要借助克隆使其激活、分化和增殖，以增加抗体的数量，通过进行免疫应答最终清除体内抗原。因此，克隆选择是生物免疫系统自适应抗原刺激的动态过程，在这一过程中所体现出的学习、记忆、抗体多样性等生物特征，正是人工免疫计算所借鉴的。根据Burnet的抗体克隆选择学说，De Castro以及Kim等人从不同的角度模拟上述生物学抗体克隆选择机理，相继提出了不同的克隆选择算法模型[6]。并给出De Castro提出的基本克隆选择算法流程。如图1所示。

1)首先生成候选解P,P是有记忆单元(M)和保留种群(Pr)组成，即：P=Pr+M;

2)根据亲和度计算，选择n个个体(Pn);

3)复制(克隆)种群中n个最好的个体，生成一个克隆临时种群(C)，克隆规模和抗体—抗原的亲和度成正比;

4)对克隆临时种群进行高频变异，这里高频变异和抗体，抗原的亲和度相对应，由此获得了一个变异后的抗体群(C*);

5)从C*中重新选择改进的个体组成记忆单元M.P中的一些个体也被C*中其他改进的个体所取代;

6)利用新产生的抗体代替d个旧抗体(引入多样性)，亲和度低抗体更容易被取代。

1.4 免疫聚类克隆选择算法流程

图2为算法流程图。

2 实验测试

实验仿真环境：windows XP系统，AMD处理器，1.90GHZ 448MB内存，仿真软件MATLAB 7.0。

2.1 数据仿真测试

运行结果(初始为聚3类，可自定义)及仿真数据源如图3，一共有32个坐标对象。

运行之后输出聚类结果如图4。

由仿真图形4可以看出可以看出其中第一类有11个对象，第二类14个对象，第三类7个对象，合计32个对象。图4画出了中心点，坐标依次为C1(2.6364,1.9091),C2(6.0714,5.8571),C3(12.143,1.429)。

2.2 TSP实例测试

为了验证本文算法的有效性性，采用国际上用的TSP测试实例库。

实例一：对ch130(城市规模130)进行10次操作，抗体种群规模m=130，输入重心点为4。本文算法获得最优值一次6110.8438，得到的最优数据优于TSPLIB提供的最优路径长度6110.9最大值为6238.8255，平均值6183.1417，偏离最优值的误差为0.0118。

实例二：对tsp202(城市规模202)进行10次测试，抗体种群规模m=202，输入重心点为4。根据本算法获得。得到最大值为496.9347，最优值489.8321。得到的最优数据优于TSPLIB提供的最优路径长度490.67，得到平均值为493.2675。

表1中平均百分误差

其中STi是第i次的最短路径，S0是已知最短路径。NGA与IDIA的求解数据均来自文献[7]。

3 小结

本章提出了一种面向组合优化经典NP难TSP问题的免疫聚类克隆选择算法，针对大规模TSP问题，利用K均值动态聚类法对TSP进行邻域分区，免疫克隆选择算法对群内细分的TSP问题进行局部精确优化，后根据K重心邻域连接方法进行全局连接以快速得到大规模TSP问题满意解。通过实验仿真可知，大部分结果优于或接近标准TSPLIB提供的已知最优路径距离S0，全局搜索能力更强，收敛速度更快。

参考文献

[1]Michalewicz Z,Fogel D.How toSolve It:Modern Heuristics[M].Berlin,Germany:Springer-Ver-lag,2000.

[2]LeFevre K,DeWitt D,Ramakrishnan R.Mondrian multidimensional k-anonymity[C]//Liu L,Reuter A,Whang KY,Zhang JJ,et al.Proc of the22nd Int'l Conf.on Data Engineering.Los Alamitos:IEEE Computer Society,2006.

[3]戴东波,汤春蕾,熊赟.基于整体和局部相似性的序列聚类算法[J].软件学报,2010,21(4):702-717.

[4]戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报,2008,19(6):1265-1273.

[5]汪中,刘贵全,陈恩红.一种优化初始中心点的K-means算法[J].模式识别与人工智能,2009,22(2):299-304.

[6]De Castro L N,Zuben F J V.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Com-putation,2002,6(1):239-251.

基于免疫记忆克隆的关联规则挖掘篇5

关联规则挖掘是数据挖掘领域中的一个重要研究方向,具有广泛的应用价值[1,2,3]。从本质上看,关联规则挖掘主要目的是挖掘数据项集之间的某种潜在的关系,从而在大量数据中发现潜在和有价值的关联关系,为决策者提供适当的依据。目前,广泛使用的关联规则挖掘算法是Apriori算法及其改进算法[4]。这些算法在关联规则挖掘中取得了很好的效果,能够比较准确地挖掘出用户需要的关联规则,但是其挖掘效率比较低,难以适用大规模数据集。因此,有必要提出更好的算法来解决关联规则挖掘算法的效率问题。从本质上看,关联挖掘算法的核心思想是找到频集, 实际上就是在一定的空间内进行搜索,将有关联关系的元素搜索出来,是一个全局搜索的优化过程。同时,已有的研究表明,智能优化算法用于关联规则挖掘是可行的。文献[5,6]分别采用遗传、基本免疫算法等进行实现,取得了一定的求解效果,但效果还有待进一步优化。常见的关联规则挖掘都是一种“由底向上”,“由小到大”的逐层搜索、逐步优化的过程,这个过程中需要强有力的搜索策略的支持。现提出了基于免疫记忆克隆的关联规则挖掘算法,在搜索过程中很好地保持了种群多样性。实验结果表明,算法可以提取用户感兴趣的关联规则,提高了所得关联规则的准确率,并且速度较快。

1 算法基础和关键技术

1.1 关联规则挖掘的基本概念

关联规则挖掘致力于数据库中指标项之间关联规则或相关关系的挖掘,实际上真正体现了数据中的知识发现。设I=(i1,i2,…,im)是数据项的集合,D为项组合的一个集合。关联规则是形如A→B的蕴涵式,其中A∈I, B∈I,并且A∩B=ϕ。一般用支持度和置信度描述关联规则的属性。其中,支持度S(support)定义为 $(A \Rightarrow B) = \frac{n (A \Rightarrow B)}{n}$ ,事务集D中同时包含事务A和B的百分比,称为规则AB具有支持度S。置信度C(confidence)定义为 $(A \Rightarrow B) = \frac{n (A \Rightarrow B)}{n (A)}$ 。事务集D中包含A的事务数与同时包含B的事务数的百分比,称为规则AB具有置信度C。显然,只有支持度较大的规则才是较有价值的规则,只有置信度比较高的规则才是比较可靠的规则。因此,只有支持度与置信度均较大的规则才是比较有价值的规则。

在关联规则挖掘时,往往需要事先指定最小支持度与最小置信度。如果一个规则满足最小支持度,则称这个规则是一个频繁规则;如果一个规则同时满足最小支持度与最小置信度,则通常称这个规则是一个强规则。关联规则挖掘的通常方法是:首先挖掘出具有最小支持度的频繁项集,再从得到的频繁规则中挖掘强关联规则。

1.2 算法对应关系

人工免疫系统是一种受启发于生物免疫系统功能的智能优化算法。免疫克隆选择是人工免疫系统的主要优化算法之一,已经在不同的领域得到了广泛应用。免疫克隆算法通过克隆、选择、变异等算子对算法逐步进行优化[7,8,9]。该算法采用免疫记忆克隆算法产生频繁规则,然后计算这些规则的各种组合是否满足最小可信度,从而产生强关联规则。使用免疫克隆算法进行关联规则挖掘时,将数据库中的所有记录作为抗原,候选模式作为抗体。最后,关联规则由记忆细胞所代表的频繁模式生成。

1.2.1 编码方式

编码方式是免疫算法进行求解的关键步骤。免疫算法中,每一个抗体表示一种可能的解。由于用于关联规则挖掘的主要是事务型数据库,因此,编码采用二进制方式。在编码之前,首先对连续属性值进行离散化预处理,得到每个属性的若干个取值。将所有的决策属性和任务属性构造成一个规则结构串,形如:{ T1, T2,…, TmM1, M2,…, Mn},其中Mi表示决策属性,Tj表示任务属性。每个属性可以采用合适长度的二进制编码,然后按顺序串接起来。

1.2.2 亲和度计算

免疫算法中,根据亲和度函数计算抗体与抗原之间的关系。根据本文特点,亲和度函数定义如下

f(X⇒Y)=sup(X⇒Y)+conf(X⇒Y)。

从亲和度函数可见,支持度和置信度都高的生存机率更大。

2 算法具体实现

现设计的算法基本步骤如下(步骤1—步骤6):

步骤1 初始化

设进化代数k为0,随机初始化种群A,规模为n。则初始化种群记为: A(k)={A1(k),A2(k),…,An(k)},同时设置记忆种群M(k),规模为s(s=nb%),初始为从A(k)中随机选取,则

M(k)={M1(k),M2(k),…,Ms(k)};设置保留种群R(k),规模为t=n-s,则R(k)={R1(k),R2(k),…,Rt(k)}, 所以有

A(k)=M(k)∪R(k)。

步骤2 亲和度评价

分别计算抗体种群亲和度,并按亲和度大小降序对抗体进行排列,选出前s个抗体更新记忆种群M(k)。

步骤3 终止条件判断

如果达到最大迭代次数kmax,算法终止,将记忆种群中保存的亲和度最高的抗体进行映射,即得到了最佳的结果;否则,转步骤4。

步骤4 克隆扩增T $_{c}^{c}$

对这s个抗体进行克隆操作T $_{c}^{C}$ ,形成种群Y(k)。对克隆操作T $_{c}^{c}$ 定义为

Y(k)=T $_{c}^{C}$ (M(k))={T $_{c}^{C}$ [M1(k)],T $_{c}^{C}$ [M2(k)],…,

T $_{c}^{C}$ [Ms(k)]}T。

具体克隆方法为:假设选出的s个抗体按亲和度降序排序为:M1(k),M2(k),…,Ms(k),则对第q个抗体Mq(k)(1≤q≤s)克隆产生的抗体数目为

$Ν_{q} = Ι n t (n_{t} \frac{f [Μ_{q} (k)]}{\sum_{i = 1}^{s} f [Μ_{i} (k)]} p_{s} [Μ_{q} (k)] 。$

则第k代克隆产生的种群抗体个数数量记为:

$Q = Ν (k) = \sum_{q = 1}^{s} Ν_{q} 。$

其中,Int(·)表示向上取整,nt(nt>s)表示控制参数,f(·)代表亲和度函数的计算;ps(·)为基于抗体浓度的选择概率。对于抗体的浓度计算,设计了一种基于矢量距的计算方法,具体如下。

定义抗体Mq(k)在种群M(k)上的距离为

$d [Μ_{q} (k)] = \sum_{i = 1}^{s} Η [Μ_{q} (k) ‚ Μ_{i} (k)] 。$

其中,H(·)表示二者之间的海明距离(距离越大,说明抗体越不相似),则抗体的浓度为:

$ρ [Μ_{q} (k)] = \frac{1}{d [Μ_{q} (k)]} 。$

则基于抗体浓度的选择公式为:

$p_{s} [Μ_{q} (k)] = \frac{d [Μ_{q} (k)]}{\sum_{q = 1}^{s} d [Μ_{q} (k)]} = \frac{\sum_{i = 1}^{s} Η [Μ_{q} (k) ‚ Μ_{i} (k)]}{\sum_{q = 1}^{s} \sum_{i = 1}^{s} Η [Μ_{q} (k) ‚ Μ_{i} (k)]} 。$

从上式可知,抗体集合中与抗体q相似的抗体越多,抗体q被选中的概率越小,理论上保持了解的多样性。本文设计的克隆策略的优势在于:避免基本克隆选择算法[10]只根据亲和度大小克隆导致算法容易早熟收敛,也避免了信息熵[7]浓度调节计算复杂,收敛较慢的缺点。

步骤5 克隆变异T $_{m}^{c}$ 。

依据概率p $_{m}^{}$ 对克隆后的种群Y(k)进行变异操作T $_{m}^{c}$ ,得到抗体种群Z(k)。定义为Z(k)=T $_{m}^{c}$ [Y(k)]。变异采用基本位变异[8]。

变异后的种群为

Z(k)={z1(k),z2(k),…,zQ(k)}。

步骤6 克隆选择T $_{s}^{c}$ 。

定义为A(k+1)=T $_{s}^{c}$ (Z(k))。具体方法为:为了保持规模稳定,重新对Z(k)进行亲和度函数评价,选择前s个亲和度高的抗体组成记忆种群M(k+1)。同时,为保持种群多样性,随机生成保留种群R(k+1)(规模为t=n-s);M(k+1)和R(k+1)组成下一代种群A(k+1); 记:A(k+1)={A1(k+1),A2(k+1)…An(k+1)};转步骤2。

3 仿真实验及结果分析

针对UCI数据集中的iris、ecoid数据集进行仿真实验。其中,支持度为0.2%,置信度为60%,实验选取文献[3,6]的算法作为对比算法。实验环境为windows系统,编程语言为Matlab。实验结果如表1所示。其中,iris数据集样本数150个,属性个数4个,分割点数123;ecoli数据集样本数336个,属性个数7,分割点数361。训练集和测试集合的比例为1∶2。

免疫克隆算法的参数设置通常是依靠经验和试验来确定,工作量大且难以得到最优的参数组合。本文采用均匀设计设定参数值[10],减少了工作量。免疫记忆克隆算法的参数设置如下:最大进化代数kmax=1 000;种群规模n=20,记忆单元规模s=0.4×n;克隆控制参数nt=20,变异概率p $_{m}^{}$ =0.1。

从表1的实验结果可以看出,文献[3]算法得到的规则数较多,但准确率较低,容易产生冗余和无效规则,并且花费时间较多。主要原因在于:算法中候选项目集的生成以及多次扫描数据集大大影响挖掘的性能,效率低下。本文算法用时少而且规则提取率高。这是因为,该算法在采用的各种免疫算子,减少了计算过程中的盲目性和随机性,提高了收敛速度和搜索效率。

4 结论

提出的一种求解关联规则挖掘的免疫记忆克隆优化算法。由于充分利用了免疫记忆特性,采用矢量距的抗体浓度选择方法保持解的多样性。实验结果表明,该算法可以较准确的得到关联规则,并且用时较少。

参考文献

[1]何波.基于频繁模式树的分布式关联规则挖掘算法.控制与决策,2012;32(2):415—420

[2]刘青宝,王文熙,王万军.基于线性链表的模糊关联规则挖掘.计算机科学,2012:21(3):312—316

[3] Srivastava J,Cooleyr,Deshpande M.Web usage mining:discoveryand application of usage patterns from Web data.IGKDD Explora-tions,2000;22(1):34—40

[4]杨光军.基于免疫克隆文化算法的关联规则挖掘.2012;34(3):118—121

[5]朱玉,张虹,孔令东.基于免疫遗传算法的多维多层关联规则挖掘.计算机工程,2009;35(23):181—184

[6]朱玉,张虹,孔令东.一种基于免疫算法的空间关联规则挖掘方法,武汉大学学报(信息科学版),2009;43(12):278—285

[7] Gong Maoguo,Jiao Licheng,Liu Fang,et al.immune algorithm with orthogonal design based initialization,cloning,and selection for global optimization.Knowledge and Information Systems,2010;25(3):523—549

[8] Yang Dongdong,Jiao Licheng,Gong Maoguo,et al.Adaptiveranks and K-nearest neighbour list based multiobjective immune algo-rithm.Computational Intelligence,2010;26(4):359—385

[9]杨咚咚,焦李成,公茂果,等.求解偏好多目标优化的克隆选择算法.软件学报,2010;21(1):14—33

【免疫记忆克隆选择算法】推荐阅读：

免疫优化算法06-19

量子免疫算法10-03

免疫PID算法11-29

记忆选择07-27

护士指导免疫病理之组织损伤的免疫机制一08-27

第二章免疫与计划免疫章末总结10-20