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.