Hai bisogno di aiuto per adattare un algoritmo genetico per "risolvere" il venditore ambulante su Ruby

Question

Ho appena scaricato la libreria AI4R http://ai4r.rubyforge.org/ e sto usando il geneticoAlgoritmo per ottenere una buona strada da più posti, proprio come questo:

http://ai4r.rubyforge.org/geneticalgorithms.html

Ma ho bisogno di essere in grado di impostare una città iniziale.

Qualsiasi indizio su come usarlo su una città di partenza "fissa"?

Answer 1

In generale, non guardando l'implementazione specifica di Ruby, puoi semplicemente rimuovere la città di inizio e assumere che il primo margine seguito sia dalla tua città di inizio a qualsiasi cosa produca GA.Assicurati solo che il primo vantaggio sia incluso nella funzione costo / fitness.

Answer 2

La soluzione di un problema di venditori ambulanti è un viaggio di andata e ritorno ed è quindi indipendente da una città di partenza. Dopo aver trovato la soluzione, puoi prendere qualsiasi città del viaggio di andata e ritorno come città di partenza.

MODIFICA: se non hai bisogno di tornare alla tua città di partenza, puoi selezionare la città di arrivo, rimuovendo la maggiore delle due distanze che lasciano la tua città di partenza. Se rimuovi nella tua soluzione finale la distanza maggiore nell'intero viaggio di andata e ritorno, otterrai il tour più breve complessivo che non è un viaggio di andata e ritorno. Questo è probabilmente quello che hanno fatto nella pagina web che hai collegato (Dublino - Mosca sembra essere la direzione più costosa). Tuttavia, tieni presente che gli autori di quella pagina hanno utilizzato una posizione sbagliata per Vienna e anche Madrid sembra essere fuori posto.

Un altro modo di quando avrai bisogno di una città di partenza è quando hai un vincolo di finestra temporale aggiuntivo. Questo vincolo specifica che per ogni città in cui devi essere lì a una certa ora, il "deposito", come viene chiamata la tua città di partenza, in questo caso ha una finestra temporale che copre l'intero viaggio. Tuttavia il TSPtw è un problema molto più complesso e spesso richiede operatori genetici avanzati. Puoi anche modellare il TSPtw come CVRPtw (Capacitated Vehicle Routing Problem with Time Windows) se utilizzi un solo veicolo. Puoi provare la nostra implementazione VRP in HeuristicLab per risolvere questo problema. Abbiamo una mailing list se hai bisogno di ulteriore supporto.

Answer 3

La risposta che otterrai dal GA al TSP è un ciclo, il che significa che la prima città è quella che desideri.Ad esempio, se la risposta è [3 4 2 6 1 5] e voglio che la prima città sia 2, posso "tirare" la soluzione per [2 6 1 5 3 4].

Tuttavia, puoi ridurre il tuo problema di 1 se nella funzione di valutazione specifichi la prima città.In tal caso è necessario tenere conto che le persone devono essere modificate per tenerne conto.Ad esempio, se imposti la prima città su # 2 (problema di 6 città) e hai una persona che è [1 2 3 4 5] (6 città meno una).L'individuo da valutare è [2 1 3 4 5 6].