No momento, estou escrevendo um algoritmo de otimização de layout de teclado em C (como aquele projetado por Peter Klausler) e quero implementar uma seleção proporcional de adequação conforme descrito aqui (Link PDF):

Com a seleção de roleta, você seleciona membros da população com base em um modelo de roda de rolete. Faça um gráfico de pizza, em que a área da fatia de um membro para todo o círculo é a proporção entre a integridade dos membros e a população total. Como você pode ver se um ponto na circunferência do círculo é escolhido aleatoriamente, os membros da população com maior aptidão terão maior probabilidade de serem escolhidos. Isso garante que a seleção natural ocorra.

O problema é que não vejo como implementá-lo com eficiência. Pensei em dois métodos: um não é confiável e o outro é lento.

Primeiro, o lento:

Para um conjunto de teclados de comprimento N, crie uma matriz de comprimento N, em que cada elemento da matriz contém, na verdade, dois elementos, um valor mínimo e um máximo. Cada teclado tem um valor mínimo e máximo correspondente e o intervalo é baseado na adequação do teclado. Por exemplo, se o teclado zero tem uma adequação de 10, o teclado um tem uma capacidade de 20 e o teclado dois tem uma adequação de 25, ele ficaria assim: 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;

(Neste caso, uma menor aptidão é melhor, uma vez que significa menos esforço é necessário.)

Em seguida, gere um número aleatório. Para qualquer intervalo em que esse número caia, o teclado correspondente é "morto" e substituído pela descendência de um teclado diferente. Repita isto quantas vezes desejar.

O problema com isso é que é muito lento. Leva operações O (N ^ 2) para terminar.

Em seguida o rápido:

Primeiro, descubra qual é a menor e a maior aptidão para os teclados. Em seguida, gere um número aleatório entre (menor aptidão) e (maior aptidão) e mate todos os teclados com uma aptidão maior do que o número gerado. Isso é eficiente, mas não é garantido matar apenas metade dos teclados. Ele também tem uma mecânica um pouco diferente de uma seleção de "roda de roleta", portanto pode nem ser aplicável.

Então a questão é: o que é uma implementação eficiente?

Existe um algoritmo um pouco eficiente na página 36 deste livro (Ligação), mas o problema é que só é eficiente se você fizer a seleção da roleta apenas uma ou algumas vezes. Existe alguma maneira eficiente de fazer muitas seleções de roleta em paralelo?