How to divide population by crossover operator

[ugokedebu]

Hello,

I would like to divide population by crossover method, calculate the feature value of each crossover method, and return the value as credit. Is there a way to divide population by crossover method in setcontribution of credit assignment?

Thank, you.

[nh295]

I don't quite understand the question. What do you mean by "divide the population by crossover"? Typically, when using crossover on a population of size N, you get N offspring solutions. Also I don't understand what you mean by "feature value". Do you mean fitness value?

Please clarify.

[ugokedebu]

Assuming that three types of crossover operators are used, SBX, DE and SPX. In that case, N individuals are generated from either SBX, DE or SPX respectively. When N=100, we assume that , SBX = 50, DE = 30 and SPX = 20 , and we would like to divide the group into {50 (SBX), 30 (DE), 20 (SPX)}. For that reason, we mean that we can make groups as many as the number of crossover operators.

For feature value, it is a value newly calculated from a group such as the evaluation index value such as HV by the group and the average value of the crowding distance.

[nh295]

I see. Currently, I do not have the capability built-in to assign multiple solutions to multiple operators. I've worked primarily with steady-state algorithms that evaluate one solution at a time (e.g. epsilon-MOEA). In order to perform what you are asking, you would have to write some custom code within the iterate() method of an Algorithm subclass.

For example, the iterate() method for NSGAII looks like:

public void iterate() {
    NondominatedSortingPopulation population = getPopulation();
    EpsilonBoxDominanceArchive archive = getArchive();
    Population offspring = new Population();
    int populationSize = population.size();

    if (selection == null) {
        // recreate the original NSGA-II implementation using binary
        // tournament selection without replacement; this version works by
        // maintaining a pool of candidate parents.
        LinkedList<Solution> pool = new LinkedList<Solution>();

        DominanceComparator comparator = new ChainedComparator(
                new ParetoDominanceComparator(),
                new CrowdingComparator());

        while (offspring.size() < populationSize) {
            // ensure the pool has enough solutions
            while (pool.size() < 2*variation.getArity()) {
                List<Solution> poolAdditions = new ArrayList<Solution>();

                for (Solution solution : population) {
                    poolAdditions.add(solution);
                }

                PRNG.shuffle(poolAdditions);
                pool.addAll(poolAdditions);
            }

            // select the parents using a binary tournament
            Solution[] parents = new Solution[variation.getArity()];

            for (int i = 0; i < parents.length; i++) {
                parents[i] = TournamentSelection.binaryTournament(
                        pool.removeFirst(),
                        pool.removeFirst(),
                        comparator);
            }

            // evolve the children
            offspring.addAll(variation.evolve(parents));
        }
    } else {
        // run NSGA-II using selection with replacement; this version allows
        // using custom selection operators
        while (offspring.size() < populationSize) {
            Solution[] parents = selection.select(variation.getArity(),
                    population);

            offspring.addAll(variation.evolve(parents));
        }
    }

    evaluateAll(offspring);

    if (archive != null) {
        archive.addAll(offspring);
    }

    population.addAll(offspring);
    population.truncate(populationSize);
}

You can change the code to look something like this:

public void iterate() {
    NondominatedSortingPopulation population = getPopulation();
    EpsilonBoxDominanceArchive archive = getArchive();
    Population offspring = new Population();
    int populationSize = population.size();

    if (selection == null) {
        // recreate the original NSGA-II implementation using binary
        // tournament selection without replacement; this version works by
        // maintaining a pool of candidate parents.
        LinkedList<Solution> pool = new LinkedList<Solution>();

        DominanceComparator comparator = new ChainedComparator(
                new ParetoDominanceComparator(),
                new CrowdingComparator());

        while (offspring.size() < populationSize) {
            // ensure the pool has enough solutions

            //##########################################
            //##**MAKE CALLS TO OPERATOR SELECTOR HERE**##
            //##########################################

                            Variation nextOperator = operatorSelector.nextOperator();
            while (pool.size() < 2* nextOperator.getArity()) {
                List<Solution> poolAdditions = new ArrayList<Solution>();

                for (Solution solution : population) {
                    poolAdditions.add(solution);
                }

                PRNG.shuffle(poolAdditions);
                pool.addAll(poolAdditions);
            }

            // select the parents using a binary tournament
            Solution[] parents = new Solution[variation.getArity()];

            for (int i = 0; i < parents.length; i++) {
                parents[i] = TournamentSelection.binaryTournament(
                        pool.removeFirst(),
                        pool.removeFirst(),
                        comparator);
            }

            // evolve the children
            offspring.addAll(variation.evolve(parents));
        }
    } else {
        // run NSGA-II using selection with replacement; this version allows
        // using custom selection operators
        while (offspring.size() < populationSize) {
            Solution[] parents = selection.select(variation.getArity(),
                    population);

            offspring.addAll(variation.evolve(parents));
        }
    }

    evaluateAll(offspring);

    if (archive != null) {
        archive.addAll(offspring);
    }

    population.addAll(offspring);
    population.truncate(populationSize);
}

If you use a set contribution credit assignment and the RouletteWheel operator selection strategy, then you will select the operators with a probability proportional to their contributions. Doing so, you would expect to divide up the solutions of a populations by each operator's selection probability.

[nh295]

As for getting a so called "feature value" of an operator and rewarding that to the operator, I think you should take a look at the IndicatorContribution and IIndicator classes. The IIndicator interface is used to create an object that can compute the contribution of a solution to a specific indicator. You can scan over the solutions in the population, create a HashMap<String,Population> that keeps track of which solutions were created by which operators. Then find the indicator value (e.g. hypervolume) of each subpopulation and assign the contribution of each solution in that subpopulation an equal amount. The contributions of each solution is then summed up by within the IndicatorContribution to reward each operator.

So the implementation of an IIndicator for crowding distance might look like this:

import aos.creditassignment.fitnessindicator.IIndicator; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import org.moeaframework.core.FastNondominatedSorting; import static org.moeaframework.core.NondominatedSorting.CROWDING_ATTRIBUTE; import org.moeaframework.core.Population; import org.moeaframework.core.Solution;

public class CrowdingIndictor implements IIndicator {

@Override
public List<Double> computeContributions(Population pop) {
    for(Solution solution : pop){
        solution.setAttribute("contribution", 0.0);
    }

    //create map so we know which solution was created by which operator
    HashMap<String, Population> map = new HashMap();
    for (Solution s : pop) {
        String operatorName = (String)s.getAttribute("operator");
        if (!map.containsKey(operatorName)) {
            map.put(operatorName, new Population());
        }
        map.get(operatorName).add(s);
    }

    //compute the crowding distance for each subpopulation
    //For simplicity of demonstration, use crowding distance computation within FastNondominatedSorting.java
    for(String str : map.keySet()){
        Population subpopulation = map.get(str);
        FastNondominatedSorting ns = new FastNondominatedSorting();
        ns.evaluate(subpopulation);
        //find average crowding distance
        double sumDistance = 0;
        for(Solution s:subpopulation){
            sumDistance += (Double)s.getAttribute(CROWDING_ATTRIBUTE);
        }
        double meanDistance = sumDistance/(double)subpopulation.size();

        //assign contribution to each solution
        for(Solution s:subpopulation){
            s.setAttribute("contribution", meanDistance);
        }
    }

    //create ordered list of contributions by reading assinged values
    ArrayList<Double> out = new ArrayList<>();
    for(Solution s : pop){
        out.add((double)s.getAttribute("contribution"));
    }
    return out;
}

@Override
public double computeContribution(Population pop, Solution offspring) {
throw new UnsupportedOperationException();
}

@Override
public double compute(Solution solnA, Solution solnB) {
    throw new UnsupportedOperationException();
}

@Override
public String toString() {
    return "CrowdingDistance";
}

@Override
public Solution getReferencePoint() {
    return null;
}

@Override
public void setReferencePoint(Solution solution
) {
    throw new UnsupportedOperationException();
}

}

[ugokedebu]

// ########################################## // ## MAKE CALLS TO OPERATOR SELECTOR HERE ## // ##########################################

Am I going to write code like the one below?

//create operator selector IOperatorSelector operatorSelector = new ProbabilityMatching(operators, 0.8, 0.1);//(operators,alpha,pmin)

    //create credit assignment
    ICreditAssignment creditAssignment = new ParetoFrontContribution(1, 0);

Thank you for telling me about feature value as well. I am going to use it as an example.

[nh295]

You should create the operatorSelector object and the creditAssignment object in a constructor and create fields for them that you can use in the other methods. Since the operator selection and credit assignment strategies will stay constant over time, you don't want to create a new object whenever iterate() is called.

Also I forgot to mention that you will need to call creditAssignment.compute(...) and operatorSelector.update(...) to compute the credits and update the operator selector with the computed credits. These would be called after the offspring solutions are evaluated.

[ugokedebu]

Does the constructor refer to the constructor in the original moeaframework?

[nh295]

Yes, the constructor for the implementation of an Alogrithm.class

For reference you can see the source code for AOSMOEA.class

[ugokedebu]

Sorry for late contact. I understand the outline. Thank you very much.

By the way, is it another case, is it possible to write the selection probability of the crossover method in a file? If so, how can I do it?