文档介绍：遗传算法的概念
一种适应度函数的改进算法
小结<br****题
遗传算法(ic Algorithms,GA)是一种基于自然选择和基因遗传学原理的优化搜索方法。遗传算法的创立有两个目的: 一是抽象和严谨地解释自然界的适应过程; 二是为了将自然生物系统的重要机理运用到工程系统、计算机系统或商业系统等人工系统的设计中。遗传算法在计算机上模拟生物进化过程和基因的操作,并不需要对象的特定知识,也不需要对象的搜索空间是连续可微的,它具有全局寻优的能力。一些用常规的优化算法能有效解决的问题,采用遗传算法寻优技术往往能得到更好的结果。
有些问题采用常规的优化算法会陷入局部次优点,而采用遗传算法可以找到全局最优解。人们常把它用于许多领域的实际问题,如函数优化、自动控制、图像识别、机器学****等。目前,遗传算法正在向其他学科和领域渗透,正在形成遗传算法和神经网络或模糊控制相结合的新算法,从而构成一种新型的智能控制系统整体优化的结构形式。本章讨论遗传算法的基本原理、操作、模式理论和计算机实现问题; 在此基础上,探讨基于遗传算法寻优的软件编程方法、基于遗传算法神经网络辨识的软件开发,并给出了相应的程序及其程序剖析。
遗传算法的定义及特点 遗传算法是John H. Holland根据生物进化的模型提出的一种优化算法。自然选择学说是进化论的中心内容。根据进化论,生物的发展进化主要有三个原因,即遗传、变异和选择。
遗传算法的概念
遗传算法基于自然选择和基因遗传学原理的搜索方法,将“优胜劣汰,适者生存”的生物进化原理引入待优化参数形成的编码串群体中,按照一定的适配值函数及一系列遗传操作对各个体进行筛选,从而使适配值高的个体被保留下来,组成新的群体; 新群体包含上一代的大量信息,并且引入了新的优于上一代的个体。这样周而复始,群体中各个体适应度不断提高,直至满足一定的极限条件。此时,群体中适配值最高的个体即为待优化参数的最优解。
正是由于遗传算法独特的工作原理,使它能够在复杂空间进行全局优化搜索,具有较强的鲁棒性; 另外,遗传算法对于搜索空间,基本上不需要什么限制性的假设(如连续、可微及单峰等)。常规的优化算法,如解析法,往往只能得到局部最优解而非全局最优解,且要求目标函数连续光滑及可微; 枚举法虽然克服了这些缺点,但计算效率太低,对于一个实际问题常常由于搜索空间太大而不能将所有的情况都搜索到; 即使很著名的动态规划法,也遇到“指数爆炸”问题,它对于中等规模和适度复杂性的问题也常常无能为力。遗传算法通过对参数空间编码并用随机选择作为工具来引导搜索过程朝着更高效的方向发展。同常规优化算法相比,遗传算法有以下特点:
(1) 遗传算法是对参数的编码进行操作,而不对参数本身。遗传算法首先基于一个有限的字母表,把最优化问题的自然参数集编码为有限长度的字符串。 (2) 遗传算法是从许多点开始并行操作的,而不局限于一点,因而可以有效地防止搜索过程收敛与局部最优解。 (3) 遗传算法通过目标函数来计算适配值,而不需要其他推导和附加信息,从而对问题的依赖性较小。 (4) 遗传算法的寻优规则是由概率决定的,而非确定性的。
(5) 遗传算法在解空间进行高效启发式搜索,而非盲目地穷举或完全随机搜索。 (6) 遗传算法对于待寻优的函数基本无限制,它既不要求函数连续,也不要求函数可微,既可以是数学解析式所表达的显函数,又可以是映射矩阵甚至是神经网络等隐函数,因而应用范围较广。 (7) 遗传算法具有并行计算的特点,因而可通过大规模并行计算来提高计算速度。 (8) 遗传算法更适合大规模复杂问题的优化。 (9) 遗传算法计算简单,功能强。
遗传操作 1. 基本术语 (1) 位串: 群体中的个体也叫位串,如0110、 1100,其个体的位数为4。 (2) 群体: 一组位串,一组位串的个数可在4~30之间选择。 (3) 适应度函数:
(4) 选择概率:
概率最大的个体复制,概率最小的个体变异或被复制的替代,其余的位串交叉操作。
(6-2)