免疫(Immunity Algorithm,IA)优化算法在物流配送中心选址中的应用

算法小狂人

2025-09-21

在物流系统的运作中,配送中心的任务就是根据各个用户的需求及时、准确和经济地配送商品货物。配送中心是连接供应商与客户的中间桥梁,其选址方式往往决定着物流的配送距离和配送模式,进而影响着物流系统的运作效率。另外,物流中心的位置一旦被确定,其位置难以再改变。因此,研究物流配送中心的选址具有重要的理论意义和现实应用意义。一般说来,物流中心选址模型是非凸和非光滑的带有复杂约束的非线性规划模型,属NP-hard问题。

NO.1|IA基本思想

群智能算法小狂人

免疫算法(Immune Algorithm，IA)是一种受生物免疫系统启发而提出的智能搜索算法，它模仿生物免疫系统中的抗原识别、抗体产生、免疫记忆等过程来解决优化问题。免疫算法的核心思想是利用生物免疫系统的高度专业化和自适应特性来指导算法的搜索过程，以达到全局优化的目的。

1、免疫算法的关键特点

(1)产生多样抗体的能力。通过细胞的分裂和分化作用，免疫系统可产生大量的抗体来抵御各种抗原。

(2)自我调节机构。免疫系统具有维持免疫平衡的机制，通过对抗体的抑制和促进作用，能自我调节产生适当数量的必要抗体。

(3)免疫记忆功能。产生抗体的部分细胞会作为记忆细胞被保存下来，对于今后侵人的同类抗原，相应的记忆细胞会迅速激发而产生大量的抗体。

免疫算法(immune algorithm)正是受生物免疫系统启发，在免疫学理论基础上发展起来的一种新兴的智能计算方法。它利用免疫系统的多样性产生和维持机制采保持群体的多样性，克服了一般寻优过程尤其是多峰函数寻优过程中难处理的“早熟”问题，最终求得全局最优解。与其他智能算法相比，免疫算法的研究起步较晚，其发展历史只有短短二十几年。Farmen 等于 1986 年率先基于免疫网络学说构造了免疫系统的动态模型，并探讨了免疫系统与其他人工智能方法的联系 ,从而开创了免疫系统的研究。

免疫算法和遗传算法都是采用群体搜索策略，并且强调群体中个体间的信息交换，因此有许多相似之处，比如两者具有大致相同的算法结构，都要经过“初始种群产生——评价标准计算——种群间个体信息交换——新种群产生”这一循环过程，最终以较大的概率获得问题的最优解。另外，两者本质上具有并行性，具有与其他智能计算方法结合的固有优势等。

NO.2|物流中心选址模型构建

群智能算法小狂人

在物流配送中心选址模型中做如下假设:

(1)配送中心的规模容量总可以满足需求点需求,并由其配送辐射范围内的需求量确定;

(2)一个需求点仅由一个配送中心供应;

(3)不考虑工厂到配送中心的运输费用。

基于以上假设,建立如下模型。该模型是一个选址/分配模型,在满足距离上限的情况下需要从n个需求点中找出配送中心并向各需求点配送物品。目标函数是各配送中心到需求点的需求量和距离值的乘积之和最小。

目标函数(要最小化的函数)： $\min F = \sum_{i \in N} \sum_{j \in M_i} \omega_i d_{ij} Z_{ij}$

约束条件： $\begin{gathered} \sum_{j \in M_i} Z_{ij} = 1, \quad i \in N (1)\\ Z_{ij} \leqslant h_j, \quad i \in N, \quad j \in M_i(2) \\\sum_{j \in M_i} h_j = p(3) \\Z_{ij}, h_j \in \{0,1\}, \quad i \in N, \quad j \in M_i (4)\\ d_{ij} \leqslant s(5) \end{gathered}$

其中, $N=\langle1,2,\cdots,n\rangle$ 是所有需求点的序号集合;Mi为到需求点i的距离小于s 的备选配送中心集合, $i\in N,M_i\subseteq N;\omega_i$ 表示需求点的需求量； $d_{ij}表示$ 从需求点i到离它最近s为新建配送中心离由它服务的需求点的距离上限。式(2)保证每个需求点只能由一个配送中心服务；式(3)确保需求点的需求量只能被设为配送中心的点供应，即没有配送中心的地点不会有客户；式(4)规定了被选为配送中心的数量为p;式(5)表示变量 $Z_{ij}、h_j$ 是 0-1 变量；式(6)保证了需求点在配送中心可配送到的范围内。

NO.3|算法实现

群智能算法小狂人

1. 初始抗体群的产生

如果记忆库非空，则初始抗体群从记忆库中选择生成。否则，在可行解空间随机产生衣抗体群。此处采用简单编码方式。每个选址方案可形成一个长度为p的抗体(p表示配送心数量),每个抗体代表被选为配送中心的需求点的序列。例如，考虑包含 31 个需求点的题。1,2,...,31 代表需求点的序号。从中选出 6 个作为配送中心。抗体[2 7 15 21 29 11]代表一个可行解，它表示 2,7,15,21,29,11 被选为配送中心。这种编码方式能够满足约束条件式(4)和式(5)。

2.解的多样性评价

(1)抗体与抗原间亲和力

抗体与抗原之间的亲和力用于表示抗体对抗原的识别程度，此处针对上述配送中心选址模型设计亲和力函数 $为A_\mathrm{v}$ $A_{\mathrm{v}}=\frac{1}{F_{\mathrm{v}}}=\frac{1}{\sum_{i\in N}\sum_{j\in M_{i}}\omega_{i}d_{ij}Z_{ij}-C\sum_{i\in N}\min\left\{\left(\sum_{j\in M_{i}}Z_{ij}\right)-1,0\right\}}$ 其中， $F_\mathrm{v}为$ 目标函数；分母中第二项表示对违反距离约束的解给予惩罚，C 取一个比较大的正数。

(2)抗体与抗体间亲和力

抗体与抗体之间的亲和力反映了抗体之间的相似程度。此处借鉴由 Forrest 等提出的R位连续方法计算抗体与抗体间的亲和力。R位连续方法实际是一种部分匹配规则。该方法的关键是确定一个R 值，代表亲和度判定的阈值。两种个体编码有超过R位或者连续R位的编码相同，则表示这两种抗体近似“相同”,否则表示两种个体不同。此处抗原的编码方法，各位之间不需考虑排序，可参考变形的R位连续方法计算抗体间亲和度，即 $S_{\mathrm{v},\mathrm{s}}=\frac{k_{\mathrm{v},\mathrm{s}}}L$

其中， $k_\mathrm{v.s}为$ 抗体 v与抗体 s 中相同的位数；L为抗体的长度。例如，两个抗体为[2 7 15 21 5 11]、[15 8 14 26 5 2],经比较，有 3 个值是相同的，此时可计算出它们的亲和度 $S_\mathrm{v,s}=0.5$ 。

(3)抗体浓度

抗体的浓度 $为C_\mathrm{v}$ 即群体中相似抗体所占的比例，即 $C_\mathrm{v}=\frac{1}{N}\sum_{j\in N}S_\mathrm{v,s}$

其中,N为抗体总数; $S_\mathrm{v.s}=\begin{cases}1,S_{\mathrm{v.s}}>T\\0,\text{其他}\end{cases}$ ;T为预先设定的一个阈值。

(4)期望繁殖概率

在群体中，每个个体的期望繁殖概率由抗体与抗原间亲和力$A_\mathrm{v}$和抗体浓度 $C_\mathrm{v}两$ 部分共同决定，即 $P=\alpha\:\frac{A_\mathrm{v}}{\sum A_\mathrm{v}}+(1-\alpha)\:\frac{C_\mathrm{v}}{\sum C_\mathrm{v}}$ 其中，α 为常数。由上式可见，个体适应度越高，则期望繁殖概率越大；个体浓度越大，则期望繁殖概率越小。这样既鼓励了适应度高的个体，同时抑制了浓度高的个体，从而确保了个体多样性。

免疫算法在抑制高浓度个体时，与抗原亲和度最高的个体也可能因其浓度高而受到抑制，从而导致已求得的最优解丢失，因此采取精英保留策略，在每次更新记忆库时，先将与抗原亲和度最高的若干个个体存人记忆库，再按照期望繁殖概率将剩余群体中优秀个体存人记忆库。

3.免疫操作

(1)选择:按照轮盘赌选择机制进行选择操作,个体被选择的概率即为计算出的期望繁殖概率。

(2)交叉:本文采用单点交叉法进行交叉操作。

(3)变异:采用常用的变异方法,即随机选择变异位进行变异，

NO.4|MATLAB实现

群智能算法小狂人

(1)抗体初始化

function pop = popinit(n,length)%种群初始化函数(记忆库库为空，全部随机产生)% n       input    种群数量% length  input    抗体长度% pop     output   初始种群for i=1:n    flag=0;    while flag==0        [a,b]=sort(rand(1,31));            pop(i,:)=b(1:length);        flag=test(pop(i,:));    endend

(2)适应度函数

function fit=fitness(individual)%计算个体适应度值%individual    input      个体%fit           output     适应度值%城市坐标city_coordinate=[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];%货物量carge=[20,90,90,60,70,70,40,90,90,70,60,40,40,40,20,80,90,70,100,50,50,50,80,70,80,40,40,60,70,50,30];%找出最近配送点for i=1:31    distance(i,:)=dist(city_coordinate(i,:),city_coordinate(individual,:)');end
[a,b]=min(distance');%计算费用for i=1:31      expense(i)=carge(i)*a(i);end
%距离大于3000取一个惩罚值fit=sum(expense) + 4.0e+4*length(find(a>3000));end

(3)浓度计算

function concentration = concentration(i,M,individuals)% 计算个体浓度值% i              input      第i个抗体% M              input      种群规模% individuals    input     个体% concentration  output     浓度值
concentration=0;for j=1:M    xsd=similar(individuals.chrom(i,:),individuals.chrom(j,:));  % 第i个体与种群个体间的相似度    % 相似度大于阀值    if xsd>0.7        concentration=concentration+1;    endend
concentration=concentration/M;end

(4)主函数代码

%% 免疫优化算法在物流配送中心选址中的应用%% 清空环境clcclear
%% 算法基本参数           sizepop=50;           % 种群规模overbest=10;          % 记忆库容量MAXGEN=100;            % 迭代次数pcross=0.5;           % 交叉概率pmutation=0.4;        % 变异概率ps=0.95;              % 多样性评价参数length=6;             % 配送中心数M=sizepop+overbest;
%% step1 识别抗原,将种群信息定义为一个结构体individuals = struct('fitness',zeros(1,M), 'concentration',zeros(1,M),'excellence',zeros(1,M),'chrom',[]);%% step2 产生初始抗体群individuals.chrom = popinit(M,length);trace=[]; %记录每代最个体优适应度和平均适应度
%% 迭代寻优for iii=1:MAXGEN
     %% step3 抗体群多样性评价     for i=1:M         individuals.fitness(i) = fitness(individuals.chrom(i,:));      % 抗体与抗原亲和度(适应度值）计算         individuals.concentration(i) = concentration(i,M,individuals); % 抗体浓度计算     end     % 综合亲和度和浓度评价抗体优秀程度，得出繁殖概率     individuals.excellence = excellence(individuals,M,ps);               % 记录当代最佳个体和种群平均适应度     [best,index] = min(individuals.fitness);   % 找出最优适应度      bestchrom = individuals.chrom(index,:);    % 找出最优个体     average = mean(individuals.fitness);       % 计算平均适应度     trace = [trace;best,average];              % 记录          %% step4 根据excellence，形成父代群，更新记忆库（加入精英保留策略，可由s控制）     bestindividuals = bestselect(individuals,M,overbest);   % 更新记忆库     individuals = bestselect(individuals,M,sizepop);        % 形成父代群
     %% step5 选择，交叉，变异操作，再加入记忆库中抗体，产生新种群     individuals = Select(individuals,sizepop);                                                             % 选择     individuals.chrom = Cross(pcross,individuals.chrom,sizepop,length);                                    % 交叉     individuals.chrom = Mutation(pmutation,individuals.chrom,sizepop,length);   % 变异     individuals = incorporate(individuals,sizepop,bestindividuals,overbest);                               % 加入记忆库中抗体      
end
%% 画出免疫算法收敛曲线figure(1)plot(trace(:,1));hold onplot(trace(:,2),'--');legend('最优适应度值','平均适应度值')title('免疫算法收敛曲线','fontsize',12)xlabel('迭代次数','fontsize',12)ylabel('适应度值','fontsize',12)
%% 画出配送中心选址图%城市坐标city_coordinate=[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];carge=[20,90,90,60,70,70,40,90,90,70,60,40,40,40,20,80,90,70,100,50,50,50,80,70,80,40,40,60,70,50,30];%找出最近配送点for i=1:31    distance(i,:)=dist(city_coordinate(i,:),city_coordinate(bestchrom,:)');end[a,b]=min(distance');
index=cell(1,length);
for i=1:length%计算各个派送点的地址index{i}=find(b==i);endfigure(2)title('最优规划派送路线')cargox=city_coordinate(bestchrom,1);cargoy=city_coordinate(bestchrom,2);plot(cargox,cargoy,'rs','LineWidth',2,...    'MarkerEdgeColor','r',...    'MarkerFaceColor','b',...    'MarkerSize',20)hold on
plot(city_coordinate(:,1),city_coordinate(:,2),'o','LineWidth',2,...    'MarkerEdgeColor','k',...    'MarkerFaceColor','g',...    'MarkerSize',10)
for i=1:31    x=[city_coordinate(i,1),city_coordinate(bestchrom(b(i)),1)];    y=[city_coordinate(i,2),city_coordinate(bestchrom(b(i)),2)];    plot(x,y,'c');hold onend