Menu
▾
▴
[cilib-devel] [PATCH 1/5] Generic selection class with fluent interface.
|
From: Wiehann M. <wcm...@gm...> - 2009-05-23 00:47:08
|
From: Gary Pampara <gpa...@gm...>
The need to provide a wide variety of selection mechanisms is very
important. There is, however, a problem that is associated with this
concept and that is that it has resulted in a plethora of classes that
have been implemented to achieve this.
This patch proposes a new manner to do such a selection mechanism,
however, the selections are all generic and the process is fluent and
obvious.
More additions will be added - this is a positive step though!
Signed-off-by: Gary Pampara <gpa...@gm...>
---
.../selection/TournamentSelectionStrategy.java | 20 +--
.../selectionstrategies/generic/Ordering.java | 41 +++++
.../generic/RandomOrdering.java | 46 ++++++
.../selectionstrategies/generic/Selection.java | 156 ++++++++++++++++++++
.../generic/SortedOrdering.java | 46 ++++++
.../selectionstrategies/generic/SelectionTest.java | 107 +++++++++++++
6 files changed, 402 insertions(+), 14 deletions(-)
create mode 100644 src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Ordering.java
create mode 100644 src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/RandomOrdering.java
create mode 100644 src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Selection.java
create mode 100644 src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SortedOrdering.java
create mode 100644 src/test/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SelectionTest.java
diff --git a/src/main/java/net/sourceforge/cilib/entity/operators/selection/TournamentSelectionStrategy.java b/src/main/java/net/sourceforge/cilib/entity/operators/selection/TournamentSelectionStrategy.java
index 96f77bf..239f783 100644
--- a/src/main/java/net/sourceforge/cilib/entity/operators/selection/TournamentSelectionStrategy.java
+++ b/src/main/java/net/sourceforge/cilib/entity/operators/selection/TournamentSelectionStrategy.java
@@ -21,8 +21,6 @@
*/
package net.sourceforge.cilib.entity.operators.selection;
-import java.util.ArrayList;
-import java.util.Collections;
import java.util.List;
import net.sourceforge.cilib.controlparameter.ControlParameter;
@@ -31,6 +29,9 @@ 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.RandomNumber;
+import net.sourceforge.cilib.util.selection.selectionstrategies.generic.RandomOrdering;
+import net.sourceforge.cilib.util.selection.selectionstrategies.generic.Selection;
+import net.sourceforge.cilib.util.selection.selectionstrategies.generic.SortedOrdering;
/**
* Perform a tournament selection process on the provided {@linkplain Topology}
@@ -72,19 +73,10 @@ public class TournamentSelectionStrategy extends SelectionStrategy {
*/
public <T extends Entity> T select(Topology<T> population) {
int tournamentSize = Double.valueOf(this.tournamentProportion.getParameter()*population.size()).intValue();
+ List<T> selection = Selection.from(population.asList()).apply(new RandomOrdering<T>()).first(tournamentSize)
+ .apply(new SortedOrdering<T>()).last().select();
- List<T> tournamentEntities = new ArrayList<T>();
-
- for (int i = 0; i < tournamentSize; i++) {
- double random = randomNumber.getUniform(0, population.size());
- T tmp = population.get(Double.valueOf(random).intValue());
-
- tournamentEntities.add(tmp);
- }
-
- Collections.sort(tournamentEntities, tournamentEntities.get(0).getComparator());
-
- return tournamentEntities.get(0);
+ return selection.get(0);
}
/**
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Ordering.java b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Ordering.java
new file mode 100644
index 0000000..46e2a50
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Ordering.java
@@ -0,0 +1,41 @@
+/**
+ * Copyright (C) 2003 - 2008
+ * 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.selectionstrategies.generic;
+
+import java.util.List;
+
+/**
+ * An ordering is a construct to define how a list of elements should be ordered.
+ * The ordering is a simple function that does a single action.
+ * @param <E> The type to apply the ordering to.
+ * @author gpampara
+ */
+public interface Ordering<E> {
+
+ /**
+ * Apply the ordering on the provided list.
+ * @param elements The list to be ordered.
+ * @return {@code true} if successful, {@code false} otherwise.
+ */
+ public boolean apply(List<E> elements);
+
+}
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/RandomOrdering.java b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/RandomOrdering.java
new file mode 100644
index 0000000..6d307c6
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/RandomOrdering.java
@@ -0,0 +1,46 @@
+/**
+ * Copyright (C) 2003 - 2008
+ * 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.selectionstrategies.generic;
+
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Apply a random ordering to the provided list. This class defines that the
+ * list instance will have it's internal order randomly shuffled.
+ * @param <E> The comparable type.
+ * @author gpampara
+ */
+public class RandomOrdering<E extends Comparable> implements Ordering<E> {
+
+ /**
+ * Randomly arrange the provided list.
+ * @param elements The list to randomly order.
+ * @return {@code true} if successful, {@code false} otherwise.
+ */
+ @Override
+ public boolean apply(List<E> elements) {
+ Collections.shuffle(elements);
+ return true;
+ }
+
+}
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Selection.java b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Selection.java
new file mode 100644
index 0000000..04cb360
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/Selection.java
@@ -0,0 +1,156 @@
+/**
+ * Copyright (C) 2003 - 2008
+ * 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.selectionstrategies.generic;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * <p>
+ * A {@code Selection} is an abstraction that allows operations to be applied to
+ * a list instace that result in a selection of list elements, based on a varied of
+ * potential combination of operators.
+ * </p>
+ * <p>
+ * The {@code Selection} is implemented to be a fluent interface that is easily
+ * understandable and for which the intent of the selection is clear.
+ * </p>
+ * <p>
+ * As an example, applying tournament selection on a list of {@code Entity} instances
+ * would be done as follows:
+ * </p>
+ * <pre>
+ * List<T> selection = Selection.from(population.asList()).apply(new RandomOrdering<T>()).first(tournamentSize)
+ * .apply(new SortedOrdering<T>()).last().select();
+ *
+ * return selection.get(0);
+ * </pre>
+ * <p>
+ * where {@code T} is a {@link Comparable} type. The above performs the following steps:
+ * </p>
+ * <ol>
+ * <li>From the provided list of entities, order the entities randomly.</li>
+ * <li>From the randomized list, select the first {@code tournamentSize} entities.</li>
+ * <li>From the subset of elements, order them from smallest to largest, based on fitness.</li>
+ * <li>Finally, select the entity that is the "most fit" and then return it as the winner of the tournament.</li>
+ * </ol>
+ * @param <E> The comparable type.
+ * @author gpampara
+ */
+public final class Selection<E extends Comparable> {
+
+ private final List<E> elements;
+
+ /**
+ * Assign the Selection to take palce on the porvided list. The list
+ * is copied to ensure that the original list reference is not altered.
+ * @param elements The elements on which the selection should take place.
+ */
+ private Selection(List<E> elements) {
+ this.elements = new ArrayList(elements);
+ }
+
+ /**
+ * Create a selection that will operate from the provided list.
+ * @param <T> The comparable type.
+ * @param elements The list to operate on.
+ * @return A selection based on the provided list.
+ */
+ public static <T extends Comparable> Selection<T> from(List<T> elements) {
+ return new Selection<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 apply.
+ * @return A selection upon which the ordering has be applied.
+ * @throws UnsupportedOperationException if the ordering cannot be applied.
+ */
+ public Selection<E> apply(Ordering<E> ordering) {
+ boolean result = ordering.apply(elements);
+
+ if (result)
+ return new Selection<E>(elements);
+
+ throw new UnsupportedOperationException("The ordering [" + ordering.getClass().getSimpleName()
+ + "] cannot be applied to the selection. Please ensure that the intention of the ordering 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.
+ */
+ public Selection<E> first() {
+ return new Selection<E>(Arrays.asList(elements.get(0)));
+ }
+
+ /**
+ * 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.
+ */
+ public Selection<E> first(int number) {
+ return new Selection<E>(elements.subList(0, number));
+ }
+
+ /**
+ * Obtain the last element contained within the current selection.
+ * @return A selection containing the last element.
+ */
+ public Selection<E> last() {
+ return new Selection<E>(Arrays.asList(elements.get(elements.size()-1)));
+ }
+
+ /**
+ * 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.
+ */
+ public Selection<E> last(int number) {
+ return new Selection<E>(elements.subList(elements.size()-number, elements.size()));
+ }
+
+ /**
+ * Return the reverse ordering of the provided selection.
+ * @return The selection in reverse.
+ */
+ public Selection<E> reverse() {
+ List<E> list = new ArrayList<E>(elements);
+ Collections.reverse(list);
+ return new Selection<E>(list);
+ }
+
+ /**
+ * Obtain the result of the selection.
+ * @return A list of elements that the selection has selected.
+ */
+ public List<E> select() {
+ return this.elements;
+ }
+
+}
diff --git a/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SortedOrdering.java b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SortedOrdering.java
new file mode 100644
index 0000000..a89ec10
--- /dev/null
+++ b/src/main/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SortedOrdering.java
@@ -0,0 +1,46 @@
+/**
+ * Copyright (C) 2003 - 2008
+ * 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.selectionstrategies.generic;
+
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Apply a sorting operation to the provided list, ordering the list naturally
+ * from smallest to largest.
+ * @param <E> The comparable type.
+ * @author gpampara
+ */
+public class SortedOrdering<E extends Comparable> implements Ordering<E> {
+
+ /**
+ * Sort the provided list in a natural order.
+ * @param element The list to sort.
+ * @return {@code true} if successful, {@code false} otherwise.
+ */
+ @Override
+ public boolean apply(List<E> element) {
+ Collections.sort(element);
+ return true;
+ }
+
+}
diff --git a/src/test/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SelectionTest.java b/src/test/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SelectionTest.java
new file mode 100644
index 0000000..2191cec
--- /dev/null
+++ b/src/test/java/net/sourceforge/cilib/util/selection/selectionstrategies/generic/SelectionTest.java
@@ -0,0 +1,107 @@
+/**
+ * Copyright (C) 2003 - 2008
+ * 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.selectionstrategies.generic;
+
+import java.util.Arrays;
+import java.util.List;
+import net.sourceforge.cilib.ec.Individual;
+import net.sourceforge.cilib.entity.EntityType;
+import net.sourceforge.cilib.problem.Fitness;
+import net.sourceforge.cilib.problem.MaximisationFitness;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ *
+ * @author gpampara
+ */
+public class SelectionTest {
+
+ @Test
+ public void randomSelectionOfFive() {
+ List<Integer> elements = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
+
+ List<Integer> selection = Selection.from(elements).apply(new RandomOrdering()).first(5).select();
+
+ Assert.assertEquals(5, selection.size());
+ }
+
+
+ @Test
+ public void tournamentSelection() {
+ List<Integer> elements = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
+ List<Integer> selection = Selection.from(elements).apply(new RandomOrdering()).first(4).apply(new SortedOrdering()).last().select();
+
+ Assert.assertEquals(1, selection.size());
+ }
+
+ @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 entitySelection() {
+ Individual i1 = createIndividual(new MaximisationFitness(1.0));
+ Individual i2 = createIndividual(new MaximisationFitness(2.0));
+ Individual i3 = createIndividual(new MaximisationFitness(3.0));
+
+ List<Individual> individuals = Arrays.asList(i1, i2, i3);
+ List<Individual> selection = Selection.from(individuals).apply(new SortedOrdering<Individual>()).first().select();
+
+ Assert.assertEquals(1, selection.size());
+ Assert.assertSame(i1, selection.get(0));
+ }
+
+ private Individual createIndividual(Fitness fitness) {
+ Individual i = new Individual();
+ i.getProperties().put(EntityType.FITNESS, fitness);
+ return i;
+ }
+
+}
--
1.6.0.6
|
