Algoritmi genetici: come fare crossover in problemi "sottoinsieme"?

Question

Ho un problema che sto cercando di risolvere con algoritmi genetici. Il problema sta selezionando alcuni sottoinsiemi (per esempio 4) di 100 numeri interi (questi numeri interi sono solo identificativi che rappresentano qualcos'altro). L'ordine non ha importanza, la soluzione al problema è un SET di numeri interi non ordinati. Ho una buona funzione fisica ma ho problemi con la funzione crossover.

Voglio essere in grado di accoppiarsi seguenti due cromosomi:

[1 2 3 4] e [3 4 5 6] in qualcosa di utile. Chiaramente non posso usare la tipica funzione crossover perché potrei finire con duplicati nei miei figli che rappresenterebbero soluzioni non valide. Qual è il miglior metodo di crossover in questo caso.

Answer 1

semplicemente ignorare qualsiasi elemento che si verifica in sia dei set (ossia nella loro intersezione.), Cioè lasciare tale elementi invariati in entrambi i set.

Il resto degli elementi forma due insiemi disgiunti, a cui è possibile applicare praticamente qualsiasi trasformazione casuale (ad esempio scambiando alcune coppie casualmente) senza ottenere duplicati.

Questo può essere pensato come ordinare e allineare entrambi gli insiemi in modo che gli elementi di corrispondenza siano uno di fronte all'altro e applicando uno degli algoritmi di crossover standard.

Answer 2

A volte è utile lasciare la soluzione andare "fuori dai limiti" in modo che la ricerca converga più rapidamente. Piuttosto che creare un insieme di 4 interi unici un requisito per il tuo cromosoma, rendi il numero di interi (e la loro unicità) parte della funzione fitness.

Answer 3

Io in realtà non so cosa vuoi dire il "Crossover tipici", ma credo che si potrebbe usare un crossover simile a quello che viene spesso utilizzato per le permutazioni:

• prendono m int dalla prima genitore (m < n, dove n è il numero di int nei vostri set)
• scansione al secondo e riempire il vostro sottoinsieme da esso con (nm) interi che sono liberi (non nel sottoinsieme già) .

In questo modo si avrà n int dalla prima e n-m interi dal secondo genitore, senza duplicazioni.

Suona come un crossover valido per me :-).

Credo che potrebbe essere utile non fare né passaggi su insiemi ordinati (o utilizzando un iteratore in cui l'ordine degli elementi restituiti correlato in qualche modo con l'ordinamento naturale di int), altrimenti il ​​numero sia più piccoli o superiore avranno la possibilità più alta essere nel bambino rendendo la tua ricerca parziale.

Se è il metodo migliore dipende dal problema che si desidera risolvere ...

Answer 4

Per combinare i set A e B, è possibile scegliere il set risultante S in modo probabilistico in modo che la probabilità che x sia in S è (numero di set di A, B, che contengono x)/2. Ciò essere garantito per contenere l'intersezione e essere contenuto nel sindacato, e avrà la cardinalità prevista 4.

Answer 5

Poiché l'ordine non è importante, è sufficiente raccogliere tutti i numeri in un array, ordinare l'array, eliminare i duplicati (disconnettendoli da un elenco collegato o impostandoli su un numero negativo o altro). Mescola l'array e prendi i primi 4 numeri.