Custom Genotype in Jenetics for nesting

Question

I'm using Jenetics to nest a list of polygons using NoFitPolygon

I have a function that gived a list of polygon nests them following the order in the list.

I adapted the TravellingSalesman problem in order to have a genotype that represent the list of polygons, and during evolution the order change.

Now I want to add the rotation to the genotype, in order to get better results, but I don't know how to add it to my code.

Currently the order of the nestpaths determines the fitness, what i want to do is add, for every nestpath, a double value (doubleChromosome?) to the genotype that represent the rotation of the nestpath.

Nestpath is the class that represent the polygon

    public class NFP_Nesting implements Problem<ISeq<NestPath>, EnumGene<NestPath>, Double>{

static Phenotype<EnumGene<NestPath>,Double> tmpBest = null;
static Result tmpBestResult =null;

private NestPath _binPolygon;
Map<String,List<NestPath>> nfpCache=new HashMap<>();

private final ISeq<NestPath> _list;

public NFP_Nesting(ISeq<NestPath> lista,NestPath binpolygon ,double binw, double binh) 
{
    _binPolygon = binpolygon;
    _list=Objects.requireNonNull(lista);

}

@Override
public Codec<ISeq<NestPath>, EnumGene<NestPath>> codec() {
    return Codecs.ofPermutation(_list);
}

@Override
public Function<ISeq<NestPath>, Double> fitness() {

    return this::scalar_fitness;

}


/**
 * @param seq_nestpath
 * @return Fitness of the model
 */
Double scalar_fitness(final ISeq<NestPath> seq_nestpath) {

    List<NestPath> paths = seq_nestpath.asList();

    final Random random = RandomRegistry.random();
    
    //TODO NOT RANDOM ROTATION
    List<Integer> ids = new ArrayList<>();  
    for(int i = 0 ; i < paths.size(); i ++){
        ids.add(paths.get(i).getId());
        NestPath n = paths.get(i);
        if(n.getPossibleRotations()!= null)
        {
            n.setRotation(n.getPossibleRotations()[random.nextInt(n.getPossibleRotations().length)]);
        }
    }

///complicated function here

    return fitness;

}



private static NFP_Nesting of (List<NestPath> l, NestPath binpol, double binw, double binh)
{
    final MSeq<NestPath> paths = MSeq.ofLength(l.size());

    final Random random = RandomRegistry.random();

    for ( int i = 0 ; i < l.size(); ++i ) {         
        paths.set(i, l.get(i));
    }

    //initial shuffle list of polygons
    for(int j=paths.length()-1; j>0;--j)
    {
        final int i = random.nextInt(j+1);
        final NestPath tmp=paths.get(i);
        paths.set(i, paths.get(j));
        paths.set(j, tmp);
    }

    return new NFP_Nesting(paths.toISeq(),binpol,binw,binh);

}

Main:

public static void main(String[] args) {


    
    ExecutorService executor = Executors.newFixedThreadPool(1);

    NFP_Nesting nst = NFP_Nesting.of(tree,binPolygon,binWidth,binHeight);
    Engine<EnumGene<NestPath>,Double> engine = Engine
            .builder(nst)
            .optimize(Optimize.MINIMUM)
            .populationSize(config.POPULATION_SIZE)
            .executor(executor)
            .alterers(
                    new SwapMutator<>(0.25),
                    new PartiallyMatchedCrossover<>(0.35)
                    )
            .build();


    final EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();   

    Phenotype<EnumGene<NestPath>,Double> best=
            engine.stream()
            .limit(Limits.bySteadyFitness(5))
            .limit(Limits.byExecutionTime(Duration.ofSeconds(MAX_SEC_DURATION)))
            //.limit(10)
            .peek(NFP_Nesting::update)
            .peek(statistics)
            .collect(toBestPhenotype());

    System.out.println(statistics);
    //System.out.println(best);


}

Answer 1

I think I understand your problem now. What you want to do is to have an additional rotation encoded in the genotype. But Jenetics only allows one gene type per genotype. Using the permutation-codec, you fixed the gene-type to a EnumGene and for your rotation you will need DoubleGene. With a simple trick we are able to express the path permutation also as DoubleGene, by using the order of the genes within the chromosome.

The following code will show you how to do this.

import static java.util.Objects.requireNonNull;

import java.util.function.Function;
import java.util.stream.IntStream;

import io.jenetics.DoubleChromosome;
import io.jenetics.DoubleGene;
import io.jenetics.Genotype;
import io.jenetics.MeanAlterer;
import io.jenetics.Phenotype;
import io.jenetics.SwapMutator;
import io.jenetics.engine.Codec;
import io.jenetics.engine.Engine;
import io.jenetics.engine.EvolutionResult;
import io.jenetics.engine.Limits;
import io.jenetics.engine.Problem;
import io.jenetics.example.NfpNesting.Solution;
import io.jenetics.util.DoubleRange;
import io.jenetics.util.ISeq;
import io.jenetics.util.ProxySorter;

public class NfpNesting implements Problem<Solution, DoubleGene, Double> {

    record NestPath() {}

    record Solution(ISeq<NestPath> paths, double[] rotations) {
        Solution {
            assert paths.length() == rotations.length;
        }
    }

    private final Codec<Solution, DoubleGene> code;


    public NfpNesting(final ISeq<NestPath> paths) {
        requireNonNull(paths);

        code = Codec.of(
            Genotype.of(
                // Encoding the order of the `NestPath` as double chromosome.
                // The order is given by the sorted gene values.
                DoubleChromosome.of(DoubleRange.of(0, 1), paths.length()),
                // Encoding the rotation of each `NestPath`.
                DoubleChromosome.of(DoubleRange.of(0, 2*Math.PI), paths.length())
            ),
            gt -> {
                /*
                The `order` array contains the sorted indexes.
                This for-loop will print the genes in ascending order.
                for (var index : order) {
                    System.out.println(gt.get(0).get(index));
                }
                */
                final int[] order = ProxySorter.sort(gt.get(0));

                // Use the `order` indexes to "permute" your path elements.
                final ISeq<NestPath> pseq = IntStream.of(order)
                    .mapToObj(paths::get)
                    .collect(ISeq.toISeq());

                // The second chromosome just contains your rotation values.
                final double[] rotations = gt.get(1)
                    .as(DoubleChromosome.class)
                    .toArray();

                return new Solution(pseq, rotations);
            }
        );
    }

    @Override
    public Codec<Solution, DoubleGene> codec() {
        return code;
    }

    @Override
    public Function<Solution, Double> fitness() {
        return solution -> {
            final ISeq<NestPath> paths = solution.paths();
            final double[] rotations = solution.rotations();

            // Do your fitness calculation.
            return 0.0;
        };
    }

    public static void main(final String[] args) {
        final var paths = ISeq.<NestPath>of();
        final var nesting = new NfpNesting(paths);

        final Engine<DoubleGene, Double> engine = Engine.builder(nesting)
            .alterers(
                new MeanAlterer<>(),
                new SwapMutator<>())
            .build();

        final Phenotype<DoubleGene, Double> best = engine.stream()
            .limit(Limits.bySteadyFitness(5))
            .collect(EvolutionResult.toBestPhenotype());

        System.out.println("Best Fitness: " + best.fitness());
        System.out.println("Best paths: " + nesting.decode(best.genotype()).paths());
    }

}

Answer 2

I'm not sure whether I fully understand the problem you want to solve, but the permutation codec (Codecs.ofPermutation(Seq)) is used for problems where the order of a given sequence of objects determines it's fitness. So, only the order of the NestPath elements in ISeq<NestPath> defines the fitness, right? The fitness function is not responsible for altering your objects, via side effects.

I also don't understand what you mean with rotate the genotype. A Genotype in Jenetics is just a sequence of chromosomes. Maybe you can explain your optimization problem in a greater detail.

Some comments to your code itself

• The NFP_Nesting::of does a shuffling of the given List<NestPath>. This is not necessary.
• Doing some updates with .peek(NFP_Nesting::update) also looks suspicious. If you need to update your NestPath objects, you no longer doing a permutation optimization. The NestPath object should be immutable.
• Don't store any static variables in your Problem implementation. The Problem interface just combines the Codec and the fitness function and should be immutable.

So, if you can explane your problem more clearly, I can try to help to find a proper encoding.