Sélection de la roulette dans les algorithmes génétiques
https://stackoverflow.com/questions/177271
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelqu'un peut-il fournir un pseudo-code pour une fonction de sélection de roulette? Comment pourrais-je implémenter ceci:
Je ne comprends pas vraiment comment lire cette notation mathématique. Je n'ai jamais pris aucune probabilité ou statistique.
La solution
Cela fait quelques années que je l'ai fait moi-même, mais le pseudo-code suivant a été trouvé assez facilement sur Google.
for all members of population
sum += fitness of this individual
end for
for all members of population
probability = sum of probabilities + (fitness / sum)
sum of probabilities += probability
end for
loop until new population is full
do this twice
number = Random between 0 and 1
for all members of population
if number > probability but less than next probability
then you have been selected
end for
end
create offspring
end loop
Vous pouvez trouver ici si vous avez besoin d'autres informations. détails.
Autres conseils
Beaucoup de solutions correctes déjà, mais je pense que ce code est plus clair.
def select(fs):
p = random.uniform(0, sum(fs))
for i, f in enumerate(fs):
if p <= 0:
break
p -= f
return i
De plus, si vous accumulez le fs, vous pouvez produire une solution plus efficace.
cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]
def select(cfs):
return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))
C’est à la fois plus rapide et extrêmement concis. STL en C ++ dispose d'un algorithme de bissection similaire si c'est le langage que vous utilisez.
Le pseudo-code affiché contient des éléments peu clairs et ajoute à la complexité de la génération de progéniture au lieu d'effectuer une sélection pure. Voici une implémentation python simple de ce pseudocode:
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
Ceci s'appelle la sélection de la roue de roulette via l'acceptation stochastique:
/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.
unsigned rw_selection(double f_max)
{
for (;;)
{
// Select randomly one of the individuals
unsigned i(random_individual());
// The selection is accepted with probability fitness(i) / f_max
if (uniform_random_01() < fitness(i) / f_max)
return i;
}
}
Le nombre moyen de tentatives nécessaires pour une sélection unique est:
& # 964; = f
- f max est l'aptitude maximale de la population
- avg (f) est l’aptitude moyenne
& # 964; ne dépend pas explicitement du nombre d'individus dans la population (N), mais le rapport peut changer avec N.
Cependant, dans de nombreuses applications (où la forme physique reste limitée et la forme moyenne ne diminue pas à 0 si vous augmentez N) & # 964; n'augmente pas de manière illimitée avec N et donc une complexité typique de cet algorithme est O (1) (la sélection de la roue de roulette à l'aide d'algorithmes de recherche a une complexité O (N) ou O (log N)).
La distribution de probabilité de cette procédure est en effet la même que dans la sélection de roue à roulette classique.
Pour plus de détails, voir:
- Sélection de la roulette par acceptation stochastique (Adam Liposki, Dorota Lipowska - 2011)
Voici du code en C:
// Find the sum of fitnesses. The function fitness(i) should
//return the fitness value for member i**
float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
sumFitness += fitness(i);
// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;
// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;
while (randomNumber > partialSum)
{
partialSum += fitness(memberID);
memberID++;
}
**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**
De la réponse ci-dessus, j'ai obtenu ce qui suit, ce qui était plus clair pour moi que la réponse elle-même.
Pour donner un exemple:
Aléatoire (somme) :: Aléatoire (12) En parcourant la population, nous vérifions les éléments suivants: random & Lt; somme
Choisissons 7 comme nombre aléatoire.
Index | Fitness | Sum | 7 < Sum
0 | 2 | 2 | false
1 | 3 | 5 | false
2 | 1 | 6 | false
3 | 4 | 10 | true
4 | 2 | 12 | ...
Dans cet exemple, le plus apte (Index 3) a le pourcentage le plus élevé d’être choisi (33%); comme le nombre aléatoire doit seulement atterrir dans 6 - > 10, et il sera choisi.
for (unsigned int i=0;i<sets.size();i++) {
sum += sets[i].eval();
}
double rand = (((double)rand() / (double)RAND_MAX) * sum);
sum = 0;
for (unsigned int i=0;i<sets.size();i++) {
sum += sets[i].eval();
if (rand < sum) {
//breed i
break;
}
}
Prof. Thrun of Stanford AI lab a également présenté un code de ré-échantillonnage rapide (er?) En python lors de son CS373 d'Udacity. Le résultat de la recherche Google a conduit au lien suivant:
http://www.udacity-forums.com/ cs373 / questions / 20194 / algorithme de rééchantillonnage rapide
J'espère que cela vous aidera
Voici une implémentation Java compacte que j’ai récemment écrite pour la sélection de la roulette et que nous espérons utile.
public static gene rouletteSelection()
{
float totalScore = 0;
float runningScore = 0;
for (gene g : genes)
{
totalScore += g.score;
}
float rnd = (float) (Math.random() * totalScore);
for (gene g : genes)
{
if ( rnd>=runningScore &&
rnd<=runningScore+g.score)
{
return g;
}
runningScore+=g.score;
}
return null;
}
Sélection de la roue de roulette dans MatLab:
TotalFitness=sum(Fitness);
ProbSelection=zeros(PopLength,1);
CumProb=zeros(PopLength,1);
for i=1:PopLength
ProbSelection(i)=Fitness(i)/TotalFitness;
if i==1
CumProb(i)=ProbSelection(i);
else
CumProb(i)=CumProb(i-1)+ProbSelection(i);
end
end
SelectInd=rand(PopLength,1);
for i=1:PopLength
flag=0;
for j=1:PopLength
if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
flag=1;
break;
end
end
if(flag==0)
SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
end
end
Based on my research ,Here is another implementation in C# if there is a need for it:
//those with higher fitness get selected wit a large probability
//return-->individuals with highest fitness
private int RouletteSelection()
{
double randomFitness = m_random.NextDouble() * m_totalFitness;
int idx = -1;
int mid;
int first = 0;
int last = m_populationSize -1;
mid = (last - first)/2;
// ArrayList's BinarySearch is for exact values only
// so do this by hand.
while (idx == -1 && first <= last)
{
if (randomFitness < (double)m_fitnessTable[mid])
{
last = mid;
}
else if (randomFitness > (double)m_fitnessTable[mid])
{
first = mid;
}
mid = (first + last)/2;
// lies between i and i+1
if ((last - first) == 1)
idx = last;
}
return idx;
}
OK, il existe donc 2 méthodes pour mettre en œuvre la sélection de la roue de roulette : Usual et une acceptation stochastique .
Algorithme habituel :
# there will be some amount of repeating organisms here.
mating_pool = []
all_organisms_in_population.each do |organism|
organism.fitness.times { mating_pool.push(organism) }
end
# [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism]
return mating_pool.sample #=> random, likely fit, parent!
Algorithme d'acceptation stochastique :
max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0]
loop do
random_parent = all_organisms_in_population.sample
probability = random_parent.fitness/max_fitness_in_population * 100
# if random_parent's fitness is 90%,
# it's very likely that rand(100) is smaller than it.
if rand(100) < probability
return random_parent #=> random, likely fit, parent!
else
next #=> or let's keep on searching for one.
end
end
Vous pouvez choisir soit, ils renverront des résultats identiques.
Ressources utiles:
http://natureofcode.com/book/chapter-9 -the-evolution-of-code - un chapitre clair et convivial pour les débutants sur les algorithmes génétiques. explique la sélection de la roue de roulette sous la forme d'un seau de lettres en bois (plus vous en mettez, plus vous avez de chances de choisir un algorithme A, Usual ).
https://en.wikipedia.org/wiki/Fitness_proportionate_selection - décrit Algorithme d'acceptation stochastique .
Cette extension de tableau Swift 4 implémente la sélection aléatoire pondérée, a.k.a une sélection de roulette à partir de ses éléments:
public extension Array where Element == Double {
/// Consider the elements as weight values and return a weighted random selection by index.
/// a.k.a Roulette wheel selection.
func weightedRandomIndex() -> Int {
var selected: Int = 0
var total: Double = self[0]
for i in 1..<self.count { // start at 1
total += self[i]
if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
}
return selected
}
}
Par exemple, étant donné le tableau à deux éléments:
[0.9, 0.1]
weightedRandomIndex() retournera zéro 90% du temps et un 10% du temps.
Voici un test plus complet:
let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
let index = weights.weightedRandomIndex()
results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
print(weights[key], Double(val)/Double(n))
}
sortie:
0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092
Cette réponse est fondamentalement la même que celle d'Andrew Mao: https://stackoverflow.com/a/15582983/74975
J'ai écrit une version en C # et je recherche vraiment une confirmation de son exactitude:
(roulette_selector est un nombre aléatoire compris entre 0,0 et 1,0)
private Individual Select_Roulette(double sum_fitness)
{
Individual ret = new Individual();
bool loop = true;
while (loop)
{
//this will give us a double within the range 0.0 to total fitness
double slice = roulette_selector.NextDouble() * sum_fitness;
double curFitness = 0.0;
foreach (Individual ind in _generation)
{
curFitness += ind.Fitness;
if (curFitness >= slice)
{
loop = false;
ret = ind;
break;
}
}
}
return ret;
}
