Metaheuristics are blind methods that make very few assumptions about the structure of the solution space. If you already know some of the structure of course you can find a better optimization algorithm. Better yet, you can find a better representation or mutation function that will massively shrink the search space. Or a fitness function more likely to lead evolution through the correct path. Or even seed solutions that give the algorithm a head start.
>On the other hand if you prove a theorem stating that for this types of problems, if you let GA run for this amount of time you are going to be close to the optimum with high probability. That would be phenomenally useful.
>At its basic, GA is a parallelized and randomized exploration of the space. Tell me why is that particular way of randomization and parallelization the right thing to do, or for what classes of problems is it the right thing to do. Without this, they are anecdotes.
That's pretty much impossible. If you already know so much about the problem space to the point of being able to prove theorems about it, then you don't need metaheuristics.
With apologies, if a proponent of an algorithm cannot tell me under what circumstances the proposed algorithm would do better, the proponent is selling me snake oil. There has to be some quantitative statements about their properties, not necessarily proof of convergence to the global optimum. Otherwise it is not science, (yet). Its not an understanding of the space of an arbitrary problem that I desire, it is a measurable or mathematical characterization of the space where these algorithms work well, ideally the process of measurement should be cheaper than applying the algorithm.
EDIT: replaced 'you' with 'proponent' lest it gives the impression that I meant it personally.
We do know what kinds of situations genetic algorithms do well at (though generally other metaheuristics like hillclimbing do slightly better.) The fitness landscape has to be as smooth as possible and not have bad local optima. You want as few variables as possible. And you want them to be independently correlated with fitness. If an improvement requires multiple things to mutate all at once it's unlikely to happen.
There are various other heuristics. But you definitely need to have an understanding of the solution space (as well as the alternative) to know for sure.
>On the other hand if you prove a theorem stating that for this types of problems, if you let GA run for this amount of time you are going to be close to the optimum with high probability. That would be phenomenally useful.
>At its basic, GA is a parallelized and randomized exploration of the space. Tell me why is that particular way of randomization and parallelization the right thing to do, or for what classes of problems is it the right thing to do. Without this, they are anecdotes.
That's pretty much impossible. If you already know so much about the problem space to the point of being able to prove theorems about it, then you don't need metaheuristics.