免疫算法解子集和问题
%这是免疫算法用于计算子集和的主程序。%免疫算法是遗传算法的变体，一般说来它不用杂交，而是采用注入疫苗的方法。
%疫苗是优秀染色体中的一段基因，把疫苗接种到其它染色体中
%但对于本程序还需要杂交。
%子集和问题：
%设有正整数集合S，正整数t,从S中找到一个子集S'，使
%min
t-(s'1+s'2+...s'm)
% s.t. t-(s'1+s'2+...s'm)>=0
%主程序运行过程
%1
初始化
%2 随机生成初始可能解：染色体
%3 判定染色是不是解，如果是解，给出结果，结束程序
%4 选择最好解对应的最优染色体
%5
把保留的最好的染色体holdBestChromosome加入到染色体群中
%6 评价可能解，即评价染色体
%7 给染色体赋概率
%8
染色体杂交，产生子代染色体
%9 从最好的染色体上截取基因片断做疫苗，注射到其它子代染色体中
%10 染色体变异：对子代染色修改
%11
到3
%这是免疫算法的主程序，它需要调用的函数如下。
%接种疫苗函数：
%function
inoculateChromosome=immunity(chromosomeGroup,bacterinChromosome,parameter)
%parameter:1,随机选取染色体接种。2，每个染色体都接种。3，每个染色体都接种，但接种的位置是随机的
%这个函数实现对染色体的疫苗接种
%计算误差函数
%chromosomeError=subsetError(chromosomeGroup,S,t)
%选择最优染色体函数：
%=best_worstChromosome(fatherChromosomeGroup,functionError);
%误差比较函数：从两个染色体中，选出误差较小的染色体
%...
%
=compareBestChromosome(holdBestChromosome,holdLeastFunctionError,...
%
bestChromosome,leastFuntionError)
%为染色体定义概率函数，好的染色体概率高，坏染色体概率低
%p=chromosomeProbability(functionError);
%按概率选择染色体函数：
%slecteChromosomeGroup=selecteChromome(fatherChromosomeGroup,p);
%父代染色体杂交产生子代染色体函数
%sonChrmosomeGroup=crossChromosome(slecteChromosomeGroup,2);
%变异函数
%fatherChromosomeGroup=varianceCh(sonChromosomeGroup,0.8,solutionN);
%通过实验有如下结果：
%1。染色体应当多一些
%2。通过概率选择染色体，在迭代早期会有效选出优秀的染色体，使解的误差迅速降低，
%但随着迭代的进行，概率选择也会导致某种染色体在基因池中迅速增加，使染色体趋同，
%这就减少了物种的多样性，反而难以逼近解
%3。不用概率选择，仅采用染色体杂交，采用保留优秀染色体，也可以得到解
%4。单纯免疫效果不好，杂交+免疫效果比较好
%%%%%%%%%%%%%%%%%%%%%%%%程序开始运行
clear,clc;%清理内存，清屏
circleN=500;%迭代次数
format
long
%%%%%%%%%%%%%%%%1:程序初始化
chromosomeGroupN=50;%染色体的个数
subsetSum=30;%集合S中的整数个数
%随机产生正整数集S，正整数t
=subset(subsetSum)
presision=10;
%%%%%%%%%%%%%%%2:随机生成初始可能解：染色体
%随机产生一组染色体
fatherChromosomeGroup=round(rand(chromosomeGroupN,subsetSum));
holdLeastChromosomeError=Inf;%可能解的最小误差的初值
holdBestChromosome=0;%对应最小误差的染色体的初值
%%%%%%%%%%%%%%%%%%开始计算
compute=1;
circle=0;
while
compute%开始迭代求解
%%%%%%%%%%%%%%%%%%3: 判定染色是不是解，如果是解，给出结果，结束程序
chromosomeError=subsetError(fatherChromosomeGroup,S,t);%计算染色体与t的误差
...
=isSolutionSubsetSum(fatherChromosomeGroup,chromosomeError,presision);
%isSolutionSubsetSum函数根据误差functionError判定方程是否已经解开，isTrue=1,方程得解。solution是方程的解
if
isTrue==1
'子集和问题得解'
solution
minError
return%结束程序
end
%%%%%%%%%%%%%4：选择最好解对应的最优染色体
=best_worstChromosome(fatherChromosomeGroup,chromosomeError);
%%%%%%%%%%%%%5：保留每次迭代产生的最好的染色体
%本次最好解与上次最好解进行比较，如果上次最好解优于本次最好解，保留上次最好解；
%反之，保留本次最好解。保留的最好染色体放在holdBestChromosome中
...
=compareBestChromosome(holdBestChromosome,holdLeastChromosomeError,...
bestChromosome,leastChromosomeError);
circle=circle+1
holdLeastChromosomeError%显示每一次循环的染色体最小误差
if
circle>circleN
return
end
%%%%%%%%%%%%%%5:把保留的最好的染色体holdBestChromosome加入到染色体群中
order=round(rand(1)*chromosomeGroupN);
if
order==0
order=1;
end
fatherChromosomeGroup(order,:)=holdBestChromosome;
chromosomeError(order)=holdLeastChromosomeError;
%%%%%%%%%%%%%%%6:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)
%%%%%%%%%%%%%%%好的染色体概率高，坏的概率低。依据误差functionError计算概率
=chromosomeProbability(chromosomeError);
if
trueP
=='Fail'
'可能解严重不适应方程，请重新开始'
return%结束程序
end
%%%%%%%%%%%%%%%7：按照概率筛选染色体(关键步骤)
%从父染体中选择优秀染色体
selecteChromosomeGroup=selecteChromosome(fatherChromosomeGroup,p);
%%%%%%%%%%%%%%%8：染色体杂交(关键步骤)
%sle=bin2dec(selecteChromosomeGroup)%显示选择出来的解的序号(染色体)
%用概率筛选出的染色体selecteChromosomeGroup进行杂交，产生子代染色体
sonChromosomeGroup=crossChromosome(selecteChromosomeGroup,2);
%不用概率筛选出的染色体selecteChromosomeGroup进行杂交，而直接用上一代(父代)的
%sonChromosomeGroup=crossChromosome(fatherChromosomeGroup,2);
%sonChromosomeGroup=immunity(fatherChromosomeGroup,holdBestChromosome,3);
%把疫苗接种到其它染色体中
sonChromosomeGroup=immunity(sonChromosomeGroup,holdBestChromosome,3);
%cro=bin2dec(sonChromosomeGroup)%显示杂交后的子代染色体
%%%%%%%%%%%%%%%9：变异
%不杂交直接变异
%fatherChromosomeGroup=varianceCh(fatherChromosomeGroup,0.1,solutionN);
%杂交后变异
fatherChromosomeGroup=varianceCh(sonChromosomeGroup,0.5);
end 函数(1)：接种疫苗函数：
%function
inoculateChromosome=immunity(chromosomeGroup,bacterinChromosome,parameter)
%parameter:1,随机选取染色体接种。2，每个染色体都接种。3，每个染色体都接种，但接种的位置是随机的
%这个函数实现对染色体的疫苗接种
%chromosomeGroup:染色体组
%bachterinChromosome:疫苗染色体，即最好的染色体。从这个染色体上取疫苗
%parameter:接种疫苗的参数，即用什么方法接种
%inoculateChromosome:接种疫苗后的染色体
function
inoculateChromosome=immunity(chromosomeGroup,bacterinChromosome,parameter)
=size(chromosomeGroup);
=size(bacterinChromosome);
%chromosomeGroupSum:染色体的条数；chromosomeLength：染色体的长度
switch
parameter
case 1%随机选择染色体进行接种
for
i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if
headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if
tailDot==0%防止出现0点位
tailDot=1;
end
if
tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%接种
randChromosomeSequence=round(rand(1)*chromosomeGroupSum);
%随机产生1条染色体的序号，对这条染色体进行接种
if
randChromosomeSequence==0%防止产生0序号
randChromosomeSequence=1;
end
inoculateChromosome(i,:)...%先把输入染色体传给输出
=chromosomeGroup(randChromosomeSequence,:);
%执行免疫，即从疫苗染色体上取出一段基因做疫苗，再注入到其它染色体中
inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
case
2 %所有染色体挨个接种
for
i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if
headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if
tailDot==0%防止出现0点位
tailDot=1;
end
if
tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%接种
inoculateChromosome(i,:)=chromosomeGroup(i,:);%先把输入染色体传给输出
%执行免疫，即从疫苗染色体上取出一段基因做疫苗，再注入到其它染色体中
inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
case
3 %接种位置是随机的
for
i=1:chromosomeGroupSum
%%%%%%%%%%%%从疫苗染色体上定位疫苗
headDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上左边的点位
if
headDot==0%防止出现0点位
headDot=1;
end
tailDot=fix(rand(1)*bacterinChromosomeLength);
%疫苗在染色体上右边的点位
if
tailDot==0%防止出现0点位
tailDot=1;
end
if
tailDot>headDot%防止右边的点位大于左边的点位
dot=headDot;
headDot=tailDot;
tailDot=dot;
end
%%%%%%%%%%%%%在染色体上随机定位接种位置
inoculateDot=fix(rand(1)*chromosomeLength);%随机选择染色体的接种点位
if
inoculateDot==0
inoculateDot=1;
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,inoculateDot:tailDot-headDot+1)...
=bacterinChromosome(1,headDot:tailDot);
elseif
inoculateDot<=headDot
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,inoculateDot:inoculateDot+tailDot-headDot)...
=bacterinChromosome(1,headDot:tailDot);
elseif
(chromosomeLength-inoculateDot)>=(tailDot-headDot)
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,inoculateDot:inoculateDot+tailDot-headDot)...
=bacterinChromosome(1,headDot:tailDot);
else
inoculateChromosome(i,:)=chromosomeGroup(i,:);
inoculateChromosome(i,headDot:tailDot)...
=bacterinChromosome(1,headDot:tailDot);
end
end
end 函数(2)：计算误差函数
%chromosomeError=subsetError(chromosomeGroup,S,t)
%计算染色体与t的差
%染色体是1-0串，
%1表示1所在位置的子集元素参与计算，
%0表示0所在位置的子集元素不参与计算，
function
chromosomeError=subsetError(chromosomeGroup,S,t)
=size(chromosomeGroup);%返回染色体的个数
for
i=1:chromosomeGroupSum
ge=0;
for
j=1:geneSum
ge=ge+chromosomeGroup(i,j)*S(j);
end
if
t-ge>=0
chromosomeError(i,1)=t-ge;
else
chromosomeError(i,1)=Inf;
end
end 函数(3)：选择最优染色体函数：
%=best_worstChromosome(fatherChromosomeGroup,functionError);
%找出最小误差所对应的最好染色体，最大误差所对应的最坏染色体
function
=best_worstChromosome(chromosomeGroup,functionError)
[leastFunctionError
minErrorOrder]=min(functionError);
%[maxFunctionError
maxErrorOrder]=max(functionError);
bestChromosome=chromosomeGroup(minErrorOrder,:);
%worstChromosome=chromosomeGroup(maxErrorOrder,:); 函数(4)：误差比较函数：从两个染色体中，选出误差较小的染色体
%...
%
=compareBestChromosome(holdBestChromosome,holdLeastFunctionError,...
%
bestChromosome,leastFuntionError)
%选择最好的基因保留下来
function
...
=compareBestChromosome(oldBestChromosome,oldLeastFunctionError,...
bestChromosome,leastFunctionError)
if
oldLeastFunctionError>leastFunctionError
newLeastFunctionError=leastFunctionError;
newBestChromosome=bestChromosome;
else
newLeastFunctionError=oldLeastFunctionError;
newBestChromosome=oldBestChromosome;
end 函数(5)：为染色体定义概率函数，好的染色体概率高，坏染色体概率低
%p=chromosomeProbability(functionError);
%根据待解的非线性函数的误差计算染色体的概率
function
=chromosomeProbability(x_Error)
InfN=sum(isinf(x_Error));%估计非线性方程计算的结果
NaNN=sum(isnan(x_Error));
if
NaNN>0
isP='Fail';
p=0;
return
else
isP='True';
errorReciprocal=1./x_Error;
sumReciprocal=sum(errorReciprocal);
p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
end 函数(6)：按概率选择染色体函数：
%slecteChromosomeGroup=selecteChromome(fatherChromosomeGroup,p);
function
chromosome=selecteChromosome(chromosomeGroup,p)
cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
=size(chromosomeGroup);
for
i=1:chromosomeSum%这个循环产生概率值
rN=rand(1);
if
rN==1
chromosome(i,:)=chromosomeGroup(chromosomeSum,:);
elseif (0<=rN)
&&
(rN<cumuP(1))
chromosome(i,:)=chromosomeGroup(1,:);%第1条染色体被选中
else
for
j=2:chromosomeSum%这个循环确定第1条以后的哪一条染色体被选中
if (cumuP(j-1)<=rN) &&
(rN<cumuP(j))
chromosome(i,:)=chromosomeGroup(j,:);
break
end
end
end
end 函数(7)：父代染色体杂交产生子代染色体函数
%sonChrmosomeGroup=crossChromosome(slecteChromosomeGroup,2);
function
sonChromosome=crossChromosome(fatherChromosome,parameter)
=size(fatherChromosome);
%chromosomeSum:染色体的条数；chromosomeLength：染色体的长度
switch
parameter
case 1%随机选择父染色体进行交叉重组
for
i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
randChromosomeSequence1=round(rand(1)*chromosomeSum);
%随机产生第1条染色体的序号
randChromosomeSequence2=round(rand(1)*chromosomeSum);
%随机产生第2条染色体的序号，这两条染色体要进行杂交
if
randChromosomeSequence1==0%防止产生0序号
randChromosomeSequence1=1;
end
if
randChromosomeSequence2==0%防止产生0序号
randChromosomeSequence2=1;
end
if
crossDot==0 ||
crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
else
%执行两条染色体的交叉
sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
%把父染色体整条传给子染色体
sonChromosome(i*2-1,crossDot:chromosomeLength)=...
fatherChromosome(randChromosomeSequence2,crossDot:chromosomeLength)
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(randChromosomeSequence1,crossDot:chromosomeLength)
end
end
case
2 %父染色体的第i号与第chromosomeSum+1-i号交叉
for
i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
if
crossDot==0 ||
crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(i,:);
sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
else
%执行两条染色体的交叉
sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
sonChromosome(i*2-1,crossDot:chromosomeLength)...
=fatherChromosome(chromosomeSum+1-i,crossDot:chromosomeLength);
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(i,crossDot:chromosomeLength);
end
end
case
3 %父染色体的第i号与第i+chromosomeSum/2号交叉
for
i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
if
crossDot==0 ||
crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(i,:);
sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
else
%执行两条染色体的交叉
sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
sonChromosome(i*2-1,crossDot:chromosomeLength)...
=fatherChromosome(i+chromosomeSum/2,crossDot:chromosomeLength);
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(i,crossDot:chromosomeLength);
end
end
end 函数(8)：变异函数
%fatherChromosomeGroup=varianceCh(sonChromosomeGroup,0.8,solutionN);
%基因变异.染色体群中的1/10变异。vR是变异概率。solutionN是解空间中全部可能解的个数
function
aberranceChromosomeGroup=varianceCh(chromosomeGroup,vR)
=size(chromosomeGroup);
if
chromosomeSum<10
N=1;
else
N=round(chromosomeSum/10);
end
if
rand(1)>vR %变异操作
for
i=1:N
chromosomeOrder=round(rand(1)*chromosomeSum);%产生变异染色体序号
if
chromosomeOrder==0
chromosomeOrder=1;
end
aberrancePosition=round(rand(1)*chromosomeLength);%产生变异位置
if
aberrancePosition==0
aberrancePosition=1;
end
if
chromosomeGroup(chromosomeOrder,aberrancePosition)==1
chromosomeGroup(chromosomeOrder,aberrancePosition)=0;%变异
else
chromosomeGroup(chromosomeOrder,aberrancePosition)=1;%变异
end
end
aberranceChromosomeGroup=chromosomeGroup;
else
aberranceChromosomeGroup=chromosomeGroup;
end
来自搜狐博客=〉人工智能
页:
[1]