Answers are grounded in this paper and cite their sources.
of a dissertation at the University of Miami. Dissertation supervised by Miroslav Kubat, Ph.D. No. of pages in text. (256) The Genetic Algorithm (GA) is a blueprint for writing computer programs capable of solving search and optimization problems. The GA blueprint describes an iterative search process that seeks to improve the quality of an initial random set of solutions (known as a “population of specimens”) with respect to some user-defined optimization criteria. All of the components of this iterative search process mimic Darwinian biological evolutionary processes such as mating, recombination, mutation, and survival of the fittest. Thus, the GA is an evolutionary approach to search and optimization. The GA has been applied to thousands of research and industrial applications across numerous domains of science. Due to its success and popularity, researchers have attempted to improve various aspects of the GA search process over the years. However, the impact of the mating strategy, which determines how existing solutions to a problem are paired during the genetic search process to generate new and better solutions, has so far been neglected in the rich and vast GA literature. The long-standing conventional mating strategy, which has been used for decades in implementations of the GA, is based on the random selection of mating partners. This paradigm has known issues. First, due to its stochastic nature, the conventional mating strategy does not guarantee that the solutions paired to generate new solutions have orthogonal (or independent) information content. This leads the GA to under-utilize the information available for the genetic search process. Second, the conventional mating strategy promotes highly-fit solutions to mate more often than others. These highly-fit solutions eventually overrun the entire set of solutions during the genetic search process, leading to issues of premature convergence to suboptimal solutions. The goal of this work is to show that the GA search process can be expedited, with the quality of its solutions improved, by replacing the conventional mating strategy with more sophisticated ones that are inspired from the Darwinian principle of ”opposites-attract.” The mating strategies proposed in this work improve over the conventional mating strategy, in which specimens (or solutions) have no mating choice, by “endowing” specimens in the GA population with mating-instincts that promote a more diverse pairing of solutions. The end result is an improved utilization of the information available for the genetic search process to discover new and better solutions and, consequently, a more efficient sampling of the solution search space of complex optimization problems. A total of five novel “instinct-based” mating strategies are proposed in this work. Four of these mating strategies are designed as single-population GA mating strategies, and one as a multi-population GA mating strategy. The five proposed mating strategies are collectively referred to by the acronym IM-GA, which stands for Instinct-Based Mating in Genetic Algorithms. To measure the effectiveness of the proposed mating strategies, they were tested on two well-known, complex optimization iii problems from the domain of supervised classification: 1) the 1-NN Tuning problem (“Testbed Problem 1”), and 2) the Optimal Decision Forests problem (“Testbed problem 2”). The 1-NN Tuning problem involves the search for optimal subsets of examples and attributes that simultaneously maximize the accuracy and minimizes the classification costs of the 1-NN classifier. The Optimal Decision Forests problem involves the search for highly-accurate and compact decision tree classifiers that can be grouped into ensembles to simultaneously maximize their combined voting classification accuracy while minimizing the overall classification costs. Testbed Problem 1 was solved by an improved implementation of a well-known GA, the RK-GA (hereinafter “baseline RK-GA0”). Testbed Problem 2 was solved by a novel GA that was implemented for the purposes of this research, the baseline TMGA0. Rigorous experiments were performed to evaluate the performances of these two GAs both with and without the proposed IM-GA “instinct-based” mating strategies. The various data sets used in the experiments were taken from the well-known UCI Machine Learning Repository. The experimental results indicated a statistically significant increase in the search speed of the GA when the IM-GA mating strategies were applied to the two chosen testbed problems. Furthermore, this increased search speed did not come at the cost of the quality of the discovered solutions and required only negligible additional computational overhead. Therefore, this work shows that more sophisticated mating strategies can indeed improve the genetic search process over the conventional mating strategy.
No takes yet. Share an insight, caveat, or question.
Thiago Quirino (2012) studied this question.