A Software Product Line (SPL) is a set of products builtfrom a number of features, the set of valid products being dened bya feature model. Typically, it does not make sense to test all productsdened by an SPL and one instead chooses a set of products to test(test selection) and, ideally, derives a good order in which to test them(test prioritisation). Since one cannot know in advance which productswill reveal faults, test selection and prioritisation are normally based onobjective functions that are known to relate to likely effectiveness orcost. This article introduces a new technique, the grid-based evolutionstrategy (GrES), which considers several objective functions that assessa selection or prioritisation and aims to optimise on all of these. Theproblem is thus a many-objective optimisation problem. We use a newapproach, in which all of the objective functions are considered but one(pairwise coverage) is seen as the most important. We also derive a novelevolution strategy based on domain knowledge. The results of the evalua-tion, on randomly generated and realistic feature models, were promising,with GrES outperforming previously proposed techniques and a range ofmany-objective optimisation algorithms.