algorithm - resueltos - Algoritmo de selección de ruleta

funcion fitness algoritmos geneticos (12)

Aquí hay un poco de código python:

def roulette_select(population, fitnesses, num): """ Roulette selection, implemented according to: <http://stackoverflow.com/questions/177271/roulette -selection-in-genetic-algorithms/177278#177278> """ total_fitness = float(sum(fitnesses)) rel_fitness = [f/total_fitness for f in fitnesses] # Generate probability intervals for each individual probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))] # Draw new population new_population = [] for n in xrange(num): r = rand() for (i, individual) in enumerate(population): if r <= probs[i]: new_population.append(individual) break return new_population

Esta pregunta ya tiene una respuesta aquí:

Roulette Selection in Genetic Algorithms 12 respuestas

¿Alguien puede proporcionar algún pseudo código para una función de selección de ruleta? ¿Cómo implementaría esto? Realmente no entiendo cómo leer esta notación matemática. Quiero un algoritmo general para esto.

Aquí hay una forma realmente rápida de hacerlo usando la selección de flujo en Java. Selecciona los índices de una matriz usando los valores como pesos. No se necesitan pesos acumulativos debido a las propiedades matemáticas .

static int selectRandomWeighted(double[] wts, Random rnd) { int selected = 0; double total = wts[0]; for( int i = 1; i < wts.length; i++ ) { total += wts[i]; if( rnd.nextDouble() <= (wts[i] / total)) selected = i; } return selected; }

Esto podría mejorarse aún más usando la suma de Kahan o leyendo a través de los dobles como iterable si la matriz era demasiado grande para inicializarla de una vez.

Bueno, para una ruleta americana, vas a necesitar generar un entero aleatorio entre 1 y 38. Hay 36 números, un 0 y un 00.

Una de las grandes cosas a considerar, sin embargo, es que en la ruleta americana, se pueden hacer muchas apuestas diferentes. Una sola apuesta puede cubrir 1, 2, 3, 4, 5, 6, dos diferentes 12 o 18. Si lo desea, puede crear una lista de listas donde cada número tenga flages adicionales para simplificar eso, o hacerlo todo en la programación .

Si lo estuviera implementando en Python, solo crearía una Tupla de 0, 00 y de 1 a 36 y usaré random.choice () para cada giro.

Esto supone un "Clasificador" de clase que solo tiene una condición de Cadena, un mensaje de Cadena y una doble resistencia. Solo sigue la lógica.

-- Pablo

public static List<Classifier> rouletteSelection(int classifiers) { List<Classifier> classifierList = new LinkedList<Classifier>(); double strengthSum = 0.0; double probabilitySum = 0.0; // add up the strengths of the map Set<String> keySet = ClassifierMap.CLASSIFIER_MAP.keySet(); for (String key : keySet) { /* used for debug to make sure wheel is working. if (strengthSum == 0.0) { ClassifierMap.CLASSIFIER_MAP.get(key).setStrength(8000.0); } */ Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key); double strength = classifier.getStrength(); strengthSum = strengthSum + strength; } System.out.println("strengthSum: " + strengthSum); // compute the total probability. this will be 1.00 or close to it. for (String key : keySet) { Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key); double probability = (classifier.getStrength() / strengthSum); probabilitySum = probabilitySum + probability; } System.out.println("probabilitySum: " + probabilitySum); while (classifierList.size() < classifiers) { boolean winnerFound = false; double rouletteRandom = random.nextDouble(); double rouletteSum = 0.0; for (String key : keySet) { Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key); double probability = (classifier.getStrength() / strengthSum); rouletteSum = rouletteSum + probability; if (rouletteSum > rouletteRandom && (winnerFound == false)) { System.out.println("Winner found: " + probability); classifierList.add(classifier); winnerFound = true; } } } return classifierList; }

Hay 2 pasos para esto: Primero crea una matriz con todos los valores en la rueda. Puede ser una matriz bidimensional con color o número, o puede elegir agregar 100 a números rojos.

Luego, simplemente genere un número aleatorio entre 0 o 1 (dependiendo de si su idioma comienza a numerar los índices de matriz de 0 o 1) y el último elemento de su matriz.

La mayoría de los idiomas tienen funciones incorporadas de números aleatorios. En VB y VBScript la función es RND() . En Javascript es Math.random()

Obtenga el valor de esa posición en la matriz y tenga su número de ruleta al azar.

Nota final : no olvides sembrar tu generador de números aleatorios o obtendrás la misma secuencia de sorteos cada vez que ejecutes el programa.

He elaborado un código Java similar al de Dan Dyer (referenciado anteriormente). Mi ruleta, sin embargo, selecciona un solo elemento basado en un vector de probabilidad (entrada) y devuelve el índice del elemento seleccionado. Habiendo dicho eso, el siguiente código es más apropiado si el tamaño de selección es unitario y si no se supone cómo se calculan las probabilidades y si se permite un valor de probabilidad cero. El código es autónomo e incluye una prueba con 20 giros de rueda (para ejecutar).

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; import java.util.logging.Level; import java.util.logging.Logger; /** * Roulette-wheel Test version. * Features a probability vector input with possibly null probability values. * Appropriate for adaptive operator selection such as Probability Matching * or Adaptive Pursuit, (Dynamic) Multi-armed Bandit. * @version October 2015. * @author Hakim Mitiche */ public class RouletteWheel { /** * Selects an element probabilistically. * @param wheelProbabilities elements probability vector. * @param rng random generator object * @return selected element index * @throws java.lang.Exception */ public int select(List<Double> wheelProbabilities, Random rng) throws Exception{ double[] cumulativeProba = new double[wheelProbabilities.size()]; cumulativeProba[0] = wheelProbabilities.get(0); for (int i = 1; i < wheelProbabilities.size(); i++) { double proba = wheelProbabilities.get(i); cumulativeProba[i] = cumulativeProba[i - 1] + proba; } int last = wheelProbabilities.size()-1; if (cumulativeProba[last] != 1.0) { throw new Exception("The probabilities does not sum up to one (" + "sum="+cumulativeProba[last]); } double r = rng.nextDouble(); int selected = Arrays.binarySearch(cumulativeProba, r); if (selected < 0) { /* Convert negative insertion point to array index. to find the correct cumulative proba range index. */ selected = Math.abs(selected + 1); } /* skip indexes of elements with Zero probability, go backward to matching index*/ int i = selected; while (wheelProbabilities.get(i) == 0.0){ System.out.print(i+" selected, correction"); i--; if (i<0) i=last; } selected = i; return selected; } public static void main(String[] args){ RouletteWheel rw = new RouletteWheel(); int rept = 20; List<Double> P = new ArrayList<>(4); P.add(0.2); P.add(0.1); P.add(0.6); P.add(0.1); Random rng = new Random(); for (int i = 0 ; i < rept; i++){ try { int s = rw.select(P, rng); System.out.println("Element selected "+s+ ", P(s)="+P.get(s)); } catch (Exception ex) { Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex); } } P.clear(); P.add(0.2); P.add(0.0); P.add(0.5); P.add(0.0); P.add(0.1); P.add(0.2); //rng = new Random(); for (int i = 0 ; i < rept; i++){ try { int s = rw.select(P, rng); System.out.println("Element selected "+s+ ", P(s)="+P.get(s)); } catch (Exception ex) { Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex); } } } /** * {@inheritDoc} * @return */ @Override public String toString() { return "Roulette Wheel Selection"; } }

Debajo de una muestra de ejecución para un vector de probabilidad P = [0.2,0.1,0.6,0.1], WheelElements = [0,1,2,3]:

Elemento seleccionado 3, P (s) = 0.1