source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/LAHC.cs @ 15563

Last change on this file since 15563 was 15563, checked in by abeham, 5 years ago

#1614:

  • Added LAHC and pLAHC-s
  • Changed all algorithms to update high frequency results only every second
File size: 7.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using System.Threading;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.IntegerVectorEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
34  [Item("LAHC (GQAP)", "Late-acceptance hill climber for the GQAP.")]
35  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
36  [StorableClass]
37  public sealed class LAHC : StochasticAlgorithm<LAHCContext> {
38
39    public override bool SupportsPause {
40      get { return true; }
41    }
42
43    public override Type ProblemType {
44      get { return typeof(GQAP); }
45    }
46
47    public new GQAP Problem {
48      get { return (GQAP)base.Problem; }
49      set { base.Problem = value; }
50    }
51
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
63    [StorableConstructor]
64    private LAHC(bool deserializing) : base(deserializing) { }
65    private LAHC(LAHC original, Cloner cloner)
66      : base(original, cloner) {
67      memorySizeParameter = cloner.Clone(original.memorySizeParameter);
68    }
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)));
71
72      Problem = new GQAP();
73    }
74   
75    public override IDeepCloneable Clone(Cloner cloner) {
76      return new LAHC(this, cloner);
77    }
78
79    protected override void Initialize(CancellationToken token) {
80      base.Initialize(token);
81
82      Context.Problem = Problem;
83      Context.LastSuccess = 0;
84     
85      var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
86      var eval = Problem.ProblemInstance.Evaluate(assign);
87      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
88      Context.EvaluatedSolutions++;
89
90      var candidate = new GQAPSolution(assign, eval);
91     
92      Context.ReplaceIncumbent(Context.ToScope(candidate, fit));
93      Context.BestQuality = fit;
94      Context.BestSolution = (GQAPSolution)candidate.Clone();
95     
96      Context.Memory = new DoubleArray(Enumerable.Repeat(Context.BestQuality, MemorySize).ToArray());
97
98      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
99      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
100      Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
101      Results.Add(new Result("BestSolution", Context.BestSolution));
102
103      Context.RunOperator(Analyzer, Context.Scope, token);
104    }
105
106    protected override void Run(CancellationToken cancellationToken) {
107      var lastUpdate = ExecutionTime;
108      while (!StoppingCriterion()) {
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];
123
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          }
136        }
137
138        if (Context.Incumbent.Fitness < prevFit)
139          Context.Memory[v] = Context.Incumbent.Fitness;
140
141        IResult result;
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        }
151        if (Results.TryGetValue("BestQuality", out result))
152          ((DoubleValue)result.Value).Value = Context.BestQuality;
153        else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
154        if (Results.TryGetValue("BestSolution", out result))
155          result.Value = Context.BestSolution;
156        else Results.Add(new Result("BestSolution", Context.BestSolution));
157
158        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
159       
160        if (cancellationToken.IsCancellationRequested) break;
161      }
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)));
169    }
170  }
171}
Note: See TracBrowser for help on using the repository browser.