Number partitioning as a random energy model
Number partitioning as a random energy model
复制标题
DOI：
10.1088/1742-5468/2004/04/p04003
复制
发表时间：
2004-04-01
影响因子：
2.4
通讯作者：
Mertens, S
中科院分区：
文献类型：
--
作者：
Bauke, H;Franz, S;Mertens, S
数字划分是组合优化中的一个经典问题。从物理角度来说，它相当于长程反铁磁伊辛自旋玻璃。已经被严格证明，数字划分的低能量表现得像不相关的随机变量。我们声称，能量轴上几乎所有位置的相邻能级都是不相关的，并且能量上相邻的配置也是不相关的。显然，优化算法可以利用的几何结构（配置）和能量之间没有关系。这种数字划分的“局部随机能量”图景得到了数值模拟和启发式论证的证实。
Number partitioning is a classical problem from combinatorial optimization. In physical terms it corresponds to a long range anti-ferromagnetic Ising spin glass. It has been rigorously proven that the low lying energies of number partitioning behave like uncorrelated random variables. We claim that neighbouring energy levels are uncorrelated almost everywhere on the energy axis, and that energetically adjacent configurations are uncorrelated, too. Apparently there is no relation between geometry (configuration) and energy that could be exploited by an optimization algorithm. This 'local random energy' picture of number partitioning is corroborated by numerical simulations and heuristic arguments.