The evolution of complexity is one of the prime features of life on Earth. Although well accepted as the product of adaptation, the dynamics underlying the evolutionary build-up of complex adaptive systems remains poorly resolved. Using simulated robot swarms that exhibit ant-like group foraging with trail pheromones, we show that their self-organizing capacity paradoxically involves regulatory behavior that arises in advance. We focus on a traffic rule on their foraging trail as a regulatory trait. We allow the simulated robot swarms to evolve pheromone responsiveness and traffic rules simultaneously. In most cases, the traffic rule, initially arising as selectively neutral component behaviors, assists the group foraging system to bypass a fitness valley caused by overcrowding on the trail. Our study reveals a hitherto underappreciated role of regulatory mechanisms in the origin of complex adaptive systems, as well as highlights the importance of embodiment in the study of their evolution.