对于遗传编程的理论请参看《集体智慧编程》一书，书中对于遗传编程的原理有详细的阐述。
遗传编程的大体执行过程如下图所示：
我们使用树形表示法来描述图中遗传编程中的程序。
下面进入到我们这篇博客的重点了，遗传编程——java语言实现
一、由于是使用树形表示法来描述，所以我们首先需要构造一棵树
树节点的构造
由于有三种类型的节点，所以首先我们定义一个通用的节点接口
public interface Node extends Cloneable{ int evaluate(int[] inp); void display(int indent); Object clone(); }这里继承Cloneable接口是为了后面节点的拷贝
之后构造函数节点、参数节点、常值节点
1、函数节点
public class FuncNode implements Node{ private Func function; private String name; private List<Node> children; public FuncNode(FunctionWapper fw, List<Node> children) { this.function = fw.getFunction(); this.name = fw.getName(); this.children = children; } public int evaluate(int[] inp) { int n = this.children.size(); int[] results = new int[n]; for (int i = 0; i<n; i++) { results[i] = this.children.get(i).evaluate(inp); } return function.cal(results); } @Override public void display(int indent) { String str = ""; for (int i=0; i<indent; i++) str += ' '; System.out.println(str+this.name); for (Node c: this.children) { c.display(indent + 2); } } public Func getFunction() { return function; } public String getName() { return name; } public List<Node> getChildren() { return children; } public void setFunction(Func function) { this.function = function; } public void setName(String name) { this.name = name; } public void setChildren(List<Node> children) { this.children = children; } @Override public Object clone(){ FuncNode node = null; try { node = (FuncNode) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } node.setFunction((Func) this.getFunction().clone()); node.children = new ArrayList<>(); for (int i=0; i<this.getChildren().size(); i++) { node.children.add(copyTree((this.getChildren().get(i)))); } return node; } }对树的深度拷贝，所以这里我们另外在定义一个对树深度拷贝的类
public class CopyTree { public static Node copyTree(Node tree) { if (tree instanceof FuncNode) { FuncNode node = (FuncNode) tree.clone(); node.setFunction((Func) ((FuncNode) tree).getFunction().clone()); for (int i=0; i<((FuncNode) tree).getChildren().size(); i++) node.getChildren().set(i, copyTree(((FuncNode) tree).getChildren().get(i))) ; return node; }else{ return (Node) tree.clone(); } } }2、参数节点
public class ParamNode implements Node{ private int idx; public ParamNode(int idx) { this.idx = idx; } public int evaluate(int[] inp) { return inp[this.idx]; } @Override public void display(int indent) { String str = ""; for (int i=0; i<indent; i++) str += ' '; System.out.println(String.format("%sp%d", str, this.idx)); } public int getIdx() { return idx; } public void setIdx(int idx) { this.idx = idx; } @Override public Object clone() { Node result = null; try { result = (Node) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return result; } }3、常值节点
public class ConstNode implements Node{ private int v; public ConstNode(int v) { this.v = v; } public int evaluate(int[] inp) { return this.v; } @Override public void display(int indent) { String str = ""; for (int i=0; i<indent; i++) str += ' '; System.out.println(String.format("%s%d", str, this.v)); } public int getV() { return v; } public void setV(int v) { this.v = v; } @Override public Object clone() { Node result = null; try { result = (Node) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return result; } }二、在FuncNode中含有Func这个属性，下面我们来定义这个属性，这个属性对应的就是节点上的操作
操作函数的构造
由于操作多种多样，所以首先我们定义一个通用的接口
public interface Func extends Cloneable { int cal(int[] l); Object clone(); }这里继承Cloneable接口是为了后面节点的拷贝
之后定义具体的操作类
1、加法操作类
public class AddFunc implements Func , Cloneable{ @Override public int cal(int[] l) { return l[0] + l[1]; } @Override public Object clone() { Func f = null; try { f = (Func) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return f; } }2、减法操作类
public class SubFunc implements Func, Cloneable { @Override public int cal(int[] l) { return l[0] - l[1]; } @Override public Object clone() { Func f = null; try { f = (Func) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return f; } }3、乘法操作类
public class MulFunc implements Func, Cloneable { @Override public int cal(int[] l) { return l[0] * l[1]; } @Override public Object clone() { Func f = null; try { f = (Func) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return f; } }4、if判断操作类
public class IfFunc implements Func, Cloneable { @Override public int cal(int[] l) { if (l[0] > 0) return l[1]; else return l[2]; } @Override public Object clone() { Func f = null; try { f = (Func) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return f; } }5、比较操作类
public class IsGreaterFunc implements Func, Cloneable { @Override public int cal(int[] l) { if (l[0] > l[1]) return 1; else return 0; } @Override public Object clone() { Func f = null; try { f = (Func) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return f; } }三、定义一个包装类，对应于函数型节点上的函数
public class FunctionWapper { private Func function; private int childCount; private String name; public FunctionWapper(Func function, int childCount, String name) { this.function = function; this.childCount = childCount; this.name = name; } public String getName() { return name; } public Func getFunction() { return function; } public int getChildCount() { return childCount; } public void setName(String name) { this.name = name; } public void setChildCount(int childCount) { this.childCount = childCount; } public void setFunction(Func function) { this.function = function; } }为了后面操作的方便下面我们在定义一个ConstantWapper类用于保存一些常量
public class ConstantWapper { public static final FunctionWapper ifw = new FunctionWapper(new IfFunc(), 3, "if"); public static final FunctionWapper gtw = new FunctionWapper(new IsGreaterFunc(), 2, "isgreater"); public static final FunctionWapper addw = new FunctionWapper(new AddFunc(), 2, "add"); public static final FunctionWapper subw = new FunctionWapper(new SubFunc(), 2, "substract"); public static final FunctionWapper mulw = new FunctionWapper(new MulFunc(), 2, "multiply"); public static final FunctionWapper[] flist = {addw, mulw, ifw, gtw, subw}; }四、尽管为遗传编程手工构造程序是可行的，但是通常的初始种群是由一组随机程序构成的，所以下面就是构造我们的随机树了。
public class RandomTree { public static Node makeRandomTree(int pc) { return makeRandomTree(pc,4,0.5, 0.6); } public static Node makeRandomTree(int pc, int maxdepth) { return makeRandomTree(pc,maxdepth,0.5, 0.6); } public static Node makeRandomTree(int pc, int maxdepth, double fpr) { return makeRandomTree(pc,maxdepth,fpr, 0.6); } public static Node makeRandomTree(int pc, int maxdepth, double fpr, double ppr) { if (Math.random() < fpr && maxdepth > 0) { FunctionWapper f = ConstantWapper.flist[(int)(Math.random()*5)]; List<Node> children = new ArrayList<>(); for (int i=0; i<f.getChildCount(); i++) { children.add(makeRandomTree(pc, maxdepth-1, fpr, ppr)); } return new FuncNode(f, children); } else if (Math.random() < ppr) { return new ParamNode((int)(Math.random()*(pc-1))); } else { return new ConstNode((int)(Math.random()*10)); } } }五、随机树构造好了，如何判断随机树的好坏就成了一个问题，所以接下来我们需要对随机树的好坏进行衡量。
由于衡量函数多种多样，所以这里我们定义一个通用的接口
public interface CostFunc { long calCost(Node tree,List<Score> s); }下面是1范式衡量的具体实现类
public class OneNormCostFunc implements CostFunc { @Override public long calCost(Node tree, List<Score> s) { long dif = 0; long v = 0; for (Score data: s) { v = tree.evaluate(new int[]{data.getX(), data.getY()}); dif += Math.abs(v - data.getScore()); } return dif; } }六、下面就是遗传编程的重点了，我们采用遗传算法对随机树进行变异和交叉。
1、变异
public class Mutate { public static Node mutate(Node t, int pc) { return mutate(t, pc, 0.1); } public static Node mutate(Node t, int pc, double probchange) { FuncNode result = null; if (Math.random() < probchange) { return RandomTree.makeRandomTree(pc); } else { if (!(t instanceof FuncNode)) { return t; } result = (FuncNode) t.clone(); FuncNode temp = (FuncNode) t; for (int i=0; i<temp.getChildren().size(); i++) { result.getChildren().set(i, mutate(temp.getChildren().get(i), pc, probchange)); } } return result; } }2、交叉
public class Crossover { public static Node crossover(Node t1, Node t2) { return crossover(t1, t2, 0.7); } public static Node crossover(Node t1, Node t2, double probswap) { return crossover(t1, t2, probswap, true); } public static Node crossover(Node t1, Node t2, double probswap, boolean top) { FuncNode result = null; if (Math.random() < probswap && !top) { return (Node) t2.clone(); } else { if (!(t1 instanceof FuncNode && t2 instanceof FuncNode)) { return t1; } result = (FuncNode) t1.clone(); FuncNode temp = (FuncNode) t1; FuncNode temp2 = (FuncNode) t2; for (int i=0; i<temp.getChildren().size(); i++) { result.getChildren().set(i, crossover(temp.getChildren().get(i), temp2.getChildren().get((int)(Math.random()*temp2.getChildren().size())),probswap, false)); } } return result; } }七、有了度量随机树优劣的方法和修改随机树的两种方法，我们接下来可以开始构筑程序进化用的竞争环境了。
首先是需要将一组程序按从优到劣的顺序进行排序，由于排序的方式多种多样，下面我们首先定义一个通用的接口
public interface RankFunction { List<RankScore> getRankFunction(List<Node> population); }这里Score保存x,y以及对应的分数
public class Score { private int x; private int y; private int score; public Score() {} public Score(int x, int y, int score) { this.x = x; this.y = y; this.score = score; } public int getScore() { return score; } public int getX() { return x; } public int getY() { return y; } public void setScore(int score) { this.score = score; } public void setX(int x) { this.x = x; } public void setY(int y) { this.y = y; } }这里RankScore保存随机树以及对应的分数
public class RankScore{ private long score; private Node t; public long getScore() { return score; } public void setScore(long score) { this.score = score; } public Node getT() { return t; } public void setT(Node t) { this.t = t; } }对应格子战争游戏的排序类如下：
public class RankFunc implements RankFunction{ public static List<Score> buildhiddenset() { List<Score> rows = new ArrayList<>(); int x,y; for (int i=0; i<200; i++) { Score score = new Score(); x = i+3; y = 3*i-1; score.setX(x); score.setY(y); score.setScore(x*y); rows.add(score); } return rows; } public List<RankScore> getRankFunction(List<Node> population) { List<RankScore> scores = new ArrayList<>(); for (int i=0; i<population.size(); i++) { RankScore rankScore = new RankScore(); rankScore.setScore(new OneNormCostFunc().calCost(population.get(i), buildhiddenset())); rankScore.setT(population.get(i)); scores.add(rankScore); } Collections.sort(scores, new Comparator<RankScore>() { @Override public int compare(RankScore o1, RankScore o2) { if (o1.getScore() > o2.getScore()) return 1; else if (o1.getScore() == o2.getScore()) return 0; else return -1; } }); return scores; } }然后就是构造竞争环境了
public class Environment { public static List<RankScore> evolve(List<Node> p,int pc, int popsize, RankFunction rankFunc) { return evolve(p, pc, popsize, rankFunc, 500); } public static List<RankScore> evolve(List<Node> p,int pc, int popsize, RankFunction rankFunc, int maxgen) { return evolve(p, pc, popsize, rankFunc, maxgen, 0.1); } public static List<RankScore> evolve(List<Node> p,int pc, int popsize, RankFunction rankFunc, int maxgen, double mutationrate) { return evolve(p, pc, popsize, rankFunc, maxgen, mutationrate, 0.4); } public static List<RankScore> evolve(List<Node> p,int pc, int popsize, RankFunction rankFunc, int maxgen, double mutationrate, double breedingrate) { return evolve(p, pc, popsize, rankFunc, maxgen, mutationrate, breedingrate, 0.7); } public static List<RankScore> evolve(List<Node> p,int pc, int popsize, RankFunction rankFunc, int maxgen, double mutationrate, double breedingrate, double pexp) { return evolve(p, pc, popsize, rankFunc, maxgen, mutationrate, breedingrate, pexp, 0.05); } public static List<RankScore> evolve(List<Node> p, int pc, int popsize, RankFunction rankFunc, int maxgen, double mutationrate, double breedingrate, double pexp, double pnew) { List<Node> population = null; if (p == null) { population = new ArrayList<>(); for (int i = 0; i < popsize; i++) { population.add(RandomTree.makeRandomTree(pc)); } } else { population = p; } List<RankScore> scores = new ArrayList<>(); List<Node> newpop = null; for (int i = 0; i < maxgen; i++) { scores = rankFunc.getRankFunction(population); System.out.println(scores.get(0).getScore()); if (scores.get(0).getScore() == 0) break; newpop = new ArrayList<>(); newpop.add(scores.get(0).getT()); newpop.add(scores.get(1).getT()); while (newpop.size() < popsize) { if (Math.random() > pnew) { int temp1 = selectIndex(pexp); int temp2 = selectIndex(pexp); int index1 = temp1 <= 1 ? temp1+2: temp1; int index2 = temp2 <= 1 ? temp2+2: temp2; newpop.add(Mutate.mutate(Crossover.crossover(scores.get(index1).getT(), scores.get(index2).getT(), breedingrate), pc, mutationrate)); } else { newpop.add(RandomTree.makeRandomTree(pc)); } } population = newpop; } scores.get(0).getT().display(2); return scores; } private static int selectIndex(double pexp) { return (int) (Math.log(Math.random()) / Math.log(pexp)); } }至此遗传编程就实现了！
下面我们来测试一下
public static List<Score> buildhiddenset() { List<Score> rows = new ArrayList<>(); int x,y; for (int i=0; i<200; i++) { Score score = new Score(); x = i+3; y = 3*i-1; score.setX(x); score.setY(y); score.setScore(x*y); rows.add(score); } return rows; }上面的程序表示我们是在x*y=3i^2+8i-3上采的数据点集，看看是否最后能够生成代表数学公式的程序
public class GeneticTest { public static void main(String[] args) { Environment.evolve(null, 3, 100, new RankFunc(), 100); } }输出：
595020 0 multiply p1 p0p0为x,p1为y，从而p0*p1=x*y=3i^2+8i-3
再次执行输出：
5349179 5015604 0 substract multiply p0 p1 substract p1 p1p0为x,p1为y，从而p0*p1=x*y=3i^2+8i-3
