sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimization.cs

   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
  22 using System;
  23 using System.Linq;
  24 using HeuristicLab.Analysis;
  25 using HeuristicLab.Common;
  26 using HeuristicLab.Core;
  27 using HeuristicLab.Data;
  28 using HeuristicLab.Operators;
  29 using HeuristicLab.Optimization;
  30 using HeuristicLab.Optimization.Operators;
  31 using HeuristicLab.Parameters;
  32 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  33 using HeuristicLab.PluginInfrastructure;
  34 using HeuristicLab.Random;
  35
  36 namespace 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     public override void Prepare() {
 261       if (Problem != null && ParticleCreator != null && ParticleUpdater != null) {
 262         base.Prepare();
 263       }
 264     }
 265
 266     #region Events
 267     protected override void OnProblemChanged() {
 268       UpdateAnalyzers();
 269       ParameterizeAnalyzers();
 270       UpdateTopologyParameters();
 271       InitializeParticleCreator();
 272       InitializeSwarmUpdater();
 273       ParameterizeSolutionsCreator();
 274       base.OnProblemChanged();
 275     }
 276
 277     void TopologyInitializerParameter_ValueChanged(object sender, EventArgs e) {
 278       this.UpdateTopologyParameters();
 279     }
 280     #endregion
 281
 282     #region Helpers
 283     private void Initialize() {
 284       TopologyInitializerParameter.ValueChanged += new EventHandler(TopologyInitializerParameter_ValueChanged);
 285     }
 286
 287     private void InitializeParticleCreator() {
 288       if (Problem != null) {
 289         IParticleCreator oldParticleCreator = ParticleCreator;
 290         ParticleCreatorParameter.ValidValues.Clear();
 291         foreach (IParticleCreator Creator in Problem.Operators.OfType<IParticleCreator>().OrderBy(x => x.Name)) {
 292           ParticleCreatorParameter.ValidValues.Add(Creator);
 293         }
 294         if (oldParticleCreator != null) {
 295           IParticleCreator creator = ParticleCreatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleCreator.GetType());
 296           if (creator != null) ParticleCreator = creator;
 297         }
 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);
 320       }
 321       Analyzer.Operators.Add(qualityAnalyzer);
 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.Value = new DoubleValue(1);
 333         updater.EndValueParameter.Value = new DoubleValue(1E-10);
 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       ITopologyInitializer 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       if (oldTopologyInitializer != null && TopologyInitializerParameter.ValidValues.Any(x => x.GetType() == oldTopologyInitializer.GetType()))
 356         TopologyInitializer = TopologyInitializerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTopologyInitializer.GetType());
 357       UpdateTopologyParameters();
 358     }
 359
 360     private void ParameterizeTopologyUpdaters() {
 361       foreach (var updater in TopologyUpdaterParameter.ValidValues) {
 362         var multiPsoUpdater = updater as MultiPSOTopologyUpdater;
 363         if (multiPsoUpdater != null) {
 364           multiPsoUpdater.CurrentIterationParameter.ActualName = "Iterations";
 365         }
 366       }
 367     }
 368
 369     private void UpdateTopologyParameters() {
 370       ITopologyUpdater oldTopologyUpdater = TopologyUpdater;
 371       IParticleUpdater oldParticleUpdater = ParticleUpdater;
 372       ClearTopologyParameters();
 373       if (Problem != null) {
 374         if (TopologyInitializer != null) {
 375           foreach (ITopologyUpdater topologyUpdater in ApplicationManager.Manager.GetInstances<ITopologyUpdater>())
 376             TopologyUpdaterParameter.ValidValues.Add(topologyUpdater);
 377           foreach (IParticleUpdater particleUpdater in Problem.Operators.OfType<ILocalParticleUpdater>().OrderBy(x => x.Name))
 378             ParticleUpdaterParameter.ValidValues.Add(particleUpdater);
 379         } else {
 380           foreach (IParticleUpdater particleUpdater in Problem.Operators.OfType<IGlobalParticleUpdater>().OrderBy(x => x.Name))
 381             ParticleUpdaterParameter.ValidValues.Add(particleUpdater);
 382         }
 383         if (oldTopologyUpdater != null) {
 384           ITopologyUpdater newTopologyUpdater = TopologyUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleUpdater.GetType());
 385           if (newTopologyUpdater != null) TopologyUpdater = newTopologyUpdater;
 386         }
 387         if (oldParticleUpdater != null) {
 388           IParticleUpdater newParticleUpdater = ParticleUpdaterParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldParticleUpdater.GetType());
 389           if (newParticleUpdater != null) ParticleUpdater = newParticleUpdater;
 390         }
 391
 392         ParameterizeTopologyUpdaters();
 393       }
 394     }
 395
 396     private void ClearTopologyParameters() {
 397       TopologyUpdaterParameter.ValidValues.Clear();
 398       ParticleUpdaterParameter.ValidValues.Clear();
 399     }
 400
 401     private void ParameterizeSolutionsCreator() {
 402       if (Problem != null) {
 403         solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
 404         solutionsCreator.SolutionCreatorParameter.ActualName = ParticleCreatorParameter.Name;
 405       }
 406     }
 407
 408     private void ParameterizeMainLoop() {
 409       if (Problem != null) {
 410         mainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
 411       }
 412     }
 413
 414     private void InitializeSwarmUpdater() {
 415       if (Problem != null) {
 416         ISwarmUpdater updater = Problem.Operators.OfType<ISwarmUpdater>().FirstOrDefault();
 417         SwarmUpdaterParameter.ValidValues.Clear();
 418         if (updater != null) {
 419           SwarmUpdaterParameter.ValidValues.Add(updater);
 420           SwarmUpdaterParameter.Value = updater;
 421         }
 422       }
 423     }
 424     #endregion
 425
 426   }
 427 }