2

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

sources = {s1, s2, s3}

targets = {t1, t2, t3, t4}

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

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

这种表示意味着矩阵中的每一列和每一行最多可以有一个 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]

后代：？？？

有什么建议么？

4

2 回答 2

1

保持您的表示并假设目标多于源，您可以使用带有内置修复算法的行交换交叉运算符。

  • 随机选择一行 ( i)
  • 交换父母i-th行
  • 修复儿童（如果需要）将冲突移动1到自由（随机或附近）列

例如

  1. 第0行随机选择

                 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]

  2. 修复前的后代

          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]

  3. CHILD2没问题（对于列交换运算符，这不会发生）；CHILD1需要维修人员

          CHILD 1
    [0][0][X][0]
    [0][0][X][0]
    [1][0][0][0]

  4. 保留交换的行（第 0 行）并更改另一个冲突的行（第 1 行）。将 1 移动到空闲列（第 1 或 3 列）

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

  5. 后代

          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]
于 2016-01-20T10:36:20.360 回答
0

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

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

  1. 您需要将所有启动节点添加到队列中。
  2. 您需要将从队列中取出的每个节点与每个完成节点进行比较。您可以使用 hashset 进行 O(1) 查找。

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

于 2016-01-19T16:46:26.100 回答