Genetic Algorithm - what data structure do I need?

Question

I hope such an open-ended question is allowed on here. I am working on a simple GA which will evolve a String output to match a given target String. Therefore a population of N strings will be created each generation, each of which will be assigned a fitness based upon its Hamming Distance from the target string. I then need some way of storing, and sorting, this information. I am working in Processing but solutions in Java can almost always be used in this language with imports.

As what I'm after is vaguely a key-value structure, my instinct is that I want some kind of Dictionary, but I've got very little experience of working with these. There are also some complications which steer us away from my understanding of how Dictionaries work. I want to do the following:

1. Store each String along with its associated fitness. Duplicates of both of these must be possible.

2. Sort the structure by value i.e. list the population in descending order of their fitness.

3. Trim off the bottom 50% of the population. Probably the simplest method would be to replace the unfit population with the offspring of the fit population directly.

Access time / computational efficiency is not of particular concern.

I tried to solve this using a HashMap last night, but I kept running into issues such as duplicate keys not being allowed under this structure, and I couldn't find a simple way to iterate through the HashMap and change only the bottom X% of entries by value.

To summarise, I need a structure where each entry consists of a String and an integer, it is possible to store duplicates of each, the structure can be sorted in descending order by integer value and thus the top or bottom X% of entries can be operated upon without affecting the rest.

Thank you very much for your time, any help would be much appreciated.

Answer 1

There are many ways of going about this problem. Personally, I would try out the simplest possible solution. I don't know the whole context of your project and its vision, however, based on the info that you have provided us with I am posting the solution I would choose.

Note: The following classes may not be complete. You will probably have to add more methods to use them more easily. This is just the idea of a solution, put forth in code, that might work for you.

The Pair class models a pair of a string and its fitness value. The Population class models the population of a particular generation. It saves its members in a list and provides methods to manipulate the list. It also allows for duplicate pairs. You can choose top or bottom X members of the population and operate on them.

public class Pair implements Comparable<Pair>{
    private final String value;
    private final int fitness;

    public Pair(String value, int fitness) {
        this.value = value;
        this.fitness = fitness;
    }

    public String getValue() {
        return value;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo(Pair pair) {
        return -Integer.compare(this.fitness, pair.fitness);
    }

    @Override
    public String toString() {
        return "Pair{" + "value='" + value + '\'' + ", fitness=" + fitness + '}';
    }
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Population {
    private final List<Pair> members = new ArrayList<>();

    public void addMember(Pair pair) {
        members.add(pair);
    }

    public List<Pair> getTop(int x) {
        return members.stream().sorted().limit(x).collect(Collectors.toList());
    }

    public List<Pair> getBottom(int x) {
        return  members.stream().sorted(Comparator.reverseOrder()).limit(x).collect(Collectors.toList());
    }
}

And here's a non-comprehensive test class:

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.List;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class PopulationTest {
    Population population = new Population();

    @BeforeEach
    void populate() {
        population.addMember(new Pair("test", 5));
        population.addMember(new Pair("abc", 13));
        population.addMember(new Pair("xyz", 8));
        population.addMember(new Pair("abc", 20));
    }

    @Test
    void testSortDescending() {
        List<Pair> members = population.getTop(4);
        for (int i = 0; i < members.size() - 1; i++) {
            assertTrue(members.get(i).getFitness() >= members.get(i + 1).getFitness());
        }
    }

    @Test
    void testGetTop() {
        List<Pair> top = population.getTop(2);

        assertEquals(20, top.get(0).getFitness());
        assertEquals(13, top.get(1).getFitness());
    }

    @Test
    void testGetBottom() {
        List<Pair> bottom = population.getBottom(2);

        assertEquals(5, bottom.get(0).getFitness());
        assertEquals(8, bottom.get(1).getFitness());
    }
}