Introducción
Implementar y probar el algoritmo de selección basado en la roulette wheel (fitness proportionate selection) en el lenguaje de programación Java.
En esta implementación la roulette wheel es una estructura de datos de este tipo:
Map<A, B> roulette_wheel_schema = new LinkedHashMap<A, B>()
donde A es un entero que representa a una casilla en la roulette, y B es un índice que identifica a un cromosoma en la población. El número de casillas es proporcional al fitness de cada cromosoma.
Al final del test, calculamos el error relativo entre el fitness proporcional de cada cromosoma y la probabilidad de ser seleccionado por el esquema de selección.
Código fuente
http://miraynopodrasverlo.blogspot.com.es/p/java-source-code.html
Descripción
- asignar valores iniciales
- generar una población inicial de n cromosomas
- FOR cada cromosoma
- en este ejemplo el fitness inicial es un número aleatorio
- calcular la proporción del fitness
- END FOR
- crear el esquema de selección (roulette-wheel selection)
- FOR cada cromosoma
- número de casillas = (fitness proporcional) · (factor de escala)
- END FOR
- test
- FOR número de lanzamientos (spins)
- generar un random entre 0 y el tamaño del esquema de selección
- recuperar el índice del cromosoma de la ruleta
- contar el número de ocurrencias de cada cromosoma
- END FOR
- mostrar la distribución de probabilidad
Variables iniciales
- número de cromosomas en la población = 10
- precisión = 2
Resultados
Para un número de lanzamientos = 1000000 estos son los resultados:
- ... 0 --> Chromosome [fitness=7.694008369786496, fitness_proportionate=0.063]
- ... 1 --> Chromosome [fitness=1.6406684960216167, fitness_proportionate=0.013]
- ... 2 --> Chromosome [fitness=6.048016494883929, fitness_proportionate=0.049]
- ... 3 --> Chromosome [fitness=31.5955002279594, fitness_proportionate=0.26]
- ... 4 --> Chromosome [fitness=36.09351840539292, fitness_proportionate=0.29]
- ... 5 --> Chromosome [fitness=12.400516138567356, fitness_proportionate=0.1]
- ... 6 --> Chromosome [fitness=9.891063532209355, fitness_proportionate=0.08]
- ... 7 --> Chromosome [fitness=5.778474137019243, fitness_proportionate=0.047]
- ... 8 --> Chromosome [fitness=2.453778365738421, fitness_proportionate=0.02]
- ... 9 --> Chromosome [fitness=9.414207571604816, fitness_proportionate=0.077]
El número de casillas en la ruleta para cada cromosoma es:
número de casillas = (fitness proporcional) · (factor de escala)
donde el factor de escala = 10^(precisión). En este ejemplo la precisión es igual a 2.
- ... 0 --> 6.0
- ... 1 --> 1.0
- ... 2 --> 5.0
- ... 3 --> 26.0
- ... 4 --> 29.0
- ... 5 --> 10.0
- ... 6 --> 8.0
- ... 7 --> 5.0
- ... 8 --> 2.0
- ... 9 --> 8.0
Y el error relativo de la probabilidad respecto al fitness proporcional:
- ... 0 --> probability = 0.05996 , %error = 0.00304 %
- ... 1 --> probability = 0.009887 , %error = 0.003113 %
- ... 2 --> probability = 0.04994 , %error = -9.4E-4 %
- ... 3 --> probability = 0.2598 , %error = 2.0E-4 %
- ... 4 --> probability = 0.29 , %error = 0.0 %
- ... 5 --> probability = 0.1003 , %error = -3.0E-4 %
- ... 6 --> probability = 0.0804 , %error = -4.0E-4 %
- ... 7 --> probability = 0.04997 , %error = -0.00297 %
- ... 8 --> probability = 0.0202 , %error = -2.0E-4 %
- ... 9 --> probability = 0.07955 , %error = -0.00255 %
- ... (sum probability = 1.0)
