基于磁隧道结概率性贪婪算法的旅行商问题求解器：硬件随机性驱动的组合优化新范式

《Nature Communications》：Probabilistic greedy algorithm solver using magnetic tunneling junctions for traveling salesman problem

为解决组合优化问题中效率与求解质量的平衡难题，研究人员开发了一种基于磁隧道结（MTJ）真随机数发生器（TRNG）的概率性贪婪算法求解器。该研究通过调控MTJ的随机开关特性，动态调整算法探索与利用的平衡，在旅行商问题（TSP）求解中展现出优于模拟退火和遗传算法的收敛速度与求解质量，为大规模组合优化问题提供了硬件高效解决方案。

　　

在人工智能、物流规划和网络设计等领域，组合优化问题如同隐藏在数据迷宫中的宝藏，寻找最优解的过程既充满挑战又极具价值。其中，旅行商问题（TSP）作为组合优化的经典代表，要求寻找访问所有城市的最短路径，随着城市数量增加，解决方案的数量呈指数级增长，使得传统算法难以在合理时间内找到最优解。确定性算法如动态规划和分支定界法在小规模问题上表现优异，但面对大规模复杂问题时往往陷入局部最优解而无法逃脱。

近年来，研究者开始将随机性引入优化算法，诞生了模拟退火、遗传算法等随机优化方法。这些方法通过引入随机性来增强搜索空间的探索能力，但其效果很大程度上依赖于所使用的随机数发生器（RNG）的质量和可配置性。传统的伪随机数发生器缺乏动态调整分布特性的灵活性，限制了算法在不同优化场景中的适应性。

正是在这样的背景下，中国科学院物理研究所联合多家研究机构在《Nature Communications》上发表了一项创新研究，他们利用磁隧道结（MTJ）的物理随机性，开发出具有概率分布可配置功能的真随机数发生器，并将其嵌入贪婪算法框架，构建了一种新型的概率性贪婪算法求解器，为组合优化问题提供了新的解决思路。

关键技术方法包括：采用钴铁硼/镁O基STT-MTJ器件结构，通过脉冲电流控制磁化随机切换实现真随机数生成；利用NI PXIe系统搭建测量平台实现多MTJ并行控制；通过切换概率的sigmoidal函数关系（P_sw=1/(1+e^-b(V+c))）精确调控随机分布；针对Burma14（14城市）和st70（70城市）TSP问题实例，将MTJ-TRNG与概率选择机制（P_i+1∝exp(-d_NN/k_BT)）集成，通过温度参数k_BT动态平衡探索与利用。

MTJ-TRNG的性能表征

研究团队首先对基于自旋转移矩（STT）的MTJ器件进行了详细表征。器件结构包含CoFeB/MgO/CoFeB核心层，通过垂直磁场扫描获得的R-H磁滞回线显示高低阻态间的锐利切换，隧道磁阻（TMR）比达到175%，确保了电阻状态的可靠区分。在电流脉冲作用下，MTJ表现出随机切换行为，切换概率与写入电压呈sigmoidal关系，通过调节电压可在25%-81%范围内精确控制切换概率，为可配置概率分布提供了物理基础。

概率分布可配置的TRNG

通过将四个MTJ连接到NI PXIe系统，研究人员实现了概率分布可配置的真随机数生成。该系统能够产生符合高斯分布、均匀分布、指数衰减分布等多种概率分布的随机数，KL散度和均方误差分析表明生成分布与理论分布高度一致。相邻相关性分析显示生成的随机数具有统计独立性，满足概率算法对随机质量的要求。这种可配置性使TRNG能够适应不同优化场景的需求。

概率性贪婪算法机制

该研究的核心创新在于将MTJ-TRNG嵌入贪婪算法框架，通过温度参数k_BT动态调节城市选择概率。当k_BT趋近零时，算法退化为确定性贪婪算法，总是选择最近城市；当k_BT极大时，选择概率均匀分布，类似于随机搜索；在中间值范围（如40-60），算法能在探索和利用间取得最佳平衡。选择概率定义为P_i+1∝(1-b_i)exp(-d_NN/k_BT)，其中b_i表示城市可访问性，确保最短路径具有最高被采样概率。

TSP求解性能评估

在Burma14问题上的实验结果显示，概率性贪婪算法在k_BT=40-60范围内能稳定找到最优解，在1000次迭代内实现收敛。与经典贪婪算法相比，新方法获得的路径更接近最优解。在70城市规模的st70问题上，算法同样展现出优越性能，在k_BT=1.3时收敛速度最快，且显著优于模拟退火和遗传算法。值得注意的是，由于MTJ-TRNG的任意概率分布可配置性，概率性贪婪算法能同时考虑所有未访问城市，而模拟退火每次只能评估两城市交换情况，使新方法能处理更高程度的纠缠问题，从而加快收敛速度。

硬件实现与扩展性

研究团队进一步提出了基于MTJ阵列的TSP求解器硬件设计方案，该设计可利用MTJ阵列的固有随机性，按需生成任意长度的随机数。性能对比表明，当前基于NI-PXIe的 prototype 平台采样率为0.5MHz，求解14城市TSP需20ms，而预计的ASIC实现可将采样率提升至≥100MHz，求解时间缩短至≤0.1ms，能耗降低至微焦耳级别。算法仅需O(log₂N)个MTJ编码N选择分布，辅助内存需求为O(N)，远低于玻尔兹曼机或伊辛机的O(N²)参数存储。

该研究通过将MTJ的真随机性与贪婪算法结合，创建了一种能动态调整随机性水平的概率优化框架。这种方法不仅显著提升了TSP问题的求解效率和质量，更重要的是为硬件加速的组合优化开辟了新途径。概率性决策过程与大型语言模型中的自回归采样机制具有概念相似性，预示着该技术在人工智能推理和生成任务中的广泛应用前景。随着集成电路技术的进步，这种基于自旋电子学的概率计算架构有望在人工智能、物流优化、网络规划等领域发挥重要作用，为解决复杂优化问题提供高效节能的硬件解决方案。