我目前正在研究一种遗传算法，我想在有向、非循环、非状态图中找到（或近似最佳排列）。可能的图如下所示：示例图
（注意，多个传入节点意味着多个条件。因此，为了选择G，必须首先选择B和F）
与旅行推销员问题相反，我的图上并非所有节点都是连接的（因此B和E），连接不适用于两个方向（A->B可以，但B->A不可能），并且没有节点可以定义为当前位置（这意味着从A到B后，D仍然是一个有效的选项）。因此，在搜索排列进行适应度计算时，解空间不是n！但要少得多（对于上面给出的例子，约为145）。验证排列的规则是"对于位于n位置的任何节点，其所有先决条件都必须位于小于n的位置"
例如，"A-B-D-E-F-H-G-I"将是一个有效的置换，而"I-G-C--E-F-D-B-A"将是尽可能无效的。
有了这些信息，我就可以验证适应度函数中的任何给定排列，如果它无效，则分配一个值0。然而，我希望在你的帮助下，我能找到一个更有效的解决方案，因为我正在处理可以有大约300个节点的图，并且计算所有无效可能性将是不可接受的耗时。因此，我想设计染色体的方式是，对于随机起始种群和进化操作，只有有效的个体才能添加到任何给定的种群中。
至于测试，我使用Java中的遗传算法和遗传编程的JGAP库，但该解决方案的实现不是强制性的。
非常感谢你的帮助，请原谅我的任何愚蠢的表达，因为我不是母语人士，也请原谅我在这个问题上的任何愚蠢，因为我对遗传算法还很陌生。
正如您所说，您的图是DAG（有向无循环图）。此外，连接到节点B的节点A必须在节点B之前。这基本上是这种图的拓扑排序的定义。你只想根据你选择的衡量标准找到这样一个最佳排序（因为可能有不止一个）。
这是我提出的一个解决方案。
基因型
为图形中的每个节点指定一个数字。这些节点的数字将是基因型。因此，对于您作为示例发布的图表，您将有9个数字。让我们给它一些符号：K(n)将是分配给节点n的数字。
解码基因型
要将基因型（一组数字）解码为表型（排序），请遵循以下程序（基本上是具有平局打破的Khan算法）：
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
通过这种方式，总是得到一个有效的解决方案，分配给节点的数字恰好决定了要构建的有效解决方案的数量。你可以很高兴地发展数字，你会得到不同的订单。
vanilla Khan算法的运行时间为O（|E|+|V|），即节点数量加上图中边的数量是线性的。在这里，我们需要对集合S进行排序，这样复杂性会变得更高，这取决于用于S的数据结构。如果它是一个基于堆的优先级队列，你会得到类似于（我现在猜是因为我太懒了，无法计算/证明它）O（|E|+|V|*log|V|）的东西。您可能希望尽可能优化此过程，因为它将被称为很多。
备注
这种解码技巧被称为间接编码，即你进化出一些没有直接评估的东西，而是转化为其他东西，然后进行评估。这有总是产生有效解决方案的好处，但也有一个主要缺点：基因型的微小变化可能导致表型的巨大变化，反之亦然。这可能会使遗传算法变得困难。
我还建议您尝试其他优化框架，而不仅仅是GA，例如Simmulated退火。