Implementação eficiente da seleção de “roleta” proporcional à aptidão

Question

Atualmente, estou escrevendo um algoritmo de otimização de layout do teclado em C (como o projetado por Peter Klausler) e quero implementar uma seleção proporcional de condicionamento físico, conforme descrito aqui (Link pdf):

Com a seleção de roleta, você seleciona membros da população com base em um modelo de roda Roullete. Faça um gráfico de pizza, onde a área da fatia de um membro para todo o círculo é a proporção da tarefa dos membros para a população total. Como você pode ver se um ponto na circunfrença do círculo é escolhido aleatoriamente, os membros da população com maior aptidão terão uma 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 pool de teclado de comprimento n, crie uma matriz de comprimento n, onde cada elemento da matriz realmente contém dois elementos, um valor mínimo e um valor máximo. Cada teclado possui um valor mínimo e máximo correspondente e o intervalo é baseado na aptidão do teclado. Por exemplo, se o teclado Zero tiver uma aptidão de 10, o teclado um terá uma aptidão de 20 e o teclado dois tiver uma aptidão de 25, 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;

(Nesse caso, uma aptidão mais baixa é melhor, pois significa que menos esforço é necessário.)

Em seguida, gerar um número aleatório. Para qualquer alcance que o número se enquadre, o teclado correspondente é "morto" e substituído pela prole de um teclado diferente. Repita isto quantas vezes desejar.

O problema é que é muito lento. São necessárias operações O (n^2) para terminar.

Em seguida, o rápido:

Primeiro, descubra quais são as fitnesses mais baixas e mais altas para os teclados. Em seguida, gerar um número aleatório entre (menor aptidão) e (mais alta aptidão) e mate todos os teclados com uma aptidão superior ao número gerado. Isso é eficiente, mas não é garantido apenas matar metade dos teclados. Ele também possui mecânica um pouco diferente de uma seleção de "roda de roleta", portanto, pode nem ser aplicável.

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

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

Answer 1

Por um lado, parece que você está falando inapto pontuações se você quiser "matar" sua seleção (que provavelmente será um teclado com Alto pontuação).

Não vejo necessidade de manter duas matrizes. Eu acho que a maneira mais simples é manter uma única variedade de pontuações, pelas quais você itera para fazer uma escolha:

/* These will need to be populated at the outset */
int scores[100];
int totalScore;

for (gen = 0; gen < nGenerations; ++gen) {
    /* Perform a selection and update */
    int r = rand() % totalScore;        /* HACK: using % introduces bias */
    int t = 0;
    for (i = 0; i < 100; ++i) {
        t += scores[i];
        if (r < t) {
            /* Bingo! */
            totalScore -= scores[i];
            keyboards[i] = generate_new_keyboard_somehow();
            scores[i] = score_keyboard(keyboards[i]);
            totalScore += scores[i];    /* Now totalScore is correct again */
        }
    }
}

Cada seleção/atualização leva o tempo O (n) para N teclados.