GPU based Non-dominated Sorting Genetic Algorithm-II for multi-objective traffic light signaling optimization with agent based modeling

摘要

Micro-simulation becomes more and more important in the Intelligent Transportation Systems (ITS) research, because it can provide detailed descriptions of the system. For a multi-agent systems (MAS) modeling of an ITS, the computation burden is large, as it involves the computation of the state changing of all the agents. And, there are many multi-objective optimization problems in the ITS research. In this paper, we solve the traffic light signaling optimization problem and we take the average delay time and the average stop times as two objectives. We use a famous method of Non-dominated Sorting Genetic Algorithm II (NSGA-II). As NSGA-II can be viewed as an intelligent way of running a number of micro-simulations, usually the computation burden is huge. Graphics Processing Units (GPUs) have been a popular tool for parallel computing. The real transportation system runs in parallel and we think that a parallel tool is more suitable for the simulation and optimization of the system. We test GPU based NSGA-II method on a 4 intersection lattice road network, and on the 18 intersection road network of the Zhongguancun area of Beijing. Compared with the CPU version, the GPU version implementation achieves a speedup factor of 21.46 and 27.64 respectively.