三种人工免疫算法综述

三种人工免疫算法综述Reference：TimminsJ,HoneA.StiborT.etal.TheoreticaladvancesinArtificialImmunesystem[J].TheoreticalComputerScience.2008.403:11-32中国民航大学计算机科学与技术学院刘东楠计算机科学与技术学院关于人工免疫算法SomethingAboutAIS计算机科学与技术学院为什么在计算领域中研究免疫算法？Whystudytheimmunesystemforcomputation?计算机科学与技术学院人工免疫算法的生物学基础BiologicalunderpinningsofAISFig.1克隆选择过程Fig.2阴性选择（否定选择）Fig.3免疫网络计算机科学与技术学院m系统组件的表现形式m具有个体和环境相互作用的评估机制，环境会被一些输入刺激后激活m管理动态系统是可适应的过程，例如，行为随着时间的变化人工免疫算法基础BasicsofAIS解决方案Solution免疫算法ImmuneAlgorithms关系方法AffinityMeasures表现形式Representation应用领域ApplicationDomain人工免疫算法应用到工程领域中具备的要素：Fig.人工免疫算法的分层框架计算机科学与技术学院m形状空间（shapespace）m概念：在数量上描述细胞和抗原的关系。m思想：免疫细胞表面的受体和抗原决定簇的匹配程度以及无力分子的适应程度决定了它们结合的强度。关系的数量影响了哪种细胞被激活后将通过克隆选择增殖，或者哪些细胞将被抑制。人工免疫算法基础BasicsofAISm争议：抗原决定簇和受体是钥匙和锁的关系吗？m如果钥匙的形状是正确的，门永远会开。m对于受体来说抗原决定簇有一点不完美，只刺激符合条件的免疫细胞（刺激物的数量依赖于形状的完美匹配）。Fig.抗原决定簇与受体的结合计算机科学与技术学院m形状空间（shapespace）——Representationm在同一空间内（可以是任意维度），分别用一个点表示抗原决定簇和受体，它们的距离表示它们之间的关系。m维度不是特别重要，但是坐标是必须的，不同的坐标决定了物质的大致形状。坐标可以测量结合部位的一些特征，例如：表面的长度或者宽度，以及其它的一些决定因素。人工免疫算法基础BasicsofAISlreceptorlepitopecase1case2Fig.抗原决定簇与受体的结合m抗原决定簇和受体的关系是成比例的。m用表示抗原决定簇，每一个决定簇有一个最大的，作为受体细胞可接受刺激物数量的阈值。m受体可能还有其它的特征，或针对不同的抗原决定簇有不同的结合部位。m用n个数定义每一个结合程度。],0[lxl计算机科学与技术学院m形状空间（shapespace）——Representationm例如：受体坐标：抗原决定簇坐标：欧式距离：m简单的方法：m为受体x定义一个半径为的“识别球”m判断抗原决定簇和受体的结合是否符合条件m“识别球”的大小由受体决定，识别区域不需要一个准确的球形，整个空间的容量关系应该提供一个可识别出的方法。人工免疫算法基础BasicsofAIS),,,(21nxxxx),,,(21nyyyynjjjyxyxD12)(),()(xB}),(|{)(yxDyxB)(0)(1),(~xByxByyxD计算机科学与技术学院Fig.DifferentHammingShapeSpacesm形状空间（shapespace）——RepresentationmHammingShapeSpacem浮点数表示的缺陷m浮点数通常会得出一些我们不希望的特征，它会将一些小规模的问题放大，导致我们面临了一个大规模的问题。所以我们需要考虑的是一种离散的形状空间，而不是连续的。人工免疫算法基础BasicsofAISHamming形状空间建立了在一个特定字母表中，所有长度为L的元素集合。L定义·一个元素检测器按照r-连续位匹配规则进行匹配，如果在某一位置P处，存在。所以，得到长度相同的两个元素至少在r个连续位上相同。),,,(,21LLeeeee),,,(,21LLddddd1,1,forrLprppideii计算机科学与技术学院mB细胞算法:简单稳定、通过评估、克隆、突变、选择的过程，设计了一个使全部B细胞达到全局最优状态的算法。每一个成员都被视为一个独立的整体，在群体中，没有相关作用，每一个B细胞都是一个Hamming空间内的L维向量。功能g被用来评估每一个B细胞的向量，并生成g(v)。简单克隆选择算法——B细胞算法Simpleclonalselectionalgorithm-BCellAlgorithm(BCA)EvaluationClonalPoolCAdaptationMutationBCellvm如何在选择中保持多样性？m克隆是随机的m元素向量是随机的m均匀的突变比例计算机科学与技术学院m关于连续位突变器(ContguousRegionSomaticHypermutationOperator,CRHO)mB细胞向量v'以一定概率进入CRHO中；mCRHO比传统的运行器变异率高；m由于经验，CRHO在第一次运行时就能找到合适的ρ值；mCRHO选择采用精英机制。mB细胞算法判断停止的条件：判断距离m[例]m（1）在检测问题中，如入侵检测，当已知最优值确定时停止。m（2）在一般问题中，在一系列相互作用后值不再增加时停止。简单克隆选择算法——B细胞算法Simpleclonalselectionalgorithm-BCellAlgorithm(BCA)计算机科学与技术学院简单克隆选择算法——B细胞算法Simpleclonalselectionalgorithm——BCellAlgorithm(BCA)Algorithm1:BcellAlgorithminput:g(v)=functiontobeoptimisedoutput:P=setofsolutionsforfunctionbegin1.CreataninitialpopulationPofindicidualsinshape-space2.Foreach,evaluateg(v)andcreateclonepopulationC3.Selectarandommemberofandapplythecontiguousregionhypermutationoperator4.Evaluate;ifthenreplacevbyclone5.Repeatsteps2-4untilstoppingcriterionismetendLPvCv)v(gv)()v(ggv计算机科学与技术学院m目标：找到一种压缩输入机制以减少冗余。m例如：aiNetAlgorithmm特点：利用与克隆选择方法类似的效率检测器m与克隆选择方法的不同：m成员之间有一种相互抑制的作用m移除了成员间匹配时的一些要素m训练项目在某一确定的阈值之下免疫网络算法ImmuneNetworkAlgorithms计算机科学与技术学院免疫网络算法ImmuneNetworkAlgorithmsAlgorithm2:ImmuneNetworkAlgorithmsinput:G=patterntoberecognised,Nasetofrandomdetectors,nnumberofbestantibodiesoutput:M=setofgenerateddetectorscapableofrecognisinginputpatternbegin1.CreateaninitialrandompopulationB2.Foreachpatterntolearn2.1DetermineinversedistanceforpatterninBtoeachmemberofN2.2SelectnmembersofBwiththebestmatchtoeachpattern2.3Cloneandmutateeachninproportiontohowgoodthematchtothepatternis2.4RetainthehighestmatchingofnandplaceinasetM2.5PerformnetworkdynamicsinMtoremoveweakmembersofM2.6GeneratebrandomelementsandplaceinB3repeatend计算机科学与技术学院m思想：阴性选择算法使用一定数量的检测器，利用这些检测器对新的数据进行“自我”及“非我”分类。阴性选择算法NegativeSelectionAlgorithms计算机科学与技术学院阴性选择算法NegativeSelectionAlgorithmsFig.阴性选择算法的过程计算机科学与技术学院阴性选择算法NegativeSelectionAlgorithmsAlgorithm3:NegativeSelectionAlgorithminput:S=setofselfelementsoutput:D=setofgenerateddetectorsbegin1.DefineselfasasetSofelementsinshape–space2.GenerateasetDofdetectors,suchthateachfailstomatchanyelementinS.3.MonitordatabycontinuallymatchingthedetectorsinDagainst.Ifanydetectormatchwith,classifyasanon-self,elseasself.endLL计算机科学与技术学院mPartⅠ人工免疫算法的马尔可夫链人工免疫算法分析AnaylsisofAISm个体数量：Npmx，是一个有限的字母表，通常m系统的状态x=（x1,x2,···,xNp）,状态集m定义每一种可能的状态，由1——M表示，m在随机的算法中，每一个时间段t，都有一个符合系统状态的值m表示的M维向量，当系统的状态在t时为j，记作m这个M维向量不依赖于tL1}{0，PLNPLNM||],1[Mxttvtx)(,jxPvtjt计算机科学与技术学院人工免疫算法分析AnaylsisofAISmPartⅠ人工免疫算法的马尔可夫链公式应用：1)|1,()(0)|()|()()|()(0011111,,1111jxtjxPjkPifPvvPPPvvjxkxPPjxkxPPPvvjxPjxkxPkxPtjkttjkttjkttjkNjjkjtktNjtttt//状态j→状态k//整个系统不依赖于t//当系统达到稳定状态时//满足此条件系统被判断为一个持续状态，否则为临时状态transientpersistent计算机科学与技术学院mPartⅡ克隆选择算法分析——BCellAlgorithm,BCAm应用：功能优化、搜索问题、多目标优化m问题：不考虑时间问题，在寻找全局最优解时，算法是否收敛？m相关研究：用马尔科夫理论证明；限制精英记忆机制；使用超突变运行器m关于CRHO，连续位超体突变器m关键词：记忆机制、克隆池m特点：克隆池的大小是随意的人工免疫算法分析AnaylsisofAIST：L的第t种状态a：系统第一次的位置b：系统最后一次的位置k：总数（0，T）ρ：在连续位中突变的概率ft：（0，T）计算机科学与技术学院人工免疫算法分析AnaylsisofAISm设计实验证明其收敛性：L=8,ρ=0.5m第一种情况：一般情况下进行分析m第二种情况：对一百万个结果进行分析的平均状态m结论：m（1）在0ρ1时，所有不能被优化的状态都是临时的。m（2）所有的优化都是终结状态。计算机科学与技术学院mAbou