java - 用 ANN 求解 XOR 的进化算法的改进

Question

我应该实现一个具有 2 个输入、2 个隐藏和 1 个输出神经元的人工神经网络 (ANN)，它可以解决 XOR 问题。应使用进化算法优化网络的权重。给出了每个神经元的激活函数和每个 ANN 的适应度函数。下图总结了问题，介绍了我用到的变量名:

现在我尽最大努力解决这个问题，但即使使用进化算法使用 1000 个 ANN 和 2000 代的人口规模，我的最佳适应度也永远不会超过 0.75。我的代码包括一个带有神经元、激活和适应度函数的 ANN 类，以及一个包含进化算法并优化 ANN 权重的 Main 类。这是代码:

每个 ANN 都使用介于 -1 和 1 之间的随机权重进行初始化，并且能够变异，即返回一个随机选择的权重不同的变异。

public class ANN implements Comparable<ANN> {
    private Random rand = new Random();
    public double[] w = new double[6];  //weights: in1->h1, in1->h2, in2->h1, in2->h2, h1->out, h2->out

    public ANN() {
        for (int i=0; i<6; i++) //randomly initialize weights in [-1,1)
            w[i] = rand.nextDouble() * 2 - 1;
    }

    //calculates the output for input a & b
    public double ann(double a, double b) {
        double h1 = activationFunc(a*w[0] + b*w[2]);
        double h2 = activationFunc(a*w[1] + b*w[3]);
        double out = activationFunc(h1*w[4] + h2*w[5]);

        return out;
    }

    private double activationFunc(double x) {
        return 2.0 / (1 + Math.exp(-2*x)) - 1;
    }

    //calculates the fitness (divergence to the right output)
    public double fitness() {
        double sum = 0;
        //test all possible inputs (0,0; 0,1; 1,0; 1,1)
        sum += 1 - Math.abs(0 - ann(0, 0));
        sum += 1 - Math.abs(1 - ann(0, 1));
        sum += 1 - Math.abs(1 - ann(1, 0));
        sum += 1 - Math.abs(0 - ann(1, 1));
        return sum / 4.0;
    }

    //randomly change random weight and return the mutated ANN
    public ANN mutate() {
        //copy weights
        ANN mutation = new ANN();
        for (int i=0; i<6; i++)
            mutation.w[i] = w[i];

        //randomly change one
        int weight = rand.nextInt(6);
        mutation.w[weight] = rand.nextDouble() * 2 - 1;

        return mutation;
    }

    @Override
    public int compareTo(ANN arg) {
        if (this.fitness() < arg.fitness())
            return -1;
        if (this.fitness() == arg.fitness())
            return 0;
        return 1;   //this.fitness > arg.fitness
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        ANN ann = (ANN)obj;
        for (int i=0; i<w.length; i++) {    //not equal if any weight is different
            if (w[i] != ann.w[i])
                return false;
        }
        return true;
    }
}

Main 类具有进化算法，并使用精英主义和基于排名的选择来创建每个种群的下一代，即复制 100 个最佳 ANN，其余 900 个是先前成功 ANN 的突变。

//rank-based selection + elitism
public class Main {
    static Random rand = new Random();
    static int size = 1000;                     //population size
    static int elitists = 100;                  //number of elitists

    public static void main(String[] args) {
        int generation = 0;
        ArrayList<ANN> population = initPopulation();
        print(population, generation);

        //stop after good fitness is reached or after 2000 generations
        while(bestFitness(population) < 0.8 && generation < 2000) {
            generation++;
            population = nextGeneration(population);
            print(population, generation);
        }
    }

    public static ArrayList<ANN> initPopulation() {
        ArrayList<ANN> population = new ArrayList<ANN>();
        for (int i=0; i<size; i++) {
            ANN ann = new ANN();
            if (!population.contains(ann))  //no duplicates
                population.add(ann);
        }
        return population;
    }

    public static ArrayList<ANN> nextGeneration(ArrayList<ANN> current) {
        ArrayList<ANN> next = new ArrayList<ANN>();
        Collections.sort(current, Collections.reverseOrder());  //sort according to fitness (0=best, 999=worst)

        //copy elitists
        for (int i=0; i<elitists; i++) {
            next.add(current.get(i));
        }

        //rank-based roulette wheel
        while (next.size() < size) {                        //keep same population size
            double total = 0;
            for (int i=0; i<size; i++)
                total += 1.0 / (i + 1.0);                   //fitness = 1/(rank+1)

            double r = rand.nextDouble() * total;
            double cap = 0;
            for (int i=0; i<size; i++) {
                cap += 1.0 / (i + 1.0);                     //higher rank => higher probability
                if (r < cap) {                              //select for mutation
                    ANN mutation = current.get(i).mutate(); //no duplicates
                    if (!next.contains(mutation))
                        next.add(mutation);     
                    break;
                }
            }
        }       

        return next;
    }

    //returns best ANN in the specified population
    public static ANN best(ArrayList<ANN> population) {
        Collections.sort(population, Collections.reverseOrder());
        return population.get(0);
    }

    //returns the best fitness of the specified population
    public static double bestFitness(ArrayList<ANN> population) {
        return best(population).fitness();
    }

    //returns the average fitness of the specified population
    public static double averageFitness(ArrayList<ANN> population) {
        double totalFitness = 0;
        for (int i=0; i<size; i++)
            totalFitness += population.get(i).fitness();
        double average = totalFitness / size;
        return average;
    }

    //print population best and average fitness
    public static void print(ArrayList<ANN> population, int generation) {       
        System.out.println("Generation: " + generation + "\nBest: " + bestFitness(population) + ", average: " + averageFitness(population));
        System.out.print("Best weights: ");
        ANN best = best(population);
        for (int i=0; i<best.w.length; i++)
            System.out.print(best.w[i] + " ");
        System.out.println();
        System.out.println();
    }
}

尽管如此，我对此进行了相当多的思考并使用了我学到的技术，但结果并不令人满意。由于某种原因，每个权重的最佳权重似乎都漂移到 -1。这有什么意义？权重的范围 -1 到 1 是一个不错的选择吗？除了突变之外，我还应该引入交叉吗？我知道这是一个非常具体的问题，但我非常感谢您的帮助!

Answer 1

网络结构不对。如果没有针对每个节点的偏差或阈值，该网络无法解决 XOR 问题。

一个隐藏节点应该编码 OR 而另一个隐藏节点应该编码 AND。然后输出节点可以编码 OR 隐藏节点为正，AND 隐藏节点为负的 XOR 问题。只有当 OR 隐藏节点被激活而 AND 隐藏节点没有被激活时，这才会产生积极的结果。

我还会增加权重的边界，让 EA 自己找到它。但如果有必要，这取决于网络结构。

如果您想将此网络与隐藏节点和阈值一起使用，请参阅:http://www.heatonresearch.com/online/introduction-neural-networks-java-edition-2/chapter-1/page4.html

如果您想使用另一个带有偏差的网络，请参阅:http://www.mind.ilstu.edu/curriculum/artificial_neural_net/xor_problem_and_solution.php