遗传算法解集合覆盖问题

frogfish · 发表于 2007-7-3 22:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

%这是用遗传算法解集合覆盖问题的主程序
%集合覆盖是指：
%集合S={x1,x2,...,xn}
%S上有一个集合族F={F1,F2,...Fm},即S包含F,
%且F覆盖S，即F1UF2U...UFm=S
%从F中找到一个子集Fi,Fj...Fq，使下式成立
%min |Fi|+|Fj|+...+|Fq|
% s.t. FiUFjU...UFq=S
%主程序调用的函数有：
%构造子集函数constructSubset(setN,subsetSum)
%计算一条染色体中所有元素的总和，
%也就是这条染色体(所代表的子集组合)中所有元素的个数
%subsetSetSum=setSum(chromosomeGroup,F)
%判断染色体是否覆盖集合S
%isCover(chromosome,F,SS)
%评价染色的函数：
%valuation=appraisal(chromosomeGroup,F,SS)
%这个函数通过一条染色体中所有元素的个数与集合S元素个数的差
%评价染色体的好坏
%该函数调用
%subsetSetSum=setSum(chromosomeGroup,F)和
%isCover(chromosome,F,SS)。
%选择最优染色体函数：
%[bestChromosome,leastFunctionError]=best_worstChromosome
(fatherChromosomeGroup,functionError);
%误差比较函数：从两个染色体中，选出误差较小的染色体
%[holdBestChromosome,holdLeastFunctionError]...
% =compareBestChromosome
(holdBestChromosome,holdLeastFunctionError,...
% bestChromosome,leastFuntionError)
%为染色体定义概率函数，好的染色体概率高，坏染色体概率低
%p=subsetChromosomeProbability(functionError);
%按概率选择染色体函数：
%slecteChromosomeGroup=selecteChromome(fatherChromosomeGroup,p);
%父代染色体杂交产生子代染色体函数
%sonChrmosomeGroup=crossChromosome(slecteChromosomeGroup,2);
%变异函数
%fatherChromosomeGroup=subsetVarianceCh(sonChromosomeGroup,0.8);
%主程序运行过程
%1 初始化
%2 随机生成初始可能解：染色体
%3 判定染色是不是解，如果是解，给出结果，结束程序
%4 评价可能解，即评价染色体
%5 给染色体赋概率
%6 按概率选择染色体，同时把最好的染色体保留下来
%7 染色体杂交，产生子代染色体
%8 染色体变异：对子代染色修改
%9 到3
clear,clc
setN=30;%setN:集合S中的元素个数
SS=1:setN;
subsetSum=10;%subsetN:子集族F中的子集数
chromosomeGroupN=20;%染色体的条数
F=constructSubset(setN,subsetSum);%构造子集
solutionSumError=5;%染色体的冗余定为5，小于5，这条染色体是最小子集覆盖染
色体
circleN=50;
%构造一个解用来检查算法的有效性
F{3}=[1 2 3 4 5 6 7];
F{5}=[8 9 10 11 12 13 14 15];
F{6}=[16 17 18 19 20 21 22];
F{9}=[23 24 25 26 27 28 29 30];
%随机产生一组染色体
fatherChromosomeGroup=round(rand(chromosomeGroupN,subsetSum));
holdLeastFunctionError=Inf;%可能解的最小误差的初值
holdBestChromosome=0;%对应最小误差的染色体的初值
fatherChromosomeGroup(1,:)=[0 0 1 0 1 1 0 0 1 0];
%%%%%%%%%%%%%%%%%%开始计算
compute=1;
circle=0;
while compute%开始迭代求解
circle=circle+1;
if circle>circleN
compute=0;
holdBestChromosome
holdLeastFunctionError
functionError
fatherChromosomeGroup
end
%计算染色体的冗余：
%如果染色体不能覆盖S，冗余=无穷大Inf
%反之冗余=染色体中所有元素个数的总和-S中所有元素的个数
functionError=appraisal(fatherChromosomeGroup,F,SS);
%%%%%%%%%%%%%2: 根据冗余判定是否是最小集合覆盖
[solution,minError,isTrue]=isSolutionSubset
(fatherChromosomeGroup,functionError,solutionSumError);
%isSolution函数根据误差functionError判定方程是否已经解开，isTrue=1,方
程得解。solution是方程的解
if isTrue==1
'找到最小集合覆盖'
solution
minError
return%结束程序
end
%%%%%%%%%%%%%3：选择最好解对应的最优染色体
[bestChromosome,leastFunctionError]=best_worstChromosome
(fatherChromosomeGroup,functionError);
%%%%%%%%%%%%%4：保留每次迭代产生的最好的染色体
%本次最好解与上次最好解进行比较，如果上次最好解优于本次最好解，保留上
次最好解；
%反之，保留本次最好解。保留的最好染色体放在holdBestChromosome中
[holdBestChromosome,holdLeastFunctionError]...
=compareBestChromosome
(holdBestChromosome,holdLeastFunctionError,...
bestChromosome,leastFunctionError);
%minError
%solution
%holdLeastFunctionError
%%%%%%%%%%%%%%5:把保留的最好的染色体holdBestChromosome加入到染色体群
中
order=round(rand(1)*chromosomeGroupN);
if order==0
order=1;
end
fatherChromosomeGroup(order,:)=holdBestChromosome;
functionError(order)=holdLeastFunctionError;
%%%%%%%%%%%%%%%6:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)
%%%%%%%%%%%%%%%好的染色体概率高，坏的概率低。依据误差functionError计
算概率
[p,trueP]=subsetChromosomeProbability(functionError);
if trueP =='Fail'
'可能解严重不适应方程，请重新开始'
return%结束程序
end
%%%%%%%%%%%%%%%7：按照概率筛选染色体(关键步骤)
%fa=bin2dec(fatherChromosomeGroup)%显示父染色体
%从父染体中选择优秀染色体
%selecteChromosomeGroup=selecteChromosome(fatherChromosomeGroup,p);
%%%%%%%%%%%%%%%8：染色体杂交(关键步骤)
%sle=bin2dec(selecteChromosomeGroup)%显示选择出来的解的序号(染色体)
%用概率筛选出的染色体selecteChromosomeGroup进行杂交，产生子代染色体
%sonChromosomeGroup=crossChromosome(selecteChromosomeGroup,2);
%不用概率筛选出的染色体selecteChromosomeGroup进行杂交，而直接用上一代
(父代)的
sonChromosomeGroup=crossChromosome(fatherChromosomeGroup,2);
%cro=bin2dec(sonChromosomeGroup)%显示杂交后的子代染色体
%%%%%%%%%%%%%%%9：变异
%不杂交直接变异
%fatherChromosomeGroup=varianceCh
(fatherChromosomeGroup,0.1,solutionN);
%杂交后变异
fatherChromosomeGroup=subsetVarianceCh(sonChromosomeGroup,0.1);
end

复制代码

frogfish · 发表于 2007-7-3 22:13

函数(1)

%构造子集函数constructSubset(setN,subsetSum)
%这是构造子集函数
%setN:集合S的势(绝对值，大小，元素的个数)
%subsetSum:集族F的势
function F=constructSubset(setN,subsetSum)
for i=1:setN%构造集合S
S(i,:)=cellstr(strcat('x',num2str(i)));
%一般情况下，MATLAB中的的字符矩阵要求矩阵中每行的字符数
%相等，cellstr则可以通过转换矩阵为clle阵，把原矩阵中为求
%每一行字符串相等而加在字串后的空格去掉
%strcat:连接字串函数
end
%构造子集族F
%注意：在这里，F中的子集只包含S中元素的序号
%构造子集族的原理：
%1 确定子集族的大小subsetSum,
% i=0，i:子集的序号
%2 i=i+1,如果i>subsetSum，停止程序
% 确定S的一个副本SS：SS=S
%3 随机确定第i个子集的大小subsetI_setN
% 如果subsetI_setN>setN(集合S的大小),subsetI_setN=setN，Fi=SS
% 反之
% j=0,j:i子集中第j个元素的序号
%4 j=j+1,如果i>subsetSum，此时第i个子集Fi构造完毕，到第5步
% 随机从SS中选出一个元素SS(k)放入子集Fi的第j个位置:F(i,j)=SS(k)
% 把SS(k)从SS中删除
% 到第4步
%5 到第2步
%注意，在实际运算时，SS是S中元素的序号集合。
for i=1:subsetSum%i:子集的序号
subsetI_setN=round(rand(1)*setN)+1;
%随机生成第i个子集的大小，也就是第i个子集所包含的元素个数
%SS中装有S中每个元素的序号
SS=1:setN;%设定集合S中元素序号的集合
%每个子集的大小不得超过S
if subsetI_setN>=setN
subsetI_setN=fix(setN/2);
%如果随机生成的元素个数超过了S，子集的大小等于S的1/2
end
setn=setN;
for j=1:subsetI_setN
%j:第i个子集中的第j个元素，把这个元素定名ij，ij=S中某元素的序号
ij=round(rand(1)*setn)+1;%setN+1-j:SS中的元素数
if ij>setn
ij=setn;
Fi(j)=SS(ij);
SS(ij)=[];
setn=size(SS,2);
%删除SS中的第ij个元素，相当于删除了S中的第ij个元素，
%因为子集中的元素不能相等
else
Fi(j)=SS(ij);
SS(ij)=[];
setn=size(SS,2);
end
end
F{i}=Fi;
Fi=[];
end

复制代码

frogfish · 发表于 2007-7-3 22:13

函数(2)

%计算一条染色体中所有元素的总和，
%也就是这条染色体(所代表的子集组合)中所有元素的个数
%subsetSetSum=setSum(chromosomeGroup,F)
%判断染色体是否覆盖集合S
%计算染色体组中每一条染色体(若干个子集的组合)中的元素和
%chromosomeGroup:染色体组，每一条染色体是一个子集组合，染色体中的基因=1，
%这个基因位对应的子集加入到组合中
function subsetSetSum=setSum(chromosomeGroup,F)
[chromosomeGroupN,chromosomeLength]=size(chromosomeGroup);
for i=1:chromosomeGroupN%对每一条染色体循环，相当于取出第一个染色体
allSubsetN=0;%i染色体中所有子集元素数的和
for j=1:chromosomeLength%计算第i条染色体中所有子集元素数的和
if chromosomeGroup(i,j)==1
subset_j_N=size(F{j},2);%F{j}:子集族F中的第j个子集中元素的个数
allSubsetN=allSubsetN+subset_j_N;
end
end
subsetSetSum(i,1)=allSubsetN;
end

复制代码

frogfish · 发表于 2007-7-3 22:13

函数(3)：检查染色体(F中若干个子集的组合)是否可以覆盖S

%这个函数检查染色体(F中若干个子集的组合)是否可以覆盖S
%cover=1:染色体可以覆盖集合S；cover=0:染色体不能覆盖S
function cover=isCover(chromosome,F,SS)
%chromosome:染色体，代表一个子集组合
%F:子集族，采用cell阵组织
%SS:相当于S集的一个副本，存放S中所有元素的序列号
cN=size(chromosome,2);%一条染色体中的基因数，也是F中的子集数
SN=size(SS,2);%集合S中的元素数
s=SS;
sn=SN;
%检查染色体是否覆盖S的算法如下
%1 从染色体中取出一个子集Fi
%2 把Fi中的元素逐一取出与s中的元素比较，如果相同，从s中把这个元素删除。
%3 如果s={}，s被染色体覆盖，检查停止
%4 到1
for i=1:cN%对基因循环，也就是取出子集i
if chromosome(i)==1
%染色体中的第i个基因为1，这个子集参与覆盖组合。
%基因的位置号i是F中子集的序号
Fi=F{i};%F采用cell阵组织。把第i个子集中的全部元素传给Fi
FiN=size(Fi,2);%获得子集中的元素个数
for j=1:FiN%对第i个子集中的每个元素循环，也就是把每个元素取出
for k=1:sn%把集合S中的每个元素取出与Fi子集中的比对
if Fi(j)==s(k)
s(k)=[];%从s中删除与Fi子集相同的元素
sn=size(s,2);
if sn==0%s={}，s为空，s被染色体覆盖
cover=1;
return
end
break
end
end
end
end
end
cover=0;

复制代码

frogfish · 发表于 2007-7-3 22:14

函数(4)评价染色的函数：

%valuation=appraisal(chromosomeGroup,F,SS)
%这个函数通过一条染色体中所有元素的个数与集合S元素个数的差
%评价染色体的好坏
%该函数调用
%subsetSetSum=setSum(chromosomeGroup,F)和
%isCover(chromosome,F,SS)。
%评价染色体优劣的函数
%chromosomeGroup:参与评价的染色体
%一条染色体就是集族F中若个子集的一个组合
%F：集族
%SS：集合S的序号集，相当于S的副本
function valuation=appraisal(chromosomeGroup,F,SS)
%chromosomeGroupN：染色体的条数
%subsetSum：集族F中子集的个数
%染色体上的一个基因代表一个子集Fj
%基因的位置是j，基因=0，第j个子集Fj不参与评价
%基因=1，第j个子集Fj参与评价
%评价原则：
%1 覆盖优先：染色体中所有的子集Fj能够覆盖S，对这样的染色体再进行评价
%2 冗余越多，染色体越不好。
% 冗余定义如下：
% 一条染色体上所有子集的势(子集中元素个数)的和allsubsetN
% 冗余=allSubsetsN-S的势(S中元素的个数)
%冗余放在valuation中
[chromosomeGroupN,subsetSum]=size(chromosomeGroup);
SSN=size(SS,2);
%计算每条染色体所包含子集的元素的总和
allSubsetN=setSum(chromosomeGroup,F);
for i=1:chromosomeGroupN%染色体的序号
cover(i,1)=isCover(chromosomeGroup(i,:),F,SS);
end
for i=1:chromosomeGroupN
if cover(i,1)==1%染色体覆盖了集合S
valuation(i,1)=allSubsetN(i,1)-SSN;%计算冗余
else
valuation(i,1)=Inf;%染色体不能覆盖冗余
end
end

复制代码

frogfish · 发表于 2007-7-3 22:14

函数(5)

%选择最优染色体函数：
%[bestChromosome,leastFunctionError]=best_worstChromosome
(fatherChromosomeGroup,functionError);
%找出最小误差所对应的最好染色体，最大误差所对应的最坏染色体
function [bestChromosome,leastFunctionError]=best_worstChromosome(chromosomeGroup,functionError)
[leastFunctionError minErrorOrder]=min(functionError);
%[maxFunctionError maxErrorOrder]=max(functionError);
bestChromosome=chromosomeGroup(minErrorOrder,:);
%worstChromosome=chromosomeGroup(maxErrorOrder,:);

复制代码

frogfish · 发表于 2007-7-3 22:14

函数(6)

%误差比较函数：从两个染色体中，选出误差较小的染色体
%[holdBestChromosome,holdLeastFunctionError]...
% =compareBestChromosome
(holdBestChromosome,holdLeastFunctionError,...
% bestChromosome,leastFuntionError)
%选择最好的基因保留下来
function [newBestChromosome,newLeastFunctionError]...
=compareBestChromosome(oldBestChromosome,oldLeastFunctionError,...
bestChromosome,leastFunctionError)
if oldLeastFunctionError>leastFunctionError
newLeastFunctionError=leastFunctionError;
newBestChromosome=bestChromosome;
else
newLeastFunctionError=oldLeastFunctionError;
newBestChromosome=oldBestChromosome;
end

复制代码

frogfish · 发表于 2007-7-3 22:15

函数(7)

%为染色体定义概率函数，好的染色体概率高，坏染色体概率低
%p=subsetChromosomeProbability(functionError);
%根据子集的冗余计算染色体的概率
function [p,isP]=subsetChromosomeProbability(chromosomeRedundance)
redundanceSum=size(chromosomeRedundance,1);
InfN=sum(isinf(chromosomeRedundance));%估计非线性方程计算的结果
if InfN==redundanceSum
isP='Fail';
p=0;
return
else
isP='True';
errorReciprocal=1./chromosomeRedundance;
sumReciprocal=sum(errorReciprocal);
p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
end

复制代码

frogfish · 发表于 2007-7-3 22:15

函数(8)

%按概率选择染色体函数：
%slecteChromosomeGroup=selecteChromome(fatherChromosomeGroup,p);
function chromosome=selecteChromosome(chromosomeGroup,p)
cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
[chromosomeSum,chromosomeLength]=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

复制代码

frogfish · 发表于 2007-7-3 22:15

函数(9)

%父代染色体杂交产生子代染色体函数
%sonChrmosomeGroup=crossChromosome(slecteChromosomeGroup,2);
function sonChromosome=crossChromosome(fatherChromosome,parameter)
[chromosomeSum,chromosomeLength]=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

复制代码

frogfish · 发表于 2007-7-3 22:15

函数(10)

%变异函数
%fatherChromosomeGroup=subsetVarianceCh(sonChromosomeGroup,0.8);
%基因变异.染色体群中的1/10变异。vR是变异概率。solutionN是解空间中全部可能解的个数
function aberranceChromosomeGroup=subsetVarianceCh(chromosomeGroup,vR)
[chromosomeSum,chromosomeLength]=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

复制代码

来自：搜狐博客=〉人工智能

账号		自动登录	找回密码
密码			我要加入

[人工智能] 遗传算法解集合覆盖问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。