Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 16418 was 15584, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers on stable

File size: 15.8 KB
RevLine 
[5622]1#region License Information
2/* HeuristicLab
[15584]3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[5622]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;
[5809]24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
[5622]26using HeuristicLab.Core;
[5809]27using HeuristicLab.Data;
[5622]28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
[6044]30using HeuristicLab.Optimization.Operators;
[5809]31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[5622]33
34namespace HeuristicLab.Algorithms.LocalSearch {
35  /// <summary>
36  /// A local search improvement operator.
37  /// </summary>
[5735]38  [Item("LocalSearchImprovementOperator", "A local search improvement operator.")]
[5622]39  [StorableClass]
[12005]40  public sealed class LocalSearchImprovementOperator : SingleSuccessorOperator, ILocalImprovementAlgorithmOperator, IStochasticOperator, ISingleObjectiveOperator {
[6042]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
[5622]58    [Storable]
[6042]59    private ISingleObjectiveHeuristicOptimizationProblem problem;
60    [Storable]
[5622]61    private LocalSearchMainLoop loop;
[5735]62    [Storable]
63    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
[5809]64
[6042]65    #region Parameter Properties
[8121]66    public IConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
67      get { return (IConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
[5622]68    }
[8121]69    public IConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
70      get { return (IConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
[5622]71    }
[8121]72    public IConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
73      get { return (IConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
[5622]74    }
[6042]75    public IValueLookupParameter<IntValue> SampleSizeParameter {
76      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
[5622]77    }
[5735]78    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
79      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
[5622]80    }
[6042]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
[5622]99
[6042]100    #region Properties
[5622]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    }
[5735]113    public MultiAnalyzer Analyzer {
114      get { return AnalyzerParameter.Value; }
115      set { AnalyzerParameter.Value = value; }
116    }
[6042]117    #endregion
[5622]118
119    [StorableConstructor]
[6042]120    private LocalSearchImprovementOperator(bool deserializing) : base(deserializing) { }
121    private LocalSearchImprovementOperator(LocalSearchImprovementOperator original, Cloner cloner)
[5622]122      : base(original, cloner) {
[5809]123      this.loop = cloner.Clone(original.loop);
124      this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
[6042]125      this.problem = cloner.Clone(original.problem);
126      RegisterEventHandlers();
[5622]127    }
[5735]128    public LocalSearchImprovementOperator()
[5622]129      : base() {
[5809]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."));
[6042]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)));
[5809]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()));
[6042]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."));
[5809]140
[6042]141      loop = new LocalSearchMainLoop();
[6044]142      ((ResultsCollector)((SingleSuccessorOperator)loop.OperatorGraph.InitialOperator).Successor).CollectedValues.Remove(loop.BestLocalQualityParameter.Name);
[6042]143      ParameterizeLSMainLoop();
144
145      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
146      Analyzer.Operators.Add(qualityAnalyzer);
147
148      RegisterEventHandlers();
[5622]149    }
150
[6042]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() {
[5642]162      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
[6042]163      if (problem != null)
164        RegisterProblemEventHandlers();
[5642]165    }
166
[6042]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) {
[5642]180      ChooseMoveOperators();
[6042]181      ParameterizeLSMainLoop();
182    }
[5642]183
[6042]184    private void problem_Reset(object sender, EventArgs e) {
185      UpdateProblem();
186    }
[5735]187
[6042]188    private void problem_OperatorsChanged(object sender, EventArgs e) {
189      UpdateProblem();
[5622]190    }
[6042]191    #endregion
[5622]192
[6042]193    #region Parameterize and Update Methods
194    private void UpdateProblem() {
195      UpdateMoveOperators();
196      ChooseMoveOperators();
197
198      ParameterizeMoveGenerators();
199
200      ParameterizeLSMainLoop();
201      ParameterizeAnalyzers();
[6052]202      UpdateAnalyzers();
[6042]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
[5735]218      if (problem != null) {
[6042]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) {
[5735]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
[6052]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;
[7172]246    }
[6052]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()) &&
[12280]253              !(analyzer is PopulationSimilarityAnalyzer)) {
[6052]254            IAnalyzer clone = analyzer.Clone() as IAnalyzer;
255            foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
256              param.Depth = 0;
[8118]257            Analyzer.Operators.Add(clone, false);
[6052]258          }
259        }
260      }
[8118]261      Analyzer.Operators.Add(qualityAnalyzer, false);
[6052]262    }
263
[6042]264    private void UpdateMoveOperators() {
[5642]265      IMoveGenerator oldMoveGenerator = MoveGenerator;
266      IMoveMaker oldMoveMaker = MoveMaker;
267      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
268
269      ClearMoveParameters();
270
[5622]271      if (problem != null) {
[6042]272        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
[5622]273          MoveGeneratorParameter.ValidValues.Add(generator);
[6042]274        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
275          MoveGeneratorParameter.ValidValues.Add(generator);
[5622]276
[6042]277        if (oldMoveGenerator != null) {
278          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
279          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
280        }
[5622]281
[6042]282        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
[5622]283      }
284    }
285
[6042]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();
[5642]291
[6042]292      if (MoveGenerator != null && Problem != null) {
293        IMoveGenerator generator = MoveGeneratorParameter.Value;
[7999]294        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
[6042]295          MoveMakerParameter.ValidValues.Add(moveMaker);
[7999]296        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
[6042]297          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
[5642]298
299        if (oldMoveMaker != null) {
[6042]300          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
[5642]301          if (mm != null) MoveMaker = mm;
[5809]302        }
[5642]303        if (oldMoveEvaluator != null) {
[6042]304          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
[5642]305          if (me != null) MoveEvaluator = me;
[5809]306        }
[5642]307      }
308    }
309
[5622]310    private void ClearMoveParameters() {
[5642]311      MoveGeneratorParameter.ValidValues.Clear();
312      MoveMakerParameter.ValidValues.Clear();
313      MoveEvaluatorParameter.ValidValues.Clear();
[5622]314    }
315
[6042]316    private void ParameterizeMoveGenerators() {
[5642]317      if (problem != null) {
318        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
319          generator.SampleSizeParameter.ActualName = SampleSizeParameter.Name;
320      }
321    }
[6042]322    #endregion
[5642]323
[5622]324    public override IOperation Apply() {
[6042]325      IScope currentScope = ExecutionContext.Scope;
326
327      Scope localScope = new Scope();
[5622]328      Scope individual = new Scope();
329
[6042]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)
[5622]332
[6042]333      localScope.SubScopes.Add(individual);
334      currentScope.SubScopes.Add(localScope);
335      int index = currentScope.SubScopes.Count - 1;
[5622]336
337      SubScopesProcessor processor = new SubScopesProcessor();
338      SubScopesRemover remover = new SubScopesRemover();
339
340      remover.RemoveAllSubScopes = false;
341      remover.SubScopeIndexParameter.Value = new IntValue(index);
342
[6042]343      if (index > 0) {
344        EmptyOperator eo = new EmptyOperator();
345        for (int i = 0; i < index - 1; i++) {
346          processor.Operators.Add(eo);
347        }
[5622]348      }
349
[5751]350      VariableCreator variableCreator = new VariableCreator();
[6042]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)));
[5751]353
354      variableCreator.Successor = loop;
355
356      processor.Operators.Add(variableCreator);
[5622]357      processor.Successor = remover;
358
[6042]359      OperationCollection next = new OperationCollection(base.Apply());
360      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
[5622]361
[6042]362      return next;
[5622]363    }
364  }
365}
Note: See TracBrowser for help on using the repository browser.