分布估计算法（EstimationofDistributionAlgorithm，EDA）。。。英文编辑
⽬录
EDA算法
EDA算法原理
通过⼀个概率模型描述候选解在空间得分布，采⽤统计学习⼿段从群体宏观的⾓度建⽴⼀个描述解分布得概率模型，然后对概率模型随机采样产⽣新的种群，如此反复进⾏，实现种群得进化，直到终⽌条件。（—建模-采⽤-建模-采样----循环）
EDA的不同变体
EDA有很多不同的变体，包括如下⼀些，想详细了解可以参照参考⽂献。
变量⽆关：PBIL、UMDA、cGA算法
双变量相关：MIMIC、BMDA算法
多变量相关：ECGA、FDA、BOA算法
EDA算法流程
通⽤算法步骤为：
Step1 随机⽣成M个个体作为初始种群 ；
Step2 对第L代种群计算个体适应度，判断是否满⾜终⽌条件，若满⾜，终⽌循环；若不满⾜，继续进⾏。
Step3 根据适应度数值从种群中选出前N个（N≤M）优势个体，组成第L+1代的优势⼦种群 ；
Step4 根据优势⼦种群更新概率模型 ；
Step5 对概率模型进⾏随机采样，⽣成新种群（规模M），返回Step2.
具体介绍两个变体UMDA（Univariate marginal distribution algorithm）和PBIL（Population bad incremental learning），主要区别在于更新概率模型的公式不同。
EDA算法变体UMDA
由德国学者Muhlenbein在1996年提出，算法描述：
Step1 随机产⽣M个个体作为初始种群；
Step2 然后计算M个个体的适应值，如果符合终⽌条件，算法结束，否则继续进⾏；
Step3 选择最优的N个个体⽤来更新概率向量p(x), N <= M
更新过程：
Step4 由新的概率模型采样M次，得到新⼀代群体，返回Step2
EDA算法变体PBIL
由美国卡耐基梅隆⼤学的Baluja在1994年提出，算法描述：
Step1 随机产⽣M个个体作为初始种群；
Step2 然后计算M个个体的适应值，如果符合终⽌条件，算法结束，否则继续进⾏；
Step3 选择最优的N个个体⽤来更新概率向量p(x), N <= M
更新过程：
Step4 由新的概率模型采样M次，得到新⼀代群体，返回Step2
一什么不振测试算例：KP
MATLAB代码
function [bestFit]=binaryUMDA(weightMax,weight_Individual,value_Individual)
%EDA_UMDA Algorithm，⼆进制编程
%参数
iterations =500;%迭代最⼤次数
populationSize =200;%种群规模
dimensionality =size(weight_Individual,2);%维度
dominantNum =20;%优势群体个数
% weightMax 背包最⼤容量/重量
% weight_Individual 每个变量的体积/重量
% value_Individual 每个变量的价值
%初始化种群
probability =0.5*ones(1,dimensionality);%初始化概率0.5
Best_Individual=zeros(iterations,dimensionality+1);%每次迭代中的最优解,(:,1)存储适应度值
%循环迭代
for I=1:iterations
%按照概率模型创建样本
flag =0;i=1;牡丹什么季节开花
while i<=populationSize
r=rand(1,dimensionality);
Species(i,:)=1.*(r<probability);
%判断是否超出容量范围
weightSum =sum(Species(i,:).*weight_Individual,2);
if flag>=20
Species(i,:)=zeros(1,dimensionality);%多次仍未符合要求，舍弃
flag =0;
elif weightSum>weightMax
i=i-1;flag=flag+1;
elcoreldraw教程
flag =0;
end
i=i+1;
end
%计算适应度
Fitness_Value=zeros(populationSize,1);%创建适应度计算
for i=1:populationSize
Fitness_Value(i,1)=sum(Species(i,:).*value_Individual,2);
end
%排序
[Fitness,index]=sort(Fitness_Value);%⼩=》⼤排序
%每次迭代中的最优解
Best_Individual(I,1)= I;
Best_Individual(I,2)=Fitness_Value(index(populationSize));
for i=3:dimensionality+2
Best_Individual(I,i)=Species(index(populationSize),i-2);
end
%选取优势种群
dominantSpecies=zeros(dominantNum,dimensionality);%创建选取的优势群体<populationSize,(:,1)存储适应度值for i=1:dominantNum
dominantSpecies(i,:)=Species(index(populationSize-dominantNum+i),:);
翻译英语翻译end
%更新概率模型划重点
Ones_Number =sum(dominantSpecies);
盆花图片大全probability = Ones_Number/dominantNum;
end
%画图函数
bestFit =Best_Individual(iterations,[2:dimensionality+2]);
%输出，画出fitness-iterations
plot(Best_Individual(:,1),Best_Individual(:,2));
disp(strcat('最优结果',':',num2str(Best_Individual(iterations,2))));
function [bestFit]=binaryPBIL(weightMax,weight_Individual,value_Individual)
%EDA_PBIL Algorithm，⼆进制编程
重生喜乐小日子
%参数
iterations =500;%迭代最⼤次数
populationSize =200;%种群规模
dimensionality =size(weight_Individual,2);%维度
learningRate =0.3;%((0.001*(dimensionality)^2)>1)*1+((0.001*(dimensionality)^2)<=1)*(0.001*(dimensionality)^2); %学习效率太⼩会不收敛
dominantNum =20;%优势群体个数
% weightMax 背包最⼤容量/重量
% weight_Individual 每个变量的体积/重量
% value_Individual 每个变量的价值
%初始化种群
probability =0.5*ones(1,dimensionality);%初始化概率0.5
Best_Individual=zeros(iterations,dimensionality+1);%每次迭代中的最优解,(:,1)存储适应度值
%循环迭代
for I=1:iterations
%按照概率模型创建样本
flag =0;i=1;
while i<=populationSize
r=rand(1,dimensionality);
Species(i,:)=1.*(r<probability);
%判断是否超出容量范围
weightSum =sum(Species(i,:).*weight_Individual,2);
if flag>=20
Species(i,:)=zeros(1,dimensionality);%多次仍未符合要求，舍弃
flag =0;
elif weightSum>weightMax
i=i-1;flag=flag+1;
el
flag =0;
end
i=i+1;
end
%计算适应度
Fitness_Value=zeros(populationSize,1);%创建适应度计算
for i=1:populationSize
Fitness_Value(i,1)=sum(Species(i,:).*value_Individual,2);
end
%排序
[Fitness,index]=sort(Fitness_Value);%⼩=》⼤
%每次迭代中的最优解
Best_Individual(I,1)= I;
Best_Individual(I,2)=Fitness_Value(index(populationSize));
for i=3:dimensionality+2
Best_Individual(I,i)=Species(index(populationSize),i-2);
end
重整%选取优势种群
dominantSpecies=zeros(dominantNum,dimensionality);%创建选取的优势群体<populationSize,(:,1)存储适应度值for i=1:dominantNum
dominantSpecies(i,:)=Species(index(populationSize-dominantNum+i),:);
end
%更新概率模型划重点
Ones_Number =sum(dominantSpecies);
probability =(1-learningRate)*probability+learningRate*Ones_Number/dominantNum;
end
%画图函数
bestFit =Best_Individual(iterations,[2:dimensionality+2]);
%输出，画出fitness-iterations
%plot(Best_Individual(:,1),Best_Individual(:,2));
disp(strcat('最优结果',':',num2str(Best_Individual(iterations,2))));
实验结果展⽰
UMDA结果
运⾏结果在如下参数的前提下得出
种群规模：200
优势群体个数：20
种群计算迭代次数：500
备注：算法运⾏结果为求50次运算结果的平均值，误差=（理论最优解-算法运⾏结果）/理论最优解*100%
PBIL结果
运⾏结果在如下参数的前提下得出
学习效率：0.3
种群规模：200
优势群体个数：20
种群计算迭代次数：500
备注：算法运⾏结果为求50次运算结果的平均值，误差=（理论最优解-算法运⾏结果）/理论最优解*100%
参考⽂献
[1] 周树德, 孙增圻. 分布估计算法综述[J]. ⾃动化学报, 2007, 33(2).
