Actualmente estoy escribiendo un algoritmo de optimización del diseño del teclado en C (como el diseñado por Peter Klausler) y quiero implementar una selección proporcional al estado físico como se describe aquí (Enlace PDF):

Con la selección de ruleta, seleccionas miembros de la población en base a un modelo de rueda roullete. Haga un gráfico circular, donde el área de la porción de un miembro con respecto al círculo completo sea la proporción de la aptitud de los miembros con respecto a la población total. Como puede ver si un punto en la circunferencia del círculo se selecciona al azar, aquellos miembros de la población con mayor aptitud física tendrán una mayor probabilidad de ser elegido. Esto asegura que la selección natural tenga lugar.

El problema es que no veo cómo implementarlo de manera eficiente. He pensado en dos métodos: uno no es confiable y el otro es lento.

Primero, el lento:

Para un grupo de teclados de longitud N, cree una matriz de longitud N donde cada elemento de la matriz contenga dos elementos, un valor mínimo y uno máximo. Cada teclado tiene un valor mínimo y máximo correspondiente, y el rango se basa en la aptitud del teclado. Por ejemplo, si el teclado cero tiene una aptitud de 10, el teclado uno tiene una aptitud de 20 y el teclado dos tiene una aptitud de 25, se vería así: Código:

array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;

(En este caso, una mejor condición física es mejor, ya que significa que se requiere menos esfuerzo).

Entonces genera un número aleatorio. Para cualquier rango en el que caiga ese número, el teclado correspondiente se "mata" y se reemplaza con la descendencia de un teclado diferente. Repita esto tantas veces como desee.

El problema con esto es que es muy lento. Toma O (N ^ 2) operaciones para terminar.

A continuación el rápido:

Primero averigua cuáles son los niveles más bajos y más altos de los teclados. Luego genere un número aleatorio entre (aptitud física más baja) y (aptitud física más alta) y elimine todos los teclados con una aptitud superior al número generado. Esto es eficiente, pero no se garantiza que solo mate a la mitad de los teclados. También tiene una mecánica algo diferente a la selección de la "rueda de la ruleta", por lo que puede que ni siquiera sea aplicable.

Entonces la pregunta es, ¿qué es una implementación eficiente?

Hay un algoritmo algo eficiente en la página 36 de este libro (Enlazar), pero el problema es que solo es eficiente si realiza la selección de la ruleta solo una o varias veces. ¿Hay alguna forma eficiente de hacer muchas selecciones de ruleta en paralelo?