Genetic algorithms applied to topological orderings of a DAG

Question

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.

Answer 1

Another way of performing the combination operation is this:

• Randomly interleave both linear orderings (obtaining a tuple containing each node twice)
• Discard the second occurrence of each node

The result will be another topological ordering since

• It contains each node once
• If a<b in the DAG, then a will precede b in each original ordering, and whatever interleaving you use will have its first a before its first b.

Answer 2

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).

Answer 3

I am not sure if this will be good enough for the performance of your problem, but here are some things I could think of.

Combination

Find the shortest prefix of the two topological sequences which are permutations of each other and choose randomly between the two. Continue greedily from this point and so on. It might happen that this often results in very long substrings being selected. If that is the case, any substring which gives the permutation of the same elements in the two sequences can be swapped. Given that there are O(n^2) subsequences, it may be too expensive to do this but a compromise might be possible.

Mutation

Take a random element and find out how far it can be "bubbled" backward or forward without destroying the topological ordering. And select a random position out of those to place the element. It might even be enough to choose randomly among allowed swaps of adjacent elements. Now this might make certain graphs more probable than others (not sure), but I think it should be enough of a mutation for a genetic algorithm.