FWIW, for that kind of search problem, I've found it useful to use a solver (or simpler exhaustive searches) on small windows as a local search, while continuin

FWIW, for that kind of search problem, I've found it useful to use a solver (or simpler exhaustive searches) on small windows as a local search, while continuing to use a stochastic search at the global level. E.g. consider a window of (say) 6 keys and ask if any of the 6! permutations of them are better, for each possible window over the keyboard. This is similar to n-opt in TSP. Make N as big as you can before your search falls down. Also try making a random move and local searching the region around the random move. Try all ~n^2 pairs of n/2 windows to jointly optimize. etc. You can also make the local searches small by grouping keys and then search for the best permutation of whole group rather than single keys. Then alternate to windows of single keys.