Generating child keys for a hill climb algorithm
My experience is that hill climbing is very efficient for solving substitution ciphers. As I understand there are two topics now.


How to generate the child keysSwapping characters of the key randomly (stochastic hill climbing) as well as trying all possible swap combinations is reasonable.  But for solving a substitution cipher I believe trying all possible character swaps per parent is more efficient. First, trying the same key more than once is avoided (at least for one parent), secondly it provides a clear condition when to stop the hill climbing: If none of the childs provide a better result than the parent.  Using the stochastic hill climbing and keeping track of the tried keys would be overkill, and I think effectively it turns this into trying all possible key swaps.
How to avoid a local maximumOne option is to use the Random-restart hill climbing (or Shotgun hill climbing, see http://en.wikipedia.org/wiki/Hill_climbing#Variants). It simply repeats the hill climbing using different random initial conditions and it works very well for breaking substitution ciphers.


Resources:


http://www.guballa.de/crypto/substitution.html
A substitution cipher solver, using the Random-restart hill climbing algorithm choosing always the first better key (called "simple hill climbing"). It uses Javascript Webworkers, so it will not run on some older browsers.
http://www.guballa.de/crypto/substitution_breaker.js
The related Javascript implementation