Changeset 15562 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms
- Timestamp:
- 12/29/17 23:56:43 (7 years ago)
- Location:
- branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3
- Files:
-
- 18 added
- 1 edited
- 2 copied
- 4 moved
Legend:
- Unmodified
- Added
- Removed
-
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/ESContext.cs
r15558 r15562 20 20 #endregion 21 21 22 using System;23 22 using System.Collections.Generic; 24 using System.Linq;25 using System.Runtime.CompilerServices;26 using System.Threading;27 23 using HeuristicLab.Common; 28 24 using HeuristicLab.Core; 29 using HeuristicLab.Data;30 using HeuristicLab.Optimization;31 25 using HeuristicLab.Parameters; 32 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 33 using HeuristicLab.Random;34 27 35 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms. GRASP{36 [Item(" GRASP+PR (GQAP) Context", "Context for GRASP+PR(GQAP).")]28 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary { 29 [Item("Evolution Strategy (GQAP) Context", "Context for Evolution Strategies (GQAP).")] 37 30 [StorableClass] 38 public sealed class GRASPContext : ParameterizedNamedItem, IExecutionContext{31 public sealed class ESContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> { 39 32 40 private IExecutionContext parent;41 public IExecutionContext Parent {42 get { return parent; }43 set { parent = value; }44 }45 46 [Storable]47 private IScope scope;48 public IScope Scope {49 get { return scope; }50 private set { scope = value; }51 }52 53 IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {54 get { return Parameters; }55 }56 57 33 [Storable] 58 34 private IValueParameter<GQAP> problem; … … 61 37 set { problem.Value = value; } 62 38 } 63 public bool Maximization {64 get { return Problem.Maximization; }65 }66 39 67 40 [Storable] 68 private IValueParameter<BoolValue> initialized; 69 public bool Initialized { 70 get { return initialized.Value.Value; } 71 set { initialized.Value.Value = value; } 72 } 73 74 [Storable] 75 private IValueParameter<IntValue> iterations; 76 public int Iterations { 77 get { return iterations.Value.Value; } 78 set { iterations.Value.Value = value; } 79 } 80 81 [Storable] 82 private IValueParameter<IntValue> evaluatedSolutions; 83 public int EvaluatedSolutions { 84 get { return evaluatedSolutions.Value.Value; } 85 set { evaluatedSolutions.Value.Value = value; } 86 } 87 88 [Storable] 89 private IValueParameter<DoubleValue> bestQuality; 90 public double BestQuality { 91 get { return bestQuality.Value.Value; } 92 set { bestQuality.Value.Value = value; } 93 } 94 95 [Storable] 96 private IValueParameter<GQAPSolution> bestSolution; 97 public GQAPSolution BestSolution { 41 private IValueParameter<ESGQAPSolution> bestSolution; 42 public ESGQAPSolution BestSolution { 98 43 get { return bestSolution.Value; } 99 44 set { bestSolution.Value = value; } 100 45 } 101 46 102 [Storable] 103 private IValueParameter<IntValue> localSearchEvaluations; 104 public int LocalSearchEvaluations { 105 get { return localSearchEvaluations.Value.Value; } 106 set { localSearchEvaluations.Value.Value = value; } 107 } 108 109 [Storable] 110 private IValueParameter<IRandom> random; 111 public IRandom Random { 112 get { return random.Value; } 113 set { random.Value = value; } 114 } 115 116 public IEnumerable<ISingleObjectiveSolutionScope<GQAPSolution>> Population { 117 get { return scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>(); } 118 } 119 public void AddToPopulation(ISingleObjectiveSolutionScope<GQAPSolution> solScope) { 120 scope.SubScopes.Add(solScope); 121 } 122 public void ReplaceAtPopulation(int index, ISingleObjectiveSolutionScope<GQAPSolution> solScope) { 123 scope.SubScopes[index] = solScope; 124 } 125 public ISingleObjectiveSolutionScope<GQAPSolution> AtPopulation(int index) { 126 return scope.SubScopes[index] as ISingleObjectiveSolutionScope<GQAPSolution>; 127 } 128 public void SortPopulation() { 129 scope.SubScopes.Replace(scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Maximization ? -x.Fitness : x.Fitness).ToList()); 130 } 131 public int PopulationCount { 132 get { return scope.SubScopes.Count; } 47 public void ReplacePopulation(IEnumerable<ISingleObjectiveSolutionScope<ESGQAPSolution>> replacement) { 48 Scope.SubScopes.Replace(replacement); 133 49 } 134 50 135 51 [StorableConstructor] 136 private GRASPContext(bool deserializing) : base(deserializing) { }137 private GRASPContext(GRASPContext original, Cloner cloner)52 private ESContext(bool deserializing) : base(deserializing) { } 53 private ESContext(ESContext original, Cloner cloner) 138 54 : base(original, cloner) { 139 scope = cloner.Clone(original.scope);140 55 problem = cloner.Clone(original.problem); 141 initialized = cloner.Clone(original.initialized);142 iterations = cloner.Clone(original.iterations);143 evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);144 bestQuality = cloner.Clone(original.bestQuality);145 56 bestSolution = cloner.Clone(original.bestSolution); 146 localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);147 random = cloner.Clone(original.random);148 57 } 149 public GRASPContext() : this("GRASP+PR (GQAP) Context") { } 150 public GRASPContext(string name) : base(name) { 151 scope = new Scope("Global"); 152 58 public ESContext() : this("Evolution Strategy (GQAP) Context") { } 59 public ESContext(string name) : base(name) { 153 60 Parameters.Add(problem = new ValueParameter<GQAP>("Problem")); 154 Parameters.Add(initialized = new ValueParameter<BoolValue>("Initialized", new BoolValue(false))); 155 Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0))); 156 Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 157 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 158 Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution")); 159 Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0))); 160 Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister())); 61 Parameters.Add(bestSolution = new ValueParameter<ESGQAPSolution>("BestFoundSolution")); 161 62 } 162 63 163 64 public override IDeepCloneable Clone(Cloner cloner) { 164 return new GRASPContext(this, cloner);65 return new ESContext(this, cloner); 165 66 } 166 67 167 public ISingleObjectiveSolutionScope< GQAPSolution> ToScope(GQAPSolution code, double fitness = double.NaN) {68 public ISingleObjectiveSolutionScope<ESGQAPSolution> ToScope(ESGQAPSolution code, double fitness = double.NaN) { 168 69 var name = Problem.Encoding.Name; 169 var scope = new SingleObjectiveSolutionScope< GQAPSolution>(code,70 var scope = new SingleObjectiveSolutionScope<ESGQAPSolution>(code, 170 71 name + "Solution", fitness, Problem.Evaluator.QualityParameter.ActualName) { 171 72 Parent = Scope … … 175 76 return scope; 176 77 } 177 178 public void IncrementEvaluatedSolutions(int byEvaluations) {179 if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");180 EvaluatedSolutions += byEvaluations;181 }182 183 private static void ExecuteAlgorithm(IAlgorithm algorithm) {184 using (var evt = new AutoResetEvent(false)) {185 EventHandler exeStateChanged = (o, args) => {186 if (algorithm.ExecutionState != ExecutionState.Started)187 evt.Set();188 };189 algorithm.ExecutionStateChanged += exeStateChanged;190 if (algorithm.ExecutionState != ExecutionState.Prepared) {191 algorithm.Prepare(true);192 evt.WaitOne();193 }194 algorithm.Start();195 evt.WaitOne();196 algorithm.ExecutionStateChanged -= exeStateChanged;197 }198 }199 [MethodImpl(MethodImplOptions.AggressiveInlining)]200 public bool IsBetter(ISingleObjectiveSolutionScope<GQAPSolution> a, ISingleObjectiveSolutionScope<GQAPSolution> b) {201 return IsBetter(a.Fitness, b.Fitness);202 }203 [MethodImpl(MethodImplOptions.AggressiveInlining)]204 public bool IsBetter(double a, double b) {205 return double.IsNaN(b) && !double.IsNaN(a)206 || Maximization && a > b207 || !Maximization && a < b;208 }209 210 #region IExecutionContext members211 public IAtomicOperation CreateOperation(IOperator op) {212 return new Core.ExecutionContext(this, op, Scope);213 }214 215 public IAtomicOperation CreateOperation(IOperator op, IScope s) {216 return new Core.ExecutionContext(this, op, s);217 }218 219 public IAtomicOperation CreateChildOperation(IOperator op) {220 return new Core.ExecutionContext(this, op, Scope);221 }222 223 public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {224 return new Core.ExecutionContext(this, op, s);225 }226 #endregion227 228 #region Engine Helper229 public void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {230 var stack = new Stack<IOperation>();231 stack.Push(CreateChildOperation(op, scope));232 233 while (stack.Count > 0) {234 cancellationToken.ThrowIfCancellationRequested();235 236 var next = stack.Pop();237 if (next is OperationCollection) {238 var coll = (OperationCollection)next;239 for (int i = coll.Count - 1; i >= 0; i--)240 if (coll[i] != null) stack.Push(coll[i]);241 } else if (next is IAtomicOperation) {242 var operation = (IAtomicOperation)next;243 try {244 next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);245 } catch (Exception ex) {246 stack.Push(operation);247 if (ex is OperationCanceledException) throw ex;248 else throw new OperatorExecutionException(operation.Operator, ex);249 }250 if (next != null) stack.Push(next);251 }252 }253 }254 #endregion255 78 } 256 79 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs
r15558 r15562 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Linq; 24 25 using System.Threading; 25 using HeuristicLab.Analysis;26 26 using HeuristicLab.Common; 27 27 using HeuristicLab.Core; … … 33 33 using HeuristicLab.Random; 34 34 35 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP { 36 37 /// <summary> 38 /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0 39 /// </summary> 40 [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")] 35 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary { 36 public enum ESSelection { Plus = 0, Comma = 1 } 37 38 [Item("Evolution Strategy (GQAP)", "The algorithm implements a simple evolution strategy (ES).")] 41 39 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] 42 40 [StorableClass] 43 public class GRASP : BasicAlgorithm{41 public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext> { 44 42 45 43 public override bool SupportsPause { … … 57 55 58 56 [Storable] 59 private ValueParameter<IAnalyzer> analyzerParameter; 60 public IValueParameter<IAnalyzer> AnalyzerParameter { 61 get { return analyzerParameter; } 62 } 63 57 private FixedValueParameter<IntValue> lambdaParameter; 58 private IFixedValueParameter<IntValue> LambdaParameter { 59 get { return lambdaParameter; } 60 } 64 61 [Storable] 65 private FixedValueParameter< BoolValue> setSeedRandomlyParameter;66 p rivate IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {67 get { return setSeedRandomlyParameter; }62 private FixedValueParameter<IntValue> muParameter; 63 public IFixedValueParameter<IntValue> MuParameter { 64 get { return muParameter; } 68 65 } 69 66 [Storable] 70 private FixedValueParameter<IntValue> seedParameter; 71 private IFixedValueParameter<IntValue> SeedParameter { 72 get { return seedParameter; } 73 } 74 [Storable] 75 private FixedValueParameter<IntValue> eliteSetSizeParameter; 76 private IFixedValueParameter<IntValue> EliteSetSizeParameter { 77 get { return eliteSetSizeParameter; } 78 } 79 [Storable] 80 private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter; 81 public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter { 82 get { return minimiumEliteSetSizeParameter; } 83 } 84 [Storable] 85 private FixedValueParameter<IntValue> maximumIterationsParameter; 86 public IFixedValueParameter<IntValue> MaximumIterationsParameter { 87 get { return maximumIterationsParameter; } 88 } 89 [Storable] 90 private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter; 91 public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter { 92 get { return maximumIterationsParameter; } 93 } 94 [Storable] 95 private FixedValueParameter<PercentValue> candidateSizeFactorParameter; 96 public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter { 97 get { return candidateSizeFactorParameter; } 98 } 99 [Storable] 100 private FixedValueParameter<IntValue> maximumCandidateListSizeParameter; 101 public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter { 102 get { return maximumCandidateListSizeParameter; } 103 } 104 [Storable] 105 private FixedValueParameter<PercentValue> oneMoveProbabilityParameter; 106 public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter { 107 get { return oneMoveProbabilityParameter; } 108 } 109 [Storable] 110 private FixedValueParameter<IntValue> minimumDifferenceParameter; 111 public IFixedValueParameter<IntValue> MinimumDifferenceParameter { 112 get { return minimumDifferenceParameter; } 113 } 114 115 public bool SetSeedRandomly { 116 get { return setSeedRandomlyParameter.Value.Value; } 117 set { setSeedRandomlyParameter.Value.Value = value; } 118 } 119 public int Seed { 120 get { return seedParameter.Value.Value; } 121 set { seedParameter.Value.Value = value; } 122 } 123 public int EliteSetSize { 124 get { return eliteSetSizeParameter.Value.Value; } 125 set { eliteSetSizeParameter.Value.Value = value; } 126 } 127 public int MinimumEliteSetSize { 128 get { return minimiumEliteSetSizeParameter.Value.Value; } 129 set { minimiumEliteSetSizeParameter.Value.Value = value; } 130 } 131 public int MaximumIterations { 132 get { return maximumIterationsParameter.Value.Value; } 133 set { maximumIterationsParameter.Value.Value = value; } 134 } 135 public int MaximumLocalSearchIterations { 136 get { return maximumLocalSearchIterationsParameter.Value.Value; } 137 set { maximumLocalSearchIterationsParameter.Value.Value = value; } 138 } 139 public double CandidateSizeFactor { 140 get { return candidateSizeFactorParameter.Value.Value; } 141 set { candidateSizeFactorParameter.Value.Value = value; } 142 } 143 public int MaximumCandidateListSize { 144 get { return maximumCandidateListSizeParameter.Value.Value; } 145 set { maximumCandidateListSizeParameter.Value.Value = value; } 146 } 147 public double OneMoveProbability { 148 get { return oneMoveProbabilityParameter.Value.Value; } 149 set { oneMoveProbabilityParameter.Value.Value = value; } 150 } 151 public int MinimumDifference { 152 get { return minimumDifferenceParameter.Value.Value; } 153 set { minimumDifferenceParameter.Value.Value = value; } 67 private FixedValueParameter<EnumValue<ESSelection>> selectionParameter; 68 public IFixedValueParameter<EnumValue<ESSelection>> SelectionParameter { 69 get { return selectionParameter; } 70 } 71 72 public int Lambda { 73 get { return lambdaParameter.Value.Value; } 74 set { lambdaParameter.Value.Value = value; } 75 } 76 public int Mu { 77 get { return muParameter.Value.Value; } 78 set { muParameter.Value.Value = value; } 79 } 80 public ESSelection Selection { 81 get { return selectionParameter.Value.Value; } 82 set { selectionParameter.Value.Value = value; } 154 83 } 155 84 156 85 [StorableConstructor] 157 pr otected GRASP(bool deserializing) : base(deserializing) { }158 pr otected GRASP(GRASPoriginal, Cloner cloner)86 private EvolutionStrategy(bool deserializing) : base(deserializing) { } 87 private EvolutionStrategy(EvolutionStrategy original, Cloner cloner) 159 88 : base(original, cloner) { 160 setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter); 161 seedParameter = cloner.Clone(original.seedParameter); 162 analyzerParameter = cloner.Clone(original.analyzerParameter); 163 eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter); 164 minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter); 165 maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter); 166 maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter); 167 candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter); 168 maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter); 169 oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter); 170 minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter); 171 context = cloner.Clone(original.context); 172 } 173 public GRASP() { 174 Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true))); 175 Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0))); 176 Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer())); 177 Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10))); 178 Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2))); 179 Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000))); 180 Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100))); 181 Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5))); 182 Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10))); 183 Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5))); 184 Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4))); 89 lambdaParameter = cloner.Clone(original.lambdaParameter); 90 muParameter = cloner.Clone(original.muParameter); 91 selectionParameter = cloner.Clone(original.selectionParameter); 92 } 93 public EvolutionStrategy() { 94 Parameters.Add(lambdaParameter = new FixedValueParameter<IntValue>("Lambda", "(λ) The amount of offspring that are created each generation.", new IntValue(10))); 95 Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1))); 96 Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus))); 97 185 98 Problem = new GQAP(); 186 99 } 187 100 188 101 public override IDeepCloneable Clone(Cloner cloner) { 189 return new GRASP(this, cloner); 190 } 191 192 public override void Prepare() { 193 base.Prepare(); 194 Results.Clear(); 195 context = null; 196 } 197 198 [Storable] 199 private GRASPContext context; 102 return new EvolutionStrategy(this, cloner); 103 } 200 104 201 105 protected override void Initialize(CancellationToken cancellationToken) { 202 106 base.Initialize(cancellationToken); 203 context = new GRASPContext(); 204 context.Problem = Problem; 205 context.Scope.Variables.Add(new Variable("Results", Results)); 206 207 IExecutionContext ctxt = null; 208 foreach (var item in Problem.ExecutionContextItems) 209 ctxt = new Core.ExecutionContext(ctxt, item, context.Scope); 210 ctxt = new Core.ExecutionContext(ctxt, this, context.Scope); 211 context.Parent = ctxt; 212 213 if (SetSeedRandomly) { 214 var rnd = new System.Random(); 215 Seed = rnd.Next(); 107 108 Context.Problem = Problem; 109 Context.BestQuality = double.NaN; 110 Context.BestSolution = null; 111 112 for (var m = 0; m < Mu; m++) { 113 var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length); 114 var eval = Problem.ProblemInstance.Evaluate(assign); 115 Context.EvaluatedSolutions++; 116 117 var ind = new ESGQAPSolution(assign, eval, 1.0 / assign.Length); 118 var fit = Problem.ProblemInstance.ToSingleObjective(eval); 119 Context.AddToPopulation(Context.ToScope(ind, fit)); 120 if (double.IsNaN(Context.BestQuality) || fit < Context.BestQuality) { 121 Context.BestQuality = fit; 122 Context.BestSolution = (ESGQAPSolution)ind.Clone(); 123 } 216 124 } 217 context.Random = new MersenneTwister((uint)Seed); 218 context.Iterations = 0; 219 context.EvaluatedSolutions = 0; 220 context.BestQuality = double.NaN; 221 context.BestSolution = null; 222 223 context.Initialized = true; 224 225 Results.Add(new Result("Iterations", new IntValue(context.Iterations))); 226 Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions))); 227 Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality))); 228 Results.Add(new Result("BestSolution", typeof(GQAPSolution))); 229 230 context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken); 125 126 Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); 127 Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); 128 Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); 129 Results.Add(new Result("BestSolution", Context.BestSolution)); 130 131 Context.RunOperator(Analyzer, Context.Scope, cancellationToken); 231 132 } 232 133 233 134 protected override void Run(CancellationToken cancellationToken) { 234 var eq = new IntegerVectorEqualityComparer(); 235 while (!StoppingCriterion()) { // line 2 in Algorithm 1 236 // next: line 3 in Algorithm 1 237 var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken); 238 if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1 239 GQAPSolution pi_prime; 240 if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1 241 pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1 242 else { 243 // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1 244 pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec); 245 context.EvaluatedSolutions++; 246 } 247 248 ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1 249 var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1 250 pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1 251 ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1 252 var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 253 // Book-keeping 254 if (context.BestQuality > fitness) { 255 context.BestQuality = fitness; 256 context.BestSolution = (GQAPSolution)pi_prime.Clone(); 257 } 258 259 if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1 260 var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 261 double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray(); 262 if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1 263 var replacement = context.Population.Select((v, i) => new { V = v, Index = i }) 264 .Where(x => x.V.Fitness >= fit).ToArray(); 265 if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1 266 // next two lines: line 14 in Algorithm 1 267 replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray(); 268 context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit)); 269 } 270 } 271 } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1 272 context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1 273 } 274 } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */ 275 && IsSufficientlyDifferent(pi_prime_vec)) /* cond. 2 of line 21 in Algorithm 1 */ { 276 var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec); 277 context.EvaluatedSolutions++; 278 var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 279 context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */ 280 // Book-keeping 281 if (context.PopulationCount == 1 || context.BestQuality > fitness) { 282 context.BestQuality = fitness; 283 context.BestSolution = (GQAPSolution)pi_prime.Clone(); 135 while (!StoppingCriterion()) { 136 var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda); 137 138 for (var l = 0; l < Lambda; l++) { 139 var m = Context.AtRandomPopulation(); 140 141 var offspring = (ESGQAPSolution)m.Solution.Clone(); 142 var count = Mutate(m, offspring); 143 offspring.SParam += ((1.0 / count) - offspring.SParam) / 10.0; 144 145 offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment); 146 Context.EvaluatedSolutions++; 147 var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation); 148 nextGen.Add(Context.ToScope(offspring, fit)); 149 150 if (fit < Context.BestQuality) { 151 Context.BestQuality = fit; 152 Context.BestSolution = (ESGQAPSolution)offspring.Clone(); 284 153 } 285 154 } 286 155 156 if (Selection == ESSelection.Comma) { 157 Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu)); 158 } else if (Selection == ESSelection.Plus) { 159 var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList(); 160 Context.ReplacePopulation(best); 161 } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection); 162 287 163 IResult result; 288 164 if (Results.TryGetValue("Iterations", out result)) 289 ((IntValue)result.Value).Value = context.Iterations;290 else Results.Add(new Result("Iterations", new IntValue( context.Iterations)));165 ((IntValue)result.Value).Value = Context.Iterations; 166 else Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); 291 167 if (Results.TryGetValue("EvaluatedSolutions", out result)) 292 ((IntValue)result.Value).Value = context.EvaluatedSolutions;293 else Results.Add(new Result("EvaluatedSolutions", new IntValue( context.EvaluatedSolutions)));168 ((IntValue)result.Value).Value = Context.EvaluatedSolutions; 169 else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); 294 170 if (Results.TryGetValue("BestQuality", out result)) 295 ((DoubleValue)result.Value).Value = context.BestQuality;296 else Results.Add(new Result("BestQuality", new DoubleValue( context.BestQuality)));171 ((DoubleValue)result.Value).Value = Context.BestQuality; 172 else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); 297 173 if (Results.TryGetValue("BestSolution", out result)) 298 result.Value = context.BestSolution; 299 else Results.Add(new Result("BestSolution", context.BestSolution)); 300 301 context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken); 302 303 context.Iterations++; 174 result.Value = Context.BestSolution; 175 else Results.Add(new Result("BestSolution", Context.BestSolution)); 176 177 Context.RunOperator(Analyzer, Context.Scope, cancellationToken); 178 179 Context.Iterations++; 180 if (cancellationToken.IsCancellationRequested) break; 304 181 } 305 182 } 306 183 307 private bool IsSufficientlyDifferent(IntegerVector vec) { 308 return context.Population.All(x => 309 HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length) 310 ); 311 } 312 313 private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) { 314 // Following code represents line 1 of Algorithm 4 315 IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment; 316 Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation; 317 var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval); 318 var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval); 319 if (targetFit < sourceFit) { 320 var h = source; 321 source = target; 322 target = h; 323 var hh = sourceEval; 324 sourceEval = targetEval; 325 targetEval = hh; 184 private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) { 185 var offspringFeasible = offspring.Evaluation.IsFeasible; 186 double[] slack = null; 187 if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray(); 188 var count = 1; 189 foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) { 190 var currentLoc = offspring.Assignment[equip]; 191 if (offspringFeasible) { 192 var demand = Problem.ProblemInstance.Demands[equip]; 193 var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v }) 194 .Where(x => x.Index != currentLoc 195 && x.Value >= demand).ToList(); 196 int newLoc = -1; 197 if (feasibleLoc.Count == 0) { 198 newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1); 199 if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc 200 offspringFeasible = false; 201 } else { 202 newLoc = feasibleLoc.SampleRandom(Context.Random).Index; 203 } 204 offspring.Assignment[equip] = newLoc; 205 slack[currentLoc] += demand; 206 slack[newLoc] -= demand; 207 } else { 208 var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1); 209 if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc 210 offspring.Assignment[equip] = newLoc; 211 } 212 if (Context.Random.NextDouble() < m.Solution.SParam) break; 213 count++; 326 214 } 327 int evaluatedSolutions; 328 // lines 2-36 of Algorithm 4 are implemented in the following call 329 var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval, 330 target, targetEval, Problem.ProblemInstance, CandidateSizeFactor, 331 out evaluatedSolutions); 332 context.EvaluatedSolutions += evaluatedSolutions; 333 return pi_star; 334 } 335 336 private void ApproxLocalSearch(GQAPSolution pi_prime) { 337 var localSearchEvaluations = 0; 338 ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize, 339 OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations); 340 context.EvaluatedSolutions += localSearchEvaluations; 341 } 342 343 private bool StoppingCriterion() { 344 return context.Iterations > MaximumIterations; 215 216 return count; 345 217 } 346 218 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs
r15561 r15562 23 23 using System.Linq; 24 24 using System.Threading; 25 using HeuristicLab.Analysis;26 25 using HeuristicLab.Common; 27 26 using HeuristicLab.Core; … … 31 30 using HeuristicLab.Parameters; 32 31 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 33 using HeuristicLab.Random;34 32 35 33 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP { … … 41 39 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] 42 40 [StorableClass] 43 public class GRASP : BasicAlgorithm{41 public sealed class GRASP : StochasticAlgorithm<GRASPContext> { 44 42 45 43 public override bool SupportsPause { … … 57 55 58 56 [Storable] 59 private ValueParameter<IAnalyzer> analyzerParameter;60 public IValueParameter<IAnalyzer> AnalyzerParameter {61 get { return analyzerParameter; }62 }63 64 [Storable]65 private FixedValueParameter<BoolValue> setSeedRandomlyParameter;66 private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {67 get { return setSeedRandomlyParameter; }68 }69 [Storable]70 private FixedValueParameter<IntValue> seedParameter;71 private IFixedValueParameter<IntValue> SeedParameter {72 get { return seedParameter; }73 }74 [Storable]75 57 private FixedValueParameter<IntValue> eliteSetSizeParameter; 76 58 private IFixedValueParameter<IntValue> EliteSetSizeParameter { … … 83 65 } 84 66 [Storable] 85 private FixedValueParameter<IntValue> maximumIterationsParameter;86 public IFixedValueParameter<IntValue> MaximumIterationsParameter {87 get { return maximumIterationsParameter; }88 }89 [Storable]90 67 private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter; 91 68 public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter { 92 get { return maximum IterationsParameter; }69 get { return maximumLocalSearchIterationsParameter; } 93 70 } 94 71 [Storable] … … 113 90 } 114 91 115 public bool SetSeedRandomly {116 get { return setSeedRandomlyParameter.Value.Value; }117 set { setSeedRandomlyParameter.Value.Value = value; }118 }119 public int Seed {120 get { return seedParameter.Value.Value; }121 set { seedParameter.Value.Value = value; }122 }123 92 public int EliteSetSize { 124 93 get { return eliteSetSizeParameter.Value.Value; } … … 129 98 set { minimiumEliteSetSizeParameter.Value.Value = value; } 130 99 } 131 public int MaximumIterations {132 get { return maximumIterationsParameter.Value.Value; }133 set { maximumIterationsParameter.Value.Value = value; }134 }135 100 public int MaximumLocalSearchIterations { 136 101 get { return maximumLocalSearchIterationsParameter.Value.Value; } … … 155 120 156 121 [StorableConstructor] 157 pr otectedGRASP(bool deserializing) : base(deserializing) { }158 pr otectedGRASP(GRASP original, Cloner cloner)122 private GRASP(bool deserializing) : base(deserializing) { } 123 private GRASP(GRASP original, Cloner cloner) 159 124 : base(original, cloner) { 160 setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);161 seedParameter = cloner.Clone(original.seedParameter);162 analyzerParameter = cloner.Clone(original.analyzerParameter);163 125 eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter); 164 126 minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter); 165 maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);166 127 maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter); 167 128 candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter); … … 169 130 oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter); 170 131 minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter); 171 context = cloner.Clone(original.context);172 132 } 173 133 public GRASP() { 174 Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));175 Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));176 Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));177 134 Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10))); 178 135 Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2))); 179 Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));180 136 Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100))); 181 137 Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5))); … … 183 139 Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5))); 184 140 Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4))); 141 185 142 Problem = new GQAP(); 186 143 } … … 190 147 } 191 148 192 public override void Prepare() {193 base.Prepare();194 Results.Clear();195 context = null;196 }197 198 [Storable]199 private GRASPContext context;200 201 149 protected override void Initialize(CancellationToken cancellationToken) { 202 150 base.Initialize(cancellationToken); 203 context = new GRASPContext(); 204 context.Problem = Problem; 205 context.Scope.Variables.Add(new Variable("Results", Results)); 206 207 IExecutionContext ctxt = null; 208 foreach (var item in Problem.ExecutionContextItems) 209 ctxt = new Core.ExecutionContext(ctxt, item, context.Scope); 210 ctxt = new Core.ExecutionContext(ctxt, this, context.Scope); 211 context.Parent = ctxt; 212 213 if (SetSeedRandomly) { 214 var rnd = new System.Random(); 215 Seed = rnd.Next(); 216 } 217 context.Random = new MersenneTwister((uint)Seed); 218 context.Iterations = 0; 219 context.EvaluatedSolutions = 0; 220 context.BestQuality = double.NaN; 221 context.BestSolution = null; 222 223 context.Initialized = true; 224 225 Results.Add(new Result("Iterations", new IntValue(context.Iterations))); 226 Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions))); 227 Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality))); 151 152 Context.Problem = Problem; 153 Context.BestQuality = double.NaN; 154 Context.BestSolution = null; 155 156 Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); 157 Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); 158 Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); 228 159 Results.Add(new Result("BestSolution", typeof(GQAPSolution))); 229 160 230 context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);161 Context.RunOperator(Analyzer, Context.Scope, cancellationToken); 231 162 } 232 163 … … 235 166 while (!StoppingCriterion()) { // line 2 in Algorithm 1 236 167 // next: line 3 in Algorithm 1 237 var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution( context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);238 if ( context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1168 var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken); 169 if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1 239 170 GQAPSolution pi_prime; 240 171 if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1 241 pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1172 pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1 242 173 else { 243 174 // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1 244 175 pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec); 245 context.EvaluatedSolutions++;176 Context.EvaluatedSolutions++; 246 177 } 247 178 248 179 ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1 249 var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1180 var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1 250 181 pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1 251 182 ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1 252 183 var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 253 184 // Book-keeping 254 if ( context.BestQuality > fitness) {255 context.BestQuality = fitness;256 context.BestSolution = (GQAPSolution)pi_prime.Clone();257 } 258 259 if ( context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1185 if (Context.BestQuality > fitness) { 186 Context.BestQuality = fitness; 187 Context.BestSolution = (GQAPSolution)pi_prime.Clone(); 188 } 189 190 if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1 260 191 var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 261 double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();192 double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray(); 262 193 if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1 263 var replacement = context.Population.Select((v, i) => new { V = v, Index = i })194 var replacement = Context.Population.Select((v, i) => new { V = v, Index = i }) 264 195 .Where(x => x.V.Fitness >= fit).ToArray(); 265 196 if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1 266 197 // next two lines: line 14 in Algorithm 1 267 198 replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray(); 268 context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit));199 Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit)); 269 200 } 270 201 } 271 202 } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1 272 context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1203 Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1 273 204 } 274 205 } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */ 275 206 && IsSufficientlyDifferent(pi_prime_vec)) /* cond. 2 of line 21 in Algorithm 1 */ { 276 207 var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec); 277 context.EvaluatedSolutions++;208 Context.EvaluatedSolutions++; 278 209 var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 279 context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */210 Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */ 280 211 // Book-keeping 281 if ( context.PopulationCount == 1 || context.BestQuality > fitness) {282 context.BestQuality = fitness;283 context.BestSolution = (GQAPSolution)pi_prime.Clone();212 if (Context.PopulationCount == 1 || Context.BestQuality > fitness) { 213 Context.BestQuality = fitness; 214 Context.BestSolution = (GQAPSolution)pi_prime.Clone(); 284 215 } 285 216 } … … 287 218 IResult result; 288 219 if (Results.TryGetValue("Iterations", out result)) 289 ((IntValue)result.Value).Value = context.Iterations;290 else Results.Add(new Result("Iterations", new IntValue( context.Iterations)));220 ((IntValue)result.Value).Value = Context.Iterations; 221 else Results.Add(new Result("Iterations", new IntValue(Context.Iterations))); 291 222 if (Results.TryGetValue("EvaluatedSolutions", out result)) 292 ((IntValue)result.Value).Value = context.EvaluatedSolutions;293 else Results.Add(new Result("EvaluatedSolutions", new IntValue( context.EvaluatedSolutions)));223 ((IntValue)result.Value).Value = Context.EvaluatedSolutions; 224 else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions))); 294 225 if (Results.TryGetValue("BestQuality", out result)) 295 ((DoubleValue)result.Value).Value = context.BestQuality;296 else Results.Add(new Result("BestQuality", new DoubleValue( context.BestQuality)));226 ((DoubleValue)result.Value).Value = Context.BestQuality; 227 else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality))); 297 228 if (Results.TryGetValue("BestSolution", out result)) 298 result.Value = context.BestSolution; 299 else Results.Add(new Result("BestSolution", context.BestSolution)); 300 301 context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken); 302 303 context.Iterations++; 229 result.Value = Context.BestSolution; 230 else Results.Add(new Result("BestSolution", Context.BestSolution)); 231 232 Context.RunOperator(Analyzer, Context.Scope, cancellationToken); 233 234 Context.Iterations++; 235 if (cancellationToken.IsCancellationRequested) break; 304 236 } 305 237 } 306 238 307 239 private bool IsSufficientlyDifferent(IntegerVector vec) { 308 return context.Population.All(x =>240 return Context.Population.All(x => 309 241 HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length) 310 242 ); … … 327 259 int evaluatedSolutions; 328 260 // lines 2-36 of Algorithm 4 are implemented in the following call 329 var pi_star = GQAPPathRelinking.Apply( context.Random, source, sourceEval,261 var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval, 330 262 target, targetEval, Problem.ProblemInstance, CandidateSizeFactor, 331 263 out evaluatedSolutions); 332 context.EvaluatedSolutions += evaluatedSolutions;264 Context.EvaluatedSolutions += evaluatedSolutions; 333 265 return pi_star; 334 266 } … … 336 268 private void ApproxLocalSearch(GQAPSolution pi_prime) { 337 269 var localSearchEvaluations = 0; 338 ApproximateLocalSearch.Apply( context.Random, pi_prime, MaximumCandidateListSize,270 ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize, 339 271 OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations); 340 context.EvaluatedSolutions += localSearchEvaluations; 341 } 342 343 private bool StoppingCriterion() { 344 return context.Iterations > MaximumIterations; 272 Context.EvaluatedSolutions += localSearchEvaluations; 345 273 } 346 274 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASPContext.cs
r15561 r15562 20 20 #endregion 21 21 22 using System;23 using System.Collections.Generic;24 22 using System.Linq; 25 using System.Runtime.CompilerServices;26 using System.Threading;27 23 using HeuristicLab.Common; 28 24 using HeuristicLab.Core; 29 using HeuristicLab.Data;30 using HeuristicLab.Optimization;31 25 using HeuristicLab.Parameters; 32 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 33 using HeuristicLab.Random;34 27 35 28 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP { 36 29 [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")] 37 30 [StorableClass] 38 public sealed class GRASPContext : ParameterizedNamedItem, IExecutionContext{31 public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 39 32 40 private IExecutionContext parent;41 public IExecutionContext Parent {42 get { return parent; }43 set { parent = value; }44 }45 46 [Storable]47 private IScope scope;48 public IScope Scope {49 get { return scope; }50 private set { scope = value; }51 }52 53 IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {54 get { return Parameters; }55 }56 57 33 [Storable] 58 34 private IValueParameter<GQAP> problem; … … 60 36 get { return problem.Value; } 61 37 set { problem.Value = value; } 62 }63 public bool Maximization {64 get { return Problem.Maximization; }65 }66 67 [Storable]68 private IValueParameter<BoolValue> initialized;69 public bool Initialized {70 get { return initialized.Value.Value; }71 set { initialized.Value.Value = value; }72 }73 74 [Storable]75 private IValueParameter<IntValue> iterations;76 public int Iterations {77 get { return iterations.Value.Value; }78 set { iterations.Value.Value = value; }79 }80 81 [Storable]82 private IValueParameter<IntValue> evaluatedSolutions;83 public int EvaluatedSolutions {84 get { return evaluatedSolutions.Value.Value; }85 set { evaluatedSolutions.Value.Value = value; }86 }87 88 [Storable]89 private IValueParameter<DoubleValue> bestQuality;90 public double BestQuality {91 get { return bestQuality.Value.Value; }92 set { bestQuality.Value.Value = value; }93 38 } 94 39 … … 99 44 set { bestSolution.Value = value; } 100 45 } 101 102 [Storable]103 private IValueParameter<IntValue> localSearchEvaluations;104 public int LocalSearchEvaluations {105 get { return localSearchEvaluations.Value.Value; }106 set { localSearchEvaluations.Value.Value = value; }107 }108 46 109 [Storable]110 private IValueParameter<IRandom> random;111 public IRandom Random {112 get { return random.Value; }113 set { random.Value = value; }114 }115 116 public IEnumerable<ISingleObjectiveSolutionScope<GQAPSolution>> Population {117 get { return scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>(); }118 }119 public void AddToPopulation(ISingleObjectiveSolutionScope<GQAPSolution> solScope) {120 scope.SubScopes.Add(solScope);121 }122 public void ReplaceAtPopulation(int index, ISingleObjectiveSolutionScope<GQAPSolution> solScope) {123 scope.SubScopes[index] = solScope;124 }125 public ISingleObjectiveSolutionScope<GQAPSolution> AtPopulation(int index) {126 return scope.SubScopes[index] as ISingleObjectiveSolutionScope<GQAPSolution>;127 }128 47 public void SortPopulation() { 129 scope.SubScopes.Replace(scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Maximization ? -x.Fitness : x.Fitness).ToList()); 130 } 131 public int PopulationCount { 132 get { return scope.SubScopes.Count; } 48 Scope.SubScopes.Replace(Scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Problem.Maximization ? -x.Fitness : x.Fitness).ToList()); 133 49 } 134 50 … … 137 53 private GRASPContext(GRASPContext original, Cloner cloner) 138 54 : base(original, cloner) { 139 scope = cloner.Clone(original.scope);140 55 problem = cloner.Clone(original.problem); 141 initialized = cloner.Clone(original.initialized);142 iterations = cloner.Clone(original.iterations);143 evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);144 bestQuality = cloner.Clone(original.bestQuality);145 56 bestSolution = cloner.Clone(original.bestSolution); 146 localSearchEvaluations = cloner.Clone(original.localSearchEvaluations);147 random = cloner.Clone(original.random);148 57 } 149 58 public GRASPContext() : this("GRASP+PR (GQAP) Context") { } 150 59 public GRASPContext(string name) : base(name) { 151 scope = new Scope("Global");152 153 60 Parameters.Add(problem = new ValueParameter<GQAP>("Problem")); 154 Parameters.Add(initialized = new ValueParameter<BoolValue>("Initialized", new BoolValue(false)));155 Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));156 Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));157 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));158 61 Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution")); 159 Parameters.Add(localSearchEvaluations = new ValueParameter<IntValue>("LocalSearchEvaluations", new IntValue(0)));160 Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));161 62 } 162 63 … … 175 76 return scope; 176 77 } 177 178 public void IncrementEvaluatedSolutions(int byEvaluations) {179 if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");180 EvaluatedSolutions += byEvaluations;181 }182 183 private static void ExecuteAlgorithm(IAlgorithm algorithm) {184 using (var evt = new AutoResetEvent(false)) {185 EventHandler exeStateChanged = (o, args) => {186 if (algorithm.ExecutionState != ExecutionState.Started)187 evt.Set();188 };189 algorithm.ExecutionStateChanged += exeStateChanged;190 if (algorithm.ExecutionState != ExecutionState.Prepared) {191 algorithm.Prepare(true);192 evt.WaitOne();193 }194 algorithm.Start();195 evt.WaitOne();196 algorithm.ExecutionStateChanged -= exeStateChanged;197 }198 }199 [MethodImpl(MethodImplOptions.AggressiveInlining)]200 public bool IsBetter(ISingleObjectiveSolutionScope<GQAPSolution> a, ISingleObjectiveSolutionScope<GQAPSolution> b) {201 return IsBetter(a.Fitness, b.Fitness);202 }203 [MethodImpl(MethodImplOptions.AggressiveInlining)]204 public bool IsBetter(double a, double b) {205 return double.IsNaN(b) && !double.IsNaN(a)206 || Maximization && a > b207 || !Maximization && a < b;208 }209 210 #region IExecutionContext members211 public IAtomicOperation CreateOperation(IOperator op) {212 return new Core.ExecutionContext(this, op, Scope);213 }214 215 public IAtomicOperation CreateOperation(IOperator op, IScope s) {216 return new Core.ExecutionContext(this, op, s);217 }218 219 public IAtomicOperation CreateChildOperation(IOperator op) {220 return new Core.ExecutionContext(this, op, Scope);221 }222 223 public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {224 return new Core.ExecutionContext(this, op, s);225 }226 #endregion227 228 #region Engine Helper229 public void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {230 var stack = new Stack<IOperation>();231 stack.Push(CreateChildOperation(op, scope));232 233 while (stack.Count > 0) {234 cancellationToken.ThrowIfCancellationRequested();235 236 var next = stack.Pop();237 if (next is OperationCollection) {238 var coll = (OperationCollection)next;239 for (int i = coll.Count - 1; i >= 0; i--)240 if (coll[i] != null) stack.Push(coll[i]);241 } else if (next is IAtomicOperation) {242 var operation = (IAtomicOperation)next;243 try {244 next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);245 } catch (Exception ex) {246 stack.Push(operation);247 if (ex is OperationCanceledException) throw ex;248 else throw new OperatorExecutionException(operation.Operator, ex);249 }250 if (next != null) stack.Push(next);251 }252 }253 }254 #endregion255 78 } 256 79 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj
r15553 r15562 99 99 </ItemGroup> 100 100 <ItemGroup> 101 <Compile Include="GRASPContext.cs" /> 102 <Compile Include="GRASP.cs" /> 103 <Compile Include="Interfaces.cs" /> 101 <Compile Include="Evolutionary\ESContext.cs" /> 102 <Compile Include="Evolutionary\ESGQAPSolution.cs" /> 103 <Compile Include="Evolutionary\EvolutionStrategy.cs" /> 104 <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" /> 105 <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" /> 106 <Compile Include="Infrastructure\Contexts\SingleObjectivePopulationContext.cs" /> 107 <Compile Include="Infrastructure\Contexts\StochasticContext.cs" /> 108 <Compile Include="Infrastructure\Contexts\BasicContext.cs" /> 109 <Compile Include="Infrastructure\Algorithms\ContextAlgorithm.cs" /> 110 <Compile Include="GRASP\GRASPContext.cs" /> 111 <Compile Include="GRASP\GRASP.cs" /> 112 <Compile Include="LocalSearch\LocalSearchContext.cs" /> 113 <Compile Include="Infrastructure\Interfaces.cs" /> 114 <Compile Include="LocalSearch\IteratedLS.cs" /> 115 <Compile Include="LocalSearch\MultistartLS.cs" /> 104 116 <Compile Include="Plugin.cs" /> 117 <Compile Include="Infrastructure\Contexts\SingleSolutionContext.cs" /> 118 <Compile Include="Infrastructure\Contexts\PopulationContext.cs" /> 105 119 <Compile Include="Properties\AssemblyInfo.cs" /> 106 <Compile Include=" SingleObjectiveSolutionScope.cs" />120 <Compile Include="Infrastructure\SingleObjectiveSolutionScope.cs" /> 107 121 </ItemGroup> 108 122 <ItemGroup> -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Interfaces.cs
r15561 r15562 29 29 void Adopt(ISingleObjectiveSolutionScope<TSolution> orphan); 30 30 } 31 32 public interface IContext : IExecutionContext { 33 new IExecutionContext Parent { get; set; } 34 int Iterations { get; set; } 35 int EvaluatedSolutions { get; set; } 36 } 37 38 public interface IStochasticContext : IContext { 39 IRandom Random { get; set; } 40 } 31 41 }
Note: See TracChangeset
for help on using the changeset viewer.