遗传编程——java语言实现

对于遗传编程的理论请参看《集体智慧编程》一书，书中对于遗传编程的原理有详细的阐述。

遗传编程的大体执行过程如下图所示：

我们使用树形表示法来描述图中遗传编程中的程序。

下面进入到我们这篇博客的重点了，遗传编程——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
    p0

p0为x,p1为y，从而p0*p1=x*y=3i^2+8i-3

再次执行输出：

5349179
5015604
0
  substract
    multiply
      p0
      p1
    substract
      p1
      p1

p0为x,p1为y，从而p0*p1=x*y=3i^2+8i-3