0b924数据挖掘及应用第10讲启发式

第10发式挖 11234遗传算蚁群算人工蜂群算人工神经网11234遗传算蚁群算人工蜂群算人工神经网Michigan大学JohnHolland

(Darwin物竞天适者生物种多样A-腺T-胸腺嘧C-胞嘧G-鸟嘌 上的位置称为座 等 可能不 各一来自父 –物 而问题中对（一就是问的解的一称个 是索空间的一点。模拟生物种群而由若 组成的群体,它一般是整个搜索空间一个很小的子 适应度函数(fitness问题中的全 与其适应度之间的一个对应关系。它一般是个实值函数。该函数 问题 的某种字符串形式的编码表示字符串中标识某种特征的字符或字符集称 干 ，生一。据化论适度的 入殖池的率越大将两 取值进行交改 上某个/ 的取0,C 的编码方 T---遗传运算终止条 生成生成初始种计计算适应终止终止选择变交变交生生成新一代种y=x2的最YYX原问题可转化为在区间［031］中搜索能使y取最大值的［0,31］中的点x就是 适应度，区间［0,31］就是一个(解)空间。 5fs1=13(01101),s2=24s3=8(01000),s4=194s1=s3=的适应度f(si。

s2=s4=f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192= P(xi)

f(xiN

f(xjjP(s1)=P(13)=P(s2)=P(24)=P(s3)=P(8)=P(s4)=P(19)=［0,1］区间内产生一个均匀分布的随机r≤q1,则x1qk-1<r≤qk(2≤k≤N),则xk中的qi称为xi(i=1,2,…,n)的积累概率,其iqiP(xjij

,r1=r3=

r2=r4=1201 s1’=11000（24）,s2’s3’=11000（24）,s4’设交叉率pc=100%，即S1中的全体 s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）, 0.02位显然不足1位，所以本轮遗传操作不1110）,2010）s3=11,s4100） 1021 4 s1’=11001（25）,s2’=s3’=11011（27）,s4’= s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19） 2011

s1’=11100（28）,s2’=11100（28）s3’=11000（24）, s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出现了适应度最高的s1=11111。于是，遗传操作终止，将“11111”作为最终结果输出。然后，将“11111”为表现型，即YY819XY25X第一代种群及其适应 YY91924XYY2428

0,C 的编码方 T---遗传运算终止条 适应度低 小为n，i的适应度为Fi，则i被选中遗传到下一n Fi/Fini 率Pc按某种方式相互交换其部 。在遗传算法中起关键作用，是产生

所谓变异运算，是指依据变异概率Pm将 基本位变异算子是指对编码串随机指定的某一位或某几位作变异运算。对于基本遗传算法中用二进制编码符号串所表示的，若需要进行变异操作的某一座上的原有值为0，则变异操作将其变为1；反之，若原有值为1，则变异操作将其变为0。高的容错能力二进制编码优点在于编码、操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，编码串较编码克服了二进制编码的不连续问浮点数编码改善了遗传算法的计算复杂性

1对群体中的所有按其适给各个；以各 所分配到

1随机产生一个与编码长度相同的二进制字P=W1W2…Wn中产生两个新XY：若Wi=0，则X的第i个继承A的对应，Y的第i个继承B的对应；若1，则A、B的第i个相互。348|7965|2348|5697|2M=20-T=100-Pc=0.4-Pm0.001-0.01度自动改变，当种群的各个适应度趋于一致或趋于局二者减小，同时对适应值高于群体平均适应值的，采用较低的PC和Pm，使性能优良的进入下一代，而低于平均适应值的，采用较高的PC和Pm，使性能较差的个体被淘汰。11234遗传算蚁群算人工蜂群算人工神经网蚁群算法(antcolonyoptimization,ACO)，又称蚂 泌物pheromone(称为信息素,该物质随着时间的推 更 最

蚂蚁观察到的范围是（一般是3），那么它能观察到的范围就是3*3个方格世。

，它就会尽量避开

每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着走远的距离，播撒的信息素越来在水平上，每只蚂蚁仅根据环境做出独立选择；在群 ⑵迭代过fori=1to (对forj=1ton-1 (对n根据式(1)，采 赌方法在窗口外选择下一个节点j;将j置 表,蚂蚁转移到jend计算每只蚂蚁的路径长度;k=k+1;⑶输出结果,结束算法择下一个节点j的概率为: [(i,j)][(i,

ifjPk(i,j)

[(i,s)][(i,s)]

0 (i,j)表示边（ij）(i,j)1d(i,j)是启发信息，d是节点ijα和βtabuk表示蚂蚁k已

ij(tn)ij(t)m

kij kk–其中：ρ为小于1

ij

一般情况下蚁群中蚂蚁的个数不超过TSP 点的个数给定一个外循环的最大数目当前最优解连续K次相同而停止，其中K是一个给定的整数，表算法已经收敛，不再需要继续1）11234遗传算蚁群算人工蜂群算人工神经网 峰外 ，查找蜜花蜜的多花蜜的好 卸载花蜜卸载花蜜，变 峰，在采蜜的附近搜索蜜卸载花蜜，变成引领11234遗传算蚁群算人工蜂群算人工神经网使用ANN研究和模拟生物学习过获得高效的机器学习算法，不管这种算法是否反映了生物过 (a)阈值激励函 (b)S型函数1/(1+e-

nwan

wa

a)sgn(wsgn(y)

y 个感知器意味着确定选择权w0,…,wn的值{w|w {w|w

wx合做到这一点，所以我们感的是学习感知器组成的多层表示了当前输入的一个函数,除了权值自身,网络没有其他内部状如单层感知器和多层感知将其输出反馈回自己的输网络的激励层构成一个动力学系统,它可能到达一个稳定状态,或生振荡,或进入混沌状能够支持短时间感知器训练方

从随机的权值开反复应用这个感知器到每个训练样例，只要它误分类样例就修改知器的权重复这个过程，直到感知器正确分类所有的训练样 wiwiwi(t 把delta训练法一个无阈值的o(x)w

22

od

ww被称为Ew的梯度，记作

ww wDescent(training_examples,)初始化每个wi为对于训练样例training_examples中的每个把实 xx对于线性单元的每个权wi

,twi新权值w输出是输入的非线性函输出是输入的可微函 o

(wx)

(y)

1e输出范围是0到身身 2 2E(w)

(tkddDkoutpus

okd BackPropagation(training_examples,,nin,nout, 创建具有nin个输入，nhidden个隐藏，nout在遇到终止条件 对于训练样例training_examples中的每个<xt把输入沿网络前学习速率该权值涉及的输入值delta法则中的误差项被替换成一个更复杂的误差项数的导数ok(1-ok元h影响的每一个单元的误差k进行求和，每个误差k wji(n)=jxji+wji(n-域表示，尽管在情况下所需隐藏单元的数量