Probabilistic greedy algorithm solver using magnetic tunneling junctions for traveling salesman problem

Area of Science:

• Physics and Computer Science
• Hardware-accelerated optimization algorithms

Background:

• Classical combinatorial optimization methods face scalability challenges.
• Balancing efficiency and solution quality remains a key issue in large-scale optimization.

Purpose of the Study:

• To develop a probabilistic framework for combinatorial optimization using hardware true random number generators.
• To enhance greedy search algorithms with controlled stochasticity for improved performance.

Main Methods:

• Embedding spin-transfer-torque magnetic tunnel junction (STT-MTJ) based true random number generators (TRNGs) into a greedy solver.
• Utilizing a temperature parameter to control randomness and balance exploration-exploitation.

Main Results:

• The framework significantly improved solution quality and convergence speed on the traveling salesman problem compared to simulated annealing and genetic algorithms.
• Near-optimal solutions were achieved with fewer iterations and reduced computational cost on larger problem instances (up to 70 cities).

Conclusions:

• Hardware true randomness with tunable statistics offers a powerful method to enhance heuristic search algorithms.
• Integrated, energy-efficient probabilistic hardware can enable scalable optimization solutions.