A family of genetic algorithms for the pallet loading problem

This paper is concerned with a family of genetic algorithms for the pallet loading problem. Our algorithms differ from previous applications of genetic algorithms to two-dimensional packing problems in that our coding contains all the information needed to produce the packing it represents, rather than relying on a packing algorithm to decode each individual solution. We experiment with traditional one-dimensional string representations, and a two-dimensional matrix representation which preserves the notion of closeness between positions on the pallet. Two new crossover operators are introduced for the two-dimensional case. Our definition of solution space includes both feasible and infeasible solutions and we suggest a number of different fitness functions which penalise infeasibility in different ways and a repair operator which allows our populations to maintain feasibility. The results of experiments designed to test the effectiveness of these features are presented.     

Integrated crossover rules in real coded genetic algorithms

Modifications in crossover rules and localization of searches are suggested to the real coded genetic algorithms for continuous global optimization. Central to our modifications is the integration of different crossover rules within the genetic algorithm. Numerical experiments using a set of 50 test problems indicate that the resulting algorithms are considerably better than the previous version considered and offer a reasonable alternative to many currently available global optimization algorithms, especially for problems requiring ‘direct search type’ methods.     

Compounded genetic algorithms for the quadratic assignment problem

We introduce the compounded genetic algorithm. We propose to run a quick genetic algorithm several times as Phase 1, and compile the best solutions in each run to create a starting population for Phase 2. This new approach was tested on the quadratic assignment problem with very good results.     

A distance based rule for removing population members in genetic algorithms

In this paper we propose a new rule for removal of population members. We tested the new approach for solving the Quadratic Assignment Problem with excellent results.Received: January 2005, AMS classification: 68T20, 90C59     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

Stochastic vendor selection problem: chance-constrained model and genetic algorithms

We study a vendor selection problem in which the buyer allocates an order quantity for an item among a set of suppliers such that the required aggregate quality, service, and lead time requirements are achieved at minimum cost. Some or all of these characteristics can be stochastic and hence, we treat the aggregate quality and service as uncertain. We develop a class of special chance-constrained programming models and a genetic algorithm is designed for the vendor selection problem. The solution procedure is tested on randomly generated problems and our computational experience is reported. The results demonstrate that the suggested approach could provide managers a promising way for studying the stochastic vendor selection problem. The authors would like to thank the referees for providing constructive comments that led to an improved version of the paper. Also, this research was partially supported by grants from National Natural Science Foundation (60776825)—China, 863 Programs (2007AA11Z208)—China, Doctorate Foundation (20040004012)—China, Villanova University Research Sabbatical Fall 2006, and the National Science Foundation (0332490)—USA.     

Automatic clustering using genetic algorithms

In face of the clustering problem, many clustering methods usually require the designer to provide the number of clusters as input. Unfortunately, the designer has no idea, in general, about this information beforehand. In this article, we develop a genetic algorithm based clustering method called automatic genetic clustering for unknown K (AGCUK). In the AGCUK algorithm, noising selection and division-absorption mutation are designed to keep a balance between selection pressure and population diversity. In addition, the Davies-Bouldin index is employed to measure the validity of clusters. Experimental results on artificial and real-life data sets are given to illustrate the effectiveness of the AGCUK algorithm in automatically evolving the number of clusters and providing the clustering partition.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.     

Fuzzy facility location-allocation problem under the Hurwicz criterion

Facility location-allocation (FLA) problem has been widely studied by operational researchers due to its many practical applications. Many researchers have studied the FLA problem in a deterministic environment. However, the models they proposed cannot accommodate satisfactorily various customer demands in the real world. Thus, we consider the FLA problem with uncertainties. In this paper, a new model named α-cost model under the Hurwicz criterion is presented with fuzzy demands. In order to solve this model, the simplex algorithm, fuzzy simulations and a genetic algorithm are integrated to produce a hybrid intelligent algorithm. Finally, some numerical examples are presented to illustrate the effectiveness of the proposed algorithm.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

A general steady state distribution based stopping criteria for finite length genetic algorithms

We propose two general stopping criteria for finite length, simple genetic algorithms based on steady state distributions, and empirically investigate the impact of mutation rate, string length, crossover rate and population size on their convergence. Our first stopping criterion is based on the second largest eigenvalue of the genetic algorithm transition matrix, and the second stopping criterion is based on minorization conditions.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

Competitive genetic algorithms for the open-shop scheduling problem

For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which the best known solution is improved.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

The service allocation problem at the Gioia Tauro Maritime Terminal

The Service Allocation Problem (SAP) is a tactical problem arising in the yard management of a container transshipment terminal. The objective is the minimization of the container rehandling operations inside the yard. This study of the SAP was undertaken for the Gioia Tauro port which is located in Italy and is the main hub terminal for container traffic in the Mediterranean Sea. The SAP can be formulated as a Generalized Quadratic Assignment Problem (GQAP) with side constraints. Two mixed integer linear programming formulations are presented. The first one exploits characteristics of the yard layout at Gioia Tauro where the berth and the corresponding yard positions extend along a line. The second formulation is an adaptation of a linearization for the GQAP. In both cases only small instances can be solved optimally. An evolutionary heuristic was therefore developed. For small size instances the heuristic always yields optimal solutions. For larger sizes it is always better than a truncated branch-and-bound algorithm applied to the exact formulations.     

A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms

Location of fire stations is an important factor in its fire protection capability. This paper aims to determine the optimal location of fire station facilities. The proposed method is the combination of a fuzzy multi-objective programming and a genetic algorithm. The original fuzzy multiple objectives are appropriately converted to a single unified ‘min–max’ goal, which makes it easy to apply a genetic algorithm for the problem solving. Compared with the existing methods of fire station location our approach has three distinguish features: (1) considering fuzzy nature of a decision maker (DM) in the location optimization model; (2) fully considering the demands for the facilities from the areas with various fire risk categories; (3) being more understandable and practical to DM. The case study was based on the data collected from the Derbyshire fire and rescue service and used to illustrate the application of the method for the optimization of fire station locations.     

Using genetic algorithms for the coordinated scheduling problem of a batching machine and two-stage transportation

This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong [1] to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution.     

Some comparisons for damage detection on structures using genetic algorithms and modal sensitivity method

The last decade witnessed the development of a large number of non-destructive tests for structural integrity evaluation. This growth is due to attracted interest to reduce time and costs to perform damage monitoring and predictive maintenance. In this way, several methods intended to detect structural damage based on sensitivity and statistical methods were proposed. However, some of these methods present some practical problems in measuring structural dynamic characteristics such as dynamic mode shapes. Some methods based exclusively on structural responses show disadvantages in finding the damage position on structures.     

A parameter-free self-adapting boundary genetic search for pipe network optimization

Commercial application of genetic algorithms (GAs) to engineering design problems, including optimal design of pipe networks, could be facilitated by the development of algorithms that require the least number of parameter tuning. This paper presents an attempt to eliminate the need for defining a priori the proper penalty parameter in GA search for pipe networks optimal designs. The method is based on the assumption that the optimal solution of a pipe network design problem lies somewhere on, or near, the boundary of the feasible region. The proposed method uses the ratio of the best feasible and infeasible designs at each generation to guide the direction of the search towards the boundary of the feasible domain by automatically adjusting the value of the penalty parameter. The value of the ratio greater than unity is interpreted as the search being performed in the feasible region and vice versa. The new adapted value of the penalty parameter at each generation is therefore calculated as the product of its current value and the aforementioned ratio. The genetic search so constructed is shown to converge to the boundary of the feasible region irrespective of the starting value of the constraint violation penalty parameter. The proposed method is described here in the context of pipe network optimisation problems but is equally applicable to any other constrained optimisation problem. The effectiveness of the method is illustrated with a benchmark pipe network optimization example from the literature.     

Two algorithms for generating and ranking the family of solutions of a finite irreflexive relation

The family of solutions, also known as 1-bases or kernels, of a finite irreflexive relation has a variety of many interesting applications. Furthermore, the decision as towhether the associated digraph posesses a solution belongs to the class of computationally intractable problems known as NP-complete. In this paper we present (a) a tree search algorithm to generate the family of solutions of a digraph and (b) a dynamic programming algorithm to generate the family of solutions ranked in increasing order of their cardinality. Extensive computational experience with the tree search algorithm on more than 1000 randomly generated digraphs ranging from 50 to 150 vertices and from 15% to 60% densities has shown that the proposed algorithm is effective.