#24 Island models in the moeaframework, and constraint handling

[olumide]

Is the moeaframework currently able to support island models? I've just realized that the the island model is suited for the problem that I am working on.

Also, how does the moeaframework currently handle constraints? By converting them to objectives? Or is the handling algorithm-dependent? I need to be sure that solutions that do NOT violate constraints CANNOT be dominated solutions that do violate constraints.

[Anonymous]

For constraints, there is a setConstraint(...) method for solutions. See Chapter 7 in the user manual for details on setting constraints, in particular pages 75-76.

The constraint handling mechanism is algorithm-dependent. Many use the org.moeaframework.core.comparator.ParetoDominanceComparator (moeaframework.org) class. This uses the method proposed by Kalyanmoy, D., "An Efficient Constraint Handling Method for Genetic Algorithms." Computer Methods in Applied Mechanics and Engineering, pp. 311--338, 1998. Solutions that violate constraints will always be dominated by solutions not violating constraints.

The MOEA Framework currently does not support island models. It is technically possible to create multiple instances of an algorithm and periodically migrate solutions between the islands, but there does not exist any code currently for this. Sorry. (I'll add two alternatives: You could try to use the MOCell algorithm, which is a cellular algorithm. Or, the ECJ library provides island model support.)

[olumide]

Thanks for your reply.

I've taken a look at the paper and it seems to me that the constraint handling technique as they describe it is suited to single objectives. What modifications were made to the algorithm to adapt it for multiple objectives?

I've taken a close look at Solution and Executor classes and I'm at a loss as to how I can migrate solutions between different Executors, without forking the framework and gutting its design (or am I over-thinking it?). Similarly I am considering implementing the constraint handling technique described in the paper "Constrained Many-Objective Optimization: A Way Forward" by Dhish Kumar Saxena, Tapabrata Ray, Kalyanmoy Deb and Ashutosh Tiwari but it appears that I would have to implement the DominanceComparator interface and replace the existing implementation.

ECJ looks interesting but does not support the range of algorithms that the moeaframwork does, which is the reason that I chose the moeaframework in the first place.

[Anonymous]

I would suggest constructing the algorithms from scratch and avoiding the Executor, as it's specifically designed to prevent the user from getting low-level access. Look at one of the AlgorithmFactory classes, such as org.moeaframework.algorithm.StandardAlgorithms. For example, NSGA-II is created as follows:

    private NSGAII newNSGAII(TypedProperties properties, Problem problem) {
        int populationSize = (int)properties.getDouble("populationSize", 100);

        Initialization initialization = new RandomInitialization(problem,
                populationSize);

        NondominatedSortingPopulation population = 
                new NondominatedSortingPopulation();

        TournamentSelection selection = new TournamentSelection(2, 
                new ChainedComparator(
                        new ParetoDominanceComparator(),
                        new CrowdingComparator()));

        // This creates the default crossover/mutation operators appropriate
        // for the problem's decision variable types
        Variation variation = OperatorFactory.getInstance().getVariation(null, 
                properties, problem);

        return new NSGAII(problem, population, null, selection, variation,
                initialization);
    }

As you observe, if you want to define your own dominance check you'll need to implement the DominanceComparator interface and replace new ParetoDominanceComparator() in the above code with this new implementation. Once you create the NSGAII object, you can then access and manipulate its population.

    NSGAII algorithm = newNSGAII(...);

    while (algorithm.getNumberOfEvaluations() < maxEvaluations) {
        algorithm.step();

        Population population = algorithm.getPopulation();
        // Add/remove solutions from the population.
    }

    algorithm.terminate();

Note that NSGAII is flexible enough for this to work. Other algorithms might need additional tweaks (for example, MOEA/D has weights and neighborhoods that would need to be updated).

P.S. If you write any new dominance comparators or get the island model working and are interested in sharing your code, I'd be glad to help incorporate any contributions back into the MOEA Framework.

[D. Hadka]

I've added a section to the user manual discussing master-slave and island-model parallelization. This will be available in version 2.4, to be released in the next few days.