operazione Crossover in algoritmo genetico per la TSP

Question

Sto cercando di risolvere il problema del commesso viaggiatore (TSP) con Genetic algoritmo. Mio genoma è una permutazione di un vertice nel grafico (percorso venditore).

Come faccio a eseguire l'operazione di incrocio sopra i miei genomi?

Dove posso trovare le implementazioni di mio problema in C #?

Answer 1

Si dovrebbe controllare " Genetic Algorithm Soluzione del TSP evitando speciale Crossover e Mutation " di Gokturk Ucoluk. Esso fornisce una panoramica degli operatori speciali di crossover per permutazioni e propone una rappresentazione intelligente di permutazioni che funziona bene con crossover standard (cioè crossing over due permutazioni produce sempre due permutazioni).

L'intuizione fondamentale è quello di rappresentare la permutazione come sua sequenza inversione, cioè per ciascun elemento i, conservare in a[i] quanti elementi maggiori di i sono a fianco di i nella permutazione. A differenza della rappresentazione diretta, l'unico vincolo a[i] è locale, cioè a[i] non può essere maggiore di N - i. Ciò significa che semplice incrocio di due sequenze di inversione validi produce sempre due sequenze di inversione validi -. Senza necessità di particolari movimentazione di elementi ripetitivi

Answer 2

Invece di utilizzare la tecnica di cross-over standard di GA (come delineato da MusiGenesis ), è meglio usare ordinato cross-over per il problema del commesso viaggiatore .

L'approccio al solito non funziona così bene per il TSP perché la funzione di fitness è molto sensibile alle posizioni relative delle diverse città del percorso evoluta, piuttosto che le loro posizioni assolute. Ad esempio, se si fosse in visita tutte le capitali europee, il percorso più breve in realtà non dipende dal fatto che si visita Bratislava 1 °, 2 ° o 9 °. La cosa più importante è che si visita immediatamente prima o immediatamente dopo la visita Vienna piuttosto che visitare Helsinki, Athens e 6 altre capitali tra.

Naturalmente, come MJV inoltre sottolinea , il tradizionale cross-over introdurrà anche i duplicati nel tuo percorso. Se un genitore ha Parigi in posizione 2 e un altro ha Parigi in posizione 14, cross-over potrebbe tradursi in una via evoluto che visita Parigi per due volte (e ci rimette un'altra città), e un altro percorso evoluto che non visitano affatto. L'operatore genetico cross-over ordinato non soffre di questo problema. Conserva gli elementi e modifica l'ordinamento.

Answer 3

Ecco un programma C # approccio per quello che sono alla ricerca di.

Per quanto riguarda l'interesse (o assenza) di attuazione incrociato , tutto dipende dal particolare logica di selezione l'implementazione utilizzerà (e / o la funzione di valutazione stesso, se per esempio comprende una valutazione della velocità di miglioramento). In molti casi, operazioni cross-over si "soccorso dal ceppo" alcune soluzioni che sono efficaci / ottimale in un'area del grafico ma in qualche modo "bloccato" in altre . Questo non vuol dire che se l'algoritmo complessivo è lento abbastanza e si estende su una buona percentuale dello spazio delle soluzioni le stesse soluzioni potrebbero non essere stati scoperti da capo, ma cross-over può anche aumentare queste scoperte (e / o lasciando bloccato in un'altra minimi locali ;-))

Non direttamente legati ma di notevole interesse a chi guarda in GA, è il originale "" esperimento di GA originale "ultimo" esperimento massimo in termini di GA dal Prof. Alderman (di RSA fama), che ha utilizzato le molecole di DNA effettivi [in un programma C - solo scherzando] per risolvere un problema relativo grafico, che di grafici hamiltoniani.

Modifica : In rileggendo la domanda capisco perché hai chiesto o più precisamente perché vuoi un "No non vuoi che cross-over" rispondere ;-)
Il tuo genonme è direttamente legato al grafico in sé (niente di sbagliato in questo, a priori ), ma questo porta l'impedimento offsrpings più cross-over non sarà praticabile, dal momento che essi possono possono avere nodi duplicati (visita stessa città due volte o più) ed essere i nodi mancanti (non riuscendo a visitare alcune città) ... Inoltre, vitali cross-over interesserà grafici simili, e quindi forse solo in modo incrementale spendono la ricerca, rispetto al ciò che le mutazioni avrebbe scoperto ...
Hum ... Poi magari cross-over, in questa particolare implementazione non aiuterà l'algoritmo molto (e in effetti prendere gran parte della sua CPU per creare, testare e spesso scartare proli cross-over, CPU che sarebbe meglio utilizzati da offrendo più iterazioni, e un tasso più lento raffreddamento ...). Salvo che! Potete trovare un modo intelligente di eseguire operatitions cross-over; -)

Answer 4

Lo scopo di crossover è di ampliare lo spazio di ricerca evolutivo riunendo nuove combinazioni genomiche.

L'unico criterio reali richiesti per il processo evolutivo è che il prodotto di attraversamento contiene porzioni di entrambi i genitori e rappresenta un genoma valido.

Solo tu sai le regole di validità per l'algoritmo in modo che solo è possibile specificare un metodo di crossover che funziona (a meno che non si desidera condividere ulteriori dettagli sulle regole di convalida per la struttura del genoma).

Answer 5

Ecco la mia esatta attuazione del metodo cosiddetto "attraversamento parzialmente mappati" in un AG per TSP.

Qui è una carta che spiega la parzialmente mappato di crossover, in teoria, e al di sotto è il mio codice.

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}

Answer 6

Quando ero al primo corso nella mia università, stavo facendo alcuni calcoli (che è durato circa 30 pagine) circa l'impatto dei vari operatori GA sulla convergenza della soluzione. Come ricordo, incrocio non è la soluzione migliore per TSP, la soluzione più adatta è mutazione, che è invertente di sotto-sequenza dei vertici.

Esempio:

prima: A BCDEF GH

dopo: A FEDCB GH

Answer 7

"crossover" in algoritmi genetici si riferisce solo a un modo arbitrario di miscelazione due "sequenze genetiche", ciascuna delle quali rappresenta una particolare soluzione di un problema (come una sequenza associata a un soluzione è a voi). Così, per esempio, supponiamo di avere una popolazione che è costituito dai seguenti due sequenze:

AAAAAAAAAA
BBBBBBBBBB

Un modo per ricombinare queste due sequenze "madre" è quello di scegliere a caso un punto di crossover (diciamo, posizione 3), con conseguente queste due sequenze "figli":

AAABBBBBBB
BBBAAAAAAA

In alternativa, si potrebbe in modo casuale selezionare due punti di crossover (diciamo, 3 e 8), con conseguente queste due sequenze:

AAABBBBBAA
BBBAAAAABB

Per il divertimento e la variabilità in più, si può anche introdurre la possibilità di mutazioni puntiformi occasionali:

AAABBBABAA
BBBAAAAABB

Non ci sono davvero tutte le regole dure e veloce per quanto riguarda come si implementa di crossover in un algoritmo genetico, così come non ci sono davvero tutte le regole dure-and-fast che disciplinano Evoluzione nel mondo biologico. Basta che funzioni, funziona.