Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VNS/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimization.cs @ 5608

Last change on this file since 5608 was 5581, checked in by mkofler, 14 years ago

#852: PSO code refactoring. Fixed wiring in main loop (Analyzer was not in loop) and fixed small issue in RealVectorSwarmUpdater.

File size: 19.6 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.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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
37  [Item("Particle Swarm Optimization", "A particle swarm optimization algorithm based on the description in Pedersen, M.E.H. (2010). PhD thesis. University of Southampton.")]
38  [Creatable("Algorithms")]
39  [StorableClass]
40  public sealed class ParticleSwarmOptimization : EngineAlgorithm, IStorableContent {
41
42    #region Problem Properties
43    public override Type ProblemType {
44      get { return typeof(ISingleObjectiveProblem); }
45    }
46    public new ISingleObjectiveProblem Problem {
47      get { return (ISingleObjectiveProblem)base.Problem; }
48      set { base.Problem = value; }
49    }
50    public MultiAnalyzer Analyzer {
51      get { return AnalyzerParameter.Value; }
52      set { AnalyzerParameter.Value = value; }
53    }
54    public IDiscreteDoubleValueModifier InertiaUpdater {
55      get { return InertiaUpdaterParameter.Value; }
56      set { InertiaUpdaterParameter.Value = value; }
57    }
58    #endregion
59
60    #region Parameter Properties
61    public IValueParameter<IntValue> SeedParameter {
62      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
63    }
64    public IValueParameter<BoolValue> SetSeedRandomlyParameter {
65      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
66    }
67    public IValueParameter<IntValue> SwarmSizeParameter {
68      get { return (IValueParameter<IntValue>)Parameters["SwarmSize"]; }
69    }
70    public IValueParameter<IntValue> MaxIterationsParameter {
71      get { return (IValueParameter<IntValue>)Parameters["MaxIterations"]; }
72    }
73    public IValueParameter<DoubleValue> InertiaParameter {
74      get { return (IValueParameter<DoubleValue>)Parameters["Inertia"]; }
75    }
76    public IValueParameter<DoubleValue> PersonalBestAttractionParameter {
77      get { return (IValueParameter<DoubleValue>)Parameters["PersonalBestAttraction"]; }
78    }
79    public IValueParameter<DoubleValue> NeighborBestAttractionParameter {
80      get { return (IValueParameter<DoubleValue>)Parameters["NeighborBestAttraction"]; }
81    }
82    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
83      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
84    }
85    public ConstrainedValueParameter<IParticleCreator> ParticleCreatorParameter {
86      get { return (ConstrainedValueParameter<IParticleCreator>)Parameters["ParticleCreator"]; }
87    }
88    public ConstrainedValueParameter<IParticleUpdater> ParticleUpdaterParameter {
89      get { return (ConstrainedValueParameter<IParticleUpdater>)Parameters["ParticleUpdater"]; }
90    }
91    public OptionalConstrainedValueParameter<ITopologyInitializer> TopologyInitializerParameter {
92      get { return (OptionalConstrainedValueParameter<ITopologyInitializer>)Parameters["TopologyInitializer"]; }
93    }
94    public OptionalConstrainedValueParameter<ITopologyUpdater> TopologyUpdaterParameter {
95      get { return (OptionalConstrainedValueParameter<ITopologyUpdater>)Parameters["TopologyUpdater"]; }
96    }
97    public OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier> InertiaUpdaterParameter {
98      get { return (OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["InertiaUpdater"]; }
99    }
100    public ConstrainedValueParameter<ISwarmUpdater> SwarmUpdaterParameter {
101      get { return (ConstrainedValueParameter<ISwarmUpdater>)Parameters["SwarmUpdater"]; }
102
103    }
104    #endregion
105
106    #region Properties
107
108    public string Filename { get; set; }
109
110    [Storable]
111    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
112
113    [Storable]
114    private SolutionsCreator solutionsCreator;
115
116    [Storable]
117    private ParticleSwarmOptimizationMainLoop mainLoop;
118
119    public ITopologyInitializer TopologyInitializer {
120      get { return TopologyInitializerParameter.Value; }
121      set { TopologyInitializerParameter.Value = value; }
122    }
123
124    public ITopologyUpdater TopologyUpdater {
125      get { return TopologyUpdaterParameter.Value; }
126      set { TopologyUpdaterParameter.Value = value; }
127    }
128
129    public IParticleCreator ParticleCreator {
130      get { return ParticleCreatorParameter.Value; }
131      set { ParticleCreatorParameter.Value = value; }
132    }
133
134    public IParticleUpdater ParticleUpdater {
135      get { return ParticleUpdaterParameter.Value; }
136      set { ParticleUpdaterParameter.Value = value; }
137    }
138    #endregion
139
140    [StorableConstructor]
141    private ParticleSwarmOptimization(bool deserializing) : base(deserializing) { }
142    private ParticleSwarmOptimization(ParticleSwarmOptimization original, Cloner cloner)
143      : base(original, cloner) {
144      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
145      solutionsCreator = cloner.Clone(original.solutionsCreator);
146      mainLoop = cloner.Clone(original.mainLoop);
147      Initialize();
148    }
149    public ParticleSwarmOptimization()
150      : base() {
151      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
152      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
153      Parameters.Add(new ValueParameter<IntValue>("SwarmSize", "Size of the particle swarm.", new IntValue(10)));
154      Parameters.Add(new ValueParameter<IntValue>("MaxIterations", "Maximal number of iterations.", new IntValue(1000)));
155      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
156      Parameters.Add(new ValueParameter<DoubleValue>("Inertia", "Inertia weight on a particle's movement (omega).", new DoubleValue(-0.2)));
157      Parameters.Add(new ValueParameter<DoubleValue>("PersonalBestAttraction", "Weight for particle's pull towards its personal best soution (phi_p).", new DoubleValue(-0.01)));
158      Parameters.Add(new ValueParameter<DoubleValue>("NeighborBestAttraction", "Weight for pull towards the neighborhood best solution or global best solution in case of a totally connected topology (phi_g).", new DoubleValue(3.7)));
159      Parameters.Add(new ConstrainedValueParameter<IParticleCreator>("ParticleCreator", "Operator creates a new particle."));
160      Parameters.Add(new ConstrainedValueParameter<IParticleUpdater>("ParticleUpdater", "Operator that updates a particle."));
161      Parameters.Add(new OptionalConstrainedValueParameter<ITopologyInitializer>("TopologyInitializer", "Creates neighborhood description vectors."));
162      Parameters.Add(new OptionalConstrainedValueParameter<ITopologyUpdater>("TopologyUpdater", "Updates the neighborhood description vectors."));
163      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("InertiaUpdater", "Updates the omega parameter."));
164      Parameters.Add(new ConstrainedValueParameter<ISwarmUpdater>("SwarmUpdater", "Encoding-specific parameter which is provided by the problem. May provide additional encoding-specific parameters, such as velocity bounds for real valued problems"));
165
166      RandomCreator randomCreator = new RandomCreator();
167      VariableCreator variableCreator = new VariableCreator();
168      solutionsCreator = new SolutionsCreator();
169      Placeholder topologyInitializerPlaceholder = new Placeholder();
170      Placeholder analyzerPlaceholder = new Placeholder();
171      mainLoop = new ParticleSwarmOptimizationMainLoop();
172
173      OperatorGraph.InitialOperator = randomCreator;
174
175      randomCreator.SetSeedRandomlyParameter.Value = null;
176      randomCreator.SeedParameter.Value = null;
177      randomCreator.Successor = variableCreator;
178
179      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("CurrentIteration", new IntValue(0)));
180      variableCreator.Successor = solutionsCreator;
181
182      solutionsCreator.NumberOfSolutionsParameter.ActualName = "SwarmSize";
183      ParameterizeSolutionsCreator();
184      solutionsCreator.Successor = topologyInitializerPlaceholder;
185
186      topologyInitializerPlaceholder.Name = "(TopologyInitializer)";
187      topologyInitializerPlaceholder.OperatorParameter.ActualName = "TopologyInitializer";
188      topologyInitializerPlaceholder.Successor = mainLoop;
189
190      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
191      mainLoop.InertiaParameter.ActualName = InertiaParameter.Name;
192      mainLoop.MaxIterationsParameter.ActualName = MaxIterationsParameter.Name;
193      mainLoop.NeighborBestAttractionParameter.ActualName = NeighborBestAttractionParameter.Name;
194      mainLoop.InertiaUpdaterParameter.ActualName = InertiaUpdaterParameter.Name;
195      mainLoop.ParticleUpdaterParameter.ActualName = ParticleUpdaterParameter.Name;
196      mainLoop.PersonalBestAttractionParameter.ActualName = PersonalBestAttractionParameter.Name;
197      mainLoop.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName;
198      mainLoop.SwarmSizeParameter.ActualName = SwarmSizeParameter.Name;
199      mainLoop.TopologyUpdaterParameter.ActualName = TopologyUpdaterParameter.Name;
200      mainLoop.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName;
201      mainLoop.ResultsParameter.ActualName = "Results";
202      // mainLoop.EvaluatedMovesParameter.ActualName = "EvaluatedMoves";
203
204      InitializeAnalyzers();
205      ////InitVelocityBoundsUpdater();
206      InitializeParticleCreator();
207      InitializeSwarmUpdater();
208      ParameterizeSolutionsCreator();
209      UpdateAnalyzers();
210      UpdateInertiaUpdater();
211      InitInertiaUpdater();
212      UpdateTopologyInitializer();
213      Initialize();
214      ParameterizeMainLoop();
215    }
216
217    public override IDeepCloneable Clone(Cloner cloner) {
218      return new ParticleSwarmOptimization(this, cloner);
219    }
220
221    [StorableHook(HookType.AfterDeserialization)]
222    private void AfterDeserialization() {
223      Initialize();
224    }
225
226    public override void Prepare() {
227      if (Problem != null && ParticleCreator != null && ParticleUpdater != null) {
228        base.Prepare();
229        if (InertiaUpdater != null && InertiaUpdater.StartValueParameter.Value != null) {
230          this.InertiaParameter.ActualValue = new DoubleValue(InertiaUpdaterParameter.Value.StartValueParameter.Value.Value);
231        }
232        //if (VelocityBoundsUpdater != null && VelocityBoundsUpdater.StartValueParameter.Value != null && VelocityBoundsParameter.Value != null) {
233        //  DoubleMatrix matrix = VelocityBoundsParameter.Value;
234        //  for (int i = 0; i < matrix.Rows; i++) {
235        //    matrix[i, 0] = -VelocityBoundsUpdater.StartValueParameter.Value.Value;
236        //    matrix[i, 1] = VelocityBoundsUpdater.StartValueParameter.Value.Value;
237        //  }
238        //}
239      }
240    }
241
242    #region Events
243    protected override void OnProblemChanged() {
244      UpdateAnalyzers();
245      ParameterizeAnalyzers();
246      UpdateTopologyParameters();
247      InitializeParticleCreator();
248      InitializeSwarmUpdater();
249      ParameterizeSolutionsCreator();
250      base.OnProblemChanged();
251    }
252
253    void TopologyInitializerParameter_ValueChanged(object sender, EventArgs e) {
254      this.UpdateTopologyParameters();
255    }
256
257    //void VelocityBoundsUpdaterParameter_ValueChanged(object sender, EventArgs e) {
258    //  if (VelocityBoundsParameter.Value != null) {
259    //    foreach (IDiscreteDoubleMatrixModifier matrixOp in VelocityBoundsUpdaterParameter.Value.ScalingOperatorParameter.ValidValues) {
260    //      matrixOp.ValueParameter.ActualName = VelocityBoundsUpdater.ScaleParameter.Name;
261    //      matrixOp.StartValueParameter.Value = new DoubleValue(VelocityBoundsUpdater.ScaleParameter.ActualValue.Value);
262    //    }
263    //  }
264    //}
265    #endregion
266
267    #region Helpers
268    private void Initialize() {
269      TopologyInitializerParameter.ValueChanged += new EventHandler(TopologyInitializerParameter_ValueChanged);
270    }
271
272    private void InitializeParticleCreator() {
273      if (Problem != null) {
274        IParticleCreator oldParticleCreator = ParticleCreator;
275        ParticleCreatorParameter.ValidValues.Clear();
276        foreach (IParticleCreator Creator in Problem.Operators.OfType<IParticleCreator>().OrderBy(x => x.Name)) {
277          ParticleCreatorParameter.ValidValues.Add(Creator);
278        }
279        if (oldParticleCreator != null) {
280          IParticleCreator creator = ParticleCreatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleCreator.GetType());
281          if (creator != null) ParticleCreator = creator;
282        }
283      }
284    }
285
286    private void InitializeAnalyzers() {
287      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
288      qualityAnalyzer.ResultsParameter.ActualName = "Results";
289      ParameterizeAnalyzers();
290    }
291
292    private void ParameterizeAnalyzers() {
293      if (Problem != null) {
294        qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
295        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
296        qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
297      }
298    }
299
300    private void UpdateAnalyzers() {
301      Analyzer.Operators.Clear();
302      if (Problem != null) {
303        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>())
304          Analyzer.Operators.Add(analyzer);
305      }
306      Analyzer.Operators.Add(qualityAnalyzer);
307    }
308
309    //private void InitVelocityBoundsUpdater() {
310    //  foreach (IDiscreteDoubleMatrixModifier matrixOp in ApplicationManager.Manager.GetInstances<IDiscreteDoubleMatrixModifier>()) {
311    //    VelocityBoundsUpdaterParameter.ValidValues.Add(matrixOp);
312    //    matrixOp.ValueParameter.ActualName = VelocityBoundsParameter.Name;
313    //    matrixOp.EndIndexParameter.ActualName = MaxIterationsParameter.Name;
314    //    matrixOp.StartIndexParameter.Value = new IntValue(0);
315    //    matrixOp.IndexParameter.ActualName = "CurrentIteration";
316    //    matrixOp.EndValueParameter.Value = new DoubleValue(0);
317    //  }
318    //  VelocityBoundsUpdaterParameter.ValueChanged += new EventHandler(VelocityBoundsUpdaterParameter_ValueChanged);
319    //}
320
321    private void InitInertiaUpdater() {
322      foreach (IDiscreteDoubleValueModifier updater in InertiaUpdaterParameter.ValidValues) {
323        updater.EndIndexParameter.ActualName = MaxIterationsParameter.Name;
324        updater.StartIndexParameter.Value = new IntValue(0);
325        updater.IndexParameter.ActualName = "CurrentIteration";
326        updater.ValueParameter.ActualName = InertiaParameter.Name;
327        updater.StartValueParameter.Value = new DoubleValue(1);
328        updater.EndValueParameter.Value = new DoubleValue(0);
329      }
330    }
331
332    private void UpdateInertiaUpdater() {
333      IDiscreteDoubleValueModifier oldInertiaUpdater = InertiaUpdater;
334      InertiaUpdaterParameter.ValidValues.Clear();
335      foreach (IDiscreteDoubleValueModifier updater in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name)) {
336        InertiaUpdaterParameter.ValidValues.Add(updater);
337      }
338      if (oldInertiaUpdater != null) {
339        IDiscreteDoubleValueModifier updater = InertiaUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldInertiaUpdater.GetType());
340        if (updater != null) InertiaUpdaterParameter.Value = updater;
341      }
342    }
343
344    private void UpdateTopologyInitializer() {
345      ITopologyInitializer oldTopologyInitializer = TopologyInitializer;
346      TopologyInitializerParameter.ValidValues.Clear();
347      foreach (ITopologyInitializer topologyInitializer in ApplicationManager.Manager.GetInstances<ITopologyInitializer>().OrderBy(x => x.Name)) {
348        TopologyInitializerParameter.ValidValues.Add(topologyInitializer);
349      }
350      if (oldTopologyInitializer != null && TopologyInitializerParameter.ValidValues.Any(x => x.GetType() == oldTopologyInitializer.GetType()))
351        TopologyInitializer = TopologyInitializerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTopologyInitializer.GetType());
352      UpdateTopologyParameters();
353    }
354
355    private void UpdateTopologyParameters() {
356      ITopologyUpdater oldTopologyUpdater = TopologyUpdater;
357      IParticleUpdater oldParticleUpdater = ParticleUpdater;
358      ClearTopologyParameters();
359      if (Problem != null) {
360        if (TopologyInitializer != null) {
361          foreach (ITopologyUpdater topologyUpdater in ApplicationManager.Manager.GetInstances<ITopologyUpdater>())
362            TopologyUpdaterParameter.ValidValues.Add(topologyUpdater);
363          foreach (IParticleUpdater particleUpdater in Problem.Operators.OfType<ILocalParticleUpdater>().OrderBy(x => x.Name))
364            ParticleUpdaterParameter.ValidValues.Add(particleUpdater);
365        } else {
366          foreach (IParticleUpdater particleUpdater in Problem.Operators.OfType<IGlobalParticleUpdater>().OrderBy(x => x.Name))
367            ParticleUpdaterParameter.ValidValues.Add(particleUpdater);
368        }
369        if (oldTopologyUpdater != null) {
370          ITopologyUpdater newTopologyUpdater = TopologyUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleUpdater.GetType());
371          if (newTopologyUpdater != null) TopologyUpdater = newTopologyUpdater;
372        }
373        if (oldParticleUpdater != null) {
374          IParticleUpdater newParticleUpdater = ParticleUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleUpdater.GetType());
375          if (newParticleUpdater != null) ParticleUpdater = newParticleUpdater;
376        }
377      }
378    }
379
380    private void ClearTopologyParameters() {
381      TopologyUpdaterParameter.ValidValues.Clear();
382      ParticleUpdaterParameter.ValidValues.Clear();
383    }
384
385    private void ParameterizeSolutionsCreator() {
386      if (Problem != null) {
387        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
388        solutionsCreator.SolutionCreatorParameter.ActualName = ParticleCreatorParameter.Name;
389      }
390    }
391
392    private void ParameterizeMainLoop() {
393      if (Problem != null) {
394        mainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
395      }
396    }
397
398    private void InitializeSwarmUpdater() {
399      if (Problem != null) {
400        ISwarmUpdater updater = Problem.Operators.OfType<ISwarmUpdater>().FirstOrDefault();
401        SwarmUpdaterParameter.ValidValues.Clear();
402        SwarmUpdaterParameter.ValidValues.Add(updater);
403        SwarmUpdaterParameter.Value = updater;
404      }
405    }
406    #endregion
407
408  }
409}
Note: See TracBrowser for help on using the repository browser.