A bottleneck in interactive storytelling is the authorial burden of writing narrative units, and connecting them to the interactive narrative structure. To address this problem, we present a hybrid approach that combines AI planning and evolutionary optimization in order to generated new plan operators representing possible story actions, within the framework of a planning-based interactive narrative system. We focus our work on inventing plan operators that are useful for contributing to suspenseful interactive stories, using suspense metrics that have been proposed in the literature. We devise an encoding scheme for converting a plan operator into a genetic-algorithm chromosome and vice versa, respecting constraints that are needed for an operator to be well-formed. We discuss the performance of the system, and several examples from preliminary experiments carried out to evaluate the evolved operators.