GA puzzle solver stuck at local maximum
1000 individuals is typically a fairly large population, so lacking further information, you're probably fine there.

You don't say how quickly your algorithm is converging or exactly you calculate the weights for weighted selection, but if you're doing the typical roulette-wheel or fitness-proportionate selection, it's known that that method produces a large amount of selection pressure, particularly early in the run. What happens is that most early solutions are terrible, so the first mediocre thing it finds gets a much higher proportion of the total fitness than it really deserves and quickly swamps the population. The easiest way to avoid that is to use something with a more controllable selection pressure, like binary tournament selection or rank-biased selection.

For mutation, the general rule of thumb has always been to mutate each allele independently with probability 1/n. Like any heuristic, that's only a starting point, and you should let experiment guide you in making any adjustments, but if I'm understanding you correctly, you have 192 alleles, so a 4% mutation rate gives an expectation of about 8 mutations per individual, which I would guess is too high.

Or do you mean you make a single mutation to 4% of the generated offspring? If that's the case, it's probably too low. I'd start with a method that mutates every single individual by a randomly selected amount, with the expected amount being one flip. Some individuals will get two or three flips, others will not be altered at all.

The third idea, having multiple populations and sharing between them goes by the name of "island model" GAs, and has been known to work pretty well for some problems. However, I think in your case there are some issues with the way the underlying algorithm is working that need to be addressed before moving to a parallel model that will only make it more difficult to tease out the dynamics of what's going on.

Without more details about exactly how you're encoding your solutions, how your crossover and mutation operators work, etc., we're kind of limited to general statements such as those I just made. Feel free to post any clarifications though and I'll take another run at helping understand what might be going on.