Generalize a pair of method without lossing static typing checks

I am working with a pet project trying to practice (pure?) OO and can not figure out how to factorize a common behavior from a couple of classes.

public Solution improve(Solution initialSolution)
{
    stopCondition.setInitialSolution(initialSolution);

    Solution nextSolution = initialSolution;
    do
    {
        nextSolution = nextSolutionGenerator.generate(nextSolution);
    }
    while(!stopCondition.isStopConditionReached());

    return nextSolution;
}

As you can see, generate is common to both BinaryNextSolutionGenerator and PermutationNextSolutionGenerator. I know that Solution generate(Solution solution) should be in NextSolutionGenerator, however I do not want to lose the type verification at compile time if I send a PermutationSolution instance into a BinaryNextSolutionGenerator instance. Looks like I have to use generic programming or my design is fundamentally wrong (or is a common tradeoff?), but I would prefer some experienced opinion before.

BTW, generate only calls doGenerate because I am planning to add some common logging code in there.