I've also had the experience that hill climbing (with random restarts) can outperform GA's. In many problems you can fairly easily define a neighborhood concept for moves from the current solution. That tends to be easier than getting a meaningful crossover and mutation working. Then you just can hill climb by making neighborhood moves, with random restarts. Run 1000 random restarts and pick the best one, and you're going to have a really good solution.