GA for TSP problem: starting at specific node

16 次查看（过去 30 天）
Thomas Wijnhoven
Thomas Wijnhoven 2018-4-5
编辑： Walter Roberson 2025-5-8
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

请先登录，再回答此问题。

回答（2 个）

Thomas Beerten
Thomas Beerten 2018-4-5
编辑：Walter Roberson 2025-5-8
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
Adam
Adam 2025-5-8
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.

类别

在 Help Center 和 File Exchange 中查找有关 Startup and Shutdown 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by