Changeset 15572 for branches/GeneralizedQAP
- Timestamp:
- 01/03/18 00:28:51 (7 years ago)
- Location:
- branches/GeneralizedQAP
- Files:
-
- 2 deleted
- 23 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/ESContext.cs
r15564 r15572 28 28 [Item("Evolution Strategy (GQAP) Context", "Context for Evolution Strategies (GQAP).")] 29 29 [StorableClass] 30 public sealed class ESContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> {30 public sealed class ESContext : PopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> { 31 31 32 32 [Storable] -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs
r15564 r15572 39 39 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] 40 40 [StorableClass] 41 public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext > {41 public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext, IntegerVectorEncoding> { 42 42 43 43 public override bool SupportsPause { -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGA.cs
r15564 r15572 35 35 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] 36 36 [StorableClass] 37 public sealed class OSGA : StochasticAlgorithm<OSGAContext > {37 public sealed class OSGA : StochasticAlgorithm<OSGAContext, IntegerVectorEncoding> { 38 38 39 39 public override bool SupportsPause { … … 127 127 128 128 while (!StoppingCriterion() && Context.NextGeneration.Count < PopulationSize 129 && Context.SelectionPressure < 1000) {129 && Context.SelectionPressure < 500) { 130 130 131 131 var idx1 = Context.Random.Next(PopulationSize); … … 160 160 Context.SelectionPressure += 1.0 / PopulationSize; 161 161 Context.Attempts++; 162 if (Context.SelectionPressure > 1 0163 && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 1000)162 if (Context.SelectionPressure > 1 163 && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 500) 164 164 break; 165 165 if (cancellationToken.IsCancellationRequested) return; -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGAContext.cs
r15564 r15572 30 30 [Item("OSGA (GQAP) Context", "Context for OSGA (GQAP).")] 31 31 [StorableClass] 32 public sealed class OSGAContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {32 public sealed class OSGAContext : PopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 33 33 34 34 [Storable] -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs
r15564 r15572 36 36 /// 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 37 37 /// </summary> 38 /// <remarks> 39 /// A fine distinction to the described algorithm is that newly found best solutions are always accepted into the elite set. This is reasonable, but not mentioned in the paper by Mateus et al. 40 /// </remarks> 38 41 [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.")] 39 42 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)] 40 43 [StorableClass] 41 public sealed class GRASP : StochasticAlgorithm<GRASPContext > {44 public sealed class GRASP : StochasticAlgorithm<GRASPContext, IntegerVectorEncoding> { 42 45 43 46 public override bool SupportsPause { … … 175 178 GQAPSolution pi_prime; 176 179 if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1 177 pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1180 pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1 178 181 else { 179 182 // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1 … … 188 191 var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation); 189 192 // Book-keeping 190 if (Context.BestQuality > fitness) { 193 var newBest = Context.BestQuality > fitness; 194 if (newBest) { 191 195 Context.BestQuality = fitness; 192 196 Context.BestSolution = (GQAPSolution)pi_prime.Clone(); … … 194 198 195 199 if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1 196 var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);197 200 double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray(); 198 if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1 199 var replacement = Context.Population.Select((v, i) => new { V = v, Index = i }) 200 .Where(x => x.V.Fitness >= fit).ToArray(); 201 if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1 202 // next two lines: line 14 in Algorithm 1 203 replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray(); 204 Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit)); 201 // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference 202 // in this implementation a new best solution is always accepted into the elite set 203 if (newBest || similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1 204 var replacement = Context.Population.Select((v, i) => new { Scope = v, Index = i }) 205 .Where(x => x.Scope.Fitness >= fitness) // cond. 1 of line 13 in Algorithm 1 206 .OrderByDescending(x => similarities[x.Index]) // line 14 in Algorithm 1 207 .FirstOrDefault(); 208 if (replacement != null) { 209 Context.ReplaceAtPopulation(replacement.Index, Context.ToScope(pi_prime, fitness)); // line 14 in Algorithm 1 205 210 } 206 211 } 207 } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1 212 // NOTE: In the original paper it is not described that new best solutions are accepted regardless of difference 213 // in this implementation a new best solution is always accepted into the elite set 214 } else if (newBest || IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1 208 215 Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1 209 216 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASPContext.cs
r15562 r15572 29 29 [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")] 30 30 [StorableClass] 31 public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {31 public sealed class GRASPContext : PopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 32 32 33 33 [Storable] -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj
r15564 r15572 105 105 <Compile Include="Evolutionary\OSGA.cs" /> 106 106 <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" /> 107 <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" />108 <Compile Include="Infrastructure\Contexts\SingleObjectivePopulationContext.cs" />109 107 <Compile Include="Infrastructure\Contexts\StochasticContext.cs" /> 110 108 <Compile Include="Infrastructure\Contexts\BasicContext.cs" /> -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs
r15562 r15572 33 33 [Item("Context-based Algorithm", "Algorithms that make use of contexts to facilitate applying operators.")] 34 34 [StorableClass] 35 public abstract class ContextAlgorithm<TContext> : BasicAlgorithm 36 where TContext : class, IContext, new() { 35 public abstract class ContextAlgorithm<TContext, TEncoding> : BasicAlgorithm 36 where TContext : class, IContext, new() 37 where TEncoding : class, IEncoding { 38 39 public override Type ProblemType { 40 get { return typeof(SingleObjectiveBasicProblem<TEncoding>); } 41 } 42 43 public new SingleObjectiveBasicProblem<TEncoding> Problem { 44 get { return (SingleObjectiveBasicProblem<TEncoding>)base.Problem; } 45 set { base.Problem = value; } 46 } 37 47 38 48 [Storable] … … 62 72 get { return maximumRuntimeParameter; } 63 73 } 74 [Storable] 75 private FixedValueParameter<BoolValue> stopAtBestKnownQualityParameter; 76 public IFixedValueParameter<BoolValue> StopAtBestKnownQualityParameter { 77 get { return stopAtBestKnownQualityParameter; } 78 } 64 79 65 80 public IAnalyzer Analyzer { … … 79 94 set { maximumRuntimeParameter.Value.Value = value; } 80 95 } 96 public bool StopAtBestKnownQuality { 97 get { return stopAtBestKnownQualityParameter.Value.Value; } 98 set { stopAtBestKnownQualityParameter.Value.Value = value; } 99 } 81 100 82 101 [StorableConstructor] 83 102 protected ContextAlgorithm(bool deserializing) : base(deserializing) { } 84 protected ContextAlgorithm(ContextAlgorithm<TContext > original, Cloner cloner)103 protected ContextAlgorithm(ContextAlgorithm<TContext, TEncoding> original, Cloner cloner) 85 104 : base(original, cloner) { 86 105 context = cloner.Clone(original.context); … … 89 108 maximumEvaluationsParameter = cloner.Clone(original.maximumEvaluationsParameter); 90 109 maximumRuntimeParameter = cloner.Clone(original.maximumRuntimeParameter); 110 stopAtBestKnownQualityParameter = cloner.Clone(original.stopAtBestKnownQualityParameter); 91 111 } 92 112 protected ContextAlgorithm() … … 96 116 Parameters.Add(maximumEvaluationsParameter = new FixedValueParameter<IntValue>("MaximumEvaluations", "The number of evaluated solutions that the algorithm should perform or < 1 to ignore.", new IntValue(0))); 97 117 Parameters.Add(maximumRuntimeParameter = new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The timespan that the algorithm is allowed to run.", new TimeSpanValue(TimeSpan.FromMinutes(1)))); 118 Parameters.Add(stopAtBestKnownQualityParameter = new FixedValueParameter<BoolValue>("StopAtBestKnownQuality", "Whether the algorithm should terminate if the best known quality has been found.", new BoolValue(true))); 98 119 } 99 120 … … 121 142 return MaximumIterations > 0 && Context.Iterations > MaximumIterations 122 143 || MaximumEvaluations > 0 && Context.EvaluatedSolutions > MaximumEvaluations 123 || MaximumRuntime > TimeSpan.Zero && ExecutionTime > MaximumRuntime; 144 || MaximumRuntime > TimeSpan.Zero && ExecutionTime > MaximumRuntime 145 || StopAtBestKnownQuality && !double.IsNaN(Problem.BestKnownQuality) 146 && Context.BestQuality.IsAlmost(Problem.BestKnownQuality); 124 147 } 125 148 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/StochasticAlgorithm.cs
r15562 r15572 24 24 using HeuristicLab.Core; 25 25 using HeuristicLab.Data; 26 using HeuristicLab.Optimization; 26 27 using HeuristicLab.Parameters; 27 28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; … … 31 32 [Item("Stochastic Algorithm", "Stochastic context-based algorithms to facilitate applying operators.")] 32 33 [StorableClass] 33 public abstract class StochasticAlgorithm<TContext> : ContextAlgorithm<TContext> 34 where TContext : class, IStochasticContext, new() { 34 public abstract class StochasticAlgorithm<TContext, TEncoding> : ContextAlgorithm<TContext, TEncoding> 35 where TContext : class, IStochasticContext, new() 36 where TEncoding : class, IEncoding { 35 37 36 38 [Storable] … … 56 58 [StorableConstructor] 57 59 protected StochasticAlgorithm(bool deserializing) : base(deserializing) { } 58 protected StochasticAlgorithm(StochasticAlgorithm<TContext > original, Cloner cloner)60 protected StochasticAlgorithm(StochasticAlgorithm<TContext, TEncoding> original, Cloner cloner) 59 61 : base(original, cloner) { 60 62 setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter); -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Contexts/BasicContext.cs
r15562 r15572 63 63 } 64 64 65 [Storable] 66 private IValueParameter<DoubleValue> bestQuality; 67 public double BestQuality { 68 get { return bestQuality.Value.Value; } 69 set { bestQuality.Value.Value = value; } 70 } 71 65 72 [StorableConstructor] 66 73 protected BasicContext(bool deserializing) : base(deserializing) { } … … 70 77 iterations = cloner.Clone(original.iterations); 71 78 evaluatedSolutions = cloner.Clone(original.evaluatedSolutions); 79 bestQuality = cloner.Clone(original.bestQuality); 72 80 } 73 81 protected BasicContext() : base() { … … 75 83 Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0))); 76 84 Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 85 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 77 86 } 78 87 protected BasicContext(string name) : base(name) { … … 80 89 Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0))); 81 90 Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 91 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 82 92 } 83 93 protected BasicContext(string name, ParameterCollection parameters) : base(name, parameters) { … … 85 95 Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0))); 86 96 Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 97 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 87 98 } 88 99 protected BasicContext(string name, string description) : base(name, description) { … … 90 101 Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0))); 91 102 Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 103 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 92 104 } 93 105 protected BasicContext(string name, string description, ParameterCollection parameters) : base(name, description, parameters) { … … 95 107 Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0))); 96 108 Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0))); 109 Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN))); 97 110 } 98 111 -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Interfaces.cs
r15562 r15572 26 26 TSolution Solution { get; set; } 27 27 double Fitness { get; set; } 28 29 void Adopt(ISingleObjectiveSolutionScope<TSolution> orphan);30 28 } 31 29 … … 34 32 int Iterations { get; set; } 35 33 int EvaluatedSolutions { get; set; } 34 double BestQuality { get; set; } 36 35 } 37 36 -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/SingleObjectiveSolutionScope.cs
r15562 r15572 134 134 } 135 135 #endregion 136 137 public void Adopt(ISingleObjectiveSolutionScope<T> orphan) {138 Solution = orphan.Solution;139 Fitness = orphan.Fitness;140 }141 136 } 142 137 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHC.cs
r15564 r15572 35 35 [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)] 36 36 [StorableClass] 37 public sealed class LAHC : StochasticAlgorithm<LAHCContext > {37 public sealed class LAHC : StochasticAlgorithm<LAHCContext, IntegerVectorEncoding> { 38 38 39 39 public override bool SupportsPause { -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHCContext.cs
r15563 r15572 27 27 28 28 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC { 29 public sealed class LAHCContext : Single ObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {29 public sealed class LAHCContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 30 30 [Storable] 31 31 private IValueParameter<GQAP> problem; -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHC.cs
r15564 r15572 34 34 [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)] 35 35 [StorableClass] 36 public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext > {36 public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext, IntegerVectorEncoding> { 37 37 38 38 public override bool SupportsPause { -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHCContext.cs
r15563 r15572 27 27 28 28 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC { 29 public sealed class PLAHCContext : Single ObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {29 public sealed class PLAHCContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 30 30 [Storable] 31 31 private IValueParameter<GQAP> problem; -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/IteratedLS.cs
r15564 r15572 25 25 using HeuristicLab.Core; 26 26 using HeuristicLab.Data; 27 using HeuristicLab.Encodings.IntegerVectorEncoding; 27 28 using HeuristicLab.Optimization; 28 29 using HeuristicLab.Parameters; … … 33 34 [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)] 34 35 [StorableClass] 35 public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext > {36 public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext, IntegerVectorEncoding> { 36 37 37 38 public override bool SupportsPause { -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/LocalSearchContext.cs
r15562 r15572 26 26 27 27 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch { 28 public sealed class LocalSearchContext : Single ObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {28 public sealed class LocalSearchContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> { 29 29 [Storable] 30 30 private IValueParameter<GQAP> problem; -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/MultistartLS.cs
r15564 r15572 33 33 [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)] 34 34 [StorableClass] 35 public sealed class MultistartLS : StochasticAlgorithm<LocalSearchContext > {35 public sealed class MultistartLS : StochasticAlgorithm<LocalSearchContext, IntegerVectorEncoding> { 36 36 37 37 public override bool SupportsPause { -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs
r15553 r15572 65 65 66 66 var reassignment = new int[dim]; 67 reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);67 reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations; 68 68 69 69 return new NMove(reassignment, equipments); … … 74 74 if (locations <= 1) throw new ArgumentException("There must be at least two locations."); 75 75 var dim = assignment.Length; 76 var equipments = new List<int>(2) { random.Next(dim), -1 }; 77 do { 78 equipments[1] = random.Next(dim); 79 } while (equipments[0] == equipments[1]); 76 var equipments = new List<int>(2) { random.Next(dim) }; 77 equipments.Add((equipments[0] + random.Next(1, dim)) % dim); 80 78 81 79 var reassignment = new int[dim]; 82 80 for (var i = 0; i < 2; i++) { 83 81 var equip = equipments[i]; 84 reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);82 reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations; 85 83 } 86 84 return new NMove(reassignment, equipments); … … 98 96 for (var i = 0; i < n; i++) { 99 97 var equip = equipments[i]; 100 reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);98 reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations; 101 99 } 102 100 return new NMove(reassignment, equipments); 103 }104 105 private static int ReassignEquipment(IRandom random, int equip, int prevLocation, int locations) {106 var newLoc = random.Next(locations) + 1;107 while (newLoc == prevLocation + 1)108 newLoc = random.Next(locations) + 1;109 return newLoc;110 101 } 111 102 -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs
r15564 r15572 83 83 } 84 84 85 var order = Enumerable.Range(0, takenEquip.Length).Shuffle(random); // avoid bias 85 var order = Enumerable.Range(0, takenEquip.Length) 86 .Where(x => !takenEquip[x]) 87 .Shuffle(random); // avoid bias 86 88 foreach (var e in order) { 87 if (takenEquip[e]) continue;88 89 var assigned = false; 89 90 // try 1: find a parent where equipment can be assigned feasibly 90 foreach (var p in Enumerable.Range(0, parents.Length).Shuffle(random)) { 91 if (slack[parents[p][e]] >= demands[e]) { 92 child[e] = parents[p][e]; 91 var fallback = -1; 92 var count = 1; 93 foreach (var p in parents.Shuffle(random)) { 94 if (slack[p[e]] >= demands[e]) { 95 child[e] = p[e]; 93 96 slack[child[e]] -= demands[e]; 94 97 assigned = true; 95 98 break; 99 } else if (random.NextDouble() < 1.0 / count) { 100 fallback = p[e]; 96 101 } 102 count++; 97 103 } 98 104 // try 2: find a random feasible location … … 103 109 child[e] = loc; 104 110 slack[loc] -= demands[e]; 105 assigned = true; 111 } else { 112 // otherwise: fallback 113 child[e] = fallback; 114 slack[child[e]] -= demands[e]; 106 115 } 107 }108 // try 3: insert in a random location (no feasible insert found)109 if (!assigned) {110 child[e] = random.Next(locations);111 slack[child[e]] -= demands[e];112 116 } 113 117 } -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs
r15558 r15572 79 79 var sFit = problemInstance.ToSingleObjective(sourceEval); 80 80 var tFit = problemInstance.ToSingleObjective(targetEval); 81 GQAPSolution pi_star = sFit < tFit ? new GQAPSolution(source, sourceEval) : new GQAPSolution(target, targetEval); // line 1 of Algorithm 4 81 GQAPSolution pi_star = sFit < tFit 82 ? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone()) 83 : new GQAPSolution((IntegerVector)target.Clone(), (Evaluation)targetEval.Clone()); // line 1 of Algorithm 4 82 84 double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4 83 85 -
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Manipulators/RelocateEquipmentManipluator.cs
r15564 r15572 51 51 foreach (var equipment in equipments) { 52 52 var oldLoc = assignment[equipment]; 53 var newLoc =random.Next(locations - 1); 54 if (newLoc >= oldLoc) newLoc++; // don't reassign to current loc 55 assignment[equipment] = newLoc; 53 assignment[equipment] = (oldLoc + random.Next(1, locations)) % locations; 56 54 if (random.NextDouble() < stopProb) break; 57 55 }
Note: See TracChangeset
for help on using the changeset viewer.