利用c语言实现遗传编程1

《利用c语言实现遗传编程1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com周俊峰遗传编程是一个与人工智能相关的、新的形式，它基于达·树形处理程序存在于一些高级语言中．也就是说．现有尔文的进化、遗传思想发展而来。有关遗传编程最早的著作是的一些高级语言可以对树形结构进行操作。JohnKoza的(GeneticProgramming))-书．书中描述了一套用于1．2遗传编程的操作符(operator)随机修改已有LISP字符串的LISP程序集合。本文试图向读者清楚地介绍遗传编程的范例，及其在C语言中的实现。遗传编程使用四种通用的操

2、作符来实现计算机程序的进化，它们是：交叉(Cr0SS0Ver)、再现(rePr0duCti0n)、转变1．遗传绾程(mutation)、倒置(inversion)。1．1什么是遗传编程?(1)交叉(crossover)Koza认为”交叉”以及沿续其后的”再现”是两个最重要的遗传编程的许多理论与遗传算法是一样的．同样都是通过遗传操作符。交叉保证了程序群体的遗传多样性。与遗传算法遗传操作符(genetiCoperators)应用了达尔文的”适者生存中的交叉功能类似．遗传编程中的交叉行为是在两个程序中进(

3、survival-of—the—fittest)”理论：但是仍有许多不同之处。遗传编行的，并会产生两个子程序。具体地说．在每个程序中任意选取程所使用的结构与遗传算法的编码字符串就大相径庭。图1描两个结点，将以这两个结点为根的”子树”进行交换．从而产生述了一个遗传编程的简单结构。两个新的程序。这些新程序将成为后代程序的一部分并被评对于这个树形结构．其等价的LISP表达式为(+12(IF(>估，见图2。TIME10)34)。需要注意的是：(2)再现(reproduction)·当前．它采用了更为灵活、清

4、晰的可变分层结构．而不”再现”是遗传编程中第二个主要的操作．主要是将当前程是一维字符结构；序中选定的成员拷贝到后代程序中。Koza对于使用交叉、再现操·该结构由一些简单函数组成．这些函数可以通过使用作对群体收敛性的影响有一段说明：”⋯⋯在遗传编程中．当个一种高级语言很容易的被编译出来：体复制它自身的时候一般会产生两种不同的后代⋯⋯这点与达尔文的再现操作会导致一种收敛趋势相似：但是．不同的是．在遗传编程中由于交叉操作会导致群体多样性结果．从而平衡了再现操作的收敛作用．因此在遗传编程中．群体的收敛是不可

5、能的。”(3)转变(mutation)在遗传算法中．”转变”是一个重要的操作．它为群体的繁殖提供了多样性的保证。然而．Koza却指出．在新的环境中．”转变”已经不再是重要的操作了因为群体中个体的动态的大小和形态已经使其有了差异．而且基于它，整体也不可能收敛．因此．”转变”可以被认为是”交叉操作的变异。图1一个简单的树形结构●维普资讯http://www.cqvip.com(4)倒置(inversion)实现遗传编程的原因，下面列举C语言可能会被视作一种不理想的构建遗传编程平台的工具的一些因素：Koz

6、a说明了倒置”操作的作用还没有被最后证明，所以这里将不对其进行介绍。·C语言缺乏LISP语言的解释特性，不易于表达；·编写能够产生其他代码或者能够在自身代码上进行操1．3分配一个适应值作的C代码实际上是非常困难和烦琐的：现在，我们仅使用基本的交叉、再现两种操作来实现遗传·另一个主要的缺点就是C语言缺乏自动垃圾回收和内编程，但是，如何为这两种操作选择合适的个体呢7我们还没有存分配的功能。这将会成为一个障碍，因为群体成员不断变化，切实可行的方法。幸运的是，遗传算法为我们介绍了一种度量这会使得C语言的实现

7、变得非常困难。方法：适应性(fitness)。我们必须确定这些个体在解决给定问题但是，C语言是一种编译语言。它在实现上又能提供许多方上的能力和适应程度。由于有了遗传算法，”交叉”和”再现”操面的优势：作不再与适应性的实际评估有关，从而使得遗传编程的操作成为一个独立的问题。·更快的性能：它可以在运行速度和程序大小上提供更优的性能。通常，我们所编写的程序要占用约1M一2M内存，而适应性的度量是一个相当模糊的问题。因为这与其他的问LISP解释程序则由于其自身的特性，可能会非常庞大，运行起来题有很大的相关性

8、，所以，我们认为，可以通过被称作scaling的就会变得很慢。过程来揣摩结果，从而使得适应性评估更加容易。简单的说，scaling过程使得如何适应特定个体(相对其余群体)的度量标准·更好的可移植性：大多数的平台都支持标准的ANSIC化。基于这种适应值，我们将采用两种不同方式进行选择：语言，并且它的运行仅需要相对较小的内存，这就使得C代码可以,i~／m修改、甚至不修改的在任何一台机器上编译通过。·为“再现”选择具有最高适应性的个体，也就是”适者生存”原则：·更好的结构支