心人工智能作业.doc

《心人工智能作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《人工智能》实验大作业实验题目：基于简单遗传算法求函数最大值问题专业信息与计算科学年级09级姓名王安心学号指导老师时华日期2012-12-10简单遗传算法一、实验目的：熟悉和掌握遗传算法的基本思想和基本方法，通过实验培养学生利用遗传算法进行问题求解的基本技能，并且了解进化计算其他分支的基本思想和基本方法。二、实验方法：1.先熟悉进化计算中遗传算法的基本思想和流程；2.用C、C++、JAVA或Prolog语言编程实现实验内容。三、实验背景知识：生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则。群体中的个体根据对环境的适应能力而被大自然所选

2、择或淘汰。进化计算(evolutionarycomputation,EC)就是通过模拟自然物群进化的一类非常鲁棒的优化算法，它们模拟群体(其中组成群体的每个个体表示搜索问题解空间中的一个解)的集体学习过程，从任意初始群体出发，通过随机选择、变异和交叉过程，使群体进化学习到搜索空间中越来越好的区域。进化计算中选择过程使群体中适应性好的个体比适应性差的个体有更多的机会遗传到下一代中，交叉算子将父代信息结合在一起并他们遗传给下一代个体，而变异过程在群体中引入新的变种。进化计算包括遗传算法(evolutionaryalgorithm,EA)、进化策略(evo

3、lutionstrategy,ES)、进化编程(evolutionaryprogramming,EP)、遗传编程(geneticprogramming,GP)。遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一种数学仿真，是进化计算的一种最重要形式。遗传算法为那些那些难以找到传统数学模型的难题找出了一个解决方法。自从Holland于1975年在其著作《AdaptationinNaturalandArtificialSystems》中首次提出遗传算法以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，

4、并且在实际中已经得到了很好的应用。1.简单遗传算法的构成要素（1）染色体编码和解码方法在实现对一个问题用遗传算法之前，我们必须先对问题的解空间进行编码，以便使得它能够由遗传算法进行操作。解码就是把遗传算法操作的个体转换成原来问题结构的过程。常见的编码方法有：二进制编码、浮点数编码、格雷码等。以二进制为例：假设某一参数的取值范围是[A，B]，A＜B，我们有长度为l的二进制编码串来表示该参数，将[A，B]等分成2l-1个子部分，每个等分的长度为δ，则它能够产生2l种不同的编码。…=0　→　A…=1→　A+δ……=　→　B二进制编码的最大缺点是使得遗传算法

5、操作的个体位串太长，这容易降低遗传算法的运行效率，很多问题采用其他编码方法可能更有利。如对于函数优化问题，浮点数编码方法就更有效，而二进制编码方法不但容易降低遗传算法的运行效率，而且会产生精度损失。浮点数编码方法是指个体的每个染色体用某一范围内的一个浮点数表示，个体的编码长度就等于问题变量的个数。在实际运用遗传算法解决问题时，一般都需要根据具体的问题采用合适的编码方法，这样更有利于遗传算法搜索到问题的最优解。（2）适应度函数遗传算法在进化搜索中基本上不用外部信息，仅用目标函数也就是适应度函数为依据。适应度函数是用于度量问题中每一个染色体优劣程度的函数

6、，体现了染色体的适应能力。遗传算法的目标函数不受连续可微的约束且定义域可以是任意集合。但对适应度函数有一个要求就是针对输入可以计算出的能加以比较的结果必须是非负的。在具体应用中，适应度函数的设计要结合求解问题本身的要求而设计。因为适应度函数对个体的评估是遗传算法进行个体选择的唯一依据，因此适应度函数的设计直接影响到遗传算法的性能。对于很多问题，可以直接把求解问题的目标函数作为适应度函数使用，但也存在很多问题需要进行一定的转换才能使得目标函数可以用作遗传算法的适应度函数。（3）遗传算子遗传算法主要有三种操作算子：选择(selection)、交叉(cro

7、ssover)、变异(mutation)。选择算子选择算子根据个体的适应度函数值所度量的优劣程度选择下一代个体。一般地，选择算子将使适应度函数值较大的个体有较大的机会被遗传到下一代，而适应度函数值较小的个体被遗传到下一代的机会较小。一般常采用的选择算子是赌轮选择机制。赌轮选择算子的基本原理如下。令表示种群的适应度值之总和，表示群体中第i个染色体的适应度值，则第i个个体产生后代的能力正好为其适应度值与群体适应度值的比值。赌轮选择算子在个体数不太多时，有可能出现不正确反映个体适应度的选择过程，也就是说适应度高的个体有可能反而被淘汰了。为了改进赌轮选择算子

8、的这种缺点，有很多改进的交叉选择算子。如：最佳个体保存法、期望值方法、排序选择方法、联赛选择方法、排挤方法等