검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers 고체 어닐러의 2차 배낭 문제에 대한 고품질 솔루션을 얻기 위한 하이브리드 정수 인코딩 방법

Satoru JIMBO, Daiki OKONOGI, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA

  • 조회수

    0

  • 이것을 인용

요약 :

QKP(Quadratic Knapsack Problem)를 QUBO(Quadratic Unconstrained Binary Optimization) 형식으로 공식화하려면 배낭 용량 제약 조건을 전체 에너지 함수로 변환하고 통합하는 정수 변수를 도입해야 합니다. QUBO에서는 이 정수 변수가 보조 바이너리 변수로 인코딩되며, 이에 사용되는 인코딩 방법은 SA(Simulated Annealing)의 동작에 큰 영향을 미칩니다. QKP 인스턴스에 대한 SA의 효율성을 향상시키기 위해 본 논문에서는 먼저 기존 바이너리 및 단항 인코딩 방법으로 인코딩된 어닐링 프로세스를 시각화하고 분석했습니다. 이 분석을 바탕으로 우리는 두 가지 장점을 모두 활용하는 새로운 하이브리드 인코딩(HE)을 제안했습니다. 제안된 HE는 평가에서 실행 가능한 솔루션을 얻었으며 중소 규모 모델에서 다른 것보다 뛰어난 성능을 보였습니다.

발행
IEICE TRANSACTIONS on Information Vol.E105-D No.12 pp.2019-2031
발행일
2022/12/01
공개일
2022/05/26
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2022PAP0006
원고의 종류
Special Section PAPER (Special Section on Forefront Computing)
범주

작성자

Satoru JIMBO
  Tokyo Institute of Technology
Daiki OKONOGI
  Tokyo Institute of Technology
Kota ANDO
  Hokkaido University
Thiem Van CHU
  Tokyo Institute of Technology
Jaehoon YU
  Tokyo Institute of Technology
Masato MOTOMURA
  Tokyo Institute of Technology
Kazushi KAWAMURA
  Tokyo Institute of Technology

키워드