人工免疫算法

人工免疫算法1.基本介绍生物免疫系统的免疫功能是通过抗体消灭人侵的病原体(抗原)而实现的。模拟生物免疫系统的功能可以构造人工免疫系统，基于人工免疫系统又可以设计人工免疫算法(AIA)。人工免疫算法和遗传算法(GA)、蚁群算法等都属于模拟自然界生物行为的仿生算法。近来，有学者发现将生物免疫系统的一些行为引人到传统的仿生算法中，构造免疫算法，可以提高算法的计算效率。在遗传算法中引人了生物免疫系统的抗体记忆机制,即算法在完成一个问题的求解以后,保留一定数量的较优解，在算法接受同类通体的求解时，可以将保留的较优解作为初始解，从而提高算法的计算效率。2.人工免疫算法在用人工免疫算法求解优化问题时，满足约束条件的最优解即是抗原；候选解即是抗体。一个抗体可以用一个字符表示。用亲和力来描述抗体和抗原之间的匹配程度，用排斥力来描述两个抗体之间的相似程度。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）字符换位算子，可分为单对字符换位算子和多对字符换位算子。定义1单对字符换位操作是对抗体123A=l（c，c，c，…，c），随机取两个正整数i，j（1,ijl，ij），以一定的概率cp（01cp）交换抗体A中的一对字符,ijcc的位置；多对字符换位操作是预先确定一个正整数eu，随机去一个正整数r（1eru），在抗体A中随机取r对字符作字符换位操作。（2）字符串移位算子，可分为单个字符串移位算子和多个字符串移位算子。定义2单个字符串移位操作是对抗体123A=l（c，c，c，…，c），随机取两个正整数i，j（1,ijl，ij），从A中取出一个字符子串lA，11()liijjAcccc，，…，，，以一定的概率(01)sspp依次往左（或往右）移动字符串lA中的各个字符，最左（或最右）边的一个字符则移动到最右（或最左）边的位置；多个字符串换位操作是预先确定一个正整数su，随机取一个正整数(1)srru，再在抗体A中随机取r个字符串位移操作。（3）字符串逆转算子，可分为单个字符串逆转算子和多个字符串逆转算子。定义3单个字符串逆转操作是对抗体123A=l（c，c，c，…，c），随机取两个正整数i，j（1,ijl，ij），从A中取出一个字符子串lA，11()liijjAcccc，，…，，，以一定的概率(01)iipp使字符串lA中的各个字符首尾倒置；多个字符串逆转操作是预先确定一个正整数iu，随机取一个正整数(1)irru，再在抗体A中随机取r个字符串作字符串逆转操作。（4）字符串重组算子。定义4字符重组操作是在抗体123A=l（c，c，c，…，c）中，随机取一个字符子串lA，11()liijjAcccc，，…，，，以一定的概率(01)rrpp使字符串lA中字符重新排列。重新排列的目的是提高抗体的亲和力，具体方法与所求解的问题有关。（5）优质串保留算子。定义5如果若干个抗体与抗原之间的亲和力都很大，且这些抗体包含了一个相同的字符子串，则称这个字符子串为优质字符串，简称优质串。定义6如果抗体中存在优质串，则在抗体产生过程中以概率(01)oopp使该优质串不受破坏，即把该优质串当成一个字符看待，称为优质串保留。（6）新抗体引入算子。若抗体群中的抗体失去了多样性，则可以产生新的抗体替换掉其中的一部分，以保持抗体群中抗体的多样性。定义7新抗体引入操作是当抗体群中有(1)kk个抗体相同时，对其中的(1)k个抗体以概率(01)nnpp用新产生的抗体替换。3.人工免疫算法的收敛性分析人工免疫算法生成的各代抗体群构成有限状态齐次马尔可夫（Markov）链。注：（1）马尔可夫链，因安德烈·马尔可夫(A.A.Markov,1856－1922)得名，是数学中具有马尔可夫性质的离散时间随机过程。马尔可夫链是满足下面两个假设的一种随机过程：a、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；b、从t时刻到t+l时刻的状态转移与t的值无关。一个马尔可夫链模型可表示为=(S,P,Q)，S系统的状态空间，P状态转移概率矩阵，Q初始概率分布。（2）许多数学研究者索性就以测度不可分性来定义遍历变换。数学的研究指出，一个能保证遍历性（即测度不可分性）的更强的条件是混合性。令为长度为l的有序符号串（抗体）iS的集合，则串空间包含||!l（1）个点。令为包含n个抗体的抗体群i的集合，则抗体群空间包含||(!)nl（2）个点。定义8若nnAR，并且对任何正整数i，j（,[1,]ijn），有1）0ija，则称A为正矩阵，记为0A；2）0ija，则称A为非负矩阵，记为0A。定理1由初始抗体群0经字符换位算子生成的各代抗体群构成的Markov链是遍历的。证字符换位操作的概率转移矩阵0eP，故定理成立。定理2由初始抗体群0经字符串移位算子生成的各代抗体群构成的Markov链是遍历的。证字符串移位操作的概率转移矩阵0sP，故定理成立。定理3由初始抗体群0经字符串逆转算子生成的各代抗体群构成的Markov链是遍历的。证字符串逆转操作的概率转移矩阵0iP，故定理成立。定理4当字符串重组算子的作用概率1rp时，字符串重组算子不会破坏字符换位算子、字符串移位算子、字符串逆转算子的遍历性。证字符串重组算子不破坏抗体的概率10rpp，故定理成立。定理5当优质串保留算子的作用概率01p时，优质串保留算子不会破坏字符换位算子、字符串移位算子、字符串逆转算子的遍历性。证优质串保留算子不破坏抗体的概率010pp，故定理成立。定理6当新抗体引入算子的作用概率1np时，新抗体引入算子不会破坏字符换位算子、字符串移位算子、字符串逆转算子的遍历性。证新抗体引入算子不破坏抗体的概率10npp，故定理成立。定理7人工免疫算法生成的各代抗体群所构成的Markov链是遍历的。证由定理1~6的证明可知，人工免疫算法的概率矩阵0P。定理7说明人工免疫算法能够搜索到问题的最优解，但这并不意味着人工免疫算法是全局收敛的。定理8如果在进行抗体选择时能确保当时的最优抗体可以进入下一代抗体群，则人工免疫算法是全局收敛的；否则人工免疫算法不是全局收敛。旅行商问题（TSP）是一个典型的组合优化问题。4.1抗体编码方式4.人工免疫算法在旅行商问题中的应用对于有个城市的旅行商问题，可以对这l个城市编号，其号码分别为1，2，3，……，l，并且把商人所在城市即出发城市编为第1号，其他城市可随意编号。4.2初始抗体的产生与预处理随机产生N个抗体作为初始抗体，构成初始抗体群。为了提高算法的搜索效率，本文提出的旅行商问题人工免疫算法先对每一个初始抗体进行预处理，然后才开始算法的迭代计算。初始抗体预处理的基本思想是考虑到旅行商问题的任何一条路径都是闭合路径，从任一城市出发，要到达的下一个城市选择为未到过的城市中距该城市最近的一个。经过预处理的初始抗体经人工免疫算子的作用能产生更好的新抗体的概率较大，算法搜索率较高。命题初始抗体的预处理不影响人工免疫算法的全局收敛性。4.3亲和力和排斥力的计算对于TSP问题，可定义抗体B与抗原G之间的亲和力为()MBappBTT(9)其中MT问为较大的正数，并要求MT大于任意抗体对应的旅行线的长度；BT为抗体B对应的旅行线路线的长度。可定义抗体1B与抗体2B之间的排斥力为1212(,)||BBrepBBTT(10)其中1BT，2BT分别为抗体1B与抗体2B对应的旅行路线的长度。4.4仿真实验对于一个100个城市的旅行商问题，人工免疫算法取抗体规模80N，人工免疫算子的作用概率分别为0.2ep，0.3sp，0.4ip，0.5rp，0.5op，0.5np，1/4[]esiuuul。[*]表示取整运算，每次抗体选择时保留与抗原匹配得最好的抗体，重复进行20次计算，每次计算随机产生不同的初始抗体，并对初始抗体进行预处理，迭代10000次，计算结果如表1所示。表1中也给出了同一问题用遗传算法的计算结果。从表1可以看出，本文提出的旅行商问题的人工免疫算法具有较好的全局搜索能力。基于人工免疫克隆选择算法的调度优化MATLAB源码%%输入参数列表%M------------人工免疫优化算法迭代次数%N------------抗体群的规模%Ns-----------免疫选择算子中选中的抗体个数%Ncm----------克隆变异算子中产生的新抗体的个数%Nr-----------抑制操作中保留下来的抗体个数%Pd-----------变异程度控制参数，取值0～1，越大变异越厉害%alpha--------亲和度加权系数，用于激励度的计算%beta---------浓度加权系数，用于激励度的计算%K------------调度分组的个数%Cx-----------节点的横坐标，1×n的向量%Cy-----------节点的纵坐标，1×n的向量%r------------节点的感知半径，1×n的向量%Sx-----------质点的横坐标，1×m的向量%Sy-----------质点的纵坐标，1×m的向量%%输出参数列表%BestX--------最优调度方案%BestY--------最优调度对应的平均覆盖率%AllABfarm----历史上所有抗体群的集合，M×1的细胞结构%LC1----------最优抗体亲和度的收敛曲线，M×1%LC2----------抗体群平均亲和度的收敛曲线，M×1%%-----------------------初始化----------------------------------n=length(Cx);LC1=zeros(M,1);LC2=zeros(M,1);AllABfarm=cell(M,1);%控制参数初始化mm=1;%迭代计数器%调用子函数，抗体群初始化ABfarm=AntiBodyInitial(N,n,K);%%-----------------------迭代过程---------------------------------whilemm=M%设置停止条件%调用子函数，计算抗体群亲和度aff=Affinity(ABfarm,K,Cx,Cy,r,Sx,Sy);%记录收敛曲线maxaff=max(aff);meanaff=mean(aff);LC1(mm)=maxaff;LC2(mm)=meanaff;pos=find(aff==maxaff);BestPos=pos(1);BestX=ABfarm(BestPos,:);BestY=maxaff;AllABfarm{mm}=ABfarm;%调用子函数，计算抗体浓度den=Density(ABfarm);%调用子函数，计算抗体激励度sim=SumUp(aff,den,alpha,beta