[15p-B414-1~11] FS.1 Focused Session "AI Electronics"

▲ [15p-B414-6] 2-opt ReRAM CiM: Travelling Salesman Problem Targeted ReRAM CiM based Simulated Annealing Using 2-opt Local Search

〇(M2)Zhongzhong Fan¹, Naoko Misawa¹, Chihiro Matsui¹, Ken Takeuchi¹ (1.Univ. Tokyo)

Keywords:Computation-in-Memory, Simulated annealing, Travelling Salesman Problem

Travelling Salesman Problem (TSP) is a famous combinatorial optimization problem that looks for the shortest tour through a city map. However, the traditional random flip search method of ReRAM Computation-in-Memory (CiM) based simulated annealing cannot work well in solving TSP due to the high unfeasible answers rate. In this paper, the 2-opt ReRAM CiM: a TSP targeted ReRAM CiM based simulated annealing using 2-opt local search is proposed. Making sure all answers are feasible by directly doing 2-opt local search on tour answer, the proposed 2-opt ReRAM CiM significantly improves TSP’s answer quality with high efficiency. Furthermore, an advanced ReRAM CiM using differential encoding is proposed, which achieves better capability on energy savings and cell error tolerance.
<quillbot-extension-portal></quillbot-extension-portal>