遗传规划

来龙去脉

在什么情况下,存在什么问题,遗传规划是从什么样的视角来解决问题的?(整体介绍,通常10分钟左右)

什么是进化算法

进化算法,又称演化算法 ,是一个算法集合,包括遗传算法、遗传规划、进化策略和进化规划4种典型方法。进化算法借鉴了进化生物学的遗传、突变、自然选择以及杂交等现象,利用“优胜劣汰”,来处理最优化问题。

由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的,在相当长的时期里相互之间没有正式沟通。直到90年代,才有所交流。

他们发现彼此的基本思想具有惊人的相似之处,于是提出将这类方法统称为“进化计算” ( Evolutionary Computation ) 。

什么是遗传规划

遗传规划,又称遗传编程,是进化算法的一个分支,与遗传算法中每个个体是一段染色体编码不同,它的个体是一个计算机程序。

首先利用计算机随机生成的千百万个程序,然后根据一个程序完成给定的任务的能力来确定某个程序的适合度,应用达尔文的自然选择(适者生存)确定胜出的程序,计算机程序间也模拟两性组合,变异,基因复制,基因删除等代代进化,直到达到预先确定的某个中止条件为止。

遗传规划与遗传算法的关系

遗传规划是遗传算法的改进算法。

遗传算法使用字符串作为染色体去表达所研究的问题,而且字符串的长度常常是固定的。然而,现实中的问题往往很复杂,有时不能用简单的字符串表达问题的所有性质,于是就产生了遗传规划。遗传规划用广义的计算机形式表达问题,它的结构和大小都是可以变化的,从而可以更灵活地表达复杂的事物性质,更有利于算法收敛到全局最优解,同时也弥补了遗传算法在某些领域得不到有效应用的不足。

主要内容

基本概念(最好举例说明)、遗传规划描述、遗传规划实例、遗传规划特点等。(细节介绍,通常20分钟左右)

主要研究问题

利用文献法来总结各种问题的研究现状,把你阅读的文献(至少3篇)提前3天发到云盘中。(重点内容介绍,通常讲解20分钟左右)
a)编码问题:比如,在哪年由谁提出了怎样的编码方案?性能如何?主要特点是什么?主要用来解决哪些类问题等。
b)参数设置问题:比如,各种操作的参数选择方法等。
c)各种启发式实现方法:比如,有记忆的遗传规划等。
d)… …

应用领域

利用文献法来总结遗传规划各种领域的应用现状,把你阅读的文献(至少3篇)提前3天发到云盘中. (重点内容介绍,通常讲解20分钟左右),比如,
a)在哪些领域的哪些方面应用了遗传规划?
b)为什么选用这个算法?具体如何实现的?
c)性能如何?存在怎样的问题?改进方向如何?

进化算法应用

1、结构性优化。通常,工程技术的优化包括结构优化和参数优化。对于后者,人们已经成功地使用了许多方法,如运筹学、数理统计、有限元等数值计算。然而对于结构优化,还缺乏成熟、有效的方法。近年来,人们运用进化算法,成功解决了建筑框架结构、飞机结构设计、电网及管网等网络结构等结构型问题,充分显示进化算法在这一领域的广阔引用前景。

2、人工智能。进化算法继模糊数学、专家系统、人工神经网络之后,成为处理人工智能的又一个有力工具。许多研究工作者利用这种新技术,从事机器学习、自动程序设计、聚类分析、博弈对策等工作。在知识工程方面,进化算法发挥越来越重要的作用。

3、复杂问题的优化。当所要解决的问题具有非线性、多峰值、不确定性时,使用传统的优化方法常常不能奏效。进化算法由于是一种黑箱式的框架型技术,不要求有明确的因果关系数学表达式,因此它是解决这类问题的有力工具,可以解决诸如液体流动、气候变化以及军事战略等非线性动态系统问题。

4、复杂系统分析。多年来,人们应用进化算法从事聚类分析、模式识别、图像处理、调度组织等工作,将表面上杂乱无章的复杂事物条理化。对于这类复杂系统的分析和归纳,进化算法具有很大的引用价值。

5、综合应用。随着科学技术的发展,各种学科不断交叉渗透,相互促进。同样,进化算法也要和其他技术手段相结合,各自发挥特长,综合解决问题。例如,人们已将遗传算法和人工神经网络相结合,成功地解决了机器学习等问题。

由于进化算法具有广阔的应用范围,我们无法一一列举具体的应用领域,只能概括地指明应用方向。随着时间的推移,它的应用范围还会不断扩大。

遗传算法应用

1、函数优化
是遗传算法的经典应用领域;

2、组合优化
实践证明,遗传算法对于组合优化中的NP完全问题非常有效;

3、自动控制
如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;

4、机器人智能控制
遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;

5、组合图像处理和模式识别
目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;

6、人工生命
基于遗传算法的进化模型是研究人工生命现象的重要理论基础,遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力;

7、遗传程序设计
Koza发展了遗传程序设计的慨念,他使用了以LISP语言所表示的编码方法,基于对一种树型结构所进行的遗传操作自动生成计算机程序;

选用和实现

1、为什么选用遗传规划?
为了解决结构性优化问题等传统方法解决不了的问题。

2、实现的例子
以曲线拟合为例,说明遗传规划的基本原理。图1-5的曲线表示实验的结果,现在要确定实验结果的的函数关系y=f(x)。

遗传规划的工作原理大致如下:
(1)选择初始结构。采用随机产生的方法,假设y=f(x)的表达式有下述四种:
$$1) y = A + Bx$$
$$2) y = A + Bx + Cx^2$$
$$3) y = xsinx$$
$$4) y = Dxsinx$$

(2)计算适应度。将不同的$x_i$带入四种初始表达式中,从而得出一组不同$y_j$,将计算所得的$y_j$与实验数据$y_i$相比较,可以衡量初始表达式的优劣。假设第3种表达式最佳,第1种表达式最差。

(3)复制。根据优胜劣汰的原则,复制效果最佳的第3种表达式,淘汰效果最差的第1种表达式,于是,新一代的表达式由下述方程组成:
$$1) y = xsinx$$
$$2) y = A + Bx + Cx^2$$
$$3) y = xsinx$$
$$4) y = Dxsinx$$

(4)交换。为了产生新的表达式,需要使用交换。采用随机选择的方法,假设第2、3种表达式进行交换,交换位置在第一项,则新的表达式为:
$$1) y = xsinx$$
$$2) y = x + Bx + Cx^2$$
$$3) y = Asinx$$
$$4) y = Dxsinx$$

(5)突变。在遗传规划中也可以采用突变产生新个体。例如,将表达式中的$sinx$变为$cosx$,不过,遗传规划中的突变远不及在遗传算法中那样重要。

上述(2)~(5)反复执行,使函数表达式y=f(x)不断变化,逐步得到所要求的表达式。

性能、问题和改进

1、性能
没有找到具体性能评估数据,猜测是用时间和适应度两方面进行衡量。

2、问题
(1)求解的是一个描述问题的程序(或者说是一个算法)。
(2)通常用树型结构来表示,描述相对复杂。
(3)每一代的个体的长度(深度)一般是不同的,即使在同一代中的个体之间的长度(深度)也是不同的。
(4)所消耗的资源是不可控的(这里所指的不可控是指不能精确的描述),需要消耗大量的内存空间,因而每一代的进化都比较慢。

3、改进
(1)确定初始群体规模的方法的改进。
(2)编码技术和程序表达技术的改进。
(3)复制、交换、突变等遗传操作的改进。
(4)适应度的表达和计算的改进。
(5)寻求其他有效的遗传算子,防止近缘杂交、过早收敛等弊病。

参考文档

进化算法
遗传算法
遗传编程

0%