Advances in Genetic Algorithm Optimization of Traffic Signals
Publication: Journal of Transportation Engineering
Volume 135, Issue 4
Abstract
Recent advances in the optimization of fixed time traffic signals have demonstrated a move toward the use of genetic algorithm optimization with traffic network performance evaluated via stochastic microscopic simulation models. This paper examines methods for improved optimization. Factors examined included the number of replications of the stochastic traffic simulation performed, the use of common random numbers to reduce variability, modified versions of the genetic algorithm, and alternative genetic operators. Computing resources are found to be best utilized by using a single replication of the traffic simulation model with common random numbers for fitness evaluations. Application of the cross-generational elitist selection, heterogeneous recombination, and cataclysmic mutation search algorithm with real crossover and mutation operators is found to offer improved optimization efficiency over the standard genetic algorithm with binary genetic operators. Combining the improvements, delay reductions between 13 and 30% were obtained on the test networks relative to the standard genetic algorithm approach. A coding scheme allowing for complete optimization of signal phasing is proposed as well as an alternative delay measurement.
Get full access to this article
View all available purchase options and get full access to this article.
References
Adams, W. F. (1936). “Road traffic considered as a random series.” J. Inst. Civ. Eng., 4, 121–130.
Aizawa, A. N., and Wah, B. W. (1994). “Scheduling of genetic algorithms in a noisy environment.” Evol. Comput., 2, 97–122.
Antonisse, J. (1989). “A new interpretation of schema notation that overturns the binary encoding constraint.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 86–91.
Bäck, T., and Hoffmeister, F. (1991). “Extended selection mechanisms in genetic algorithms.” Proc., 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 92–99.
Baker, J. E. (1985). “Adaptive selection methods for genetic algorithms.” Proc., 1st Int. Conf. on Genetic Algorithms and their Applications, Lawrence Erlbaum, Mahwah, N.J., 101–111.
Chaudhary, N. A., Kovvali, V. G., and Mahabubul Alam, S. M. (2002). “Guidelines for selecting signal timing software.” Rep. No. FHWA/TX-03/0-4020-P2, Texas Transportation Institute, College Station, Tex.
Chi, P.-C. (1989). “Genetic search with proportion estimations.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 92–97.
Davis, L. (1991a). “Bit climbing, representational bias, and test suite design.” Proc., 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 18–23.
Davis, L. (1991b). Handbook of genetic algorithms, Van Nostrand Reinhold, New York.
Eshelman, L. J. (1991). “The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination.” Foundations of genetic algorithms, Morgan Kaufmann, San Mateo, Calif., 265–283.
Eshelman, L. J., Caruana, R. A., and Schaffer, J. D. (1989). “Biases in the crossover landscape.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 10–19.
Eshelman, L. J., and Schaffer, J. D. (1991). “Preventing premature convergence in genetic algorithms by preventing incest.” Proc., 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 115–122.
Eshelman, L. J., and Schaffer, J. D. (1993). “Real-coded genetic algorithms and interval-schemata.” Foundations of genetic algorithms-2, Morgan Kauffman, San Mateo, Calif., 187–202.
Federal Highway Administration (FHwA). (2003). Traffic software integrated system (TSIS), Version 5.1 user’s guide, Office of Operations Research, Development and Technology, Washington, D.C.
Fitzpatrick, J. M., and Grefenstette, J. J. (1988). “Genetic algorithms in noisy environments.” Mach. Learn., 3, 101–120.
Foy, M. D., Benekohal, R. F., and Goldberg, D. E. (1992). “Signal timing determination using genetic algorithms.” Transportation Research Record. 1365, Transportation Research Board, Washington, D.C., 108–115.
Gartner, N. H., Assmann, S. F., Lasaga, F., and Hou, D. L. (1990). “MULTIBAND—A variable-bandwidth arterial progression scheme.” Transportation Research Record. 1287, Transportation Research Board, Washington, D.C., 212–222.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning, Addison Wesley, Reading, Mass.
Goldberg, D. E. (1991). “The theory of virtual alphabets.” Parallel problem solving from nature, Springer, New York, 13–22.
Goldberg, D. E., and Deb, K. (1991). “Comparative analysis of selection schemes used in genetic algorithms.” Foundations of genetic algorithms, Morgan Kaufmann, San Mateo, Calif., 69–93.
Gordon, V. S., and Whitley, D. (1993). “Serial and parallel genetic algorithms as function optimizers.” Proc., 5th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 177–183.
Grefenstette, J. (1986). “Optimization of control parameters for genetic algorithms.” IEEE Trans. Syst. Man Cybern., 16, 122–128.
Grefenstette, J. J., and Fitzpatrick, J. M. (1985). “Genetic search with approximate function evaluations.” Proc., 1st Int. Conf. on Genetic Algorithms and Their Applications, Lawrence Erlbaum, Mahwah, N.J., 112–120.
Hale, B. (2005). Traffic network study tool, TRANSYT-7F, United States Version 10, McTrans Center, Univ. of Florida, Gainesville, Fla.
Hinterding, R., Gielewski, H., and Peachey, T. C. (1995). “The nature of mutation in genetic algorithms.” Proc., 6th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 65–72.
Hunter, A. (1998). “Crossing over genetic algorithms: The Sugal generalized GA.” J. Heuristics, 4, 179–192.
Kesur, K. B. (2007). Advances in genetic algorithm optimization of traffic signals, MSc dissertation, Univ. of the Witwatersrand, Witwatersrand, South Africa, ⟨http://witsetd.wits.ac.za:8080/dspace/bitstream/123456789/4900/1/TrafficSignalOptimization.pdf⟩.
Law, A. M., and Kelton, D. W. (1991). Simulation modeling and analysis, McGraw-Hill, New York.
Memon, G. Q., and Bullen, A. G. R. (1996). “Multivariate optimization strategies for real-time traffic control signals.” Transportation Research Record. 1554, Transportation Research Board, Washington, D.C., 36–42.
Messer, C. J., and Bonneson, J. A. (1997). NCHRP web document 12: Capacity analysis of interchange ramp terminals, Transportation Research Board, National Research Council, Washington, D.C.
Meysenburg, M. M., and Foster, J. A. (1997). “The quality of pseudo-random number generators and simple genetic algorithm performance.” Proc., 7th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 276–282.
Michalewicz, Z. (1996). Genetic algorithms + data structures = evolution programs, Springer, Berlin.
Nissen, V., and Propach, J. (1998). “On the robustness of population-based versus point-based optimization in the presence of noise.” IEEE Trans. Evol. Comput., 2, 107–119.
Oda, T., Otokita, T., Tsugui, T., Kohno, M., and Mashiyama, Y. (1996). “Optimization of signal control parameters using a genetic algorithm.” Proc., 3rd Annual World Congress on Intelligent Transportation Systems, Orlando, Fla.
Park, B. (1998). “Development of genetic algorithm based signal optimization program for oversaturated intersections.” Ph.D. thesis, Texas A&M Univ., College Station, Tex.
Rana, S., Whitley, D., and Cogswell, R. (1996). “Searching in the presence of noise.” Proc., 4th Int. Conf. on Parallel Problem Solving from Nature (PPSN IV), Springer, Berlin, 198–207.
Rathi, A. K. (1992). “The use of common random numbers to reduce the variance in network simulation of traffic.” Transp. Res., Part B: Methodol., 26, 357–363.
Reeves, C. R. (1993). “Using genetic algorithms with small populations.” Proc., 5th Int. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 92–99.
Rouphail, N. M., Park, B., and Sacks, J. (2000). “Direct signal timing optimization: Strategy development and results.” Technical Rep. No. 109, National Institute of Statistical Sciences, Research Triangle Park, N.C.
Schaffer, J. D., Eshelman, L. J., and Offutt, D. (1991). “Spurious correlations and premature convergence in genetic algorithms.” Foundations of genetic algorithms, Morgan Kaufmann, San Mateo, Calif., 102–112.
Stamatiadis, C., and Gartner, N. H. (1996). “MULTIBAND-96: A program for variable bandwidth progression optimization of multiarterial traffic networks.” Transportation Research Record. 1554, Transportation Research Board, Washington, D.C., 9–17.
Syswerda, G. (1989). “Uniform crossover in genetic algorithms.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 2–9.
Webster, F. V. (1958). “Traffic signal settings.” Road Research Technical Paper No. 39, H.M.S.O., London.
Whitley, D. (1989). “The GENITOR algorithm and selection pressure: Why rank based allocation of reproductive trials is best.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 116–121.
Whitley, D., Beveridge, R., Graves, C., and Mathias, K. (1995). “Test driving three 1995 genetic algorithms: New test functions and geometric matching.” J. Heuristics, 1, 77–104.
Whitley, D., and Hanson, T. (1989). “Optimizing neural networks using faster more accurate genetic search.” Proc., 3rd Int. Conf. in Genetic Algorithms, Morgan Kaufmann, San Mateo, Calif., 391–397.
Whitley, D., and Kauth, J. (1988). “GENITOR: A different genetic algorithm.” Proc., Rocky Mountain Conf. on Artificial Intelligence, Denver, 118–130.
Wright, A. H. (1991). “Genetic algorithms for real parameter optimization.” Foundations of genetic algorithms, Morgan Kaufmann, San Mateo, Calif., 205–218.
Yang, X. K. (2001). “Comparisons among computer packages in providing timing plans for Iowa arterial in Lawrence, Kansas.” J. Transp. Eng., 127, 311–318.
Yun, I., and Park, B. (2005). “Stochastic optimization method for coordinated actuated signal systems.” Research Rep. No. UVACTS-15-0-102, Center for Transportation Studies, Univ. of Virginia, Charlottesville, Va.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 135 • Issue 4 • April 2009
Pages: 160 - 173
Copyright
© 2009 ASCE.
History
Received: Feb 15, 2008
Accepted: Aug 27, 2008
Published online: Apr 1, 2009
Published in print: Apr 2009
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.