A hybrid grouping genetic algorithm for bin packing

The grouping genetic algorithm (GGA) is a genetic algorithm heavily modified to suit the structure of grouping problems. Those are the problems where the aim is to find a good partition of a set or to group together the members of the set. The bin packing problem (BPP) is a well known NP-hard grouping problem: items of various sizes have to be grouped inside bins of fixed capacity. On the other hand, the reduction method of Martello and Toth, based on their dominance criterion, constitutes one of the best OR techniques for optimization of the BPP to date.In this article, we first describe the GGA paradigm as compared to the classic Holland-style GA and the ordering GA. We then show how the bin packing GGA can be enhanced with a local optimization inspired by the dominance criterion. An extensive experimental comparison shows that the combination yields an algorithm superior to either of its components.     

Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems

The majority of Combinatorial Optimization Problems (COPs) are defined in the discrete space. Hence, proposing an efficient algorithm to solve the problems has become an attractive subject in recent years. In this paper, a meta-heuristic algorithm based on Binary Particle Swarm Algorithm (BPSO) and the governing Newtonian motion laws, so-called Binary Accelerated Particle Swarm Algorithm (BAPSA) is offered for discrete search spaces. The method is presented in two global and local topologies and evaluated on the 0–1 Multidimensional Knapsack Problem (MKP) as a famous problem in the class of COPs and NP-hard problems. Besides, the results are compared with BPSO for both global and local topologies as well as Genetic Algorithm (GA). We applied three methods of Penalty Function (PF) technique, Check-and-Drop (CD) and Improved Check-and-Repair Operator (ICRO) algorithms to solve the problem of infeasible solutions in the 0–1 MKP. Experimental results show that the proposed methods have better performance than BPSO and GA especially when ICRO algorithm is applied to convert infeasible solutions to feasible ones.     

Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics

The tradeoff between the speed and quality of the solutions obtained by various construction and local search algorithms for the elementary bin packing problem (BPP) are analyzed to obtain useful information for designing algorithms for real-world problems that can be modeled as BPPs. On the basis of intensive computational experiments, we observe that the framework of a solution (i.e., a part of a solution consisting of large items or items with tight constraints) should be constructed in the early stages of a local search. New local search algorithms are proposed as empirical support for the observation.     

New perspectives in VLSI design automation: deterministic packing by Sequence Pair

In the paper we consider a problem of packing rectangular blocks on a plane, which is known as Block Packing Problem (BPP). This problem is a central issue of the modern VLSI chips design methods. Basing on a new interpretation of the Sequence-Pair representation of the packing solution-space, which is based on Complementary Mirror Constraint Graphs (CMCG), we develop the efficient method of neighborhood exploration. This method might be able to improve the efficiency of other neighborhood-based search methods, such as simulated annealing or tabu search, as well as, to construct efficient heuristics. We illustrate application of the developed method by constructing a heuristic algorithm for solving BPP and comparing its efficiency and effectiveness to the algorithms commonly used so far.     

An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem

In this paper we consider the two-dimensional (2D) rectangular packing problem, where a fixed set of items have to be allocated on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left (BL) stability, are hybridised with three meta-heuristic algorithms (genetic algorithms (GA), simulated annealing (SA), naı̈ve evolution (NE)) and local search heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms, their performance is compared to random search (RS) and heuristic packing routines.     

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.     

Hybrid algorithm for the two-dimensional rectangular layer-packing problem

In this paper, a rectangular layer-packing algorithm (RLPA) combined with modified genetic algorithm (GA) or particle swarm optimization (PSO) algorithm is developed to solve the problem with emerging restraints, which is raised from the two-dimensional rectangular packing problem with some small rectangles that need to be packed into a fixed rectangular object. RLPA is designed from the BL algorithm and lowest horizontal line algorithm. GA and PSO are also modified to satisfy the constraint conditions. Best GA or PSO parameters are obtained by conducting experiments on some typical instances. The results are also compared, which validate the quality of the solutions and show the effectiveness of the modified algorithm.     

Multiple-type,two-dimensional bin packing problems: Applications and algorithms

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.     

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 heuristic for solving large bin packing problems in two and three dimensions

The more-dimensional bin packing problem (BPP) considered here requires packing a set of rectangular-shaped items into a minimum number of identical rectangular-shaped bins. All items may be rotated and the guillotine cut constraint has to be respected. A straightforward heuristic is presented that is based on a method for the container loading problem following a wall-building approach and on a method for the one-dimensional BPP. 1,800 new benchmark instances are introduced for the two-dimensional and three-dimensional BPP. The instances include more than 1,500 items on average. Applied to these very large instances, the heuristic generates solutions of acceptable quality in short computation times. Moreover, the influence of different instance parameters on the solution quality is investigated by an extended computational study.     

A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

Given a set of rectangular pieces and a container of fixed width and variable length, the two-dimensional strip packing problem (2D-SPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimised. Until now mainly heuristics, for example genetic algorithms (GA), were proposed for the 2D-SPP which use encoded solutions that are manipulated by standard operators. In this paper a GA for the 2D-SPP is suggested that works without any encoding of solutions. Rather fully defined layouts are manipulated as such by means of specific genetic operators. Two additional constraints, namely the orientation constraint and the guillotine constraint, can be taken into account. The GA is subjected to a comprehensive test using benchmark instances with up to 5000 pieces. Compared to eleven competing methods from the literature the GA performs best.     

含不相关机的动态可重入柔性流水车间问题的混合DABC-GA算法

为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。     

An imperialist competitive algorithm for multi-objective U-type assembly line design

Many assembly lines are now being designed as U-type assembly lines rather than straight lines because of the pressure of the just-in-time (JIT) manufacturing concept. Since any type of an assembly line balancing problem is known to be NP-hard, there has been a growing tendency toward using evolutionary algorithms to solve such a hard problem. This paper proposes a new population-based evolutionary algorithm, namely imperialist competitive algorithm (ICA) inspired by the process of socio-political evolution, to address the multi-objective U-type assembly line balancing problem (UALBP). Two considered objectives are to minimize the line efficiency and minimize the variation of workload. Furthermore, the Taguchi design is applied to tune the effective parameters of the proposed ICA. To demonstrate the efficiency of the proposed algorithm, the associated results are compared against an efficient genetic algorithm (GA) in the literature over a large group of benchmarks taken from the literature. The computational results show that the proposed ICA outperforms GA.     

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.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

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.     

Application of honey-bee mating optimization algorithm on clustering

Cluster analysis is one of attractive data mining technique that use in many fields. One popular class of data clustering algorithms is the center based clustering algorithm. K-means used as a popular clustering method due to its simplicity and high speed in clustering large datasets. However, K-means has two shortcomings: dependency on the initial state and convergence to local optima and global solutions of large problems cannot found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. Over the last decade, modeling the behavior of social insects, such as ants and bees, for the purpose of search and problem solving has been the context of the emerging area of swarm intelligence. Honey-bees are among the most closely studied social insects. Honey-bee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm is inspired by the process of marriage in real honey-bee. Honey-bee has been used to model agent-based systems. In this paper, we proposed application of honeybee mating optimization in clustering (HBMK-means). We compared HBMK-means with other heuristics algorithm in clustering, such as GA, SA, TS, and ACO, by implementing them on several well-known datasets. Our finding shows that the proposed algorithm works than the best one.     

A robust parameter design for multi-response problems

Most real world search and optimization problems naturally involve multiple responses. In this paper we investigate a multiple response problem within desirability function framework and try to determine values of input variables that achieve a target value for each response through three meta-heuristic algorithms such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Each algorithm has some parameters that need to be accurately calibrated to ensure the best performance. For this purpose, a robust calibration is applied to the parameters by means of Taguchi method. The computational results of these three algorithms are compared against each others. The superior performance of SA over TS and TS over GA is inferred from the obtained results in various situations.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

The mixed vertex packing problem

We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The well-known vertex packing model arises as a subproblem or relaxation of many 0-1 integer problems, whereas the mixed vertex packing model arises as a natural counterpart of vertex packing in the context of mixed 0-1 integer programming. We describe strong valid inequalities for the convex hull of solutions to the MVPP and separation algorithms for these inequalities. We give a summary of computational results with a branch-and-cut algorithm for solving the MVPP and using it to solve general mixed-integer problems. Received: June 1998 / Accepted: February 2000?Published online September 20, 2000