Nowadays the increase of traffic causes numerous serious traffic jams, and traffic signals are desired to work adaptively for dynamic traffic flows. In this paper, we view such a problem of traffic signal control as a multi-agent problem where each signal has a controlling agent, and aim to make the agents work cooperatively depending on the traffic status. To build such an agent program automatically, we introduce genetic programming (GP), an evolutionary method for program construction. In GP, it is known as important to encapsulate the substructures of a program which leads to higher fitness to the environment, and we propose a new encapsulation method using an efficient technique for discovering frequent substructures, which has been recently proposed in the data mining field. We also conducted a simulation with a real traffic data, and confirmed that GP with our encapsulation method outperforms the normal GP. It is also observed that the best individual has a communication part that chooses an appropriate communication area and adapts to the traffic status.