遗传算法介绍及应用.docx

遗传算法的介绍及应用 目录TOC\o1-5\h\z \o CurrentDocument 1遗传算法介绍2 \o CurrentDocument 1.1遗传算法的产生和发展2 \o CurrentDocument 1.2遗传算法的基本求解步骤2 \o CurrentDocument 1.2.1编码2 \o CurrentDocument 1.2.2初始化：3 \o CurrentDocument 1.2.3估计适应度：3 \o CurrentDocument 1.2.4再生（选择）：3 \o CurrentDocument 交叉：3 \o CurrentDocument 变异：3 \o CurrentDocument 重复：3 \o CurrentDocument 2遗传算法的应用例子4 \o CurrentDocument 2.1编码4 \o CurrentDocument 2.2初始化4 \o CurrentDocument 2.3计算适应度5 2.4再生（选择）5 \o CurrentDocument 2.5交叉5 \o CurrentDocument 2.6变异6 \o CurrentDocument 3遗传算法解决TSP的例子7 \o CurrentDocument 3.1TSP问题描述7 \o CurrentDocument 3.2遗传算法用于TSP问题8 \o CurrentDocument 3.2.1编码表示8 \o CurrentDocument 3.2.2初始化群体和适应度函数及其终止条件的设定8 \o CurrentDocument 3.2.3选择算子9 \o CurrentDocument 3.2.4交叉算子9 \o CurrentDocument 3.2.5变异算子10 \o CurrentDocument 3.2.6TSP问题的总结10 1遗传算法介绍 遗传算法(geneticalgorithms,GA)是一种模拟自然选择和遗传机制的寻优方法，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。 1.1遗传算法的产生和发展 50年代末60年代初，生物学家Fraser试图通过计算的方法来模拟生物界〃遗传与选择〃的进化过程，这便是GA的雏形。受此启发，Holland教授认识到自然遗传可以转化为人工遗传算法。1967年Bagley在其博士论文中首次提出了〃遗传算法〃这一术语。1975年，Holland出版了《自然与人工系统中的适应性行为》。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理，从而奠定了遗传算法的理论基础。20世纪80年代初，Holland教授实现了第一个基于遗传算法的机器学习系统一分类器系统(ClassifierSystem简称CS)，开创了基于遗传算法的机器学习的新概念。l992年，JohnR.Koza出版了专著《遗传编程》，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向。 1.2遗传算法的基本求解步骤1.2.1编码： 确定用何种码制，然后将问题参数编码形成基因码链，每一个码链代表一个个体，表示优化问题的一个解。 1.2.2初始化： 随机产生一个规模为P的初始种群，其中每个个体为一定长度的码链，该群体代表优化问题的一些可能解的集合。 1.2.3估计适应度： 计算种群中每个个体的适应度，适应度为群体进化时的选择提供了依据。一般来说适应度越高，解的素质越好。适应度函数可以根据目标函数而定。 1.2.4再生（选择）： 根据每个个体的相对适应度，计算每个个体的再生次数，并进行再生操作，产生新的个体加人下一代群体中，一般再生的概率与其适应度成正比。 1.2.5交叉： 从种群中随机选择两个染色体，按一定的概率进行基因交换，交换位置的选取是随机的。 1.2.6变异： 从种群中随机地选择一个染色体，按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋于的，变异算子则保证了算法能搜索到问题空间的每一点，从而使算法具有全局最优性，它进一步增强7GA的能力. 1.2.7重复： 若发现最优解，则算法停止，否则转3,对产生的新一代群体进行重新评价、选择、交叉、变异操作，如此循环往复，使群体中最优个体的适应度和平均适应度不断提高。其流程图如下： ］编码,生成初始种群 计算与评价种群中个体