尾递归遗传算法投掷 "AWT-EventQueue-0" java.lang.StackOverflowError

Question

我创建了一个运行遗传算法来解决迷宫的项目，使用尾递归函数计算最佳染色体以防止WhosebugError。

控制台产生的错误是：

Exception in thread "AWT-EventQueue-0" java.lang.WhosebugError
at java.util.TimSort.mergeLo(Unknown Source)
at java.util.TimSort.mergeAt(Unknown Source)
at java.util.TimSort.mergeCollapse(Unknown Source)
at java.util.TimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at java.util.stream.SortedOps$SizedRefSortingSink.end(Unknown Source)
at java.util.stream.AbstractPipeline.copyInto(Unknown Source)
at java.util.stream.AbstractPipeline.wrapAndCopyInto(Unknown Source)
at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(Unknown Source)
at java.util.stream.AbstractPipeline.evaluate(Unknown Source)
at java.util.stream.ReferencePipeline.collect(Unknown Source)
at GeneticAlgorithm.searchOptimalMovesTR(GeneticAlgorithm.java:168)
at GeneticAlgorithm.searchOptimalMovesTR(GeneticAlgorithm.java:184)
at GeneticAlgorithm.searchOptimalMovesTR(GeneticAlgorithm.java:184)

searchOptimalMovesTR和searchOptimalMoves函数如下：

//Optimal moves wrapper
    private int[][] searchOptimalMoves(int[][] population) {
        return searchOptimalMovesTR(population, 999);
    }
    
    //search optimal moves using tail recursion
    private int[][] searchOptimalMovesTR(int[][] population, int acceptableScore) {
        runCount++;
        System.out.println(runCount);
        if(acceptableScore <= 10) {
            System.out.println("HIT ACCEPTABLE SCORE");
            return population;
        } 
        else {
            //populate hashmap of chromosome(key), fitness(value)  
            HashMap<Integer[], Integer> fitness = new HashMap<Integer[], Integer>();
            for(int i = 0; i < population.length; i++) {
                Integer score = new Integer(calcFitness(population[i]));
                Integer[] chromosome = new Integer[population[i].length];

                for(int j = 0; j < population[i].length; j++) {
                    chromosome[j] = Integer.valueOf(population[i][j]);
                }
                fitness.put(chromosome, score);
            }
            
            //sort hashmap by value REF THIS https://www.javacodegeeks.com/2017/09/java-8-sorting-hashmap-values-ascending-descending-order.html
            HashMap<Integer[], Integer> sortedFitness = fitness.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(
                    toMap(e -> e.getKey(), e -> e.getValue(), (e1, e2) -> e2, LinkedHashMap::new));
                                
            //turn sorted fitness keys into an array and take half of the length
            Integer[][] arrayFitness = new Integer[sortedFitness.keySet().size()][sortedFitness.size()]; 
            arrayFitness = sortedFitness.keySet().toArray(arrayFitness);
            int[][] halfFitness = new int[arrayFitness.length / 2][arrayFitness[0].length];

            //convert to int primitive type
            for(int i = 0; i < halfFitness.length; i++) {
                for(int j = 0; j < halfFitness[i].length; j++) {
                    halfFitness[i][j] = arrayFitness[i][j].intValue();
                }
            }
            
            //create new population 
            int[][] newpopulation = new int[arrayFitness.length / 2][arrayFitness[0].length];
            newpopulation = crossover(halfFitness, arrayFitness.length, 0.5);
            return searchOptimalMovesTR(newpopulation, getFittest(newpopulation));
        }           
    }

控制台线 at GeneticAlgorithm.searchOptimalMovesTR(GeneticAlgorithm.java:168) 突出显示这行代码：

HashMap<Integer[], Integer> sortedFitness = fitness.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect( toMap(e -> e.getKey(), e -> e.getValue(), (e1, e2) -> e2, LinkedHashMap::new));

我正在使用此行按值而不是键对哈希图进行排序，以根据适应度值获得最有效的染色体。我最初的想法是 hashmap 的使用以某种方式影响堆栈并导致程序不是尾递归的，但我不熟悉另一种按值而不是键对 hashmap 进行排序的方法。

Answer 1

Java 未实现尾递归优化：您必须手动将递归替换为循环。幸运的是这很容易：

    while (acceptableScore > 10) {
        runCount++;
        System.out.println(runCount);
        //populate hashmap of chromosome(key), fitness(value)  
        HashMap<Integer[], Integer> fitness = new HashMap<Integer[], Integer>();
        for(int i = 0; i < population.length; i++) {
            Integer score = new Integer(calcFitness(population[i]));
            Integer[] chromosome = new Integer[population[i].length];

            for(int j = 0; j < population[i].length; j++) {
                chromosome[j] = Integer.valueOf(population[i][j]);
            }
            fitness.put(chromosome, score);
        }
        
        //sort hashmap by value REF THIS https://www.javacodegeeks.com/2017/09/java-8-sorting-hashmap-values-ascending-descending-order.html
        HashMap<Integer[], Integer> sortedFitness = fitness.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(
                toMap(e -> e.getKey(), e -> e.getValue(), (e1, e2) -> e2, LinkedHashMap::new));
                            
        //turn sorted fitness keys into an array and take half of the length
        Integer[][] arrayFitness = new Integer[sortedFitness.keySet().size()][sortedFitness.size()]; 
        arrayFitness = sortedFitness.keySet().toArray(arrayFitness);
        int[][] halfFitness = new int[arrayFitness.length / 2][arrayFitness[0].length];

        //convert to int primitive type
        for(int i = 0; i < halfFitness.length; i++) {
            for(int j = 0; j < halfFitness[i].length; j++) {
                halfFitness[i][j] = arrayFitness[i][j].intValue();
            }
        }
        
        //create new population 
        int[][] newpopulation = new int[arrayFitness.length / 2][arrayFitness[0].length];
        newpopulation = crossover(halfFitness, arrayFitness.length, 0.5);
        population = newpopulation;
        acceptableScore = getFittest(newpopulation));
    }           
    System.out.println("HIT ACCEPTABLE SCORE");
    return population;

尾递归遗传算法投掷 "AWT-EventQueue-0" java.lang.StackOverflowError

Tail Recursive Genetic Algorithm throwing "AWT-EventQueue-0" java.lang.StackOverflowError

java

stack-overflow

genetic-algorithm

tail-recursion