Quantization-Based Optimization: A New Algorithm Based on Number Theory
Researchers developed a quantization-based optimization algorithm that outperforms conventional algorithms in solving hard optimization problems
Effective combinatorial optimization algorithms for solving NP-hard problems are essential for using machine learning to overcome engineering challenges. Conventional algorithms such as simulated annealing and quantum annealing suffer from low convergence speeds and poor optimization performance for NP-hard problems. Now, researchers from ETRI, Korea, have developed a novel quantization-based optimization algorithm using number theory, which significantly outperforms conventional algorithms and finds feasible solutions even where conventional algorithms fail, marking a significant achievement.
Combinatorial optimization problems, in which the objective is to find an optimal solution from a finite set of possible solutions, play a critical role in many fields like finance, artificial intelligence, and very large-scale integration (VLSI). Developing effective algorithms for solving NP-hard problems is crucial for using machine learning to overcome engineering challenges in these fields. NP-hard problems, such as the traveling salesman problem (TSP), the knapsack problem, and 3D packing problems, are especially tough because of their complexity and large solution spaces.
Conventional optimization algorithms, like simulated annealing (SA) and quantum annealing (QA), use stochastic or random properties to slowly converge to a final solution while minimizing an objective function. These algorithms often require multiple attempts to find a solution for NP-hard problems and suffer from slow convergence speeds and reduced optimization performance.
To address these limitations, researchers led by Adjunct Professor Jinwuk Seok from the Artificial Intelligence Research Laboratory at the Electronics and Telecommunications Research Institute, Korea, developed a novel optimization algorithm based on number theory, called quantization-based optimization. “Traditional optimization analyses rarely utilize number theory, which has kept quantization-based optimization largely unexplored. Our study applied concepts from number and measure theories to tackle highly complicated NP-hard problems,” explains Dr. Seok. Their study was published in the ETRI Journal on November 22, 2023.
The novel algorithm begins by selecting a random input point to evaluate an objective function. Then, the value of the objective function is quantized with a pre-determined quantization parameter, and the blind random search algorithm, which is similar to QA, selects another input point. Later, the proposed algorithm compares the quantized value of this new point with the quantized value of the previous point. If the previous point’s quantized value is greater than or equal to that of the new point, then the new point is considered the better solution and becomes the new starting point for the next iteration. The quantization parameter is then updated, and the new initial point’s quantized value is requantized. This process is repeated until the algorithm finds an optimal solution. Notably, the new algorithm automatically provides a predetermined objective function with low quantization resolution, whereas in QA, this function must be set manually.
The researchers compared the performance of the proposed algorithm with those of SA and QA in TSP simulations for 100 cities. The results revealed that conventional SA and QA could not find feasible solutions, while the proposed algorithm could find feasible solutions even when the number of cities exceeded 100. Moreover, it could find solutions even for 200 cities, where conventional algorithms got stuck at the initial point. The proposed algorithm also required fewer search iterations than SA and QA. Notably, it can be applied to both discrete combinatorial and classical continuous optimization problems.
“Our optimization technique can be a valuable tool in applications such as optimal synthesis of functions or modules in VLSI, development of pharmaceuticals by optimal protein combination, and also in artificial intelligence and quantum computing,” remarks Dr. Seok.
Overall, this innovative algorithm could lead to more efficient optimization in complex engineering problems, potentially leading to significant economic benefits.
Reference
Title of original paper: Numerical analysis of quantization-based optimization
Journal: ETRI Journal
About the institute
Established in 1976, ETRI is a non-profit government-funded research institute and is one of the leading research institutes in the wireless communications domain. It has more than 2500 patents filed. Equipped with state-of-the-art labs, this institute strives for social and economic development through technology research.
About the author
Jinwuk Seok received his B.S. and M.S. degrees in electrical control engineering in Seoul, Korea, in 1993 and 1995, respectively, and his Ph.D. degree in electrical engineering in Seoul, Korea, in 1998. He has been a principal member of the engineering staff at the Electronics and Telecommunications Research Institute (ETRI) in Korea since 2000 and an adjunct professor of the computer software engineering department at the University of Science and Technology (UST) in Korea since 2009. His research interests include artificial intelligence, machine learning, nonlinear dynamics, and stochastic nonlinear control.
