Optimization via Rejection-Free Partial Neighbor Search

Autor:	Chen, Sigeng, Rosenthal, Jeffrey S., Dote, Aki, Tamura, Hirotaka, Sheikholeslami, Ali
Rok vydání:	2022
Předmět:	Mathematics - Optimization and Control Statistics - Methodology
Druh dokumentu:	Working Paper
Popis:	Simulated Annealing using Metropolis steps at decreasing temperatures is widely used to solve complex combinatorial optimization problems. In order to improve its efficiency, we can use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by considering all the neighbors at every step. As a solution to avoid the algorithm from becoming stuck in local extreme areas, we propose an enhanced version of Rejection-Free called Partial Neighbor Search (PNS), which only considers random parts of the neighbors while applying Rejection-Free. We demonstrate the superior performance of the Rejection-Free PNS algorithm by applying these methods to several examples, such as the QUBO question, the Knapsack problem, the 3R3XOR problem, and the quadratic programming. Comment: 24 pages with 2 more pages of reference, 9 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2205.02083 Zobrazit plný text záznamu View this record from Arxiv