第4讲免疫算法概要VIP专享VIP免费

第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)At7.终止条件一般设置为最大迭代次数或求解精度或者二者的结合，获得问题解图4.2一般免疫算法第2步中，初始抗体通常是在解空间中用随机的方法产生。与进化算法相似，一般需要对抗体进行编码，并且遵循完备性、健全性、和非冗余性要求。第3步中，比如二进制编码情况，一般采用海明距离表示，实数编码采用欧氏距离等，其他各种距离方法可参见第...