Hybrid genetic algorithms for bin-packing and related problems

The genetic algorithm (GA) paradigm has attracted considerable attention as a promising heuristic approach for solving optimization problems. Much of the development has related to problems of optimizing functions of continuous variables, but recently there have been several applications to problems of a combinatorial nature. What is often found is that GAs have fairly poor performance for combinatorial problems if implemented in a naive way, and most reported work has involved somewhat ad hoc adjustments to the basic method. In this paper, we will describe a general approach which promises good performance for a fairly extensive class of problems by hybridizing the GA with existing simple heuristics. The procedure will be illustrated mainly in relation to the problem ofbin-packing, but it could be extended to other problems such asgraph partitioning, parallel-machine scheduling andgeneralized assignment. The method is further extended by usingproblem size reduction hybrids. Some results of numerical experiments will be presented which attempt to identify those circumstances in which these heuristics will perform well relative to exact methods. Finally, we discuss some general issues involving hybridization: in particular, we raise the possibility of blending GAs with orthodox mathematical programming procedures.     

Fitting the control parameters of a genetic algorithm: An application to technical trading systems design

This paper studies the problem of how changes in the design of the genetic algorithm (GA) have an effect on the results obtained in real-life applications. In this study, focused on the application of a GA to the tuning of technical trading rules in the context of financial markets, our tentative thesis is that the GA is robust with respect to design changes. The optimization of technical trading systems is a suitable area for the application of the GA metaheuristic, as the complexity of the problem grows exponentially as new technical rules are added to the system and as the answer time is crucial when applying the system to real-time data. Up to now, most of GAs applications to this subject obviated the question of possible “design dependence” in their results. The data we report, based on our experiments, do not allow us to refute the hypothesis of robustness of the GA to design implementation, when applying to technical trading systems tuning.     

Nature inspired genetic algorithms for hard packing problems

This paper presents two novel genetic algorithms (GAs) for hard industrially relevant packing problems. The design of both algorithms is inspired by aspects of molecular genetics, in particular, the modular exon-intron structure of eukaryotic genes. Two representative packing problems are used to test the utility of the proposed approach: the bin packing problem (BPP) and the multiple knapsack problem (MKP). The algorithm for the BPP, the exon shuffling GA (ESGA), is a steady-state GA with a sophisticated crossover operator that makes maximum use of the principle of natural selection to evolve feasible solutions with no explicit verification of constraint violations. The second algorithm, the Exonic GA (ExGA), implements an RNA inspired adaptive repair function necessary for the highly constrained MKP. Three different variants of this algorithm are presented and compared, which evolve a partial ordering of items using a segmented encoding that is utilised in the repair of infeasible solutions. All algorithms are tested on a range of benchmark problems, and the results indicate a very high degree of accuracy and reliability compared to other approaches in the literature.     

The use of genetic algorithms to solve the economic lot size scheduling problem

The purpose of this paper is to investigate the use genetic algorithms (GAs) for solving the Economic Lot Size Scheduling Problem (ELSP). The ELSP is formulated using the Basic Period (BP) approach which results in a problem having one continuous decision variable and a number of integer decision variables equal to the number of products being produced. This formulation is ideally suited for using GAs. The GA is tested on Bomberger's classical problem. The resulting solutions were better than those obtained using an iterative dynamic programming (DP) approach. The total cost of GA solutions to the problem with utilization up to 65% were within 3.4% of the lower bound. The GA also performed well for higher utilization yielding solutions within 13.87% of the lower bound for utilization up to 86%. The GA was tested on a 30-item problem and good solutions were obtained. The results of the GA under different binary representations, crossover methods, and initialization methods are compared to identify the best settings. The results indicate that for this particular problem, binary representation works better than Gray coding, 2-point crossover is best, and an infeasible starting population is better than feasible.     

Progressive genetic algorithm for solution of optimization problems with nonlinear equality and inequality constraints

A new approach, identified as progressive genetic algorithm (PGA), is proposed for the solutions of optimization problems with nonlinear equality and inequality constraints. Based on genetic algorithms (GAs) and iteration method, PGA divides the optimization process into two steps; iteration and search steps. In the iteration step, the constraints of the original problem are linearized using truncated Taylor series expansion, yielding an approximate problem with linearized constraints. In the search step, GA is applied to the problem with linearized constraints for the local optimal solution. The final solution is obtained from a progressive iterative process. Application of the proposed method to two simple examples is given to demonstrate the algorithm.     

Learning genetic algorithm parameters using hidden Markov models

Genetic algorithms (GAs) are routinely used to search problem spaces of interest. A lesser known but growing group of applications of GAs is the modeling of so-called “evolutionary processes”, for example, organizational learning and group decision-making. Given such an application, we show it is possible to compute the likely GA parameter settings given observed populations of such an evolutionary process. We examine the parameter estimation process using estimation procedures for learning hidden Markov models, with mathematical models that exactly capture expected GA behavior. We then explore the sampling distributions relevant to this estimation problem using an experimental approach.     

A genetic algorithm approach to the product line design problem using the seller's return criterion: An extensive comparative computational study

In this paper we deal with the product line design problem employing the seller's marginal return criterion. Because this problem is NP-Hard, many researchers proposed heuristic methods. We present a genetic algorithm (GA) based heuristic for solving the above problem. In the implementation, the GA is initialized in two different ways. In the first way, the GA is initialized with a random population. We call this algorithm GA1. In the second way, the solution of the beam search (BS) method is included in the first population of the GA. We call this algorithm GA2. We compare GA1, a recently developed BS method and GA2 on randomly generated problems. GA1 seems to be substantially better than the BS method in terms of CPU time. Also, the solutions found by GA1 are substantially better than those found by the BS method in comparable times. In many cases, GA2 improves the solution found by the BS method. Consequently, it is a good second step of the BS method.     

Military antenna design using simple and competent genetic algorithms

Over the past decade, the Air Force Research Laboratory (AFRL) Antenna Technology Branch at Hanscom AFB has employed the simple genetic algorithm (SGA) as an optimization tool for a wide variety of antenna applications. Over roughly the same period, researchers at the Illinois Genetic Algorithm Laboratory (IlliGAL) at the University of Illinois at Urbana Champaign have developed GA design theory and advanced GA techniques called competent genetic algorithms—GAs that solve hard problems quickly, reliably, and accurately. Recently, under the guidance and direction of the Air Force Office of Scientific Research (AFOSR), the two laboratories have formed a collaboration, the common goal of which is to apply simple, competent, and hybrid GA techniques to challenging antenna problems.This paper is composed of two parts. The first part of this paper summarizes previous research conducted by AFRL at Hanscom for which SGAs were implemented to obtain acceptable solutions to several antenna problems. This research covers diverse areas of interest, including array pattern synthesis, antenna test-bed design, gain enhancement, electrically small single bent wire elements, and wideband antenna elements.The second part of this paper starts by briefly reviewing the design theory and design principles necessary for the invention and implementation of fast, scalable genetic algorithms. A particular procedure, the hierarchical Bayesian optimization algorithm (hBOA) is then briefly outlined, and the remainder of the paper describes collaborative efforts of AFRL and IlliGAL to solve more difficult antenna problems. In particular, recent results of using hBOA to optimize a novel, wideband overlapped subarray system to achieve −35 dB sidelobes over a 20% bandwidth. The problem was sufficiently difficult that acceptable solutions were not obtained using SGAs. The case study demonstrates the utility of using more advanced GA techniques to obtain acceptable solution quality as problem difficulty increases.     

Maintenance scheduling of rolling stock using a genetic algorithm

We have developed a Genetic algorithm (GA) for the optimisation of maintenance overhaul scheduling of rolling stock (trains) at the Hong Kong Mass Transit Railway Corporation (MTRC). The problem is one of combinatorial optimisation. Genetic algorithms (GAs) belong to the class of heuristic optimisation techniques that utilise randomisation as well as directed smart search to seek the global optima. The workshop at MTRC does have difficulties in establishing good schedules for the overhaul maintenance of the rolling stock. Currently, an experienced scheduler at MTRC performs this task manually. In this paper, we study the problem in a scientific manner and propose ways in which the task can be automated with the help of an algorithm embedded in a computer program. The algorithm enables the scheduler to establish the annual maintenance schedule of the trains in an efficient manner; the objective being to satisfy the maintenance requirements of various units of the trains as closely as possible to their due dates since there is a cost associated with undertaking the maintenance tasks either `too early’ or ‘too late’. The genetic algorithm developed is found to be very effective for solving this intractable problem. Computational results indicate that the genetic algorithm consistently provides significantly better schedules than those established manually at MTRC. More over, we provide evidence that the algorithm delivers close to optimal solutions for randomly generated problems with known optimal solutions. We also propose a local search method to reconfigure the trains in order to improve the schedule and to balance the work load of the overhaul maintenance section of the workshop throughout the planning horizon. We demonstrate that the reconfiguration of trains improves the schedule and reduces cost significantly.     

The Container Transshipment Problem: Searching Representation Landscapes with Metaheuristic Algorithms

The container transshipment problem involves scheduling a fleet of lorries to collect and deliver containers of various sizes while minimizing the total distance travelled. The problem originates in the need for logistics companies to solve the problem on a regular basis as part of their daily operations. In this paper, we compare two genetic algorithms tailored to solve this problem based on permutation and bin-packing inspired encodings. Results are presented and analysed in order to evaluate the validity and robustness of the two approaches. As part of the analysis, bounds were calculated to determine how well both GAs perform in absolute terms as well as relative to each other. Of the two GA there is one clear winner, although it is not the one that would have been indicated by previous research. Whilst the winning GA is able to generate significant savings in practice, compared to the optimum there remains room for further improvement.     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

A biased random key genetic algorithm applied to the electric distribution network reconfiguration problem

This work presents a biased random-key genetic algorithm (BRKGA) to solve the electric distribution network reconfiguration problem (DNR). The DNR is one of the most studied combinatorial optimization problems in power system analysis. Given a set of switches of an electric network that can be opened or closed, the objective is to select the best configuration of the switches to optimize a given network objective while at the same time satisfying a set of operational constraints. The good performance of BRKGAs on many combinatorial optimization problems and the fact that it has never been applied to solve DNR problems are the main motivation for this research. A BRKGA is a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. Solutions are encoded by using random keys, which are represented as vectors of real numbers in the interval (0,1), thus enabling an indirect search of the solution inside a proprietary search space. The genetic operators do not need to be modified to generate only feasible solutions, which is an exclusive task of the decoder of the problem. Tests were performed on standard distribution systems used in DNR studies found in the technical literature and the performance and robustness of the BRKGA were compared with other GA implementations.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

OMEGA one multi ethnic genetic approach

The genetic algorithm (GA) is a quite efficient paradigm to solve several optimization problems. It is substantially a search technique that uses an ever-changing neighborhood structure related to a population which evolves according to a number of genetic operators. In the GA framework many techniques have been devised to escape from a local optimum when the algorithm fails in locating the global one. To this aim we present a variant of the GA which we call OMEGA (One Multi Ethnic Genetic Approach). The main difference is that, starting from an initial population, \(k\) different sub-populations are produced at each iteration and they independently evolve in \(k\) different environments. The resulting sub–populations are then recombined and the process is iterated. Our basic algorithmic scheme is tested on a recent and well-studied variant of the classic problem of the minimum spanning tree: the Minimum Labeling Spanning Tree problem. We compare our algorithm with several approaches drawn from the literature. The results are encouraging in view of future application of OMEGA to other classes of problems.     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

Worst-Case Tolerance Design and Quality Assurance via Genetic Algorithms

In many engineering designs, several components are often placed together in a mechanical assembly. Due to manufacturing variations, there is a tolerance associated with the nominal dimension of each component in the assembly. The goal of worst-case tolerance analysis is to determine the effect of the smallest and largest assembly dimensions on the product performance. Furthermore, to achieve product quality and robustness, designers must ensure that the product performance variation is minimal.Recently, genetic algorithms (GAs) have gained a great deal of attention in the field of tolerance design. The main strength of GAs lies in their ability to effectively perform directed random search in a large space of design solutions and produce optimum results. However, simultaneous treatment of tolerance analysis and robust design for quality assurance via genetic algorithms has been marginal.In this paper, we introduce a new method based on GAs, which addresses both the worst-case tolerance analysis of mechanical assemblies and robust design. A novel formulation based on manufacturing capability indices allows the GA to rank candidate designs based on varying the tolerances around the nominal design parameter values. Standard genetic operators are then applied to ensure that the product performance measure exhibits minimal variation from the desired target value. The computational results in the design of a clutch assembly highlight the advantages of the proposed methodology.     

Evaluating Kohonen’s learning rule: An approach through genetic algorithms

This paper examines the technical foundations of the self-organising map (SOM). It compares Kohonen’s heuristic-based training algorithm with direct optimisation of a locally-weighted distortion index, also used by Kohonen. Direct optimisation is achieved through a genetic algorithm (GA). Although GAs have been used before with the SOM, this has not been done in conjunction with the distortion index. Comparing heuristic-based training and direct optimisation for the SOM is analogous to comparing the Backpropagation algorithm for feedforward networks with direct optimisation of RMS error. Our experiments reveal lower values of the distortion index with direct optimisation. As to whether the heuristic-based algorithm is able to provide an approximation to gradient descent, our results suggest the answer should be in the negative. Theorems for one-dimensional and for square maps indicate that different point densities will emerge for the two training approaches. Our findings are in accordance with these results.     

Selecting survivors in genetic algorithm using tabu search strategies

Genetic algorithm (GA) is well-known for its effectiveness in global search and optimization. To balance selection pressure and population diversity is an important issue of designing GA. This paper proposes a novel hybridization of GA and tabu search (TS) to address this issue. The proposed method embeds the key elements of TS—tabu restriction and aspiration criterion—into the survival selection operator of GA. More specifically, the tabu restriction is used to prevent inbreeding for diversity maintenance, and the aspiration criterion is activated to provide moderate selection pressure under the tabu restriction. The interaction of tabu restriction and aspiration criterion enables survivor selection to balance selection pressure and population diversity. The experimental results on numerical and combinatorial optimization problems show that this hybridization can significantly improve GAs in terms of solution quality as well as convergence speed. An empirical analysis further identifies the influences of the TS strategies on the performance of this hybrid GA.     

Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study

The potential of Genetic Algorithmic (GA) approaches for solving order-based problems including the Traveling Salesman Problem (TSP) is recognized in a number of recent studies. By applying various GAs, these studies developed a set of unresolved GA design and configuration issues. The purpose of this study is to resolve the conflicting GA design and configuration issues by (1) concentrating on the classical TSP; and (2) developing, implementing, and testing a complete set of alternative GA configurations, 144 GAs are developed and evaluated by solvinh 5000 TSPs. A carefully designed statistical experimental plan accompanied by rigorous statistical analysis isolate the most promising configurations and identify their effect on solution time and quality. Although, the emphasis is on the TSP, the final results are applicable to other order-based problems that use sequence encoding.