遗传算法求端点之间的最短距离

假设有 $n$ 个点，每个点的位置用二维坐标 $(x_i, y_i)$ 表示，其中 $i=1, 2, \ldots, n$。现在要求从点 $s$ 到点 $t$ 的最短路径，可以使用遗传算法来解决。

以下是一个简单的 MATLAB 代码：

% 假设有 n 个点，每个点的位置用二维坐标 (x_i, y_i) 表示
% s 和 t 分别表示起点和终点的下标
n = 10;
s = 1;
t = 10;
x = rand(n,1);
y = rand(n,1);

% 初始化种群
m = 100; % 种群数量
p = 0.01; % 变异概率
gen = 100; % 迭代次数
pop = zeros(m,n); % 种群矩阵
dis = zeros(m,1); % 距离矩阵
best = zeros(gen,1); % 最优解矩阵
for i = 1:m
    pop(i,:) = randperm(n);
end

% 迭代计算
for k = 1:gen
    % 计算每个个体的距离
    for i = 1:m
        dis(i) = norm([x(pop(i,1))-x(s), y(pop(i,1))-y(s)]);
        for j = 1:n-1
            dis(i) = dis(i) + norm([x(pop(i,j+1))-x(pop(i,j)), y(pop(i,j+1))-y(pop(i,j))]);
        end
        dis(i) = dis(i) + norm([x(pop(i,n))-x(t), y(pop(i,n))-y(t)]);
    end
    % 找出最优解
    [val,idx] = min(dis);
    best(k) = val;
    % 挑选优秀个体进行交叉
    [~,I] = sort(dis);
    pop1 = pop(I(1:m/2),:);
    pop2 = pop(I(1:m/2)+1,:);
    for i = 1:m/2
        j = ceil(n*rand);
        pop(i,:) = [pop1(i,1:j),pop2(i,j+1:end)];
    end
    % 变异
    for i = 1:m
        if rand < p
            j = ceil(n*rand);
            k = ceil(n*rand);
            pop(i,[j,k]) = pop(i,[k,j]);
        end
    end
end

% 打印最优解
[val,idx] = min(dis);
fprintf('从点 %d 到点 %d 的最短路径为：', s, t);
disp(pop(idx,:));
fprintf('路径长度为：%f\n',val);

% 绘图
plot(x, y, 'o');
hold on;
plot(x([s,t]), y([s,t]), 'r*');
plot(x(pop(idx,[1:n,1])), y(pop(idx,[1:n,1])), '-');
hold off;

代码中的 `x` 和 `y` 分别表示每个点的横纵坐标，`s` 和 `t` 分别表示起点和终点的下标。变量 `m` 表示种群数量，`p` 表示变异概率，`gen` 表示迭代次数。种群矩阵 `pop` 的每一行都表示一条路径，即每个点的访问顺序。距离矩阵 `dis` 的每个元素表示对应路径的总长度。最优解矩阵 `best` 记录每次迭代的最优解。

算法的主要步骤是：

1. 初始化种群
2. 计算每个个体的距离
3. 挑选优秀个体进行交叉
4. 变异
5. 重复 2-4 步直到达到迭代次数

最后会输出最短路径和路径长度，并绘制出路径图。