Genetic algorithms applied to topological orderings of a DAG

I need to solve an optimization problem, whose search space is all possible topological orderings of a DAG. There is a cost function associated with each ordering, which has no simple mathematical representation -- I have a black box which, given one of the orderings, will return the cost associated with that ordering.

I'd like to apply e.g. genetic algorithms to solve the problem. In order to do that, I understand I need to find some kind of representation (e.g. a vector in a certain $n$-dimensional space) to which I can apply mutations and breeding with other candidates, outputting a new ordering whose cost I can then compute using the black box.

I learned that this can be done with generic permutations, as in this example for the traveling salesman problem. However, not every permutation will be a valid topological ordering. In principle, I could follow the procedure to generate an arbitrary permutation, and then discard and repeat in case it's not a valid topological ordering. However, I'm afraid that, depending on the structure of the DAG, I may have to test a very large number of orderings before a valid one is found.

Thus, I'm looking for a procedure to perturb a topological ordering, and to combine two topological orderings, such that the result is guaranteed to be another topological ordering.

There is no one correct answer. You may have to try different possibilities and see how well they work.

One candidate mutation operation is the following: pick a random pair of adjacent nodes (i.e., adjacent in the ordering), swap them, and check if the result is still a valid topological ordering. If not, try again.

Usually with genetic programming we want to do local search, i.e., we want each mutation to make a small change to the ordering -- not replace it with something entirely different.

Here is another approach you could try. Imagine labelling each node with a number. Now, this labelling induces an ordering: run a topological sort algorithm on the graph, but whenever the algorithm has multiple chioces for what to do next, break ties based on the labelling. For instance, use Kahn's algorithm, but replace "remove a node n from S" with "remove the node n from S with the smallest label". Now you can use your genetic algorithm to try to optimize the labelling, and you can apply mutation and breeding to the labelling, not to the ordering. Because the labelling does not have any complicated constraints, you can easily use simple mutation and breeding operators (e.g., a mutation is "change a single label", breeding is the standard crossover).

StackExchange Computer Science Q#149014, answer score: 7