In modular robotics, modules can be reconfigured to change the morphology of\nthe robot, making it able to adapt for specific tasks. However, optimizing both\nthe body and control is a difficult challenge due to the intricate relationship\nbetween fine-tuning control and morphological changes that can invalidate such\noptimizations. To solve this challenge we compare three different Evolutionary\nAlgorithms on their capacity to optimize morphologies in modular robotics. We\ncompare two objective-based search algorithms, with MAP-Elites. To understand\nthe benefit of diversity we transition the evolved populations into two\ndifficult environments to see if diversity can have an impact on solving\ncomplex environments. In addition, we analyse the genealogical ancestry to shed\nlight on the notion of stepping stones as key to enable high performance. The\nresults show that MAP-Elites is capable of evolving the highest performing\nsolutions in addition to generating the largest morphological diversity. For\nthe transition between environments the results show that MAP-Elites is better\nat regaining performance by promoting morphological diversity. With the\nanalysis of genealogical ancestry we show that MAP-Elites produces more diverse\nand higher performing stepping stones than the other objective-based search\nalgorithms. Transitioning the populations to more difficult environments show\nthe utility of morphological diversity, while the analysis of stepping stones\nshow a strong correlation between diversity of ancestry and maximum performance\non the locomotion task. The paper shows the advantage of promoting diversity\nfor solving a locomotion task in different environments for modular robotics.\nBy showing that the quality and diversity of stepping stones in Evolutionary\nAlgorithms is an important factor for overall performance we have opened up a\nnew area of analysis and results.\n