集训队论文1999-2009 集训队2002论 张宁 张宁_第1页
集训队论文1999-2009 集训队2002论 张宁 张宁_第2页
集训队论文1999-2009 集训队2002论 张宁 张宁_第3页
集训队论文1999-2009 集训队2002论 张宁 张宁_第4页
集训队论文1999-2009 集训队2002论 张宁 张宁_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、遗传算法的特点及其应用,省、市:上海市学校:复旦附中姓名:张宁,IOI2002合宿论文,目录,遗传算法的基本概念简单的遗传算法选择,交换,变异遗传算法应用案例子定径套和问题TSP (旅行者)问题结语,遗传传统数学上可能难以解决,也可能明显无效简单的遗传算法,GA将可能的解作为一个向量查询密码,称为染色体,向量的各要素称为基因。 所有染色体构成群体。 每次染色提取都用规定的目标函数进行评价,根据其结果给出适应度的值。 在算法开始时首先随机产生几条染色体,补正其适应度,根据适应度对各染色体进行选择、交换、变异等遗传操作,去除适应度低的染色体,保留适应度高的染色体。 因为新组的成员是上一代组的优秀者

2、,所以总体上比上一代优秀。 GA重复迭代直到满足某一预定的优化指标。 上述GA的动作过程可以用图1简单地说明。 在选择、选择运算中比较普遍的一种是适应度比例法。 实际上,适应度的值可以看作其权重,选择权重大的一方的概率也大。 与各染色体的适应度成正比。 某染色体被选择的概率是,式中的xi是与种群中第I条染色体相对应的数字列,f(xi )是第I条染色体的适应度值,是种群中所有染色体的适应度值的和。 显然,这种方法要求染色体的适应度为正值。 交换、复制操作可以从旧的种群中筛选出优秀者,而不能构建新的染色体,因此遗传算法的缔造者提出了交换操作。 即,通过在匹配定径套中选择2条染色体,随机选择1点或多

3、点交换点的位置,交换父母的染色体交换点右侧的部分,能够得到2个新的染色体数字串。 变异,变异演算被用于模拟生物在遗传环境中的各种偶然因素造成的基因变异,使基因值以较小的概率随机变化。 在二进制代码了染色体的系统中,将有染色体的基因随机地从1变更为0,或者从0变更为1。 根据变异操作,能够在尽可能大的空间进行探索,能够得到高质量的最佳解。遗传算法的应用实例、子定径套和问题TSP (旅行者)问题、子定径套和问题、GA在子定径套和问题上的应用子定径套和问题SUBSET_SUM :给出正整数集合s和整数t,判断是否存在s的子定径套,将其s的整数和设为t。 我知道这个问题是NP-完全的问题。 在实际应用

4、中,经常会优化子定径套和问题。 在这种情况下,找到s的子定径套s,使其和不超过t,但尽量接近t。 用遗传算法解决亚定径套和问题。 每个染色体可以用n二进制位的二进制数字表示。 每个二进制位用0、1表示是否属于子定径套。 如果设染色体表示的子定径套的元素体与给定的t之差为适应度,即染色体x的第1位为xi,表示的元素体的值为Si,则由于适应度的相对差小,所以适应度非常接近,难以区别染色体的优劣,遗传进化非常慢,f(x )有可能成为负值,所以还需要适应度函数f 子定径套和问题可以用前面介绍的适应度比例法来选择,但偶然发现优秀染色体上没有子孙的可能性。 因此,这里使用确定性选择方法来校正该组中各个串的

5、生存概率,然后校正所期望的复制数ei=Ps*n。 式中,n是群体中染色体的数量。根据ei的值对每个染色体列分配复制数。 交换演算与上述相同,但如果进行单点交换,则两染色体交换时产生的差异过大,遗传变得不稳定,优秀的染色体有可能无法遗传给下一代。 因此,可以采用多点交换。 在变异运算的情况下,注意变异概率的可取值即可,但具体的算法如上所述。 子定径套和问题,本问题的一些数值可取如下:种群长度(染色体个数):20选择概率: 0.9变异概率: 0.1终止条件:目前最优解在100代遗传后也不变,或取了最优解,TSP (旅行者)问题这是典型的NP-完全问题传统的解法对此效果不大,所以我们要用遗传算法来解

6、决这个问题。 TSP (旅行者)问题是,我们首先采用十进制查询密码,每条染色体由按一定顺序排列的n个城市的号码组成,表示了可能的旅行路线。 适应度是与1个旅行路径对应的距离,路径越短染色体适应度越高。 例如,设N=10,城市代码为1到10。 例如,种群中的染色体: 284105173692表示旅行路径284105173692的总路径长度,能够将最小化目标函数转换为以最大值为目标的适应度函数,cmax能够确定是进化过程中的路径长度的最大值,或者f(x )为正此处的交换演算与以前不同,由于是2条染色体,如果进行简单的交换演算,染色体所表示的路径中有可能重复经由同一个城市,即同一染色体中的2条基因具

7、有同一个城市编号。 因此,需要改进交换运算。 可采用部分一致交换运算(PMX )。 当然,也可以不进行交换运算而直接进行变异运算,这是因为本例中的变异运算本暗示了交换的意思。 变异操作与二进制代码时不同,从群体中随机抽出1个染色体,随机抽出2个基因,使两者交换,即城市的顺序相反。 算法的主要部分已经讨论完毕,还有一点需要提出来。 由于遗传算法是不断优化的搜索算法,我们可以用贪婪的算法建构初始群。 TSP (旅行者)问题、主题中的一些数值可取如下:种群长度(染色体个数):20变异概率:0.1终止条件:目前的最佳解在100代遗传后也不变。 通过遗传算法的应用实例,两个例题,我们将遗传算法扩展到原来

8、的简单定义,介绍一些高级遗传算法在具体例子中的应用,以打开思想的局限性为目的,不仅仅在原来的简单定义下写文章,还可以对一盏茶发挥想象,对于不同的问题, 在遗传算法框架下使用合理的算法,可以发挥遗传算法的优点来解决问题。 结束语、遗传算法的原理虽然简单,但如何很好地运用遗传算法并不是一个简单的问题,理论必须现实,对于不同的问题,遗传算法必须加以少许变化,遗传算法必须与已有的优化算法相结合,单独地处理遗传算法和已有的优化算法本文的主要目的还是初步了解遗传算法,有助于大家深入实践。 希望通过本文的指导,能够在各个方面运用遗传算法。图1、多点交换,在本例中使用多点交换,仅进行2点交换即可,但实际上2点交换类似于单点交换。 设置两个母染色体a和b:a:10100101110 b:0100110110001交换点为a:10100|10010|1110 b:01001|11011|0001,则交换的结果为a:101001101110 b:0100110 部分重合交换运算在父母的染色体列上分别生成2个交换点,将这些个的2个点之间的区域定义为匹配区域,然后用对应匹配置换2个匹配区域中的基因。 例如,父母染色体列用a:28410*573*6b:5671*1023*94的符号“

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论