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 presentado por James Baker. [1]
SUS es un desarrollo de la selección proporcional a la aptitud (FPS) que no presenta sesgos y una dispersión mínima. Cuando FPS elige varias soluciones de la población mediante muestreo aleatorio repetido, SUS utiliza un único valor aleatorio para muestrear todas las soluciones eligiéndolas a intervalos espaciados uniformemente . Esto da a los miembros más débiles de la población (según su aptitud) la oportunidad de ser elegidos.
Los FPS pueden tener un mal rendimiento cuando un miembro de la población tiene una aptitud física realmente grande en comparación con otros miembros. Usando una regla similar a un 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 para 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 los Puntos I : = 0 mientras que la suma de aptitud de la Población [0 .. I ] < P I ++ añadir Población [ I ] para Conservar volver Conservar
¿Dónde está el conjunto de individuos con índice de matriz 0 a (incluido) I ?Population[0..I]
Aquí RWS () describe la mayor parte de la selección de la aptitud proporcional (también conocido como " ruleta selección de rueda ") - en verdadero fitness selección proporcional el parámetro Puntos es siempre una lista (ordenada) de números aleatorios de 0 a F . El algoritmo anterior está destinado a ser ilustrativo en lugar de canónico.
Ver también
Referencias
- ^ 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.