Even local optima are often pretty good in practice.

Also, it's a very good practice to iterate through the neighbors in a random order (if you're doing next descent, for steepest descent obviously it doesn't matter).

The simplest version where you just choose the single change that produces the best score isn't quite good enough for my purposes. I modified that slightly to run that to completion, then switch to choosing the two changes that produce the best score until that can't improve anymore either, which works a lot better. Fortunately my membership list is small enough that this is still computationally feasible.