求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard问题,其求解算法多为启发式算法。该文侧重于构造布局求解算法中定位函数(规则)的优化,将模拟退火算法的思想融入到遗传算法中,提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。

An adaptive algorithm for rectangular packing problems

Rectangular packing problem is NP-Hard and normally solved by heuristic algorithms. By combining simulated annealing with genetic algorithm, an adaptive algorithm for rectangular packing problem is presented. The placer.aent function for the structural algorithm is studied. Some strategies such as adaptive crossover, mutation and the probability of accepting poor solution can be used in order to optimize the parameter of placement function. The algorithm through two way determination initial population＇s number has the strong compatibility. In the algorithm search＇s later period, the most different individual is used to carry on crossover operation, thus maintains the population＇s multiplicity. The experimental results show that the algorithm is reasonable and efficient with comparing ones of other algorithms.