《遗传算法毕业论文遗传算法在实际数值函数优化问题中的应用研究其中以解决函数问题为例37951》由会员分享,可在线阅读,更多相关《遗传算法毕业论文遗传算法在实际数值函数优化问题中的应用研究其中以解决函数问题为例37951(35页珍藏版)》请在金锄头文库上搜索。
1、遗传算法求中文摘要:本文首先介绍遗传算法的历史背景,基本思想,对遗传算法的常见的编码解码方法进行了深入的阐述,并对算子选择方法进行深入分析和对比,在此基础上把遗传算法应用于求解复杂函数的极值计算。最后在MATLAB语言环境下编写程序,对求解函数的最大值进行了仿真,并对调试的结果进行了分析,得出了部分结论。关键词:遗传算法 最优解 算子选择 复杂函数 作者:xx xx 指导老师:xxxx xxUsing Genetic Algorithm to Solve Extreme Problem of Complex Function AbstractFirstly, the historical ba
2、ckground and basic idea of genetic algorithm are introduced in this paper. The common coding and decoding method of genetic algorithm are discussed too.Secondly, the selection method of genetic operator is analyzed and compared deeply, based on which genetic algorithm is used to solve extreme proble
3、m of complex function.Finally, with MATLAB software, the program is compiled and the maximum is sought out. At the end of the paper, the debugging result is analyzed and the conclusion is given. Keywords: Genetic Algorithm Optimal Solution Operator Selection Complex Function Written by : xx xx Super
4、vised by: xxxx xx 目 录第一章 绪论 (5)1.1 遗传算法生物学背景(5)1.1.1 遗传与变异(5)1.1.2 进化 (5)1.2 本文主要内容 (5)第二章 遗传算法简介 (6)2.1 遗传算法历史和发展(6)2.2 遗传算法的基本原理(6)2.3 遗传算法的特点(7)2.4 遗传算法的目的(7)2.5 遗传算法应用(8)第三章 遗传算法的参数和算子选择(10)3.1 遗传算法的数学理论(10)3.2 编码(11)3.2.1 编码方法 (11)3.2.2 编码原则 (13)3.3 个体适应度函数 (13)3.3.1 评价个体适应 (13)3.2.2 适应度尺度变换(14
5、)3.3 算子选择(14)3.3.1 选择运算 (14)3.3.2 交叉运算(16)3.3.3 变异运算(18)3.4 其他运行参数 (18)第四章 遗传算法求解复杂函数极值问题 (20)4.1 遗传算法的求解步骤(20)4.2 算例验证 (24)第五章 结论(28)参考文献(28)附录(程序)(29) 第一章 绪 论1.1遗传算法生物学背景生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。1.1.1 遗传与变异1、遗传世间的生物从其亲代继承特性或性状,这种生命现象叫遗传,研究这种生命现象
6、的科学叫做遗传学。遗传信息是由基因组成的,生物的各种性状由其相应基因来控制,基因是遗传的基本单位。细胞分裂具有自我复制的能力,在细胞分裂的过程中,其遗传基因也同时被复制到下一代,从而其性状也被下一代所继承。2、变异 细胞在分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新细胞就继承了旧细胞的基因,在进行细胞复制时,虽然概率很小,但也有可能产生某些复制差错,从而使DNA发生某种变异产生出新的染色体,从而表现出新的性状。1.1.2 进化 生物在其延续生存的过程中,逐渐适应于其生存环境,使得其品质不断得到改良,这种现象叫做进化。新的基因依据其与环境的适应程度决定其增殖能力,有利于生存环境的基因
7、逐渐增加,而不利于生存环境的基因逐渐减少,通过这种自然的选择,物种渐渐的向适应于生存环境的方向进化,从而产生优良的物种。1.2 本文主要内容 本文主要讨论遗传算法在实际数值函数优化问题中的应用,即对实际问题建模后求函数最大值的问题。遗传算法通过对群体所施加的迭代进化过程,不断的将当前群体中具有较高适应度的个体遗传到下一代群体中,并且不断的淘汰掉适应度较低的个体,从而最终寻求出适应度最大的个体。这个适应度最大的个体经解码处理之后所对应的个体表现型即为实际问题最优解或是最近似最优解第二章 遗传算法简介 2.1 历史与发展二十世纪六十年代,I.Rechenberg在他的演化战略中第一次引入了进化算法
8、的思想(起初称之为Evolutionsstragegie)。他的这一思想逐渐被其他一些研究者发展。遗传算法(Genetic Algorithms) 是John Holland 发明的,后来他和他的学生及他的同事又不断发展了它。终于,在1975年John Holland 出版了专著自然系统和人工系统中的自适应(Adaption In Natural and Artificial Systems)。1992年,John Koza 曾经使用遗传算法编出新的程序去做一些具体的工作。他称他的这种方法为“进化规划”(Genetic Programming,简称GP)。其中使用了LISP规划方法,这是因为这
9、种语言中的程序被表示为“分析树”(Parse Tree),而这种遗传算法就是以这些分析树为对象的。2.2 遗传算法的基本原理: 遗传算法GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。这里所指的某种结束准则一般是指个体的适应度达到给定的阀值;或者个体的适应度的变化率为零。图2-1
10、中表示了遗传算法的执行过程。图2-1 遗传算法基本原理2.3 遗传算法特点:(1) 遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因此具有良好的并行性。(2) 遗传算法只需利用目标函数取值信息,而无须梯度等高价信息,因而实用用于大规模高度非线形的不连续多峰值函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性。(3) 遗传算法的择优机制是一种“软“策略,加上其良好的并行性使其具有良好的全局优化性能和稳健性鲁棒性。(4) 遗传算法的可行解集是经过编码的,目标函数可解释为编码化个体的适应值因而具有良好的可操作性与简单性。2.4 遗传算法的目的典型的遗传算法CGA
11、(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题:考虑对于一群长度为L的二进制编码bi,i1,2,n;有 bi0,1L给定目标函数f,有f(bi),并且760F(BI) 同时 f(bi)f(bi+1)求满足下式maxf(bi)|bi0,1L 的bi。很明显,遗传算法是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串bi处,即求出最优解。2.5 遗传算法的应用 遗传算法已经在很多复杂问题(比如说NP-难题)、机器学习和简单的进化规划中得到了使用。遗传算法在一些艺术领域也取得了很大成就,比如说进化图片和进化音乐。 遗传算法的优势在于他的并行性。遗传算法在搜索空间中非常独立地移动(按照基因型而不是表现型),所以它几乎不可能像其它算法那样“粘”在局部极值点。 遗传算法更容易实现。一旦你有了一个遗传算法的程序,如果你想解决一个新的问题,你只需要针对新的问题重新进行基因编码就行。如果编码方法也相同,那你只需要改变一下适应度函数就可以了。当然,选择编码方法和适应度函数是一件非常难的问题。 遗传算法的缺点是它的计算时间太长。它们可能比其他任何算法需要的时间都长。当然,对于今天的高速计算机来说,这已经不是个大问题了。 为了让读者更好地了解遗传算法所