Changeset 15713 for branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis
- Timestamp:
- 02/02/18 16:31:42 (7 years ago)
- Location:
- branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis
- Files:
-
- 1 added
- 3 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPCharacteristicCalculator.cs
r15702 r15713 20 20 #endregion 21 21 22 using System; 23 using System.Collections.Generic; 24 using System.Linq; 22 25 using HeuristicLab.Common; 23 26 using HeuristicLab.Core; … … 25 28 using HeuristicLab.Optimization; 26 29 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 using HeuristicLab.Problems.QuadraticAssignment; 28 using System; 29 using System.Collections.Generic; 30 using System.Linq; 30 using HeuristicLab.Problems.GeneralizedQuadraticAssignment; 31 31 32 32 namespace HeuristicLab.Analysis.FitnessLandscape { 33 [Item(" QAP Characteristic Calculator", "")]33 [Item("GQAP Characteristic Calculator", "")] 34 34 [StorableClass] 35 public sealed class QAPCharacteristicCalculator : CharacteristicCalculator {35 public sealed class GQAPCharacteristicCalculator : CharacteristicCalculator { 36 36 37 37 [StorableConstructor] 38 private QAPCharacteristicCalculator(bool deserializing) : base(deserializing) { } 39 private QAPCharacteristicCalculator(QAPCharacteristicCalculator original, Cloner cloner) : base(original, cloner) { } 40 public QAPCharacteristicCalculator() { 41 characteristics.AddRange(new[] { "Dimension", 38 private GQAPCharacteristicCalculator(bool deserializing) : base(deserializing) { } 39 private GQAPCharacteristicCalculator(GQAPCharacteristicCalculator original, Cloner cloner) : base(original, cloner) { } 40 public GQAPCharacteristicCalculator() { 41 characteristics.AddRange(new[] { 42 "Dimension", "MNRatio", 42 43 "FlowDominance", "DistanceDominance", 43 "FlowAsymmetry", "DistanceAsymmetry",44 44 "FlowSparsity", "DistanceSparsity", 45 "FlowSkewness", "DistanceSkewness", 46 "FlowDisparity", "DistanceDisparity" }.Select(x => new StringValue(x)).ToList()); 45 "DemandDominance", "CapacityDominance", 46 "Utilization", "BasicFeasibility", 47 }.Select(x => new StringValue(x)).ToList()); 47 48 } 48 49 49 50 public override IDeepCloneable Clone(Cloner cloner) { 50 return new QAPCharacteristicCalculator(this, cloner);51 return new GQAPCharacteristicCalculator(this, cloner); 51 52 } 52 53 53 54 public override bool CanCalculate() { 54 return Problem is QuadraticAssignmentProblem;55 return Problem is GQAP; 55 56 } 56 57 57 58 public override IEnumerable<IResult> Calculate() { 58 var qap = Problem as QuadraticAssignmentProblem; 59 if (qap == null) throw new ArgumentException("Instance is not of type QuadraticAssignmentProblem"); 59 var gqap = Problem as GQAP; 60 if (gqap == null) throw new ArgumentException("Instance is not of type GQAP"); 61 var inst = gqap.ProblemInstance; 60 62 foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) { 61 63 if (chara == "Dimension") 62 yield return new Result(chara, new IntValue(qap.Weights.Rows)); 64 yield return new Result(chara, new IntValue(inst.Demands.Length)); 65 if (chara == "MNRatio") 66 yield return new Result(chara, new DoubleValue(inst.Capacities.Length / (double)inst.Demands.Length)); 63 67 if (chara == "FlowDominance") 64 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation( qap.Weights)));68 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Weights))); 65 69 if (chara == "DistanceDominance") 66 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(qap.Distances))); 67 if (chara == "FlowAsymmetry") 68 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Weights))); 69 if (chara == "DistanceAsymmetry") 70 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Distances))); 70 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Distances))); 71 71 if (chara == "FlowSparsity") 72 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity( qap.Weights)));72 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Weights))); 73 73 if (chara == "DistanceSparsity") 74 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity( qap.Distances)));75 if (chara == " FlowSkewness")76 yield return new Result(chara, new DoubleValue( DoubleMatrixCharacteristicCalculator.Skewness(qap.Weights)));77 if (chara == " DistanceSkewness")78 yield return new Result(chara, new DoubleValue( DoubleMatrixCharacteristicCalculator.Skewness(qap.Distances)));79 if (chara == " FlowDisparity")80 yield return new Result(chara, new DoubleValue( DoubleMatrixCharacteristicCalculator.Disparity(qap.Weights)));81 if (chara == " DistanceDisparity")82 yield return new Result(chara, new DoubleValue( DoubleMatrixCharacteristicCalculator.Disparity(qap.Distances)));74 yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Distances))); 75 if (chara == "DemandDominance") 76 yield return new Result(chara, new DoubleValue(inst.Demands.StandardDeviation() / inst.Demands.Average())); 77 if (chara == "CapacityDominance") 78 yield return new Result(chara, new DoubleValue(inst.Capacities.StandardDeviation() / inst.Capacities.Average())); 79 if (chara == "Utilization") 80 yield return new Result(chara, new DoubleValue(inst.Demands.Sum() / inst.Capacities.Sum())); 81 if (chara == "BasicFeasibility") 82 yield return new Result(chara, new DoubleValue(inst.Demands.Select(d => inst.Capacities.Count(c => d <= c)).Average() / inst.Capacities.Length)); 83 83 } 84 84 } -
branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs
r15702 r15713 20 20 #endregion 21 21 22 using System; 23 using System.Collections.Generic; 24 using System.Linq; 22 25 using HeuristicLab.Common; 23 26 using HeuristicLab.Core; 24 27 using HeuristicLab.Data; 25 using HeuristicLab.Encodings. PermutationEncoding;28 using HeuristicLab.Encodings.IntegerVectorEncoding; 26 29 using HeuristicLab.Optimization; 27 30 using HeuristicLab.Parameters; 28 31 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 29 using HeuristicLab.Problems. QuadraticAssignment;32 using HeuristicLab.Problems.GeneralizedQuadraticAssignment; 30 33 using HeuristicLab.Random; 31 using System;32 using System.Collections.Generic;33 using System.Linq;34 using System.Threading;35 34 36 35 namespace HeuristicLab.Analysis.FitnessLandscape { 37 [Item("Directed Walk ( QAP-specific)", "")]36 [Item("Directed Walk (GQAP-specific)", "")] 38 37 [StorableClass] 39 public class QAPDirectedWalk : CharacteristicCalculator {38 public class GQAPDirectedWalk : CharacteristicCalculator { 40 39 41 40 public IFixedValueParameter<IntValue> PathsParameter { … … 76 75 77 76 [StorableConstructor] 78 private QAPDirectedWalk(bool deserializing) : base(deserializing) { }79 private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }80 public QAPDirectedWalk() {81 characteristics.AddRange(new[] { " Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }77 private GQAPDirectedWalk(bool deserializing) : base(deserializing) { } 78 private GQAPDirectedWalk(GQAPDirectedWalk original, Cloner cloner) : base(original, cloner) { } 79 public GQAPDirectedWalk() { 80 characteristics.AddRange(new[] { "1Shift.Sharpness", "1Shift.Bumpiness", "1Shift.Flatness" } 82 81 .Select(x => new StringValue(x)).ToList()); 83 82 Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50))); … … 88 87 89 88 public override IDeepCloneable Clone(Cloner cloner) { 90 return new QAPDirectedWalk(this, cloner);89 return new GQAPDirectedWalk(this, cloner); 91 90 } 92 91 93 92 public override bool CanCalculate() { 94 return Problem is QuadraticAssignmentProblem;93 return Problem is GQAP; 95 94 } 96 95 97 96 public override IEnumerable<IResult> Calculate() { 98 97 IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister(); 99 var qap = (QuadraticAssignmentProblem)Problem;100 List< Permutation> permutations = CalculateRelinkingPoints(random,qap, Paths, LocalOptima);101 102 var trajectories = Run(random, ( QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();103 var result = PermutationPathAnalysis.GetCharacteristics(trajectories);98 var gqap = (GQAP)Problem; 99 List<IntegerVector> assignments = CalculateRelinkingPoints(random, gqap, Paths, LocalOptima); 100 101 var trajectories = Run(random, (GQAP)Problem, assignments, BestImprovement).ToList(); 102 var result = IntegerVectorPathAnalysis.GetCharacteristics(trajectories); 104 103 105 104 foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) { 106 if (chara == " Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));107 if (chara == " Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));108 if (chara == " Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));109 } 110 } 111 112 public static List< Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblemqap, int pathCount, bool localOptima) {113 var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);105 if (chara == "1Shift.Sharpness") yield return new Result("1Shift.Sharpness", new DoubleValue(result.Sharpness)); 106 if (chara == "1Shift.Bumpiness") yield return new Result("1Shift.Bumpiness", new DoubleValue(result.Bumpiness)); 107 if (chara == "1Shift.Flatness") yield return new Result("1Shift.Flatness", new DoubleValue(result.Flatness)); 108 } 109 } 110 111 public static List<IntegerVector> CalculateRelinkingPoints(IRandom random, GQAP gqap, int pathCount, bool localOptima) { 112 var assign = new IntegerVector(gqap.ProblemInstance.Demands.Length, random, 0, gqap.ProblemInstance.Capacities.Length); 114 113 if (localOptima) { 115 var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances)); 116 QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None); 117 } 118 var permutations = new List<Permutation> { perm }; 119 while (permutations.Count < pathCount + 1) { 120 perm = (Permutation)permutations.Last().Clone(); 121 BiasedShuffle(perm, random); 114 var eval = gqap.ProblemInstance.Evaluate(assign); 115 var fit = gqap.ProblemInstance.ToSingleObjective(eval); 116 OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals); 117 } 118 var points = new List<IntegerVector> { assign }; 119 while (points.Count < pathCount + 1) { 120 assign = (IntegerVector)points.Last().Clone(); 121 RelocateEquipmentManipluator.Apply(random, assign, gqap.ProblemInstance.Capacities.Length, 0); 122 122 if (localOptima) { 123 var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances)); 124 QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None); 123 var eval = gqap.ProblemInstance.Evaluate(assign); 124 var fit = gqap.ProblemInstance.ToSingleObjective(eval); 125 OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals); 125 126 } 126 if (HammingSimilarityCalculator.CalculateSimilarity(p ermutations.Last(), perm) < 0.75)127 p ermutations.Add(perm);128 } 129 130 return p ermutations;131 } 132 133 public static IEnumerable<List<Tuple< Permutation, double>>> Run(IRandom random, QuadraticAssignmentProblem qap, IEnumerable<Permutation> permutations, bool bestImprovement = true) {134 var iter = p ermutations.GetEnumerator();127 if (HammingSimilarityCalculator.CalculateSimilarity(points.Last(), assign) < 0.75) 128 points.Add(assign); 129 } 130 131 return points; 132 } 133 134 public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) { 135 var iter = points.GetEnumerator(); 135 136 if (!iter.MoveNext()) yield break; 136 137 var min = qap.LowerBound.Value;138 var max = qap.AverageQuality.Value;139 137 140 138 var start = iter.Current; … … 142 140 var end = iter.Current; 143 141 144 var walk = (bestImprovement ? BestDirectedWalk( qap, start, end) : FirstDirectedWalk(random,qap, start, end)).ToList();145 yield return walk. Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();142 var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList(); 143 yield return walk.ToList(); 146 144 start = end; 147 145 } // end paths 148 146 } 149 147 150 private static IEnumerable<Tuple< Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutationend) {151 var N = qap.Weights.Rows;148 private static IEnumerable<Tuple<IntegerVector, double>> BestDirectedWalk(GQAP gqap, IntegerVector start, IntegerVector end) { 149 var N = gqap.ProblemInstance.Demands.Length; 152 150 var sol = start; 153 var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances); 151 var evaluation = gqap.ProblemInstance.Evaluate(start); 152 var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation); 154 153 yield return Tuple.Create(sol, fitness); 155 156 var invSol = GetInverse(sol); 157 // we require at most N-1 steps to move from one permutation to another 158 for (var step = 0; step < N - 1; step++) { 154 155 var reassignments = Enumerable.Range(0, N).Select(x => { 156 if (start[x] == end[x]) return null; 157 var r = new int[N]; 158 r[x] = end[x] + 1; 159 return r; 160 }).ToArray(); 161 var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray(); 162 163 for (var step = 0; step < N; step++) { 159 164 var bestFitness = double.MaxValue; 165 Evaluation bestEvaluation = null; 160 166 var bestIndex = -1; 161 sol = (Permutation)sol.Clone(); 167 sol = (IntegerVector)sol.Clone(); 168 162 169 for (var index = 0; index < N; index++) { 163 170 if (sol[index] == end[index]) continue; 164 var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances); 171 172 var oneMove = new NMove(reassignments[index], indices[index]); 173 var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance); 174 var fit = gqap.ProblemInstance.ToSingleObjective(eval); 165 175 if (fit < bestFitness) { // QAP is minimization 166 176 bestFitness = fit; 177 bestEvaluation = eval; 167 178 bestIndex = index; 168 179 } 169 180 } 170 181 if (bestIndex >= 0) { 171 var prev = sol[bestIndex];172 Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);173 fitness += bestFitness;182 sol[bestIndex] = end[bestIndex]; 183 fitness = bestFitness; 184 evaluation = bestEvaluation; 174 185 yield return Tuple.Create(sol, fitness); 175 invSol[prev] = invSol[end[bestIndex]];176 invSol[sol[bestIndex]] = bestIndex;177 186 } else break; 178 187 } 179 188 } 180 189 181 private static IEnumerable<Tuple< Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutationend) {182 var N = qap.Weights.Rows;190 private static IEnumerable<Tuple<IntegerVector, double>> FirstDirectedWalk(IRandom random, GQAP gqap, IntegerVector start, IntegerVector end) { 191 var N = gqap.ProblemInstance.Demands.Length; 183 192 var sol = start; 184 var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances); 193 var evaluation = gqap.ProblemInstance.Evaluate(start); 194 var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation); 185 195 yield return Tuple.Create(sol, fitness); 186 196 187 var invSol = GetInverse(sol); 197 var reassignments = Enumerable.Range(0, N).Select(x => { 198 if (start[x] == end[x]) return null; 199 var r = new int[N]; 200 r[x] = end[x] + 1; 201 return r; 202 }).ToArray(); 203 var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray(); 204 188 205 // randomize the order in which improvements are tried 189 206 var order = Enumerable.Range(0, N).Shuffle(random).ToArray(); 190 // we require at most N-1 steps to move from one permutation to another 191 for (var step = 0; step < N - 1; step++) {207 208 for (var step = 0; step < N; step++) { 192 209 var bestFitness = double.MaxValue; 210 Evaluation bestEvaluation = null; 193 211 var bestIndex = -1; 194 sol = ( Permutation)sol.Clone();212 sol = (IntegerVector)sol.Clone(); 195 213 for (var i = 0; i < N; i++) { 196 214 var index = order[i]; 197 215 if (sol[index] == end[index]) continue; 198 var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances); 199 if (fit < bestFitness) { // QAP is minimization 216 217 var oneMove = new NMove(reassignments[index], indices[index]); 218 var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance); 219 var fit = gqap.ProblemInstance.ToSingleObjective(eval); 220 221 if (fit < bestFitness) { // GQAP is minimization 200 222 bestFitness = fit; 223 bestEvaluation = evaluation; 201 224 bestIndex = index; 202 if ( bestFitness < 0) break;225 if (fit < fitness) break; 203 226 } 204 227 } 205 228 if (bestIndex >= 0) { 206 var prev = sol[bestIndex];207 Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);208 fitness += bestFitness;229 sol[bestIndex] = end[bestIndex]; 230 fitness = bestFitness; 231 evaluation = bestEvaluation; 209 232 yield return Tuple.Create(sol, fitness); 210 invSol[prev] = invSol[end[bestIndex]];211 invSol[sol[bestIndex]] = bestIndex;212 233 } else break; 213 }214 }215 216 private static int[] GetInverse(Permutation p) {217 var inv = new int[p.Length];218 for (var i = 0; i < p.Length; i++) {219 inv[p[i]] = i;220 }221 return inv;222 }223 224 // permutation must be strictly different in every position225 private static void BiasedShuffle(Permutation p, IRandom random) {226 for (var i = p.Length - 1; i > 0; i--) {227 // Swap element "i" with a random earlier element (excluding itself)228 var swapIndex = random.Next(i);229 var h = p[swapIndex];230 p[swapIndex] = p[i];231 p[i] = h;232 234 } 233 235 } -
branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/IntegerVectorPathAnalysis.cs
r15702 r15713 1 1 using System; 2 2 using System.Collections.Generic; 3 using HeuristicLab.Encodings. PermutationEncoding;3 using HeuristicLab.Encodings.IntegerVectorEncoding; 4 4 5 5 namespace HeuristicLab.Analysis.FitnessLandscape { 6 public static class PermutationPathAnalysis {7 public static CurveAnalysisResult GetCharacteristics(List<List<Tuple< Permutation, double>>> trajectories) {8 return CurveAnalysis< Permutation>.GetCharacteristics(trajectories, Dist);6 public static class IntegerVectorPathAnalysis { 7 public static CurveAnalysisResult GetCharacteristics(List<List<Tuple<IntegerVector, double>>> trajectories) { 8 return CurveAnalysis<IntegerVector>.GetCharacteristics(trajectories, Dist); 9 9 } 10 10 11 private static double Dist( Permutation a, Permutationb) {11 private static double Dist(IntegerVector a, IntegerVector b) { 12 12 var dist = 0; 13 13 for (var i = 0; i < a.Length; i++)
Note: See TracChangeset
for help on using the changeset viewer.