免疫算法理论与应用近代免疫的概念是指机体对自己或非己的识别并排除非己的功能，目的是维持自身生理平衡与稳定.免疫算法就是模拟免疫系统抗原识别、抗原与抗体结合及抗体产生过程，并利用免疫系统多样性和记忆机理抽象得到的一种免疫算法。这里介绍免疫算法的算法流程与代码.免疫学中基本概念的思想在免疫算法设计中得到有效应用，即亲和力，相似度，浓度及激励度,根据算法需要给出描述. 定义1 亲和力指抗体与抗原的匹配程度.反映在优化问题上，抗体（NBP）的亲和力定义为函数，与成反比，在此仍表示抗
(x)f(x)f(x)x体对应的可行解的目标函数.这里选
择 1
定义2 相似度指抗体
与其他抗体的相似程度，其被定义为，此根据信息熵理论设计.设M为含有m个字符的字符集，群体G为由N个长度为的字符串构成的集合，即l，其中G中基因座的信息熵定义为其中为M 中第个符号出现在基因座上的概率p ij定义3 抗体浓度指抗体在抗体群中与其相似的抗体所占的比例，定义为函数即
，其中为
浓度阈值，，在此称为浓度抑制半径. 定义 4 激励度是指抗体应答抗原和被其他抗体激活的综合能力，定义为函
e 数，其中为调节因子，.抗体应答
抗原综合能力与其亲和力成正比，与其在抗体群中浓度成反比定义 5 克隆选择是
指在给定的选择率下，，在抗体群中选择亲和力较高的抗体.亲和力低的抗体则被清除. 定义6 细胞克隆是指在给定
的繁殖数M下，抗体群X中所有抗体依据自
s2身的亲和力及繁殖率共繁殖M个克隆的映射.，它是确定性映射，即设为抗体群的繁殖率函数，为抗体群，则定义x抗体繁殖个相同的克隆构成的集合. 由下式确定：
mmiiim . 定义 7 亲和突变是指抗体空间到自身的随机映射，，其作用方式:S T m是抗体按与其亲和力成正比的可变概率独立地改变自身的基因，可选 . 定义 8 克隆抑制指在抗体群中依据抗体的亲和力和相似度抑制部分抗体的确定性映射,.克隆抑制算子的设计，设X是群体规模为M的抗体群，依据抗体的相似度和抑制半径以及式，将X划分为子群，不妨设获q个子群，利用处罚函数对中亲和力低的抗体进行处罚. 定义9 免疫选择是指在抗体群中依据抗体的激励度选择抗体的随机映射，N按其概率
规则 . x(X)ii j定义 10 募集
新成员指在抗体空间S中随机选择抗体. 免疫算法描
述如下： Step 1 确定初始群体规模N，克隆总数
M，克隆选择率，抑制半径，募集新成员插入率，. Step 2 随机产生N个抗体构成初始抗体群，
计算中抗体亲和力. AA00 Step 3 利用克隆选择算子在
中选择个抗体构成群体. NABnn1Step 4 克隆选择算子
作用繁殖M个克隆，中抗体进入记忆池，并更BBnn新
记忆池中亲和力低的抗体. Step 5 依据亲和突变算
子对每个克隆细胞进行突变，获得克隆集. Cn* Step 6
克隆抑制算子作用于，获得克隆集C C nn
* Step 7 计算与中亲和力较高的N个抗体的激励度.
用比例选择选取CAnn个抗体.其中中亲和力最高的
不参与选择.获得新群体.
8 由募集新成员算子任选个自我抗体插入，并计算
个抗体的亲和力，从而获得.
1 Step 9 若满足终止条件，输出结果，
否则，返回step 3. 免疫算法在函数优化中应用举例
例Rosebrock函数的全局最大值计算. 222max
i确定编码方法：xx用长度为10
的二进制编码串来分别表示俩个决策变量.10位二进
制编码串,12xx可以表示从0到1023之间的1024个
数，故将的定义域离散化为1023个,12均等的区域，
包括俩端点共1024个不同的离散点.从离散点-2.048
到 2.048，依次让它们对应于00000000000（0）到11111111111（1023）之间的二进制编码.再将xx,分
别表示的两个10位长的二进制编码串接在一起，组
成一个20位长的二12进制编码，它就构成了函数优
化问题的染色体编码方法.使用这种编码方法，解空
间与免疫算法的搜索空间具有一一对应的关系. 确定
解码方法：解码时需将20位长的二进制编码串切断
为二个10位长的二进制编码串，然后分别将它们转
换成对应的十进制整数代码，分别记为和. 依据前述
个体编码方yy12yx法和对定义域的离散化方法可知，
将代码转换为的解码公式为：iiyx ,
i1023求函数的全局最大值免疫
算法代码如下：Rosebrock #include
#include
#include
double activity; }; int generation; int best_index; struct individual
population[POPSIZE]; struct individual nextpopulation[POPSIZE];
struct individual array[POPSIZE]; struct individual A; struct
individual B; struct individual bestindividual; struct individual currentbest; int PopSize =80; double umu =0.08; double r =0.001; double rad =0.3; int clone_total =0;
//******************************************************
************** void GenerateInitialPopulation(); long DecodeChromosome(char *string,int point,int length); void CalculateObjectValue(struct individual array[],int n); void Calculateaffective(struct individual array[],int n); void EvaluatePopulation(); void affectivesort(struct individual array[],int
n); void clonenum(); void MutationOperator(void);
void GenerateNextPopulation(void); double CalculateSimilarity(struct individual A,struct individual B); void
Inhibition(void); void chongzu(); void CalculateConcentrationValue(struct individual population[],int n);
void CalculateActivityValue(struct individual population[],int n);
void activeslect(); void sortnewmember(); void PerformEvolution();
void FindBestIndividual(); void OutputTextReport();
//******************************************************
************** void main() { generation=0; GenerateInitialPopulation(); EvaluatePopulation(); while(generation ************************ void GenerateInitialPopulation() { int i,j; srand((unsigned)time(NULL)); //srand((unsigned)time(0)); for(i=0;i ************************void GenerateNextPopulation(void) { //排序选择亲和力高的进行克隆affectivesort(population,PopSize); clonenum(); MutationOperator(); Inhibition(); chongzu(); activeslect(); sortnewmember(); } //****************************************************** ************** void EvaluatePopulation(void) { CalculateObjectValue ( population,PopSize); Calculateaffective ( population,PopSize); FindBestIndividual(); } //****************************************************** *********************** long DecodeChromosome(char *string,int point,int length) { int i; long decimal=0L; char *pointer; for(i=0,pointer=string+point;i x1=4.096*temp1/1023.0-2.048; x2=4.096*temp2/1023.0-2.048; array[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1); } } //****************************************************** *********************** void Calculateaffective(struct individual array[],int n) { int i; for(i=0;i { for(i=0;i { a=array[i+1]; array[i+1]=array[i]; array[i]=a; } } } } //****************************************************** ************ void FindBestIndividual() { int i; bestindividual=population[0]; for(i=0;i { if(population[i].affective>bestindividual.affective) { bestindividual=population[i]; best_index=i; } if(generation==0) { currentbest=bestindividual; } else { if(bestindividual.affective>currentbest.affective) { currentbest=bestindividual; } } } } //****************************************************** *********************** void PerformEvolution() { if(bestindividual.affective>currentbest.affective) { currentbest=population[best_index]; } } //****************************************************** *********************** void clonenum() { int i,j; int M =100; int m[POPSIZE]; int L=0; double sum1=0; double sg =0.8; for(i=0;i<(int)(sg*M);i++) { sum1+=array[i].affective; m[i]=(int)(array[i].affective*M/sum1); clone_total+=m[i]; } for(i=0;i<(int)(sg*M);i++) { for(j=0;j //****************************************************** *********************** void MutationOperator(void) { int i,j; double p,po; for(i=0;i { for(j=0;j :'0'; } } } } //****************************************************** *********************** double CalculateSimilarity (struct individual A,struct individual B) { int j=0; double sum=0.0; for(j=0;j { sum+=(A.chrom[j]=B.chrom[j])?0:1; } sum=sum*(log(2.0))/CHROMLENGTH; return sum; } //****************************************************** *********************** void Inhibition(void) { int i,j; int L=0; int numinh=0; //double rad =0.3; CalculateObjectValue(nextpopulation,clone_total); Calculateaffective(nextpopulation,clone_total); 排序进行抑制affectivesort(nextpopulation,clone_total);// for(i=0;i 1;i++) { for(j=i+1;j L=i+1; } clone_total=L+1; } //****************************************************** *********************** void chongzu() { int i; for(i=0;i { population[i+PopSize]=nextpopulation[i]; } affectivesort(population,clone_total+PopSize); } //****************************************************** *********************** void CalculateConcentrationValue(struct individual population[],int n) { int i,j,m=0; for(i=0;i double sum2=0.0; double concent[POPSIZE]; struct individual con_population[POPSIZE]; CalculateConcentrationValue(population,PopSize); CalculateActivityValue(population,PopSize); for(i=0;i *********************** void sortnewmember() { int i,j; int N3=(int)(PopSize*umu); for(i=0;i N3].chrom[j]=(rand()%10<5)?'0':'1'; } population[i+PopSize- N3].chrom[CHROMLENGTH]='\0'; } } //****************************************************** *********************** void OutputTextReport(void) { int i; printf("gen=%d,best=%f,",generation,currentbest.value); printf("chromosome="); for(i=0;i 参考文献[1] 黄席樾，张 著洪等.现代智能算法理论及应用.北京科学出版社，2005. [2] 周明.遗传算法原理及其应用.国防工业出版社，2002.202. 文件头: 一个基于Matlab的人工免疫算法 %Immune Algorithm based on the immune network model for function f(x1,x2) optimum %copy right SCUT Guangxing Tan 2005.02.18 clear all; %Parameters Size=120; G=200; CodeL=15; E=round(rand(Size,2*CodeL)); %Initial Code %Main Program for k=1:1:G time(k)=k; for s=1:1:Size m=E(s,:); y1=0;y2=0; %Uncoding m1=m(1:1:CodeL); for i=1:1:CodeL y1=y1+m1(i)*2^(i-1); end x1=10.24*y1/65535.0-5.12; m2=m(CodeL+1:1:2*CodeL); for i=1:1:CodeL y2=y2+m2(i)*2^(i-1); end x2=10.24*y2/65535.0-5.12; %f(X1,X2)=(a/(b+(x1*x1+x2*x2)))*(a/(b+(x1*x1+x2*x2)))+(x1*x1+x2*x2)*(x1*x1+x2*x2) %here -5.12= 基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。由于DE 算法操作简单，寻优能力强，自提出以来引起了国内外学者的高度关注，目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群P 0001[,,]N =X x x L ，其中000T 1[,,]i i iN x x =x L ，p N 为DE 种群规模。DE 算法的核心思想在于采取变异和交叉操 作生成试验种群，然后对试验种群进行适应度评估，再通过贪婪思想的选择机制，将原种群和试验种群进行一对一比较，择优进入下一代。 基本DE 算法主要包括变异、交叉和选择三个操作。首先，在种群中随机选取三个个体，进行变异操作： 1123()t t t t i r r r F +=+-v x x x 其中1t i +v 表示变异后得到的种群，t 表示种群代数，F 为缩放因子，一般取(0,2]，它的大小可以决定种群分布情况，使种群在全局范围内进行搜索；1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。 然后，将变异种群和原种群进行交叉操作： 1,R 1 ,,R () or () () and ()t i j t i j t i j v rand j C j randn i u x rand j C j randn i ++?≤=?=?>≠?? 其中t 1,i j u +表示交叉后得到的种群，()rand j 为[0,1]之间的随机数，j 表示个体的第j 个分量，R C 为交叉概率，()randn i 为[1,,]N L 之间的随机量，用于保证新个体至少有一维分量由变异个体贡献。 最后，DE 算法通过贪婪选择模式，从原种群和试验种群中选择适应度更高的个体进入下一代： 11t 11 ()() ()()t t t i i i i t t t i i i f f f f ++++?<=?≥?u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。当试验个体1t i +u 的适应度优于t i x 时， 1．差分进化算法背景 差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。 差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。它的全局寻优能力和易于实施使其在诸多应用中取得成功。 2.差分进化算法简介 差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE 的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。 3.差分进化算法适用情况 差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。它可以对非线性不可微连续空间的函数进行最小化。目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。 4.基本DE算法 差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。然后，变异向量的参数与另外事先确 基于异构网络环境的人工免疫系统及其算法研究综述 摘要：人工免疫作为一种新型的研究领域，有着广泛的应用范围，人工免疫算法的研究也已成为人工智能研究领域的一个重要内容，它突出地体现了现代科学发展的多层次、多学科和多领域的相互渗透、相互交叉和相互促进的特点。因此，将人工免疫系统的原理应用在计算机领域有着重要的理论意义和实际应用价值。本文详细介绍了几种常见的免疫算法机理，并指出了人工免疫系统的研究方向。 关键词：人工免疫系统，人工免疫算法 1、人工免疫系统介绍 1.1 人工免疫系统 20世纪70年代，Jerne[1,2]首先提出了人工免疫系统的网络假说，并以此开创了独特型网络理论。独特型网络理论为人工免疫系统以后的应用和研究提供了理论指导，并发展成为人工免疫的基础理论之一。 Perelson[3]在独特型网络理论的基础上进一步给出了免疫网络的数学框架，从而加快了人工免疫系统在计算机科学方面的发展。1986年，Farmer【4】基于免疫网络的假说，构造了一个免疫系统的动态模型，并提出了一些学习算法的构造思想。此后Forrest 又提出了阴性选择算法，他的工作对于人工免疫系统的发展尤其是在信息安全领域应 用的发展具有十分重要意义。随后的研究者不断从生物免疫系统中吸取精髓，使之广泛用于优化、数据分析、机器学习、聚类分析、模式识别、故障诊断、机器人控制、自适应控制领域、计算机及网络安全领域等各个应用领域。人工免疫系统主要关注的是用计算和数学模型对免疫学进行模拟，更好地了解免疫系统。人工免疫包括：免疫系统，遗传系统和神经系统。 按照目前人们普遍接受的观点，基于免疫系统仿生机理开发的入工免疫系统[9-12]的理论研究主要在集中在人工免疫网络模型 和人工免疫算法两个方面。针对人工免疫网络模型的研究多集中在以Jerne的独特性免疫网络为基础的不同模型仿真实验上。而针对人工免疫算法的研究主要是在已有系统 模型的基础上，制定一些目的性较强的计算方法或实施策略，主要包括免疫遗传算法、克隆选择算法、阴性选择算法和免疫学习算法等。 1.2 人工免疫系统处理特性 从信息处理的角度上分析，人工免疫系统具有如下特点： （1）多样性：免疫系统抗体库的多样性特征，能及时对不同类型的入侵抗原进行有效的保证和消除。 （2）容错性：免疫系统在分类和响应中突发的一些比较小的信息处理错误不会使整个信息处理结果造成严重影响。 （3）分布自律性：免疫系统没有集中控制系统，它是由许多局部的并且相互作用的基本信息单元联合起来达到对全局的保护。 （4）动态稳定性：免疫系统要消除各种外来的不断变化的入侵抗原，并保持整个系统的稳定。 （5）自适应鲁棒性：免疫系统具有非常强的自我学习能力，并且通过此学习使其成为能够随环境不断变化而不断改变和完善的一个自适应型的鲁棒进化系统。 2、免疫算法[6-8]介绍 人工免疫系统是借鉴免疫系统机理特点和功能的智能系统，具有广泛的应用和理论基础。在此着重阐述免疫算法的研究和AIS的应用研究。 2.1 免疫遗传算法 为了使遗传算法在个体多样性和群体收敛性之间取得平衡，并克服遗传算法的缺 目录 1选题依据和意义 (2) 1.1研究背景及意义 (2) 1.2免疫算法的概述 (2) 1.3免疫算法的研究现状 (3) 1.4物流配送中心选址的概述 (4) 1.5物流配送中心的研究现状： (4) 1.6论文组织结构 (5) 2基本的免疫算法 (5) 2.1免疫算法的相关概念介绍： (6) 2.2免疫算法的步骤 (7) 2.3免疫算法流程图： (8) 2.4选择参数 (11) 2.5免疫算法与遗传算法的比较： (12) 3物流配送中心选址的数学模型的建立 (13) 4免疫算法物流配送中心选址中的应用： (14) 5实验： (15) 5.1小结 (18) 6总结与展望 (18) 1选题依据和意义 1.1研究背景及意义 科技日新月异的发展的21世纪，学科之间的融合成为了各学者的研究新方向，各学科之间相互渗透、相互影响、相互作用成为了新世纪科技发展的新特征。其中，由计算机科学与生命学科相互结合而产生的新型智能算法——免疫 算法就是其中的代表之一。 近年来，随着我国经济的快速发展并逐渐走向全球化的道路，物流已成为 了经济发展的重要产业之一，现如今各大城市都建设有自己的物流配送网络， 这对于城市的招商引资，资源的优化配置，经济产业的运行效率都有着促进作用。物流配送中心作为物流业重要的环节，其选址问题吸引着专家学者投身研 究当中。由于物流配送中心一旦选定并进行建设，其位置是固定的，所以在地 址的选定上尤为重要。相比较于传统的选址方法，免疫算法以其收敛速度快， 鲁棒性强等特点，得到专家学者们的青睐。 免疫算法是模仿生物免疫机制，结合基因的进化机理，人工地构造出的一 种新型智能搜索算法。免疫算法具有一般免疫系统的特征，免疫算法采用群体 搜索策略，一般遵循几个步骤”产生初始化种群→适应度的计算评价→种群间个 体的选择、交叉、变异→产生新种群”。通过这样的迭代计算，最终以较大的概 率得到问题的最优解。相比较于其他算法，免疫算法利用自身产生多样性和维 持机制，保证了种群的多样性，克服了一般寻优过程中特别是多峰值的寻优过 程中不可避免的“早熟”问题，求得全局最优解。大量表明，免疫算法能在较少 的迭代数能快速收敛到全局最优。因此，免疫算法在物流配送中心选址问题的 研究具有一定的应用价值和参考价值。 1.2免疫算法的概述 人们对人工免疫算法的研究从免疫学的基础上开始的。对免疫算法的深入研究，发现其在解决复杂问题上西安实处了强大的信息处理能力。 基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体，而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}12(),, ,t t t NP X t x x x =，()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =，则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =，222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群 体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。 差分进化算法-入门 基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}1 2 (),,,t t t NP X t x x x =L ，() 1 2 ,,,T t t t t i i i iD x x x x =L 为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,,,)t t t t T i i i iD v v v v =L ，则 123() 1,2,,D t t t t ij r j r j r j v x F x x j =+-=L (1) 其中111112(,,,)t t t t T r r r r D x x x x =L ，222212(,,,)t t t t T r r r r D x x x x =L 和333312(,,,)t t t t T r r r r D x x x x =L 是群体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。 差分进化算法（DE）[1]是Storn 和Price 在1995 年提出的一种基于种群差异的进化算法，DE是一种随机的并行搜索算法。差分进化计算和其他进化计算算法一样，都是基于群体智能理论的优化算法，利用群体内个体之间的合作与竞争产生的群体智能模式来指导优化搜索的进行。与其他进化计算不同的是，差分进化计算保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了进化操作的复杂性。差分进化计算特有的进化操作使得其具有较强的全局收敛能力和鲁棒性，非常适合求解一些复杂环境中的优化问题。 最初试图使用向量差进行向量种群的混洗，以此来解决切比雪夫多项式适应性问题。DE 通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质上是一种基于实数编码的具有保优思想的进化算法。该算法实现技术简单，在对各种测试问题的实验中表现优异，已经成为近年来进化算法研究中的热点之一。 差分进化算法基本原理 基本的差分进化算法是基于候选方案种群的算法，在整个搜索空间内进行方案的搜索，通过使用简单的数学公式对种群中的现有方案进行组合实现的。如果新的方案有所改进，则被接受，否则被丢弃，重复这一过程直到找到满意的方案。 设 f 是最小化适应度函数，适应度函数以实数向量的形式取一个候选方案作为参数，给出一个实数数值作为候选方案的输出适应值。其目的是在搜索空间的所有方案p 中找到m 使得f(m) ≤f(p)。最大化是找到一个m 使得f(m) ≥f(p)。 设X=(x1, x2,…, xn)∈?n是种群中一个个体，基本的差分进化算法如下所述： ?在搜索空间中随机地初始化所有的个体。 ?重复如下操作直到满足终止条件（最大迭代数或者找到满足适应值的个体） o 对于种群中的每个个体： ●随机地从种群中选择三个彼此不同的个体a，b 和c。 ●选择一个随机索引R ∈{1, ..., n}，n 是被优化问题的维数。 ●通过对每个i ∈{1, ..., n}进行如下的迭代计算可能的新个体Y = [y1, ..., yn] 生成一 个随机数ri~U(0,1)； ●如果(i=R)或者(ri Immune(免疫)是从拉丁文Immunise衍生而来的。很早以前，人们就注意到传染病患者痊愈后，对该病有不同程度的免疫力。因此，在相当长时期内，免疫在微生物学和病毒学上是指免除瘟疫；换言之，是指对传染因子的再次感染有抵抗力，这是机体在初次感染后对该传染因子产生了免疫应答的结果。在医学上，免疫是指机体接触抗原性异物的一种生理反应。免疫系统有能力产生很多种抗体，免疫系统的控制机制可完成这一调节功能，即只产生所需数量的抗体。根据网络理论，如果任一细胞系中的细胞由于抗原的刺激而被激活并开始繁殖，其它能识别这种基因类型的细胞系也被激活并开始繁殖。这样，如果这一过程连续地进行，就构成了对自身的免疫，并且通过所有淋巴细胞的作用实现了调节机制。 基本免疫算法 基本免疫算法基于生物免疫系统基本机制，模仿了人体的免疫系统。基本免疫算法从体细胞理论和网络理论得到启发，实现了类似于生物免疫系统的抗原识别、细胞分化、记忆和自我调节的功能。如果将免疫算法与求解优化问题的一般搜索方法相比较，那么抗原、抗体、抗原和抗体之间的亲和性分别对应于优化问题的目标函数、优化解、解与目标函数的匹配程度。 通俗地说，抗原就是入侵人体的病原体，而人体内的免疫系统会相应地产生免疫应答，产生抗体。而其中B细胞和T细胞的重要作用： B 细胞的主要功能是产生抗体，且每个B细胞只产生一种抗体．免疫系统主要依靠抗体来对入侵抗原进行攻击以保护有机体．T细胞的主要功能是调节其它细胞的活动或直接对抗原实施攻击．成熟的B细胞产生于骨髓中，成熟的T细胞产生于胸腺之中。B细胞和T 细胞成熟之后进行克隆增殖、分化并表达功能．两种淋巴细胞共同作用并相互影响和控制对方功能，形成了机体内部高度规律的反馈型免疫网络． 对于不同的系统，你所要关注的量不同的话，人工免疫的应用也就有不同的意义． 比如说，我要应用到通过估计饭堂里吃饭的人数，来寻优哪个时间点是最好的吃饭点（人数较少，饭又比较多等条件），这是你可以先定义一个目标函数minf (x)+约束条件来作为抗原，而争对抗原的变量计算，可以产生很多抗体（就是许多种可以选择的情况），再通过判断抗原和抗体的亲和力（亲和力高表示这个抗体是比较好的），和抗体之间的排斥力（相似度，相似度高的两个可以排除一个，使抗体多样化），再同通过交叉变异等操作来更新抗体，一直循环到满足一定条件就可以退出循环。 免疫的机理是具有特定性的，最可以说明问题的就是种牛痘只能防止天花，他不可能产生免疫防止肝炎。并且多目标优化多是互相矛盾的，没有又想让马儿跑还想让马儿不吃草的好事情。解决优化最简单的是图论中著名的柯尼斯堡七桥问题和欧拉示性一笔画方法。再就是优选法的0.618黄金分割和QC的质量控制方法。免疫算法是基于生物免疫学抗体克隆的选择学说，而提出的一种新人工免疫系统算法-免疫克隆选择算法ICSA（Immune Clonal Selection Algorithm），ICSA算法具有自组选择学习、全息容错记忆、辩证克隆仿真和协同免疫优化的启发式人工智能。由于该方法收敛速度快，求解精度高，稳定性能好，并有效克服了早熟和骗的问题，成为新兴的实用智能算法。 基本差分进化算法 (1)初始化。 DE 利用NP 个维数为D 的实数值参数向量作为每一代的种群，每个个体表示为： X i ，G (i=1，2，……，NP) （1） 式中：i —— 个体在种群中的序列；G ——进化代数；NP — —种群规模，在最小化过程中NP 保持不变。 为了建立优化搜索的初始点，种群必须被初始化。通常寻找初始种群的一个方法是从给定边界约束内的值中随机选择。在DE 研究中，一般假定对所有随机初始化种群均符合均匀概率分布。设参数变量的界限为 )( )( U j j L j X X X << ，则： )( )( )( 0,)()`1,0(L j L j U j ji X X X rand X +-?= （i=1，2，……， NP ；j=1，3，……，D ） （2） 式中：rand[0，1]——在[0，1]之间产生的均匀随机数。 如果预先可以得到问题的初步解，初始种群也可以通过对初步解加入正态分布随机偏差来产生，这样可以提高重建效果。 (2)变异。 对于每个目标向量 X i ，G (i=1，2，……，NP)，基本DE 算法的变 异向量如下产生： )(,3,2,11,G r G r G r G i x x F X v -?+=+ （3） 其中，随机选择的序号r1，r2和r3互不相同，且r1，r2和r3与目标向 量序号i 也应不同，所以须满足NP ≥4。变异算子F ∈[0，2]是一个实常数因数，控制偏差变量的放大作用。 (3)交叉。 为了增加干扰参数向量的多样性，引入交叉操作。则试验向量变为： ),...,,(1,1,21,11,++++=G Di G i G i G i u u u u （4） ???=+++1 ,1,1,G ji G ji G ji X v u )(rnb CR (j) b rand rnbr(i))(rand i r j j CR j b ≠>=≤且如果或者如果 （i=1，2，……，NP ；j=1，3，……，D ） （5） 式中：randb(j)——产生[0，1]之间随机数发生器的第j 个估计值；rnbr(i)∈ 1，2，? ，D ——一选择的序列，用它来确保1,+G i u 至少从1,+G i u ;获得一个参数；CR ——交叉算子，取值范围为[0，1]。 (4)选择。 为决定试验向量1,+G i u ，是否会成为下一代中的成员，DE 按照贪婪 准则将试验向量与当前种群中的目标向量进行比较。如果目标函数要被最小化，那么具有较小目标函数值的向量将在下一代种群中赢得一席地位。下一代中的所有个体都比当前种群的对应个体更佳或者至少一样好。注意在DE 选择程序中试验向量只与一个个体相比较，而不是与现有种群中的所有个体相比较。 (5)边界条件的处理。 在有边界约束的问题中，确保产生新个体的参数值位于问题的可行域中是必要的，一个简单方法是将不符合边界约束的新个体用在可行域中随机产生的参数向量代替。 第五章人工免疫算法习题与答案 1. 填空题 （1）人工免疫算法的缩写是，它是对的一种模拟。判别优劣的适应度函数这里称为。 （2）利用生物免疫系统的某一方面原理就可以设计新算法，因此人工免疫算法是多个算法的统称，其中最具代表性的算法有、 和。 解释： 本题考查人工免疫算法的基础知识。 具体内容请参考课堂视频“第5章人工免疫算法”及其课件。 答案： （1）AIA，生物免疫机理，亲和度 （2）否定选择算法、免疫规划算法、克隆选择算法 2.给出人工免疫算法的定义，并指出其特征。 解释： 本题考查人工免疫算法的定义和特点。 具体内容请参考课堂视频“第5章人工免疫算法”及其课件。 答案： 人工免疫算法是基于免疫学理论和生物免疫系统机制而提出的计算智能算法，是对生物免疫机理的一种模拟，并受到遗传算法的启发，因此免疫算法与遗传算法有许多相似之处。 AIS算法具有以下特征： （1）具有全局搜索能力。 （2）具有多样性保持机制。 （3）鲁棒性强。 （4）具有并行分布式搜索机制。 3.关于人工免疫算法，下面说法错误的是（）。 A）人工免疫算法是一种全局搜索优化方法。 B）抗原对应着优化问题的可行解。 C）免疫操作可以用于产生新的解。 D）优化问题的寻优过程实际上是免疫系统识别抗原并实现抗体进化的过程。解释： 本题考查人工免疫算法的特点。 具体内容请参考课堂视频“第5章人工免疫算法”及其课件。 答案：B （1）生物免疫系统运用多种免疫调节机制产生多样性抗体以识别、匹配并最终消灭外界抗原，免疫应答中的抗体更新过程是一个全局搜索的进化过程，A 选项正确。 （2）抗原对应着问题，抗体对应着优化问题的可行解，B选项错误。 （3）免疫操作中克隆变异、抗体补充等可以产生新的抗体，对应着新解产生的过程，C选项正确。 （4）优化问题的寻优过程对应着免疫系统识别抗原并实现抗体进化的过程，D选项正确。 4.试写出克隆选择算法的基本流程。 解释： 本题考查克隆选择算法CSA的步骤。 具体内容请参考课堂视频“第5章人工免疫算法”及其课件。 答案： 步骤1：初始化。随机产生N个抗体对应问题的可能解，作为初始种群。 步骤2：克隆选择操作。第一次评价和选择，计算种群抗体的亲和度函数， 差分进化算法的算法设计研究 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。而作为一种优化算法，差分进化算法因其有效性，在现代优化技术和工程实践应用中的作用越来越凸显。阐述了差分进化算法的基本概念，对差分简化算法的原理进行了介绍，对算法步骤进行了论述，并结合一物流配送路径优化例子，重点围绕该算法的设计进行分析，为差分进化算法的应用提供了思路。 标签：差分进化算法；算法设计；应用 0 引言 差分进化算法（Differential Evolution ，DE）是一种新兴的进化计算技术。它是由R.Storn 和K.Price于1995 年提出的，最初的设想是用于解决切比雪夫多项式问题，后来发现DE 也是解决复杂优化问题的有效技术。DE 特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。近年来，DE 已经在许多领域得到了应用，譬如人工神经元网络、化工、电力、机械设计、信号处理、路径优化等。 1 差分进化算法概述 1.1 概念 差分进化算法是一种强调在全局中寻找最优解的技术，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法，是一种以“适者生存”的理念来进行“优胜劣汰”的智能型算法，同时，差分进化算法在对问题的求解过程中采用了并行搜索的实现方式，通过该方式，大大减少了对问题求解过程中所需要的时间。差分进化算法通过非常简单的算法结构，趋于智能化的适应条件判断来进行新一代种群的生成，并最终通过适应条件判断来选出全局的最优方案。 1.2 优点 差分进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而且在大多数情况下都能得到比较满意的有效解。它对问题的整个参数空间给出一种编码方案，而不是直接对问题的具体参数进行处理，不是从某个单一的初始点开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。 2 差分进化算法的原理 免疫算法理论与应用近代免疫的概念是指机体对自己或非己的识别并排除非己的功能，目的是维持自身生理平衡与稳定.免疫算法就是模拟免疫系统抗原识别、抗原与抗体结合及抗体产生过程，并利用免疫系统多样性和记忆机理抽象得到的一种免疫算法。这里介绍免疫算法的算法流程与代码.免疫学中基本概念的思想在免疫算法设计中得到有效应用，即亲和力，相似度，浓度及激励度,根据算法需要给出描述. 定义1 亲和力指抗体与抗原的匹配程度.反映在优化问题上，抗体（NBP）的亲和力定义为函数，与成反比，在此仍表示抗 (x)f(x)f(x)x体对应的可行解的目标函数.这里选 择 1 定义2 相似度指抗体 与其他抗体的相似程度，其被定义为，此根据信息熵理论设计.设M为含有m个字符的字符集，群体G为由N个长度为的字符串构成的集合，即l，其中G中基因座的信息熵定义为其中为M 中第个符号出现在基因座上的概率p ij定义3 抗体浓度指抗体在抗体群中与其相似的抗体所占的比例，定义为函数即 ，其中为 浓度阈值，，在此称为浓度抑制半径. 定义 4 激励度是指抗体应答抗原和被其他抗体激活的综合能力，定义为函 e 数，其中为调节因子，.抗体应答 抗原综合能力与其亲和力成正比，与其在抗体群中浓度成反比定义 5 克隆选择是 指在给定的选择率下，，在抗体群中选择亲和力较高的抗体.亲和力低的抗体则被清除. 定义6 细胞克隆是指在给定 的繁殖数M下，抗体群X中所有抗体依据自 s2身的亲和力及繁殖率共繁殖M个克隆的映射.，它是确定性映射，即设为抗体群的繁殖率函数，为抗体群，则定义x抗体繁殖个相同的克隆构成的集合. 由下式确定： mmiiim . 定义 7 亲和突变是指抗体空间到自身的随机映射，，其作用方式:S T m是抗体按与其亲和力成正比的可变概率独立地改变自身的基因，可选 . 定义 8 克隆抑制指在抗体群中依据抗体的亲和力和相似度抑制部分抗体的确定性映射,.克隆抑制算子的设计，设X是群体规模为M的抗体群，依据抗体的相似度和抑制半径以及式，将X划分为子群，不妨设获q个子群，利用处罚函数对中亲和力低的抗体进行处罚. 定义9 免疫选择是指在抗体群中依据抗体的激励度选择抗体的随机映射，N按其概率 规则 . x(X)ii j定义 10 募集 差分进化算法- 入门 基本差分进化算法 1基本差分进化算法的基本思想 DE算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解 有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法米用二进制编码，而差分进化算法米用实数编码。 2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2差分进化算法的基本操作 设当前进化代数为t，群体规模为NP，空间维数为D，当前种群为X（t） x ；,x ；,川,X N P ，x ； x i t 1,x i t 2^|,x i t D 为种群中的第i 个个体。在进化过程 中，对于每个个体x ：依次进行下面三种操作。 2.1变异操作 对于每个个体X ：按下式产生变异个体V “1,也,|||"；）丁，则 V ： ￡j F （x ；j 心）j 1,2,|||,D （1） 其中 x ：阳乂2」||凡）丁，X ； （乂21公；22,|||心）丁 和 x r 3 （X ：31,X ；32,|||,X ；3D ）T 是群 体中随机选择的三个个体，并且r 1 r 2 r 3 i ； xj j ，x ；j 和x ；3 j 分别为个体口，r 2 和r 3的第j 维分量；F 为变异因子，一般取值于［0,2］。这样就得到了变异个体V ；。 2.2交叉操作 由变异个体V 和父代个体X ：得到试验个体u ： (u 1 U i t 2^|,U i t D )T ，则 v ： if ran d[0 1] CR or j j_rand X ； if ra nd[0 1] CR and j j_rand 其中，rand ［0,1］是［0,1 ］间的随机数；CR 是范围在［0,1 ］间的常数，称为交叉因子, CR 值越大，发生交叉的可能性就越大；j_rand 是在［1,D ］随机选择的一整数， 它保证了对于试验个体u t 至少要从变异个体v ；中获得一个元素。以上的变异操 作和交叉操作统称为繁殖操作。 2.3选择操作 差分进化算法采用的是“贪婪”选择策略，即从父代个体x t 和试验个体u t 中 选 择一个适应度值最好的作为下一代的个体 x t+1 ，选择操作为： t 1 X ： if fit ness (X ：) fit ness(u ：) x t ⑶ u i otherwise 其中，fitness()为适应度函数，一般以所要优化的目标函数为适应度函数。本 文的适应度函数如无特殊说明均为目标函数且为求函数极小值。 t U j基于Matlab的人工免疫算法
基本差分进化算法
差分进化算法介绍
人工免疫系统及其算法综述
免疫算法
差分进化算法-入门
差分进化算法-入门
差分进化算法综述概况
人工免疫算法介绍
基本差分进化算法
05第五章 人工免疫算法
差分进化算法的算法设计研究
免疫算法
差分进化算法-入门
相关主题
文本预览