面向布局问题求解的混合全局优化算法研究

A mixed global optimization algorithm (MGOA) for packing problems

布局问题属于 NP完全问题。由于布局函数的病态性状 ,传统的优化算法很难解决此问题。遗传算法、模拟退火算法等对全局优化展示了一定的前景 ,但是它们的求解精度和效率不能令人满意。本文将启发式随机搜索策略和局部优化算法相结合 ,构造了混合全局优化算法 (MGOA)来解决这一困难。通过典型测试函数与经典遗传算法 ,模拟退火算法 ,复合形法进行比较验算 ,表明该算法具有优良的求解质量和较好的求解效率 ;并以旋转卫星舱布局的简化模型为背景 ,建立多目标优化数学模型 ,通过一个已知最优解的布局算例与遗传算法和乘子法的计算结果比较 ,该算法求解的质量和效率更优。表明此算法在布局优化中具有应用潜力。

Packing problems are categorized as NP-complete. The traditional optimization methods have difficulties in dealing with such problems effectively due to the nature of the ill-conditioned functions of the problems. Genetic Algorithms (GA) and Simulation Annealing Algorithms (SAA) have shown some promising for global optimization, but their efficiency to locate a precise result are not quite satisfied. This paper, combining a heuristic random searching strategy with local optimal algorithm, proposes and develops a composite algorithm named Mixed Global Optimization Algorithm (MGOA) to overcome the difficulties. By comparison with an original GA and SAA and a Complex Method on some testing functions, MGOA shows very good global results in terms of high precision and efficiency. A multi-object optimization model is formulated on simplified satellite cabin packing problem. By comparison on a case of such packing problem with known optimal solution, MGOA is superior to the Multiplier Algorithm and an Improved GA in term of solution quality and efficiency. Therefore, the proposed MGOA has shown some potential to deal with packing problems with good expectation.