I do think that something could be done. I'm not very familiar with Ant Colony Optimization in particular, and it's not immediately obvious to me how it would be applied here. Specifically, how would it take advantage of the algorithmic complexity if that's all we know beforehand? Often, we're working with infinite parameter spaces where even reasonable subsets will grow exponentially large as we expand them. Is there something like a lazy version of Ant Colony Optimization which can be applied here?
I do think some kind of randomized, learning search would be helpful. I mentioned genetic programming and I think stochastic supercompilation like searches (a la Stoke) would likely work as well.