Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15563


Ignore:
Timestamp:
12/30/17 23:10:29 (7 years ago)
Author:
abeham
Message:

#1614:

  • Added LAHC and pLAHC-s
  • Changed all algorithms to update high frequency results only every second
Location:
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3
Files:
1 added
8 edited
4 copied

Legend:

Unmodified
Added
Removed

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

    r15562 r15563  
    4545    }
    4646
     47    [Storable]
     48    private IValueParameter<IRandom> normalRand;
     49    public IRandom NormalRand {
     50      get { return normalRand.Value; }
     51      set { normalRand.Value = value; }
     52    }
     53
    4754    public void ReplacePopulation(IEnumerable<ISingleObjectiveSolutionScope<ESGQAPSolution>> replacement) {
    4855      Scope.SubScopes.Replace(replacement);
    … …  
    5562      problem = cloner.Clone(original.problem);
    5663      bestSolution = cloner.Clone(original.bestSolution);
     64      normalRand = cloner.Clone(original.normalRand);
    5765    }
    5866    public ESContext() : this("Evolution Strategy (GQAP) Context") { }
    … …  
    6068      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    6169      Parameters.Add(bestSolution = new ValueParameter<ESGQAPSolution>("BestFoundSolution"));
     70      Parameters.Add(normalRand = new ValueParameter<IRandom>("NormalRand"));
    6271    }
    6372
    … …  
    7483      scope.Variables.Add(new Variable(name, code.Assignment));
    7584      scope.Variables.Add(new Variable("Evaluation", code.Evaluation));
     85      scope.Variables.Add(new Variable("StrategyParameter", code.sParam));
    7686      return scope;
    7787    }

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

    r15562 r15563  
    2121
    2222using HeuristicLab.Common;
     23using HeuristicLab.Data;
    2324using HeuristicLab.Encodings.IntegerVectorEncoding;
    2425using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    2829
    2930    [Storable]
    30     private double sParam;
     31    internal DoubleValue sParam;
    3132    public double SParam {
    32       get { return sParam; }
     33      get { return sParam.Value; }
    3334      set {
    34         if (sParam == value) return;
    35         sParam = value;
     35        if (sParam.Value == value) return;
     36        sParam.Value = value;
    3637        OnPropertyChanged(nameof(SParam));
    3738      }
    … …  
    4243    protected ESGQAPSolution(ESGQAPSolution original, Cloner cloner)
    4344    : base(original, cloner) {
    44       sParam = original.sParam;
     45      sParam = cloner.Clone(original.sParam);
    4546    }
    4647    public ESGQAPSolution(IntegerVector assignment, Evaluation eval, double sParam)
    4748      : base(assignment, eval) {
    48       this.sParam = sParam;
     49      this.sParam = new DoubleValue(sParam);
    4950    }
    5051   

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

    r15562 r15563  
    106106      base.Initialize(cancellationToken);
    107107
     108      Context.NormalRand = new NormalDistributedRandom(Context.Random, 0, 1);
    108109      Context.Problem = Problem;     
    109110      Context.BestQuality = double.NaN;
    110111      Context.BestSolution = null;
    111 
     112     
    112113      for (var m = 0; m < Mu; m++) {
    113114        var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
    … …  
    115116        Context.EvaluatedSolutions++;
    116117
    117         var ind = new ESGQAPSolution(assign, eval, 1.0 / assign.Length);
     118        var ind = new ESGQAPSolution(assign, eval, Context.Random.NextDouble() * 2 - 1);
    118119        var fit = Problem.ProblemInstance.ToSingleObjective(eval);
    119120        Context.AddToPopulation(Context.ToScope(ind, fit));
    … …  
    133134
    134135    protected override void Run(CancellationToken cancellationToken) {
     136      var lastUpdate = ExecutionTime;
     137
    135138      while (!StoppingCriterion()) {
    136139        var nextGen = new List<ISingleObjectiveSolutionScope<ESGQAPSolution>>(Lambda);
    … …  
    141144          var offspring = (ESGQAPSolution)m.Solution.Clone();
    142145          var count = Mutate(m, offspring);
    143           offspring.SParam += ((1.0 / count) - offspring.SParam) / 10.0;
     146          offspring.SParam += 0.7071 * Context.NormalRand.NextDouble(); //((1.0 / count) - offspring.SParam) / 10.0;
    144147
    145148          offspring.Evaluation = Problem.ProblemInstance.Evaluate(offspring.Assignment);
    … …  
    162165
    163166        IResult result;
    164         if (Results.TryGetValue("Iterations", out result))
    165           ((IntValue)result.Value).Value = Context.Iterations;
    166         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    167         if (Results.TryGetValue("EvaluatedSolutions", out result))
    168           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    169         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     167        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     168          if (Results.TryGetValue("Iterations", out result))
     169            ((IntValue)result.Value).Value = Context.Iterations;
     170          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     171          if (Results.TryGetValue("EvaluatedSolutions", out result))
     172            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     173          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     174          lastUpdate = ExecutionTime;
     175        }
    170176        if (Results.TryGetValue("BestQuality", out result))
    171177          ((DoubleValue)result.Value).Value = Context.BestQuality;
    … …  
    180186        if (cancellationToken.IsCancellationRequested) break;
    181187      }
     188      IResult result2;
     189      if (Results.TryGetValue("Iterations", out result2))
     190        ((IntValue)result2.Value).Value = Context.Iterations;
     191      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     192      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     193        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     194      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    182195    }
    183196
    184197    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[
    185199      var offspringFeasible = offspring.Evaluation.IsFeasible;
    186200      double[] slack = null;
    … …  
    210224          offspring.Assignment[equip] = newLoc;
    211225        }
    212         if (Context.Random.NextDouble() < m.Solution.SParam) break;
     226        if (Context.Random.NextDouble() < stopProb) break;
    213227        count++;
    214228      }

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

    r15562 r15563  
    164164    protected override void Run(CancellationToken cancellationToken) {
    165165      var eq = new IntegerVectorEqualityComparer();
     166      var lastUpdate = ExecutionTime;
    166167      while (!StoppingCriterion()) { // line 2 in Algorithm 1
    167168        // next: line 3 in Algorithm 1
    … …  
    217218
    218219        IResult result;
    219         if (Results.TryGetValue("Iterations", out result))
    220           ((IntValue)result.Value).Value = Context.Iterations;
    221         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    222         if (Results.TryGetValue("EvaluatedSolutions", out result))
    223           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    224         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     220        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     221          if (Results.TryGetValue("Iterations", out result))
     222            ((IntValue)result.Value).Value = Context.Iterations;
     223          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     224          if (Results.TryGetValue("EvaluatedSolutions", out result))
     225            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     226          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     227          lastUpdate = ExecutionTime;
     228        }
    225229        if (Results.TryGetValue("BestQuality", out result))
    226230          ((DoubleValue)result.Value).Value = Context.BestQuality;
    … …  
    235239        if (cancellationToken.IsCancellationRequested) break;
    236240      }
     241      IResult result2;
     242      if (Results.TryGetValue("Iterations", out result2))
     243        ((IntValue)result2.Value).Value = Context.Iterations;
     244      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     245      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     246        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     247      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    237248    }
    238249

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

    r15562 r15563  
    110110    <Compile Include="GRASP\GRASPContext.cs" />
    111111    <Compile Include="GRASP\GRASP.cs" />
     112    <Compile Include="LAHC\pLAHCContext.cs" />
     113    <Compile Include="LAHC\pLAHC.cs" />
     114    <Compile Include="LAHC\LAHC.cs" />
     115    <Compile Include="LAHC\LAHCContext.cs" />
    112116    <Compile Include="LocalSearch\LocalSearchContext.cs" />
    113117    <Compile Include="Infrastructure\Interfaces.cs" />
    … …  
    140144    <None Include="HeuristicLab.snk" />
    141145  </ItemGroup>
     146  <ItemGroup />
    142147  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    143148  <PropertyGroup>

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

    r15562 r15563  
    2424using HeuristicLab.Parameters;
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    26 using HeuristicLab.Random;
    2726
    2827namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms {
    … …  
    4342    }
    4443    protected StochasticContext() : base() {
    45       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     44      Parameters.Add(random = new ValueParameter<IRandom>("Random"));
    4645    }
    4746    protected StochasticContext(string name) : base(name) {
    48       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     47      Parameters.Add(random = new ValueParameter<IRandom>("Random"));
    4948    }
    5049    protected StochasticContext(string name, ParameterCollection parameters) : base(name, parameters) {
    51       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     50      Parameters.Add(random = new ValueParameter<IRandom>("Random"));
    5251    }
    5352    protected StochasticContext(string name, string description) : base(name, description) {
    54       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     53      Parameters.Add(random = new ValueParameter<IRandom>("Random"));
    5554    }
    5655    protected StochasticContext(string name, string description, ParameterCollection parameters) : base(name, description, parameters) {
    57       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
     56      Parameters.Add(random = new ValueParameter<IRandom>("Random"));
    5857    }
    5958

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

    r15562 r15563  
    2121
    2222using System;
     23using System.Linq;
    2324using System.Threading;
    2425using HeuristicLab.Common;
    … …  
    2728using HeuristicLab.Encodings.IntegerVectorEncoding;
    2829using HeuristicLab.Optimization;
     30using HeuristicLab.Parameters;
    2931using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3032
    31 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
    32   [Item("Iterated Local Search (GQAP)", "Iterated local search for the GQAP.")]
     33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
     34  [Item("LAHC (GQAP)", "Late-acceptance hill climber for the GQAP.")]
    3335  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3436  [StorableClass]
    35   public sealed class IteratedLS : ContextAlgorithm<LocalSearchContext> {
     37  public sealed class LAHC : StochasticAlgorithm<LAHCContext> {
    3638
    3739    public override bool SupportsPause {
    … …  
    4850    }
    4951
     52    [Storable]
     53    private FixedValueParameter<IntValue> memorySizeParameter;
     54    public IFixedValueParameter<IntValue> MemorySizeParameter {
     55      get { return memorySizeParameter; }
     56    }
     57
     58    public int MemorySize {
     59      get { return memorySizeParameter.Value.Value; }
     60      set { memorySizeParameter.Value.Value = value; }
     61    }
     62
    5063    [StorableConstructor]
    51     private IteratedLS(bool deserializing) : base(deserializing) { }
    52     private IteratedLS(IteratedLS original, Cloner cloner)
     64    private LAHC(bool deserializing) : base(deserializing) { }
     65    private LAHC(LAHC original, Cloner cloner)
    5366      : base(original, cloner) {
     67      memorySizeParameter = cloner.Clone(original.memorySizeParameter);
    5468    }
    55     public IteratedLS() {
     69    public LAHC() {
     70      Parameters.Add(memorySizeParameter = new FixedValueParameter<IntValue>("MemorySize", "The size of the memory, the shorter the more greedy LAHC performs.", new IntValue(100)));
    5671
    5772      Problem = new GQAP();
    … …  
    5974   
    6075    public override IDeepCloneable Clone(Cloner cloner) {
    61       return new IteratedLS(this, cloner);
     76      return new LAHC(this, cloner);
    6277    }
    6378
    … …  
    6681
    6782      Context.Problem = Problem;
    68       Context.BestQuality = double.NaN;
    69       Context.BestSolution = null;
    70 
    71       var assign = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 10, true, token);
     83      Context.LastSuccess = 0;
     84     
     85      var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
    7286      var eval = Problem.ProblemInstance.Evaluate(assign);
    7387      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
    … …  
    7589
    7690      var candidate = new GQAPSolution(assign, eval);
    77       var lsevaluations = 0;
    78       OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
    79       Context.EvaluatedSolutions += lsevaluations;
    80 
     91     
    8192      Context.ReplaceIncumbent(Context.ToScope(candidate, fit));
    8293      Context.BestQuality = fit;
    8394      Context.BestSolution = (GQAPSolution)candidate.Clone();
     95     
     96      Context.Memory = new DoubleArray(Enumerable.Repeat(Context.BestQuality, MemorySize).ToArray());
    8497
    8598      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    … …  
    92105
    93106    protected override void Run(CancellationToken cancellationToken) {
     107      var lastUpdate = ExecutionTime;
    94108      while (!StoppingCriterion()) {
    95         var lsevaluations = 0;
    96         var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();
    97         RandomWalk(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, candidate.Assignment.Length);
    98         candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);
    99         Context.EvaluatedSolutions++;
    100         OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
    101         Context.EvaluatedSolutions += lsevaluations;
     109        var move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(Context.Random,
     110          Context.Incumbent.Solution.Assignment, Problem.ProblemInstance.Capacities);
     111        var moveEval = GQAPNMoveEvaluator.Evaluate(move,
     112          Context.Incumbent.Solution.Assignment,
     113          Context.Incumbent.Solution.Evaluation, Problem.ProblemInstance);
     114        if (Context.Iterations % Problem.ProblemInstance.Demands.Length == 0)
     115          Context.EvaluatedSolutions++;
     116        var nextFit = Problem.ProblemInstance.ToSingleObjective(moveEval);
     117        var nextVec = new IntegerVector(Context.Incumbent.Solution.Assignment);
     118        NMoveMaker.Apply(nextVec, move);
     119       
     120        var v = Context.Iterations % Context.Memory.Length;
     121        Context.Iterations++;
     122        var prevFit = Context.Memory[v];
    102123
    103         var candidateFit = Problem.ProblemInstance.ToSingleObjective(candidate.Evaluation);
    104         if (candidateFit < Context.Incumbent.Fitness) {
    105           Context.ReplaceIncumbent(Context.ToScope(candidate, candidateFit));
    106           Context.BestQuality = candidateFit;
    107           Context.BestSolution = (GQAPSolution)candidate.Clone();
     124        var accept = nextFit <= Context.Incumbent.Fitness
     125                  || nextFit <= prevFit;
     126
     127        if (accept && nextFit < Context.Incumbent.Fitness)
     128          Context.LastSuccess = Context.Iterations;
     129
     130        if (accept) {
     131          Context.ReplaceIncumbent(Context.ToScope(new GQAPSolution(nextVec, moveEval), nextFit));
     132          if (nextFit < Context.BestQuality) {
     133            Context.BestSolution = (GQAPSolution)Context.Incumbent.Solution.Clone();
     134            Context.BestQuality = nextFit;
     135          }
    108136        }
    109137
     138        if (Context.Incumbent.Fitness < prevFit)
     139          Context.Memory[v] = Context.Incumbent.Fitness;
     140
    110141        IResult result;
    111         if (Results.TryGetValue("Iterations", out result))
    112           ((IntValue)result.Value).Value = Context.Iterations;
    113         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    114         if (Results.TryGetValue("EvaluatedSolutions", out result))
    115           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    116         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     142        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     143          if (Results.TryGetValue("Iterations", out result))
     144            ((IntValue)result.Value).Value = Context.Iterations;
     145          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     146          if (Results.TryGetValue("EvaluatedSolutions", out result))
     147            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     148          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     149          lastUpdate = ExecutionTime;
     150        }
    117151        if (Results.TryGetValue("BestQuality", out result))
    118152          ((DoubleValue)result.Value).Value = Context.BestQuality;
    … …  
    123157
    124158        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    125 
    126         Context.Iterations++;
     159       
    127160        if (cancellationToken.IsCancellationRequested) break;
    128161      }
    129     }
    130 
    131     private static void RandomWalk(IRandom random, IntegerVector assignment, int locations, int walkLength) {
    132       for (int i = 0; i < walkLength; i++) {
    133         var equipment = random.Next(assignment.Length);
    134         assignment[equipment] = random.Next(locations);
    135         if (random.NextDouble() < 1.0 / walkLength) break;
    136       }
     162      IResult result2;
     163      if (Results.TryGetValue("Iterations", out result2))
     164        ((IntValue)result2.Value).Value = Context.Iterations;
     165      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     166      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     167        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     168      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    137169    }
    138170  }

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

    r15562 r15563  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Core;
     24using HeuristicLab.Data;
    2425using HeuristicLab.Parameters;
    2526using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2627
    27 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
    28   public sealed class LocalSearchContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     28namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
     29  public sealed class LAHCContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    2930    [Storable]
    3031    private IValueParameter<GQAP> problem;
    … …  
    4041      set { bestSolution.Value = value; }
    4142    }
     43
     44    [Storable]
     45    private IValueParameter<DoubleArray> memory;
     46    public DoubleArray Memory {
     47      get { return memory.Value; }
     48      set { memory.Value = value; }
     49    }
     50
     51    [Storable]
     52    private IValueParameter<IntValue> lastSuccess;
     53    public int LastSuccess {
     54      get { return lastSuccess.Value.Value; }
     55      set { lastSuccess.Value.Value = value; }
     56    }
    4257   
    4358    [StorableConstructor]
    44     private LocalSearchContext(bool deserializing) : base(deserializing) { }
    45     private LocalSearchContext(LocalSearchContext original, Cloner cloner)
     59    private LAHCContext(bool deserializing) : base(deserializing) { }
     60    private LAHCContext(LAHCContext original, Cloner cloner)
    4661    : base(original, cloner) {
    4762      problem = cloner.Clone(original.problem);
    4863      bestSolution = cloner.Clone(original.bestSolution);
     64      memory = cloner.Clone(original.memory);
     65      lastSuccess = cloner.Clone(original.lastSuccess);
    4966    }
    50     public LocalSearchContext() {
     67    public LAHCContext() {
    5168      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    5269      Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
     70      Parameters.Add(memory = new ValueParameter<DoubleArray>("Memory"));
     71      Parameters.Add(lastSuccess = new ValueParameter<IntValue>("LastSuccess"));
    5372    }
    5473
    5574    public override IDeepCloneable Clone(Cloner cloner) {
    56       return new LocalSearchContext(this, cloner);
     75      return new LAHCContext(this, cloner);
    5776    }
    5877

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

    r15562 r15563  
    2727using HeuristicLab.Encodings.IntegerVectorEncoding;
    2828using HeuristicLab.Optimization;
     29using HeuristicLab.Parameters;
    2930using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3031
    31 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
    32   [Item("Iterated Local Search (GQAP)", "Iterated local search for the GQAP.")]
     32namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
     33  [Item("pLAHC-s (GQAP)", "Parameterless Late-acceptance hill climber for the GQAP.")]
    3334  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3435  [StorableClass]
    35   public sealed class IteratedLS : ContextAlgorithm<LocalSearchContext> {
     36  public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext> {
    3637
    3738    public override bool SupportsPause {
    … …  
    4849    }
    4950
     51    [Storable]
     52    private FixedValueParameter<IntValue> maximumExponentParameter;
     53    public IFixedValueParameter<IntValue> MaximumExponentParameter {
     54      get { return maximumExponentParameter; }
     55    }
     56
     57    [Storable]
     58    private FixedValueParameter<IntValue> minimumSprintIterationsParameter;
     59    public IFixedValueParameter<IntValue> MinimumSprintIterationsParameter {
     60      get { return minimumSprintIterationsParameter; }
     61    }
     62
     63    public int MaximumExponent {
     64      get { return maximumExponentParameter.Value.Value; }
     65      set { maximumExponentParameter.Value.Value = value; }
     66    }
     67
     68    public int MinimumSprintIterations {
     69      get { return minimumSprintIterationsParameter.Value.Value; }
     70      set { minimumSprintIterationsParameter.Value.Value = value; }
     71    }
     72
    5073    [StorableConstructor]
    51     private IteratedLS(bool deserializing) : base(deserializing) { }
    52     private IteratedLS(IteratedLS original, Cloner cloner)
     74    private PLAHCS(bool deserializing) : base(deserializing) { }
     75    private PLAHCS(PLAHCS original, Cloner cloner)
    5376      : base(original, cloner) {
    54     }
    55     public IteratedLS() {
     77      maximumExponentParameter = cloner.Clone(original.maximumExponentParameter);
     78      minimumSprintIterationsParameter = cloner.Clone(original.minimumSprintIterationsParameter);
     79    }
     80    public PLAHCS() {
     81      Parameters.Add(maximumExponentParameter = new FixedValueParameter<IntValue>("MaximumExponent", "The maximum power to which memory sizes should be tried (2^x). Do not set higher than 31", new IntValue(24)));
     82      Parameters.Add(minimumSprintIterationsParameter = new FixedValueParameter<IntValue>("MinimumSprintIterations", "The minimum amount of iterations per sprint.", new IntValue(100000)));
    5683
    5784      Problem = new GQAP();
    … …  
    5986   
    6087    public override IDeepCloneable Clone(Cloner cloner) {
    61       return new IteratedLS(this, cloner);
     88      return new PLAHCS(this, cloner);
    6289    }
    6390
    … …  
    6693
    6794      Context.Problem = Problem;
    68       Context.BestQuality = double.NaN;
    69       Context.BestSolution = null;
    70 
    71       var assign = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 10, true, token);
     95      Context.LastSuccess = 0;
     96
     97      var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
    7298      var eval = Problem.ProblemInstance.Evaluate(assign);
    7399      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
    … …  
    75101
    76102      var candidate = new GQAPSolution(assign, eval);
    77       var lsevaluations = 0;
    78       OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
    79       Context.EvaluatedSolutions += lsevaluations;
    80103
    81104      Context.ReplaceIncumbent(Context.ToScope(candidate, fit));
    … …  
    83106      Context.BestSolution = (GQAPSolution)candidate.Clone();
    84107
     108      Context.BestList = new ItemList<DoubleValue>(new[] { new DoubleValue(Context.BestQuality) });
     109
     110      Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
    85111      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    86112      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    87       Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
    88       Results.Add(new Result("BestSolution", Context.BestSolution));
    89 
    90       Context.RunOperator(Analyzer, Context.Scope, token);
     113      Results.Add(new Result("CurrentMemorySize", new IntValue(0)));
    91114    }
    92115
    93116    protected override void Run(CancellationToken cancellationToken) {
    94       while (!StoppingCriterion()) {
    95         var lsevaluations = 0;
    96         var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();
    97         RandomWalk(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, candidate.Assignment.Length);
    98         candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);
    99         Context.EvaluatedSolutions++;
    100         OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
    101         Context.EvaluatedSolutions += lsevaluations;
    102 
    103         var candidateFit = Problem.ProblemInstance.ToSingleObjective(candidate.Evaluation);
    104         if (candidateFit < Context.Incumbent.Fitness) {
    105           Context.ReplaceIncumbent(Context.ToScope(candidate, candidateFit));
    106           Context.BestQuality = candidateFit;
    107           Context.BestSolution = (GQAPSolution)candidate.Clone();
     117      var lastUpdate = ExecutionTime;
     118      for (var i = 0; i <= MaximumExponent; i++) {
     119        var l = (int)Math.Pow(2, i);
     120        var memory = new double[l];
     121        for (var vv = 0; vv < l; vv++)
     122          memory[vv] = Context.BestList[Context.BestList.Count - 1 - (vv % Context.BestList.Count)].Value;
     123        Array.Sort(memory);
     124        Context.Memory = new DoubleArray(memory);
     125        if (i > 0) Context.ReplaceIncumbent(Context.ToScope((GQAPSolution)Context.BestSolution.Clone(), Context.BestQuality));
     126        IResult memorySizeResult;
     127        if (Results.TryGetValue("CurrentMemorySize", out memorySizeResult))
     128          ((IntValue)memorySizeResult.Value).Value = Context.Memory.Length;
     129        else Results.Add(new Result("CurrentMemorySize", new IntValue(Context.Memory.Length)));
     130
     131        Context.SprintIterations = 0;
     132        while (!StoppingCriterion()
     133          && (Context.SprintIterations < MinimumSprintIterations
     134          || (Context.SprintIterations - Context.LastSuccess) < Context.SprintIterations * 0.02)) {
     135
     136          var move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(Context.Random,
     137            Context.Incumbent.Solution.Assignment, Problem.ProblemInstance.Capacities);
     138          var moveEval = GQAPNMoveEvaluator.Evaluate(move,
     139            Context.Incumbent.Solution.Assignment,
     140            Context.Incumbent.Solution.Evaluation, Problem.ProblemInstance);
     141          if (Context.SprintIterations % Problem.ProblemInstance.Demands.Length == 0)
     142            Context.EvaluatedSolutions++;
     143          var nextFit = Problem.ProblemInstance.ToSingleObjective(moveEval);
     144          var nextVec = new IntegerVector(Context.Incumbent.Solution.Assignment);
     145          NMoveMaker.Apply(nextVec, move);
     146
     147          var v = Context.Iterations % Context.Memory.Length;
     148          Context.Iterations++;
     149          Context.SprintIterations++;
     150          var prevFit = Context.Memory[v];
     151
     152          var accept = nextFit <= Context.Incumbent.Fitness
     153                    || nextFit <= prevFit;
     154
     155          if (accept && nextFit < Context.Incumbent.Fitness)
     156            Context.LastSuccess = Context.SprintIterations;
     157
     158          if (accept) {
     159            Context.ReplaceIncumbent(Context.ToScope(new GQAPSolution(nextVec, moveEval), nextFit));
     160            if (nextFit < Context.BestQuality) {
     161              Context.BestSolution = (GQAPSolution)Context.Incumbent.Solution.Clone();
     162              Context.BestQuality = nextFit;
     163              Context.BestList.Add(new DoubleValue(Context.BestQuality));
     164            }
     165          }
     166
     167          if (Context.Incumbent.Fitness < prevFit)
     168            Context.Memory[v] = Context.Incumbent.Fitness;
     169
     170          IResult result;
     171          if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     172            if (Results.TryGetValue("Iterations", out result))
     173              ((IntValue)result.Value).Value = Context.Iterations;
     174            else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     175            if (Results.TryGetValue("Sprint Iterations", out result))
     176              ((IntValue)result.Value).Value = Context.SprintIterations;
     177            else Results.Add(new Result("Total Iterations", new IntValue(Context.SprintIterations)));
     178            if (Results.TryGetValue("EvaluatedSolutions", out result))
     179              ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     180            else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     181            lastUpdate = ExecutionTime;
     182          }
     183          if (Results.TryGetValue("BestQuality", out result))
     184            ((DoubleValue)result.Value).Value = Context.BestQuality;
     185          else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
     186          if (Results.TryGetValue("BestSolution", out result))
     187            result.Value = Context.BestSolution;
     188          else Results.Add(new Result("BestSolution", Context.BestSolution));
     189          Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
     190
     191          if (cancellationToken.IsCancellationRequested) break;
    108192        }
    109 
    110         IResult result;
    111         if (Results.TryGetValue("Iterations", out result))
    112           ((IntValue)result.Value).Value = Context.Iterations;
    113         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    114         if (Results.TryGetValue("EvaluatedSolutions", out result))
    115           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    116         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    117         if (Results.TryGetValue("BestQuality", out result))
    118           ((DoubleValue)result.Value).Value = Context.BestQuality;
    119         else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
    120         if (Results.TryGetValue("BestSolution", out result))
    121           result.Value = Context.BestSolution;
    122         else Results.Add(new Result("BestSolution", Context.BestSolution));
    123 
    124         Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
    125 
    126         Context.Iterations++;
    127         if (cancellationToken.IsCancellationRequested) break;
     193        if (StoppingCriterion() || cancellationToken.IsCancellationRequested) break;
    128194      }
    129     }
    130 
    131     private static void RandomWalk(IRandom random, IntegerVector assignment, int locations, int walkLength) {
    132       for (int i = 0; i < walkLength; i++) {
    133         var equipment = random.Next(assignment.Length);
    134         assignment[equipment] = random.Next(locations);
    135         if (random.NextDouble() < 1.0 / walkLength) break;
    136       }
     195
     196      IResult result2;
     197      if (Results.TryGetValue("Iterations", out result2))
     198        ((IntValue)result2.Value).Value = Context.Iterations;
     199      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     200      if (Results.TryGetValue("Sprint Iterations", out result2))
     201        ((IntValue)result2.Value).Value = Context.SprintIterations;
     202      else Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
     203      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     204        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     205      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    137206    }
    138207  }

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

    r15562 r15563  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Core;
     24using HeuristicLab.Data;
    2425using HeuristicLab.Parameters;
    2526using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2627
    27 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
    28   public sealed class LocalSearchContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
     28namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
     29  public sealed class PLAHCContext : SingleObjectiveSingleSolutionContext<ISingleObjectiveSolutionScope<GQAPSolution>> {
    2930    [Storable]
    3031    private IValueParameter<GQAP> problem;
    … …  
    4041      set { bestSolution.Value = value; }
    4142    }
     43
     44    [Storable]
     45    private IValueParameter<IntValue> sprintIterations;
     46    public int SprintIterations {
     47      get { return sprintIterations.Value.Value; }
     48      set { sprintIterations.Value.Value = value; }
     49    }
     50
     51    [Storable]
     52    private IValueParameter<DoubleArray> memory;
     53    public DoubleArray Memory {
     54      get { return memory.Value; }
     55      set { memory.Value = value; }
     56    }
     57
     58    [Storable]
     59    private IValueParameter<IntValue> lastSuccess;
     60    public int LastSuccess {
     61      get { return lastSuccess.Value.Value; }
     62      set { lastSuccess.Value.Value = value; }
     63    }
     64
     65    [Storable]
     66    private IValueParameter<ItemList<DoubleValue>> bestList;
     67    public ItemList<DoubleValue> BestList {
     68      get { return bestList.Value; }
     69      set { bestList.Value = value; }
     70    }
    4271   
    4372    [StorableConstructor]
    44     private LocalSearchContext(bool deserializing) : base(deserializing) { }
    45     private LocalSearchContext(LocalSearchContext original, Cloner cloner)
     73    private PLAHCContext(bool deserializing) : base(deserializing) { }
     74    private PLAHCContext(PLAHCContext original, Cloner cloner)
    4675    : base(original, cloner) {
    4776      problem = cloner.Clone(original.problem);
    4877      bestSolution = cloner.Clone(original.bestSolution);
     78      sprintIterations = cloner.Clone(original.sprintIterations);
     79      memory = cloner.Clone(original.memory);
     80      lastSuccess = cloner.Clone(original.lastSuccess);
     81      bestList = cloner.Clone(original.bestList);
    4982    }
    50     public LocalSearchContext() {
     83    public PLAHCContext() {
    5184      Parameters.Add(problem = new ValueParameter<GQAP>("Problem"));
    5285      Parameters.Add(bestSolution = new ValueParameter<GQAPSolution>("BestFoundSolution"));
     86      Parameters.Add(sprintIterations = new ValueParameter<IntValue>("SprintIterations"));
     87      Parameters.Add(memory = new ValueParameter<DoubleArray>("Memory"));
     88      Parameters.Add(lastSuccess = new ValueParameter<IntValue>("LastSuccess"));
     89      Parameters.Add(bestList = new ValueParameter<ItemList<DoubleValue>>("BestList"));
    5390    }
    5491
    5592    public override IDeepCloneable Clone(Cloner cloner) {
    56       return new LocalSearchContext(this, cloner);
     93      return new PLAHCContext(this, cloner);
    5794    }
    5895

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

    r15562 r15563  
    3333  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3434  [StorableClass]
    35   public sealed class IteratedLS : ContextAlgorithm<LocalSearchContext> {
     35  public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext> {
    3636
    3737    public override bool SupportsPause {
    … …  
    9292
    9393    protected override void Run(CancellationToken cancellationToken) {
     94      var lastUpdate = ExecutionTime;
     95
    9496      while (!StoppingCriterion()) {
    9597        var lsevaluations = 0;
    … …  
    109111
    110112        IResult result;
    111         if (Results.TryGetValue("Iterations", out result))
    112           ((IntValue)result.Value).Value = Context.Iterations;
    113         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    114         if (Results.TryGetValue("EvaluatedSolutions", out result))
    115           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    116         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     113        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     114          if (Results.TryGetValue("Iterations", out result))
     115            ((IntValue)result.Value).Value = Context.Iterations;
     116          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     117          if (Results.TryGetValue("EvaluatedSolutions", out result))
     118            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     119          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     120          lastUpdate = ExecutionTime;
     121        }
    117122        if (Results.TryGetValue("BestQuality", out result))
    118123          ((DoubleValue)result.Value).Value = Context.BestQuality;
    … …  
    127132        if (cancellationToken.IsCancellationRequested) break;
    128133      }
     134      IResult result2;
     135      if (Results.TryGetValue("Iterations", out result2))
     136        ((IntValue)result2.Value).Value = Context.Iterations;
     137      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     138      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     139        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     140      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    129141    }
    130142

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

    r15562 r15563  
    3333  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
    3434  [StorableClass]
    35   public sealed class MultistartLS : ContextAlgorithm<LocalSearchContext> {
     35  public sealed class MultistartLS : StochasticAlgorithm<LocalSearchContext> {
    3636
    3737    public override bool SupportsPause {
    … …  
    7171
    7272    protected override void Run(CancellationToken cancellationToken) {
     73      var lastUpdate = ExecutionTime;
     74
    7375      while (!StoppingCriterion()) {
    7476        var lsevaluations = 0;
    … …  
    8991
    9092        IResult result;
    91         if (Results.TryGetValue("Iterations", out result))
    92           ((IntValue)result.Value).Value = Context.Iterations;
    93         else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
    94         if (Results.TryGetValue("EvaluatedSolutions", out result))
    95           ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
    96         else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     93        if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
     94          if (Results.TryGetValue("Iterations", out result))
     95            ((IntValue)result.Value).Value = Context.Iterations;
     96          else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     97          if (Results.TryGetValue("EvaluatedSolutions", out result))
     98            ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
     99          else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
     100          lastUpdate = ExecutionTime;
     101        }
    97102        if (Results.TryGetValue("BestQuality", out result))
    98103          ((DoubleValue)result.Value).Value = Context.BestQuality;
    … …  
    107112        if (cancellationToken.IsCancellationRequested) break;
    108113      }
     114
     115      IResult result2;
     116      if (Results.TryGetValue("Iterations", out result2))
     117        ((IntValue)result2.Value).Value = Context.Iterations;
     118      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
     119      if (Results.TryGetValue("EvaluatedSolutions", out result2))
     120        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
     121      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    109122    }
    110123  }
Note: See TracChangeset for help on using the changeset viewer.