第8章 遗传算法.ppt

第八章遗传算法
遗传算法(ic Algorithm,简称GA)作为一种解决复杂问题的优化搜索方法,是由美国密执安大学的John Holland教授首先提出来的(Holland,1975)。遗传算法是以达尔文的生物进化论为启发而创建的,是一种基于进化论中优胜劣汰、自然选择、适者生存和物种遗传思想的优化算法。
遗传算法广泛应用于人工智能、机器学习、知识工程、函数优化、自动控制、模式识别、图像处理、生物工程等众多领域。目前,遗传算法正在向其它学科和领域渗透,正在形成遗传算法、神经网络和模糊控制相结合,从而构成一种新型的智能控制系统整体优化的结构形式。
遗传算法基本原理
GA的基本思想来源于Darwin的进化论和Mendel的遗传学说。Darwin的进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承,但后代又不完全同于父代,这些新的变化,若适应环境,则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来,这就是适者生存的原理。
遗传算法的由来
遗传算法基本原理
遗传算法的出发点是一个简单的群体遗传模型,该模型基于如下假设:
(1)染色体(基因型)由一固定长度的字符串组成,其中的每一位具有有限数目的等位基因。
(2)群体由有限数目的基因型组成。
(3)每一基因型有一相应的适应度(Fitness),表示该基因型生存与复制的能力。适应度为大于零的实数,适应度越大表示生存能力越强。
遗传算法的由来
遗传算法基本原理
复制(Reproduction)
复制(又称繁殖),是从一个旧种群( old population)中选择生命力强的个体位串(或称字符串)产生新种群的过程。或者说,复制是个体位串根据其目标函数(即适应度函数)拷贝自己的过程。根据位串的适应度值拷贝位串意味着,具有较高适应度值的位串更有可能在下一代中产生一个或多个后代。显然,这个操作是模仿自然选择现象,将达尔文的适者生存理论应用于位串的复制,适应度值是该位串被复制或被淘汰的决定因素。
遗传算法的基本操作
遗传算法基本原理
交叉(Crossover)
交叉是在两个基因型之间进行的,指其中部分内容进行了互换。

A = a1a2…al 和 B = b1b2…bl
若在位置i交换,则产生两个新的串
A′=a1…albi+1…bl 和 B′=b1…blai+1…al
遗传算法的基本操作
遗传算法基本原理
变异(Mutation)
若基因型中某个或某几个位置上的等位基因从一种状态跳变到另一种状态(0变为1或1变为0),则称该基因型发生了变异。其中变异的位置也是随机的。
遗传算法的基本操作
遗传算法基本原理
遗传算法的基本操作
遗传算法的基本步骤
遗传算法基本原理
(1)GA是对问题参数的编码(染色体)进行操作,而不是参数本身。
(2)GA计算简单,便于计算机编程,功能强。
(3)GA是从问题解的串集开始搜索,而不是从单个解开始,更有利于搜索到全局最优解。
(4)GA使用对象函数值(即适应值)这一信息进行搜索,而不需导数等其它信息。
(5)GA的复制、交叉、变异这三个算子都是由概率决定的,而非确定性的。
(6)GA算法具有隐含的并行性,因而可通过大规模并行计算来提高计算速度。
(7)GA更适合大规模复杂问题的优化,但解决简单问题效率并不高。
遗传算法的特点
遗传算法基本原理
图式H的长度δ(H)是指图式第一个确定位置和最后一个确定位置之间的距离。如H=**00*1*,则δ(H)=4。
图式H的阶○(H)是指图式中固定串位的个数。如H=**00*1*,则○(H)=3。
图式定理是GA算法的理论基础,它说明高适应值、长度短、阶数低的图式在后代中至少以指数增长包含该图式H的串的数目。原因在于再生使高适应值的图式复制更多的后代,而简单的交换操作不易破坏长度短、阶数低的图式,而变异概率很小,一般不会影响这些重要图式。
遗传算法的理论基础