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

Last change on this file since 15572 was 15572, checked in by abeham, 2 years ago

#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)
File size: 9.6 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.Threading;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
33  [Item("pLAHC-s (GQAP)", "Parameterless Late-acceptance hill climber for the GQAP.")]
34  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
35  [StorableClass]
36  public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext, IntegerVectorEncoding> {
37
38    public override bool SupportsPause {
39      get { return true; }
40    }
41
42    public override Type ProblemType {
43      get { return typeof(GQAP); }
44    }
45
46    public new GQAP Problem {
47      get { return (GQAP)base.Problem; }
48      set { base.Problem = value; }
49    }
50
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
73    [StorableConstructor]
74    private PLAHCS(bool deserializing) : base(deserializing) { }
75    private PLAHCS(PLAHCS original, Cloner cloner)
76      : base(original, cloner) {
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)));
83
84      Problem = new GQAP();
85    }
86   
87    public override IDeepCloneable Clone(Cloner cloner) {
88      return new PLAHCS(this, cloner);
89    }
90
91    protected override void Initialize(CancellationToken token) {
92      base.Initialize(token);
93
94      Context.Problem = Problem;
95      Context.LastSuccess = 0;
96
97      var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
98      var eval = Problem.ProblemInstance.Evaluate(assign);
99      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
100      Context.EvaluatedSolutions++;
101
102      var candidate = new GQAPSolution(assign, eval);
103
104      Context.ReplaceIncumbent(Context.ToScope(candidate, fit));
105      Context.BestQuality = fit;
106      Context.BestSolution = (GQAPSolution)candidate.Clone();
107
108      Context.BestList = new ItemList<DoubleValue>(new[] { new DoubleValue(Context.BestQuality) });
109
110      Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
111      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
112      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
113      Results.Add(new Result("CurrentMemorySize", new IntValue(0)));
114    }
115
116    protected override void Run(CancellationToken cancellationToken) {
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
190          try {
191            Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
192          } catch (OperationCanceledException) { }
193
194          if (cancellationToken.IsCancellationRequested) break;
195        }
196        if (StoppingCriterion() || cancellationToken.IsCancellationRequested) break;
197      }
198
199      IResult result2;
200      if (Results.TryGetValue("Iterations", out result2))
201        ((IntValue)result2.Value).Value = Context.Iterations;
202      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
203      if (Results.TryGetValue("Sprint Iterations", out result2))
204        ((IntValue)result2.Value).Value = Context.SprintIterations;
205      else Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
206      if (Results.TryGetValue("EvaluatedSolutions", out result2))
207        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
208      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
209    }
210  }
211}
Note: See TracBrowser for help on using the repository browser.