Constraints when creating a Genotype using Jenetics

Question

I am experimenting with the Multi-objective Optimization Problem (MOP) using Jenetics. A toy problem I created is to select two subsets from a given set, maximizing their total sum, given each subset has a limit. However I want to ensure that the two subsets are mutually exclusive. How can I set this constraint when creating Genotype of the two Chromosomes?

The set I'm using for my toy problem is:

private static final ISeq<Integer> SET = ISeq.of( IntStream.rangeClosed( 1, 10 )
            .boxed()
            .collect( Collectors.toList() ) );

The signature of my problem is:

Problem<List<ISeq<Integer>>, BitGene, Vec<int[]>>

And the codec is:

@Override public Codec<List<ISeq<Integer>>, BitGene> codec() {
        Objects.requireNonNull( SET );
        final Genotype<BitGene> g =
                Genotype.of( BitChromosome.of( SET.length() ), BitChromosome.of( SET.length() ) );
        return Codec.of(
                g,
                gc -> gc.stream().map( z -> z.as( BitChromosome.class ).ones().mapToObj( SET )
                        .collect( ISeq.toISeq() ) ).collect( Collectors.toList() )
        );
    }

I have assigned the first subset with a limit of 9 and the second subset with a limit of 4.

I expect an initial population of two chromosomes with mutually exclusive genes such that Phenotype's in the end will yield individuals that do not have items duplicated from the SET.

An example output I'm currently getting is:

[[4,5], [4]]

But I expect both individuals to have mutually exclusive items. How can this be achieved with Jenetics?

Answer 1

It's not the only possible encoding of your problem, since every problem has its own characteristics. For a Multi Knapsack Problem I would choose an IntegerChromosome instead of a BitChromosomes.

private static final ISeq<Integer> ITEMS = IntStream.rangeClosed(1, 10)
    .boxed()
    .collect(ISeq.toISeq());

public Codec<ISeq<List<Integer>>, IntegerGene> codec(final int knapsackCount) {
    return Codec.of(
        Genotype.of(IntegerChromosome.of(
            0, knapsackCount, ITEMS.length())
        ),
        gt -> {
            final ISeq<List<Integer>> knapsacks = IntStream.range(0, knapsackCount)
                .mapToObj(i -> new ArrayList<Integer>())
                .collect(ISeq.toISeq());

            for (int i = 0; i < ITEMS.length(); ++i) {
                final IntegerGene gene = gt.get(0, i);
                if (gene.intValue() < knapsackCount) {
                    knapsacks.get(gene.intValue()).add(ITEMS.get(i));
                }
            }

            return knapsacks;
        }
    );
}

The codec given above chooses an IntegerChromoses with the length of the number of Knapsack items. Its gene range will be bigger than the number of Knapsacks. Item i will be put into the Knapsack with the chromosome index of IntegerChromosome.get(0, i).intValue(). If the index is out of the valid range, the item is skipped. This encoding will guarantee a distinct division of the items.

Answer 2

If you want a distinct set of genes, you have to define two distinct sets.

private static final ISeq<Integer> SET1 = IntStream.rangeClosed(1, 10)
    .boxed()
    .collect(ISeq.toISeq());

private static final ISeq<Integer> SET2 = IntStream.rangeClosed(11, 20)
    .boxed()
    .collect(ISeq.toISeq());


public Codec<ISeq<ISeq<Integer>>, BitGene> codec() {
    return Codec.of(
        Genotype.of(
            BitChromosome.of(SET1.length()),
            BitChromosome.of(SET2.length())
        ),
        gt -> ISeq.of(
            gt.getChromosome(0).as(BitChromosome.class).ones()
                .mapToObj(SET1)
                .collect(ISeq.toISeq()),
            gt.getChromosome(1).as(BitChromosome.class).ones()
                .mapToObj(SET2)
                .collect(ISeq.toISeq())
        )
    );
}

With the two integer sets you will have guaranteed the distinctiveness.