I would say that hill climbing with random restarts works better because you must first define a cost function in a precise (and concise) symbolic mathematical way. Very much similar to simulated annealing, stochastic gradient descent and the like. However, GA's can be applied regardless of the piece of knowledge that is required to build this cost function. GA is a universal optimisation technique: as long as you can encode features in a gene form (this is very convenient for binary attributes) and rate the fitting of that gene you are ready to search the optimum.

My stab at explaining GA's: http://ai-maker.atrilla.net/the-%EF%BB%BFgenetic-algorithms/