免疫算法

免疫算法理论与应用近代免疫的概念是指机体对自己或非己的识别并排除非己的功能，目的是维持自身生理平衡与稳定.免疫算法就是模拟免疫系统抗原识别、抗原与抗体结合及抗体产生过程，并利用免疫系统多样性和记忆机理抽象得到的一种免疫算法。

这里介绍免疫算法的算法流程与代码.免疫学中基本概念的思想在免疫算法设计中得到有效应用，即亲和力，相似度，浓度及激励度,根据算法需要给出描述. 定义1 亲和力指抗体与抗原的匹配程度.反映在优化问题上，抗体（NBP）的亲和力定义为函数，与成反比，在此仍表示抗aff:S(0,1)aff(x)f(x)f(x)x体对应的可行解的目标函数.这里选择 1aff(x),0 1 . f(x)1e定义2 相似度指抗体与其他抗体的相似程度，其被定义为，此根据信息熵理论设计.设M为含有m个字符的字符集，群Aff:S S[0,1]体G为由N个长度为的字符串构成的集合，即l，其中G中基因座的信息熵定义为jG{X...,M,1i l}xxxx12lim其中为M中第个符号出现在基因座上的概率. ,ij log(G,N)p pp Hj ij ijiji1定义3 抗体浓度指抗体在抗体群中与其相似的抗体所占的比例，定义为函数即C:X S[0,1],{X|Aff(u,)}C(u)，其中为浓度阈值，，在此称为浓度抑01N制半径. 定义 4 激励度是指抗体应答抗原和被其他抗体激活的综合能力，定义为函c(x)/e数，其中为调节因子，.抗体应答1act:X S,act(x)aff(x)抗原综合能力与其亲和力成正比，与其在抗体群中浓度成反比. 定义5 克隆选择是指在给定的选择率下，，在抗体群中选择亲01和力较高的抗体.亲和力低的抗体则被清除. 定义 6 细胞克隆是指在给定的繁殖数M下，抗体群X中所有抗体依据自s2身的亲和力及繁殖率共繁殖M个克隆的映射.，它是确定性映射，:X S Tcmxxxs即设为抗体群的繁殖率函数，为抗体群，则定义X{,,...,}r:12m x抗体繁殖个相同的克隆构成的集合. 由下式确定：mmiiim . N r(X)af(f),Mmxmiiii1定义 7 亲和突变是指抗体空间到自身的随机映射，，其作用方式:S S T m是抗体按与其亲和力成正比的可变概率独立地改变自身的基因，可选 . P(x)exp(aff(x))定义 8 克隆抑制指在抗体群中依据抗体的亲和力和相似度抑制部分抗体的确定性映射,.克隆抑制算子的设计，设X是群体规模为M的抗体群，:SMSTr依据抗体的相似度和抑制半径以及式，将X划分为子群，不妨设Aff(u,)获q个子群，利用处罚函数对中亲和力低的抗体进行处罚. ,1i qPPii定义9 免疫选择是指在抗体群中依据抗体的激励度选择抗体的随机映射，N按其概率规则:S,STisact()xiP{T} . x(X)ii act()xjx X j定义 10 募集新成员指在抗体空间S中随机选择抗体. 免疫算法描述如下： Step 1 确定初始群体规模N，克隆总数M，克隆选择率，抑制半径，募集新成员插入率，. M N Step 2 随机产生N个抗体构成初始抗体群，计算中抗体亲和力. AA00 Step 3 利用克隆选择算子在中选择个抗体构成群体. NABnn1 Step 4 克隆选择算子作用繁殖M个克隆，中抗体进入记忆池，并更BBnn新记忆池中亲和力低的抗体. Step 5 依据亲和突变算子对每个克隆细胞进行突变，获得克隆集.Cn* Step 6 克隆抑制算子作用于，获得克隆集C C nn* Step 7 计算与中亲和力较高的N个抗体的激励度.用比例选择选取CAnn个抗体.其中中亲和力最高的不参与选择.获得新群体. N round(N)1ADnnStep 8 由募集新成员算子任选个自我抗体插入，并计算round(N)Dn个抗体的亲和力，从而获得. round(N)An1 Step 9 若满足终止条件，输出结果，否则，返回step 3. 免疫算法在函数优化中应用举例例Rosebrock函数的全局最大值计算. 222max )(1)f(,)100(xxxxx21121s..t8 2.0i48(1 2.04x 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 ,(i1,2) 4.0962.048i i1023求函数的全局最大值免疫算法代码如下：Rosebrock #include <stdio.h>#include<stdlib.h> #include<time.h>#include<math.h> #define LENGTH1 10#define LENGTH2 10 #define CHROMLENGTH LENGTH1+LENGTH2 #define POPSIZE 300 int MaxGeneration =500; struct individual { char chrom[CHROMLENGTH+1]; ;//适应度double value ;//亲和力double affective //浓度double concentration; //激励度double activity;}; int generation; int best_index; structindividual 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 individualarray[],int n); void clonenum(); void MutationOperator(void);void GenerateNextPopulation(void); double CalculateSimilarity(struct individual A,struct individual B); voidInhibition(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(); voidOutputTextReport();//******************************************************************** void main() { generation=0; GenerateInitialPopulation(); EvaluatePopulation(); while(generation<MaxGeneration) { generation++; GenerateNextPopulation(); EvaluatePopulation(); PerformEvolution(); OutputTextReport(); } }//********************************************************************void GenerateInitialPopulation() { int i,j; srand((unsigned)time(NULL)); //srand((unsigned)time(0));for(i=0;i<PopSize ;i++) { for(j=0;j<CHROMLENGTH;j++) { population[i].chrom[j]=(rand()%10<5)?'0':'1'; } population[i].chrom[CHROMLENGTH]='\0'; } }//******************************************************************** 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<length;i++,pointer++){ decimal+=(*pointer-'0')<<(length-1-i); } return(decimal); } //***************************************************************************** void CalculateObjectValue(struct individual array[],int n) { int i; long temp1,temp2; double x1,x2; for (i=0;i<n;i++){ temp1=DecodeChromosome(array[i].chrom,0,LENGTH1); temp2=DecodeChromosome(array[i].chrom,LENGTH1,LENGTH2 ); 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<n;i++) { array[i].affective=1.0/(exp(-(r*array[i].value))+1.0); } } //***************************************************************************** void affectivesort(struct individual array[],int n) { int i,j; struct individual a; for(j=0;j<n-1;j++){ for(i=0;i<n-1-j;i++){ if(array[i].affective<array[i+1].affective) { a=array[i+1];array[i+1]=array[i]; array[i]=a; } } } }//****************************************************************** void FindBestIndividual() { int i; bestindividual=population[0]; for(i=0;i<PopSize;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; doublesg =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<m[i];j++)nextpopulation[L++]=array[i]; } }//***************************************************************************** void MutationOperator(void) { int i,j; doublep,po; for(i=0;i<clone_total;i++){ for(j=0;j<CHROMLENGTH;j++) { po=rand()%1000/1000.0; p=exp((-1)*nextpopulation[i].affective); if(po<p) { nextpopulation[i].chrom[j]=(nextpopulation[i].chrom[j]=='0')?'1':'0'; } } } }//***************************************************************************** double CalculateSimilarity (struct individual A,struct individual B) { int j=0; double sum=0.0; for(j=0;j<CHROMLENGTH;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<clone_total-1;i++) { for(j=i+1;j<clone_total;j++){ if(CalculateSimilarity(nextpopulation[i],nextpopulation[j])>ra d) { nextpopulation[++L]=nextpopulation[j]; } } clone_total=L+1;L=i+1; } clone_total=L+1; } //***************************************************************************** void chongzu() { int i; for(i=0;i<clone_total;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<n;i++) { for(j=0;j<n;j++) { m+=(CalculateSimilarity(population[i],population[j])<rad )?1:0; } } population[i].concentration=m*(1.0)/(n); } //***************************************************************************** void CalculateActivityValue(struct individual population[],int n) { int i; double h=1.5; for(i=0;i<n;i++) { population[i].activity=population[i].affective*exp(-population[i].concentration/h); } } //***************************************************************************** void activeslect() { int i,index; double umu=0.08; int N3=(int)(PopSize*umu); double p;double sum2=0.0; double concent[POPSIZE]; struct individual con_population[POPSIZE]; CalculateConcentrationValue(population,PopSize); CalculateActivityValue(population,PopSize);for(i=0;i<PopSize;i++) { sum2+=population[i].activity; } for(i=0;i<PopSize;i++){ concent[i]=population[i].activity/sum2; } for(i=1;i<PopSize;i++) { concent[i]=concent[i-1]+concent[i]; } for(i=0;i<PopSize;i++) { p=rand()%1000/1000.0; index=0; while (p>concent[index]) { index++; } con_population[i]=population[index]; } for(i=0;i<PopSize-N3;i++){ population[i]=con_population[i]; } } //***************************************************************************** void sortnewmember() { int i,j; intN3=(int)(PopSize*umu); for(i=0;i<N3;i++) { for(j=0;j<CHROMLENGTH;j++) { population[i+PopSize-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<CHROMLENGTH;i++) { printf("%c",currentbest.chrom[i]); } printf("\n"); } 运行结果为：所以该问题全局最优解为. f( 2.048,2.048)3905.926227参考文献[1] 黄席樾，张著洪等.现代智能算法理论及应用.北京科学出版社，2005. [2] 周明.遗传算法原理及其应用.国防工业出版社，2002.202.。