Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/10/17 17:26:43 (7 years ago)
Author:
abeham
Message:

#2797:

  • Added IStochasticOperator interface to MultiPSOTopologyUpdater
  • Changed parameter defaults to those described in the paper
  • Added analyzer placeholder for the last iteration (has not been previously analyzed)
  • Changed random topology initializer to include itself (to be able to use it with SPSOSwarmUpdater -> this should not change the old RealVectorSwarmUpdater)
  • Changed ring topology initializer to include itself (same as above)
  • Changed von neumann topology initializer to include itself (same as above)
  • Added SPSO compatible random topology initializer (as described in the paper by Clerc)
  • Changed sampling of the random directional vector to be uniformly random on the surface of a hypersphere to avoid a slight bias in diagonal direction
  • Updating SwarmBestQuality and BestRealVector parameters in SPSOSwarmUpdater (an oversight)
  • Added a faster method to create a copy of a RealVector (based on Array.Copy)
  • Updated the sample
  • Updated the sample's test results (due to changed sampling in SPSO2011ParticleUpdater)
Location:
trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3
Files:
7 edited
2 copied

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/AdaptiveRandomTopologyUpdater.cs

    r15167 r15181  
    3131
    3232namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    33   [Item("Multi PSO Topology Updater", "Splits swarm into NrOfSwarms non-overlapping sub-swarms. Swarms are re-grouped every regroupingPeriod iteration. The operator is implemented as described in Liang, J.J. and Suganthan, P.N 2005. Dynamic multi-swarm particle swarm optimizer. IEEE Swarm Intelligence Symposium, pp. 124-129.")]
     33  [Item("SPSO Adaptive Random Topology Updater", "Each unsuccessful iteration the topology initializer is applied again.")]
    3434  [StorableClass]
    35   public sealed class MultiPSOTopologyUpdater : SingleSuccessorOperator, ITopologyUpdater {
     35  public sealed class SPSOAdaptiveRandomTopologyUpdater : SingleSuccessorOperator, ITopologyUpdater, ISingleObjectiveOperator {
    3636
    3737    public override bool CanChangeName {
    … …  
    4040
    4141    #region Parameters
    42     public ILookupParameter<IRandom> RandomParameter {
    43       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     42    public ILookupParameter<BoolValue> MaximizationParameter {
     43      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
    4444    }
    45     public IValueLookupParameter<IntValue> NrOfSwarmsParameter {
    46       get { return (IValueLookupParameter<IntValue>)Parameters["NrOfSwarms"]; }
     45    public ILookupParameter<DoubleValue> SwarmBestQualityParameter {
     46      get { return (ILookupParameter<DoubleValue>)Parameters["SwarmBestQuality"]; }
    4747    }
    48     public ILookupParameter<IntValue> SwarmSizeParameter {
    49       get { return (ILookupParameter<IntValue>)Parameters["SwarmSize"]; }
     48    public ILookupParameter<DoubleValue> PreviousBestQualityParameter {
     49      get { return (ILookupParameter<DoubleValue>)Parameters["PreviousBestQuality"]; }
     50    }
     51    public ILookupParameter<ITopologyInitializer> TopologyInitializerParameter {
     52      get { return (ILookupParameter<ITopologyInitializer>)Parameters["TopologyInitializer"]; }
    5053    }
    5154    public IScopeTreeLookupParameter<IntArray> NeighborsParameter {
    5255      get { return (IScopeTreeLookupParameter<IntArray>)Parameters["Neighbors"]; }
    53     }
    54     public ILookupParameter<IntValue> CurrentIterationParameter {
    55       get { return (ILookupParameter<IntValue>)Parameters["CurrentIteration"]; }
    56     }
    57     public IValueLookupParameter<IntValue> RegroupingPeriodParameter {
    58       get { return (IValueLookupParameter<IntValue>)Parameters["RegroupingPeriod"]; }
    59     }
    60     #endregion
    61 
    62     #region Parameter Values
    63     private IRandom Random {
    64       get { return RandomParameter.ActualValue; }
    65     }
    66     private int NrOfSwarms {
    67       get { return NrOfSwarmsParameter.ActualValue.Value; }
    68     }
    69     private int SwarmSize {
    70       get { return SwarmSizeParameter.ActualValue.Value; }
    71     }
    72     private ItemArray<IntArray> Neighbors {
    73       get { return NeighborsParameter.ActualValue; }
    74       set { NeighborsParameter.ActualValue = value; }
    75     }
    76     private int CurrentIteration {
    77       get { return CurrentIterationParameter.ActualValue.Value; }
    78     }
    79     private int RegroupingPeriod {
    80       get { return RegroupingPeriodParameter.ActualValue.Value; }
    8156    }
    8257    #endregion
    … …  
    8459    #region Construction & Cloning
    8560    [StorableConstructor]
    86     private MultiPSOTopologyUpdater(bool deserializing) : base(deserializing) { }
    87     private MultiPSOTopologyUpdater(MultiPSOTopologyUpdater original, Cloner cloner) : base(original, cloner) { }
    88     public MultiPSOTopologyUpdater()
     61    private SPSOAdaptiveRandomTopologyUpdater(bool deserializing) : base(deserializing) { }
     62    private SPSOAdaptiveRandomTopologyUpdater(SPSOAdaptiveRandomTopologyUpdater original, Cloner cloner) : base(original, cloner) { }
     63    public SPSOAdaptiveRandomTopologyUpdater()
    8964      : base() {
    90       Parameters.Add(new LookupParameter<IRandom>("Random", "A random number generator."));
    91       Parameters.Add(new ValueLookupParameter<IntValue>("NrOfSwarms", "Nr of connected sub-swarms.", new IntValue(3)));
    92       Parameters.Add(new LookupParameter<IntValue>("SwarmSize", "Number of particles in the swarm."));
     65      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Whether the problem is to be maximized or not."));
     66      Parameters.Add(new LookupParameter<DoubleValue>("SwarmBestQuality", "The swarm's best quality."));
     67      Parameters.Add(new LookupParameter<DoubleValue>("PreviousBestQuality", "The best quality of the previous iteration."));
     68      Parameters.Add(new LookupParameter<ITopologyInitializer>("TopologyInitializer", "The topology initializer is called again in case no improvement is made."));
    9369      Parameters.Add(new ScopeTreeLookupParameter<IntArray>("Neighbors", "The list of neighbors for each particle."));
    94       Parameters.Add(new LookupParameter<IntValue>("CurrentIteration", "The current iteration of the algorithm."));
    95       Parameters.Add(new ValueLookupParameter<IntValue>("RegroupingPeriod", "Update interval (=iterations) for regrouping of neighborhoods.", new IntValue(5)));
    9670    }
    9771    public override IDeepCloneable Clone(Cloner cloner) {
    98       return new MultiPSOTopologyUpdater(this, cloner);
     72      return new SPSOAdaptiveRandomTopologyUpdater(this, cloner);
    9973    }
    10074    #endregion
    10175
    10276    public override IOperation Apply() {
    103       if (CurrentIteration > 0 && CurrentIteration % RegroupingPeriod == 0) {
    104         ItemArray<IntArray> neighbors = new ItemArray<IntArray>(SwarmSize);
     77      var swarmBest = SwarmBestQualityParameter.ActualValue;
     78      if (swarmBest == null) return base.Apply();
    10579
    106         var particles = Enumerable.Range(0, SwarmSize).ToList();
    107         for (int i = SwarmSize-1; i>0; i--) {
    108           int j = Random.Next(i+1);
    109           int t = particles[j];
    110           particles[j] = particles[i];
    111           particles[i] = t;
    112         }
     80      var previousBest = PreviousBestQualityParameter.ActualValue;
     81      if (previousBest == null) {
     82        PreviousBestQualityParameter.ActualValue = new DoubleValue(swarmBest.Value);
     83        return base.Apply();
     84      };
    11385
    114         for (int partitionNr = 0; partitionNr<NrOfSwarms; partitionNr++) {
    115           int start = partitionNr*SwarmSize/NrOfSwarms;
    116           int end = (partitionNr+1)*SwarmSize/NrOfSwarms;
    117           for (int i = start; i<end; i++)
    118             neighbors[particles[i]] = GetSegment(particles, start, end, i);
    119         }
     86      var successor = new OperationCollection(new[] { base.Apply() });
     87      var max = MaximizationParameter.ActualValue.Value;
     88      if (max && swarmBest.Value >= previousBest.Value
     89        || !max && swarmBest.Value <= previousBest.Value)
     90        successor.Insert(0, ExecutionContext.CreateOperation(TopologyInitializerParameter.ActualValue));
    12091
    121         Neighbors = neighbors;
    122       }
    123       return base.Apply();
    124     }
    125 
    126     public static IntArray GetSegment(IEnumerable<int> list, int start, int end, int excludedIndex) {
    127       return new IntArray(list
    128         .Skip(start)
    129         .Take(end-start)
    130         .Where((p, j) => start+j != excludedIndex)
    131         .ToArray());
     92      previousBest.Value = swarmBest.Value;
     93      return successor;
    13294    }
    13395  }

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/HeuristicLab.Algorithms.ParticleSwarmOptimization-3.3.csproj

    r11623 r15181  
    113113  </ItemGroup>
    114114  <ItemGroup>
     115    <Compile Include="AdaptiveRandomTopologyUpdater.cs" />
    115116    <Compile Include="MultiPSOTopologyUpdater.cs" />
    116117    <Compile Include="ParticleSwarmOptimizationMainLoop.cs" />
    117118    <Compile Include="Plugin.cs" />
     119    <Compile Include="SPSORandomTopologyInitializer.cs" />
    118120    <Compile Include="RandomTopologyInitializer.cs" />
    119121    <Compile Include="VonNeumannTopologyInitializer.cs" />

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/MultiPSOTopologyUpdater.cs

    r14185 r15181  
    3333  [Item("Multi PSO Topology Updater", "Splits swarm into NrOfSwarms non-overlapping sub-swarms. Swarms are re-grouped every regroupingPeriod iteration. The operator is implemented as described in Liang, J.J. and Suganthan, P.N 2005. Dynamic multi-swarm particle swarm optimizer. IEEE Swarm Intelligence Symposium, pp. 124-129.")]
    3434  [StorableClass]
    35   public sealed class MultiPSOTopologyUpdater : SingleSuccessorOperator, ITopologyUpdater {
     35  public sealed class MultiPSOTopologyUpdater : SingleSuccessorOperator, ITopologyUpdater, IStochasticOperator {
    3636
    3737    public override bool CanChangeName {

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

    r15102 r15181  
    177177      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
    178178      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(20)));
     179      Parameters.Add(new ValueParameter<IntValue>("SwarmSize", "Size of the particle swarm.", new IntValue(40)));
    180180      Parameters.Add(new ValueParameter<IntValue>("MaxIterations", "Maximal number of iterations.", new IntValue(1000)));
    181181      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.8)));
     182      Parameters.Add(new ValueParameter<DoubleValue>("Inertia", "Inertia weight on a particle's movement (omega).", new DoubleValue(0.721)));
    183183      Parameters.Add(new ValueParameter<DoubleValue>("PersonalBestAttraction", "Weight for particle's pull towards its personal best soution (phi_p).", new DoubleValue(1)));
    184184      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(1)));

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/ParticleSwarmOptimizationMainLoop.cs

    r14185 r15181  
    122122      Placeholder evaluatorPlaceholder = new Placeholder();
    123123      Placeholder analyzerPlaceholder = new Placeholder();
     124      Placeholder analyzer2Placeholder = new Placeholder();
    124125      UniformSubScopesProcessor uniformSubScopeProcessor = new UniformSubScopesProcessor();
    125126      Placeholder particleUpdaterPlaceholder = new Placeholder();
    … …  
    192193      conditionalBranch.ConditionParameter.ActualName = "ContinueIteration";
    193194      conditionalBranch.TrueBranch = analyzerPlaceholder;
     195      conditionalBranch.FalseBranch = analyzer2Placeholder;
     196
     197      analyzer2Placeholder.Name = "(Analyzer)";
     198      analyzer2Placeholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
    194199      #endregion
    195200    }

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/RandomTopologyInitializer.cs

    r15091 r15181  
    3030
    3131namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    32   [Item("Random Topology Initializer", "Randomly connectes every particle with k other particles.")]
     32  [Item("Random Topology Initializer", "Each particle is informed by exactly k+1 distinct other particles (including itself).")]
    3333  [StorableClass]
    3434  public sealed class RandomTopologyInitializer : TopologyInitializer, IStochasticOperator {
    … …  
    6565        var numbers = Enumerable.Range(0, swarmSize).ToList();
    6666        numbers.RemoveAt(i);
    67         var selectedNumbers = new List<int>(nrOfConnections);
     67        var selectedNumbers = new List<int>(nrOfConnections + 1);
     68        selectedNumbers.Add(i);
    6869        for (int j = 0; j < nrOfConnections && numbers.Count > 0; j++) {
    6970          int index = random.Next(numbers.Count);

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/RingTopologyInitializer.cs

    r15091 r15181  
    2626
    2727namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    28   [Item("Ring Topology Initializer", "Connected every particle with its preceeding and its following particle.")]
     28  [Item("Ring Topology Initializer", "Each particle is informed by its preceeding and its succeeding particle wrapping around at the beginning and the end of the swarm (in addition each particle also informs itself).")]
    2929  [StorableClass]
    3030  public sealed class RingTopologyInitializer : TopologyInitializer {
    … …  
    4747      ItemArray<IntArray> neighbors = new ItemArray<IntArray>(swarmSize);
    4848      for (int i = 0; i < swarmSize; i++) {
    49         neighbors[i] = new IntArray(new[] { (swarmSize + i - 1) % swarmSize, (i + 1) % swarmSize });
     49        neighbors[i] = new IntArray(new[] { (swarmSize + i - 1) % swarmSize, i, (i + 1) % swarmSize });
    5050      }
    5151      NeighborsParameter.ActualValue = neighbors;

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/SPSORandomTopologyInitializer.cs

    r15167 r15181  
    3030
    3131namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    32   [Item("Random Topology Initializer", "Randomly connectes every particle with k other particles.")]
     32  [Item("SPSO Random Topology Initializer", "Each particle informs k+1 other particles (including itself). The same particle (including itself) can be informed multiple times.")]
    3333  [StorableClass]
    34   public sealed class RandomTopologyInitializer : TopologyInitializer, IStochasticOperator {
     34  public sealed class SPSORandomTopologyInitializer : TopologyInitializer, IStochasticOperator {
    3535    #region Parameters
    3636    public ILookupParameter<IRandom> RandomParameter {
    3737      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    3838    }
    39     public IValueLookupParameter<IntValue> NrOfConnectionsParameter {
    40       get { return (IValueLookupParameter<IntValue>)Parameters["NrOfConnections"]; }
     39    public IValueLookupParameter<IntValue> KParameter {
     40      get { return (IValueLookupParameter<IntValue>)Parameters["K"]; }
    4141    }
    4242    #endregion
    … …  
    4444    #region Construction & Cloning
    4545    [StorableConstructor]
    46     private RandomTopologyInitializer(bool deserializing) : base(deserializing) { }
    47     private RandomTopologyInitializer(RandomTopologyInitializer original, Cloner cloner) : base(original, cloner) { }
    48     public RandomTopologyInitializer() {
     46    private SPSORandomTopologyInitializer(bool deserializing) : base(deserializing) { }
     47    private SPSORandomTopologyInitializer(SPSORandomTopologyInitializer original, Cloner cloner) : base(original, cloner) { }
     48    public SPSORandomTopologyInitializer() {
    4949      Parameters.Add(new LookupParameter<IRandom>("Random", "A random number generation."));
    50       Parameters.Add(new ValueLookupParameter<IntValue>("NrOfConnections", "Nr of connected neighbors.", new IntValue(3)));
     50      Parameters.Add(new ValueLookupParameter<IntValue>("K", "The number of informed particles (excluding itself).", new IntValue(3)));
    5151    }
    5252
    5353    public override IDeepCloneable Clone(Cloner cloner) {
    54       return new RandomTopologyInitializer(this, cloner);
     54      return new SPSORandomTopologyInitializer(this, cloner);
    5555    }
    5656    #endregion
    … …  
    5959      var random = RandomParameter.ActualValue;
    6060      var swarmSize = SwarmSizeParameter.ActualValue.Value;
    61       var nrOfConnections = NrOfConnectionsParameter.ActualValue.Value;
     61      var k = KParameter.ActualValue.Value;
    6262
    63       ItemArray<IntArray> neighbors = new ItemArray<IntArray>(swarmSize);
     63      // SPSO: Each particle informs at most K+1 particles (at least itself and K others)
     64      var particlesInform = Enumerable.Repeat(k + 1, swarmSize)
     65        .Select((v, i) => new HashSet<int>(Enumerable.Range(0, v).Select(x => x == 0 ? i : random.Next(swarmSize)))).ToList();
     66
     67      var neighbors = new ItemArray<IntArray>(swarmSize);
    6468      for (int i = 0; i < swarmSize; i++) {
    65         var numbers = Enumerable.Range(0, swarmSize).ToList();
    66         numbers.RemoveAt(i);
    67         var selectedNumbers = new List<int>(nrOfConnections);
    68         for (int j = 0; j < nrOfConnections && numbers.Count > 0; j++) {
    69           int index = random.Next(numbers.Count);
    70           selectedNumbers.Add(numbers[index]);
    71           numbers.RemoveAt(index);
    72         }
    73         neighbors[i] = new IntArray(selectedNumbers.ToArray());
     69        // calculate the informants for each particle
     70        var informants = particlesInform.Select((val, idx) => val.Contains(i) ? idx : -1).Where(x => x >= 0).ToArray();
     71        neighbors[i] = new IntArray(informants);
    7472      }
    7573      NeighborsParameter.ActualValue = neighbors;

  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/VonNeumannTopologyInitializer.cs

    r15091 r15181  
    2626
    2727namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    28   [Item("Von Neumann Topology Initializer", "Every particle is connected with the two following and the two previous particles wrapping around at the beginning and the end of the population.")]
     28  [Item("Von Neumann Topology Initializer", "Every particle is informed by the two following and the two previous particles wrapping around at the beginning and the end of the swarm (in addition each particle also informs itself).")]
    2929  [StorableClass]
    3030  public sealed class VonNeumannTopologyInitializer : TopologyInitializer {
    … …  
    5151          (swarmSize + i-2) % swarmSize,
    5252          (swarmSize + i-1) % swarmSize,
     53          i,
    5354          (i+1) % swarmSize,
    5455          (i+2) % swarmSize
Note: See TracChangeset for help on using the changeset viewer.