GA for TSP problem: starting at specific node

Hello,

for a traveling salesman problem I have, I am currently modifying a matlab example of tsp using GA that can be found at openExample('globaloptim/traveling_salesman_demo'). I have implemented my problem so far (by just changing the input to my input), but the algorithm always starts a random node. I would like to start always at the same node, and then calculate the optimal distance. Besides that, the algorithm works fine. We have studied the functions inside the example, but we can't seem to modify it the right way, to suit our problem.

Thanks in advance,

Thomas

Answer 1

[Thomas Beerten]

I am having the same problem. I guess that I need to change some parts in the create permutation function. However, I am not sure whether the problem is here. The create permutation function looks the following:

function pop = create_permutations(NVARS,FitnessFcn,options) 
    totalPopulationSize = sum(options.PopulationSize); 
    n = NVARS; 
    pop = cell(totalPopulationSize,1);
    for i = 1:totalPopulationSize 
        pop{i} = randperm(n);
    end
end

and the setup looks the following:

options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ...
    [1;cities]);
options = optimoptions(options,'CreationFcn',@create_permutations, ...
        'CrossoverFcn',@crossover_permutation, ...
        'MutationFcn',@mutate_permutation, ...
        'PlotFcn', my_plot, ...
        'MaxGenerations',500,'PopulationSize',60, ...
        'MaxStallGenerations',200,'UseVectorized',true);
    numberOfVariables = cities;
    [x,fval,reason,output] = ...
        ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options);

Kind regards, Thomas

Answer 2

[Adam]

Once (slightly hacky) way to accomplish always starting at the same node is to set the travel cost to that node as an arbitrarily high number. You can also use this to always end at a desired node - set the travel cost from that node arbitrarily high. More generally, this approach works to prohibit travel between any nodes of your network. Make sure you are consistent in your indexing to distinguish which node you are departing from and which node you are traveling to.