More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?
Hmmm, I see some issues that are actually present in both of the approaches you propose.

It is important to note that the depth level that your Minimax search process manages to reach, and therefore also the speed with which it can traverse the tree, is extremely important for the algorithm's performance. Therefore, when evaluating how good or bad a particular heuristic function for move ordering is, it is not only important to look at how well it ordered moves; it is also important to take into account the runtime overhead of the heuristic function call. If your heuristic functions manages to sort well, but is so computationally expensive that you can't search as deep in the tree, it's often not really worth it. Neither of the solutions you propose are able to take this into account.

Another issue is that it's not trivial to measure what ordering is the "best". A heuristic that has the highest accuracy for the position of the best move only is not necessarily the best heuristic. For example, a heuristic that always places the best move in the second position ($0\%$ accuracy because it's in the wrong position, should be first position) might be better than a heuristic that places the best move in the first position $50\%$ of the time ($50\%$ accuracy), and places the best move last in the other $50\%$ of cases.



I would be more inclined to evaluate the performance of different heuristic functions by setting up tournaments where different versions of your AI (same search algorithm, same processing time constraints per turn, different heuristic function) play against each other, and measuring the win percentage.

This set up can also be done with two variants analogous to what you proposed; you can exhaustively put all the heuristic functions you can come up with against each other in tournaments, or you can let let an evolutionary algorithm sequentially generate populations of hypothesis-heuristic-functions, and run a tournament with each population. Generally, I would lean towards the evolutionary approach, since we expect it to search the same search space of hypotheses (heuristic functions), but we expect it to do so in a more clever / efficient manner than an exhaustive search. Of course, if you happen to have a ridiculous amount of hardware available (e.g., if you're Google), you might be able to perform the complete exhaustive search at once in parallel.



Note that there are also ways to do fairly decent move ordering without heuristic functions like the ones you suggested.

For example, you likely should be using iterative deepening; this is a variant of your search algorithm where you first only perform a search with a depth limit $d = 1$, then repeat the complete search process with a depth limit $d = 2$, then again with a limit $d = 3$, etc., until processing time runs out.

Once you have completed such a search process for a depth limit $d$, and move on to the subsequent search process with a limit of $d + 1$, you can order order the moves in the root node according to your evaluations from the previous search process (with depth limit $d$). Yes, here you would only have move ordering in the root node, and nowhere else, but this is by far the most influential / important place in the tree to do move ordering. Move ordering becomes less and less important as you move further away from the root.

If you're using a transposition table (TT), it is also common to store the "best move" found for every state in your TT. If, later on, you run into a state that already exists in your TT (which will be very often if you're using iterative deepening), and if you cannot directly take the stored value but have to actually do a search (for instance, because your depth limit increased due to iterative deepening), you can search the "best move" stored in the TT first. This is very light move ordering in that you only put one move at the front and don't order the rest, but it can still be effective.