《免疫优化算法ppt课件.pptx》由会员分享，可在线阅读，更多相关《免疫优化算法ppt课件.pptx（34页珍藏版）》请在三一办公上搜索。
1、免疫优化算法,作者qq:2919282547,免疫算法,一、免疫算法的生物学原理二、免疫算法的基本模型及算法三、免疫算法的简单应用,一、免疫算法的生物学原理,1.基本概念免疫系统 是由许多分布式的具有一定功能的个体（T细胞、B细胞、抗体和细胞因子等）通过相互作用形成的一个复杂的动态大系统的典型例子，具有个体特异性（一种免疫细胞仅对特定的抗原起作用）和整体多样性（免疫系统几乎对所有抗原都能进行处理）的双重特点，具备学习、记忆、自我调整、模式识别和特征提取能力。,一、免疫算法的生物学原理免疫系统,1.基本概念抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外
2、发生特异性反应的物质。抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。,一、免疫算法的生物学原理免疫系统,1.基本概念免疫疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。免疫调节在免疫反应过程中，大量的抗体的产生降低了抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同时产生的抗体之间也存在着相互刺激和抑制的关系，这种抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫反应维持一定的强度，保证机体的免疫平衡。,一、免疫算法的生物学原理免疫系统,一、免疫算法的生物学原理免疫系统,2.免疫系统的工作模型,二、免疫算法
3、的基本模型及算法,免疫系统与免疫算法的比较,二、免疫算法的基本模型及算法,免疫网络,左图是Jerne在克隆选择学说的基础上提出的独特型免疫网络。,免疫网络的微分方程,（1-1）,（1-2）,免疫系统特点,基因重组网络作用混沌增殖免疫变异免疫选择免疫记忆免疫元动态浓度控制,免疫优化算法算子,.免疫重组：模拟基因重组行为，在子群内将个基因位统一编码，然后随机取出基因重组为新的染色体。.免疫变异：以类似SGA的方式（如随机方式）和较大的概率进行变异操作，模拟高可变区的变异行为。抗体生成：模拟免疫网络作用、免疫选择和浓度控制。,首先，重写式（1-1）和式（1-2）,计算整理得：,控制浓度算法如下：,免
4、疫选择：在免疫行为中由于免疫过程中许多的高变异行为会破坏抗体和抗原的亲和力，因此要选择性的增加高亲和力的抗体数目来解决这个问题，因此我们根据抗体生成算子中计算出来的复制概率copy_probi（n）进行下一代的复制操作。混沌增殖：白细胞生成控制的研究表明在确定性时间系统中存在着内在混沌的可能，为模拟免疫行为中细胞的混沌增殖现象，引入Logistic方程：,由此生成的混沌序列是遗传学中用以描述昆虫数目世代变化规律的方程，可以用于模拟免疫细胞的增殖方式。免疫记忆：各子群依次计算完毕后，计算总群体的最大适应值。如果最大适应值大于免疫网络已存在的抗体所能提供的最大适应值，则对应的个体作为新的抗体加入抗
5、体记忆表中，本次最大适应值加入抗体适应值表，否则，启动免疫记忆，根据抗体表中所记忆的历史抗体，利用混沌增殖算子找出新的高适应值个体作为更好的免疫抗体，混沌初值分为历史抗体及抗体的变异个体两种。免疫代谢：模拟免疫元动态行为，找出子群内5%的低激励水平的个体并去除，利用方程从免疫记忆表中生成新的高适应值个体加入种群中。,免疫算法的基本流程,Y,N,三、免疫算法的简单应用,基于免疫优化算法的物流中心选址,1.配送中心的规模容量总可以满足需求点需求，并由其配送辐射范围内的需求量确定。2.一个需求点仅由一个配送中心供应。3.不考虑工厂到配送中心的运输费用。 然后要从n个需求点中找出配送中心，并向需求点配
6、送物品。目标函数是各配送中心到需求点的需求量和距离的乘积之和最小。 目标函数：,Z表示供应与否，取0或1,在物流配送中心选址模型中做如下假设,算法的实现步骤：1.产生初始种群。2.对上述群体中各个抗体进行评价。3.形成父代群体。4.判断是否满足条件，是则结束，反之，则继续下一步操作。5.新种群的产生。6.转去执行步骤2。,免疫优化算法流程图,抗原识别,初始抗体产生,抗体适应度计算,记忆细胞产生,抗体产生的促进和抑制,抗体产生(选择、交叉、变异),满足终止条件,输出结果,否,是,1.初始群体的产生,如果记忆库非空，则初始抗体群从记忆库中生成。否则，在可行解空间随机产生初始抗体群。此处采用简单的编
7、码方式。每个选址方案可形成一个长度为P的抗体（P表示配送中心的数量），每个抗体代表被选为配送中心的需求点的序列。如：考虑包含31个需求点的问题，从中选取6个作为配送中心。抗体2,7,15,21,29,11代表一个可行解。,2.解的多样性评价,1.抗体与抗原之间的亲和力 表示新的目标函数，分母的第二项表示对违反距离约束的解给予惩罚C取比较大的正数。,2.抗体与抗体之间的亲和力 其反映抗体之间的相似程度，此处借鉴Forrest等人提出的R位连续方法计算抗体之间的亲和力，两个个体有至少R位编码相同则两种抗体近似相同。,其中k表示抗体v和抗体s之间相同的位数，L为抗体的总长。例如，两个抗体2,7,15
8、,21,5,11、15,8,14,26,5,2经比较有3个相同则亲和度为0.5.,3.抗体浓度,T是设置的一个阈值,4.期望繁殖概率 在种群中，每个个体的期望繁殖概率与抗体与抗原之间的亲和力A和抗体浓度共同决定,是常数，可见个体的适应度越高，则期望繁殖率越大，个体的浓度越大，则期望繁殖率越大。这样就鼓励了高适应度个体，抑制了高浓度个体。,3.免疫操作：,1.选择：按照轮盘赌机制进行选择操作，个体被选择的概率即为期望繁殖概率。2.交叉：采用单点交叉法进行交叉操作。3.变异：采用随机变异位进行变异操作。,4.模型求解,为证明算法的有效性和可行性，采集了31个城市的坐标，每个用户的位置以及物资需求进
9、行仿真。 根据配送中心选址模型，按照免疫算法流程对该例求解。参数设置：种群规模：50；记忆库容量：10；迭代次数：100；交叉率：0.5；变异概率：0.4；多样性评价参数：0.95；,5.Matlab仿真：,sizepop=50; % 种群规模overbest=10; % 记忆库容量MAXGEN=100; % 迭代次数pcross=0.5; % 交叉概率pmutation=0.4; % 变异概率ps=0.95; % 多样性评价参数length=6; % 配送中心数M=sizepop+overbest; step1 识别抗原,将种群信息定义为一个结构体individuals = struct(f
10、itness,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.concentratio
11、n(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); % 计算平均适应度 tra
12、ce = trace;best,average; % 记录 step4 根据excellence，形成父代群，更新记忆库（加入精英保留策略，可由s控制） bestindividuals = bestselect(individuals,M,overbest); % 更新记忆库 individuals = bestselect(individuals,M,sizepop); % 形成父代群 step5 选择，交叉，变异操作，再加入记忆库中抗体，产生新种群 individuals = Select(individuals,sizepop); % 选择 individuals.chrom = Cro
13、ss(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),r,linewidth,2);hold onplot(trace(:,2),-,linewi
14、dth,2);legend(最优适应度值,平均适应度值)grid ontitle(免疫算法收敛曲线,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
15、;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_coord
16、inate(i,:),city_coordinate(bestchrom,:);enda,b=min(distance); index=cell(1,length); for i=1:length%计算各个派送点的地址indexi=find(b=i);end,figure(2)title(最优规划派送路线)cargox=city_coordinate(bestchrom,1);cargoy=city_coordinate(bestchrom,2);plot(cargox,cargoy,rs,LineWidth,2,. MarkerEdgeColor,r,. MarkerFaceColor,b,
17、. MarkerSize,20)hold on plot(city_coordinate(:,1),city_coordinate(:,2),o,LineWidth,2,. MarkerEdgeColor,k,. MarkerFaceColor,g,. MarkerSize,10)grid onfor 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,LineWidth,2);hold onendtitle(物流配送中心选址方案),6.仿真结果,最后，结果选址方案是5,25,18,9,12,27,如图中所标，可以看出免疫算法有较好的收敛性。,
