A genetic algorithm solution for one-dimensional bundled stock cutting

This paper discusses a one-dimensional cutting stock problem in which lumber is cut in bundles. The nature of this problem is such that the traditional approaches of linear programming with an integer round-up procedure or sequential heuristics are not effective. A good solution to this problem must consider trim loss, stock usage and ending inventory levels. A genetic search algorithm is proposed and results compared to optimal solutions for an integer programming formulation of the problem.     

Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution

Hub and spoke networks are used to switch and transfer commodities between terminal nodes in distribution systems at minimum cost and/or time. The p-hub center allocation problem is to minimize maximum travel time in networks by locating p hubs from a set of candidate hub locations and allocating demand and supply nodes to hubs. The capacities of the hubs are given. In previous studies, authors usually considered only quantitative parameters such as cost and time to find the optimum location. But it seems not to be sufficient and often the critical role of qualitative parameters like quality of service, zone traffic, environmental issues, capability for development in the future and etc. that are critical for decision makers (DMs), have not been incorporated into models. In many real world situations qualitative parameters are as much important as quantitative ones. We present a hybrid approach to the p-hub center problem in which the location of hub facilities is determined by both parameters simultaneously. Dealing with qualitative and uncertain data, Fuzzy systems are used to cope with these conditions and they are used as the basis of this work. We use fuzzy VIKOR to model a hybrid solution to the hub location problem. Results are used by a genetic algorithm solution to successfully solve a number of problem instances. Furthermore, this method can be used to take into account more desired quantitative variables other than cost and time, like future market and potential customers easily.     

GA-Ensemble: a genetic algorithm for robust ensembles

Many simple and complex methods have been developed to solve the classification problem. Boosting is one of the best known techniques for improving the accuracy of classifiers. However, boosting is prone to overfitting with noisy data and the final model is difficult to interpret. Some boosting methods, including AdaBoost, are also very sensitive to outliers. In this article we propose a new method, GA-Ensemble, which directly solves for the set of weak classifiers and their associated weights using a genetic algorithm. The genetic algorithm utilizes a new penalized fitness function that limits the number of weak classifiers and controls the effects of outliers by maximizing an appropriately chosen $p$ th percentile of margins. We compare the test set error rates of GA-Ensemble, AdaBoost, and GentleBoost (an outlier-resistant version of AdaBoost) using several artificial data sets and real-world data sets from the UC-Irvine Machine Learning Repository. GA-Ensemble is found to be more resistant to outliers and results in simpler predictive models than AdaBoost and GentleBoost.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

Polyominoes tiling by a genetic algorithm

Most existing placement algorithms were designed to handle blocks that are rectangular in shape. In this paper, we show how a genetic algorithm (GA) is used to construct an optimal arrangement of two-dimensional rectilinear blocks. Our approach does not require the orientation of each block to be fixed. To transform the placement problem to a GA problem, we devised a decoding technique known as circular placement. The novelty of the circular placement technique is that it configures the rectilinear blocks by building up potentially good groupings of blocks starting from the corners of the placement area. To complement the circular placement approach, we present a methodology for deriving a suitable objective function. We confirm the performance of our GA-based placement algorithm by presenting simulation results of some problems on tiling with up to 128 polyominoes. The algorithm described in this paper has great potential for applications in packing, compacting and general component placement in the various disciplines of engineering.     

Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.     

Linearized solution of a flow over a nonuniform bottom

A linearized theory is presented for determining the shape of the free surface of a running stream which is disturbed by some irregularities lying on the bottom. The bottom is represented in integral form using Fourier's double-integral theorem. Then following Lamb [3], a linear free-surface profile is obtained for the supercritical and subcritical cases.The results are plotted for the two cases of the flow for different shapes of the bottom, and different values of the Froude number. The effect of the Froude number, the bottom height and the shape of the bottom are discussed.     

Affinity genetic algorithm

Based on some phenomena from human society and nature, we propose a binary affinity genetic algorithm (aGA) by adopting the following strategies: the population is adaptively updated to avoid stagnation; the newly generated individuals will be ensured to survive for some generations in order for them to have time to show their good genes; new individuals and the old ones are balanced to have the advantages of both. In order to quantitatively analyze the selective pressure, the concept of selection degree and a simple linear control equation are introduced. We can maintain the diversity of the evolutionary population by controlling the value of the selection degree. Performance of aGA is further enhanced by incorporating local search strategies. Partially supported by a National Key Basic Research Project of China and by a USA NSF grant CCR-0201253.     

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.     

Induction over constrained strategic agents

In a new learning paradigm called Induction over Strategic Agents, the principal anticipates possible alteration of attributes by agents wishing to achieve a positive classification. In many cases, agents are constrained on how an attribute can be modified. For example, attribute values may have upper and lower bounds or they may need to belong to a certain set of possible values such as binary valued attributes like “pays bills on time” or be linearly dependent like the relationships between accounting entries in an income statement. In this paper, we explore Induction over Strategic Agents for a class of problems where attributes are binary values.     

MHD flow of a Newtonian fluid over a stretching sheet: an approximate solution

An approximate solution to the problem of steady laminar flow of a viscous incompressible electrically conducting fluid over a stretching sheet is presented. The approach is based on the idea of stretching the variables of the flow problem and then using least squares method to minimize the residual of a differential equation. The effects of the magnetic field on the flow characteristics are demonstrated through numerical computations with different values of the Hartman number.     

A curve-fitting genetic algorithm for a styling application

Fitting curves in computer-aided geometric design is generally regarded as an optimisation problem. Depending on the application, the conditions to be satisfied can make the problem difficult to solve using classic methods, and for this reason, stochastic methods, such as genetic algorithms appear to be appropriate. This article considers a curve fitting problem, with the objective of generating shapes with specific curvature variations for use in the design of car bodies. To this end, a particular curve model was developed and implemented within a genetic algorithm. The main characteristics of this algorithm are described and its promising results are presented. The conclusion will show that this technique can be used as an alternative method in the design of car bodies.     

Finding groups with a simple genetic algorithm*

A new solution to the old problem of partitioning a matrix of social proximities into groups is proposed. It draws on a heuristic developed in computer science, the simple genetic algorithm. The algorithm is described and its utility is demonstrated with applications to three standard data sets.     

Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach

This paper considers multiprocessor task scheduling in a multistage hybrid flow-shop environment. The objective is to minimize the make-span, that is, the completion time of all the tasks in the last stage. This problem is of practical interest in the textile and process industries. A genetic algorithm (GA) is developed to solve the problem. The GA is tested against a lower bound from the literature as well as against heuristic rules on a test bed comprising 400 problems with up to 100 jobs, 10 stages, and with up to five processors on each stage. For small problems, solutions found by the GA are compared to optimal solutions, which are obtained by total enumeration. For larger problems, optimum solutions are estimated by a statistical prediction technique. Computational results show that the GA is both effective and efficient for the current problem. Test problems are provided in a web site at www.benchmark.ibu.edu.tr/mpt-hfsp.     

Implementation of fractional-order electromagnetic potential through a genetic algorithm

Several phenomena present in electrical systems motivated the development of comprehensive models based on the theory of fractional calculus (FC). Bearing these ideas in mind, in this work are applied the FC concepts to define, and to evaluate, the electrical potential of fractional order, based in a genetic algorithm optimization scheme. The feasibility and the convergence of the proposed method are evaluated.     

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.     

A Forex trading system based on a genetic algorithm

In this paper, a genetic algorithm will be described that aims at optimizing a set of rules that constitute a trading system for the Forex market. Each individual in the population represents a set of ten technical trading rules (five to enter a position and five others to exit). These rules have 31 parameters in total, which correspond to the individuals’ genes. The population will evolve in a given environment, defined by a time series of a specific currency pair. The fitness of a given individual represents how well it has been able to adapt to the environment, and it is calculated by applying the corresponding rules to the time series, and then calculating the ratio between the profit and the maximum drawdown (the Stirling ratio). Two currency pairs have been used: EUR/USD and GBP/USD. Different data was used for the evolution of the population and for testing the best individuals. The results achieved by the system are discussed. The best individuals are able to achieve very good results in the training series. In the test series, the developed strategies show some difficulty in achieving positive results, if you take transaction costs into account. If you ignore transaction costs, the results are mostly positive, showing that the best individuals have some forecasting ability.     

BIANCA: a genetic algorithm to solve hard combinatorial optimisation problems in engineering

The genetic algorithm BIANCA, developed for design and optimisation of composite laminates, is a multi-population genetic algorithm, capable to deal with unconstrained and constrained hard combinatorial optimisation problems in engineering. The effectiveness and robustness of BIANCA rely on the great generality and richness in the representation of the information, i.e. the structure of populations and individuals in BIANCA, and on the way the information is extensively exploited during genetic operations. Moreover, we developed proper and original strategies to treat constrained optimisation problems through the generalisation of penalisation methods. BIANCA can also treat constrained multi-objective problems based on the construction of the Pareto frontier. Therefore, BIANCA allows us to approach very general design problems for composite laminates, but also to make a step forward to the treatment of more general problems of optimisation of materials and structures. In this paper, we describe specifically the case of optimal design of composite laminates, concerning both the theoretical formulation and the numeric resolution.     

Optimization of a highway project planning using a modified genetic algorithm

This paper proposes an optimization method for a national-level highway project planning based on a modified genetic algorithm. The proposed method adds to the existing methods by integrating various planning elements into a single system. A simulation model is used in order to determine the best investment strategy with regard to net present value, time deviation from the initial plan and discrepancy between available resources and investment costs by taking into account economical, social, traffic and political factors. The outcome is a project schedule with an optimized cash flow. The proposed method was tested using the example of the National Highway Programme in Slovenia.     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.