tom的机器学习方法 ml-chap09

《tom的机器学习方法 ml-chap09》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章遗传算法遗传算法提供了一种大致基于模拟进化的学习方法。其中的假设常被描述为二进制位串，位串的含义依赖于具体的应用。然而，假设也可以被描述为符号表达式或者甚至是计算机程序。对合适假设的搜索是从若干初始假设的群体（population）或汇集（collection）开始的。当前群体的成员通过模仿生物进化的方式来产生下一代群体，比如说随机变异（mutation）和交叉（crossover）。在每一步，根据给定的适应度（fitness）度量评估当前群体中的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。遗传算法已被成功地应用到多种学习任务

2、和最优化问题中。例如，遗传算法已被用于学习机器人控制的规则集，以及优化人工神经网络的拓扑结构和学习参数。这一章既覆盖了用位串描述假设的遗传算法（geneticalgorithms），也覆盖了用计算机程序描述假设的遗传编程（geneticprogramming）。9.1动机遗传算法（GA）提供了一种受生物进化启发的学习方法。它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设。在每一步，被称为当前群体（population）的一组假设被更新，方法是通过使用目前适应度最高的假设的后代替代群体的某个部分。这个过程

3、形成了对假设的生成并测试（generate-and-test）柱状搜索（beam-search），其中若干个最佳当前假设的变体最有可能在下一步被考虑。GA的普及和发展得益于以下因素：·在生物系统中进化被认为是一种成功的自适应方法，并且具有很好的鲁棒性。·GA搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度的影响难以建模。·遗传算法易于并行化，且可降低由于使用超强计算机硬件的带来的昂贵费用。这一章描述了遗传算法，举例演示了它的用法，并分析了它搜索的假设空间的特性。我们也描述了它的一个变体，称为遗传编程，在这种方法中，整个计算机程序向着某

4、个适应度准则进化。遗传算法和遗传编程是进化计算（evolutionarycomputation）领域的中的两种流行方法。在本章的最后一节我们将接触一些研究生物进化的课题，包括鲍德温效应（Baldwineffect），它描述了个体的学习能力与整个群体进化速度之间有趣的相互作用。9.2遗传算法GA研究的问题是搜索一个候选假设的空间，以确定最佳的假设。在GA中，“最佳假设”被定义为是使“适应度（fitness）”最优的假设，适应度是为当前问题预先定义的数字度量。例如，如果学习任务是在给定一个未知函数的输入输出训练样例后逼近这个函数，那么适应度可被定义为假设在

5、训练数据上的精度。如果任务是学习下国际象棋的策略，那么适应度可被定义为该个体在当前群体中与其他个体对弈的胜率。尽管遗传算法的不同实现在细节上有所不同，但它们都具有以下的共同结构：算法迭代更新一个假设池，这个假设池称为群体。在每一次迭代中，根据适应度函数评估群体中的所有成员。然后从当前群体中用概率方法选取适应度最高的个体产生新的一代。在这些被选中的个体中，一部分保持原样地进入下一代群体，其他的被用作产生后代个体的基础，其中应用象交叉和变异这样的遗传方法。表9-1描述了一个遗传算法原型。算法的输入包括：用来排序候选假设的适应度函数；定义算法终止时适应度的阈

6、值；要维持的群体大小；和决定如何产生后继群体的参数：每一代群体中被淘汰的比例和变异率。表9-1遗传算法原型算法中维持一个包含p个假设的群体。在每一次迭代中，后继群体PS的形成通过两种途径：根据假设的适应度用概率方法选择个体，以及加入新假设。新假设通过两种方法得到：对最高适应度假设对应用交叉算子；对通过选择和交叉产生的新一代群体中的部分假设进行单点变异。重复这个迭代过程，直到发现适应度足够好的假设。典型的交叉和变异算子定义在后面的表格中。GA(Fitness,Fitness_threshold,p,r,m)Fitness：适应度评分函数，为给定假设赋予一

7、个评估得分。Fitness_threshold：指定终止判据的阈值。p：群体中包含的假设数量。r：每一步中通过交叉取代群体成员的比例。m：变异率。·初始化群体：P¬随机产生的p个假设·评估：对于P中的每一个h，计算Fitness(h)·当[Fitness(h)]应用交叉算子产生两个后代。

8、把所有的后代加入PS。3．变异：使用均匀的概率从PS中选择m百分比的成员。对于选出的每个成员，