先进制造技术

上海应用技术学院研究生课程（论文类）试卷2013/2014学年第2学期课程名称：先进制造系统课程代码：DZ0202002论文题目：免疫优化算法在物流配送中心选址中的应用学生姓名：贺国昂专业﹑学号：136101106学院：电气与电子工程学院课程（论文）成绩：课程（论文）评分依据（必填）：任课教师签字：日期：年月日课程（论文）题目：免疫优化算法在物流配送中心选址中的应用内容：免疫优化算法在物流配送中心选址中的应用贺国昂（上海应用技术学院电气与电子工程学院，上海201408）摘要：遗传算法是目前最为广泛使用的可以用于优化问题的寻优方法之一。针对其容易陷入局部极值点等弱点，目前已提出了一些基于免疫概念的优化算法。本文针对物流配送中心选址问题，以物流成本为目标函数，采用免疫优化算法对配送中心进行选址。通过全国31城市的物流需求点实例进行论证。关键词：免疫优化算法；配送中心；目标函数；ImmuneOptimizationAlgorithmandApplicationonLocationofDistributionCenterAbstract：Geneticalgorithmsarecurrentlyoneofthemostwidelyusedmethodofoptimizationproblemscanbeusedforoptimization.Foritiseasytofallintolocaloptimumandotherweaknesseshasmadeanumberofoptimizationalgorithmbasedontheconceptofimmunity.Inthispaper,theproblemoflogisticsdistributioncenterlocation,logisticscostsastheobjectivefunction,immuneoptimizationalgorithmusingthedistributioncentersiteselection.Demonstratethrough31citiesnationwidelogisticsdemandpointsinstance.Keywords:ImmuneOptimizationAlgorithm;DistributionCenter;ObjectiveFunction1引言

遗传算法是基于遗传学理论和生物进化论而建立的一类相对完善的算法体系。遗传算法在群体优化的过程中通过不同的操作算子不断地优化种群，达到寻找最优解或满意解的目的，尤其适用于非线性优化问题。因而是目前使用最为广泛的一类可以用于优化问题的寻优方法之一。然而实验和实际应用表明，该类算法仍存在许多不足，例如：对于多目标函数优化问题，它容易出现过早陷于局部极值点的问题。

另一方面，自然生物系统的许多其他机制为进一步的研究提供了依据。生物免疫系统正满足了这种需求。免疫系统是一个高度分布、高度并行的大规模自适应系统。随着世界经济的快速发展以及现代科学技术的进步，物流业作为国民经济的一个新兴服务部门，正在全球范围内迅速发展。物流业的发展给社会的生产和管理、人们的生活和就业乃至政府的职能以及社会的法律制度等带来巨大的影响，因此物流也被认为是国民经济发展的动脉和基础产业，被形象地喻为促进经济发展的“加速器”。

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

免疫系统对侵入机体的非己成分（如细胞、病毒和各种病原体）以及发生了突变的自身细胞（如癌细胞）具有精确地识别、适度地应答和有效地排除的能力。免疫系统的功能主要由免疫细胞完成，免疫细胞主要有淋巴细胞（包括T淋巴细胞、B淋巴细胞）和巨噬细胞。

免疫系统可分为先天性免疫系统和适应性免疫系统、先天性免疫系统是生物在种系发育和进化过程中逐渐建立起来的一系列天然防御功能，其特点是与生俱有，能传给下一代，无特异性，对各种病原体都有一定的防御功能。适应性免疫系统则是在个体生命过程中慢慢建立起来的，当免疫系统与某种病原体产生“免疫初次相应”之后，能记住该病原体，当再次遇到它时，会产生“免疫再次响应”，迅速而有效地消除该病原体

从生物信息处理的角度来看，免疫系统具有以下的特征：多样性

多样性是免疫系统的重要特征之一。免疫学的初步研究表明，通过细胞的分裂和分化作用，体细胞超变异，抗体的可变区与不变区的基因重组等方式，免疫系统可产生大量的不同抗体来抵御各种抗原从而使免疫抗体库具有丰富的多样性。免疫自我调节

免疫系统具有维持免疫平衡的机制，能将免疫响应的强度限定在一定水平上。通过对抗体的抑制和促进作用，能自我调节产生适当数量的必要抗体。免疫记忆特性

产生抗体的小部分细胞会作为长寿的记忆细胞而被保存下来，当再次遇到同类抗原，相应的记忆细胞会迅速激发而产生大量的抗体。这一特性在医学临床中应用为接种疫苗，将某些传染病的低活性疫苗注射到未感染者身上，刺激接受者产生抗体，从而产生对此类传染病的抵抗能力。分布式系统

免疫系统是一个典型的分布式系统，由许多局部相互作用的免疫细胞组成来完成对全局免疫保护功能，并没有一个集中控制中心，因而也具有容错功能，不会象集中控制系统那样因为控制中心的小失误，造成全局功能的瘫痪。

动态适应特性

几百万年以来，免疫系统都在与病原体不断竞争的过程中逐渐进化，这种免疫系统与病原体的相互适应的过程具有明显的动态特性，两者相互竞争共同进化。

多时间尺度进化系统

免疫系统的变化包括从只有几毫秒的亚分子事件到几分钟、几年的细胞群体变化，以及需要无数代才能完成的改变，免疫系统实际上是一个随环境改变而不断完善的多事件尺度优化系统。3物流配送中心选址模型的建立配送中心选址问题描述为在有限的位置（m个）中选择一定数量的地点（p个），以合理的规模建立配送中心，为n个配送点配送物品,使得在选出点建立的配送中心在满足配送需求的前提下，成本（包括建造成本和运营成本）最低。因此，在物流配送中心选址模型中作如下假设：（1）

配送中心的规模容量总可以满足需求点需求，并由其配送辐射范围内的需求量决定；

（2）一个需求点仅有一个配送中心供应；

（3）不考虑工厂到配送中心的运输费用。基于以上假设，建立如下模型。该模型是一个选址/分配模型，在满足距离上限的情况下，需要从n个需求点找出配送中心并向各个需求点配送货物。目标函数是个配送中心到需求点的需求量和距离之的乘积之和最小，目标函数为约束条件为：其中，是所有需求点的序号集合；为到需求点的距离小于s的备选配送中心集合，表示配送点的需求量；表示从需求点i到离他最近的的配送中心的距离，为0-1变量，表示拥护和物流中心的服务需求分配关系，当其为1时，表示需求点j的需求量由配送中心j供应，否则，是0-1变量，当其为1时，表示点j被选为配送中心，s为新建配送中心里有他服务的需求点的距离上限。式（1-2）保证每个需求点只能由一个配送中心服务，式（1-3）确保需求点的需求量只能被设为配送中心的点供应，既没有配送中心的点不会有客户；式（1-4）规定了被选为配送中心的数量为p；式（1-5）表示变量和是0-1变量；式（1-6）保证了需求点在配送中心可配送到的范围内。4免疫优化算法免疫算法（immunealgorithm）是受生物免疫系统启发，在免疫学基础上发展起来的一种新型的智能计算方法。它利用免疫系统的多样性产生和维持机制来保持群体的多样性，克服了一般寻优过程尤其是多峰函数寻优过程中难处理的早熟问题，最终求得全局最优解。4.1算法流程免疫算法流程如图2-1所示：图2-1免疫算法流程图免疫优化算法具体实现步骤如下：（1）分析问题。对问题及其解的特性进行分析，分析解合适表达形式；（2）产生初始抗体群。随机产生N个个体并从记忆库中提取m个个体构成初始群体，其中m为记忆库中个体的数量；（3）对上述群体中各个抗体进行评价。在本算法中对个体的评价是以个体的期望繁殖率P为标准的；（4）形成父带群体。将初始群体按期望繁殖率P进行降序排列，并取前N个个体构成父带群体；同时取前m个个体存入记忆库中。（5）判断是否满足结束条件，是则结束；反之，则进行下一步操作；（6）新群体产生。基于步骤（4）的计算结果对抗体群体进行选择、交叉、变异操作得到新群体，再从记忆库中取出记忆的个体，共同构成新一代群体。（7）转去执行步骤（3）。4.2初始抗体群的产生如果记忆库为空，则初始抗体群从记忆库中选择生成。否则，在可行解空间随机产生初始抗体群。此处采用简单编码方式。每个选址方案可形成一个长度为p的抗体（p表示配送中心数量），每个抗体代表被选为配送中心的需求点的序列。例如，考虑包含31个需求点的问题1,2，…,31表示需求点的序列。从中选出6个作为配送中心。抗体[2715212911]代表一个可行解，它表示2,7,15,21,29,11被选为配送中心。这种编码方式能够满足与约束条件。4.3解的多样性评价（1）抗体与抗原间亲和力抗体与抗原之间的亲和力用于表示抗体对抗原的识别程度，此处针对上述配送中心选址模型设计亲和力函数（4-1）其中，为目标函数；分母中第二项表示为违反距离约束的解给予惩罚，C取一个比较大的正数。（2）抗体与抗体间亲合力抗体与抗体之间的亲和力反映了抗体之间的相似程度。鉴于此处抗原的编码方法，各位之间不需考虑排序，可参考变形的R位连续方法计算抗体间亲和度，即（4-2）其中，为抗体v与抗体s中相同的位数；L为抗体的长度。（3）抗体浓度抗体的浓度即群体中相似抗体所占的比例，即（4-3）其中，N为抗体总数；；T为预先设定的一个阀值。（4）期望繁殖概率在群体中，每个个体的期望繁殖概率有抗体与抗原间亲和力和抗体浓度两部分共同决定，即（4-4）其中，为常数。由上式可见，个体适应度越高，则期望繁殖概率越大；个体浓度越大，则期望繁殖概率越小。4.4免疫操作（1）选择：按照轮盘赌选择机制进行选择操作，个体被选择的概率为式（2-4）计算出期望繁殖概率。（2）交叉：本文采用单点交叉法进行交叉操作；（3）变异：采用常用的变异方法，即随机选择变异位进行变异。5仿真实验及结果分析为证明算法的可行性和有效性，采集了全国31个城市的坐标，每个用户的位置及其物资需求量由表3-1中给出，这里的物资需求量是经过规范化处理后的数值，并不代表实际值。从中选择6个作为物流配送中心。根据配送中心选址模型，按照免疫算法步骤对算例进行求解，算法的参数分别为：种群规模为50，记忆库容量为10，迭代次数为100，交叉概率为0.5，变异概率为0.4，多样性评价参数设为0.95，求得配送中心的选址方案为[1825527914],此方案以各需求点需求量为权重的距离和为。免疫算法主函数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=[];%记录每代最个体优适应度和平均适应度%%迭代寻优foriii=1:MAXGEN%%step3抗体群多样性评价fori=1:Mindividuals.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));holdonplot(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];%找出最近配送点fori=1:31distance(i,:)=dist(city_coordinate(i,:),city_coordinate(bestchrom,:)');end[a,b]=min(distance');index=cell(1,length);fori=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)holdonplot(city_coordinate(:,1),city_coordinate(:,2),'o','LineWidth',2,...'MarkerEdgeColor','k',...'MarkerFaceColor','g',...'MarkerSize',10)fori=1:31x=[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');holdonend适应度计算functionfit=fitness(individual)%计算个体适应度值%individualinput个体%fitoutput适应度值%城市坐标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];%找出最近配送点fori=1:31distance(i,:)=dist(city_coordinate(i,:),city_coordinate(individual,:)');end[a,b]=min(distance');%计算费用fori=1:31expense(i)=carge(i)*a(i);end%距离大于3000取一个惩罚值fit=sum(expense)+4.0e+4*length(find(a>3000));end相似度计算functionresemble=similar(individual1,individual2)%计算个体individual1和individual2的相似度%individual1,individual2input两个个体%resembleoutput相似度k=zeros(1,length(individual1));fori=1:length(individual1)iffind(individual1(i)==individual2)k(i)=1;endendresemble=sum(k)/length(individual1);end浓度计算functionconcentration=concentration(i,M,individuals)%计算个体浓度值%iinput第i个抗体%Minput种群规模%individualsinput个体%concentrationoutput浓度值concentration=0;forj=1:Mxsd=similar(individuals.chrom(i,:),individuals.chrom(j,:));%第i个体与种群个体间的相似度%相似度大于阀值ifxsd>0.7concentration=concentration+1;endendconcentration=concentration/M;End期望繁殖率计算functionexc=excellence(individuals,M,ps)%计算个体繁殖概率%individualsinput种群%Minput种群规模%psinput多样性评价参数%excoutput繁殖概率fit=1./individuals.fitness;sumfit=sum(fit);con=individuals.concentration;sumcon=sum(con);fori=1:Mexc(i)=fit(i)/sumfit*ps+con(i)/sumcon*(1-ps);endend选择个体functionret=Select(individuals,sizepop)%轮盘赌选择%individualsinput:种群信息%sizepopinput:种群规模%retoutput:选择后得到的种群excellence=individuals.excellence;pselect=excellence./sum(excellence);%事实上pselect=excellence；index=[];fori=1:sizepop%转sizepop次轮盘pick=rand;whilepick==0pick=rand;endforj=1:sizepoppick=pick-pselect(j);ifpick<0index=[indexj];break;%寻找落入的区间，此次转轮盘选中了染色体jendendend%注意：在转sizepop次轮盘的过程中，有可能会重复选择某些染色体individuals.chrom=individuals.chrom(index,:);individuals.fitness=individuals.fitness(index);individuals.concentration=individuals.concentration(index);individuals.excellence=individuals.excellence(index);ret=individuals;end实数交叉functionret=Cross(pcross,chrom,sizepop,length)%交叉操作%pcorssinput:交叉概率%chrominput:抗体群%sizepopinput:种群规模%lengthinput:抗体长度%retoutput:交叉得到的抗体群%每一轮for循环中，可能会进行一次交叉操作，随机选择染色体是和交叉位置，是否进行交叉操作则由交叉概率（continue）控制fori=1:sizepop%随机选择两个染色体进行交叉pick=rand;whileprod(pick)==0pick=rand(1);endifpick>pcrosscontinue;end%找出交叉个体index(1)=unidrnd(sizepop);index(2)=unidrnd(sizepop);whileindex(2)==index(1)index(2)=unidrnd(sizepop);end%选择交叉位置pos=ceil(length*rand);whilepos==1pos=ceil(length*rand);end%个体交叉chrom1=chrom(index(1),:);chrom2=chrom(index(2),:);k=chrom1(pos:length);chrom1(pos:length)=chrom2(pos:length);chrom2(pos:length)=k;%满足约束条件赋予新种群flag1=test(chrom(index(1),:));flag2=test(chrom(index(2),:));ifflag1*flag2==1chrom(index(1),:)=chrom1;chrom(index(2),:)=chrom2;endendret=chrom;End实数变异functionret=Mutation(pmutation,chrom,sizepop,length1)%变异操作%pmutationinput:变异概率%chrominput:抗体群%sizepopinput:种群规模%iiiinput:进化代数%MAXGENinput:最大进化代数%length1input:抗体长度%retoutput:变异得到的抗体群%每一轮for循环中，可能会进行一次变异操作，染色体是随机选择的，变异位置也是随机选择的fori=1:sizepop%变异概率pick=rand;whilepick==0pick=rand;endindex=unidrnd(sizepop);%判断是否变异ifpick>pmutationcontinue;endpos=unidrnd(length1);whilepos==1pos=unidrnd(length1);endnchrom=chrom(index,:);nchrom(pos)=unidrnd(31);whilelength(unique(nchrom))==(length1-1)nchrom(pos)=unidrnd(31);endflag=test(nchrom);ifflag==1chrom(index,:)=nchrom;endendret=chrom;End产生新种群Functionnewindividuals=incorporate(individuals,sizepop,bestindividuals,overbest)%将记忆库中抗体加入，形成新种群%individualsinput抗体群%sizepopinput抗体数%bestindividualsinput记忆库%overbestinput记忆库容量m=sizepop+overbest;newindividuals=struct('fitness',zeros(1,m),'concentration',zeros(1,m),'excellence',zeros(1,m),'chrom',[]);%遗传操作得到的抗体fori=1:sizepopnewindividuals.fitness(i)=individuals.fitness(i);newindividuals.concentration(i)=individuals.concentration(i);newindividuals.excellence(i)=individuals.excellence(i);newindividuals.chrom(i,:)=individuals.chrom(i,:);end%记忆库中抗体fori=sizepop+1:mnewindividuals.fitness(i)=bestindividuals.fitness(i-sizepop);