分布估计算法提出了一种全新的进化模式。在传统的遗传算法中，用种群表示优化问题的一组候选解，种群中的每个个体都有相应的适应值，然后进行选择、交叉和变异等模拟自然进化的操作，反复进行，对问题进行求解。而在分布估计算法中，没有传统的交叉、变异等遗传操作，取而代之的是概率模型的学习和采样。分布估计算法通过一个概率模型描述候选解在空间的分布，采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型，然后对概率模型随机采样产生新的种群，如此反复进行，实现种群的进化，直到终止条件。
- 随机生成M个个体作为初始种群
- 对第
代种群计算个体适应度，判断是否满足终止条件。若满足条件则终止循环，否则继续执行。
- 根据适应度值从种群中选出前N(
)个优势个体，组成第
代优势子种群
- 根据优势子种群更新概率模型
- 对概率模型进行随机采样，生成新种群，新种群规模大小为
，返回第2步。
这个仓库中的主代码文件时分布估计算法的样例代码。以经典0-1背包问题为背景，使用EDA分布估计算法来解决背包问题。具体计算步骤如下：
-
以概率 T 随机产生N个个体组成一个初始种群； $$ T=(p_1,p_2,...,p_n)^T=(0.5,0.5,...,0.5)^T $$
-
评估初始种群中所有个体的适应度，保留最好解；
-
按照适应度从高到低的顺序对种群进行排序，并从中选出最优的 m 个个体；
-
分析产生的 m 个个体所包含的信息，估计每个变量取1的概率 T；
-
从构建的概率模型中采样，得到 N 个新样本，构成新种群；
-
若达到算法终止条件则结束（例如达到规定迭代次数 n_max ），否则执行步骤2.
该分布估计算法的时间复杂性估算如下：以计算适应度操作花费时间最多，所以时间复杂性大约为 $$ O(N \cdot n_{max}) $$
eda.py
GitHub主页：XintaoPeach (Xintao) (github.com)