Menu
▾
▴
[cilib-devel] [PATCH] Constriction PSO
|
From: Andrich <avw...@gm...> - 2009-07-02 13:11:10
|
Added a velocity update strategy for a Constriction PSO as well as its unit test.
---
.../ConstrictionVelocityUpdate.java | 243 ++++++++++++++++++++
.../ConstrictionVelocityUpdateTest.java | 144 ++++++++++++
xml/constrictionPSO.xml | 57 +++++
3 files changed, 444 insertions(+), 0 deletions(-)
create mode 100644 src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
create mode 100644 src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
create mode 100644 xml/constrictionPSO.xml
diff --git a/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
new file mode 100644
index 0000000..41d955b
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdate.java
@@ -0,0 +1,243 @@
+/**
+ * Copyright (C) 2003 - 2009
+ * Computational Intelligence Research Group (CIRG@UP)
+ * Department of Computer Science
+ * University of Pretoria
+ * South Africa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+package net.sourceforge.cilib.pso.velocityupdatestrategies;
+
+import net.sourceforge.cilib.controlparameter.ConstantControlParameter;
+import net.sourceforge.cilib.controlparameter.ControlParameter;
+import net.sourceforge.cilib.controlparameter.RandomizingControlParameter;
+import net.sourceforge.cilib.entity.Particle;
+import net.sourceforge.cilib.type.types.container.Vector;
+
+/**
+ * A velocity update strategy that utilizes the constriction coefficient as
+ * developed by Clerc. References:
+ * <ul>
+ * <li>
+ * Inproceedings (Clerc1999)
+ * Clerc, M.
+ * The swarm and the queen: towards a deterministic and adaptive particle swarm
+ * optimization
+ * Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on,
+ * 1999, 3, -1957 Vol. 3
+ * </li>
+ * <li>
+ * Article (Clerc2002)
+ * Clerc, M. & Kennedy, J.
+ * The particle swarm - explosion, stability, and convergence in a
+ * multidimensional complex space Evolutionary Computation,
+ * IEEE Transactions on, 2002, 6, 58-73
+ * </li>
+ * </ul>
+ *
+ * Note, this strategy does not 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
+ * $\kappa \in [0, 1]$
+ *
+ * @author andrich
+ */
+public class ConstrictionVelocityUpdate implements VelocityUpdateStrategy {
+
+ protected ControlParameter socialAcceleration;
+ protected ControlParameter cognitiveAcceleration;
+ protected ControlParameter vMax;
+ protected ControlParameter kappa;
+
+ /**
+ * Default constructor. The values given to the control parameters attempt to
+ * adhere to the constraints of calculating the constriction constant, but do not
+ * necessarily represent good values.
+ */
+ public ConstrictionVelocityUpdate() {
+ socialAcceleration = new RandomizingControlParameter();
+ cognitiveAcceleration = new RandomizingControlParameter();
+ vMax = new ConstantControlParameter();
+ kappa = new ConstantControlParameter();
+
+ socialAcceleration.setParameter(3.0);
+ cognitiveAcceleration.setParameter(3.0);
+ vMax.setParameter(Double.MAX_VALUE);
+ kappa.setParameter(0.1);
+ }
+
+ /**
+ * Copy constructor.
+ * @param orig the ConstrictionVelocityUpdate to copy.
+ */
+ public ConstrictionVelocityUpdate(ConstrictionVelocityUpdate orig) {
+ this.socialAcceleration = new RandomizingControlParameter((RandomizingControlParameter) orig.socialAcceleration);
+ this.cognitiveAcceleration = new RandomizingControlParameter((RandomizingControlParameter) orig.cognitiveAcceleration);
+ this.vMax = new ConstantControlParameter((ConstantControlParameter) orig.vMax);
+ this.kappa = new ConstantControlParameter((ConstantControlParameter) orig.kappa);
+ }
+
+ /**
+ * {@inheritDoc }
+ */
+ @Override
+ public VelocityUpdateStrategy getClone() {
+ return new ConstrictionVelocityUpdate(this);
+ }
+
+ /**
+ * {@inheritDoc }
+ */
+ @Override
+ public void updateVelocity(Particle particle) {
+ assertAccelerationConstraints();
+
+ Vector velocity = (Vector) particle.getVelocity();
+ Vector position = (Vector) particle.getPosition();
+ Vector bestPosition = (Vector) particle.getBestPosition();
+ Vector nBestPosition = (Vector) particle.getNeighbourhoodBest().getBestPosition();
+
+
+ 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;
+ velocity.setReal(i, value);
+
+ clamp(velocity, i);
+ }
+ }
+
+ /**
+ * Clamp to maximum velocity.
+ * @param velocity The {@link Vector} to be clamped.
+ * @param i The dimension index to be clamped
+ */
+ protected void clamp(Vector velocity, int i) {
+ // if vMax is not set (or set as max), it is unnecessary to clamp
+ if (Double.compare(vMax.getParameter(), Double.MAX_VALUE) == 0) {
+ return;
+ }
+ if (velocity.getReal(i) < -vMax.getParameter()) {
+ velocity.setReal(i, -vMax.getParameter());
+ } else if (velocity.getReal(i) > vMax.getParameter()) {
+ velocity.setReal(i, vMax.getParameter());
+ }
+ }
+
+ /**
+ * {@inheritDoc }
+ */
+ @Override
+ public void updateControlParameters(Particle particle) {
+ this.kappa.updateParameter();
+ this.cognitiveAcceleration.updateParameter();
+ this.socialAcceleration.updateParameter();
+ this.vMax.updateParameter();
+ }
+
+ /**
+ * Ensure that values of c1 and c2 make it possible to calculate the
+ * constriction coefficient.
+ */
+ private void assertAccelerationConstraints() {
+ double c1 = ((RandomizingControlParameter) cognitiveAcceleration).getControlParameter().getParameter();
+ double c2 = ((RandomizingControlParameter) socialAcceleration).getControlParameter().getParameter();
+ if (c1 + c2 < 4) {
+ 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.");
+ }
+ }
+
+ /**
+ * Get the coginitive acceleration parameter.
+ * @return the cognitive acceleration {@link ControlParameter control parameter }.
+ */
+ public ControlParameter getCognitiveAcceleration() {
+ return cognitiveAcceleration;
+ }
+
+ /**
+ * Set the coginitive acceleration parameter.
+ * @param cognitiveAcceleration the new cognitive acceleration {@link ControlParameter control parameter }.
+ */
+ public void setCognitiveAcceleration(ControlParameter cognitiveAcceleration) {
+ this.cognitiveAcceleration = cognitiveAcceleration;
+ }
+
+ /**
+ * Get the Kappa control parameter.
+ * @return the kappa {@link ControlParameter control parameter }.
+ */
+ public ControlParameter getKappa() {
+ return kappa;
+ }
+
+ /**
+ * Set the Kappa control parameter.
+ * @param kappa the new kappa {@link ControlParameter control parameter }.
+ */
+ public void setKappa(ControlParameter kappa) {
+ this.kappa = kappa;
+ }
+
+ /**
+ * Get the social acceleration parameter.
+ * @return the social acceleration {@link ControlParameter control parameter }.
+ */
+ public ControlParameter getSocialAcceleration() {
+ return socialAcceleration;
+ }
+
+ /**
+ * Set the social acceleration parameter.
+ * @param socialAcceleration the new social accerelation {@link ControlParameter control parameter }.
+ */
+ public void setSocialAcceleration(ControlParameter socialAcceleration) {
+ this.socialAcceleration = socialAcceleration;
+ }
+
+ /**
+ * Get the maximum velocity parameter.
+ * @return the maximum velocity {@link ControlParameter control parameter }.
+ */
+ public ControlParameter getVMax() {
+ return vMax;
+ }
+
+ /**
+ * Set the maximum velocity parameter.
+ * @param vMax the new maximum velocity {@link ControlParameter control parameter }.
+ */
+ public void setVMax(ControlParameter vMax) {
+ this.vMax = vMax;
+ }
+}
diff --git a/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
new file mode 100644
index 0000000..189cca9
--- /dev/null
+++ b/src/test/java/net/sourceforge/cilib/pso/velocityupdatestrategies/ConstrictionVelocityUpdateTest.java
@@ -0,0 +1,144 @@
+/**
+ * Copyright (C) 2003 - 2009
+ * Computational Intelligence Research Group (CIRG@UP)
+ * Department of Computer Science
+ * University of Pretoria
+ * South Africa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+package net.sourceforge.cilib.pso.velocityupdatestrategies;
+
+import net.sourceforge.cilib.controlparameter.ConstantControlParameter;
+import net.sourceforge.cilib.controlparameter.RandomizingControlParameter;
+import net.sourceforge.cilib.functions.continuous.Spherical;
+import net.sourceforge.cilib.math.Maths;
+import net.sourceforge.cilib.math.random.generator.MersenneTwister;
+import net.sourceforge.cilib.problem.FunctionMinimisationProblem;
+import net.sourceforge.cilib.pso.particle.StandardParticle;
+import net.sourceforge.cilib.type.types.Numeric;
+import net.sourceforge.cilib.type.types.container.Vector;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Unit test for the constriction velocity update.
+ * @author andrich
+ */
+public class ConstrictionVelocityUpdateTest {
+
+ /**
+ * Test cloning and implicetly the copy constructor.
+ */
+ @Test
+ public void testClone() {
+ ConstrictionVelocityUpdate original = new ConstrictionVelocityUpdate();
+ ConstrictionVelocityUpdate copy = (ConstrictionVelocityUpdate) 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.cognitiveAcceleration).getControlParameter().getParameter(),
+ ((RandomizingControlParameter)copy.cognitiveAcceleration).getControlParameter().getParameter(), Maths.EPSILON);
+ Assert.assertEquals(((RandomizingControlParameter)original.socialAcceleration).getControlParameter().getParameter(),
+ ((RandomizingControlParameter)copy.socialAcceleration).getControlParameter().getParameter(), Maths.EPSILON);
+
+ copy.setKappa(new ConstantControlParameter(0.7));
+ copy.setVMax(new ConstantControlParameter(0.7));
+ RandomizingControlParameter randomizingControlParameter = new RandomizingControlParameter();
+ randomizingControlParameter.setParameter(4.0);
+ copy.setSocialAcceleration(new RandomizingControlParameter(randomizingControlParameter.getClone()));
+ copy.setCognitiveAcceleration(new RandomizingControlParameter(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.cognitiveAcceleration).getControlParameter().getParameter(),
+ ((RandomizingControlParameter)copy.cognitiveAcceleration).getControlParameter().getParameter()) == 0);
+ Assert.assertFalse(Double.compare(((RandomizingControlParameter)original.socialAcceleration).getControlParameter().getParameter(),
+ ((RandomizingControlParameter)copy.socialAcceleration).getControlParameter().getParameter()) == 0);
+ }
+
+ /**
+ * Test the velocity update as well as the constraint assertion.
+ */
+ @Test
+ public void testUpdateAndConstraintAssertion() {
+ MersenneTwister twister = new MersenneTwister();
+ FunctionMinimisationProblem problem = new FunctionMinimisationProblem();
+ problem.setFunction(new Spherical());
+
+ StandardParticle nBest = new StandardParticle();
+ StandardParticle particle = new StandardParticle();
+ particle.initialise(problem);
+ nBest.initialise(problem);
+ ((Vector)particle.getVelocity()).randomize(twister);
+ particle.setNeighbourhoodBest(nBest);
+
+ ConstrictionVelocityUpdate constrictionVelocityUpdate = new ConstrictionVelocityUpdate();
+
+ boolean assertionExceptionOccured = false;
+ try {
+ constrictionVelocityUpdate.updateVelocity(particle);
+ }
+ catch(UnsupportedOperationException ex) {
+ assertionExceptionOccured = true;
+ }
+
+ Assert.assertFalse(assertionExceptionOccured);
+
+ RandomizingControlParameter randomizingControlParameter = new RandomizingControlParameter();
+ randomizingControlParameter.setParameter(1.0);
+ constrictionVelocityUpdate.setSocialAcceleration(new RandomizingControlParameter(randomizingControlParameter.getClone()));
+ constrictionVelocityUpdate.setCognitiveAcceleration(new RandomizingControlParameter(randomizingControlParameter.getClone()));
+
+ assertionExceptionOccured = false;
+ try {
+ constrictionVelocityUpdate.updateVelocity(particle);
+ }
+ catch(UnsupportedOperationException ex) {
+ assertionExceptionOccured = true;
+ }
+
+ Assert.assertTrue(assertionExceptionOccured);
+
+ }
+
+ /**
+ * Test velocity clamping.
+ */
+ @Test
+ public void testClamping() {
+ MersenneTwister twister = new MersenneTwister();
+ FunctionMinimisationProblem problem = new FunctionMinimisationProblem();
+ problem.setFunction(new Spherical());
+
+ StandardParticle nBest = new StandardParticle();
+ StandardParticle particle = new StandardParticle();
+ particle.initialise(problem);
+ nBest.initialise(problem);
+ ((Vector)particle.getVelocity()).randomize(twister);
+ particle.setNeighbourhoodBest(nBest);
+
+ ConstrictionVelocityUpdate constrictionVelocityUpdate = new ConstrictionVelocityUpdate();
+ constrictionVelocityUpdate.setVMax(new ConstantControlParameter(0.5));
+ constrictionVelocityUpdate.updateVelocity(particle);
+ Vector velocity = particle.getVelocity();
+ for (Numeric number : velocity) {
+ Assert.assertTrue(Double.compare(number.getReal(), 0.5) <= 0);
+ Assert.assertTrue(Double.compare(number.getReal(), -0.5) >= 0);
+ }
+
+ }
+
+}
diff --git a/xml/constrictionPSO.xml b/xml/constrictionPSO.xml
new file mode 100644
index 0000000..77c3eb4
--- /dev/null
+++ b/xml/constrictionPSO.xml
@@ -0,0 +1,57 @@
+<?xml version="1.0"?>
+<!DOCTYPE simulator [
+<!ATTLIST algorithm id ID #IMPLIED>
+<!ATTLIST problem id ID #IMPLIED>
+<!ATTLIST measurements id ID #IMPLIED>
+]>
+<simulator>
+ <algorithms>
+ <algorithm id="constrictionPSO" class="pso.PSO">
+ <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" />
+ <!--vMax class="controlparameter.ConstantControlParameter" parameter="0.1" /-->
+ </velocityUpdateStrategy>
+ </entityType>
+ </initialisationStrategy>
+ <topology class="entity.topologies.GBestTopology"/>
+ <addStoppingCondition class="stoppingcondition.MaximumIterations" maximumIterations="1000"/>
+ </algorithm>
+ </algorithms>
+
+ <problems>
+ <problem id="spherical" class="problem.FunctionMinimisationProblem">
+ <function class="functions.continuous.Spherical"/>
+ </problem>
+ <problem id="rosenbrock" class="problem.FunctionMinimisationProblem">
+ <function class="functions.continuous.Rosenbrock"/>
+ </problem>
+ <problem id="rastrigin" class="problem.FunctionMinimisationProblem">
+ <function class="functions.continuous.unconstrained.Rastrigin"/>
+ </problem>
+ </problems>
+
+ <measurements id="fitness" class="simulator.MeasurementSuite" resolution="10" samples="1">
+ <addMeasurement class="measurement.single.Fitness"/>
+ </measurements>
+ <simulations>
+ <simulation>
+ <algorithm idref="constrictionPSO"/>
+ <problem idref="spherical"/>
+ <measurements idref="fitness" file="data/constrictionpso_spherical.txt"/>
+ </simulation>
+ <simulation>
+ <algorithm idref="constrictionPSO"/>
+ <problem idref="rosenbrock"/>
+ <measurements idref="fitness" file="data/constrictionpso_rosenbrock.txt"/>
+ </simulation>
+ <simulation>
+ <algorithm idref="constrictionPSO"/>
+ <problem idref="rastrigin"/>
+ <measurements idref="fitness" file="data/constrictionpso_rastrigin.txt"/>
+ </simulation>
+ </simulations>
+</simulator>
--
1.6.0.4
|
