/*
  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.*;
import ec.util.*;

/* 
 * GreedyOverselection.java
 * 
 * Created: Thu Feb 10 17:39:03 2000
 * By: Sean Luke
 */

/**
 * GreedyOverselection is a SelectionMethod which implements Koza-style
 * fitness-proportionate greedy overselection.  Not appropriate for
 * multiobjective fitnesses.
 *
 * 
 This selection method first 
 * divides individuals in a population into two groups: the "good" 
 * ("top") group, and the "bad" ("bottom") group.  The best top
 * percent of individuals in the population go into the good group.
 * The rest go into the "bad" group.  With a certain probability (determined
 * by the gets setting), an individual will be picked out of the
 * "good" group.  Once we have determined which group the individual
 * will be selected from, the individual is picked using fitness proportionate
 * selection in that group, that is, the likelihood he is picked is 
 * proportionate to his fitness relative to the fitnesses of others in his
 * group.
 *
 * 
 All 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. 
 *
 * 

 * 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.top

 0.0 <= double <= 1.0
 
(the percentage of the population going into the "good" (top) group)
 
base.gets

 0.0 <= double <= 1.0
 
(the likelihood that an individual will be picked from the "good" group)
 

 
Default Base

 select.greedy
 * @author Sean Luke
 * @version 1.0 
 */

public class GreedyOverselection extends SelectionMethod
    {
    public double[] sortedFitOver;
    public double[] sortedFitUnder;
    /** Sorted population -- since I *have* to use an int-sized
        individual (short gives me only 16K), 
        I might as well just have pointers to the
        population itself.  :-( */
    public int[] sortedPop;

    public static final String P_GREEDY = "greedy";
    public static final String P_TOP = "top";
    public static final String P_GETS = "gets";

    public double top_n_percent;
    public double gets_n_percent;

    public Parameter defaultBase()
        {
        return SelectDefaults.base().push(P_GREEDY);
        }

    public void setup(final EvolutionState state, final Parameter base)
        {
        super.setup(state,base);
        
        Parameter def = defaultBase();
        
        top_n_percent =
            state.parameters.getDoubleWithMax(base.push(P_TOP),def.push(P_TOP),0.0,1.0);
        if (top_n_percent < 0.0)
            state.output.fatal("Top-n-percent must be between 0.0 and 1.0", base.push(P_TOP),def.push(P_TOP));
        
        gets_n_percent =
            state.parameters.getDoubleWithMax(base.push(P_GETS),def.push(P_GETS),0.0,1.0);
        if (gets_n_percent < 0.0)
            state.output.fatal("Gets-n-percent must be between 0.0 and 1.0", base.push(P_GETS),def.push(P_GETS));
        
        }
    
    
    // don't need clone etc. -- I'll never clone with my arrays intact
    
    public void prepareToProduce(final EvolutionState s,
        final int subpopulation,
        final int thread)
        {
        // load sortedPop integers
        final Individual[] i = s.population.subpops[subpopulation].individuals;

        sortedPop = new int[i.length];
        for(int x=0;x