。
美国Michigan大学的Holland教授提出的遗传算法(GeneticAlgorithm,GA)是求解复杂的组合优化问题的有效方法，其思想来自于达尔文进化论和门德尔松遗传学说，它模拟生物进化过程来从庞大的搜索空间中筛选出较优秀的解，是一种高效而且具有强鲁棒性方法。
所以，遗传算法在求解TSP和MTSP问题中得到了广泛的应用。
matlab程序如下：function[opt_rte,opt_brk,min_dist]=mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter)%%%实例% n=20;%城市个数% xy=10*rand(n,2);%城市坐标 随机产生，也可以自己设定% salesmen=5;%旅行商个数% min_tour=3;%每个旅行商最少访问的城市数% pop_size=80;%种群个数% num_iter=200;%迭代次数% a=meshgrid(1:n);% dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);% [opt_rte,opt_brk,min_dist]=mtspf_ga(xy,dmat,salesmen,min_tour,...% pop_size,num_iter);%函数%%[N,dims]=size(xy);%城市矩阵大小[nr,nc]=size(dmat);%城市距离矩阵大小n=N-1;%除去起始的城市后剩余的城市的数%初始化路线、断点的选择num_brks=salesmen-1;dof=n-min_tour*salesmen; %初始化路线、断点的选择addto=ones(1,dof+1);fork=2:num_brksaddto=cumsum(addto);endc