Plenary Lecture

A Critical Review of the Mathematical Robustness of Genetic Algorithms in Optimization Problems

Associate Professor Manoj K. Jha
Center for Advanced Transportation and
Infrastructure Engineering Research
Department of Civil Engineering
Morgan State University
1700 East Cold Spring Lane, Baltimore, MD 21251
USA
E-mail: manoj.jha@morgan.edu

Abstract: Genetic Algorithms (GAs) have been shown to be particularly effective in many optimization problems due to their ability to search in a continuous space without getting trapped in local optima while exploiting the entire search space. Some recent research works however, show that the mathematical theory of GAs are not fully understood and its validity may be questioned. This may affect the quality and reliability of solutions obtained from the GA optimization process. In addition, sensitivity of critical parameters in GAs may also affect the quality of solution. If GAs are applied properly, similar solutions should be expected at each replication, regardless of where the search process starts. Some of the critical parameters affecting search performance include the number of genetic operators, the number of decision variables, the parameter for selective pressure, and the parameter for non-uniform mutation.
In this presentation I provide a critical review of the mathematical foundation of GAs and also show a sensitivity analysis of the critical parameters that may affect the quality of solutions. Attention is directed specifically to the schema theory, which are considered to be the building blocks for GA operation. Using my previous collaborative work with Dr. David Lovell of the University of Maryland, College Park I show a hard upper bound on the number of matching schemata in binary and real coded GAs for a population of a given size and string length. A loose upper bound is commonly reported in the published literature, but does not take into account redundancies that are inevitable for certain values of the population size. In this ppresentation, this over-counting is rectified. A special case when the string length is small compared to the population size is shown to have a particularly elegant solution. In order to investigate the effects of critical parameters when adopting GAs I show a sensitivity analysis using previous collaborative work with Dr. Eungcheol Kim of the University of Incheon, South Korea, which shows that quality of solutions depend on their proximity of convergence from different starting points. Finally, we investigate the improvement in solution quality with the derived hard upper bound.

Brief Biography of the Speaker:
Dr. Manoj K. Jha is Associate Professor and Founding Director of the Center for Advanced Transportation and Infrastructure Engineering Research (CATIER) in the department of civil engineering at the Morgan State University, Baltimore, MD, USA. He obtained a Ph.D. in Civil Engineering with transportation specialization from the University of Maryland, College Park in 2000; a M.S. degree in Mechanical Engineering from the Old Dominion University in 1993; and a B.E. degree in Mechanical Engineering from the National Institute of Technology, Durgapur, India in 1991. He also attended the Rensselaer Polytechnic Institute during 1993-94 as a Ph.D. student in Mechanical Engineering and Virginia Tech.’s National Capital campus as a post doctoral fellow during 2000-2001.
Dr. Jha’s research interests are in investigating mathematic foundation of artificial intelligence-based optimization algorithms, and highway route optimization and visualization. For his scholastic and research achievements Dr. Jha has received several awards, among which are the 2005 and 2006 United Negro College Funds Special Program/Department of Defense (UNCFSP/DoD) Faculty Development Award, 2005 Department of Homeland Security (DHS) Summer Faculty Research award by the Study of Terrorism and Responses to Terrorism (START) Center of Excellence, University of Maryland, College Park, and 2005 NSF-PASI-TS (National Science Foundation’s Pan-American Advanced Study Institute on Transportation Sciences) award by the Rensselaer Polytechnic Institute. He is a registered Professional Engineer in the State of Maryland since 1997.
Dr. Jha has served as a PI, Co-PI, or collaborator with other researchers on numerous research project totaling over $4 million. The key sponsoring agencies of his research projects include Army Research Lab., Maryland State Highway Administration, Federal Highway Administration, National Science Foundation, and several Baltimore area consulting firms. Dr. Jha has authored (or co-authored) more than 90 articles in journals, books, and conference proceedings in the highway design, optimization, and transportation literature. He has also co-authored 2 books on road design entitled “Intelligent Road Design” and “Fundamentals of Road Design.”