A quasi-human strategy-based improved basin filling algorithm for the orthogonal rectangular packing problem with mass balance constraint. (May 2017)

• Record Type: Journal Article
• Authors: Liu, Jingfa; Li, Jian; Lü, Zhipeng; Xue, Yu
• Is Part Of: Computers & industrial engineering. Volume 107(2017)
• Page Start: 196
• Page End: 210
• Publication Date: 2017-05
• Subjects: Packing -- Basin filling algorithm -- Corner-occupying strategy -- Quasi-human strategy -- Heuristic algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.03.019
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The problem is converted into an unconstrained optimization problem by the quasi-physical strategy. A feasible solution of the problem is obtained by an improved basin filling algorithm. A new update mechanism of the histogram function in the energy landscape paving is proposed. A quasi-human corner-occupying strategy and local movement mechanism are used to update the layouts. The proposed algorithm has refreshed the current best results in literature. Abstract: Under the background of layout optimization of the satellite module, we study the orthogonal rectangle packing problem (ORPP) with mass balance constraint, which is an NP-hard problem. Based on the quasi-physical strategy, we convert the problem into an unconstrained optimization problem. The major challenge of solving this problem is that the objective function being optimized is characterized by a multitude of local minima separated by high-energy barriers. Basin filling (BF) algorithm is a new heuristic global optimization algorithm, which combines the energy landscape paving (ELP), based on Monte Carlo sampling, and local search, based on the gradient method. We use the improved basin filling (IBF) algorithm to solve the ORPP with mass balance constraint. In the IBF algorithm, in order to avoid the ELP falling into narrow and deep valleys of energy landscape, a new update mechanism of the histogram function in the ELP is proposed. In addition, a quasi-human corner-occupying strategy and a local movement strategy, based on the adaptive gradient method with retreat and acceleration, are used to update the layouts. Experimental results show that the proposed algorithm is an effective method for solving the ORPP with mass balance constraint.