旅行商问题matlab算法

旅行商问题是一个经典的组合优化问题，目的是找到一条路径，使得旅行商可以在经过每个城市恰好一次的情况下，完成旅行并回到起点，同时路径的总长度最小。下面是使用matlab编写遗传算法求解TSP旅行商问题的步骤：

1.读取城市坐标数据，计算城市之间的距离矩阵。

2.初始化种群，每个个体表示一条路径，使用随机生成的方式。

3.计算每个个体的适应度，即路径长度。

4.选择优秀的个体进行交叉和变异，生成新的个体。

5.重复步骤3-4，直到达到预设的迭代次数或者找到最优解。

下面是使用matlab实现的代码：

% 读取城市坐标数据
data = load('city_data.txt');
n = size(data, 1);

% 计算城市之间的距离矩阵
dist = zeros(n, n);
for i = 1:n
    for j = i+1:n
        d = norm(data(i,:) - data(j,:));
        dist(i,j) = d;
        dist(j,i) = d;
    end
end

% 初始化种群
pop_size = 50;
pop = zeros(pop_size, n);
for i = 1:pop_size
    pop(i,:) = randperm(n);
end

% 迭代次数
max_iter = 1000;
best_fitness = inf;
best_path = zeros(1, n);

for iter = 1:max_iter
    % 计算适应度
    fitness = zeros(1, pop_size);
    for i = 1:pop_size
        path = pop(i,:);
        d = 0;
        for j = 1:n-1
            d = d + dist(path(j), path(j+1));
        end
        d = d + dist(path(n), path(1));
        fitness(i) = d;
        if d < best_fitness
            best_fitness = d;
            best_path = path;
        end
    end
    
    % 选择优秀的个体
    [sorted_fitness, idx] = sort(fitness);
    elite_size = 5;
    elite = pop(idx(1:elite_size),:);
    
    % 交叉和变异
    new_pop = zeros(pop_size, n);
    for i = 1:pop_size
        if i <= elite_size
            new_pop(i,:) = elite(i,:);
        else
            parent1 = elite(randi(elite_size),:);
            parent2 = elite(randi(elite_size),:);
            child = crossover(parent1, parent2);
            child = mutate(child);
            new_pop(i,:) = child;
        end
    end
    
    pop = new_pop;
end

% 输出结果
disp(['Best fitness: ', num2str(best_fitness)]);
disp(['Best path: ', num2str(best_path)]);

% 交叉
function child = crossover(parent1, parent2)
    n = length(parent1);
    child = zeros(1, n);
    start = randi(n);
    stop = randi(n);
    if start > stop
        temp = start;
        start = stop;
        stop = temp;
    end
    child(start:stop) = parent1(start:stop);
    idx = find(~ismember(parent2, child));
    child(idx) = parent2(idx);
end
% 变异
function child = mutate(parent)
    n = length(parent);
    child = parent;
    if rand < 0.1
        idx = randperm(n, 2);
        child(idx) = fliplr(child(idx));
    end
end