In this work, we study a multi-start weights-guided random bit climber (wgRBC). This algorithm selects a random weight from a predefined set, and a simple (1+1) random bit climber uses it to optimize, one bit at a time, the weighted sum of the objective functions of the problem until it reaches a local optimum. A population of non-dominated solutions generated during the climb is kept bounded using the set of weights. The algorithm iterates restarting the climber with a solution chosen randomly from the population of non-dominated solutions and selecting another weight randomly. Thus, the weights are used to provide climbing directions and to maintain a set of non-dominated solutions well-distributed in the reference population. We evaluate the method on subclasses of epistatic problems using MNK-landscapes, varying the number of objectives from 2 to 7 and the number of epistatic interactions from 1 to 20. We show that the simple wgRBC is largely superior to decomposition algorithms like MOEA/D and NSGA-III on this problem class.