Java 和提高遗传算法的效率

Question

我想知道是否可以获得一些关于提高实现遗传算法的程序的整体效率的建议。是的，这是一个作业问题，但我已经自己完成了作业，只是在寻找一种方法让它表现得更好 问题描述

我的程序位于此时读取由 h 或 p 类型的成分组成的给定链。 （例如：hphpphhphpphpphpphph）对于每个 H 和 P，它生成一个随机移动（上、下、左、右），并将该移动添加到“染色体”对象中包含的 arrayList 中。开始时，程序为 10,000 条染色体生成 19 个移动，

   SecureRandom sec = new SecureRandom();
    byte[] sbuf = sec.generateSeed(8);
    ByteBuffer bb = ByteBuffer.wrap(sbuf);
    Random numberGen = new Random(bb.getLong());
    int numberMoves = chromosoneData.length();
    moveList = new ArrayList(numberMoves);
    for (int a = 0; a < numberMoves; a++) {
        int randomMove = numberGen.nextInt(4);
        char typeChro = chromosoneData.charAt(a);
        if (randomMove == 0) {
            moveList.add(Move.Down);
        } else if (randomMove == 1) {
            moveList.add(Move.Up);
        } else if (randomMove == 2) {
            moveList.add(Move.Left);
        } else if (randomMove == 3) {
            moveList.add(Move.Right);
        }

    }

之后从种群中选择染色体进行交叉。我的交叉函数从种群中最适合的 20% 中随机选择第一个染色体，并从前 20% 之外随机选择另一个染色体。然后将选定的染色体进行交叉并调用突变函数。我相信我受到最大打击的领域是计算每条染色体的适合度。目前，我的适应度函数创建一个二维数组作为网格，按照上面显示的函数生成的移动列表中的顺序放置移动，然后循环遍历该数组以进行适应度计算。 （即发现位置 [2,1] 处的 H 是 Cord [1,1] [3,1] [2,0] 或 [2,2] 也是一个 H，如果找到 H，则只会增加发现键）

计算完成后，从我的种群中删除最不适合的染色体，并添加新的染色体，然后对染色体数组列表进行排序。冲洗并重复直到找到目标解决方案

如果你们想在寻求帮助之前查看更多我的代码来证明我确实完成了工作，请让我知道（不想发布太多内容，这样其他学生就不能复制我的东西）

正如评论中所建议的，我已经在我的应用程序上运行了分析器（以前从未使用过它，只是一年级的计算机科学学生），我最初对我遇到问题的地方的猜测有些不正确。从分析器告诉我的来看，最大的热点是：

1. 将新染色体与群体中的其他染色体进行比较以确定其位置时。我通过实现 Comparable 来做到这一点：

    public int compareTo(Chromosome other) {
        if(this.fitness >= other.fitness)
                        return 1;
             if(this.fitness ==other.fitness )
                       return 0;
                else
                        return -1;
    }

2. 所描述的另一个问题领域是在我的实际进化函数中，消耗了大约 40% 的 CPU 时间。下面所述方法的代码示例

    double topPercentile =最高值;
    最高百分比 = 最高百分比 * .20;
    topPercentile = Math.ceil(topPercentile);
    randomOne = numberGen.nextInt((int) topPercentile);
    //降低随机两个的奖励，因此它来自前 20% 之外
    int randomTwo = numberGen.nextInt(highestValue - (int) topPercentile);
    随机二 = 随机二 + 25;
    //System.out.println("选择第一个：" + randomOne + " 选择第二个：" + randomTwo);
    染色体firstChrom = (染色体)populationList.get(randomOne);
    染色体 secondaryChrom = (染色体)populationList.get(randomTwo);
    //System.out.println("选定的2条染色体交叉");
    染色体结果Chromosome = firstChrom.crossOver(secondChrom);
    populationList.add(结果染色体);
    Collections.sort(populationList);
    人口列表.remove(highestValue);
    染色体 bestResult = (染色体)populationList.get(0);
   

3. 另一个主要性能命中是由帖子中的第一个代码示例执行的初始群体播种

Answer 1

我相信我受到最大打击的领域是计算每条染色体的适应度

如果您不确定，那么我假设您还没有在程序上运行分析器。
如果你想提高性能，分析是你应该做的第一件事。

Answer 2

不要重复对总体进行排序，而是使用一个维护其内容已排序的集合。 （例如树集）

Answer 3

如果您的适应度测量在各代之间是一致的（即不依赖于人口中的其他成员），那么我至少希望您将其存储在染色体对象中，这样您只需为人口中的每个成员计算一次。有了这个，您只需在每次迭代中计算新生成/组装的染色体上的适应度。如果没有更多关于如何计算健身的信息，就很难在该领域提供任何优化。

Answer 4

您的随机数生成器种子不需要加密强度很高。

Random numberGen = new Random();

Answer 5

播种群体时的一个小加速是删除所有测试和分支：

    static Move[] moves = {Move.Down, Move.Up, Move.Left, Move.Right};

    ...

    moveList.add(moves[randomMove]);