Menu
▾
▴
[cilib-devel] [PATCH] UPDATED:Implemented the Rand-to-best DE target creation strategy
|
From: <leo...@gm...> - 2009-07-17 13:40:05
|
From: Leo Langenhoven <lla...@cs...>
Please note: This patch replaces the previous Rand-to-best patch.
Made some members of RandCreationStrategy protected, since Rand-to-Best
inherets from it.
Added a setScaleParameter method to RandCreationStrategy so that the
parameter can be set in the xml file.
Added new functionality to the Selection class:
1. Added a exclusion method that accepts a list of entities. This method
will remove all elements from the Selection that exist in the exclusion
list.
2. Added a random method and an overload that accepts a size parameter.
This method will randomly select elements from the current Selection.
Refactored the RandomCreation class so that it will use the selection
interface in order to select entities when calculating the distance
vector.
Test cases for the new functionality is also included.
---
.../operators/creation/RandCreationStrategy.java | 52 ++++------
.../creation/RandToBestCreationStrategy.java | 105 ++++++++++++++++++++
.../cilib/util/selection/Selection.java | 39 +++++++
.../cilib/util/selection/SelectionSyntax.java | 7 ++
.../operators/creation/RandToBestCreationTest.java | 88 ++++++++++++++++
.../cilib/util/selection/SelectionTest.java | 11 ++
6 files changed, 269 insertions(+), 33 deletions(-)
create mode 100644 src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationStrategy.java
create mode 100644 src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationTest.java
diff --git a/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreationStrategy.java b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreationStrategy.java
index 722a7de..59cd174 100644
--- a/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreationStrategy.java
+++ b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreationStrategy.java
@@ -21,7 +21,7 @@
*/
package net.sourceforge.cilib.entity.operators.creation;
-import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
@@ -29,24 +29,25 @@ import net.sourceforge.cilib.controlparameter.ConstantControlParameter;
import net.sourceforge.cilib.controlparameter.ControlParameter;
import net.sourceforge.cilib.entity.Entity;
import net.sourceforge.cilib.entity.Topology;
-import net.sourceforge.cilib.entity.operators.selection.RandomSelectionStrategy;
-import net.sourceforge.cilib.entity.operators.selection.SelectionStrategy;
import net.sourceforge.cilib.entity.topologies.TopologyHolder;
+import net.sourceforge.cilib.math.random.generator.MersenneTwister;
+import net.sourceforge.cilib.math.random.generator.Random;
import net.sourceforge.cilib.type.types.Real;
import net.sourceforge.cilib.type.types.container.Vector;
+import net.sourceforge.cilib.util.selection.Selection;
public class RandCreationStrategy implements CreationStrategy {
private static final long serialVersionUID = 930740770470361009L;
- private ControlParameter scaleParameter;
- private ControlParameter numberOfDifferenceVectors;
+ protected ControlParameter scaleParameter;
+ protected ControlParameter numberOfDifferenceVectors;
/**
* Create a new instance of {@code CurrentToRandCreationStrategy}.
*/
public RandCreationStrategy() {
this.scaleParameter = new ConstantControlParameter(0.5);
- this.numberOfDifferenceVectors = new ConstantControlParameter(1);
+ this.numberOfDifferenceVectors = new ConstantControlParameter(2);
}
/**
@@ -72,7 +73,8 @@ public class RandCreationStrategy implements CreationStrategy {
*/
@Override
public Entity create(Entity targetEntity, Entity current, Topology<? extends Entity> topology) {
- List<Entity> participants = selectEntities(current, topology);
+ Random random = new MersenneTwister();
+ List<Entity> participants = Selection.from(topology.asList()).exclude(Arrays.asList(targetEntity, current)).random(random, (int)numberOfDifferenceVectors.getParameter()).select();
Vector differenceVector = determineDistanceVector(participants);
Vector targetVector = (Vector) targetEntity.getCandidateSolution();
@@ -92,7 +94,7 @@ public class RandCreationStrategy implements CreationStrategy {
* reduce the diversity of the population as not all entities will be considered.
* @return A {@linkplain Vector} representing the resultant of all calculated difference vectors.
*/
- private Vector determineDistanceVector(List<Entity> participants) {
+ protected Vector determineDistanceVector(List<Entity> participants) {
Vector distanceVector = new Vector(participants.get(0).getCandidateSolution().size(), new Real(0.0));
Iterator<Entity> iterator = participants.iterator();
@@ -108,31 +110,6 @@ public class RandCreationStrategy implements CreationStrategy {
}
/**
- * This private method implements the "y" part of the DE/x/y/z structure.
- * @param current The current {@linkplain Entity} in the {@linkplain Topology}
- * @param topology The current population.
- * @return {@linkplain List} containing the entities to be used in the calculation of
- * the difference vectors.
- */
- private List<Entity> selectEntities(Entity current, Topology<? extends Entity> topology) {
- SelectionStrategy randomSelectionStrategy = new RandomSelectionStrategy();
- List<Entity> participants = new ArrayList<Entity>();
-
- int total = 2 * Double.valueOf(this.numberOfDifferenceVectors.getParameter()).intValue();
-
- while (participants.size() < total) {
- Entity entity = randomSelectionStrategy.select(topology);
-
- if (participants.contains(entity)) continue;
- if (current == entity) continue;
-
- participants.add(entity);
- }
-
- return participants;
- }
-
- /**
* {@inheritDoc}
*/
@Override
@@ -140,5 +117,14 @@ public class RandCreationStrategy implements CreationStrategy {
throw new UnsupportedOperationException("Not supported yet. This may need some more refactoring. May require looping operator?");
}
+ public void setScaleParameter(ControlParameter scaleParameter) {
+ this.scaleParameter = scaleParameter;
+ }
+
+ public void setNumberOfDifferenceVectors(
+ ControlParameter numberOfDifferenceVectors) {
+ this.numberOfDifferenceVectors = numberOfDifferenceVectors;
+ }
+
}
diff --git a/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationStrategy.java b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationStrategy.java
new file mode 100644
index 0000000..7797796
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationStrategy.java
@@ -0,0 +1,105 @@
+/**
+ * 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.entity.operators.creation;
+
+import java.util.Arrays;
+import java.util.List;
+
+import net.sourceforge.cilib.controlparameter.ConstantControlParameter;
+import net.sourceforge.cilib.controlparameter.ControlParameter;
+import net.sourceforge.cilib.entity.Entity;
+import net.sourceforge.cilib.entity.Topology;
+import net.sourceforge.cilib.entity.topologies.TopologyHolder;
+import net.sourceforge.cilib.math.random.generator.MersenneTwister;
+import net.sourceforge.cilib.math.random.generator.Random;
+import net.sourceforge.cilib.type.types.container.Vector;
+import net.sourceforge.cilib.util.selection.Selection;
+
+/**
+ * @author leo
+ * This is an implimentation of the Rand-to-best DE target creation strategy. This implimentation is simply an extension of the {@linkplain RandCreationStrategy} that also includes the best {@linkplain Entity}'s solution vector. The influence of the best vector and the
+ * random vector is determined by the greedynessParameter, which is sampled as E [0,1]. A value of 0 will ignore the contribution of the best {@linkplain Entity}, and a
+ * value of 1 will ignore the controbution of the random {@linkplain Entity}.
+ */
+public class RandToBestCreationStrategy extends RandCreationStrategy {
+ private static final long serialVersionUID = 413628791093573875L;
+ private ControlParameter greedynessParameter;
+ /**
+ * Create a new instance of {@code RandToBestCreationStrategy}.
+ */
+ public RandToBestCreationStrategy() {
+ super();
+ greedynessParameter = new ConstantControlParameter(0.5);
+ }
+ /**
+ * Copy constructor. Create a copy of the provided instance.
+ * @param copy The instance to copy.
+ */
+ public RandToBestCreationStrategy(RandToBestCreationStrategy other) {
+ super(other);
+ greedynessParameter = other.greedynessParameter.getClone();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Entity create(Entity targetEntity, Entity current,
+ Topology<? extends Entity> topology) {
+ Entity bestEntity = topology.getBestEntity();
+ Random random = new MersenneTwister();
+ List<Entity> participants = Selection.from(topology.asList()).exclude(Arrays.asList(targetEntity, bestEntity, current)).random(random, (int)numberOfDifferenceVectors.getParameter()).select();
+ Vector differenceVector = determineDistanceVector(participants);
+
+ Vector targetVector = ((Vector) targetEntity.getCandidateSolution()).multiply(1 - greedynessParameter.getParameter());
+ Vector bestVector = ((Vector) bestEntity.getCandidateSolution()).multiply(greedynessParameter.getParameter());
+
+ Vector trialVector = bestVector.plus(targetVector.plus(differenceVector.multiply(scaleParameter.getParameter())));
+
+ Entity trialEntity = current.getClone();
+ trialEntity.setCandidateSolution(trialVector);
+
+ return trialEntity;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public RandToBestCreationStrategy getClone() {
+ return new RandToBestCreationStrategy(this);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void performOperation(TopologyHolder holder) {
+ throw new UnsupportedOperationException("Not supported yet. This may need some more refactoring. May require looping operator?");
+ }
+
+ public void setGreedynessParameter(ControlParameter greedynessParameter) {
+ this.greedynessParameter = greedynessParameter;
+ }
+
+}
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/Selection.java b/src/main/java/net/sourceforge/cilib/util/selection/Selection.java
index 29c069b..6b01214 100644
--- a/src/main/java/net/sourceforge/cilib/util/selection/Selection.java
+++ b/src/main/java/net/sourceforge/cilib/util/selection/Selection.java
@@ -249,7 +249,46 @@ public final class Selection<E> implements SelectionSyntax<E> {
@Override
public List<Selection.Entry<E>> entries() {
return this.elements;
+ }
+
+ /**
+ * Remove any {@code Entry}'s from {@code elements} that are also contained in {@code exclusion}.
+ * @return A selection containing the remaining elements which do not occur in {@code exclusion}.
+ */
+ @Override
+ public Selection<E> exclude(List<? extends E> exclusion) {
+ for(int i = elements.size() - 1; i >= 0; --i){
+ Entry element = elements.get(i);
+ if(exclusion.contains(element.getElement()))
+ elements.remove(element);
+ }
+ return this;
+ }
+
+ /**
+ * Obtain a random element from the current Selection.
+ * @param random The random number to be used in the selection.
+ * @return A selection containing a random element from the original {@code elements} member.
+ */
+ @Override
+ public SelectionSyntax<E> random(Random random) {
+ Entry<E> randomEntry = Selection.randomFrom(elements, random);
+ elements.clear();
+ elements.add(randomEntry);
+ return this;
}
+
+ /**
+ * Obtain a random number of elements from the current Selection.
+ * @param random The random number to be used in the selection.
+ * @param number The number of elements to select.
+ * @return A selection containing the random elements from the original {@code elements} member.
+ */
+ @Override
+ public SelectionSyntax<E> random(Random random, int number) {
+ elements = Selection.randomFrom(elements, random, number);
+ return this;
+ }
/**
* This class provides the notion of an entry within a list
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java b/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java
index 9cd9ea2..2680d4b 100644
--- a/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java
+++ b/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java
@@ -22,6 +22,7 @@
package net.sourceforge.cilib.util.selection;
import java.util.List;
+import net.sourceforge.cilib.math.random.generator.Random;
import net.sourceforge.cilib.util.selection.ordering.Ordering;
import net.sourceforge.cilib.util.selection.weighing.Weighing;
@@ -42,6 +43,12 @@ public interface SelectionSyntax<E> {
public SelectionSyntax<E> last();
public SelectionSyntax<E> last(int number);
+
+ public SelectionSyntax<E> exclude(List<? extends E> exclusion);
+
+ public SelectionSyntax<E> random(Random random);
+
+ public SelectionSyntax<E> random(Random random, int number);
public List<E> select();
diff --git a/src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationTest.java b/src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationTest.java
new file mode 100644
index 0000000..f749f88
--- /dev/null
+++ b/src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCreationTest.java
@@ -0,0 +1,88 @@
+/**
+ * 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.entity.operators.creation;
+
+import static org.hamcrest.CoreMatchers.is;
+import net.sourceforge.cilib.ec.Individual;
+import net.sourceforge.cilib.entity.Entity;
+import net.sourceforge.cilib.entity.EntityType;
+import net.sourceforge.cilib.entity.Topology;
+import net.sourceforge.cilib.entity.topologies.GBestTopology;
+import net.sourceforge.cilib.math.random.generator.SeedSelectionStrategy;
+import net.sourceforge.cilib.math.random.generator.Seeder;
+import net.sourceforge.cilib.math.random.generator.ZeroSeederStrategy;
+import net.sourceforge.cilib.problem.MinimisationFitness;
+import net.sourceforge.cilib.type.types.Real;
+import net.sourceforge.cilib.type.types.container.Vector;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author leo
+ *
+ */
+public class RandToBestCreationTest {
+
+ @Test
+ public void randToBestCreationTest(){
+ SeedSelectionStrategy seedStrategy = Seeder.getSeederStrategy();
+ Seeder.setSeederStrategy(new ZeroSeederStrategy());
+
+ try {
+
+ RandToBestCreationStrategy creation = new RandToBestCreationStrategy();
+ Topology<Individual> testTopology = new GBestTopology<Individual>();
+
+ Entity current = new Individual();
+ Entity entityBest = new Individual();
+ Entity entityRandom = new Individual();
+ Entity entity1 = new Individual();
+ Entity entity2 = new Individual();
+
+ testTopology.add((Individual)current);
+ testTopology.add((Individual)entityBest);
+ testTopology.add((Individual)entityRandom);
+ testTopology.add((Individual)entity1);
+ testTopology.add((Individual)entity2);
+
+ entityBest.getProperties().put(EntityType.FITNESS, new MinimisationFitness(0.0));
+ entityBest.getProperties().put(EntityType.CANDIDATE_SOLUTION, new Vector(1, new Real(0.1)));
+ entityRandom.getProperties().put(EntityType.FITNESS, new MinimisationFitness(1.0));
+ entityRandom.getProperties().put(EntityType.CANDIDATE_SOLUTION, new Vector(1, new Real(0.2)));
+ entity1.getProperties().put(EntityType.FITNESS, new MinimisationFitness(2.0));
+ entity1.getProperties().put(EntityType.CANDIDATE_SOLUTION, new Vector(1, new Real(0.3)));
+ entity2.getProperties().put(EntityType.FITNESS, new MinimisationFitness(3.0));
+ entity2.getProperties().put(EntityType.CANDIDATE_SOLUTION, new Vector(1, new Real(0.4)));
+
+ Entity resultEntity = creation.create(entityRandom, current, testTopology);
+
+ Assert.assertThat((Double)((Vector)resultEntity.getCandidateSolution()).get(0).getReal(), is(0.2));
+ } finally {
+ Seeder.setSeederStrategy(seedStrategy);
+ }
+ }
+
+}
diff --git a/src/test/java/net/sourceforge/cilib/util/selection/SelectionTest.java b/src/test/java/net/sourceforge/cilib/util/selection/SelectionTest.java
index 60fce8c..476ed37 100644
--- a/src/test/java/net/sourceforge/cilib/util/selection/SelectionTest.java
+++ b/src/test/java/net/sourceforge/cilib/util/selection/SelectionTest.java
@@ -61,4 +61,15 @@ public class SelectionTest {
Assert.assertEquals(1, selection.get(0).intValue());
Assert.assertEquals(1, selection.size());
}
+
+ @Test
+ public void exclusionSelection(){
+ List<Integer> elements = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
+ List<Integer> exlusionElements = Arrays.asList(1, 2, 4, 6);
+ List<Integer> selection = Selection.from(elements).exclude(exlusionElements).first(3).select();
+ Assert.assertEquals(3, selection.size());
+ Assert.assertEquals(3, selection.get(0).intValue());
+ Assert.assertEquals(5, selection.get(1).intValue());
+ Assert.assertEquals(7, selection.get(2).intValue());
+ }
}
--
1.5.4.3
|
