An Evolutionary Ising Optimization Framework for Unconstrained Binary Quadratic Programming

doi:10.1109/TEVC.2025.3566963

Return

An Evolutionary Ising Optimization Framework for Unconstrained Binary Quadratic Programming

2025-05-07

PRE

DOI：10.1109/TEVC.2025.3566963

Original

Original request for help

Save

Abstract

En 中文

An Ising machine (IM), as a type of analog computer tailored for tackling intractable combinatorial optimization problems, has attracted remarkable attention in recent years. In contrast to the blossoming field of bespoke IM hardware, developing metaheuristics from IMs remains largely uninvestigated. Here, we propose a physics-inspired evolutionary computation paradigm, termed the Ising optimization framework (IOF); it comprises a unique Ising algorithm and a hybrid annealing scheme, which together are well-suited for solving quadratic unconstrained binary optimization (QUBO) problems embedded in Ising system energy. The Ising algorithm leverages a set of iterated self-mapping functions to evolve an Ising-spin swarm, enabling efficient energy minimization in artificial Ising systems while mitigating detrimental chaos. Complementing the algorithm, a hybrid annealing scheme integrating singular value dropout, bifurcation control, and a nudging strategy, is devised to augment the overall optimization capacity. The effectiveness of the IOF is validated on various Ising and Max-cut problems with decision variables ranging from 625 to 5000 in number. In comparison to four major types of methods for solving QUBOs, including IM simulations, nature-inspired algorithms, a state-of-the-art heuristic, and the commercial solver Gurobi, the IOF consistently demonstrates notable optimization quality and computational efficiency. This article provides a theoretical foundation and practical guidelines for bridging Ising-inspired approaches with evolutionary computation, offering an evolutionary perspective on Ising optimizations and suggesting a fertile avenue for future research and application.

Keywords:

Energy minimization

Ising model

nature-inspired metaheuristic

quadratic unconstrained binary optimization (QUBO)