| 1 | package de.uka.ipd.sdq.tcfmoop.terminationcriteria; |
| 2 | |
| 3 | import java.util.LinkedList; |
| 4 | import java.util.List; |
| 5 | |
| 6 | import org.opt4j.core.Archive; |
| 7 | import org.opt4j.core.DoubleValue; |
| 8 | import org.opt4j.core.Individual; |
| 9 | import org.opt4j.core.Objective; |
| 10 | import org.opt4j.core.Population; |
| 11 | import org.opt4j.core.Value; |
| 12 | import org.opt4j.core.Objective.Sign; |
| 13 | |
| 14 | import de.uka.ipd.sdq.tcfmoop.config.IConfiguration; |
| 15 | import de.uka.ipd.sdq.tcfmoop.config.InsignificantSetQualityImprovementConfig; |
| 16 | import de.uka.ipd.sdq.tcfmoop.config.InsignificantSetQualityImprovementConfig.ValueDifference; |
| 17 | import de.uka.ipd.sdq.tcfmoop.outputtree.Node; |
| 18 | import de.uka.ipd.sdq.tcfmoop.outputtree.Tree; |
| 19 | import de.uka.ipd.sdq.tcfmoop.outputtree.Node.NodeType; |
| 20 | |
| 21 | /** |
| 22 | * @author Atanas Dimitrov |
| 23 | */ |
| 24 | public class InsignificantSetQualityImprovementCriterion extends |
| 25 | AbstractTerminationCriterion { |
| 26 | |
| 27 | //List of Average/MaxMin values archives for all objectives for x generations. |
| 28 | private List<AverageValuesArchive> averageValueArchive = new LinkedList<AverageValuesArchive>(); |
| 29 | //the n-x. set to compare with |
| 30 | private Integer pastIterationNumber; |
| 31 | |
| 32 | //OutputNodes |
| 33 | //dynamic |
| 34 | private Node generationToCompareWithNode; |
| 35 | private Node objectivesNode; |
| 36 | |
| 37 | public InsignificantSetQualityImprovementCriterion(IConfiguration conf, Population population, |
| 38 | Archive archive) { |
| 39 | super(conf, population, archive); |
| 40 | if((conf instanceof InsignificantSetQualityImprovementConfig) && conf.validateConfiguration()){ |
| 41 | this.pastIterationNumber = ((InsignificantSetQualityImprovementConfig)(conf)).getComparisionGenerations(); |
| 42 | this.initializeObjectives(((InsignificantSetQualityImprovementConfig)(conf)).getValueDifferences()); |
| 43 | }else{ |
| 44 | throw new RuntimeException("InsignificantSetQualityImprovementCriterion.initialize: " + |
| 45 | "wrong or invalid configuration object"); |
| 46 | } |
| 47 | initializeOutputTree(); |
| 48 | } |
| 49 | |
| 50 | private void initializeOutputTree(){ |
| 51 | this.outputInformation.updateValue("Insignificant Set Quality Improvement"); |
| 52 | this.outputInformation.getChildren().clear(); |
| 53 | this.objectivesNode = this.outputInformation.addChild("Objectives", NodeType.PARAMETER_GROUP); |
| 54 | |
| 55 | for(AverageValuesArchive ava : this.averageValueArchive){ |
| 56 | Tree temp = new Tree(ava.objective.getName(), NodeType.PARAMETER_GROUP); |
| 57 | temp.addChild("Current Average: " + ava.getCurrentAverage(), NodeType.PARAMETER); |
| 58 | temp.addChild("Difference current/required: " + ava.getCurrentAverageDifference()+ "/" + ava.requiredAveragesDifference, NodeType.PARAMETER); |
| 59 | this.objectivesNode.attachSubtree(temp); |
| 60 | } |
| 61 | this.generationToCompareWithNode = this.outputInformation.addChild("Current Generation is compared with : " + this.pastIterationNumber + " generations ago", NodeType.PARAMETER); |
| 62 | this.outputInformation.getChildren().add(this.suggestedStop); |
| 63 | } |
| 64 | |
| 65 | /** |
| 66 | * Transforms the supplied objective names into references to real existing objective objects. |
| 67 | */ |
| 68 | private void initializeObjectives(List<ValueDifference> valueDiferencesList){ |
| 69 | for(ValueDifference vd : valueDiferencesList){ |
| 70 | try { |
| 71 | this.averageValueArchive.add(new AverageValuesArchive(vd.objective, new DoubleValue(vd.averageImprovement), new DoubleValue(vd.maxMinImprovement), this.pastIterationNumber)); |
| 72 | } catch (Exception e) { |
| 73 | System.out.println(e.getMessage()); |
| 74 | e.printStackTrace(); |
| 75 | } |
| 76 | } |
| 77 | } |
| 78 | |
| 79 | /** |
| 80 | * {@inheritDoc} |
| 81 | * Implements the Insignificant Set Quality Improvement Criterion: This criterion compares the averages |
| 82 | * minimum/maximum values of all or of part of the quality criteria in the pareto optimal set of the |
| 83 | * n. iteration with the pareto optimal set of the n-x. iteration. If changes are insignificant |
| 84 | * this criterion reports that the optimization should stop. |
| 85 | */ |
| 86 | @Override |
| 87 | public void evaluateImpl(int iteration, long currentTime){ |
| 88 | this.evaluationResult = true; |
| 89 | |
| 90 | for(AverageValuesArchive ava : this.averageValueArchive){ |
| 91 | double newAverage = this.getAverage(ava.objective); |
| 92 | double newMaxMin = this.getMaxMin(ava.objective); |
| 93 | ava.update(newAverage, newMaxMin); |
| 94 | |
| 95 | if(this.evaluationResult == true){ |
| 96 | this.evaluationResult = ava.getIsChangeInsignificant(); |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | /** |
| 102 | * Calculate the average of the objective o for the current iteration. |
| 103 | * @param o The Objective to calculate the average for. |
| 104 | * @return the average value of the Objective o in the n. iteration. |
| 105 | */ |
| 106 | private double getAverage(Objective o){ |
| 107 | double sum = 0; |
| 108 | |
| 109 | for(Individual indi : this.archive){ |
| 110 | sum += indi.getObjectives().get(o).getDouble(); |
| 111 | } |
| 112 | |
| 113 | return (sum/archive.size()); |
| 114 | } |
| 115 | |
| 116 | /** |
| 117 | * Discover the maximum (by maximizing) or minimum (by minimizing) value of the objective o in the n. iteration. |
| 118 | * @param o The Objective to calculate the average for. |
| 119 | * @return the maximum (by maximizing) or minimum (by minimizing) value of the objective o in the n. iteration. |
| 120 | */ |
| 121 | private double getMaxMin(Objective o){ |
| 122 | double currentMaxMin; |
| 123 | |
| 124 | if(o.getSign() == Sign.MAX){ |
| 125 | currentMaxMin = Double.NEGATIVE_INFINITY; |
| 126 | for(Individual indi : this.archive){ |
| 127 | if(indi.getObjectives().get(o).getDouble() > currentMaxMin){ |
| 128 | currentMaxMin = indi.getObjectives().get(o).getDouble(); |
| 129 | } |
| 130 | } |
| 131 | }else{ |
| 132 | currentMaxMin = Double.POSITIVE_INFINITY; |
| 133 | for(Individual indi : this.archive){ |
| 134 | if(indi.getObjectives().get(o).getDouble() < currentMaxMin){ |
| 135 | currentMaxMin = indi.getObjectives().get(o).getDouble(); |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | |
| 140 | return currentMaxMin; |
| 141 | } |
| 142 | |
| 143 | /** |
| 144 | * {@inheritDoc} |
| 145 | */ |
| 146 | @Override |
| 147 | public void updateOutputInformation() { |
| 148 | |
| 149 | for(Node objectiveNode : this.objectivesNode.getChildren()){ |
| 150 | for(AverageValuesArchive ava : this.averageValueArchive){ |
| 151 | if(objectiveNode.getValue().equals(ava.objective.getName())){ |
| 152 | objectiveNode.getChildren().get(0).updateValue("Current Average: " + ava.getCurrentAverage()); |
| 153 | objectiveNode.getChildren().get(1).updateValue("Difference current/required: " + ava.getCurrentAverageDifference()+ "/" + ava.requiredAveragesDifference); |
| 154 | } |
| 155 | } |
| 156 | } |
| 157 | this.generationToCompareWithNode.updateValue("Current Generation is compared with : " + this.pastIterationNumber + " generations ago"); |
| 158 | } |
| 159 | |
| 160 | private class AverageValuesArchive{ |
| 161 | //The Objective this archive stores history for |
| 162 | public final Objective objective; |
| 163 | //The minimum required Differences. Everything below these percentages is considered insignificant |
| 164 | public final Value<?> requiredAveragesDifference; |
| 165 | public final Value<?> requiredMaxMinDifference; |
| 166 | //Archives for the average values and for the max/min values for x iterations. |
| 167 | private LinkedList<Double> averageValues = new LinkedList<Double>(); |
| 168 | private LinkedList<Double> maxMinValues = new LinkedList<Double>(); |
| 169 | //The percentage differences between the n. and the n-x. iteration value of the average and minMin |
| 170 | private double currentAveragesDifference = 0; |
| 171 | private double currentMaxMinDifference = 0; |
| 172 | //The x of the n-x. iteration |
| 173 | private int pastIterationNumber = 0; |
| 174 | //Denotes whether the made change was insignificant or not |
| 175 | private boolean isChangeInsignificant = false; |
| 176 | |
| 177 | /** |
| 178 | * Represents an archive that stores average values and max/min values of the objective for x generations. |
| 179 | * @param objective The Objective |
| 180 | * @param requiredAveragesDifference The minimum required average Differences. A percentage value in the interval [0, 1] |
| 181 | * @param requiredMaxMinDifference The minimum required max/min Differences. A percentage value in the interval [0, 1] |
| 182 | * @param pastIterationNumber The x of the n-x. iteration ( >= 1 ) |
| 183 | * @throws Exception If the required conditions are not obeyed. |
| 184 | */ |
| 185 | public AverageValuesArchive(Objective objective, Value<?> requiredAveragesDifference, Value<?> requiredMaxMinDifference, int pastIterationNumber) throws Exception{ |
| 186 | if(requiredAveragesDifference == null || objective == null || |
| 187 | requiredAveragesDifference.getDouble() < 0 || requiredAveragesDifference.getDouble() > 1 || |
| 188 | pastIterationNumber < 1 || |
| 189 | requiredMaxMinDifference.getDouble() < 0 || requiredMaxMinDifference.getDouble() >1 ){ |
| 190 | throw new Exception("AverageValuesArchive.AverageValuesArchive: " + |
| 191 | "None of the supplied parameters should be null, maximumPercentageImprovement and minimumPercentageHighestValue must be a percentage values between 0 and 1" + |
| 192 | "pastIterationNumber must be at least 1"); |
| 193 | } |
| 194 | this.objective = objective; |
| 195 | this.requiredAveragesDifference = requiredAveragesDifference; |
| 196 | this.requiredMaxMinDifference = requiredMaxMinDifference; |
| 197 | this.pastIterationNumber = pastIterationNumber; |
| 198 | } |
| 199 | |
| 200 | /** |
| 201 | * Update the archive with another tuple of (average, maxmin) - values. |
| 202 | * Calling this function will automatically make all required changes to the archive including |
| 203 | * setup, evaluation and cleanup. Call getIsChangeInsignificant() afterwards to see the result |
| 204 | * of the evaluation. |
| 205 | * @param newAverageValue the average value for the objective in the n. iteration |
| 206 | * @param newMaximumValue the maximum/minimum value for the objective in the n. iteration |
| 207 | */ |
| 208 | public void update(double newAverageValue, double newMaxMinValue){ |
| 209 | this.averageValues.addFirst(newAverageValue); |
| 210 | this.maxMinValues.addFirst(newMaxMinValue); |
| 211 | |
| 212 | if(averageValues.size() > pastIterationNumber){ |
| 213 | |
| 214 | this.currentAveragesDifference = Math.abs((this.averageValues.getFirst() / this.averageValues.getLast()) - 1); |
| 215 | this.currentMaxMinDifference = Math.abs((this.maxMinValues.getFirst() / this.maxMinValues.getLast()) - 1); |
| 216 | |
| 217 | if(this.currentAveragesDifference <= this.requiredAveragesDifference.getDouble() && |
| 218 | this.currentMaxMinDifference <= this.requiredMaxMinDifference.getDouble()){ |
| 219 | this.isChangeInsignificant = true; |
| 220 | }else{ |
| 221 | this.isChangeInsignificant = false; |
| 222 | } |
| 223 | |
| 224 | this.averageValues.removeLast(); |
| 225 | this.maxMinValues.removeLast(); |
| 226 | } |
| 227 | } |
| 228 | |
| 229 | /** |
| 230 | * Returns the result of the evaluation of the archive. |
| 231 | * @return the result of the evaluation of the archive. |
| 232 | */ |
| 233 | public boolean getIsChangeInsignificant(){ |
| 234 | return this.isChangeInsignificant; |
| 235 | } |
| 236 | |
| 237 | /** |
| 238 | * Returns the difference between the averages of the objective from the n. and the n-x. iterations. Percentage value in the interval [0, 1] |
| 239 | * @return the difference between the averages of the objective from the n. and the n-x. iterations. Percentage value in the interval [0, 1] |
| 240 | */ |
| 241 | public double getCurrentAverageDifference(){ |
| 242 | return this.currentAveragesDifference; |
| 243 | } |
| 244 | |
| 245 | /** |
| 246 | * Returns the difference between the maxmin of the objective from the n. and the n-x. iterations. Percentage value in the interval [0, 1] |
| 247 | * @return the difference between the maxmin of the objective from the n. and the n-x. iterations. Percentage value in the interval [0, 1] |
| 248 | */ |
| 249 | public double getCurrentMaxMinDifference(){ |
| 250 | return this.currentMaxMinDifference; |
| 251 | } |
| 252 | |
| 253 | /** |
| 254 | * Returns the average of the objective from the n. iterations. |
| 255 | * @return the average of the objective from the n. iterations. |
| 256 | */ |
| 257 | public double getCurrentAverage(){ |
| 258 | if(this.averageValues.isEmpty()){ |
| 259 | return 0; |
| 260 | }else{ |
| 261 | return this.averageValues.getFirst(); |
| 262 | } |
| 263 | } |
| 264 | } |
| 265 | } |