Più iterazioni di torneo di selezione in Genetic Algorithm

Question

Hey ragazzi, sono un po 'confusi su come molteplici iterazioni delle opere di selezione del torneo.

Lo so che si avvia selezionando coppie casuali (o membri k) e mettere il vincitore in una piscina di accoppiamento. Si continua farlo fino alla piscina di accoppiamento è riempita.

Tuttavia, non sono sicuro di quello che succede dopo.

Dobbiamo solo iniziare l'accoppiamento in modo casuale quelli in piscina accoppiamento? E quindi riavviare il processo di selezione, scegliendo coppie casuali dalla nuova generazione?

Grazie.

Answer 1

Tradizionalmente dopo che i vincitori del torneo si trovano formano la prossima generazione. Tutti i processi di mutazione, selezione ecc continuano dopo questo in cicli.

Answer 2

ho scritto un sacco di questi algoritmi generici, al punto che ho fatto un quadro di evitare di scrivere più e più volte lo stesso codice.

Per la piscina di accoppiamento, dipende dal tipo di individui che stai cercando, le soluzioni che stai cercando, e se si dispone di un modo per unire le persone in un modo non c'è più possibilità che ti producono un meglio individuale.

È possibile utilizzare l'accoppiamento casuale, ma questo vi darà le soluzioni "peggiore" - peggio, perché non avete idea se essi produrranno una migliore individuo o meno. E sarà ancora buone soluzioni, e quando ho iniziato a scrivere questi algoritmi ho sempre usato l'accoppiamento casuale, ma subito dopo aver ottenuto un nuovo individuo da 2 quelli vecchi, ho confrontato le prestazioni del 3, e scartato il peggio, finendo con il 2 genitori a volte (e scartando l'1-secondo-vecchio bambino), o finire con 1 adulto e 1 bambino.

Ma per essere più efficiente, e se si sa come combinare gli individui in modo che essi producono una soluzione migliore (e questo può essere molto difficile), è possibile utilizzare una funzione di affinità, che prende 2 individui e restituisce un'affinità tra loro. La parte difficile è determinare l'affinità. A seconda del problema, può essere molto diversa. Ad esempio, se prendo il problema del commesso viaggiatore, ho ottenuto le migliori soluzioni durante l'accoppiamento individuale con meno somiglianza. Quindi la mia funzione di affinità restituito 1 -. Similitudine

In questo modo, ho potuto ridurre il numero di iterazioni del 80% e di ottenere ottime soluzioni.

Ma tenere a mente che la più grande è la vostra piscina, il più a lungo avrà la funzione di affinità di eseguire - funzioni di affinità possono essere O (n²), o anche O (n³), in quali casi può essere il collo di bottiglia il vostro algoritmo. In questo caso, può essere meglio usare l'accoppiamento casuale.

In conclusione, l'accoppiamento casuale è buona - dopo tutto, possiamo dire che funziona in questo modo nella vita reale - ma se si sa come calcolare un'affinità tra 2 individui, si può utilizzare per ridurre il numero di iterazioni è necessario ottenere una buona soluzione. Tenete a mente che il calcolo affinità può essere molto complessa (e ho anche indovinare che il calcolo delle migliori affinità per un dato piscina è NP-completo).

Answer 3

Questo non è un buon consiglio, ma ...

  

Tuttavia, non sono sicuro di quello che succede dopo.

Fai quello che vuoi. Si potrebbe mutare tutti ... oppure si può accoppiarsi ogni coppia che si sceglie nel torneo. Usa quello che funziona meglio. Siate creativi.

Come qualcun altro su questo forum ha sottolineato:. Il piccolo sporco segreto sul gas è che è più arte che scienza

Inoltre, per ottenere veramente un buon consiglio, avrete bisogno di una migliore descrizione del problema che si vuole risolvere.