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