matlab实现旅行商问题

旅行商问题是一个NP完全问题，因此在实际求解时需要采用一些近似算法。其中比较常用的是遗传算法和模拟退火算法。

下面给出一个基于遗传算法的Matlab代码实现：

function [best_path, best_dist] = tsp_ga(cities, pop_size, num_gen, elite_rate, mutation_rate)
% TSP_GA solves the Traveling Salesman Problem using a genetic algorithm
% cities: a n-by-2 matrix containing the coordinates of n cities
% pop_size: the size of the population, default is 50
% num_gen: the number of generations, default is 100
% elite_rate: the percentage of the best individuals to be kept in the next generation, default is 0.1
% mutation_rate: the probability of mutation, default is 0.01

% default parameters
if nargin < 5
    mutation_rate = 0.01;
end
if nargin < 4
    elite_rate = 0.1;
end
if nargin < 3
    num_gen = 100;
end
if nargin < 2
    pop_size = 50;
end

% number of cities
n = size(cities, 1);

% initialize population
pop = zeros(pop_size, n);
for i = 1:pop_size
    pop(i,:) = randperm(n);
end

% main loop
for gen = 1:num_gen
    % evaluate fitness of each individual
    dist = zeros(pop_size, 1);
    for i = 1:pop_size
        path = pop(i,:);
        dist(i) = 0;
        for j = 1:n-1
            dist(i) = dist(i) + norm(cities(path(j+1),:) - cities(path(j),:));
        end
        dist(i) = dist(i) + norm(cities(path(1),:) - cities(path(n),:)); % add distance from last to first city
    end
    [sorted_dist, idx] = sort(dist);
    best_path = pop(idx(1),:);
    best_dist = sorted_dist(1);

    % selection
    elite_size = round(elite_rate * pop_size);
    elite_pop = pop(idx(1:elite_size),:);
    nonelite_size = pop_size - elite_size;
    nonelite_pop = zeros(nonelite_size, n);
    for i = 1:nonelite_size
        % tournament selection
        k = randi(pop_size, 1, 2);
        if dist(k(1)) < dist(k(2))
            nonelite_pop(i,:) = pop(k(1),:);
        else
            nonelite_pop(i,:) = pop(k(2),:);
        end
    end
    pop = [elite_pop; nonelite_pop];

    % crossover
    for i = 1:2:nonelite_size
        % choose two parents
        p = randperm(nonelite_size, 2);
        parent1 = nonelite_pop(p(1),:);
        parent2 = nonelite_pop(p(2),:);
        child = zeros(1, n);
        % choose a random segment from parent1
        seg_start = randi(n);
        seg_end = randi([seg_start+1,n]);
        child(seg_start:seg_end) = parent1(seg_start:seg_end);
        % insert remaining cities from parent2
        idx = 1;
        for j = 1:n
            if child(j) == 0
                while ismember(parent2(idx), child)
                    idx = idx + 1;
                    if idx > n
                        idx = 1;
                    end
                end
                child(j) = parent2(idx);
                idx = idx + 1;
                if idx > n
                    idx = 1;
                end
            end
        end
        pop(elite_size+i,:) = child;
    end

    % mutation
    for i = 1:pop_size
        if rand < mutation_rate
            % swap two random cities
            j = randi(n, 1, 2);
            pop(i,[j(1),j(2)]) = pop(i,[j(2),j(1)]);
        end
    end
end
end

使用方法：

首先定义一组城市坐标，例如：

cities = [0, 0;
          1, 1;
          2, 1;
          1, 2;
          2, 2];

然后调用`tsp_ga`函数求解：

[best_path, best_dist] = tsp_ga(cities);

其中`best_path`为最优路径，`best_dist`为最优路径长度。

需要注意的是，由于遗传算法是一种随机算法，因此每次运行的结果可能会有所不同。