1、I 本科毕业设计开题报告 （2012 届）届） 论文题目 带互动界面的遗传算法演 示系统 1 一、选题的背景与意义 1.1 研究开发的目的 遗传算法的应用无论是用来解决实际问题还是建模，其范围不断扩展，这主 要依赖于遗传算法本身的逐渐成熟。近年来，许多冠以“遗传算法”的研究与 Holland 最初提出的算法已少有雷同之处，不同的遗传基因表达方式，不同的交 叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但这些改进方法 产生的灵感都来自于大自然的生物进化，可以归为一个“算法簇” 。人们用进化 计算（EC）来包容这样的遗传“算法簇” 。它基本划分为四个分支 1：遗传算法 （GA） 、进化规
2、划（EP） 、进化策略（ES）和遗传程序设计（GP） 。有些学者甚至 提出，进化计算是人工智能的未来。其观点是，虽然我们不能设计人工智能（即 用机器代替人的自然智能） ，但我们可以利用进化通过计算获得智能 2。目前， 进化计算与人工神经网络、 模糊系统理论一起已经形成一个新的研究方向计算 智能（computational intelligence） 。人工智能已经从传统的基于符号处理的符号 主义， 向以神经网络为代表的连接主义和以进化计算为代表的进化主义方向发展 3。 遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究， 广泛应用于自动控制、计算科学、模式识别、智能故障诊断管理科
3、学和社会科学 领域，适用于解决复杂的非线性和多维空间寻优问题。利用遗传算法的搜索过程 不受优化函数的连续性约束，也没有优化函数的导数必须存在的要求；遗传算法 采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速 度；遗传算法更适合大规模复杂问题的优化。鉴于遗传算法有以上这些优点，所 以对它的研究将具有重要意义。可以预料在不远的将来，随着理论研究的不断深 入和应用领域的不断拓广，遗传算法将取得长足的进展。 1.2 国内外研究发展现状 在二十世纪 60 年代， 美国 Michigan 大学的 Holland 教授及其他一些科学家 分别独立地通过对自然和人工系统的研究，提出了遗传算
4、法的基本思想。1975 年，Holland 教授出版了关于遗传算法的经典著作Adaptation in Nature and Artificial System ，标志着遗传算法的正式诞生。Holland 教授在文献中提出的 浙江工业大学本科毕业设计开题报告 2 遗传算法后来被人们称为简单遗传算法(SGA)。简单遗传算法的个体采取二进制 编码方式，主要由交换算子产生新的个体，通过选择操作体现“优胜劣汰”的自 然选择机制。简单遗传算法以图式定理或称型式定理、模式定理为理论基础，认 为遗传算法具有隐含并行性和全局收敛性。 这一结论现在被普遍认为是值得怀疑 的。经过近三十年的发展，遗传算法的理论研究
5、取得了很大进展，已有不少学术 专著出版，有关人工智能的著作中一般也有关于遗传算法的章节，其应用研究更 是取得了辉煌的成就。近年来，有不少博士学位论文对遗传算法的理论和应用作 了专题论述。现在，遗传算法的实际应用已经渗透到了各行各业。 遗传算法是建立在自然选择和群体遗传学基础上的一种非数值计算优化方 法 4。遗传算法将问题的解表示成字符串，并把这样的字符串当作人工染色体或 称为个体，多个个体构成一个群体。随机产生若干个个体构成初始群体，通过对 群体的不断进化，利用“优胜劣汰”的自然选择机制，使群体中的个体不断朝着 最优解的方向移动，最终搜索到问题的最优解。个体通过遗传算子的作用生成子 代个体。通
6、过定义个体的评价函数，称为适应度函数来评价个体的优劣。个体的 适应度反映个体适应环境的能力，适应度大的个体生存能力强。按照自然选择的 基本原理，适应度越大的个体被选择用来繁殖后代的机会越大。遗传算法是模拟 遗传行为的智能算法，而遗传算法的理论研究内容主要包括染色体的编码方法、 遗传算子、算法的运行过程、遗传控制参数的选择、算法的收敛性和收敛速度以 及遗传算法的改进和与其它方法的综合等 5。 遗传算法虽然有诸多的优点， 也已在实际中得到了大量应用 ,但它也存在着 许多急待解决的问题。例如，如何进行算法本身的参数优化选择 67，即对群体 的规模、交换概率和变异概率进行优化选择。因为实践发现这些参数的选取直接 关系着 GA 求解问题的成败。如何避免算法过早收敛的产生 8，过早收敛是指 GA 在执行过程中会出现群体中的个体过早地在一个非最优点上达到完全相同或接 近完全相同的现象。一旦出现该现象,利用 GA 就不能求得问题的全域最优解。对 于动态数据， 用遗传算法求最优解比较困难， 因为染色体种群很可能过早地收敛， 而对以后变化了的数据不再变化。针对这一问
