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