Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.VariableNeighborhoodSearch/3.3/VariableNeighborhoodSearch.cs @ 5809

Last change on this file since 5809 was 5809, checked in by mkommend, 12 years ago

#1418: Reintegrated branch into trunk.

File size: 13.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Algorithms.LocalSearch;
5using HeuristicLab.Analysis;
6using HeuristicLab.Common;
7using HeuristicLab.Core;
8using HeuristicLab.Data;
9using HeuristicLab.Operators;
10using HeuristicLab.Optimization;
11using HeuristicLab.Optimization.Operators;
12using HeuristicLab.Parameters;
13using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
14using HeuristicLab.Random;
15
16namespace HeuristicLab.Algorithms.VariableNeighborhoodSearch {
17  [Item("Variable Neighborhood Search", "A variable neighborhood search algorithm.")]
18  [Creatable("Algorithms")]
19  [StorableClass]
20  public sealed class VariableNeighborhoodSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent {
21    public string Filename { get; set; }
22
23    #region Problem Properties
24    public override Type ProblemType {
25      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
26    }
27    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
28      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
29      set { base.Problem = value; }
30    }
31    #endregion
32
33    #region Parameter Properties
34    private ValueParameter<IntValue> SeedParameter {
35      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
36    }
37    private ValueParameter<BoolValue> SetSeedRandomlyParameter {
38      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
39    }
40    private ValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
41      get { return (ValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
42    }
43    private ValueParameter<IShakingOperator> ShakingParameter {
44      get { return (ValueParameter<IShakingOperator>)Parameters["Shaking"]; }
45    }
46    private ValueParameter<IntValue> MaximumIterationsParameter {
47      get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
48    }
49    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
50      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
51    }
52    private VariableNeighborhoodSearchMainLoop VNSMainLoop {
53      get { return FindMainLoop(SolutionsCreator.Successor); }
54    }
55    #endregion
56
57    #region Properties
58    private RandomCreator RandomCreator {
59      get { return (RandomCreator)OperatorGraph.InitialOperator; }
60    }
61    public MultiAnalyzer Analyzer {
62      get { return AnalyzerParameter.Value; }
63      set { AnalyzerParameter.Value = value; }
64    }
65    private SolutionsCreator SolutionsCreator {
66      get { return (SolutionsCreator)RandomCreator.Successor; }
67    }
68    #endregion
69
70    [Storable]
71    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
72
73    [StorableConstructor]
74    private VariableNeighborhoodSearch(bool deserializing) : base(deserializing) { }
75    [StorableHook(HookType.AfterDeserialization)]
76    private void AfterDeserialization() {
77
78    }
79    private VariableNeighborhoodSearch(VariableNeighborhoodSearch original, Cloner cloner)
80      : base(original, cloner) {
81      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
82      Initialize();
83    }
84    public override IDeepCloneable Clone(Cloner cloner) {
85      return new VariableNeighborhoodSearch(this, cloner);
86    }
87    public VariableNeighborhoodSearch()
88      : base() {
89      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
90      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
91      Parameters.Add(new ValueParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation", new LocalSearchImprovementOperator()));
92      Parameters.Add(new ValueParameter<IShakingOperator>("Shaking", "The shaking operation"));
93      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
94      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
95
96      RandomCreator randomCreator = new RandomCreator();
97      SolutionsCreator solutionsCreator = new SolutionsCreator();
98      VariableCreator variableCreator = new VariableCreator();
99      ResultsCollector resultsCollector = new ResultsCollector();
100      VariableNeighborhoodSearchMainLoop mainLoop = new VariableNeighborhoodSearchMainLoop();
101      OperatorGraph.InitialOperator = randomCreator;
102
103      randomCreator.RandomParameter.ActualName = "Random";
104      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
105      randomCreator.SeedParameter.Value = null;
106      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
107      randomCreator.SetSeedRandomlyParameter.Value = null;
108      randomCreator.Successor = solutionsCreator;
109
110      solutionsCreator.NumberOfSolutions = new IntValue(1);
111      solutionsCreator.Successor = variableCreator;
112
113      variableCreator.Name = "Initialize Evaluated Solutions";
114      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue()));
115      variableCreator.Successor = resultsCollector;
116
117      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
118      resultsCollector.ResultsParameter.ActualName = "Results";
119      resultsCollector.Successor = mainLoop;
120
121      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
122      mainLoop.ShakingParameter.ActualName = ShakingParameter.Name;
123      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
124      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
125      mainLoop.ResultsParameter.ActualName = "Results";
126      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
127      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
128
129      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
130      ParameterizeAnalyzers();
131      UpdateAnalyzers();
132
133      Initialize();
134    }
135
136    public override void Prepare() {
137      if (Problem != null) base.Prepare();
138    }
139
140    private void Initialize() {
141      if (Problem != null) {
142        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
143      }
144      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
145    }
146
147    #region Events
148    protected override void OnProblemChanged() {
149      ParameterizeStochasticOperator(Problem.SolutionCreator);
150      ParameterizeStochasticOperator(Problem.Evaluator);
151      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
152      ParameterizeSolutionsCreator();
153      ParameterizeVNSMainLoop();
154      ParameterizeAnalyzers();
155      ParameterizeIterationBasedOperators();
156      UpdateShakingOperator();
157      UpdateLocalImprovementOperator();
158      UpdateAnalyzers();
159      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
160      base.OnProblemChanged();
161    }
162
163    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
164      ParameterizeStochasticOperator(Problem.SolutionCreator);
165      ParameterizeSolutionsCreator();
166      base.Problem_SolutionCreatorChanged(sender, e);
167    }
168    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
169      ParameterizeStochasticOperator(Problem.Evaluator);
170      ParameterizeSolutionsCreator();
171      ParameterizeVNSMainLoop();
172      ParameterizeAnalyzers();
173      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
174      base.Problem_EvaluatorChanged(sender, e);
175    }
176    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
177      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
178      ParameterizeIterationBasedOperators();
179      UpdateShakingOperator();
180      UpdateLocalImprovementOperator();
181      UpdateAnalyzers();
182      base.Problem_OperatorsChanged(sender, e);
183    }
184
185    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
186      ParameterizeVNSMainLoop();
187      ParameterizeAnalyzers();
188    }
189
190    void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
191      if (LocalImprovementParameter.Value != null)
192        LocalImprovementParameter.Value.OnProblemChanged(Problem);
193    }
194    #endregion
195
196    #region Helpers
197    private void ParameterizeSolutionsCreator() {
198      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
199      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
200    }
201    private void ParameterizeStochasticOperator(IOperator op) {
202      if (op is IStochasticOperator)
203        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
204    }
205    private void ParameterizeVNSMainLoop() {
206      VNSMainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
207      VNSMainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
208      VNSMainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
209    }
210    private void ParameterizeAnalyzers() {
211      qualityAnalyzer.ResultsParameter.ActualName = "Results";
212      if (Problem != null) {
213        qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
214        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
215        qualityAnalyzer.QualityParameter.Depth = 1;
216        qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
217      }
218    }
219    private void ParameterizeIterationBasedOperators() {
220      if (Problem != null) {
221        foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
222          op.IterationsParameter.ActualName = "Iterations";
223          op.MaximumIterationsParameter.ActualName = "MaximumIterations";
224        }
225      }
226    }
227    private void UpdateShakingOperator() {
228      Type manipulatorType = typeof(IManipulator);
229      List<Type> manipulatorInterfaces = new List<Type>();
230
231      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name)) {
232        Type t = mutator.GetType();
233        Type[] interfaces = t.GetInterfaces();
234
235        for (int i = 0; i < interfaces.Length; i++) {
236          if (manipulatorType.IsAssignableFrom(interfaces[i])) {
237            bool assignable = false;
238            for (int j = 0; j < interfaces.Length; j++) {
239              if (i != j && interfaces[i].IsAssignableFrom(interfaces[j])) {
240                assignable = true;
241                break;
242              }
243            }
244
245            if (!assignable)
246              manipulatorInterfaces.Add(interfaces[i]);
247          }
248        }
249      }
250
251      foreach (Type manipulatorInterface in manipulatorInterfaces) {
252        //manipulatorInterface is more specific
253        if (manipulatorType.IsAssignableFrom(manipulatorInterface)) {
254          //and compatible to all other found manipulator types
255          bool compatible = true;
256          foreach (Type manipulatorInterface2 in manipulatorInterfaces) {
257            if (!manipulatorInterface.IsAssignableFrom(manipulatorInterface2)) {
258              compatible = false;
259              break;
260            }
261          }
262
263          if (compatible)
264            manipulatorType = manipulatorInterface;
265        }
266      }
267
268      Type genericType = typeof(ShakingOperator<>).MakeGenericType(manipulatorType);
269      ShakingParameter.Value = (IShakingOperator)Activator.CreateInstance(genericType, new object[] { });
270
271      ShakingParameter.Value.OnProblemChanged(Problem);
272    }
273    private void UpdateLocalImprovementOperator() {
274      LocalImprovementParameter.Value.OnProblemChanged(Problem);
275    }
276    private void UpdateAnalyzers() {
277      Analyzer.Operators.Clear();
278      if (Problem != null) {
279        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
280          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
281            param.Depth = 1;
282          Analyzer.Operators.Add(analyzer);
283        }
284      }
285      Analyzer.Operators.Add(qualityAnalyzer);
286    }
287    private VariableNeighborhoodSearchMainLoop FindMainLoop(IOperator start) {
288      IOperator mainLoop = start;
289      while (mainLoop != null && !(mainLoop is VariableNeighborhoodSearchMainLoop))
290        mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
291      if (mainLoop == null) return null;
292      else return (VariableNeighborhoodSearchMainLoop)mainLoop;
293    }
294    #endregion
295  }
296}
Note: See TracBrowser for help on using the repository browser.