第9章分布估计算法.ppt

皖西学院应用数学学院数学建模教学基地周本达
******@wxc.
1
思想
遗传算法中的交叉、变异等操作有可能破坏已经优化好的个体。为了避免这种现象,一种新的演化算法–分布估计算法应运而生。
分布估计算法中没有交叉和变异。主要用到是好的个体的一种概率模型,以及根据此模型抽样产生下一代。
2
7/7/2017
GA to EDA
3
基于种群的增强式学习
Population based Incremental Learning (PBIL, Baluja, 1994)
Populations based search, such as GA
Create a probability vector by counting the number of 1s and 0s in each gene position
Generate new population using the probability vector
No information is carried from generation to generation!
petitive learning, . LVQ
Winner-take-all reinforcement learning in ANN
Winner is a kind of prototype of the sample presented
PBIL = GA + CL
Capture the trend from the best performer
4
Basic PBIL
P  initialize probability vector (each position = )
while (generations++ < limit)
for each vector i do
for each position j do
generate Vi(j) according to P(j)
end-do
evaluate f(Vi)
end-do
Vmax = max(f(Vi))
update P according to Vmax
if random(0,1] < Pmutate
mutate P
end-if
end-while
5
Details
Population replaced by probability vector
P = {p1 , p2 , …, p}
pi : Probability of 1 in the ith bit
Generate n individuals
Update P using the best individual
pi(t+1) = xi + pi(t)(1- ), i = 1,2,…,
Mutate P:
pi(t+1) = mU[0,1) + pi(t+1)(1- m)
6
PBIL Example
t = 0, P = {, , , }
Generate 5 individuals
{1010, 1100, 0100, 0111, 0001}
Fitness: {2, 2, 1, 3, 1}
Best individual: 0111; =
Update P
p1 = *(1-) =
p2 = p3 = p4 = *1 + *(1-) =
7
Some applications
Function optimization
Job-shop scheduling
TSP
Bin-packing
Knapsack Problem
work weight training
8
分布估计算法:总的框架
Estimation of Distribution Algorithms do just that!
Typically they operate as follows:
Step 0: Randomly generate a set of  individuals (t=0)
Step 1: Evaluate the  individuals
While (not done)
Step 2: Select  individuals (where ) to be parents
Develop a probability distribution/density function, pt, based on the parents
Step 3: Create  offspring using pt
Step 4: Evaluate the offspri