Menu
▾
▴
Re: [cilib-devel] [PATCH] Corrected Constriction PSO.
|
From: Gary P. <gpa...@gm...> - 2009-07-15 13:55:34
|
Thanks Andrich.
The patch looks much better. I've applied the patch and merged it into next.
Regards,
Gary
On Wednesday 15 July 2009 13:24:14 Andrich van Wyk wrote:
> 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/Constric
>tionVelocityUpdate.java
> b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdate.java index 86b0e4c..54542bf 100644
> ---
> a/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdate.java +++
> b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdate.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/Constric
>tionVelocityUpdateTest.java
> b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdateTest.java index 45e701a..b7133f7 100644
> ---
> a/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdateTest.java +++
> b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/Constric
>tionVelocityUpdateTest.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.getCognitiveAcce
>leration()).getControlParameter().getParameter(), -
> ((RandomizingControlParameter)copy.getCognitiveAcceleration()).getControlPa
>rameter().getParameter(), Maths.EPSILON); -
> Assert.assertEquals(((RandomizingControlParameter)original.getSocialAcceler
>ation()).getControlParameter().getParameter(), -
> ((RandomizingControlParameter)copy.getSocialAcceleration()).getControlParam
>eter().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.ge
>tCognitiveAcceleration()).getControlParameter().getParameter(), -
>
> ((RandomizingControlParameter)copy.getCognitiveAcceleration()).getControlPa
>rameter().getParameter()) == 0); -
> Assert.assertFalse(Double.compare(((RandomizingControlParameter)original.ge
>tSocialAcceleration()).getControlParameter().getParameter(), -
>
> ((RandomizingControlParameter)copy.getSocialAcceleration()).getControlParam
>eter().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().getParam
>eter(), + ((ConstrictionVelocityUpdate)
> clone.getVelocityUpdateStrategy()).getConstrictionCoefficient().getParamete
>r(), 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>
|
