matlab遗传算法为什么这种交叉方法不会出现子回路

Question

这题目是一百个地点，经度纬度给出，求飞机巡航最短路径。交叉操作中如果一个父代的截取的那一段含有另一个父代的未截取那一段的点，那子代就有两个点是重复点，为什么不会出现子回路？哪怕迭代数为1也不会出现

Answer 1

引自免费微信小程序：皆我百晓生

这个问题涉及到遗传算法、交叉操作和变异操作等多个方面。在遗传算法中，交叉操作是指通过一定的概率将两个个体的基因片段组合在一起，形成新的个体。在这个过程中，存在子回路的问题，即后代个体中有两个点是相同的，导致路径不唯一。

在你提供的代码中，交叉操作采用了单点交叉的方法。在这种情况下，当两个父代个体的交叉点位于同一个基因时，会产生子回路。这是因为这两个点代表的是同一条路径上的两个不同节点，因此它们会出现在后代个体的路径中。

要解决这个问题，我们需要改变交叉操作的方式。一种可能的做法是在两个父代个体之间插入一些随机的中间基因，使得交叉点不在同一基因上。这样，在交叉后的个体中就不会再出现子回路。

具体来说，我们可以引入一个随机数u和一个随机数v，然后在u和v之间插入一个随机的中间基因。例如，我们可以使用以下代码：

for i = 1 : 2 : w 
    F=2+floor(100*rand(1));8产生交叉操作的地址
    for j = i + 1 : 102 
        if d(c1(i), c1(j)) < d(c1(i+1), c1(j+1))
            x = randperm(w);
            y = sort(randperm(w));
            z = [x y];
            temp = A(c(i), [F:102]);
            B = A(z, :);
            A(c(i), [F:102]) = A(c(i+1), [F:102]);
            A(c(i+1), [F:102]) = temp;
            by = find(rand(1, w) < 0.1);
            B = A(by, :);
            for j = 1 : length(by)
                bw = sort(2 + floor(100 * rand(1, 3));
                B(i,:) = B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
            end
            break;
        end
    end
end

这段代码首先计算交叉点的位置，然后从父代个体中随机选择中间基因进行插入。这样，即使在交叉点相同的情况下，也能确保后代个体的路径不包含重复的点。

注意，这个方法只是一个简化版本，实际应用中可能需要根据具体情况调整参数，比如交叉的概率、插入的随机数等。此外，还需要考虑其他因素，如变异操作和适配度函数的选择，以进一步优化搜索过程。