Evaluating performance advantages of grouping genetic algorithms

The genetic algorithm (GA) and a related procedure called the grouping genetic algorithm (GGA) are solution methodologies used to search for optimal solutions in constrained optimization problems. While the GA has been successfully applied to a range of problem types, the GGA was created specifically for problems involving the formation of groups. Falkenauer (JORBEL—Belg. J. Oper. Res. Stat. Comput. Sci. 33 (1992) 79), the originator of the GGA, and subsequent researchers have proposed reasons for expecting the GGA to perform more efficiently than the GA on grouping problems. Yet, there has been no research published to date which tests claims of GGA superiority. This paper describes empirical tests of the performance of GA and GGA in three domains which have substantial, practical importance, and which have been the subject of considerable academic research. Our purpose is not to determine which of these two approaches is better across an entire problem domain, but rather to begin to document practical differences between a standard off-the-shelf GA and a tailored GGA. Based on the level of solution quality desired, it may be the case that the additional time and resources required to design a tailored GGA may not be justified if the improvement in solution quality is only minor or non-existent.     

A new evolutionary approach to cutting stock problems with and without contiguity

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems.     

Scheduling of Virtual Cellular Manufacturing Systems: A Biogeography-Based Optimization Algorithm

Virtual cellular manufacturing system (VCMS) is one of the modern strategies in the production facilities layout, which has attracted considerable attention in recent years. In this system, machines are located in different positions on the shop floor and virtual cells are a logical grouping of machines, jobs, and workers from the viewpoint of the production control system. These features not only enhance the system’s agility but also allow a dynamic reassignment of cells as demand changes. This paper addresses the VCMS scheduling problems where the jobs have different orders on machines and the objective is to simultaneously minimize the weighted sum of the makespan and total traveling distance in order to create a balance between criteria. The research methodology firstly consists of a mathematical programming model with regard to the production constraints in order to describe the characteristics of the VCMS. Secondly, a basic genetic algorithm (GA), a biogeography-based optimization (BBO) algorithm, an algorithm based on hybridization of BBO and GA, and the BBO algorithm accompanied by restart phase are developed to solve the VCMS scheduling problems. The developed algorithms have been compared to each other and their performance are evaluated in terms of their best solution and computational time as effectiveness and efficiency criteria, respectively. Consequently, the performance of the best algorithm has been evaluated by the state-of-the-art algorithm, GA, in the literature. The results show that the best algorithm based on BBO could find solutions at least as good as the last famous algorithm, GA, in the literature.     

A review of genetic algorithms applied to training radial basis function networks

The problems associated with training feedforward artificial neural networks (ANNs) such as the multilayer perceptron (MLP) network and radial basis function (RBF) network have been well documented. The solutions to these problems have inspired a considerable amount of research, one particular area being the application of evolutionary search algorithms such as the genetic algorithm (GA). To date, the vast majority of GA solutions have been aimed at the MLP network. This paper begins with a brief overview of feedforward ANNs and GAs followed by a review of the current state of research in applying evolutionary techniques to training RBF networks.     

Comparison of visualization of optimal clustering using self-organizing map and growing hierarchical self-organizing map in cellular manufacturing system

The present research deals with the cell formation problem (CFP) of cellular manufacturing system which is a NP-hard problem thus, the development of optimum machine-part cell formation algorithms has always been the primary attraction in the design of cellular manufacturing system. In this proposed work, the self-organizing map (SOM) approach has been used which is able to project data from a high-dimensional space to a low-dimensional space so it is considered a visualized approach for explaining a complicated CFP data set. However, for a large data set with a high dimensionality, a traditional flat SOM seems difficult to further explain the concepts inside the clusters. We propose one such possible solution for a large CFP data set by using the SOM in a hierarchical manner known as growing hierarchical self-organizing map (GHSOM). In the present work, the two novel contributions using GHSOM are: the choice of optimum architecture through the minimum pattern units extracted at layer 1 for the respective threshold values and selection. Furthermore, the experimental results clearly indicated that the machine-part visual clustering using GHSOM can be successfully applied in identifying a cohesive set of part family that is processed by a machine group. Computational experience specifically with the proposed GHSOM algorithm, on a set of 15 CFP problems from the literature, has shown that it performs remarkably well. The GHSOM algorithm obtained solutions that are at least as good as the ones found the literature. For 75% of the cell formation problems, the GHSOM algorithm improved the goodness of cell formation through GTE performance measure using SOM as well as best one from the literature, in some cases by as much as more than 12.81% (GTE). Thus, comparing the results of the experiment in this paper with the SOM and GHSOM using the paired t-test it has been revealed that the GHSOM approach performed better than the SOM approach so far the group technology efficiency (GTE) measures of performance of the goodness of cell formation is concerned.     

A case study of scheduling storage tanks using a hybrid geneticalgorithm

This paper proposes the application of a hybrid genetic algorithm (GA) for scheduling storage tanks. The proposed approach integrates GAs and heuristic rule-based techniques, decomposing the complex mixed-integer optimization problem into integer and real-number subproblems. The GA string considers the integer problem and the heuristic approach solves the real-number problems within the GA framework. The algorithm is demonstrated for three test scenarios of a water treatment facility at a port and has been found to be robust and to give a significantly better schedule than those generated using a random search and a heuristic-based approach     

Multi-operator based evolutionary algorithms for solving constrained optimization problems

Over the last two decades, many sophisticated evolutionary algorithms have been introduced for solving constrained optimization problems. Due to the variability of characteristics in different COPs, no single algorithm performs consistently over a range of problems. In this paper, for a better coverage of the problem characteristics, we introduce an algorithm framework that uses multiple search operators in each generation. The appropriate mix of the search operators, for any given problem, is determined adaptively. The framework is tested by implementing two different algorithms. The performance of the algorithms is judged by solving 60 test instances taken from two constrained optimization benchmark sets from specialized literature. The first algorithm, which is a multi-operator based genetic algorithm (GA), shows a significant improvement over different versions of GA (each with a single one of these operators). The second algorithm, using differential evolution (DE), also confirms the benefit of the multi-operator algorithm by providing better and consistent solutions. The overall results demonstrated that both GA and DE based algorithms show competitive, if not better, performance as compared to the state of the art algorithms.     

MRCD: a genetic algorithm for multiobjective robust control design

A genetic algorithm (GA) for the class of multiobjective optimization problems that appears in the design of robust controllers is presented in this paper. The design of a robust controller is a trade-off problem among competitive objectives such as disturbance rejection, reference tracking, stability against unmodeled dynamics, moderate control effort and so on. However, general methodologies for solving this class of design problems are not easily encountered in the literature because of the complexity of the resultant multiobjective problems. In this paper, a recently developed class of GAs, multiobjective GAs, are used to solve robust control design problems. Here, a new algorithm, called multiobjective robust control design, has been proposed. The structure and operators of this algorithm have been specifically developed for control design problems. The performace of the algorithm is evaluated by solving several test cases and is also compared to the standard algorithms used for the multiobjective design of robust controllers.     

An Electromagnetism-like algorithm for cell formation and layout problem

Implementation of cellular manufacturing systems (CMS) is thriving among manufacturing companies due to many advantages that are attained by applying this system. In this study CMS formation and layout problems are considered. An Electromagnetism like (EM-like) algorithm is developed to solve the mentioned problems. In addition the required modifications to make EM-like algorithm applicable in these problems are mentioned. A heuristic approach is developed as a local search method to improve the quality of solution of EM-like. Beside in order to examine its performance, it is compared with two other methods. The performance of EM-like algorithm with proposed heuristic and GA are compared and it is demonstrated that implementing EM-like algorithm in this problem can improve the results significantly in comparison with GA. In addition some statistical tests are conducted to find the best performance of EM-like algorithm and GA due to their parameters. The convergence diagrams are plotted for two problems to compare the convergence process of the algorithms. For small size problems the performances of the algorithms are compared with an exact algorithm (Branch & Bound).     

No-wait two stage hybrid flow shop scheduling with genetic and adaptive imperialist competitive algorithms

This article studies a no-wait two-stage flexible flow shop scheduling problem with setup times aiming to minimize the total completion time. The problem is solved using an adaptive imperialist competitive algorithm (AICA) and genetic algorithm (GA). To test the performance of the proposed AICA and GA, the algorithms are compared with ant colony optimisation, known as an effective algorithm in the literature. The performance of the algorithms are evaluated by solving both small and large-scale problems. Their performance is evaluated in terms of relative percentage deviation. Finally the results of the study are discussed and conclusions and potential areas for further study are highlighted.     

Designing heterogeneous distributed GAs by efficiently self-adapting the migration period

This paper investigates a new heterogeneous method that dynamically sets the migration period of a distributed Genetic Algorithm (dGA). Each island GA of this multipopulation technique self-adapts the period for exchanging information with the other islands regarding the local evolution process. Thus, the different islands can develop different migration settings behaving like a heterogeneous dGA. The proposed algorithm is tested on a large set of instances of the Max-Cut problem, and it can be easily applied to other optimization problems. The results of this heterogeneous dGA are competitive with the best existing algorithms, with the added advantage of avoiding time-consuming preliminary tests for tuning the algorithm.     

Immune network simulations in multicriterion design

A modification to the genetic algorithm (GA) based search procedure, based on the modeling of a biological immune system, is proposed as an approach to solving the multicriterion design problem. Such problems have received considerable attention, given that decisions in engineering design practice typically require allocation of resources to satisfy multiple, and frequently conflicting requirements. The approach is particularly amenable to problems with a mix of continuous, discrete, and integer design variables, where the GA has been shown to perform in an effective manner. The approach considered in the present work is based on the concept of converting the multicriterion problem into one with a scalar objective through the use of the utility function. The strength of the approach is in its ability to generate the Pareto-Edgeworth front of compromise solutions in a single execution of the GA. A characteristic feature of biological immune systems which allows for the generation of multiple specialist antibodies, is shown to be an effective approach to facilitate the generation of the Pareto-Edgeworth front. Solutions to problems in structural design are presented in support of the proposed approach.     

AGFS: Adaptive Genetic Fuzzy System for medical data classification

A Genetic Fuzzy System (GFS) is basically a fuzzy system augmented by a learning process based on a genetic algorithm (GA). Fuzzy systems have demonstrated their ability to solve different kinds of problems in various application domains. Currently, there is an increasing interest to augment fuzzy systems with learning and adaptation capabilities. Two of the most successful approaches to hybridize fuzzy systems with learning and adaptation methods have been made in the realm of soft computing. The GA can be merged with Fuzzy system for different purposes like rule selection, membership function optimization, rule generation, co-efficient optimization, for data classification. Here we propose an Adaptive Genetic Fuzzy System (AGFS) for optimizing rules and membership functions for medical data classification process. The primary intension of the research is 1) Generating rules from data as well as for the optimized rules selection, adapting of genetic algorithm is done and to explain the exploration problem in genetic algorithm, introduction of new operator, called systematic addition is done, 2) Proposing a simple technique for scheming of membership function and Discretization, and 3) Designing a fitness function by allowing the frequency of occurrence of the rules in the training data. Finally, to establish the efficiency of the proposed classifier the presentation of the anticipated genetic-fuzzy classifier is evaluated with quantitative, qualitative and comparative analysis. From the outcome, AGFS obtained better accuracy when compared to the existing systems.     

A genetic algorithm for the optimisation of assembly sequences

This paper describes a Genetic Algorithm (GA) designed to optimise the Assembly Sequence Planning Problem (ASPP), an extremely diverse, large scale and highly constrained combinatorial problem. The modelling of the ASPP problem, which has to be able to encode any industrial-size product with realistic constraints, and the GA have been designed to accommodate any type of assembly plan and component. A number of specific modelling issues necessary for understanding the manner in which the algorithm works and how it relates to real-life problems, are succinctly presented, as they have to be taken into account/adapted/solved prior to Solving and Optimising (S/O) the problem. The GA has a classical structure but modified genetic operators, to avoid the combinatorial explosion. It works only with feasible assembly sequences and has the ability to search the entire solution space of full-scale, unabridged problems of industrial size. A case study illustrates the application of the proposed GA for a 25-components product.     

Evolutionary based hybrid GA for solving multi-objective grid scheduling problem

The grid computing aims at bringing computing capacities together in a manner that can be used to find solutions for complicated problems of science. Conventional algorithms like first come first serve (FCFS), shortest job first (SJF) has been used for solving grid scheduling problem (GSP), but the increased complexity and job size led to the poor performance of these algorithms especially in the grid environment due to its dynamic nature. Previously, researchers have used a genetic algorithm (GA) to schedule jobs in the grid environment. In this paper, a multi-objective GSP is solved and optimized using the proposed algorithm. The proposed algorithm enhances the way the genetic algorithm performs and incorporate significant changes in the initialization step of the algorithm. The proposed algorithm uses SJF during its initialization step for producing the initial population solution. The proposed GA has three key features which are discussed in this paper: It executes jobs with minimum job completion time. It performs load balancing and improves resource utilization. Lastly, it supports scalability. The proposed algorithm is tested using a standard workload (given by Czech National Grid Infrastructure named Metacentrum) which can be a benchmark for further research. A performance comparison shows that the proposed algorithm has got better scheduling results than other scheduling algorithms.

     

A fuzzy self-tuning parallel genetic algorithm for optimization

The genetic algorithm (GA) is now a very popular tool for solving optimization problems. Each operator has its special approach route to a solution. For example, a GA using crossover as its major operator arrives at solutions depending on its initial conditions. In other words, a GA with multiple operators should be more robust in global search. However, a multiple operator GA needs a large population size thus taking a huge time for evaluation. We therefore apply fuzzy reasoning to give effective operators more opportunity to search while keeping the overall population size constant. We propose a fuzzy self-tuning parallel genetic algorithm (FPGA) for optimization problems. In our test case FPGA there are four operators—crossover, mutation, sub-exchange, and sub-copy. These operators are modified using the eugenic concept under the assumption that the individuals with higher fitness values have a higher probability of breeding new better individuals. All operators are executed in each generation through parallel processing, but the populations of these operators are decided by fuzzy reasoning. The fuzzy reasoning senses the contributions of these operators, and then decides their population sizes. The contribution of each operator is defined as an accumulative increment of fitness value due to each operator's success in searching. We make the assumption that the operators that give higher contribution are more suitable for the typical optimization problem. The fuzzy reasoning is built under this concept and adjusts the population sizes in each generation. As a test case, a FPGA is applied to the optimization of the fuzzy rule set for a model reference adaptive control system. The simulation results show that the FPGA is better at finding optimal solutions than a traditional GA.     

Constrained combinatorial optimization of multi-layered composite structures by means of Stud GA with proportionate selection and extinction

In this paper a revised algorithm, derived by the Stud GA, to optimize the stacking sequence of layered composite structures is presented. The constrained combinatorial problem is formulated and hence solved by means of the algorithm presented herein. Unlike the Stud GA, the proposed algorithm uses a fitness-proportionate selection to find potential mates to the Stud and a self-adaptive extinction to avoid premature convergence. Elitism is also allowed. Standard benchmark problems have been used to fully assess the validity of the proposed algorithm. Results in terms of reliability and efficiency are compared against three GAs and a Permutation Search (PS) algorithm. It has been demonstrated, by means of a parametric study, that a low probability of extinction is sufficient to ensure fast convergence as well as reliable results. Finally the optimization of a more complex aeronautic structure is addressed aiming to prove the validity of the proposed algorithm in a two level optimization strategy. Results in terms of efficiency are compared against those of an in-house standard GA.     

Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness

This paper studies the flowshop scheduling problem with a complex bicriteria objective function. A weighted sum of makespan and maximum tardiness subject to a maximum tardiness threshold value is to be optimized. This problem, with interesting potential applications in practice, has been sparsely studied in the literature. We propose global and local dominance relationships for the three-machine problem and a fast and effective genetic algorithm (GA) for the more general m$m$-machine case. The proposed GA incorporates a novel three-phase fitness assignment mechanism specially targeted at dealing with populations in which both feasible as well as infeasible solutions might coexist. Comprehensive computational and statistical experiments show that the proposed GA outperforms the two most effective existing heuristics by a considerable margin in all scenarios. Furthermore, the proposed GA is also faster and able to find more feasible solutions. It should be noted that when the weight assigned to maximum tardiness is zero, then the problem is reduced to minimizing makespan subject to a maximum tardiness threshold value. Heuristics for both problems have been provided in the literature recently but they have not been compared. Another contribution of this paper is to compare these recent heuristics with each other.     

An effective evolutionary algorithm for the practical capacitated vehicle routing problems

The evolutionary algorithms are extensively adopted to resolve complex optimization problem. Genetic algorithm (GA), an evolutionary algorithm, has been proved capable of solving vehicle routing problems (VRPs). However, the resolution effectiveness of GA decreases with the increase of nodes within VRPs. Normally, a hybrid GA outperforms pure GA. This study attempts to solve a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) that is practical for use by manufacturers. The proposed HGA involves three stages. First, a diverse and well-structured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristics containing improved insertion algorithm and random insertion mutation operator was established to stir over gene permutations and enhance the exploration capability of GA diversely. Furthermore, an elitism conservation strategy was implemented that replace inferior chromosomes with superior ones. As the proposed HGA is primarily used to solve practical problems, benchmark problems involving fewer than 100 nodes from an Internet website were utilized to confirm the feasibility of the proposed HGA. Two real cases one for locally active distribution and another for arms part transportation at a combined maintenance facility, both involving the Taiwanese armed forces are used to detail the analytical process and demonstrate the practicability of the proposed HGA for optimizing the CVRP.     

A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem

In this paper, a novel competitive co-evolutionary quantum genetic algorithm (CCQGA) is proposed for a stochastic job shop scheduling problem (SJSSP) with the objective to minimize the expected value of makespan. Three new strategies named as competitive hunter, cooperative surviving and the big fish eating small fish are developed in population growth process. Based on improved co-evolution idea of multi-population and concepts of quantum theory, this algorithm could not only adjust population size dynamically to increase the diversity of genes and avoid premature convergence, but also accelerate the convergence speed with Q-bit representation and quantum rotation gate. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by CCQGA. The experiment results achieved by CCQGA are compared with quantum-inspired genetic algorithm (QGA) and standard genetic algorithm (GA), which shows that CCQGA has better feasibility and effectiveness.