Heuristic with worst-case exponential complexity
While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential. 

Two canonical examples are the simplex algorithm for linear programming and the $k$-means heuristic for clustering. 

It seems highly unlikely that you'll be able to show a worst-case running time that's better than exponential for a GA-like heuristic. As Tobias points out, it would be useful to know if there's some kind of guarantee of quality if the heuristic is terminated early - but I'm pessimistic that this can be done as well.