4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Are you sure the objective function really is a blackbox? Could you perhaps derive a heuristic function that assigns costs to partial orderings? This might make a huge difference. For instance, the only difference between "bruteforce" and "backtracking" is the ability to invalidate a partial solution. Genetic algorithms also rely on the assumption that mixing two good partial solutions can result in a good solution. $\endgroup$
    – Stef
    Feb 7, 2022 at 13:47
  • $\begingroup$ @Stef thanks for doing all this research. Most of these questions seem to be concerned with generating a random topological sort. However, I don't think this is adequate for performing a local search, where you need to generate a "neighbor", i.e. another topological sort which is similar in some sense to the initial one, say obtainable via a few exchanges from the initial one. I don't think a random new topological ordering would fit this. $\endgroup$
    – swineone
    Feb 7, 2022 at 17:12
  • $\begingroup$ I linked those questions to address this particular paragraph: "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." $\endgroup$
    – Stef
    Feb 7, 2022 at 19:04

3 Answers 3

2
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ Thank you so much for this. I have implemented this in the context of my problem, and the resulting combinations almost always work -- the (very rare) failures are not due to any problem with your proof, but because some candidate solutions, created by the mutation operator I chose, are not topological orderings, but are still valid solutions to my problem, and thus I do not discard them. When these solutions are chosen as parents for the combination operator, occasionally they generate invalid children. But again: this is problem-specific and not a general issue with your solution. $\endgroup$
    – swineone
    Feb 18, 2022 at 22:43
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.