Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15572


Ignore:
Timestamp:
01/03/18 00:28:51 (7 years ago)
Author:
abeham
Message:

#1614:

  • fixed a bug in GRASP where solutions in the elite set would be mutated
  • introduced termination criteria when reaching best-known quality
  • tweaked generating random numbers in StochasticNMoveSingleMoveGenerator
  • changed DiscreteLocationCrossover to use an allele from one of the parents instead of introducing a mutation in case no feasible insert location is found
  • changed OSGA maxselpress to 500
  • slight change to contexts, introduced single-objectiveness much earlier in the class hierachy
    • limited ContextAlgorithm to SingleObjectiveBasicProblems (doesn't matter here)
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  
    2828  [Item("Evolution Strategy (GQAP) Context", "Context for Evolution Strategies (GQAP).")]
    2929  [StorableClass]
    30   public sealed class ESContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> {
     30  public sealed class ESContext : PopulationContext<ISingleObjectiveSolutionScope<ESGQAPSolution>> {
    3131   
    3232    [Storable]

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs

    r15564 r15572  
    3939  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    4040  [StorableClass]
    41   public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext> {
     41  public sealed class EvolutionStrategy : StochasticAlgorithm<ESContext, IntegerVectorEncoding> {
    4242
    4343    public override bool SupportsPause {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGA.cs

    r15564 r15572  
    3535  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    3636  [StorableClass]
    37   public sealed class OSGA : StochasticAlgorithm<OSGAContext> {
     37  public sealed class OSGA : StochasticAlgorithm<OSGAContext, IntegerVectorEncoding> {
    3838
    3939    public override bool SupportsPause {
    … …  
    127127       
    128128        while (!StoppingCriterion() && Context.NextGeneration.Count < PopulationSize
    129           && Context.SelectionPressure < 1000) {
     129          && Context.SelectionPressure < 500) {
    130130
    131131          var idx1 = Context.Random.Next(PopulationSize);
    … …  
    160160          Context.SelectionPressure += 1.0 / PopulationSize;
    161161          Context.Attempts++;
    162           if (Context.SelectionPressure > 10
    163             && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 1000)
     162          if (Context.SelectionPressure > 1
     163            && Context.NextGeneration.Count / (double)PopulationSize < Context.SelectionPressure / 500)
    164164            break;
    165165          if (cancellationToken.IsCancellationRequested) return;

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGAContext.cs

    r15564 r15572  
    3030  [Item("OSGA (GQAP) Context", "Context for OSGA (GQAP).")]
    3131  [StorableClass]
    32   public sealed class OSGAContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     32  public sealed class OSGAContext : PopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3333   
    3434    [Storable]

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs

    r15564 r15572  
    3636  /// 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
    3737  /// </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>
    3841  [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.")]
    3942  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
    4043  [StorableClass]
    41   public sealed class GRASP : StochasticAlgorithm<GRASPContext> {
     44  public sealed class GRASP : StochasticAlgorithm<GRASPContext, IntegerVectorEncoding> {
    4245
    4346    public override bool SupportsPause {
    … …  
    175178          GQAPSolution pi_prime;
    176179          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 1
     180            pi_prime = (GQAPSolution)Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution.Clone(); // line 6 in Algorithm 1
    178181          else {
    179182            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
    … …  
    188191          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    189192          // Book-keeping
    190           if (Context.BestQuality > fitness) {
     193          var newBest = Context.BestQuality > fitness;
     194          if (newBest) {
    191195            Context.BestQuality = fitness;
    192196            Context.BestSolution = (GQAPSolution)pi_prime.Clone();
    … …  
    194198
    195199          if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
    196             var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    197200            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
    205210              }
    206211            }
    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
    208215            Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
    209216          }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASPContext.cs

    r15562 r15572  
    2929  [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")]
    3030  [StorableClass]
    31   public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     31  public sealed class GRASPContext : PopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3232   
    3333    [Storable]

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj

    r15564 r15572  
    105105    <Compile Include="Evolutionary\OSGA.cs" />
    106106    <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" />
    107     <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" />
    108     <Compile Include="Infrastructure\Contexts\SingleObjectivePopulationContext.cs" />
    109107    <Compile Include="Infrastructure\Contexts\StochasticContext.cs" />
    110108    <Compile Include="Infrastructure\Contexts\BasicContext.cs" />

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs

    r15562 r15572  
    3333  [Item("Context-based Algorithm", "Algorithms that make use of contexts to facilitate applying operators.")]
    3434  [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    }
    3747
    3848    [Storable]
    … …  
    6272      get { return maximumRuntimeParameter; }
    6373    }
     74    [Storable]
     75    private FixedValueParameter<BoolValue> stopAtBestKnownQualityParameter;
     76    public IFixedValueParameter<BoolValue> StopAtBestKnownQualityParameter {
     77      get { return stopAtBestKnownQualityParameter; }
     78    }
    6479
    6580    public IAnalyzer Analyzer {
    … …  
    7994      set { maximumRuntimeParameter.Value.Value = value; }
    8095    }
     96    public bool StopAtBestKnownQuality {
     97      get { return stopAtBestKnownQualityParameter.Value.Value; }
     98      set { stopAtBestKnownQualityParameter.Value.Value = value; }
     99    }
    81100
    82101    [StorableConstructor]
    83102    protected ContextAlgorithm(bool deserializing) : base(deserializing) { }
    84     protected ContextAlgorithm(ContextAlgorithm<TContext> original, Cloner cloner)
     103    protected ContextAlgorithm(ContextAlgorithm<TContext, TEncoding> original, Cloner cloner)
    85104      : base(original, cloner) {
    86105      context = cloner.Clone(original.context);
    … …  
    89108      maximumEvaluationsParameter = cloner.Clone(original.maximumEvaluationsParameter);
    90109      maximumRuntimeParameter = cloner.Clone(original.maximumRuntimeParameter);
     110      stopAtBestKnownQualityParameter = cloner.Clone(original.stopAtBestKnownQualityParameter);
    91111    }
    92112    protected ContextAlgorithm()
    … …  
    96116      Parameters.Add(maximumEvaluationsParameter = new FixedValueParameter<IntValue>("MaximumEvaluations", "The number of evaluated solutions that the algorithm should perform or < 1 to ignore.", new IntValue(0)));
    97117      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)));
    98119    }
    99120
    … …  
    121142      return MaximumIterations > 0 && Context.Iterations > MaximumIterations
    122143        || 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);
    124147    }
    125148  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/StochasticAlgorithm.cs

    r15562 r15572  
    2424using HeuristicLab.Core;
    2525using HeuristicLab.Data;
     26using HeuristicLab.Optimization;
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3132  [Item("Stochastic Algorithm", "Stochastic context-based algorithms to facilitate applying operators.")]
    3233  [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 {
    3537   
    3638    [Storable]
    … …  
    5658    [StorableConstructor]
    5759    protected StochasticAlgorithm(bool deserializing) : base(deserializing) { }
    58     protected StochasticAlgorithm(StochasticAlgorithm<TContext> original, Cloner cloner)
     60    protected StochasticAlgorithm(StochasticAlgorithm<TContext, TEncoding> original, Cloner cloner)
    5961      : base(original, cloner) {
    6062      setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Contexts/BasicContext.cs

    r15562 r15572  
    6363    }
    6464
     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
    6572    [StorableConstructor]
    6673    protected BasicContext(bool deserializing) : base(deserializing) { }
    … …  
    7077      iterations = cloner.Clone(original.iterations);
    7178      evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
     79      bestQuality = cloner.Clone(original.bestQuality);
    7280    }
    7381    protected BasicContext() : base() {
    … …  
    7583      Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0)));
    7684      Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     85      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    7786    }
    7887    protected BasicContext(string name) : base(name) {
    … …  
    8089      Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0)));
    8190      Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     91      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    8292    }
    8393    protected BasicContext(string name, ParameterCollection parameters) : base(name, parameters) {
    … …  
    8595      Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0)));
    8696      Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     97      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    8798    }
    8899    protected BasicContext(string name, string description) : base(name, description) {
    … …  
    90101      Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0)));
    91102      Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     103      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    92104    }
    93105    protected BasicContext(string name, string description, ParameterCollection parameters) : base(name, description, parameters) {
    … …  
    95107      Parameters.Add(iterations = new FixedValueParameter<IntValue>("Iterations", new IntValue(0)));
    96108      Parameters.Add(evaluatedSolutions = new FixedValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     109      Parameters.Add(bestQuality = new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(double.NaN)));
    97110    }
    98111

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Interfaces.cs

    r15562 r15572  
    2626    TSolution Solution { get; set; }
    2727    double Fitness { get; set; }
    28 
    29     void Adopt(ISingleObjectiveSolutionScope<TSolution> orphan);
    3028  }
    3129
    … …  
    3432    int Iterations { get; set; }
    3533    int EvaluatedSolutions { get; set; }
     34    double BestQuality { get; set; }
    3635  }
    3736

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/SingleObjectiveSolutionScope.cs

    r15562 r15572  
    134134    }
    135135    #endregion
    136 
    137     public void Adopt(ISingleObjectiveSolutionScope<T> orphan) {
    138       Solution = orphan.Solution;
    139       Fitness = orphan.Fitness;
    140     }
    141136  }
    142137}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHC.cs

    r15564 r15572  
    3535  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3636  [StorableClass]
    37   public sealed class LAHC : StochasticAlgorithm<LAHCContext> {
     37  public sealed class LAHC : StochasticAlgorithm<LAHCContext, IntegerVectorEncoding> {
    3838
    3939    public override bool SupportsPause {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHCContext.cs

    r15563 r15572  
    2727
    2828namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
    29   public sealed class LAHCContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     29  public sealed class LAHCContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3030    [Storable]
    3131    private IValueParameter<GQAP> problem;

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHC.cs

    r15564 r15572  
    3434  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3535  [StorableClass]
    36   public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext> {
     36  public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext, IntegerVectorEncoding> {
    3737
    3838    public override bool SupportsPause {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHCContext.cs

    r15563 r15572  
    2727
    2828namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
    29   public sealed class PLAHCContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     29  public sealed class PLAHCContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3030    [Storable]
    3131    private IValueParameter<GQAP> problem;

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/IteratedLS.cs

    r15564 r15572  
    2525using HeuristicLab.Core;
    2626using HeuristicLab.Data;
     27using HeuristicLab.Encodings.IntegerVectorEncoding;
    2728using HeuristicLab.Optimization;
    2829using HeuristicLab.Parameters;
    … …  
    3334  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3435  [StorableClass]
    35   public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext> {
     36  public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext, IntegerVectorEncoding> {
    3637
    3738    public override bool SupportsPause {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/LocalSearchContext.cs

    r15562 r15572  
    2626
    2727namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
    28   public sealed class LocalSearchContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     28  public sealed class LocalSearchContext : SingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    2929    [Storable]
    3030    private IValueParameter<GQAP> problem;

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/MultistartLS.cs

    r15564 r15572  
    3333  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3434  [StorableClass]
    35   public sealed class MultistartLS : StochasticAlgorithm<LocalSearchContext> {
     35  public sealed class MultistartLS : StochasticAlgorithm<LocalSearchContext, IntegerVectorEncoding> {
    3636
    3737    public override bool SupportsPause {

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs

    r15553 r15572  
    6565
    6666      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;
    6868
    6969      return new NMove(reassignment, equipments);
    … …  
    7474      if (locations <= 1) throw new ArgumentException("There must be at least two locations.");
    7575      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);
    8078
    8179      var reassignment = new int[dim];
    8280      for (var i = 0; i < 2; i++) {
    8381        var equip = equipments[i];
    84         reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
     82        reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations;
    8583      }
    8684      return new NMove(reassignment, equipments);
    … …  
    9896      for (var i = 0; i < n; i++) {
    9997        var equip = equipments[i];
    100         reassignment[equip] = ReassignEquipment(random, equip, assignment[equip], locations);
     98        reassignment[equip] = 1 + (assignment[equip] + random.Next(1, locations)) % locations;
    10199      }
    102100      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;
    110101    }
    111102

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs

    r15564 r15572  
    8383      }
    8484
    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
    8688      foreach (var e in order) {
    87         if (takenEquip[e]) continue;
    8889        var assigned = false;
    8990        // 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];
    9396            slack[child[e]] -= demands[e];
    9497            assigned = true;
    9598            break;
     99          } else if (random.NextDouble() < 1.0 / count) {
     100            fallback = p[e];
    96101          }
     102          count++;
    97103        }
    98104        // try 2: find a random feasible location
    … …  
    103109            child[e] = loc;
    104110            slack[loc] -= demands[e];
    105             assigned = true;
     111          } else {
     112            // otherwise: fallback
     113            child[e] = fallback;
     114            slack[child[e]] -= demands[e];
    106115          }
    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];
    112116        }
    113117      }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs

    r15558 r15572  
    7979      var sFit = problemInstance.ToSingleObjective(sourceEval);
    8080      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
    8284      double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
    8385     

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Manipulators/RelocateEquipmentManipluator.cs

    r15564 r15572  
    5151      foreach (var equipment in equipments) {
    5252        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;
    5654        if (random.NextDouble() < stopProb) break;
    5755      }
Note: See TracChangeset for help on using the changeset viewer.