001package net.sf.cpsolver.ifs.heuristics; 002 003import java.util.ArrayList; 004import java.util.Enumeration; 005import java.util.List; 006 007import 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 Tomáš Müller<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 037public 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}