Implementazione efficiente della selezione della “roulette” proporzionata al fitness

Question

Attualmente sto scrivendo un algoritmo di ottimizzazione del layout della tastiera in C (come quello progettato da Peter Klausler) e voglio implementare una selezione proporzionata al fitness come descritto qui (Collegamento PDF):

Con la selezione della roulette seleziona i membri della popolazione in base a un modello di ruota roulleta.Crea un grafico a torta, in cui l'area della fetta di un membro all'intero cerchio è il rapporto tra i membri e la popolazione totale.Come puoi vedere se un punto sulla circonferenza del cerchio viene raccolto a caso, quei membri della popolazione con maggiore dimensione avranno una maggiore probabilità di essere scelti.Ciò garantisce che si svolge la selezione naturale.

Il problema è che non vedo come implementarlo in modo efficiente.Ho pensato a due metodi:uno è inaffidabile e l'altro è lento.

Innanzitutto, quello lento:

Per un pool di tastiere di lunghezza N, creare un array di lunghezza N in cui ciascun elemento dell'array contiene effettivamente due elementi, un valore minimo e uno massimo.Ciascuna tastiera ha un valore minimo e massimo corrispondente e l'intervallo si basa sull'idoneità della tastiera.Ad esempio, se la tastiera zero ha un'idoneità di 10, la tastiera uno ha un'idoneità di 20 e la tastiera due ha un'idoneità di 25, sarebbe simile a questa:Codice:

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;

(In questo caso è meglio una forma fisica inferiore, poiché significa che è richiesto meno sforzo.)

Quindi genera un numero casuale.Per qualunque intervallo rientri in quel numero, la tastiera corrispondente viene "uccisa" e sostituita con la progenie di una tastiera diversa.Ripeti l'operazione tutte le volte che desideri.

Il problema è che è molto lento.Per completare sono necessarie O (N ^ 2) operazioni.

Poi quello veloce:

Per prima cosa scopri quali sono le fitness più basse e più alte per le tastiere.Quindi genera un numero casuale tra (forma fisica più bassa) e (forma fisica più alta) e uccidi tutte le tastiere con una forma fisica superiore al numero generato.Questo è efficiente, ma non è garantito che uccida solo la metà delle tastiere.Ha anche una meccanica leggermente diversa da quella della "ruota della roulette", quindi potrebbe non essere nemmeno applicabile.

Quindi la domanda è: cos’è un’implementazione efficiente?

C'è un algoritmo piuttosto efficiente a pagina 36 di questo libro (Collegamento), ma il problema è che è efficace solo se esegui la selezione della roulette solo una o poche volte.Esiste un modo efficace per effettuare più selezioni di roulette in parallelo?

Answer 1

Per prima cosa, sembra che tu stia parlando inidoneità punteggi se vuoi "eliminare" la tua selezione (che probabilmente sarà una tastiera con alto punto).

Non vedo la necessità di mantenere due array.Penso che il modo più semplice sia mantenere un unico array di punteggi, che poi si ripete per fare una scelta:

/* 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 */
        }
    }
}

Ogni selezione/aggiornamento richiede O(n) tempo per n tastiere.