genetic algorithm - resueltos - Selección de Ruleta en Algoritmos Genéticos
presion de seleccion algoritmo genetico (12)
¿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. Nunca tomé ninguna probabilidad o estadística.
Aquí hay un código 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**
Aquí hay una implementación java compacta que escribí recientemente para la selección de ruleta, con suerte de uso.
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;
}
De acuerdo, entonces hay 2 métodos para la implementación de la selección de ruleta : Aceptación usual y estocástica .
Algoritmo usual :
# 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!
Algoritmo de aceptación estocástica :
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
Puede elegir cualquiera de ellos, devolverán resultados idénticos.
Recursos útiles:
http://natureofcode.com/book/chapter-9-the-evolution-of-code : un capítulo claro y sencillo para principiantes sobre algoritmos genéticos. explica la selección de la rueda de ruleta como un cubo de letras de madera (mientras más lo pones, más grande es la posibilidad de elegir un algoritmo A, usual ).
https://en.wikipedia.org/wiki/Fitness_proportionate_selection - describe el algoritmo de aceptación estocástica .
De la respuesta anterior, obtuve lo siguiente, que fue más claro para mí que la respuesta en sí.
Para dar un ejemplo:
Aleatorio (suma) :: Aleatorio (12) Iterando a través de la población, verificamos lo siguiente: al azar <suma
Permítanos elegir 7 como el número aleatorio.
Index | Fitness | Sum | 7 < Sum
0 | 2 | 2 | false
1 | 3 | 5 | false
2 | 1 | 6 | false
3 | 4 | 10 | true
4 | 2 | 12 | ...
A través de este ejemplo, el más apto (Índice 3) tiene el porcentaje más alto de ser elegido (33%); como el número aleatorio solo tiene que aterrizar dentro de 6-> 10, y será elegido.
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;
}
}
El Prof. Thrun, del laboratorio de IA de Stanford, también presentó un rápido (¿?) Código de re-muestreo en Python durante su CS373 de Udacity. El resultado de búsqueda de Google llevó al siguiente enlace:
http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm
Espero que esto ayude
El pseudocódigo publicado contenía algunos elementos poco claros, y agrega la complejidad de generar descendencia en lugar de realizar una selección pura. Aquí hay una implementación simple de Python de ese pseudocódigo:
def roulette_select(population, fitnesses, num):
""" Roulette selection, implemented according to:
<http://.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
Escribí una versión en C # y realmente estoy buscando confirmación de que sea correcta:
(roulette_selector es un número aleatorio que estará en el rango de 0.0 a 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;
}
Esto se llama selección de ruleta mediante aceptación estocástica:
/// /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;
}
}
El número promedio de intentos necesarios para una única selección es:
τ = f max / avg (f)
- f max es la aptitud máxima de la población
- avg (f) es la aptitud promedio
τ no depende explícitamente del número de individuos en la población (N), pero la relación puede cambiar con N.
Sin embargo, en muchas aplicaciones (donde la aptitud permanece limitada y la aptitud promedio no disminuye a 0 para aumentar N), τ no aumenta sin límites con N y, por lo tanto, una complejidad típica de este algoritmo es O (1) (selección de ruleta usando los algoritmos de búsqueda tienen complejidad O (N) u O (log N).
La distribución de probabilidad de este procedimiento es de hecho la misma que en la selección de rueda de ruleta clásica.
Para más detalles ver:
- Selección de rueda de la ruleta mediante aceptación estocástica (Adam Liposki, Dorota Lipowska - 2011)
Han pasado unos años desde que hice esto yo mismo, sin embargo, el siguiente pseudo código se encontró con bastante facilidad en 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
El sitio de donde vino esto se puede encontrar here si necesita más detalles.
Ya hay muchas soluciones correctas, pero creo que este código es más claro.
def select(fs):
p = random.uniform(0, sum(fs))
for i, f in enumerate(fs):
if p <= 0:
break
p -= f
return i
Además, si acumula el fs, puede producir una solución más eficiente.
cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]
def select(cfs):
return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))
Esto es más rápido y es un código extremadamente conciso. STL en C ++ tiene un algoritmo de bisección similar disponible si ese es el idioma que está usando.
Selección de rueda de ruleta en 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;
}