Menu
▾
▴
Re: [cilib-devel] [PATCH] UPDATED:Implemented the Rand-to-best DE target creation strategy
|
From: Gary P. <gpa...@gm...> - 2009-07-20 10:18:55
|
Hi,
I agree with a lot in this patch, but the changes to the selection class just
need to be massaged a little.
One thing to take into consideration is that the random selection that needs
to take place within the RandCreationStrategy requires that the selected
entities should be unique, as in:
i1 != i2 != i3
Maybe something like: Selection.from(list).unique().random(4) ?
Also, I think that the manner in which the difference vectors are calculated
should be changed a little. Having a private member in the class is very
restrictive.
Regards,
Gary
On Friday 17 July 2009 15:39:52 leo...@gm... wrote:
> 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/RandToBestCre
>ationStrategy.java create mode 100644
> src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestCre
>ationTest.java
>
> diff --git
> a/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreatio
>nStrategy.java
> b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreatio
>nStrategy.java index 722a7de..59cd174 100644
> ---
> a/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreatio
>nStrategy.java +++
> b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandCreatio
>nStrategy.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/RandToBestC
>reationStrategy.java
> b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestC
>reationStrategy.java new file mode 100644
> index 0000000..7797796
> --- /dev/null
> +++
> b/src/main/java/net/sourceforge/cilib/entity/operators/creation/RandToBestC
>reationStrategy.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.getParamete
>r()); +
> + 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/RandToBestC
>reationTest.java
> b/src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestC
>reationTest.java new file mode 100644
> index 0000000..f749f88
> --- /dev/null
> +++
> b/src/test/java/net/sourceforge/cilib/entity/operators/creation/RandToBestC
>reationTest.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());
> + }
> }
|
