[6152] | 1 | /* |
---|
| 2 | Copyright 2006 by Sean Luke |
---|
| 3 | Licensed under the Academic Free License version 3.0 |
---|
| 4 | See the file "LICENSE" for more information |
---|
| 5 | */ |
---|
| 6 | |
---|
| 7 | |
---|
| 8 | package ec.select; |
---|
| 9 | import ec.util.*; |
---|
| 10 | import ec.*; |
---|
| 11 | |
---|
| 12 | /* |
---|
| 13 | * BoltzmannSelection.java |
---|
| 14 | * |
---|
| 15 | * Created: Thu May 14 2009 |
---|
| 16 | * By: Jack Compton |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | /** |
---|
| 20 | * Similar to FitProportionateSelection, but with a Simulated Annealing style twist. BoltzmannSelection picks individuals of a population in |
---|
| 21 | * proportion to an adjusted version of their fitnesses instead of their actual fitnesses as returned by fitness(). The adjusted fitness is |
---|
| 22 | * calculated by e^(fitness/current_temperature) where current_temperature is a temperature value that decreases by a constant cooling rate as |
---|
| 23 | * generations of evolution pass. The current_temperature is calculated by starting-temperature - (cooling-rate * the_current_generation_number). |
---|
| 24 | * When the temperature dips below 1.0, annealing ceases and BoltzmannSelection reverts to normal FitProportionateSelection behavior. |
---|
| 25 | * |
---|
| 26 | * <p> |
---|
| 27 | * Like FitProportionateSelection this is not appropriate for steady-state evolution. |
---|
| 28 | * If you're not familiar with the relative advantages of |
---|
| 29 | * selection methods and just want a good one, |
---|
| 30 | * use TournamentSelection instead. Not appropriate for |
---|
| 31 | * multiobjective fitnesses. |
---|
| 32 | * |
---|
| 33 | * <p><b><font color=red> |
---|
| 34 | * Note: Fitnesses must be non-negative. 0 is assumed to be the worst fitness. |
---|
| 35 | * </font></b> |
---|
| 36 | |
---|
| 37 | <p><b>Typical Number of Individuals Produced Per <tt>produce(...)</tt> call</b><br> |
---|
| 38 | Always 1. |
---|
| 39 | |
---|
| 40 | <p><b>Parameters</b><br> |
---|
| 41 | <table> |
---|
| 42 | <tr><td valign=top><i>base.</i><tt>starting-temperature</tt><br> |
---|
| 43 | <font size=-1>double = some large number (defaults to 1.0)</font></td> |
---|
| 44 | <td valign=top>(the starting temperature for our simulated annealing style adjusted fitness proportions)</td></tr> |
---|
| 45 | |
---|
| 46 | <tr><td valign=top><i>base.</i><tt>cooling-rate</tt><br> |
---|
| 47 | <font size=-1> double = some smaller number (defaults to 0.0 which causes BoltzmannSelection to behave just as FitProportionateSelection would)</font></td> |
---|
| 48 | <td valign=top>(how slow, or fast, do you want to cool the annealing fitness proportions?)</td></tr> |
---|
| 49 | |
---|
| 50 | </table> |
---|
| 51 | |
---|
| 52 | <p><b>Default Base</b><br> |
---|
| 53 | select.boltzmann |
---|
| 54 | |
---|
| 55 | * |
---|
| 56 | * @author Jack Compton |
---|
| 57 | * @version 1.0 |
---|
| 58 | */ |
---|
| 59 | |
---|
| 60 | public class BoltzmannSelection extends FitProportionateSelection |
---|
| 61 | { |
---|
| 62 | /** Default base */ |
---|
| 63 | public static final String P_BOLTZMANN = "boltzmann"; |
---|
| 64 | |
---|
| 65 | /** Starting temperature parameter */ |
---|
| 66 | public static final String P_STARTING_TEMPERATURE = "starting-temperature"; |
---|
| 67 | |
---|
| 68 | /** Cooling rate parameter */ |
---|
| 69 | public static final String P_COOLING_RATE = "cooling-rate"; |
---|
| 70 | |
---|
| 71 | /** Starting temperature **/ |
---|
| 72 | private double startingTemperature; |
---|
| 73 | |
---|
| 74 | /** Cooling rate */ |
---|
| 75 | private double coolingRate; |
---|
| 76 | |
---|
| 77 | public Parameter defaultBase() |
---|
| 78 | { |
---|
| 79 | return SelectDefaults.base().push(P_BOLTZMANN); |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | public void setup(final EvolutionState state, final Parameter base) |
---|
| 83 | { |
---|
| 84 | super.setup(state,base); |
---|
| 85 | |
---|
| 86 | Parameter def = defaultBase(); |
---|
| 87 | |
---|
| 88 | coolingRate = state.parameters.getDouble(base.push(P_COOLING_RATE),def.push(P_COOLING_RATE)); // default cooling rate of 1.0 per generation |
---|
| 89 | startingTemperature = state.parameters.getDouble(base.push(P_STARTING_TEMPERATURE),def.push(P_STARTING_TEMPERATURE)); // default starting temp is 0.0/completely cooled - will act as normal fit proportionate selection |
---|
| 90 | |
---|
| 91 | if (coolingRate <= 0) |
---|
| 92 | { |
---|
| 93 | //Hey! you gotta cool! Set your cooling rate to a positive value! |
---|
| 94 | state.output.fatal("Cooling rate should be a positive value.",base.push(P_COOLING_RATE),def.push(P_COOLING_RATE)); |
---|
| 95 | } |
---|
| 96 | |
---|
| 97 | if ((startingTemperature - coolingRate) <= 0) { |
---|
| 98 | // C'mon, you should cool slowly if you want boltzmann selection to be effective. |
---|
| 99 | state.output.fatal("For best results, try to set your temperature to cool to 0 a more slowly. This can be acheived by increasing your starting-temperature and/or decreasing your cooling rate.\nstarting-temperatire/cooling-rate: " + startingTemperature + " / " + coolingRate); |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | int total_generations = state.numGenerations; |
---|
| 103 | if (total_generations == 0) |
---|
| 104 | { |
---|
| 105 | //Load from parameter database!! |
---|
| 106 | state.output.fatal("Hey now, we gotta load the total_generations from the param DB"); |
---|
| 107 | } |
---|
| 108 | |
---|
| 109 | if ((startingTemperature - (coolingRate * total_generations)) > 0) |
---|
| 110 | { |
---|
| 111 | //Either your cooling rate is to low, or your starting temp is too high, because at this rate you will never cool to 0! (kind of essential to reaping the benefits of boltzmann selection) |
---|
| 112 | state.output.warning("If you want BoltzmannnSelection to be effective, your temperature should cool to 0 before all generations have passed. Make sure that (starting-temperature - (cooling-rate * generations)) <= 0."); |
---|
| 113 | } |
---|
| 114 | |
---|
| 115 | } |
---|
| 116 | |
---|
| 117 | // completely override FitProportionateSelection.prepareToProduce |
---|
| 118 | public void prepareToProduce(final EvolutionState s, |
---|
| 119 | final int subpopulation, |
---|
| 120 | final int thread) |
---|
| 121 | { |
---|
| 122 | // load fitnesses |
---|
| 123 | fitnesses = new float[s.population.subpops[subpopulation].individuals.length]; |
---|
| 124 | for(int x=0;x<fitnesses.length;x++) |
---|
| 125 | { |
---|
| 126 | fitnesses[x] = (float) boltzmannExpectedValue( |
---|
| 127 | ((Individual)(s.population.subpops[subpopulation].individuals[x])).fitness.fitness(), |
---|
| 128 | s); // adjust the fitness proportion according to current temperature. |
---|
| 129 | if (fitnesses[x] < 0) // uh oh |
---|
| 130 | s.output.fatal("Discovered a negative fitness value. BoltzmannnSelection requires that all fitness values be non-negative(offending subpopulation #" + subpopulation + ")"); |
---|
| 131 | } |
---|
| 132 | |
---|
| 133 | // organize the distribution. All zeros in fitness is fine |
---|
| 134 | RandomChoice.organizeDistribution(fitnesses, true); |
---|
| 135 | } |
---|
| 136 | |
---|
| 137 | private double boltzmannExpectedValue(double fitness, final EvolutionState s) |
---|
| 138 | { |
---|
| 139 | double current_temperature = startingTemperature - (coolingRate * s.generation); |
---|
| 140 | if (current_temperature < 1.0) |
---|
| 141 | return fitness; |
---|
| 142 | return Math.exp(fitness/current_temperature); |
---|
| 143 | } |
---|
| 144 | |
---|
| 145 | } |
---|