Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VNS/HeuristicLab.Algorithms.VariableNeighborhoodSearch/3.3/VariableNeighborhoodSearch.cs @ 5642

Last change on this file since 5642 was 5642, checked in by svonolfe, 13 years ago

Implemented wiring (#1425)

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