CODEWITHSUNDEEP
javaalgorithmgenetic-algorithm
JNMN
JNMN

Reputation: 165

Genetic Algorithm using Roulette Wheel Selection

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.

Upvotes: 4

Views: 963

Answers (2)

cantordust
cantordust

Reputation: 1612

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.

Upvotes: 1

daniu
daniu

Reputation: 14999

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.

Upvotes: 1

Related Questions