1、高等运筹学高等运筹学大连海事大学大连海事大学刘巍刘巍目录 第一篇第一篇 运筹学发展历史运筹学发展历史 第二篇第二篇 运筹学中的数学规划运筹学中的数学规划 第三篇第三篇 运筹学中的组合优化运筹学中的组合优化 第四篇第四篇 运筹学中的随机优化运筹学中的随机优化 第五篇第五篇 运筹学中的博弈论运筹学中的博弈论 第六篇第六篇 运筹学中管理科学运筹学中管理科学 第七篇第七篇 运筹学中智能计算运筹学中智能计算 第八篇第八篇 运筹学发展势态运筹学发展势态第六篇 运筹学中的智能计算 第二十三章 遗传算法 第二十四章 模拟退火 第二十五章 蚁群算法 第二十六章 人工神经网络 智能计算是涉及数学、运筹学、生命科学
2、、计算机科学等的一个交叉研究方向。智能计算主要是借鉴仿生学和拟物的思想，基于人们对生物体智能机理和某些自然规律的认识，采用数值计算的方法去模拟和实现人类的智能、生物智能和其它社会与自然的规律。智能计算的发展具有较悠久的历史。尽管20世纪50年代后，符号智能体系就取得了巨大的成功，但是80年代以后，这种经典人工智能的发展一度受到了阻碍。而后，智能计算在遗传算法和神经网络的带动下又迅猛发展。特别是，它与生命科学、系统科学联系在一起，使得计算机学者还有其他学科的学者也加入到智能计算的研究中来，极大地促进了智能计算的发展。虽然，至今没有一个统一的定义来精确刻画智能计算，但智能计算愈来愈引起人们广泛的关
3、注。尤其随着随机理论、模糊理论、不确定理论、人工神经网络理论的快速发展，智能计算为研究不精确、不完整、不确定性等间题提供了有效的处理技术和方法，并且在许多应用领域取得了长足的进展。第三十二章 遗传算法 遗传算法是模拟达尔文生物进化论的遗传学机理和自然选择的生物进化过程的计算模型，是通过模拟自然界的进化过程来搜索最优解的一种方法。它起源于20世纪50年代。1965年霍兰德首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。1975年他发表了著名专著自然系统和人工系统的适应性，系统地阐述了遗传算法的基本理论和方法。遗传算法与进化模型遗传算法与进化模型 一、遗传算法概述一、遗传算法概
4、述 二、遗传算法改进二、遗传算法改进 三、遗传算法的应用三、遗传算法的应用第1节 遗传算法概述 1 遗传算法起源 遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。2、基本遗传算法 基本遗传算法（Simple Genetic
5、Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成 （1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数 编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。函数优化示例 求下列一元函数的最大值：0.2)10sin()(xxxfSGA对于本例的编码 由于区间长度为3，求解结果精确到6位小数，因此可将自变
6、量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。几个术语 基因型：1000101110110101000111 表现型：0.637197 编码解码个体（染色体）基因初始种群 SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身
7、的要求而定。选择算子 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：niiiiFFP1/轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算
8、每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。单点交叉运算 交叉前：00000|01110000000010000 11100|00000111111000101 交叉后：00000|00000111111000101 111
9、00|01110000000010000交叉点交叉点变异算子 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。基本位变异算子 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为
10、1，则变异操作将其变为0。基本位变异算子的执行过程 变异前：000001110000000010000 变异后：000001110001000010000变异点变异点运行参数 （1）M ：种群规模 （2）T ：遗传运算的终止进化代数 （3）Pc ：交叉概率 （4）Pm：变异概率 SGA的框图 产生初始群体产生初始群体是否满足停止是否满足停止准则准则是是输出结果并输出结果并结束结束计算个体适应计算个体适应度值度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运基本位变异运算算否否产生新一代群产生新一代群体体执行执行M/2M/2次次3、遗传算法的特点 （1）群体搜索，易于并行化处理；（
11、2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。第2节 遗传算法的改进 遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。遗传算法的改进途径（1）对编码方式的改进 （2）对遗传算子 的改进（3）对控制参数的改进 （4）对执行策略的改进 对编码方式的改进 二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮
12、点数编码改善了遗传算法的计算复杂性。对遗传算子 的改进 排序选择 均匀交叉 逆序变异（1 1）对群体中的所有个体对群体中的所有个体按其适应度大小进行降序排按其适应度大小进行降序排序；序；（2 2）根据具体求解问题，根据具体求解问题，设计一个概率分配表，将各设计一个概率分配表，将各个概率值按上述排列次序分个概率值按上述排列次序分配给各个个体；配给各个个体；（3 3）以各个个体所分配到以各个个体所分配到的概率值作为其遗传到下一的概率值作为其遗传到下一代的概率，基于这些概率用代的概率，基于这些概率用赌盘选择法来产生下一代群赌盘选择法来产生下一代群体。体。对遗传算子 的改进 排序选择 均匀交叉 逆序变
13、异（1 1）随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字P=WP=W1 1W W2 2W Wn n ；（2 2）按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W Wi i=0=0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i=1=1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。对遗传算
14、子 的改进 排序选择 均匀交叉 逆序变异变异前：变异前：3 4 8|7 9 6 5|2 13 4 8|7 9 6 5|2 1变异前：变异前：3 4 8|5 6 9 7|2 13 4 8|5 6 9 7|2 1对控制参数的改进 Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。对控制参数的改进 Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和P
15、m，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰。对执行策略的改进 混合遗传算法 免疫遗传算法 小生境遗传算法 单亲遗传算法 并行遗传算法第第3节节 遗传算法的应用遗传算法的应用 1、遗传算法的应用领域 2、遗传算法的应用示例 1、遗传算法的应用领域（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度 （5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘 遗传算法应用于组合优化 随着问题规模的增大，组合优化问题的搜随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很索空间也急剧扩大，有时在计算机上
16、用枚举法很难甚至不可能求出其最优解。实践证明，遗传算难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有、布局优化、网络路由等具有NP难度的组合优难度的组合优化问题上取得了成功的应用。化问题上取得了成功的应用。2、遗传算法的应用示例 弹药装载问题（Ammunition Loading Problem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。AGSAA的基本原理 在弹药装载中，考虑到模拟退火算法的基
17、本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。AGSAA的编码方式 AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。AGSAA的解码和适应度函数 AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。弹药装载的启发式算法 （1）定位规则（Locating rule
18、）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Ordering rule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。遗传算子的选择 AGSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。交叉算子的选择 由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件
19、的个体，因此，AGSAA采用的是部分映射交叉算子。部分映射交叉算子 交叉前：8 7|4 3|1 2 6 5 1 2|5 7|8 3 4 6 交叉后：8 3|6 7|1 2 4 5 1 7|6 2|8 3 4 5第三十三章第三十三章 模拟退火算法与人与人工免疫算法简介工免疫算法简介 前言 为了找出地球上最高的山-珠穆朗玛峰，一群有志气的兔子们开始行动了！前言(C.)方案一：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。局部搜索法 前言(C.)方案二：兔子们吃了失忆药片
20、，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法 前言(C.)方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法蚁群算法 前言(C.)方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。模拟退火法 前言(C.)模拟退火算法得益于材料的统计力学的研究成果。
21、统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。前言(C.)算法的提出：模拟退火算法最早的思想由Metropolis等(1953)提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。前言(C.)在对固体物质进行模拟退火处理时，通常先将它加温熔化，使其中的粒子可自由运动，然后随着温度的逐渐下降
22、，粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能态的基态。前言(C.e)组合优化问题解空间中的每一点都代表一个具有不同目标函数值的解。所谓优化，就是在解空间中寻找目标函数最小（大）解的过程。若把目标函数看成能量函数，某一控制参数视为温度T，解空间当作形态空间，那么寻找基态的过程也就是求目标函数极小值的优化过程。模拟退火算法与模型物理退火过程：什么是退火？退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。模拟退火算法与模型(C.)物理退火过程：加温过程增强粒子的热运动，消除系统
23、原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。11.1 模拟退火算法 模拟退火算法(simulated annealing,简称SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法 模拟退火算法在某一初温下
24、，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。模拟退火算法11.1.1 物理退火过程和Metropolis准则简单而言，物理退火过程由以下三部分组成：加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。模拟退火算法等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的
25、封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。模拟退火算法Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为 ，若 则接受新状态j为当前状态；否则，若概率 大于 区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为Boltzmann常数。jiEE 和ijEE/)(expktEEpijr)1,0 模拟退火算法这种重要性采样过程在高温下可接受与当前状态能
26、量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。模拟退火算法11.1.2 模拟退火算法的基本思想和步骤1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，
27、最终得到问题的全局最优解。模拟退火算法标准模拟退火算法的一般步骤可描述如下：给定初温 ，随机产生初始状态 ，令 ；Repeat:Repeat 产生新状态 ；0tt 0ss 0k)(sGenetesjjjssrandomsCsCif 1,0)()(exp,1min 模拟退火算法 Until 抽样稳定准则满足；退温 ，并令 ；Until 算法终止准则满足；输出算法搜索结果。)(1kktupdatet1 kk模拟退火算法12.1.3 模拟退火算法关键参数和操作的设定从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计
28、将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。模拟退火算法状态产生函数设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。模拟退火算法状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；模拟退火算法随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引
29、入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min1,exp(-C/t)作为状态接受函数。模拟退火算法初温初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：模拟退火算法均匀抽样一组状态，以各状态目标值的方差为初温。随机产生一组状态，确定两两状态间的最大目标值差 ，然后依据差值，利用一定的函数确定初温。譬如 ，其中 为初始接受概率利用经验公式给出。|maxrptln/0rp模拟退火算法温度更新
30、函数温度更新函数，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。模拟退火算法内循环终止准则内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。模拟退火算法而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样
31、。模拟退火算法外循环终止准则外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：模拟退火算法设置终止温度的阈值；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；检验系统熵是否稳定。11.2 人工免疫系统人工免疫系统引言12免疫算法3典型的人工免疫系统ARTIS4基本免疫方法引言 人工免疫系统作为人工智能领域的重要分支人工免疫系统作为人工智能领域的重要分支，同神经网络及遗传算法一样也是智能信息，同神经网络及遗传算法一样也是智能信息处理的重要手段，已经受到越来越多的关注处理的重要手段，
32、已经受到越来越多的关注。它通过类似于生物免疫系统的机能，构造具它通过类似于生物免疫系统的机能，构造具有动态性和自适应性的信息防御体系，以此有动态性和自适应性的信息防御体系，以此来抵制外部无用、有害信息的侵入，从而保来抵制外部无用、有害信息的侵入，从而保证接受信息的有效性与无害性。证接受信息的有效性与无害性。背景O 在生物科学领域，人们对进化、遗传和免疫等自然在生物科学领域，人们对进化、遗传和免疫等自然 现现象已经进行了广泛而深入的研究象已经进行了广泛而深入的研究；O 进化算法是建立在模仿生物遗传与自然选择基础上的进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广
33、泛；一种并行优化算法，其性能优异、应用广泛；O 进化算子在为每个个体提供了进化机会的同时，也无进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；可避免地产生了退化的可能；O 大多数待求问题有可以利用的先验知识或特征信息，大多数待求问题有可以利用的先验知识或特征信息，故可以利用这些信息来抑制进化过程中的退化现象；故可以利用这些信息来抑制进化过程中的退化现象；O 生物免疫理论为改进原有算法的性能，建立集进化与生物免疫理论为改进原有算法的性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础免疫机制于一体的新型全局并行算法奠定了基础。一门新兴的研究领域一门新兴的研究领域
34、Farmer等人在等人在1986年首先在工程领域提年首先在工程领域提出免疫概念出免疫概念；Varela等人受免疫网络学说的启发，提等人受免疫网络学说的启发，提出并进而完善免疫网络模型。出并进而完善免疫网络模型。人工免疫网络模型人工免疫网络模型 独特型免疫网络（独特型免疫网络（Jerne）；）；互联耦合免疫网络（互联耦合免疫网络（Ishiguro）；）；免疫反应网络（免疫反应网络（Mitsumoto）；）；对称网络（对称网络（Hoffmann）；）；多值免疫网络（多值免疫网络（Tang）.免疫学习算法免疫学习算法 反面选择算法（反面选择算法（Forrest）；）；免疫学习算法（免疫学习算法（Hu
35、nt&Cooke）；）；免疫遗传算法（免疫遗传算法（Chun）；）；免疫免疫Agent算法（算法（Ishida）；）；免疫网络调节算法（免疫网络调节算法（Wang&Cao）；）；免疫进化算法（免疫进化算法（Jiao&Wang）国际研究 1996年，日本，基于免疫性系统的国际年，日本，基于免疫性系统的国际专题讨论会，提出并确认人工免疫系统专题讨论会，提出并确认人工免疫系统（AIS）的概念）的概念；1997年，年，IEEE的的SMC组织专门成立了人组织专门成立了人工免疫系统及应用的分会组织；工免疫系统及应用的分会组织；目前，几乎所有有关人工智能领域的学目前，几乎所有有关人工智能领域的学术会议都收录
36、术会议都收录AIS方面的论文。方面的论文。应用 自动控制 故障诊断 模式识别 图象识别 优化设计 机器学习 网络安全AIS在控制领域中的应用 PID型免疫反馈控制器（型免疫反馈控制器（Takahashi）；）；机器人控制（机器人控制（Mitsumoto,Ishiguro,Lee）；）；控制系统的设计（控制系统的设计（Ishida）；）；复杂动态行为建模和自适应控制（复杂动态行为建模和自适应控制（Kumak）；）；倒摆的控制（倒摆的控制（Bersini）。）。AIS在故障诊断中的应用 基于相关识别特性的免疫网络模型用于基于相关识别特性的免疫网络模型用于故障诊断的方法（故障诊断的方法（Ishida
37、）；）；通过构造大规模独特型免疫网络来建立通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统（用于在线服务的故障诊断系统（Ishiguru）。）。AIS在模式识别中的应用Hunt等人开发了一种具有学习能力的人工等人开发了一种具有学习能力的人工免疫系统并用于模式识别。免疫系统并用于模式识别。AIS在联想记忆中的应用Gilbert等人采用免疫网络模型设计了一种等人采用免疫网络模型设计了一种内容可访的自动联想记忆系统并用于图内容可访的自动联想记忆系统并用于图像识别。像识别。AIS在优化设计中的应用 永磁同步电动机的参数修正的优化设计永磁同步电动机的参数修正的优化设计；电磁设备的外形优化；电
38、磁设备的外形优化；VLSI印刷线路板的布线优化设计；印刷线路板的布线优化设计；函数测试；函数测试；旅行商问题的求解；旅行商问题的求解；约束搜索优化问题和多判据设计问题约束搜索优化问题和多判据设计问题；AIS在网络安全的应用 数据检测（数据检测（Forrest）；）；病毒检测（病毒检测（Kephart）；）；UNIX过程监控过程监控（Forrest）。国际研究新动向之一 以开发新型的智能系统方法为背景，研究基于生物免疫系统机理的智能系统理论和技术，同时将AIS与模糊系统、神经网络和遗传算法等软计算技术进行集成，并给出其应用方法。国际研究新动向之二 基于最新发展的免疫网络学说进一步建立并完善模糊、
39、神经和其它一些专有类型的人工免疫网络模型及其应用方法。国际研究新动向之三 将人工免疫系统与遗传系统的机理相互结合，并归纳出各种免疫学习算法。比如：免疫系统的多样性遗传机理和细胞选择机理可用于改善原遗传算法中对局部搜索问题不是很有效的情况；独特型网络机理可用于免疫系统中的遗传部分以避免系统出现早熟现象；发展用于处理受约束的遗传搜索和多准则问题的免疫学习算法等。国际研究新动向之四 基于免疫反馈和学习机理，设计自调整、自组织和自学习的免疫反馈控制器。展开对基于免疫反馈机理的控制系统的设计方法和应用研究，这有可能成为工程领域中种新型的智能控制系统，具有重要的理论意义与广泛的应用前景。国际研究新动向之五
40、 进一步研究基于免疫系统机理的分布式自治系统。分布式免疫自治系统在智能计算、系统科学和经济领域将会有广阔的应用前景。国际研究新动向之六 发展基于DNA编码的人工免疫系统以及基于DNA计算的免疫算法。尝试将DNA计算模型引入人工免疫系统中，研究一种基于DNA计算与AIS相结合的，有较强抗干扰能力和稳定性能的智能系统国际研究新动向之七 近年来有学者已开始研究B细胞抗体网络的振荡、混浊和稳态等非线性特性，不过其工作才刚刚开始。人们应进一步借助非线性的研究方法来研究免疫系统的非线性行为，拓宽非线性科学的研究范围。国际研究新动向之八 进一步发展AIS在科学和工程上的应用，并研制实际产品，如研制在复杂系统
41、的协调控制、故障检测和诊断、机器监控、签名确认、噪声检测、计算机与网络数据的安全性、图像与模式识别等方面的实际产品。生物免疫的启示 在生物自然界中，免疫现象普遍存在，并对物种在生物自然界中，免疫现象普遍存在，并对物种的的 生存与繁衍生存与繁衍 发挥着重要的作用；发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；由其构成的器官来完成的；生物免疫主要有两种类型：生物免疫主要有两种类型：特异性免疫特异性免疫（Specific Immunity），），非非特异性免疫反应特异性免疫反应（Nonspecific Immunity）
42、；）；生物免疫系统是通过自我识别、相互刺激与制约生物免疫系统是通过自我识别、相互刺激与制约而构成了一个而构成了一个 动态平衡的网络结构动态平衡的网络结构。免疫生物学的基本概念抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。免疫系统的主要功能OO 免疫防御即机体防御病原微生物的感染；OO 免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；OO 免疫监视即机体通过免疫功能防止或消除体内细胞
43、在新陈代谢过程中发生突变的和异常的细胞大于阈值spam记忆细胞检测器亲和力计算不大于阈值大于阈值不大于阈值亲和力计算正文特征提取用户反馈未成熟细胞检测器hamspam特征库随机特征项检测到spam？删除该未成熟检测器克隆记忆YN用户反馈更新检测器、spam特征库基本免疫方法 1.免疫识别 2.免疫学习 3.免疫记忆 4.克隆选择免疫识别 免疫识别是免疫系统的主要功能，同时也是AIS的核心之一，而识别的本质是区分“自我”和“非我”。核心机制是根据识别的对象特征进行编码，定义一个自我集合并随机产生一系列检测器，用于检测自我集合的变化。根据阴性选择原理，若检测集合与自我集合匹配，则完成匹配任务，机体
44、发现病变。基本免疫方法(1)定义自己(self)为一个字符串集合S，每个字符串由n个字母组成，字符串可以是一个网络数据包，电子邮件特征向量电子邮件特征向量或程序的一般行为模式。(2)产生一个初始监测器集合R。(3)监测器集合中每个监测器经历阴性选择过程。其中每一个监测器都不能与集合S中的任何一个字符串相匹配，否则就从监测器集合中删去对应的检测器。(4)通过与R集合的匹配匹配不断监测S的变化，一旦发生任何匹配，则说明S集发生了变化，即有外来抗原侵入。基本免疫方法 在最初的算法描述中，候选的监测器是随机产生的，然后测试以删除与自身字串相匹配的监测器，算法中采用的匹配规则是r-连续位匹配连续位匹配，
45、即当两个字符串至少存在连续r位相同是才发生匹配。该过程重复进行，直到所需数量的监测所需数量的监测器器被产生出来。通常用概率分析方法概率分析方法来估算为了满足一定的可靠性所应有的监测器的数目。基本免疫方法免疫学习 免疫识别过程同时也是一个学习的过程，学习的结果是免疫细胞的个体亲和度提高、群体规模扩大，并且最优个体以免疫记忆的形式得到保存。当机体重复遇到同一抗原时，由于免疫记忆机制的作用，免疫系统对该抗原的应答速度大大提高，并且产生高亲和度的抗体去除病原，这个过程是一个增强式学习过程。而且可以对结构类似的抗而且可以对结构类似的抗原进行识别原进行识别。基本免疫方法 免疫学习一般有以下几种途径:(a)
46、对同一抗原进行重复学习，属于增强式学习。(b)亲合度成熟，对应于AIS中的个体经遗传操作后其亲合度逐步提高的过程，属于遗传学习。(c)低度的重复感染，对应于AIS的重复训练过程。(d)对内生和外生抗原的交叉应答，属于联想式学习，对应于联想记忆机制。基本免疫方法免疫记忆 当免疫系统初次遇到一种抗原时，淋巴细胞需要一定的时间进行调整以更好地识别抗原，并在识别结束后以最优抗体以最优抗体的形式保留对该抗原的记忆信息的形式保留对该抗原的记忆信息。而当免疫系统再次遇到相同或者结构相似的抗原时，在联想记忆的作用下，其应答速度将大大提高。免疫记忆主要体现在再次免疫应答和交叉免疫应答时，可以大大加速优化搜索过程
47、，加快学习进程并提高学习质量。基本免疫方法克隆选择 克隆选择原理最先由Jerne提出，后由Burnet给予完整阐述。其大致内容为:当淋巴细胞实现对抗原的识别(即抗体和抗原的亲和度超过一定阈值)后，B细胞被激活并增殖复制产生B细胞克隆，随后克隆细胞经历变异过程，产生对抗原具有特异性的抗体。克隆选择理论描述了获得性免疫的基本特性，并且声明只有成功识别抗原的免疫细胞才得以增殖。经历变异后的免疫细胞分化为效应细胞变异后的免疫细胞分化为效应细胞(抗抗体体)和记忆细胞两种和记忆细胞两种。基本免疫方法 克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗传变异分化为多样性抗体细胞和记忆细胞。克隆
48、选择对应着一个亲和度成熟的过程，即对抗原亲和度较低的个体对抗原亲和度较低的个体在克隆选择机制的作用下，经历增殖复制和变异操作后，其亲和度逐步提高而亲和度逐步提高而“成熟成熟”的过程。因此亲和度成熟本质上是一个达尔文式的选择和变异的过程，克隆选择原理通过采用交叉、变异等遗传算子交叉、变异等遗传算子和相应的群体控制机制和相应的群体控制机制实现。基本免疫方法免疫算法 一般的免疫算法可分为三种情况:模仿免疫系统抗体与抗原识别，结合抗体产生过程而抽象出来的免疫算法;基于免疫系统中的其他特殊机制抽象出的算法，例如克隆选择算法;与遗传算法等其他计算智能融合产生的新算法，例如免疫遗传算法。免疫算法的一般步骤
49、初始抗体生成抗原识别抗体促进和抑制满足终止条件？群体更新结束亲和力计算记忆细胞分化YN免疫算法(1)识别抗原：免疫系统确认抗原入侵。(2)产生初始抗体群体：激活记忆细胞产生抗体，清除以前出现过的抗原，从包含最优抗体(最优解)的数据库中选择出来一些抗体。(3)计算亲和力：计算抗体和抗原之间的亲和力。(4)记忆细胞分化：与抗原有最大亲和力的抗体加给记忆细胞。由于记忆细胞数目有限，新产生的与抗原具有更高亲和力的抗体替换较低亲和力的抗体。(5)抗体促进和抑制：高亲和力抗体受到促进，高密度抗体受到抑制。通常通过计算抗体存活的期望值来实施。(6)抗体产生:对未知抗原的响应，产生新淋巴细胞免疫算法阴性选择算
50、法 Procedure Begin 随机生成大量的候选检测器(即免疫细胞)/*初始化*/While一个给定大小的检测器集合还没有被产生do/*耐受*/Begin 计算出每一个自体元素和一个候选检测器之间的亲和力;If这个候选的检测器识别出了自体集合中的任何一个元素Then这个检测器就要被消除掉;Else把这个检测器放入检测器集合里面;/*该检测器成熟*/利用经过耐受的检测器集合，检测系统以找出变种;End;End.常见免疫算法克隆选择算法 Begin 随机生成一个属性串(免疫细胞)的群体 While收敛标准没有满足do Begin While not所有抗原搜索完毕do;*/初始化*/Begi
