文档介绍：遗传算法(ic Algorithm)
Keynote :尤志强
遗传算法与模拟退火算法一样是为解决组合优化问题而提出!
人工智能在信息处理和解决组合爆炸方面遇到的困难越来越明显迫使寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法,基于生活进化论的遗传算法被提出!
遗传算法
遗传算法简称GA(ic Algorithms)是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。
遗传算法是以达尔文的自然选择学说(适者生存)以及Mendel遗传学说(基因遗传原理)为基础发展起来的。
算法思路: GA将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的一代代不断进化,包括复制、交叉、变异等操作,最终收敛到“最适应环境”的个体,从而求得问题的最优解或满意解。
特点:隐含并行性和全局解空间搜索
GA的应用领域:机器学习、模式识别、图像处理、神经网络、优化控制、组合优化等
遗传算法中的自然法则
自然选择学说包括以下三个方面:
(1)遗传:这是生物的普遍特征,亲代把生物信息交给子代,子代总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳定存在。
(2)变异:亲代和子代之间以及子代的不同个体之间的差异,称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。
(3)生存斗争和适者生存:具有适应性变异的个体被保留下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,性状逐渐逐渐与祖先有所不同,演变为新的物种。
Mendel遗传学说
遗传以密码方式存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以,每个基因产生的个体对环境具有某种适应性。
遗传算法中的自然法则
遗传算法将“优胜劣汰,适者生存”的生物进化原理引入优化参数形成的编码串联群体中,按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。遗传算法的算法简单,可并行处理,并能得到全局最优解。
遗传算法中的相关概念
遗传算法用到各种进化和遗传学得概念。以下是一些主要的概念:
(1)串(String):它是个体(Individual)的形式,在算法中为二进制串,并且对应于遗传学中的染色体(Chromosome).
(2)群体(Population):个体的集合称为群体,串是群体的元素。
(3)群体规模(Population Size):在群体中个体的数量称为群体规模,又称群体的大小。
(4)基因(Gene):基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,则其中1,0,1,1这四个元素分别称为基因,它们的值称为等位基因。
(5)基因位置(Gene Position):一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左边向右计算,例如在串S=1011中,(Locus).
(6)适应度(Fitness):表示某一个体对于环境的适应程度。
图1 解空间与生物空间的对应
遗传算法的基本流程
遗传算法是一类随机优化算法,但它不是简单的随机比较搜索,而是通过对染色体的评价和对染色体中基因的作用,有效地利用已有的信息来指导搜索有希望改善优化质量的状态。
该算法包括5个基本要素:变量编码、初始群体的设定、适应度函数的设计、遗传操作设计和参数设定。
(1)编码
通过编码将解空间的数据表示成遗传空间的基因型串结构数据。编码一般有二进制编码和实数编码。对于问题解X,X=(x1,x2,…,xn),二进制编码是把X用0,1串表示,而实数编码是把X用一向量表示,即X=(x1,x2,…,xn),xi是实数。编码设计应适合要解决的问题,应考虑完全性、封闭性、可扩展性和复杂性等。完全性是指分布在所有问题域的解都可能被构造出来;封闭性是指每个基因编码对应一个可接受的个体,不产生无效的个体;可扩展性是指对于具体问题,要考虑编码形式与大小影响下的解码时间;复杂性是指整体考虑基因型的结构复杂性、解码复杂性、计算复杂性等。
(2)初始群体的生成
在遗传算法处理流程中,继编码设计后的任务是初始群体的生成,并以此为起点一代代进化直到满足某种进化停止准则终止进化过程,初始群体也称为进化的初始代,即第一代。初始群体的个体一般可采用随机产生,一般群体可表示为Z={Xi|Xi=(xi1,xi2,…..xin)},i=1,2,…N},即Xi是染色体或个体,xi是基因或位。若是实数编码,则xi
遗传算法的基本流程