Changeset 15564


Ignore:
Timestamp:
01/01/18 23:52:39 (12 months ago)
Author:
abeham
Message:

#1614:

  • Fixed some bugs
  • Added OSGA
  • Updated ES (added recombination)
  • Reusing operators among algorihtms (RelocateEquipmentManipluator)
  • Rewrote DiscreteLocationCrossover
Location:
branches/GeneralizedQAP
Files:
1 added
11 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/ESContext.cs

    r15563 r15564  
    2020#endregion
    2121
    22 using System.Collections.Generic;
    2322using HeuristicLab.Common;
    2423using HeuristicLab.Core;
     
    5049      get { return normalRand.Value; }
    5150      set { normalRand.Value = value; }
    52     }
    53 
    54     public void ReplacePopulation(IEnumerable<ISingleObjectiveSolutionScope<ESGQAPSolution>> replacement) {
    55       Scope.SubScopes.Replace(replacement);
    5651    }
    5752   
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/EvolutionStrategy.cs

    r15563 r15564  
    6969      get { return selectionParameter; }
    7070    }
     71    [Storable]
     72    private FixedValueParameter<BoolValue> useRecombinationParameter;
     73    public IFixedValueParameter<BoolValue> UseRecombinationParameter {
     74      get { return useRecombinationParameter; }
     75    }
    7176
    7277    public int Lambda {
     
    8186      get { return selectionParameter.Value.Value; }
    8287      set { selectionParameter.Value.Value = value; }
     88    }
     89    public bool UseRecombination {
     90      get { return useRecombinationParameter.Value.Value; }
     91      set { useRecombinationParameter.Value.Value = value; }
    8392    }
    8493
     
    9099      muParameter = cloner.Clone(original.muParameter);
    91100      selectionParameter = cloner.Clone(original.selectionParameter);
     101      useRecombinationParameter = cloner.Clone(original.useRecombinationParameter);
    92102    }
    93103    public EvolutionStrategy() {
     
    95105      Parameters.Add(muParameter = new FixedValueParameter<IntValue>("Mu", "(μ) The population size.", new IntValue(1)));
    96106      Parameters.Add(selectionParameter= new FixedValueParameter<EnumValue<ESSelection>>("Selection", "The selection strategy: elitist (plus) or generational (comma).", new EnumValue<ESSelection>(ESSelection.Plus)));
    97      
     107      Parameters.Add(useRecombinationParameter = new FixedValueParameter<BoolValue>("Use Recombination", "Whether to create an \"intermediate\" solution to perform the mutation from.", new BoolValue(false)));
     108
    98109      Problem = new GQAP();
    99110    }
     
    116127        Context.EvaluatedSolutions++;
    117128
    118         var ind = new ESGQAPSolution(assign, eval, Context.Random.NextDouble() * 2 - 1);
     129        var min = (1.0 / assign.Length) * 2 - 1; // desired min prob
     130        var max = (4.0 / assign.Length) * 2 - 1; // desired max prob
     131        min = 0.5 * (Math.Log(1 + min) - Math.Log(1 - min)); // arctanh
     132        max = 0.5 * (Math.Log(1 + max) - Math.Log(1 - max));
     133        var ind = new ESGQAPSolution(assign, eval, min + Context.Random.NextDouble() * (max - min));
    119134        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
    120135        Context.AddToPopulation(Context.ToScope(ind, fit));
     
    135150    protected override void Run(CancellationToken cancellationToken) {
    136151      var lastUpdate = ExecutionTime;
     152      var eq = new IntegerVectorEqualityComparer();
    137153
    138154      while (!StoppingCriterion()) {
     
    140156
    141157        for (var l = 0; l < Lambda; l++) {
    142           var m = Context.AtRandomPopulation();
    143 
    144           var offspring = (ESGQAPSolution)m.Solution.Clone();
    145           var count = Mutate(m, offspring);
    146           offspring.SParam += 0.7071 * Context.NormalRand.NextDouble(); //((1.0 / count) - offspring.SParam) / 10.0;
    147 
    148           offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
     158          IntegerVector child = null;
     159          var sParam = 0.0;
     160          if (UseRecombination) {
     161            child = DiscreteLocationCrossover.Apply(Context.Random, new ItemArray<IntegerVector>(Context.Population.Select(x => x.Solution.Assignment)), Problem.ProblemInstance.Demands, Problem.ProblemInstance.Capacities);
     162            sParam = Context.Population.Select(x => x.Solution.SParam).Average();
     163          } else {
     164            var m = Context.AtRandomPopulation();
     165            child = (IntegerVector)m.Solution.Assignment.Clone();
     166            sParam = m.Solution.SParam;
     167          }
     168          sParam += 0.7071 * Context.NormalRand.NextDouble();
     169          RelocateEquipmentManipluator.Apply(Context.Random, child,
     170            Problem.ProblemInstance.Capacities.Length, (Math.Tanh(sParam) + 1) / 2.0);
     171          var eval = Problem.ProblemInstance.Evaluate(child);
    149172          Context.EvaluatedSolutions++;
     173
     174          var offspring = new ESGQAPSolution(child, eval, sParam);
     175
    150176          var fit = Problem.ProblemInstance.ToSingleObjective(offspring.Evaluation);
    151           nextGen.Add(Context.ToScope(offspring, fit));
     177          if (Selection == ESSelection.Comma || Context.Population.Select(x => x.Solution.Assignment).All(x => !eq.Equals(child, x)))
     178            nextGen.Add(Context.ToScope(offspring, fit));
    152179
    153180          if (fit < Context.BestQuality) {
     
    160187          Context.ReplacePopulation(nextGen.OrderBy(x => x.Fitness).Take(Mu));
    161188        } else if (Selection == ESSelection.Plus) {
    162           var best = nextGen.Concat(Context.Population).OrderBy(x => x.Fitness).Take(Mu).ToList();
     189          var best = Context.Population.Concat(nextGen).OrderBy(x => x.Fitness).Take(Mu).ToList();
    163190          Context.ReplacePopulation(best);
    164191        } else throw new InvalidOperationException("Unknown Selection strategy: " + Selection);
     
    181208        else Results.Add(new Result("BestSolution", Context.BestSolution));
    182209
    183         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     210        try {
     211          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     212        } catch (OperationCanceledException) { }
    184213
    185214        Context.Iterations++;
     
    194223      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    195224    }
    196 
    197     private int Mutate(ISingleObjectiveSolutionScope<ESGQAPSolution> m, ESGQAPSolution offspring) {
    198       var stopProb = (Math.Tanh(m.Solution.SParam) + 1) / 2.0; // squash strategy parameter to ]0;1[
    199       var offspringFeasible = offspring.Evaluation.IsFeasible;
    200       double[] slack = null;
    201       if (offspringFeasible) slack = offspring.Evaluation.Slack.ToArray();
    202       var count = 1;
    203       foreach (var equip in Enumerable.Range(0, Problem.ProblemInstance.Demands.Length).Shuffle(Context.Random)) {
    204         var currentLoc = offspring.Assignment[equip];
    205         if (offspringFeasible) {
    206           var demand = Problem.ProblemInstance.Demands[equip];
    207           var feasibleLoc = slack.Select((v, i) => new { Index = i, Value = v })
    208             .Where(x => x.Index != currentLoc
    209             && x.Value >= demand).ToList();
    210           int newLoc = -1;
    211           if (feasibleLoc.Count == 0) {
    212             newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
    213             if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
    214             offspringFeasible = false;
    215           } else {
    216             newLoc = feasibleLoc.SampleRandom(Context.Random).Index;
    217           }
    218           offspring.Assignment[equip] = newLoc;
    219           slack[currentLoc] += demand;
    220           slack[newLoc] -= demand;
    221         } else {
    222           var newLoc = Context.Random.Next(Problem.ProblemInstance.Capacities.Length - 1);
    223           if (newLoc >= currentLoc) newLoc++; // don't reassign to current loc
    224           offspring.Assignment[equip] = newLoc;
    225         }
    226         if (Context.Random.NextDouble() < stopProb) break;
    227         count++;
    228       }
    229 
    230       return count;
    231     }
    232225  }
    233226}
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Evolutionary/OSGAContext.cs

    r15562 r15564  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Data;
    2526using HeuristicLab.Parameters;
    2627using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2728
    28 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
    29   [Item("GRASP+PR (GQAP) Context", "Context for GRASP+PR (GQAP).")]
     29namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.Evolutionary {
     30  [Item("OSGA (GQAP) Context", "Context for OSGA (GQAP).")]
    3031  [StorableClass]
    31   public sealed class GRASPContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     32  public sealed class OSGAContext : SingleObjectivePopulationContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    3233   
    3334    [Storable]
     
    4445      set { bestSolution.Value = value; }
    4546    }
    46    
     47
     48    [Storable]
     49    private IValueParameter<ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>> nextGeneration;
     50    public ItemList<ISingleObjectiveSolutionScope<GQAPSolution>> NextGeneration {
     51      get { return nextGeneration.Value; }
     52      set { nextGeneration.Value = value; }
     53    }
     54
     55    [Storable]
     56    private IValueParameter<DoubleValue> selectionPressure;
     57    public double SelectionPressure {
     58      get { return selectionPressure.Value.Value; }
     59      set { selectionPressure.Value.Value = value; }
     60    }
     61
     62    [Storable]
     63    private IValueParameter<IntValue> attempts;
     64    public int Attempts {
     65      get { return attempts.Value.Value; }
     66      set { attempts.Value.Value = value; }
     67    }
     68
    4769    public void SortPopulation() {
    4870      Scope.SubScopes.Replace(Scope.SubScopes.OfType<ISingleObjectiveSolutionScope<GQAPSolution>>().OrderBy(x => Problem.Maximization ? -x.Fitness : x.Fitness).ToList());
     
    5072   
    5173    [StorableConstructor]
    52     private GRASPContext(bool deserializing) : base(deserializing) { }
    53     private GRASPContext(GRASPContext original, Cloner cloner)
     74    private OSGAContext(bool deserializing) : base(deserializing) { }
     75    private OSGAContext(OSGAContext original, Cloner cloner)
    5476      : base(original, cloner) {
    5577      problem = cloner.Clone(original.problem);
    5678      bestSolution = cloner.Clone(original.bestSolution);
     79      nextGeneration = cloner.Clone(original.nextGeneration);
     80      selectionPressure = cloner.Clone(original.selectionPressure);
     81      attempts = cloner.Clone(original.attempts);
    5782    }
    58     public GRASPContext() : this("GRASP+PR (GQAP) Context") { }
    59     public GRASPContext(string name) : base(name) {
     83    public OSGAContext() : this("OSGA (GQAP) Context") { }
     84    public OSGAContext(string name) : base(name) {
    6085      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    6186      Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
     87      Parameters.Add(nextGeneration = new ValueParameter<ItemList<ISingleObjectiveSolutionScope<GQAPSolution>>>("NextGeneration"));
     88      Parameters.Add(selectionPressure = new ValueParameter<DoubleValue>("SelectionPressure", new DoubleValue(0)));
     89      Parameters.Add(attempts = new ValueParameter<IntValue>("Attempts", new IntValue(0)));
    6290    }
    6391
    6492    public override IDeepCloneable Clone(Cloner cloner) {
    65       return new GRASPContext(this, cloner);
     93      return new OSGAContext(this, cloner);
    6694    }
    6795
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP/GRASP.cs

    r15563 r15564  
    167167      while (!StoppingCriterion()) { // line 2 in Algorithm 1
    168168        // next: line 3 in Algorithm 1
    169         var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
     169        IntegerVector pi_prime_vec = null;
     170        try {
     171          pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
     172        } catch (OperationCanceledException) { break; }
     173
    170174        if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
    171175          GQAPSolution pi_prime;
     
    234238        else Results.Add(new Result("BestSolution", Context.BestSolution));
    235239
    236         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     240        try {
     241          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     242        } catch (OperationCanceledException) { }
    237243
    238244        Context.Iterations++;
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj

    r15563 r15564  
    102102    <Compile Include="Evolutionary\ESGQAPSolution.cs" />
    103103    <Compile Include="Evolutionary\EvolutionStrategy.cs" />
     104    <Compile Include="Evolutionary\OSGAContext.cs" />
     105    <Compile Include="Evolutionary\OSGA.cs" />
    104106    <Compile Include="Infrastructure\Algorithms\StochasticAlgorithm.cs" />
    105107    <Compile Include="Infrastructure\Contexts\SingleObjectiveSingleSolutionContext.cs" />
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Contexts/PopulationContext.cs

    r15562 r15564  
    4040      Scope.SubScopes[index] = solScope;
    4141    }
     42    public void ReplacePopulation(IEnumerable<TSolutionScope> replacement) {
     43      Scope.SubScopes.Replace(replacement);
     44    }
    4245    public TSolutionScope AtPopulation(int index) {
    4346      return Scope.SubScopes[index] as TSolutionScope;
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHC.cs

    r15563 r15564  
    156156        else Results.Add(new Result("BestSolution", Context.BestSolution));
    157157
    158         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    159        
     158        try {
     159          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     160        } catch (OperationCanceledException) { }
     161
    160162        if (cancellationToken.IsCancellationRequested) break;
    161163      }
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHC.cs

    r15563 r15564  
    187187            result.Value = Context.BestSolution;
    188188          else Results.Add(new Result("BestSolution", Context.BestSolution));
    189           Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     189
     190          try {
     191            Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     192          } catch (OperationCanceledException) { }
    190193
    191194          if (cancellationToken.IsCancellationRequested) break;
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/IteratedLS.cs

    r15563 r15564  
    2525using HeuristicLab.Core;
    2626using HeuristicLab.Data;
    27 using HeuristicLab.Encodings.IntegerVectorEncoding;
    2827using HeuristicLab.Optimization;
     28using HeuristicLab.Parameters;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3030
     
    4848    }
    4949
     50    [Storable]
     51    private IFixedValueParameter<PercentValue> perturbationStrengthParameter;
     52    public IFixedValueParameter<PercentValue> PerturbationStrengthParameter {
     53      get { return perturbationStrengthParameter; }
     54    }
     55
     56    public double PerturbationStrength {
     57      get { return perturbationStrengthParameter.Value.Value; }
     58      set { perturbationStrengthParameter.Value.Value = value; }
     59    }
     60
    5061    [StorableConstructor]
    5162    private IteratedLS(bool deserializing) : base(deserializing) { }
     
    5465    }
    5566    public IteratedLS() {
     67      Parameters.Add(perturbationStrengthParameter = new FixedValueParameter<PercentValue>("PerturbationStrength", "The expected length of the random walk relative to the size of the solution vector.", new PercentValue(0.5)));
    5668
    5769      Problem = new GQAP();
     
    97109        var lsevaluations = 0;
    98110        var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();
    99         RandomWalk(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, candidate.Assignment.Length);
     111        RelocateEquipmentManipluator.Apply(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, 1.0 / (PerturbationStrength * candidate.Assignment.Length));
    100112        candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);
    101113        Context.EvaluatedSolutions++;
     
    127139        else Results.Add(new Result("BestSolution", Context.BestSolution));
    128140
    129         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     141        try {
     142          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     143        } catch (OperationCanceledException) { }
    130144
    131145        Context.Iterations++;
     
    140154      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    141155    }
    142 
    143     private static void RandomWalk(IRandom random, IntegerVector assignment, int locations, int walkLength) {
    144       for (int i = 0; i < walkLength; i++) {
    145         var equipment = random.Next(assignment.Length);
    146         assignment[equipment] = random.Next(locations);
    147         if (random.NextDouble() < 1.0 / walkLength) break;
    148       }
    149     }
    150156  }
    151157}
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/MultistartLS.cs

    r15563 r15564  
    107107        else Results.Add(new Result("BestSolution", Context.BestSolution));
    108108
    109         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     109        try {
     110          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     111        } catch (OperationCanceledException) { }
    110112
    111113        Context.Iterations++;
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/DiscreteLocationCrossover.cs

    r15504 r15564  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    4647    }
    4748
    48     public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, DoubleArray capacities) {
     49    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, DoubleArray demands, DoubleArray capacities) {
     50      var locations = capacities.Length;
     51      var cap = Math.Max(parents[0].Length / locations, 1);
     52      var lookup = new List<int>[parents.Length][];
     53      for (var p = 0; p < parents.Length; p++) {
     54        lookup[p] = new List<int>[locations];
     55        var assign = parents[p];
     56        for (var e = 0; e < parents[p].Length; e++) {
     57          var loc = assign[e];
     58          if (lookup[p][loc] == null) lookup[p][loc] = new List<int>(cap);
     59          lookup[p][loc].Add(e);
     60        }
     61      }
    4962
    50       var groupedLocations = parents
    51               .Select(p => p.Select((value, index) => new { Equipment = index, Location = value })
    52               .GroupBy(x => x.Location)
    53               .ToDictionary(x => x.Key, y => y.AsEnumerable())).ToArray();
    54 
     63      var slack = capacities.ToArray();
    5564      IntegerVector child = new IntegerVector(parents[0].Length);
    56       HashSet<int> remainingEquipment = new HashSet<int>(Enumerable.Range(0, child.Length));
    57       int locations = capacities.Length;
    58       foreach (var i in Enumerable.Range(0, locations).Shuffle(random)) {
     65      var takenEquip = new bool[child.Length];
     66      foreach (var loc in Enumerable.Range(0, locations).Shuffle(random)) {
    5967        int parent = random.Next(parents.Length);
    60         if (!groupedLocations[parent].ContainsKey(i)) {
     68        if (lookup[parent][loc] == null) {
    6169          int tmp = parent;
    6270          do {
    6371            tmp = (tmp + 1) % parents.Length;
    64           } while (tmp != parent && !groupedLocations[tmp].ContainsKey(i));
     72          } while (tmp != parent && lookup[tmp][loc] == null);
    6573          if (parent == tmp) continue;
    6674          else parent = tmp;
    6775        }
    68         foreach (var item in groupedLocations[parent][i]) {
    69           if (remainingEquipment.Contains(item.Equipment)) {
    70             child[item.Equipment] = i;
    71             remainingEquipment.Remove(item.Equipment);
     76        foreach (var equip in lookup[parent][loc]) {
     77          if (!takenEquip[equip]) {
     78            child[equip] = loc;
     79            takenEquip[equip] = true;
     80            slack[loc] -= demands[equip];
    7281          }
    7382        }
    7483      }
    7584
    76       foreach (var equipment in remainingEquipment) {
    77         int parent = random.Next(parents.Length);
    78         child[equipment] = parents[parent][equipment];
     85      var order = Enumerable.Range(0, takenEquip.Length).Shuffle(random); // avoid bias
     86      foreach (var e in order) {
     87        if (takenEquip[e]) continue;
     88        var assigned = false;
     89        // 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];
     93            slack[child[e]] -= demands[e];
     94            assigned = true;
     95            break;
     96          }
     97        }
     98        // try 2: find a random feasible location
     99        if (!assigned) {
     100          var possible = Enumerable.Range(0, locations).Where(x => slack[x] >= demands[e]).ToList();
     101          if (possible.Count > 0) {
     102            var loc = possible.SampleRandom(random);
     103            child[e] = loc;
     104            slack[loc] -= demands[e];
     105            assigned = true;
     106          }
     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        }
    79113      }
    80114
     
    84118    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,
    85119      GQAPInstance problemInstance) {
    86       return Apply(random, parents, problemInstance.Capacities);
     120      return Apply(random, parents, problemInstance.Demands, problemInstance.Capacities);
    87121    }
    88122  }
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Manipulators/RelocateEquipmentManipluator.cs

    r15504 r15564  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Common;
    2625using HeuristicLab.Core;
    27 using HeuristicLab.Data;
    2826using HeuristicLab.Encodings.IntegerVectorEncoding;
    2927using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    4745    }
    4846
    49     public static void Apply(IRandom random, IntegerVector assignment, DoubleArray capacities, DoubleArray demands) {
    50       int locations = capacities.Length;
     47    public static void Apply(IRandom random, IntegerVector assignment, int locations, double stopProb) {
    5148      if (locations < 2) throw new InvalidOperationException("There are not enough locations for relocation operations.");
    5249
    53       Dictionary<int, double> usedCapacities = new Dictionary<int, double>();
    54       Dictionary<int, List<int>> groupedLocations = new Dictionary<int, List<int>>();
    55       for (int i = 0; i < locations; i++) {
    56         usedCapacities[i] = 0.0;
    57         groupedLocations.Add(i, new List<int>());
    58       }
    59       for (int i = 0; i < assignment.Length; i++) {
    60         usedCapacities[assignment[i]] += demands[i];
    61         groupedLocations[assignment[i]].Add(i);
    62       }
    63 
    64       var overbookedLocations = usedCapacities.Where(x => capacities[x.Key] < x.Value);
    65       var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value);
    66       if (!overbookedLocations.Any() || !freeLocations.Any()) { // perform a random relocation
    67         assignment[random.Next(assignment.Length)] = random.Next(locations);
    68         return;
    69       }
    70 
    71       var sourceLocation = overbookedLocations.SampleRandom(random);
    72       int equipmentToRelocate = groupedLocations[sourceLocation.Key].SampleRandom(random);
    73       var bestFreeLocations = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipmentToRelocate]);
    74 
    75       if (bestFreeLocations.Any()) { // a feasible solution will still be feasible, an infeasible solution might become feasible
    76         var selected = bestFreeLocations.SampleRandom(random);
    77         assignment[equipmentToRelocate] = sourceLocation.Key;
    78       } else { // the solution will become infeasible
    79         sourceLocation = freeLocations.SampleRandom(random);
    80         assignment[equipmentToRelocate] = sourceLocation.Key;
     50      var equipments = Enumerable.Range(0, assignment.Length).Shuffle(random);
     51      foreach (var equipment in equipments) {
     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;
     56        if (random.NextDouble() < stopProb) break;
    8157      }
    8258    }
    8359
    8460    protected override void Manipulate(IRandom random, IntegerVector vector, GQAPInstance problemInstance) {
    85       Apply(random, vector, problemInstance.Capacities, problemInstance.Demands);
     61      Apply(random, vector, problemInstance.Capacities.Length, 4.0 / problemInstance.Demands.Length);
    8662    }
    8763  }
Note: See TracChangeset for help on using the changeset viewer.