Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

The parallel genetic algorithms (PGA) have been developed for combinatorial optimization problems, and its parallel efficiencies have been investigated on a specific problem. These investigations were concerned with how to design a topology and the determination of the optimum setting for parameters (for example, size of subpopulations, migration interval, and so on) rather than the effectiveness of genetic operators. This paper investigates a relation between the parallel efficiency of the coarse-grained PGA and genetic (crossover and selection) operators for the traveling salesman problem on an MIMD parallel computer. The following genetic operators are considered: improved edge recombination (IERX), distance preserving (DPX), and complete subtour exchange (CSEX) crossovers, and two selection operators, which have relatively high selection pressures. Computational results indicate that the parallel efficiency is significantly affected by the difference of crossovers rather than the selections, and the PGA with CSEX gives better properties.     

A genetic algorithm for cellular manufacturing design and layout

Cellular manufacturing (CM) is an approach that can be used to enhance both flexibility and efficiency in today’s small-to-medium lot production environment. The design of a CM system (CMS) often involves three major decisions: cell formation, group layout, and group schedule. Ideally, these decisions should be addressed simultaneously in order to obtain the best results. However, due to the complexity and NP-complete nature of each decision and the limitations of traditional approaches, most researchers have only addressed these decisions sequentially or independently. In this study, a hierarchical genetic algorithm is developed to simultaneously form manufacturing cells and determine the group layout of a CMS. The intrinsic features of our proposed algorithm include a hierarchical chromosome structure to encode two important cell design decisions, a new selection scheme to dynamically consider two correlated fitness functions, and a group mutation operator to increase the probability of mutation. From the computational analyses, these proposed structure and operators are found to be effective in improving solution quality as well as accelerating convergence.     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.     

Ensuring population diversity in genetic algorithms: A technical note with application to the cell formation problem

The entropy-based measure has been used in previous works to compute the population diversity in solving the cell formation problem with the genetic algorithm. Population diversity is crucial to the genetic algorithm’s ability to continue fruitful exploration as it may be used in choosing an initial population, in defining a stopping criterion, in evaluating the population convergence, and in making the search more efficient throughout the selection of crossover operators or the adjustment of various control parameters (e.g., crossover or mutation rate, population size). We show in this note that, when a non-ordinal chromosome representation corresponding to the allocation of machines to cells is used, the current way of measuring the population diversity is inaccurate. Consequently, it leads to wrong conclusions when, at various iterations, carrying out fruitful exploration or an efficient search of the solution space is guided by the perceived population diversity degree. An alternative approach based on computing the distance and the similarity between chromosomes is discussed.     

Nonlinear system identification and control using a real-coded genetic algorithm

A real-coded genetic algorithm (GA) applied to the system identification and control for a class of nonlinear systems is proposed in this paper. It is well known that GA is a globally optimal method motivated from natural evolutionary concepts. For solving a given optimization problem, there are two different kinds of GA operations: binary coding and real coding. In general, a real-coded GA is more suitable and convenient to deal with most practical engineering applications. In this paper, in the beginning we attempt to utilize a real-coded GA to identify the unknown system which its structure is assumed to be known previously. Next, according to the estimated system model an optimal off-line PID controller is optimally solved by also using the real-coded GA. Two simulated examples are finally given to demonstrate the effectiveness of the proposed method.