第四章 节 ：遗传算法 .ppt

第四章 遗传算法;目 录;目 录;4.1 引言;遗传算法(Genetic Algorithm,GA)就是根据生物进化思想而启发得出的一种智能理论和方法. 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法,是通过对生物进化的归纳和模拟得到的一种仿生算法. GA在本质上是一种不依赖具体问题的直接搜索方法,是一种具有普适性的优化方法. GA的发展历程为: 1965年,Michigan大学的Holland首次提出了人工遗传操作的重要性,并把这些应用于自然系统和人工系统中. 1967年,J.D.Bagley在他的论文中首次提出了GA这一术语与概念,并讨论了GA在自动博弈中的应用.;GA与其它优化方法相比,具有如下特点: GA不是直接作用在参变量集上, 而是利用参变量集的某种编码; GA不是从单个点, 而是在群体中从多个点开始搜索; GA利用适应值信息, 无需导数或其它辅助信息; 因此对优化问题(函数)的限制较弱,灵活,通用性(普适性)强,有着较广泛的应用领域. GA利用概率转移规则, 而非确定性规则. GA在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜索，效率优于其它算法。;GA的优点: 较容易的和其它方法结合 避免陷入局部最优解 即使在较短的有限时间内,也能获得较好的次优解、满意解. 鲁棒性佳 对优化问题的初始条件(状态)依赖性小。 抗干扰性强。 具有并行计算的特点，可提高计算速度;GA的不足: No guarantee for optimal solution within finite time Weak theoretical basis GA能解决的问题: 优化 NP完全 高度复杂的非线性问题;近年,GA在各应用领域中得到极大重视,并广泛应用于各领域的优化、搜索、问题求解中,并在 模式识别、 NN、 图像处理、 机器学习、 工业优化控制、 自适应控制、 生物科学、 社会科学 等方面都得到应用.;当前在AI研究中,人们认为“GA、自适应系统、细胞自动机、混沌理论与AI一样,都是对今后十年的计算技术有重大影响的关键技术”.;4.2 GA的基本概念;4.2.1 Darwin进化论及进化系统模型;物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化. 在环境变化时,只有那些能适应环境的个体特征方能保留下来.;4.2.1 Darwin进化论及进化系统模型;自Darwin以来的新进化学说强调: 个体是基本的选择目标; 随机过程在进化中起重大作用,遗传变异大部分是偶然现象; 进化是在适应中变化的,形式多样,不仅是基因的变化; 选择是概率型的,而不是决定型的.;4.2.2 Mendel遗传学说;4.2.2 Mendel遗传学说;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.2.3 GA的基本概念与术语;4.3 GA的原理;4.3 GA的原理;4.3.1 GA的目的;4.3.1 GA的目的;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;例如有2个父代个体 S1=100|101 S2=010|111 若随机选择它们的左边3位进行交叉操作,则产生的子代为 S1=010|101 S2=100|111;4.3.2 GA的基本原理;例如有2个父代个体 S1 S2若屏蔽字为1101110,则产生的子代为 S14.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.2 GA的基本原理;4.3.3 GA的算法过程;4.3.3 GA的算法过程;4.3.3 GA的算法过程;4.3.3 GA的算法过程;4.3.3 GA的算法过程;4.3.3 GA的算法过程;4.4 GA的应用;4.4.1 GA的特点;4.4.1 GA的特点;4.4.1 GA的特点;4.4.1 GA的特点;4.4.1 GA的特点; GA在应用中最关键的问题有如下3个: (1) 串的编码方式 这本质是问题编码. 一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串. 串长度及编码形式对算法收敛影响极