BOLTZMANN MACHINES FOR TRAVELING SALESMAN PROBLEMS
BOLTZMANN MACHINES FOR TRAVELING SALESMAN PROBLEMS
复制标题
DOI：
10.1016/0377-2217(89)90355-x
复制
发表时间：
1989-03-06
影响因子：
6.4
通讯作者：
KORST, JHM
中科院分区：
文献类型：
--
作者：
AARTS, EHL;KORST, JHM
玻尔兹曼机被提议作为（顺序）模拟退火算法的大规模并行替代方案。我们的方法是针对旅行商问题量身定制的，但它也可以应用于更一般的组合优化问题。对于旅行商问题的两个不同的 0-1 编程公式（作为线性和二次分配问题），结果表明，通过将相应的 0-1 变量映射到玻尔兹曼机的逻辑计算元件上，并将与 0-1 编程公式相对应的成本函数转换为与玻尔兹曼机相关的一致函数，可以获得接近最优的解决方案。给出了两个问题实例的计算机模拟结果，即分别针对 10 个城市和 30 个城市。
Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0–1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0–1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0–1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.