Scegliere solo il x superiore per la selezione in un algoritmo genetico

Question

Attualmente sto lavorando su un StringEvolver e non sono abbastanza sicuro di un termine specifico che può essere utilizzato in GA.

In algoritmi genetici, elitism si riferisce a quel sottoinsieme della popolazione che viene promossa direttamente alla generazione successiva; corretta?

Ma esiste un termine specifico per l'utilizzo solo, ad esempio, del 75% superiore della popolazione attuale per il processo di selezione, crossover e mutazione anziché dell'intera popolazione? Fondamentalmente, qual è il tasso x% chiamato?

Quello che voglio dire è che invece di utilizzare tutta la popolazione per dire, un processo di roulette-selezione, io uso solo la parte superiore x% (vale a dire razza solo tra i migliori x% della popolazione)

---

Il motivo per cui lo chiedo è perché ho notato miglioramenti significativi delle prestazioni (convergenza più rapida) quando si utilizza, ad esempio, il 10-25% della popolazione per i processi di selezione, crossover e mutazione per far progredire la generazione piuttosto che utilizzare il pieno popolazione.

Answer 1

Una strategia di selezione ingenua in cui si scartano semplicemente i candidati più deboli viene talvolta chiamata Selezione tronchi. Per molti problemi porta a una convergenza prematura, anche se ho trovato che funziona abbastanza bene per il problema del venditore ambulante.

Sembra che tu abbia una strategia a due fasi, in primo luogo utilizzando la selezione del troncamento per eliminare i candidati deboli e quindi applicare una strategia più sofisticata (la ruota della roulette?) Per finalizzare la selezione.

Piuttosto che eliminare completamente la possibilità che i candidati deboli sopravvivano, potrebbe essere preferibile scegliere una strategia di selezione che consenta di modificare tale probabilità. Ad esempio, con la selezione del torneo puoi regolare la soglia per determinare quanto è probabile che un candidato debole sopravviva invece di uno più forte.

Answer 2

Sembra che tu stia parlando solo di una specifica metodologia di selezione. Potresti fare approssimativamente la stessa cosa ridimensionando la tua funzione di fitness per aumentare a tassi più alti piuttosto che in modo lineare.

Detto questo, vorrei mettere in guardia dall'eliminare ogni volta le parti inferiori della popolazione. Per GA più piccoli questo ti permetterà di convergere più velocemente, ma per problemi del mondo reale questo ti porterà spesso ai minimi locali, degradando la qualità delle tue soluzioni.

Detto questo, c'è un termine chiamato decimazione. Questo è quando si butta fuori l'X% inferiore della popolazione prima del crossover e della mutazione. Generalmente non viene fatto ogni generazione. In genere inizierai con una popolazione esteticamente grande per coprire uno spazio di ricerca più grande e poi decimali dopo le generazioni X, dato che i GA ottengono spesso i loro maggiori guadagni nelle prime 100 gens circa. Si procede quindi con la popolazione più piccola e più facilmente gestita.

Spero che questo aiuti.

Answer 3

Non esiste un termine specifico per limitare la selezione agli elementi x superiori in alto, è solo uno dei fattori che devi impostare quando si implementa una strategia di selezione.

È possibile ottenere una convergenza più rapida in alcuni casi limitando quella cifra x%, ma suggerirei di provare con stringhe di lunghezza diversa e vedere come questo influenza la convergenza. L'ho già fatto (vedi i progetti this e this, sia sulle stringhe in evoluzione), e se si rende il pool genetico troppo piccolo quando si selezionano gli individui, la probabilità di rimanere bloccati può salire alle stelle in relazione alla lunghezza della stringa, il motivo è che stai seriamente compromettendo la diversità.