Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchImprovementOperator.cs @ 17883

Last change on this file since 17883 was 17181, checked in by swagner, 5 years ago

#2875: Merged r17180 from trunk to stable

File size: 15.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HEAL.Attic;
33
34namespace HeuristicLab.Algorithms.LocalSearch {
35  /// <summary>
36  /// A local search improvement operator.
37  /// </summary>
38  [Item("LocalSearchImprovementOperator", "A local search improvement operator.")]
39  [StorableType("40424217-DBA8-4787-A38A-2AE7130CB69D")]
40  public sealed class LocalSearchImprovementOperator : SingleSuccessorOperator, ILocalImprovementAlgorithmOperator, IStochasticOperator, ISingleObjectiveOperator {
41    #region IGenericLocalImprovementOperator Properties
42    public Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } }
43    public IProblem Problem {
44      get { return problem; }
45      set {
46        if (problem != value) {
47          if (value != null && !(value is ISingleObjectiveHeuristicOptimizationProblem))
48            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
49          if (problem != null) DeregisterProblemEventHandlers();
50          problem = (ISingleObjectiveHeuristicOptimizationProblem)value;
51          if (problem != null) RegisterProblemEventHandlers();
52          UpdateProblem();
53        }
54      }
55    }
56    #endregion
57
58    [Storable]
59    private ISingleObjectiveHeuristicOptimizationProblem problem;
60    [Storable]
61    private LocalSearchMainLoop loop;
62    [Storable]
63    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
64
65    #region Parameter Properties
66    public IConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
67      get { return (IConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
68    }
69    public IConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
70      get { return (IConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
71    }
72    public IConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
73      get { return (IConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
74    }
75    public IValueLookupParameter<IntValue> SampleSizeParameter {
76      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
77    }
78    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
79      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
80    }
81    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
82      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
83    }
84    public ILookupParameter<IRandom> RandomParameter {
85      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
86    }
87    #region ILocalImprovementOperator Parameters
88    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
89      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
90    }
91    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
92      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
93    }
94    public ILookupParameter<ResultCollection> ResultsParameter {
95      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
96    }
97    #endregion
98    #endregion
99
100    #region Properties
101    public IMoveGenerator MoveGenerator {
102      get { return MoveGeneratorParameter.Value; }
103      set { MoveGeneratorParameter.Value = value; }
104    }
105    public IMoveMaker MoveMaker {
106      get { return MoveMakerParameter.Value; }
107      set { MoveMakerParameter.Value = value; }
108    }
109    public ISingleObjectiveMoveEvaluator MoveEvaluator {
110      get { return MoveEvaluatorParameter.Value; }
111      set { MoveEvaluatorParameter.Value = value; }
112    }
113    public MultiAnalyzer Analyzer {
114      get { return AnalyzerParameter.Value; }
115      set { AnalyzerParameter.Value = value; }
116    }
117    #endregion
118
119    [StorableConstructor]
120    private LocalSearchImprovementOperator(StorableConstructorFlag _) : base(_) { }
121    private LocalSearchImprovementOperator(LocalSearchImprovementOperator original, Cloner cloner)
122      : base(original, cloner) {
123      this.loop = cloner.Clone(original.loop);
124      this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
125      this.problem = cloner.Clone(original.problem);
126      RegisterEventHandlers();
127    }
128    public LocalSearchImprovementOperator()
129      : base() {
130      Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
131      Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
132      Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
133      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
134      Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(300)));
135      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
136      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
137      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
138      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality/fitness value of a solution."));
139      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
140
141      loop = new LocalSearchMainLoop();
142      ((ResultsCollector)((SingleSuccessorOperator)loop.OperatorGraph.InitialOperator).Successor).CollectedValues.Remove(loop.BestLocalQualityParameter.Name);
143      ParameterizeLSMainLoop();
144
145      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
146      Analyzer.Operators.Add(qualityAnalyzer);
147
148      RegisterEventHandlers();
149    }
150
151    public override IDeepCloneable Clone(Cloner cloner) {
152      return new LocalSearchImprovementOperator(this, cloner);
153    }
154
155    [StorableHook(HookType.AfterDeserialization)]
156    private void AfterDeserialization() {
157      RegisterEventHandlers();
158    }
159
160    #region Event Handler Registration
161    private void RegisterEventHandlers() {
162      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
163      if (problem != null)
164        RegisterProblemEventHandlers();
165    }
166
167    private void RegisterProblemEventHandlers() {
168      problem.Reset += new EventHandler(problem_Reset);
169      problem.OperatorsChanged += new EventHandler(problem_OperatorsChanged);
170    }
171
172    private void DeregisterProblemEventHandlers() {
173      problem.Reset -= new EventHandler(problem_Reset);
174      problem.OperatorsChanged -= new EventHandler(problem_OperatorsChanged);
175    }
176    #endregion
177
178    #region Event Handlers
179    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
180      ChooseMoveOperators();
181      ParameterizeLSMainLoop();
182    }
183
184    private void problem_Reset(object sender, EventArgs e) {
185      UpdateProblem();
186    }
187
188    private void problem_OperatorsChanged(object sender, EventArgs e) {
189      UpdateProblem();
190    }
191    #endregion
192
193    #region Parameterize and Update Methods
194    private void UpdateProblem() {
195      UpdateMoveOperators();
196      ChooseMoveOperators();
197
198      ParameterizeMoveGenerators();
199
200      ParameterizeLSMainLoop();
201      ParameterizeAnalyzers();
202      UpdateAnalyzers();
203    }
204
205    private void ParameterizeLSMainLoop() {
206      loop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
207      loop.BestLocalQualityParameter.ActualName = QualityParameter.Name;
208      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.Name;
209      loop.IterationsParameter.ActualName = "LocalIterations";
210      loop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
211      loop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
212      loop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
213      loop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
214      loop.QualityParameter.ActualName = QualityParameter.Name;
215      loop.RandomParameter.ActualName = RandomParameter.Name;
216      loop.ResultsParameter.ActualName = ResultsParameter.Name;
217
218      if (problem != null) {
219        loop.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
220        loop.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
221      }
222      if (MoveEvaluator != null) {
223        loop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
224      }
225    }
226
227    private void ParameterizeAnalyzers() {
228      qualityAnalyzer.ResultsParameter.ActualName = ResultsParameter.Name;
229      if (problem != null) {
230        qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
231        if (MoveEvaluator != null)
232          qualityAnalyzer.QualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
233        qualityAnalyzer.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
234      }
235    }
236
237    private bool IsSubclassOfGeneric(Type generic, Type toCheck) {
238      while (toCheck != typeof(object)) {
239        var cur = toCheck.IsGenericType ? toCheck.GetGenericTypeDefinition() : toCheck;
240        if (generic == cur) {
241          return true;
242        }
243        toCheck = toCheck.BaseType;
244      }
245      return false;
246    }
247
248    private void UpdateAnalyzers() {
249      Analyzer.Operators.Clear();
250      if (problem != null) {
251        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
252          if (!IsSubclassOfGeneric(typeof(AlleleFrequencyAnalyzer<>), analyzer.GetType()) &&
253              !(analyzer is PopulationSimilarityAnalyzer)) {
254            IAnalyzer clone = analyzer.Clone() as IAnalyzer;
255            foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
256              param.Depth = 0;
257            Analyzer.Operators.Add(clone, false);
258          }
259        }
260      }
261      Analyzer.Operators.Add(qualityAnalyzer, false);
262    }
263
264    private void UpdateMoveOperators() {
265      IMoveGenerator oldMoveGenerator = MoveGenerator;
266      IMoveMaker oldMoveMaker = MoveMaker;
267      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
268
269      ClearMoveParameters();
270
271      if (problem != null) {
272        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
273          MoveGeneratorParameter.ValidValues.Add(generator);
274        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
275          MoveGeneratorParameter.ValidValues.Add(generator);
276
277        if (oldMoveGenerator != null) {
278          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
279          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
280        }
281
282        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
283      }
284    }
285
286    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
287      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
288      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
289      MoveMakerParameter.ValidValues.Clear();
290      MoveEvaluatorParameter.ValidValues.Clear();
291
292      if (MoveGenerator != null && Problem != null) {
293        IMoveGenerator generator = MoveGeneratorParameter.Value;
294        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
295          MoveMakerParameter.ValidValues.Add(moveMaker);
296        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
297          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
298
299        if (oldMoveMaker != null) {
300          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
301          if (mm != null) MoveMaker = mm;
302        }
303        if (oldMoveEvaluator != null) {
304          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
305          if (me != null) MoveEvaluator = me;
306        }
307      }
308    }
309
310    private void ClearMoveParameters() {
311      MoveGeneratorParameter.ValidValues.Clear();
312      MoveMakerParameter.ValidValues.Clear();
313      MoveEvaluatorParameter.ValidValues.Clear();
314    }
315
316    private void ParameterizeMoveGenerators() {
317      if (problem != null) {
318        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
319          generator.SampleSizeParameter.ActualName = SampleSizeParameter.Name;
320      }
321    }
322    #endregion
323
324    public override IOperation Apply() {
325      IScope currentScope = ExecutionContext.Scope;
326
327      Scope localScope = new Scope();
328      Scope individual = new Scope();
329
330      foreach (IVariable var in currentScope.Variables)
331        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
332
333      localScope.SubScopes.Add(individual);
334      currentScope.SubScopes.Add(localScope);
335      int index = currentScope.SubScopes.Count - 1;
336
337      SubScopesProcessor processor = new SubScopesProcessor();
338      SubScopesRemover remover = new SubScopesRemover();
339
340      remover.RemoveAllSubScopes = false;
341      remover.SubScopeIndexParameter.Value = new IntValue(index);
342
343      if (index > 0) {
344        EmptyOperator eo = new EmptyOperator();
345        for (int i = 0; i < index - 1; i++) {
346          processor.Operators.Add(eo);
347        }
348      }
349
350      VariableCreator variableCreator = new VariableCreator();
351      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
352      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(loop.BestLocalQualityParameter.ActualName, new DoubleValue(0)));
353
354      variableCreator.Successor = loop;
355
356      processor.Operators.Add(variableCreator);
357      processor.Successor = remover;
358
359      OperationCollection next = new OperationCollection(base.Apply());
360      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
361
362      return next;
363    }
364  }
365}
Note: See TracBrowser for help on using the repository browser.