総件数 : 25908 件

YUNOCAについて

本データベースは、山口大学において生産された電子的学術情報資源を学内外に無償で発信・提供することにより、学術研究の振興及び社会貢献に寄与することを目的として公開しています。

検索

お知らせ

過去のお知らせ

新着一覧

最新5件を表示

published_at 2022-03
Creators : 柴田 義大 Updated At : 2022-06-14 13:39:47
Algorithms Volume 15 Issue 6 pp. 192 -
published_at 2022-06-02
The quadratic unconstrained binary optimization (QUBO) problem is categorized as an NP-hard combinatorial optimization problem. The variable neighborhood search (VNS) algorithm is one of the leading algorithms used to solve QUBO problems. As neighborhood structure change is the central concept in the VNS algorithm, the design of the neighborhood structure is crucial. This paper presents a modified VNS algorithm called "B-VNS", which can be used to solve QUBO problems. A binomial trial was used to construct the neighborhood structure, and this was used with the aim of reducing computation time. The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg-Rendl, and on those proposed by Burer, Monteiro, and Zhang. Finally, Mann-Whitney tests were conducted using α = 0.05, to statistically compare the performance of the two algorithms. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed the best in all of the max-cut problems, regardless of problem size, and it performed the best in QUBO problems, with sizes less than 500. The results suggest that the use of binomial distribution, to construct the neighborhood structure, has the potential for further development.
Creators : Pambudi Dhidhi | Kawamura Masaki Publishers : Multidisciplinary Digital Publishing Institute Updated At : 2022-06-13 10:46:59