第4讲--免疫算法概要

第4讲免疫算法学习目的：了解和掌握免疫算法的基本思想和流程，解决优化等实际问题学校要点：一般免疫算法、免疫克隆选择算法、免疫网络算法，免疫调度算法，其他改进的免疫算法。免疫算法在调度等优化问题方面的应用。内容概述：免疫算法没有统一的模式，即使在生物学基础上也不是统一的。它与遗传算法等传统自然计算或计算智能方法的差别在于，遗传算法、人工神经网络等方法是基于单一的生物学理论而发展，比如进化论、人脑的神经网络结构。而免疫算法的生物学基础是多样的，比如免疫网络、克隆选择理论、阴性选择等，基于这些免疫学理论或机制已经开发出多种形式的算法模型。它是人工免疫系统的主要研究内容，也是免疫计算的主要形式。免疫算法是面向问题的方法，因此从人工免疫系统发展以来，已经有许多用于不同领域的免疫算法开发出来[3][4][5][6][7]，多数利用免疫系统的某一方面机制或原理设计新算法，或者改进现有技术。所依据的原理基本是传统的免疫学理论，因此免疫算法从启发源角度大致大致可以分为三类：免疫网络模型（分连续和离散两种形式）、克隆选择、阴性选择。代表性的主要有一般免疫算法[8]、早期的骨髓模型[9]、DeCastro提出的克隆选择算法[10]、Forrest提出阴性选择算法[11]，DeCastro提出的人工免疫网络算法（aiNet）等[12]。此外，文献[13]中提出了B细胞算法，文献[14]最早提出了基于疫苗概念的免疫算法。文献[15][16]分别对免疫算法进行了较为深入的研究。多数免疫算法都是针对优化问题展开研究，具体见第9、10章。上述免疫算法可进一步分为两类：基于群体的和基于网络的。第一类包括所有不考虑免疫网络的免疫算法，如阴性选择、克隆选择算法等，基于网络的算法是所有受免疫系统网络理论启发的算法。一般免疫算法本质上是基于网络的算法。图4.1免疫算法与搜索算法[21]4.1一般免疫算法进化算法Tabu搜索间接法直接法模拟退火动态规划盲目随机导向随机随机法枚举法搜索方法免疫算法解析法遗传算法进化规划进化策略免疫网络克隆选择一般免疫算法免疫混合算法B细胞算法、疫苗算法等其他方法一般免疫算法描述定义7.1一般免疫算法是基于免疫网络理论而开发的一种优化算法。与遗传算法在算子设计上有类似之处。其基本要素和流程等可以描述如下：),,,,,,,,,(MSfGIA：搜索空间（形态空间）(抗体)；G：表示空间(抗体抗原表示方法)；：抗体集合；：抗原集合；f：亲合力函数；S：相似度函数；M：记忆机制；：免疫算子（变异、重组等）；：选择百分比；：终止条件。在使用免疫算法解决问题时，一般各个步骤有对应形式：抗原对应要解决问题数据输入如目标、约束；抗体对应优化问题的最优解；亲合力对应解的评估、结合强度的评估；记忆细胞分化对应保留优化解，抗体促进和抑制对应优化解促进，非优化解的删除等；抗体产生对应优化解的出现等。对应内容因解决问题对象不同而内容各异。为了叙述算法方便，定义B为输入抗原；A为包含有n个网络单元(抗体)的集合；AM为N个记忆单元；Af为抗原、抗体之间的亲合力向量函数；S为抗体抗体之间的相似度矩阵；为选择成熟分子的比率；ds为相对自然死亡或衰减的阈值。则算法具体过程描述如下[18]：1.抗原输入输入待解问题抗原，抗原输入一般将目标函数和各种约束作为算法的抗原B2.产生初始抗体群体()At3.计算亲合力群体未变，分别计算抗原和抗体之间的亲合力及抗体和抗体之间的相似度。抗体和抗体相似度的度量一般采用解空间中的距离：||||,1,2,...,ijijsaain(4.1)12|,,...,|nAfAfAfAf(4.2)4.记忆细胞分化更新记忆单元选择％个与抗原的亲合性高的抗体加入到记忆单元中。由于记忆单元数目有限，清除那些与抗原亲合力低于ds以及较大密度的记忆单元(抗体的自然死亡)5.抗体促进和抑制6.抗体产生()At(1)At7.终止条件一般设置为最大迭代次数或求解精度或者二者的结合，获得问题解图4.2一般免疫算法第2步中，初始抗体通常是在解空间中用随机的方法产生。与进化算法相似，一般需要对抗体进行编码，并且遵循完备性、健全性、和非冗余性要求。第3步中，比如二进制编码情况，一般采用海明距离表示，实数编码采用欧氏距离等，其他各种距离方法可参见第15章。抗原和抗体之间的亲合力则采用抗体对抗原的适应程度(即候选解和目标函数的匹配程度).其中步骤4中定义抗体记忆矩阵与抗原的平均适应度为niiAfMAAf1)((4.3)因此，))(())1((tMAAftMAAf(4.4)第5步中，高亲合力抗体受到促进，高浓度抗体受到抑制。群体分化产生新抗体。一般来讲，与抗原亲合性高的抗体和低密度的抗体生存机率较大，但是，为了有利于优化过程的进行，某些与抗原有较高亲合性的抗体也必须受到抑制，从而体现了抗体克隆控制机制的多样性。可以再随机产生新的抗体，也可以通过变异和交叉产生进入下一代的抗体，并将M加入新抗体群落，祛除那些亲合力低于的记忆单元。第6步通过交叉等算子变异产生多种抗体。上述步骤5、6实现了对抗体产生过程的控制，如果步骤6没有采用遗传操作，则该一般免疫算法仅体现免疫网络理论；若通过变异和交叉产生新的抗体，则是进化算法的改进[18]。在上述算法中，如果抗体也采用类似进化算法的编码方法，而且新抗体的产生也主要通过交叉和变异来实现，则同样有类似进化算法的模板理论[18]：)]((*)(1)(1[)(),()1,(SAfGPPSOlSPAfSAftStSsmC(4.5)式中，S为抗体模式，l为模式长度，O为模式阶，为模式的定义距，Af为抗体与抗原的亲合力，cP为交叉概率，mP为变异概率，为抗体选择时因为保持多样性而促进或抑制时形成的选择概率，G为与亲合力有关的函数。在应用中，根据具体问题，研究人员对上述免疫算法进行不同的改进或变化，比如与遗传算法结合，利用遗传算子产生多样抗体等，以符合解决具体问题需要，从而发展出多种形式的免疫算法，但基本上都遵循这六个步骤。注意免疫细胞识别抗原的不完全匹配性，即免疫细胞识别抗原的过程就是与抗原匹配并结合的过程，这种匹配不要求二者的完全匹配，只要这种匹配所导致的亲合力大于某一固定的阈值即可。基于不完全匹配性，一种免疫细胞可以识别多种不同的抗原。形态空间理论可以对识别多样性作出合理解释。与遗传算法主要区别在于：生物启发机制不同，一个是免疫学，一个是进化论。解的进化方式不同，包括解的适应性度量、进化解的算子等。文献[19]对一般免疫算法的优缺点进行了较详细的分析，文献[20]针对一般免疫算法中基于信息熵的浓度计算缺陷提出了四点改进。一般免疫算法可分为两种形式，一种是基于信息熵度量亲合力，保持多样性的免疫算法，以下简称为信息熵免疫算法，另一种为基于距离矢量度量抗体浓度，保持多样性的免疫算法，简称为矢量矩免疫算法，本质上都是基于距离的一般免疫算法。4.2信息熵免疫算法基于信息熵的免疫算法的突出特点是利用信息熵度量和保持候选解的多样性，这种操作方式与遗传算法有明显区别。4.2.1算法描述[21]该算法实现步骤如图7.4下：1.识别抗原(问题)对问题及其解的特性进行分析和了解，进行抗体编码。初始群体的产生，在记忆库空的情况下，即随机产生；否则就以记忆库为基础产生2.产生群体解第一次迭代时，在解空间中随机产生N个抗体，并从记忆库中提取kN个抗体构成初始抗体群体，其中kN为记忆库中抗体的数量，如果记忆库中没有抗体，则随机产生kNN个初始抗体构成初始群体。如果不是首次迭代，则对原有抗体群体进行选择、交叉、变异操作得到新群体，再从记忆库中取出记忆的抗体共同构成新一代抗体群体3.对各抗体进行评价4.抗体促进和抑制5.判断暂时解集是否已满若还没有达到N个，则转到步骤3，对剩余的解群体重新评价。由于前面消除了两个极端抗体，所以再次评价解群体才能体现真实性和动态性。若暂时解集已满，则进行下一步操作6.记忆细胞产生这一步形成父代群体，由于暂时解集中暂存了经过动态选择的较优群体，所以此时抛弃剩余解群体，而将暂时解集更新到解群体。同时从暂时解集取其前kN个较优抗体存入记忆库中。最后，清除暂时解集7.抗体解产生最后判断是否满足约束条件若满足，则结束；否则，转到步骤2图4.3信息熵免疫算法步骤4对应抗体的促进和抑制。为了防止浓度较高的较优解一次性全部被消除所导致的后期收敛速度下降，该算法引入一个新的群体——暂时解集，其容量为N。将解群体按ve降序排列，消除ve值最小的一个抗体，同时把ve值最大的抗体作为暂时最优解转移到暂时解集中，这样每次使解群体减少两个极端抗体，分多次动态促进和抑制抗体群体。步骤7中，抗体解产生操作一般采用变异和选择算子，与遗传算法类似。但是，免疫系统中抗体是基于单个细胞内基因库的重组、变异而产生多样性的。因而，采用父代交叉算子并不符合免疫原理，许多改进算法加入该算子可看作是免疫算法中结合遗传算法的交叉算子。关于算法的参数设定比如变异率等，对算法性能的影响是值得研究的问题，尤其是对于参数不断变化的免疫算法，更为复杂。其中步骤3中，如果以抗体的亲合力评价为标准，当群体中的某个抗体占据了相当规模，而又不是最优解时，就极易导致过早收敛。为此，当有些抗体的规模达到一定程度后，就要对其进行限制，以防过早收敛。同时，也要相应提高规模小的抗体的产生，把算法引向全局搜索。该算法采用抗体浓度来抑制规模比较大又不是最优解的抗体，并且以信息熵作为度量亲合力的指标，以抗体的期望繁殖率作为评价抗体的标准。123…-j…M-1M抗体1抗体i抗体N等位基因k1,k2,k3,…kl图4.4抗体基因的平均信息量(熵)免疫系统中的抗体多样性可以利用信息熵的概念表现[228]。设一个免疫系统由具有M个基因的N个抗体组成，}1,0{jk，如图7.5所示。根据信息学理论，第j个基因的平均信息量（entropy）)(NEj可以计算为：)1log()(1ijNiijjPPNE（4.6）其中ijP是第i个等位基因（allele）来自第j个基因的概率。注意在第j个基因的所有等位基因都是同样形式，平均信息量等于零。平均信息量由此可以看做一种度量免疫系统中认知多样性的方法。利用信息熵的概念情况下，一个说明抗原和抗体之间的关系，即目标和解之间结合强度；另一个负责抗体之间的协同关联程度，表达如下：)2(11)(EAijb（4.7）其中ijbA)(是第i个抗体和第j个抗体之间的亲合力。)2(E是抗体i和抗体j的平均信息量。)2(E等于0表示第i个抗体和第j个抗体基因相同。同样，抗体和抗原之间的亲合力定义为：k1ksks)1/(1,,wvwvEay（4.8）wvE,是抗体v和抗体w的信息熵。wvE,=0说明抗体v和w的基因完全匹配，这种情况下，wvay,=1。wya,表示抗体之间的相似程度。抗体v和抗原之间的亲合力为：)10(vvvoptoptax（4.9）这里，vopt是抗原和抗体v之间的结合强度，可根据具体问题，利用抗体对抗原的适应度fitness计算，fitness表示抗原(问题)和抗体(解)之间的适应值函数。如果是二进制，1vax时，说明抗体和抗原非常匹配，抗体是最优解。抗体的浓度用于表示某个抗体以及与其很相似的抗体的规模。评价解的浓度：NwvwvacNc11其中otherwiseayacvwvw,0,11，1为阈值。(4.10)采用浓度概念或期望值[3]来调节抗体的促进和抑制。在免疫系统中，当一种抗体受到抗原刺激或其它抗体刺激或抑制时，这种抗体的数量将发生变化。在群体更新中，亲合力大的抗体浓度提高，高到一定值就要受到抑制，反之相应提高浓度低的抗体的产生和选择概率。这与实际免疫系统中的抗体产生的促进和抑制是一致的。这种机制确保抗体群体更新的抗体多样性，避免未成熟收敛。抗体v的期望繁殖率(选择率)定义：NiivNssvvvaxcasaxe11,)1((4.11)otherwis