遗传编程 - 版本历史

2025年6月14日 (六) 15:15 念

2025-06-14T15:15:57Z

2025年6月14日 (六) 15:11 念

2025-06-14T15:11:37Z

2025年6月14日 (六) 14:38 念

2025-06-14T14:38:34Z

2025年6月14日 (六) 14:03 念

2025-06-14T14:03:19Z

2025年6月14日 (六) 14:02 念

2025-06-14T14:02:28Z

念：建立内容为“这是一个初稿”的新页面

2025-06-14T13:08:04Z

建立内容为“这是一个初稿”的新页面

新页面

这是一个初稿

@@ 第10行： / 第10行： @@
 [[文件:Image555.png|替代=图1 函数f(x)=ax+b的树形表达|居中|无框|图1 函数f(x)=ax+b的树形表达]]
+图1 函数 f(x)=ax+b的树形表达
 （2）程序表达能力受限：无法直接表示方程求解、数据回归及包含分支/循环/递归的程序；
@@ 第43行： / 第43行： @@
 [[文件:Image556.png|居中|无框|图2 函数((2.2-(X/11) ))+((7*cos(Y) )) 的树形表达]]
+图2 函数((2.2-(X/11) ))+((7*cos(Y) )) 的树形表达表达结构方式；从下往上，从左往右
 === 2.2 初始个体生成原理 ===
@@ 第98行： / 第97行： @@
 [[文件:Image561.png|居中|无框|350x350像素]]
 图8 遗传网络编程结构

←上一版本		2025年6月14日 (六) 15:11的版本
第96行：		第96行：
	=== 3.遗传编程的扩展 ===		=== 3.遗传编程的扩展 ===
	遗传网络编程（GNP）被认为是遗传编程（GP）基因结构的延伸。GNP的基因结构用有向图表示，与GP的树状结构相比，具有节点可重用性、结构紧凑和考虑过去事件的决策能力等优点。		遗传网络编程（GNP）被认为是遗传编程（GP）基因结构的延伸。GNP的基因结构用有向图表示，与GP的树状结构相比，具有节点可重用性、结构紧凑和考虑过去事件的决策能力等优点。
		+	[[文件:Image561.png\|居中\|无框\|350x350像素]]
		+	图8 遗传网络编程结构

←上一版本		2025年6月14日 (六) 14:38的版本
第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的树状结构相比，具有节点可重用性、结构紧凑和考虑过去事件的决策能力等优点。

←上一版本		2025年6月14日 (六) 14:03的版本
第9行：		第9行：
	（1）无法表达层次结构：实际问题如数学表达式f(x)=ax+b本质是层次化结构，如图1所示，而线性字符串难以有效描述；		（1）无法表达层次结构：实际问题如数学表达式f(x)=ax+b本质是层次化结构，如图1所示，而线性字符串难以有效描述；
	[[文件:Image555.png\|替代=图1 函数f(x)=ax+b的树形表达\|居中\|无框\|图1 函数f(x)=ax+b的树形表达]]		[[文件:Image555.png\|替代=图1 函数f(x)=ax+b的树形表达\|居中\|无框\|图1 函数f(x)=ax+b的树形表达]]
		+

←上一版本		2025年6月14日 (六) 14:02的版本
第1行：		第1行：
−	~~这是一个初稿~~	+	== '''1. 绪言''' ==
		+
		+	=== 1.1 遗传编程概述 ===
		+	遗传编程继承了遗传算法的思想，但其采用分层结构作为解的表示形式。这种结构以问题原始变量为叶节点，通过组合函数构成中间节点，每个完整结构既对应问题的一个解，也可视为解决该问题的计算机程序。通过遗传操作持续调整这些结构，系统最终能演化出有效的可行程序。
		+
		+	=== 1.2 传统遗传算法的局限性 ===
		+	遗传算法通过对字符串的进化操作实现优化，其理论框架经过多年发展已较为完善。但定长字符串编码限制了应用范围，主要缺陷包括：
		+
		+	（1）无法表达层次结构：实际问题如数学表达式f(x)=ax+b本质是层次化结构，如图1所示，而线性字符串难以有效描述；
		+	[[文件:Image555.png\|替代=图1 函数f(x)=ax+b的树形表达\|居中\|无框\|图1 函数f(x)=ax+b的树形表达]]
		+
		+
		+	（2）程序表达能力受限：无法直接表示方程求解、数据回归及包含分支/循环/递归的程序；
		+
		+	（3）结构刚性缺陷：固定长度字符串难以动态调整，制约问题表征能力。
		+	遗传编程通过非线性树状结构突破这些限制，其本质是通过广义计算机程序求解问题。该方法建立初始种群后，基于适者生存原则持续应用遗传操作，通过迭代进化使个体逐步逼近最优解。作为遗传算法的扩展，该进化算法具有更强的通用性。
		+
		+	== '''2.遗传编程''' ==
		+
		+	=== 2.1 遗传编程基础 ===
		+	遗传编程中的个体是由函数符号集F={f<sub>1</sub>,f<sub>2</sub>,⋅⋅⋅,f<sub>n</sub>}与终止符集T={t<sub>1</sub>,t<sub>2</sub>,⋅⋅⋅,t<sub>m</sub>}通过属性层次结构组合而成。函数符集 F内的函数可以为：
		+
		+	算法运算符： +、-、×、÷ 等。（其中除号为防止计算机溢出，规定分母不为零，称为保护性除法，一旦遇到分母为零时，最简单的处理方法令其商为被除数，或重新选择算术运算符）；
		+
		+	超越函数： sin、cos、log、exp 等。其中 log 要防止处理小于或等于零的自变量，采用保护性对数；
		+
		+	布尔运算符： AND、OR、NOT 等；
		+
		+	条件表达式： If-then-else、Switch-case 等；
		+
		+	循环表达式： Do-until、While-do、For-do 等；
		+
		+	控制转移说明语句： Go to、Call、Jump 等；
		+
		+	变量赋值函数： a=1， Read、Write 等；
		+
		+	其他定义的函数；
		+
		+	终止符集是变量或常量。
		+
		+	例如，设函数符集为：F={+,×,÷,cos}，终止符集为：T={x,y,p}，图2表示了一个由 F 和 T 组成的个体的层次化结构。
		+	[[文件:Image556.png\|居中\|无框\|图2 函数((2.2-(X/11) ))+((7*cos(Y) )) 的树形表达]]
		+
		+
		+	表达结构方式；从下往上，从左往右
		+
		+	=== 2.2 初始个体生成原理 ===
		+	初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的符号表达式，它通过随机方法产生。
		+
		+	开始时在函数集 F 中按均匀分布随机地选出一个函数作为算法树的根结点。通常把根结点限制在函数集 F 中是为了生成一个层次化的复杂结构；相反，若从终止符 T 中随机选取根结点，则生成只有一个终止符的退化结构。一般情况下，从函数集中选出的函数 f 如果具有Z(f) 个自变量，那么就要从该结点发出Z(f)个子节点。然后，对于每个子节点，从函数集 F 和终止符 T 的并集 C =F∪T 中再按均匀分布随机地选出一个元素作为该条线的尾结点。如果此时选出的是一个函数，则重复执行上述过程。如果从并集C 中选出的是终止符，它作为从节点发出的尾节点，则该分支点上的树就终止生长。上述过程从上到下，从左到右不断重复，直到一棵完整的树生成位置
		+
		+	初始群体中的初始个体通过某种随机方法产生，图3描述了一个初始个体的创建过程。