# An Improved Adaptive Genetic Algorithm for Two-Dimensional Rectangular Packing Problem
## 1 Introduction  
The two-dimensional rectangular packing (2 DRP) problem is often involved in the manufacturing process of furniture, glass, metal, paper products, VLSI chip design, newspapers paging, and so on [1, 2]. Consequently, optimized algorithms designed to improve the quality and efficiency of packing (therefore reducing the cost of the enterprises) are the subject of many researchers' explorations in recent years. The 2 DRP problem can be described simply as this: rectangles of different sizes are put into a large two-dimensional rectangular container (which we call the sheet) in a certain way to maximize the filling rate of the sheet. The 2 DRP is a representative NP-hard problem [3] with complex constraints, which means that there is no exact method to solve the problem in polynomial time. Thus, most researchers have devoted their efforts to fast approximate heuristics and meta-heuristics to obtain practical solutions with higher qualities. In recent decades, in order to solve the optimal or nearly optimal packing scheme of the 2 DRP problem in a compromise time and space, scholars have explored and studied many methods for solving the problem. Two types of representative approaches have been used to address the 2 DRP problem: the first solves the problem directly by using different heuristics; the second uses meta-heuristic algorithms, such as Simulated Annealing (SA) [4], Genetic Algorithm (GA) [5], Particle Swarm Optimization (PSO) [6], Ant Colony Optimization (ACO) [7], etc., combined with heuristic placement strategy. Recently, otherintroduced algorithms include whale optimization algorithm [8], dragonfly algorithm [9], naked mole-rat algorithm [10], moth flame optimization [11], etc. The component in the first approach is the layout representation for packing sequence. The bottom-left (BL) algorithm [12] proposed by [PERSON] et al. is the earliest heuristic. The main idea is to start from the top right corner of the container, making each item continuously slide as far as possible downwards and then as far as possible to the left until the item is placed in a stable position. Some BL algorithms have improved heuristic variants such as bottom-left-fill (BLF) [13], deepest bottom-left-fill (DBLF) [14], improved bottom-left (IBL) [15], and bottom-left decreasing (BLD) [16]. The lowest horizontal line algorithm (LHLA) [17] proposed by [PERSON] et al. queries the horizontal line with the lowest height when laying out the rectangle and places the rectangle on it. However, taking account of the lack of iterative optimization, in general, the packing quality of the heuristic approach is poor. In order to improve the packing quality, the key part of the second method is how to use meta-heuristics combined with a layout representation approach to optimize the packing sequence. [PERSON] et al. conducted empirical research, combining SA and GA with BL and BLF approaches [18]. The best fit algorithm (BF) [19] proposed by [PERSON] et al. describes the sheet as a set of dynamic slots, places items on the lowest available slot at each iteration step, and then combines them together. Later, [PERSON]'s team also proposed a simulated annealing enhancement to the BF algorithm [20]. [PERSON] et al. suggested an efficient deterministic heuristic [21] using the action space. [PERSON] et al. investigated an adaptive selection approach [22] without any control parameter to address the 2D rectangle packing area minimization problem. Recently, [PERSON] et al. proposed an adaptive genetic simulated annealing algorithm [23] applied to the problem of packing optimization of rectangles. In view of the premature problem of Simple Genetic Algorithm (SGA) in practical applications, it is easy to fall into local optimal solution prematurely as well as poor local search ability [24]. [PERSON] et al. [25] proposed an Adaptive Genetic Algorithm (AGA) that dynamically adjusts the crossover probability and mutation probability according to the fitness of the individual.