旅行商问题matlab遗传算法求解

旅行商问题是一个经典的组合优化问题，它的目标是找到一条路径，使得旅行商能够经过每个城市一次且仅一次，并回到出发城市，同时使得总路径长度最短。

遗传算法是一种常用的优化算法，可以应用于解决旅行商问题。以下是基于Matlab实现的遗传算法求解旅行商问题的步骤：

1. 定义城市坐标

首先需要定义城市的坐标，可以使用二维平面上的坐标系表示，例如：

num_cities = 10; % 城市数量
cities = 10 * rand(num_cities, 2); % 随机生成城市坐标

2. 初始化遗传算法参数

需要定义遗传算法的参数，包括种群大小、交叉概率、变异概率等。例如：

pop_size = 100; % 种群大小
cross_prob = 0.8; % 交叉概率
mut_prob = 0.01; % 变异概率

3. 初始化种群

在种群中随机生成若干个染色体，每个染色体表示一条路径。例如：

pop = zeros(pop_size, num_cities);
for i = 1 : pop_size
    pop(i, :) = randperm(num_cities);
end

4. 计算适应度

根据路径长度计算每个染色体的适应度，适应度越高表示路径越短。例如：

fit = zeros(pop_size, 1);
for i = 1 : pop_size
    path_len = 0;
    for j = 1 : num_cities-1
        path_len = path_len + norm(cities(pop(i,j),:) - cities(pop(i,j+1),:));
    end
    path_len = path_len + norm(cities(pop(i,num_cities),:) - cities(pop(i,1),:));
    fit(i) = 1/path_len;
end

5. 选择操作

按照适应度大小对种群进行选择，选择的概率与适应度成正比。可以使用轮盘赌算法进行选择，例如：

prob = fit/sum(fit);
acc_prob = cumsum(prob);
new_pop = zeros(size(pop));
for i = 1 : pop_size
    r = rand();
    sel_idx = find(acc_prob>=r, 1);
    new_pop(i,:) = pop(sel_idx,:);
end

6. 交叉操作

随机选取两个染色体进行交叉，生成新的染色体。例如：

for i = 1 : 2 : pop_size-1
    if rand() < cross_prob
        p1 = new_pop(i,:);
        p2 = new_pop(i+1,:);
        cross_point = randi(num_cities-1);
        c1 = [p1(1:cross_point), setdiff(p2, p1(1:cross_point), 'stable')];
        c2 = [p2(1:cross_point), setdiff(p1, p2(1:cross_point), 'stable')];
        new_pop(i,:) = c1;
        new_pop(i+1,:) = c2;
    end
end

7. 变异操作

对每个染色体进行变异，例如随机交换两个城市的位置。例如：

for i = 1 : pop_size
    if rand() < mut_prob
        mut_pos = randperm(num_cities, 2);
        new_pop(i, mut_pos) = new_pop(i, mut_pos(end:-1:1));
    end
end

8. 更新种群

将新生成的种群替换原有的种群，继续进行下一轮迭代。例如：

pop = new_pop;

9. 输出结果

迭代若干次后，选择适应度最高的染色体作为最终的解，并输出路径长度和路径顺序。例如：

[~, best_idx] = max(fit);
best_path = pop(best_idx,:);
best_len = 0;
for i = 1 : num_cities-1
    best_len = best_len + norm(cities(best_path(i),:) - cities(best_path(i+1),:));
end
best_len = best_len + norm(cities(best_path(num_cities),:) - cities(best_path(1),:));
disp(['Best path length: ', num2str(best_len)]);
disp(['Best path order: ', num2str(best_path)]);