计算智能与深度学习 课件 8禁忌搜索算法、9人工免疫系统、10粗糙集

第二章禁忌搜索算法

智能优化计算山东大学威海分校信息工程学院20092.1局部搜索

2.1.1邻域的概念

2.1.2局部搜索算法

2.1.3局部搜索示例

2.2禁忌搜索

2.2.1算法的主要思路

2.2.2禁忌搜索示例2.3禁忌搜索的关键参数和操作

2.3.1变化因素

2.3.2禁忌表

2.3.3其他

2.4禁忌搜索的实现与应用

2.4.130城市TSP问题（d*=423.741byDBFogel）

2.4.2基于禁忌搜索算法的系统辨识智能优化计算山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算函数优化问题中

在距离空间中，通常的邻域定义是以一点为中心的一个球体；组合优化问题中

2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算例

TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定义它的邻域映射为2－opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。例如：x=(1,2,3,4)，则C42=6，N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算例

TSP问题解的邻域映射可由2－opt，推广到k－opt，即对k个元素按一定规则互换。邻域概念的重要性

邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算STEP1

选定一个初始可行解x0，记录当前最优解xbest:=x0,T=N(xbest)；STEP2

当T\{xbest}=Φ时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f(xnow)<f(xbest)，则xbest:=xnow

，T=N(xbest)；否则T:=T\S；重复STEP2。2.1.2局部搜索算法

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题

初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法1：全邻域搜索

第1步

N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

ABCDE山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法1：全邻域搜索

第2步

N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法2：一步随机搜索

第1步

从N(xbest)中随机选一点，如xnow=(ACBDE)，对应目标函数为f(xnow)=43<45

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法2：一步随机搜索

第2步

从N(xbest)中又随机选一点，如xnow=(ADBCE)，对应目标函数为f(xnow)=44>43

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题解（solution)的表示：向量五个任务分到三台计算机上的一种分配方安：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域（Neighborhood）定义我们定义两种邻域映射：1、单向移动（one-waymoveortransfer):重新分配一个任务从其当前机器到另一台机器。2、双向移动（two-wayexchange):交换分配于两台不同机器上的任务。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）对于目标1最小化执行与通信代价之和。任务重分配收益（reassignmentgain)就是代价（cost）的减少。

这里xip表示第i个任务在第p台机器上的执行代价（时间）2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题约束惩罚收益？2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题对于目标2，最小化周转时间（turnaroundtime)或者说最小化完成时间（completiontime)

邻域结构的定义：分流负载最终的机器（themostloadedmachine,i.e.criticalmachine):transferandexchange。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算算法的提出

禁忌搜索（Tabusearch）是局部邻域搜索算法的推广，FredGlover在1986年提出这个概念，进而形成一套完整算法。算法的特点禁忌——禁止重复前面的工作。跳出局部最优点。2.2.1算法的主要思路

/~glover/山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。2.2.2禁忌搜索示例

山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第1步解的形式禁忌对象及长度候选解

f(x0)=42.2.2禁忌搜索示例

ABCDBCDABC对换评价值CD4.5BC7.5BD8☻山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第2步解的形式禁忌对象及长度候选解

f(x1)=4.52.2.2禁忌搜索示例

ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5☻T山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第3步解的形式禁忌对象及长度候选解

f(x2)=3.52.2.2禁忌搜索示例

ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第4步解的形式禁忌对象及长度候选解

f(x3)=7.5

禁忌长度的选取2.2.2禁忌搜索示例

ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第4步（如果减小禁忌长度）解的形式禁忌对象及长度候选解

f(x3)=7.52.2.2禁忌搜索示例

ACBDBCDAB12C0对换评价值CD4.5BC4.5BD3.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第5步解的形式禁忌对象及长度候选解

f(x4)=4.52.2.2禁忌搜索示例

ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第6步解的形式禁忌对象及长度候选解

f(x5)=82.2.2禁忌搜索示例

ADCBBCDAB20C1对换评价值CD3.5BC4.5BD4☻TT山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌长度：禁忌的步数状态变化（三种变化）解的简单变化解向量分量的变化目标值变化

2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算解的简单变化

2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算向量分量的变化

设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为

(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)

即只有第i个分量发生变化。也包含多个分量变化的情形。2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算目标值的变化

目标值的变化隐含着解集合的变化。2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化禁忌长度为4，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第1步——

xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ACBED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第3步——

xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)}Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。2.3.2禁忌表

xnext=(ABCED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第4步——

xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)}Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。2.3.2禁忌表

xnext=(AECBD)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第5步——

xnow=(AECBD)，f(xnow)=44，H={(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)}Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。2.3.2禁忌表

xnext=(AEDBC)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第1步——

xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。2.3.2禁忌表

xnext=(ACBED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第3步——

xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)}Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)}。2.3.2禁忌表

xnext=(AEBCD)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化第1步——

xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={45，43}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ADBCE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌长度的选取

（1）t可以为常数，易于实现；（2），t是可以变化的数，tmin和tmax是确定的。

tmin和tmax根据问题的规模确定，t的大小主要依据实际问题、实验和设计者的经验。（3）tmin和tmax的动态选择。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌长度的选取禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。（例）2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算特赦（藐视）原则（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；（3）基于影响力的规则，可以特赦对目标值影响大的对象。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算候选集合的确定（1）从邻域中选择若干目标值最佳的邻居入选；（2）在邻域中的一部分邻居中选择若干目标值最佳的状态入选；（3）随机选取。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算评价函数（1）直接评价函数，通过目标函数的运算得到评价函数；（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算记忆频率信息根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。例如：如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算记忆频率信息可记录的信息：（1）静态频率信息：解、对换或目标值在计算中出现的频率；（2）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算终止规则（1）确定步数终止，无法保证解的效果，应记录当前最优解；（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。2.3.3其他

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;4502.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算算法流程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算初始条件禁忌长度为50

从2－opt邻域中随机选择200个邻域解，选出其中100个最佳解组成候选集终止步数20002.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算初始条件禁忌长度为10

从2－opt邻域中随机选择200个邻域解，选出其中100个最佳解组成候选集终止步数2000

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程比较

禁忌长度50禁忌长度102.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算解决连续系统优化的禁忌搜索算法邻域——引入超矩形来定义一个点的邻域

2.4.2基于禁忌搜索算法的系统辨识山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算解决连续系统优化的禁忌搜索算法禁忌表——将当前点及其目标函数值放入禁忌表中，作为禁忌区域的中心首先判断点x的目标函数值f(x)，如果f(x)跟禁忌表中的任一个函数值都不接近，则点x没被禁忌；如果f(x)跟禁忌表中点x*的函数值f(x*)接近，则判断点x跟点x*是否接近，如果接近，则点x

被禁忌，否则就没被禁忌。2.4.2基于禁忌搜索算法的系统辨识山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算解决连续系统优化的禁忌搜索算法特赦原则——

若点x

的目标函数值优于目前为止搜索到的最优点的目标函数值，则点x

满足特赦规则。终止原则——

当达到最大迭代步数，或在一个给定的迭代步数内算法搜索到的最优点没有改善时，将终止迭代。2.4.2基于禁忌搜索算法的系统辨识山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算将系统辨识转化为优化问题待辨识模型：估计模型输出：准则函数：优化问题：2.4.2基于禁忌搜索算法的系统辨识山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算辨识结果辨识模型：

统计结果：

2.4.2基于禁忌搜索算法的系统辨识山东大学威海分校信息工程学院2009第二章结束智能优化计算山东大学威海分校信息工程学院2009免疫进化理论的研究

王磊西安电子科技大学雷达信号处理国家重点实验室，710071

wanglei@

导师：焦李成教授西安电子科技大学研究生院，710071

lchjiao@89主要内容

研究背景与现状； 免疫进化算法； 免疫神经网络； 计算机免疫安全

系统的探索。90研究背景在生物科学领域，人们对进化、遗传和免疫等自然现象已经进行了广泛而深入的研究；进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广泛；进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；大多数待求问题又可利用先验知识或特征信息，故可以利用这些信息来抑制进化过程中的退化现象；生物免疫理论为改进原有算法性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础。91ArtificialImmuneSystem－AIS人工智能信息处理系统的研究脑神经系统（神经网络）；遗传系统（进化计算）；免疫系统（人工免疫系统）。92

一门新兴的研究领域。AIS的研究历史Farmer等人在1986年首先在工程领域提出免疫概念；Varela等人受免疫网络学说的启发，提出并进而完善免疫网络模型。93

人工免疫网络模型AIS的研究现状之一独特型免疫网络（Jerne）；互联耦合免疫网络（Ishiguro）；免疫反应网络（Mitsumoto）；对称网络（Hoffmann）；多值免疫网络（Tang）.94

免疫学习算法AIS的研究现状之二反面选择算法（Forrest）；免疫学习算法（Hunt&Cooke）；免疫遗传算法（Chun）；免疫Agent算法（Ishida）；免疫网络调节算法（Wang&Cao）；免疫进化算法（Jiao&Wang）.95

国际研究AIS的研究现状之三1996年，日本，基于免疫性系统的国际专题讨论会，提出并确认人工免疫系统（AIS）的概念；1997年，IEEE的SMC组织专门成立了人工免疫系统及应用的分会组织；目前，几乎所有有关人工智能领域的学术会议都收录AIS方面的论文。96AIS的应用

自动控制

故障诊断

模式识别

图象识别

优化设计

机器学习

网络安全97AIS在控制领域中的应用PID型免疫反馈控制器（Takahashi）；机器人控制（Mitsumoto,Ishiguro,Lee）；控制系统的设计（Ishida）；复杂动态行为建模和自适应控制（Kumak）；倒摆的控制（Bersini）。98AIS在故障诊断中的应用基于相关识别特性的免疫网络模型用于故障诊断的方法（Ishida）；通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统（Ishiguru）。99AIS在模式识别中的应用Hunt等人开发了一种具有学习能力的人工免疫系统并用于模式识别。100AIS在联想记忆中的应用Gilbert等人采用免疫网络模型设计了一种内容可访的自动联想记忆系统并用于图像识别。101AIS在优化设计中的应用永磁同步电动机的参数修正的优化设计；电磁设备的外形优化；VLSI印刷线路板的布线优化设计；函数测试；旅行商问题的求解；约束搜索优化问题和多判据设计问题；102AIS在网络安全的应用数据检测（Forrest）；病毒检测（Kephart）；UNIX过程监控（Forrest）。103国际研究新动向之一以开发新型的智能系统方法为背景，研究基于生物免疫系统机理的智能系统理论和技术，同时将AIS与模糊系统、神经网络和遗传算法等软计算技术进行集成，并给出其应用方法。104国际研究新动向之二基于最新发展的免疫网络学说进一步建立并完善模糊、神经和其它一些专有类型的人工免疫网络模型及其应用方法。105国际研究新动向之三将人工免疫系统与遗传系统的机理相互结合，并归纳出各种免疫学习算法。比如：免疫系统的多样性遗传机理和细胞选择机理可用于改善原遗传算法中对局部搜索问题不是很有效的情况；独特型网络机理可用于免疫系统中的遗传部分以避免系统出现早熟现象；发展用于处理受约束的遗传搜索和多准则问题的免疫学习算法等。106国际研究新动向之四基于免疫反馈和学习机理，设计自调整、自组织和自学习的免疫反馈控制器。展开对基于免疫反馈机理的控制系统的设计方法和应用研究，这有可能成为工程领域中种新型的智能控制系统，具有重要的理论意义与广泛的应用前景。107国际研究新动向之五进一步研究基于免疫系统机理的分布式自治系统。分布式免疫自治系统在智能计算、系统科学和经济领域将会有广阔的应用前景。108国际研究新动向之六发展基于DNA编码的人工免疫系统以及基于DNA计算的免疫算法。尝试将DNA计算模型引入人工免疫系统中，研究一种基于DNA计算与AIS相结合的，有较强抗干扰能力和稳定性能的智能系统。109国际研究新动向之七近年来有学者已开始研究B细胞—抗体网络的振荡、混浊和稳态等非线性特性[61]，不过其工作才刚刚开始。人们应进一步借助非线性的研究方法来研究免疫系统的非线性行为，拓宽非线性科学的研究范围。110国际研究新动向之八进一步发展AIS在科学和工程上的应用，并研制实际产品，如研制在复杂系统的协调控制、故障检测和诊断、机器监控、签名确认、噪声检测、计算机与网络数据的安全性、图像与模式识别等方面的实际产品。111免疫进化算法的研究第一部分112生物免疫的启示在生物自然界中，免疫现象普遍存在，并对物种的

生存与繁衍

发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物免疫主要有两种类型：

特异性免疫（SpecificImmunity）

非特异性免疫反应（NonspecificImmunity）生物免疫系统是通过自我识别、相互刺激与制约而构成了一个

动态平衡的网络结构

。113免疫生物学的基本概念

抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。

抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。114免疫系统的主要功能

免疫防御即机体防御病原微生物的感染；

免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；

免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。115免疫系统的主要特点

免疫识别

免疫应答

免疫耐受

免疫记忆

免疫调节116算法研究生物学概念与理论方法：工程计算方法117进化＋免疫

传统进化算法是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。

每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时，操作的可变程度较小。118基本概念

染色体 表示待求问题的解的形式的一种数据结构。

基因构成染色体的最基本的数据单位。

个体 具有某类染色体结构的一种特例。119基本概念

抗原: 所有可能错误的基因，即非最佳个体的基因。

疫苗: 根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。

抗体: 根据疫苗修正某个个体的基因所得到的新个体。120免疫算子有两种类型：

全免疫

非特异性免疫

目标免疫

特异性免疫免疫思想的实现

免疫算子即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。121免疫操作的基本过程

首先，对待求解问题进行具体分析，从中提取出最基本的特征信息；

其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；

最后，将此方案以适当的形式转化成免疫算子

以实施具体的操作。122免疫算子

算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；

免疫算子由接种疫苗

和免疫选择

两个操作完成的。TheImmuneoperator为了防止群体的退化。为了提高个体的适应度。123设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上的基因或其分量，使所得个体以较大的概率具有更高的适应度。疫苗是从先验知识中提炼出来的，它所含的信息量及其准确性对算法性能的发挥起着重要的作用。免疫算子接种疫苗之124这一操作一般分两步完成：第一步是免疫检测

，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，则该个体将被父代中所对应的个体所取代；第二步是退火选择，即在目前的子代群体中以右边所示概率选择个体进入新的父代群体。免疫算子免疫检测之在免疫策略中，仅有免疫检测而没有退火选择。125体系结构免疫算法免疫规划免疫策略126免疫算法(1)随机产生初始父代种群A1，据先验知识抽取疫苗；(2)若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续；(3)对当前第k代种群Ak进行交叉操作，得到种群Bk；(4)对Bk进行变异操作，得到种群Ck；(5)对Ck进行接种疫苗操作，得到种群Dk；(6)对Dk作免疫选择操作,得新一代父本Ak+1,转步(2)。ImmuneAlgorithm---IA127免疫算法的收敛性状态转移过程示意图：定理：免疫算法是收敛的。定义：如果对于任意的初始分布均有则称算法收敛。128(1)初始化：首先，根据要求确定解的精度；其次，随机产生N个个体，并由此构成初始的父代种群A0；(2)根据先验知识抽取疫苗H；(3)计算当前种群Ak的个体适应度,并进行停机条件判断。若条件满足，则停机,并输出结果；否则继续；(4)对当前父代群体Ak变异操作，生成子代群体Bk；(5)对群体Bk进行接种疫苗操作，得到种群Ck；(6)对种群Ck进行免疫选择操作，得到新一代父本Ak+1，转步(3)。免疫规划ImmuneProgramming---IP129免疫规划的收敛性状态转移过程示意图：定理：免疫规划是收敛的。定义：如果对于任意的初始分布均有则称算法收敛。130免疫策略(1)根据要求确定解精度,再根据先验知识抽取疫苗H；(2)随机产生

个个体作为初始的父本群体；(3)交叉:由父代和子代构成规模为2

的中间群体；(4)变异:对每一个个体进行变异得到一个新的个体；(5)免疫:首先按照对问题的先验知识修改个体(x,)的某些分量；然后对群体中注射了疫苗的个体进行检测；(6)选择：从规模为2

的群体中按适应度的大小取出前

个个体作为新一代父本的群体；(7)停机条件检测。ImmuneStrategy---IS131免疫策略的收敛性状态转移过程示意图：定理：免疫策略是收敛的。定义：如果对于任意的初始分布均有则称算法收敛。132免疫算子的机理在免疫选择作用下，若疫苗使抗体适应度得到提高，且高于当前群体的平均适应度，则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。定理：133Begin:抽取疫苗：分析待求问题，搜集特征信息；据特征信息估计特定基因位上的模式:；k=0andj=0；while(Conditions=True)if{PV}=True,thenj=j+1；i=0；for(i≤n)接种疫苗：免疫检验：ifthenelsei=i+1；退火选择：；

k=k+1；End免疫算子的执行算法134具体分析待求问题，搜集特征信息。免疫疫苗的选取方法通用方法之一以TSP问题为例，通过具体分析可以得出相邻两两城市之间的最短路径即为求解该问题时可以利用的一种疫苗。135TSP问题的描述TSP问题是旅行商问题的简称。即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。所要研究的问题是在所有可能的路径中寻找一条路程最短的路线。该问题是一个典型的NP问题，即随着规模的增加，可行解的数目将做指数级增长。136TSP问题的分析设所有与城市Ai距离最近的城市为Aj,进行一次如虚线所示的调整后,多数情况下，l3较aj-1+aj的减少量要大于l1+l2较ai的增加量。故：137Begin:while(Conditions=True)统计父代群体，确定最佳个体： ;分解最佳个体，抽取免疫基因： ;执行遗传和免疫算子操作;end免疫疫苗的选取方法自适应方法之二138Begin:邻近城市序列初始化：Neighbor(i)=random(1,n),

i=1,…,n;最短子路径的初始化：Sub_path(i)i=1,…,n;while(Conditions=True)fori=1ton变异：Neighbor(i)=Floor(Gauss(Neighbor(i),1));选择：ifDistance(City_i,Neighbor(i))<Min_distance(i)thenSub_path(i)=Neighbor(i);Min_distance(i)=Distance(City_i,Neighbor(i));endendend免疫疫苗的选取方法进化规划方法之三139仿真实验基于IA的TSP求解之一a.免疫抗体 b.最优化路径75城市的TSP问题免疫优化仿真示意图140子代适应度值随进化过程的变化曲线a通用遗传算法计算曲线 b免疫算法计算曲线141仿真实验基于IS的TSP求解之二a.免疫疫苗示意图 b.最优路径示意图442城市的TSP问题免疫优化仿真示意图142子代适应度值随进化过程的变化曲线a(

,2

)-ES计算曲线 b(

,2

)-IS

计算曲线143仿真实验基于IE的函数优化之三问题:

在(0,1)内寻找xmax使下式成立:144接受正常免疫疫苗时的计算曲线(a)基于EP的进化过程中个体分布图;(b)基于IP的进化过程中个体分布图(c)EP和IP所求得的最佳适应度对比图(d)EP和IP所求得的平均适应度对比图145免疫疫苗为时的

计算曲线(a)基于EP的进化过程中个体分布图;(b)基于IP的进化过程中个体分布图(c)EP和IP所求得的最佳适应度对比图(d)EP和IP所求得的平均适应度对比图146免疫神经网络的研究第二部分147自然免疫网络

生物学免疫网络原型：Jerne:免疫系统是通过自我识别和相互刺激与约束而构成的一个动态平衡的网络结构。

免疫应答(免疫耐受与记忆);

Varela的免疫网络模型：系统的动力学部分；系统的元动力学部分；系统的免疫恢复机制(IRM).148免疫神经网络的生物学特征

一个完整的神经元由细胞体、树突、轴突、突触和神经末梢等几大部分构成，其中细胞体是神经元的主体。

人的脑系统大约由1011个神经元组成。这些神经元虽然在物理结构上是基本一致的，但其功能和在系统中所发挥的作用是有明显差别的。

生物免疫系统具有记忆功能以及自学习、自组织和自适应的能力。149人工免疫神经网络的研究

已有人工神经网络的特点。

利用先验知识改进人工神经网络结构的尝试：

Stork，1992年，奇偶校验问题。

Kryghyak，1993年，奇偶校验问题。

吴佑寿，1996年，奇偶校验和对称性校验的问题。150一种免疫神经网络模型151免疫神经网络中激励函数的选取方法

分析待求问题的过程，搜集特征信息，再根据先验知识找出输入变量之间的相互约束关系；

设计激励单元的基本类型。即根据上述约束关系，选取一种适当的含有待定参数的函数族；

根据第

步所提取的疫苗填充疫苗接种单元；

选取一种网络学习算法，如LMS和改进的BP算法等，利用训练样本来修正网络中的权值矩阵和阀值等相关参数。152免疫神经网络的自学习算法

将激励函数中的参数V当作网络训练的目标之一；

采用成批训练和添加动量项的方法来训练网络权值和激励函数中的参数。153免疫神经网络的设计实例154双螺旋线问题的求解设螺旋线的参数方程形式为：由此可得：155双螺旋线问题的求解设计激励单元的基本类型：156双螺旋线问题的求解解决双螺旋线的免疫神经网络的形式为：157双螺旋线问题的仿真结果带有随机干扰的两类螺旋线：158免疫进化子波网络模型159网络方程：免疫进化子波网络模型目标函数：160子波函数的参数初始化

确定一个母波函数以及对特定目标信号的伸缩、平移参数的取值范围；

利用免疫进化算法进行优化搜索；

获得一组有利于分类识别的信号子波特征。161子波网络的学习算法

初始化。将任意选取n组权值以及初始化后的子波基参数做为初始群体；

根据先验知识抽取疫苗H。根据对问题的先验知识或其应用背景方面的特征信息，来确定个体在某些基因上的取值特征或基因之间的相互制约关系，并以此做为待求问题的免疫疫苗，经编码处理后即可视为H；另一方面，若以上条件尚不具备，我们即可采用算法2来动态寻找H，并将该过程置于第4与第5步骤之间进行；162学习算法（续）

计算当前群体中所有个体的适应度，并从中确定最佳个体，然后判断停机条件是否满足；

对当前群体实施变异操作；

对当前群体实施接种疫苗操作；

对接种了疫苗的个体进行检验，并对所注射疫苗做出评价；

计算当前群体中所有个体的适应度，并以此为根据在一定的选择机制下，挑选出n个个体组成下一代进化的群体，然后转至第3步。163双螺旋线问题的仿真结果带有随机干扰的两类螺旋线：164仿真结果分析

正确识别率为95.3125%，略低于免疫神经网络的识别结果（97.81%）。

在免疫神经网络中，免疫调节的范围包括网络结构和参数两个方面；而在免疫子波神经网络中，调节范围只限于函数参数的调节上。165免疫理论的应用研究第三部分166计算机免疫系统的研究计算机网络模型示意图167

随着现代计算机网络技术和信息技术的高速发展和Internet在全球领域的推广，计算机信息系统的安全日渐突出；

从功能上分析，计算机（网络）系统一般包括信息的传输与变换两个方面。由于这两方面对信息处理的目的不同，所以它们对安全性的要求也不一样。

就传输过程而言，系统要求防止外界自然因素对信息的影 响和人为因素的监听、截获和施扰；

在对信息的转换和处理过程中，主要预防黑客的入侵和 病毒的破坏。计算机免疫系统的研究168

先天免疫性

自适应免疫性

信息发布的快速性

可测量性

安全与可靠性

用户可控性免疫系统的设计原则169信息传输免疫系统信息传输免疫系统示意图170信息传输免疫系统信息序列的基带信号：伪随机信号：调制后发送信号：171信息传输免疫系统接收段信号：经伪随机解调信号：经过解调输出的干扰信号总能量：172信息处理免疫系统计算机人工免疫系统结构示意图173终端层各单元的功能

病毒检测

指在终端机或单独的计算机上进行针对病毒代码和信息异常变化的检测，所采取的主要技术包括病毒特征码的扫描技术和系统信息跟踪技术；

获取样本病毒

在单机系统内部散布一些“诱饵”程序并监测其变化情况，将被改变程序中的相关代码与已知病毒代码进行比对处理，从中获取相应的、新的病毒样本。这一过程即为后面即将介绍的诱饵算法的基本思路；

病毒清除清除由病毒检测过程和“诱饵”算法所查获的新旧病毒，然后记录操作情况并发出警告；

信息修复根据上一级免疫系统提供的修复程序对病毒破坏的信息进行自主式修复。174局域层各单元的功能

系统监控系统随时监测本系统内信息的变化情况，遇有异常迹象则释放“诱饵”并跟踪和记录该信息的变化过程，以判断其操作的合法性。

系统报警

当判断信息的变化过程确属异常或非法时，锁定信息并向上一层或管理人员报警；另外，系统根据本层病毒特征提取的情况确定是否向下层发出新型病毒入侵的警报。

病毒特征提取

系统响应下层上报的病毒报警信息，从病毒样本中提取病毒代码。然后将其与广域层的病毒数据库进行对比，属于新代码则上传给广域层进行病毒数据库的更新。175广域层各单元的功能

系统信息发布根据局域层上报的信息异常变化警报，决定是否将其跟踪和记录变化过程的数据向下层发布；定期和不定期向下层发布新型病毒特征代码和一些修复程序。

修复程序生成根据信息遭受破坏的过程记录及其特点，人为或自动地生成相应的信息修复程序。

病毒数据库更新

根据下层上报的病毒特征代码更新当前的全局病毒数据库（添补新型病毒代码和删除一些长期不用的代码）。176病毒监测算法177异常变化监测算法178广域层各单元的功能

系统信息发布根据局域层上报的信息异常变化警报，决定是否将其跟踪和记录变化过程的数据向下层发布；定期和不定期向下层发布新型病毒特征代码和一些修复程序。