Title: Modelling time complexity of micro-genetic algorithms for online traffic control decisions

Authors: Ghassan Abu-Lebdeh; Kenan Hazirbaba; Omar Mughieda; Bassant Abdelrahman

Addresses: Department of Civil Engineering, American University of Sharjah, Sharjah, UAE ' Department of Civil and Infrastructure Engineering, American University of Ras Al Khaimah, Ras Al Khaimah, UAE ' Department of Civil Engineering, Abu Dhabi University, Abu Dhabi, UAE ' Department of Civil Engineering, American University of Sharjah, Sharjah, UAE

Abstract: This paper describes an experimental approach to test the suitability of micro-genetic algorithms (m-GAs) to solve large combinatorial traffic control problems and establishes relationships between time to convergence and problem size. A discrete time dynamical traffic control problem with different sizes and levels of complexity was used as a test-bed. Results showed that m-GAs can tackle computationally demanding problems. Upon appropriately sizing the m-GA population, the m-GA converged to a near-optimal solution in a number of generations equal to the string length. Results also demonstrated that with the selection of appropriate number of generations, it is possible to get most of the worth of the theoretically optimal solution but with only a fraction of the computation cost. Results showed that as the size of the optimisation problem grew exponentially, the time requirements of m-GA grew only linearly thus making m-GAs especially suited for optimising large-scale and combinatorial problems for online optimisation.

Keywords: online traffic control decisions; genetic algorithms; sustainable transport; genetic algorithms convergence.

DOI: 10.1504/IJIDS.2019.101141

International Journal of Information and Decision Sciences, 2019 Vol.11 No.2, pp.141 - 162

Received: 16 Jun 2017
Accepted: 07 Sep 2017
Published online: 25 Jul 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article