Genetic Algorithm using Roulette Wheel Selection

Question

I'm trying to create different selection methods for a genetic algorithm I'm working on but one problem I meet in all selection methods is that my fitness of each node must be different. This is a problem for me as my fitness calculator is quite basic and will yield several identical fitness's

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% of all my different selection methods are the same so I'm sure if I could solve it for one I can solve it for all. Any help on what I'm doing wrong would be appreciated

EDIT: I saw I'm meant to post the general behavior of what's happening so essentially the method takes in a HashMap<>, sorts the values based on their fitness, picks half sorted values randomly and adds these to a new HashMap<> with their corresponding chromosomes.

Why sort first if you want to select randomly later? How many specimen are supposed to survive in the end anyway? I'd expect something like "a random half of the fittest half", but your code selects half of the whole population randomly. — daniu, Nov 01 '17 at 13:42
Here is pseudo code for this problem. https://stackoverflow.com/questions/177271/roulette-selection-in-genetic-algorithms — Muhammad Adnan, Nov 01 '17 at 13:44
@daniu It's recommended that when you use a roulette wheel selection algorithm that you sort the items first. It think it's purpose is that the random selection will have an even spread of good and bad solutions, to keep the population diverse — JNMN, Nov 01 '17 at 13:50
In roulette wheel selection values are selected based on their fitness. Higher fitness means higher chance of being selected and the chance is proportional to fitness. I see in your case you are just selecting fitnesses randomly from the list of sorted fitnesses and matching them back to their nodes to construct the output. So you need to somehow ensure the chance of being selected is proportional to fitness and not just random. — Sergey Ovchinnik, Nov 01 '17 at 14:12

score 1 · Accepted Answer · answered Nov 01 '17 at 14:20

I think you'd be much better off using collection classes.

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;

But, as Sergey stated, I don't believe this is what you need for your algorithm; you do need to favor the individuals with higher fitness.

score 1 · Answer 2 · answered Nov 02 '17 at 11:20

As mentioned in the comments, in roulette wheel selection order is not important, only weights are. A roulette wheel is like a pie chart with different sections occupying different portions of the disk, but in the end they all sum up to unit area (the area of the disk).

I'm not sure if there is an equivalent in Java, but in C++ you have std::discrete_distribution. It generates a distribution [0,n) which you initialise with weights representing the probability of each of those integers being picked. So what I normally do is have the IDs of my agents in an array and their corresponding fitness values in another array. Order is not important as long as indices match. I pass the array of fitness values to the discrete distribution, which returns an integer interpretable as an array index. I then use that integer to select the individual from the other array.

Genetic Algorithm using Roulette Wheel Selection

2 Answers2