The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Performance analysis for genetic algorithms.
Author:	Wong, Hermrean
View Online:	njit-etd1995-091 (xvi, 74 pages ~ 3.2 MB pdf)
Department:	Department of Mechanical Engineering
Degree:	Doctor of Philosophy
Program:	Mechanical Engineering
Document Type:	Dissertation
Advisory Committee:	Leu, M.C. (Committee chair) Chen, Rong-Yaw (Committee member) Blackmore, Denis L. (Committee member) Levy, Nouri (Committee member) Ji, Zhiming (Committee member)
Date:	1995-10
Keywords:	Genetic algorithms Optimization
Availability:	Unrestricted
Abstract:	Genetic algorithms have been shown effective for solving complex optimization problems such as job scheduling, machine learning, pattern recognition, and assembly planning. Due to the random process involved in genetic algorithms, the analysis of performance characteristics of genetic algorithms is a challenging research topic. Studied in this dissertation are methods to analyze convergence of genetic algorithms and to investigate whether modifications made to genetic algorithms, such as varying the operator rates during the iterative process, improve their performance. Both statistical analysis, which is used for investigation of different modifications to the genetic algorithm, and probability analysis, which is used to derive the expectation of convergence, are used in the study. The Wilcoxon signed rank test is used to examine the effects of changing parameters in genetic algorithms during the iterations. A Markov chain is derived to show how the random selection process affects the genetic evolution, including the so called genetic drift and preferential selection. A link distance is introduced as a numerical index for the study of the convergence process of order-based genetic algorithms. Also studied are the effects of random selection, mutation operator, and the combination of both to the expected average link distance. The genetic drift is shown to enforce the convergence exponentially with increase in the number of iterations. The mutation operator, on the other hand, suppresses the convergence. The combined results of these two parameters lead to a general formula for the estimation of the expected number of iterations needed to achieve convergence for the order-based genetic algorithm with selection and mutation and provide important insights about how order-based genetic algorithms converge.