遗传编程(Genetic Programming,GP)是利用遗传算法的进化原理来自动进化出计算机程序的一种开放式搜索算法。20世纪50年代末期,Friedberg在进化计算编程方面进行了最早的研究,通过随意地修改程序和测试已经修改的程序,在研究一些复杂程序上取得了成功。这表明了计算机自动解决问题的可行性[43]。1985年,Nichael Lynn Cramer首先提出将遗传算法运用于树形程序。一些重要的概念(包括程序的树形结构、终止要求、子树交叉等)被提出。1989年,美国斯坦福大学的Koza教授基于遗传算法提出了遗传编程的概念并对其进行了深入的研究[44]。自20世纪90年代以来,Koza利用1000台350MHz的PC机自动进化出30多项模拟电子电路专利。这些能自动设计出具有专利水平的设计成果使得基于遗传编程的“自动发明机器”成为新一代计算智能的代表。2000年,Koza进化出了超越传统PID控制器的控制器,并成功申请专利[45,46]。2004年,国际遗传与进化计算会议颁发了首届全球挑战人类设计锦标赛,获奖成果包括利用遗传编程实现的量子电路设计、美国航天宇航局(NASA)进化出的性能优异外形奇特的卫星天线、康奈尔大学Lipson进化出的能够实现直线运动的连杆机构、美国喷气推进实验室进化出的特殊的电子电路[47]。
当前,基于遗传编程的自动设计的成功应用主要集中于模拟电路设计和控制器[48,49],正在向工业化电路的自动设计方向发展。Cadence公司已经在开始这方面的初步研究。在控制器设计方面,Koza已经成功进化出具有实际应用水平的控制器[50]。在利用遗传编程进行机电产品设计方面,美国密歇根州立大学在美国国家自然科学基金的资助下于2000年以来开展了基于功率键合图和遗传编程的机电产品自动进化设计的研究,提出了一些机电产品设计方法的新概念,并对MEMS(微机电系统)和老式机械打印机[51]的设计方法进行了局部优化。
国内关于遗传编程的研究起步较晚,但研究成果颇丰。常州工学院的查志琴和上海交通大学的高波等人针对遗传编程的特点,提出了一个通用的概念模型,以虚拟机来提高遗传编程的效率[52]。西安交通大学的李良敏等提出了一种基于遗传编程和支持向量机的故障诊断模型,该模型利用遗传编程对传统的时域指标进行特征选择和提取,得到更能反映信号本质的特征,与其他特征组合后作为识别特征输入多类支持向量机,实现了对机器不同类型故障的识别[53]。北京化工大学的白焰采用遗传编程方法解决非单调非线性系统的辨识问题,在对象的结构和参数未知的情况下,先进行参数恒定下的辨识,再进行在运行期间非线性环节参数发生变化的系统辨识。贵州大学的李少波等提出一种基于遗传编程和功率键合图的机电产品自动设计方法,该方法具有开放式的拓扑设计空间搜索能力,并同时具有参数设计能力[54]。2007年,中国台湾交通大学的J.Yeh等[55]采用遗传编程技术解决信息检索领域中排序函数的学习问题,Yeh在其工作中采用传统的树状结构个体来表示排序函数,运用了直接复制、交叉繁殖和变异等三种遗传操作,并用评价标准MAP值作为适应度函数。
在GP算法理论研究的基础上,它的应用主要有以下几个方面:
(1)系统建模和模式识别 GP算法是一种先进的数据挖掘方法,可以使用GP进行特征分析和数据分类,特别是对于特征提取的数据量非常大或者特征变量间关系不明确的情况。(www.xing528.com)
(2)过程控制和机器人控制 在这类系统中,大多数控制对象是复杂的,难以建立输入与输出变量间明确的解析表示。GP算法起源于对人工自适应系统的研究,它可以解决这些现有方法很难解决或不能解决的控制问题。
(3)组合优化 优化问题是GP算法的经典问题,随着问题规模的扩大,组合优化问题的搜索空间急剧扩大,目前常用的枚举法很难或者甚至不可能得到精确最优解。对于这类复杂问题,GP算法是寻求全局满意解的最佳方法之一。
(4)组合智能算法 与其他智能算法结合,弥补传统智能算法的不足。比如GP算法与模糊逻辑结合,利用GP算法训练模糊规则、学习隶属函数等,减少模糊推理过程中人为因素的影响,改进模糊系统的性能。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。