带平衡约束的圆形packing问题解空间结构分析

带平衡约束的packing问题属于NP-hard问题,不同问题的函数往往对应不同的解空间结构,解空间的结构对算法的寻优搜索效果有很大影响.以一类2D带平衡约束的圆形packing问题(转动圆桌平衡摆盘问题)为例,利用主元分析,对用进化算法求解的该问题的解空间结构进行分析,给出可视化主元地貌图,指出该问题的主元解空间结构是一种极限突变和对称的多模态的地貌结构.该解空间结构可以为构造具有针对性的新算法或选择算法提供理论依据.

Analyses of solution space structure of circles packing problem with constraints of equilibrium

Packing problem with constraints of equilibrium belongs to NP-hard problem.Functions of different problems usually correspond to different solution spaces structures,and the structure of the solution space has great influence on the effectiveness of optimization and search for the algorithm.Taking a class of 2D circles packing problem(equilibrium disk problem of rotating circle table) with the equilibrium constraint for instance,principal component analysis is used to analyze the structure of solution space obtained by evolutionary algorithm and the visual landscape is given.It is indicated that the solution space structure of the problem is a limit mutation and symmetric multi-modal landscape structure.The solution space structure provides a theoretical basis for constructing new special algorithms or selecting algorithms.