A GPU-Based Parallel Genetic Algorithm for Generating Daily Activity Plans

Kai Wang

doi:10.1109/TITS.2012.2205147

2012-09-01

PRE

Kai Wang

Zhen Shen *

DOI：10.1109/TITS.2012.2205147

原文链接

原文求助

摘要

En 中文

As computing technologies develop, there is a trend in traffic simulation research in which the focus is moving from macro- and meso-simulation to micro-simulation since microsimulation can provide more detailed quantitative results. Moreover, the success of the Artificial societies-Computational experiments-Parallel execution (ACP) approach indicates that integrating other metropolitan systems such as logistic, infrastructure, legal and regulatory, and weather and environmental systems to build an Artificial Transportation System (ATS) can be helpful in solving Intelligent Transportation Systems (ITS) problems. However, the computational burden is very heavy as there are many agents interacting in parallel in the ATS. Therefore, a parallel computing tool is desirable. We think that we can employ a Graphics Processing Unit (GPU), which has been applied in many areas. In this paper, we use a GPU-adapted Parallel Genetic Algorithm (PGA) to solve the problem of generating daily activity plans for individual and household agents in the ATS, which is important as the activity plans determine the traffic demand in the ATS. Previous research has shown that GA is effective but that the computational burden is heavy. We extend the work to GPU and test our method on an NVIDIA Tesla C2050 GPU for two scenarios of generating plans for 1000 individual agents and 1000 three-person household agents. Speedup factors of 23 and 32 are obtained compared with implementations on a mainstream CPU.

Keyword:

Artificial societies-Computational experiments-Parallel execution (ACP)

artificial transportation system (ATS)

compute unified device architecture (CUDA)

daily activity plan

genetic algorithm (GA)

graphics processing unit (GPU)

microsimulation