Changeset 14484
 Timestamp:
 12/13/16 08:02:53 (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
r14477 r14484 101 101 var evaluations = 0; 102 102 var quality = scope.Fitness; 103 var bestQuality = quality;104 103 if (double.IsNaN(quality)) { 105 104 Evaluate(scope, token); … … 108 107 if (evaluations >= maxEvals) return evaluations; 109 108 } 109 var bestQuality = quality; 110 110 var currentScope = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)scope.Clone(); 111 111 var current = currentScope.Solution; 112 Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null; 113 var bestOfTheWalkF = double.NaN; 112 114 113 115 var tabu = new double[current.Length, current.Length]; … … 121 123 // this dictionary holds the last relevant links 122 124 var links = new BidirectionalDictionary<int, int>(); 123 bool allMoveTabu; 125 Move bestOfTheRest = null; 126 var bestOfTheRestF = double.NaN; 127 var lastAppliedMove = 1; 124 128 for (var iter = 0; iter < int.MaxValue; iter++) { 125 allMoveTabu = true;126 129 // clear the dictionary before a new pass through the array is made 127 130 links.Clear(); … … 134 137 135 138 var next = current[i]; 136 foreach (var move in MoveGenerator.GenerateForItem(i, next, links)) { 137 // we intend to break link i > next 138 var qualityToBreak = tabu[i, next]; 139 move.Apply(current); 140 var qualityToRestore = tabu[i, current[i]]; // current[i] is new next 141 Evaluate(currentScope, token); 142 evaluations++; 143 var moveF = currentScope.Fitness; 144 var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak) 145 && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore); 146 if (isNotTabu) allMoveTabu = false; 147 var isImprovement = FitnessComparer.IsBetter(maximization, moveF, bestQuality); 148 if (isNotTabu  isImprovement) { 139 140 if (lastAppliedMove == i) { 141 if (bestOfTheRest != null) { 142 bestOfTheRest.Apply(current); 143 currentScope.Fitness = bestOfTheRestF; 144 quality = bestOfTheRestF; 149 145 if (maximization) { 150 tabu[i, next] = Math.Max(tabu[i, next], moveF);151 tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);146 tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF); 147 tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF); 152 148 } else { 153 tabu[i, next] = Math.Min(tabu[i, next], moveF);154 tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);149 tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF); 150 tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF); 155 151 } 156 quality = moveF; 157 if (isImprovement) bestQuality = quality; 158 159 move.UpdateLinks(links); 160 break; 161 } else move.Undo(current); 162 if (evaluations >= maxEvals) break; 152 if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) { 153 bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone(); 154 bestOfTheWalkF = bestOfTheRestF; 155 } 156 bestOfTheRest = null; 157 bestOfTheRestF = double.NaN; 158 lastAppliedMove = i; 159 } else { 160 lastAppliedMove = 1; 161 } 162 break; 163 } else { 164 foreach (var move in MoveGenerator.GenerateForItem(i, next, links)) { 165 // we intend to break link i > next 166 var qualityToBreak = tabu[i, next]; 167 move.Apply(current); 168 var qualityToRestore = tabu[i, current[i]]; // current[i] is new next 169 Evaluate(currentScope, token); 170 evaluations++; 171 var moveF = currentScope.Fitness; 172 var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak) 173 && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore); 174 var isImprovement = FitnessComparer.IsBetter(maximization, moveF, quality); 175 var isAspired = FitnessComparer.IsBetter(maximization, moveF, bestQuality); 176 if ((isNotTabu && isImprovement)  isAspired) { 177 if (maximization) { 178 tabu[i, next] = Math.Max(tabu[i, next], moveF); 179 tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF); 180 } else { 181 tabu[i, next] = Math.Min(tabu[i, next], moveF); 182 tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF); 183 } 184 quality = moveF; 185 if (isAspired) bestQuality = quality; 186 187 move.UpdateLinks(links); 188 189 if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) { 190 bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone(); 191 bestOfTheWalkF = moveF; 192 } 193 194 bestOfTheRest = null; 195 bestOfTheRestF = double.NaN; 196 lastAppliedMove = i; 197 break; 198 } else { 199 if (isNotTabu) { 200 if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheRestF)) { 201 bestOfTheRest = move; 202 bestOfTheRestF = moveF; 203 } 204 } 205 move.Undo(current); 206 currentScope.Fitness = quality; 207 } 208 if (evaluations >= maxEvals) break; 209 } 163 210 } 164 211 links.RemoveBySecond(i); … … 167 214 if (token.IsCancellationRequested) break; 168 215 } 169 if (allMoveTabu) break; 216 if (lastAppliedMove == 1) { // no move has been applied 217 if (bestOfTheRest != null) { 218 var i = bestOfTheRest.Item; 219 var next = current[i]; 220 bestOfTheRest.Apply(current); 221 currentScope.Fitness = bestOfTheRestF; 222 quality = bestOfTheRestF; 223 if (maximization) { 224 tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF); 225 tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF); 226 } else { 227 tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF); 228 tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF); 229 } 230 if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) { 231 bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone(); 232 bestOfTheWalkF = bestOfTheRestF; 233 } 234 235 bestOfTheRest = null; 236 bestOfTheRestF = double.NaN; 237 } else break; 238 } 170 239 if (evaluations >= maxEvals) break; 171 240 if (token.IsCancellationRequested) break; 241 } 242 if (bestOfTheWalk != null) { 243 scope.Solution = bestOfTheWalk; 244 scope.Fitness = bestOfTheWalkF; 172 245 } 173 246 return evaluations;
Note: See TracChangeset
for help on using the changeset viewer.