Genetic algorithms

Three major problems make Genetic Programming unfeasible or impractical
for real world problems.
The first is the excessive time complexity.In nature the evolutionary process
can take millions of years, a time frame that is clearly not acceptable for the solution
of problems on a computer. In order to apply Genetic Programming to real world
problems, it is essential that its efficiency be improved.
The second is called overfitting (where results are inaccurate outside the
training data). In a paper[36] for the Federal Reserve Bank, authors Neely and
Weller state “a perennial problem with using flexible, powerful search procedures
like Genetic Programming is overfitting, the finding of spurious patterns in the data.
Given the well-documented tendency for the genetic program to overfit the data it
is necessary to design procedures to mitigate this.”
The third is the difficulty of determining optimal control parameters for the
Genetic Programming process. Control parameters control the evolutionary process. They include settings such as, the size of the population and the number of generations
to be run. In his book[45], Banzhaf describes this problem, “The bad
news is that Genetic Programming is a young field and the effect of using various
combinations of parameters is just beginning to be explored.”
We address these problems by implementing and testing a number of novel
techniques and improvements to the Genetic Programming process. We conduct
experiments using data sets of various degrees of difficulty to demonstrate success
with a high degree of statistical confidence.

Multi-agent control is a very promising area of robotics. In applications for which it is difficult or impossible for humans to intervene, the utilization of multi-agent, autonomous robot groups is indispensable. This thesis presents a novel approach to reactive multi-agent control that is practical and elegant in its simplicity. The basic idea upon which this approach is based is that a group of robots can cooperate to determine the shortest path through a previously unmapped environment by virtue of redundant sharing of simple data between multiple agents. The idea was implemented with two robots. In simulation, it was tested with over sixty agents. The results clearly show that the shortest path through various environments emerges as a result of redundant sharing of information between agents. In addition, this approach exhibits safeguarding techniques that reduce the risk to robot agents working in unknown and possibly hazardous environments. Further, the simplicity of this approach makes implementation very practical and easily expandable to reliably control a group comprised of many agents.

Many complex engineering designs have conflicting requirements that must be compromised to effect a successful product. Traditionally, the engineering approach breaks up the complex problem into smaller sub-components in known areas of study. Tradeoffs occur between the conflicting requirements and a sub-optimal design results. A new computational approach based on the evolutionary processes observed in nature is explored in this dissertation. Evolutionary algorithms provide methods to solve complex engineering problems by optimizing the entire system, rather than sub-components of the system. Three standard forms of evolutionary algorithms have been developed: evolutionary programming, genetic algorithms and evolution strategies. Mathematical and algorithmic details are described for each of these methods. In this dissertation, four engineering problems are explored using evolutionary programming and genetic algorithms. Exploiting the inherently parallel nature of evolution, a parallel version of evolutionary programming is developed and implemented on the MasPar MP-1. This parallel version is compared to a serial version of the same algorithm in the solution of a trial set of unimodal and multi-modal functions. The parallel version had significantly improved performance over the serial version of evolutionary programming. An evolutionary programming algorithm is developed for the solution of electronic part placement problems with different assembly devices. The results are compared with previously published results for genetic algorithms and show that evolutionary programming can successfully solve this class of problem using fewer genetic operators. The finite element problem is cast into an optimization problem and an evolutionary programming algorithm is developed to solve 2-D truss problems. A comparison to LU-decomposition showed that evolutionary programming can solve these problems and that it has the capability to solve the more complex nonlinear problems. Finally, ordinary differential equations are discretized using finite difference representation and an objective function is formulated for the application of evolutionary programming and genetic algorithms. Evolutionary programming and genetic algorithms have the benefit of permitting over-constraining a problem to obtain a successful solution. In all of these engineering problems, evolutionary algorithms have been shown to offer a new solution method.

This thesis presents a model designed to optimize the allocation of corporate resources required for the success of a product in the marketplace. The product development resources used in the model are: market research, applied research, product design, cost reduction and advertising. The key goals of this thesis are to provide industry with a usable tool: (1) Implement strategic plans through effective budgeting; (2) Optimize both short and long term profits; (3) Evaluate the impact of resource inter-dependencies; (4) Enable accountability that leads to goal achievement and checks unnecessary growth; (5) Remove much of the negative political and emotional variability; (6) Easily adapt to internal and external changes; (7) Output a specific allocation for each resource as a percentage of sales; (8) Output an estimate of future profitability. Genetic Algorithms are particularly well suited for this application because an exact optima is not required and the search space can be extremely large, complex, and non-linear.

This thesis presents the results of an empirical investigation of the applicability of genetic algorithms to a real-world problem in software reliability--the fault-prone module identification problem. The solution developed is an effective hybrid of genetic algorithms and neural networks. This approach (ENNs) was found to be superior, in terms of time, effort, and confidence in the optimality of results, to the common practice of searching manually for the best-performing net. Comparisons were made to discriminant analysis. On fault-prone, not-fault-prone, and overall classification, the lower error proportions for ENNs were found to be statistically significant. The robustness of ENNs follows from their superior performance over many data configurations. Given these encouraging results, it is suggested that ENNs have potential value in other software reliability problem domains, where genetic algorithms have been largely ignored. For future research, several plans are outlined for enhancing ENNs with respect to accuracy and applicability.

This thesis refers to a research addressing the use of information-theoretic techniques in optimizing an artificial neural network (ANN) via a genetic selection algorithm. Pertinent studies address emulating relevant experiments on a test ANN (based on Hopfield's associative memory model) wherein the said optimization is tried with different sets of control parameters. These parameters include a new entity based on the concept of entropy as conceived in the field of information theory. That is, the mutual entropy (Shannon entropy) or information-distance (Kullback-Leibler-Jensen distance) measure between a pair of candidates is considered in the reproduction process of the genetic algorithm (GA) and adopted as a selection-constraint parameter. The research envisaged further includes a comparative analysis of the test results which indicate the importance of proper parameter selection to realize an optimal network performance. It also demonstrates the ability of the concepts proposed here in developing a new neural network approach for pattern recognition problems.

Vision systems have been widely used for parts inspection in electronics assembly lines. In order to improve the overall performance of a visual inspection system, it is important to employ an efficient object recognition algorithm. In this thesis work, a genetic algorithm based correlation algorithm is designed for the task of visual electronic parts inspection. The proposed procedure is composed of two stages. In the first stage, a genetic algorithm is devised to find a sufficient number of candidate image windows. For each candidate window, the correlation is performed between the sampled template and the image pattern inside the window. In the second stage, local searches are conducted in the neighborhood of these candidate windows. Among all the searched locations, the one that has a highest correlation value with the given template is selected as the best matched location. To apply the genetic algorithm technique, a number of important issues, such as selection of a fitness function, design of a coding scheme, and tuning of genetic parameters are addressed in the thesis. Experimental studies have confirmed that the proposed GA-based correlation method is much more effective in terms of accuracy and speed in locating the desired object, compared with the existing Monte-Carlo random search method.

Research and applications of genetic algorithms have become increasingly important in a wide variety of scientific fields. In this thesis, we present an empirical analysis of genetic algorithms in the function optimization area. As a focus of our research, a novel empirical analysis approach to various genetic algorithms is provided. The research starts from the survey of current trends in genetic algorithms, followed by exploring the characteristics of the simple genetic algorithm, the modified genetic algorithm and hybridized genetic algorithm. A number of typical function optimization problems are solved by these genetic algorithms. Ample empirical data associated with various modifications to the simple genetic algorithm is also provided. Results from this research can be used to assist practitioners in their applications of genetic algorithms.

In this thesis work, techniques developed in the science of genetic computing is applied to solve the problem of planning a robot calibration experiment. Robot calibration is a process by the robot accuracy is enhanced through modification of its control software. The selection of robot measurement configurations is an important element in successfully completing a robot calibration experiment. A classical genetic algorithm is first customized for a type of robot measurement configuration selection problem in which the robot workspace constraints are defined in terms of robot joint limits. The genetic parameters are tuned in a systematic way to greatly enhance the performance of the algorithm. A recruit-oriented genetic algorithm is then proposed, together with new genetic operators. Examples are also given to illustrate the concepts of this new genetic algorithm. This new algorithm is aimed at solving another type of configuration selection problem, in which not all points in the robot workspace are measurable by an external measuring device. Extensive simulation studies are conducted for both classical and recruit-oriented genetic algorithms, to examine the effectiveness of these algorithms.

The crucial goal of enhancing industrial productivity has led researchers to look for robust and efficient solutions to problems in production systems. Evolving technologies has also, led to an immediate demand for algorithms which can exploit these developments. During the last three decades there has been a growing interest in algorithms which rely on analogies to natural processes. The best known algorithms in this class include evolutionary programming, genetic algorithms, evolution strategies and neural networks. The emergence of massively parallel systems has made these inherently parallel algorithms of high practical interest. The advantages offered by these algorithms over other classical techniques has resulted in their wide acceptance. These algorithms have been applied for solving a large class of interesting problems, for which no efficient or reasonably fast algorithm exists. This thesis extends their usage to the domain of production research. Problems of high practical interest in the domain of production research are solved using a subclass of these algorithms i.e. those based on the principle of evolution. The problems include: the flowpath design of AGV systems and vehicle routing in a transportation system. Furthermore, a Genetic Based Machine Learning (GBML) system has been developed for optimal scheduling and control of a job shop.