Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.OneMax/3.3/OnemaxProblem.cs @ 6042

Last change on this file since 6042 was 6042, checked in by abeham, 13 years ago

#1425

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options
File size: 11.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34
35namespace HeuristicLab.Problems.OneMax {
36  [Item("OneMax Problem", "Represents a OneMax Problem.")]
37  [Creatable("Problems")]
38  [StorableClass]
39  public sealed class OneMaxProblem : ParameterizedNamedItem, ISingleObjectiveHeuristicOptimizationProblem, IStorableContent {
40    public string Filename { get; set; }
41
42    public override Image ItemImage {
43      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
44    }
45
46    #region Parameter Properties
47    public ValueParameter<BoolValue> MaximizationParameter {
48      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
49    }
50    IParameter ISingleObjectiveHeuristicOptimizationProblem.MaximizationParameter {
51      get { return MaximizationParameter; }
52    }
53    public ValueParameter<IntValue> LengthParameter {
54      get { return (ValueParameter<IntValue>)Parameters["Length"]; }
55    }
56    public ValueParameter<IBinaryVectorCreator> SolutionCreatorParameter {
57      get { return (ValueParameter<IBinaryVectorCreator>)Parameters["SolutionCreator"]; }
58    }
59    IParameter IHeuristicOptimizationProblem.SolutionCreatorParameter {
60      get { return SolutionCreatorParameter; }
61    }
62    public ValueParameter<IOneMaxEvaluator> EvaluatorParameter {
63      get { return (ValueParameter<IOneMaxEvaluator>)Parameters["Evaluator"]; }
64    }
65    IParameter IHeuristicOptimizationProblem.EvaluatorParameter {
66      get { return EvaluatorParameter; }
67    }
68    public ValueParameter<DoubleValue> BestKnownQualityParameter {
69      get { return (ValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
70    }
71    IParameter ISingleObjectiveHeuristicOptimizationProblem.BestKnownQualityParameter {
72      get { return BestKnownQualityParameter; }
73    }
74    #endregion
75
76    #region Properties
77    public IntValue Length {
78      get { return LengthParameter.Value; }
79      set { LengthParameter.Value = value; }
80    }
81    public IBinaryVectorCreator SolutionCreator {
82      get { return SolutionCreatorParameter.Value; }
83      set { SolutionCreatorParameter.Value = value; }
84    }
85    ISolutionCreator IHeuristicOptimizationProblem.SolutionCreator {
86      get { return SolutionCreatorParameter.Value; }
87    }
88    public IOneMaxEvaluator Evaluator {
89      get { return EvaluatorParameter.Value; }
90      set { EvaluatorParameter.Value = value; }
91    }
92    ISingleObjectiveEvaluator ISingleObjectiveHeuristicOptimizationProblem.Evaluator {
93      get { return EvaluatorParameter.Value; }
94    }
95    IEvaluator IHeuristicOptimizationProblem.Evaluator {
96      get { return EvaluatorParameter.Value; }
97    }
98    public DoubleValue BestKnownQuality {
99      get { return BestKnownQualityParameter.Value; }
100    }
101    public IEnumerable<IOperator> Operators {
102      get { return operators.Cast<IOperator>(); }
103    }
104    private BestOneMaxSolutionAnalyzer BestOneMaxSolutionAnalyzer {
105      get { return operators.OfType<BestOneMaxSolutionAnalyzer>().FirstOrDefault(); }
106    }
107    #endregion
108
109    [Storable]
110    private List<IOperator> operators;
111
112    [StorableConstructor]
113    private OneMaxProblem(bool deserializing) : base(deserializing) { }
114    private OneMaxProblem(OneMaxProblem original, Cloner cloner)
115      : base(original, cloner) {
116      operators = original.operators.Select(x => (IOperator)cloner.Clone(x)).ToList();
117      AttachEventHandlers();
118    }
119    public OneMaxProblem()
120      : base() {
121      RandomBinaryVectorCreator creator = new RandomBinaryVectorCreator();
122      OneMaxEvaluator evaluator = new OneMaxEvaluator();
123
124      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to true as the OneMax Problem is a maximization problem.", new BoolValue(true)));
125      Parameters.Add(new ValueParameter<IntValue>("Length", "The length of the BinaryVector.", new IntValue(5)));
126      Parameters.Add(new ValueParameter<IBinaryVectorCreator>("SolutionCreator", "The operator which should be used to create new OneMax solutions.", creator));
127      Parameters.Add(new ValueParameter<IOneMaxEvaluator>("Evaluator", "The operator which should be used to evaluate OneMax solutions.", evaluator));
128      Parameters.Add(new ValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this OneMax instance.", new DoubleValue(5)));
129
130      creator.BinaryVectorParameter.ActualName = "OneMaxSolution";
131      evaluator.QualityParameter.ActualName = "NumberOfOnes";
132      ParameterizeSolutionCreator();
133      ParameterizeEvaluator();
134
135      InitializeOperators();
136      AttachEventHandlers();
137    }
138
139    public override IDeepCloneable Clone(Cloner cloner) {
140      return new OneMaxProblem(this, cloner);
141    }
142
143    #region Events
144    public event EventHandler SolutionCreatorChanged;
145    private void OnSolutionCreatorChanged() {
146      EventHandler handler = SolutionCreatorChanged;
147      if (handler != null) handler(this, EventArgs.Empty);
148    }
149    public event EventHandler EvaluatorChanged;
150    private void OnEvaluatorChanged() {
151      EventHandler handler = EvaluatorChanged;
152      if (handler != null) handler(this, EventArgs.Empty);
153    }
154    public event EventHandler OperatorsChanged;
155    private void OnOperatorsChanged() {
156      EventHandler handler = OperatorsChanged;
157      if (handler != null) handler(this, EventArgs.Empty);
158    }
159    public event EventHandler Reset;
160    private void OnReset() {
161      EventHandler handler = Reset;
162      if (handler != null) handler(this, EventArgs.Empty);
163    }
164
165    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
166      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
167      ParameterizeSolutionCreator();
168      ParameterizeEvaluator();
169      ParameterizeAnalyzer();
170      ParameterizeOperators();
171      OnSolutionCreatorChanged();
172    }
173    private void SolutionCreator_BinaryVectorParameter_ActualNameChanged(object sender, EventArgs e) {
174      ParameterizeEvaluator();
175      ParameterizeAnalyzer();
176      ParameterizeOperators();
177    }
178    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
179      ParameterizeEvaluator();
180      ParameterizeAnalyzer();
181      OnEvaluatorChanged();
182    }
183    void LengthParameter_ValueChanged(object sender, EventArgs e) {
184      ParameterizeSolutionCreator();
185      LengthParameter.Value.ValueChanged += new EventHandler(Length_ValueChanged);
186      BestKnownQualityParameter.Value.Value = Length.Value;
187    }
188    void Length_ValueChanged(object sender, EventArgs e) {
189      BestKnownQualityParameter.Value.Value = Length.Value;
190    }
191    void BestKnownQualityParameter_ValueChanged(object sender, EventArgs e) {
192      BestKnownQualityParameter.Value.Value = Length.Value;
193    }
194    void OneBitflipMoveParameter_ActualNameChanged(object sender, EventArgs e) {
195      string name = ((ILookupParameter<OneBitflipMove>)sender).ActualName;
196      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
197        op.OneBitflipMoveParameter.ActualName = name;
198      }
199    }
200    #endregion
201
202    #region Helpers
203    [StorableHook(HookType.AfterDeserialization)]
204    private void AfterDeserialization() {
205      // BackwardsCompatibility3.3
206      #region Backwards compatible code (remove with 3.4)
207      if (operators == null) InitializeOperators();
208      #endregion
209      AttachEventHandlers();
210    }
211
212    private void AttachEventHandlers() {
213      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
214      SolutionCreator.BinaryVectorParameter.ActualNameChanged += new EventHandler(SolutionCreator_BinaryVectorParameter_ActualNameChanged);
215      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
216      LengthParameter.ValueChanged += new EventHandler(LengthParameter_ValueChanged);
217      LengthParameter.Value.ValueChanged += new EventHandler(Length_ValueChanged);
218      BestKnownQualityParameter.ValueChanged += new EventHandler(BestKnownQualityParameter_ValueChanged);
219    }
220
221    private void ParameterizeSolutionCreator() {
222      SolutionCreator.LengthParameter.ActualName = LengthParameter.Name;
223    }
224    private void ParameterizeEvaluator() {
225      if (Evaluator is OneMaxEvaluator)
226        ((OneMaxEvaluator)Evaluator).BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
227    }
228    private void ParameterizeAnalyzer() {
229      BestOneMaxSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
230      BestOneMaxSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
231      BestOneMaxSolutionAnalyzer.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
232      BestOneMaxSolutionAnalyzer.ResultsParameter.ActualName = "Results";
233    }
234    private void InitializeOperators() {
235      operators = new List<IOperator>();
236      operators.Add(new BestOneMaxSolutionAnalyzer());
237      ParameterizeAnalyzer();
238      foreach (IBinaryVectorOperator op in ApplicationManager.Manager.GetInstances<IBinaryVectorOperator>()) {
239        if (!(op is ISingleObjectiveMoveEvaluator) || (op is IOneMaxMoveEvaluator)) {
240          operators.Add(op);
241        }
242      }
243      ParameterizeOperators();
244      InitializeMoveGenerators();
245    }
246    private void InitializeMoveGenerators() {
247      foreach (IOneBitflipMoveOperator op in Operators.OfType<IOneBitflipMoveOperator>()) {
248        if (op is IMoveGenerator) {
249          op.OneBitflipMoveParameter.ActualNameChanged += new EventHandler(OneBitflipMoveParameter_ActualNameChanged);
250        }
251      }
252    }
253    private void ParameterizeOperators() {
254      foreach (IBinaryVectorCrossover op in Operators.OfType<IBinaryVectorCrossover>()) {
255        op.ParentsParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
256        op.ChildParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
257      }
258      foreach (IBinaryVectorManipulator op in Operators.OfType<IBinaryVectorManipulator>()) {
259        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
260      }
261      foreach (IBinaryVectorMoveOperator op in Operators.OfType<IBinaryVectorMoveOperator>()) {
262        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
263      }
264      foreach (var op in Operators.OfType<IBinaryVectorMultiNeighborhoodShakingOperator>())
265        op.BinaryVectorParameter.ActualName = SolutionCreator.BinaryVectorParameter.ActualName;
266    }
267    #endregion
268  }
269}
Note: See TracBrowser for help on using the repository browser.