可能性贪的算法解决者使用磁道连接点来解决旅行销售员问题
Ran Zhang1, Xiaohan Li1, Caihua Wan2,3,4
1Beijing National Laboratory for Condensed Matter Physics, Institute of Physics, Chinese Academy of Sciences, Beijing, China.
Nature communications
|December 4, 2025
概括
这项研究引入了一个新的概率框架,使用硬件真随机数生成器来增强组合优化. 这种方法提高了解决方案的质量和融合速度,用于复杂的问题,如旅行销售员问题.
科学领域:
- 物理学和计算机科学 物理和计算机科学
- 硬件加速优化算法 硬件加速优化算法
背景情况:
- 经典的组合优化方法面临着可扩展性挑战.
- 在大规模优化中,平衡效率和解决方案质量仍然是一个关键问题.
研究的目的:
- 开发一个概率框架,以使用硬件真正的随机数生成器进行组合优化.
- 以控制的随机性来增强贪的搜索算法,以提高性能.
主要方法:
- 在一个贪的解决器中嵌入基于自旋转转矩磁道结 (STT-MTJ) 的真随机数生成器 (TRNG).
- 使用温度参数来控制随机性和平衡勘探-开采.
主要成果:
- 与模拟和遗传算法相比,该框架显著提高了旅行销售员问题的解决方案质量和融合速度.
- 在较大的问题实例 (多达70个城市) 中,通过更少的代实现了近乎最佳的解决方案,并降低了计算成本.
结论:
- 具有可调整统计数据的硬件真随机性提供了一种强大的方法来增强启发式搜索算法.
- 集成的,节能的概率硬件可以实现可扩展的优化解决方案.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
264
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
264
Biot-Savart Law: Problem-Solving
3.8K
The magnitude and direction of a magnetic field created by a steady current can be calculated using the Biot-Savart law.
Consider a mobile phone battery bank as a source of steady current, which flows through the wire connected between the two. What is the magnitude of the magnetic field created by this current at a field point P?
To estimate the magnitude of the total magnetic field, we first consider a small current element of length dl, at a distance r from the field point. Now the following...
Consider a mobile phone battery bank as a source of steady current, which flows through the wire connected between the two. What is the magnitude of the magnetic field created by this current at a field point P?
To estimate the magnitude of the total magnetic field, we first consider a small current element of length dl, at a distance r from the field point. Now the following...
3.8K
Ampere-Maxwell's Law: Problem-Solving
1.1K
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the...
1.1K
Statically Indeterminate Problem Solving
670
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
670
Distributed Loads: Problem Solving
1.1K
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
1.1K
Machines: Problem Solving I
661
A toggle clamp is a mechanical device commonly used for holding and clamping objects in various applications, such as woodworking, metalworking, and assembly operations. Consider a toggle clamp subjected to a force of 200 N at the handle. The vertical clamping force can be calculated, provided the dimensions of the toggle clamp are known.
The toggle clamp system is a machine structure consisting of movable, pin-connected multi-force members that form a stabilized system to transmit forces. The...
The toggle clamp system is a machine structure consisting of movable, pin-connected multi-force members that form a stabilized system to transmit forces. The...
661


