Modern codecs offer numerous settings that can nonuniformly alter the encoding process. Some researchers have proposed video encoding multiobjective optimization, but none of these proposals addresses optimization of the entire encoder's option space when it is large. In this paper, we present a method for multiobjective encoding optimization of a given encoder in terms of relative video bitrate and encoding speed. The process takes place over one or more videos against a set of reference presets. It actively exploits similarities in the encoding process for similar videos. Experiments have shown that our method outperforms existing multiobjective optimization alternatives on every video/encoder pair, judging by the hypervolume metric. A comparison using an x264 encoder revealed that our method discovered configs that achieve 21.8% relative bitrate gains on average while keeping relative quality and encoding speed unchanged.