遗传算法：如何实现小于 n!有效排列
Genetic Algorithms: how to implement permutation-chromosomes with less than n! valid permutations
我目前正在研究一种我想找到的遗传算法（或在有向的、非循环的、非基于状态的图中近似最佳排列。可能的图可能如下所示：
Example-Graph
（注意，多个传入节点意味着多个条件。所以为了选择G，必须先选择B和F）
与旅行推销员问题不同，并非我图上的所有节点都连接（因此 B 和 E），连接不适用于两个方向（A->B 很好，但 B-> A 是不可能的）并且没有节点可以定义为当前位置（意味着从 A 到 B 之后，D 仍然是一个有效选项）。因此，在搜索排列以进行适应度计算时，解决方案 space 不是 n！但要少得多（上面给出的示例约为 145）。
验证排列的规则是 "for any node at position n, all its preconditions must be at a position less than n"
例如 "A-B-D-C-E-F-H-G-I" 将是一个有效的排列，而 "I-G-C-H-E-F-D-B-A" 几乎是无效的。
有了这些信息，我就可以验证适应度函数内的任何给定排列，如果无效，则赋值 0。然而，我希望在你的帮助下我能找到一个更有效的解决方案，因为我正在处理可能有大约 300 个节点的图形，并且计算所有无效的可能性将非常耗时。所以我想以一种方式设计染色体，即对于随机起始种群和进化操作，只将有效个体添加到任何给定种群中。
至于测试，我在 Java 中使用 JGAP 库进行遗传算法和遗传编程，但该解决方案的实现不是强制性的。
非常感谢您的帮助，请原谅我任何愚蠢的表达，因为我不是母语人士，也请原谅我在这个问题中的任何愚蠢，因为我对遗传算法还很陌生。
你说的图是DAG（Directed Acyclic Graph）。此外，连接到节点 B 的节点 A 必须 位于节点 B 之前。这基本上是此类图的 topological sorting 的定义。您只想根据您选择的衡量标准找到最佳这样的排序（因为可以有多个）。
这是我提出的解决方案。
基因型
为图中的每个节点分配一个数字。这些节点的数字将成为基因型。因此，对于您作为示例发布的图表，您将有 9 个数字。让我们给它一些符号：K(n) 将是分配给节点 n.
的数字
解码基因型
要将基因型（数字集）解码为表型（排序），请遵循以下过程（基本上 Khan's algorithm 并打破平局）：
input: N is a set of all nodes in the graph
S += {r | r in N && r has no incoming connections } // a set with the root nodes
I := {n -> |predecessors(n)| | n in N} // a mapping from the nodes to numbers, the numbers being the numbers of incoming edges to the nodes
ordering := [] // a list of nodes
while |S| > 0 // while the open set is non-empty
n := arg min_q {K(q) | q in S} // from the open set, select the node with the lowest assigned number (see above)
S -= {n} // remove the node from the open set
ordering += n // add the node to the ordering
for each q in successors(n)
I[q] -= 1 // decrease the number of incoming nodes for each successor of n
S += {q | I[q] == 0} // add all nodes that have no incoming edge left to S
return ordering
这样你总是得到一个有效的解决方案，分配给节点的数字只决定了要构建的有效解决方案的数量。你可以愉快地进化数字，你会得到不同的顺序。
香草 Khan 算法的 运行 时间为 O(|E| + |V|)，即与图中的节点数加上边数成线性关系。这里我们需要对集合 S 进行排序，因此复杂度会更高，具体取决于 S 使用的数据结构。如果它是一个基于堆的优先级队列，你会得到类似的东西（我现在猜是因为我懒得 compute/prove 它）O(|E| + |V| * log |V|)。您可能希望尽可能多地优化此过程，因为它将被称为 很多。
备注
这种解码技巧被称为间接编码，也就是说，你进化出一些不直接评估的东西，而是转换成其他东西，然后再评估。这具有始终产生有效解决方案的好处，但它也有一个主要缺点：基因型的小变化可能导致表型的大变化，反之亦然。这可能会给遗传算法带来困难。
我还建议您尝试其他优化框架，而不仅仅是 GA，例如Simmulated annealing.
我目前正在研究一种我想找到的遗传算法（或在有向的、非循环的、非基于状态的图中近似最佳排列。可能的图可能如下所示： Example-Graph
（注意，多个传入节点意味着多个条件。所以为了选择G，必须先选择B和F）
与旅行推销员问题不同，并非我图上的所有节点都连接（因此 B 和 E），连接不适用于两个方向（A->B 很好，但 B-> A 是不可能的）并且没有节点可以定义为当前位置（意味着从 A 到 B 之后，D 仍然是一个有效选项）。因此，在搜索排列以进行适应度计算时，解决方案 space 不是 n！但要少得多（上面给出的示例约为 145）。 验证排列的规则是 "for any node at position n, all its preconditions must be at a position less than n"
例如 "A-B-D-C-E-F-H-G-I" 将是一个有效的排列，而 "I-G-C-H-E-F-D-B-A" 几乎是无效的。
有了这些信息，我就可以验证适应度函数内的任何给定排列，如果无效，则赋值 0。然而，我希望在你的帮助下我能找到一个更有效的解决方案，因为我正在处理可能有大约 300 个节点的图形，并且计算所有无效的可能性将非常耗时。所以我想以一种方式设计染色体，即对于随机起始种群和进化操作，只将有效个体添加到任何给定种群中。
至于测试，我在 Java 中使用 JGAP 库进行遗传算法和遗传编程，但该解决方案的实现不是强制性的。
非常感谢您的帮助，请原谅我任何愚蠢的表达，因为我不是母语人士，也请原谅我在这个问题中的任何愚蠢，因为我对遗传算法还很陌生。
你说的图是DAG（Directed Acyclic Graph）。此外，连接到节点 B 的节点 A 必须 位于节点 B 之前。这基本上是此类图的 topological sorting 的定义。您只想根据您选择的衡量标准找到最佳这样的排序（因为可以有多个）。
这是我提出的解决方案。
基因型
为图中的每个节点分配一个数字。这些节点的数字将成为基因型。因此，对于您作为示例发布的图表，您将有 9 个数字。让我们给它一些符号：K(n) 将是分配给节点 n.
解码基因型
要将基因型（数字集）解码为表型（排序），请遵循以下过程（基本上 Khan's algorithm 并打破平局）：
input: N is a set of all nodes in the graph
S += {r | r in N && r has no incoming connections } // a set with the root nodes
I := {n -> |predecessors(n)| | n in N} // a mapping from the nodes to numbers, the numbers being the numbers of incoming edges to the nodes
ordering := [] // a list of nodes
while |S| > 0 // while the open set is non-empty
n := arg min_q {K(q) | q in S} // from the open set, select the node with the lowest assigned number (see above)
S -= {n} // remove the node from the open set
ordering += n // add the node to the ordering
for each q in successors(n)
I[q] -= 1 // decrease the number of incoming nodes for each successor of n
S += {q | I[q] == 0} // add all nodes that have no incoming edge left to S
return ordering
这样你总是得到一个有效的解决方案，分配给节点的数字只决定了要构建的有效解决方案的数量。你可以愉快地进化数字，你会得到不同的顺序。
香草 Khan 算法的 运行 时间为 O(|E| + |V|)，即与图中的节点数加上边数成线性关系。这里我们需要对集合 S 进行排序，因此复杂度会更高，具体取决于 S 使用的数据结构。如果它是一个基于堆的优先级队列，你会得到类似的东西（我现在猜是因为我懒得 compute/prove 它）O(|E| + |V| * log |V|)。您可能希望尽可能多地优化此过程，因为它将被称为 很多。
备注
这种解码技巧被称为间接编码，也就是说，你进化出一些不直接评估的东西，而是转换成其他东西，然后再评估。这具有始终产生有效解决方案的好处，但它也有一个主要缺点：基因型的小变化可能导致表型的大变化，反之亦然。这可能会给遗传算法带来困难。
我还建议您尝试其他优化框架，而不仅仅是 GA，例如Simmulated annealing.