遗传规划

文章目录
  1. 1. 来龙去脉
    1. 1.1. 什么是进化算法
    2. 1.2. 什么是遗传规划
    3. 1.3. 遗传规划与遗传算法的关系
  2. 2. 主要内容
  3. 3. 主要研究问题
  4. 4. 应用领域
    1. 4.1. 进化算法应用
    2. 4.2. 遗传算法应用
    3. 4.3. 选用和实现
    4. 4.4. 性能、问题和改进
  5. 5. 参考文档

来龙去脉

在什么情况下,存在什么问题,遗传规划是从什么样的视角来解决问题的?(整体介绍,通常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)寻求其他有效的遗传算子,防止近缘杂交、过早收敛等弊病。

参考文档

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