001 package net.sf.cpsolver.ifs.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.Enumeration;
005 import java.util.List;
006
007 import net.sf.cpsolver.ifs.util.ToolBox;
008
009 /**
010 * A general roulette wheel selection. An object is selected randomly,
011 * proportionaly to the provided weight. This class also supports multiple
012 * selections (it implements {@link Enumeration} interface).
013 *
014 * <br>
015 * <br>
016 *
017 * @version StudentSct 1.2 (Student Sectioning)<br>
018 * Copyright (C) 2007 - 2010 Tomas Muller<br>
019 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
020 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
021 * <br>
022 * This library is free software; you can redistribute it and/or modify
023 * it under the terms of the GNU Lesser General Public License as
024 * published by the Free Software Foundation; either version 3 of the
025 * License, or (at your option) any later version. <br>
026 * <br>
027 * This library is distributed in the hope that it will be useful, but
028 * WITHOUT ANY WARRANTY; without even the implied warranty of
029 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
030 * Lesser General Public License for more details. <br>
031 * <br>
032 * You should have received a copy of the GNU Lesser General Public
033 * License along with this library; if not see
034 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
035 */
036
037 public class RouletteWheelSelection<E> implements Enumeration<E> {
038 private List<E> iAdepts = new ArrayList<E>();
039 private List<Double> iPoints = new ArrayList<Double>();
040 private double iTotalPoints = 0, iUsedPoints = 0;
041 private int iFirst = 0;
042
043 /**
044 * Add an adept to the selection
045 *
046 * @param adept
047 * an object
048 * @param points
049 * object weight (more points, better chance to be selected)
050 */
051 public void add(E adept, double points) {
052 iAdepts.add(adept);
053 iPoints.add(points);
054 iTotalPoints += points;
055 }
056
057 private void swap(int idx1, int idx2) {
058 E a1 = iAdepts.get(idx1);
059 E a2 = iAdepts.get(idx2);
060 iAdepts.set(idx1, a2);
061 iAdepts.set(idx2, a1);
062 Double p1 = iPoints.get(idx1);
063 Double p2 = iPoints.get(idx2);
064 iPoints.set(idx1, p2);
065 iPoints.set(idx2, p1);
066 }
067
068 /** Are there still some adepts that have not been yet selected */
069 @Override
070 public boolean hasMoreElements() {
071 return iFirst < iAdepts.size();
072 }
073
074 /**
075 * Perform selection. An object is selected randomly with the probability
076 * proportional to the provided weight. Each object can be selected only
077 * once.
078 */
079 @Override
080 public E nextElement() {
081 if (!hasMoreElements())
082 return null;
083 double rx = ToolBox.random() * iTotalPoints;
084
085 int iIdx = iFirst;
086 rx -= iPoints.get(iIdx);
087 while (rx > 0 && iIdx + 1 < iAdepts.size()) {
088 iIdx++;
089 rx -= iPoints.get(iIdx);
090 }
091
092 E selectedObject = iAdepts.get(iIdx);
093 double points = iPoints.get(iIdx);
094 iTotalPoints -= points;
095 iUsedPoints += points;
096 swap(iFirst, iIdx);
097 iFirst++;
098
099 return selectedObject;
100 }
101
102 /** Number of objects in the set */
103 public int size() {
104 return iAdepts.size();
105 }
106
107 /** Total value of objects that were already returned by the selection. */
108 public double getUsedPoints() {
109 return iUsedPoints;
110 }
111
112 /** Total value of objects that are still in the selection. */
113 public double getRemainingPoints() {
114 return iTotalPoints;
115 }
116
117 /** Total value of objects that were added into the selection. */
118 public double getTotalPoints() {
119 return iTotalPoints + iUsedPoints;
120 }
121 }