| 1 | package de.uka.ipd.sdq.dsexplore.opt4j.optimizer; |
| 2 | |
| 3 | import java.util.Collection; |
| 4 | import java.util.Iterator; |
| 5 | |
| 6 | import org.apache.log4j.Logger; |
| 7 | import org.opt4j.core.Archive; |
| 8 | import org.opt4j.core.Individual; |
| 9 | import org.opt4j.core.IndividualBuilder; |
| 10 | import org.opt4j.core.Population; |
| 11 | import org.opt4j.core.optimizer.Completer; |
| 12 | import org.opt4j.core.optimizer.Control; |
| 13 | import org.opt4j.core.optimizer.Iterations; |
| 14 | import org.opt4j.core.optimizer.StopException; |
| 15 | import org.opt4j.core.optimizer.TerminationException; |
| 16 | import org.opt4j.optimizer.ea.EvolutionaryAlgorithm; |
| 17 | import org.opt4j.optimizer.ea.Mating; |
| 18 | import org.opt4j.optimizer.ea.Selector; |
| 19 | import org.opt4j.start.Constant; |
| 20 | |
| 21 | import com.google.inject.Inject; |
| 22 | |
| 23 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.startingPopulation.impl.StartingPopulationHeuristicImpl; |
| 24 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividual; |
| 25 | import de.uka.ipd.sdq.dsexplore.opt4j.start.Opt4JStarter; |
| 26 | |
| 27 | /** |
| 28 | * Copy of {@link EvolutionaryAlgorithm} that detects duplicates in the population and creates new random candidates |
| 29 | * to replace them. |
| 30 | * @author martens |
| 31 | * |
| 32 | */ |
| 33 | public class NoDuplicatesEvolutionaryAlgorithm extends EvolutionaryAlgorithm { |
| 34 | |
| 35 | /** Logger for log4j. */ |
| 36 | private static Logger logger = |
| 37 | Logger.getLogger("de.uka.ipd.sdq.dsexplore.opt4j.optimizer.NoDuplicatesEvolutionaryAlgorithm"); |
| 38 | |
| 39 | |
| 40 | /** |
| 41 | * {@inheritDoc} |
| 42 | */ |
| 43 | @Inject |
| 44 | public NoDuplicatesEvolutionaryAlgorithm( |
| 45 | Population population, |
| 46 | Archive archive, |
| 47 | IndividualBuilder individualBuilder, |
| 48 | Completer completer, |
| 49 | Control control, |
| 50 | Selector selector, |
| 51 | Mating mating, |
| 52 | @Iterations int generations, |
| 53 | @Constant(value = "alpha", namespace = EvolutionaryAlgorithm.class) int alpha, |
| 54 | @Constant(value = "mu", namespace = EvolutionaryAlgorithm.class) int mu, |
| 55 | @Constant(value = "lambda", namespace = EvolutionaryAlgorithm.class) int lambda) { |
| 56 | super(population, archive, individualBuilder, completer, control, selector, mating, generations, alpha, mu, lambda); |
| 57 | } |
| 58 | |
| 59 | /* |
| 60 | * (non-Javadoc) |
| 61 | * |
| 62 | * @see org.opt4j.core.optimizer.Optimizer#optimize() |
| 63 | */ |
| 64 | @Override |
| 65 | public void optimize() throws TerminationException, StopException { |
| 66 | |
| 67 | selector.init(alpha + lambda); |
| 68 | |
| 69 | final boolean useGeneratedStartingPopulation = Opt4JStarter.getDSEWorkflowConfig().getUseStartingPopulationHeuristic(); |
| 70 | final boolean usePredefinedPopulation = Opt4JStarter.getDSEWorkflowConfig().getPredefinedInstancesFileName() != ""; |
| 71 | if (useGeneratedStartingPopulation && ! usePredefinedPopulation) { |
| 72 | DSEIndividual firstIndividual = (DSEIndividual) individualBuilder.build(); |
| 73 | StartingPopulationHeuristicImpl startingPopulationHelper = new StartingPopulationHeuristicImpl(Opt4JStarter.getDSEWorkflowConfig()); |
| 74 | Collection<DSEIndividual> generatedStartingPopulation = startingPopulationHelper.getStartingPopulation(completer, individualBuilder, firstIndividual); |
| 75 | population.add(firstIndividual); |
| 76 | population.addAll(generatedStartingPopulation); |
| 77 | } |
| 78 | |
| 79 | int count = 0; |
| 80 | while (population.size() < alpha && count < alpha + 200) { |
| 81 | Individual i = individualBuilder.build(); |
| 82 | if (!population.contains(i)){ |
| 83 | population.add(i); |
| 84 | } |
| 85 | count ++; |
| 86 | } |
| 87 | |
| 88 | nextIteration(); |
| 89 | |
| 90 | for (int g = 0; g < generations; g++) { |
| 91 | |
| 92 | Collection<Individual> parents = selector |
| 93 | .getParents(mu, population); |
| 94 | Collection<Individual> offspring = mating.getOffspring(lambda, |
| 95 | parents); |
| 96 | |
| 97 | |
| 98 | int sizeBefore = offspring.size(); |
| 99 | //remove duplicates |
| 100 | offspring.removeAll(population); |
| 101 | |
| 102 | //we had one un-reproducible case in which the offspring list contained a null. |
| 103 | //catch this here. |
| 104 | for (Iterator<Individual> iterator = offspring.iterator(); iterator.hasNext();) { |
| 105 | Individual individual = iterator.next(); |
| 106 | if (individual == null || individual.getGenotype().size() == 0){ |
| 107 | iterator.remove(); |
| 108 | logger.warn("Encountered a null individual or empty genotype in offspring, removing it."); |
| 109 | } |
| 110 | } |
| 111 | int sizeAfter = offspring.size(); |
| 112 | |
| 113 | population.addAll(offspring); //This causes a decrease in population, TODO: get to the root of this problem |
| 114 | |
| 115 | //TODO: If the offspring contains duplicates, they should also be removed. Andere Datenstruktur (Set)? |
| 116 | if (sizeBefore > sizeAfter){ |
| 117 | int maximumTries = 100; //we do not want to get stuck here... |
| 118 | count = sizeAfter; |
| 119 | while (count < sizeBefore && count < maximumTries + sizeAfter){ |
| 120 | Individual i = individualBuilder.build(); |
| 121 | if (!population.contains(i)){ |
| 122 | completer.complete(i); |
| 123 | population.add(i); |
| 124 | count ++; |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | // evaluate offspring before selecting lames |
| 130 | completer.complete(offspring); |
| 131 | |
| 132 | |
| 133 | //Only remove so many that population is reduced to original size |
| 134 | if (population.size() > alpha){ |
| 135 | /* Get lame candidates based on Nsga2 */ |
| 136 | Collection<Individual> lames = selector |
| 137 | .getLames(population.size() - alpha, population); |
| 138 | /* Remove these lames */ |
| 139 | population.removeAll(lames); |
| 140 | } |
| 141 | |
| 142 | nextIteration(); |
| 143 | |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | } |