Depending on multiple parameters, soft robots can exhibit different modes of locomotion that are difficult to model numerically. As a result, improving their performance is complex, especially in small-scale systems characterized by low Reynolds numbers, when multiple aero- and hydrodynamical processes influence their movement. In this work, we optimize light-powered millimetre-scale underwater swimmer locomotion by applying experimental results - measured swimming speed - as the fitness function in two evolutionary algorithms: particle swarm optimization and genetic algorithm. As these soft, light-powered robots with different characteristics (phenotypes) can be fabricated quickly, they provide a great platform for optimisation experiments, using many competing robots to improve swimming speed over consecutive generations. Interestingly, just like in natural evolution, unexpected gene combinations led to surprisingly good results, including eight-fold increase in speed or the discovery of a self-oscillating underwater locomotion mode.