第7章 计算智能

2023/10/131第7章计算智能2023/10/132内容7.1人工免疫算法7.2蚁群算法7.3粒子群算法7.4模拟退火算法2023/10/1337.1人工免疫算法7.1.1自然免疫系统7.1.2人工免疫算法7.1.3人工免疫算法的应用2023/10/1347.1.1自然免疫系统（1）免疫是指肌体对感染具有抵抗能力而不患疫病或传染病。生物免疫系统是一个由众多组织、细胞与分子等构成的复杂系统，它由免疫活性分子、免疫细胞、免疫组织和器官组成。具有识别机制，能够从人体自体细胞（被感染的细胞）或自体分子和外因感染的微组织中检测并消除病毒等病原体。

2023/10/1357.1.1自然免疫系统（2）免疫系统的主要功能有以下三个方面：1.免疫防御：指机体排斥外源性抗原异物的能力。这是机体藉以自净、不受外来物质干扰和保持物种纯洁的生理机制。2.免疫自稳：指机体识别和清除自身衰老残损的组织、细胞的能力，这是机体藉以维持正常内环境稳定的重要机制。3.免疫监视：指机体杀伤和清除异常突变细胞的能力，机体藉以监视和抑制恶性肿瘤在体内生长。免疫监视功能低下，则机体易患恶性肿瘤。2023/10/1367.1.2人工免疫算法（1）目前主要存在两种类型的免疫算法：一种是基于免疫学原理的免疫算法；一种是与遗传算法等其他计算智能融合的免疫遗传和进化算法。人工免疫算法模型主要考虑三个方面：抗原、抗体的形式抗原与抗体以及抗体与抗体之间相互作用机制整个系统的构造2023/10/1377.1.2人工免疫算法（2）人工免疫算法的步骤：步1识别抗原。免疫系统确认抗原入侵；步2产生初始抗体群体。激活记忆细胞产生抗体，清除以前出现过的抗原，从包含最优抗体（最优解）数据库中选择出来一些抗体。初始抗体群体也可以随机产生或依据先验知识产生；步3抗体评价。抗体与抗原接触，然后，计算抗原和抗体之间的亲和力，对抗体进行评价；步4产生记忆。在记忆库规模范围内，将群体中优良抗体存入记忆库。与抗原有最大亲和力的抗体加给记忆细胞。由于记忆细胞数目有限，新产生的与抗原具有更高亲和力的抗体替换较低亲和力的抗体；2023/10/1387.1.2人工免疫算法（3）步5结束判断。依据问题所确定的结束条件，判断记忆库中的抗体是否满足要求，满足，则结束。步6抗体的亲和力成熟。对抗体群体进行克隆选择和超变异操作，改变群体中的抗体，使群体在保持多样性的情况下与抗原更好地匹配；步7群体控制及新抗体群体产生，即抗体的死亡和产生。在群体规模的范围内，对抗体群体与记忆库中的抗体进行评价，依据群体规模参数将刺激度最差的一部分抗体删除，形成新一代抗体群体。高亲和力抗体受到促进，高密度抗体受到抑制。转步3。2023/10/1397.1.2人工免疫算法（4）免疫算法中一个关键问题是对抗体的评价，评价取决于四个因素抗体与抗原的匹配度抗体间的相互刺激作用抑制作用抗体的奖励2023/10/13107.1.3人工免疫算法的应用

1.计算机安全：自然免疫系统本身就是一个分布的、具有自适应性和自学习能力的生物入侵检测系统，它在抵抗病毒和细菌等病原体的入侵方面担当着与计算机入侵检测系统类似的任务。2.故障诊断：将免疫机理设计用于软件或硬件系统的故障诊断的算法或模型，并用现代计算机系统编程实现3.智能优化：在函数优化、组合优化、调度问题等方面得到应用并取得了很好的效果。4.数据挖掘：采用人工免疫模型的数据挖掘任务目前主要集中在数据聚类分析、数据浓缩、归类任务等方面。2023/10/13117.2蚁群算法7.2.1蚂蚁系统的原理7.2.2蚁群算法模型7.2.3蚁群算法的应用2023/10/13127.2.1蚂蚁系统的原理多里科用图形描述了蚂蚁系统的原理：2023/10/13137.2.2蚁群算法模型（1）人工蚂蚁与真实蚂蚁的相似之处：（1）人工蚂蚁也具有信息素释放和挥发机制，并且通过信息素进行间接的通讯。（2）人工蚂蚁也利用正反馈机制，以信息素作为反（3）人工蚂蚁也是采用概率机制进行状态转移（4）人工蚂蚁也是一个相互合作的个体。2023/10/13147.2.2蚁群算法模型（2）求解旅行商问题的蚁群算法步骤：步1

初始化：设蚂蚁个数m，最大进化代数NCmax，当前进化代数NC=0，时间t=0，每条边（两个城市间）上的信息素浓度将m个蚂蚁随机地置于n个城市上。步2

禁忌表中的索引。将蚂蚁k的起点城市加入到禁忌表中tabuk；步3如果禁忌表不满，则：s=s+1；对每只蚂蚁k，计算转移概率，使用轮盘赌方法选择下一个要到的城市；蚂蚁k移到城市j，并将城市j加入到tabuk中；2023/10/13157.2.2蚁群算法模型（3）步4

（1）对每只蚂蚁，计算蚂蚁k走过的周游长度Lk；更新当前的最优路径。（2）对每条边，若蚂蚁k在本次周游中经过lij，则更新边lij的信息素：步5

对每条边，计算信息素量：步6

t=t+1，NC=NC+1。并对每条信息度增加浓度为0;步7如果NC<NCmax，且没出现停滞现象，则清空所有禁忌表，转步2，否则，输出最优路径，算法终止。2023/10/13167.2.3蚁群算法的应用（1）静态组合优化问题，如：经典旅行商问题（TSP，0-1背包问题（O-1KP），二次分配问题（QAP），车间任务调度问题（JSP），车辆路径问题（VRP），图着色问题（GCP），有序排列问题（SOP）等等。（2）动态组合优化问题，动态问题被定义为一些量的函数，这些量的值由隐含系统动态设置，因此，问题在运行时间内是变化的，而优化算法需在线适应不断变化的环境。如网络路由问题等。蚁群算法的具体应用也可以分为路由、分配、调度、子集、机器学习、网络路由等类型的问题2023/10/13177.3粒子群算法7.3.1粒子群系统7.3.2粒子群算法模型7.3.3粒子群算法的应用2023/10/13187.3.1粒子群系统粒子群算法是对粒子群系统的模拟，主要是模拟鸟群的捕食行为。一群鸟在随机地搜索食物，它们通过与同伴间的相互通信确定寻找食物的最短路径。这是一种基于邻域原理的找到食物的最简单、有效的策略，即搜寻目前离食物最近的鸟的邻域。依靠群体中个体之间的交互作用，通过像近邻学习和历史学习，达到对解进行优化的目的。2023/10/13197.3.2粒子群算法模型（1）基本的粒子群算法步骤：步1初始化：t=0，对每个微粒pi，在允许范围内随机设置其初始位置xi(t)和速度vi(t)，每个微粒pi的pBesti设为其初始位置适应值，pBesti中的最好值设为gBest；步2评价每个微粒的适应值τ(xi(t))；步3对每个微粒pi，如果τ(xi(t))

<pBesti

，则pBesti=τ(xi(t))，xpBesti

=xi(t)；步4对每个微粒pi，如果τ(xi(t))

<gBes