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

摘要

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.