Algorithme de sélection des roues de Roulette [dupliquer]

les autres réponses semblent supposer que vous essayez d'implémenter un jeu de roulette. Je pense que vous posez des questions sur la sélection des roues de roulette dans les algorithmes évolutifs.

voici un code Java qui implémente la sélection des roues de roulette.

supposons que vous avez 10 articles à choisir et vous choisissez en générant un nombre aléatoire entre 0 et 1. Vous divisez la gamme 0 à 1 jusqu'à dix non-chevauchement segments, chacun proportionnel à la valeur de l'un des dix éléments. Par exemple, cela pourrait ressembler à ceci:

0 - 0.3 is item 1
0.3 - 0.4 is item 2
0.4 - 0.5 is item 3
0.5 - 0.57 is item 4
0.57 - 0.63 is item 5
0.63 - 0.68 is item 6
0.68 - 0.8 is item 7
0.8 - 0.85 is item 8
0.85 - 0.98 is item 9
0.98 - 1 is item 10

c'est votre roulette. Votre nombre aléatoire entre 0 et 1 est votre tour. Si le nombre aléatoire est de 0,46, alors l'article choisi est l'article 3. Si c'est 0,92, c'est l'article 9.

voici un peu de code python:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        </q/roulette-selection-in-genetic-algorithms-58498/"""
    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

Il y a 2 étapes: tout d'Abord créer un tableau avec toutes les valeurs sur la roue. Il peut s'agir d'un tableau bidimensionnel avec des couleurs et des nombres, ou vous pouvez choisir d'ajouter 100 aux nombres rouges.

génère alors simplement un nombre aléatoire entre 0 ou 1 (selon que votre langue commence à numéroter les index des tableaux à partir de 0 ou 1) et le dernier élément de votre tableau.

la plupart des langues ont intégré des fonctions de nombres aléatoires. En VB et VBScript la fonction est RND() . En Javascript c'est Math.random()

récupérez la valeur de cette position dans le tableau et vous avez votre numéro de roulette aléatoire.

note finale : n'oubliez pas de lancer votre générateur de nombres aléatoires ou vous obtiendrez la même séquence de tirages à chaque fois que vous exécutez le programme.

d'abord, générez un tableau des pourcentages que vous avez attribués, disons p[1..n] et d'assumer le total est la somme de tous les pourcentages.

puis obtenir un nombre aléatoire entre 1 au total, disons r

maintenant, l'algorithme dans lua:

local  c  =  0
for i = 1,n do
    c = c + p[i]
    if r <= c then
        return i
    end
end

voici un moyen très rapide de le faire en utilisant la sélection stream en Java. Il sélectionne les indices d'un tableau en utilisant les valeurs des poids. Aucune pondération cumulative n'est nécessaire en raison des "propriétés mathématiques .

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;        
}

cela pourrait être encore amélioré en utilisant Kahan summation ou la lecture à travers les doubles comme un itérable si le tableau était trop grand pour initialiser à la fois.

je voulais la même chose et j'ai donc créé cette classe de Roulette autonome. Vous lui donnez une série de poids (sous la forme d'un tableau double), et il retournera simplement un index de ce tableau selon un choix aléatoire pondéré.

j'ai créé une classe parce que vous pouvez obtenir une grande vitesse en ne faisant les additions cumulatives qu'une seule fois via le constructeur. C'est C # code, mais profitez du C comme la vitesse et la simplicité!

class Roulette
{
    double[] c;
    double total;
    Random random;

    public Roulette(double[] n) {
        random = new Random();
        total = 0;
        c = new double[n.Length+1];
        c[0] = 0;
        // Create cumulative values for later:
        for (int i = 0; i < n.Length; i++) {
            c[i+1] = c[i] + n[i];
            total += n[i];
        }
    }

    public int spin() {
        double r = random.NextDouble() * total;     // Create a random number between 0 and 1 and times by the total we calculated earlier.
        //int j; for (j = 0; j < c.Length; j++) if (c[j] > r) break; return j-1; // Don't use this - it's slower than the binary search below.

        //// Binary search for efficiency. Objective is to find index of the number just above r:
        int a = 0;
        int b = c.Length - 1;
        while (b - a > 1) {
            int mid = (a + b) / 2;
            if (c[mid] > r) b = mid;
            else a = mid;
        }
        return a;
    }
}

La première les poids sont à vous. Peut-être pourrait-il s'agir de l'aptitude de chaque membre, ou d'une valeur inversement proportionnelle à la position du membre dans le "top 50". Par exemple: Première place = 1,0 pondération, deuxième place = 0,5, troisième place = 0,333, quatrième place = 0,25 pondération etc. etc.

pour une roue de Roulette américaine, vous allez devoir générer un nombre entier aléatoire entre 1 et 38. Il y a 36 nombres, un 0, et un 00.

une des grandes choses à considérer, cependant, est que dans la roulette américaine, leurs sont de nombreux paris différents qui peuvent être faits. Un seul pari peut couvrir 1, 2, 3, 4, 5, 6, deux 12 ou 18 ans différents. Vous pouvez créer une liste de listes où chaque nombre a des flages supplémentaires pour simplifier cela, ou faire tout dans le programmation.

si je l'implémentais en Python, je créerais un Tuple de 0, 00, et de 1 à 36 et j'utiliserais random.choix() à chaque tour.

cela suppose une classe" Classifier " qui a juste une condition de chaîne, un message de chaîne, et une double force. Il suffit de suivre la logique.

-- Paul

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;
}

vous pouvez utiliser une structure de données comme ceci:

Map<A, B> roulette_wheel_schema = new LinkedHashMap<A, B>()

où A est un entier qui représente une poche de la roue de roulette , et B est un indice qui identifie un chromosome dans la population . Le nombre de poches est proportionnel au fitness proportionnel de chaque chromosome:

nombre de poches = (proportionnelles à la condition physique) · (facteur d'échelle)

ensuite nous produisons un aléatoire entre 0 et la taille du schéma de sélection et avec ce nombre aléatoire nous obtenons l'index du chromosome de la roulette.

nous calculons l'erreur relative entre le fitness proportionnel de chaque chromosome et la probabilité d'être sélectionné par le schéma de sélection.

la méthode getRouletteWheel renvoie le schéma de sélection basé sur structure des données antérieures.

private Map<Integer, Integer> getRouletteWheel(
        ArrayList<Chromosome_fitnessProportionate> chromosomes,
        int precision) {

    /*
     * The number of pockets on the wheel
     * 
     * number of pockets in roulette_wheel_schema = probability ·
     * (10^precision)
     */
    Map<Integer, Integer> roulette_wheel_schema = new LinkedHashMap<Integer, Integer>();
    double fitness_proportionate = 0.0D;
    double pockets = 0.0D;
    int key_counter = -1;
    double scale_factor = Math
            .pow(new Double(10.0D), new Double(precision));
    for (int index_cromosome = 0; index_cromosome < chromosomes.size(); index_cromosome++){

        Chromosome_fitnessProportionate chromosome = chromosomes
                .get(index_cromosome);
        fitness_proportionate = chromosome.getFitness_proportionate();
        fitness_proportionate *= scale_factor;
        pockets = Math.rint(fitness_proportionate);
        System.out.println("... " + index_cromosome + " : " + pockets);

        for (int j = 0; j < pockets; j++) {
            roulette_wheel_schema.put(Integer.valueOf(++key_counter),
                    Integer.valueOf(index_cromosome));
        }
    }

    return roulette_wheel_schema;
}

j'ai élaboré un code Java similaire à celui de Dan Dyer (déjà cité). Ma roulette-roue, cependant, sélectionne un élément simple basé sur un vecteur de probabilité (input) et retourne l'index de l'élément sélectionné. Ceci étant dit, le code suivant est plus approprié si la taille de sélection est unitaire et si vous ne supposez pas comment les probabilités sont calculées et la valeur de probabilité Zéro est permise. Le code est autonome et comprend un essai avec 20 tours de roue (pour exécuter.)

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";
 }
}

sous un échantillon d'exécution pour un vecteur proba P = [0,2, 0,1, 0,6, 0,1], WheelElements = [0,1,2,3]:

élément sélectionné 3, P (S)=0.1

élément sélectionné 2, P (s)=0.6

élément sélectionné 3, P (S)=0.1

élément sélectionné 2, P (s)=0.6

élément sélectionné 1, P (S)=0.1

élément sélectionné 2, P (s)=0.6

élément sélectionné 3, P (S)=0.1

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 3, P (S)=0.1

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (S)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 0, P (s)=0.2

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

élément sélectionné 2, P (s)=0.6

le code teste également une roue de roulette avec une probabilité zéro.

je crains que quiconque utilisant le générateur de nombres aléatoires dans construit dans tous les langages de programmation doit être conscient que le nombre généré n'est pas 100% aléatoire.Il convient donc de l'utiliser avec prudence.

générateur de nombres aléatoires pseudo code

• ajouter un à un compteur séquentiel
• obtenir la valeur actuelle du compteur séquentiel
• ajouter la valeur du compteur par le nombre de ticks de l'ordinateur ou une autre valeur de minuterie à petit intervalle
• possibilité d'ajouter des numéros d'addition, comme un numéro d'une pièce de matériel externe comme un générateur de plasma ou un autre type de phénomène quelque peu aléatoire
• divisez le résultat par un nombre premier très grand 359334085968622831041960188598043661065388726959079837 par exemple
• obtenir des chiffres de l'extrême droite de la virgule décimale du résultat
• utilisez ces chiffres comme un nombre aléatoire

utilisez les nombres aléatoires pour créer des nombres aléatoires entre 1 et 38 (ou 37 Européen) pour la roulette.