人工免疫算法ppt课件.ppt

人工免疫算法人工免疫算法1.基本介绍v生物免疫系统的免疫功能是通过抗体消灭人侵的病原体生物免疫系统的免疫功能是通过抗体消灭人侵的病原体(抗原抗原)而实现的模拟生物免疫系统的功能可以构造人工免疫系而实现的模拟生物免疫系统的功能可以构造人工免疫系统，基于人工免疫系统又可以设计人工免疫算法统，基于人工免疫系统又可以设计人工免疫算法(AIA)人工免疫算法和遗传算法工免疫算法和遗传算法(GA)、蚁群算法等都属于模拟自然界、蚁群算法等都属于模拟自然界生物行为的仿生算法生物行为的仿生算法v近来，有学者发现将生物免疫系统的一些行为引人到传统的近来，有学者发现将生物免疫系统的一些行为引人到传统的仿生算法中，构造免疫算法，可以提高算法的计算效率在仿生算法中，构造免疫算法，可以提高算法的计算效率在遗传算法中引人了生物免疫系统的抗体记忆机制遗传算法中引人了生物免疫系统的抗体记忆机制,即算法在完即算法在完成一个问题的求解以后成一个问题的求解以后,保留一定数量的较优解，在算法接受保留一定数量的较优解，在算法接受同类通体的求解时，可以将保留的较优解作为初始解，从而同类通体的求解时，可以将保留的较优解作为初始解，从而提高算法的计算效率。

提高算法的计算效率 2.人工免疫算法v在用人工免疫算法求解优化问题时，满足约在用人工免疫算法求解优化问题时，满足约束条件的最优解即是抗原；候选解即是抗体束条件的最优解即是抗原；候选解即是抗体一个抗体可以用一个字符表示用亲和力来一个抗体可以用一个字符表示用亲和力来描述抗体和抗原之间的匹配程度，用排斥力描述抗体和抗原之间的匹配程度，用排斥力来描述两个抗体之间的相似程度来描述两个抗体之间的相似程度2.1 人工免疫算法的基本步骤（1）输入问题的目标函数和约束条件，作为人工免）输入问题的目标函数和约束条件，作为人工免疫算法的抗原疫算法的抗原2）确定抗体的编码方式人工免疫算法的抗体可）确定抗体的编码方式人工免疫算法的抗体可以用字符串表示以用字符串表示3）产生初始抗体通常可以在解空间中随机产生）产生初始抗体通常可以在解空间中随机产生N个候选抗体个候选抗体N为抗体群中抗体的数目为抗体群中抗体的数目4）计算亲和力构造抗体的亲和力函数）计算亲和力构造抗体的亲和力函数f(B),f(B)越大说明抗体越大说明抗体B和抗原和抗原G之间匹配的越好之间匹配的越好5）计算排斥力构造抗体与抗体之间的排斥力函）计算排斥力。

构造抗体与抗体之间的排斥力函数数f(B1,B2)，， f(B1,B2)越大说明抗体越大说明抗体B1与抗体与抗体B2之间的差距越大计算抗体群中所有抗体与之间的差距越大计算抗体群中所有抗体与当前抗体群中最好抗体之间的排斥力当前抗体群中最好抗体之间的排斥力（（6）产生新的抗体构造人工免疫算子，抗体通过）产生新的抗体构造人工免疫算子，抗体通过人工免疫算子的作用产生新的抗体人工免疫算子的作用产生新的抗体7）计算新抗体的亲和力和排斥力若新抗体中有）计算新抗体的亲和力和排斥力若新抗体中有与抗原相匹配的抗体，或已满足预定的停机条与抗原相匹配的抗体，或已满足预定的停机条件则停机否则转下一步件则停机否则转下一步8）抗体选择按照）抗体选择按照“优胜劣汰优胜劣汰”的自然选择机制，的自然选择机制，在原有的在原有的N个有效抗体和新产生的若干个抗体中个有效抗体和新产生的若干个抗体中选择出选择出N个与抗原匹配得较好的抗体构成新的抗个与抗原匹配得较好的抗体构成新的抗体群，转体群，转6）在进行选择操作时，应依据抗体）在进行选择操作时，应依据抗体之间的排斥力限制进入新抗体群中的相同抗体之间的排斥力限制进入新抗体群中的相同抗体的数目，以保持抗体群中抗体的多样性，增强的数目，以保持抗体群中抗体的多样性，增强抗体群的免疫力，防止算法收敛于局部最优解。

抗体群的免疫力，防止算法收敛于局部最优解 2.2 人工免疫算子（1）字符换位算子，可分为单对字符换位算字符换位算子，可分为单对字符换位算子和多对字符换位算子子和多对字符换位算子（2）字符串移位算子，可分为单个字符串移字符串移位算子，可分为单个字符串移位算子和多个字符串移位算子位算子和多个字符串移位算子（3）字符串逆转算子，可分为单个字符串逆字符串逆转算子，可分为单个字符串逆转算子和多个字符串逆转算子转算子和多个字符串逆转算子 （4）字符串重组算子字符串重组算子（5）优质串保留算子优质串保留算子（6）新抗体引入算子若抗体群中的抗体失新抗体引入算子若抗体群中的抗体失去了多样性，则可以产生新的抗体替换掉去了多样性，则可以产生新的抗体替换掉其中的一部分，以保持抗体群中抗体的多其中的一部分，以保持抗体群中抗体的多样性3.人工免疫算法的收敛性分析v人工免疫算法生成的各代抗体群构成有限人工免疫算法生成的各代抗体群构成有限状态齐次马尔可夫（状态齐次马尔可夫（Markov）链v注：（注：（1）马尔可夫链，因安德烈）马尔可夫链，因安德烈·马尔可夫马尔可夫(A.A.Markov,1856－－1922)得名，是数学中得名，是数学中具有马尔可夫性质的离散时间随机过程。

具有马尔可夫性质的离散时间随机过程马尔可夫链是满足下面两个假设的一种随马尔可夫链是满足下面两个假设的一种随机过程：机过程：va、t+l时刻系统状态的概率分布只与时刻系统状态的概率分布只与t时刻时刻的状态有关，与的状态有关，与t时刻以前的状态无关；时刻以前的状态无关；vb、从、从t时刻到时刻到t+l时刻的状态转移与时刻的状态转移与t的值无的值无关一个马尔可夫链模型可表示为关一个马尔可夫链模型可表示为=(S,P,Q)，，S系统的状态空间，系统的状态空间，P状态转移概率矩阵，状态转移概率矩阵，Q初始概率分布初始概率分布v（2）许多数学研究者索性就以测度不可分许多数学研究者索性就以测度不可分性来定义遍历变换数学的研究指出，一性来定义遍历变换数学的研究指出，一个能保证遍历性（即测度不可分性）的更个能保证遍历性（即测度不可分性）的更强的条件是混合性强的条件是混合性 定理定理7说明人工免疫算法能够搜索到问题的最优解，说明人工免疫算法能够搜索到问题的最优解，但这并不意味着人工免疫算法是全局收敛的但这并不意味着人工免疫算法是全局收敛的v旅行商问题（旅行商问题（TSP）是一个典型的组合优化问题。

是一个典型的组合优化问题 4.1 抗体编码方式抗体编码方式4.人工免疫算法在旅行商问题中的应用 4.2 初始抗体的产生与预处理初始抗体的产生与预处理4.3 亲和力和排斥力的计算亲和力和排斥力的计算4.4 仿真实验仿真实验5.结论v人工免疫算法的新抗体产生方法比遗传算人工免疫算法的新抗体产生方法比遗传算法的新个体产生方法要灵活得多，人工免法的新个体产生方法要灵活得多，人工免疫算法比遗传算法具有更强的全局搜索能疫算法比遗传算法具有更强的全局搜索能力，是继遗传算法以来有一种具有广阔应力，是继遗传算法以来有一种具有广阔应用前景的仿生智能计算方法用前景的仿生智能计算方法Thank you！。