Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/02/11 15:22:54 (13 years ago)
Author:
epitzer
Message:

Additional improvements to PSO (#852)

  • simplify and clean up RealVectorSwarmUpdater
  • make the RealVectorParticleCreator an AlgorithmOperator
  • standardize naming of local variables in ParticleUpdaters
  • remove default parameter values from main loop
  • new implementation of MultiPSOTopologyUpdater (using shuffling)
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Algorithms.ParticleSwarmOptimization/3.3/MultiPSOTopologyUpdater.cs

    r5560 r5592  
    3131
    3232namespace HeuristicLab.Algorithms.ParticleSwarmOptimization {
    33   [Item("Multi PSO Topology Updater", "Splits swarm into swarmsize / (nrOfConnections + 1) 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("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]
    3535  public sealed class MultiPSOTopologyUpdater : SingleSuccessorOperator, ITopologyUpdater {
     36
    3637    public override bool CanChangeName {
    3738      get { return false; }
     
    4243      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    4344    }
    44     public IValueLookupParameter<IntValue> NrOfConnectionsParameter {
    45       get { return (IValueLookupParameter<IntValue>)Parameters["NrOfConnections"]; }
     45    public IValueLookupParameter<IntValue> NrOfSwarmsParameter {
     46      get { return (IValueLookupParameter<IntValue>)Parameters["NrOfSwarms"]; }
    4647    }
    4748    public ILookupParameter<IntValue> SwarmSizeParameter {
     
    6364      get { return RandomParameter.ActualValue; }
    6465    }
    65     private int NrOfConnections {
    66       get { return NrOfConnectionsParameter.ActualValue.Value; }
     66    private int NrOfSwarms {
     67      get { return NrOfSwarmsParameter.ActualValue.Value; }
    6768    }
    6869    private int SwarmSize {
     
    8182    #endregion
    8283
     84    #region Construction & Cloning
    8385    [StorableConstructor]
    8486    private MultiPSOTopologyUpdater(bool deserializing) : base(deserializing) { }
    8587    private MultiPSOTopologyUpdater(MultiPSOTopologyUpdater original, Cloner cloner) : base(original, cloner) { }
    86    
    8788    public MultiPSOTopologyUpdater()
    8889      : base() {
    8990      Parameters.Add(new LookupParameter<IRandom>("Random", "A random number generator."));
    90       Parameters.Add(new ValueLookupParameter<IntValue>("NrOfConnections", "Nr of connected neighbors.", new IntValue(3)));
     91      Parameters.Add(new ValueLookupParameter<IntValue>("NrOfSwarms", "Nr of connected sub-swarms.", new IntValue(3)));
    9192      Parameters.Add(new LookupParameter<IntValue>("SwarmSize", "Number of particles in the swarm."));
    9293      Parameters.Add(new ScopeTreeLookupParameter<IntArray>("Neighbors", "The list of neighbors for each particle."));
     
    9495      Parameters.Add(new ValueLookupParameter<IntValue>("RegroupingPeriod", "Update interval (=iterations) for regrouping of neighborhoods.", new IntValue(5)));
    9596    }
    96 
    9797    public override IDeepCloneable Clone(Cloner cloner) {
    9898      return new MultiPSOTopologyUpdater(this, cloner);
    9999    }
     100    #endregion
    100101
    101     // Splits the swarm into non-overlapping sub swarms
    102102    public override IOperation Apply() {
    103103      if (CurrentIteration > 0 && CurrentIteration % RegroupingPeriod == 0) {
    104104        ItemArray<IntArray> neighbors = new ItemArray<IntArray>(SwarmSize);
    105         Dictionary<int, List<int>> neighborsPerParticle = new Dictionary<int, List<int>>();
    106         for (int i = 0; i < SwarmSize; i++) {
    107           neighborsPerParticle.Add(i, new List<int>());
     105
     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;
    108112        }
    109113
    110         // partition swarm into groups
    111         Dictionary<int, List<int>> groups = new Dictionary<int, List<int>>();
    112         int groupId = 0;
    113         var numbers = Enumerable.Range(0, SwarmSize).ToList();
    114         for (int i = 0; i < SwarmSize; i++) {
    115           int nextParticle = numbers[Random.Next(0, numbers.Count)];
    116           if (!groups.ContainsKey(groupId)) {
    117             groups.Add(groupId, new List<int>());
    118           }
    119           groups[groupId].Add(nextParticle);
    120           if (groups[groupId].Count - 1 == NrOfConnections) {
    121             groupId++;
    122           }
    123           numbers.Remove(nextParticle);
     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);
    124119        }
    125120
    126         // add neighbors to each particle
    127         foreach (List<int> group in groups.Values) {
    128           foreach (int sib1 in group) {
    129             foreach (int sib2 in group) {
    130               if (sib1 != sib2 && !neighborsPerParticle[sib1].Contains(sib2)) {
    131                 neighborsPerParticle[sib1].Add(sib2);
    132               }
    133             }
    134           }
    135         }
    136 
    137         for (int particle = 0; particle < neighborsPerParticle.Count; particle++) {
    138           neighbors[particle] = new IntArray(neighborsPerParticle[particle].ToArray());
    139         }
    140121        Neighbors = neighbors;
    141122      }
    142123      return base.Apply();
    143124    }
     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());
     132    }
    144133  }
    145134}
Note: See TracChangeset for help on using the changeset viewer.