idea建设完整的网站,微官网下载,四种营销模式,色块网站概论
分布估计算法#xff08;Estimation of distribution algorithm#xff0c;EDA#xff09;是一种新兴的基于统计学原理的随机优化算法。
为什么要叫这个名字呢#xff1f;
首先#xff0c;“分布”指的就是概率分布。
其次#xff0c;“估计”指的是这个概率分布…概论
分布估计算法Estimation of distribution algorithmEDA是一种新兴的基于统计学原理的随机优化算法。
为什么要叫这个名字呢
首先“分布”指的就是概率分布。
其次“估计”指的是这个概率分布是我们根据数据以及算法的迭代过程中估算出来的是一个近似并不是真实的分布。
但是大数定律告诉我们样本足够大的情况下样本出现频率会无限接近于真实概率。因此这种估计的方法是具有一定的理论依据的。 EDA v.s. GA
其实这两个算法整体思路非常相似。
不同的是GA通过交叉、变异产生新解EDA则通过估计截至目前群体中最优解的概率分布即较优个体主要都分布在哪一区间这样做的好处是可以使得搜索具有一定的方向性。
两种算法的流程图如下 图1遗传算法的流程图 图2分布估计算法的流程图 算法原理
概率模型是EDA的核心, EDA通过概率模型及其更新来描述解空间分布以及种群整体进化趋势. 按概率模型的结构及变量间的相互关系, 可分为变量无关、双变量相关和多变量相关 EDA。1
上面已经提到分布估计算法与遗传算法非常相似关于选择过程可以参考这篇文章遗传算法附简单案例及matlab详细代码因此不再介绍其相同的流程只介绍不同点。
EDA算法是一个大类的算法根据采用不同的概率模型还有很多细分。相比于遗传算法EDA最大的特点就是种群产生的方式通过概率分布来产生。因此了解其中的概率模型的细节很重要。
Univariate marginal distribution algorithm (UMDA)
UMDA是一种简单的EDA它通过估计所选择个体的边界概率来建立模型。
从当前群体中选择 λ \lambda λ 个个体组成繁殖群体 S ( t ) S(t) S(t)。
依据 S ( t ) S(t) S(t) 建立模型如下 p t 1 ( x i ) 1 λ ∑ x ∈ S ( t ) x i , i 1 , 2 , . . . , n p_{t1}(x_i)\frac{1}{\lambda}\sum_{x\in S(t)}x_i,i1,2,...,n pt1(xi)λ1x∈S(t)∑xi,i1,2,...,n Population-based incremental learning (PBIL)
PBIL算法是UMDA的一种改进它通过增量的方式来建立概率模型。
同样从当前群体中选择 λ \lambda λ 个个体组成繁殖群体 S ( t ) S(t) S(t)。
依据 S ( t ) S(t) S(t) 建立模型如下 p t 1 ( x i ) ( 1 − γ ) ⋅ p t ( x i ) γ ⋅ 1 λ ∑ x ∈ S ( t ) x i p_{t1}(x_i)(1-\gamma)\cdot p_t(x_i)\gamma\cdot \frac{1}{\lambda}\sum_{x\in S(t)}x_i pt1(xi)(1−γ)⋅pt(xi)γ⋅λ1x∈S(t)∑xi
其中 γ ∈ ( 0 , 1 ] \gamma \in (0,1] γ∈(0,1]是学习因子learning rate。 基于高斯模型的EDA算法流程
随机生成初始种群 P ( 0 ) P(0) P(0)初始化高斯模型的均值 μ \mu μ和方差 δ \delta δ。假设每维变量的高斯模型为 { N ( μ 1 , δ 1 ) , . . . , N ( μ n , δ n ) } \{N(\mu_1,\delta_1),...,N(\mu_n,\delta_n)\} {N(μ1,δ1),...,N(μn,δn)}n为自变量的维数抽样根据各位自变量对应的高斯模型抽样产生新种群 T ( t ) T(t) T(t)选择从新种群种选择优秀个体集合 S ( t ) S(t) S(t)建模计算 S ( t ) S(t) S(t)在各个变量上的均值与方差对原有模型进行更新。算法未达到结束条件返回2否则退出。
均值更新模型如下 μ j t 1 ( 1 − α ) ⋅ μ j t α ⋅ ( x j b e s t , 1 x j b e s t , 2 − x j w o r s t ) \mu_j^{t1}(1-\alpha)\cdot \mu_j^t\alpha\cdot(x_{j}^{best,1}x_{j}^{best,2}-x_{j}^{worst}) μjt1(1−α)⋅μjtα⋅(xjbest,1xjbest,2−xjworst)
方差更新模型如下 δ j t 1 ( 1 − α ) ⋅ δ j t α ⋅ ∑ k 1 K ( x j k − x ˉ j ) K \delta_j^{t1}(1-\alpha)\cdot \delta_j^t\alpha\cdot \sqrt{\frac{\sum_{k1}^K(x_j^k-\bar{x}_j)}{K}} δjt1(1−α)⋅δjtα⋅K∑k1K(xjk−xˉj)
其中 α ∈ [ 0 , 1 ] \alpha\in [0,1] α∈[0,1]是学习因子K为所选择的优秀个体数目 x ˉ \bar{x} xˉ是所选择的优秀个体的平均值 x b e s t , 1 , x b e s t , 1 x^{best,1},x^{best,1} xbest,1,xbest,1是当前群体种最好的两个个体 x w o r s t x^{worst} xworst是当前群体中的最差个体
更新方式多种多样也可以直接用优秀个体的均值和防擦好来替代原来的均值和方差。 Matlab 仿真实例
问题
求解下列函数的最大值 y x 1 ⋅ c o s ( 2 π x 2 ) x 2 ⋅ c o s ( 2 π x 1 ) yx_1\cdot cos(2\pi x_2)x_2\cdot cos(2\pi x_1) yx1⋅cos(2πx2)x2⋅cos(2πx1) 分析
该问题可以采用PBIL算法进行实现因为是求最大值所以就选取目标函数作为适应度函数。 代码实现
代码参考博客2我已经逐行注释感兴趣的可以阅读一下代码细节供参考学习使用。
% 问题 -2x1, x22 yx1 * cos(2*pi*x2) x2 * cos(2*pi*x1)
%%%%%%%%%%%%PBIL algorithm
clc
clear
clf
tic %开始计时
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%参数设置%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Pop_Size40; % 种群中个体数量
Variable_Num2; % 每个个体中种群的变量数
Individual_Len20; % 每个变量的长度(相当于一个二进制数)
Iteration_Times1000; % 进化次数
I1; % 表示第几次进化过程
Learning_Rate0.01; % 学习速率
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%产生初始种群%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Binary_Xzeros(Pop_Size,Variable_Num,Individual_Len); % 生成值为0的种群矩阵Binary_X
for i1:1:Pop_Size % Pop_Size40for j1:1:Variable_Num % Variable_Num2for k1:1:Individual_Len % Individual_Len20Binary_X(i,j,k)round(rand()); % round函数用于四舍五入随机产生的值 rand()end % 函数随机产生 0到1 之间的小数 round函数将小数四舍五入为0或1end
end
% zeros是MATLAB内的一个函数。
% 其功能是返回一个m×n×p×...的double类零矩阵。注意m, n, p,...必须是非负整数
% 负整数将被当做0看待。
% 二维用法zeros(m,n)或zeros(n)
% 功能zeros(m,n)产生m×n的double类零矩阵zeros(n)产生n×n的全0方阵。
Best_Individualzeros(1,Iteration_Times); % 初始化值为0的优势种群矩阵用于记录每次进化最好情况
Probability_Vectorzeros(Iteration_Times,Variable_Num,Individual_Len); % 初始化概率向量矩阵
traceszeros(3,Iteration_Times); % 追踪每一代的最优值trace为最优值矩阵用来记录每一代的最优值
%%%%%%%%%%%%%%%%%%%%%%%%%%开始进行迭代%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
while IIteration_Times
%%%%%%%%%%%%%%%%%%%%%%%将采样的值由二进制转化到十进制%%%%%%%%%%%%%%%%%%%%%%Decimal_Xzeros(Pop_Size,Variable_Num); % 初始化十进制矩阵for i1:1:Pop_Sizefor j1:1:Variable_Num kIndividual_Len; % Individual_Len20t1;while k1%将二进制矩阵转化为十进制矩阵,便于后面进行排序Decimal_X(i,j)Decimal_X(i,j)Binary_X(i,j,k)*2^(t-1); % 将一位二进制转化为十进制kk-1; % 向左切换到下一位进行进制转换tt1; endendend
%%%%%%%%%%%%%%%%%%%%%%%%%%%将十进制映射到解空间中%%%%%%%%%%%%%%%%%%%%%%%%%%%Solutionzeros(Pop_Size,Variable_Num); % 初始化解空间矩阵二维for i1:1:Pop_Sizefor j1:1:Variable_NumSolution(i,j) -2 Decimal_X(i,j) * 4 / (2^Individual_Len-1); % 存储每个个体对应变量的解endend
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%计算适应值%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Fitness_Valuezeros(1,Pop_Size); % 初始化适应值矩阵一维表针对每个个体for i1:1:Pop_Size % .*表示矩阵之间元素按位置相乘Fitness_Value(i)Solution(i,1).*cos(2*pi*Solution(i,2))Solution(i,2).*cos(2*pi*Solution(i,1));end % 计算每个个体的适应值相当于求f(x)的值这里是求解函数的最大值
%%%%%%%%%%%%%%%%将适应值按照从小到大的顺序排序并选出最优个体%%%%%%%%%%%%%%%[FitnessValue,index]sort(Fitness_Value); % 排序适应值升序FinnessValue存储排序好的值index存储对应值在原函数的索引Best_Individual(I)Fitness_Value(index(Pop_Size)); % 存储本次进化最优个体升序对应索引位置的值最大的值traces(1,I)Solution(index(Pop_Size),1); % 存储每代最优个体各变量的值及最优值traces(2,I)Solution(index(Pop_Size),2);traces(3,I)Fitness_Value(index(Pop_Size));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%选出优势群体%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Superiority_Polutionzeros(Pop_Size/2,Variable_Num,Individual_Len); % 只从所有个体选择一半作为优势个体初始化优势种群矩阵for i1:1:Pop_Size/2 % Pop_Size/2决定优势种群个体数for j1:1:Variable_Numfor k1:1:Individual_LenSuperiority_Polution(i,j,k)Binary_X(index(iPop_Size/2),j,k);end % 由于之前是升序排序且是选择一半优势个体所以优势个体都是从中间开始向后才有的end % 索引在这里起到了很重要的作用不能使用FitnessValue矩阵因为矩阵内是十进制数end % 而索引在这里可以帮助寻找原矩阵中的二进制数
%%%%%%%%%%%%%%%%从优势群体中统计基因位的值来更新概率向量%%%%%%%%%%%%%%%%%%%Ones_Numberzeros(Variable_Num,Individual_Len);for i1:1:Pop_Size/2for j1:1:Variable_Numfor k1:1:Individual_Lenif Superiority_Polution(i,j,k)1 % 如果优势种群中某个体中某变量中二进制串某一位为1Ones_Number(j,k)Ones_Number(j,k)1; % 让对应变量对应位在下次产生1的概率增加1endendendendfor j1:1:Variable_Numfor k1:1:Individual_LenProbability_Vector(I,j,k)Ones_Number(j,k)/(Pop_Size/2); % 更新每一变量每一位可能出现1概率向量采用百分比形式end end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%更新概率向量%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if I1 % 如果这不是第一次进化进行增量学习for j1:1:Variable_Numfor k1:1:Individual_Len% 这里结合了最优个体(此处只选择了一个当然也可以选择多个)和上一代的概率得到这一带的概率Probability_Vector(I,j,k)Learning_Rate.*Binary_X(index(Pop_Size),j,k)(1-Learning_Rate).*Probability_Vector(I-1,j,k);endend
end
%%%%%%%%%%%%%%%%%%%%%%%%根据概率向量对解空间采样%%%%%%%%%%%%%%%%%%%%%%%%%%%%for i1:1:Pop_Size % 这里针对上面得到的最新概率重新产生新的种群for j1:1:Variable_Numfor k1:1:Individual_Lenrrand(); % 随机生成数0到1之间的小数rif rProbability_Vector(I,j,k) % 如果r小于概率向量的值对应为1Binary_X(i,j,k)1; % 种群矩阵为1else Binary_X(i,j,k)0; % 否种群矩阵为0endendendend % 执行如上操作就得到了下一代群体II1; % 进化次数1
end % 迭代终止
toc % 计时终止显示程序运行所用
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%生成种群演化图%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%figure(1) % 生成画图窗口
hold on
%hold on是当前轴及图像保持而不被刷新准备接受此后将绘制的图形多图共存
%hold off使当前轴及图像不再具备被刷新的性质新图出现时取消原图。即关闭图形保持功能。
xlabel(进化代数) % X轴名称为进化代数
ylabel(最优解的变化) % Y轴名称为最优解的变化
title(进化过程) % 图像名为进化过程
plot(Best_Individual); % 根据每代种群中最优个体绘制函数图像
grid on % grid on为显示函数网格线 grid off 为隐藏函数网格线
[Best_Polution,xuhao_Iteration]max(Best_Individual); % 获取最优个体
bestx1traces(1,xuhao_Iteration); % 获取最优个体参数1
bestx2traces(2,xuhao_Iteration); % 获取最优个体参数2
bestztraces(3,xuhao_Iteration); % 获取最优个体值
% 打印结果
fprintf([最优解:\nx1,num2str(bestx1),\nx2,num2str(bestx2),\nf,num2str(bestz),\niteration,num2str(xuhao_Iteration),\n]);
hold off%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%百度百科——分布估计算法 ↩︎ https://blog.csdn.net/basketball616/article/details/102715280 ↩︎
