java - Jenetics lib: Constraints are still violated - Stack Overflow

admin管理员组

文章数量:1401459

I am working on a linear programming optimization problem similar to this picture (a linear optimization example) This is a simplified example, in my case I am dealing with around 25 thousands of variables (in denoted as x's in the picture) and those variables can take a value of 0, or 1. Think of this problem as a list of items I want to add to my collection, where 0 means I add the item, and 1 means I don't add it. I have a set of constraints as well, around hundreds of them.

What I did so far is implementing this engine

 Engine<BitGene, Long> engine = Engine.builder(this::fittness, genotypeFactory)
            .populationSize(100)
            .optimize(Optimize.MAXIMUM)
            .alterers(new ShuffleMutator<>(0.7), new UniformCrossover<>(0.5),
                new SwapMutator<>(0.3))
            .offspringSelector(new TournamentSelector<>(10000))
            .survivorsSelector(new RouletteWheelSelector<>())
            .constraint(constraint)
            .build();
        Phenotype<BitGene, Long> best = engine.stream()
            .limit(Limits.bySteadyFitness(200))
            .collect(EvolutionResult.toBestPhenotype());

Where the constraint is the following

 Constraint<BitGene, Long> constraint = Constraint.of(
            phenotype -> {
                Genotype<BitGene> genotype = phenotype.genotype();
                BitChromosome chromosome = genotype.chromosome().as(BitChromosome.class);

                int[] solution = chromosome.stream()
                    .map(gene -> gene.bit() ? 1 : 0)
                    .mapToInt(Integer::intValue)
                    .toArray();

                for (int i = 0; i < constraintCoeffs.length; i++) {
                    long sum = 0;
                    for (int j = 0; j < solution.length; j++) {
                        sum += constraintCoeffs[i][j] * solution[j];
                    }
                    if (sum > bounds[i]) {
                        return false; // Solution violates a constraint
                    }
                }

                return true; // Solution is valid
            }
        );

Here's the genotype factory

Factory<Genotype<BitGene>> genotypeFactory = Genotype.of(
            BitChromosome.of(objects.size(), 0.9)
        );

and here's my fitness function

private long fittness(Genotype<BitGene> genotype) {
        var bitChromosome = genotype.chromosome().as(BitChromosome.class);
        variables = bitChromosome.stream().mapToInt(gene -> gene.bit() ? 1 : 0).toArray();
        var objects = dataModel.getObjects();
        for (int i = 0; i < constraintCoeffs.length; i++) {
            long temp = 0;
            for (int j = 0; j < variables.length; j++) {
                temp += constraintCoeffs[i][j] * variables[j];
            }

            if (temp > bounds[i]) {
                return 0;
            }
        }

        double result = 0.0;
        for (int i = 0; i < objects.size(); i++) {
            result += objects.get(i).getValue() * variables[i];
        }
        long longResult = (long) (result * 100000000);
        return longResult * 30000;
    }

My issue is that regardless of how long I run this code, and regardless of the count of generations in it, or the count of individuals in it, I can't seem to reach a solution that actually satisfies my bounds limits. For instance, I have a value of the bounds where the percentage of the selected objects should not exceed 9% but for some reason it's always around 9.0x%

I am working on a linear programming optimization problem similar to this picture (a linear optimization example) This is a simplified example, in my case I am dealing with around 25 thousands of variables (in denoted as x's in the picture) and those variables can take a value of 0, or 1. Think of this problem as a list of items I want to add to my collection, where 0 means I add the item, and 1 means I don't add it. I have a set of constraints as well, around hundreds of them.

What I did so far is implementing this engine

 Engine<BitGene, Long> engine = Engine.builder(this::fittness, genotypeFactory)
            .populationSize(100)
            .optimize(Optimize.MAXIMUM)
            .alterers(new ShuffleMutator<>(0.7), new UniformCrossover<>(0.5),
                new SwapMutator<>(0.3))
            .offspringSelector(new TournamentSelector<>(10000))
            .survivorsSelector(new RouletteWheelSelector<>())
            .constraint(constraint)
            .build();
        Phenotype<BitGene, Long> best = engine.stream()
            .limit(Limits.bySteadyFitness(200))
            .collect(EvolutionResult.toBestPhenotype());

Where the constraint is the following

 Constraint<BitGene, Long> constraint = Constraint.of(
            phenotype -> {
                Genotype<BitGene> genotype = phenotype.genotype();
                BitChromosome chromosome = genotype.chromosome().as(BitChromosome.class);

                int[] solution = chromosome.stream()
                    .map(gene -> gene.bit() ? 1 : 0)
                    .mapToInt(Integer::intValue)
                    .toArray();

                for (int i = 0; i < constraintCoeffs.length; i++) {
                    long sum = 0;
                    for (int j = 0; j < solution.length; j++) {
                        sum += constraintCoeffs[i][j] * solution[j];
                    }
                    if (sum > bounds[i]) {
                        return false; // Solution violates a constraint
                    }
                }

                return true; // Solution is valid
            }
        );

Here's the genotype factory

Factory<Genotype<BitGene>> genotypeFactory = Genotype.of(
            BitChromosome.of(objects.size(), 0.9)
        );

and here's my fitness function

private long fittness(Genotype<BitGene> genotype) {
        var bitChromosome = genotype.chromosome().as(BitChromosome.class);
        variables = bitChromosome.stream().mapToInt(gene -> gene.bit() ? 1 : 0).toArray();
        var objects = dataModel.getObjects();
        for (int i = 0; i < constraintCoeffs.length; i++) {
            long temp = 0;
            for (int j = 0; j < variables.length; j++) {
                temp += constraintCoeffs[i][j] * variables[j];
            }

            if (temp > bounds[i]) {
                return 0;
            }
        }

        double result = 0.0;
        for (int i = 0; i < objects.size(); i++) {
            result += objects.get(i).getValue() * variables[i];
        }
        long longResult = (long) (result * 100000000);
        return longResult * 30000;
    }

My issue is that regardless of how long I run this code, and regardless of the count of generations in it, or the count of individuals in it, I can't seem to reach a solution that actually satisfies my bounds limits. For instance, I have a value of the bounds where the percentage of the selected objects should not exceed 9% but for some reason it's always around 9.0x%

• java
• jenetics

Share Improve this question Follow asked Mar 24 at 15:38 Ali WassoufAli Wassouf 1

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

One line in your fitness function looks suspicious.

private long fitness(Genotype<BitGene> genotype) {
    var bitChromosome = genotype.chromosome().as(BitChromosome.class);
    // Is this a field in your class? Should be a local variable.
    variables = bitChromosome.stream()
        .mapToInt(gene -> gene.bit() ? 1 : 0)
        .toArray();
    var objects = dataModel.getObjects();
    ...
}

If variable is defined outside your the fitness function, it will be shared between several threads during the evaluation. This will lead to an undefined behavior and might explain your results. The fitness function must thread safe and/or re-entrant.

private long fitness(Genotype<BitGene> genotype) {
    var bitChromosome = genotype.chromosome().as(BitChromosome.class);
    // Make it a local variable.
    var variables = bitChromosome.stream()
        .mapToInt(gene -> gene.bit() ? 1 : 0)
        .toArray();
    var objects = dataModel.getObjects();
    ...
}

Regards, Franz

本文标签： javaJenetics lib Constraints are still violatedStack Overflow