Changeset 14690
- Timestamp:
- 02/20/17 20:41:33 (8 years ago)
- Location:
- branches/PerformanceComparison
- Files:
-
- 1 added
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs
r14563 r14690 25 25 using HeuristicLab.Algorithms.MemPR.Grouping; 26 26 using HeuristicLab.Algorithms.MemPR.Permutation; 27 using HeuristicLab.Analysis.FitnessLandscape; 27 28 using HeuristicLab.Core; 28 29 using HeuristicLab.Encodings.BinaryVectorEncoding; … … 76 77 } 77 78 79 public interface ILocalSearchPathContext<TSolution> : IExecutionContext where TSolution : class, IItem { 80 DirectedPath<TSolution> LocalSearchPaths { get; } 81 } 82 78 83 public interface IEvaluationServiceContext<TSolution> : IExecutionContext { 79 84 double Evaluate(TSolution solution, CancellationToken token); -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs
r14666 r14690 220 220 protected virtual TPopulationContext CreateContext() { 221 221 return new TPopulationContext(); 222 } 223 224 public void StartSync() { 225 using (var w = new AutoResetEvent(false)) { 226 EventHandler handler = (sender, e) => { 227 if (ExecutionState == ExecutionState.Paused 228 || ExecutionState == ExecutionState.Stopped) 229 w.Set(); 230 }; 231 ExecutionStateChanged += handler; 232 try { 233 Start(); 234 w.WaitOne(); 235 } finally { ExecutionStateChanged -= handler; } 236 } 222 237 } 223 238 -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs
r14678 r14690 40 40 [StorableClass] 41 41 public abstract class MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext> : ParameterizedNamedItem, 42 IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution> 43 where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem 42 IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution>, 43 ILocalSearchPathContext<TSolution> 44 where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem 44 45 where TSolution : class, IItem 45 46 where TPopulationContext : MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext> … … 169 170 get { return relinkedPaths.Value; } 170 171 set { relinkedPaths.Value = value; } 172 } 173 174 [Storable] 175 private IValueParameter<DirectedPath<TSolution>> localSearchPaths; 176 public DirectedPath<TSolution> LocalSearchPaths { 177 get { return localSearchPaths.Value; } 178 set { localSearchPaths.Value = value; } 171 179 } 172 180 … … 267 275 byAdaptivewalking = cloner.Clone(original.byAdaptivewalking); 268 276 relinkedPaths = cloner.Clone(original.relinkedPaths); 277 localSearchPaths = cloner.Clone(original.localSearchPaths); 269 278 random = cloner.Clone(original.random); 270 279 breedingStat = original.breedingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3, x.Item4)).ToList(); … … 296 305 Parameters.Add(byAdaptivewalking = new ValueParameter<IntValue>("ByAdaptivewalking", new IntValue(0))); 297 306 Parameters.Add(relinkedPaths = new ValueParameter<DirectedPath<TSolution>>("RelinkedPaths", new DirectedPath<TSolution>())); 307 Parameters.Add(localSearchPaths = new ValueParameter<DirectedPath<TSolution>>("LocalSearchPaths", new DirectedPath<TSolution>())); 298 308 Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister())); 299 309 -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimb.cs
r14552 r14690 20 20 #endregion 21 21 22 using System; 23 using System.Collections.Generic; 22 24 using System.Threading; 23 25 using HeuristicLab.Algorithms.MemPR.Interfaces; 24 using HeuristicLab.Algorithms.MemPR.Util;25 26 using HeuristicLab.Common; 26 27 using HeuristicLab.Core; 27 using HeuristicLab.Encodings.PermutationEncoding;28 28 using HeuristicLab.Optimization; 29 29 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; … … 34 34 public class ExhaustiveHillClimb<TContext> : NamedItem, ILocalSearch<TContext> 35 35 where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>, 36 IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> { 36 IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>, 37 ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> { 37 38 38 39 [StorableConstructor] … … 49 50 50 51 public void Optimize(TContext context) { 52 if (double.IsNaN(context.Solution.Fitness)) 53 context.Evaluate(context.Solution, CancellationToken.None); 51 54 var quality = context.Solution.Fitness; 52 55 try { 53 var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality, 56 var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>(); 57 path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality)); 58 59 var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality, 54 60 context.Maximization, context.Evaluate, CancellationToken.None); 55 context.IncrementEvaluatedSolutions(result.Item1); 56 context.Iterations = result.Item2; 61 62 Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null; 63 foreach (var step in result) { 64 path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2)); 65 last = step; 66 } 67 context.LocalSearchPaths.AddPath(path); 68 context.IncrementEvaluatedSolutions(last.Item3); 69 context.Iterations = path.Count - 2; 57 70 } finally { 58 71 context.Solution.Fitness = quality; -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs
r14556 r14690 20 20 #endregion 21 21 22 using System; 23 using System.Collections.Generic; 22 24 using System.Threading; 23 25 using HeuristicLab.Algorithms.MemPR.Interfaces; 24 using HeuristicLab.Algorithms.MemPR.Util;25 26 using HeuristicLab.Common; 26 27 using HeuristicLab.Core; 27 using HeuristicLab.Encodings.PermutationEncoding;28 28 using HeuristicLab.Optimization; 29 29 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; … … 34 34 public class ExhaustiveHillClimbSubspace<TContext> : NamedItem, ILocalSearch<TContext> 35 35 where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>, 36 IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> { 36 IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>, 37 ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> { 37 38 38 39 [StorableConstructor] … … 49 50 50 51 public void Optimize(TContext context) { 52 if (double.IsNaN(context.Solution.Fitness)) 53 context.Evaluate(context.Solution, CancellationToken.None); 51 54 var quality = context.Solution.Fitness; 52 55 try { 53 var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality, 56 var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>(); 57 path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality)); 58 59 var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality, 54 60 context.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace); 55 context.IncrementEvaluatedSolutions(result.Item1); 56 context.Iterations = result.Item2; 61 62 Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null; 63 foreach (var step in result) { 64 path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2)); 65 last = step; 66 } 67 context.LocalSearchPaths.AddPath(path); 68 context.IncrementEvaluatedSolutions(last.Item3); 69 context.Iterations = path.Count - 2; 57 70 } finally { 58 71 context.Solution.Fitness = quality; -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs
r14552 r14690 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Threading; 24 25 using HeuristicLab.Core; … … 33 34 #endif 34 35 35 public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,36 refdouble quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,36 public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 37 double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 37 38 CancellationToken token, bool[,] subspace = null) { 38 39 if (double.IsNaN(quality)) quality = eval(perm, token); 39 Tuple<int, int> changes;40 IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> localSearchPath; 40 41 switch (perm.PermutationType) { 41 42 case PermutationTypes.Absolute: 42 changes = ExhaustiveSwap2.HillClimb(random, perm, refquality, maximization, eval, token, subspace);43 localSearchPath = ExhaustiveSwap2.HillClimb(random, perm, quality, maximization, eval, token, subspace); 43 44 break; 44 45 case PermutationTypes.RelativeDirected: 45 changes = Exhaustive1Shift.HillClimb(random, perm, refquality, maximization, eval, token, subspace);46 localSearchPath = Exhaustive1Shift.HillClimb(random, perm, quality, maximization, eval, token, subspace); 46 47 break; 47 48 case PermutationTypes.RelativeUndirected: 48 changes = Exhaustive2Opt.HillClimb(random, perm, refquality, maximization, eval, token, subspace);49 localSearchPath = Exhaustive2Opt.HillClimb(random, perm, quality, maximization, eval, token, subspace); 49 50 break; 50 51 default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType)); 51 52 } 52 53 if (VALIDATE && !perm.Validate()) throw new ArgumentException("HillClimb produced invalid child"); 53 return changes;54 return localSearchPath; 54 55 } 55 56 } -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs
r14552 r14690 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Linq; 24 25 using System.Threading; … … 30 31 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch { 31 32 public static class Exhaustive1Shift { 32 public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 33 ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 33 public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> 34 HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 35 double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 34 36 CancellationToken token, bool[,] subspace = null) { 35 37 var evaluations = 0; … … 40 42 } 41 43 TranslocationMove lastSuccessMove = null; 42 var steps = 0;43 44 var neighborhood = ExhaustiveInsertionMoveGenerator.Generate(current).Shuffle(random).ToList(); 44 45 while (true) { … … 62 63 evaluations++; 63 64 if (FitnessComparer.IsBetter(maximization, q, quality)) { 64 steps++;65 yield return Tuple.Create(current, q, evaluations); 65 66 quality = q; 66 67 lastSuccessMove = shift; … … 74 75 if (lastSuccessMove == null) break; 75 76 } 76 return Tuple.Create(evaluations, steps);77 yield return Tuple.Create(current, quality, evaluations); 77 78 } 78 79 } -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs
r14556 r14690 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Linq; 24 25 using System.Threading; … … 30 31 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch { 31 32 public static class Exhaustive2Opt { 32 public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 33 ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 33 public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> 34 HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 35 double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 34 36 CancellationToken token, bool[,] subspace = null) { 35 37 var evaluations = 0; … … 40 42 } 41 43 InversionMove lastSuccessMove = null; 42 var steps = 0;43 44 var neighborhood = ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random).ToList(); 44 45 while (true) { … … 59 60 evaluations++; 60 61 if (FitnessComparer.IsBetter(maximization, q, quality)) { 61 steps++;62 yield return Tuple.Create(current, q, evaluations); 62 63 quality = q; 63 64 lastSuccessMove = opt; … … 71 72 if (lastSuccessMove == null) break; 72 73 } 73 return Tuple.Create(evaluations, steps);74 yield return Tuple.Create(current, quality, evaluations); 74 75 } 75 76 } -
branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs
r14552 r14690 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Linq; 24 25 using System.Threading; … … 30 31 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch { 31 32 public static class ExhaustiveSwap2 { 32 public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 33 ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 33 public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> 34 HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm, 35 double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, 34 36 CancellationToken token, bool[,] subspace = null) { 35 37 var evaluations = 0; … … 40 42 } 41 43 Swap2Move lastSuccessMove = null; 42 var steps = 0;43 44 var neighborhood = ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random).ToList(); 44 45 while (true) { … … 58 59 evaluations++; 59 60 if (FitnessComparer.IsBetter(maximization, q, quality)) { 60 steps++;61 yield return Tuple.Create(current, q, evaluations); 61 62 quality = q; 62 63 lastSuccessMove = swap; … … 73 74 if (lastSuccessMove == null) break; 74 75 } 75 return Tuple.Create(evaluations, steps);76 yield return Tuple.Create(current, quality, evaluations); 76 77 } 77 78 } -
branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/RandomWalkCalculator.cs
r13920 r14690 58 58 characteristics = cloner.Clone(original.characteristics); 59 59 } 60 public RandomWalkCalculator() { 60 public RandomWalkCalculator() : this(new RandomWalk()) { } 61 public RandomWalkCalculator(RandomWalk walker) { 61 62 Name = ItemName; 62 63 Description = ItemDescription; 63 walker = new RandomWalk();64 this.walker = walker; 64 65 characteristics = new CheckedItemList<StringValue>( 65 66 new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent", 66 "PartialInformationContent", "DensityBasinInformation", "InformationStability", 67 "PartialInformationContent", "DensityBasinInformation", "InformationStability", 67 68 "Diversity", "Regularity", "TotalEntropy", "PeakInformationContent", 68 69 "PeakDensityBasinInformation" }.Select(x => new StringValue(x))); … … 91 92 }; 92 93 walker.ExecutionStateChanged += evHandle; 93 walker.Start(); 94 waitHandle.WaitOne(); 95 walker.ExecutionStateChanged -= evHandle; 94 try { 95 walker.Start(); 96 waitHandle.WaitOne(); 97 } finally { walker.ExecutionStateChanged -= evHandle; } 96 98 } 97 99 foreach (var p in characteristics.CheckedItems) { 98 yield return new Result("RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value, walker.Results[p.Value.Value].Value); 100 var resultName = "RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value; 101 IResult result; 102 if (walker.Results.TryGetValue(p.Value.Value, out result)) { 103 yield return new Result(resultName, result.Value); 104 } else yield return new Result(resultName, new DoubleValue(0)); 99 105 } 100 106 walker.Prepare(true); -
branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs
r14678 r14690 32 32 using System.Collections.Generic; 33 33 using System.Linq; 34 using System.Threading; 34 35 35 36 namespace HeuristicLab.Analysis.FitnessLandscape { … … 50 51 } 51 52 53 public IFixedValueParameter<BoolValue> LocalOptimaParameter { 54 get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; } 55 } 56 52 57 public int Paths { 53 58 get { return PathsParameter.Value.Value; } … … 63 68 get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; } 64 69 set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; } 70 } 71 72 public bool LocalOptima { 73 get { return LocalOptimaParameter.Value.Value; } 74 set { LocalOptimaParameter.Value.Value = value; } 65 75 } 66 76 … … 74 84 Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true))); 75 85 Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator.")); 86 Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false))); 76 87 } 77 88 … … 90 101 91 102 var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random); 103 if (LocalOptima) { 104 var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances)); 105 QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None); 106 } 92 107 var permutations = new List<Permutation> { perm }; 93 108 while (permutations.Count < pathCount + 1) { 94 109 perm = (Permutation)permutations.Last().Clone(); 95 110 BiasedShuffle(perm, random); 96 permutations.Add(perm); 111 if (LocalOptima) { 112 var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances)); 113 QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None); 114 } 115 if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75) 116 permutations.Add(perm); 97 117 } 98 118 … … 151 171 152 172 for (var p = 0; p < f2.Count; p++) { 173 if (f2[p].Count <= 2) continue; 153 174 var bump = 0; 154 175 var flat = 0; … … 266 287 } 267 288 289 // Center-of-Mass 268 290 private static double ComBelowZero(IEnumerable<Tuple<Permutation, double>> path) { 269 291 var area = 0.0; -
branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs
r14678 r14690 1 using System.Linq; 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 2 4 using HeuristicLab.Analysis.FitnessLandscape; 5 using HeuristicLab.Common; 3 6 using HeuristicLab.Data; 7 using HeuristicLab.Encodings.PermutationEncoding; 4 8 using HeuristicLab.Problems.QuadraticAssignment; 5 9 … … 9 13 public string Cls { get; private set; } 10 14 public int Dimension { get; set; } 11 public double Sharpness { get; set; } 12 public double SharpnessSdev { get; set; } 13 public double Bumpiness { get; set; } 14 public double BumpinessSdev { get; set; } 15 public double Flatness { get; set; } 16 public double FlatnessSdev { get; set; } 17 public double Steadiness { get; set; } 18 public double SteadinessSdev { get; set; } 15 16 public string[] FeatureNames { get; set; } 17 public double[] FeatureValues { get; set; } 19 18 20 19 private InstanceDescriptor() { } 21 20 22 public static InstanceDescriptor FromPathRelinkingAnalysis(QuadraticAssignmentProblem qap, int paths, int? seed) { 23 var walk = new QAPDirectedWalk { 24 Problem = qap, 25 BestImprovement = true, 26 Paths = paths, 27 Seed = seed 21 public InstanceDescriptor(string name, string cls, int dimension, string[] names, double[] values) { 22 Name = name; 23 Cls = cls; 24 Dimension = dimension; 25 FeatureNames = names; 26 FeatureValues = values; 27 } 28 29 public InstanceDescriptor(InstanceDescriptor other) { 30 Name = other.Name; 31 Cls = other.Cls; 32 Dimension = other.Dimension; 33 FeatureNames = (string[])other.FeatureNames.Clone(); 34 FeatureValues = (double[]) other.FeatureValues.Clone(); 35 } 36 37 public static InstanceDescriptor FromProblemOnly(QuadraticAssignmentProblem qap) { 38 return new InstanceDescriptor() { 39 Name = qap.Name, 40 Cls = GetClass(qap.Name), 41 Dimension = qap.Weights.Rows, 42 FeatureNames = new string[0], 43 FeatureValues = new double[0] 28 44 }; 29 var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value); 45 } 46 47 public static InstanceDescriptor FromPaths(QuadraticAssignmentProblem qap, List<List<Tuple<Permutation, double>>> trajectories) { 48 var features = QAPDirectedWalk.Calculate(trajectories).ToDictionary(x => x.Name, x => x.Value); 30 49 31 50 return new InstanceDescriptor() { … … 33 52 Cls = GetClass(qap.Name), 34 53 Dimension = qap.Weights.Rows, 35 Sharpness = ((DoubleValue)features["Swap2.Sharpness"]).Value, 36 Bumpiness = ((DoubleValue)features["Swap2.Bumpiness"]).Value, 37 Flatness = ((DoubleValue)features["Swap2.Flatness"]).Value, 38 Steadiness = ((DoubleValue)features["Swap2.Steadiness"]).Value, 54 FeatureNames = features.Keys.ToArray(), 55 FeatureValues = features.Values.Select(x => ((DoubleValue)x).Value).ToArray() 39 56 }; 40 57 } 41 58 42 p rivatestatic string GetClass(string name) {59 public static string GetClass(string name) { 43 60 var cls = name.Substring(0, 3); 44 61 var subCls = name.Last(); … … 58 75 59 76 public double CalculateSimilarity(InstanceDescriptor other) { 60 var sa = (Sharpness - other.Sharpness); 61 var bu = (Bumpiness - other.Bumpiness); 62 var fl = (Flatness - other.Flatness); 63 var se = (Steadiness - other.Steadiness); 64 return sa * sa + bu * bu + fl * fl + se * se; 77 return FeatureValues.Select((v, i) => (v - other.FeatureValues[i]) * (v - other.FeatureValues[i])).Sum(); 65 78 } 66 79 … … 69 82 } 70 83 } 84 85 public class InstancesStandardizer { 86 private double[] featureMeans; 87 private double[] featureStdevs; 88 89 private InstancesStandardizer() { } 90 91 public static InstancesStandardizer Create(IList<InstanceDescriptor> instances) { 92 var standardizer = new InstancesStandardizer(); 93 var featureLength = instances.First().FeatureValues.Length; 94 standardizer.featureMeans = 95 Enumerable.Range(0, featureLength) 96 .Select(x => instances.Select(y => y.FeatureValues[x]).Average()).ToArray(); 97 standardizer.featureStdevs = 98 Enumerable.Range(0, featureLength) 99 .Select(x => instances.Select(y => y.FeatureValues[x]).StandardDeviation()).ToArray(); 100 101 return standardizer; 102 } 103 104 public void Apply(IList<InstanceDescriptor> instances) { 105 for (var i = 0; i < instances.Count; i++) { 106 var inst = instances[i]; 107 for (var x = 0; x < featureMeans.Length; x++) 108 inst.FeatureValues[x] = (inst.FeatureValues[x] - featureMeans[x]) / featureStdevs[x]; 109 } 110 } 111 } 71 112 } -
branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj
r14678 r14690 23 23 <ErrorReport>prompt</ErrorReport> 24 24 <WarningLevel>4</WarningLevel> 25 <Prefer32Bit>false</Prefer32Bit> 25 26 </PropertyGroup> 26 27 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> … … 32 33 <ErrorReport>prompt</ErrorReport> 33 34 <WarningLevel>4</WarningLevel> 35 <Prefer32Bit>false</Prefer32Bit> 34 36 </PropertyGroup> 35 37 <ItemGroup> … … 67 69 <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath> 68 70 </Reference> 71 <Reference Include="HeuristicLab.Selection-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL"> 72 <SpecificVersion>False</SpecificVersion> 73 <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Selection-3.3.dll</HintPath> 74 </Reference> 75 <Reference Include="HeuristicLab.SequentialEngine-3.3"> 76 <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath> 77 </Reference> 69 78 <Reference Include="System" /> 70 79 <Reference Include="System.Core" /> … … 78 87 <ItemGroup> 79 88 <Compile Include="InstanceDescriptor.cs" /> 89 <Compile Include="InstanceExplorer.cs" /> 80 90 <Compile Include="Program.cs" /> 81 91 <Compile Include="Properties\AssemblyInfo.cs" /> … … 85 95 </ItemGroup> 86 96 <ItemGroup> 97 <ProjectReference Include="..\HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj"> 98 <Project>{9d274421-6332-4fbc-aae4-467ace27c368}</Project> 99 <Name>HeuristicLab.Algorithms.MemPR-3.3</Name> 100 </ProjectReference> 87 101 <ProjectReference Include="..\HeuristicLab.Analysis.FitnessLandscape\3.3\HeuristicLab.Analysis.FitnessLandscape-3.3.csproj"> 88 102 <Project>{5fbdcd4a-3c2a-4ec6-83ce-34b29f43621a}</Project> -
branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs
r14678 r14690 1 1 using System; 2 2 using System.Collections.Generic; 3 using System.Globalization; 3 4 using System.Linq; 4 5 using System.Threading.Tasks; 6 using HeuristicLab.Algorithms.MemPR.Permutation; 5 7 using HeuristicLab.PluginInfrastructure; 6 8 using HeuristicLab.Problems.Instances; … … 10 12 namespace ProblemInstanceIdentifier { 11 13 class Program { 14 private static HashSet<string> selectedInstances = new HashSet<string>() { 15 "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b", 16 "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50", 17 "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci" 18 }; 12 19 static void Main(string[] args) { 13 20 var sync = new object(); … … 18 25 if (provider is TaillardQAPInstanceProvider) continue; 19 26 Parallel.ForEach(provider.GetDataDescriptors(), desc => { 20 if (desc.Name == "esc16f") return; 27 if (!selectedInstances.Contains(desc.Name)) return; 28 //if (desc.Name == "esc16f") return; 21 29 var qapData = provider.LoadData(desc); 22 if (qapData.Dimension < 15 || qapData.Dimension > 150) return;30 //if (qapData.Dimension < 15 || qapData.Dimension > 150) return; 23 31 var qap = new QuadraticAssignmentProblem(); 24 32 qap.Load(qapData); … … 29 37 } 30 38 31 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", "Repetition", "KB-Paths", "Exp-Paths", "Cls-Hits", "Exact-Hits", "No-Hits", "Cls-Rank", "Exact-Rank"); 32 var paths = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50 }; 33 for (var r = 0; r < 20; r++) { 34 Parallel.ForEach(paths, kbPaths => { 35 foreach (var expPaths in paths) { 36 if (expPaths > kbPaths) continue; 39 /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls); 40 foreach (var cls in classes.OrderBy(x => x.Key)) { 41 Console.WriteLine("{0};{1}", cls.Key, cls.Count()); 42 }*/ 43 44 //var kb = GenerateKnowledgeBase(instances, 200, localOptima: false); 45 46 47 //var paths = new[] { 1, 2, 3, 5, 10, 20, 30, 50, 100, 200 }; 48 //var kbExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray(); 49 //var expExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray(); 50 //ExploreSelfIdentification(instances, kbExplorers, expExplorers); 51 52 var iterations = new[] { 100, 1000, 10000, 100000 }; 53 var kbExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(); 54 var expExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(); 55 ExploreSelfIdentification(instances, kbExplorers, expExplorers); 56 57 //ExploreMemPrIdentification(instances); 58 } 59 60 private static List<InstanceDescriptor> GenerateKnowledgeBase(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer) { 61 var headerPrinted = false; 62 var sync = new object(); 63 var kb = new List<InstanceDescriptor>(); 64 Parallel.ForEach(instances.OrderBy(x => x.Weights.Rows), qap => { 65 var instance = explorer.Explore(qap); 66 lock (sync) { 67 if (!headerPrinted) { 68 headerPrinted = true; 69 Console.WriteLine(string.Join(";", 70 new [] { "Name", "Cls", "Dimension" } 71 .Concat(instance.FeatureNames))); 72 } 73 PrintInstanceLine(instance); 74 kb.Add(instance); 75 } 76 }); 77 var standardizer = InstancesStandardizer.Create(kb); 78 var normalizedKb = kb.Select(x => new InstanceDescriptor(x)).ToList(); 79 standardizer.Apply(normalizedKb); 80 Console.WriteLine(); 81 foreach (var instance in kb) { 82 PrintInstanceLine(instance); 83 } 84 //return normalizedKb; 85 return kb; 86 } 87 88 private static void PrintInstanceLine(InstanceDescriptor instance) { 89 Console.WriteLine(string.Join(";", 90 new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)} 91 .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture))))); 92 } 93 94 private static void ExploreSelfIdentification(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] kbExplorer, InstanceExplorer[] expExporer) { 95 var sync = new object(); 96 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Effort", "Exp-Effort", 97 "Exact-Hits", "No-Hits", "Exact-Rank"); 98 var kbSeeds = Enumerable.Range(0, 20).ToList(); 99 var expSeeds = Enumerable.Range(20, 20).ToList(); 100 for (var r = 0; r < 10; r++) { 101 var rlokal = r; 102 Parallel.ForEach(kbExplorer, kbPaths => { 103 //foreach (var kbPaths in kbExplorer) { 104 foreach (var expPaths in expExporer) { 105 //if (expPaths > kbPaths) continue; 37 106 var kb = new List<InstanceDescriptor>(); 38 107 var exp = new List<InstanceDescriptor>(); 39 108 foreach (var qap in instances) { 40 kb.Add( InstanceDescriptor.FromPathRelinkingAnalysis(qap, kbPaths, null));41 exp.Add( InstanceDescriptor.FromPathRelinkingAnalysis(qap, expPaths, null));109 kb.Add(kbPaths.Explore(qap, kbSeeds[rlokal])); 110 exp.Add(expPaths.Explore(qap, expSeeds[rlokal])); 42 111 } 112 var standardizer = InstancesStandardizer.Create(kb); 113 standardizer.Apply(kb); 114 standardizer.Apply(exp); 115 int exactCount = 0, clsCount = 0, missedCount = 0; 116 int exactRank = 0, clsRank = 0; 117 foreach (var e in exp) { 118 var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList(); 119 var bestMatch = ordered.First(); 120 if (bestMatch.Cls == e.Cls) { 121 clsCount++; 122 if (bestMatch.Name == e.Name) exactCount++; 123 } 124 else missedCount++; 125 clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1; 126 exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1; 127 } 128 lock (sync) { 129 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths.Effort, expPaths.Effort, exactCount, 130 missedCount, exactRank / (double) exp.Count); 131 } 132 } 133 }); 134 //} 135 } 136 } 137 138 private static void ExploreMemPrIdentification(List<QuadraticAssignmentProblem> instances) { 139 var sync = new object(); 140 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Runtime", "Exp-Runtime", 141 "Exact-Hits", "No-Hits", "Average-Rank"); 142 var paths = new[] { 10 }; 143 var repetitions = 10; 144 var kbSeeds = Enumerable.Range(0, repetitions).ToList(); 145 var expSeeds = Enumerable.Range(repetitions, repetitions).ToList(); 146 for (var r = 0; r < repetitions; r++) { 147 var rlokal = r; 148 Parallel.ForEach(paths, kbPaths => { 149 var memPr = new PermutationMemPR(); 150 foreach (var expPaths in paths) { 151 //if (expPaths > kbPaths) continue; 152 var kb = new List<InstanceDescriptor>(); 153 var exp = new List<InstanceDescriptor>(); 154 foreach (var qap in instances.Select(x => (QuadraticAssignmentProblem)x.Clone())) { 155 memPr.Problem = qap; 156 memPr.Prepare(true); 157 memPr.Seed = kbSeeds[rlokal]; 158 memPr.MaximumExecutionTime = TimeSpan.FromSeconds(kbPaths); 159 memPr.StartSync(); 160 if (memPr.Context.RelinkedPaths.IsEmpty) continue; 161 kb.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList())); 162 memPr.Prepare(true); 163 memPr.Seed = expSeeds[rlokal]; 164 memPr.MaximumExecutionTime = TimeSpan.FromSeconds(expPaths); 165 memPr.StartSync(); 166 if (memPr.Context.RelinkedPaths.IsEmpty) continue; 167 exp.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList())); 168 } 169 var standardizer = InstancesStandardizer.Create(kb); 170 standardizer.Apply(kb); 171 standardizer.Apply(exp); 43 172 int exactCount = 0, clsCount = 0, missedCount = 0; 44 173 int exactRank = 0, clsRank = 0; … … 54 183 } 55 184 lock (sync) { 56 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", r, kbPaths, expPaths, clsCount, exactCount, missedCount, clsRank / (double)exp.Count, exactRank / (double)exp.Count); 185 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths, expPaths, exactCount, 186 missedCount, exactRank / (double)exp.Count); 57 187 } 58 188 }
Note: See TracChangeset
for help on using the changeset viewer.