Operatore di mutazione per algoritmi genetici per risolvere problemi di commesso viaggiatore

Question

Operatore di mutazione per algoritmi genetici per risolvere problemi di commesso viaggiatore

#1 da (2 voti)
#2 da (0 voti)

4

Ho bisogno di aiuto per definire l'operatore di mutazione per il problema del commesso viaggiatore.

Attualmente sto usando questo ora (pseudocodice):

mutate ( strand ):
    for n in random_interval ( min_gene_index, max_gene_index ):
        i := random_interval ( min_gene_index, max_gene_index );
        j := random_interval ( min_gene_index, max_gene_index );
        swap ( strand[i], strand[j] );

Quindi, quando lo swap viene eseguito, vengono scambiate due città nel percorso. L'obiettivo è che deve essere veloce ed efficace. Non voglio che sia un successo nel circuito principale. Posso migliorare la mia implementazione o c'è qualche altra alternativa che sia migliore?

genetic-algorithms graph-traversal

posta Jossi 06.03.2015 - 15:20

fonte

2 risposte

0

A meno che tu non stia utilizzando una versione non standard del TSP, non penso che ti serva un loop qui. Con un GA che utilizza una codifica binaria di parametri con valori reali, occasionalmente potrebbe essere necessario un ciclo come

for each gene:
    for each bit in the gene:
        do something

È abbastanza raro anche allora, ma a volte vuoi osservare i limiti dei parametri in questo modo.

Per quanto riguarda TSP, la rappresentazione canonica è solo una permutazione di numeri interi che rappresentano le città nell'ordine in cui si verificano nel tour. Se vuoi fare uno swap (la più piccola mutazione valida), devi solo fare

def mutate(candidate):
    p1 = random_index()
    p2 = random_index()
    swap(candidate[p1], candidate[p2])

Puoi provare a fare lo swap trick con operatori bit a bit, ma non immagino che farebbe una differenza notevole. Altrimenti, è più efficiente che puoi ottenere.

risposta data 06.03.2015 - 16:37

fonte

Leggi altre domande sui tag genetic-algorithms graph-traversal

Come conservare i dati registrati con frequenza diversa? Library OSes vs Unikernels

score 2 · Accepted Answer

Molti operatori di mutazione (e crossover) diversi sono stati ideati per il TSP e ciascuno di essi fornisce risultati diversi.

Potresti usare informazioni specifiche del dominio (mutazione euristica).

es. la mutazione 2-opt è un algoritmo spesso usato.

Solitamente migliora le soluzioni rispetto a un approccio solo crossover (in ( 2 ) l'operatore di mutazione 2-opt è stato testato anche senza crossover con buoni risultati).

      ..                   ..
     /  \                 /  \
    /    \               /    \
  (a)    (c)           (a)    (c)
     \  /               |      |
      \/         =>     |      |
      /\                |      |
     /  \               |      |
  (d)    (b)           (d)    (b)
    \    /               \    /
     \  /                 \  /
      ..                   ..

L'operatore seleziona a caso due bordi ad es. (a,b) e (c,d) dal tour e controlla se:

distance(a, b) + distance (c, d) > distance(a, d) + distance(c, b)

se questo è il caso, il tour viene modificato rimuovendo (a,b) e (c,d) e sostituendoli con i bordi (a,d) e (c,b) .

Questo è abbastanza leggero e semplice da implementare.

Riferimenti