| 1 | package de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.startingPopulation.impl; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.Collection; |
| 5 | import java.util.LinkedList; |
| 6 | import java.util.List; |
| 7 | import java.util.Random; |
| 8 | |
| 9 | import org.eclipse.emf.ecore.EObject; |
| 10 | import org.opt4j.core.Individual; |
| 11 | import org.opt4j.core.IndividualBuilder; |
| 12 | import org.opt4j.core.optimizer.Completer; |
| 13 | import org.opt4j.core.optimizer.TerminationException; |
| 14 | |
| 15 | import de.uka.ipd.sdq.dsexplore.launch.DSEWorkflowConfiguration; |
| 16 | import de.uka.ipd.sdq.dsexplore.opt4j.genotype.DesignDecisionGenotype; |
| 17 | import de.uka.ipd.sdq.dsexplore.opt4j.operator.CopyDesignDecisionGenotype; |
| 18 | import de.uka.ipd.sdq.dsexplore.opt4j.optimizer.heuristic.startingPopulation.AbstractStartingPopulationHeuristic; |
| 19 | import de.uka.ipd.sdq.dsexplore.opt4j.representation.DSEIndividual; |
| 20 | import de.uka.ipd.sdq.pcm.core.entity.Entity; |
| 21 | import de.uka.ipd.sdq.pcm.designdecision.AllocationDegree; |
| 22 | import de.uka.ipd.sdq.pcm.designdecision.Choice; |
| 23 | import de.uka.ipd.sdq.pcm.designdecision.ContinousRangeChoice; |
| 24 | import de.uka.ipd.sdq.pcm.designdecision.ContinuousProcessingRateDegree; |
| 25 | import de.uka.ipd.sdq.pcm.designdecision.DegreeOfFreedomInstance; |
| 26 | import de.uka.ipd.sdq.pcm.designdecision.ClassChoice; |
| 27 | import de.uka.ipd.sdq.pcm.resourceenvironment.ResourceContainer; |
| 28 | |
| 29 | /** |
| 30 | * Class implements a basic strategy to implement a heuristic that generates a starting |
| 31 | * population. The user specifies minNumerOfResourceContainers and maxNumberOfResourceContainers. Then |
| 32 | * the algorithm will generate numberOfCandidatesPerAllocationLevel individuals for each resource container |
| 33 | * number ("allocation level") between minNumberOfResourceContainers and maxNumberOfResourceContainers using a random allocation |
| 34 | * of components (resp. allocation contexts) to resource containers and the default processing rate (as used |
| 35 | * by firstIndividual. For each allocation level all individuals are evaluated and the Pareto optimal |
| 36 | * candidates are put into the population. Then four new individuals are generated for each Pareto optimal |
| 37 | * individual in the population. These new individuals use four different processing rates: minimum processing |
| 38 | * rate, maximum processing rate, lower processing rate (mean between default and minimum) and higher processing rate |
| 39 | * (mean between default and maximum). All of them are put into the population as well. |
| 40 | * @author Tom Beyer |
| 41 | * |
| 42 | */ |
| 43 | public class StartingPopulationHeuristicImpl extends AbstractStartingPopulationHeuristic { |
| 44 | private int minNumberOfResourceContainers; |
| 45 | private int maxNumberOfResourceContainers; |
| 46 | private final static int MAX_TRIES = 50; |
| 47 | // private final double thresholdMaxUtilisation = 0.70; |
| 48 | private int numberOfCandidatesPerAllocationLevel; |
| 49 | public enum PROCESSING_RATE_LEVEL {MIN, LESS, DEFAULT, MORE, MAX}; |
| 50 | |
| 51 | /** |
| 52 | * |
| 53 | * @param configuration As defined by the user in the GUI. |
| 54 | */ |
| 55 | public StartingPopulationHeuristicImpl(DSEWorkflowConfiguration configuration) { |
| 56 | super(configuration); |
| 57 | minNumberOfResourceContainers = configuration.getMinNumberOfResourceContainers(); |
| 58 | maxNumberOfResourceContainers = configuration.getMaxNumberOfResourceContainers(); |
| 59 | numberOfCandidatesPerAllocationLevel = configuration.getNumberOfCandidatesPerAllocationLevel(); |
| 60 | } |
| 61 | |
| 62 | /** |
| 63 | * |
| 64 | * @param numberOfComponents |
| 65 | * @param numberOfResourceContainers |
| 66 | * @return Calculates the number of components on each resource container when using numberOfComponents allocation |
| 67 | * contexts and numberOfResourceContainers resource containers. Integer represents number of components/allocation |
| 68 | * contexts and each resource container. Size of array will be numberOfResourceContainers. |
| 69 | */ |
| 70 | public static ArrayList<Integer> getNumberOfComponentsPerResourceContainer(int numberOfComponents, int numberOfResourceContainers) { |
| 71 | if (numberOfResourceContainers <= 0 || numberOfComponents < 0) { |
| 72 | throw new IllegalArgumentException(); |
| 73 | } |
| 74 | // calculate number of resource containers with floor(numberOfComponents/numberOfResourceContainers) components |
| 75 | int numberOfServersWithLessComponents = (int) ((numberOfComponents - Math.ceil(((double)numberOfComponents)/((double)numberOfResourceContainers))*numberOfResourceContainers)/ |
| 76 | (Math.floor(((double)numberOfComponents)/((double)numberOfResourceContainers))-Math.ceil(((double)numberOfComponents)/((double)numberOfResourceContainers)))); |
| 77 | ArrayList<Integer> numberOfComponentsPerResourceContainer = new ArrayList<Integer>(numberOfResourceContainers); |
| 78 | for (int i = 1; i <= numberOfResourceContainers; i++) { |
| 79 | if (i <= numberOfServersWithLessComponents) { |
| 80 | numberOfComponentsPerResourceContainer.add((int)Math.floor(((double)numberOfComponents)/((double)numberOfResourceContainers))); |
| 81 | } else { |
| 82 | numberOfComponentsPerResourceContainer.add((int)Math.ceil(((double)numberOfComponents)/((double)numberOfResourceContainers))); |
| 83 | } |
| 84 | } |
| 85 | return numberOfComponentsPerResourceContainer; |
| 86 | } |
| 87 | |
| 88 | /** |
| 89 | * Used to generate starting population as described in class documentation. |
| 90 | * |
| 91 | * FIXME: Must only use those servers that are allowed in designdecisions. |
| 92 | */ |
| 93 | public Collection<DSEIndividual> getStartingPopulation(Completer completer, IndividualBuilder individualBuilder, DSEIndividual baseIndividual) { |
| 94 | Collection<DSEIndividual> result = new LinkedList<DSEIndividual>(); |
| 95 | // default processing rate |
| 96 | Collection<DSEIndividual> population = getStartingPopulationWithDefaultProcessingRate(completer, individualBuilder, baseIndividual); |
| 97 | // max processing rate |
| 98 | result.addAll(getAdjustedProcessingRatePopulation(population, individualBuilder, PROCESSING_RATE_LEVEL.MAX)); |
| 99 | // min processing rate |
| 100 | result.addAll(getAdjustedProcessingRatePopulation(population, individualBuilder, PROCESSING_RATE_LEVEL.MIN)); |
| 101 | // less processing rate |
| 102 | result.addAll(getAdjustedProcessingRatePopulation(population, individualBuilder, PROCESSING_RATE_LEVEL.LESS)); |
| 103 | // more processing rate |
| 104 | result.addAll(getAdjustedProcessingRatePopulation(population, individualBuilder, PROCESSING_RATE_LEVEL.MORE)); |
| 105 | result.addAll(population); |
| 106 | return result; |
| 107 | } |
| 108 | |
| 109 | |
| 110 | private Collection<DSEIndividual> getAdjustedProcessingRatePopulation(Collection<DSEIndividual> population, IndividualBuilder individualBuilder, PROCESSING_RATE_LEVEL processingRateLevel) { |
| 111 | CopyDesignDecisionGenotype copy = new CopyDesignDecisionGenotype(); |
| 112 | Collection<DSEIndividual> result = new LinkedList<DSEIndividual>(); |
| 113 | for (DSEIndividual individual : population) { |
| 114 | DSEIndividual newIndividual = (DSEIndividual)individualBuilder.build(copy.copy((DesignDecisionGenotype)individual.getGenotype())); |
| 115 | result.add(newIndividual); |
| 116 | } |
| 117 | for (DSEIndividual individual : result) { |
| 118 | for (Choice choice : individual.getGenotype()) { |
| 119 | if (choice instanceof ContinousRangeChoice) { |
| 120 | ContinousRangeChoice continousRangeChoice = (ContinousRangeChoice) choice; |
| 121 | DegreeOfFreedomInstance DegreeOfFreedomInstance = choice.getDegreeOfFreedomInstance(); |
| 122 | if (DegreeOfFreedomInstance instanceof ContinuousProcessingRateDegree) { |
| 123 | ContinuousProcessingRateDegree processingRateDegree = (ContinuousProcessingRateDegree) DegreeOfFreedomInstance; |
| 124 | // actually adjust processing rate. Respect |
| 125 | // maximum and minimum allowed value of processing rate |
| 126 | double newProcessingRate = continousRangeChoice.getChosenValue(); |
| 127 | switch (processingRateLevel) { |
| 128 | case MIN: |
| 129 | newProcessingRate = processingRateDegree.getFrom(); |
| 130 | break; |
| 131 | case LESS: |
| 132 | newProcessingRate = (processingRateDegree.getFrom() + continousRangeChoice.getChosenValue())/2; |
| 133 | break; |
| 134 | case DEFAULT: |
| 135 | newProcessingRate = continousRangeChoice.getChosenValue(); |
| 136 | break; |
| 137 | case MORE: |
| 138 | newProcessingRate = (processingRateDegree.getTo() + continousRangeChoice.getChosenValue())/2; |
| 139 | break; |
| 140 | case MAX: |
| 141 | newProcessingRate = processingRateDegree.getTo(); |
| 142 | break; |
| 143 | } |
| 144 | continousRangeChoice.setChosenValue(newProcessingRate); |
| 145 | } |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | return result; |
| 150 | } |
| 151 | |
| 152 | // public Collection<DSEIndividual> getStartingPopulation(Completer completer, IndividualBuilder individualBuilder, int populationSize, DSEIndividual firstIndividual) { |
| 153 | // Collection<DSEIndividual> population = new LinkedList<DSEIndividual>(); |
| 154 | // CopyDesignDecisionGenotype copy = new CopyDesignDecisionGenotype(); |
| 155 | // if (minNumberOfResourceContainers > maxNumberOfResourceContainers) { |
| 156 | // throw new IllegalArgumentException("Minimum number of resource containers cannot be larger than maximum number of containers."); |
| 157 | // } |
| 158 | // if (maxNumberOfResourceContainers > getResourceContainers().size()) { |
| 159 | // throw new IllegalArgumentException("There are not enough resource containers available."); |
| 160 | // } |
| 161 | // int tries = 0; |
| 162 | // while (population.size() < populationSize && tries < populationSize + MAX_TRIES) { |
| 163 | // int randomNumberOfResourceContainers = getRandomInt(minNumberOfResourceContainers, maxNumberOfResourceContainers); |
| 164 | // ArrayList<Integer> allocation = getNumberOfComponentsPerResourceContainer(getAllocationContexts().size(), randomNumberOfResourceContainers); |
| 165 | // DSEIndividual newIndividual = (DSEIndividual)individualBuilder.build(copy.copy((DesignDecisionGenotype)firstIndividual.getGenotype())); |
| 166 | // newIndividual = (DSEIndividual) getRandomIndividual(allocation, newIndividual); |
| 167 | // if (!population.contains(newIndividual)) { |
| 168 | // try { |
| 169 | // completer.complete(newIndividual); |
| 170 | // if(UtilisationHelper.getMaxUtilisation((DSEIndividual) newIndividual) <= thresholdMaxUtilisation) { |
| 171 | // population.add(newIndividual); |
| 172 | // } |
| 173 | // } catch (TerminationException e) { |
| 174 | // // nothing to do here. we don't add the individual to the population |
| 175 | // } catch (NullPointerException e) { |
| 176 | // // nothing to do here. we don't add the individual to the population |
| 177 | // } |
| 178 | // |
| 179 | // } |
| 180 | // tries++; |
| 181 | // } |
| 182 | // return population; |
| 183 | // } |
| 184 | |
| 185 | private Collection<DSEIndividual> getStartingPopulationWithDefaultProcessingRate(Completer completer, IndividualBuilder individualBuilder, |
| 186 | DSEIndividual firstIndividual) { |
| 187 | Collection<DSEIndividual> population = new LinkedList<DSEIndividual>(); |
| 188 | CopyDesignDecisionGenotype copy = new CopyDesignDecisionGenotype(); |
| 189 | if (minNumberOfResourceContainers > maxNumberOfResourceContainers) { |
| 190 | throw new IllegalArgumentException( |
| 191 | "Minimum number of resource containers cannot be larger than maximum number of containers. Check your starting population heuristic settings."); |
| 192 | } |
| 193 | if (maxNumberOfResourceContainers > getResourceContainers().size()) { |
| 194 | throw new IllegalArgumentException("There are not enough resource containers available. Decrease the \"maximum number of resource containers\" setting in the starting population heuristic configuration in your launch configuration."); |
| 195 | } |
| 196 | for (int numberOfResourceContainers = minNumberOfResourceContainers; numberOfResourceContainers <= maxNumberOfResourceContainers; numberOfResourceContainers++) { |
| 197 | List<DSEIndividual> individualsForAllocation = new ArrayList<DSEIndividual>(); |
| 198 | int tries = 0; |
| 199 | while (individualsForAllocation.size() < numberOfCandidatesPerAllocationLevel && tries <= numberOfCandidatesPerAllocationLevel + MAX_TRIES) { |
| 200 | ArrayList<Integer> allocation = getNumberOfComponentsPerResourceContainer(getAllocationContexts() |
| 201 | .size(), numberOfResourceContainers); |
| 202 | DSEIndividual newIndividual = (DSEIndividual) individualBuilder.build(copy |
| 203 | .copy((DesignDecisionGenotype) firstIndividual.getGenotype())); |
| 204 | newIndividual = (DSEIndividual) getRandomIndividual(allocation, newIndividual); |
| 205 | if (!individualsForAllocation.contains(newIndividual)) { |
| 206 | try { |
| 207 | completer.complete(newIndividual); |
| 208 | individualsForAllocation.add(newIndividual); |
| 209 | } catch (TerminationException e) { |
| 210 | // nothing to do here. we don't add the individual to |
| 211 | // the population |
| 212 | } catch (NullPointerException e) { |
| 213 | // nothing to do here. we don't add the individual to |
| 214 | // the population |
| 215 | } |
| 216 | } |
| 217 | tries++; |
| 218 | } |
| 219 | population.addAll(getParetoOptimalIndividuals(individualsForAllocation)); |
| 220 | } |
| 221 | return population; |
| 222 | } |
| 223 | |
| 224 | |
| 225 | private List<DSEIndividual> getParetoOptimalIndividuals(List<DSEIndividual> individuals) { |
| 226 | if (individuals.isEmpty()) { |
| 227 | return null; |
| 228 | } |
| 229 | List<DSEIndividual> toBeRemoved = new ArrayList<DSEIndividual>(individuals.size()); |
| 230 | List<DSEIndividual> result = new ArrayList<DSEIndividual>(individuals.size()); |
| 231 | |
| 232 | result.addAll(individuals); |
| 233 | |
| 234 | for (int i = 0; i < individuals.size(); i++) { |
| 235 | DSEIndividual indiv1 = individuals.get(i); |
| 236 | for (int j = i + 1; j < individuals.size(); j++){ |
| 237 | DSEIndividual indiv2 = individuals.get(j); |
| 238 | if (indiv1.getObjectives().dominates(indiv2.getObjectives())){ |
| 239 | toBeRemoved.add(indiv2); |
| 240 | } else if (indiv2.getObjectives().dominates(indiv1.getObjectives())){ |
| 241 | toBeRemoved.add(indiv1); |
| 242 | } |
| 243 | } |
| 244 | |
| 245 | } |
| 246 | |
| 247 | result.removeAll(toBeRemoved); |
| 248 | return result; |
| 249 | } |
| 250 | |
| 251 | private Individual getRandomIndividual(ArrayList<Integer> allocation, Individual individual) { |
| 252 | ArrayList<Integer> contexts = new ArrayList<Integer>(); |
| 253 | for (int i = 0; i < getAllocationContexts().size(); i++) { |
| 254 | contexts.add(new Integer(i)); |
| 255 | } |
| 256 | for (int i = 0; i < allocation.size(); i++) { |
| 257 | allocateRandomlyToContainer(individual, getResourceContainers().get(i), allocation.get(i), contexts); |
| 258 | } |
| 259 | return individual; |
| 260 | } |
| 261 | |
| 262 | private void allocateRandomlyToContainer(Individual individual, ResourceContainer container, int numberOfAllocationContexts, |
| 263 | ArrayList<Integer> contexts) { |
| 264 | |
| 265 | for (int i = 1; i <= numberOfAllocationContexts; i++) { |
| 266 | int randomIndex = getRandomInt(0, contexts.size()-1); |
| 267 | int randomContext = contexts.get(randomIndex); |
| 268 | allocateContextToContainer(container, randomContext, (DSEIndividual)individual); |
| 269 | contexts.remove(randomIndex); |
| 270 | } |
| 271 | } |
| 272 | |
| 273 | private void allocateContextToContainer(ResourceContainer container, int allocationContext, |
| 274 | DSEIndividual individual) { |
| 275 | int iterationCounter = 0; |
| 276 | for (Choice choice : individual.getGenotype()) { |
| 277 | if (choice instanceof ClassChoice) { |
| 278 | ClassChoice ClassChoice = (ClassChoice)choice; |
| 279 | if (ClassChoice.getDegreeOfFreedomInstance() instanceof AllocationDegree) { |
| 280 | if (iterationCounter == allocationContext) { |
| 281 | boolean foundMatchingServer = false; |
| 282 | DegreeOfFreedomInstance dof = ClassChoice.getDegreeOfFreedomInstance(); |
| 283 | if (dof instanceof AllocationDegree){ |
| 284 | List<EObject> domain = ((AllocationDegree) dof).getClassDesignOptions(); |
| 285 | for (EObject entity : domain) { |
| 286 | if (entity instanceof Entity && ((Entity)entity).getId().equals(container.getId())){ |
| 287 | ClassChoice.setChosenValue(container); |
| 288 | foundMatchingServer = true; |
| 289 | break; |
| 290 | } |
| 291 | } |
| 292 | } |
| 293 | if (!foundMatchingServer){ |
| 294 | throw new RuntimeException("Start Population Heuristic only supports design decision files that allow all components to be allocated to all servers. Sorry! Please disable the Starting population heuristic for this model."); |
| 295 | } |
| 296 | |
| 297 | } |
| 298 | } |
| 299 | iterationCounter++; |
| 300 | } |
| 301 | } |
| 302 | } |
| 303 | |
| 304 | /** |
| 305 | * Generates random int between from (inclusive) and to (inclusive) based on uniform distribution |
| 306 | * @param from |
| 307 | * @param to |
| 308 | * @return Random int with from <= return value <= to |
| 309 | */ |
| 310 | private static int getRandomInt(int from, int to) { |
| 311 | Random random = new Random(); |
| 312 | return random.nextInt(to - from + 1) + from; |
| 313 | } |
| 314 | |
| 315 | } |