761
个编辑
更改
跳到导航
跳到搜索
第52行：
第52行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
无编辑摘要
初始群体中的初始个体通过某种随机方法产生，图3描述了一个初始个体的创建过程。
初始群体中的初始个体通过某种随机方法产生，图3描述了一个初始个体的创建过程。
[[文件:Image5557.png|居中|无框|550x550像素]]
（a）生产根节点 （b）生成子节点 （c）生产子节点
图3 算法树生成过程
初始个体的生成方法有多种，它们的共同要求是要能产生不同的组合。常用的初始个体的生成方法有三种，即完全法，生长法和混合法。
==== '''2.2.1完全法：''' ====
完全法产生的初始个体，每一叶子的深度都等于给定的最大深度。所谓叶子的深度是指叶子距树根的层次。首先从函数集 F 中选取元素作为根节点，然后根据给定的最大深度分别从函数集 F 及终止符 T 中选取元素。假若待定节点的深度小于给定的最大深度，则该节点从函数集中随机选取，以便算法树延伸；若待定结点的深度等于给定的最大深度，则该节点从终止符集中选取，以便终止算法树的生长。
[[文件:Image557.png|居中|无框|370x370像素]]
图4 完全法随机生成图例（节点数为7，最大深度为2）
==== '''2.2.2生长法：''' ====
生长法形成的初始个体，每一叶子的深度不一定都等于给定的最大深度，但是算法树的最大深度要等于给定值。它也同样首先从函数集 F 中选取根节点，然后再选取外延的待定节点。假若待定节点的深度小于给定的最大深度，则该节点从函数集 F 及终止符 T 的并集 C =F∪T 中选取。若待定结点的深度等于给定的最大深度，则该节点仅从终止符集中选取，以便终止算法树的生长。
[[文件:Image558.png|居中|无框|455x455像素]]
图5 生长法随机生成图例（节点数为5，最大深度为2）
==== '''2.2.3混合法''' ====
混合法是完全法和生长法的两者的综合。其实现方法是：初始个体的深度2至给定的最大深度之间随机选取，然后一半的初始个体用完全法产生，另一半的初始个体用生长法产生。
在完全发和生长法两者方法中，为了防止产生的初始树节点数目太多，需限定都树的最大深度不超过一个给定的数。可以看出，用完全法将产生非常大的个体树，而用生长法生成的树，大小和形状有更多的差异。
=== 2.3适应度 ===
在遗传编程中，选择算子与遗传算法相同，选择适应度高的树作为父代，交叉变异需根据表达方式来。
=== 2.4交叉 ===
选择和复制出来的个体还要进行交叉，对每一对个体，产生一个随机数，如果这个数小于交叉概率 P<sub>c</sub>，将对个体执行交叉操作。
交叉模拟的是自然界中的遗传以及两性生殖过程，父代通过DNA重新组合，产生子代，子代继承了父代的一些基因，同时产生了新的基因。
交叉操作的实现步骤如下：首先选择父代，然后，在每个父代个体中随机选取 某个结点作为交叉点，交换父代中以交叉点为根结点的相应子树得到两个后代。图6给出了交叉的一个例子。
[[文件:Image559.png|居中|无框|271x271像素]]
图6 交叉示意图（黑色节点是被选中的交叉点）
2.5 变异
变异模拟的是生物界中基因突变。交叉只对现有的基因进行排列组合，产生不出新的基因材料，容易发生“早熟”现象，而变异有利于形成群体的多样性，使算法有机会从局部最优解中解脱出来。
对于每一个个体，产生一个随机数，如果它小于变异概率 Pm，则对此个体执行变异操作。产生变异的一般的方法是:在个体上随机选定一个变异点，变异点一般选择除根之外的任意节点，删掉以变异点为根的子树,然后用随机方法产生新的子树(方法同初始个体的产生方法相同)插入到该变异点处，变异之后的个体树不能超出最大深度限制。图7给出了一个个体变异的例子。
[[文件:Image560.png|居中|无框|350x350像素]]
图7 变异示意图（黑色节点是被选中的变异点）
=== 3.遗传编程的扩展 ===
遗传网络编程（GNP）被认为是遗传编程（GP）基因结构的延伸。GNP的基因结构用有向图表示，与GP的树状结构相比，具有节点可重用性、结构紧凑和考虑过去事件的决策能力等优点。