Menu
▾
▴
Re: [cilib-devel] [PATCH] UPDATED:Implemented the Rand-to-best DE target creation strategy V2
|
From: Gary P. <gpa...@gm...> - 2009-07-21 06:45:39
|
Looks fine.
I've changed the return types for a few methods to use the actual
implementation. Minor etc.
Also, I'm going to change the creation method of the UniqueSelection to be
package access - I don't want UniqueSelection to be instantiated directly, you
should be going through the Selection class to get an instance.
The only other issue might be the exclude() method, should we worry about that
or should we assume that the user will sort it out?
On Monday 20 July 2009 14:52:41 leo...@gm... wrote:
> From: Leo Langenhoven <lla...@cs...>
>
> This patch should be applied along with the UPDATED:Implemented the
> Rand-to-best DE target creation strategy patch.
>
> Added functionality so that random selection will be unqiue. This was
> achieved as follows:
>
> - Added a RandomSyntax interface, this interface defines the random
> methods.
> - Added a UniqueSyntax interface, this interface defines a method
> called unique, that returns a new instance of SelectionSyntax.
> - Added a UniqueSelection class. This class inherets from
> SelectionSyntax as well as RandomSyntax. It has a similar implementation
> to Selection, but the rand(int) method has the added constraint that the
> random elements selected are all unique.
> - The Selection class now inherets from the above two interfaces as
> well as SelectionSyntax. The unique method returns an instance of
> UniqueSelection that contains the same elements as the Selection object.
>
> The DE creation strategies were updated to use the new functionality.
> ---
> .../operators/creation/RandCreationStrategy.java | 2 +-
> .../creation/RandToBestCreationStrategy.java | 2 +-
> .../cilib/util/selection/RandomSyntax.java | 32 +++
> .../cilib/util/selection/Selection.java | 13 +-
> .../cilib/util/selection/SelectionSyntax.java | 5 -
> .../cilib/util/selection/UniqueSelection.java | 236
> ++++++++++++++++++++ .../cilib/util/selection/UniqueSyntax.java |
> 28 +++
> .../cilib/util/selection/UniqueSelectionTest.java | 94 ++++++++
> 8 files changed, 403 insertions(+), 9 deletions(-)
> create mode 100644
> src/main/java/net/sourceforge/cilib/util/selection/RandomSyntax.java create
> mode 100644
> src/main/java/net/sourceforge/cilib/util/selection/UniqueSelection.java
> create mode 100644
> src/main/java/net/sourceforge/cilib/util/selection/UniqueSyntax.java create
> mode 100644
> src/test/java/net/sourceforge/cilib/util/selection/UniqueSelectionTest.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 59cd174..56733b8 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 @@ -74,7 +74,7 @@ public class RandCreationStrategy
> implements CreationStrategy { @Override
> public Entity create(Entity targetEntity, Entity current, Topology<?
> extends Entity> topology) { Random random = new MersenneTwister();
> - List<Entity> participants =
> Selection.from(topology.asList()).exclude(Arrays.asList(targetEntity,
> current)).random(random,
> (int)numberOfDifferenceVectors.getParameter()).select(); +
> List<Entity> participants =
> Selection.from(topology.asList()).exclude(Arrays.asList(targetEntity,
> current)).unique().random(random,
> (int)numberOfDifferenceVectors.getParameter()).select(); Vector
> differenceVector = determineDistanceVector(participants);
>
> Vector targetVector = (Vector)
> targetEntity.getCandidateSolution(); 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 index 7797796..1566d8d 100644
> ---
> 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 @@ -69,7 +69,7 @@ public class
> RandToBestCreationStrategy extends RandCreationStrategy { 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(); + List<Entity>
> participants =
> Selection.from(topology.asList()).exclude(Arrays.asList(targetEntity,
> bestEntity, current)).unique().random(random,
> (int)numberOfDifferenceVectors.getParameter()).select(); Vector
> differenceVector = determineDistanceVector(participants);
>
> Vector targetVector = ((Vector)
> targetEntity.getCandidateSolution()).multiply(1 -
> greedynessParameter.getParameter()); diff --git
> a/src/main/java/net/sourceforge/cilib/util/selection/RandomSyntax.java
> b/src/main/java/net/sourceforge/cilib/util/selection/RandomSyntax.java new
> file mode 100644
> index 0000000..cd39e67
> --- /dev/null
> +++ b/src/main/java/net/sourceforge/cilib/util/selection/RandomSyntax.java
> @@ -0,0 +1,32 @@
> +/**
> + * 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.util.selection;
> +
> +import net.sourceforge.cilib.math.random.generator.Random;
> +
> +public interface RandomSyntax<E> {
> +
> + public SelectionSyntax<E> random(Random random);
> +
> + public SelectionSyntax<E> random(Random random, int number);
> +
> +}
> 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
> 6b01214..d331bb0 100644
> --- a/src/main/java/net/sourceforge/cilib/util/selection/Selection.java
> +++ b/src/main/java/net/sourceforge/cilib/util/selection/Selection.java
> @@ -61,7 +61,7 @@ import
> net.sourceforge.cilib.util.selection.weighing.Weighing; * @param <E> The
> comparable type.
> * @author gpampara
> */
> -public final class Selection<E> implements SelectionSyntax<E> {
> +public final class Selection<E> implements SelectionSyntax<E>,
> RandomSyntax<E>, UniqueSyntax<E> {
>
> private List<Entry<E>> elements;
>
> @@ -88,6 +88,15 @@ public final class Selection<E> implements
> SelectionSyntax<E> { public static <T> Selection<T> from(List<? extends T>
> elements) { return new Selection<T>(elements);
> }
> +
> + /**
> + * Create an instance of {@code UniqueSelection} that contains the
> same elements as this Selection + * @return An instance of {@code
> UniqueSelection} with identical elements. + */
> + @Override
> + public UniqueSelection<E> unique(){
> + return UniqueSelection.from(this.select());
> + }
>
> /**
> * Obtain a random element from the provided list. This is a
> convenience method @@ -307,7 +316,7 @@ public final class Selection<E>
> implements SelectionSyntax<E> { /**
> * Create a new {@code Entry}. This constructor is private
> intentionall * @param element The element to decorate.
> + */ - private Entry(E element) {
> + Entry(E element) {
> this.element = element;
> this.weight = 0.0;
> }
> 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 2680d4b..4485c97 100644
> ---
> a/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java
> +++
> b/src/main/java/net/sourceforge/cilib/util/selection/SelectionSyntax.java
> @@ -22,7 +22,6 @@
> 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;
>
> @@ -46,10 +45,6 @@ public interface SelectionSyntax<E> {
>
> 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();
>
> public List<Selection.Entry<E>> entries();
> diff --git
> a/src/main/java/net/sourceforge/cilib/util/selection/UniqueSelection.java
> b/src/main/java/net/sourceforge/cilib/util/selection/UniqueSelection.java
> new file mode 100644
> index 0000000..fde9913
> --- /dev/null
> +++
> b/src/main/java/net/sourceforge/cilib/util/selection/UniqueSelection.java
> @@ -0,0 +1,236 @@
> +/**
> + * 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.util.selection;
> +
> +import java.util.ArrayList;
> +import java.util.Collection;
> +import java.util.List;
> +
> +import net.sourceforge.cilib.math.random.generator.Random;
> +import net.sourceforge.cilib.util.selection.Selection.Entry;
> +import net.sourceforge.cilib.util.selection.ordering.Ordering;
> +import net.sourceforge.cilib.util.selection.weighing.Weighing;
> +
> +/**
> + * <p>
> + * A {@code UniqueSelection} is an abstraction that allows operations to
> be applied to + * a collection instace that result in a selection of list
> elements, based on a varied of + * potential combination of operators.
> {@code UniqueSelection} is similar to {@code Selection}, except that the
> {#code random(int)} method + * will return a list of unique random entries.
> + * </p>
> + * @param <E> The comparable type.
> + * @author gpampara
> + * @author leo
> + */
> +public class UniqueSelection<E> implements SelectionSyntax<E>,
> RandomSyntax<E> { + private List<Entry<E>> elements;
> +
> + /**
> + * Assign the UniqueSelection to take palce on the provided
> collection. The + * collection is copied to ensure that the original
> collection reference is + * not altered.
> + * @param elements The elements on which the selection should take
> place. + */
> + private UniqueSelection(Collection<? extends E> elements) {
> + this.elements = new ArrayList<Entry<E>>(elements.size());
> +
> + for (E element : elements) {
> + this.elements.add(new Entry<E>(element));
> + }
> + }
> +
> + /**
> + * Create a selection that will operate on the provided collection.
> + * @param <T> The comparable type.
> + * @param elements The collection of elements to operate on.
> + * @return A UniqueSelection based on the provided collection.
> + */
> + public static <T> UniqueSelection<T> from(List<? extends T> elements)
> { + return new UniqueSelection<T>(elements);
> + }
> +
> + /**
> + * Apply the provided ordering on the current selection. The result of
> the + * operation will result in a modified selection.
> + * @param ordering The ordering to orderBy.
> + * @return A selection upon which the ordering has been applied.
> + * @throws UnsupportedOperationException if the ordering cannot be
> applied. + */
> + @Override
> + public SelectionSyntax<E> orderBy(Ordering<E> ordering) {
> + boolean result = ordering.order(this.elements);
> +
> + if (result) {
> + return this;
> + }
> +
> + throw new UnsupportedOperationException("The ordering [" +
> ordering.getClass().getSimpleName() + "] " + + "cannot be
> applied to the selection. Please ensure that the intention of the ordering
> is correct."); + }
> +
> + /**
> + * Apply the provided weighing on the current selection. The result of
> the + * operation will result in new weighed selection.
> + * @param weighing The weighing to weighWith.
> + * @return A selection upon which the weighing has been applied.
> + */
> + @Override
> + public SelectionSyntax<E> weigh(Weighing<E> weighing) {
> + boolean result = weighing.weigh(this.elements);
> +
> + if (result) {
> + return this;
> + }
> +
> + throw new UnsupportedOperationException("The weighing [" +
> weighing.getClass().getSimpleName() + "]" + + "cannot be
> applied to the selection. Please ensure that the intention of the weighing
> is correct."); + }
> +
> + /**
> + * Obtain the first result from the current selection. These elements
> are returned + * from the front of the current selection.
> + * @return A selection containing the first element.
> + */
> + @Override
> + public SelectionSyntax<E> first() {
> + this.elements = this.elements.subList(0, 1);
> + return this;
> + }
> +
> + /**
> + * Obtain the frist {@code number} of elements from the current
> selection. These + * elements are returned from the front of the
> current selection. + * @param number The number of elements to return.
> + * @return A selection containing the first {@code number} elements.
> + */
> + @Override
> + public SelectionSyntax<E> first(int number) {
> + this.elements = this.elements.subList(0, number);
> + return this;
> + }
> +
> + /**
> + * Obtain the last element contained within the current selection.
> + * @return A selection containing the last element.
> + */
> + @Override
> + public SelectionSyntax<E> last() {
> + this.elements = this.elements.subList(this.elements.size() - 1,
> this.elements.size()); + return this;
> + }
> +
> + /**
> + * Obtain the last {@code number} of elements from the current
> selection. + * @param number The number of elements to select.
> + * @return A selection containing the last {@code number} of elements.
> + */
> + @Override
> + public SelectionSyntax<E> last(int number) {
> + this.elements = this.elements.subList(this.elements.size() -
> number, this.elements.size()); + return this;
> + }
> +
> + /**
> + * Obtain the result of the selection.
> + * @return A list of elements that the selection has selected.
> + */
> + @Override
> + public List<E> select() {
> + List<E> result = new ArrayList<E>();
> +
> + for (Entry<E> entry : elements) {
> + result.add(entry.getElement());
> + }
> +
> + return result;
> + }
> +
> + /**
> + * Obtain the first result of the selection.
> + * @return The first element returned by the selection.
> + */
> + @Override
> + public E singleSelect() {
> + return this.elements.get(0).getElement();
> + }
> +
> + /**
> + * Obtain the list of internal {@code Entry} instances.
> + * @return The list of internal {@code Entry} instances.
> + */
> + @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 UniqueSelection<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 UniqueSelection.
> + * @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. Each
> of these elements has to be unqiue + * @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) {
> + if(number > elements.size())
> + throw new RuntimeException("Unable to select " + number + " unique
> elements, current Selection only contains " + elements.size() + "
> elements."); + List<Entry<E>> tmp = new ArrayList<Entry<E>>(number);
> +
> + for (int i = 0; i < number; i++) {
> + int index = random.nextInt(elements.size());
> + tmp.add(elements.get(index));
> + elements.remove(index);
> + }
> + elements = tmp;
> + return this;
> + }
> +
> +}
> diff --git
> a/src/main/java/net/sourceforge/cilib/util/selection/UniqueSyntax.java
> b/src/main/java/net/sourceforge/cilib/util/selection/UniqueSyntax.java new
> file mode 100644
> index 0000000..d33b36e
> --- /dev/null
> +++ b/src/main/java/net/sourceforge/cilib/util/selection/UniqueSyntax.java
> @@ -0,0 +1,28 @@
> +/**
> + * 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.util.selection;
> +
> +public interface UniqueSyntax<E> {
> +
> + public SelectionSyntax<E> unique();
> +
> +}
> \ No newline at end of file
> diff --git
> a/src/test/java/net/sourceforge/cilib/util/selection/UniqueSelectionTest.ja
>va
> b/src/test/java/net/sourceforge/cilib/util/selection/UniqueSelectionTest.ja
>va new file mode 100644
> index 0000000..06fed0c
> --- /dev/null
> +++
> b/src/test/java/net/sourceforge/cilib/util/selection/UniqueSelectionTest.ja
>va @@ -0,0 +1,94 @@
> +/**
> + * 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.util.selection;
> +
> +import java.util.Arrays;
> +import java.util.List;
> +
> +import net.sourceforge.cilib.math.random.generator.MersenneTwister;
> +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 org.junit.Assert;
> +import org.junit.Test;
> +
> +public class UniqueSelectionTest {
> + @Test
> + public void lastSelection() {
> + List<Integer> elements = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8,
> 9); + List<Integer> selection =
> Selection.from(elements).last(3).select(); +
> + Assert.assertEquals(3, selection.size());
> + Assert.assertTrue(selection.contains(7));
> + Assert.assertTrue(selection.contains(8));
> + Assert.assertTrue(selection.contains(9));
> +
> + selection = Selection.from(elements).last().select();
> + Assert.assertEquals(1, selection.size());
> + Assert.assertEquals(9, selection.get(0).intValue());
> + }
> +
> + @Test
> + public void firstSelection() {
> + List<Integer> elements = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8,
> 9); + List<Integer> selection =
> Selection.from(elements).first(3).select(); +
> + Assert.assertEquals(3, selection.size());
> + Assert.assertEquals(1, selection.get(0).intValue());
> + Assert.assertEquals(2, selection.get(1).intValue());
> + Assert.assertEquals(3, selection.get(2).intValue());
> +
> + selection = Selection.from(elements).first().select();
> + 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());
> + }
> +
> + @Test
> + public void randomSelection(){
> + SeedSelectionStrategy seedStrategy = Seeder.getSeederStrategy();
> + Seeder.setSeederStrategy(new ZeroSeederStrategy());
> +
> + try {
> + List<Integer> elements = Arrays.asList(1, 2, 3, 4);
> + List<Integer> selection =
> UniqueSelection.from(elements).random(new MersenneTwister(), 4).select();
> + Assert.assertEquals(4, selection.size());
> + Assert.assertEquals(4, selection.get(0).intValue());
> + Assert.assertEquals(1, selection.get(1).intValue());
> + Assert.assertEquals(3, selection.get(2).intValue());
> + Assert.assertEquals(2, selection.get(3).intValue());
> + } finally {
> + Seeder.setSeederStrategy(seedStrategy);
> + }
> + }
> +}
|
