Ограничение Jenetics, кажется, не имеет никакого эффекта

Я реализовал вариант проблема с рюкзаком с использованием Дженетикс следующим образом:

@Value
public class Knapsack {

    public static void main( final String[] args ) {
        final var knapsackEngine = Engine.builder( Knapsack::fitness, Knapsack.codec() )
                .constraint( Knapsack.constraint() )
                .build();
        final var bestPhenotype = knapsackEngine.stream()
                .limit( 1000L )
                .collect( EvolutionResult.toBestPhenotype() );
        final var knapsack = bestPhenotype.getGenotype().getGene().getAllele();
        final var profit = bestPhenotype.getFitness();
        final var weight = knapsack.getWeight();
        System.out.println( "Valid: " + bestPhenotype.isValid() );
        System.out.println( String.format( "Solution: profit %d | weight %d", profit, weight ) );
        System.out.println( String.format( "Optimum: profit %d | weight %d", Problem.OPTIMAL_PROFIT, Problem.OPTIMAL_WEIGHT ) );
    }

    List<Item> items;

    public int getProfit() {
        return items.stream()
                .mapToInt( Item::getProfit )
                .sum();
    }

    public int getWeight() {
        return items.stream()
                .mapToInt( Item::getWeight )
                .sum();
    }

    private static Codec<Knapsack, AnyGene<Knapsack>> codec() {
        return Codec.of(
                Genotype.of( AnyChromosome.of( Knapsack::create ) ),
                genotype -> genotype.getGene().getAllele() );
    }

    private static Knapsack create() {
        final Random rand = RandomRegistry.getRandom();
        final List<Item> items = Problem.ITEMS.stream()
                .filter( item -> rand.nextBoolean() )
                .collect( Collectors.toList() );
        return new Knapsack( items );
    }

    private static int fitness( final Knapsack knapsack ) {
        return knapsack.getProfit();
    }

    private static Constraint<AnyGene<Knapsack>, Integer> constraint() {
        return Constraint.of( phenotype -> {
            final Knapsack knapsack = phenotype.getGenotype().getGene().getAllele();
            final int weight = knapsack.getItems().stream()
                    .mapToInt( Item::getWeight )
                    .sum();
            return weight <= Problem.MAX_CAPACITY;
        } );
    }

}

@Value является частью Ломбок и генерирует кучу кода, такого как конструктор, геттеры и т. д. Класс Problem определяет некоторые константы для конкретной задачи о рюкзаке (P07 из https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html):

public class Problem {

    public static final int MAX_CAPACITY = 750;

    public static final BitChromosome OPTIMAL_SOLUTION = BitChromosome.of( "101010111000011" );

    public static final int OPTIMAL_PROFIT = 1458;

    public static final int OPTIMAL_WEIGHT = 749;

    private static final List<Integer> profits = List.of(
            135, 139, 149, 150, 156,
            163, 173, 184, 192, 201,
            210, 214, 221, 229, 240 );

    private static final List<Integer> weights = List.of(
            70, 73, 77, 80, 82,
            87, 90, 94, 98, 106,
            110, 113, 115, 118, 120 );

    public static final List<Item> ITEMS = IntStream.range( 0, profits.size() )
            .mapToObj( i -> new Item( profits.get( i ), weights.get( i ) ) )
            .collect( Collectors.toList() );

}

Хотя в Jenetics гид пользователя сказано (см. раздел 2.5):

A given problem should usually encoded in a way, that it is not possible for the evolution Engine to create invalid individuals (Genotypes).

Интересно, почему движок постоянно создает решения с весом, превышающим максимальную вместимость ранца. Таким образом, хотя эти решения недействительны в соответствии с заданным Constraint, Phenotype#isValid() возвращает true.

Я могу решить эту проблему, изменив фитнес-функцию на:

private static int fitness( final Knapsack knapsack ) {
    final int profit = knapsack.getProfit();
    final int weight = knapsack.getWeight();
    return weight <= Problem.MAX_CAPACITY ? profit : 0;
}

Или убедившись, что кодек может создавать только допустимые решения:

private static Knapsack create() {
    final Random rand = RandomRegistry.getRandom();
    final List<Item> items = Problem.ITEMS.stream()
            .filter( item -> rand.nextBoolean() )
            .collect( Collectors.toList() );
    final Knapsack knapsack = new Knapsack( items );
    return knapsack.getWeight() <= Problem.MAX_CAPACITY ? knapsack : create();
}

Но тогда в чем смысл Constraint, если он не имеет никакого эффекта?

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
0
160
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я представил интерфейс Constraint в последней версии Jenetics. Он задуман как последняя линия защиты, когда дело доходит до проверки действительности человека. В вашем примере вы использовали фабричный метод интерфейса Constraint, который принимает только предикат валидности. Второй важный метод Constraint — это метод repair. Этот метод пытается исправить данного индивидуума. Без определения этого метода создается только новый случайный фенотип. Поскольку этот интерфейс новый, кажется, я недостаточно хорошо объяснил предполагаемое использование интерфейса Constraint. Это у меня на повестке дня #541. Один из возможных примеров использования приведен в #540 во втором примере.

void constrainedVersion() {
    final Codec<double[], DoubleGene> codec = Codecs
        .ofVector(DoubleRange.of(0, 1), 4);

    final Constraint<DoubleGene, Double> constraint = Constraint.of(
        pt -> isValid(codec.decode(pt.getGenotype())),
        (pt, g) -> {
            final double[] r = normalize(codec.decode(pt.getGenotype()));
            return newPT(r, g);
        }
    );
}

private static Phenotype<DoubleGene, Double> newPT(final double[] r, final long gen) {
    final Genotype<DoubleGene> gt = Genotype.of(
        DoubleChromosome.of(
            DoubleStream.of(r).boxed()
                .map(v -> DoubleGene.of(v, DoubleRange.of(0, 1)))
                .collect(ISeq.toISeq())
        )
    );
    return Phenotype.of(gt, gen);
}

private static boolean isValid(final double[] x) {
    return x[0] + x[1] + x[2] == 1 && x[3] > 0.8;
}


private static double[] normalize(final double[] x) {
    double[] r = x;
    final double sum = r[0] + r[1] + r[2];
    if (sum != 1) {
        r[0] /= sum;
        r[1] /= sum;
        r[2] /= sum;
    }
    if (r[3] > 0.8) {
        r[3] = 0.8;
    }
    return r;
}

И метод Phenotype::isValid возвращает true, потому что это проверка достоверности местный, которая только проверяет, являются ли все хромосомы и гены человека действительными или находятся в допустимом диапазоне.

Я надеюсь, что смог ответить на ваш вопрос, и лучшее описание с одним (или несколькими) примерами уже в пути. С другой стороны: если у вас есть идеи для хороших примеров использования интерфейса Constraint, дайте мне знать.

Другие вопросы по теме