/*
  Copyright 2006 by Sean Luke
  Licensed under the Academic Free License version 3.0
  See the file "LICENSE" for more information
*/


package ec.select;
import ec.util.*;
import ec.*;

/* 
 * SUSSelection.java
 * 
 * Created: Thu Feb 12 16:19:52 EST 2009
 * By: Sean Luke
 */

/**
 * Picks individuals in a population using the Stochastic Universal Selection (SUS) process, using
 * fitnesses as returned by their fitness() methods.  This is expensive to
 * set up and bring down, so it's not appropriate for steady-state evolution.
 * If you're not familiar with the relative advantages of 
 * selection methods and just want a good one,
 * use TournamentSelection instead.   Not appropriate for
 * multiobjective fitnesses.
 *
 * 
By default this implementation of SUS shuffles the order of the individuals
 * in the distribution before performing selection.  This isn't always present in classic
 * implementations of the algorithm but it can't hurt anything and certainly can avoid
 * certain pathological situations.  If you'd prefer not to preshuffle, set shuffle=false
 * Note that we don't actually change the order of the individuals in the population -- instead
 * we maintain our own internal array of indices and shuffle that.
 *
 * 
Like truncation selection, 
 * SUS samples N individuals (with replacement) up front from the population,
 * Then returns those individuals one by one.
 * ECJ's implementation assumes that N is the size of the population -- that is, you're
 * going to ultimately request a whole population out of this one selection method.
 * This could be a false assumption: for example, if you only sometimes call this
 * selection method, and sometimes TournamentSelection; or if you've got multiple
 * pipelines.  In these cases, SUS is probably a bad choice anyway.
 *
 * 
If you ask for more than a population's worth of individuals, SUS tries
 * to handle this gracefully by reshuffling its array and starting to select over
 * again.  But again that might suggest you are doing something wrong.
 *
 * 

 * Note: Fitnesses must be non-negative.  0 is assumed to be the worst fitness.
 * 

 
Typical Number of Individuals Produced Per produce(...) call

 Always 1.


 
Parameters

 

 
base.shuffle

  bool = true (default) or false
 
(should we preshuffle the array before doing selection?)

 
 
Default Base

 select.sus

 *
 * @author Sean Luke
 * @version 1.0 
 */

public class SUSSelection extends SelectionMethod
    {
    /** Default base */
    public static final String P_SUS = "sus";
    public static final String P_SHUFFLE = "shuffle";
    
    /** An array of pointers to individuals in the population, shuffled along with the fitnesses array. */
    public int[] indices;
    /** The distribution of fitnesses. */
    public double[] fitnesses;
    
    /** Should we shuffle first? */
    public boolean shuffle = true;
    /** The floating point value to consider for the next selected individual. */
    public double offset = 0.0;
    /** The index in the array of the last individual selected. */
    public int lastIndex;
    /** How many samples have been done?  */
    public int steps;
    
    public Parameter defaultBase()
        {
        return SelectDefaults.base().push(P_SUS);
        }

    public void setup(final EvolutionState state, final Parameter base)
        {
        super.setup(state,base);
        
        Parameter def = defaultBase();
        shuffle = state.parameters.getBoolean(base.push(P_SHUFFLE),def.push(P_SHUFFLE),true);
        }

    /* Largely stolen from sim.util.Bag.  Shuffles both the indices and the doubles */
    void shuffle(MersenneTwisterFast random, double[] fitnesses, int[] indices)
        {
        int numObjs = fitnesses.length;
        //double[] fitnesses = this.fitnesses;
        //int[] indices = this.indices;
        
        double f;
        int i;
        int rand;
        
        for(int x=numObjs-1; x >= 1 ; x--)
            {
            rand = random.nextInt(x+1);
            f = fitnesses[x];
            fitnesses[x] = fitnesses[rand];
            fitnesses[rand] = f;

            i = indices[x];
            indices[x] = indices[rand];
            indices[rand] = i;
            }
        }

    // don't need clone etc. 
    public void prepareToProduce(final EvolutionState s,
        final int subpopulation,
        final int thread)
        {
        lastIndex = 0;
        steps = 0;
        
        fitnesses = new double[s.population.subpops[subpopulation].individuals.length];

        // compute offset
        offset = (double)(s.random[thread].nextDouble() / fitnesses.length);
        
        // load fitnesses but don't build distribution yet
        for(int x=0;x= fitnesses.length)  // we've gone too far, clearly an error
            {
            state.output.warning("SUSSelection was asked for too many individuals, so we're re-shuffling.  This will give you proper results, but it might suggest an error in your code.");
            boolean s = shuffle;
            shuffle = true;
            prepareToProduce(state, subpopulation, thread);  // rebuild
            shuffle = s; // just in case
            }
            
        // find the next index
        for( /* empty */ ; lastIndex < fitnesses.length - 1; lastIndex++)
            if ((lastIndex == 0 || offset >= fitnesses[lastIndex - 1]) && offset < fitnesses[lastIndex])
                break;

        offset += (double)(1.0 / fitnesses.length);  // update for next time
        steps++;
        return indices[lastIndex];
        }
    }