免疫算法理论与应用近代免疫的概念是指机体对自己或非己的识别并排除非己的功能，目的是维持自身生理平衡与稳定.免疫算法就是模拟免疫系统抗原识别、抗原与抗体结合及抗体产生过程，并利用免疫系统多样性和记忆机理抽象得到的一种免疫算法。
这里介绍免疫算法的算法流程与代码.免疫学中基本概念的思想在免疫算法设计中得到有效应用，即亲和力，相似度，浓度及激励度,根据算法需要给出描述.定义1 亲和力指抗体与抗原的匹配程度.反映在优化问题（NBP ）上，抗体的亲和力定义为函数:(0,1)aff S →，()aff x 与()f x 成反比，在此()f x 仍表示抗体x 对应的可行解的目标函数.这里选择()1(),011f x aff x eηη⋅=<<+.定义2 相似度指抗体与其他抗体的相似程度，其被定义为:[0,1]Aff S S ⨯→，此根据信息熵理论设计.设M 为含有m 个字符的字符集，群体G 为由N 个长度为l 的字符串构成的集合，即12{...,,1}l i G X M i l x x x x ==∈≤≤，其中G 中基因座j 的信息熵定义为1(,)l o g mj i j i ji G N p p H ==-∑,其中ij p 为M 中第i 个符号出现在基因座j 上的概率. 定义 3 抗体浓度指抗体在抗体群中与其相似的抗体所占的比例，定义为函数:[0,1],C X S ⊂→即{|(,)}()X Aff u C u Nυυσ∈≤=，其中σ为浓度阈值，01σ≤≤，在此称为浓度抑制半径.定义 4 激励度是指抗体应答抗原和被其他抗体激活的综合能力，定义为函数()/:,()()c x act X S act x aff x eβ-+⊂→=⋅ ，其中β为调节因子，1β≥.抗体应答抗原综合能力与其亲和力成正比，与其在抗体群中浓度成反比.定义 5 克隆选择是指在给定的选择率α下，01α<<，在抗体群中选择亲和力较高的抗体.亲和力低的抗体则被清除.定义 6 细胞克隆是指在给定的繁殖数M 下，抗体群X 中所有抗体依据自身的亲和力及繁殖率共繁殖M 个克隆的映射.:2sc T X S ⊂→，它是确定性映射，即设:mr s +→ 为抗体群的繁殖率函数，12{,,...,}m X x x x =为抗体群，则定义抗体i x 繁殖i m 个相同的克隆构成的集合. i m 由下式确定：1()(),mi i i i N r X a f f Mm x m ==⋅⋅=∑. 定义 7 亲和突变是指抗体空间到自身的随机映射，:m T S S →，其作用方式是抗体按与其亲和力成正比的可变概率独立地改变自身的基因，可选()e x p (())P x a f f x =-. 定义 8 克隆抑制指在抗体群中依据抗体的亲和力和相似度抑制部分抗体的确定性映射,:M r S T S →.克隆抑制算子的设计，设X 是群体规模为M 的抗体群，依据抗体的相似度和抑制半径σ以及式(,)Aff u υσ<，将X 划分为子群，不妨设获q 个子群,1i i q P ≤≤，利用处罚函数对i P 中亲和力低的抗体进行处罚. 定义 9 免疫选择是指在抗体群中依据抗体的激励度选择抗体的随机映射，:,Nis S S T →按其概率规则()(){}()ji X i i j Xx x x xact P T act ∈==∑.定义 10 募集新成员指在抗体空间S 中随机选择抗体. 免疫算法描述如下：Step 1 确定初始群体规模N ，克隆总数M ，克隆选择率α，抑制半径σ，募集新成员插入率μ，M N α>.Step 2 随机产生N 个抗体构成初始抗体群0A ，计算0A 中抗体亲和力. Step 3 利用克隆选择算子在n A 中选择1N 个抗体构成群体n B .Step 4 克隆选择算子作用n B 繁殖M 个克隆，n B 中抗体进入记忆池，并更新记忆池中亲和力低的抗体.Step 5 依据亲和突变算子对每个克隆细胞进行突变，获得克隆集n C . Step 6 克隆抑制算子作用于n C ，获得克隆集*n CStep 7 计算n A 与*n C 中亲和力较高的N 个抗体的激励度.用比例选择选取()1N round N μ-⋅-个抗体.其中n A 中亲和力最高的不参与选择.获得新群体n D .Step 8 由募集新成员算子任选()round N μ⋅个自我抗体插入n D ，并计算()round N μ⋅个抗体的亲和力，从而获得1n A +.Step 9 若满足终止条件，输出结果，否则，返回step 3. 免疫算法在函数优化中应用举例 例 Rosebrock 函数的全局最大值计算.max 22212121(,)100()(1)f x x x x x =⋅-+- ..s t 2.048 2.048(1i i x -≤≤= 确定编码方法：用长度为10的二进制编码串来分别表示俩个决策变量12,x x .10位二进制编码串可以表示从0到1023之间的1024个数，故将12,x x 的定义域离散化为1023个均等的区域，包括俩端点共1024个不同的离散点.从离散点-2.048到2.048，依次让它们对应于00000000000（0）到11111111111（1023）之间的二进制编码.再将分别表示12,x x 的两个10位长的二进制编码串接在一起，组成一个20位长的二进制编码，它就构成了函数优化问题的染色体编码方法.使用这种编码方法，解空间与免疫算法的搜索空间具有一一对应的关系. 确定解码方法：解码时需将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换成对应的十进制整数代码，分别记为1y 和2y . 依据前述个体编码方法和对定义域的离散化方法可知，将代码i y 转换为i x 的解码公式为：4.096 2.0481023ii yx =⨯-, (1,2)i = 求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 300int MaxGeneration =500;struct individual{char chrom[CHROMLENGTH+1];double value;//适应度double affective;//亲和力double concentration;//浓度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 CalculateObjectV alue(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<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 CalculateObjectV alue(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;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<m[i];j++)nextpopulation[L++]=array[i];}}//***************************************************************************** void MutationOperator(void){int i,j;double p,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])>rad){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];CalculateConcentrationV alue(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;int N3=(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");}运行结果为：所以该问题全局最优解为( 2.048,2.048)3905.926227f-=.参考文献[1] 黄席樾，张著洪等.现代智能算法理论及应用.北京科学出版社，2005.[2] 周明.遗传算法原理及其应用.国防工业出版社，2002.202.。
