使用轮盘赌选择的遗传算法

Question

我正在尝试为我正在研究的遗传算法创建不同的选择方法，但我在所有选择方法中遇到的一个问题是我对每个节点的适应度必须不同。这对我来说是个问题，因为我的健身计算器非常基础，会产生几个相同的健身

public static Map<String, Double> calculateRouletteSelection(Map<String, Double> population) {
        String[] keys = new String[population.size()];
        Double[] values = new Double[population.size()];
        Double[] unsortedValues = new Double[population.size()];
        int index = 0;
        for(Map.Entry<String, Double> mapEntry : population.entrySet()) {
            keys[index] = mapEntry.getKey();
            values[index] = mapEntry.getValue();
            unsortedValues[index] = mapEntry.getValue();
            index++;
        }
        Arrays.sort(values);
        ArrayList<Integer> numbers = new ArrayList<>();
        while(numbers.size() < values.length/2) {
            int random = rnd.nextInt(values.length);
            if (!numbers.contains(random)) {
                numbers.add(random);
            }
        }

        HashMap<String, Double> finalHashMap = new HashMap<>();
        for(int i = 0; i<numbers.size(); i++) {
            for(int j = 0; j<values.length; j++) {
                if(values[numbers.get(i)] == unsortedValues[j]) {
                    finalHashMap.put(keys[j], unsortedValues[j]);
                }
            }
        }

        return finalHashMap;

    }

我所有不同的选择方法中有 90% 都是相同的，所以我确信如果我能解决一个问题，我就能解决所有问题。对我做错的任何帮助将不胜感激

编辑：我看到我打算 post 正在发生的事情的一般行为所以基本上该方法采用 HashMap<>，根据它们的适合度对值进行排序，随机选择半排序值，然后将它们添加到具有相应染色体的新 HashMap<>。

Answer 1

我认为你最好使用集合类。

List<Map.Entry<String, Double>> sorted = new ArrayList<>(population.entrySet());
// sort by fitness
Collections.sort(sorted, Comparator.comparing(Map.Entry::getValue));

Set<Integer> usedIndices = new HashSet<>(); // keep track of used indices
Map<String, Double> result = new HashMap<>();
while (result.size() < sorted.size()/2) {
    int index = rnd.nextInt(sorted.size());
    if (!usedIndices.add(index)) {
        continue; // was already used
    }
    Map.Entry<String,Double> survivor = sorted.get(index);
    result.put(survivor.getKey(), survivor.getValue());
}
return result;

但是，正如 Sergey 所说，我认为这不是您的算法所需要的；您确实需要偏爱具有更高适应性的个体。

Answer 2

如评论中所述，在轮盘赌中 select离子顺序并不重要，只有权重重要。轮盘就像一个饼图，不同的部分占据了圆盘的不同部分，但最后它们都加起来就是单位面积（圆盘的面积）。

我不确定 Java 中是否有等效项，但在 C++ 中有 std::discrete_distribution。它会生成一个分布 [0,n)，您可以使用表示每个整数被选中概率的权重对其进行初始化。所以我通常做的是将代理的 ID 放在一个数组中，将它们对应的适应度值放在另一个数组中。只要索引匹配，顺序并不重要。我将适应度值数组传递给离散分布，其中 returns 一个可解释为数组索引的整数。然后我将该整数用于 select 来自另一个数组的个体。

使用轮盘赌选择的遗传算法

Genetic Algorithm using Roulette Wheel Selection

java

algorithm

genetic-algorithm