1

I developed a genetic algorithm in java 8 taking advantage of its reasonably free parallelism opportunities with Streams. As you are likely aware, running the epochs takes its time for even a test problem of generating the phrase "to be or not to be, that is the question" with char genes. I have managed to parallelize all the operations except two, that have become significant bottlenecks: speciation (determining the compatibility of a chromosome with others so they can be put into the appropriate species or create new ones) and the calculation of how many offspring a species should have.

I doubt I'll ever be able to parallelize speciation, as it involves iterating through all the chromosomes while creating new species if necessary that the next chromosome should have access to; too many concurrent modifications of lists. I get the feeling that the species offspring calculation could be parallelized, but I can't figure out how. I think it's a reduction operation, but it needs to carry over the fractional part of divisions so they can be added when necessary. This accumulation should be available to each species and each chromosome. I suspect the solution might involve creating a complex class that implements IntConsumer, but I'm not bright enough to figure out. The code is below. Any ideas?

    private Map<ID, Integer> createMapWithTheExpectedOffspringNumberForEachSpecies() {

    final Map<ID, Integer> mapWithTheExpectedOffspringNumberForEachSpecies = new ConcurrentHashMap<ID, Integer>();

    final double averageOfFitnesses = this.calculateAverageOfFitnesses();

    double skim = 0.0;

    for (final ISpecies<T> species : this.collectionOfSpecies.get()) {

        int offspringThisSpeciesShouldHave = 0;

        for (final IChromosome<T> chromosome : species.getChromosomes().get()) {

            int offspringThisChromosomeShouldHave = 0;

            final double fitnessOfThisChromosome = this
                    .retrieveFitnessForChromosome(chromosome);

            final int floorOfChromosomesExpectedOffspring = (int) Math.floor(this.expectedAmountOfChildrenForChromosome(averageOfFitnesses,
                    fitnessOfThisChromosome));
            final double fractionalPartOfChromosomesExpectedOffspring = this.expectedAmountOfChildrenForChromosome(averageOfFitnesses,
                    fitnessOfThisChromosome) % 1.0;

            offspringThisChromosomeShouldHave += floorOfChromosomesExpectedOffspring;

            skim += fractionalPartOfChromosomesExpectedOffspring;

            if (skim > 1.0) {
                final double skimIntPart = Math.floor(skim);
                offspringThisChromosomeShouldHave += skimIntPart;
                skim -= skimIntPart;
            }

            offspringThisSpeciesShouldHave += offspringThisChromosomeShouldHave;
        }

        mapWithTheExpectedOffspringNumberForEachSpecies.put(
                species.getID(), offspringThisSpeciesShouldHave);
    }

    return mapWithTheExpectedOffspringNumberForEachSpecies;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.