stringtranslate.com

Muestreo universal estocástico

Ejemplo de SUS

El muestreo universal estocástico ( SUS ) es una técnica utilizada en algoritmos genéticos para seleccionar soluciones potencialmente útiles para la recombinación. Fue introducida por James Baker. [1]

SUS es un desarrollo de la selección proporcional a la aptitud (FPS) que no muestra sesgo y una dispersión mínima. Mientras que FPS elige varias soluciones de la población mediante un muestreo aleatorio repetido, SUS utiliza un único valor aleatorio para muestrear todas las soluciones eligiéndolas a intervalos espaciados uniformemente . Esto les da a los miembros más débiles de la población (según su aptitud) la posibilidad de ser elegidos.

Los FPS pueden tener un mal desempeño cuando un miembro de la población tiene una aptitud muy alta en comparación con otros miembros. Utilizando una regla con forma de peine, SUS comienza con un pequeño número aleatorio y elige a los siguientes candidatos del resto de la población restante, sin permitir que los miembros más aptos saturen el espacio de candidatos.

Descrito como un algoritmo, el pseudocódigo para SUS se ve así:

SUS( Población , N ) F  := aptitud total de la Población  N  := número de descendientes a mantener P  := distancia entre los punteros ( F / N ) Inicio  := número aleatorio entre 0 y P  Punteros  := [ Inicio + i * P | i  en [0..( N -1)]] devuelve RWS( Población , Punteros )RWS( Población , Puntos ) Mantener = [] para  P  en  Puntos  I  := 0 mientras la suma de aptitud de Población [0.. I ] < P  I ++ añadir Población [ I ] a Mantener  devolver  Mantener

¿Dónde está el conjunto de individuos con índice de matriz de 0 a (e incluyendo) I ?Population[0..I]

Aquí, RWS() describe la mayor parte de la selección proporcional a la aptitud (también conocida como " selección de ruleta "): en la verdadera selección proporcional a la aptitud, el parámetro Points siempre es una lista (ordenada) de números aleatorios de 0 a F. El algoritmo anterior pretende ser ilustrativo en lugar de canónico.

Véase también

Referencias

  1. ^ Baker, James E. (1987). "Reducción del sesgo y la ineficiencia en el algoritmo de selección". Actas de la Segunda Conferencia Internacional sobre Algoritmos Genéticos y su Aplicación . Hillsdale, Nueva Jersey: L. Erlbaum Associates: 14–21.