Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimization.cs @ 7952

Last change on this file since 7952 was 7781, checked in by epitzer, 13 years ago

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