k-着色问题及其均场退火求解算法

A Mean Field Annealing-Based Algorithm for k-Colorable Problem

均场退火方法既可以看作是一种新的神经网络计算模型 ,又可视为是对模拟退火的重大改进 .该文把具有相邻约束的多层通孔最小化问题转换为更具广泛意义的 k-着色问题 ,并提出了 k-着色问题的均场退火求解算法 .算法在线段相交图模型的基础上 ,提出了相邻矩阵和交叠矩阵等概念 ,并利用换位矩阵 ,将问题映射为相应的神经网络 ,再构造了该问题的能量函数 .能量函数中的目标项、违背交叠约束的惩罚项、违背相邻约束的惩罚项和神经元归一化处理保证了网络能够求解到一个合法解 .实验结果表明 ,这是一个有效的算法 .

The mean field annealing approach is a new neural network model, which improves the simulated annealing approach greatly. In the paper, the via minimization problem in multi layer routing with adjacent constraints is translated to a k colorable problem which has more general meanings, and a mean field annealing algorithm for the k colorable problem is proposed. On the basis of the segment crossing graph model, the adjacent matrix and the crossing matrix are introduced. A permute matrix of binary variables is used to map the problem to the neural network, and then the energy function is presented. The object item, crossing constrained item and adjacency constrained item in the energy function, and the normalization of neurons prove that the effective result can be gotten. The experimental results show that it is an effective method.