A combination of the search for both good lower bounds and upper bounds on the optimal value may help a lot for *most* problems - it is in any case better than to focus only on one of them.

I think combining opposition based learning (OBL) with the heuristic you are utilizing is one of the ways you can arrive at the good solutions quickly. There are a large number of opposition based strategies you can use, you may have to experiment, which depends on your search space. Only drawback is the increase in computational effort (for example the most general form of OBL will lead to twice the evaluations) but if implemented only for initialization stage, it shouldn't have much of an impact.

Other than that, chaotic map based initializations are also there but its weaker and highly circumstantial compared to OBL, according to me.

Finally, as Michael Patriksson pointed out, to search for optimal bounds will work for most problem.

The simplest think you can try is a random search as initialization: https://en.wikipedia.org/wiki/Random_search

Thanks Michael Patriksson , definitely would try that on some of my problems. thanks Iago Augusto Carvalho i would look into approximate algorithms, from experience i know heuristics are usually good as well but I havent tried approximate algorithms. Maybe i can try random search first since its the simplest according to Todor Balabanov . i havent heard of chaotic map initialization before, thanks for pointing out Dhruv