Changeset 15181 for trunk/sources/HeuristicLab.Encodings.RealVectorEncoding

Timestamp:

07/10/17 17:26:43 (8 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.Encodings.RealVectorEncoding/3.3

Files:

• ParticleOperators/SPSO2011ParticleUpdater.cs (modified) (2 diffs)
• ParticleOperators/SPSOSwarmUpdater.cs (modified) (5 diffs)
• RealVector.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Encodings.RealVectorEncoding/3.3/ParticleOperators/SPSO2011ParticleUpdater.cs ¶

@@ -25 +25 @@
 using HeuristicLab.Data;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Encodings.RealVectorEncoding {
@@ -42 +43 @@
     public static void UpdateVelocity(IRandom random, RealVector velocity, double maxVelocity, RealVector position, double inertia, RealVector personalBest, double personalBestAttraction, RealVector neighborBest, double neighborBestAttraction, double c = 1.193) {
       var gravity = new double[velocity.Length];
-      var direct = new RealVector(velocity.Length);
+      var direction = new RealVector(velocity.Length);
       var radius = 0.0;
+
+      var nd = new NormalDistributedRandom(random, 0, 1);
 
       for (int i = 0; i < velocity.Length; i++) {
         var g_id = c * ((personalBest[i] + neighborBest[i] - 2 * position[i]) / 3.0);
+        // center of the hyper-sphere
         gravity[i] = g_id + position[i];
-        direct[i] = (random.NextDouble() - 0.5) * 2;
+        // a random direction vector uniform over the surface of hyper-sphere, see http://mathworld.wolfram.com/HyperspherePointPicking.html
+        direction[i] = nd.NextDouble();
         radius += g_id * g_id;
       }
 
+      // randomly choose a radius within the hyper-sphere
       radius = random.NextDouble() * Math.Sqrt(radius);
 
-      var unitscale = Math.Sqrt(direct.DotProduct(direct));
+      // unitscale is used to rescale the random direction vector to unit length, resp. length of the radius
+      var unitscale = Math.Sqrt(direction.DotProduct(direction));
       if (unitscale > 0) {
         for (var i = 0; i < velocity.Length; i++) {
-          velocity[i] = velocity[i] * inertia + gravity[i] + direct[i] * radius / unitscale - position[i];
+          var sampledPos = gravity[i] + direction[i] * radius / unitscale;
+          velocity[i] = velocity[i] * inertia + sampledPos - position[i];
         }
       }

trunk/sources/HeuristicLab.Encodings.RealVectorEncoding/3.3/ParticleOperators/SPSOSwarmUpdater.cs ¶

@@ -34 +34 @@
 
 namespace HeuristicLab.Encodings.RealVectorEncoding {
-  [Item("Swarm Updater (SPSO)", "Updates personal best point and quality as well as global best point and quality.")]
+  [Item("Swarm Updater (SPSO)", "Updates personal best point and quality as well as neighbor best point and quality.")]
   [StorableClass]
   public sealed class SPSOSwarmUpdater : SingleSuccessorOperator, IRealVectorSwarmUpdater, ISingleObjectiveOperator {
@@ -126 +126 @@
       Parameters.Add(new ScopeTreeLookupParameter<IntArray>("Neighbors", "The list of neighbors for each particle."));
       Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
-      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaxVelocity", "Speed limit for each particle.", new DoubleValue(1000000)));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("MaxVelocity", "The maximum velocity for each particle and initial velocity if scaling is used.", new DoubleValue(double.MaxValue)));
       Parameters.Add(new LookupParameter<DoubleValue>("CurrentMaxVelocity", "Current value of the speed limit."));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "Results"));
@@ -132 +132 @@
       #region Max Velocity Updating
       Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("MaxVelocityScalingOperator", "Modifies the value"));
-      Parameters.Add(new ValueLookupParameter<DoubleValue>("FinalMaxVelocity", "The value of maximum velocity if PSO has reached maximum iterations.", new DoubleValue(1E-10)));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("FinalMaxVelocity", "The value of maximum velocity if scaling is used and PSO has reached maximum iterations.", new DoubleValue(1E-10)));
       Parameters.Add(new LookupParameter<IntValue>("MaxVelocityIndex", "The current index.", "Iterations"));
       Parameters.Add(new ValueLookupParameter<IntValue>("MaxVelocityStartIndex", "The start index at which to start modifying 'Value'.", new IntValue(0)));
@@ -195 +195 @@
         var neighborBest = new ItemArray<RealVector>(neighbors.Length);
         var neighborBestQuality = new ItemArray<DoubleValue>(neighbors.Length);
+        double overallBest = double.NaN;
+        RealVector overallBestVector = null;
         for (int n = 0; n < neighbors.Length; n++) {
-          var pairs = particles.Where(x => x.Item1 == n || neighbors[n].Contains(x.Item1));
-          var bestNeighbor = (maximization ? pairs.MaxItems(p => p.Item3)
-                                           : pairs.MinItems(p => p.Item3)).First();
+          var neighborhood = particles.Where(x => neighbors[n].Contains(x.Item1));
+          var bestNeighbor = (maximization ? neighborhood.MaxItems(p => p.Item3)
+                                           : neighborhood.MinItems(p => p.Item3)).First();
           neighborBest[n] = bestNeighbor.Item2;
           neighborBestQuality[n] = new DoubleValue(bestNeighbor.Item3);
+          if (double.IsNaN(overallBest) || maximization && bestNeighbor.Item3 > overallBest
+            || !maximization && bestNeighbor.Item3 < overallBest) {
+            overallBest = bestNeighbor.Item3;
+            overallBestVector = bestNeighbor.Item2;
+          }
         }
         NeighborBestParameter.ActualValue = neighborBest;
         NeighborBestQualityParameter.ActualValue = neighborBestQuality;
+        SwarmBestQualityParameter.ActualValue = new DoubleValue(overallBest);
+        BestRealVectorParameter.ActualValue = overallBestVector;
       } else {
         // Neighbor best = Global best
         var best = maximization ? particles.MaxItems(x => x.Item3).First() : particles.MinItems(x => x.Item3).First();
-        NeighborBestParameter.ActualValue = new ItemArray<RealVector>(particles.Select(x => best.Item2));
-        NeighborBestQualityParameter.ActualValue = new ItemArray<DoubleValue>(particles.Select(x => new DoubleValue(best.Item3)));
+        NeighborBestParameter.ActualValue = new ItemArray<RealVector>(Enumerable.Repeat(best.Item2, particles.Count));
+        NeighborBestQualityParameter.ActualValue = new ItemArray<DoubleValue>(Enumerable.Repeat(new DoubleValue(best.Item3), particles.Count));
+        SwarmBestQualityParameter.ActualValue = new DoubleValue(best.Item3);
+        BestRealVectorParameter.ActualValue = best.Item2;
       }
     }
@@ -224 +235 @@
           !maximization && p.Item3 < personalBestQuality[p.Item1].Value) {
           personalBestQuality[p.Item1].Value = p.Item3;
-          personalBest[p.Item1] = (RealVector)p.Item2.Clone();
+          personalBest[p.Item1] = new RealVector(p.Item2);
         }
       }

trunk/sources/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVector.cs ¶

@@ -45 +45 @@
         array[i] = elements[i];
     }
+    public RealVector(RealVector other)
+      : this(other.Length) {
+      Array.Copy(other.array, array, other.Length);
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {