Menu
▾
▴
[cilib-devel] [PATCH] Corrected Constriction PSO.
|
From: Andrich v. W. <avw...@gm...> - 2009-07-15 11:41:06
|
Corrected the ConstrictionVelocityUpdate: The constriction coefficient has to be calculated only
once during the course of the algorithm (as opposed to every time it is used) similar to inertia.
The calculation also uses c1 and c2 WITHOUT the randomization of r1 and r2. Resulting implementation
delivers good results that are very similar to those reported by reference papers.
---
.../ConstrictionVelocityUpdate.java | 112 +++++++++++---------
.../ConstrictionVelocityUpdateTest.java | 76 ++++++++++----
xml/constrictionPSO.xml | 24 +++--
3 files changed, 134 insertions(+), 78 deletions(-)
diff --git a/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
index 86b0e4c..54542bf 100644
--- a/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
+++ b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
@@ -29,33 +29,28 @@ import net.sourceforge.cilib.type.types.container.Vector;
/**
* A velocity update strategy that utilizes the constriction coefficient as
- * developed by Clerc.
+ * developed by M. Clerc.
* <p>References:
* <ul>
* <li>
* <pre>
-{@literal @}INPROCEEDINGS{785513,
-title={The swarm and the queen: towards a deterministic and adaptive particle swarm optimization},
-author={Clerc, M.},
-booktitle={Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on},
-year={1999},
+{@literal @}@INPROCEEDINGS{870279,
+title={Comparing inertia weights and constriction factors in particle swarm optimization},
+author={Eberhart, R.C. and Shi, Y.},
+booktitle={Evolutionary Computation, 2000. Proceedings of the 2000 Congress on},
+year={2000},
month={},
-volume={3},
+volume={1},
number={},
-pages={-1957 Vol. 3},
-abstract={A very simple particle swarm optimization iterative algorithm is presented, with just
-one equation and one social/confidence parameter. We define a âno-hopeâ convergence criterion and
-a ârehopeâ method so that, from time to time, the swarm re-initializes its position, according to
-some gradient estimations of the objective function and to the previous re-initialization (it means
-it has a kind of very rudimentary memory). We then study two different cases, a quite âeasyâ one
-(the Alpine function) and a âdifficultâ one (the Banana function), but both just in dimension two.
-The process is improved by taking into account the swarm gravity center (the âqueenâ) and the results
-are good enough so that it is certainly worthwhile trying the method on more complex problems},
-keywords={adaptive systems, deterministic algorithms, evolutionary computation, iterative methodsAlpine function,
-Banana function, adaptive particle swarm optimization, gradient estimations, no-hope convergence criterion,
-objective function, queen, re-initialization, rehope method, rudimentary memory, simple particle swarm
-optimization iterative algorithm, social/confidence parameter, swarm gravity center},
-doi={10.1109/CEC.1999.785513},
+pages={84-88 vol.1},
+abstract={The performance of particle swarm optimization using an inertia weight is compared
+with performance using a constriction factor. Five benchmark functions are used for the
+comparison. It is concluded that the best approach is to use the constriction factor while
+limiting the maximum velocity Vmax to the dynamic range of the variable Xmax on each
+dimension. This approach provides performance on the benchmark functions superior to any
+other published results known by the authors},
+keywords={evolutionary computationbenchmark functions, constriction factors, inertia weights, particle swarm optimization},
+doi={10.1109/CEC.2000.870279},
ISSN={}, }
</pre>
* </li>
@@ -89,21 +84,22 @@ ISSN={1089-778X}, }
* </ul>
*
* <p>
- * Note, this strategy does not the inertia control parameter.
+ * Note, this strategy does not use the inertia control parameter.
* Certain constraints are imposed on the other control parameters in order to
* calculate the constriction coefficient, namely:
- * $c1r1 + c2r2 \leq 4$ , and
+ * $c1 + c2 \leq 4$ , and
* $\kappa \in [0, 1]$
*
* @author andrich
*/
public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
- private static final long serialVersionUID = -4470110903487138758L;
+ private static final long serialVersionUID = -4470110903487138758L;
private ControlParameter socialAcceleration;
private ControlParameter cognitiveAcceleration;
private ControlParameter vMax;
private ControlParameter kappa;
+ private ControlParameter constrictionCoefficient;
/**
* Default constructor. The values given to the control parameters attempt to
@@ -115,11 +111,12 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
cognitiveAcceleration = new RandomizingControlParameter();
vMax = new ConstantControlParameter();
kappa = new ConstantControlParameter();
+ constrictionCoefficient = null;
- socialAcceleration.setParameter(3.0);
- cognitiveAcceleration.setParameter(3.0);
+ socialAcceleration.setParameter(2.05);
+ cognitiveAcceleration.setParameter(2.05);
+ kappa.setParameter(1.0);
vMax.setParameter(Double.MAX_VALUE);
- kappa.setParameter(0.1);
}
/**
@@ -146,8 +143,10 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
*/
@Override
public void updateVelocity(Particle particle) {
- assertAccelerationConstraints();
-
+ // lazy construction (necessary to do this after user has set c1 and c2, and to only do it once per particle).
+ if (constrictionCoefficient == null) {
+ calculateConstrictionCoefficient();
+ }
Vector velocity = (Vector) particle.getVelocity();
Vector position = (Vector) particle.getPosition();
Vector bestPosition = (Vector) particle.getBestPosition();
@@ -155,22 +154,9 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
for (int i = 0; i < particle.getDimension(); ++i) {
- // calculate the constriction coefficient
- double c1 = cognitiveAcceleration.getParameter();
- double c2 = socialAcceleration.getParameter();
- // c1r1 + c2r2 has to be greater or equal to 4
- while ((c1 + c2) < 4) {
- c1 = cognitiveAcceleration.getParameter();
- c2 = socialAcceleration.getParameter();
- }
- double phi = c1 + c2;
- double constrictionCoefficient = (2 * kappa.getParameter()) /
- Math.abs(2 - phi - Math.sqrt(phi * (phi - 4.0)));
-
- double value = velocity.getReal(i) +
- (bestPosition.getReal(i) - position.getReal(i)) * c1 +
- (nBestPosition.getReal(i) - position.getReal(i)) * c2;
- value = constrictionCoefficient * value;
+ double value = constrictionCoefficient.getParameter() * (velocity.getReal(i) +
+ (bestPosition.getReal(i) - position.getReal(i)) * cognitiveAcceleration.getParameter() +
+ (nBestPosition.getReal(i) - position.getReal(i)) * socialAcceleration.getParameter());
velocity.setReal(i, value);
clamp(velocity, i);
@@ -206,17 +192,25 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
}
/**
- * Ensure that values of c1 and c2 make it possible to calculate the
- * constriction coefficient.
+ * Calculate the constriction coefficient as well as the
+ * maximum acceleration.
*/
- private void assertAccelerationConstraints() {
+ private void calculateConstrictionCoefficient() {
double c1 = ((RandomizingControlParameter) cognitiveAcceleration).getControlParameter().getParameter();
double c2 = ((RandomizingControlParameter) socialAcceleration).getControlParameter().getParameter();
- if (c1 + c2 < 4) {
+
+ double phi = c1 + c2;
+ if (phi < 4.0) {
throw new UnsupportedOperationException("Parameter constraint violation: " +
"The sum of the Cognitive (" + c1 + ") and Social (" + c2 + ") acceleration parameters " +
"has to be greater than or equal to 4.");
}
+ double chi;
+ chi = (2 * kappa.getParameter()) /
+ Math.abs(2 - phi - Math.sqrt(phi * (phi - 4.0)));
+
+ constrictionCoefficient = new ConstantControlParameter();
+ constrictionCoefficient.setParameter(chi);
}
/**
@@ -271,7 +265,7 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
* Get the maximum velocity parameter.
* @return the maximum velocity {@link ControlParameter control parameter }.
*/
- public ControlParameter getVMax() {
+ public ControlParameter getvMax() {
return vMax;
}
@@ -279,7 +273,23 @@ public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
* Set the maximum velocity parameter.
* @param vMax the new maximum velocity {@link ControlParameter control parameter }.
*/
- public void setVMax(ControlParameter vMax) {
+ public void setvMax(ControlParameter vMax) {
this.vMax = vMax;
}
+
+ /**
+ * Gets the constriction coefficient.
+ * @return the constriction coefficient {@link ControlParameter control parameter }.
+ */
+ public ControlParameter getConstrictionCoefficient() {
+ return constrictionCoefficient;
+ }
+
+ /**
+ * Sets the constriction coefficient.
+ * @param constrictionCoefficient the new constriction coefficient {@link ControlParameter control parameter }.
+ */
+ public void setConstrictionCoefficient(ControlParameter constrictionCoefficient) {
+ this.constrictionCoefficient = constrictionCoefficient;
+ }
}
diff --git a/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
index 45e701a..b7133f7 100644
--- a/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
+++ b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
@@ -47,6 +47,7 @@ import org.junit.runner.RunWith;
*/
@RunWith(JMock.class)
public class ConstrictionVelocityUpdateTest {
+
private Mockery mockery = new JUnit4Mockery();
/**
@@ -58,25 +59,25 @@ public class ConstrictionVelocityUpdateTest {
ConstrictionVelocityUpdate copy = original.getClone();
Assert.assertEquals(original.getKappa().getParameter(), copy.getKappa().getParameter(), Maths.EPSILON);
- Assert.assertEquals(original.getVMax().getParameter(), copy.getVMax().getParameter(), Maths.EPSILON);
- Assert.assertEquals(((RandomizingControlParameter)original.getCognitiveAcceleration()).getControlParameter().getParameter(),
- ((RandomizingControlParameter)copy.getCognitiveAcceleration()).getControlParameter().getParameter(), Maths.EPSILON);
- Assert.assertEquals(((RandomizingControlParameter)original.getSocialAcceleration()).getControlParameter().getParameter(),
- ((RandomizingControlParameter)copy.getSocialAcceleration()).getControlParameter().getParameter(), Maths.EPSILON);
+ Assert.assertEquals(original.getvMax().getParameter(), copy.getvMax().getParameter(), Maths.EPSILON);
+ Assert.assertEquals(((RandomizingControlParameter) original.getCognitiveAcceleration()).getControlParameter().getParameter(),
+ ((RandomizingControlParameter) copy.getCognitiveAcceleration()).getControlParameter().getParameter(), Maths.EPSILON);
+ Assert.assertEquals(((RandomizingControlParameter) original.getSocialAcceleration()).getControlParameter().getParameter(),
+ ((RandomizingControlParameter) copy.getSocialAcceleration()).getControlParameter().getParameter(), Maths.EPSILON);
copy.setKappa(new ConstantControlParameter(0.7));
- copy.setVMax(new ConstantControlParameter(0.7));
+ copy.setvMax(new ConstantControlParameter(0.7));
RandomizingControlParameter randomizingControlParameter = new RandomizingControlParameter();
randomizingControlParameter.setParameter(4.0);
copy.setSocialAcceleration(randomizingControlParameter.getClone());
copy.setCognitiveAcceleration(randomizingControlParameter.getClone());
Assert.assertFalse(Double.compare(original.getKappa().getParameter(), copy.getKappa().getParameter()) == 0);
- Assert.assertFalse(Double.compare(original.getVMax().getParameter(), copy.getVMax().getParameter()) == 0);
- Assert.assertFalse(Double.compare(((RandomizingControlParameter)original.getCognitiveAcceleration()).getControlParameter().getParameter(),
- ((RandomizingControlParameter)copy.getCognitiveAcceleration()).getControlParameter().getParameter()) == 0);
- Assert.assertFalse(Double.compare(((RandomizingControlParameter)original.getSocialAcceleration()).getControlParameter().getParameter(),
- ((RandomizingControlParameter)copy.getSocialAcceleration()).getControlParameter().getParameter()) == 0);
+ Assert.assertFalse(Double.compare(original.getvMax().getParameter(), copy.getvMax().getParameter()) == 0);
+ Assert.assertFalse(Double.compare(((RandomizingControlParameter) original.getCognitiveAcceleration()).getControlParameter().getParameter(),
+ ((RandomizingControlParameter) copy.getCognitiveAcceleration()).getControlParameter().getParameter()) == 0);
+ Assert.assertFalse(Double.compare(((RandomizingControlParameter) original.getSocialAcceleration()).getControlParameter().getParameter(),
+ ((RandomizingControlParameter) copy.getSocialAcceleration()).getControlParameter().getParameter()) == 0);
}
/**
@@ -99,9 +100,44 @@ public class ConstrictionVelocityUpdateTest {
velocityUpdate.updateVelocity(particle);
Vector velocity = (Vector) particle.getVelocity();
- Assert.assertEquals(0.09831319691873514, velocity.getReal(0), Maths.EPSILON);
+ Assert.assertEquals(1.2189730956981684, velocity.getReal(0), Maths.EPSILON);
+ } finally {
+ Seeder.setSeederStrategy(strategy);
}
- finally {
+ }
+
+ @Test
+ public void testConstrictionCalculation() {
+ SeedSelectionStrategy strategy = Seeder.getSeederStrategy();
+ Seeder.setSeederStrategy(new ZeroSeederStrategy());
+
+ try {
+ ConstrictionVelocityUpdate velocityUpdate = new ConstrictionVelocityUpdate();
+ Particle particle = createParticle(Vectors.create(0.0));
+ particle.setVelocityUpdateStrategy(velocityUpdate);
+ Particle nBest = createParticle(Vectors.create(1.0));
+ particle.setNeighbourhoodBest(nBest);
+ nBest.setNeighbourhoodBest(nBest);
+ Particle clone = particle.getClone();
+
+ particle.getVelocityUpdateStrategy().updateVelocity(particle);
+ clone.getVelocityUpdateStrategy().updateVelocity(particle);
+
+ double kappa = 1.0;
+ double c1 = 2.05;
+ double c2 = 2.05;
+ double phi = c1 + c2;
+ double chi = (2 * kappa) / Math.abs(2 - phi - Math.sqrt(phi * phi - 4.0 * phi)); //this was not copied from the implementation.
+
+ //verify implementation maths is correct.
+ Assert.assertEquals(chi, velocityUpdate.getConstrictionCoefficient().getParameter(), Maths.EPSILON);
+ //verify it is the same for two particles.
+
+ Assert.assertEquals(((ConstrictionVelocityUpdate) particle.getVelocityUpdateStrategy()).getConstrictionCoefficient().getParameter(),
+ ((ConstrictionVelocityUpdate) clone.getVelocityUpdateStrategy()).getConstrictionCoefficient().getParameter(), Maths.EPSILON);
+
+
+ } finally {
Seeder.setSeederStrategy(strategy);
}
}
@@ -115,7 +151,7 @@ public class ConstrictionVelocityUpdateTest {
return particle;
}
- @Test(expected=UnsupportedOperationException.class)
+ @Test(expected = UnsupportedOperationException.class)
public void illegalVelocityUpdate() {
final Particle particle = mockery.mock(Particle.class);
@@ -124,9 +160,12 @@ public class ConstrictionVelocityUpdateTest {
velocityUpdate.setCognitiveAcceleration(randomizingControlParameter);
velocityUpdate.setSocialAcceleration(randomizingControlParameter);
- mockery.checking(new Expectations() {{
- ignoring(particle);
- }});
+ mockery.checking(new Expectations() {
+
+ {
+ ignoring(particle);
+ }
+ });
velocityUpdate.updateVelocity(particle);
}
@@ -142,7 +181,7 @@ public class ConstrictionVelocityUpdateTest {
nBest.setNeighbourhoodBest(nBest);
ConstrictionVelocityUpdate constrictionVelocityUpdate = new ConstrictionVelocityUpdate();
- constrictionVelocityUpdate.setVMax(new ConstantControlParameter(0.5));
+ constrictionVelocityUpdate.setvMax(new ConstantControlParameter(0.5));
constrictionVelocityUpdate.updateVelocity(particle);
Vector velocity = (Vector) particle.getVelocity();
@@ -152,5 +191,4 @@ public class ConstrictionVelocityUpdateTest {
}
}
-
}
diff --git a/xml/constrictionPSO.xml b/xml/constrictionPSO.xml
index 6ce91a3..ab1f795 100644
--- a/xml/constrictionPSO.xml
+++ b/xml/constrictionPSO.xml
@@ -10,31 +10,34 @@
<initialisationStrategy class="algorithm.initialisation.ClonedPopulationInitialisationStrategy">
<entityType class="pso.particle.StandardParticle">
<velocityUpdateStrategy class="pso.velocityupdatestrategies.ConstrictionVelocityUpdate">
- <kappa class="controlparameter.ConstantControlParameter" parameter="0.1" />
- <socialAcceleration class="controlparameter.RandomizingControlParameter" parameter="3.0" />
- <cognitiveAcceleration class="controlparameter.RandomizingControlParameter" parameter="3.0" />
+ <kappa class="controlparameter.ConstantControlParameter" parameter="1.0"/>
+ <socialAcceleration class="controlparameter.RandomizingControlParameter" parameter="2.05" />
+ <cognitiveAcceleration class="controlparameter.RandomizingControlParameter" parameter="2.05" />
<!--vMax class="controlparameter.ConstantControlParameter" parameter="0.1" /-->
</velocityUpdateStrategy>
</entityType>
</initialisationStrategy>
<topology class="entity.topologies.GBestTopology"/>
- <addStoppingCondition class="stoppingcondition.MaximumIterations" maximumIterations="1000"/>
+ <addStoppingCondition class="stoppingcondition.MaximumIterations" maximumIterations="2000"/>
</algorithm>
</algorithms>
<problems>
<problem id="spherical" class="problem.FunctionMinimisationProblem">
- <function class="functions.continuous.unconstrained.Spherical"/>
+ <function class="functions.continuous.unconstrained.Spherical" domain="R(-20.0, 20.0)^30"/>
</problem>
<problem id="rosenbrock" class="problem.FunctionMinimisationProblem">
- <function class="functions.continuous.unconstrained.Rosenbrock"/>
+ <function class="functions.continuous.unconstrained.Rosenbrock" domain="R(-10.0, 10.0)^30"/>
</problem>
<problem id="rastrigin" class="problem.FunctionMinimisationProblem">
- <function class="functions.continuous.unconstrained.Rastrigin"/>
+ <function class="functions.continuous.unconstrained.Rastrigin" domain="R(-5.12, 5.12)^30"/>
+ </problem>
+ <problem id="griewank" class="problem.FunctionMinimisationProblem">
+ <function class="functions.continuous.unconstrained.Griewank" domain="R(-300, 300)^30"/>
</problem>
</problems>
- <measurements id="fitness" class="simulator.MeasurementSuite" resolution="10" samples="1">
+ <measurements id="fitness" class="simulator.MeasurementSuite" resolution="10" samples="50">
<addMeasurement class="measurement.single.Fitness"/>
</measurements>
<simulations>
@@ -53,5 +56,10 @@
<problem idref="rastrigin"/>
<measurements idref="fitness" file="data/constrictionpso_rastrigin.txt"/>
</simulation>
+ <simulation>
+ <algorithm idref="constrictionPSO"/>
+ <problem idref="griewank"/>
+ <measurements idref="fitness" file="data/constrictionpso_griewank.txt"/>
+ </simulation>
</simulations>
</simulator>
--
1.6.0.4
|
