Several tools for automatically testing Android applications have been proposed. In particular, Sapienz is a search-based tool that has been recently deployed in an industrial setting. Although it has been shown that Sapienz outperforms several state-of-the-art tools, it is still to be seen what features of SAPIENZ impact the most on its effectiveness. We conducted an extensive empirical study where we compare the impact of the search algorithm and the usage of motif genes, a more compact representation of individuals. Our empirical study shows that the usage of motif genes improves coverage both for Evolutionary Algorithms and random approaches. In particular, it also shows that NSGA-II, the multi-objective evolutionary algorithm used by Sapienz, does not have a clear improvement over other algorithms. In terms of number of crashes detected, our study shows that both NSGA-II and Random Search perform similarly. While the usage of motif genes improves the crash detection of algorithms, it is not enough to make it statistically significant. These facts cast doubts about the use of Evolutionary Algorithms in the context of Android test generation and suggest that motif genes can have a great impact on the overall effectiveness.