置换矩阵的交叉算法

Question

我正在开发一种遗传算法来找到点之间的最佳连接（最小化距离）。假设我们有两个点列表：

sources = {s1, s2, s3}

targets = {t1, t2, t3, t4}

我决定将基因组表示为二维二进制数组，其中：

行代表源点
列代表目标点
1s表示source和target之间的连接

这种表示意味着矩阵中的每一列和每一行最多只能有一个 1。

现在我正在努力寻找一个交叉运算符来保持解决方案的完整性。

示例：

父母 1 :

[0][1][0][0]
[0][0][1][0]
[1][0][0][0]

父母 2 :

[0][0][1][0]
[1][0][0][0]
[0][0][0][1]

后代：???

有什么建议吗？

Answer 1

您可以将 BFS 推广到这种情况。（如果我正确理解任务）

在简单的图形遍历任务中，您需要找到从起始节点到结束节点的最短路径，因此您需要为每个节点存储从起始节点到该节点的前任节点（来自您来自哪个单元格）的距离。在 BFS 迭代算法之前，您需要将起始节点添加到队列中。在每次迭代中取一个项目，检查该节点是否为结束节点并将该节点的邻居节点添加到队列等。那么，我们如何将这个算法推广到多个开始和结束节点。很简单。

您需要将所有起始节点加入队列
您需要比较从队列中取出的每个节点和每个结束节点。您可以使用 hashset 进行 O(1) 查找。

这个概括的时间复杂度不依赖于开始和结束节点的数量，与简单的 BFS 算法相同：O(V+E)

Answer 2

保持您的表示并假设目标多于来源，您可以使用 row-swapping 交叉运算符和 built-in 修复算法。

随机select一行(i)
交换 parents' i-th 行
修复 children（如果需要）将冲突的 1 移动到空闲（随机或附近）列

例如

第 0 行随机 selected

             PARENT 1                   PARENT 2
    ROW 0  [0][1][0][0] <-crossover-> [0][0][1][0]
    ROW 1  [0][0][1][0]               [1][0][0][0]
    ROW 2  [1][0][0][0]               [0][0][0][1]

修复前的后代

      CHILD 1            CHILD 2
    [0][0][1][0]       [0][1][0][0]
    [0][0][1][0]  and  [1][0][0][0]
    [1][0][0][0]       [0][0][0][1]

CHILD2 可以（对于 column-swapping 运算符，这不会发生）； CHILD1 需要维修操作员
```
      CHILD 1
    [0][0][X][0]
    [0][0][X][0]
    [1][0][0][0]
```
保留交换的行（第 0 行）并更改其他冲突行（第 1 行）。将 1 移动到空闲列（第 1 列或第 3 列）
```
      CHILD 1
    [0][0][1][0]
    [0][1][0][0]
    [1][0][0][0]
```

后代

      CHILD 1            CHILD 2
    [0][0][1][0]       [0][1][0][0]
    [0][1][0][0]  and  [1][0][0][0]
    [1][0][0][0]       [0][0][0][1]

置换矩阵的交叉算法

Crossover algorithms for permutation matrices

combinations

matrix

genetic-algorithm

crossover