Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PSO/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimization.cs @ 5312

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

#852: Adjusted PSO Prepare to use start value of omega/velocity updater(s) if specified.
File size: 19.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Encodings.RealVectorEncoding;
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
39  [Item("Particle Swarm Optimization", "A particle swarm optimization algorithm based on the description in Pedersen, M.E.H. (2010). PhD thesis. University of Southampton.")]
40  [Creatable("Algorithms")]
41  [StorableClass]
42  public class ParticleSwarmOptimization : EngineAlgorithm {
43
44    #region Problem Properties
45    public override Type ProblemType {
46      get { return typeof(ISingleObjectiveProblem); }
47    }
48    public new ISingleObjectiveProblem Problem {
49      get { return (ISingleObjectiveProblem)base.Problem; }
50      set { base.Problem = value; }
51    }
52    public MultiAnalyzer Analyzer {
53      get { return AnalyzerParameter.Value; }
54      set { AnalyzerParameter.Value = value; }
55    }
56    public IDiscreteDoubleValueModifier OmegaUpdater {
57      get { return OmegaUpdaterParameter.Value; }
58      set { OmegaUpdaterParameter.Value = value; }
59    }
60    public IDiscreteDoubleMatrixModifier VelocityBoundsUpdater {
61      get { return VelocityBoundsUpdaterParameter.Value; }
62      set { VelocityBoundsUpdaterParameter.Value = value; }
63    }
64    #endregion
65
66    #region Parameter Properties
67    public ValueParameter<IntValue> SeedParameter {
68      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
69    }
70    public ValueParameter<BoolValue> SetSeedRandomlyParameter {
71      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
72    }
73    public ValueParameter<IntValue> SwarmSizeParameter {
74      get { return (ValueParameter<IntValue>)Parameters["SwarmSize"]; }
75    }
76    public ValueParameter<IntValue> MaxIterationsParameter {
77      get { return (ValueParameter<IntValue>)Parameters["MaxIterations"]; }
78    }
79    public ValueParameter<DoubleValue> OmegaParameter {
80      get { return (ValueParameter<DoubleValue>)Parameters["Omega"]; }
81    }
82    public ValueParameter<DoubleValue> Phi_PParameter {
83      get { return (ValueParameter<DoubleValue>)Parameters["Phi_P"]; }
84    }
85    public ValueParameter<DoubleValue> Phi_GParameter {
86      get { return (ValueParameter<DoubleValue>)Parameters["Phi_G"]; }
87    }
88    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
89      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
90    }
91    public ValueLookupParameter<DoubleMatrix> VelocityBoundsParameter {
92      get { return (ValueLookupParameter<DoubleMatrix>)Parameters["VelocityBounds"]; }
93    }
94    public ConstrainedValueParameter<IParticleUpdater> ParticleUpdaterParameter {
95      get { return (ConstrainedValueParameter<IParticleUpdater>)Parameters["ParticleUpdater"]; }
96    }
97    public ConstrainedValueParameter<ITopologyInitializer> TopologyInitializerParameter {
98      get { return (ConstrainedValueParameter<ITopologyInitializer>)Parameters["TopologyInitializer"]; }
99    }
100    public ConstrainedValueParameter<ITopologyUpdater> TopologyUpdaterParameter {
101      get { return (ConstrainedValueParameter<ITopologyUpdater>)Parameters["TopologyUpdater"]; }
102    }
103    public OptionalConstrainedValueParameter<IDiscreteDoubleMatrixModifier> VelocityBoundsUpdaterParameter {
104      get { return (OptionalConstrainedValueParameter<IDiscreteDoubleMatrixModifier>)Parameters["VelocityBoundsUpdater"]; }
105    }
106    public OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier> OmegaUpdaterParameter {
107      get { return (OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["OmegaUpdater"]; }
108    }
109    #endregion
110
111    #region Properties
112    [Storable]
113    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
114    #endregion
115
116    [StorableConstructor]
117    protected ParticleSwarmOptimization(bool deserializing) : base(deserializing) { }
118    protected ParticleSwarmOptimization(ParticleSwarmOptimization original, Cloner cloner)
119      : base(original, cloner) {
120      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
121    }
122
123    public ParticleSwarmOptimization()
124      : base() {
125      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
126      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
127      Parameters.Add(new ValueParameter<IntValue>("SwarmSize", "Size of the particle swarm.", new IntValue(10)));
128      Parameters.Add(new ValueParameter<IntValue>("MaxIterations", "Maximal number of iterations.", new IntValue(1000)));
129      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
130      Parameters.Add(new ValueParameter<DoubleValue>("Omega", "Weight for particle's velocity vector.", new DoubleValue(-0.2)));
131      Parameters.Add(new ValueParameter<DoubleValue>("Phi_P", "Weight for particle's personal best position.", new DoubleValue(-0.01)));
132      Parameters.Add(new ValueParameter<DoubleValue>("Phi_G", "Weight for global best position.", new DoubleValue(3.7)));
133      Parameters.Add(new ValueLookupParameter<DoubleMatrix>("VelocityBounds", "Maximum Velocity in every dimension", new DoubleMatrix(new double[,] { { -1, 1 } })));
134      Parameters.Add(new ConstrainedValueParameter<IParticleUpdater>("ParticleUpdater", "Operator that calculates new position and velocity of a particle",
135        new ItemSet<IParticleUpdater>(ApplicationManager.Manager.GetInstances<IParticleUpdater>())));
136      Parameters.Add(new ConstrainedValueParameter<ITopologyInitializer>("TopologyInitializer", "Creates neighborhood description vectors",
137        new ItemSet<ITopologyInitializer>(ApplicationManager.Manager.GetInstances<ITopologyInitializer>())));
138      Parameters.Add(new ConstrainedValueParameter<ITopologyUpdater>("TopologyUpdater", "Updates the neighborhood description vectors",
139        new ItemSet<ITopologyUpdater>(ApplicationManager.Manager.GetInstances<ITopologyUpdater>())));
140      //Parameters.Add(new ValueParameter<MultiParameterUpdater>("ParameterUpdater", "Updates the algorithm parameters according to some strategy",
141      //  new MultiParameterUpdater()));
142      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("OmegaUpdater", "Updates the omega parameter"));
143      //Parameters.Add(new ValueParameter<MatrixValueModifierSelector>("VelocityBoundsUpdater", "Adjusts the velocity bounds", new MatrixValueModifierSelector()));
144      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleMatrixModifier>("VelocityBoundsUpdater", "Adjusts the velocity bounds."));
145      ParticleUpdaterParameter.ActualValue = ParticleUpdaterParameter.ValidValues.SingleOrDefault(v => v.GetType() == typeof(TotallyConnectedParticleUpdater));
146      TopologyInitializerParameter.ActualValue = TopologyInitializerParameter.ValidValues.SingleOrDefault(v => v.GetType() == typeof(EmptyTopologyInitializer));
147
148      RandomCreator randomCreator = new RandomCreator();
149      VariableCreator variableCreator = new VariableCreator();
150      SolutionsCreator solutionsCreator = new SolutionsCreator();
151      CombinedOperator particleCreator = new CombinedOperator();
152      Placeholder evaluatorPlaceholder = new Placeholder();
153      Assigner bestPersonalQualityAssigner = new Assigner();
154      BestPointInitializer bestPositionInitializer = new BestPointInitializer();
155      Placeholder topologyInitializerPlaceholder = new Placeholder();
156      NeighborUpdater neighborUpdater = new NeighborUpdater();
157      Placeholder analyzerPlaceholder = new Placeholder();
158      UniformSubScopesProcessor uniformSubScopeProcessor = new UniformSubScopesProcessor();
159      Placeholder particleUpdaterPlaceholder = new Placeholder();
160      Placeholder topologyUpdaterPlaceholder = new Placeholder();
161      UniformSubScopesProcessor uniformSubscopesProcessor2 = new UniformSubScopesProcessor();
162      NeighborUpdater neighborUpdater2 = new NeighborUpdater();
163      Placeholder evaluatorPlaceholder2 = new Placeholder();
164      SwarmUpdater swarmUpdater = new SwarmUpdater();
165      Placeholder analyzerPlaceholder2 = new Placeholder();
166      IntCounter currentIterationCounter = new IntCounter();
167      Comparator currentIterationComparator = new Comparator();
168      ConditionalBranch conditionalBranch = new ConditionalBranch();
169      Placeholder velocityBoundsUpdaterPlaceholder = new Placeholder();
170      Placeholder omegaUpdaterPlaceholder = new Placeholder();
171
172      OperatorGraph.InitialOperator = randomCreator;
173
174      randomCreator.SetSeedRandomlyParameter.Value = null;
175      randomCreator.SeedParameter.Value = null;
176      randomCreator.Successor = variableCreator;
177
178      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("CurrentIteration", new IntValue(0)));
179      variableCreator.Successor = solutionsCreator;
180
181      solutionsCreator.NumberOfSolutionsParameter.ActualName = "SwarmSize";
182      solutionsCreator.EvaluatorParameter.Value = evaluatorPlaceholder;
183      solutionsCreator.SolutionCreatorParameter.Value = particleCreator;
184      solutionsCreator.Successor = bestPositionInitializer;
185
186      InitializeParticleCreator(particleCreator);
187
188      evaluatorPlaceholder.Name = "(Evaluator)";
189      evaluatorPlaceholder.OperatorParameter.ActualName = "Evaluator";
190      evaluatorPlaceholder.Successor = bestPersonalQualityAssigner;
191
192      bestPersonalQualityAssigner.LeftSideParameter.ActualName = "PersonalBestQuality";
193      bestPersonalQualityAssigner.RightSideParameter.ActualName = "Quality";
194
195      bestPositionInitializer.Successor = topologyInitializerPlaceholder;
196
197      topologyInitializerPlaceholder.Name = "(TopologyInitializer)";
198      topologyInitializerPlaceholder.OperatorParameter.ActualName = "TopologyInitializer";
199      topologyInitializerPlaceholder.Successor = neighborUpdater;
200
201      neighborUpdater.Successor = analyzerPlaceholder;
202
203      analyzerPlaceholder.Name = "(Analyzer)";
204      analyzerPlaceholder.OperatorParameter.ActualName = "Analyzer";
205      analyzerPlaceholder.Successor = uniformSubScopeProcessor;
206
207      uniformSubScopeProcessor.Operator = particleUpdaterPlaceholder;
208      uniformSubScopeProcessor.Successor = topologyUpdaterPlaceholder;
209
210      particleUpdaterPlaceholder.Name = "(ParticleUpdater)";
211      particleUpdaterPlaceholder.OperatorParameter.ActualName = "ParticleUpdater";
212      particleUpdaterPlaceholder.Successor = evaluatorPlaceholder2;
213
214      evaluatorPlaceholder2.Name = "(Evaluator)";
215      evaluatorPlaceholder2.OperatorParameter.ActualName = "Evaluator";
216
217      topologyUpdaterPlaceholder.Name = "(TopologyUpdater)";
218      topologyUpdaterPlaceholder.OperatorParameter.ActualName = "TopologyUpdater";
219      topologyUpdaterPlaceholder.Successor = neighborUpdater2;
220
221      neighborUpdater2.Successor = uniformSubscopesProcessor2;
222
223      uniformSubscopesProcessor2.Operator = swarmUpdater;
224      uniformSubscopesProcessor2.Successor = analyzerPlaceholder2;
225
226      analyzerPlaceholder2.Name = "(Analyzer)";
227      analyzerPlaceholder2.OperatorParameter.ActualName = "Analyzer";
228      analyzerPlaceholder2.Successor = currentIterationCounter;
229
230      currentIterationCounter.Name = "CurrentIteration++";
231      currentIterationCounter.ValueParameter.ActualName = "CurrentIteration";
232      currentIterationCounter.Successor = omegaUpdaterPlaceholder;
233
234      omegaUpdaterPlaceholder.Name = "(Omega Updater)";
235      omegaUpdaterPlaceholder.OperatorParameter.ActualName = "OmegaUpdater";
236      omegaUpdaterPlaceholder.Successor = velocityBoundsUpdaterPlaceholder;
237
238      velocityBoundsUpdaterPlaceholder.Name = "(Velocity Bounds Updater)";
239      velocityBoundsUpdaterPlaceholder.OperatorParameter.ActualName = "VelocityBoundsUpdater";
240      velocityBoundsUpdaterPlaceholder.Successor = currentIterationComparator;
241
242      currentIterationComparator.LeftSideParameter.ActualName = "CurrentIteration";
243      currentIterationComparator.Comparison = new Comparison(ComparisonType.Less);
244      currentIterationComparator.RightSideParameter.ActualName = "MaxIterations";
245      currentIterationComparator.ResultParameter.ActualName = "ContinueIteration";
246      currentIterationComparator.Successor = conditionalBranch;
247
248      conditionalBranch.Name = "ContinueIteration?";
249      conditionalBranch.ConditionParameter.ActualName = "ContinueIteration";
250      conditionalBranch.TrueBranch = uniformSubScopeProcessor;
251
252      InitializeAnalyzers();
253      InitVelocityBoundsUpdater();
254      UpdateAnalyzers();
255      UpdateOmegaUpdater();
256      InitOmegaUpdater();
257    }
258
259    private static void InitializeParticleCreator(CombinedOperator particleCreator) {
260      Placeholder positionCreator = new Placeholder();
261      Assigner personalBestPositionAssigner = new Assigner();
262      UniformRandomRealVectorCreator velocityCreator = new UniformRandomRealVectorCreator();
263
264      particleCreator.Name = "Particle Creator";
265      particleCreator.OperatorGraph.InitialOperator = positionCreator;
266
267      positionCreator.Name = "(SolutionCreator)";
268      positionCreator.OperatorParameter.ActualName = "SolutionCreator";
269      positionCreator.Successor = personalBestPositionAssigner;
270
271      personalBestPositionAssigner.LeftSideParameter.ActualName = "PersonalBestPoint";
272      personalBestPositionAssigner.RightSideParameter.ActualName = "Point";
273      personalBestPositionAssigner.Successor = velocityCreator;
274
275      velocityCreator.LengthParameter.ActualName = "ProblemSize";
276      velocityCreator.BoundsParameter.ActualName = "VelocityBounds";
277      velocityCreator.RealVectorParameter.ActualName = "Velocity";
278    }
279
280    public override IDeepCloneable Clone(Cloner cloner) {
281      return new ParticleSwarmOptimization(this, cloner);
282    }
283
284    public override void Prepare() {
285      if (Problem != null) {
286        base.Prepare();
287        if (OmegaUpdater != null && OmegaUpdater.StartValueParameter.Value != null) {
288          this.OmegaParameter.ActualValue = new DoubleValue(OmegaUpdaterParameter.Value.StartValueParameter.Value.Value);
289        }
290        if (VelocityBoundsUpdater != null && VelocityBoundsUpdater.StartValueParameter.Value != null && VelocityBoundsParameter.ActualValue != null) {
291          DoubleMatrix matrix = VelocityBoundsParameter.ActualValue;
292          for (int i = 0; i < matrix.Rows; i++) {
293            for (int j = 0; j < matrix.Columns; j++) {
294              if (matrix[i, j] >= 0) {
295                matrix[i, j] = VelocityBoundsUpdater.StartValueParameter.Value.Value;
296              } else {
297                matrix[i, j] = (-1) * VelocityBoundsUpdater.StartValueParameter.Value.Value;
298              }
299            }
300          }
301        }
302      }
303    }
304
305    #region Events
306    protected override void OnProblemChanged() {
307      UpdateAnalyzers();
308      ParameterizeAnalyzers();
309      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
310      base.OnProblemChanged();
311    }
312
313    #endregion
314
315    #region Helpers
316    private void InitializeParticleUpdaters() {
317    }
318
319    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
320    }
321
322    private void InitializeAnalyzers() {
323      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
324      ParameterizeAnalyzers();
325    }
326
327    private void InitVelocityBoundsUpdater() {
328      foreach (IDiscreteDoubleMatrixModifier matrixOp in ApplicationManager.Manager.GetInstances<IDiscreteDoubleMatrixModifier>()) {
329        VelocityBoundsUpdaterParameter.ValidValues.Add(matrixOp);
330        matrixOp.ValueParameter.ActualName = VelocityBoundsParameter.Name;
331        matrixOp.EndIndexParameter.ActualName = MaxIterationsParameter.Name;
332        matrixOp.StartIndexParameter.Value = new IntValue(0);
333        matrixOp.IndexParameter.ActualName = "CurrentIteration";
334        matrixOp.EndValueParameter.Value = new DoubleValue(0);
335      }
336      VelocityBoundsUpdaterParameter.ValueChanged += new EventHandler(VelocityBoundsUpdaterParameter_ValueChanged);
337    }
338
339    void VelocityBoundsUpdaterParameter_ValueChanged(object sender, EventArgs e) {
340      if (VelocityBoundsParameter.Value != null) {
341        foreach (IDiscreteDoubleMatrixModifier matrixOp in VelocityBoundsUpdaterParameter.Value.ScalingOperatorParameter.ValidValues) {
342            matrixOp.ValueParameter.ActualName = VelocityBoundsUpdater.ScaleParameter.Name;
343            matrixOp.StartValueParameter.Value = new DoubleValue(VelocityBoundsUpdater.ScaleParameter.ActualValue.Value);
344        }
345      }
346    }
347
348    private void InitOmegaUpdater() {
349      foreach (IDiscreteDoubleValueModifier updater in OmegaUpdaterParameter.ValidValues) {
350        updater.EndIndexParameter.ActualName = MaxIterationsParameter.Name;
351        updater.StartIndexParameter.Value = new IntValue(0);
352        updater.IndexParameter.ActualName = "CurrentIteration";
353        updater.ValueParameter.ActualName = OmegaParameter.Name;
354        updater.StartValueParameter.Value = new DoubleValue(1);
355        updater.EndValueParameter.Value = new DoubleValue(0);
356      }
357    }
358
359    private void UpdateOmegaUpdater() {
360      IDiscreteDoubleValueModifier oldOmegaUpdater = OmegaUpdater;
361      OmegaUpdaterParameter.ValidValues.Clear();
362      foreach (IDiscreteDoubleValueModifier updater in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name)) {
363        OmegaUpdaterParameter.ValidValues.Add(updater);
364      }
365      if (oldOmegaUpdater != null) {
366        IDiscreteDoubleValueModifier updater = OmegaUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldOmegaUpdater.GetType());
367        if (updater != null) OmegaUpdaterParameter.Value = updater;
368      }
369    }
370
371    private void ParameterizeAnalyzers() {
372      if (Problem != null) {
373        qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
374        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
375        qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
376      }
377    }
378
379    private void UpdateAnalyzers() {
380      Analyzer.Operators.Clear();
381      if (Problem != null) {
382        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>())
383          Analyzer.Operators.Add(analyzer);
384      }
385      Analyzer.Operators.Add(qualityAnalyzer);
386    }
387
388    #endregion
389  }
390}
Note: See TracBrowser for help on using the repository browser.