source: trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimization.cs @ 15091

Last change on this file since 15091 was 15091, checked in by abeham, 2 years ago

#2797:

  • Updated PSO to make it more compatible with SPSO 2011
  • Removed truncation of velocity vector and instead rescaled it given the maximum velocity
  • Added non-zero initial velocity according to SPSO 2011
  • Removed complicated bouncing code due to box constraints and instead implemented as described in SPSO 2011
  • Calculating neighbor best has been changed to use personal best
  • Avoiding local and global particle update and instead relying on neighborbest
  • More randomization during velocity update by using a separate random numbers per dimension
  • Reusing problem specific solution creator in RealVectorParticleCreator instead of always using UniformRandomRealVectorCreator
File size: 20.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
38  [Item("Particle Swarm Optimization (PSO)", "A particle swarm optimization algorithm based on the description in Pedersen, M.E.H. (2010). PhD thesis. University of Southampton.")]
39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 300)]
40  [StorableClass]
41  public sealed class ParticleSwarmOptimization : HeuristicOptimizationEngineAlgorithm, IStorableContent {
42    #region Parameter Properties
43    public IValueParameter<IntValue> SeedParameter {
44      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
45    }
46    public IValueParameter<BoolValue> SetSeedRandomlyParameter {
47      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
48    }
49    public IValueParameter<IntValue> SwarmSizeParameter {
50      get { return (IValueParameter<IntValue>)Parameters["SwarmSize"]; }
51    }
52    public IValueParameter<IntValue> MaxIterationsParameter {
53      get { return (IValueParameter<IntValue>)Parameters["MaxIterations"]; }
54    }
55    public IValueParameter<DoubleValue> InertiaParameter {
56      get { return (IValueParameter<DoubleValue>)Parameters["Inertia"]; }
57    }
58    public IValueParameter<DoubleValue> PersonalBestAttractionParameter {
59      get { return (IValueParameter<DoubleValue>)Parameters["PersonalBestAttraction"]; }
60    }
61    public IValueParameter<DoubleValue> NeighborBestAttractionParameter {
62      get { return (IValueParameter<DoubleValue>)Parameters["NeighborBestAttraction"]; }
63    }
64    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
65      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
66    }
67    public IConstrainedValueParameter<IParticleCreator> ParticleCreatorParameter {
68      get { return (IConstrainedValueParameter<IParticleCreator>)Parameters["ParticleCreator"]; }
69    }
70    public IConstrainedValueParameter<IParticleUpdater> ParticleUpdaterParameter {
71      get { return (IConstrainedValueParameter<IParticleUpdater>)Parameters["ParticleUpdater"]; }
72    }
73    public IConstrainedValueParameter<ITopologyInitializer> TopologyInitializerParameter {
74      get { return (IConstrainedValueParameter<ITopologyInitializer>)Parameters["TopologyInitializer"]; }
75    }
76    public IConstrainedValueParameter<ITopologyUpdater> TopologyUpdaterParameter {
77      get { return (IConstrainedValueParameter<ITopologyUpdater>)Parameters["TopologyUpdater"]; }
78    }
79    public IConstrainedValueParameter<IDiscreteDoubleValueModifier> InertiaUpdaterParameter {
80      get { return (IConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["InertiaUpdater"]; }
81    }
82    public IConstrainedValueParameter<ISwarmUpdater> SwarmUpdaterParameter {
83      get { return (IConstrainedValueParameter<ISwarmUpdater>)Parameters["SwarmUpdater"]; }
84
85    }
86    #endregion
87
88    #region Properties
89
90    public string Filename { get; set; }
91
92    [Storable]
93    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
94
95    [Storable]
96    private SolutionsCreator solutionsCreator;
97
98    [Storable]
99    private ParticleSwarmOptimizationMainLoop mainLoop;
100
101    public override Type ProblemType {
102      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
103    }
104    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
105      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
106      set { base.Problem = value; }
107    }
108    public IntValue Seed {
109      get { return SeedParameter.Value; }
110      set { SeedParameter.Value = value; }
111    }
112    public BoolValue SetSeedRandomly {
113      get { return SetSeedRandomlyParameter.Value; }
114      set { SetSeedRandomlyParameter.Value = value; }
115    }
116    public IntValue SwarmSize {
117      get { return SwarmSizeParameter.Value; }
118      set { SwarmSizeParameter.Value = value; }
119    }
120    public IntValue MaxIterations {
121      get { return MaxIterationsParameter.Value; }
122      set { MaxIterationsParameter.Value = value; }
123    }
124    public DoubleValue Inertia {
125      get { return InertiaParameter.Value; }
126      set { InertiaParameter.Value = value; }
127    }
128    public DoubleValue PersonalBestAttraction {
129      get { return PersonalBestAttractionParameter.Value; }
130      set { PersonalBestAttractionParameter.Value = value; }
131    }
132    public DoubleValue NeighborBestAttraction {
133      get { return NeighborBestAttractionParameter.Value; }
134      set { NeighborBestAttractionParameter.Value = value; }
135    }
136    public MultiAnalyzer Analyzer {
137      get { return AnalyzerParameter.Value; }
138      set { AnalyzerParameter.Value = value; }
139    }
140    public IParticleCreator ParticleCreator {
141      get { return ParticleCreatorParameter.Value; }
142      set { ParticleCreatorParameter.Value = value; }
143    }
144    public IParticleUpdater ParticleUpdater {
145      get { return ParticleUpdaterParameter.Value; }
146      set { ParticleUpdaterParameter.Value = value; }
147    }
148    public ITopologyInitializer TopologyInitializer {
149      get { return TopologyInitializerParameter.Value; }
150      set { TopologyInitializerParameter.Value = value; }
151    }
152    public ITopologyUpdater TopologyUpdater {
153      get { return TopologyUpdaterParameter.Value; }
154      set { TopologyUpdaterParameter.Value = value; }
155    }
156    public IDiscreteDoubleValueModifier InertiaUpdater {
157      get { return InertiaUpdaterParameter.Value; }
158      set { InertiaUpdaterParameter.Value = value; }
159    }
160    public ISwarmUpdater SwarmUpdater {
161      get { return SwarmUpdaterParameter.Value; }
162      set { SwarmUpdaterParameter.Value = value; }
163    }
164    #endregion
165
166    [StorableConstructor]
167    private ParticleSwarmOptimization(bool deserializing) : base(deserializing) { }
168    private ParticleSwarmOptimization(ParticleSwarmOptimization original, Cloner cloner)
169      : base(original, cloner) {
170      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
171      solutionsCreator = cloner.Clone(original.solutionsCreator);
172      mainLoop = cloner.Clone(original.mainLoop);
173      Initialize();
174    }
175    public ParticleSwarmOptimization()
176      : base() {
177      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
178      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
179      Parameters.Add(new ValueParameter<IntValue>("SwarmSize", "Size of the particle swarm.", new IntValue(10)));
180      Parameters.Add(new ValueParameter<IntValue>("MaxIterations", "Maximal number of iterations.", new IntValue(1000)));
181      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
182      Parameters.Add(new ValueParameter<DoubleValue>("Inertia", "Inertia weight on a particle's movement (omega).", new DoubleValue(0.9)));
183      Parameters.Add(new ValueParameter<DoubleValue>("PersonalBestAttraction", "Weight for particle's pull towards its personal best soution (phi_p).", new DoubleValue(0.05)));
184      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(0.5)));
185      Parameters.Add(new ConstrainedValueParameter<IParticleCreator>("ParticleCreator", "Operator that creates a new particle."));
186      Parameters.Add(new ConstrainedValueParameter<IParticleUpdater>("ParticleUpdater", "Operator that updates a particle."));
187      Parameters.Add(new OptionalConstrainedValueParameter<ITopologyInitializer>("TopologyInitializer", "Creates neighborhood description vectors."));
188      Parameters.Add(new OptionalConstrainedValueParameter<ITopologyUpdater>("TopologyUpdater", "Updates the neighborhood description vectors."));
189      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("InertiaUpdater", "Updates the omega parameter."));
190      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"));
191      ParticleUpdaterParameter.Hidden = true;
192
193      RandomCreator randomCreator = new RandomCreator();
194      VariableCreator variableCreator = new VariableCreator();
195      Assigner currentInertiaAssigner = new Assigner();
196      solutionsCreator = new SolutionsCreator();
197      SubScopesCounter subScopesCounter = new SubScopesCounter();
198      Placeholder topologyInitializerPlaceholder = new Placeholder();
199      mainLoop = new ParticleSwarmOptimizationMainLoop();
200
201      OperatorGraph.InitialOperator = randomCreator;
202
203      randomCreator.SetSeedRandomlyParameter.Value = null;
204      randomCreator.SeedParameter.Value = null;
205      randomCreator.Successor = variableCreator;
206
207      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
208      variableCreator.Successor = currentInertiaAssigner;
209
210      currentInertiaAssigner.Name = "CurrentInertia := Inertia";
211      currentInertiaAssigner.LeftSideParameter.ActualName = "CurrentInertia";
212      currentInertiaAssigner.RightSideParameter.ActualName = "Inertia";
213      currentInertiaAssigner.Successor = solutionsCreator;
214
215      solutionsCreator.NumberOfSolutionsParameter.ActualName = "SwarmSize";
216      ParameterizeSolutionsCreator();
217      solutionsCreator.Successor = subScopesCounter;
218
219      subScopesCounter.Name = "Initialize EvaluatedSolutions";
220      subScopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
221      subScopesCounter.Successor = topologyInitializerPlaceholder;
222
223      topologyInitializerPlaceholder.Name = "(TopologyInitializer)";
224      topologyInitializerPlaceholder.OperatorParameter.ActualName = "TopologyInitializer";
225      topologyInitializerPlaceholder.Successor = mainLoop;
226
227      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
228      mainLoop.InertiaParameter.ActualName = "CurrentInertia";
229      mainLoop.MaxIterationsParameter.ActualName = MaxIterationsParameter.Name;
230      mainLoop.NeighborBestAttractionParameter.ActualName = NeighborBestAttractionParameter.Name;
231      mainLoop.InertiaUpdaterParameter.ActualName = InertiaUpdaterParameter.Name;
232      mainLoop.ParticleUpdaterParameter.ActualName = ParticleUpdaterParameter.Name;
233      mainLoop.PersonalBestAttractionParameter.ActualName = PersonalBestAttractionParameter.Name;
234      mainLoop.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName;
235      mainLoop.SwarmSizeParameter.ActualName = SwarmSizeParameter.Name;
236      mainLoop.TopologyUpdaterParameter.ActualName = TopologyUpdaterParameter.Name;
237      mainLoop.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName;
238      mainLoop.ResultsParameter.ActualName = "Results";
239
240      InitializeAnalyzers();
241      InitializeParticleCreator();
242      InitializeSwarmUpdater();
243      ParameterizeSolutionsCreator();
244      UpdateAnalyzers();
245      UpdateInertiaUpdater();
246      InitInertiaUpdater();
247      UpdateTopologyInitializer();
248      Initialize();
249      ParameterizeMainLoop();
250    }
251
252    public override IDeepCloneable Clone(Cloner cloner) {
253      return new ParticleSwarmOptimization(this, cloner);
254    }
255
256    [StorableHook(HookType.AfterDeserialization)]
257    private void AfterDeserialization() {
258      Initialize();
259    }
260
261    #region Events
262    protected override void OnProblemChanged() {
263      UpdateAnalyzers();
264      ParameterizeAnalyzers();
265      UpdateParticleUpdaterParameter();
266      UpdateTopologyParameters();
267      InitializeParticleCreator();
268      InitializeSwarmUpdater();
269      ParameterizeSolutionsCreator();
270      base.OnProblemChanged();
271    }
272
273    void TopologyInitializerParameter_ValueChanged(object sender, EventArgs e) {
274      this.UpdateTopologyParameters();
275    }
276    #endregion
277
278    #region Helpers
279    private void Initialize() {
280      TopologyInitializerParameter.ValueChanged += new EventHandler(TopologyInitializerParameter_ValueChanged);
281    }
282
283    private void InitializeParticleCreator() {
284      ParticleCreatorParameter.ValidValues.Clear();
285      if (Problem != null) {
286        IParticleCreator oldParticleCreator = ParticleCreator;
287        IParticleCreator defaultParticleCreator = Problem.Operators.OfType<IParticleCreator>().FirstOrDefault();
288        foreach (var creator in Problem.Operators.OfType<IParticleCreator>().OrderBy(x => x.Name)) {
289          ParticleCreatorParameter.ValidValues.Add(creator);
290        }
291        if (oldParticleCreator != null) {
292          var creator = ParticleCreatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleCreator.GetType());
293          if (creator != null) ParticleCreator = creator;
294          else oldParticleCreator = null;
295        }
296        if (oldParticleCreator == null && defaultParticleCreator != null)
297          ParticleCreator = defaultParticleCreator;
298      }
299    }
300
301    private void InitializeAnalyzers() {
302      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
303      qualityAnalyzer.ResultsParameter.ActualName = "Results";
304      ParameterizeAnalyzers();
305    }
306
307    private void ParameterizeAnalyzers() {
308      if (Problem != null) {
309        qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
310        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
311        qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
312      }
313    }
314
315    private void UpdateAnalyzers() {
316      Analyzer.Operators.Clear();
317      if (Problem != null) {
318        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>())
319          Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
320      }
321      Analyzer.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
322    }
323
324    private void InitInertiaUpdater() {
325      foreach (IDiscreteDoubleValueModifier updater in InertiaUpdaterParameter.ValidValues) {
326        updater.EndIndexParameter.ActualName = MaxIterationsParameter.Name;
327        updater.EndIndexParameter.Hidden = true;
328        updater.StartIndexParameter.Value = new IntValue(0);
329        updater.StartIndexParameter.Hidden = true;
330        updater.IndexParameter.ActualName = "Iterations";
331        updater.ValueParameter.ActualName = "CurrentInertia";
332        updater.StartValueParameter.ActualName = InertiaParameter.Name;
333        updater.EndValueParameter.Value = new DoubleValue(0.70);
334      }
335    }
336
337    private void UpdateInertiaUpdater() {
338      IDiscreteDoubleValueModifier oldInertiaUpdater = InertiaUpdater;
339      InertiaUpdaterParameter.ValidValues.Clear();
340      foreach (IDiscreteDoubleValueModifier updater in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name)) {
341        InertiaUpdaterParameter.ValidValues.Add(updater);
342      }
343      if (oldInertiaUpdater != null) {
344        IDiscreteDoubleValueModifier updater = InertiaUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldInertiaUpdater.GetType());
345        if (updater != null) InertiaUpdaterParameter.Value = updater;
346      }
347    }
348
349    private void UpdateTopologyInitializer() {
350      var oldTopologyInitializer = TopologyInitializer;
351      TopologyInitializerParameter.ValidValues.Clear();
352      foreach (ITopologyInitializer topologyInitializer in ApplicationManager.Manager.GetInstances<ITopologyInitializer>().OrderBy(x => x.Name)) {
353        TopologyInitializerParameter.ValidValues.Add(topologyInitializer);
354      }
355
356      if (oldTopologyInitializer != null && TopologyInitializerParameter.ValidValues.Any(x => x.GetType() == oldTopologyInitializer.GetType()))
357        TopologyInitializer = TopologyInitializerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTopologyInitializer.GetType());
358      UpdateTopologyParameters();
359    }
360
361    private void ParameterizeTopologyUpdaters() {
362      foreach (var updater in TopologyUpdaterParameter.ValidValues.OfType<MultiPSOTopologyUpdater>()) {
363        updater.CurrentIterationParameter.ActualName = "Iterations";
364      }
365    }
366
367    private void UpdateParticleUpdaterParameter() {
368      var oldParticleUpdater = ParticleUpdater;
369      ParticleUpdaterParameter.ValidValues.Clear();
370      if (Problem != null) {
371        var defaultParticleUpdater = Problem.Operators.OfType<IParticleUpdater>().FirstOrDefault();
372
373        foreach (var particleUpdater in Problem.Operators.OfType<IParticleUpdater>().OrderBy(x => x.Name))
374          ParticleUpdaterParameter.ValidValues.Add(particleUpdater);
375
376        if (oldParticleUpdater != null) {
377          var newParticleUpdater = ParticleUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleUpdater.GetType());
378          if (newParticleUpdater != null) ParticleUpdater = newParticleUpdater;
379          else oldParticleUpdater = null;
380        }
381        if (oldParticleUpdater == null && defaultParticleUpdater != null)
382          ParticleUpdater = defaultParticleUpdater;
383      }
384    }
385
386    private void UpdateTopologyParameters() {
387      ITopologyUpdater oldTopologyUpdater = TopologyUpdater;
388      TopologyUpdaterParameter.ValidValues.Clear();
389      if (Problem != null) {
390        if (TopologyInitializerParameter.Value != null) {
391          foreach (ITopologyUpdater topologyUpdater in ApplicationManager.Manager.GetInstances<ITopologyUpdater>())
392            TopologyUpdaterParameter.ValidValues.Add(topologyUpdater);
393
394          if (oldTopologyUpdater != null) {
395            ITopologyUpdater newTopologyUpdater = TopologyUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTopologyUpdater.GetType());
396            if (newTopologyUpdater != null) TopologyUpdater = newTopologyUpdater;
397          }
398          ParameterizeTopologyUpdaters();
399        }
400      }
401    }
402
403    private void ParameterizeSolutionsCreator() {
404      if (Problem != null) {
405        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
406        if (ParticleCreatorParameter.Value != null)
407          solutionsCreator.SolutionCreatorParameter.ActualName = ParticleCreatorParameter.Name;
408        else
409          solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
410      }
411    }
412
413    private void ParameterizeMainLoop() {
414      if (Problem != null) {
415        mainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
416      }
417    }
418
419    private void InitializeSwarmUpdater() {
420      if (Problem != null) {
421        ISwarmUpdater updater = Problem.Operators.OfType<ISwarmUpdater>().FirstOrDefault();
422        SwarmUpdaterParameter.ValidValues.Clear();
423        if (updater != null) {
424          SwarmUpdaterParameter.ValidValues.Add(updater);
425          SwarmUpdaterParameter.Value = updater;
426        }
427      }
428    }
429    #endregion
430
431  }
432}
Note: See TracBrowser for help on using the repository browser.