SelectionHelper.java

Go to the documentation of this file.

/*
 *   DENOPTIM
 *   Copyright (C) 2019 Vishwesh Venkatraman <vishwesh.venkatraman@ntnu.no>
 * 
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU Affero General Public License as published
 *   by the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU Affero General Public License for more details.
 *
 *   You should have received a copy of the GNU Affero General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
package denoptim.ga;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.lang.Math;
 
import denoptim.graph.Candidate;
import denoptim.programs.RunTimeParameters;
import denoptim.programs.denovo.GAParameters;
 
 
public class SelectionHelper
{
    
//------------------------------------------------------------------------------
 
    protected static Candidate[] performTournamentSelection(
            List<Candidate> eligibleParents, int sz,
            GAParameters settings)
    {
        Candidate[] selection = new Candidate[sz];
        for (int i=0; i<sz; i++)
        {
            List<Candidate> pool = new ArrayList<Candidate>();
            for (int j=0; j<settings.getSelectivePressure(); j++)
            {
                pool.add(settings.getRandomizer().randomlyChooseOne(
                        eligibleParents));
            }
            
            selection[i] = Collections.max(pool, Comparator.comparing(
                    c -> c.getFitness()));
        }
        return selection;
    }
 
//------------------------------------------------------------------------------
 
    protected static Candidate[] performRandomSelection(
            List<Candidate> population, int sz, RunTimeParameters settings)
    {
        Candidate[] selection = new Candidate[sz];
        for (int i=0; i<sz; i++)
            selection[i] = settings.getRandomizer().randomlyChooseOne(population);
 
        return selection;
    }
 
//------------------------------------------------------------------------------
 
    protected static Candidate[] performSUS(List<Candidate> population, 
            int sz, RunTimeParameters settings)
    {
        int k = population.size();
        Candidate[] selection = new Candidate[sz];
        // Calculate the sum of all fitness values.
        double aggregateFitness = 0;
        List<Double> fitnesses = new ArrayList<>();
        
        
        // Get module of the lowest fitness
        for (int i=0; i<k; i++)
        {
            fitnesses.add(population.get(i).getFitness());
        }
        double offSet = Math.abs(Collections.min(fitnesses));
         
        // Sum all candidates' fitness translated by the offSet
        // to ensure feasibility also with negative values
        for (int i=0; i<k; i++)
        {
            aggregateFitness += population.get(i).getFitness() + offSet;
        }
 
        // Pick a random pointer between 0 and 1 as the starting point for selection.
        double randomPointer = settings.getRandomizer().nextDouble();
        double cumulativeExpectation = 0;
        int index = 0;
        int c = 0;
        for (int i=0; i<k; i++)
        {
            
            // Calculate the probability of the i-th candidate to be selected and 
            // sum it to the previous values
            cumulativeExpectation += (population.get(i).getFitness() + offSet)
                                    / aggregateFitness * sz;
 
            // Select the candidate i if the randomPointer falls in the values spanned
            // by the cumulative probabilities 
            while (cumulativeExpectation > randomPointer + index)
            {
                selection[c] = population.get(i);
                c++;
                index++;
            }
        }
        
        return selection;
    }
 
//------------------------------------------------------------------------------
 
    protected static Candidate[] performRWS(List<Candidate> population,
            int sz, RunTimeParameters settings)
    {
        int k = population.size();
        Candidate[] selection = new Candidate[sz];
 
        double[] cumulativeFitnesses = new double[k];
        cumulativeFitnesses[0] = population.get(0).getFitness();
 
        for (int i=1; i<k; i++)
        {
            double fitness = population.get(i).getFitness();
 
            cumulativeFitnesses[i] = cumulativeFitnesses[i-1] + fitness;
        }
 
        for (int i=0; i<sz; i++)
        {
            double randomFitness = settings.getRandomizer().nextDouble() *
                        cumulativeFitnesses[cumulativeFitnesses.length-1];
            int index = Arrays.binarySearch(cumulativeFitnesses, randomFitness);
            if (index < 0)
            {
                // Convert negative insertion point to array index.
                index = Math.abs(index + 1);
            }
            selection[i] = population.get(index);
        }
        
        return selection;
    }
    
//------------------------------------------------------------------------------
}