1、免疫算法流程

与遗传算法等其他智能优化算法类似，免疫算法的进化寻优过程也是通过算子来实现的。免疫算法的算子包括：亲和度评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆算子、变异算子、克隆抑制算子和种群刷新算子等。由于算法的编码方式可能为实数编码、离散编码等，不同编码方式下的算法算子也会有所不同。

目前还没有统一的免疫算法及框图，下面介绍一种含有以上免疫算子的算法流程，分为以下几个步骤：

（1）首先进行抗原识别，即理解待优化的问题，对问题进行可行性分析，提取先验知识，构造出合适的亲和度函数，并制定各种约束条件。

（2）然后产生初始抗体群，通过编码把问题的可行解表示成解空间中的抗体，在解的空间内随机产生一个初始种群。

（3）对种群中的每一个可行解进行亲和度评价。

（4）判断是否满足算法终止条件：如果满足条件则终止算法寻优过程，输出计算结果；否则继续寻优运算。

（5）计算抗体浓度和激励度。

（6）进行免疫处理，包括免疫选择、克隆、变异和克隆抑制。

免疫选择： 根据种群中抗体的亲和度和浓度计算结果选择优质抗体，使其活化；

克隆： 对活化的抗体进行克隆复制，得到若干副本；

变异： 对克隆得到的副本进行变异操作，使其发生亲和度突变；

克隆抑制： 对变异结果进行再选择，抑制亲和度低的抗体，保留亲和度高的 变异结果。

（7）种群刷新，以随机生成的新抗体替代种群中激励度较低的抗体，形成新一代抗体，转步骤（3）。

免疫算法运算流程如下图所示：

免疫算法中的进化操作是采用了基于免疫原理的进化算子实现的，如免疫选择、克隆、变异等。而且算法中增加了抗体浓度和激励度的计算，并将抗体浓度作为评价个体质量的一个标准，有利于保持个体多样性，实现全局寻优。

2、关键参数说明

下面介绍一下免疫算法的主要参数，它在程序设计与调试中起着至关重要的作用。免疫算法主要包括以下关键参数：

（1）抗体种群大小 NP
抗体种群保留了免疫细胞的多样性，从直观上看，种群越大，免疫算法的全局搜索能力越好，但是算法每代的计算量也相应增大。在大多数问题中，NP 取 10～100 较为合适，一般不超过 200。

（2）免疫选择比例
免疫选择的抗体的数量越多，将产生更多的克隆，其搜索能力越强，但是将增加每代的计算量。一般可以取抗体种群大小 NP 的 10%～50%。

（3）抗体克隆扩增的倍数
克隆的倍数决定了克隆扩增的细胞的数量，从而决定了算法的搜索能力，主要是局部搜索能力。克隆倍数数值越大，局部搜索能力越好，全局搜索能力也有一定提高，但是计算量也随之增大，一般取 5～10 倍。

（4）种群刷新比例
细胞的淘汰和更新是产生抗体多样性的重要机制，因而对免疫算法的全局搜索能力产生重要影响。每代更新的抗体一般不超过抗体种群的 50%。

（5）最大进化代数 G
最大进化代数 G 是表示免疫算法运行结束条件的一个参数，表示免疫算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般 G 取 100～500。

3、MATLAB仿真实例

3.1 免疫算法求一元函数的极值

例1 计算函数 $f(x)={\sum }_{i=1}^n{x}_i^2(-20\le x_i\le 20)$的最小值，其中个体 $x$ 的维数 为 $n=10$。这是一个简单的平方和函数，只有一个极小点 $x=(0，0，\dots ，0)$，理论最小值$f(0，0，\dots ，0)=0$。

解： 仿真过程如下：
（1）初始化免疫个体维数为 $D=10$，免疫种群个体数为 $NP=100$，最大免疫代数为 $G=500$，变异概率为 $P_m=0.7$，激励度系数为 $\alpha =1，\beta =1$，相似度阈值为 $\delta =0.2$，克隆个数为 $N_{cl}=10$。
（2）随机产生初始种群，计算个体亲和度、抗体浓度和激励度，并按激励度排序。
（3）取激励度前 $NP/2$ 个个体进行克隆、变异、克隆抑制的免疫操作，免疫后的种群进行激励度计算。
（4）随机生成 $NP/2$ 个个体的新种群，并计算个体亲和度、抗体浓度和激励度；免疫种群和随机种群合并，按激励度排序，进行免疫迭代。
（5）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

优化结束后，亲和度进化曲线如图所示，优化后的结果为： $\left[\begin{array}{cccccccccc}0.0002& -0.0035& -0.0036& 0.0007& 0.0000& -0.0009& -0.0004& -0.0005& -0.0010& 0.0070\end{array}\right]$，函数 $f(x)$ 的最小值为 $8.745\times 10^{-5}$。

MATLAB 源程序如下：

%%%%%%%%%%%%%%免疫算法求函数最值%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%
clear all; %清除所有变量
close all; %清图
clc; %清屏
D = 10; %免疫个体维数
NP = 100; %免疫个体数目
Xs = 20; %取值上限
Xx = -20; %取值下限
G = 500; %最大免疫代数
pm = 0.7; %变异概率
alfa = 1; %激励度系数
belta = 1; %激励度系数
detas = 0.2; %相似度阈值
gen = 0; %免疫代数
Ncl = 10; %克隆个数
deta0 = 1*Xs; %邻域范围初值
%%%%%%%%%%%%%%%%初始种群%%%%%%%%%%%%%%%%%%
f = rand(D,NP)*(Xs-Xx)+Xx;
for np = 1:NPMSLL(np) = func1(f(:,np));
end
%%%%%%%%%%%%%%计算个体浓度和激励度%%%%%%%%%%%%%%
for np = 1:NPfor j = 1:NPnd(j) = sum(sqrt((f(:,np)-f(:,j)).^2));if nd(j) < detasnd(j) = 1;elsend(j) = 0;endendND(np) = sum(nd)/NP;
end
MSLL = alfa*MSLL - belta*ND;
%%%%%%%%%%%%%%%激励度按升序排列%%%%%%%%%%%%%%%%
[SortMSLL,Index] = sort(MSLL);
Sortf = f(:,Index);
%%%%%%%%%%%%%%%%%免疫循环%%%%%%%%%%%%%%%%%%%
while gen < Gfor i = 1:NP/2%%%%%%%%选激励度前 NP/2 个个体进行免疫操作%%%%%%%%%a = Sortf(:,i);Na = repmat(a,1,Ncl);deta = deta0/gen;for j = 1:Nclfor ii = 1:D%%%%%%%%%%%%%%变异%%%%%%%%%%%%%%if rand < pmNa(ii,j) = Na(ii,j)+(rand-0.5)*deta;end%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%if (Na(ii,j) > Xs) | (Na(ii,j) < Xx)Na(ii,j) = rand * (Xs-Xx)+Xx;endendendNa(:,1) = Sortf(:,i); %保留克隆源个体%%%%%%%%%克隆抑制，保留亲和度最高的个体%%%%%%%%%for j = 1:NclNaMSLL(j) = func1(Na(:,j));end[NaSortMSLL,Index] = sort(NaMSLL);aMSLL(i) = NaSortMSLL(1);NaSortf = Na(:,Index);af(:,i) = NaSortf(:,1);end%%%%%%%%%%%%%%%免疫种群激励度%%%%%%%%%%%%%%%for np = 1:NP/2for j = 1:NP/2nda(j) = sum(sqrt((af(:,np)-af(:,j)).^2));if nda(j) < detasnda(j) = 1;elsenda(j) = 0;endendaND(np) = sum(nda)/NP/2;endaMSLL = alfa*aMSLL - belta*aND;%%%%%%%%%%%%%%%种群刷新%%%%%%%%%%%%%%%%%bf = rand(D,NP/2)*(Xs-Xx)+Xx;for np = 1:NP/2bMSLL(np) = func1(bf(:,np));end%%%%%%%%%%%%%新生成种群激励度%%%%%%%%%%%%%%for np = 1:NP/2for j = 1:NP/2ndc(j) = sum(sqrt((bf(:,np)-bf(:,j)).^2));if ndc(j) < detasndc(j) = 1;elsendc(j) = 0;endendbND(np) = sum(ndc)/NP/2;endbMSLL = alfa*bMSLL - belta*bND;%%%%%%%%%%免疫种群与新生种群合并%%%%%%%%%%%%%f1 = [af,bf];MSLL1 = [aMSLL,bMSLL];[SortMSLL,Index] = sort(MSLL1);Sortf = f1(:,Index);gen = gen+1;trace(gen) = func1(Sortf(:,1));
end
%%%%%%%%%%%%%%%输出优化结果%%%%%%%%%%%%%%%%%%
Bestf = Sortf(:,1); %最优变量
trace(end); %最优值
figure,plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('亲和度进化曲线')
%%%%%%%%%%%%%%%%亲和度函数%%%%%%%%%%%%%%%%%
function result = func1(x)
summ = sum(x.^2);
result = summ;
end

3.2 免疫算法求二元函数的极值

例2 求函数$f(x,y)=5\sin (xy)+x^2+y^2$最小值，其中 $x$ 的取值范围为$[-4，4]$，$y$的取值范围为$[-4，4]$。这是一个有多个局部极值的函数，其函数值图形如下图所示。

解： 仿真过程如下：
（1）初始化免疫个体维数为$D=2$，免疫种群个体数为 $NP=50$，最大免疫代数为 $G=200$，变异概率为 $P_m=0.7$，激励度系数为 $\alpha =2，\beta =1$，相似度阈值为 $\delta =0.2$，克隆个数为 $N_{cl}=5$；
（2）随机产生初始种群，计算个体亲和度、抗体浓度和激励度，并按激励度
排序。
（3）取激励度前 $NP/2$ 个个体进行克隆、变异、克隆抑制的免疫操作；免疫
后的种群进行激励度计算。
（4）随机生成 $NP/2$ 个个体的新种群，并计算个体亲和度、抗体浓度和激励
度；免疫种群和随机种群合并，按激励度排序，进行免疫迭代。
（5）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不
满足，则继续进行迭代优化。
优化结束后，其亲和度进化曲线如下图所示，优化后的结果为：$x=1.0767，y=-1.0767$，函数 $f(x，y)$的最小值为$-2.264$。

MATLAB 源程序如下：

%%%%%%%%%%%%%免疫算法求函数最值%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%
clear all; %清除所有变量
close all; %清图
clc; %清屏
D = 2; %免疫个体维数
NP = 50; %免疫个体数目
Xs = 4; %取值上限
Xx = -4; %取值下限
G = 200; %最大免疫代数
pm = 0.7; %变异概率
alfa = 2; %激励度系数
belta = 1; %激励度系数
detas = 0.2; %相似度阈值
gen = 0; %免疫代数
Ncl = 5; %克隆个数
deta0 = 0.5*Xs; %邻域范围初值
%%%%%%%%%%%%%%%初始种群%%%%%%%%%%%%%%%%%%
f = rand(D,NP)*(Xs-Xx)+Xx;
for np = 1:NPMSLL(np) = func2(f(:,np));
end
%%%%%%%%%%%计算个体浓度和激励度%%%%%%%%%%%%%%%
for np = 1:NPfor j = 1:NPnd(j) = sum(sqrt((f(:,np)-f(:,j)).^2));if nd(j) < detasnd(j) = 1;elsend(j) = 0;endendND(np) = sum(nd)/NP;
end
MSLL = alfa*MSLL - belta*ND;
%%%%%%%%%%%%%激励度按升序排列%%%%%%%%%%%%%%%%
[SortMSLL,Index] = sort(MSLL);
Sortf = f(:,Index);
%%%%%%%%%%%%%%%免疫循环%%%%%%%%%%%%%%%%%%
while gen < Gfor i = 1:NP/2%%%%%%%选激励度前 NP/2 个个体进行免疫操作%%%%%%%%a = Sortf(:,i);Na = repmat(a,1,Ncl);deta = deta0/gen;for j = 1:Nclfor ii = 1:D%%%%%%%%%%%%变异%%%%%%%%%%%%%%if rand < pmNa(ii,j) = Na(ii,j)+(rand-0.5)*deta;end%%%%%%%%%%%边界条件处理%%%%%%%%%%%if (Na(ii,j) > Xs) | (Na(ii,j) < Xx)Na(ii,j) = rand * (Xs-Xx)+Xx;endendendNa(:,1) = Sortf(:,i); %保留克隆源个体%%%%%%%%克隆抑制，保留亲和度最高的个体%%%%%%%%for j = 1:NclNaMSLL(j) = func2(Na(:,j));end[NaSortMSLL,Index] = sort(NaMSLL);aMSLL(i) = NaSortMSLL(1);NaSortf = Na(:,Index);af(:,i) = NaSortf(:,1);end%%%%%%%%%%%%%%%免疫种群激励度%%%%%%%%%%%%%%for np = 1:NP/2for j = 1:NP/2nda(j) = sum(sqrt((af(:,np)-af(:,j)).^2));if nda(j) < detasnda(j) = 1;elsenda(j) = 0;endendaND(np) = sum(nda)/NP/2;endaMSLL = alfa*aMSLL - belta*aND;%%%%%%%%%%%%%%%%%种群刷新%%%%%%%%%%%%%%%bf = rand(D,NP/2)*(Xs-Xx)+Xx;for np = 1:NP/2bMSLL(np) = func2(bf(:,np));end%%%%%%%%%%%%%%新生成种群激励度%%%%%%%%%%%%%%for np = 1:NP/2for j = 1:NP/2ndc(j) = sum(sqrt((bf(:,np)-bf(:,j)).^2));if ndc(j) < detasndc(j) = 1;elsendc(j) = 0;endendbND(np) = sum(ndc)/NP/2;endbMSLL = alfa*bMSLL - belta*bND;%%%%%%%%%%%免疫种群与新生种群合并%%%%%%%%%%%%%f1 = [af,bf];MSLL1 = [aMSLL,bMSLL];[SortMSLL,Index] = sort(MSLL1);Sortf = f1(:,Index);gen = gen+1;trace(gen) = func2(Sortf(:,1));
end
%%%%%%%%%%%%%%%%输出优化结果%%%%%%%%%%%%%%%%%
Bestf = Sortf(:,1); %最优变量
trace(end); %最优值
figure,plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('亲和度进化曲线')
%%%%%%%%%%%%%%%%亲和度函数%%%%%%%%%%%%%%%%%%
function value = func2(x)
value = 5*sin(x(1)*x(2))+x(1)*x(1)+x(2)*x(2);
end

3.3 免疫算法求解旅行商问题

例3 旅行商问题（TSP 问题）。假设有一个旅行商人要拜访全国 31个省会城市，他需要选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择要求是：所选路径的路程为所有路径之中的最小值。全国 31 个省会城市的坐标为 [1304 2312; 3639 1315; 4177 2244; 3712 1399; 3488 1535; 3326 1556; 3238 1229; 4196 1004; 4312 790; 4386 570; 3007 1970; 2562 1756; 2788 1491; 2381 1676; 1332 695; 3715 1678; 3918 2179; 4061 2370; 3780 2212; 3676 2578; 4029 2838; 4263 2931; 3429 1908; 3507 2367; 3394 2643; 3439 3201; 2935 3240; 3140 3550; 2545 2357; 2778 2826; 2370 2975]。

解： 仿真过程如下：
（1）初始化免疫个体维数为城市个数 $N=31$，免疫种群个体数为 $NP=200$，最大免疫代数为 $G=1000$，克隆个数为 $N_{cl}=10$；计算任意两个城市间的距离矩阵 D。
（2）随机产生初始种群，计算个体亲和度，并按亲和度排序。
（3）在取亲和度前对 $NP/2$ 个个体进行克隆操作，并对每个源个体产生的克
隆个体进行任意交换两个城市坐标的变异操作；然后计算其亲和度，进行克隆抑制操作，只保留亲和度最高的个体，从而产生新的免疫种群。
（4）随机生成 $NP/2$ 个个体的新种群，并计算个体亲和度；免疫种群和随机
种群合并，按亲和度排序，进行免疫迭代。
（5）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不
满足，则继续进行迭代优化。

优化后的路径以及亲和度进化曲线如下图所示：


MATLAB 源程序如下：

%%%%%%%%%%%%%免疫算法求解 TSP 问题%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%
clear all; %清除所有变量
close all; %清图
clc; %清屏
C = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...2370 2975]; %31 个省会城市坐标
N = size(C,1); %TSP 问题的规模,即城市数目
D = zeros(N); %任意两个城市距离间隔矩阵
%%%%%%%%%%%%求任意两个城市距离间隔矩阵%%%%%%%%%%%%%
for i = 1:Nfor j = 1:ND(i,j) = ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;end
end
NP = 200; %免疫个体数目
G = 1000; %最大免疫代数
f = zeros(N,NP); %用于存储种群
for i = 1:NPf(:,i) = randperm(N); %随机生成初始种群
end
len = zeros(NP,1); %存储路径长度
for i = 1:NPlen(i) = func3(D,f(:,i),N); %计算路径长度
end
[Sortlen,Index] = sort(len);
Sortf = f(:,Index); %种群个体排序
gen = 0; %免疫代数
Ncl = 10; %克隆个数
%%%%%%%%%%%%%%%%免疫循环%%%%%%%%%%%%%%%%%%
while gen < Gfor i = 1:NP/2%%%%%%%选激励度前 NP/2 个个体进行免疫操作%%%%%%%%%a = Sortf(:,i);Ca = repmat(a,1,Ncl);for j = 1:Nclp1 = floor(1+N*rand());p2 = floor(1+N*rand());while p1==p2p1 = floor(1+N*rand());p2 = floor(1+N*rand());endtmp = Ca(p1,j);Ca(p1,j) = Ca(p2,j);Ca(p2,j) = tmp;endCa(:,1) = Sortf(:,i); %保留克隆源个体%%%%%%%%%克隆抑制，保留亲和度最高的个体%%%%%%%%for j = 1:NclCalen(j) = func3(D,Ca(:,j),N);end[SortCalen,Index] = sort(Calen);SortCa = Ca(:,Index);af(:,i) = SortCa(:,1);alen(i) = SortCalen(1);end%%%%%%%%%%%%%%%%%种群刷新%%%%%%%%%%%%%%%for i = 1:NP/2bf(:,i) = randperm(N); %随机生成初始种群blen(i) = func3(D,bf(:,i),N); %计算路径长度end%%%%%%%%%%%%%免疫种群与新种群合并%%%%%%%%%%%%f = [af,bf];len = [alen,blen];[Sortlen,Index] = sort(len);Sortf = f(:,Index);gen = gen+1;trace(gen) = Sortlen(1);
end
%%%%%%%%%%%%%%%输出优化结果%%%%%%%%%%%%%%%%%%
Bestf = Sortf(:,1); %最优变量
Bestlen = trace(end); %最优值
figure
for i = 1:N-1plot([C(Bestf(i),1),C(Bestf(i+1),1)],...[C(Bestf(i),2),C(Bestf(i+1),2)],'bo-');hold on;
end
plot([C(Bestf(N),1),C(Bestf(1),1)],...[C(Bestf(N),2),C(Bestf(1),2)],'ro-');
title(['优化最短距离:',num2str(trace(end))]);
figure,plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('亲和度进化曲线')
%%%%%%%%%%%%%%%%计算路线总长度%%%%%%%%%%%%%%%%
function len = func3(D,f,N)
len = D(f(N),f(1));
for i = 1:(N-1)len = len+D(f(i),f(i+1));
end
end

4、免疫算法的特点

免疫算法是受免疫学启发，模拟生物免疫系统功能和原理来解决复杂问题的自适应智能系统，它保留了生物免疫系统所具有的若干特点，包括：

（1）全局搜索能力。 模仿免疫应答过程提出的免疫算法是一种具有全局搜索能力的优化算法，免疫算法在对优质抗体邻域进行局部搜索的同时利用变异算子和种群刷新算子不断产生新个体，探索可行解区间的新区域，保证算法在完整的可行解区间进行搜索，具有全局收敛性能。
（2）多样性保持机制。 免疫算法借鉴了生物免疫系统的多样性保持机制，对抗体进行浓度计算，并将浓度计算的结果作为评价抗体个体优劣的一个重要标准；它使浓度高的抗体被抑制，保证抗体种群具有很好的多样性，这也是保证算法全局收敛性能的一个重要方面。
（3）鲁棒性强。 基于生物免疫机理的免疫算法不针对特定问题，而且不强调算法参数设置和初始解的质量，利用其启发式的智能搜索机制，即使起步于劣质解种群，最终也可以搜索到问题的全局最优解，对问题和初始解的依赖性不强，具有很强的适应性和鲁棒性。
（4）并行分布式搜索机制。 免疫算法不需要集中控制，可以实现并行处理。而且，免疫算法的优化进程是一种多进程的并行优化，在探求问题最优解的同时可以得到问题的多个次优解，即除找到问题的最佳